Как популярно понять алгоритм EM

Как понять алгоритм EM в целом

 

 

предисловие

Студенты, которые узнали об алгоритме EM, могут знать, что алгоритм EM входит в десятку лучших алгоритмов интеллектуального анализа данных.Можно сказать, что машинного обучения или интеллектуального анализа данных нельзя избежать, но алгоритм EM подобен алгоритму интеллектуального анализа данных.KMPАлгоритмы кажутся простыми, но они не кажутся понятными с первого взгляда, вы хотите их избежать, но вы не можете их избежать, вы можете чувствовать то же самое, когда читаете эту статью.

Долгое время я всегда настаивал на точке зрения: когда ты усваиваешь какой-то пункт знания и чувствуешь, что не понимаешь его, девять раз из десяти это не значит, что ты недостаточно умен, а девять раз из десяти информация, которую вы читаете, недостаточно популярна или проста для понимания (если все еще нет, спросите у людей).

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

Поэтому в этой статье будет меньше говориться о формулах и приводить больше примеров.После понимания сути и значения алгоритма ЭМ само собой разумеется будет внимательно изучить формулы. Если у вас есть какие-либо вопросы, пожалуйста, не стесняйтесь оставлять комментарии, спасибо.

 

1. Что такое максимальная вероятность

Что такое алгоритм EM? Объяснение, данное Википедией, таково:

Алгоритм максимизации ожидания (алгоритм максимизации ожидания, также переводится как алгоритм максимизации ожидания) — это алгоритм нахождения оценки максимального правдоподобия или максимальной апостериорной оценки параметров в вероятностной модели, где вероятностная модель зависит от ненаблюдаемых скрытых переменных.

Алгоритм максимального ожидания вычисляется поочередно в два шага,

1. Первый шаг — рассчитать математическое ожидание (E), используя существующие оценки скрытых переменных для расчета их оценок максимального правдоподобия;
2. Второй шаг заключается в максимизации (M), максимизируя максимальное значение правдоподобия, полученное на шаге E, для вычисления значения параметра. Оценки параметров, найденные на шаге M, используются в расчете следующего шага E, который непрерывно чередуется.

1.1 Функция правдоподобия

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

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

Максимальная вероятность эквивалентна максимально возможному значению.

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

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

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

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

Предположим, что параметр известенB, спекулятивное событиеAВероятность того, что это произойдет, записывается как:

По формуле Байеса можно получить

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

Как только вы поставите формулу, вы можете запутаться. Тут я вспоминаю, что сказал в начале фронтира: Неужто не понятная статья?

Ответ, конечно же, да. Начнем с конкретного примера рабочей силы.

1.2 Пример функции правдоподобия: известная выборка X, найти параметрыθ

С тех пор, как робот Google Go AlphaGo победил чемпиона мира среди людей Ли Шиши со счетом 4:1, поток искусственного интеллекта вышел из-под контроля, и он стал популярным в различных областях, таких как беспилотное вождение, распознавание лиц, мониторинг безопасности и медицинская визуализация. . Сосредоточьтесь на обучении ИИОнлайн июльК концу 2017 года в нем также обучалось 100 000 студентов ИИ.

Предположим, нам нужно посчитать распределение роста мальчиков и девочек среди 100 000 онлайн-студентов в июле, как вести статистику? Учитывая огромное количество в 100 000, невозможно сосчитать их поодиночке. Да, случайная выборка, случайным образом выбрать 100 мальчиков и 100 девочек из 100 000 учеников, а затем по очереди подсчитать их рост.

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

1. Во-первых, мы извлекаем рост 100 мальчиков/девочек из 100 000 учащихся, чтобы сформировать выборку X, X={x1,x2,…,xN}, где xi представляет собой рост i-го нарисованного человека, а N равно до 100, Указывает количество взятых образцов.
2. Предполагается, что рост мальчиков имеет нормальное распределение., рост девушек подчиняется другому нормальному распределению:.
3. Но среднее значение u и дисперсию ∂2 этих двух распределений не знаю (не спрашивайте меня, что такое среднее значение и какова дисперсия, проверьте, пожалуйста, Google или Wikipedia), установите неизвестный параметр θ=[u, ∂] Т
4. Теперь необходимо использовать метод максимального правдоподобия (MLE) для оценки неизвестных параметров θ двух нормальных распределений через результаты роста этих 100 мальчиков или 100 девочек, то есть выборочного множества X. Постановка задачи эквивалентна известное X, найти θ, другими словами, найти p(θ|x)

Потому что эти мальчики (рост) подчиняются одному и тому же гауссовскому распределению p(x|θ). Тогда вероятность нарисовать мальчика А (рост) равна p(xA|θ), а вероятность нарисовать мальчика B равна p(xB|θ). Учитывая, что они независимы, мальчик A и мальчик B нарисованы одновременно. Вероятность равна p(xA|θ)*p(xB|θ).

Точно так же вероятность того, что я возьму эти 100 мужских выборок из общей выборки, распределение которых равно p(x|θ) одновременно, то есть совместная вероятность 100 выборок в выборке X (то есть, произведение их соответствующих вероятностей), используйте следующую формулу:

Вставьте предложение, в одной статье это будет использоваться для представления p(x|θ), а в некоторых статьях будет использоваться p(x;θ), но независимо от того, какой метод представления используется, суть одна и та же. Конечно, если задействована формула Байеса, лучше использовать первую для выражения p(x|θ).

Среди такого количества учеников мужского пола в сети в июле я нарисовал именно этих 100 мальчиков, как только нарисовал, а не других, а это значит, что во всей школе у ​​этих 100 человек (рост) самая высокая вероятность появления.Эта вероятность выше. Как достигается эта функция правдоподобия L(θ)?Другими словами, какое θ может максимизировать L(θ)?

1.3 Максимальное правдоподобие — это максимальное правдоподобие

Предположим, мы находим параметр, можно составить функцию правдоподобия L(θ)(θ), тогда рост этих 100 мальчиков самый большой)Должно быть «наиболее вероятное» значение параметра, эквивалентное оценке максимального правдоподобия θ. Записать как:

Здесь L(θ) — непрерывное умножение.Для удобства анализа мы можем определить логарифмическую функцию правдоподобия и превратить ее в непрерывное сложение:

Теперь нам нужно максимизировать функцию правдоподобия L(θ) для θ, и тогда θ, соответствующее максимальному значению, является нашей оценкой.

Для нахождения экстремального значения функции, благодаря знаниям исчисления, которые мы изучили в бакалавриате, наиболее прямая идея состоит в том, чтобы взять производную, а затем пусть производная равна 0, тогда θ, полученное путем решения этого уравнения (конечно, предпосылка состоит в том, что функция L( θ) непрерывно дифференцируема). Но что, если θ — это вектор с несколькими параметрами? Конечно, найти частную производную L(θ) по всем параметрам, то есть по градиенту, так, чтобы было n уравнений относительно n неизвестных параметров, а решением системы уравнений была крайняя точка функция правдоподобия и, наконец, значение параметра.

Общие шаги для нахождения оценки функции максимального правдоподобия:

1. Запишите функцию правдоподобия;
2. Возьмем логарифм функции правдоподобия и отсортируем;
3. Найдите производную, пусть производная равна 0, и получите уравнение правдоподобия;
4. Решите уравнение правдоподобия, и полученные параметры являются искомыми параметрами;

 

Во-вторых, популярное понимание алгоритма EM

2.1 Сложный случай оценки максимального правдоподобия

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

Например, в приведенном выше примере для подсчета распределения роста мальчиков и девочек среди 100 000 онлайн-студентов в июле

• Во-первых, мы извлекаем рост 100 мальчиков/девочек из 100 000 учащихся, чтобы сформировать выборку X, X={x1,x2,…,xN}, где xi представляет собой рост i-го нарисованного человека, а N равно до 100, Указывает количество взятых образцов.
• Предполагается, что рост мальчиков имеет нормальное распределение., рост девушек подчиняется другому нормальному распределению:, но среднее значение u и дисперсия ∂2 этих двух распределений неизвестны, установите неизвестный параметр θ=[u, ∂]T
• Теперь необходимо использовать метод максимального правдоподобия (MLE) для оценки неизвестных параметров θ двух нормальных распределений через результаты роста этих 100 мальчиков или 100 девочек, то есть выборочного множества X. Постановка задачи эквивалентна известное X, найти θ, другими словами, найти p(θ|x)

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

А теперь давайте немного усложним ситуацию, например, эти 100 мальчиков смешаны со 100 девочками. У нас есть данные о росте 200 человек, но мы не знаем, является ли каждый из этих 200 человек мальчиком или девочкой.В настоящее время пол мужчины и женщины является скрытой переменной.

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

Алгоритм EM существует для решения более сложной «оценки максимального правдоподобия».

2.2 Скрытые переменные в алгоритме EM

Понимание скрытых переменных в алгоритме EM имеет решающее значение, точно так же, как для понимания KMP требуется понимание значения массива NEXT.

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

На данный момент вы обнаружили, что основная проблема, с которой сталкивается алгоритм EM, заключается в следующем: существует скрытая переменная data Z. А если Z известно, то задачу можно решить с оценкой максимального правдоподобия. Итак, как сделать Z известным?

Возьмем другой пример из повседневной жизни.

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

решение:

1. Повар сначала пересыпает блюда из котла в две посуды, а затем смотрит, в каком блюде больше блюд, а затем равномерно распределяет блюда в этом блюде в другое блюдо, а затем повторяет процесс смешивания несколько раз. овощей в обеих тарелках примерно одинаково. В приведенном выше примереРезультатом среднего распределения является «наблюдаемые данные z», а количество блюд, распределенных по каждой тарелке для достижения среднего распределения, является «параметром θ, который необходимо найти», а ощущение распределенных блюд является «распределением вероятностей». ".
2. Таким образом, если есть только одна тарелка, определяется распределение вероятностей (ощущение «высыпать все блюда в кастрюле в одну тарелку» есть у всех), а поскольку тарелок две, «сколько блюд можно получить из одна пластина «Это хорошо» немного расплывчато, но мы можем использовать вышеуказанное решение для достижения конечной цели.

Идея алгоритма EM заключается в следующем:

