Почему оптимизация смеси гауссов напрямую в вычислительном отношении трудна?

Рассмотрим логарифмическую вероятность смешения гауссиан:

Мне было интересно, почему в вычислительном отношении было трудно максимизировать это уравнение напрямую? Я искал либо ясную твердую интуицию о том, почему должно быть очевидно, что это сложно, либо, может быть, более строгое объяснение, почему это сложно. Эта проблема NP-полная или мы просто еще не знаем, как ее решить? Это причина, по которой мы прибегаем к использованию алгоритма EM ( ожидание-максимизация )?

Обозначения:

$S_n$ = тренировочные данные.

$x^{(t)}$ = точка данных.

$\theta$ = набор параметров, задающих гауссиан, их средние значения, стандартные отклонения и вероятность генерации точки из каждого кластера / класса / гаусса.

$p_i$ = вероятность генерации точки из кластера / класса / гауссова i.

Во-первых, GMM - это особый алгоритм кластеризации, где вы пытаетесь найти оптимальную маркировку ваших наблюдений. Имея k возможных классов, это означает, что есть k n возможных обозначений ваших тренировочных данных. Это становится уже огромным для умеренных значений k и n .$n$$k$$k^n$$k$$n$

Во-вторых, функционал, который вы пытаетесь минимизировать, не является выпуклым, и вместе с размером вашей проблемы делает его очень сложным. Я только знаю, что k-means (GMM можно рассматривать как мягкую версию kmeans) является NP-сложным. Но я не знаю, было ли это доказано и для GMM.

Чтобы увидеть, что проблема не является выпуклой, рассмотрим одномерный случай: и убедитесь, что вы не можете гарантировать, что d 2

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

В дополнение к пунктам Джуампы, позвольте мне сообщить о следующих трудностях:

• Функция не ограничена, поэтому истинный максимум + ∞ и соответствует ц ( я ) = х 1 (к примеру) и σ я = 0 . Поэтому истинный максимизатор должен заканчиваться этим решением, которое бесполезно для целей оценки.$l(\theta|S_n)$$+\infty$$\hat\mu^{(i)}=x_1$$\hat\sigma_i=0$
• $k^n$$l(\theta|S_n)$$\theta$

взято из моей книги .

Дополнительное замечание: без вызова EM-алгоритма можно использовать стандартный алгоритм оптимизации (например, Ньютона-Рафсона) по одному параметру за раз, то есть повторять

• $\theta_1^\prime=\arg\max_{\theta_1} l(\theta|S_n)$
• найти$\theta_2^\prime=\arg\max_{\theta_2} l(\theta_1^\prime,\theta_{-1}|S_n)$
• ...
• найти$\theta_v^\prime=\arg\max_{\theta_v} l(\theta_{-v}^\prime,\theta_v|S_n)$

если есть параметров и каждый шаг должен увеличивать значение целевой функции , но эта схема в лучшем случае окажется в том же режиме, что и EM-алгоритм.l ( θ | S n$v$$l(\theta|S_n)$