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

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

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

История

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

Анализ сходимости алгоритма Демпстера – Лэрда – Рубина был ошибочным, и корректный анализ сходимости был опубликован CF Jeff Wu в 1983 году. Доказательство Ву установило сходимость метода EM вне экспоненциального семейства , как утверждал Демпстер – Лейрд – Рубин.

Вступление

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

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

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

Описание

Учитывая статистическую модель , которая генерирует набор наблюдаемых данных, набор ненаблюдаемых латентных данных или пропущенные значения , и вектор неизвестных параметров , а также функция правдоподобия , то оценка максимального правдоподобия (MLE) неизвестных параметров определяются путем максимизации предельная вероятность наблюдаемых данных

Однако с этой величиной часто трудно справиться, поскольку ее не наблюдают, а распределение неизвестно до достижения .

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

Шаг Ожидание (Е шаг) : Определить , как ожидаемое значение из журнала функции правдоподобия из , по отношению к текущему условного распределения из дается и текущих оценок параметров :
Шаг максимизации (шаг M) : найдите параметры, которые максимизируют это количество:

Типичные модели, к которым применяется EM, используют как скрытую переменную, указывающую на принадлежность к одной из множества групп:

  1. Наблюдаемые точки данных могут быть дискретными (принимающими значения в конечном или счетно бесконечном множестве) или непрерывными (принимающими значения в несчетно бесконечном множестве). С каждой точкой данных может быть связан вектор наблюдений.
  2. В пропущенные значения ( так называемые латентные переменные ) являются дискретными , взяты из фиксированного числа значений, и с одной скрытой переменной в наблюдаемой единицы.
  3. Параметры являются непрерывными и бывают двух видов: параметры, которые связаны со всеми точками данных, и параметры, связанные с конкретным значением скрытой переменной (т. Е. Связанные со всеми точками данных, у которых соответствующая скрытая переменная имеет это значение).

Однако ЭМ можно применять к другим типам моделей.

Мотивация следующая. Если значение параметров известно, обычно значение скрытых переменных можно найти путем максимизации логарифма правдоподобия по всем возможным значениям , либо просто путем повторения, либо с помощью такого алгоритма, как алгоритм Баума – Велча для скрытого Маркова. модели . И наоборот, если мы знаем значение скрытых переменных , мы можем довольно легко найти оценку параметров , обычно просто группируя наблюдаемые точки данных в соответствии со значением связанной скрытой переменной и усредняя значения или некоторую функцию от значения баллов в каждой группе. Это предполагает итерационный алгоритм в случае, когда оба и неизвестны:

  1. Сначала инициализируйте параметры некоторыми случайными значениями.
  2. Вычислите вероятность каждого возможного значения , данного .
  3. Затем используйте только что вычисленные значения, чтобы вычислить более точную оценку параметров .
  4. Повторите шаги 2 и 3 до схождения.

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

Характеристики

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

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

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

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

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

Доказательство правильности

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

Для любого с ненулевой вероятностью мы можем написать

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

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

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

Однако неравенство Гиббса говорит нам об этом , поэтому мы можем заключить, что

На словах, выбор улучшения приводит к улучшению как минимум на столько же.

Как процедура максимизации – максимизации

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

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

где это условное распределение ненаблюдаемых данных , приведенных наблюдаемые данные и является Кульбак-Либлер дивергенции .

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

Шаг ожидания : выберите, чтобы максимизировать :
Шаг максимизации : выберите, чтобы максимизировать :

Приложения

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

В психометрии EM - важный инструмент для оценки параметров предмета и скрытых способностей моделей теории реакции на предмет .

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

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

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

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

Алгоритмы фильтрации и сглаживания EM

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

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

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

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

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

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

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

Варианты

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

Отношение к вариационным байесовским методам

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

Геометрическая интерпретация

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

Примеры

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

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

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

а также

куда

а также

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

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

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

или

где - индикаторная функция, а - функция плотности вероятности многомерной нормали.

В последнем равенстве для каждого i один показатель равен нулю, а один показатель равен единице. Таким образом, внутренняя сумма сводится к одному члену.

E шаг

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

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

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

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

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

Шаг M

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

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

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

Для следующих оценок ( μ 1 , Σ 1 ):

Он имеет ту же форму, что и взвешенный MLE для нормального распределения, поэтому

а также

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

а также

Прекращение

Заключить итерационный процесс , если для ниже некоторого заданного порога.

Обобщение

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

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

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

Альтернативы

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

Смотрите также

использованная литература

дальнейшее чтение

  • Хогг, Роберт; Маккин, Джозеф; Крейг, Аллен (2005). Введение в математическую статистику . Река Аппер Сэдл, Нью-Джерси: Пирсон Прентис Холл. С. 359–364.
  • Делларт, Франк (2002). «Алгоритм максимизации ожидания». CiteSeerX  10.1.1.9.97 35 . Цитировать журнал требует |journal=( помощь ) дает более простое объяснение алгоритма EM в отношении максимизации нижней границы.
  • Епископ, Кристофер М. (2006). Распознавание образов и машинное обучение . Springer. ISBN 978-0-387-31073-2.
  • Гупта, MR; Чен, Ю. (2010). «Теория и использование алгоритма ЭМ». Основы и тенденции в обработке сигналов . 4 (3): 223–296. CiteSeerX  10.1.1.219.6830 . DOI : 10.1561 / 2000000034 . Хорошо написанная короткая книга по EM, включая подробный вывод EM для GMM, HMM и Дирихле.
  • Билмес, Джефф (1998). "Мягкое руководство по алгоритму ЭМ и его применению к оценке параметров для гауссовской смеси и скрытых марковских моделей". CiteSeerX  10.1.1.28.613 . Цитировать журнал требует |journal=( помощь ) включает упрощенный вывод уравнений EM для гауссовых смесей и скрытых марковских моделей гауссовской смеси.
  • Маклахлан, Джеффри Дж .; Кришнан, Триямбакам (2008). Алгоритм EM и расширения (2-е изд.). Хобокен: Вайли. ISBN 978-0-471-20170-0.

внешние ссылки