W podejściu algorytmu EM wykorzystujemy nierówność Jensena do uzyskania
Wszystko, co czytam EM, po prostu go rozwala, ale zawsze czułem się nieswojo, nie mając wyjaśnienia, dlaczego algorytm EM powstaje naturalnie. Rozumiem, że prawdopodobieństwo zwykle zajmuje się dodawaniem zamiast mnożenia, ale pojawienie się w definicji wydaje mi się niemotywowane. Dlaczego warto brać pod uwagę a nie inne funkcje monotoniczne? Z różnych powodów podejrzewam, że „znaczenie” lub „motywacja” stojąca za maksymalizacją oczekiwań ma jakieś wyjaśnienie w zakresie teorii informacji i wystarczających statystyk. Gdyby istniało takie wyjaśnienie, które byłoby znacznie bardziej satysfakcjonujące niż tylko abstrakcyjny algorytm.
mixture
expectation-maximization
użytkownik782220
źródło
źródło
Odpowiedzi:
Algorytm EM ma różne interpretacje i może występować w różnych formach w różnych aplikacjach.
Wszystko zaczyna się od funkcji wiarygodnościp(x|θ) lub równoważnie funkcji log-wiarygodności logp(x|θ) którą chcielibyśmy zmaksymalizować. (Na ogół używamy logarytmu, ponieważ upraszcza obliczenia: jest ściśle monotoniczny, wklęsły i log(ab)=loga+logb .) W idealnym świecie wartość p zależy tylko od parametru modelu θ , więc możemy przeszukać przestrzeń θ i znaleźć taki, który maksymalizujep .
Jednak w wielu interesujących rzeczywistych aplikacjach rzeczy są bardziej skomplikowane, ponieważ nie wszystkie zmienne są obserwowane. Tak, możemy bezpośrednio zaobserwowaćx , ale niektóre inne zmienne z nie są obserwowane. Ze względu na brakujące zmienne z jesteśmy w pewnej sytuacji z kurczakiem i jajami: bez z nie możemy oszacować parametru θ a bez θ nie możemy wywnioskować, jaka może być wartość z .
To tutaj pojawia się algorytm EM. Zaczynamy od wstępnego odgadnięcia parametrów modeluθ i uzyskujemy oczekiwane wartości brakujących zmiennych z (tj. Krok E). Gdy mamy wartości z , możemy zmaksymalizować prawdopodobieństwo wrt Parametry θ (czyli krok M, odpowiadający argmax równania w rachunku problem). Dzięki temu θ możemy uzyskać nowe oczekiwane wartości z (kolejny krok E), itd. I tak dalej. Innymi słowy, w każdym kroku zakładamy jedno z obu, z i θ , jest znany. Powtarzamy ten iteracyjny proces, dopóki nie można już zwiększyć prawdopodobieństwa.
To jest algorytm EM w pigułce. Powszechnie wiadomo, że prawdopodobieństwo nigdy nie spadnie podczas tego iteracyjnego procesu EM. Pamiętaj jednak, że algorytm EM nie gwarantuje globalnego optimum. Oznacza to, że może skończyć się lokalnym optimum dla funkcji prawdopodobieństwa.
Pojawienie się w równaniu θ ( k + 1 ) jest nieuniknione, ponieważ tutaj funkcja, którą chciałbyś zmaksymalizować, zapisywana jest jako prawdopodobieństwo logarytmiczne.log θ(k+1)
źródło
Prawdopodobieństwo a prawdopodobieństwo dziennika
Jak już powiedziano, jest wprowadzany z maksymalnym prawdopodobieństwem po prostu dlatego, że ogólnie łatwiej jest zoptymalizować sumy niż produkty. Powodem, dla którego nie bierzemy pod uwagę innych funkcji monotonicznych, jest to, że logarytm jest unikalną funkcją z właściwością przekształcania produktów w sumy.log
Innym sposobem motywowania logarytmu jest: Zamiast maksymalizować prawdopodobieństwo danych w naszym modelu, moglibyśmy w równoważny sposób spróbować zminimalizować rozbieżność Kullbacka-Leiblera między rozkładem danych, danych i rozkładem modelu, p ( x ∣ θ ) ,pdata(x) p(x∣θ)
Pierwszy termin po prawej stronie jest stały w parametrach. Jeśli mamy próbek z rozkładu danych (naszych punktów danych), możemy aproksymować drugi termin ze średnim prawdopodobieństwem logarytmicznym danych,N
Alternatywny pogląd na EM
Nie jestem pewien, czy to będzie tego rodzaju wyjaśnienie, którego szukasz, ale znalazłem następujący pogląd na maksymalizację oczekiwań o wiele bardziej pouczającą niż jej motywacja poprzez nierówność Jensena (szczegółowy opis znajdziesz w Neal i Hinton (1998)) lub w książce PRML Chrisa Bishopa, rozdział 9.3).
Nietrudno to pokazać
dla dowolnego . Jeśli nazwiemy pierwszy termin po prawej stronie F ( q , θ ) , oznacza to, żeq(z∣x) F(q,θ)
Ponieważ rozbieżność KL jest zawsze dodatnia , jest dolną granicą prawdopodobieństwa logarytmicznego dla każdego ustalonego q . Teraz EM można postrzegać jako naprzemiennie maksymalizujący F w stosunku do q i θ . W szczególności, ustawienie Q ( z | x ) = P ( z | x , θ ) w etapie E, to zminimalizowania rozbieżności KL po stronie prawej, a zatem maksymalizacji F .F(q,θ) q F q θ q(z∣x)=p(z∣x,θ) F
źródło
The paper that I found clarifying with respect to expectation-maximization is Bayesian K-Means as a "Maximization-Expectation" Algorithm (pdf) by Welling and Kurihara.
Suppose we have a probabilistic modelp(x,z,θ) with x observations, z hidden random variables, and a total of θ parameters. We are given a dataset D and are forced (by higher powers) to establish p(z,θ|D) .
1. Gibbs sampling
We can approximatep(z,θ|D) by sampling. Gibbs sampling gives p(z,θ|D) by alternating:
2. Variational Bayes
Instead, we can try to establish a distributionq(θ) and q(z) and minimize the difference with the distribution we are after p(θ,z|D) . The difference between distributions has a convenient fancy name, the KL-divergence. To minimize KL[q(θ)q(z)||p(θ,z|D)] we update:
3. Oczekiwanie-maksymalizacja
Hereθ∗∈argmax would actually be a better notation: the argmax operator can return multiple values. But let's not nitpick. Compared to variational Bayes you see that correcting for the log by exp doesn't change the result, so that is not necessary anymore.
4. Maximization-Expectation
There is no reason to treatz as a spoiled child. We can just as well use point estimates z∗ for our hidden variables and give the parameters θ the luxury of a full distribution.
If our hidden variablesz are indicator variables, we suddenly have a computationally cheap method to perform inference on the number of clusters. This is in other words: model selection (or automatic relevance detection or imagine another fancy name).
5. Iterated conditional modes
Of course, the poster child of approximate inference is to use point estimates for both the parametersθ as well as the observations z .
To see how Maximization-Expectation plays out I highly recommend the article. In my opinion, the strength of this article is however not the application to ak -means alternative, but this lucid and concise exposition of approximation.
źródło
There is a useful optimisation technique underlying the EM algorithm. However, it's usually expressed in the language of probability theory so it's hard to see that at the core is a method that has nothing to do with probability and expectation.
Consider the problem of maximising
Now suppose that thefi play well together in the sense that linear combinations of them give you something easy to optimise. For example, if all of the fi(x) are quadratic in x then a linear combination of the fi(x) will also be quadratic, and hence easy to optimise.
Given this supposition, it'd be cool if, in order to optimiselogg(x)=log∑iexp(fi(x)) we could somehow shuffle the log past the ∑ so it could meet the exp s and eliminate them. Then the fi could play together. But we can't do that.
Let's do the next best thing. We'll make another functionh that is similar to g . And we'll make it out of linear combinations of the fi .
Let's sayx0 is a guess for an optimal value. We'd like to improve this. Let's find another function h that matches g and its derivative at x0 , i.e. g(x0)=h(x0) and g′(x0)=h′(x0) . If you plot a graph of h in a small neighbourhood of x0 it's going to look similar to g .
You can show that
So starting withx0 , we form h(x) and optimise that. Because it's similar to g(x) in the neighbourhood of x0 we hope the optimum of h is similar to the optimum of g. Once you have a new estimate, construct the next h and repeat.
I hope this has motivated the choice ofh . This is exactly the procedure that takes place in EM.
But there's one more important point. Using Jensen's inequality you can show thath(x)≤g(x) . This means that when you optimise h(x) you always get an x that makes g bigger compared to g(x0) . So even though h was motivated by its local similarity to g , it's safe to globally maximise h at each iteration. The hope I mentioned above isn't required.
This also gives a clue to when to use EM: when linear combinations of the arguments to theexp function are easier to optimise. For example when they're quadratic - as happens when working with mixtures of Gaussians. This is particularly relevant to statistics where many of the standard distributions are from exponential families.
źródło
As you said, I will not go into technical details. There are quite a few very nice tutorials. One of my favourites are Andrew Ng's lecture notes. Take a look also at the references here.
EM is naturally motivated in mixture models and models with hidden factors in general. Take for example the case of Gaussian mixture models (GMM). Here we model the density of the observations as a weighted sum ofK gaussians:
The point is not using monotonic functions but convex functions. And the reason is the Jensen's inequality which ensures that the estimates of the EM algorithm will improve at every step.
źródło