1. Задайте начальное значение для θ самостоятельно (поскольку я не знаю, сколько тарелок должно быть на каждой тарелке, если я хочу добиться «две тарелки равномерно распределяют посуду в кастрюле», то я сначала оценю значение);
2. По заданным данным наблюдения и текущему параметру θ найти математическое ожидание условного распределения вероятностей ненаблюдаемых данных z (на предыдущем шаге посуда была разлита в две тарелки по ощущению руки, а затем этот шаг на основе «оба блюда в обоих блюдах. Есть блюда» и «сколько блюд в настоящее время на двух тарелках», чтобы судить об ощущении наливания тарелок);
3. На предыдущем шаге было найдено z, поэтому оптимальное θ' вычисляется по оценке максимального правдоподобия (осязание руки уже есть, затем судите, сколько блюд должно быть на тарелке по ощупыванию руки, а затем равномерно разложить посуду);
4. Поскольку результаты шагов 2 и 3 могут быть неоптимальными, повторяйте шаги 2 и 3 до сходимости (повторяйте равномерный процесс несколько раз, пока количество овощей в двух блюдах не станет примерно одинаковым).

Второй шаг выше называется Е-шагом (поиск ожидания), а третий шаг называется М-шагом (поиск максимизации), так что Е и М постоянно повторяются.

2.3 Третий пример алгоритма ЭМ: подбрасывание монеты

Nature Biotech использовал подбрасывание монеты в своей учебной статье по EM «Do, CB, & Batzoglou, S. (2008). Что такое алгоритм максимизации ожидания?. Nature biotechnology, 26 (8), 897». Пример, иллюстрирующий идею. алгоритма ЭМ.

Например, две монеты A и B. Если вы знаете, что подбрасывается каждый раз, A или B, вы можете напрямую оценить это (см. рис. a ниже).

Если вы не знаете, является ли это подбрасыванием A или B (в настоящее время это интересно, да, это скрытая переменная, о которой мы не знаем), наблюдается только 5 раундов петель, 10 раз за раунд, всего из 50 бросков монеты.В настоящее время невозможно напрямую оценить вероятность выпадения головы А и В. В это время настала очередь алгоритма EM (см. рисунок б ниже).

Возможно, с первого взгляда вы не поняли. Ничего, давайте популяризируем этот пример.

Еще две монеты A и B, предположим, что вероятность выпадения орла после случайного броска равна PA, PB соответственно. Чтобы оценить вероятность того, что эти две монеты выпадут, мы подбрасываем монеты A и B по очереди, 5 последовательных подбрасываний в каждом раунде, всего 5 раундов:

монета	результат	статистика
A	положительный и отрицательный	3 вперед - 2 назад
B	Плюсы и минусы	2 вперед - 3 назад
A	Плюсы и минусы	1 вперед - 4 назад
B	положительный и отрицательный	3 вперед - 2 назад
A	Плюсы и минусы	2 вперед - 3 назад

Монета A была подброшена 15 раз, и в первом, третьем и пятом раундах выпало 3 положительных, 1 положительный и 2 положительных результата соответственно, поэтому легко оценить PA, и, аналогично, PB также легко вычислить. следующее:

ПА = (3+1+2) / 15 = 0,4
ПВ= (2+3)/10 = 0,5

Проблема в том, что если мы не знаем, является ли подбрасываемая монета А или В (то есть тип монеты является скрытой переменной), а затем подбрасываем ее пять раз по очереди, мы получаем следующие результаты:

монета	результат	статистика
Unknown	положительный и отрицательный	3 вперед - 2 назад
Unknown	Плюсы и минусы	2 вперед - 3 назад
Unknown	Плюсы и минусы	1 вперед - 4 назад
Unknown	положительный и отрицательный	3 вперед - 2 назад
Unknown	Плюсы и минусы	2 вперед - 3 назад

Хорошо, вопрос становится интересным. Теперь наша цель не изменилась, по-прежнему оцениваем PA и PB, что нужно сделать?

Очевидно, в этот момент у нас есть дополнительная скрытая переменная типа монеты, которой присвоено значение z, которую можно рассматривать как 5-мерный вектор (z1, z2, z3, z4, z5), представляющий монету используется для каждого броска. Например, z1 представляет собой монету, использованную при первом броске, A или B.

• Однако, если эта переменная z неизвестна, невозможно оценить PA и PB, поэтому мы должны сначала оценить z, прежде чем мы сможем далее оценить PA и PB.
• Но чтобы оценить z, мы должны знать PA и PB, чтобы мы могли использовать правило вероятности максимального правдоподобия для оценки z. Разве это не проблема курицы и яйца? Как ее решить?

Ответ состоит в том, чтобы случайным образом инициализировать PA и PB, использовать их для оценки z, а затем оценить новые PA и PB в соответствии с правилом вероятности максимального правдоподобия на основе z.Если новые PA и PB такие же, как наши инициализированные PA и ПБ, о чем это говорит?

Это показывает, что наши инициализированные PA и PB являются вполне надежными оценками!

То есть для инициализированных нами PA и PB можно оценить z в соответствии с вероятностью максимального правдоподобия, а затем на основе z P1 и P2 можно в свою очередь оценить в соответствии с вероятностью максимального правдоподобия. инициализированы PA и PB. Объяснение состоит в том, что P1 и P2, вероятно, являются реальными значениями. Он содержит оценки максимального правдоподобия двух взаимодействий.

Что, если вновь оцененные PA и PB сильно отличаются от наших инициализированных значений? Он должен продолжать итерацию с новыми P1 и P2 до сходимости.

