Подробное объяснение алгоритма ЭМ десяти классических алгоритмов машинного обучения

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания

СегодняБумага 14 в темах машинного обученияВ этой статье поговорим о знаменитом алгоритме EM.

Полное английское название алгоритма EM:Expectation-maximizationалгоритм, то есть алгоритм максимального ожидания или алгоритм максимизации ожидания. Алгоритм EM называетсяОдин из десяти лучших алгоритмов машинного обучения, слушайте это имя и знайте, что оно необыкновенно. Я прочитал много блогов и материалов, но очень мало материалов, которые могут объяснить подноготную этого алгоритма и детали его вывода, поэтому я сегодня изучу различных директоров и постараюсь объяснить это максимально понятно.

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

оценка максимального правдоподобия

Предположим, что в данный момент у нас есть монета, и мы хотим знать, какова вероятность того, что монета упадет решкой при броске, поэтому мы проведем эксперимент, подбросив монету 10 раз. Найди этоКоличество раз, когда выпадет орел, равно 5, и количество раз, когда выпадет решка, также 5 раз.. Таким образом, мы думаем, что монета имеет 50% шанс выпадения орла каждый раз.

На первый взгляд, этот вывод вполне нормальный и заслуживает его. Но после тщательного анализа мы обнаружим, что это проблематично.Проблема в том, что полученные нами экспериментальные результаты и экспериментальные параметры не сильно связаны. То есть, если с монетой манипулировали, вероятность того, что она выпадет орлом, составляет 60%, и если мы подбросим ее 10 раз, также можно получить вероятность 5 орлов и 5 решек. Точно так же, если вероятность выпадения орла составляет 70%, у нас также есть определенная вероятность получить 5 орлов и 5 решек. Теперь, когда мы получили такой результат, как мы можем объяснить, что он должен быть вызван 50% вероятностью роста?

Так что мы должны делать, продолжать экспериментировать?

Очевидно, что сколько бы мы ни проводили экспериментов, мы не можем принципиально решить эту проблему, поскольку параметры влияют на вероятность результата, мы должны вернуться к этому ракурсу и начать с вероятности. Мы знаем, что подбрасывание монеты является событием с биномиальным распределением, и мы предполагаем, что вероятность того, что монета выпадет орлом, равна p, тогда вероятность выпадения решки равна 1-p. Итак, мы можем ввести формулу биномиального распределения и выяснить, какова вероятность того, что после 10 подбрасываний 5 будут положительными результатами при текущем параметре p.

Таким образом, мы можем получить такую кривую:

этоПри вероятности выпадения орла 0,5 вероятность выпадения 5 орлов за 10 бросков наибольшая.. Мы рассматриваем вероятность выпадения орла как параметр эксперимента, а вероятность — как вероятность. Тогда оценка максимального правдоподобия фактически относится к параметру, который делает текущий экспериментальный результат наиболее вероятным.

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

Принцип понятен, и решение тоже идет гладко.

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

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

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

Введите скрытые переменные

Вышеприведенное — это просто базовое использование оценки максимального правдоподобия.Если мы немного изменим задачу и введем еще одну переменную, что произойдет?

Давайте рассмотрим классический пример, который также является подбрасыванием монеты, но если мы немного изменим условия задачи, вся задача будет совсем другой.

Этот пример взят из классической статьи с описанием алгоритма EM: Do, C.B., & Batzoglou, S. (2008).What is the expectation maximization algorithm?. Nature biotechnology, 26(8), 897». В этом примере у нас есть две монеты, A и B, где вероятность того, что монета A выпадет орлом, равна 0,5, а вероятность того, что монета B выпадет орлом, равна 0,4, и мы случайно Выберите одну из двух монет для эксперимента.

Всего мы проводили по 5 раз в каждом эксперименте и записывали количество положительных и отрицательных сторон. После 5 раундов экспериментов мы получили следующие результаты:

Поскольку мы знали, какая монета выбирается для эксперимента в каждом раунде, весь процесс был очень гладким. Если мы удалим информацию о монете,Предположим, мы не знаем, какая монета была выбрана в каждом раунде.Поэкспериментируйте, как мы должны задать вероятность A и B?

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

Алгоритм EM был создан для решения этой проблемы.

ЭМ-алгоритм

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

Да, вы не ошиблись, суть алгоритма ЭМ очень проста и груба: поскольку мы не можем решить скрытую переменную, мы ее не запрашиваем, мы напрямуюПредположим, что начальное значение подставляется в расчет, а затем повторить результат.

Например, предположим, что P1 - это вероятность того, что монета a возникает головы, а P2 - это вероятность того, что монета B возникает головы. Первоначально мы надеялись решить P1 и P2, что приводит к тому, что результат появляется через оценку максимальной вероятности. Теперь мы напрямую предполагаем и итерацию:

Мы принимаем p1=0,7, p2=0,3, это значение принято нами произвольно, вы можете произвольно принять другие значения. Мы подставляем p1 и p2 в приведенные выше результаты для расчета.

Например, в первом раунде выпало 3 орла и 2 решки.Если это монета А, то вероятность такого результата легко вычислить по биномиальному распределению: 0.7^3 * 0.3^2 = 0.03087 , таким же образом мы можем рассчитать вероятность монеты B как 0,01323. Таким же образом вычисляем все вероятности:

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

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

Первый раунд - монетаA

Второй раунд - монетаB

Третий раунд - монетаB

Четвертый раунд - монетаA

Пятый раунд - монетаB

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

Например, в первом и четвертом раундах появляется монета А. Всего в этих двух раундах было проведено 10 опытов, из них 6 орлов и 4 решки, тогда мы можем скорректировать значение p1 до 0,6. Во 2-м, 3-м и 5-м раундах выпадала монета B. В течение этих трех раундов было проведено 15 экспериментов, всего выпало 5 орлов и 10 решек, поэтому вероятность выпадения орла составляет 1/3. Можно обнаружить, что после одной итерации нашаРезультат ближе к истинному значению.

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

Примеры улучшений

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

Есть ли способ лучше?

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

Мы используем эту вероятность, чтобы ввести экспериментальные результаты для расчета ожидания, и мы можем получить таблицу ожиданий p1:

p_1 = \frac{2.1+0.6+0.0729+2.1+0.6}{2.7+2.7+0.292+2.7+2.7}=0.490

Точно так же мы можем вычислить ожидаемую таблицу нового p2:

Подставив, мы можем получитьНовый p2 равен 0,377..

После изменения результата оценки для использования вероятности и подстановки его в итерацию наша оценкаРезультат намного точнее, а это значит, что мы сходимся быстрее. Мы повторяем описанный выше процесс до сходимости, При сходимости мы можем получить значения p1 и p2, когда оценка максимального правдоподобия является максимальной. Это также суть всего алгоритма EM.

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

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

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

Этот метод введен здесь, я думаю, что все должны его понять, но мы не доказали его математически, почему эта операция работает? Почему этот метод обязательно сходится, а значение, которое мы сошлись, является оптимальным решением? Так что нам все еще нужно доказать это математически.

Математическое доказательство

Предположим, у нас есть выборка X, состоящая из m выборок, которую можно записать как $X=\{x_1, x_2, \cdots x_m\}$ , для этих m выборок все они имеют скрытую переменную z, которая неизвестна. и есть еще один параметр $\theta$ , то есть параметры, которые мы хотим решить с помощью оценки максимального правдоподобия. Поскольку он содержит скрытую переменную z, мы не можем напрямую вычислить вывод и экстремальное значение функции вероятности.

Сначала напишем функцию вероятности со скрытыми переменными:

Мы хотим найти параметры, оптимальные для глобальной $\theta$ , так что мы надеемся найти такие $\prod_{i=1}^mP_i$ Максимум, находим лог этой формулы, можем получить:

\sum_{i=1}^m\log P_i= \sum_{i=1}^m \log \sum_{z_i}P(x_i, z_i; \theta)

Мы предполагаем, что распределение вероятностей скрытой переменной z равно Q_i , поэтому приведенную выше формулу можно преобразовать в:

\sum_{i=1}^m\log P_i= \sum_{i=1}^m \log \sum_{z_i}Q_i(z_i)\frac{P(x_i, z_i; \theta)}{Q_i(z_i)}

Здесь вроде бы застрял, но это не так.В предыдущей статье мы писали, что для выпуклых функций естьНеравенство Дженсена: E [f (x)]> = f (e [x]), то есть.Ожидаемое значение функции больше или равно ожидаемому значению значения функции. иЛогарифмическая функция является выпуклой функцией в широком смысле и вогнутой функцией в строгом смысле., можно использовать неравенство Дженсена, но нужно изменить направление знака неравенства.

В приведенной выше формуле Q_i(z_i) - распределение вероятностей скрытой переменной, поэтому $\sum_{z_i}Q_i(z_i)[\frac{P(x_i, z_i; \theta)}{Q_i(z_i)}]$ да $\frac{P(x_i, z_i; \theta)}{Q_i(z_i)}$ , поэтому мы можем заменить неравенство Дженсена, чтобы получить:

\sum_{i=1}^m\log P_i \geq \sum_{i=1}^m \sum_{z_i}Q_i(z_i)\log \frac{P(x_i, z_i; \theta)}{Q_i(z_i)}

Формулу в правой части знака неравенства выше решить намного проще.Когда мы фиксируем переменную z, мы можем легко решить параметры, когда вероятность наибольшая. $\theta$ . Точно так же, когда у нас есть $\theta$ После значения z снова можно оптимизировать. Этот метод фиксирования одной из двух переменных и оптимизации другой, в свою очередь, называетсяКоординатный подъем, что также является очень распространенным методом решения в машинном обучении.

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

В дополнение к этому, мы также можем объяснить это математически.

Поскольку приведенная выше формула является неравенством, у нас нет возможности напрямую решить максимальное значение слева, поэтому мы передаемМетод непрерывной оптимизации выражения в правой части для аппроксимации максимального значения в левой части. Пусть последовательность выражений слева будет $L(\theta)$ , выражение в правой части знака неравенства имеет вид $J(z, \theta)$ Тогда мы смотрим на график, который является Богом, я получил из блога Бога:

Верхний красный цвет на картинке выше $L(\theta)$ , изображение ниже — Дж. Каждый раз, когда мы исправляем z, мы можем найти лучшее $\theta$ , так что $J(z, \theta)$ Приближаясь к высшей точке, она в итоге достигает своего максимального значения.

Интуитивно это нормально, но нам все еще нужно доказать это математически.

Согласно неравенству Йенсена, только еслиНезависимая переменная x является константойможно взять только тогда, когда наша независимая переменная равна $\frac{P(x_i, z_i; \theta)}{Q_i(z_i)}$ , приравняем его к константе c:

\frac{P(x_i, z_i, \theta)}{Q_i(z_i)} = c

так как $\sum_{z_i}Q_i(z_i)=1$ , чтобы мы могли знать $\sum_{z_i}P(x_i,z_i, \theta)=c$ , подставляя в приведенную выше формулу, можем получить:

\begin{aligned} Q_i(z_i)\cdot c &= P(x_i, z_i, \theta) \\ Q_i(z_i) &=\frac{P(x_i. z_i; \theta)}{c}\\ Q_i(z_i) &= \frac{P(x_i. z_i; \theta)}{\sum_{z_i}P(x_i, z_i; \theta)}\\ Q_i(z_i) &= \frac{P(x_i. z_i; \theta)}{P(x_i; \theta)}\\ Q_i(z_i) &= P(z_i|x_i; \theta)\\ \end{aligned}

После этой цепочки деформаций получаем Q_i(z_i) Формула расчета на самом делеАпостериорная вероятность. Этот шаг также является только что введенным шагом E. После этого, после подтвержденияПосле этого найдем метод вывода, чтобы найти экстремум, чтобы найти максимальное значение функции $\theta$ , который сейчас является шагом М.

Следовательно, весь процесс алгоритма ЭМ состоит в том, чтобы повторять этот процесс до сходимости.

Итак, как мы можем гарантировать, что алгоритм может сходиться до определенной степени? На самом деле это несложно.Поскольку мы следуем z, полученному по условию равенства неравенства Йенсена при выполнении шага E, мы можем гарантировать, что знак равенства может быть получен, то есть:

L(\theta_t) = \sum_{i=1}^m \sum_{z_i}Q_i(z_i)\log \frac{P(x_i, z_i; \theta_t)}{Q_i(z_i)}

когда мы исправим Q_i(z_i) Вывод для максимизации параметров $\theta_{t+1}$ После этого мы получаем правую форму, которая должна быть лучше, чем $L(\theta)$ , но мы не можем быть уверены в новом $\theta_{t+1}$ , наш предыдущий Q_i(t_i) Распределение также может удовлетворять условию равенства неравенства Дженсена, поэтому:

\begin{aligned} L(\theta_{t+1}) &\geq \sum_{i=1}^m \sum_{z_i}Q_i(z_i)\log \frac{P(x_i, z_i; \theta_{t+1})}{Q_i(z_i)}\\ &\geq \sum_{i=1}^m \sum_{z_i}Q_i(z_i)\log \frac{P(x_i, z_i; \theta_{t})}{Q_i(z_i)} \\ &=L(\theta) \end{aligned}

Таким образом, мы доказываем, что значение функции правдоподобия увеличивается. Когда оно, наконец, сходится, это значение оценки максимального правдоподобия. Параметры в это время $\theta$ параметры, которые нам нужны из метода оценки максимального правдоподобия.

Суммировать

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

Наконец, я не знаю, есть ли у вас ощущение, когда вы его смотрите, то есть идея алгоритма EM вроде бы где-то уже была замечена? Чувствуете себя знакомым?

Это правильное чувство.Если вы вспомните K-средние, о которых мы говорили ранее, вы обнаружите, что мы также догадывались в начале, потому что мы не знали центр кластера. Затем он аппроксимируется по крупицам путем итерации. Если немного подумать, то можно найтиПроцесс расчета MDHEANS может быть подтвержден процессом алгоритма EMиз. Благодаря моделированию, мы можем преобразовать проблему KMAIANS в модель алгоритма EM. Заинтересованные студенты могут изучить эту проблему, и, конечно, с нетерпением ждем наших последующих статей.

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