Hauptmenü öffnen

EM-Algorithmus

Algorithmus der mathematischen Statistik

Der Expectation-Maximization-Algorithmus, kurz EM-Algorithmus, selten auch Estimation-Maximization-Algorithmus (deutsch Erwartungs-Maximierungs-Algorithmus) ist ein Algorithmus der mathematischen Statistik.

EM-Clustering für Old-Faithful-Eruptionsdaten. Das zufällige Modell (durch die Skalierung der Achsen erscheinen die Sphären flach und breit) wird an die beobachteten Daten angepasst. Gut erkennbar sind die zwei typischen Modi des Geysirs. In den ersten Iterationen ändert sich das Modell noch stark, anschließend werden die Änderungen kleiner und nähern sich einem Grenzwert an. Visualisierung erzeugt mit ELKI.

Die Kernidee des EM-Algorithmus ist es, mit einem zufällig gewählten Modell zu starten, und abwechselnd die Zuordnung der Daten zu den einzelnen Teilen des Modells (Expectation-Schritt, kurz E-Schritt) und die Parameter des Modells an die neueste Zuordnung (Maximization-Schritt, kurz M-Schritt) zu verbessern.

In beiden Schritten wird dabei die Qualität des Ergebnisses verbessert: Im E-Schritt werden die Punkte besser zugeordnet, im M-Schritt wird das Modell so verändert, dass es besser zu den Daten passt. Findet keine wesentliche Verbesserung mehr statt, beendet man das Verfahren.

Das Verfahren findet typischerweise nur „lokale“ Optima. Dadurch ist es oft notwendig, das Verfahren mehrfach aufzurufen und das beste so gefundene Ergebnis auszuwählen.

Inhaltsverzeichnis

Mathematische FormulierungBearbeiten

FunktionsweiseBearbeiten

Es liegen Objekte mit einer gewissen Anzahl von Eigenschaften vor. Die Eigenschaften nehmen zufällige Werte an. Einige Eigenschaften können gemessen werden, andere jedoch nicht. Formal gesehen sind die Objekte Instanzen einer mehrdimensionalen Zufallsvariablen  , die einer unbekannten Wahrscheinlichkeitsverteilung   unterliegt; einige Dimensionen sind „beobachtbar“, andere sind „versteckt“. Ziel ist es, die unbekannte Wahrscheinlichkeitsverteilung zu bestimmen.

Zunächst nimmt man an,   sei bis auf einige Parameter bekannt. Meist wählt man   als Mischverteilung, also als gewichtete Summe von so vielen Standardverteilungen, wie beobachtbare Eigenschaften vorliegen. Wählt man beispielsweise als Standardverteilung die Normalverteilung, so sind die unbekannten Parameter jeweils der Erwartungswert   und die Varianz  . Ziel ist es nun, die Parameter   der vermuteten Wahrscheinlichkeitsverteilung zu bestimmen. Wählt man eine Mischverteilung, so enthält   auch die Gewichtungsfaktoren der Summe.

Für gewöhnlich geht man ein solches Problem mit der Maximum-Likelihood-Methode an. Dies ist hier jedoch nicht möglich, da die gesuchten Parameter von den versteckten Eigenschaften abhängen – und diese sind unbekannt. Um trotzdem zum Ziel zu kommen, wird also eine Methode benötigt, die mit den gesuchten Endparametern die versteckten Eigenschaften schätzt. Diese Aufgabe erfüllt der EM-Algorithmus.

Der EM-Algorithmus arbeitet iterativ und führt in jedem Durchgang zwei Schritte aus:

  1. E-Schritt: Versteckte Eigenschaften   schätzen. Zunächst werden die versteckten Eigenschaften aus den im vorherigen Durchgang bestimmten Endparametern   und den beobachteten Daten   geschätzt. Dazu wird die sogenannte Q-Funktion verwendet, die einen vorläufigen Erwartungswert der gesuchten Verteilung berechnet.
  2. M-Schritt: Endparameter   bestimmen. Jetzt, wo die versteckten Eigenschaften abgeschätzt sind, wird die Maximum-Likelihood-Methode angewandt, um die eigentlich gesuchten Parameter zu bestimmen.

Der Algorithmus endet, wenn sich die bestimmten Parameter nicht mehr wesentlich ändern.

Bewiesenermaßen konvergiert die Folge der bestimmten  , das heißt, der Algorithmus terminiert auf jeden Fall. Allerdings bildet das Ergebnis meist nur ein lokales Optimum, welches zwar gut, aber nicht unbedingt optimal ist. Es ist daher nötig den Algorithmus viele Male mit unterschiedlichen Startwerten zu wiederholen, um ein möglichst optimales Endergebnis zu finden.

Formulierung als ZufallsexperimentBearbeiten

