ЕМ-процедура

ЕМ-процедура

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

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

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

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

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

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}},

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

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

Θn + 1 = argmaxΘQ(Θ)

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

Q(Θ) вычисляется следующим образом:


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

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

Другими словами, Θn + 1 - это значение, маскимизирующее (M) условное матожидание (E) логарифма правдоподобия при данных значениях наблюдаемых переменных и предыдущем значении параметров. В непрерывном случае значение Q(Θ) вычисляется так:


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


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

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "ЕМ-процедура" в других словарях:

  • ПРОЦЕДУРА — (ново лат., от лат. procedere проистекать, происходить). 1) порядок, способ ведения дела в суде. 2) если говорят о медленности исполнения чего либо, то употребляют выражение «длинная или долгая процедура»; вообще всякое длительное,… …   Словарь иностранных слов русского языка

  • процедура — Упорядоченная совокупность взаимосвязанных определенными отношениями действий, направленных на решение задачи. [МУ 64 01 001 2002] процедура Установленный способ осуществления деятельности или процесса. Примечания 1. Процедуры могут быть… …   Справочник технического переводчика

  • Процедура — Процедура  взаимосвязанная последовательность действий, например Медицинская процедура Процедура в программировании Процедура банкротства Таможенная процедура …   Википедия

  • процедура — ы, ж. procédure <лат. procedere продвигаться. 1. Официально установленная последовательность действий для осуществления или выполнения чего л. Процедура голосования. Процедура подписания договора. БАС 1. Началась обычная процедура:… …   Исторический словарь галлицизмов русского языка

  • Процедура Кэли — Диксона (процедура удвоения) это рекурсивная процедура построения алгебр над полем вещественных чисел, с удвоением размерности на каждом шагу. Названа в честь Артура Кэли и Леонарда Диксона. Эта процедура позволяет построить комплексные числа,… …   Википедия

  • процедура обжалования — апелляционная процедура процедура подачи и рассмотрения апелляции производство по апелляции — [Упрощение процедур торговли: англо русский глоссарий терминов (пересмотренное второе издание) НЬЮ ЙОРК, ЖЕНЕВА, МОСКВА 2011 год] EN appeal… …   Справочник технического переводчика

  • Процедура — (иноск.) обрядъ, порядокъ, ходъ дѣла, длительное, послѣдовательное дѣло (процедура собств. шествіе, ходъ). Ср. Началась обычная процедура: перечисленіе присяжныхъ засѣдателей, разсужденіе о неявившихся, наложеніи на нихъ штрафовъ... Гр. Л. Н.… …   Большой толково-фразеологический словарь Михельсона (оригинальная орфография)

  • ПРОЦЕДУРА — ПРОЦЕДУРА, процедуры, жен. (от лат. procedo иду вперед). 1. Порядок выполнения, ряд последовательных действий, необходимых для выполнения чего нибудь (книжн.). Процедура подписания договора. Судебная процедура. Сложная процедура. 2. Отдельный… …   Толковый словарь Ушакова

  • процедура — См …   Словарь синонимов

  • Процедура выбора столицы Олимпийских игр — Согласно Олимпийской хартии, честь организации Олимпийских игр представляется городу, а не стране. Предложения об организации Игр, исходящие от высших властей города и подтвержденные Национальным Олимпийским комитетом страны, в которой находится… …   Энциклопедия ньюсмейкеров

  • Процедура выборов мэра Москвы — Выборы мэра и вице мэра Москвы проводятся в соответствии с основными законодательными актами РФ и города Москвы – Конституцией РФ, Федеральными законами от 6 декабря 1994 года Об основных гарантиях избирательных прав граждан РФ и от 19 мая… …   Энциклопедия ньюсмейкеров


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»