Алгоритм ожидания - максимизации

Итерационный метод поиска оценок максимального правдоподобия в статистических моделях

В статистике, алгоритм ожидания - максимизации (EM) - это итерационный метод для нахождения (локального) максимальный правдоподобия или максимальный апостериорный (MAP) оценки параметров в статистических моделях, где модель зависит от ненаблюдаемых скрытых чисел. Итерация EM проходит между выполнением этапа ожидания (E), который выполняет ожидаемую функцию для ожидания журнал-правдоподобия, оцененный с использованием текущих параметров, этапом максимизации (M), вычисляет параметры, максимизирующие логарифмическую правдоподобие, найденную на шаге E Эти методы используются для определения определения скрытых на следующем этапе E.

ЭМ-кластеризация данных извержении Старый Верный. Случайная исходная модель (которая из-за разных масштабов кажется двумя очень плоскими и широкими сферами) соответствует наблюдаемым данным. На первых страницах модель простого, но затем сходится к двум режимам гейзера. Визуализируется с помощью ELKI.

• 1 История
• 2 Введение
• 3 Описание
• 4 Свойства
• 5 Подтверждение правильности
• 6 В качестве процедуры максимизации - максимизации
• 7 Приложения
• 8 Фильтрация и сглаживание EM-алгоритмов
• 9 Варианты
  • 9.1 Алгоритм α-EM
• 10 Связь с вариационными байесовскими методами
• 11 Геометрическая интерпретация
• 12 Примеры
  • 12.1 Гауссова смесь
    • 12.1.1 Шаг E
    • 12.1.2 Шаг M
    • 12.1.3 Завершение
    • 12.1.4 Обобщение
  • 12.2 Усеченная и цензурированная регрессия
• 13 Альтернативы
• 14 См. Также
• 15 Ссылки
• 16 Дополнительная литература
• 17 Внешние ссылки

Алгоритм EM был объяснен и получил свое название в классической статье 1977 года Артуром Демпстером, Нэн Лэрд и Дональд Рубин. Они отметили, что этот метод «много раз предлагался при обстоятельствах» более ранними авторами. Один из первых - это метод подсчета генов для оценки частот аллелей по Седрику Смиту. Очень подробное описание метода ЭМ для экспоненциальных семейств было опубликовано Рольфом Сундбергом в его диссертации и нескольких статьях после его сотрудничества с Пер Мартин-Лёф и Андерсом Мартином-Лёфом. Статья Демпстера - Лэрда - Рубина 1977 г. обобщила этот метод и наметила анализ сходимости для более широкого класса проблем. В статье Демпстера - Лэрда - Рубина ЭМ-метод определен как важный инструмент статистического анализа.

Анализ сходимости алгоритма Демпстера - Лэрда - Рубина был некорректным, и С. опубликовал правильный анализ сходимости. Ф. Джефф Ву в 1983 году. Доказательство Ву установило сходимость метода ЭМ вне экспоненциального семейства, как утверждал Демпстер-Лэрд-Рубин.

Алгоритм EM используется для поиска (локальных) параметров правдоподобия статистической модели в случаях, когда уравнения не могут быть решены напрямую. Обычно эти модели включают скрытые переменные в дополнение к неизвестным параметрам и известным данным наблюдений. То есть либо данных существует пропущенных значений, либо модель может быть сформулирована более просто, допуская существование дополнительных ненаблюдаемых точек данных. Например, модель смеси можно описать более просто, если предположить, что последняя точка имеет ненаблюдаемую точку данных или скрытую переменную, определяющую компонент смеси, соответствующую каждую точку данных.

Для поиска решений с максимальным правдоподобием обычно требуется брать производные от функции правдоподобия по всем неизвестным значениям, параметрам и скрытым переменным и используемым уравнениям. В статистических моделях со скрытыми переменными это обычно невозможно. Вместо этого обычно является набором взаимосвязанных параметров, требуемых параметров, используемых друг с другом.

Алгоритм EM исходит из наблюдения, что существует способ решить эти два набора инструментовенно. Можно просто выбрать два произвольных значения для одного набора неизвестных, использовать их для оценки второго набора, затем использовать эти новые значения, чтобы найти лучшую оценку первого набора, а затем продолжить чередовать эти два, пока оба результата не получат. сходятся к неподвижным точкам. Не очевидно, что это сработает, но можно доказать, что в данном контексте это работает, и что производная вероятность (произвольно близка) к нулю в этой точке, что, в свою очередь, означает, что точка является либо максимумом, либо a седловая точка. Как правило, могут быть найдены глобальные максимумы без гарантии, что глобальный максимум будет найден. Некоторые вероятности также содержат особенности, то есть бессмысленные максимумы. Например, одно из решений, которое может быть найдено ЭМ в смешанной модели, включает установку одного из компонентов, чтобы иметь нулевую дисперсию, и параметр среднего значения для того же компонента, равный одной из точек данных.

Учитывая статистическую модель, которая генерирует набор $X\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{X\}\}$наблюдаемых данных, набор ненаблюдаемых скрытых данных или отсутствующих значений $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$и вектор неизвестных параметров $\theta \; \{\backslash \; displaystyle\; \{\backslash \; жирный\; символ\; \{\backslash \; theta\}\}\; \}$вместе с функция правдоподобия $L\; (\theta ;\; X,\; Z)\; =\; p\; (X,\; Z\; \mid \; \theta )\; \{\backslash \; displaystyle\; L\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ;\; \backslash \; mathbf\; \{X\},\; \backslash \; mathbf\; \{Z\})\; =\; p\; (\backslash \; mathbf\; \{X\},\; \backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\}$, оценка максимальное правдоподобия (MLE) неизвестных факторов путем максимизации предельного правдоподобия наблюдаемых данных

$L\; (\theta ;\; X)\; =\; p\; (Икс\; \mid \; \theta )\; знак\; равно\; п\; (Икс,\; Z\; \mid \; \theta )\; d\; Z\; \{\backslash \; Displaystyle\; L\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\};\; \backslash \; mathbf\; \{X\})\; =\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; =\; \backslash \; int\; p\; (\backslash \; mathbf\; \{X\},\; \backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; \backslash ,\; d\; \backslash \; mathbf\; \{Z\}\}$

Однако часто это количество я решаемый (например, если $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$представляет собой последовательность событий, так что количество роста растет.

Алгоритм EM пытается найти MLE предельного правдоподобия, итеративно применяя эти два шага:

Шаг ожидания (шаг E): Определите $Q\; (\theta \; \mid \; \theta \; (t))\; \{\backslash \; displaystyle\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\}$как ожидаемое значение журнала функция правдоподобия для $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$относительно текущего условного распределения $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$с учетом $X\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{X\}\}$и текущих оценок параметров $\theta \; (t)\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}\}$:

$Q\; (\theta \; \mid \; \theta \; (t))\; =\; EZ\; \mid \; X,\; \theta \; (t)\; \; [журнал\; \; L\; (\theta ;\; X,\; Z)]\; \{\backslash \; Displaystyle\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\; \backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; =\; \backslash \; operatorname\; \{E\}\; \_\; \{\backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \backslash \; mathbf\; \{X\},\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}\}\; \backslash \; left\; [\backslash \; log\; L\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\};\; \backslash \; mathbf\; \{X\},\; \backslash \; mathbf\; \{Z\})\; \backslash \; right]\; \backslash ,\}$

