Почему используется алгоритм максимизации ожидания?

22

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

expectation-maximization user782220
источник

20

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

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

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

гораздо более интенсивный в вычислительном отношении
менее надежный

Очень распространенное применение метода EM - подбор модели смеси. В этом случае, рассматривая переменную, которая присваивает каждую выборку одному из компонентов в качестве «скрытых» переменных, проблема значительно упрощается.

Давайте посмотрим на пример. У нас есть N выборок извлеченных из смеси 2 нормальных распределений. Чтобы найти параметры без ЭМ, мы должны минимизировать: $s = \{s_i\}$

- журнал L (Икс, θ) знак равно - журнал [a_{1} ехр (\frac{(Икс - μ_{1})^{2}}{2 σ_{1}^{2}}) + a_{2} ехр (\frac{(Икс - μ_{2})^{2}}{2 σ_{2}^{2}})]

$-\log \mathcal{L}(x,\theta) = -\log\Big[ a_1 \exp\Big( \frac{(x-\mu_1)^2}{2\sigma_1^2}\Big) + a_2 \exp\Big(\frac{(x-\mu_2)^2}{2\sigma_2^2}\Big) \Big]$

Напротив, используя EM-алгоритм, мы сначала «назначаем» каждую выборку компоненту ( шаг E ), а затем подбираем (или максимизируем вероятность ) каждый компонент отдельно ( шаг M ). В этом примере M-шаг - это просто взвешенное среднее значение для поиска и . Повторение этих двух шагов является более простым и надежным способом минимизации . $\mu_k$ $\sigma_k$ $-\log \mathcal{L}(x,\theta)$

user2304916
источник

12

EM не требуется вместо использования некоторой численной техники, потому что EM также является численным методом. Так что это не замена Ньютон-Рафсон. EM для конкретного случая, когда у вас отсутствуют значения в матрице данных. Рассмотрим образец который имеет условную плотность . Тогда логарифмическая вероятность этого равна Теперь предположим, что у вас нет полного набора данных, так что состоит из наблюдаемых данных. и отсутствующие (или скрытые) переменные , такие что . Тогда логарифмическая вероятность для наблюдаемых данных $X = (X_{1},...,X_{n})$ $f_{X|\Theta}(x|\theta)$

L (θ; Икс) знак равно L о г е_{Икс | Θ} (Икс | θ)

$l(\theta;X) = log f_{X|\Theta}(X|\theta)$

X

$X$

Y

$Y$

Z

$Z$

X = (Y, Z)

$X=(Y,Z)$

L_{о б s} (θ, Y) знак равно L о г \int е_{Икс | Θ} (Y, Z | θ) ν_{Z} (d Z)

$l_{obs}(\theta,Y)=log \int f_{X|\Theta}(Y,z|\theta)\nu_{z}(dz)$ В общем случае вы не можете вычислить этот интеграл напрямую и не получите решение в замкнутой форме для . Для этого вы используете метод EM. Есть два шага, которые повторяются для раз. На этом шаге это шаг ожидания, на котором вы вычисляете где - оценка на шаге . Затем вычислите шаг максимизации, на котором вы максимизируете относительно и установить

l_{o b s} (θ, Y)

$l_{obs}(\theta,Y)$

i

$i$

(i + 1)^{t h}

$(i + 1)^{th}$

Q (θ | θ^{(я)}) знак равно Е_{θ^{(я)}} [L (θ; Икс | Y]

$Q(\theta|\theta^{(i)}) = E_{\theta^{(i)}}[l(\theta;X|Y]$

θ^{(i)}

$\theta^{(i)}$

Θ

$\Theta$

i^{t h}

$i^{th}$

Q (θ | θ^{(i)})

$Q(\theta|\theta^{(i)})$

θ

$\theta$

θ^{(i + 1)} = m a x Q (θ | θ^{i})

$\theta^{(i+1)} = max Q(\theta|\theta^{i})$ . Затем вы повторяете эти шаги, пока метод не приблизится к некоторому значению, которое будет вашей оценкой.

Если вам нужна дополнительная информация о методе, его свойствах, доказательствах или приложениях, просто взгляните на соответствующую статью в вики .

Энди
источник

1

+1 ... EM не только для случая пропущенных значений.

Glen_b

@ Энди: Даже учитывая случай пропущенных данных, я все еще не понимаю, почему использование общих численных методов для нахождения точки, где частные производные равны нулю, не работает.

user782220

Спасибо Глен, я знал это только в контексте пропущенных значений / скрытых переменных. @ user782220: если вы не можете иметь решение в виде закрытой формы производной логарифмического правдоподобия, установка производной равной нулю не будет определять ваш параметр. Вот почему вы используете численные методы в этом случае. Объяснение и пример см. В лекции здесь: people.stat.sfu.ca/~raltman/stat402/402L5.pdf

Энди

1

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

TheGrimmScientist
источник

Почему используется алгоритм максимизации ожидания?

Ответы: