Pattern Recognition - Exam

Aufgabe 1)

Angenommen, Du hast einen Datensatz mit n Beobachtungen und p Ursprungsmerkmalen. Du sollst Principal Component Analysis (PCA) anwenden, um die Dimensionen zu reduzieren. Im Rahmen der PCA ermöglichst Du die Projektion der Daten auf einen Raum mit k Dimensionen, wobei k < p ist. Dabei soll sichergestellt werden, dass die projizierten Daten die größte Varianz aufweisen.

Gegeben sei der Datensatz:

'X = [[2.5, 2.4], [0.5, 0.7], [2.2, 2.9], [1.9, 2.2], [3.1, 3.0], [2.3, 2.7], [2, 1.6], [1, 1.1], [1.5, 1.6], [1.1, 0.9]]'

a)

a) Führe die PCA auf den gegebenen Datensatz durch. Gehe dabei die folgenden Schritte durch:

• Zentriere die Daten, indem Du den Mittelwert für jedes Merkmal abziehst.
• Berechne die Kovarianzmatrix der zentrierten Daten.
• Bestimme die Eigenvektoren und Eigenwerte der Kovarianzmatrix.
• Projiziere die Daten auf die ersten k Hauptkomponenten (wähle k = 1).

Zeige alle Berechnungen und Zwischenergebnisse.

Lösung:

Um die PCA auf den gegebenen Datensatz anzuwenden, werde ich die angeforderten Schritte Schritt für Schritt durchgehen.

b)

b) Interpretiere die Ergebnisse der PCA. Beantworte dabei folgende Fragen:

• Was repräsentieren die Hauptkomponenten in diesem Datensatz?
• Wie viel Prozent der Gesamtvarianz der Originaldaten wird durch die ersten k Hauptkomponenten erklärt?
• Warum ist es wichtig, die Daten zu zentrieren, bevor die Kovarianzmatrix berechnet wird?

Lösung:

Interpretation der Ergebnisse der PCA

• Was repräsentieren die Hauptkomponenten in diesem Datensatz?

Die Hauptkomponenten (Principal Components) in diesem Datensatz repräsentieren die neuen, orthogonalen Achsen, auf die die Daten projiziert werden. Diese Achsen sind so gewählt, dass die Varianz der auf sie projizierten Daten maximiert wird. Die erste Hauptkomponente trägt die meiste Varianz der Daten, die zweite Hauptkomponente die zweitmeiste, und so weiter. In einem zweidimensionalen Raum, wie in unserem Datensatz, bedeutet das, dass die erste Hauptkomponente die Richtung ist, in der die Daten die größte Varianz aufweisen.

• Wie viel Prozent der Gesamtvarianz der Originaldaten wird durch die ersten k Hauptkomponenten erklärt?

Um diese Frage zu beantworten, muss man die Eigenwerte der Kovarianzmatrix betrachten. Die Eigenwerte repräsentieren die Varianz, die durch die jeweiligen Hauptkomponenten erklärt wird.

# Berechnung der Varianz-Anteileimport numpy as npX = np.array([[2.5, 2.4], [0.5, 0.7], [2.2, 2.9], [1.9, 2.2], [3.1, 3.0],               [2.3, 2.7], [2, 1.6], [1, 1.1], [1.5, 1.6], [1.1, 0.9]])# Zentrieren der DatenX_mean = np.mean(X, axis=0)X_centered = X - X_mean# Berechnung der Kovarianzmatrixcov_matrix = np.cov(X_centered, rowvar=False)# Berechnen der Eigenwerte und Eigenvektoreneig_vals, eig_vecs = np.linalg.eig(cov_matrix)# Anteil der Gesamtvarianzvar_explained = [(i / sum(eig_vals)) * 100 for i in eig_vals]print(f'Varianz-Anteil der ersten Hauptkomponente: {var_explained[0]:.2f}%')

Die Antwort variiert von Datensatz zu Datensatz. Dies sind die Prozentsatzanteile der Varianz, die jede Hauptkomponente erklärt. Die Summe der Varianz-Anteile der ersten k Hauptkomponenten gibt den Gesamtanteil der durch diese k Komponenten erklärten Varianz der Originaldaten an.

Warum ist es wichtig, die Daten zu zentrieren, bevor die Kovarianzmatrix berechnet wird?

Das Zentrieren der Daten, also das Abziehen des Mittelwerts jeder Variablen, ist ein wichtiger Schritt in der PCA. Dies stellt sicher, dass die Daten einen Mittelwert von null haben. Der Grund dafür ist, dass die Kovarianz zwischen den Merkmalen ohne Zentrierung nicht korrekt dargestellt wird und die Hauptkomponenten nicht die richtige Richtung anzeigen würden. Zentrierte Daten garantieren, dass die Hauptkomponenten auf die wahre Struktur der Varianz und Kovarianz der Daten basieren und nicht durch unterschiedliche Mittelwerte der Ausgangsmerkmale verzerrt werden.

Aufgabe 2)

Support Vector Machines (SVM) und ihre AnwendungSVM ist ein überwacht lernender Algorithmus, der verwendet wird, um Daten in Klassen zu unterteilen, indem er die optimale Trennlinie (Hyperplane) findet.

• Kernel-Trick: Erlaubt SVM, nichtlineare Trennungen durchzuführen, indem Daten in höhere Dimensionen projiziert werden.
• Mathematische Formulierung: Optimaler Hyperplane maximiert den Abstand zwischen den Datenpunkten beider Klassen. Optimierungsproblem: \[\text{minimize } \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w} \text{ subject to } y_i (\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1 \text{ for all } i\]
• Soft-Margin SVM: Toleriert einige Fehlklassifizierungen, einführend variablen \(\xi_i \): \[\text{minimize } \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w} + C \sum_{i=1}^n \xi_i \text{ subject to } y_i (\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1 - \xi_i \]
• Kernel-Funktionen: Wichtig zur Handhabung von komplexeren Datensätzen (z.B. linear, polynomial, RBF).
• Verwendung in Mustererkennung:
• Bild- und Spracherkennung
• Bioinformatik
• Text- und Dokumentklassifizierung

a)

(a) Erläutere den Kernel-Trick und warum er für SVMs nützlich ist. Gehe dabei auf den Unterschied zwischen einem linearen und einem nichtlinearen Kernel ein.

Lösung:

(a) Erläutere den Kernel-Trick und warum er für SVMs nützlich ist. Gehe dabei auf den Unterschied zwischen einem linearen und einem nichtlinearen Kernel ein.Der Kernel-Trick ist eine Technik, die es dem Support Vector Machine (SVM)-Algorithmus ermöglicht, nichtlineare Trennungen in den Daten zu erzeugen, indem die Daten in einen höherdimensionalen Raum projiziert werden. Das bedeutet, dass die Daten in einem neuen Raum dargestellt werden, in dem eine lineare Trennung möglich ist, auch wenn dies im ursprünglichen Raum nicht möglich war.Ein wesentlicher Vorteil des Kernel-Tricks besteht darin, dass diese Transformationen implizit durchgeführt werden, ohne dass wir die expliziten Koordinaten der höherdimensionalen Räume berechnen müssen. Stattdessen wird eine Kernel-Funktion verwendet, die die Berechnungen der Skalarprodukte in diesen höheren Dimensionen übernimmt. Dadurch werden komplexe Berechnungen und die Notwendigkeit der expliziten Darstellung in einem höherdimensionalen Raum vermieden.Hier sind die Schritte, wie der Kernel-Trick funktioniert:

• Zunächst werden die ursprünglichen Datenpunkte \(\boldsymbol{x}\) in einen höherdimensionalen Raum \(\boldsymbol{\boldsymbol{Φ(x)}}\) projiziert.
• In diesem neuen Raum kann dann eine lineare Trennung gefunden werden.
• Der Trick besteht darin, dass wir den Raum \(\boldsymbol{Φ(x)}\) nicht explizit berechnen müssen, sondern stattdessen über die Kernel-Funktion den SVM-Algorithmus direkt auf den Skalarprodukten \(K(x, x')\) der projizierten Punkte arbeiten lassen.

Der Unterschied zwischen einem linearen und einem nichtlinearen Kernel:

• Lineare Kernel: Der einfachste Kernel ist der lineare Kernel, bei dem die Kernel-Funktion das Skalarprodukt der Eingabedaten direkt berechnet. Hier wird keine Transformation in einen höheren Raum durchgeführt, und der Klassifikator sucht nur nach einer linearen Trennlinie im ursprünglichen Raum.

  K(x, x') = x \cdot x'

• Nichtlineare Kernel: Diese Kernel führen eine implizite Transformation der Eingaben in einen höherdimensionalen Raum durch. Beispiele für nichtlineare Kernel sind:
• Polynomialer Kernel:

  K(x, x') = (x \cdot x' + 1)^d

• Radial Basis Function (RBF) Kernel:

  K(x, x') = \exp \left( -\frac{||x - x'||^2}{2\tau^2} \right)

Der Hauptnutzen des Kernel-Tricks liegt also darin, dass komplexe und nichtlineare Trennungen möglich gemacht werden, ohne dass die Berechnungen in einem hochdimensionalen Raum explizit durchgeführt werden müssen. Dies ermöglicht SVMs, auch komplexere Datensätze effektiv zu klassifizieren.

b)

(b) Zeige die Schritte zur Lösung des Optimierungsproblems einer Soft-Margin SVM mathematisch auf. Erläutere die Bedeutung der Variablen \( \xi_i \) und des Parameters \( C \) in diesem Kontext.

Lösung:

(b) Zeige die Schritte zur Lösung des Optimierungsproblems einer Soft-Margin SVM mathematisch auf. Erläutere die Bedeutung der Variablen \( \xi_i \) und des Parameters \( C \) in diesem Kontext.Die Soft-Margin SVM ermöglicht es, einige Fehlklassifizierungen zu tolerieren, um eine bessere Generalisierung auf neuen, nicht gesehenen Daten zu ermöglichen. Die Einführung slacker Variablen \( \xi_i \) ermöglicht diese Flexibilität. Der Parameter \( C \) ist ein Regularisierungsparameter, der den Kompromiss zwischen einer großen Margin und einer geringen Fehlklassifizierungsrate steuert.Hier sind die Schritte zur Lösung des Optimierungsproblems einer Soft-Margin SVM mathematisch dargestellt:1. Formuliere das Primale Optimierungsproblem:Das primale Optimierungsproblem einer Soft-Margin SVM kann wie folgt formuliert werden:

• Zielfunktion:\[ \text{minimize } \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w} + C \sum_{i=1}^n \xi_i \]
• Nebenbedingungen:\[ y_i (\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1 - \xi_i \]
• \[ \xi_i \ge 0 \]

2. Einführung der Lagrange-Multiplikatoren:Um das Problem zu lösen, verwenden wir die Lagrange-Multiplikatoren \( \alpha_i \) und \( \mu_i \) für die Nebenbedingungen:

• Lagrange-Funktion:\[ \mathcal{L}(\boldsymbol{w}, b, \xi, \alpha, \mu) = \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w} + C \sum_{i=1}^n \xi_i - \sum_{i=1}^n \alpha_i [y_i (\boldsymbol{w}^T \boldsymbol{x}_i + b) - 1 + \xi_i] - \sum_{i=1}^n \mu_i \xi_i \]

3. Bestimme die KKT-Bedingungen (Karush-Kuhn-Tucker):Die optimalen Werte für \( \boldsymbol{w} \), \( b \), und \( \xi_i \) müssen die folgenden KKT-Bedingungen erfüllen:

• Stationaritätsbedingungen:\[ \frac{\partial \mathcal{L}}{\partial \boldsymbol{w}} = \boldsymbol{w} - \sum_{i=1}^n \alpha_i y_i \boldsymbol{x}_i = 0 \]
• \[ \frac{\partial \mathcal{L}}{\partial b} = - \sum_{i=1}^n \alpha_i y_i = 0 \]
• \[ \frac{\partial \mathcal{L}}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \]

4. Formuliere das Duale Optimierungsproblem:Durch Einsetzen der Stationaritätsbedingungen in die Lagrange-Funktion erhalten wir das duale Problem:

• Zielfunktion im dualen Problem:\[ \text{maximize } \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i \cdot \boldsymbol{x}_j \]
• Nebenbedingungen:\[ \sum_{i=1}^n \alpha_i y_i = 0 \]
• \[ 0 \le \alpha_i \le C \]

5. Lösung des Dualen Problems:Das duale Optimierungsproblem wird typischerweise unter Verwendung von Quadratischer Programmierung (QP) gelöst. Die optimalen Lösungen \( \alpha_i \) werden verwendet, um \( \boldsymbol{w} \) zu berechnen:\[ \boldsymbol{w} = \sum_{i=1}^n \alpha_i y_i \boldsymbol{x}_i \]Der Bias-Term \( b \) kann aus den KKT-Bedingungen erhalten werden.Bedeutung der Variablen \( \xi_i \) und des Parameters \( C \):Die Variablen \( \xi_i \) (slack variables) repräsentieren den Grad der Fehlklassifizierung für jeden Datenpunkt. Ein \( \xi_i \) von 0 bedeutet, dass der Punkt korrekt klassifiziert ist und auf der richtigen Seite des Randes liegt. Ein \( \xi_i \) > 0 bedeutet, dass der Punkt entweder innerhalb der Margin oder auf der falschen Seite des Hyperplanes liegt.Der Parameter \( C \) ist ein Regularisierungsparameter, der den Kompromiss zwischen einer großen Margin und der Anzahl der zulässigen Fehlklassifizierungen steuert. Ein großer Wert von \( C \) versucht, alle Trainingsbeispiele korrekt zu klassifizieren und toleriert weniger Fehlklassifizierungen, was zu einer geringeren Margin führt. Ein kleiner Wert von \( C \) ermöglicht eine größere Margin, toleriert aber auch mehr Fehlklassifizierungen.

c)

(c) Wende eine RBF-Kernel SVM an, um einen gegebenen Datensatz zu klassifizieren. Beschreibe die verschiedenen Schritte, die dabei durchlaufen werden, und begründe die Wahl der Parameter.

Lösung:

(c) Wende eine RBF-Kernel SVM an, um einen gegebenen Datensatz zu klassifizieren. Beschreibe die verschiedenen Schritte, die dabei durchlaufen werden, und begründe die Wahl der Parameter.Um eine RBF-Kernel SVM (Radial Basis Function-Kernel) zur Klassifikation eines gegebenen Datensatzes anzuwenden, durchlaufen wir mehrere Schritte. Hier ist eine detaillierte Beschreibung dieser Schritte und die Begründung der Wahl der Parameter:

• Schritt 1: DatenvorverarbeitungBevor wir das SVM-Modell anwenden, müssen wir sicherstellen, dass die Daten korrekt vorverarbeitet werden. Dies umfasst:
• Datenbereinigung: Entferne fehlende Werte oder fülle sie entsprechend auf.
• Normalisierung/Standardisierung: Skaliere die Features, um sicherzustellen, dass sie eine vergleichbare Größenordnung haben. Dies ist besonders wichtig für RBF-Kernel, da große Unterschiede in den Skalen der Features die Performance der SVM negativ beeinflussen können.
• Schritt 2: Wahl der ParameterDie RBF-Kernel SVM hat zwei wichtige Hyperparameter, die eingestellt werden müssen:
• \(C\): Der Regularisierungsparameter, der den Kompromiss zwischen einer großen Margin und der Anzahl der zulässigen Fehlklassifizierungen steuert. Ein hoher Wert von C versucht, alle Trainingsbeispiele korrekt zu klassifizieren, mit weniger Toleranz gegenüber Fehlern, während ein niedriger Wert von C größere Marginen zulässt, aber auch mehr Fehlklassifizierungen toleriert.
• \(\gamma\): Der Parameter \(\gamma\) des RBF-Kernels bestimmt den Einflussbereich eines einzelnen Trainingsbeispiels. Ein hoher Wert von \(\gamma\) führt zu einer kleinere Einflussreichweite und somit zu einem engeren Fit des Modells, während ein niedriger Wert von \(\gamma\) eine größere Einflussreichweite hat und ein glatteres Modell führt.

RBF-Kernel-Funktion: \(K(x, x') = \exp \left( -\gamma ||x - x'||^2 \right)\)

• Schritt 3: ModelltrainingVerwende die SVM Implementierung in einer Machine Learning Bibliothek (wie scikit-learn in Python). Trainiere das Modell mit den trainierten Daten:

  from sklearn.svm import SVCfrom sklearn.preprocessing import StandardScalerfrom sklearn.pipeline import make_pipeline# Beispiel-DatensatzX_train = ...  # Trainingsdateny_train = ...  # Zielvariable# Erstelle und trainiere ein SVM-Modell mit RBF-Kernelmodel = make_pipeline(StandardScaler(), SVC(kernel='rbf', C=1.0, gamma='scale'))model.fit(X_train, y_train)

• Schritt 4: Hyperparameter-OptimierungWende Cross-Validation (z.B. k-fold Cross-Validation) an, um die besten Werte für die Hyperparameter \(C\) und \(\gamma\) zu finden. Es ist üblich, eine Grid-Suche oder Random-Suche für diese Optimierung zu verwenden:

from sklearn.model_selection import GridSearchCV# Definiere den Parameterbereichparam_grid = {'svc__C': [0.1, 1, 10, 100], 'svc__gamma': ['scale', 0.1, 1, 10, 100]}# Grid-Suche mit Cross-Validationgrid_search = GridSearchCV(model, param_grid, cv=5)grid_search.fit(X_train, y_train)# Beste Parameterbest_params = grid_search.best_params_print(best_params)

Schritt 5: ModellbewertungBewerte die Leistung des trainierten Modells auf einem separaten Testdatensatz, um sicherzustellen, dass das Modell gut generalisiert:

from sklearn.metrics import classification_report, confusion_matrixX_test = ...  # Testdateny_test = ...  # Zielvariable# Vorhersageny_pred = model.predict(X_test)# Auswertenprint(classification_report(y_test, y_pred))print(confusion_matrix(y_test, y_pred))

Schritt 6: ModellanwendungNachdem das Modell ausgewertet wurde und zufriedenstellende Ergebnisse liefert, kann es verwendet werden, um neue, unbeobachtete Daten zu klassifizieren.

Begründung der Parameterwahl:

• Die Wahl von \(C\) ist entscheidend, um einen geeigneten Kompromiss zwischen der Generalisierung des Modells und der Anpassung an die Trainingsdaten zu finden. Zu hohe Werte können zu Overfitting führen, während zu niedrige Werte zu Underfitting führen könnten.
• Der Parameter \(\gamma\) bestimmt die Komplexität des RBF-Kernels. Ein gut gewählter Wert von \(\gamma\) ermöglicht es dem Modell, die feinen Strukturen der Daten zu erfassen, während ein schlechter Wert zu einem schlecht leistungsfähigen Modell führen kann.

Aufgabe 3)

Du entwickelst ein System zur Mustererkennung, das auf dem Naive Bayes Klassifikator basiert. Das System soll verschiedene Dokumente (Texte) klassifizieren und verwendet dafür diskrete Merkmale, die angeben, ob ausgewählte Schlüsselwörter in den Dokumenten vorkommen oder nicht. Um die Wahrscheinlichkeiten zu schätzen, nutzt Dein System das Multinomial Naive Bayes Modell. Die Dokumentklassen sind 'Sport', 'Politik' und 'Technologie'. Du hast eine Trainingsdatensatz mit 100 Dokumenten, die gleichmäßig auf die drei Klassen verteilt sind. Die Merkmale Deiner Dokumente bestehen aus 10 Schlüsselwörtern. Gegeben sei die Wortanzahl der ausgewählten Schlüsselwörter in den Klassen 'Sport', 'Politik' und 'Technologie' (zusammengefasst in der folgenden Tabelle):

• Schlüsselwort: k1, k2, k3, ..., k10
• Sport: 20, 10, 15, ..., 5
• Politik: 5, 9, 10, ..., 12
• Technologie: 8, 12, 9, ..., 15

a)

Berechne die bedingte Wahrscheinlichkeit eines Dokuments, das die Schlüsselwörter k1, k2 und k3 enthält, gegeben die Klasse 'Sport'. Schätze zunächst die Wahrscheinlichkeiten für jedes der drei Schlüsselwörter in der Klasse 'Sport' unter der Annahme des Multinomial Naive Bayes Modells. Berechne dann die Gesamtwahrscheinlichkeit für das Dokument unter der Klasse 'Sport'. Hinweis: Verwende \alpha = 1 für die additive Glättung (Laplace Glättung), falls notwendig.

Lösung:

Um die bedingte Wahrscheinlichkeit eines Dokuments zu berechnen, das die Schlüsselwörter k1, k2 und k3 enthält, gegeben die Klasse 'Sport', müssen wir die Wahrscheinlichkeiten dieser Schlüsselwörter in der Klasse 'Sport' berechnen. Anschließend nutzen wir diese Wahrscheinlichkeiten, um die Gesamtwahrscheinlichkeit des Dokuments unter Verwendung des Multinomial Naive Bayes Modells zu berechnen.

• 1. Schritt: Wahrscheinlichkeiten der Schlüsselwörter unter der Klasse 'Sport' berechnen

Wir verwenden \(\alpha = 1\) für die additive Glättung.

Die Wortanzahl der Schlüsselwörter unter 'Sport' ist wie folgt:

• k1: 20
• k2: 10
• k3: 15
• k4,...,k10: ...

Gesamtanzahl aller Schlüsselwörter in der Klasse 'Sport' (ohne Glättung): \(\sum_{i=1}^{10} \text{count}(k_i) = 20 + 10 + 15 + ... + 5 = 100\)

Mit additive Glättung beträgt die angepasste Gesamtanzahl aller Schlüsselwörter in der Klasse 'Sport':

Gesamtanzahl mit Glättung: \(100 + 10 * \alpha = 100 + 10 = 110\)

Berechnen der Einzelwahrscheinlichkeiten:

\(P(k1|Sport) = \frac{\text{count}(k1) + \alpha}{N_{\text{Sport}} + V} = \frac{20 + 1}{100 + 10} = \frac{21}{110} = 0.19\)

\(P(k2|Sport) = \frac{\text{count}(k2) + \alpha}{N_{\text{Sport}} + V} = \frac{10 + 1}{100 + 10} = \frac{11}{110} = 0.10\)

\(P(k3|Sport) = \frac{\text{count}(k3) + \alpha}{N_{\text{Sport}} + V} = \frac{15 + 1}{100 + 10} = \frac{16}{110} = 0.145\)

• 2. Schritt: Gesamtwahrscheinlichkeit des Dokuments unter der Klasse 'Sport' berechnen

Die Gesamtwahrscheinlichkeit ist das Produkt der Einzelwahrscheinlichkeiten:

\(P(\text{Dokument}|\text{Sport}) = P(k1|Sport) \cdot P(k2|Sport) \cdot P(k3|Sport) = 0.19 \cdot 0.10 \cdot 0.145\)

Bei der Multiplikation ergibt sich:

\(P(\text{Dokument}|\text{Sport}) = 0.002755\)

Daher beträgt die bedingte Wahrscheinlichkeit für das Dokument, das die Schlüsselwörter k1, k2 und k3 enthält, gegeben die Klasse 'Sport',:

\(\boxed{0.002755}\)

b)

Diskutiere, wie das System verbessert werden könnte, indem Du Abhängigkeiten zwischen den Schlüsselwörtern berücksichtigst. Erläutere kurz, wie ein Bayessches Netzwerk in diesem Kontext angewendet werden könnte und wie es die Limitierungen des Naive Bayes Klassifikators überwinden könnte.

Lösung:

Das Basismodell des Naive Bayes Klassifikators geht davon aus, dass die Merkmale (in diesem Fall die Schlüsselwörter) bedingungslos unabhängig voneinander sind, wenn die Klasse gegeben ist. Diese Annahme der bedingten Unabhängigkeit ist oft nicht realistisch, da in Texten häufig Abhängigkeiten zwischen den Schlüsselwörtern bestehen. Beispielsweise treten die Wörter „Ball“ und „Tor“ häufig gemeinsam in Sportartikeln auf.

• Verbesserungen durch Berücksichtigung von Abhängigkeiten

Um die Abhängigkeiten zwischen Schlüsselwörtern abzubilden und zu nutzen, könnte ein Bayessches Netzwerk (Bayesian Network) verwendet werden.

Ein Bayessches Netzwerk ist ein probabilistisches grafisches Modell, das die Abhängigkeiten zwischen verschiedenen Variablen (Merkmalen) darstellt. Es besteht aus Knoten, die die Variablen repräsentieren, und Kanten, die die Abhängigkeiten (bedingte Wahrscheinlichkeiten) zwischen diesen Variablen darstellen. Durch diese Struktur kann das Netzwerk die Verhältnisse und Wechselwirkungen zwischen den Schlüsselwörtern explizit modellieren.

• Anwendung eines Bayesschen Netzwerks im Kontext der Mustererkennung

Statt anzunehmen, dass die Wahrscheinlichkeit eines Schlüsselworts allein von der Klasse abhängt, könnte ein Bayessches Netzwerk zum Beispiel die direkte Abhängigkeit zwischen bestimmten Schlüsselwörtern und deren Bedingung aufeinander ausdrücken. Das Netzwerk könnte so konstruiert werden, dass es die wahrscheinliche Korrelation reflektiert, z.B.:

• k1 → k2 (d.h. das Auftreten von k1 beeinflusst das Auftreten von k2)
• k2 → k3

Die bedingten Wahrscheinlichkeiten könnten auf Basis der Trainingsdaten ermittelt werden. Ein Bayessches Netzwerk ermöglicht es, komplexere Wahrscheinlichkeitsverteilungen zu modellieren und bietet dadurch eine präzisere und genauere Klassifikation.

Ein möglicher Ansatz wäre es, die Trainingsdaten durch ein Verfahren wie das Expectation-Maximization (EM) Verfahren zu verwenden, um die Struktur des Netzes und die entsprechenden Wahrscheinlichkeitsverteilungen zu lernen.

• Vorteile des Bayesschen Netzwerks

Das Bayessche Netzwerk könnte helfen, die folgenden Limitierungen des Naive Bayes Klassifikators zu überwinden:

• Modellierung von Abhängigkeiten: Durch explizite Modellierung der Abhängigkeiten zwischen den Schlüsselwörtern erhöht sich die Genauigkeit.
• Besseres Verständnis der Daten: Die Struktur des Netzwerks bietet eine verständlichere Darstellung der Beziehungen zwischen den Schlüsselwörtern.
• Flexibilität: Das Netzwerk kann einfacher an neue Informationen angepasst oder weiterentwickelt werden als der Naive Bayes Ansatz.

Zusammenfassend lässt sich sagen, dass durch die Einführung eines Bayesschen Netzwerks zur Modellierung der Abhängigkeiten zwischen den Schlüsselwörtern das System präziser und leistungsfähiger werden kann.

Aufgabe 4)

Gegeben ist ein Hidden-Markov-Modell (HMM) mit folgenden Bestandteilen:

• Ein Satz von Zuständen: S = {s1, s2, s3}.
• Ein Satz von Beobachtungen: O = {o1, o2}.
• Übergangswahrscheinlichkeiten:
  • P(s1|s1) = 0.5, P(s2|s1) = 0.3, P(s3|s1) = 0.2
  • P(s1|s2) = 0.4, P(s2|s2) = 0.4, P(s3|s2) = 0.2
  • P(s1|s3) = 0.3, P(s2|s3) = 0.3, P(s3|s3) = 0.4
• Emissionwahrscheinlichkeiten:
  • P(o1|s1) = 0.7, P(o2|s1) = 0.3
  • P(o1|s2) = 0.4, P(o2|s2) = 0.6
  • P(o1|s3) = 0.5, P(o2|s3) = 0.5
• Die Anfangswahrscheinlichkeiten: P(s1) = 0.6, P(s2) = 0.3, P(s3) = 0.1.

Berechne die gesuchte Wahrscheinlichkeiten mit dem Vorwärts-Algorithmus und finde den wahrscheinlichsten Zustandsweg mit dem Viterbi-Algorithmus für die Beobachtungssequenz O = {o1, o2, o1}.

a)

Berechne mithilfe des Vorwärts-Algorithmus die Wahrscheinlichkeit der Beobachtungssequenz O = {o1, o2, o1} bis einschließlich des letzten Schrittes. Gegeben sind:

• Forward-Formel: \( \text{forward}(t, j) = \text{obs}_j(t) \times \sum_{i=1}^{N} \text{transition}_{ij} \times \text{forward}(t-1, i) \).

Stelle die Rechnungen für jeden Zustand und jeden Schritt dar.

Lösung:

Berechnung der Wahrscheinlichkeit der Beobachtungssequenz O = {o1, o2, o1} mithilfe des Vorwärts-Algorithmus

Folgendes Hidden-Markov-Modell ist gegeben:

• Zustände: S = {s1, s2, s3}
• Beobachtungen: O = {o1, o2}
• Übergangswahrscheinlichkeiten:
• P(s1|s1) = 0.5, P(s2|s1) = 0.3, P(s3|s1) = 0.2
• P(s1|s2) = 0.4, P(s2|s2) = 0.4, P(s3|s2) = 0.2
• P(s1|s3) = 0.3, P(s2|s3) = 0.3, P(s3|s3) = 0.4
• Emissionwahrscheinlichkeiten:
• P(o1|s1) = 0.7, P(o2|s1) = 0.3
• P(o1|s2) = 0.4, P(o2|s2) = 0.6
• P(o1|s3) = 0.5, P(o2|s3) = 0.5
• Anfangswahrscheinlichkeiten: P(s1) = 0.6, P(s2) = 0.3, P(s3) = 0.1

Die Beobachtungssequenz ist O = {o1, o2, o1}. Verwenden wir den Vorwärts-Algorithmus, um die Wahrscheinlichkeit der Sequenz zu berechnen.

Initialisierung:

Für den ersten Beobachtungszeitpunkt t = 1 und jeder Zustand j berechnen wir:

• forward(1, s1) = P(o1|s1) * P(s1)\td.h. forward(1, s1) = 0.7 * 0.6 = 0.42

• forward(1, s2) = P(o1|s2) * P(s2)\td.h. forward(1, s2) = 0.4 * 0.3 = 0.12

• forward(1, s3) = P(o1|s3) * P(s3)\td.h. forward(1, s3) = 0.5 * 0.1 = 0.05

Rekursion:

Für jeden nachfolgenden Schritt t = 2, 3 und jeden Zustand j, verwenden wir:

• t = 2

  Beobachtung o2:

  • forward(2, s1) = P(o2|s1) * [P(s1|s1) * forward(1, s1) + P(s1|s2) * forward(1, s2) + P(s1|s3) * forward(1, s3)]d.h. forward(2, s1) = 0.3 * [0.5 * 0.42 + 0.4 * 0.12 + 0.3 * 0.05] = 0.3 * [0.21 + 0.048 + 0.015] = 0.3 * 0.273 = 0.0819
  • forward(2, s2) = P(o2|s2) * [P(s2|s1) * forward(1, s1) + P(s2|s2) * forward(1, s2) + P(s2|s3) * forward(1, s3)]d.h. forward(2, s2) = 0.6 * [0.3 * 0.42 + 0.4 * 0.12 + 0.3 * 0.05] = 0.6 * [0.126 + 0.048 + 0.015] = 0.6 * 0.189 = 0.1134
  • forward(2, s3) = P(o2|s3) * [P(s3|s1) * forward(1, s1) + P(s3|s2) * forward(1, s2) + P(s3|s3) * forward(1, s3)]d.h. forward(2, s3) = 0.5 * [0.2 * 0.42 + 0.2 * 0.12 + 0.4 * 0.05] = 0.5 * [0.084 + 0.024 + 0.02] = 0.5 * 0.128 = 0.064

• t = 3

  Beobachtung o1:

  • forward(3, s1) = P(o1|s1) * [P(s1|s1) * forward(2, s1) + P(s1|s2) * forward(2, s2) + P(s1|s3) * forward(2, s3)]d.h. forward(3, s1) = 0.7 * [0.5 * 0.0819 + 0.4 * 0.1134 + 0.3 * 0.064] = 0.7 * [0.04095 + 0.04536 + 0.0192] = 0.7 * 0.10551 = 0.073857
  • forward(3, s2) = P(o1|s2) * [P(s2|s1) * forward(2, s1) + P(s2|s2) * forward(2, s2) + P(s2|s3) * forward(2, s3)]d.h. forward(3, s2) = 0.4 * [0.3 * 0.0819 + 0.4 * 0.1134 + 0.3 * 0.064] = 0.4 * [0.02457 + 0.04536 + 0.0192] = 0.4 * 0.08913 = 0.035652
  • forward(3, s3) = P(o1|s3) * [P(s3|s1) * forward(2, s1) + P(s3|s2) * forward(2, s2) + P(s3|s3) * forward(2, s3)]d.h. forward(3, s3) = 0.5 * [0.2 * 0.0819 + 0.2 * 0.1134 + 0.4 * 0.064] = 0.5 * [0.01638 + 0.02268 + 0.0256] = 0.5 * 0.06466 = 0.03233

Berechnung der gesamten Wahrscheinlichkeit:

Zum Abschluss aggregieren wir die Wahrscheinlichkeiten für alle Zustände für den letzten Zeitschritt t = 3:

p(O|HMM) = forward(3, s1) + forward(3, s2) + forward(3, s3)

d.h. p(O|HMM) = 0.073857 + 0.035652 + 0.03233 = 0.141839

Die Wahrscheinlichkeit der Beobachtungssequenz O = {o1, o2, o1} beträgt also 0.141839.

b)

Finde den wahrscheinlichsten Zustandsweg dieser Beobachtungssequenz mithilfe des Viterbi-Algorithmus. Nutze hierzu die Formel: \( \text{viterbi}(t, j) = \text{obs}_j(t) \times \max_{i=1}^{N} \text{transition}_{ij} \times \text{viterbi}(t-1, i) \). Stelle den Viterbi-Trellis und die Rückverfolgung dar.

Lösung:

Finde den wahrscheinlichsten Zustandsweg mithilfe des Viterbi-Algorithmus

Gegeben ist das Hidden-Markov-Modell (HMM) mit folgenden Parametern:

• Zustände: S = {s1, s2, s3}
• Beobachtungen: O = {o1, o2}
• Übergangswahrscheinlichkeiten:
• P(s1|s1) = 0.5, P(s2|s1) = 0.3, P(s3|s1) = 0.2
• P(s1|s2) = 0.4, P(s2|s2) = 0.4, P(s3|s2) = 0.2
• P(s1|s3) = 0.3, P(s2|s3) = 0.3, P(s3|s3) = 0.4
• Emissionwahrscheinlichkeiten:
• P(o1|s1) = 0.7, P(o2|s1) = 0.3
• P(o1|s2) = 0.4, P(o2|s2) = 0.6
• P(o1|s3) = 0.5, P(o2|s3) = 0.5
• Anfangswahrscheinlichkeiten: P(s1) = 0.6, P(s2) = 0.3, P(s3) = 0.1

Die Beobachtungssequenz ist O = {o1, o2, o1}. Verwenden wir den Viterbi-Algorithmus, um den wahrscheinlichsten Zustandsweg zu berechnen.

Initialisierung:

Für den ersten Beobachtungszeitpunkt t = 1 und jeden Zustand j berechnen wir:

• viterbi(1, s1) = P(o1|s1) * P(s1)d.h. viterbi(1, s1) = 0.7 * 0.6 = 0.42

• viterbi(1, s2) = P(o1|s2) * P(s2)d.h. viterbi(1, s2) = 0.4 * 0.3 = 0.12

• viterbi(1, s3) = P(o1|s3) * P(s3)d.h. viterbi(1, s3) = 0.5 * 0.1 = 0.05

Rekursion:

Für jeden nachfolgenden Schritt t = 2, 3 und jeden Zustand j, verwenden wir:

• t = 2

  Beobachtung o2:

  • viterbi(2, s1) = P(o2|s1) * max(P(s1|s1) * viterbi(1, s1), P(s1|s2) * viterbi(1, s2), P(s1|s3) * viterbi(1, s3))d.h. viterbi(2, s1) = 0.3 * max(0.5 * 0.42, 0.4 * 0.12, 0.3 * 0.05) = 0.3 * max(0.21, 0.048, 0.015) = 0.3 * 0.21 = 0.063Hier stammt der Maximale Wert aus Zustand s1.
  • viterbi(2, s2) = P(o2|s2) * max(P(s2|s1) * viterbi(1, s1), P(s2|s2) * viterbi(1, s2), P(s2|s3) * viterbi(1, s3))d.h. viterbi(2, s2) = 0.6 * max(0.3 * 0.42, 0.4 * 0.12, 0.3 * 0.05) = 0.6 * max(0.126, 0.048, 0.015) = 0.6 * 0.126 = 0.0756Hier stammt der Maximale Wert aus Zustand s1.
  • viterbi(2, s3) = P(o2|s3) * max(P(s3|s1) * viterbi(1, s1), P(s3|s2) * viterbi(1, s2), P(s3|s3) * viterbi(1, s3))d.h. viterbi(2, s3) = 0.5 * max(0.2 * 0.42, 0.2 * 0.12, 0.4 * 0.05) = 0.5 * max(0.084, 0.024, 0.02) = 0.5 * 0.084 = 0.042Hier stammt der Maximale Wert aus Zustand s1.

• t = 3

  Beobachtung o1:

  • viterbi(3, s1) = P(o1|s1) * max(P(s1|s1) * viterbi(2, s1), P(s1|s2) * viterbi(2, s2), P(s1|s3) * viterbi(2, s3))d.h. viterbi(3, s1) = 0.7 * max(0.5 * 0.063, 0.4 * 0.0756, 0.3 * 0.042) = 0.7 * max(0.0315, 0.030240, 0.0126) = 0.7 * 0.0315 = 0.02205Hier stammt der Maximale Wert aus Zustand s1.
  • viterbi(3, s2) = P(o1|s2) * max(P(s2|s1) * viterbi(2, s1), P(s2|s2) * viterbi(2, s2), P(s2|s3) * viterbi(2, s3))d.h. viterbi(3, s2) = 0.4 * max(0.3 * 0.063, 0.4 * 0.0756, 0.3 * 0.042) = 0.4 * max(0.0189, 0.03024, 0.0126) = 0.4 * 0.03024 = 0.012096Hier stammt der Maximale Wert aus Zustand s2.
  • viterbi(3, s3) = P(o1|s3) * max(P(s3|s1) * viterbi(2, s1), P(s3|s2) * viterbi(2, s2), P(s3|s3) * viterbi(2, s3))d.h. viterbi(3, s3) = 0.5 * max(0.2 * 0.063, 0.2 * 0.0756, 0.4 * 0.042) = 0.5 * max(0.0126, 0.01512, 0.0168) = 0.5 * 0.0168 = 0.0084Hier stammt der Maximale Wert aus Zustand s3.

Rückverfolgung:

Um den wahrscheinlichsten Zustandsweg zu finden, müssen wir die Rückverfolgungsinformation verwenden, die wir während der Rekursionsschritte gespeichert haben. Wir beginnen bei t = 3 und gehen rückwärts:

• Für t = 3, der wahrscheinlichste Zustand ist s1 (da viterbi(3, s1) = 0.02205 der höchste Wert ist).

• Für t = 2, der Zustand vor s1 war auch s1.

• Für t = 1, der Zustand vor s1 war auch s1.

Der wahrscheinlichste Zustandsweg für die Beobachtungssequenz O = {o1, o2, o1} lautet daher: s1 → s1 → s1.