Русская Википедия:EM-алгоритм
EM-алгоритм (Шаблон:Lang-en) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На 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 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> \mathbf X </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>
Примеры использования
- k-means — алгоритм кластеризации, построенный на идее EM-алгоритма
- Метод упругих карт для нелинейного сокращения размерности данных
- Алгоритм Баума-Велша — алгоритм для оценки параметров скрытых марковских моделей
Примечания
Ссылки
Шаблон:Перевести Шаблон:Машинное обучение
