После того, как я написал в прошлой статье о доказательстве сходимости алгоритма EM, она закончилась в спешке.Потом я вышел поиграть на несколько дней, и хорошо провел время.Я вернулся и начал наверстывать предыдущую флаг:
В предыдущей статье, когда мы получили результат сходимости, нам нужно объяснение скорости сходимости.Теперь мы можем рассмотреть порядок сходимости метода.Видно, что ЕМ-алгоритм по существу определяет отображение:
Когда алгоритм ЭМ начинает сходиться, если он сходится к фиксированной точке карты, то можно считать, что
Пусть первая производная указанной выше функции является матрицей Якоби, элементы (i, j) которой равны
Из формулы можно получить следующую формулу:
Расширение Тейлора формулы дает:
По его характеристикам сходимости можно узнать, что если p=1, алгоритм EM сходится линейно, а когда p>1, если информация о наблюдаемом результате положительно определена, то сходимость все же можно считать линейной.
Скорость сходимости ЭМ сходимости можно определить как:
Скорость сходимости итеративного алгоритма равна наибольшему характеристическому корню производной матрицы.Матрица Якоби представляет собой долю недостающей информации, поэтому p является скаляром, который может эффективно представлять долю недостающей информации.Доля недостающей информации на самом деле является единичной матрицей I. Вычитание доли наблюдаемой информации из полной информации на самом деле:
Скорость сходимости алгоритма EM тесно связана с коэффициентом недостающей информации.Соотношение недостающей информации на самом деле представляет собой наклон отображения в алгоритме EM, который управляет скоростью сходимости EM.Максимальное собственное значение отношения недостающей информации называется глобальной скоростью сходимости, но чем больше p, тем медленнее скорость сходимости, поэтому матрица S = I - отношение недостающей информации определяется как матрица ускорения, s = 1-p называется глобальным ускорением, когда отношение недостающая информация велика, то EM Алгоритм по-прежнему должен испытывать относительно низкую скорость сходимости.Например, по сравнению с методом Ньютона, скорость сходимости EM будет казаться чрезвычайно медленной, особенно когда доля недостающей информации велика, но из-за стабильность алгоритма EM и удобство исполнения, но он по-прежнему имеет сильную привлекательность. Позже мы обсудим метод ускорения алгоритма EM.
4: Улучшение алгоритма EM
Вводя историю EM-алгоритма, мы знаем, что причина, по которой EM-алгоритм широко используется, заключается в том, что его можно просто выполнить, а затем оптимальное решение функции правдоподобия или локальное оптимальное решение может быть получено с помощью устойчивого восходящего алгоритма. , В этом случае EM-алгоритм имеет сильную применимость и работоспособность, но все еще есть три основные проблемы, поэтому я надеюсь представить, какие методы люди приняли для более широкого применения EM-алгоритма (это будет разделено на две части, одна часть - представить улучшенный алгоритм E-шага, а другая часть - улучшить часть M-шага)
Улучшить шаг Е
1: В предыдущем введении мы можем понять, что шаг M в основном такой же, как и полная обработка данных, и общая ситуация относительно проста, но расчет шага E требует условного ожидания «отсутствующих данных» под условии наблюдаемых данных, а затем перейти к нахождению ожидаемого логарифмического правдоподобия при полных данных (об этом упоминалось ранее), но в процессе нахождения матожидания вычисление представляет собой наиболее сложную задачу, поскольку в некоторых случаях это очень сложно получить ожидаемое явное трудно, что ограничивает использование алгоритма, поэтому существует генерация алгоритма MCEM, который решается методом приближенной реализации.Алгоритм будет подробно объяснен ниже:
1: В процессе расчета k+1-й шаг E можно заменить следующими двумя шагами:
E1: случайным образом выбрать m(k) чисел из Py|x(y|x,0(k)) для формирования независимого и идентично распределенного набора отсутствующих данных y1, y2, ...... ym(k), каждый y (i) в наборе используется для дополнения данных наблюдения, таким образом формируя полный набор данных z(j)=(x, yj);
E2: Рассчитайте по следующей формуле:
Полученный результат на самом деле является оценкой Монте-Карло для Q(0|0(k)), и пока m достаточно велико, мы можем приблизительно считать, что Q(0|0(k)) и Q(0|0 (k) ), оценки Монте и Карло в основном эквивалентны.
После выполнения двух вышеуказанных шагов E оценка Монте-Карло Q(0|0(k)) может быть максимизирована на шаге M, так что 0(k+1) может быть получено вместо 0(k) .
Есть несколько соображений по использованию алгоритма MCEM:
1: Во-первых, это определение m(k).Точность результата алгоритма MCEM в основном зависит от выбранного m(k).С учетом точности, чем больше m(k), тем лучше, но если m(k) слишком велико, это приведет к замедлению вычислений. Следовательно, выбор m(t) чрезвычайно важен.Рекомендуемая стратегия состоит в том, чтобы использовать маленькое значение m(k) в начальной итерации EM и постепенно увеличивать m(k) по мере прохождения итерации, чтобы сократить использование валового метода Монте-Карло. Моделирование E. Рассчитайте ошибку, вызванную Q.
2: Другой момент - судить о сходимости. Алгоритм MCEM и алгоритм EM имеют разные методы сходимости. Согласно приведенной выше теории, 0 (k), полученное таким образом, не будет сходиться к точке, но по мере продолжения итерации 0(k) Значение, наконец, слегка подскакивает к реальному максимальному значению, поэтому в алгоритме MCEM часто необходимо использовать график для оценки сходимости. После многих итераций, если оценочная последовательность слегка колеблется около 0 = 0 (*), считается, что оценочная последовательность сошлась.
Улучшить М шагов
1: Алгоритм ЕСМ
После улучшения Е-шага алгоритма ЕМ будет задумано продолжить совершенствование расчета М-шага. Одним из преимуществ алгоритма EM является то, что максимизация Q(0|0(k)) обычно проще, чем оценка максимального правдоподобия в условиях неполных данных, потому что Q(010(k)) такое же, как вычисление правдоподобия. при полных данных в основном то же самое. Однако в некоторых случаях М-шаг не имеет простой формы расчета, и вычисление Q(0|0(k)) не так просто реализовать, поэтому были предложены различные стратегии улучшения для облегчения реализации М-этапа. изменять
Хороший способ сделать M шагов — избежать повторяющихся шагов M. Вы можете увеличить функцию Q в каждом расчете M шагов, то есть Q(0(k+1|0(k))>Q(0(k)| 0(k)) вместо максимизации. На этом принципе основан алгоритм GEM. Алгоритм GEM на каждом шаге итерации увеличивает значение функции правдоподобия, но ему не хватает деталей процесса увеличения функции, поэтому он не может быть гарантированной сходимости Алгоритм ECM, предложенный Менгом и Рубином в 1993 году, является подклассом алгоритма GEM, но имеет более широкое применение.
Чтобы избежать повторяющихся M шагов, алгоритм ECM использует ряд относительно простых расчетных условий, чтобы максимизировать
Шаг оптимизации (CM) заменяет шаг M, который разработан как простая задача оптимизации каждый раз, когда он ищет максимизацию функции Q для p, Мы называем этот набор более простых шагов условной максимизации набором Следовательно, считается, что k-я итерация алгоритма ECM включает k-й E-шаг и k-й цикл CM.
Таким образом, шаги шага М также делятся на два:
1: Обозначим через S количество шагов КМ в каждом цикле КМ Для s=1, 2, ..., S в k-м цикле КМ k-го итерационного процесса требуется s-й шаг КМ. находиться в состоянии ограничения.
Ниже приводится максимизация функции Q(0|0(k)), где 0(k+(s-1)/s) – оценочное значение, полученное на шаге s-1 CM k-го цикла CM.
2: Когда S циклов шага CM завершены, пусть 0(k+l)=O(k+S/S) и выполняется седьмая+1-я итерация шага E алгоритма ECM.
Поскольку каждый шаг CM увеличивает функцию Q, Q(0(k+s/S)|0(k))>Q(0(k)|0(k)), очевидно, что алгоритм ECM является разновидностью GEM. Для того чтобы обеспечить сходимость алгоритма ECM, необходимо убедиться, что
Каждый цикл шага CM заключается в поиске точки максимума функции Q(0|0(k)) в любом направлении, так что алгоритм ECM, когда ему разрешено максимизировать исходное пространство p, может гарантировать, что в EM сходится к устойчивой точке в основном при тех же условиях.Как и алгоритм EM, алгоритм ECM не может гарантировать, что он сойдётся к точке глобального максимума или локальному оптимуму. Рассмотрим скорость сходимости алгоритма ECM ниже.Подобно алгоритму EM, глобальная скорость сходимости алгоритма ECM выражается следующим образом:
Скорость сходимости итерационного алгоритмаPравен матрице (0*) является наибольшим собственным значением ), так какPЧем больше значение, тем больше доля недостающей информации, тем медленнее скорость сходимости, поэтому скорость сходимости алгоритма определяется как1одинP. Из расчета видно, чтоECMСкорость итерации алгоритма обычно такая же, какEMАлгоритм тот же или похожий, но по количеству итерацийECMалгоритм, чемEMАлгоритмы быстрые.
в соответствии сECMТеория алгоритмов, видно, что конструкция эффективнаECMАлгоритмы сложны,
Необходимо выбрать ограничения. привычно, естественно0разделен наSподвектор0=(01,02,03,,,,,0s). затем в8КусокCMшаг, фиксированный0оставшиеся пары элементов, чтобы найти функциюQмаксимизации. Это эквивалентно использованиюg(0)=(01,02,,,,,,0s) как ограничение. Эта стратегия называется итеративным условным режимом.
в соответствии сECMХарактеристики алгоритма можно увидетьECMПреимущества алгоритмов:
1:если ты встретишьMшаг не имеет упрощенной формы,CMЦиклы часто упрощают вычисления2:ECMАлгоритм заключается в максимизации исходного пространства параметров защиты, которое является более устойчивым и может устойчиво сходиться.
Алгоритм ЭКМЕ:
Алгоритм ECME был предложен Линем и Рубином в 1994 году для замены некоторых шагов CM алгоритма ECM.
Это улучшенная форма алгоритма ECM.Характеристика алгоритма ECME заключается в том, что на шаге CM
На основе максимизации, т. е. оценка максимального правдоподобия выполняется для ожидаемого Q(0|0(k)) ограниченной функции логарифмического правдоподобия полных данных, а на некоторых шагах — соответствующей ограниченной ограниченной фактической функции правдоподобия L (0|Z).
M-шаговая форма k+1-й итерации алгоритма ECME:
Шаг E и шаг CM непрерывно повторяются, после итерации получается 0(k+1) и продолжается вычисление шага E на шаге k+2 до сходимости.
Отсюда видно, что данный алгоритм обладает свойствами устойчивой монотонной сходимости как алгоритмов EM, так и алгоритмов ECM, а также относительно быстрый метод сходимости. То есть реализована базовая простота алгоритма EM.Кроме того, видно, что ECME может иметь более высокую скорость сходимости, чем алгоритмы EM и ECM, а количество итераций и время, необходимое для итерации до сходимости, меньше. . Это улучшение объясняется двумя основными причинами: во-первых, на некоторых этапах максимизации в алгоритме ECME фактическая функция правдоподобия, находящаяся в полных данных, условно максимизируется, а не аппроксимируется, как в предыдущих алгоритмах EM и ECM; во-вторых, ECME Алгоритм может выполнять быстро сходящиеся численные вычисления для тех максимизаций с ограничениями, где он чрезвычайно эффективен.
Подобно алгоритмам EM и ECM, для алгоритма ECME производная от 0(k)-0(k+1) отображается на 0*, то есть наклон определяет скорость сходимости ECME, которая определяется наблюдаемыми данными , отсутствующие данные и полная информация о данных.Расчетом подтверждено, что скорость сходимости алгоритма ECME выше, чем у алгоритмов EM и ECM, а метод расчета сложнее; Ожидаемое Q(0|0(k)) , которая не является логарифмической функцией правдоподобия полных данных, очевидно, более точна, поскольку функция Q является приближенной. В общем, с точки зрения количества итераций и фактического требуемого времени алгоритм ECME превосходит алгоритмы EM и ECM, особенно когда задача более сложная.
AECM:
Другой вариант алгоритма EM, алгоритм условной максимизации ожиданий (AECM), основан на алгоритме ECME.
На основе метода, соответствующего алгоритмам ECM и ECME, алгоритм AECM будет максимизировать некоторые функции, отличные от L и Q, на шаге CM. Функция максимизации 3 является частным случаем без пропущенных данных.Итерация AECM также состоит из серии циклов.Каждый цикл состоит из специально определенного E-шага с полными данными и отсутствующими данными и соответствующего специального определения.A полная итерация AECM определяется таким набором шагов CM, который представляет собой максимизацию с заполнением пространства в смысле параметризации ECM.Как и ECME, он может обеспечить высокую вычислительную эффективность.
Алгоритм PX-EM:
Алгоритм расширения параметров EM (PX.EM), предложенный в 1998 г., значительно ускорил скорость сходимости алгоритма EM.Основная идея алгоритма PX-EM состоит в корректировке ковариации в шагах M для получения дополнительной информации о полные данные. Можно видеть, что в алгоритме EM p(z|0) по полным данным и p(xl0) по данным наблюдения имеют разные параметры, поэтому алгоритм PX-EM расширяет набор параметров, вводя дополнительные порты параметров, если параметр в исходной модели равен 0, новое расширенное пространство параметров = (0 *, a), тогда 0 * - это та же размерность, что и в алгоритме EM, и когда a = a (0), предел равен 0 * =0, получается исходная модель, т. е. имеется p(z|0)=p(zl пространство параметров).
При его использовании должны быть соблюдены два условия:
1. Существует некоторое известное преобразование R такое, что 0=R(0*,a)
2. При а=а(0) выбрать расширенную модель так, чтобы в наблюдаемых данных X не было информации о а, т. е.
3.В расширенной модели параметр≯для полных данныхZ=(X,y) можно идентифицироватьPX-EMалгоритм какEMРасширенная модель алгоритма, его перваяk+1Подитеративная форма:
1:PX-E:
Рассчитайте следующую формулу:
2: шаг PX-M:
Рассчитайте по следующей формуле:
, а затем шаги PX-E, PX-M непрерывно повторяются до сходимости.
PX-EMКаждый шаг алгоритма увеличиваетp(x|0*,a), с тех пор какa=a0, он равенp(xlO),следовательноPX-EMКаждый шаг алгоритма увеличивает соответствующую функцию правдоподобияp(xlO),иPX-EMСвойства сходимости алгоритма связаны сEMАлгоритм параллельный,PX-EMВ конечном итоге алгоритм сойдется к стабильной точке и точке локального максимума. Следующие вещи, которые следует учитывать,PX-EMСкорость сходимости алгоритма
Что быстрее, чем алгоритм EM.
В соответствующем преобразовании0=R(0*,aПод≯=(0*,a)прибыть(0,a) параметризация относительно близка. упоминалось ранее обо всемa,a'существуетp(x|0*,a)=p(x|0*,a'), Видно, что по словамp(z|0,a) может получить информационную матрицу по наблюдаемым данным и полные данные:
Подобно заключению о сходимости алгоритма EM, коэффициент недостающей информации составляет:
В том смысле, что разница между этими двумя матрицами является положительно полуопределенной, это меньше, чем доля недостающей информации в предыдущем алгоритме EM:
Как упоминалось ранее, чем больше доля недостающей информации, тем медленнее скорость сходимости, поэтому скорость сходимости алгоритма PX-EM выше, чем у EM. Фактически, это связано с расширением пространства параметров и эффектом увеличение параметра a означает увеличение полного объема информации. Внесите изменения, соответствующая недостающая информация также будет уменьшена, что сыграет роль в уменьшении доли недостающей информации, тем самым ускорив алгоритм ЭМ:
В этом случае видны преимущества PX-EM:
1: Пока базовая модификация алгоритма EM невелика, конструкция относительно проста.
2: В полной мере используйте эффективную информацию для расширения полных данных, оценки параметров, поддержания монотонной сходимости алгоритма EM, а скорость сходимости высока.
Как важный итерационный метод для оценки параметров неполных данных, алгоритм EM широко используется из-за его простой реализации, простоты в эксплуатации, стабильных результатов оценки и хорошей сходимости. Однако в алгоритме все еще есть неудовлетворительные места, такие как медленная скорость сходимости, сложность вычисления интегрального математического ожидания Е-шага, отсутствие явной формы вычисления М-шага и т. д. Перед лицом трех основных проблем алгоритма Алгоритм ЭМ, основное содержание этой главы То есть в процессе разработки алгоритма ЭМ, чтобы преодолеть вышеуказанные проблемы, люди выдвинули принципы, алгоритмы, свойства и примеры приложений некоторых популярных алгоритмов. Например, для улучшения алгоритма ЕМ Монте-Карло, предложенного на Е-шаге, усовершенствовать алгоритмы ЕСМ, ECME, AECM М-этапа, метод увеличения скорости сходимости и алгоритм РХ-ЭМ.
В следующей статье мы обсудим некоторые практические применения алгоритма EM.
использованная литература:
[1] Марк Б.Л., Эфраим Ю. EM-алгоритм для двумерных вычислений с непрерывным временем.
Цепи Маркова[J], Вычислительная статистика и анализ данных, 2013, 57(1): 504-517.
【2】 Ryd6n T.Алгоритм EM для оценки в марковско-модулированном Пуассоне
процессы[J], Вычислительная статистика и анализ данных, 1996, 21(4): 431-447.
[3] Лиан Джунянь, Применение алгоритма ЭМ и его усовершенствование для оценки параметров смешанных моделей, [D], Университет Чанъань, 2006.
[4] Ян Цзидун Теория ЭМ-алгоритмов и ее применение [J1.Journal of Anqing Normal University: Natural Science Edition, 2009, 15(4):30-35.
[5] Ван Айпин, Чжан Гунъин, Лю Фан Исследование и применение ЭМ-алгоритма [J1.Компьютерные технологии и разработка, 2009, 19(9):108-110.
[6] Ру Чжэнлян, Гао Анли. Применение алгоритма EM при оценке параметров неполных данных [J], Журнал Нанкинского технологического института: выпуск естественных наук, 2009 г., 6(4):9—12.
[7] Принцип и объяснение алгоритма EM, документ Шаньдунского университета.