K bedeutet als Grenzfall des EM-Algorithmus für Gaußsche Gemische mit Kovarianzen bis

8

Mein Ziel ist es zu sehen, dass der K-Mittelwert-Algorithmus tatsächlich ein Erwartungsmaximierungsalgorithmus für Gaußsche Gemische ist, bei dem alle Komponenten eine Kovarianz im Grenzwert als .σ2Ilimσ0

Angenommen , wir haben einen Datensatz {x1,,xN} von Beobachtungen von Zufallsvariablen X .
Die Zielfunktion für M-Mittel ist gegeben durch:

J=n=1Nk=1Krnk||xnμk||2
wobei rnk ist eine binäre Indikatorvariable einer harten Zuordnung von xn zu Cluster k .
(Wenn der Datenpunkt xn dem Cluster k zugewiesen ist k, ist rnk=1 und rnj=0 für j k).
Der K-Mittelwert-Algorithmus minimiert J durch Iteration bis zur Konvergenz, was zwei aufeinanderfolgende Schritte umfasst:
(E) MinimierenJ in Bezug auf {rnk}n,k hält alle μk fest
(M) minimiert J in Bezug auf {μk}k hält alle rnk fest

Im Allgemeinen maximiert der EM-Algorithmus, indem er alle beobachteten Daten mit X , alle latenten Variablen mit Z und alle Modellparameter mit θ , die posteriore Verteilung p(θ|X) durch Iteration bis zur Konvergenz von zwei abwechselnden Schritten:
(E. ) Berechnen Sie die Erwartung Q(θ,θold):=Zp(Z|X,θold)logp(Z,X|θ)
(M) find θnew=argmaxθQ(θ,θold)

Betrachten Sie nun die Gaußsche Mischungsverteilung: Einführung einer latenten dimensionalen binären Zufallsvariablen durch , wir sehen, dass: Also

p(x)=k=1KπkN(x|μk,Σk)
Kzp(zk=1)=πk
p(X,Z)=n=1Nk=1KπkznkN(xn|μk,Σk)znk
γ(zk):=p(zk=1|x)=πkN(x|μk,Σk)j=1KπjN(x|μj,Σj)
logp(X,Z|μ,Σ,π)=n=1Nk=1Kznk(logπk+logN(xn|μk,Σk))
E(znk)=γ(znk)
Q((π,μ,Σ),(π,μ,Σ)old)=n=1Nk=1Kγ(znk)(logπk+logN(xn|μk,Σk))

Wenn jetzt alle Gaußschen im Mischungsmodell die Kovarianz , kann unter Berücksichtigung der Grenze leicht zeigen, dass wobei as ist oben definiert. In der Tat aktualisiert der (E) -Schritt wie im K-Mittelwert-Algorithmus.σ2Iσ0γ(znk)rnkrnkrnk

Ich habe jedoch Probleme mit der Maximierung von in diesem Zusammenhang, wie für . Stimmt es, dass bis zu einer konstanten und skalaren Multiplikation: ?Q((π,μ,Σ),(π,μ,Σ)old)xμ limσ0log(N(x|μ,σ2))=
limσ0Q((π,μ,Σ),(π,μ,Σ)old)=J

Vielleicht fehlt mir etwas. Irgendein Rat?

Andrzej Neugebauer
quelle
2
Willkommen auf der Website @Andrzej. Bitte posten Sie die vollständige Frage - erwarten Sie nicht, dass Leute nach Ihrem Buch suchen.
StasK
1
Lieber StasK, ich habe gerade die vollständige Frage gestellt und hoffe, dass sie jetzt klar ist.
Andrzej Neugebauer

Antworten:

3

Stimmt es, dass bis zu einer konstanten und skalaren Multiplikation: ?limσ0Q((π,μ,Σ),(π,μ,Σ)old)=J

Dies ist nicht der Fall, da - wie Sie selbst beobachtet haben - die Grenze abweicht.

Wenn wir jedoch zuerst transformieren und dann die Grenze nehmen, konvergieren wir zum k-Mittelwert-Ziel. Für und wirQΣk=σ2Iπk=1/K

Q=n,kγnk(logπk+logN(xnμk,Σk))=Nlog1K1σ2n,kγnk||xnμk||2ND2log2πσ2.

Durch Multiplizieren mit (was den EM-Algorithmus nicht beeinflusst, da nicht optimiert, sondern konstant ist) und Sammeln aller konstanten Terme in wir, dass Beachten Sie, dass die Maximierung dieser Funktion in Bezug auf für jedes und dasselbe ergibt Ergebnis als obige Zielfunktion, dh es ist eine äquivalente Formulierung des M-Schritts. Aber das Limit zu nehmen ergibt jetzt .σ2σC

Qn,kγnk||xnμk||2+σ2C.
μγσJ

Abgesehen davon besteht eine meiner Ansicht nach etwas elegantere Formulierung von EM darin, die Zielfunktion Mit dieser Zielfunktion läuft der EM-Algorithmus auf Alternieren hinaus zwischen der Optimierung von in Bezug auf (M-Schritt) und (E-Schritt). Wenn wir die Grenze nehmen, sehen wir, dass sowohl der M-Schritt als auch der E-Schritt zum k-Mittelwert-Algorithmus konvergieren.

F(μ,γ)=n,kγnklogπkN(xnμk,Σk)/γnkn,kn,kγnk||xnμk||2σ2n,kγnklogγnk+σ2C.
Fμγ

Siehe auch eine alternative Ansicht von EM .

Lucas
quelle