Шаг максимизации (шаг M): F и параме тр ы, которые максимизируют это количество:

$\theta \; (t\; +\; 1)\; =\; argmax\; \theta \; Q\; (\theta \; \mid \; \theta \; (t))\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t\; +\; 1)\}\; =\; \{\; \backslash \; нижний\; набор\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \{\backslash \; operatorname\; \{arg\; \backslash ,\; max\}\}\}\; \backslash \; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; \backslash ,\}$

Типичные модели, используемые ЭМ, используют $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$как скрытую переменную, указывающий член в одном из наборов групп:

1. Наблюдаемые точки данных $X\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{X\}\}$могут быть дискретными (принимающими значения в конечном или счетно бесконечном множестве) или непрерывными (последние значения в несчетно бесконечном множестве). С каждой точкой данных может быть связан вектор наблюдений.
2. пропущенные значения (также известные как скрытые переменные ) $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$являются дискретными взятыми из фиксированного количества значений и с одной скрытой на наблюдаемой единице.
3. Параметры непрерывными и бывают двух видов: Параметры, которые связаны со всеми точками данных, и параметры, связанные с конкретным значением скрытой переменной (т. Е. Связанные со всеми точками данных, у соответствующая скрытая переменная имеет это значение).

Однако можно применить EM к другим всякие модели.

Мотив следующий. Если известно значение параметров $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$, обычно значение скрытых чисел $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$можно найти, максимизируя логарифмическую вероятность для всех обнаруженных $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$, либо просто перебирая $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$или с помощью такого алгоритма, как алгоритм Баума - Велча для скрытых марковских моделей. И наоборот, если мы знаем значение скрытых чисел $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$, мы можем найти оценку параметров $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$довольно легко, обычно простой способ группировки наблюдаемых точек данных в соответствии с указанными значениями скрытой и усреднения значений или некоторой функции значений точек в каждой группе. Это предполагает итеративный алгоритм в случае, когда и $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$, и $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$неизвестны:

1. Сначала инициализируйте параметры $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$некоторыми случайными значениями.
2. Вычислите вероятность каждого возможного значения $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$, учитывая $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$.
3. Затем используйте только -вычисленные значения $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$для вычислений более точной оценки параметров $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$.
4. Повторяйте шаги 2 и 3 до сходимости.

Алгоритм, как только что описанный, монотонно приближается к локальному минимуму функции стоимости.

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

Хотя итерация EM увеличивает текущие данные (т. Е. Маргинальную) функцию правдоподобия, нет гарантии, что последовательность сходится к оценке значения правдоподобия. Для мультимодальных распределений это означает, что алгоритм EM может сходиться к локальному максимуму наблюдаемой функции правдоподобия данных, в зависимости от начальных значений. Существует множество эвристических или метаэвристических подходов, позволяющих избежать локального максимума, как такой случайный перезапуск восхождение на холм (начиная с нескольких различных случайных начальных оценок θ) или применение смоделированного методы отжига.

EM особенно полезен, когда вероятность является экспоненциальным семейством : шаг E суммой ожиданий достаточной статистики, а шаг M включает максимизацию линейного функции. В таком случае обычно можно получить обновления выражения в закрытой форме для каждого шага, используя формулу Сундберга (опубликованную Рольфом Сундбергом с использованием неопубликованных результатов Согласно Мартин-Лёф и Андерс Мартин-Лёф ).

Метод EM был изменен для вычислений максимальных апостериорных (MAP) оценок для байесовского вывода в исходной статье Демпстера, Лэрда и Рубина.

Существуют другие методы для поиска оценок повышения правдоподобия, как градиентный спуск, сопряженный градиент или варианты алгоритма Гаусса - Ньютона. В отличие от EM, такие методы обычно требуют оценки первой и / или второй производных функций правдоподобия.

Максимизация ожидания работает для улучшения $Q\; (\theta \; \mid \; \theta \; (t))\; \{\backslash \; displaystyle\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\}$вместо прямого улучшения $журнала\; \; п\; (Икс\; \mid \; \theta )\; \{\backslash \; Стиль\; отображения\; \backslash \; журнал\; р\; (\backslash \; mathbf\; \{X\}\; \backslash \; ми\; d\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\}$. Здесь показано, что улучшения первого подразумевают улучшения второго.

Для любого $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$с ненулевой вероятностью $p\; (Z\; \mid \; X,\; \theta )\; \{\backslash \; displaystyle\; p\; (\backslash \; mathbf\; \{Z\; \}\; \backslash \; mid\; \backslash \; mathbf\; \{X\},\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\}$, мы можем записать

$журнал\; \; p\; (X\; \mid \; \theta )\; =\; журнал\; \; p\; (X,\; Z\; \mid \; \theta )\; -\; журнал\; \; p\; (Z\; \mid \; X,\; \theta ).\; \{\backslash \; displaystyle\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; =\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\},\; \backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; -\; \backslash \; log\; p\; (\backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \backslash \; mathbf\; \{X\},\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}).\}$

Мы берем математическое ожидание по возможным значениям неизвестных данных $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$при текущей оценке программы $\theta \; (t)\; \{\backslash \; displaystyle\; \backslash \; theta\; ^\; \{(t)\}\}$путем умножения обеих сторон на $п\; (Z\; \mid \; Икс,\; \theta \; (t))\; \{\backslash \; displaystyle\; p\; (\backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \backslash \; mathbf\; \{X\},\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\}$и суммирование (или интегрирование) по $Z\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Z\}\}$. Левая часть представляет собой математическое ожидание константы, поэтому мы получаем:

$log\; \; p\; (X\; \mid \; \theta )\; =\; \sum \; Z\; p\; (Z\; \mid \; X,\; \theta \; (t))\; log\; \; p\; (X,\; Z\; \mid \; \theta ).)\; -\; \sum \; Z\; п\; (Z\; \mid \; Икс,\; \theta \; (t))\; журнал\; \; п\; (Z\; \mid \; X,\; \theta )\; =\; Q\; (\theta \; \mid \; \theta \; (t))\; +\; H\; (\theta \; \mid \; \theta \; (t)),\; \{\backslash \; displaystyle\; \{\; \backslash \; begin\; \{align\}\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; =\; \backslash \; sum\; \_\; \{\backslash \; mathbf\; \{Z\}\}\; p\; (\backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \backslash \; mathbf\; \{X\; \},\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\},\; \backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; -\; \backslash \; sum\; \_\; \{\backslash \; mathbf\; \{Z\}\}\; p\; (\backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \backslash \; mathbf\; \{X\},\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; \backslash \; log\; p\; (\backslash \; mathbf\; \{Z\}\; \backslash \; mid\; \backslash \; mathbf\; \{X\},\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; \backslash \backslash \; =\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; +\; H\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\; \}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}),\; \backslash \; end\; \{align\}\}\}$

где $H\; (\theta \; \mid \; \theta \; (t))\; \{\backslash \; displaystyle\; H\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\}$определяется отрицательной суммой, которую он заменяет. Это последнее уравнение справедливо для каждого значения $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$, включая $\theta \; =\; \theta \; (t)\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\; \}\; =\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}\}$,

$журнал\; \; p\; (X\; \mid \; \theta \; (t))\; =\; Q\; (\theta \; (t)\; \mid \; \theta \; (t))\; +\; H\; (\theta \; (t)\; \mid \; \theta \; (т)),\; \{\backslash \; displaystyle\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; =\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{\; (t)\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; +\; H\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{\; (t)\}),\}$

и вычитание этого последнего уравнения из предыдущих уравнений дает

$log\; \; p\; (X\; \mid \; \theta )\; -\; log\; \; p\; (X\; \mid \; \theta \; (t))\; =\; Q\; (\theta \; \mid \; \theta \; (t))\; -\; Q\; (\theta \; (t)\; \mid \; \theta \; (t))\; +\; H\; (\theta \; \mid \; \theta \; (t))\; -\; H\; (\theta \; (t)\; \mid \; \theta \; (t)),\; \{\backslash \; displaystyle\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\; \}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; -\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; =\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; -\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; +\; H\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; -\; H\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}),\}$

Однако Неравенство Гиббса говорит нам, что $H\; (\theta \; \mid \; \theta \; (t))\; \ge \; H\; (\theta \; (t)\; \mid \; \theta \; (t))\; \{\backslash \; displaystyle\; H\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; \backslash \; geq\; H\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(\; t)\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\}$, поэтому мы можем заключить, что

$log\; \; p\; (X\; \mid \; \theta )\; -\; log\; \; p\; (\; X\; \mid \; \theta \; (t))\; \ge \; Q\; (\theta \; \mid \; \theta \; (t))\; -\; Q\; (\theta \; (t)\; \mid \; \theta \; (t)).\; \{\backslash \; displaystyle\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\; -\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; \backslash \; geq\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\; -\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\}).\}$

На словах, выбирая $\theta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\}$для улучшения $Q\; (\theta \; \mid \; \theta \; (t))\; \{\backslash \; displaystyle\; Q\; (\{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\}\; ^\; \{(t)\})\}$вызывает $журнал\; \; p\; (Икс\; \mid \; \theta )\; \{\backslash \; displaystyle\; \backslash \; log\; p\; (\backslash \; mathbf\; \{X\}\; \backslash \; mid\; \{\backslash \; boldsymbol\; \{\backslash \; theta\}\})\}$, чтобы улучшить как минимум на столько же.

Алгоритм EM можно рассматривать как два чередующих шага максимизации, то есть как пример спуска координаты. Рассмотрим функцию:

$F\; (q,\; \theta ):\; =\; E\; q\; \; [журнал\; \; L\; (\theta ;\; x,\; Z)]\; +\; H\; (q),\; \{\backslash \; displaystyle\; F\; (q,\; \backslash \; theta):\; =\; \backslash \; operatorname\; \{\; E\}\; \_\; \{q\}\; [\backslash \; log\; L\; (\backslash \; theta;\; x,\; Z)]\; +\; H\; (q),\}$

где q - произвольное распределение вероятностей по ненаблюдаемым данным z, а H (q) - энтропия распределения q. Эту функцию можно записать как

$F\; (q,\; \theta )\; =\; -\; DKL\; (q\; \parallel \; p\; Z\; \mid \; X\; (\cdot \; \mid \; x;\; \theta ))\; +\; журнал\; \; L\; (\theta ;\; x),\; \{\backslash \; displaystyle\; F\; (q,\; \backslash \; theta)\; =\; -\; D\; \_\; \{\backslash \; mathrm\; \{KL\}\}\; \{\backslash \; big\; (\}\; q\; \backslash \; parallel\; p\_\; \{Z\; \backslash \; mid\; X\}\; (\backslash \; cdot\; \backslash \; mid\; x;\; \backslash \; theta)\; \{\backslash \; big)\}\; +\; \backslash \; log\; L\; (\backslash \; theta\; ;\; x),\}$

где $p\; Z\; \mid \; X\; (\cdot \; \mid \; x;\; \theta )\; \{\backslash \; displaystyle\; p\_\; \{Z\; \backslash \; mid\; X\}\; (\backslash \; cdot\; \backslash \; mid\; x;\; \backslash \; theta)\}$- условное распределение ненаблюдаемых данных с учетом наблюдаемых данных $x\; \{\backslash \; displaystyle\; x\}$и $DKL\; \{\backslash \; displaystyle\; D\_\; \{KL\}\}$- Расхождение Кульбака - Лейблера.

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

Шаг ожидания: выбрать $q\; \{\backslash \; displaystyle\; q\}$, чтобы максимизировать $F\; \{\backslash \; displaystyle\; F\}$:

$q\; (t)\; знак\; равно\; argmaxq\; \; F\; (q,\; \theta \; (t))\; \{\backslash \; displaystyle\; q\; ^\; \{(t)\}\; =\; \backslash \; operatorname\; \{arg\; \backslash ,\; max\}\; \_\; \{q\}\; \backslash \; F\; (q,\; \backslash \; theta\; ^\; \{(\; t)\})\}$

Шаг максимизации: выберите $\theta \; \{\backslash \; displaystyle\; \backslash \; theta\}$, чтобы максимизировать $F\; \{\backslash \; displaystyle\; F\}$:

$\theta \; (t\; +\; 1)\; знак\; равн\; о\; argmax\; \theta \; \; F\; (q\; (t),\; \theta )\; \{\backslash \; displaystyle\; \backslash \; th\; eta\; ^\; \{(t\; +\; 1)\}\; =\; \backslash \; operatorname\; \{arg\; \backslash ,\; max\}\; \_\; \{\backslash \; theta\}\; \backslash \; F\; (q\; ^\; \{(t)\; \},\; \backslash \; theta)\}$

EM - это часто используется для кластеризации данных в машинном обучении и компьютерном зрении. В обработка естественного языка два примера алгоритма - это алгоритм Баума - Велча для скрытых марковских моделей и алгоритм-снаружи для неконтролируемой индукции вероятностных контекстно-свободных грамматик.

EM используется для оценки параметров смешанных моделей, особенно в количественной генетике.

в психометрии, EM практически для оценки параметров предмета и скрытых способностей моделей теории отклика предмета.

Благодаря способности работать с отсутствующими данными и наблюдать неидентифицированные переменные, EM становится полезным инструментом для определения цены и управления рисками портфеля.

Алгоритм EM (и его более быстрый вариант максимизация ожидаемого упорядоченного подмножества ) также широко используется в реконструкции изображений, особенно в позитронно-эмиссионной томографии, однофотонной эмиссионной компьютерной томографии и x -ray компьютерная томография. См. Ниже другие быстрые варианты EM.

В проектирование конструкций, структурная идентификация с использованием алгоритма максимизации ожидания (STRIDE) - метод только для вывода свойств естественной вибрации структурной системы с использованием датчиков (см. Эксплуатация Модальный анализ ).