Мы могли бы также сделать это, сначала присвоив значение PA и PB, например:
Вероятность выпадения монеты А орлом PA = 0,2
Монеты B положительная вероятность PB = 0,7

Затем мы смотрим, какая монета, скорее всего, будет подброшена в первом раунде.
Если это монета А, то вероятность выпадения 3 орлов и 2 решек равна 0,2*0,2*0,2*0,8*0,8 = 0,00512.
Если это монета B, то вероятность выпадения 3 орлов и 2 решек равна 0,7*0,7*0,7*0,3*0,3=0,03087.
Затем найдите соответствующие вероятности в остальных 4 раундах по очереди. Составьте таблицу следующим образом (жирным шрифтом отмечена большая вероятность):

количество раундов	Если монета А	Если монета Б
1	0,00512, т.е. 0,2 0,2 ​​0,2 ​​0,8 0,8, 3 положительных - 2 отрицательных	0,03087,3 вперед - 2 назад
2	0.020480,2 0,2 ​​0,8 0,8 0,8, 2 положительных - 3 отрицательных	0,01323, 2 вперед - 3 назад
3	0,08192,То есть 0,2 0,8 0,8 0,8 0,8, 1 положительный - 4 отрицательный	0,00567, 1 вперед - 4 назад
4	0,00512, т.е. 0,2 0,2 ​​0,2 ​​0,8 0,8, 3 положительных - 2 отрицательных	0,03087,3 вперед - 2 назад
5	0,02048,То есть 0,2 0,2 ​​0,8 0,8 0,8, 2 положительных - 3 отрицательных	0,01323, 2 вперед - 3 назад

Согласно правилу максимального правдоподобия:
Скорее всего в 1 раундемонета Б
Скорее всего во 2 туремонета А
Скорее всего в 3 раундемонета А
Скорее всего в 4 раундемонета Б
Скорее всего в 5 раундемонета А

Мы складываем более высокую вероятность, то есть более вероятно, что это будет А, то есть количество раз 2, 1 и 2, которые оказываются положительными во 2-м, 3-м и 5-м раундах, и делим на общее количество раз A бросается 15 (A бросает три раунда, по 5 раз каждый), как оценка z, B вычисляется аналогично. Затем мы можем оценить новые PA и PB в соответствии с правилом вероятности максимального правдоподобия.

ПА = (2+1+2)/15 = 0,33
ПБ = (3 + 3) / 10 = 0,6

Предположим, что мы всезнающие боги и знаем, что монета при каждом подбрасывании такая, как указано в начале этого текстового раздела, тогда оценки максимального правдоподобия для PA и PB равны 0,4 и 0,5 (здесь и далее эти два значения обозначаются как PA и истинное значение PB). Затем сравните наши инициализированные PA и PB с недавно оцененными PA и PB:

Инициализированный ПА	Расчетная PA	настоящий ПА	инициализированный ПБ	Расчетный ПБ	реальный ПБ
0.2	0.33	0.4	0.7	0.6	0.5

Ты видел? Наши расчетные PA и PB намного ближе к своим истинным значениям, чем их первоначальные значения! Таким образом, постоянная итерация продолжает приближаться к истинному значению, что является магией алгоритма EM.

Можно ожидать, что мы будем продолжать следовать изложенным выше идеям, использовать предполагаемые PA и PB для оценки z, а затем использовать z для оценки новых PA и PB, После повторных итераций мы можем, наконец, получить PA = 0,4, PB = 0,5, в это время Как бы ни выполнялись итерации, значения PA и PB останутся неизменными на уровне 0,4 и 0,5, поэтому мы нашли оценки максимального правдоподобия PA и PB.

 

3. Вывод формулы алгоритма ЭМ

3.1 Целевая функция алгоритма EM   

Помните, что я сказал в начале раздела 1.2?

Вероятность извлечения этих 100 выборок из общей выборки с распределением p(x|θ), то есть совместная вероятность каждой выборки в наборе выборок X, выражается следующей формулой:

Предположим, у нас есть выборка {x(1),...,x(m)}, содержащая m независимых выборок, и теперь мы хотим найти неявный класс z каждой выборки, который может максимизировать p(x,z ). Оценка максимального правдоподобия p(x,z) выглядит следующим образом:

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

Для оценки параметров мы, по сути, по-прежнему хотим получить параметр θ, который максимизирует функцию правдоподобия, Теперь отличие от максимального правдоподобия состоит в том, что в функции правдоподобия есть неизвестная переменная z, см. следующую формулу (1). Другими словами, наша цель — найти подходящие θ и z, чтобы максимизировать L(θ). Тогда мы можем подумать, что у вас просто есть неизвестная переменная.Я также могу взять частные производные неизвестных θ и z соответственно, а затем сделать их равными 0. Разве решение не то же самое?

По сути, нам нужно максимизировать формулу (1), которая является функцией правдоподобия, но мы видим, что в ней есть «логарифм суммы», и вид после вывода будет очень сложным (можете себе представить log( f1(x)+ f2(x)+ f3(x)+…) вывод сложной функции), поэтому трудно решить, чтобы получить неизвестные параметры z и θ.

Умножаем числитель и знаменатель на равную функцию (то есть на распределение вероятностей Qi(z(i)) скрытой переменной Z, а сумма ее вероятностей равна 1, то есть), то есть формула (2) на приведенном выше рисунке получается, но формула (2) по-прежнему имеет «логарифм суммы», и решить ее по-прежнему нельзя, что делать? Затем, чтобы засвидетельствовать волшебный момент, мы можем получить (3) через неравенство Дженсена, и в это время (3) становится «сумма логарифмов», так что вывод легко.

