Алгоритм мотивации ожидания максимизации

20

В подходе EM-алгоритма мы используем неравенство Дженсена для получения

logp(x|θ)logp(z,x|θ)p(z|x,θ(k))dzlogp(z|x,θ)p(z|x,θ(k))dz

θ(k+1)

θ(k+1)=argmaxθlogp(z,x|θ)p(z|x,θ(k))dz

Все, что я читаю EM, просто сводит это на нет, но я всегда чувствовал себя неловко, не имея объяснения, почему алгоритм EM возникает естественным образом. Я понимаю, что вероятность обычно рассматривается для сложения вместо умножения, но появление в определении \ theta ^ {(k + 1)} кажется мне немотивированным. Почему следует рассматривать \ log, а не другие монотонные функции? По разным причинам я подозреваю, что «значение» или «мотивация», лежащая в основе максимизации ожидания, имеет какое-то объяснение с точки зрения теории информации и достаточной статистики. Если бы было такое объяснение, это было бы гораздо более удовлетворительным, чем просто абстрактный алгоритм.журналloglog logθ(k+1)log

user782220
источник
3
Каков алгоритм максимизации ожидания? , Nature Biotechnology 26 : 897–899 (2008), имеет хорошую картину, которая иллюстрирует, как работает алгоритм.
ЧЛ
@chl: я видел эту статью. Вопрос, который я спрашиваю, заключается в том, что обратите внимание, что нигде не объясняется, почему не может работать подход без регистрации
user782220

Ответы:

10

EM-алгоритм имеет разные интерпретации и может возникать в разных формах в разных приложениях.

Все начинается с функции правдоподобия p(x|θ) или, что то же самое, логарифмической функции правдоподобия logp(x|θ) мы хотели бы максимизировать. (Обычно мы используем логарифм, поскольку он упрощает вычисления: он строго монотонный, вогнутый и log(ab)=loga+logb .) В идеальном мире значение p зависит только от параметра модели θ , поэтому мы можем искать в пространстве θ и найти тот, который максимизируетp .

Однако во многих интересных реальных приложениях дела обстоят сложнее, потому что наблюдаются не все переменные. Да, мы могли бы непосредственно наблюдать x , но некоторые другие переменные z являются ненаблюдаемыми. Из-за отсутствующих переменных z мы находимся в некотором роде ситуации "курица и яйцо": без z мы не можем оценить параметр θ а без θ мы не можем сделать вывод, каким может быть значение z .

Это где EM алгоритм вступает в игру. Мы начнем с первоначального предположения параметров модели θ и получим ожидаемые значения отсутствующих переменных z (т. Е. Шаг E). Когда у нас есть значения z , мы можем максимизировать вероятность относительно параметров θ (то есть шаг М, соответствующий уравнению argmax в постановке задачи). С этим θ мы можем получить новые ожидаемые значения z (еще один шаг E), и так далее, и так далее. Другими словами, на каждом шаге мы принимаем одно из обоих, z и θ, известен. Мы повторяем этот итеративный процесс, пока вероятность больше не может быть увеличена.

Это алгоритм EM в двух словах. Хорошо известно, что вероятность этого никогда не уменьшится во время этого итеративного процесса EM. Но имейте в виду, что алгоритм EM не гарантирует глобального оптимума. Таким образом, это могло бы закончиться локальным оптимумом функции правдоподобия.

Появление log в уравнении θ(k+1) неизбежно, потому что здесь функция, которую вы хотели бы максимизировать, записывается как логарифмическая вероятность.

Вэйвэй
источник
Я не понимаю, как это отвечает на вопрос.
broncoAbierto
9

Вероятность против логарифмической вероятности

Как уже было сказано, вводится с максимальной вероятностью просто потому, что оптимизировать суммы, как правило, проще, чем продукты. Причина, по которой мы не рассматриваем другие монотонные функции, заключается в том, что логарифм - это уникальная функция, обладающая свойством превращать произведения в суммы.log

Другой способ мотивации логарифма заключается в следующем: вместо того, чтобы максимизировать вероятность данных в нашей модели, мы могли бы эквивалентно попытаться минимизировать расхождение Кульбака-Лейблера между распределением данных и распределением модели p ( х θ ) ,pdata(x)p(xθ)

DKL[pdata(x)∣∣p(xθ)]=pdata(x)logpdata(x)p(xθ)dx=constpdata(x)logp(xθ)dx.

Первый член в правой части является постоянным в параметрах. Если у нас есть выборок из распределения данных (наши точки данных), мы можем приблизить второе слагаемое к средней логарифмической вероятности данных,N

pdata(x)logp(xθ)dx1Nnlogp(xnθ).

Альтернативный взгляд на ЭМ

Я не уверен, что это будет именно то объяснение, которое вы ищете, но я нашел следующий взгляд на максимизацию ожиданий гораздо более поучительным, чем его мотивация через неравенство Дженсена (подробное описание можно найти в Neal & Hinton (1998). или в книге PRML Криса Бишопа, глава 9.3).

Нетрудно показать, что

logp(xθ)=q(zx)logp(x,zθ)q(zx)dz+DKL[q(zx)∣∣p(zx,θ)]

для любого . Если мы назовем первый член в правой части F ( q , θ ) , это означает, чтоq(zx)F(q,θ)

F(q,θ)=q(zx)logp(x,zθ)q(zx)dz=logp(xθ)DKL[q(zx)∣∣p(zx,θ)].

Поскольку дивергенция KL всегда положительна , является нижней границей логарифмической вероятности для каждого фиксированного q . Теперь EM можно рассматривать как попеременно максимизирующую F относительно q и θ . В частности, путем установки д ( г | х ) = р ( г | х , & thetas ) в E-стадии, мы свести к минимуму расхождение KL на правой стороне , и , таким образом , максимально F .F(q,θ)qFqθq(zx)=p(zx,θ)F

Лукас
источник
Спасибо за пост! Хотя в данном документе не говорится, что логарифм - единственная функция, превращающая продукты в суммы. В нем говорится, что логарифм является единственной функцией, которая выполняет все три перечисленных свойства одновременно .
Weiwei
@ Weiwei: Да, но первое условие в основном требует, чтобы функция была обратимой. Конечно, f (x) = 0 также подразумевает f (x + y) = f (x) f (y), но это неинтересный случай. Третье условие требует, чтобы производная в 1 была 1, что верно только для логарифма по основанию . Отбросьте это ограничение, и вы получите логарифмы для разных оснований, но все равно логарифмы. e
Лукас
4

Бумага, которую я нашел разъясняющей в отношении максимизации ожидания, представляет собой байесовский метод K-средних как алгоритм «максимизация-ожидание» (pdf) по Welling и Kurihara.

Предположим, у нас есть вероятностная модель с x наблюдениями, z скрытыми случайными величинами и суммой θ параметров. Нам дан набор данных D и мы вынуждены (высшими силами) установить p (p(x,z,θ)xzθD .p(z,θ|D)

1. Выборка Гиббса

Мы можем аппроксимировать выборкой. Выборка Гиббса дает p ( z , θ | D ) , чередуя:p(z,θ|D)p(z,θ|D)

θp(θ|z,D)zp(z|θ,D)

2. Variational Bayes

Instead, we can try to establish a distribution q(θ) 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:

q(θ)exp(E[logp(θ,z,D)]q(z))q(z)exp(E[logp(θ,z,D)]q(θ))

3. Expectation-Maximization

To come up with full-fledged probability distributions for both z and θ might be considered extreme. Why don't we instead consider a point estimate for one of these and keep the other nice and nuanced. In EM the parameter θ is established as the one being unworthy of a full distribution, and set to its MAP (Maximum A Posteriori) value, θ.

θ=argmaxθE[logp(θ,z,D)]q(z)q(z)=p(z|θ,D)

θargmaxlog by exp doesn't change the result, so that is not necessary anymore.

4. Maximization-Expectation

zz for our hidden variables and give the parameters θ the luxury of a full distribution.

z=argmaxzE[logp(θ,z,D)]q(θ)q(θ)=p(θ|z,D)

If our hidden variables z 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.

θ=argmaxθp(θ,z,D)z=argmaxzp(θ,z,D)

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 a k-means alternative, but this lucid and concise exposition of approximation.

Anne van Rossum
источник
(+1) this is a beautiful summary of all methods.
kedarps
4

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

g(x)=iexp(fi(x))
(or equivalently logg(x)) with respect to x. If you write down an expression for g(x) and set it equal to zero you will often end up with a transcendental equation to solve. These can be nasty.

Now suppose that the fi 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 optimise logg(x)=logiexp(fi(x)) we could somehow shuffle the log past the so it could meet the exps 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 function h that is similar to g. And we'll make it out of linear combinations of the fi.

Let's say x0 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

g(x)=ifi(x)exp(fi(x)).
We want something that matches this at x0. There's a natural choice:
h(x)=constant+ifi(x)exp(fi(x0)).
You can see they match at x=x0. We get
h(x)=ifi(x)exp(fi(x0)).
As x0 is a constant we have a simple linear combination of the fi whose derivative matches g. We just have to choose the constant in h to make g(x0)=h(x0).

So starting with x0, 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 of h. This is exactly the procedure that takes place in EM.

But there's one more important point. Using Jensen's inequality you can show that h(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 the exp 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.

Dan Piponi
источник
3

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.

  1. 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 of K gaussians:

    p(x)=i=1KπiN(x|μi,Σi)
    where πi is the probability that the sample x was caused/generated by the ith component, μi is the mean of the distribution, and Σi is the covariance matrix. The way to understand this expression is the following: each data sample has been generated/caused by one component, but we do not know which one. The approach is then to express the uncertainty in terms of probability (πi represents the chances that the ith component can account for that sample), and take the weighted sum. As a concrete example, imagine you want to cluster text documents. The idea is to assume that each document belong to a topic (science, sports,...) which you do not know beforehand!. The possible topics are hidden variables. Then you are given a bunch of documents, and by counting n-grams or whatever features you extract, you want to then find those clusters and see to which cluster each document belongs to. EM is a procedure which attacks this problem step-wise: the expectation step attempts to improve the assignments of the samples it has achieved so far. The maximization step you improve the parameters of the mixture, in other words, the form of the clusters.
  2. 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.

jpmuc
источник