Application de la maximisation des attentes aux exemples de lancer de pièces

18

J'ai auto-étudié la maximisation des attentes récemment et je me suis emparé de quelques exemples simples dans le processus:

De : Il y a trois pièces , et avec , et la probabilité respective d'atterrir sur la tête lorsqu'elle est lancée. Toss . Si le résultat est Tête, lancez trois fois, sinon lancez trois fois. Les données observées produites par et sont les suivantes: HHH, TTT, HHH, TTT, HHH. Les données cachées sont le résultat de . Estimez , et .c 1 c 2 p 0 p 1 p 2 c 0 c 1 c 2 c 1 c 2 c 0 p 0 p 1 p 2c0c1c2p0p1p2c0c1c2c1c2c0p0p1p2

Et à partir d' ici : Il y a deux pièces et avec et étant la probabilité respective d'atterrir sur la tête lorsqu'elle est lancée. Chaque tour, sélectionnez une pièce au hasard et lancez-la dix fois; enregistrer les résultats. Les données observées sont les résultats du tirage fournis par ces deux pièces. Cependant, nous ne savons pas quelle pièce a été sélectionnée pour un tour particulier. Estimation et .cUNEcBpUNEpBpUNEpB

Bien que je puisse obtenir les calculs, je ne peux pas relier les façons dont ils sont résolus à la théorie EM originale. Plus précisément, pendant l'étape M des deux exemples, je ne vois pas comment ils maximisent quoi que ce soit. Il semble juste qu'ils recalculent les paramètres et d'une manière ou d'une autre, les nouveaux paramètres sont meilleurs que les anciens. De plus, les deux étapes E ne se ressemblent même pas, sans parler de l'étape E de la théorie originale.

Alors, comment fonctionnent exactement ces exemples?

IcySnow
la source
Dans le premier exemple, combien d'instances de la même expérience obtenons-nous? Dans le deuxième exemple, quelle est la loi de "sélectionner une pièce au hasard"? Combien de rounds observons-nous?
Raphael
Les fichiers PDF que j'ai liés résolvent déjà ces deux exemples étape par étape. Cependant, je ne comprends pas vraiment l'algorithme EM utilisé.
IcySnow
@IcySnow, comprenez-vous le concept d'attente et d'attente conditionnelle d'une variable aléatoire?
Nicholas Mancuso
Je comprends l'attente de base d'une variable aléatoire et d'une probabilité conditionnelle. Cependant, je ne connais pas l'attente conditionnelle, sa dérivée et sa statistique suffisante.
IcySnow

Réponses:

12

(Cette réponse utilise le deuxième lien que vous avez donné.)

θ = ( θ A , θ B )

L[θ|X]=Pr[X|θ]=ZPr[X,Z|θ]
θ=(θA,θB)X=(X1,,X5)XiZ=(Z1,,Z5)

Nous voulons trouver l'estimateur du maximum de vraisemblance . L'algorithme Expectation-Maximization (EM) est une de ces méthodes pour trouver (au moins local) . Il fonctionne en trouvant l'espérance conditionnelle, qui est ensuite utilisée pour maximiser . L'idée est qu'en trouvant continuellement un plus probable (c'est-à-dire plus probable) à chaque itération, nous augmenterons continuellement qui à son tour, augmentera la fonction de vraisemblance. Il y a trois choses à faire avant de continuer à concevoir un algorithme basé sur EM.θ^θ^θθPr[X,Z|θ]

  1. Construire le modèle
  2. Calcul des attentes conditionnelles sous le modèle (E-Step)
  3. Maximisez notre probabilité en mettant à jour notre estimation actuelle de (étape M)θ

Construire le modèle

Avant d'aller plus loin avec EM, nous devons déterminer ce que nous calculons exactement. Dans l'étape E, nous calculons exactement la valeur attendue pour . Alors, quelle est vraiment cette valeur? Observez que La raison en est que nous avons 5 expériences à prendre en compte, et nous ne savons pas quelle pièce a été utilisée dans chacune. L'inégalité est due àlog Pr [ X , Z | θ ]JournalPr[X,Z|θ]Journal

logPr[X,Z|θ]=i=15logC{A,B}Pr[Xi,Zi=C|θ]=i=15logC{A,B}Pr[Zi=C|Xi,θ]Pr[Xi,Zi=C|θ]Pr[Zi=C|Xi,θ]i=15C{A,B}Pr[Zi=C|Xi,θ]logPr[Xi,Zi=C|θ]Pr[Zi=C|Xi,θ].
logêtre concave et appliquer l'inégalité de Jensen. La raison pour laquelle nous avons besoin de cette borne inférieure est que nous ne pouvons pas calculer directement l'arg max à l'équation d'origine. Cependant, nous pouvons le calculer pour la borne inférieure finale.

Maintenant, qu'est-ce que ? C'est la probabilité que nous voyions la pièce expérience et . En utilisant les probabilités conditionnelles, nous avons,C X i θ Pr [ Z i = C | X i , θ ] = Pr [ X i , Z i = C | θ ]Pr[Zi=C|Xi,θ]CXiθ

Pr[Zje=C|Xje,θ]=Pr[Xje,Zje=C|θ]Pr[Xje|θ].

Bien que nous ayons fait quelques progrès, nous n'en avons pas encore fini avec le modèle. Quelle est la probabilité qu'une pièce donnée retourne la séquence ? Laisser Maintenant est clairement que la probabilité dans les deux possibilités de ou . Puisque nous avons, h i = # têtes dans  X i Pr [ X i , Z i = C | θ ] = 1Xjehje=#tête en Xje Pr[Xi| θ]Zi=AZi=BPr[Zi=A]=Pr[Zi=B]=1/deux

Pr[Xje,Zje=C|θ]=12θChje(1-θC)dix-hje,  pour  C{UNE,B}.
Pr[Xje|θ]Zje=UNEZje=BPr[Zi=A]=Pr[Zi=B]=1/2
Pr[Xje|θ]=1/2(Pr[Xje|Zje=UNE,θ]+Pr[Xje|Zje=B,θ]).

E-Step

D'accord ... ce n'était pas si amusant, mais nous pouvons commencer à faire du travail EM maintenant. L'algorithme EM commence par faire une supposition aléatoire pour . Dans cet exemple, nous avons . Nous calculons Cette valeur correspond à ce qui est dans le papier. Maintenant, nous pouvons calculer le nombre attendu de têtes dans partir de la pièce , Faire la même chose pour la pièce nous obtenons, θ 0 = ( 0,6 , 0,5 ) Pr [ Z 1 = A | X 1 , θ ] = 1 / deux ( 0,6 50,4 5 )θθ0=(0,6,0,5)

Pr[Z1=UNE|X1,θ]=1/2(0,650,45)1/2((0,650,45)+(0,550,55))0,45.
X1=(H,T,T,T,H,H,T,H,T,H)UNEB E [ # têtes par pièce  B | X 1 , θ ] = h 1Pr [ Z 1 = B | X 1 , θ ] = 5 0,55 2,8. h 1 10
E[#têtes par pièce UNE|X1,θ]=h1Pr[Z1=UNE|X1,θ]=50,452.2.
B
E[#têtes par pièce B|X1,θ]=h1Pr[Z1=B|X1,θ]=50,552.8.
Nous pouvons calculer la même chose pour le nombre de queues en substituant à . Cela continue pour toutes les autres valeurs de et . Grâce à la linéarité des attentes, nous pouvons comprendre h1X i h i 1 i 5 E [ # têtes par pièce  A | X , θ ] = 5 i = 1 E [ # têtes par pièce  A | X i , θ ]dix-h1Xjehje 1je5
E[#têtes par pièce UNE|X,θ]=je=15E[#têtes par pièce UNE|Xje,θ]

M-Step

Avec nos valeurs attendues en main, vient maintenant l'étape M où nous voulons maximiser compte tenu de nos valeurs attendues. Cela se fait par simple normalisation! De même pour . Ce processus recommence avec l'E-Step et et continue jusqu'à ce que les valeurs de convergent (ou jusqu'à un certain seuil autorisé). Dans cet exemple, nous avons 10 itérations et . À chaque itération, la valeur de augmente, en raison de la meilleure estimation deθ 1 A = E [ # se dirige vers  X  avec la pièce  A | X , θ ]θ

θUNE1=E[#se dirige vers X par pièce UNE|X,θ]E[#têtes et queues sur X par pièce UNE|X,θ]=21,321,3+9,60,71.
Bθ1θθ^=θdix=(0,8,0,52)Pr[X,Z|θ]θ .

Maintenant, dans ce cas, le modèle était assez simpliste. Les choses peuvent devenir beaucoup plus compliquées assez rapidement, mais l'algorithme EM convergera toujours et produira toujours un estimateur de vraisemblance maximum . Il peut s'agir d'un estimateur local , mais pour contourner ce problème, nous pouvons simplement redémarrer le processus EM avec une initialisation différente. Nous pouvons le faire un nombre de fois constant et conserver les meilleurs résultats (c'est-à-dire ceux avec la probabilité finale la plus élevée).θ^

Nicholas Mancuso
la source
Si certaines parties ne sont pas claires, je peux également les développer.
Nicholas Mancuso
Cela devient beaucoup plus clair maintenant. Ce que je ne comprends pas vraiment, c'est pourquoi le nombre attendu de têtes pour la pièce A a été calculé comme suit: E [#têtes par pièce A | X1, θ] = h1⋅Pr [Z1 = A | X1, θ] = 5⋅0.45 ≈2,2? Le problème mentionné dans le premier PDF est plus compliqué. Si cela ne vous dérange pas, pouvez-vous également faire des calculs illustratifs? Merci beaucoup pour votre réponse.
IcySnow
@IcySnow, en ce qui concerne le calcul des attentes: . La raison en est que vous pouvez penser qu'il existe une autre variable aléatoire d'indicateur si A a été utilisé. Le calcul des attentes par rapport aux variables indicatrices est simplement la probabilité de cet événement. E[# têtes par pièce UNE|X1,θ]=# tête en X1Pr[Z1=UNE|X1,θ]=5Pr[Z1=UNE|X1,θ]
Nicholas Mancuso
Désolé pour la réponse lente. Grâce à vous, je peux maintenant vraiment comprendre la logique derrière les deux exemples de pièces, après avoir répété votre réponse plusieurs fois. Il y a une dernière chose que je veux demander concernant cette question: l'exemple à partir de la page 8 de cette diapositive cs.northwestern.edu/~ddowney/courses/395_Winter2010/em.ppt montre que dans l'étape M, nous devons d'abord calculer la dérivée de la fonction log-vraisemblance et l'utiliser pour maximiser l'attente. Pourquoi n'y a-t-il pas quelque chose comme ça dans les M-Steps des exemples de lancer de pièces? Parce que ces étapes M n'ont pas l'air de maximiser quoi que ce soit
IcySnow
Je suis confus par la première équation affichée après "Construire le modèle". Pouvez-vous expliquer d'où cela vient? Il me semble que , donc la somme intérieure est 1 pour chaque , donc tout le côté droit devient nul. Je suis sûr qu'il me manque quelque chose - pouvez-vous expliquer le raisonnement sur la façon dont vous êtes arrivé à cette équation? Pr[Zje=UNE|Xje,θ]+Pr[Zje=B|Xje,θ]=1je
DW