EM-алгоритм

Поделись знанием:
(перенаправлено с «ЕМ-алгоритм»)
Перейти к: навигация, поиск

EM-алгоритм (англ. Expectation-maximization (EM) algorithm) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

Часто EM-алгоритм используют для разделения смеси гауссиан.





Описание алгоритма

Пусть <math>\textbf{X}</math> — некоторые из значений наблюдаемых переменных, а <math>\textbf{T}</math> — скрытые переменные. Вместе <math>\textbf{X}</math> и <math>\textbf{T}</math> образуют полный набор данных. Вообще, <math>\textbf{T}</math> может быть некоторой подсказкой, которая облегчает решение проблемы в случае, если она известна. Например, если имеется смесь распределений, функция правдоподобия легко выражается через параметры отдельных распределений смеси.

Положим <math>p</math> — плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами <math>\Theta</math>: <math>p( \mathbf X, \mathbf T | \Theta).</math> Эту функцию можно понимать как правдоподобие всей модели, если рассматривать её как функцию параметров <math>\Theta</math>. Заметим, что условное распределение скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:

<math>p(\mathbf T |\mathbf X, \Theta) = \frac{p(\mathbf X, \mathbf T | \Theta)}{p(\mathbf X | \Theta)} = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{\int p(\mathbf X|\mathbf{\hat{T}}, \Theta) p(\mathbf{\hat{T}} |\Theta) d\mathbf{ \hat{T}}}</math>,

используя расширенную формулу Байеса и формулу полной вероятности. Таким образом, нам необходимо знать только распределение наблюдаемой компоненты при фиксированной скрытой <math>p(\mathbf X|\mathbf T, \Theta)</math> и вероятности скрытых данных <math>p(\mathbf T |\Theta)</math>.

EM-алгоритм итеративно улучшает начальную оценку <math>\Theta_0</math>, вычисляя новые значения оценок <math>\Theta_1, \Theta_2, </math> и так далее. На каждом шаге переход к <math>\Theta_{n+1}</math> от <math>\Theta_n</math> выполняется следующим образом:

<math>

\Theta_{n+1} = \arg\max_{\Theta}Q(\Theta) </math>

где <math>Q(\Theta)</math> — матожидание логарифма правдоподобия. Другими словами, мы не можем сразу вычислить точное правдоподобие, но по известным данным (<math>X</math>) мы можем найти апостериорную оценку вероятностей для различных значений скрытых переменных <math>T</math>. Для каждого набора значений <math>T</math> и параметров <math>\Theta</math> мы можем вычислить матожидание функции правдоподобия по данному набору <math>X</math>. Оно зависит от предыдущего значения <math>\Theta</math>, потому что это значение влияет на вероятности скрытых переменных <math>T</math>.

<math>Q(\Theta)</math> вычисляется следующим образом:

<math>

Q(\Theta) = 

E_{\mathbf T} \! \! \left[ \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) \Big| \mathbf X \right]

</math> то есть это условное матожидание <math>\log p \left( \mathbf X, \mathbf T \,|\, \Theta \right) </math> при условии <math> \Theta </math>.

Другими словами, <math>\Theta_{n+1}</math> — это значение, максимизирующее (M) условное матожидание (E) логарифма правдоподобия при данных значениях наблюдаемых переменных и предыдущем значении параметров. В непрерывном случае значение <math>Q(\Theta)</math> вычисляется так:

<math>

Q(\Theta)

E_{\mathbf T} \! \! \left[ \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) \Big| \mathbf X \right]

\int^\infty _{- \infty} 

p \left(\mathbf T \,|\, \mathbf X, \Theta_n \right)
\log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) d\mathbf T

</math>

Альтернативное описание

При определенных обстоятельствах удобно рассматривать EM-алгоритм как два чередующихся шага максимизации.[1][2] Рассмотрим функцию:

<math>F(q,\theta) = \operatorname{E}_q [ \log L (\theta ; x,Z) ] + H(q) = -D_{\text{KL}}\big(q \big\| p_{Z|X}(\cdot|x;\theta ) \big) + \log L(\theta;x) </math>

где q — распределение вероятностей ненаблюдаемых переменных Z; pZ|X(· |x;θ) — условное распределение ненаблюдаемых переменных при фиксированных наблюдаемых x и параметрах θ; H — энтропия и DKL — расстояние Кульбака-Лейблера.

Тогда шаги EM-алгоритма можно представить как:

E(xpectation) шаг: Выбираем q, чтобы максимизировать F:
<math> q^{(t)} = \operatorname*{arg\,max}_q \ F(q,\theta^{(t)}) </math>
M(aximization) шаг: Выбираем θ, чтобы максимизировать F:
<math> \theta^{(t+1)} = \operatorname*{\arg\,max}_{\theta} \ F(q^{(t)},\theta) </math>

Примеры использования

Напишите отзыв о статье "EM-алгоритм"

Примечания

  1. ↑ (1999) «A view of the EM algorithm that justifies incremental, sparse, and other variants». Learning in Graphical Models (MIT Press): 355–368. Проверено 2009-03-22.
  2. ↑ 8.5 The EM algorithm // The Elements of Statistical Learning. — New York: Springer, 2001. — P. 236–243.

Ссылки

  • [www.socr.ucla.edu/htmls/SOCR_Experiments.html Демонстрация разделения смеси гауссиан с помощью EM-алгоритма]
  • [lcn.epfl.ch/tutorial/english/mixtureModel/index.html Реализация на Java]

Отрывок, характеризующий EM-алгоритм

– Как, как это ты сказал? – спросил Пьер.
– Я то? – спросил Каратаев. – Я говорю: не нашим умом, а божьим судом, – сказал он, думая, что повторяет сказанное. И тотчас же продолжал: – Как же у вас, барин, и вотчины есть? И дом есть? Стало быть, полная чаша! И хозяйка есть? А старики родители живы? – спрашивал он, и хотя Пьер не видел в темноте, но чувствовал, что у солдата морщились губы сдержанною улыбкой ласки в то время, как он спрашивал это. Он, видимо, был огорчен тем, что у Пьера не было родителей, в особенности матери.
– Жена для совета, теща для привета, а нет милей родной матушки! – сказал он. – Ну, а детки есть? – продолжал он спрашивать. Отрицательный ответ Пьера опять, видимо, огорчил его, и он поспешил прибавить: – Что ж, люди молодые, еще даст бог, будут. Только бы в совете жить…
– Да теперь все равно, – невольно сказал Пьер.
– Эх, милый человек ты, – возразил Платон. – От сумы да от тюрьмы никогда не отказывайся. – Он уселся получше, прокашлялся, видимо приготовляясь к длинному рассказу. – Так то, друг мой любезный, жил я еще дома, – начал он. – Вотчина у нас богатая, земли много, хорошо живут мужики, и наш дом, слава тебе богу. Сам сем батюшка косить выходил. Жили хорошо. Христьяне настоящие были. Случилось… – И Платон Каратаев рассказал длинную историю о том, как он поехал в чужую рощу за лесом и попался сторожу, как его секли, судили и отдали ь солдаты. – Что ж соколик, – говорил он изменяющимся от улыбки голосом, – думали горе, ан радость! Брату бы идти, кабы не мой грех. А у брата меньшого сам пят ребят, – а у меня, гляди, одна солдатка осталась. Была девочка, да еще до солдатства бог прибрал. Пришел я на побывку, скажу я тебе. Гляжу – лучше прежнего живут. Животов полон двор, бабы дома, два брата на заработках. Один Михайло, меньшой, дома. Батюшка и говорит: «Мне, говорит, все детки равны: какой палец ни укуси, все больно. А кабы не Платона тогда забрили, Михайле бы идти». Позвал нас всех – веришь – поставил перед образа. Михайло, говорит, поди сюда, кланяйся ему в ноги, и ты, баба, кланяйся, и внучата кланяйтесь. Поняли? говорит. Так то, друг мой любезный. Рок головы ищет. А мы всё судим: то не хорошо, то не ладно. Наше счастье, дружок, как вода в бредне: тянешь – надулось, а вытащишь – ничего нету. Так то. – И Платон пересел на своей соломе.
Помолчав несколько времени, Платон встал.
– Что ж, я чай, спать хочешь? – сказал он и быстро начал креститься, приговаривая:
– Господи, Иисус Христос, Никола угодник, Фрола и Лавра, господи Иисус Христос, Никола угодник! Фрола и Лавра, господи Иисус Христос – помилуй и спаси нас! – заключил он, поклонился в землю, встал и, вздохнув, сел на свою солому. – Вот так то. Положи, боже, камушком, подними калачиком, – проговорил он и лег, натягивая на себя шинель.
– Какую это ты молитву читал? – спросил Пьер.
– Ась? – проговорил Платон (он уже было заснул). – Читал что? Богу молился. А ты рази не молишься?
– Нет, и я молюсь, – сказал Пьер. – Но что ты говорил: Фрола и Лавра?
– А как же, – быстро отвечал Платон, – лошадиный праздник. И скота жалеть надо, – сказал Каратаев. – Вишь, шельма, свернулась. Угрелась, сукина дочь, – сказал он, ощупав собаку у своих ног, и, повернувшись опять, тотчас же заснул.
Наружи слышались где то вдалеке плач и крики, и сквозь щели балагана виднелся огонь; но в балагане было тихо и темно. Пьер долго не спал и с открытыми глазами лежал в темноте на своем месте, прислушиваясь к мерному храпенью Платона, лежавшего подле него, и чувствовал, что прежде разрушенный мир теперь с новой красотой, на каких то новых и незыблемых основах, воздвигался в его душе.


В балагане, в который поступил Пьер и в котором он пробыл четыре недели, было двадцать три человека пленных солдат, три офицера и два чиновника.
Все они потом как в тумане представлялись Пьеру, но Платон Каратаев остался навсегда в душе Пьера самым сильным и дорогим воспоминанием и олицетворением всего русского, доброго и круглого. Когда на другой день, на рассвете, Пьер увидал своего соседа, первое впечатление чего то круглого подтвердилось вполне: вся фигура Платона в его подпоясанной веревкою французской шинели, в фуражке и лаптях, была круглая, голова была совершенно круглая, спина, грудь, плечи, даже руки, которые он носил, как бы всегда собираясь обнять что то, были круглые; приятная улыбка и большие карие нежные глаза были круглые.
Платону Каратаеву должно было быть за пятьдесят лет, судя по его рассказам о походах, в которых он участвовал давнишним солдатом. Он сам не знал и никак не мог определить, сколько ему было лет; но зубы его, ярко белые и крепкие, которые все выкатывались своими двумя полукругами, когда он смеялся (что он часто делал), были все хороши и целы; ни одного седого волоса не было в его бороде и волосах, и все тело его имело вид гибкости и в особенности твердости и сносливости.
Лицо его, несмотря на мелкие круглые морщинки, имело выражение невинности и юности; голос у него был приятный и певучий. Но главная особенность его речи состояла в непосредственности и спорости. Он, видимо, никогда не думал о том, что он сказал и что он скажет; и от этого в быстроте и верности его интонаций была особенная неотразимая убедительность.


Источник — «http://wiki-org.ru/wiki/index.php?title=EM-алгоритм&oldid=79926777»