От формулы (2) до формулы (3) есть два волшебных места:

1. Когда мы ищем максимальное значение уравнения (2), уравнение (2) вычислить нелегко, мы думаем, что уравнение (2) больше, чем нижняя граница (3), которую удобно вычислять, и пытаемся сделать так, чтобы нижняя граница (3) максимально. ) максимизируется до тех пор, пока результат вычисления (3) не станет равным (2), затем максимальное значение (2) получается косвенным путем;
2. Неравенство Дженсена, каково происхождение неравенства Дженсена, продвигающего магию?

3.2 Неравенство Дженсена

Пусть f функция, область определения которой действительна.

• Если для всех действительных чисел x вторая производная от f (x), то f — выпуклая функция.
• когдаxКогда это вектор, если его гессенская матрица H - полуположительна (), то f — выпуклая функция.
• еслиили, то f называется строго выпуклой функцией.

Неравенство Дженсена формулируется следующим образом:

Если f — выпуклая функция, а X — случайная величина, то: E[f(X)]>=f(E[X]), популярная поговорка состоит в том, что математическое ожидание функции больше или равно ожидаемому функция.

В частности, если f — строго выпуклая функция, тогда и только тогда, когда P(X = EX) = 1, т. е. X — константа, приведенное выше уравнение принимает знак равенства, т. е. E[f(X)] = f(ЕХ).

Как показано ниже

 

На рисунке сплошная линия f представляет собой выпуклую функцию (поскольку область над функцией представляет собой выпуклое множество), X — случайная величина с вероятностью 0,5 быть a и с вероятностью 0,5 быть b (как подбрасывание монета). Ожидаемое значение X является медианой значений a и b. Это хорошо видно из.

Конечно, когда f — (строго) вогнутая функция тогда и только тогда, когда —f — (строго) выпуклая функция, направление знака неравенства меняется на противоположное, т. е..

Вернемся к формуле (2), поскольку f(x)=log x — вогнутая функция (ее вторая производная равна -1/x2

(2) гдеэто ожидания. Зачем? Вспомните правило ленивого статистика в формуле ожидания следующим образом

Пусть Y — функция случайной величины X(g — непрерывная функция), то (1) X — дискретная случайная величина, закон ее распределения, к=1,2,…. какабсолютно сходится, то(2) X — непрерывная случайная величина, плотность вероятности которой равна,какабсолютно сходится, то

Учитывая, что E(X)=∑x*p(x), f(X) является функцией X, тогда E(f(X))=∑f(x)*p(x)), и, поэтому можно получить неравенство формулы (3):

Хорошо, здесь, теперь уравнение (3) можно легко вывести, но уравнение (2) и уравнение (3) являются знаками неравенства, максимальное значение уравнения (2) не является максимальным значением уравнения (3), и мы Если вы хотите получить максимальное значение формулы (2), что нам делать?

Приведенные выше неравенства уравнений (2) и (3) можно записать в виде: функция правдоподобия L(θ)>=J(z, Q), как упоминалось в конце раздела 3.1, мы можем непрерывно максимизировать эту нижнюю границу J, Сделать так, чтобы L(θ) непрерывно увеличивалась и, наконец, достигла максимального значения L(θ).

На рис. выше у нас [тета] фиксирована, корректировка Q (z) так, чтобы нижняя граница J (z, Q) до L (θ) в этой точке была равна [тета] (зеленые кривые переходят в синюю кривую) , затем зафиксировали Q (z), отрегулировали так, чтобы нижняя граница [тета] J (z, Q) достигла максимума (от [тета] t до θt + 1), затем зафиксировали θ, подкорректировав Q (z)…. .. до сходимости к функции максимального правдоподобия L (θ) при θ * .

Вот два вопроса:

1. Когда нижняя граница J(z, Q) равна L(θ) в этой точке θ?
2. Почему он должен сходиться?

   

Прежде всего, в неравенстве Йенсена упоминается первый вопрос, когда независимая переменная X является константой, уравнение выполняется. Другими словами, чтобы сделать уравнение (3) равным, нам нужно:

где c — константа, не зависящая от. Преобразуйте эту формулу и просуммируйте все z, чтобы получить

потому что вышеупомянутое(Да, распределение вероятностей скрытой переменной Z, сумма его вероятностей равна 1), поэтому можно вывести:

так что проходите, может быть получензначение (т.е./с), плюс,такза

Мгновенно внезапно открыть! На данный момент мы запустили формулу расчета Q (z) нижней границы q (z) после неподвижного параметра θ, и решает задачу того, как выбрана q (z). Этот шаг - это шаг e, устанавливая нижнюю границу L (θ).

Следующие M шагов состоят в том, чтобы скорректировать θ после заданного Q (z), чтобы максимизировать нижнюю границу J (z, Q) L (θ), В конце концов, после фиксации Q (z) нижнюю границу все еще можно скорректировать. .

Это шаг алгоритма EM.

3.3 Процесс и доказательство алгоритма ЭМ

Подытожим, алгоритм EM математического ожидания — это метод оценки максимального правдоподобия для решения параметров вероятностной модели по неполным данным или наборам данных с отсутствующими данными (со скрытыми переменными).

Другими словами, когда мы не знаем конкретное значение скрытой переменной z (такой как монета A или монета B), нелегко судить о вероятности θ того, что монета A или монета B выпадут орлом. тогда

1 Случайным образом инициализируйте параметр распределения θ2, а затем повторите цикл до сходимости { (шаг E, найдите функцию Q) Для каждого i вычислите апостериорную вероятность скрытой переменной на основе параметров модели предыдущей итерации (фактически скрытая переменная ожидание), как текущая оценка скрытой переменной:(M шагов, найдите значение параметра, когда функция Q максимизируется) Максимизируйте функцию правдоподобия, чтобы получить новое значение параметра

Таким образом, Q(z) вычисляется и подставляется в θ, а θ вычисляется и подставляется обратно в Q(z).При такой постоянной итерации можно получить параметр θ, который максимизирует функцию правдоподобия L(θ).

Кроме того, как и второй вопрос, поднятый в предыдущем разделе, будет ли он сходиться? Или как обеспечить ЭМ сходимость?

Здесь прямо цитируются заметки о машинном обучении, сделанные JerryLead, чтобы доказать, что я сделал соответствующие объяснения и пояснения.

Предполагатьиявляется результатом EM после итерации t и t+1 (да, верхний индекс t означает итерацию t). если мы докажем, что означает, что оценка максимального правдоподобия монотонно возрастает, то в итоге мы достигнем максимального значения оценки максимального правдоподобия.

Докажите это ниже.

выбранПосле того, как мы получим шаг E

      

Этот шаг гарантирует, что при заданномПри выполняется уравнение в неравенстве Йенсена, т. е.

      

Затем выполните M шагов, зафиксированных, и воляв качестве переменной для вышеуказанногоПосле вывода получаем, после некоторого вывода будет установлена ​​следующая формула:

Объясните шаг (4), получите, просто максимизировать, это,Нижняя граница , без выполнения уравнения, уравнение выполняется только при фиксированном, и нажмите E, чтобы получитьвремя установить.

Более того, согласно следующей формуле, полученной нами ранее, для всехиоба установлены

           

Шаг (5) использует определение M-шага, которое заключается вприспособить к, что максимизирует нижнюю границу. Таким образом, (5) выполняется, а (6) является результатом предыдущего уравнения.

Это доказываетбудет монотонно возрастать. Метод сходимостиНикаких изменений, другое в том, что изменение очень мало.

Объясните (4), (5), (6) еще раз.

• Во-первых, (4) выполняется для всех параметров, а условия его равенства фиксируются только при, и он устанавливается при регулировке Q, а шаг (4) заключается только в том, чтобы зафиксировать Q, отрегулировать, нет никакой гарантии, что уравнение будет выполнено.
• (4)–(5) — определения M шагов, а (5)–(6) — условия установления равенства, гарантированного предыдущими E шагами. То есть шаг Е будет тянуть Нижний кконкретное значение (здесь) на той же высоте и в это время обнаруживается, что нижняя грань еще может подняться, поэтому через M шагов нижняя грань снова подтягивается вверх, но не может достичь той же высоты, что иДругим конкретным значением является та же высота, а затем шаг E подтягивает нижнюю границу к той же высоте, что и это конкретное значение, и повторяется до максимального значения.

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

Сначала найдем Q(z) и подставим его в θ, мы можем получить:

 (7)

в:

 (8)

 (9)

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

1. Во-первых, согласно формуле (9), поНайдите условное распределение
2. 
3. положить сноваВнесите его в (7), чтобы получить

 (10)

Это просто нужно, чтобы максимизировать совместное распределение, чтобы максимизироватьЗатем повторите эти 2 шага.

Очевидно, что шаг M максимизирует, так что насчет шага E? Согласно формуле (10) имеем

  

Фактически шаг Е состоит в том, чтобы найти условное математическое ожидание при заданном X, то есть апостериорное математическое ожидание, чтобы неравенство Циньшэна формулы (3) могло принять знак равенства, то есть увеличить меньший конец неравенства Дженсена до сделать его равным В большом конце, это расширение; M шагов максимизируют совместное распределение и находят крайнюю точку с помощью 0 градиента, метода Лагранжа и т. д., что является еще одним расширением. Пока функция правдоподобия ограничена, пока точка градиента 0 на шаге M является точкой максимального значения, окончательный запрос можно найти, продолжая увеличивать масштаб.

3.4 Другое понимание алгоритма EM

Если мы определим

Из предыдущего вывода мы знаем, EM можно рассматривать как метод подъема по координате J, а шаг E фиксируется,оптимизация, M шагов фиксированыоптимизация.

Координаты подъема:

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

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

Соответствует EM, то есть:Е шаг: фиксированное θ, оптимизированное Q;М шаг: исправляем Q, оптимизируем θ, поочередно подталкиваем крайние значения к максимуму. 

 

4. Применение ЭМ: оценка двух неизвестных параметров pLSA

На самом деле существует много приложений алгоритма EM, наиболее широко используемыми являются модель Гаусса смеси GMM, кластеризация, HMM и так далее. такие как кластеризация

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

4.1 Создание документов по модели pLSA

Статья часто имеет несколько тем, но вероятность появления каждой из этих тем в документе различна. Например, в документе, представляющем страну, часто упоминается несколько тем, таких как образование, экономика и транспорт. Затем в pLSAКак формируется документ??

Предположим, вы хотите написать M документов.Поскольку документ состоит из разных слов, вам нужно определить слово в каждой позиции в каждом документе.

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

• 1Предположим, вы делаете K-грань кубика «документ-тема» для каждого документа, который вы пишете (бросайте этот кубик, чтобы получить любую из K тем), и K-граней «тема-термин» кубика (каждый кубик соответствует теме). , K кубиков соответствуют предыдущим K темам, и каждая грань кубика соответствует термину, который нужно выбрать, а V сторон соответствуют V необязательным словам).

  • Например, можно установить К=3, то есть можно сделать кубик «тема документа» с тремя темами, причем тремя темами могут быть: образование, экономика и транспорт. Тогда пусть V = 3, сделайте 3 кубика «тема-термин» с 3 сторонами, где слова на 3 сторонах кубика с образовательной тематикой могут быть: университет, учитель, курс и 3 стороны кубика с экономической тематикой. Слова на кубике могут быть: рынок, бизнес, финансы, транспорт Слова на трех сторонах кубика могут быть: высокоскоростная железная дорога, автомобиль и самолет.

