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 {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)$ при условии $\mathbf {X}$ .

Другими словами, $\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; p_Z|X(· |x;θ) — условное распределение ненаблюдаемых переменных при фиксированных наблюдаемых x и параметрах θ; H — энтропия и D_KL — расстояние Кульбака-Лейблера.

Тогда шаги 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 )

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

k-means — алгоритм кластеризации, построенный на идее EM-алгоритма
Метод упругих карт для нелинейного сокращения размерности данных
Алгоритм Баума-Велша — алгоритм для оценки параметров скрытых марковских моделей

Примечания

↑ Radford; Neal; Hinton, Geoffrey. A view of the EM algorithm that justifies incremental, sparse, and other variants (англ.) // Learning in Graphical Models : journal / Michael I. Jordan. — Cambridge, MA: MIT Press, 1999. — P. 355—368. — ISBN 0262600323. Архивировано 7 июня 2020 года.
↑ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome. 8.5 The EM algorithm // The Elements of Statistical Learning (неопр.). — New York: Springer, 2001. — С. 236—243. — ISBN 0-387-95284-5.

Ссылки

[neal1999-1] Radford; Neal; Hinton, Geoffrey. A view of the EM algorithm that justifies incremental, sparse, and other variants (англ.) // Learning in Graphical Models : journal / Michael I. Jordan. — Cambridge, MA: MIT Press, 1999. — P. 355—368. — ISBN 0262600323. Архивировано 7 июня 2020 года.

[hastie2001-2] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome. 8.5 The EM algorithm // The Elements of Statistical Learning (неопр.). — New York: Springer, 2001. — С. 236—243. — ISBN 0-387-95284-5.

[1]

[2]

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG

EM-алгоритм

Содержание

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

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

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

Примечания

Ссылки

Навигация

EM-алгоритм

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

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

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

Примечания

Ссылки

Навигация

Поиск