Демистификация ужасов ЭМ-алгоритма путем создания его с нуля
Алгоритм максимизации ожидания (EM) — это метод статистического машинного обучения для нахождения оценок максимального правдоподобия моделей с неизвестными скрытыми переменными. Я уверен, что это предложение не будет иметь никакого смысла для некоторых из вас. Не беспокоиться! Эта статья направлена на то, чтобы демистифицировать уравнения ужасов и загадочные словари алгоритма EM. К сожалению, без должной математики нельзя по-настоящему понять суть алгоритма ЭМ. Вот что я собираюсь сделать. Каждый раздел этой статьи будет включать раздел Полная математика и раздел Все, что вам нужно знать. Раздел Полная математика включает полные выводы алгоритма, а раздел Все, что вам нужно знать, содержит основные сведения без выводов. Чтобы следовать разделу Полная математика, я предполагаю, что вы знакомы с теорией вероятности, статистической теорией и фундаментальным исчислением. В разделе Все, что вам нужно знать все еще будут математические расчеты, но они не такие сложные.
Чтобы понять алгоритм, мы должны сначала понять данные, с которыми имеем дело. Алгоритм EM работает с данными из нескольких кластеров, т. е. со смешанной моделью. У каждого кластера есть вероятность того, что данные принадлежат этому кластеру, но мы не знаем эти вероятности. Каждый кластер данных имеет свое распределение, о котором мы знаем, но параметры распределения нам неизвестны. См. пример ниже для модели смеси Пуассона.
В этом примере кластеров 2. Zᵢобозначает кластер данных Xᵢ. π обозначает вероятность быть из определенного кластера.
Следовательно, сумма всех значений π должна равняться единице. В этом уроке я буду использовать эти значения параметров.
Если точка данных из первого кластера, она исходит из распределения Пуассона с параметром λ = 2, а если точка данных из второго кластера, она исходит из распределения Пуассона с λ = 6. Помните, что мы не знаем этих значений параметров и пытаемся их оценить.
Цель алгоритма EM — найти оценки параметров этой смешанной модели. В приведенном выше случае алгоритм EM будет оценивать π₁, π₂, λ₁ и λ₂. π — это вероятность кластера, а λ — параметр распределения Пуассона. Следовательно, если распределение кластеров является гауссовым (нормальным), а не пуассоновским, алгоритм EM будет оценивать μ и σ² вместо λ. Позвольте мне оставить эту функцию PDF Пуассона здесь. Пожалуйста, отрегулируйте его, чтобы он соответствовал желаемому дистрибутиву.
На практике может быть столько кластеров, сколько пожелают пользователи, и распределение каждого кластера может быть любым, каким мы захотим. Еще раз напомню, что мы не знаем ни одного значения параметра, а также не знаем, из какого кластера каждая точка данных. Это неизвестное распределение кластеров является причиной того, что кластеры называются скрытыми переменными. Алгоритм EM очень полезен для работы с такими ненаблюдаемыми переменными.
Поскольку алгоритм EM является итеративным, я буду использовать θ для обозначения новых оценок параметров и θ⁰ для обозначения оценок предыдущей итерации. Некоторые другие переменные; N обозначает общее количество выборок, а K представляет общее количество кластеров.
Вам следует перейти к разделу 4. Алгоритм, чтобы сразу перейти к демистифицирующей части илиесли вы ищете нематематическую сводку алгоритма.
1. Ожидание полного логарифмического правдоподобия
Полное логарифмическое правдоподобие эквивалентно логарифмическому правдоподобию данных. Мы использовали термин «полный», потому что в следующих разделах будет другая статистика, называемая «неполная логарифмическая вероятность». Я буду использовать термины «полное логарифмическое правдоподобие» и «логарифмическое правдоподобие» взаимозаменяемо только для этого раздела.
Полная математика
Перейдите к разделу Все, что вам нужно знать, если вы не заинтересованы в выводах.
Чтобы найти параметры распределения некоторых данных, мы обычно берем параметры, которые максимизируют вероятность этих данных. Алгоритм EM применяет здесь ту же концепцию, пытаясь максимизировать полную вероятность.
Мы можем расширить приведенную выше формулу, как показано ниже,
Функция экспоненты — это индикаторная функция, возвращающая единицу, если условие внутри истинно, и 0 в противном случае. Чтобы упростить последующие расчеты, мы предпочитаем, чтобы эта индикаторная функция не находилась в показателе степени. Возьмем журнал вероятности.
Это более простая форма для максимизации. К сожалению, мы не можем рассчитать эту логарифмическую вероятность, потому что не знаем, из каких кластеров поступают те или иные данные. Таким образом, мы не знаем вывод функции индикатора и параметры распределения, которые нужно использовать. Решение этой проблемы состоит в том, чтобы использовать ожидание логарифмического правдоподобия вместо фактического логарифмического правдоподобия. Давайте определим математическое ожидание логарифмической вероятности, как показано ниже:
Ожидание логарифмического правдоподобия заменяет индикаторную функцию апостериорными вероятностями. Мы вычислим значения апостериорных вероятностей в последующих разделах.
Для нашего примера Пуассона выше ожидание становится следующим:
Все, что тебе нужно знать
Все, что вам нужно знать о полном логарифмическом правдоподобии, это то, что мы хотим найти параметры, которые максимизируют его. К сожалению, полное логарифмическое правдоподобие трудно рассчитать из-за неизвестных кластеров. Чтобы обойти это, мы вычисляем ожидаемое логарифмическое правдоподобие и максимизируем его вместо фактического логарифмического правдоподобия.
Ожидание полного логарифмического правдоподобия обозначается как Q(θ, θ⁰). Формула для Q(θ, θ⁰) приведена ниже.
Для нашего примера Пуассона это становится
На данный момент это все, что вам нужно знать об ожидании полного логарифмического правдоподобия.
2. Апостериорная вероятность
Полная математика
Перейдите к разделу Все, что вам нужно знать, если вы не заинтересованы в выводах.
Апостериорная вероятность — это вероятность получения конкретной точки данных из кластера с учетом значения этой точки данных и параметров в текущей итерации. Это не следует путать с вероятностью, обозначенной π. Определим их,
Было бы полезно, если бы вы поняли, что я использовал определение условной вероятности, чтобы получить это. Мы можем расширить это выражение до следующего,
Я не буду вдаваться в вероятностные свойства, которые я применил здесь, но это точное определение условной вероятности, приведенное выше. Если вы заметили, числитель — это вероятность данных и кластера. Мы видели эти вероятности в предыдущем разделе. Знаменатель — это просто сумма вероятностей всех кластеров.
Для нашего примера Пуассона апостериорная вероятность принимает вид
Обратите внимание, что параметры, используемые для расчета апостериорных вероятностей, являются параметрами предыдущей итерации. Следовательно, апостериорная вероятность будет считаться константой в ожидании полного логарифмического правдоподобия.
Все, что тебе нужно знать
Все, что вам нужно знать об апостериорной вероятности, это то, что это вероятность получения кластера с учетом текущих данных и параметров. Нам нужна эта вероятность, чтобы вычислить ожидание полного логарифмического правдоподобия. К счастью, найти его не так уж сложно, поэтому я просто приведу формулу.
Эта формула проста, потому что мы уже все знаем. Числитель — это вероятность данных и кластера, а знаменатель — сумма вероятностей тех же данных и всех возможных кластеров.
В нашем предыдущем примере у нас есть только два возможных кластера. Следовательно, апостериорная вероятность для первого кластера в этом примере — это просто вероятность первого кластера, деленная на сумму вероятности первого кластера и вероятности второго кластера.
Я надеюсь, что вы сможете экстраполировать этот пример на другие примеры.
Код Python
Используя пример смеси Пуассона, ниже приведена функция для вычисления апостериорной вероятности.
Приведенная выше функция возвращает список списков, где каждый внутренний список обозначает кластер, а содержимое внутреннего списка — это апостериорные вероятности. Попробуйте сопоставить этот код Python с приведенным выше изображением апостериорной формулы Пуассона.
3. Максимизация
Полная математика
Перейдите к разделу Все, что вам нужно знать, если вы не заинтересованы в выводах.
Максимизация относится к получению параметров путем максимизации ожидания полного логарифмического правдоподобия. Мы делаем это, находя производную математического ожидания и приравнивая ее к нулю. Вернемся к формуле.
Я буду использовать это обозначение для обозначения апостериорной вероятности, чтобы упростить уравнения.
Начнем с поиска оптимального π₁. Поскольку у нас есть только 2 кластера, мы можем заменить π₂ на 1 - π₁. Теперь давайте удалим из Q(θ, θ⁰) все члены, не содержащие π₁.
Нам разрешено это делать, потому что мы собираемся вывести это уравнение относительно π₁. Это означает, что все остальные члены, не содержащие π₁, в любом случае станут равными 0, поэтому давайте удалим их, чтобы уравнение стало проще для глаз. Следующим шагом является расширение внутренней сигмы.
На этом этапе получение производных относительно просто.
Установка производной на 0 даст следующие результаты.
С некоторой простой алгеброй решение для π₁ даст нам,
Интерпретация этого результата заключается в том, что с текущей полученной апостериорной вероятностью мы можем обновить π₁ до любого результата этого уравнения.
Я не буду повторять процесс для λ, потому что это будет слишком долго. Если вам интересно, посмотрите мои расчеты здесь. Кроме того, посетите раздел Все, что вам нужно знать, чтобы ознакомиться только с окончательными оценками.
Все, что тебе нужно знать
Все, что вам нужно знать о процессе максимизации, это то, что для получения оценок параметров нам нужно максимизировать полное логарифмическое ожидание правдоподобия. Вернемся к формуле.
Чтобы максимизировать это, нужно взять производные Q(θ, θ⁰) по каждому параметру и установить их равными 0. Помните, что апостериорная вероятность постоянна при взятии производных, поскольку она рассчитывается с использованием оценки предыдущей итерации.
Я покажу вам результат вывода для примера Пуассона.
Следовательно, чтобы получить новые оценки параметров каждой итерации, нам необходимо вычислить эти уравнения.
Код Python
Используя пример смеси Пуассона, ниже приведены функции для расчета оптимальных оценок параметров.
Приведенные выше функции возвращают два списка для оценок π и λ соответственно. Попробуйте сопоставить этот код Python с изображением Оптимальные формулы выше.
4. Алгоритм
До сих пор мы не дошли до демистифицирующей части статьи. Я понимаю, что все еще может быть размыто. Итак, давайте завершим все, что мы знаем, и запустим алгоритм.
Шаги алгоритма EM:
- Инициализировать случайные значения параметров.
- Получите математическое ожидание полного логарифмического правдоподобия, Q(θ, θ⁰).
- Вычислить апостериорные вероятности.
- Учитывая апостериорную вероятность, найдите оптимальные параметры путем дифференцирования Q(θ, θ⁰) по каждому параметру, установите производные равными 0 и найдите параметр.
- Измените текущие параметры на полученные на шаге 4.
Обратите внимание, что после изменения оценок параметров на шаге 5 пересчет апостериорных вероятностей даст другие результаты (см. апостериорную формулу Пуассонаизображение). Но если апостериорные вероятности теперь другие, то повторение шага 4 наверняка приведет к получению других оценок параметров (см. Оптимальные формулы image). И в этом суть алгоритма EM. Повторим это на английском языке. Алгоритм ЭМ таков:
- Используя текущие параметры, рассчитайте апостериорную вероятность.
- Используя текущую апостериорную вероятность, обновите параметры.
И мы повторяем эти шаги снова и снова. Не так уж это и мистично, не так ли? Конечно, математика все еще может быть тяжелой, но суть алгоритма заключается именно в этих двух маленьких шагах. Попробуем перевести это в код.
Теперь, без необходимости понимать содержимое каждой функции, этот код Python должен быть в состоянии выделить ядро алгоритма EM. Суть его математическая и сложная, но алгоритм довольно прост.
Единственная нерешенная часть головоломки — это критерии остановки. Теперь, когда мы понимаем, что делается на каждой итерации, мы хотим знать, когда останавливать итерацию. В следующем разделе объясняется этот критерий остановки.
5. Неполное логарифмическое правдоподобие
В этом разделе я введу понятие неполного логарифмического правдоподобия. Идея неполного логарифмического правдоподобия аналогична полному логарифмическому правдоподобию. Я не буду вдаваться в математические подробности, но, по сути, неполная логарифмическая правдоподобие не заботится о кластере данных. Он вычисляет вероятность из всех кластеров и суммирует их. Принимая во внимание, что полное логарифмическое правдоподобие принимает только вероятность кластера, из которого происходят данные.
Я собираюсь перевести эту формулу на Python.
Приведенная выше функция возвращает значение неполного логарифмического правдоподобия.
Из-за некоторых свойств, которые я не буду рассматривать, вероятность неполного логарифмического правдоподобия всегда будет увеличиваться на каждой итерации.Итерация алгоритма EM останавливается, когда изменение неполного логарифмического правдоподобия перестает быть значительным.
5. Резюме
Давайте поместим все в код.
Результатом этой функции является окончательная оценка параметра.
Теперь вам может быть интересно, почему я сказал, что алгоритм EM — это метод машинного обучения, тогда как это явно метод оценки. Мы вычисляли апостериорные вероятности по пути, и мы можем использовать это для получения кластеров каждой точки данных. Мы делаем это, вычисляя апостериорную вероятность точки данных, принадлежащей каждому кластеру, и назначая класс кластеру с наибольшей вероятностью. Отсюда и неконтролируемый метод машинного обучения.
Приведенные выше параметры lambdas и probs относятся к окончательной оценке алгоритма EM. Запуск этой функции вернет массив NumPy кластеров данных X.
6. Поздравления
Вы успешно закончили эту статью. Если бы вам удалось понять и воссоздать алгоритм, я бы вам поаплодировал. Но если нет, то это продвинутый алгоритм, и вы поймете его правильно, если попрактикуетесь. Посмотрите мой полный код на GitHub, чтобы узнать, как использовать наши функции на практике. Если вам понравилась эта статья, рассмотрите возможность аплодировать и подписаться. Пожалуйста, делитесь любыми отзывами и мыслями в комментариях. Спасибо за чтение!
