Максимизация ожиданий (EM) - это своего рода вероятностный метод классификации данных. Пожалуйста, поправьте меня, если я ошибаюсь, если это не классификатор.
Каково интуитивное объяснение этой техники ЭМ? Что expectation
здесь и что происходит maximized
?
Ответы:
Примечание: код этого ответа можно найти здесь .
Предположим, у нас есть данные, взятые из двух разных групп, красной и синей:
Здесь мы можем увидеть, какая точка данных принадлежит красной или синей группе. Это позволяет легко найти параметры, характеризующие каждую группу. Например, среднее значение для красной группы составляет около 3, а для синей группы - около 7 (и мы могли бы найти точные средние значения, если бы захотели).
Это, вообще говоря, называется оценкой максимального правдоподобия . Учитывая некоторые данные, мы вычисляем значение параметра (или параметров), которое лучше всего объясняет эти данные.
Теперь представьте, что мы не можем видеть, какое значение было выбрано из какой группы. Нам все кажется фиолетовым:
Здесь мы знаем, что существует две группы ценностей, но мы не знаем, к какой группе принадлежит конкретная ценность.
Можем ли мы по-прежнему оценить средние значения для красной группы и синей группы, которые лучше всего соответствуют этим данным?
Да, часто можно! Максимизация ожиданий дает нам возможность это сделать. Самая общая идея алгоритма такова:
Эти шаги требуют дальнейшего объяснения, поэтому я рассмотрю проблему, описанную выше.
Пример: оценка среднего и стандартного отклонения
В этом примере я буду использовать Python, но код должен быть довольно простым для понимания, если вы не знакомы с этим языком.
Предположим, у нас есть две группы, красная и синяя, со значениями, распределенными, как на изображении выше. В частности, каждая группа содержит значение, полученное из нормального распределения со следующими параметрами:
Вот снова изображение этих красных и синих групп (чтобы избавить вас от необходимости прокручивать вверх):
Когда мы видим цвет каждой точки (то есть к какой группе она принадлежит), очень легко оценить среднее значение и стандартное отклонение для каждой группы. Мы просто передаем красные и синие значения встроенным функциям в NumPy. Например:
Но что, если мы не можем видеть цвета точек? То есть вместо красного или синего каждая точка была окрашена в фиолетовый цвет.
Чтобы попытаться восстановить параметры среднего и стандартного отклонения для красной и синей групп, мы можем использовать максимизацию ожидания.
Наш первый шаг ( шаг 1 выше) - угадать значения параметров для среднего значения и стандартного отклонения каждой группы. Нам не нужно гадать разумно; мы можем выбрать любые числа, которые нам нравятся:
Эти оценки параметров дают колоколообразные кривые, которые выглядят следующим образом:
Это плохие оценки. Оба средства (вертикальные пунктирные линии) выглядят далеко от любой «середины», например, для разумных групп точек. Мы хотим улучшить эти оценки.
Следующим шагом ( шаг 2 ) является вычисление вероятности появления каждой точки данных в предположениях текущего параметра:
Здесь мы просто поместили каждую точку данных в функцию плотности вероятности для нормального распределения, используя наши текущие предположения о среднем значении и стандартном отклонении для красного и синего. Это говорит нам, что , например, с нашими текущими предположениями данные указывают на 1.761 это гораздо более вероятно, будет красный (0,189) , чем синий (0,00003).
Для каждой точки данных мы можем превратить эти два значения правдоподобия в веса ( шаг 3 ), чтобы они суммировались до 1 следующим образом:
С нашими текущими оценками и нашими недавно вычисленными весами теперь мы можем вычислить новые оценки для среднего и стандартного отклонения красной и синей групп ( шаг 4 ).
Мы дважды вычисляем среднее значение и стандартное отклонение, используя все точки данных, но с разными весами: один раз для красных весов и один раз для синих весов.
Ключевым моментом интуиции является то, что чем больше вес цвета в точке данных, тем больше точка данных влияет на следующие оценки параметров этого цвета. Это дает эффект «подтягивания» параметров в правильном направлении.
У нас есть новые оценки параметров. Чтобы снова улучшить их, мы можем вернуться к шагу 2 и повторить процесс. Мы делаем это до тех пор, пока оценки не сойдутся, или после того, как будет выполнено некоторое количество итераций ( шаг 5 ).
Для наших данных первые пять итераций этого процесса выглядят следующим образом (последние итерации выглядят сильнее):
Мы видим, что средние значения уже сходятся на некоторых значениях, а формы кривых (определяемые стандартным отклонением) также становятся более стабильными.
Если мы продолжим 20 итераций, мы получим следующее:
Процесс EM сошелся на следующие значения, которые оказались очень близкими к фактическим значениям (где мы можем видеть цвета - никаких скрытых переменных):
В приведенном выше коде вы могли заметить, что новая оценка стандартного отклонения была вычислена с использованием оценки среднего значения предыдущей итерацией. В конечном итоге не имеет значения, вычисляем ли мы сначала новое значение для среднего, поскольку мы просто находим (взвешенную) дисперсию значений вокруг некоторой центральной точки. Мы по-прежнему увидим, что оценки параметров сходятся.
источник
EM - это алгоритм для максимизации функции правдоподобия, когда некоторые переменные в вашей модели не наблюдаются (т.е. когда у вас есть скрытые переменные).
Вы можете справедливо спросить, если мы просто пытаемся максимизировать функцию, почему бы нам просто не использовать существующий механизм для максимизации функции. Что ж, если вы попытаетесь максимизировать это, взяв производные и установив их в ноль, вы обнаружите, что во многих случаях условия первого порядка не имеют решения. Проблема курицы и яйца состоит в том, что для решения параметров вашей модели вам необходимо знать распределение ваших ненаблюдаемых данных; но распределение ваших ненаблюдаемых данных является функцией параметров вашей модели.
EM пытается обойти это, итеративно угадывая распределение ненаблюдаемых данных, затем оценивая параметры модели, максимизируя то, что является нижней границей фактической функции правдоподобия, и повторяя до сходимости:
EM алгоритм
Начните с предположения значений параметров вашей модели
Шаг E: для каждой точки данных, в которой отсутствуют значения, используйте уравнение модели, чтобы найти распределение недостающих данных с учетом вашего текущего предположения о параметрах модели и наблюдаемых данных (обратите внимание, что вы решаете распределение для каждого отсутствующего значение, а не ожидаемое значение). Теперь, когда у нас есть распределение для каждого пропущенного значения, мы можем вычислить математическое ожидание функции правдоподобия по отношению к ненаблюдаемым переменным. Если наше предположение для параметра модели было правильным, эта ожидаемая вероятность будет фактической вероятностью наших наблюдаемых данных; если параметры были неправильными, это будет просто нижняя граница.
M-шаг: Теперь, когда у нас есть ожидаемая функция правдоподобия без ненаблюдаемых переменных в ней, максимизируйте функцию, как в полностью наблюдаемом случае, чтобы получить новую оценку параметров вашей модели.
Повторяйте до схождения.
источник
Вот простой рецепт, чтобы понять алгоритм максимизации ожидания:
1- Прочтите этот учебник по EM от До и Бацоглу.
2- У вас могут быть вопросительные знаки в голове, взгляните на пояснения на этой странице обмена математическим стеком .
3- Взгляните на этот код, который я написал на Python, который объясняет пример из учебного документа EM, пункт 1:
Предупреждение: код может быть беспорядочным / неоптимальным, поскольку я не разработчик Python. Но это работает.
источник
Технически термин "EM" немного недооценен, но я предполагаю, что вы имеете в виду метод кластерного анализа Gaussian Mixture Modeling, который является примером общего принципа EM.
Собственно, кластерный анализ EM - это не классификатор . Я знаю, что некоторые люди считают кластеризацию «классификацией без учителя», но на самом деле кластерный анализ - это совсем другое.
Ключевое различие и большое непонимание классификации, которое люди всегда имеют с кластерным анализом, заключается в том, что при кластерном анализе нет «правильного решения» . Это метод открытия знаний , он на самом деле предназначен для поиска чего-то нового ! Это делает оценку очень сложной. Он часто оценивается с использованием известной классификации в качестве справочной, но это не всегда уместно: имеющаяся у вас классификация может или не может отражать то, что содержится в данных.
Приведу пример: у вас есть большой набор данных о клиентах, включая данные о поле. Метод, который разделяет этот набор данных на «мужской» и «женский», является оптимальным при сравнении его с существующими классами. С точки зрения «предсказания» это хорошо, поскольку для новых пользователей теперь можно предсказать их пол. С точки зрения «открытия знаний» это на самом деле плохо, потому что вы хотели обнаружить какую-то новую структуру в данных. Метод, который, например, разделил бы данные на пожилых людей и детей, тем не менее, будет иметь худшие результаты по сравнению с классом мужчин / женщин. Однако это был бы отличный результат кластеризации (если бы возраст не был указан).
А теперь вернемся к EM. По сути, он предполагает, что ваши данные состоят из нескольких многомерных нормальных распределений (обратите внимание, что это очень сильное предположение, особенно когда вы фиксируете количество кластеров!). Затем он пытается найти для этого локальную оптимальную модель, поочередно улучшая модель и назначение объекта модели .
Для достижения наилучших результатов в контексте классификации выберите количество кластеров, превышающее количество классов, или даже примените кластеризацию только к отдельным классам (чтобы узнать, есть ли какая-то структура внутри класса!).
Допустим, вы хотите научить классификатор различать «автомобили», «мотоциклы» и «грузовики». Мало смысла предполагать, что данные состоят ровно из трех нормальных распределений. Однако вы можете предположить, что существует более одного типа автомобилей (а также грузовиков и мотоциклов). Таким образом, вместо обучения классификатора для этих трех классов вы группируете автомобили, грузовики и мотоциклы в 10 кластеров каждый (или, может быть, 10 автомобилей, 3 грузовика и 3 велосипеда, что угодно), затем обучаете классификатора различать эти 30 классов, а затем объединить результат класса с исходными классами. Вы также можете обнаружить, что есть один кластер, который особенно трудно классифицировать, например Trikes. Это что-то вроде автомобилей и в некотором роде мотоциклов. Или грузовики для доставки, которые больше похожи на негабаритные автомобили, чем на грузовики.
источник
Если другие ответы хороши, я попытаюсь представить другую точку зрения и заняться интуитивной частью вопроса.
Алгоритм EM (Expectation-Maximization) - это вариант класса итерационных алгоритмов, использующих двойственность
Отрывок (выделено мной):
Обычно двойник B объекта A связан с A каким-либо образом, который сохраняет некоторую симметрию или совместимость . Например AB = const
Примеры итерационных алгоритмов, использующих двойственность (в предыдущем смысле):
Аналогичным образом алгоритм EM можно рассматривать как два двойных шага максимизации :
В итеративном алгоритме, использующем двойственность, существует явное (или неявное) предположение о равновесной (или фиксированной) точке сходимости (для EM это доказывается с помощью неравенства Йенсена)
Итак, схема таких алгоритмов такова:
Обратите внимание, что когда такой алгоритм сходится к (глобальному) оптимуму, он обнаруживает конфигурацию, которая является наилучшей в обоих смыслах (то есть как в области / параметрах x, так и в области / параметрах y ). Однако алгоритм может просто найти локальный оптимум, а не глобальный оптимум.
я бы сказал, что это интуитивное описание схемы алгоритма
Что касается статистических аргументов и приложений, другие ответы дали хорошие объяснения (также проверьте ссылки в этом ответе)
источник
Принятый ответ ссылается на статью Chuong EM Paper , которая неплохо объясняет EM. Существует также видео на YouTube , в котором статья объясняется более подробно.
Напомним, вот сценарий:
В случае вопроса первого испытания интуитивно мы могли бы подумать, что B сгенерировал его, поскольку доля орлов очень хорошо соответствует смещению B ... но это значение было всего лишь предположением, поэтому мы не можем быть уверены.
Имея это в виду, мне нравится думать о решении EM следующим образом:
Это может быть чрезмерным упрощением (или даже в корне неверным на некоторых уровнях), но я надеюсь, что это поможет на интуитивном уровне!
источник
EM используется, чтобы максимизировать вероятность модели Q со скрытыми переменными Z.
Это итеративная оптимизация.
e-step: с учетом текущей оценки Z вычислить ожидаемую функцию логарифмического правдоподобия
m-шаг: найдите тета, которая максимизирует этот Q
Пример GMM:
Электронный шаг: оценка присвоений меток для каждой точки данных с учетом текущей оценки gmm-параметра
m-шаг: максимизировать новую тэту с учетом новых присвоений метки
K-means также является алгоритмом EM, и есть много поясняющих анимаций на K-means.
источник
Используя ту же статью До и Бацоглу, процитированную в ответе Жубарба, я реализовал EM для этой проблемы на Java . Комментарии к его ответу показывают, что алгоритм застревает на локальном оптимуме, что также происходит с моей реализацией, если параметры thetaA и thetaB совпадают.
Ниже приведен стандартный вывод моего кода, показывающий сходимость параметров.
Ниже представлена моя Java-реализация EM для решения проблемы в (Do and Batzoglou, 2008). Основная часть реализации - это цикл для запуска EM до тех пор, пока параметры не сойдутся.
Ниже представлен весь код.
источник