• 2Для каждого написанного слова сначала бросьте кубик «тема документа», чтобы выбрать тему, а после получения результата по теме используйте кубик «тема-термин», соответствующий результату темы, и бросьте кубик, чтобы выбрать слово, которое нужно написать.

  • Сначала бросьте кубик «тема документа», предполагая (с определенной вероятностью), что полученная тема является образованием, поэтому следующим шагом будет бросить сито темы образования и (с определенной вероятностью) получить слово, соответствующее образованию. Тематическое сито: университет.

    • Описанный выше процесс бросания игральных костей для генерации слов упрощается следующим образом: «Сначала выберите тему с определенной вероятностью, а затем выберите слово с определенной вероятностью». На самом деле, в начале есть три темы на выбор: образование, экономика, транспорт, так зачем выбирать тему образования? На самом деле он выбирается случайно, но этот случай следует определенному распределению вероятностей. Например, вероятность выбора темы образования равна 0,5, вероятность выбора темы экономики равна 0,3, а вероятность выбора темы транспорта равна 0,2, тогдаРаспределение вероятностей для этих 3 тепов {Образование: 0,5, Экономика: 0,3, Транспортировка: 0,2}, мы называем распределение вероятностей каждой темы z в документе d распределением тем, и это полиномиальное распределение.
    • Точно так же после случайного извлечения образовательных тем из тематического распределения остаются три слова: университет, преподаватель и курс.Эти три слова могут быть выбраны, но вероятность их выбора также различна. Например, вероятность выбора слова университет равна 0,5, вероятность выбора слова учитель равна 0,3, а вероятность выбора слова курс равна 0,2, тогдаРаспределение вероятности этих 3 слов: {Университет: 0,5, Учитель: 0,3, Курс: 0,2}, мы называем распределение вероятности каждого слова w по теме z как распределение слов, которое также является полиномиальным распределением.
    • так,И выбор темы, и выбор слова — два случайных процесса: сначала тема: образование извлекается из распределения тем {образование: 0,5, экономика: 0,3, транспорт: 0,2}, а затем распределение слов, соответствующее теме образования {университет: 0,5 , учитель: 0,3, курс: 0,2} для извлечения слова: университет.

• 3, Наконец, вы продолжаете неоднократно бросать кости «тема документа» и «тема-термин», повторяя N раз (генерируя N слов), чтобы завершить документ, повторяя этот метод создания документа M раз, затем завершите M документы.

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

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

• выразить словов данном документевероятность появления в .

  • Как его рассчитать? Для массивных документов после токенизации всех документов получается список словарей, так что каждый документ представляет собой набор слов. Для каждого слова разделите количество раз, которое оно встречается в документе, на общее количество слов в документе, чтобы получить вероятность его появления в документе..

• указать конкретную темув данном документевероятность возникновения.

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

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

1. по вероятностивыбрать документ
2. выбранный документТогда по вероятности из тематического распределенияВыберите подразумеваемую категорию темы
3. выбранТогда по вероятности из распределения словвыбрать слово

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

4.2 Сделать вывод о распределении темы на основе документа

И наоборот, поскольку документ был сгенерирован, как сделать вывод о его теме на основе сгенерированного документа? Этот процесс вывода его скрытых тем (распространения) из просмотренных документов (фактически обратный процесс создания документов) является целью моделирования тем: автоматически обнаруживать темы (распространения) в наборе документов.

Другими словами, люди писали различные статьи на основе модели генерации документов, а затем бросали их вКомпьютер эквивалентен тому, что компьютер видит, это статья, которая была написана. Теперь компьютер должен обобщить тему статьи на основе ряда слов, встречающихся в статье, а затем получить различную вероятность появления каждой темы: распределение темы. То есть документ d и слово w доступны для наблюдения, но тема z скрыта.

Как показано на рисунке ниже (цветные d и w на рисунке представляют наблюдаемые переменные, незакрашенный z представляет неизвестные скрытые переменные, N представляет собой всего N слов в документе, а M представляет M документов):

На приведенном выше рисунке документ d и слово w — это образцы, которые мы получили (выборки случайны, параметры неизвестны, но фиксированы, поэтому pLSA принадлежит частотной идее. Отличие от LDA, введенного в ссылке 8: образец фиксирован, параметры неизвестны, но не фиксированы, является случайной величиной и подчиняется определенному распределению, поэтому LDA принадлежит байесовской мысли) и может наблюдаться, поэтому для любого документа егоизвестен.

Таким образом, он может быть основан на большом количестве известной информации о терминах документа., обученный документ-темаи предметный термин, как показано в следующей формуле:

Следовательно, вероятность генерации каждого слова в документе получается как:

так какможно рассчитать заранее,иинеизвестно, так чтопараметр (значение), который мы хотим оценить, с точки зрения непрофессионала, состоит в том, чтобы максимизировать это θ.

Какой метод используется для оценки Обычно используемые методы оценки параметров включают оценку максимального правдоподобия MLE, максимальную оценку MAP после проверки, байесовскую оценку и так далее. Поскольку оцениваемый параметр содержит скрытую переменную z, мы можем рассмотреть алгоритм EM.

4.3 EM-алгоритм для оценки двух неизвестных параметров pLSA

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

• предполагается использоватьрепрезентативный словарьв темуполиномиальное распределение на , томожет быть представлен в виде вектора, каждый элемент **экспресс-терминпоявится в теме** вероятность в,Сейчас

• использоватьпоказать все темыв документацииполиномиальное распределение на , томожет быть представлен в виде вектора, каждый элемент **Укажите темупоявиться в документеВероятность в **, т.е.

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

Поскольку слова и слова независимы друг от друга, распределение N слов во всем документе таково:

Поскольку документы и документы также независимы друг от друга, распределение слов во всем корпусе таково (M документов во всем корпусе, N слов в каждом документе):

в,экспресс-терминв документацииЧастота слов,Указывает общее количество слов в документе DI, очевидно.
Таким образом, получается логарифмическая функция правдоподобия распределения слов всего корпуса (в следующей формуле есть небольшая ошибка, правильная должна быть: N is M, M is N):

Теперь нам нужно максимизировать приведенную выше функцию логарифмического правдоподобия, чтобы найти параметрыи. Для этой оценки максимального правдоподобия со скрытыми переменными можно использовать алгоритм EM. Алгоритм EM делится на два шага: сначала E-шаг, затем M-шаг.

• E-step: Предполагая, что параметры известны, вычислить апостериорную вероятность скрытой переменной в это время.

Используя правило Байеса, мы можем получить:

• M-step: Введите апостериорную вероятность скрытой переменной, максимизируйте логарифмическую функцию правдоподобия выборочного распределения и решите соответствующие параметры.

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

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

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

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

потому что параметр, который мы хотим решить,и, соответственноиНайдите частную производную, а затем установите результат частной производной равным 0, чтобы получить (в следующей формуле есть небольшая ошибка, правильная должна быть: N равно M, M равно N):

Устраните множители Лагранжа, и, наконец, можно будет оценить параметры.и(В следующей формуле есть небольшая ошибка, правильная должна быть: N есть M, M есть N):

Таким образом, в pLSA:

1. так какинеизвестно, поэтому мы используем алгоритм EM для оценкиЗначение этого параметра.
2. Затем используйтеэкспресс-терминпоявится в темевероятность в,использоватьУкажите темупоявиться в документевероятность в, тем самым ставяПреобразовав в матрицу «тема-термин» Φ (слова-генераторы темы), положимПреобразуется в матрицу «тема документа» Θ (тема генерации документа).
3. наконец решено,.

Наконец, стоит упомянуть, что на основе модели pLSA добавлена ​​байесовская структура, которая представляет собой LDA.Более подробную информацию о LDA см. в Справке 8.

 

5. Ссылки и рекомендуемая литература

1. ДжерриЛид:(алгоритм EM) Алгоритм EM
2. зукси09:От максимального правдоподобия к алгоритму EM
3. Как доступно объяснить алгоритм ЭМ и привести пример?
4. Милтер:Как понять алгоритм ЭМ перцептивно?
5. Алгоритм EM девять областей
6. Онлайн открытое занятие в июле:18-минутный алгоритм EM
7. Онлайн июльМашинное обучение, выпуск 9Четвертое занятие: доктор Тан провел 5 часов, подробно анализируя и вырабатывая ЭМ-алгоритм.
8. Популярное понимание тематической модели LDA

 

6. Постскриптум

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

Ниже указано количество ревизий.

1. Вечером 8.25 первый раунд доработок по улучшению формулы вычисления функции плотности вероятности Q(z) скрытой переменной z - вывод условной вероятности;
2. Ранним утром 8.26 второй раунд исправлений улучшил вывод формулы алгоритма EM, в том числе: Q(z) было вычислено и заменено на θ, а θ было вычислено и заменено обратно на Q(z);
3. Утром 8:26 был проведен третий раунд доработок для улучшения итеративного решения θ в алгоритме EM;
4. Вечером 8.26 четвертый раунд доработок, упрощающий описание примеров, связанных с алгоритмом EM, сделал идеи написания более понятными;
5. Утром 8.28 пятый раунд доработки, добавляющий алгоритм EM для оценки двух неизвестных параметров pLSA, делает читателей не только знакомыми с сущностью и выводом, но и опытными в применении.

Июль, август 2018.