A фильтр Калмана обычно используется для оценки состояния в оперативном режиме, а сглаживатель с минимальной дисперсией может оценивать состояния в автономном режиме или в пакетном режиме. Однако эти решения с минимальной дисперсией требуют оценок параметров в космических условиях. EM-"Программы" Моя книга задач оценивания состояния и параметров.

ЭМ-алгоритмы фильтрации и сглаживания возникают в результате повторения этой двухэтапной процедуры:

E-step

Используйте фильтр Калмана или сглаживатель с минимальной дисперсией, с текущими оценками параметров для получения обновленных оценок состояния.

M-шаг

Используйте отфильтрованные или сглаженные оценки состояния в вычислениях максимального правдоподобия для получения обновленных оценок параметров.

Предположим, что фильтр Калмана или минимальное устройство сглаживания дисперсии работает с измерениями системы с одним входом и одним выходом, которые обладают аддитивным белым шумом. Обновленная оценка дисперсии шума измерения может быть получена из расчета Максимальная правдоподобия

$\sigma \; ^\; v\; 2\; =\; 1\; N\; \sum \; k\; =\; 1\; N\; (zk\; -\; x\; ^\; k)\; 2,\; \{\backslash \; displaystyle\; \{\backslash \; widehat\; \{\backslash \; sigma\}\}\; \_\; \{v\}\; ^\; \{2\}\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{N\}\; \{(z\_\; \{k\}\; -\; \{\backslash \; widehat\; \{x\}\}\; \_\; \{\; k\})\}\; ^\; \{2\},\}$

где $x\; ^\; k\; \{\backslash \; displaystyle\; \{\backslash \; widehat\; \{x\}\}\; \_\; \{k\}\}$- скалярные оценки выходных данных, рассчитанные фильтр или сглаживание из N скалярных измерений $zk\; \{\backslash \; displaystyle\; z\_\; \{k\}\}$. Вышеупомянутое обновление также можно применить для обновления шума измерения Пуассона. Аналогично, для авторегрессивного процесса первого порядка обновленной оценки дисперсии шума может быть рассчитана как

$\sigma \; ^\; w\; 2\; =\; 1\; N\; \sum \; k\; =\; 1\; N\; (x\; ^\; k\; +\; 1\; -\; F\; ^\; x\; ^\; k)\; 2,\; \{\backslash \; displaystyle\; \{\; \backslash \; widehat\; \{\backslash \; sigma\}\}\; \_\; \{w\}\; ^\; \{2\}\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{N\}\; \{(\{\backslash \; widehat\; \{x\}\}\; \_\; \{k\; +\; 1\}\; -\; \{\backslash \; widehat\; \{F\}\}\; \{\backslash \; widehat\; \{x\}\}\; \_\; \{k\})\}\; ^\; \{2\},\}$

где $x\; ^\; k\; \{\backslash \; displaystyle\; \{\backslash \; widehat\; \{x\}\}\; \_\; \{k\}\}$и $x\; ^\; k\; +\; 1\; \{\backslash \; displaystyle\; \{\backslash \; widehat\; \{x\}\}\; \_\; \{k\; +\; 1\}\}$представляют собой скалярные оценки состояния, вычисленные фильтром или сглаживателем. Обновленная оценка коэффициента модели получается с помощью

$F\; ^\; =\; \sum \; k\; =\; 1\; N\; (x\; ^\; k\; +\; 1\; -\; F\; ^\; x\; ^\; k)\; \sum \; k\; =\; 1\; N\; x\; ^\; k\; 2.\; \{\backslash \; displaystyle\; \{\backslash \; widehat\; \{F\}\; \}\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{N\}\; (\{\backslash \; widehat\; \{x\}\}\; \_\; \{k\; +\; 1\}\; -\; \{\backslash \; widehat\; \{F\}\}\; \{\backslash \; widehat\; \{x\}\}\; \_\; \{k\; \})\}\; \{\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{N\}\; \{\backslash \; widehat\; \{x\}\}\; \_\; \{k\}\; ^\; \{2\}\}\}.\}$

Сходимость оценки показателей, приведенным выше, хорошо изучены.

Был предложен ряд методов для ускорения иногда медленной сходимости алгоритма EM, например, методы, использующие сопряженный градиент и модифицированные методы Ньютона (Ньютон - Рафсон). Кроме того, EM может установить с ограниченными методами оценки.

Алгоритм максимизации ожидания с расширенными функциями (PX-EM) обеспечивает ускорение за счет "использования" ковариа корректировки "для корректировки анализа шага M, извлекая выгоду из дополнительной информации, содержащейся в вмененном полном объеме данных".

Условная максимизация ожидания (ECM) заменяет каждый шаг M последовательностью шагов условной максимизации (CM), в которой каждый параметр θ i максимизируется индивидуально, при условии, что другие параметры остаются остающимся. Сама по себе идея может быть расширена до алгоритма условной максимизации ожидания (ECME).

Эта идея получила дальнейшее развитие в алгоритме обобщенной максимизации ожидания (GEM), в которой требуется только увеличение функций F как для Шаг E и шаг M, как описано в разделе Как процедура максимизации-максимизации. GEM продолжает развиваться в распределенной среде и показывает многообещающие результаты.

Также возможно рассматривать алгоритм EM как подкласс алгоритма MM (Majorize / Minimize или Minorize / Maximize, в зависимости от контекста), а потому использовать любую технику, разработанную в более общем случае.

Алгоритм α-EM

Q-функция, используемая в алгоритме EM, основанная на логарифмической вероятности. Поэтому он рассматривается как алгоритм log-EM. Использование логарифма правдоподобия может быть обобщено на использование логарифмического отношения правдоподобия. Тогда тогда правдоподобия наблюдаемых данных может быть точно выражено как равенство с использованием логарифмических отношений правдоподобия и дивергенции. Получение этой Q-функции представляет собой обобщенный шаг E. Его максимизация - это обобщенный M шаг. Эта пара называется алгоритмом α-EM, который содержит алгоритм log-EM в качестве подкласса. Таким образом, алгоритм α-EM точ Ясуо Мацуяма, является обобщенным обобщением алгоритма log-EM. Расчет градиента или матрицы Гессе не требуется. Α-EM демонстрирует более быструю сходимость, чем алгоритм log-EM, при выборе α. Алгоритм α-EM приводит к более быстрой версии алгоритма оценки скрытой марковской модели α-HMM.

ЭМ является частично небайесовским методом правдоподобия. Его окончательный результат дает распределение вероятностей по скрытым переменным (в байесовском стиле) вместе с точечной оценкой для θ (либо оценкой верхней правдоподобия, либо апостериорной модой). Может потребоваться полностью байесовская версия этого, дающая распределение вероятностей по θ и скрытым переменным. Байесовский подход к умозаключениям заключается в том, чтобы рассматривать θ как еще одну скрытую переменную. В этой парадигме исчезает различие между ступенями E и M. При использовании факторизованного Q-приближения, описанного выше (вариационный Байес ), решение может повторяться по каждой скрытой вариации (теперь включая θ) и оптимизировать их по одному. Теперь необходимо k шагов на итерацию, где k - количество скрытых чисел. Для графических моделей это легко сделать, поскольку новый Q зависит только от ее марковского бланка, для эффективного использования можно использовать локальную передачу сообщений.

