introduction

J'étudie actuellement le raisonnement bayésien. Cette fois, j'aimerais écrire ma compréhension de ** l'algorithme EM en distribution gaussienne mixte **.

Au fur et à mesure que je continue à étudier, je pense que ** des exemples simples sont bien, donc comprendre les formules et les mots progressera très rapidement en réfléchissant tout en les illustrant et en les incarnant **. Par conséquent, je voudrais rendre l'article facile à comprendre avec la mise en œuvre autant que possible.

J'ai beaucoup évoqué cet article cette fois. Il est très facile à comprendre du concept à la transformation et à l'implémentation de l'expression.

Explication approfondie de l'algorithme EM https://qiita.com/kenmatsu4/items/59ea3e5dfa3d4c161efb

Qu'est-ce que l'algorithme EM?

L'algorithme EM (Expectation Maximazation algorithm) est ** un algorithme utilisé pour entraîner et optimiser des modèles qui incluent des variables cachées **.

Coefficient de mélange

Pour expliquer les termes, approfondissez d'abord votre compréhension du coefficient de mélange.

Considérons le modèle de probabilité $ p (x) $ de $ x $ lorsque l'observation bidimensionnelle suivante $ x $ est obtenue. À ce stade, il semble qu'il soit généré à partir de deux clusters A et B, alors considérez un modèle qui reflète cela.

En supposant qu'il est déterminé par la distribution gaussienne, il peut être exprimé comme suit.

\begin{align}
p(x) &= \pi_A\mathcal N(x|\mu_A, \Sigma_A) +\pi_B\mathcal N(x|\mu_B, \Sigma_B)\\

\end{align}

cependant,

$ X $: $ D $ données dimensionnelles
$ \ mathcal {D} = {x_1, \ cdots, x_N} $: $ N $ points d'observation (ensemble de données)
$ Μ $: $ D $ Vecteur moyen dimensionnel
$ Σ $: $ D × D $ matrice de covariance
$ \ mathcal N (x | μ, Σ) $: $ D $ distribution gaussienne dimensionnelle

ça ira. La généralisation est la suivante.

\begin{align}
p(x) &= \sum_{k=1}^{K} \pi_k\mathcal N(x|\mu_k, \Sigma_k) \hspace{1cm}(Équation 1)

\end{align}

Ce $ π_k $ est appelé ** coefficient de mélange ** et satisfait ce qui suit.

\sum_{k=1}^{K} π_k =1\\

0 \leqq π_k \leqq 1

Cependant, $ K $: Nombre de clusters. En d'autres termes, le coefficient de mélange est une valeur numérique qui représente ** le poids dans chaque grappe (= quelle grappe a la plus grande probabilité d'existence) **.

Taux de charge

Ensuite, considérons le terme taux de charge. Soit $ π_k $ = $ p (k) $ la pré-probabilité de sélectionner le $ k $ ème cluster \mathcal N(x|\mu_k, \Sigma_k)=p(x|k)ÀkUne fois donnéxCompte tenu de la probabilité conditionnelle dexDensité périphérique de

p(x) = \sum_{k=1}^{K} p(k)p(x|k)\hspace{1cm}(Équation 2)\\

Cela peut être exprimé par. Cela équivaut à la formule 1 $ ci-dessus. À propos, $ p (k | x) $ à ce moment est appelé le taux de charge. Ce taux de charge est également exprimé comme $ γ_k (x) $, et en utilisant le théorème de Bayes,

\begin{align}
γ_k(x) &\equiv p(k|x)\\
&=\frac {p(k)p(x|k)}{\sum_lp(l)p(x|l)}\\
&=\frac {π_k\mathcal N(x|\mu_k, \Sigma_k)}{\sum_lπ_l\mathcal N(x|\mu_l, \Sigma_l)}

\end{align}

Peut être exprimé comme. Que signifie ce taux de charge? Je voudrais le confirmer lors de sa mise en œuvre.

Mettre en œuvre et vérifier

`EM.ipynb`


import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from scipy import stats as st
# ======================================
# Parameters
K = 4
n = 300
xx = np.linspace(-4, 10, n)

mu = [-1.2, 0.4, 2, 4]
sigma = [1.1, 0.7, 1.5, 2.0]
pi = [0.2, 0.3, 0.3, 0.2]

# Density function
pdfs = np.zeros((n, K))
for k in range(K):
    pdfs[:, k] = pi[k]*st.norm.pdf(xx, loc=mu[k], scale=sigma[k])

# =======================================
# Visualization
plt.figure(figsize=(14, 6))
for k in range(K):
    plt.plot(xx, pdfs[:, k])
plt.title("pdfs")
plt.show()

plt.figure(figsize=(14, 6))
plt.stackplot(xx, pdfs[:, 0], pdfs[:, 1], pdfs[:, 2], pdfs[:, 3])
plt.title("stacked")
plt.show()

Comme vous pouvez le voir dans la figure ci-dessus, le taux de charge est la valeur moyenne de la fonction de densité de la distribution gaussienne mixte pour un certain point $ x $, et est le rapport de $ k $ à chaque cluster.

Détour sur la distribution gaussienne (3 types de matrice de covariance)

Maintenant, en apprenant la distribution gaussienne, la matrice de covariance $ Σ $ peut être calculée comme $ Σ = σ ^ 2I $. Pour réfléchir à ce que cela signifie, résumons les trois types de matrices de covariance.

Matrice de covariance symétrique générale

Considérons une distribution gaussienne de dimension $ D $. À ce stade, la matrice de covariance $ Σ $ peut être exprimée comme suit.


\Sigma = \begin{pmatrix}
σ_{1}^2 & σ_{12} &・ ・ ・& σ_{1D}^2 \\
σ_{12} & σ_{2}^2\\
・\\
・\\
・\\
σ_{1D}& σ_{22} &・ ・ ・& σ_{D}^2\\
\end{pmatrix}\\

Une telle matrice de covariance est appelée un type symétrique général. Cette matrice de covariance a $ D × (D + 1) / 2 $ paramètres libres (compter les variables dans la matrice ci-dessus).

La matrice de covariance est diagonale

Ensuite, considérons le cas où la matrice de covariance est diagonale.

\Sigma =diag(σ_i^2)=\begin{pmatrix}
σ_{1}^2 & 0 &・ ・ ・& 0 \\
0 & σ_{2}^2\\
・\\
・\\
・\\
0& 0 &・ ・ ・& σ_{D}^2\\
\end{pmatrix}\\

Dans ce cas, le nombre de paramètres libres est $ D $, qui est égal au nombre de dimensions.

La matrice de covariance est proportionnelle à la matrice unitaire (isotrope)

Enfin, considérons le cas où la matrice de covariance est proportionnelle à la matrice unitaire. C'est ce qu'on appelle une matrice de covariance isotrope.

\Sigma =σ^2\bf I= σ^2\begin{pmatrix}
1 & 0 &・ ・ ・& 0 \\
0 & 1\\
・\\
・\\
・\\
0& 0 &・ ・ ・& 1\\
\end{pmatrix}\\

Dans un tel cas, il n'y a qu'un seul paramètre libre, $ σ $. Maintenant, les densités de probabilité pour ces trois cas sont indiquées ci-dessous.

En réduisant le nombre de paramètres libres, le calcul devient plus facile et la vitesse de calcul augmente. D'autre part, vous pouvez voir que le pouvoir expressif de la densité de probabilité diminue. Dans le cas de la symétrie générale, il peut également représenter des formes diagonales ou isotropes. 　 Il y a une idée pour le résoudre en introduisant ** des variables latentes et des variables non observées ** afin de réaliser à la fois un calcul rapide et assurer l'expressivité. Il est courant d'améliorer l'expressivité avec cette variable latente et de multiples distributions gaussiennes (= distributions gaussiennes mixtes).

Application de l'algorithme EM à une distribution gaussienne mixte

Maintenant, revenons au sujet principal. L'algorithme EM utilisé cette fois correspond à 3. ci-dessous.

Étant donné une matrice $ N × K $ $ \ bf Z $ avec la variable latente $ \ bf z ^ T $ comme vecteur de ligne, la fonction de vraisemblance logarithmique peut être exprimée comme:

\begin{align}
ln \hspace{1mm} p(\bf X| π,μ,Σ) &=\sum_{n=1}^{N}ln\Bigl\{ \sum_{k=1}^{K} \pi_k\mathcal N(x|\mu_k, \Sigma_k) \Bigr\}

\end{align}

Désormais, en maximisant cette ** fonction de vraisemblance de type log, il devient possible de prédire des données inconnues $ x $ avec une probabilité élevée **. En d'autres termes, cela signifie trouver la fonction la plus probable.

Cliquez ici pour le contenu détaillé de l'idée de vraisemblance, j'y ai fait référence en détail.

[Statistiques] Qu'est-ce que la vraisemblance? Expliquons graphiquement. https://qiita.com/kenmatsu4/items/b28d1b3b3d291d0cc698

Cependant, il est très difficile d'exécuter cette fonction de reprobabilité analytiquement ($ log-Σ $ est très difficile à résoudre). Par conséquent, considérons une méthode appelée ** algorithme EM **.

** L'algorithme EM en distribution gaussienne mixte ** est le suivant.

Étant donné un modèle gaussien mixte (ou défini par vous-même), l'objectif est d'ajuster les ** paramètres de moyenne, de variance et de coefficient de mélange ** de chaque élément pour maximiser la fonction de vraisemblance.

Je pensais que c'était similaire à la mise à jour des paramètres de poids dans un réseau neuronal. Le paramètre de poids est mis à jour en utilisant la pente de la fonction de perte pour trouver le paramètre de poids qui minimise la fonction de perte. À ce stade, il serait énorme de calculer le gradient (= différenciation) de la fonction de perte elle-même mathématiquement. Par conséquent, le gradient est calculé par un algorithme appelé méthode de propagation d'erreur inverse.

De même, dans le cas de l'algorithme EM, $ π, μ et Σ $ sont calculés et mis à jour respectivement. Ensuite, si la convergence est jugée et que les critères sont satisfaits, la fonction la plus probable est utilisée.

Mise à jour des paramètres

L'algorithme EM dans une distribution gaussienne mixte nécessite de mettre à jour le facteur de charge $ γ (z_ {nk}) $, le coefficient de mélange $ π_k $, la moyenne $ μ_k $ et la matrice de covariance $ Σ_k $. Il est nécessaire de différencier ce calcul et de le mettre à 0 et de le résoudre. Cet article est très détaillé sur la façon de le résoudre, je vous serais donc reconnaissant de bien vouloir y jeter un coup d'œil.

Explication approfondie de l'algorithme EM https://qiita.com/kenmatsu4/items/59ea3e5dfa3d4c161efb

En conséquence, chaque paramètre peut être exprimé comme:


γ(z_{nk}) =\frac {π_k\mathcal N(x_n|\mu_k, \Sigma_k)}{\sum_{l=1}^{K}π_l\mathcal N(x|\mu_l, \Sigma_l)}\\

π_k = \frac {N_k}{N}\\
μ_k = \frac {1}{N_k}\sum_{n=1}^{N}γ(z_{nk})\bf{ x_n}\\
\Sigma_k = \frac{1}{N_k}\sum_{n=1}^{N}γ(z_{nk})(\bf x_n -μ_k)(\bf x_n -μ_k)^T\\

Comme vous pouvez le voir, $ π, μ et Σ $ dépendent tous de $ γ (z_ {nk}) $. Aussi, lorsque vous essayez de trouver la fonction la plus probable dans une seule distribution gaussienne, c'est la valeur lorsque ce $ γ (z_ {nk}) $ devient 1. Ensuite, c'est facile à comprendre car chacun d'eux demande simplement la valeur moyenne et la covariance.

Essayez de mettre en œuvre

Le programme est stocké ici. https://github.com/Fumio-eisan/EM_20200509/upload

Les points sont la valeur moyenne et la ligne continue est la ligne de contour de la distribution de densité de probabilité. Vous pouvez voir qu'il est progressivement optimisé pour chaque cluster.

À la fin

Cette fois, nous avons résumé l'algorithme EM pour la distribution gaussienne mixte. J'ai pensé qu'il serait plus facile de comprendre en connaissant visuellement avant de comprendre mathématiquement.

Je suis faible dans l'expansion et la mise en œuvre des formules, alors je vais aller plus loin pour approfondir ma compréhension. Je voudrais également écrire un article sur les algorithmes EM courants.