Rein formal wird beim EM-Algorithmus angenommen, dass die Werte der beobachteten stochastischen Größe auf folgende Art und Weise zustande kommen: Wähle zuerst eine der eingehenden Zufallsvariablen aus und übernimm deren Wert als Endergebnis. Das bedeutet, dass genau ein Gewicht den Wert eins annimmt und alle anderen null sind. Bei der Approximation der Gewichte durch den EM-Algorithmus ist dies normalerweise aber nicht mehr der Fall. Die Wahrscheinlichkeitsdichte eines Zielwertes lässt sich bei Normalverteilungsannahme und konstanter Varianz der einzelnen Zufallsvariablen darstellen als:  

Dabei besitzen die verwendeten Bezeichnungen folgende Bedeutungen:

  •  : Gewicht der  -ten Zufallsvariable für den  -ten Wert der Zielgröße
  •  : Anzahl der Gewichte
  •  : Wert der  -ten Zielgröße
  •  : Stichprobe
  •  : Erwartungswert der  -ten Zufallsvariable
  •  : Varianz

EM-ClusteringBearbeiten

Das EM-Clustering ist ein Verfahren zur Clusteranalyse, das die Daten mit einem „Mixture of Gaussians“-Modell – also als Überlagerung von Normalverteilungen – repräsentiert. Dieses Modell wird zufällig oder heuristisch initialisiert und anschließend mit dem allgemeinen EM-Prinzip verfeinert.

Das EM-Clustering besteht aus mehreren Iterationen der Schritte Expectation und Maximization.

  • Im Initialisierungs-Schritt muss das   frei gewählt werden. Nimm dazu an, dass genau eine beliebige Zufallsvariable (genau eine beliebige Trainingsinstanz  ) diesem Erwartungswert   entspricht, d. h. setze  .
  • Im Expectation-Schritt werden die Erwartungswerte der Gewichte berechnet unter der Annahme, dass die Erwartungswerte der eingehenden Zufallsvariablen den im Maximization-Schritt berechneten entsprechen. Dies ist allerdings nur möglich, falls es sich nicht um die erste Iteration handelt.
    Die Erwartungswerte lassen sich darstellen als  
  • Im Maximization-Schritt werden die Erwartungswerte der Wahrscheinlichkeitsverteilungen der einzelnen Zufallsvariablen bestimmt, bei denen die Wahrscheinlichkeit für das Eintreffen des Stichprobenergebnisses maximiert wird. Dies geschieht unter der Annahme, dass die exakten Werte der Gewichte jeweils ihren Erwartungswerten entsprechen (Maximum-Likelihood-Algorithmus). Die auf diese Weise geschätzten Erwartungswerte ergeben sich bei Normalverteilungsannahme durch  
wobei   die Größe des Trainingsdatensatzes bezeichnet.
  • Durch Wiederholung der Expectation- und Maximization-Schritte werden die Parameter ihren tatsächlichen Werten weiter angenähert.

Vorteile des EM-ClusteringsBearbeiten

 
Vergleich k-Means und EM auf einem künstlichen Datensatz, visualisiert mit ELKI. Durch Verwendung von Varianzen kann EM die unterschiedlichen Normalverteilungen akkurat beschreiben, während k-Means die Daten in ungünstige Voronoi-Zellen aufteilt. Die Clusterzentren sind durch größere, blassere Symbole gekennzeichnet.
  • Mathematisches Modell der Daten mit Normalverteilungen
  • Erlaubt Cluster unterschiedlicher Größe (im Sinne von Streuung – k-means ignoriert die Varianz der Cluster).
  • Kann korrelierte Cluster erkennen und repräsentieren durch die Kovarianzmatrix
  • Kann mit unvollständigen Beobachtungen umgehen

K-Means als EM-VerfahrenBearbeiten

Auch der k-Means-Algorithmus kann als EM-Algorithmus verstanden werden, der die Daten als Voronoi-Zellen modelliert.

Eine EM-Variante des k-Means-Algorithmus sieht wie folgt aus:

  • Im Initialisierungs-Schritt werden die Clusterzentren   zufällig oder mit einer Heuristik gewählt.
  • Im Expectation-Schritt werden Datenobjekte ihrem nächsten Clusterzentrum zugeordnet, d. h.  
  • Im Maximization-Schritt werden die Clusterzentren neu berechnet als Mittelwert der ihnen zugeordneten Datenpunkte:
     

Weitere Instanzen des EM-AlgorithmusBearbeiten

Beweis für den Maximization-Schritt bei NormalverteilungsannahmeBearbeiten

Bewiesen werden soll:  

Anstatt   zu maximieren, kann auch   maximiert werden, da der Logarithmus eine streng monoton steigende Funktion ist.

   
 

Der Minuend ist eine Konstante, deswegen ist es ausreichend, den Subtrahend zu minimieren:

   

Eine quadratische Summe ergibt stets einen nichtnegativen Wert. Daher ist das absolute Minimum durch 0 beschränkt und somit auch ein lokales Minimum. Man setze die 1. Ableitung für diesen Term   nach jedem   auf 0:

 ,

denn die Ableitung aller Summanden der Summe über j sind 0, außer für j=k. Folglich:

 

q. e. d.

LiteraturBearbeiten