Einführung

Ich studiere gerade Bayesianisches Denken. Dieses Mal möchte ich mein Verständnis des ** EM-Algorithmus in gemischter Gaußscher Verteilung ** schreiben.

Während ich weiter studiere, habe ich das Gefühl, dass ** einfache Beispiele in Ordnung sind, so dass das Verstehen von Formeln und Wörtern sehr schnell voranschreitet, wenn man denkt, während man sie illustriert und verkörpert **. Daher möchte ich den Artikel mit der Implementierung so leicht wie möglich verständlich machen.

Ich habe dieses Mal viel auf diesen Artikel verwiesen. Es ist vom Konzept bis zur Transformation und Implementierung des Ausdrucks sehr leicht zu verstehen.

Gründliche Erklärung des EM-Algorithmus https://qiita.com/kenmatsu4/items/59ea3e5dfa3d4c161efb

Was ist der EM-Algorithmus?

Der EM-Algorithmus (Expectation Maximazation-Algorithmus) ist ** ein Algorithmus zum Lernen und Optimieren von Modellen, die versteckte Variablen enthalten **.

Mischungskoeffizient

Vertiefen Sie zur Erklärung der Begriffe zunächst Ihr Verständnis des Mischungskoeffizienten.

Betrachten Sie das Wahrscheinlichkeitsmodell $ p (x) $ von $ x $, wenn die folgende zweidimensionale Beobachtung $ x $ erhalten wird. Derzeit scheint es, dass es aus zwei Clustern A und B generiert wird. Betrachten Sie also ein Modell, das dies widerspiegelt.

Unter der Annahme, dass es durch die Gaußsche Verteilung bestimmt wird, kann es wie folgt ausgedrückt werden.

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

\end{align}

Jedoch,

$ X $: $ D $ dimensionale Daten
$ \ mathcal {D} = {x_1, \ cdots, x_N} $: $ N $ Beobachtungspunkte (Datensatz)
$ Μ $: $ D $ Dimensional Mean Vector
$ Σ $: $ D × D $ Kovarianzmatrix
$ \ mathcal N (x | μ, Σ) $: $ D $ dimensionale Gaußsche Verteilung

Wird besorgt. Die Verallgemeinerung ist wie folgt.

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

\end{align}

Dieser $ π_k $ heißt ** Mischungskoeffizient ** und erfüllt die folgenden Anforderungen.

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

0 \leqq π_k \leqq 1

$ K $: Anzahl der Cluster. Mit anderen Worten, der Mischungskoeffizient ist ein numerischer Wert, der ** das Gewicht in jedem Cluster darstellt (= welcher Cluster die höchste Existenzwahrscheinlichkeit hat) **.

Belastungsrate

Betrachten Sie als nächstes den Begriff Belastungsrate. Sei $ π_k $ = $ p (k) $ die vorherige Wahrscheinlichkeit, den $ k $ -ten Cluster auszuwählen \mathcal N(x|\mu_k, \Sigma_k)=p(x|k)ZukWenn gegebenxAngesichts der bedingten Wahrscheinlichkeit vonxPeriphere Dichte von

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

Es kann ausgedrückt werden als. Dies entspricht der obigen Formel $ 1 $. Übrigens wird $ p (k | x) $ zu diesem Zeitpunkt als Belastungsrate bezeichnet. Diese Belastungsrate wird auch als $ γ_k (x) $ ausgedrückt und unter Verwendung des Bayes-Theorems

\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}

Kann ausgedrückt werden als. Was bedeutet diese Belastungsrate? Ich möchte es bei der Implementierung bestätigen.

Implementieren und überprüfen

