[PDF] Cours 1 — 30 septembre 1.1 Introduction

View - Download Cours 1 — 30 septembre 1.1 Introduction

Previous PDF

Next PDF

Introduction aux modeles graphiques 2009/2010

Cours 1 | 30 septembre

Enseignant: Francis Bach Scribe: Marc Weber, Ruocong ZhangPour information { Page web du courshttp://www.di.ens.fr/~fbach/courses/fall2009/

1.1 Introduction

1.1.1 Problemes poses

Lorsque l'on veut realiser des modelisations statistiques de donnees complexes, on se trouve confronte a des questions issues de deux problematiques principales : { Comment gerer la complexite des donnees a traiter? { Comment inferer les proprietes globales a partir de modeles locaux? Les problemes rencontres sont de trois types : la representation des donnees (Comment obtenir un modele global a partir d'un modele local), l'inference des lois (Comment utiliser le modele), et l'apprentissage des modeles (Quels sont les parametres du modele?).

1.1.2 Exemples

{ Image : soit une image monochromatique composee de 100100 pixels. On considere une variable aleatoire discrete par pixel, on a doncn= 10000. Le modele utilise pourra

^etre une grille de cette forme :{ Bioinformatique : soit une longue sequence de taille 10000 de base ADN. On considere

une variable aleatoire discrete par base de cette sequence (en general a valeurs dans fA;C;G;Tg). Le modele utilise pourra ^etre une cha^ne de Markov : 1-1

Cours 1 | 30 septembre 2009/2010

{ Finance : On considere des actions evoluant dans un domaine temporel discret ou l'on dispose des valeurs aux instants n. Il est legitime de supposer que l'evolution d'une action a l'instant n peut dependre de l'evolution d'une autre action au tempsn1.

Pour un modele simplie a deux actions, on aura donc le graphe de dependance suivant :{ Traitement de la parole : On considere les syllabes d'un mot et la maniere dont elles

sont interpretees par l'oreille humaine ou par un ordinateur. A chaque syllabe d'un mot correspond un son aleatoire (la m^eme syllabe sera prononcee dieremment chaque fois). On cherche alors a remonter au mot prononce en fonction des sons entendus.

Dans ce cas il est possible d'utiliser un modele de Markov cache.{ Texte : soit un texte de 1000000 mots. On modelise le texte par un vecteur ou chaque

composante du vecteur est egale au nombre d'occurences de chaque mot cle. On utilise ici le modele\bag of words", qui est assez faible car il ne prend pas en compte l'ordre des mots rencontres dans le texte, mais il est souvent susant en pratique. L'algorithme utilise pour la classication (par exemple spam vs non spam) est le\naive Bayes". On peut deja constater qu'il est trop faible de considerer un modele ou les variables aleatoires sont toutes independantes les unes des autres et qu'il est trop co^uteux de supposer que chaque variable est liee a toutes les autres. Il faudra donc faire des hypotheses respectant un certain compromis entre un modele explicite et un temps de calcul associe raisonnable.

1.2 Rappels de probabilites

Dans ce cours, nous considererons le plus souvent un ensemblefX1;X2:::;Xngde va- riables aleatoiresdiscreteset nous noteronsxila realisation de la variableXipour tout 1-2

Cours 1 | 30 septembre 2009/2010

i= 1;:::;n. Nous garderons a l'esprit quenest en pratique assez grand. LesXipeuvent^etre denis simplement par la donnee de leur loi jointeP(X1=x1;:::;Xn=xn) (nous verrons que ce n'est pas la meilleure maniere de proceder en particulier lorsquenest grand). Dans le cadre des variables dites\continues", i.e., a valeurs reelles ou vectorielles,p(x1;:::;xn) representera la densite par rapport a la mesure de Lebesgue.

1.2.1 Denitions

Denition 1.1 (Independance)Deux variables aleatoiresXetYsont dites indepen- dantes, noteesX?Y, si quelles que soient les valeursxetyprises parXetY, on a :

P(X=x;Y=y) =P(X=x)P(Y=y)

Denition 1.2 (Independance conditionnelle)SoientX,Y, etZtrois variables alea- toires. On dit queXest independante deYsachantZsiX,YetZverient l'une des deux assertions equivalentes suivantes : {8x;y;z;P(X=x;Y=yjZ=z) =P(X=xjZ=z)P(Y=yjZ=z) {8x;y;z;P(X=xjY=y;Z=z) =P(X=xjZ=z) On notera cette relation d'independanceX?YjZ, qui se lit \XetYsont independantes sachantZ".

1.2.2 Notations

On dira qu'un ensemble de variables aleatoires esti.i.d.lorsque qu'elles sont indepen- dantes et identiquement distribuees. SoitX= (X1;:::;Xn) un vecteur aleatoire discrete (prend un nombre ni de valeurs) et A=fa1;:::;akgun sous-ensemble def1;:::;ng. Nous utiliserons dans la suite du cours les abreviations suivantes pour la marginalisation de variables :

P(XA=xA) =P(Xa1=xa1;:::;Xak=xak) =p(xA)

X x a1X x a2X x akp(xa1;xa2;:::;xak) =X x

Ap(xA)

En particulier, siA=f1g, on noterap(X1=x1) =p(x1). De m^eme on notera la probabilite conditionnelle de la facon suivante :

P(X=xjY=y) =p(xjy)

1-3

Cours 1 | 30 septembre 2009/2010

SoientAetBdeux operateurs et soientDAetDBleurs domaines de denition respectifs. Soit (a;b)2 DA DB. On dira queA(a)/B(b) lorsqueABest constant, ouA=Best constant (selon le contexte). Cette notation sera utilisee pour simplier l'ecriture lors des dierents calculs, notamment lorsqu'apparaissent des constantes ne dependant pas des variables aleatoires considerees.

1.2.3 Autres rappels

Formule de Bayes

Soient A et B deux evenements, alors

P(AjB) =P(BjA)P(A)P(B)

Marginalisation

On calcule en pratique les probabilites de la maniere suivante : p(x1) =X x 2X x 2X x np(x1;x2;:::;xn)

On a ainsi pour tout sous-ensemble A def1;:::;ng:

p(xA) =X x

Acp(xA;xAc)

Exercices

{ J'ai 2 enfants dont 1 lle, quelle est la probabilite que l'autre soit un garcon? { J'ai 3 enfants dont 2 lles, quelle est la probabilite que l'autre soit un garcon? { J'ai 1 lle, quelle est la probabilite que celui qui va na^tre soit un garcon?

1.3 Modele a un noeud

SoitXune variable aleatoire avec des observationsX1;:::;Xni.i.d.

Notre objectif est le suivant :

1. Decrire un modele pourX, i.e., determiner la loi deX, c'est-a-direp(x), en fonction

d'un parametre.

2. Estimer (ou\apprendre")a partir des observationsX1;:::;Xn.

1-4

Cours 1 | 30 septembre 2009/2010

1.3.1 Estimation de parametre a partir de donnees i.i.d.

SoitXun variable aleatoire de loip(x). Il existe deux philosophies dierentes pour es- timer. Philosophie Bayesienne(cf. cours de methodes MCMC et applications) On etudie la loip(x) en supposant queune variable aleatoire. On denit alors la probabilite a priori : p() et la vraisemblance :p(xj) =p(x), ce qui permet d'en deduire la loi a posteriori (par la regle de Bayes) p(jx) =p(xj)p()p(x) En particulier, le statisticien Bayesien essaiera de ne jamais utiliser un estimateur ponc- tuel de, mais utilisera toujours l'ensemble de la loi a posteriori. Dans certains cas, le mode ou la moyenne de cette distribution sont utilisees. Dans le cas du mode, on parle de \maxi- mum a posteriori" (MAP). Philosophie frequentisteIl faut trouver un bon estimateur^(x1;:::;xn) et l'evaluer. L'estimateur utilise dans ce cours sera le maximum de vraisemblance, qui jouit de proprietes numeriques (convexite) et statistiques (en theorie asymptotique) interessantes [1]. Denition 1.3 (Estimateur de maximum de vraisemblance)Soit une loip(x), avec x2, et des donneesx1;:::;xn2i.i.d. La vraisemblanceL() =P(X1=x1;:::;Xn= x n)est alors egale aQn i=1P(Xi=xi) =Qn i=1p(xi)L'estimateur de maximum de vraisem- blance (EMV) ^est deni de la facon suivante : (x1;:::;xn) = argmaxn Y i=1p (xi)

1.3.2 Estimation de lois par maximum de vraisemblance

Les denitions des dierentes lois suivantes se trouvent, par exemple, dans [2]

Loi de Bernoulli

Soitp2[0;1] etXune variable a valeurs dansf0;1g, de loi denie comme suit : p(X= 1) =p p(X= 0) = 1p Dans ce cas le parametrea estimer est le reelp(attention a la surcharge de notation, ici pratique). 1-5

Cours 1 | 30 septembre 2009/2010

On a :

p(x1;:::;xn) =nY i=1p(xi) a cause de l'independance, nY i=1p xi(1p)1xicar lesXisont identiquement distribuees. Plut^ot que de considerer la vraisemblance, il est plus pratique d'eectuer les calculs sur la log-vraisemblance`(), en appliquant le logarithme a l'equation. On en deduit : `() = log(p(x1;:::;xn)) = log(p)(nX i=1x i) + log(1p)(nnX i=1x i)

On posen1=nX

i=1x i= \nombre de 1". On obtient alors : `() =n1logp+ (nn1)log(1p) Cette derniere fonction est convexe par rapport ap. On peut donc determiner son mi- nimum en annulant son gradient, ce qui revient a determinerptel quen1p nn11p= 0. La solution estp=n1n , qui est la frequence empirique de l'observation 1 (estimateur naturel).

On a nalement :

^p=n1=n=1n n X i=1x i

Loi multinomiale

Soit une variable aleatoireXprenant ses valeurs dansf1;:::;qg. La loi est parametree par un vecteur2Rqtel que0 etP ii= 1. Soit un echantillonx1;:::;xni.i.d. (independant et identiquement distribue). La vraisemblance est donnee par p (x1;:::;xn) =nY j=1p (xj) =nY j=1q Y i=1(xj=i) i qY i=1P n j=1(xj=i) i qY i=1 nii 1-6

Cours 1 | 30 septembre 2009/2010

ouni=Pn j=1(xj=i) est le nombre de valeursiobservees dans l'echantillon.

Le maximum de vraisemblance est donne par :

max 0;P ii=1log qY i=1 nii! ()min0;P ii=1 qX i=1n ilogi! On introduit les multiplicateurs de Lagrange an de passer la contrainte P ii= 1 dans la fonction objectif. On obtient le Lagrangien suivant :

L(;) =qX

i=1n ilogi+(qX i=1 i1) On doit desormais minimiser le Lagrangien par rapport a0 ce qui revient a annuler son gradient. On obtient le systeme suivant : 8

1L(;) =n1

1+= 0 qL(;) =nq q+= 0

L(;) =Pq

i=1i1 = 0 En sommant lesqpremieres equations de notre systeme, on obtient=qX j=1n j. On re- marque que la contrainte reappara^t dans la derniere equation du systeme. On obtient donc la solution suivante (frequence empirique) : i=niq X j=1n j Remarque :Nous nous sommes ici contentes de la seconde contrainte (P ii= 1), la contrainte de positivite0 etant naturellement imposee par le logarithme qui tend vers

1en 0. Sinon, il aurait fallu introduire un terme supplementaire dans le lagrangien, de

typePk j=1jjavecj0. NB : La page [3] donne quelque precisions sur les multiplicateurs de Lagrange. Pour une introduction a l'optimisation convexe avec contraintes, voir par exemple, le livre [4]. 1-7

Cours 1 | 30 septembre 2009/2010

Loi Gaussienne

Soit une variablex2R. Nous supposons qu'elle suit une loi normale parametree par sa moyenneet sa variance2: p(xj;2) =1p2e(x)222 Soit un echantillonx1;:::;xni.i.d. La log-vraisemblance est donnee par : ;2= logpx1;:::;xnj;2 = log nY i=1pxij;2 nX i=1 logp2 (xi)222 / nlog() +nX i=1(xi)222 En derivant par rapport aet2, nous trouvons les estimateursbetb2qui maximisent la vraisemblance : b=1n n X i=1x i Notons que cette valeur est exactement la moyenne empirique. b2=1nquotesdbs_dbs14.pdfusesText_20

[PDF] Math206 – Equations aux Dérivées Partielles Feuille d'Exercices 1

[PDF] Dérivées partielles - Exo7

[PDF] Dérivées et différentielles des fonctions de plusieurs variables

[PDF] Résolution d'équations aux dérivées partielles non linéaires et

[PDF] Dérivées et différentielles des fonctions de plusieurs variables

[PDF] Calcul différentiel et intégral

[PDF] Cours Micro éco N Laroche - Cerdi

[PDF] Fiche N°1 Produit scalaire, dérivée et intégrale Le produit scalaire

[PDF] P2-3-Signaux periodiques non sinusoidaux - Free

[PDF] Tableau des dérivées élémentaires et règles de - Lycée d'Adultes

[PDF] Fascicule d'exercices - L'UNF3S en 2015, c'est

[PDF] Polycopié en PDF - Institut de Mathématiques de Bordeaux

[PDF] Thème 15: Dérivée d'une fonction, les règles de calcul

[PDF] Tableaux des dérivées Dérivées des fonctions usuelles Notes

[PDF] Guide pratique de Saint-Quentin-en-Yvelines