В информационной геометрии шаг E и шаг M интерпретируются как проекции при двойных аффинных связях, называемых e- подключение и м-подключение ; расхождение Кульбака - Лейблера также может быть понято в этих терминах.

Гауссова смесь

Сравнение k-средних и EM на искусственных данных, визуализированных с помощью ELKI. Используя дисперсии, алгоритм EM может точно описывать нормальные распределения, в то время как k-означает разбивает данные на -ячейки Вороного. Центр кластера обозначен более светлым и большим символом. Анимация, демонстрирующая алгоритм EM, подгоняющий двухкомпонентную модель смеси Гаусса к набору данных Старый Верный. Алгоритм переходит от случайной инициализации к сходимости.

Пусть $x\; =\; (x\; 1,\; x\; 2,\dots ,\; xn)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; =\; (\backslash \; mathbf\; \{x\}\; \_\; \{1\},\; \backslash \; mathbf\; \{x\}\; \_\; \{2\},\; \backslash \; ldots,\; \backslash \; mathbf\; \{x\}\; \_\; \{n\})\}$быть образцом $n\; \{\backslash \; displaystyle\; n\}$Независимые наблюдения из смеси двух многомерных нормальных распределений размерности $d\; \{\backslash \; displaystyle\; d\}$, и пусть $z\; =\; (z\; 1,\; z\; 2,\dots ,\; zn)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{z\}\; =\; (z\_\; \{1\},\; z\_\; \{2\},\; \backslash \; ldots,\; z\_\; \{n\})\}$- скрытые переменные, определяющие компонент, из которого происходит наблюдение.

$Икс\; я\; \mid \; (Z\; i\; =\; 1)\; \sim \; N\; d\; (\mu \; 1,\; \Sigma \; 1)\; \{\backslash \; displaystyle\; X\_\; \{i\}\; \backslash \; mid\; (Z\_\; \{i\}\; =\; 1)\; \backslash \; sim\; \{\backslash \; mathcal\; \{N\}\}\; \_\; \{\; d\}\; (\{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{1\},\; \backslash \; Sigma\; \_\; \{1\})\}$и $X\; i\; \mid \; (Z\; i\; =\; 2)\; \sim \; N\; d\; (\mu \; 2,\; \Sigma \; 2),\; \{\backslash \; Displaystyle\; X\_\; \{i\}\; \backslash \; mid\; (Z\_\; \{i\}\; =\; 2)\; \backslash \; sim\; \{\backslash \; mathcal\; \{N\}\}\; \_\; \{d\}\; (\{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{2\},\; \backslash \; Sigma\; \_\; \{2\}),\}$

где

$P\; \; (Z\; i\; =\; 1)\; =\; \tau \; 1\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{P\}\; (Z\_\; \{i\}\; =\; 1)\; =\; \backslash \; тау\; \_\; \{1\}\; \backslash ,\; \}$и $P\; \; (Z\; i\; =\; 2)\; =\; \tau \; 2\; =\; 1\; -\; \tau \; 1.\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{P\}\; (Z\_\; \{i\}\; =\; 2)\; =\; \backslash \; tau\; \_\; \{2\; \}\; =\; 1-\; \backslash \; tau\; \_\; \{1\}.\}$

Цель в том, чтобы оценить неизвестные параметры, представляющие значение смешивания между гауссианы, а также средние и ковариации каждого:

$\theta \; =\; (\tau ,\; \mu \; 1,\; \mu \; 2,\; \Sigma \; 1,\; \Sigma \; 2),\; \{\backslash \; displaystyle\; \backslash \; theta\; =\; \{\backslash \; big\; (\}\; \{\backslash \; boldsymbol\; \{\backslash \; tau\}\},\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{1\},\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{2\},\; \backslash \; Sigma\; \_\; \{1\},\; \backslash \; Sigma\; \_\; \{2\}\; \{\backslash \; big)\},\}$

где функция правдоподобия неполных данных имеет вид

$L\; (\theta ;\; x)\; =\; \prod \; i\; =\; 1\; n\; \sum \; j\; =\; 1\; 2\; \tau \; jf\; (xi;\; \mu \; j,\; \Sigma \; j),\; \{\backslash \; displaystyle\; L\; (\backslash \; theta;\; \backslash \; mathbf\; \{x\})\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{2\}\; \backslash \; tau\; \_\; \{\; j\}\; \backslash \; f\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\};\; \{\backslash \; жирный\; символ\; \{\backslash \; mu\}\}\; \_\; \{j\},\; \backslash \; Sigma\; \_\; \{j\}),\}$

, функция правдоподобия для полных данных -

$L\; (\theta ;\; x,\; z)\; =\; p\; (x,\; z\; \mid \; \theta )\; Знак\; равно\; \prod \; я\; знак\; равно\; 1\; N\; \prod \; J\; знак\; равно\; 1\; 2\; [е\; (xi;\; \mu \; j,\; \Sigma \; j)\; \tau \; j]\; I\; (zi\; знак\; равно\; J),\; \{\backslash \; Displaystyle\; L\; (\backslash \; theta;\; \backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{z\})\; =\; p\; (\backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{z\}\; \backslash \; mid\; \backslash \; theta)\; =\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; prod\; \_\; \{j\; =\; 1\}\; ^\; \{2\}\; \backslash \; [f\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\};\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{j\},\; \backslash \; Sigma\; \_\; \{j\; \})\; \backslash \; tau\; \_\; \{j\}]\; ^\; \{\backslash \; mathbb\; \{I\}\; (z\_\; \{i\}\; =\; j)\},\}$

или

$L\; (\theta ;\; x,\; z)\; =\; ехр\; \; \{\sum \; i\; =\; 1\; n\; \sum \; j\; =\; 1\; 2\; I\; (zi\; =\; j)\; [журнал\; \; \tau \; j\; -\; 1\; 2\; журнал\; \; |\; \Sigma \; j\; |\; -\; 1\; 2\; (xi\; -\; \mu \; j)\; \top \; \Sigma \; j\; -\; 1\; (xi\; -\; \mu \; j)\; -\; d\; 2\; журнал\; \; (2\; \pi )]\},\; \{\backslash \; displaystyle\; L\; (\backslash \; theta;\; \backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{z))\})\; =\; \backslash \; exp\; \backslash \; left\; \backslash \; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{2\}\; \backslash \; mathbb\; \{I\}\; (z\_\; \{i\}\; =\; j)\; \{\backslash \; big\; [\}\; \backslash \; log\; \backslash \; tau\; \_\; \{j\}\; -\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; \backslash \; log\; |\; \backslash \; Sigma\; \_\; \{j\}\; |\; -\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\}\; -\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{j\})\; ^\; \{\backslash \; top\}\; \backslash \; Sigma\; \_\; \{j\}\; ^\; \{-\; 1\; \}\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\}\; -\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{j\})\; -\; \{\backslash \; tfrac\; \{d\}\; \{2\}\}\; \backslash \; log\; (2\; \backslash \; pi)\; \{\backslash \; big]\}\; \backslash \; right\; \backslash \},\}$

где $I\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{I\}\}$- это индикаторная функция, а $f\; \{\backslash \; displaystyle\; f\}$- функция плотности вероятности многомерной нормыли.

За один показатель за один показатель $I\; (zi\; =\; j)\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{I\}\; (z\_\; \{i\}\; =\; j)\}$равенство нулю, а один показатель равен единице. Таким образом, внутренняя сумма сводится к одному члену.

E step

Учитывая нашу текущую оценку θ, условное распределение Z i определяет теоремой Байеса как пропорциональная высота нормальной плотности, взвешенной по τ:

$T\; j,\; i\; (t):\; =\; P\; \; (Z\; i\; =\; j\; \mid \; X\; i\; =\; xi;\; \theta \; (t))\; =\; \tau \; j\; (t)\; f\; (xi;\; \mu \; j\; (t),\; \Sigma \; j\; (t))\; \tau \; 1\; (t)\; f\; (xi;\; \mu \; 1\; (t),\; \Sigma \; 1\; (t))\; +\; \tau \; 2\; (t)\; f\; (xi;\; \mu \; 2\; (t),\; \Sigma \; 2\; (t)).\; \{\backslash \; Displaystyle\; T\_\; \{j,\; i\}\; ^\; \{(t)\}:\; =\; \backslash \; operatorname\; \{P\}\; (Z\_\; \{i\}\; =\; j\; \backslash \; mid\; X\_\; \{i\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{i\};\; \backslash \; theta\; ^\; \{\; (t)\})\; =\; \{\backslash \; frac\; \{\backslash \; tau\; \_\; \{j\}\; ^\; \{(t)\}\; \backslash \; f\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\};\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{j\}\; ^\; \{(\; t)\},\; \backslash \; Sigma\; \_\; \{j\}\; ^\; \{(t)\})\}\; \{\backslash \; tau\; \_\; \{1\}\; ^\; \{(t)\}\; \backslash \; f\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\};\; \{\backslash \; boldsymbol\; \{\backslash \; mu\; \}\}\; \_\; \{1\}\; ^\; \{(t)\},\; \backslash \; Sigma\; \_\; \{1\}\; ^\; \{(t)\})\; +\; \backslash \; tau\; \_\; \{2\}\; ^\; \{(t)\}\; \backslash \; f\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\; \};\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{2\}\; ^\; \{(t)\},\; \backslash \; Sigma\; \_\; \{2\}\; ^\; \{(t)\})\}\}.\}$

Они называются «вероятностными членами», которые обычно считаются выходом шага E (хотя это не функция Q, описанная ниже).

Этот шаг E соответствует настройке этой функции для Q:

$Q (θ ∣ θ (t)) = EZ ∣ X, θ (t) ⁡ [log ⁡ L (θ; x, Z)] = EZ ∣ X, θ (t) ⁡ [журнал ⁡ ∏ i = 1 n L (θ; xi, Z i)] = EZ ∣ X, θ (t) ⁡ [∑ i = 1 n log ⁡ L ( θ; xi, Z i)] = ∑ i = 1 n EZ i ∣ X; θ (t) ⁡ [журнал ⁡ L (θ; xi, Z i)] = ∑ i = 1 n ∑ j = 1 2 P (Z i = j ∣ X i = xi; θ (t)) журнал ⁡ L ( θ j; xi, j) = ∑ i = 1 n ∑ j = 1 2 T j, i (t) [журнал ⁡ τ j - 1 2 log ⁡ | Σ j | - 1 2 (x i - μ j) ⊤ Σ j - 1 (x i - μ j) - d 2 log ⁡ (2 π)]. {\ displaystyle {\ begin {align} Q (\ theta \ mid \ theta ^ {(t)}) = \ operatorname {E} _ {\ mathbf {Z} \ mid \ mathbf {X}, \ mathbf {\ theta} ^ {(t)}} [\ log L (\ theta; \ mathbf {x}, \ mathbf {Z})] \\ = \ operatorname {E} _ {\ mathbf {Z} \ mid \ mathbf {X}, \ mathbf {\ theta} ^ {(t)}} [\ log \ prod _ {i = 1} ^ {n} L (\ theta; \ mathbf {x} _ {i}, Z_ {i })] \\ = \ operatorname {E} _ {\ mathbf {Z} \ mid \ mathbf {X}, \ mathbf {\ theta} ^ {(t)}} [\ sum _ {i = 1} ^ {n} \ log L (\ theta; \ mathbf {x} _ {i}, Z_ {i})] \\ = \ sum _ {i = 1} ^ {n} \ operatorname {E} _ {Z_ {i} \ mid \ mathbf {X}; \ mathbf {\ theta} ^ {(t)}} [\ log L (\ theta; \ mathbf {x} _ {i}, Z_ {i})] \\ = \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {2} P (Z_ {i} = j \ mid X_ {i} = \ mathbf {x} _ {i} ; \ theta ^ {(t)}) \ log L (\ theta _ {j}; \ mathbf {x} _ {i}, j) \\ = \ sum _ {i = 1} ^ {n} \ сумма _ {j = 1} ^ {2} T_ {j, i} ^ {(t)} {\ big [} \ log \ tau _ {j} - {\ tfrac {1} {2}} \ log | \ Sigma _ {j} | - {\ tfrac {1} {2}} (\ mathbf {x} _ {i} - {\ boldsymbol {\ mu}} _ {j}) ^ {\ top} \ Sigma _ {j} ^ {- 1} (\ mathbf {x} _ {i} - {\ boldsymbol {\ mu}} _ {j}) - {\ tfrac {d} {2}} \ log (2 \ pi) {\ big]}. \ end {align}}}$

Ожидание из $log\; \; L\; (\theta ;\; xi,\; Z\; i)\; \{\backslash \; displaystyle\; \backslash \; log\; L\; (\backslash \; theta;\; \backslash \; mathbf\; \{x\}\; \_\; \{i\},\; Z\_\; \{i\})\}$внутри сумма берется по отношению к функции плотности вероятности $п\; (Z\; я\; \mid \; Икс\; я\; знак\; равно\; xi;\; \theta \; (t))\; \{\backslash \; displaystyle\; P\; (Z\_\; \{i\}\; \backslash \; mid\; X\_\; \{i\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{i\};\; \backslash \; theta\; ^\; \{(t)\; \})\}$, которые могут быть разными для каждого $xi\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{i\}\}$обучающего набора. Все, что есть на шаге E, известно до его выполнения, за исключением $T\; j,\; i\; \{\backslash \; displaystyle\; T\_\; \{j,\; i\}\}$, которое вычисляется в соответствии с уравнением в начале E ступенчатый раздел.

Это полное условное ожидание не нужно рассчитывать за один шаг, потому что τ и μ/Σпоявляются в отдельных линейных членах и, таким образом, могут быть максимизированы независимо.

M step

Q (θ | θ), являющийся квадратичным по форме, означает, что определение максимальных значений θ относительно несложно. Кроме того, τ, (μ1,Σ1) и (μ2,Σ2) все могут быть максимизированы независимо, поскольку все они появляются в отдельных линейных членах.

Для начала рассмотрим τ, которое имеет ограничение τ 1 + τ 2 = 1:

$\tau \; (t\; +\; 1)\; =\; argmax\; \tau \; Q\; (\; \theta \; \mid \; \theta \; (t))\; =\; argmax\; \tau \; \{[\sum \; i\; =\; 1\; n\; T\; 1,\; i\; (t)]\; log\; \; \tau \; 1\; +\; [\sum \; i\; =\; 1\; n\; T\; 2,\; i\; (t)]\; log\; \; \tau \; 2\}.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \{\backslash \; boldsymbol\; \{\backslash \; tau\}\}\; ^\; \{(t\; +\; 1)\}\; =\; \{\backslash \; underset\; \{\backslash \; boldsymbol\; \{\backslash \; tau\}\}\; \{\backslash \; operatorname\; \{arg\; \backslash ,\; max\}\}\}\; \backslash \; Q\; (\backslash \; theta\; \backslash \; mid\; \backslash \; theta\; ^\; \{(t)\})\; \backslash \backslash \; =\; \{\backslash \; underset\; \{\backslash \; boldsymbol\; \{\backslash \; tau\}\}\; \{\backslash \; operatorname\; \{arg\; \backslash ,\; max\}\}\}\; \backslash \; \backslash \; left\; \backslash \; \{\backslash \; left\; [\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{1,\; i\}\; ^\; \{(t)\}\; \backslash \; right]\; \backslash \; log\; \backslash \; tau\; \_\; \{1\}\; +\; \backslash \; left\; [\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{2,\; i\}\; ^\; \{(t)\}\; \backslash \; right]\; \backslash \; log\; \backslash \; tau\; \_\; \{2\}\; \backslash \; right\; \backslash \}.\; \backslash \; End\; \{align\}\}\}$

Он имеет ту же форму, что и MLE для биномиальное распределение, поэтому

$\tau \; j\; (t\; +\; 1)\; =\; \sum \; i\; =\; 1\; n\; T\; j,\; i\; (t)\; \sum \; i\; =\; 1\; n\; (T\; 1,\; i\; (t)\; +\; T\; 2,\; i\; (\; т))\; =\; 1\; n\; \sum \; i\; =\; 1\; n\; T\; j,\; i\; (\; t).\; \{\backslash displaystyle\; \backslash tau\; \_\{j\}^\{(t+1)\}=\{\backslash frac\; \{\backslash sum\; \_\{i=1\}^\{n\}T\_\{j,i\}^\{(t)\}\}\{\backslash sum\; \_\{i=1\}^\{n\}(T\_\{1,i\}^\{(t)\}+T\_\{2,i\}^\{(t)\})\}\}=\{\backslash frac\; \{1\}\{n\}\}\backslash sum\; \_\{i=1\}^\{n\}T\_\{j,i\}^\{(t)\}.\}$

For the next estimates of (μ1,Σ1):

$(\; \mu \; 1\; (\; t\; +\; 1),\; \Sigma \; 1\; (\; t\; +\; 1))\; =\; a\; r\; g\; m\; a\; x\; \mu \; 1,\; \Sigma \; 1\; Q\; (\; \theta \; \mid \; \theta \; (\; t))\; =\; a\; r\; g\; m\; a\; x\; \mu \; 1,\; \Sigma \; 1\; \sum \; i\; =\; 1\; n\; T\; 1,\; i\; (\; t)\; \{\; -\; 1\; 2\; log\; \; |\; \Sigma \; 1\; |\; -\; 1\; 2\; (\; x\; i\; -\; \mu \; 1)\; \top \; \Sigma \; 1\; -\; 1\; (\; x\; i\; -\; \mu \; 1)\; \}.\; \{\backslash displaystyle\; \{\backslash begin\{aligned\}(\{\backslash boldsymbol\; \{\backslash mu\; \}\}\_\{1\}^\{(t+1)\},\backslash Sigma\; \_\{1\}^\{(t+1)\})=\{\backslash underset\; \{\{\backslash boldsymbol\; \{\backslash mu\; \}\}\_\{1\},\backslash Sigma\; \_\{1\}\}\{\backslash operatorname\; \{arg\backslash ,max\}\; \}\}Q(\backslash theta\; \backslash mid\; \backslash theta\; ^\{(t)\})\backslash \backslash =\{\backslash underset\; \{\{\backslash boldsymbol\; \{\backslash mu\; \}\}\_\{1\},\backslash Sigma\; \_\{1\}\}\{\backslash operatorname\; \{arg\backslash ,max\}\; \}\}\backslash sum\; \_\{i=1\}^\{n\}T\_\{1,i\}^\{(t)\}\backslash left\backslash \{-\{\backslash tfrac\; \{1\}\{2\}\}\backslash log\; |\backslash Sigma\; \_\{1\}|-\{\backslash tfrac\; \{1\}\{2\}\}(\backslash mathbf\; \{x\}\; \_\{i\}-\{\backslash boldsymbol\; \{\backslash mu\; \}\}\_\{1\})^\{\backslash top\; \}\backslash Sigma\; \_\{1\}^\{-1\}(\backslash mathbf\; \{x\}\; \_\{i\}-\{\backslash boldsymbol\; \{\backslash mu\; \}\}\_\{1\})\backslash right\backslash \}\backslash end\{aligned\}\}.\}$

This has the same form as a weighted MLE for a normal distribution, so

$\mu \; 1\; (\; t\; +\; 1)\; =\; \sum \; i\; =\; 1\; n\; T\; 1,\; i\; (\; t)\; x\; i\; \sum \; i\; =\; 1\; n\; T\; 1,\; i\; (\; t)\; \{\backslash displaystyle\; \{\backslash boldsymbol\; \{\backslash mu\; \}\}\_\{1\}^\{(t+1)\}=\{\backslash frac\; \{\backslash sum\; \_\{i=1\}^\{n\}T\_\{1,i\}^\{(t)\}\backslash m\; athbf\; \{x\}\; \_\; \{i\}\}\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{1,\; i\}\; ^\; \{(t)\}\}\}\}$и $\Sigma \; 1\; (\; t\; +\; 1)\; =\; \sum \; i\; =\; 1\; n\; T\; 1,\; i\; (t)\; (xi\; -\; \mu \; 1\; (t\; +\; 1))\; (xi\; -\; \mu \; 1\; (t\; +\; 1))\; \top \; \sum \; i\; =\; 1\; n\; T\; 1,\; i\; (\; t)\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{1\}\; ^\; \{(t\; +\; 1)\}\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{1,\; i\}\; ^\; \{(t)\}\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\}\; -\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{1\}\; ^\; \{(t\; +\; 1)\})\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\}\; -\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{1\}\; ^\; \{(t\; +\; 1)\})\; ^\; \{\backslash \; top\}\}\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{1,\; i\}\; ^\; \{(t)\}\}\}\}$

и, по симметрии