`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()

Wie Sie in der obigen Abbildung sehen können, ist die Belastungsrate der Mittelwert der Dichtefunktion der gemischten Gaußschen Verteilung bei einem bestimmten Punkt $ x $ und das Verhältnis von $ k $ zu jedem Cluster.

Umweg über die Gaußsche Verteilung (3 Arten von Kovarianzmatrix)

Beim Lernen der Gaußschen Verteilung kann die Kovarianzmatrix $ Σ $ als $ Σ = σ ^ 2I $ berechnet werden. Um darüber nachzudenken, was dies bedeutet, lassen Sie uns die drei Arten von Kovarianzmatrizen zusammenfassen.

Allgemeine symmetrische Kovarianzmatrix

Betrachten Sie eine Gaußsche Verteilung der $ D $ -Dimension. Zu diesem Zeitpunkt kann die Kovarianzmatrix $ Σ $ wie folgt ausgedrückt werden.


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

Eine solche Kovarianzmatrix wird als allgemeiner symmetrischer Typ bezeichnet. Diese Kovarianzmatrix hat $ D × (D + 1) / 2 $ freie Parameter (zählen Sie die Variablen in der obigen Matrix).

Die Kovarianzmatrix ist diagonal

Betrachten Sie als nächstes den Fall, in dem die Kovarianzmatrix diagonal ist.

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

In diesem Fall beträgt die Anzahl der freien Parameter $ D $, was der Anzahl der Dimensionen entspricht.

Die Kovarianzmatrix ist proportional zur Einheitsmatrix (isotrop)

Betrachten Sie schließlich den Fall, in dem die Kovarianzmatrix proportional zur Einheitsmatrix ist. Dies wird als isotrope Kovarianzmatrix bezeichnet.

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

In einem solchen Fall gibt es nur einen freien Parameter, $ σ $. Die Wahrscheinlichkeitsdichten für diese drei Fälle sind nachstehend aufgeführt.

Durch Reduzieren der Anzahl freier Parameter wird die Berechnung einfacher und die Berechnungsgeschwindigkeit erhöht sich. Andererseits können Sie sehen, dass die Ausdruckskraft der Wahrscheinlichkeitsdichte abnimmt. Bei allgemeiner Symmetrie kann es auch diagonale oder isotrope Formen darstellen. 　 Es gibt eine Idee, dies durch die Einführung von ** latenten und nicht beobachteten Variablen ** zu lösen, um sowohl eine schnelle Berechnung als auch eine Sicherstellung der Ausdruckskraft zu erreichen. Es ist üblich, die Ausdruckskraft mit dieser latenten Variablen und mehreren Gaußschen Verteilungen (= gemischten Gaußschen Verteilungen) zu verbessern.

Anwendung des EM-Algorithmus auf die gemischte Gaußsche Verteilung

Kehren wir nun zum Hauptthema zurück. Der diesmal verwendete EM-Algorithmus entspricht 3. unten.

Unter der Annahme, dass die latente Variable $ \ bf z ^ T $ der Zeilenvektor $ N × K $ Matrix $ \ bf Z $ ist, kann die logarithmische Wahrscheinlichkeitsfunktion wie folgt ausgedrückt werden.

\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}

Durch Maximieren dieser ** log-ähnlichen Wahrscheinlichkeitsfunktion ist es möglich, unbekannte Daten $ x $ mit hoher Wahrscheinlichkeit ** vorherzusagen. Mit anderen Worten bedeutet es, die wahrscheinlichste Funktion zu finden.

Klicken Sie hier, um den detaillierten Inhalt der Wahrscheinlichkeitsidee anzuzeigen. Ich habe ausführlich darauf hingewiesen.

[Statistik] Was ist Wahrscheinlichkeit? Lassen Sie uns grafisch erklären. https://qiita.com/kenmatsu4/items/b28d1b3b3d291d0cc698

Es ist jedoch sehr schwierig, diese Funktion analytisch durchzuführen ($ log-Σ $ ist sehr schwer zu lösen). Betrachten Sie daher eine Methode namens ** EM-Algorithmus **.

** EM-Algorithmus in gemischter Gaußscher Verteilung ** ist wie folgt.

Bei einem gemischten Gaußschen Modell (oder selbst festlegen) besteht das Ziel darin, die Parameter ** Durchschnitt, Varianz und Mischungskoeffizient ** jedes Elements anzupassen, um die Wahrscheinlichkeitsfunktion zu maximieren.

Ich dachte, es wäre ähnlich wie beim Aktualisieren von Gewichtsparametern in einem neuronalen Netzwerk. Der Gewichtsparameter wird unter Verwendung der Steigung der Verlustfunktion aktualisiert, um den Gewichtsparameter zu finden, der die Verlustfunktion minimiert. Zu diesem Zeitpunkt wäre es enorm, den Gradienten (= Differenzierung) der Verlustfunktion selbst mathematisch zu berechnen. Daher wird der Gradient durch einen Algorithmus berechnet, der als inverse Fehlerausbreitungsmethode bezeichnet wird.

In ähnlicher Weise werden im Fall des EM-Algorithmus $ π, μ und Σ $ berechnet bzw. aktualisiert. Wenn dann die Konvergenz beurteilt wird und die Kriterien erfüllt sind, wird die wahrscheinlichste Funktion verwendet.

Parameteraktualisierung

Der EM-Algorithmus in einer gemischten Gaußschen Verteilung erfordert die Aktualisierung des Belastungsfaktors $ γ (z_ {nk}) $, des Mischungskoeffizienten $ π_k $, des Mittelwerts $ μ_k $ und der Kovarianzmatrix $ Σ_k $. Es ist notwendig, diese Berechnung zu differenzieren und auf 0 zu setzen und zu lösen. Dieser Artikel enthält sehr detaillierte Informationen zur Lösung. Ich wäre Ihnen dankbar, wenn Sie einen Blick darauf werfen könnten.

Gründliche Erklärung des EM-Algorithmus https://qiita.com/kenmatsu4/items/59ea3e5dfa3d4c161efb

Infolgedessen kann jeder Parameter ausgedrückt werden als:


γ(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\\

Wie Sie sehen können, hängen $ π, μ und Σ $ alle von $ γ (z_ {nk}) $ ab. Wenn Sie versuchen, die wahrscheinlichste Funktion in einer einzelnen Gaußschen Verteilung zu finden, ist dies der Wert, wenn dieses $ γ (z_ {nk}) $ 1 wird. Dann ist es leicht zu verstehen, weil jeder von ihnen einfach nach dem Durchschnittswert und der Kovarianz fragt.

Versuchen Sie zu implementieren

Das Programm ist hier gespeichert. https://github.com/Fumio-eisan/EM_20200509/upload

Die Punkte sind der Durchschnittswert und die durchgezogene Linie ist die Konturlinie der Wahrscheinlichkeitsdichteverteilung. Sie können sehen, dass es schrittweise für jeden Cluster optimiert wird.

Am Ende

Dieses Mal haben wir den EM-Algorithmus für die gemischte Gaußsche Verteilung zusammengefasst. Ich dachte, es wäre einfacher zu verstehen, wenn man es visuell kennt, bevor man es mathematisch versteht.

Ich bin schwach in der Erweiterung und Implementierung von Formeln, daher werde ich meine Hände weiter bewegen, um mein Verständnis zu vertiefen. Ich möchte auch einen Artikel über gängige EM-Algorithmen schreiben.