¿Por qué es la optimización de una mezcla de Gaussianas directamente computacionalmente difícil?

Question

Considerar la probabilidad de registro de una mezcla de Gaussianas:

$$l(S_n; \theta) = \sum^n_{t=1}\log f(x^{(t)}|\theta) = \sum^n_{t=1}\log\left\{\sum^k_{i=1}p_i f(x^{(t)}|\mu^{(i)}, \sigma^2_i)\right\}$$

Me preguntaba por qué era computacionalmente difícil para maximizar la ecuación directamente? Yo estaba buscando un claro sólidos intuición sobre por qué debería ser obvio que es muy difícil o tal vez una más rigurosa explicación de por qué su disco duro. Es este problema NP-completo o no acabamos de no saber cómo resolverlo? Es esta la razón por la que recurrir al uso de la EM (expectation-maximization) algoritmo?

---

Notación:

$S_n$ = datos de entrenamiento.

$x^{(t)}$ = punto de datos.

$\theta$ = el conjunto de parámetros que especifican el Gaussiano, la suya medios, desviaciones estándar y la probabilidad de generar un punto de cada grupo/clase/Gauss.

$p_i$ = la probabilidad de generar un punto de clúster/clase/Gauss yo.

Answer 1

En primer lugar, GMM es un algoritmo particular para la agrupación, donde se intenta encontrar el óptimo etiquetado de los su $n$ observaciones. Habiendo $k$ clases posibles, significa que hay $k^n$ posible labellings de los datos de su entrenamiento. Esto se convierte ya enorme para los moderados valores de$k$$n$.

Segundo, la funcional que están tratando de minimizar no es convexa, y junto con el tamaño de su problema, hace muy difícil. Sólo sé que k-means (GMM puede ser visto como una versión suave de kmeans) es NP-duro. Pero yo no soy consciente de que si se ha demostrado por GMM así.

A ver que el problema no es convexa, considere el caso unidimensional: $$ L = \log \left(e^{-({x}/{\sigma_{1}})^2} + e^{-({x}/{\sigma_{2}})^2}\right) $$ y comprobar que no se puede garantizar que $\frac{d^2L}{dx^2} > 0$ para todo x.

Tener un no-convexo problema significa que usted puede quedar atrapado en mínimos locales. En general, no tienen el fuerte de las garantías que han de optimización convexa, y la búsqueda de una solución también es mucho más difícil.

Answer 2

En adición a juampa puntos, permítanme la señal de las dificultades:

• La función de $l(\theta|S_n)$ es ilimitado, por lo que el máximo real es de $+\infty$ y corresponde a $\hat\mu^{(i)}=x_1$ (por ejemplo) y $\hat\sigma_i=0$. Un verdadero maximizador por lo tanto debe terminar con esta solución, que no es útil para la estimación de los efectos.
• Incluso sin tener en cuenta el $k^n$ términos en la descomposición del producto y de la suma como una suma de productos en $l(\theta|S_n)$, la función a ser máximo en $\theta$ es altamente multi-modal (además de ser no-convexo) por lo tanto, un desafío para los métodos numéricos. EM reconoce la dificultad mediante la convergencia de un modo local o punto de silla y que requieren múltiples pistas. Como se muestra en

tomado de mi libro.

Una observación complementaria: sin llamar el algoritmo EM, se puede utilizar un estándar de optimización (algoritmo como el de Newton-Raphson) un parámetro a la vez, es decir, recorrer

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

si hay $v$ parámetros y cada paso debe aumentar el valor de la función de destino $l(\theta|S_n)$, pero este esquema a lo mejor terminan en el mismo modo que el algoritmo EM.