EM-алгоритм: различия между версиями

Материал из Поле цифровой дидактики
(Новая страница: «{{Понятие |Description=EM-алгоритм (англ. Expectation-maximization (EM) algorithm) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых пер...»)
 
Строка 5: Строка 5:
}}
}}
== Описание алгоритма ==
== Описание алгоритма ==
Пусть <math>\textbf{X}</math> — некоторые из значений наблюдаемых переменных, а <math>\textbf{T}</math> — скрытые переменные. Вместе <math>\textbf{X}</math> и <math>\textbf{T}</math> образуют полный набор данных. Вообще, <math>\textbf{T}</math> может быть некоторой подсказкой, которая облегчает решение проблемы в случае, если она известна. Например, если имеется [[смесь распределений]], [[функция правдоподобия]] легко выражается через параметры отдельных распределений смеси.
Пусть <math>\textbf{X}</math> — некоторые из значений наблюдаемых переменных, а <math>\textbf{T}</math> — скрытые переменные. Вместе <math>\textbf{X}</math> и <math>\textbf{T}</math> образуют полный набор данных. Вообще, <math>\textbf{T}</math> может быть некоторой подсказкой, которая облегчает решение проблемы в случае, если она известна. Например, если имеется смесь распределений, функция правдоподобия легко выражается через параметры отдельных распределений смеси.


Положим <math>p</math> — [[плотность вероятности]] (в непрерывном случае) или [[функция вероятности]] (в дискретном случае) полного набора данных с параметрами <math>\Theta</math>: <math>p( \mathbf X, \mathbf T | \Theta).</math> Эту функцию можно понимать как [[функция правдоподобия|правдоподобие]] всей модели, если рассматривать её как функцию параметров <math>\Theta</math>. Заметим, что [[условное распределение]] скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:
Положим <math>p</math> — [[плотность вероятности]] (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами <math>\Theta</math>: <math>p( \mathbf X, \mathbf T | \Theta).</math> Эту функцию можно понимать как[функция правдоподобия|правдоподобие всей модели, если рассматривать её как функцию параметров <math>\Theta</math>. Заметим, что условное распределение скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:


:<math>p(\mathbf T |\mathbf X, \Theta) = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{p(\mathbf X | \Theta)} = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{\int p(\mathbf X|\mathbf{\hat{T}}, \Theta) p(\mathbf{\hat{T}} |\Theta) d\mathbf{ \hat{T}}}</math>,
:<math>p(\mathbf T |\mathbf X, \Theta) = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{p(\mathbf X | \Theta)} = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{\int p(\mathbf X|\mathbf{\hat{T}}, \Theta) p(\mathbf{\hat{T}} |\Theta) d\mathbf{ \hat{T}}}</math>,
Строка 20: Строка 20:
</math>
</math>


где <math>Q(\Theta)</math> — [[Математическое ожидание|матожидание]] логарифма правдоподобия. Другими словами, мы не можем сразу вычислить точное правдоподобие, но по известным данным (<math>X</math>) мы можем найти ''[[Апостериори|апостериорную]]'' оценку вероятностей для различных значений скрытых переменных <math>T</math>. Для каждого набора значений <math>T</math> и параметров <math>\Theta</math> мы можем вычислить матожидание [[функция правдоподобия|функции правдоподобия]] по данному набору <math>X</math>. Оно зависит от предыдущего значения <math>\Theta</math>, потому что это значение влияет на вероятности скрытых переменных <math>T</math>.
где <math>Q(\Theta)</math> — [[Математическое ожидание|матожидание]] логарифма правдоподобия. Другими словами, мы не можем сразу вычислить точное правдоподобие, но по известным данным (<math>X</math>) мы можем найти ''[[Апостериори|апостериорную]]'' оценку вероятностей для различных значений скрытых переменных <math>T</math>. Для каждого набора значений <math>T</math> и параметров <math>\Theta</math> мы можем вычислить матожидание функции правдоподобия по данному набору <math>X</math>. Оно зависит от предыдущего значения <math>\Theta</math>, потому что это значение влияет на вероятности скрытых переменных <math>T</math>.


<math>Q(\Theta)</math> вычисляется следующим образом:
<math>Q(\Theta)</math> вычисляется следующим образом:

Версия 12:18, 26 марта 2023


Описание EM-алгоритм (англ. Expectation-maximization (EM) algorithm) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.
Область знаний Информатика, Робототехника
Авторы
Поясняющее видео
Близкие понятия SLAM
Среды и средства для освоения понятия

Описание алгоритма

Пусть [math]\displaystyle{ \textbf{X} }[/math] — некоторые из значений наблюдаемых переменных, а [math]\displaystyle{ \textbf{T} }[/math] — скрытые переменные. Вместе [math]\displaystyle{ \textbf{X} }[/math] и [math]\displaystyle{ \textbf{T} }[/math] образуют полный набор данных. Вообще, [math]\displaystyle{ \textbf{T} }[/math] может быть некоторой подсказкой, которая облегчает решение проблемы в случае, если она известна. Например, если имеется смесь распределений, функция правдоподобия легко выражается через параметры отдельных распределений смеси.

Положим [math]\displaystyle{ p }[/math] — плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами [math]\displaystyle{ \Theta }[/math]: [math]\displaystyle{ p( \mathbf X, \mathbf T | \Theta). }[/math] Эту функцию можно понимать как[функция правдоподобия|правдоподобие всей модели, если рассматривать её как функцию параметров [math]\displaystyle{ \Theta }[/math]. Заметим, что условное распределение скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:

[math]\displaystyle{ p(\mathbf T |\mathbf X, \Theta) = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{p(\mathbf X | \Theta)} = \frac{p(\mathbf X|\mathbf T, \Theta) p(\mathbf T |\Theta) }{\int p(\mathbf X|\mathbf{\hat{T}}, \Theta) p(\mathbf{\hat{T}} |\Theta) d\mathbf{ \hat{T}}} }[/math],

используя расширенную формулу Байеса и формулу полной вероятности. Таким образом, нам необходимо знать только распределение наблюдаемой компоненты при фиксированной скрытой [math]\displaystyle{ p(\mathbf X|\mathbf T, \Theta) }[/math] и вероятности скрытых данных [math]\displaystyle{ p(\mathbf T |\Theta) }[/math].

EM-алгоритм итеративно улучшает начальную оценку [math]\displaystyle{ \Theta_0 }[/math], вычисляя новые значения оценок [math]\displaystyle{ \Theta_1, \Theta_2, }[/math] и так далее. На каждом шаге переход к [math]\displaystyle{ \Theta_{n+1} }[/math] от [math]\displaystyle{ \Theta_n }[/math] выполняется следующим образом:

[math]\displaystyle{ \Theta_{n+1} = \arg\max_{\Theta}Q(\Theta) }[/math]

где [math]\displaystyle{ Q(\Theta) }[/math] — матожидание логарифма правдоподобия. Другими словами, мы не можем сразу вычислить точное правдоподобие, но по известным данным ([math]\displaystyle{ X }[/math]) мы можем найти апостериорную оценку вероятностей для различных значений скрытых переменных [math]\displaystyle{ T }[/math]. Для каждого набора значений [math]\displaystyle{ T }[/math] и параметров [math]\displaystyle{ \Theta }[/math] мы можем вычислить матожидание функции правдоподобия по данному набору [math]\displaystyle{ X }[/math]. Оно зависит от предыдущего значения [math]\displaystyle{ \Theta }[/math], потому что это значение влияет на вероятности скрытых переменных [math]\displaystyle{ T }[/math].

[math]\displaystyle{ Q(\Theta) }[/math] вычисляется следующим образом:

[math]\displaystyle{ Q(\Theta) = E_{\mathbf T} \! \! \left[ \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) \Big| \mathbf X \right] }[/math]

то есть это условное матожидание [math]\displaystyle{ \log p \left( \mathbf X, \mathbf T \,|\, \Theta \right) }[/math] при условии [math]\displaystyle{ \mathbf X }[/math].

Другими словами, [math]\displaystyle{ \Theta_{n+1} }[/math] — это значение, максимизирующее (M) условное матожидание (E) логарифма правдоподобия при данных значениях наблюдаемых переменных и предыдущем значении параметров. В непрерывном случае значение [math]\displaystyle{ Q(\Theta) }[/math] вычисляется так:

[math]\displaystyle{ Q(\Theta) = E_{\mathbf T} \! \! \left[ \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) \Big| \mathbf X \right] = \int^\infty _{- \infty} p \left(\mathbf T \,|\, \mathbf X, \Theta_n \right) \log p \left(\mathbf X, \mathbf T \,|\, \Theta \right) d\mathbf T }[/math]