ЭМ-алгоритм

машинное обучение искусственный интеллект алгоритм .NET

 Алгоритм максимизации ожидания(expectation maximization algorithm), сокращенноЭМ-алгоритм, является итеративным алгоритмом, который можно использовать для определения скрытых переменных (hidden variable) является оценкой максимального правдоподобия параметров вероятностной модели или максимальной апостериорной оценкой.Алгоритм максимизации ожидания(expectation maximization algorithm), сокращенноЭМ-алгоритм, является итеративным алгоритмом, который можно использовать для определения скрытых переменных (hidden variable) является оценкой максимального правдоподобия параметров вероятностной модели или максимальной апостериорной оценкой.

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

Прежде чем вводить алгоритм EM, сначала введем важное неравенство -Неравенство Дженсена(Jensen's Inequality)

  • сделатьx_1< x_2 , f(x)является выпуклой функцией, и если она имеет вторую производную, вторая производная которой всегда больше или равна 0, то существуют:
    tf(x_1) + (1-t)f(x) \ge f(tx_1+(1-t)x_2) \quad 0\le t\le1\tag{1}
    延森不等式

Если мы находимся в этом состоянии, предположим,xявляется случайной величиной, то:

E[f(x)] \ge f[E(x)] \tag{2}

  • Точно так же, когдаf(x)Когда это вогнутая функция, есть:

    E[f(x)] \le f[E(x)] \tag{3}

  • Далее, если вторая производная функции больше 0, то:

    \begin{align} E[f(x)] = f[E(x)] &\Leftrightarrow x为常量 \\ &\Leftrightarrow x = E(x) \end{align}\tag{4}

ЭМ-алгоритм

определение проблемы

Гипотетический обучающий набор\{x^{(1)},x^{(2)},...,x^{(m)}\}Отmсостоят из независимых немаркированных образцов. У нас есть модель распределения вероятностей для этого обучающего набораp(x,z;θ), но мы можем только наблюдатьx. Нам нужно сделать параметрθмаксимизировать логарифмическую вероятность , а именно:

\begin{align} arg \max_\theta l(\theta) &= arg \max_\theta \sum_{i=1}^m \log P(x^{(i)};\theta) \\ &= arg \max_\theta \sum^m_{i=1} \log \sum_z P(x^{(i)},z^{(i)};\theta) \end{align} \tag{5}

процесс формализации

В частности, нам нужно каждый раз для функции\log P(x;\theta)указать на\theta, найти вогнутую функциюg(\theta) \le \log P(x;\theta), каждый разg(\theta)Максимальный балл следующий\theta, итерируем до тех пор, пока не будет найдена целевая функцияlogP(x;\theta)достигает локального максимума.

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

EM

получить

Мы предполагаем, что каждыйz^{(i)}Функция распределенияQ_i,Так и есть\sum_ZQ_i(z)=1, Q_i(z) \ge0,имеют:

\begin{align} l(\theta) &= \sum_i\log\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta) \\ &= \sum_i \log \sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \\ &\ge \sum_i \sum_{z^{(i)}}Q_i(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \end{align} \tag{6}

мы знаем\logявляется вогнутой функцией, если положить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)})}, то приведенное выше неравенство можно получить из неравенства Йенсена (3).

С того времени,\thetaЛогарифмическая функция правдоподобияl(\theta)Существует нижняя граница, но мы хотим получить более точную нижнюю границу, что является случаем, когда соблюдается знак равенства.Тогда мы имеем:

\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} = c \quad(c为常数) \tag{7}

но:

Q_i(z^{(i)}) = c*p(x^{(i)},z^{(i)};\theta) \tag{8}

снова\sum_ZQ_i(z)=1, Q_i(z) \ge0,так:

\sum_ZQ_i(z^{(i)})= \sum_Z c*p(x^{(i)},z^{(i)};\theta)=1 \tag{9}

так:

c = \frac{1}{\sum_Z p(x^{(i)},z^{(i)};\theta)} \tag{10}

Тогда по формуле (8) имеем:

\begin{align} Q_i(z^{(i)}) &= \frac{p(x^{(i)},z^{(i)};\theta)}{\sum_Z p(x^{(i)},z^{(i)};\theta)}\\ & = \frac{p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)} \\ &= p(z^{(i)}| x^{(i)};\theta) \end{align} \tag{11}

Поток алгоритма

repeat

​(E step) for each i

Q_i(z^{(i)}) := p(z^{(i)}| x^{(i)};\theta)

​end for

​(M step)

\theta := arg\max_\theta\sum_i \sum_{z^{(i)}}Q_i(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}

untilФункция правдоподобия достигает своего максимального значения

использованная литература

[1] danerer-CSDN, Эндрю Нг Примечания к курсу машинного обучения (13) Алгоритм EM для неконтролируемого обучения [EB/OL], https://blog.csdn.net/danerer/article/details/80282612#expectation-maximization-algorithm , 2018-5-11/2018-7-30.

[2] Википедия, Неравенство Дженсена[DB/OL], https://en.wikipedia.org/wiki/Jensen%27s_inequality, 2018-06-06/2018-7-30.

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

Прежде чем вводить алгоритм EM, сначала введем важное неравенство -Неравенство Дженсена(Jensen's Inequality)

  • сделатьx_1< x_2 , f(x)является выпуклой функцией, и если она имеет вторую производную, вторая производная которой всегда больше или равна 0, то существуют:
    tf(x_1) + (1-t)f(x) \ge f(tx_1+(1-t)x_2) \quad 0\le t\le1\tag{1}
    延森不等式

Если мы находимся в этом состоянии, предположим,xявляется случайной величиной, то:

E[f(x)] \ge f[E(x)] \tag{2}

  • Точно так же, когдаf(x)Когда это вогнутая функция, есть:

    E[f(x)] \le f[E(x)] \tag{3}

  • Далее, если вторая производная функции больше 0, то:

    \begin{align} E[f(x)] = f[E(x)] &\Leftrightarrow x为常量 \\ &\Leftrightarrow x = E(x) \end{align}\tag{4}

ЭМ-алгоритм

определение проблемы

Гипотетический обучающий набор\{x^{(1)},x^{(2)},...,x^{(m)}\}Отmсостоят из независимых немаркированных образцов. У нас есть модель распределения вероятностей для этого обучающего набораp(x,z;θ), но мы можем только наблюдатьx. Нам нужно сделать параметрθмаксимизировать логарифмическую вероятность , а именно:

\begin{align} arg \max_\theta l(\theta) &= arg \max_\theta \sum_{i=1}^m \log P(x^{(i)};\theta) \\ &= arg \max_\theta \sum^m_{i=1} \log \sum_z P(x^{(i)},z^{(i)};\theta) \end{align} \tag{5}

процесс формализации

В частности, нам нужно каждый раз для функции\log P(x;\theta)указать на\theta, найти вогнутую функциюg(\theta) \le \log P(x;\theta), каждый разg(\theta)Максимальный балл следующий\theta, итерируем до тех пор, пока не будет найдена целевая функцияlogP(x;\theta)достигает локального максимума.

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

EM

получить

Мы предполагаем, что каждыйz^{(i)}Функция распределенияQ_i,Так и есть\sum_ZQ_i(z)=1, Q_i(z) \ge0,имеют:

\begin{align} l(\theta) &= \sum_i\log\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta) \\ &= \sum_i \log \sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \\ &\ge \sum_i \sum_{z^{(i)}}Q_i(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \end{align} \tag{6}

мы знаем\logявляется вогнутой функцией, если положить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)})}, то приведенное выше неравенство можно получить из неравенства Йенсена (3).

С того времени,\thetaЛогарифмическая функция правдоподобияl(\theta)Существует нижняя граница, но мы хотим получить более точную нижнюю границу, что является случаем, когда соблюдается знак равенства.Тогда мы имеем:

\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} = c \quad(c为常数) \tag{7}

но:

Q_i(z^{(i)}) = c*p(x^{(i)},z^{(i)};\theta) \tag{8}

снова\sum_ZQ_i(z)=1, Q_i(z) \ge0,так:

\sum_ZQ_i(z^{(i)})= \sum_Z c*p(x^{(i)},z^{(i)};\theta)=1 \tag{9}

так:

c = \frac{1}{\sum_Z p(x^{(i)},z^{(i)};\theta)} \tag{10}

Тогда по формуле (8) имеем:

\begin{align} Q_i(z^{(i)}) &= \frac{p(x^{(i)},z^{(i)};\theta)}{\sum_Z p(x^{(i)},z^{(i)};\theta)}\\ & = \frac{p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)} \\ &= p(z^{(i)}| x^{(i)};\theta) \end{align} \tag{11}

Поток алгоритма

repeat

​(E step) for each i

Q_i(z^{(i)}) := p(z^{(i)}| x^{(i)};\theta)

​end for

​(M step)

\theta := arg\max_\theta\sum_i \sum_{z^{(i)}}Q_i(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}

untilФункция правдоподобия достигает своего максимального значения

использованная литература

[1] danerer-CSDN, Эндрю Нг Примечания к курсу машинного обучения (13) Алгоритм EM для неконтролируемого обучения [EB/OL], https://blog.csdn.net/danerer/article/details/80282612#expectation-maximization-algorithm , 2018-5-11/2018-7-30.

[2] Википедия, Неравенство Дженсена[DB/OL], https://en.wikipedia.org/wiki/Jensen%27s_inequality, 2018-06-06/2018-7-30.

Категории