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

18

Considere la probabilidad logarítmica de una mezcla de gaussianos:

l (S_{norte}; θ) = \sum_{t = 1}^{norte} Iniciar sesión F (X^{(t)} El | θ) = \sum_{t = 1}^{norte} Iniciar sesión {\sum_{yo = 1}^{k} {pag}_{yo} F (X^{(t)} El | μ^{(yo)}, σ_{yo}^{2})}

$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 maximizar esa ecuación directamente. Estaba buscando una intuición clara y sólida sobre por qué debería ser obvio que es difícil o tal vez una explicación más rigurosa de por qué es difícil. ¿Es este problema NP-completo o simplemente no sabemos cómo resolverlo todavía? ¿Es esta la razón por la que recurrimos al algoritmo EM ( maximización de expectativas )?

Notación:

$S_n$ = datos de entrenamiento.

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

$\theta$ = el conjunto de parámetros que especifican el gaussiano, sus medias, desviaciones estándar y la probabilidad de generar un punto a partir de cada grupo / clase / gaussiano.

$p_i$ = la probabilidad de generar un punto a partir de clúster / clase / gaussiano i.

machine-learning gaussian-mixture expectation-maximization Pinocho
fuente

14

Primero, GMM es un algoritmo particular para la agrupación, donde intenta encontrar el etiquetado óptimo de sus observaciones. Tener clases posibles, significa que hay posibles presentaciones de sus datos de entrenamiento. Esto ya se vuelve enorme para valores moderados de y . $n$ $k$ $k^n$ $k$ $n$

En segundo lugar, el funcional que intenta minimizar no es convexo y, junto con el tamaño de su problema, lo hace muy difícil. Solo sé que k-means (GMM puede verse como una versión suave de kmeans) es NP-hard. Pero no sé si también se ha probado para GMM.

Para ver que el problema no es convexo, considere el caso unidimensional: y compruebe que no puede garantizar que

L = \log (e^{- (x / σ_{1})^{2}} + e^{- (x / σ_{2})^{2}})

$L = \log \left(e^{-({x}/{\sigma_{1}})^2} + e^{-({x}/{\sigma_{2}})^2}\right)$

para todas las x.

\frac{d^{2} L}{d x^{2}} > 0

$\frac{d^2L}{dx^2} > 0$

Tener un problema no convexo significa que puede quedarse atascado en los mínimos locales. En general, no tiene las fuertes garantías que tiene en la optimización convexa, y la búsqueda de una solución también es mucho más difícil.

jpmuc
fuente

3

Con respecto al segundo punto: k-means se puede ver como un caso especial de GMM (más precisamente, un caso límite donde las variaciones se llevan a cero). Si podemos reducir k-means al ajuste de un GMM, este último también debe ser un problema NP-difícil.

Lucas

1

@Lucas: Aquí hay un enlace de validación cruzada a su comentario.

Xi'an

7

Además de los puntos de juampa, permítanme señalar esas dificultades:

La función es ilimitada, por lo que el verdadero máximo es de y corresponde a (por ejemplo) y . Por lo tanto, un verdadero maximizador debería terminar con esta solución, que no es útil para fines de estimación. $l(\theta|S_n)$ $+\infty$ $\hat\mu^{(i)}=x_1$ $\hat\sigma_i=0$
$k^n$ $l(\theta|S_n)$ $\theta$

tomado de mi libro .

Una observación adicional: sin llamar al algoritmo EM, uno puede usar un algoritmo de optimización estándar (como Newton-Raphson) un parámetro a la vez, es decir, iterar

$\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)$

$v$ $l(\theta|S_n)$

Xi'an
fuente

OK, L no tiene límites si la varianza es 0. Pero si los excluimos de los posibles parámetros (por lo que suponemos que toda la varianza> 0), L no debería ser tan alta siempre que la varianza infinitesimal elegida (debido a otros puntos). Estoy en lo cierto? Entonces, para este posible conjunto de parámetros, L estaría acotado, y esto implicaría que el algoritmo EM converge (secuencia acotada creciente).

ahstat

@ahstat: asumir que las variaciones son estrictamente positivas no evita que EM converja a una solución degenerada si se inicia lo suficientemente cerca.

Xi'an

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

Respuestas: