Pourquoi l'optimisation d'un mélange de gaussien directement est-elle difficile à calculer?

18

Considérez la probabilité logarithmique d'un mélange de gaussiens:

l (S_{n}; θ) = \sum_{t = 1}^{n} \log f (x^{(t)} | θ) = \sum_{t = 1}^{n} \log {\sum_{i = 1}^{k} p_{i} f (x^{(t)} | μ^{(i)}, σ_{i}^{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\}$

Je me demandais pourquoi il était difficile de calculer directement cette équation? Je cherchais soit une claire intuition solide sur pourquoi il devrait être évident que c'est difficile, soit peut-être une explication plus rigoureuse de la raison pour laquelle c'est dur. Ce problème est-il NP-complet ou ne savons-nous pas encore comment le résoudre? Est-ce la raison pour laquelle nous avons recours à l' algorithme EM ( expectation-maximization )?

Notation:

$S_n$ = données d'entraînement.

$x^{(t)}$ = point de données.

$\theta$ = l'ensemble des paramètres spécifiant le gaussien, leurs moyennes, les écarts-types et la probabilité de générer un point à partir de chaque cluster / classe / gaussien.

$p_i$ = la probabilité de générer un point à partir d'un cluster / classe / gaussien i.

machine-learning gaussian-mixture expectation-maximization Pinocchio
la source

14

$n$ $k$ $k^n$ $k$ $n$

Deuxièmement, la fonctionnalité que vous essayez de minimiser n'est pas convexe et, avec la taille de votre problème, la rend très difficile. Je sais seulement que k-means (GMM peut être vu comme une version douce de kmeans) est NP-difficile. Mais je ne sais pas si cela a également été prouvé pour GMM.

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

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

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

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

Avoir un problème non convexe signifie que vous pouvez rester coincé dans les minima locaux. En général, vous n'avez pas les garanties solides que vous avez dans l'optimisation convexe, et la recherche d'une solution est également beaucoup plus difficile.

jpmuc
la source

3

Concernant le deuxième point: les k-moyennes peuvent être considérées comme un cas particulier des GMM (plus précisément, un cas limite où les variances sont ramenées à zéro). Si nous pouvons réduire les k-moyennes à l'ajustement d'un GMM, celui-ci doit également être un problème NP-difficile.

Lucas

1

@Lucas: Voici un lien Cross Validated vers votre remarque.

Xi'an

7

En plus des points de juampa, permettez-moi de signaler ces difficultés:

$l(\theta|S_n)$ $+\infty$ $\hat\mu^{(i)}=x_1$ $\hat\sigma_i=0$
$k^n$ $l(\theta|S_n)$ $\theta$

tiré de mon livre .

Une remarque supplémentaire: sans appeler l'algorithme EM, on peut utiliser un algorithme d'optimisation standard (comme Newton-Raphson) un paramètre à la fois, c'est-à-dire, itérer

$\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
la source

OK, L est illimité si la variance est 0. Mais si nous les excluons des paramètres possibles (donc nous supposons que toute variance> 0), alors L ne devrait pas être si élevé chaque fois que la variance infinitésimale choisie (à cause d'autres points). Ai-je raison? Ensuite, pour cet ensemble possible de paramètres, L serait borné, ce qui impliquerait que l'algorithme EM converge (augmentation de la séquence bornée).

ahstat

@ahstat: supposer que les variances sont strictement positives n'empêche pas EM de converger vers une solution dégénérée s'il est démarré suffisamment près.

Xi'an

Pourquoi l'optimisation d'un mélange de gaussien directement est-elle difficile à calculer?

Réponses: