Erwartungsmaximierung in CS6601: Schritt-für-Schritt-Anleitung für Assignment 5

Einführung in die Erwartungsmaximierung (EM)

Die Erwartungsmaximierung (Expectation Maximization, EM) ist ein leistungsstarkes Verfahren zur Schätzung von Parametern in probabilistischen Modellen mit latenten Variablen. In CS6601 Assignment 5 wirst du den EM-Algorithmus implementieren, um Gaussian Mixture Models (GMM) zu trainieren und Clusteranalysen durchzuführen. Der EM-Algorithmus findet Anwendung in vielen Bereichen, von der Bildsegmentierung bis zur Anomalieerkennung in Finanzdaten – ähnlich wie Algorithmen in modernen Apps wie Spotify oder Netflix verwendet werden, um Nutzer in Gruppen einzuteilen.

Dieses Tutorial führt dich durch die Kernkonzepte von EM, die du für die Aufgaben in Assignment 5 benötigst: k-Means-Clustering, Gaussian Mixture Models, Modellverbesserungen und Bayesian Information Criterion (BIC). Wir verzichten darauf, die konkreten Programmieraufgaben zu lösen, aber du erhältst das nötige Verständnis, um sie eigenständig umzusetzen.

1. k-Means-Clustering: Der erste Schritt

k-Means ist ein einfacher, aber effektiver Clusteralgorithmus, der als Grundlage für EM dient. In Assignment 5 wirst du k-Means implementieren, um initiale Clusterzentren für das GMM zu finden. Der Algorithmus funktioniert iterativ:

1. Wähle k zufällige Datenpunkte als anfängliche Clusterzentren.
2. Weise jeden Datenpunkt dem nächstgelegenen Zentrum zu (Erwartungsschritt).
3. Aktualisiere die Zentren als Mittelwert aller zugewiesenen Punkte (Maximierungsschritt).
4. Wiederhole, bis Konvergenz eintritt.

Ein häufiges Problem bei k-Means ist die Abhängigkeit von der Initialisierung. Verwende daher den k-Means++-Ansatz, um bessere Startzentren zu wählen. In deiner Implementierung solltest du die Vektorisierung nutzen, um die Distanzberechnungen effizient zu gestalten – verwende numpy und vermeide langsame Schleifen.

import numpy as np
def k_means(X, k, max_iters=100):
    # Initialisierung mit k-Means++
    centers = [X[np.random.choice(len(X))]]
    for _ in range(k-1):
        dists = np.min([np.linalg.norm(X - c, axis=1) for c in centers], axis=0)
        probs = dists**2 / np.sum(dists**2)
        centers.append(X[np.random.choice(len(X), p=probs)])
    centers = np.array(centers)
    for _ in range(max_iters):
        # Erwartungsschritt: Zuordnung
        labels = np.argmin(np.linalg.norm(X[:, None] - centers[None], axis=2), axis=1)
        # Maximierungsschritt: Zentren aktualisieren
        new_centers = np.array([X[labels == i].mean(axis=0) for i in range(k)])
        if np.allclose(centers, new_centers):
            break
        centers = new_centers
    return centers, labels

Achte darauf, dass die Tests in mixture_tests.py die Korrektheit deiner Implementierung prüfen. Nutze die lokalen Tests im Jupyter Notebook, um sicherzustellen, dass alles funktioniert.

2. Gaussian Mixture Model (GMM): Der EM-Algorithmus

Ein GMM modelliert die Daten als gewichtete Summe mehrerer Gaußscher Verteilungen. Der EM-Algorithmus schätzt die Parameter (Mittelwerte, Kovarianzen und Mischungskoeffizienten) iterativ. In Assignment 5 ist dies der größte Teil (48 Punkte).

Der EM-Algorithmus für GMM besteht aus zwei Schritten:

• E-Schritt (Erwartung): Berechne die Verantwortlichkeiten (posterior probabilities) für jeden Datenpunkt und jede Komponente.
• M-Schritt (Maximierung): Aktualisiere die Parameter basierend auf den Verantwortlichkeiten.

Eine effiziente Implementierung erfordert Vektorisierung. Verwende numpy.einsum oder Broadcasting, um die Berechnungen zu beschleunigen. Beachte die numerische Stabilität: Füge einen kleinen Wert zu den Kovarianzen hinzu, um Singularitäten zu vermeiden.

def e_step(X, means, covs, weights):
    n_components = len(weights)
    n_samples = len(X)
    resp = np.zeros((n_samples, n_components))
    for k in range(n_components):
        diff = X - means[k]
        # Multivariate Normalverteilung (vektorisiert)
        inv_cov = np.linalg.inv(covs[k])
        exponent = -0.5 * np.sum(diff @ inv_cov * diff, axis=1)
        const = 1 / np.sqrt((2*np.pi)**X.shape[1] * np.linalg.det(covs[k]))
        resp[:, k] = weights[k] * const * np.exp(exponent)
    resp /= resp.sum(axis=1, keepdims=True)
    return resp

Beachte, dass die Nutzung von Schleifen über Komponenten in Ordnung ist, aber vermeide Schleifen über Datenpunkte. In der Praxis solltest du die Berechnung weiter vektorisieren, z.B. mit scipy.stats.multivariate_normal oder durch Matrixoperationen.

3. Modellverbesserungen: Initialisierung und Regularisierung

Der EM-Algorithmus konvergiert oft zu einem lokalen Optimum. Daher ist eine gute Initialisierung entscheidend. In Assignment 5 wirst du verschiedene Methoden vergleichen:

• Zufällige Initialisierung
• k-Means-basierte Initialisierung
• Verwendung der wahren Labels (falls bekannt)

Zusätzlich solltest du Regularisierungstechniken anwenden, um übermäßig spezifische Kovarianzmatrizen zu vermeiden. Ein gängiger Ansatz ist das Hinzufügen eines kleinen Wertes (z.B. 1e-6) zur Diagonalen der Kovarianzmatrix. Dies verhindert numerische Instabilität und verbessert die Generalisierung.

In der Aufgabenstellung wirst du auch aufgefordert, die Log-Likelihood zu überwachen, um die Konvergenz zu beurteilen. Ein Anstieg der Log-Likelihood zeigt an, dass der Algorithmus fortschreitet.

4. Bayesian Information Criterion (BIC) zur Modellauswahl

Das BIC hilft dir, die optimale Anzahl von Komponenten (k) für das GMM zu wählen. Es bestraft komplexe Modelle und balanciert Anpassungsgüte und Modellkomplexität. Die Formel lautet:

BIC = -2 * log_likelihood + k * log(n) * d

wobei k die Anzahl der Parameter ist, n die Anzahl der Datenpunkte und d die Dimension. In Assignment 5 wirst du das BIC für verschiedene k berechnen und das Modell mit dem niedrigsten BIC auswählen. Dies ist ein typischer Ansatz in der Praxis, z.B. bei der Bestimmung der Anzahl von Nutzersegmenten in Marketingdaten.

Implementiere die BIC-Berechnung effizient, indem du die bereits berechnete Log-Likelihood verwendest. Achte darauf, die Anzahl der Parameter korrekt zu zählen: Für ein GMM mit k Komponenten in d Dimensionen gibt es k*d Mittelwerte, k*d*(d+1)/2 Kovarianzparameter (bei voller Kovarianz) und k-1 Mischungskoeffizienten.

5. Effiziente Implementierung und Testdurchlauf

Die Tests auf Gradescope haben ein Zeitlimit von 40 Minuten. Daher ist Vektorisierung entscheidend. Nutze numpy-Funktionen wie np.linalg.solve anstelle von np.linalg.inv für bessere numerische Stabilität und Geschwindigkeit. Verwende np.einsum für komplexe Matrixoperationen.

Ein weiterer Tipp: Speichere Zwischenergebnisse, um redundante Berechnungen zu vermeiden. Zum Beispiel kannst du die Determinante und Inverse der Kovarianzmatrix einmal pro Iteration berechnen und dann für alle Datenpunkte wiederverwenden.

Führe die Tests lokal im Jupyter Notebook aus, bevor du auf Gradescope einreichst. Die Tests sind in mixture_tests.py definiert und werden automatisch ausgeführt. Stelle sicher, dass alle Tests bestehen und die Laufzeit akzeptabel ist.

6. Häufige Fehler und Debugging-Tipps

• Numerische Instabilität: Füge Regularisierung zu Kovarianzen hinzu.
• Falsche Initialisierung: Verwende k-Means++ oder mehrere Restarts.
• Langsame Ausführung: Vermeide Python-Schleifen über Datenpunkte; nutze Broadcasting.
• Falsche Log-Likelihood: Überprüfe die Berechnung der multivariaten Normalverteilung.

Nutze die bereitgestellten Ressourcen wie das gaussians.pdf und das em.pdf im read/-Ordner. Das Video von Alexander Ihler auf YouTube erklärt den EM-Algorithmus detailliert.

Fazit

Der EM-Algorithmus ist ein zentrales Werkzeug im maschinellen Lernen. Mit diesem Tutorial hast du die Grundlagen für Assignment 5 in CS6601 verstanden. Implementiere die Schritte sorgfältig, achte auf Vektorisierung und teste frühzeitig. Viel Erfolg bei deiner Abgabe!