Interested Article - EM-алгоритм
![](/images/006/786/6786544/1.jpg?rand=406181)
![](https://cdn.wafarin.com/avatars/83ffde00f6480b8447091cf284a2af47.gif)
- 2020-01-12
- 1
EM-алгоритм ( англ. Expectation-maximization (EM) algorithm ) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных . Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия , при этом скрытые переменные рассматриваются как наблюдаемые . На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.
Часто EM-алгоритм используют для разделения смеси гауссиан .
Описание алгоритма
Пусть — некоторые из значений наблюдаемых переменных, а — скрытые переменные. Вместе и образуют полный набор данных. Вообще, может быть некоторой подсказкой, которая облегчает решение проблемы в случае, если она известна. Например, если имеется , функция правдоподобия легко выражается через параметры отдельных распределений смеси.
Положим — плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами : Эту функцию можно понимать как правдоподобие всей модели, если рассматривать её как функцию параметров . Заметим, что условное распределение скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:
- ,
используя расширенную формулу Байеса и формулу полной вероятности . Таким образом, нам необходимо знать только распределение наблюдаемой компоненты при фиксированной скрытой и вероятности скрытых данных .
EM-алгоритм итеративно улучшает начальную оценку , вычисляя новые значения оценок и так далее. На каждом шаге переход к от выполняется следующим образом:
где — матожидание логарифма правдоподобия. Другими словами, мы не можем сразу вычислить точное правдоподобие, но по известным данным ( ) мы можем найти апостериорную оценку вероятностей для различных значений скрытых переменных . Для каждого набора значений и параметров мы можем вычислить матожидание функции правдоподобия по данному набору . Оно зависит от предыдущего значения , потому что это значение влияет на вероятности скрытых переменных .
вычисляется следующим образом:
то есть это условное матожидание при условии .
Другими словами, — это значение, максимизирующее (M) условное матожидание (E) логарифма правдоподобия при данных значениях наблюдаемых переменных и предыдущем значении параметров. В непрерывном случае значение вычисляется так:
Альтернативное описание
При определённых обстоятельствах удобно рассматривать EM-алгоритм как два чередующихся шага максимизации. Рассмотрим функцию:
где q — распределение вероятностей ненаблюдаемых переменных Z ; p Z | X (· | x ; θ ) — условное распределение ненаблюдаемых переменных при фиксированных наблюдаемых x и параметрах θ ; H — энтропия и D KL — расстояние Кульбака-Лейблера .
Тогда шаги EM-алгоритма можно представить как:
-
E(xpectation) шаг
: Выбираем
q
, чтобы максимизировать
F
:
-
M(aximization) шаг
: Выбираем
θ
, чтобы максимизировать
F
:
Примеры использования
- k-means — алгоритм кластеризации , построенный на идее EM-алгоритма
- Метод упругих карт для нелинейного сокращения размерности данных
- Алгоритм Баума-Велша — алгоритм для оценки параметров скрытых марковских моделей
Примечания
- Radford; Neal; Hinton, Geoffrey . (англ.) // Learning in Graphical Models : journal / . — Cambridge, MA: MIT Press, 1999. — P. 355—368 . — ISBN 0262600323 . 7 июня 2020 года.
- Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome. 8.5 The EM algorithm // (неопр.) . — New York: Springer, 2001. — С. 236—243. — ISBN 0-387-95284-5 .
Ссылки
![](https://cdn.wafarin.com/avatars/83ffde00f6480b8447091cf284a2af47.gif)
- 2020-01-12
- 1