EM-Algorithmus

Der Erwartungs-Maximierungs-Algorithmus (englisch expectation-maximization algorithm, daher auch Expectation-Maximization-Algorithmus, selten auch Estimation-Maximization-Algorithmus, kurz EM-Algorithmus) ist ein Algorithmus der mathematischen Statistik.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 (Erwartungsschritt, kurz: E-Schritt) und die Parameter des Modells an die neueste Zuordnung (Maximierungsschritt, 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.