EM-алгоритм

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Описание алгоритма[править | править вики-текст]

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

Положим p\, — плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами \Theta: p( \mathbf X, \mathbf T | \Theta). Эту функцию можно понимать как правдоподобие всей модели, если рассматривать её как функцию параметров \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-алгоритм итеративно улучшает начальную оценку \Theta_0, вычисляя новые значения оценок \Theta_1, \Theta_2, и так далее. На каждом шаге переход к \Theta_{n+1}\, от \Theta_n\, выполняется следующим образом:


\Theta_{n+1}
=
\arg\max_{\Theta}Q(\Theta)

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

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


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) при условии  \Theta .

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


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

Альтернативное описание[править | править вики-текст]

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

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)

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

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

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

Примеры использования[править | править вики-текст]

Примечания[править | править вики-текст]

  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.

Ссылки[править | править вики-текст]