$\mu \; 2\; (t\; +\; 1)\; =\; \sum \; i\; =\; 1\; n\; T\; 2,\; i\; (t)\; xi\; \sum \; i\; =\; 1\; n\; T\; 2,\; i\; (t)\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\; \}\; \_\; \{2\}\; ^\; \{(t\; +\; 1)\}\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{2,\; i\}\; ^\; \{(t)\}\; \backslash \; mathbf\; \{x\}\; \_\; \{i\; \}\}\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{2,\; i\}\; ^\; \{(t)\}\}\}\}$и $\Sigma \; 2\; (t\; +\; 1)\; =\; \sum \; i\; =\; 1\; n\; T\; 2,\; i\; (t)\; (xi\; -\; \mu \; 2\; (t\; +\; 1))\; (xi\; -\; \mu \; 2\; (t\; +\; 1))\; \top \; \sum \; i\; =\; 1\; n\; T\; 2,\; i\; (t).\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{2\}\; ^\; \{(t\; +\; 1)\}\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{2,\; i\}\; ^\; \{(t)\}\; (\backslash \; mathbf\; \{\; x\}\; \_\; \{i\}\; -\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{2\}\; ^\; \{(t\; +\; 1)\})\; (\backslash \; mathbf\; \{x\}\; \_\; \{i\}\; -\; \{\backslash \; boldsymbol\; \{\backslash \; mu\}\}\; \_\; \{2\; \}\; ^\; \{(t\; +\; 1)\})\; ^\; \{\backslash \; top\}\}\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; T\_\; \{2,\; i\}\; ^\; \{(t)\}\}\}.\}$

Прекращение действия

Завершите итерационный процесс, если $EZ\; \mid \; \theta \; (t),\; x\; [log\; \; L\; (\theta \; (t);\; x,\; Z)]\; \le \; EZ\; \mid \; \theta \; (t\; -\; 1),\; x\; [log\; \; L\; (\theta \; (т\; -\; 1);\; Икс,\; Z)]\; +\; \epsilon \; \{\backslash \; Displaystyle\; E\_\; \{Z\; \backslash \; mid\; \backslash \; theta\; ^\; \{(t)\},\; \backslash \; mathbf\; \{x\}\}\; [\backslash \; log\; L\; (\backslash \; theta\; ^\; \{(т)\};\; \backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{Z\})]\; \backslash \; leq\; E\_\; \{Z\; \backslash \; mid\; \backslash \; theta\; ^\; \{(t-1)\},\; \backslash \; mathbf\; \{x\}\}\; [\backslash \; log\; L\; (\backslash \; theta\; ^\; \{(\; t-1)\};\; \backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{Z\})]\; +\; \backslash \; varepsilon\}$для $\epsilon \; \{\backslash \; displaystyle\; \backslash \; varepsilon\}$ниже некоторого заданного порога.

Обобщение

Алгоритм, проиллюстрированный выше, может быть обобщен для смесей более двух многомерных нормальных распределений.

Усеченная и цензурированная регрессия

Алгоритм EM был реализована в случае, когда существует базовая модель линейной регрессии, объясняющая изменение некоторой величины, но где фактически наблюдаемые значения являются цензурированными или усеченными версиями тех, которые представлены в модели. Особые случаи этой модели включают цензурированные или усеченные наблюдения из одного нормального распределения.

EM обычно сходится к локальному оптимуму, не обязательно к глобальному оптимуму, без ограничения скорости сходимости в целом. Возможно, что он может быть сколь угодно плохим в больших размерностях и может иметь экспоненциальное число локальных оптимумов. Следовательно, существует потребность в альтернативных методах гарантированного обучения, особенно в условиях большой размерности. Существуют альтернативы ЭМ с лучшими гарантиями согласованности, которые называются подходами на основе моментов или так называемыми спектральными методами. Моментные подходы к изучению параметров вероятностной модели в последнее время вызывают все больший интерес, поскольку они обладают такими гарантиями, как глобальная конвергенция при определенных условиях, в отличие от EM, который часто страдает проблемой застревания в локальных оптимумах. Алгоритмы с гарантиями обучения могут быть получены для ряда важных моделей, таких как модели смесей, ГММ и т. Д. Для этих спектральных методов не возникает ложных локальных оптимумов, и истинные параметры могут быть последовательно оценены при некоторых условиях регулярности.

• распределение смеси
• распределение соединений
• оценка плотности
• спектроскопия общего поглощения
• алгоритм ожидания – максимизации
• Алгоритм EM можно рассматривать как частный случай алгоритм мажоризация-минимизация (MM).

• Hogg, Robert; Маккин, Джозеф; Крейг, Аллен (2005). Введение в математическую статистику. Река Аппер Сэдл, штат Нью-Джерси: Pearson Prentice Hall. стр. 359–364.
• Деллаерт, Франк (2002). «Алгоритм максимизации ожидания». CiteSeerX 10.1.1.9.9735. Журнал цитирования требует | journal =() дает более простое объяснение алгоритма EM в отношении максимизации нижней границы.
• Бишоп, Кристофер М. (2006). Распознавание образов и машинное обучение. Springer. ISBN 978-0-387-31073-2.
• Gupta, M. R.; Чен, Ю. (2010). «Теория и использование алгоритма ЭМ». Основы и тенденции в обработке сигналов. 4 (3): 223–296. CiteSeerX 10.1.1.219.6830. doi : 10.1561 / 2000000034.Хорошо написанная короткая книга по ЭМ, включая подробный вывод ЭМ для GMM, HMM и Дирихле.
• Bilmes, Jeff (1998). "Мягкое руководство по алгоритму EM и его применению для оценки параметров для гауссовской смеси и скрытых марковских моделей". CiteSeerX 10.1.1.28.613. Журнал цитирования требует | journal =() включает упрощенный вывод уравнений ЭМ для гауссовских смесей и скрытых марковских моделей гауссовских смесей.
• McLachlan, Geoffrey J.; Кришнан, Триямбакам (2008). Алгоритм EM и расширения (2-е изд.). Хобокен: Вайли. ISBN 978-0-471-20170-0.

• Различные 1D, 2D и 3D демонстрации ЭМ вместе с Моделированием смеси предоставляются как часть парных действий и апплетов SOCR. Эти апплеты и действия эмпирически демонстрируют свойства алгоритма EM для оценки параметров в различных условиях.
• k-MLE: быстрый алгоритм для изучения статистических моделей смеси
• Иерархия классов в C ++ (GPL), включая гауссовские смеси
• Он-лайн учебник: Теория информации, логический вывод и алгоритмы обучения, автор Дэвида Дж. К. Маккея, включает простые примеры алгоритма EM, такие как кластеризация с использованием программного алгоритм k-средних и подчеркивает вариационный взгляд на алгоритм EM, как описано в главе 33.7 версии 7.2 (четвертое издание).
• Вариационные алгоритмы для приближенного байесовского вывода, автор MJ Beal, включает сравнения EM с вариационным Байесовский EM и производные нескольких моделей, включая вариационные байесовские HMM (главы ).
• Алгоритм максимизации ожиданий: краткое руководство, автономный вывод алгоритма EM Шона Бормана.
• Алгоритм EM, Сяоцзинь Чжу.
• Алгоритм и варианты EM: неформальное руководство Алексис Рош. Краткое и очень ясное описание EM и множество интересных вариантов.