Introduction to Machine Learning - Exam

Aufgabe 1)

Du arbeitest an einem Projekt, das sowohl Klassifikations- als auch Regressionsmethoden umfasst. Dein Ziel ist es, eine E-Mail-Filter-App zu entwickeln, die eingehende E-Mails als Spam oder Nicht-Spam klassifiziert (Klassifikation). Außerdem enthält das Projekt eine Temperaturvorhersagefunktion (Regression).

a)

• Klassifikation: Du verwendest ein Support Vector Machine (SVM) Modell, um E-Mails zu klassifizieren. Beschreibe den mathematischen Hintergrund einer SVM und erläutere, wie die Trennung der Klassen in höherdimensionalen Räumen durch den Kernel-Trick erreicht werden kann. Formel: Die Entscheidungsgleichung einer SVM ist \[f(x) = sign(w^T x + b)\]

Lösung:

Um eine Support Vector Machine (SVM) besser zu verstehen, gehen wir Schritt für Schritt durch den mathematischen Hintergrund und wie der Kernel-Trick funktioniert.

• Mathematischer Hintergrund einer SVM: SVMs sind überwachte Lernmodelle, die verwendet werden, um Klassen in einem gegebenen Datensatz zu trennen. Die Hauptidee besteht darin, eine Trennlinie (oder in höherdimensionalen Räumen: eine Trennfläche) zu finden, die die Klassen optimal trennt. Das Ziel ist es, die Margin (Abstand) zwischen den nächstgelegenen Datenpunkten beider Klassen zu maximieren.
• Entscheidungsgleichung: Die Entscheidungsgleichung einer SVM ist gegeben durch:

  f(x) = sign(w^T x + b)

  Hierbei gilt:
  • w ist der Gewichtungsvektor.
  • x ist der Eingangsvektor (Merkmale der E-Mail).
  • b ist der Bias-Term.
  • sign ist die Signumfunktion, die das Vorzeichen des Arguments bestimmt.
• Kernel-Trick: Ein Problem bei SVMs kann auftreten, wenn die Daten nicht linear trennbar sind. In solchen Fällen wird der Kernel-Trick verwendet, um die Datenpunkte in einen höherdimensionalen Raum abzubilden, in dem sie linear trennbar werden. Der Kernel-Trick ermöglicht es uns, Berechnungen in diesem höherdimensionalen Raum durchzuführen, ohne tatsächlich in diesen Raum zu wechseln. Dies geschieht durch die Verwendung einer Kernel-Funktion K(x_i, x_j), die das Skalarprodukt der Datenpunkte x_i und x_j in diesem höherdimensionalen Raum berechnet. Häufig verwendete Kernel-Funktionen sind:
  • Linearkernel: \( K(x_i, x_j) = x_i^T x_j \)
  • Polynomkernel: \( K(x_i, x_j) = (\gamma x_i^T x_j + r)^d \)
  • RBF-Kernel (radial-basis function): \( K(x_i, x_j) = exp(-\gamma ||x_i - x_j||^2) \)

Durch die Verwendung dieser Techniken kann das SVM-Modell die eingehenden E-Mails effektiv als Spam oder Nicht-Spam klassifizieren.

b)

• Regression: Für die Temperaturvorhersage setzt Du das Modell der linearen Regression ein. Erkläre, wie das Modell der linearen Regression funktioniert und wie die Parameter mithilfe des kleinsten quadratischen Fehlers (MSE) geschätzt werden. Welche Rolle spielt die Verlustfunktion in diesem Kontext? Formel: Der kleinste quadratische Fehler (MSE) ist definiert als \[MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y_i})^2\]

Lösung:

Das Modell der linearen Regression ist ein grundlegendes Werkzeug zur Vorhersage von kontinuierlichen Zielen. Lassen Sie uns näher betrachten, wie es funktioniert, wie die Parameter geschätzt werden und welche Rolle die Verlustfunktion spielt:

• Funktionsweise der linearen Regression: Ein lineares Regressionsmodell versucht, die Beziehung zwischen einer Zielvariablen (z.B. Temperatur) und einer oder mehreren Eingangsvariablen (z.B. Uhrzeit, geografische Lage) durch eine lineare Gleichung zu modellieren. Die allgemeine Form der linearen Regression ist:

  Ŷ = β0 + β1X1 + β2X2 + ... + βpXp

  Dabei gilt:
  • Ŷ ist die vorhergesagte Zielvariable.
  • β0 ist der Achsenabschnitt.
  • β1, β2, ..., βp sind die Koeffizienten der Eingangsvariablen, die die Gewichtungen darstellen.
  • X1, X2, ..., Xp sind die Eingangsvariablen (Prädiktoren).
• Schätzung der Parameter mithilfe des kleinsten quadratischen Fehlers (MSE): Um die Parameter \(β0, β1, ..., βp\) zu schätzen, wird die Methode der kleinsten Quadrate verwendet. Das Ziel ist es, die Summe der quadrierten Abweichungen zwischen den tatsächlichen Werten \(y_i\) und den vorhergesagten Werten \(\hat{y_i}\) zu minimieren. Der mittlere quadratische Fehler (MSE) ist ein Maß dafür und wird folgendermaßen definiert:

  MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y_i})^2

  Hierbei gilt:
  • n ist die Anzahl der Beobachtungen.
  • y_i sind die tatsächlichen Werte der Zielvariable.
  • \hat{y_i} sind die vorhergesagten Werte der Zielvariable.
  Die Methode der kleinsten Quadrate versucht, die Gesamtabweichung zu minimieren, wodurch wir die optimalen Parameter für die lineare Gleichung erhalten.
• Die Rolle der Verlustfunktion: Die Verlustfunktion in diesem Kontext ist der MSE. Die Verlustfunktion misst, wie gut oder schlecht unser Modell die Daten vorhersagt. Ein niedriger MSE bedeutet, dass das Modell gute Vorhersagen macht, weil die Differenz zwischen den tatsächlichen und vorhergesagten Werten gering ist. Das Ziel der Optimierung ist es, die Verlustfunktion zu minimieren, was dazu führt, dass die Parameter der linearen Regression so festgelegt werden, dass die Vorhersagefehler minimiert werden.

Durch die Minimierung des MSE werden die besten Parameter für das Regressionsmodell gefunden, was zu einer effektiven Vorhersage der Temperatur führt.

Aufgabe 2)

Du hast ein Klassifikationsmodell entwickelt, um E-Mails als Spam oder Nicht-Spam zu klassifizieren. Um die Effektivität und Generalisierungsfähigkeit deines Modells zu bewerten, entscheidest du dich, verschiedene Evaluationsmetriken und Kreuzvalidierungstechniken zu verwenden.

a)

Erkläre die Begriffe Accuracy, Precision, Recall und F1-Score. Welche dieser Metriken würdest du bevorzugt zur Bewertung eines Spam-Filters verwenden und warum?

Lösung:

Um die Effektivität deines Klassifikationsmodells zu bewerten, ist es wichtig, die folgenden Metriken zu verstehen:

• Accuracy: Die Genauigkeit gibt den Anteil der korrekt klassifizierten E-Mails (sowohl Spam als auch Nicht-Spam) an der Gesamtzahl der E-Mails an. Sie wird berechnet als: \begin{equation} \text{Accuracy} = \frac{\text{Anzahl der korrekten Klassifikationen}}{\text{Gesamtanzahl der E-Mails}} \end{equation} Beispiel: Wenn von 100 E-Mails 90 korrekt klassifiziert wurden, beträgt die Genauigkeit 90%.
• Precision: Präzision gibt den Anteil der korrekt als Spam klassifizierten E-Mails an allen als Spam klassifizierten E-Mails an. Sie wird berechnet als: \begin{equation} \text{Precision} = \frac{\text{True Positives}}{\text{True Positives + False Positives}} \end{equation} Beispiel: Wenn von 100 als Spam klassifizierten E-Mails 80 tatsächlich Spam sind, beträgt die Präzision 80%.
• Recall (Sensitivität): Empfindlichkeit gibt den Anteil der korrekt als Spam klassifizierten E-Mails an allen tatsächlich Spam-E-Mails an. Sie wird berechnet als: \begin{equation} \text{Recall} = \frac{\text{True Positives}}{\text{True Positives + False Negatives}} \end{equation} Beispiel: Wenn von 100 tatsächlichen Spam-E-Mails 70 korrekt als Spam erkannt werden, beträgt der Recall 70%.
• F1-Score: Der F1-Score ist das harmonische Mittel aus Präzision und Empfindlichkeit und bietet eine ausgewogenere Metrik als jede für sich genommen. Er wird berechnet als: \begin{equation} \text{F1-Score} = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision + Recall}} \end{equation} Beispiel: Wenn die Präzision 80% und der Recall 70% beträgt, ist der F1-Score: \begin{equation} \text{F1-Score} = 2 \times \frac{0.8 \times 0.7}{0.8 + 0.7} = 2 \times \frac{0.56}{1.5} \approx 0.75 \end{equation}

Empfehlung: Für die Bewertung eines Spam-Filters würde ich den F1-Score bevorzugen, da er einen ausgewogenen Kompromiss zwischen Präzision und Empfindlichkeit darstellt. Dies ist besonders wichtig, weil bei einem Spam-Filter sowohl falsch positive als auch falsch negative Klassifikationen problematisch sein können. Der F1-Score hilft sicherzustellen, dass das Modell sowohl effektiv bei der Erkennung von Spam als auch bei der Minimierung von Fehlalarmen ist.

b)

Beschreibe den Ablauf der k-fachen Kreuzvalidierung. Warum ist diese Technik besonders nützlich für die Abschätzung der Modellleistung?

Lösung:

Die k-fache Kreuzvalidierung ist eine weit verbreitete Technik zur Bewertung der Modellleistung, da sie eine robustere Schätzung der Generalisierungsfähigkeit eines Modells ermöglicht. Hier ist der Ablauf der k-fachen Kreuzvalidierung im Detail beschrieben:

• Schritt 1: Datenaufteilung Die gesamten Daten werden in k gleiche Teile, sogenannte Folds, unterteilt. Typische Werte für k sind 5 oder 10.
• Schritt 2: Iterative Modellbildung Das Modell wird k-mal trainiert und getestet. Dabei wird jedes Mal ein anderer Fold als Testdatensatz und die verbleibenden k-1 Folds als Trainingsdatensatz verwendet.
  • Iteration 1: Fold 1 ist der Testdatensatz, die Folds 2 bis k sind die Trainingsdatensätze.
  • Iteration 2: Fold 2 ist der Testdatensatz, die Folds 1, 3 bis k sind die Trainingsdatensätze.
  • ...
  • Iteration k: Fold k ist der Testdatensatz, die Folds 1 bis k-1 sind die Trainingsdatensätze.
• Schritt 3: Leistungsmessung Für jede der k Iterationen wird die Modellleistung gemessen (z.B. anhand des F1-Scores, der Accuracy, etc.).
• Schritt 4: Durchschnittsbildung Am Ende der k Iterationen werden die Leistungswerte der einzelnen Iterationen gemittelt, um eine Gesamtschätzung der Modellleistung zu erhalten.

Vorteile der k-fachen Kreuzvalidierung

• Robustheit: Durch das mehrfache Trainieren und Testen wird sichergestellt, dass das Modell auf verschiedenen Datenteilen bewertet wird, wodurch die Leistungsbewertung robuster und weniger anfällig für Zufälligkeiten wird.
• Generalisation: Die k-fache Kreuzvalidierung gibt eine bessere Schätzung der Generalisierungsfähigkeit des Modells auf unabhängigen Daten, da jede Datenprobe sowohl als Trainings- als auch als Testdaten verwendet wird.
• Datenverwaltung: Die Technik maximiert die Ausnutzung der verfügbaren Daten, da alle Datenpunkte sowohl für das Training als auch für das Testen verwendet werden (jedoch nicht gleichzeitig).

Durch die Anwendung der k-fachen Kreuzvalidierung erhältst Du eine zuverlässigere Schätzung der Modellleistung, was besonders wichtig ist, wenn Du die Eignung eines Modells für reale Anwendungen, wie beispielsweise einen Spam-Filter, beurteilen möchtest.

c)

Angenommen, du führst eine 5-fache Kreuzvalidierung durch und erhältst die folgenden Fehlerraten nach jedem Durchlauf: 0.15, 0.20, 0.18, 0.22, 0.17. Berechne die geschätzte mittlere Fehlerrate \( \text{CV}_{(k)} \) und interpretiere das Ergebnis.

Lösung:

Die geschätzte mittlere Fehlerrate \( \text{CV}_{(k)} \) bei einer k-fachen Kreuzvalidierung wird berechnet, indem man den Durchschnitt der Fehlerraten aus den k Durchläufen nimmt. In deinem Fall führst du eine 5-fache Kreuzvalidierung durch und hast die folgenden Fehlerraten erhalten: 0.15, 0.20, 0.18, 0.22, 0.17.

• Schritt 1: Aufsummieren der Fehlerraten 0.15 + 0.20 + 0.18 + 0.22 + 0.17 = 0.92
• Schritt 2: Berechnung der geschätzten mittleren FehlerrateDie geschätzte mittlere Fehlerrate \( \text{CV}_{(k)} \) ergibt sich, indem man die Summe der Fehlerraten durch die Anzahl der Durchläufe teilt:\( \text{CV}_{(k)} = \frac{0.92}{5} = 0.184 \)

Interpretation des Ergebnisses:Das Ergebnis zeigt, dass dein Modell im Durchschnitt eine Fehlerrate von 18.4% hat, wenn es auf verschiedene Segmente der Daten angewendet wird. Dies bedeutet, dass im Durchschnitt 18.4% der E-Mails vom Modell falsch klassifiziert werden, sei es als Spam oder Nicht-Spam. Eine niedrigere durchschnittliche Fehlerrate bedeutet eine bessere Modellleistung. Daher zeigt eine Fehlerrate von 18.4%, dass das Modell noch Verbesserungspotenzial hat, um zuverlässiger zwischen Spam und Nicht-Spam zu unterscheiden.

d)

Diskutiere, wie die Verwendung von Kreuzvalidierung dazu beitragen kann, Overfitting zu vermeiden und die Generalisierungsfähigkeit deines Modells zu verbessern. Gib konkrete Beispiele oder Szenarien an.

Lösung:

Die Verwendung von Kreuzvalidierung ist eine bewährte Technik, um Overfitting zu vermeiden und die Generalisierungsfähigkeit eines Modells zu verbessern. Hier sind einige wichtige Punkte, die erläutern, wie Kreuzvalidierung dazu beiträgt:

• Vermeidung von Overfitting: Overfitting tritt auf, wenn ein Modell zu stark auf die Trainingsdaten abgestimmt ist und daher schlecht auf neuen, unbekannten Daten performt. Kreuzvalidierung hilft, Overfitting zu erkennen und zu vermeiden, indem das Modell auf mehreren verschiedenen Teilmengen der Daten getestet wird.
• Robustere Leistungsbewertung: Durch die Aufteilung der Daten in k verschiedene Folds und die Durchführung von k Trainings- und Testdurchläufen wird die Modellleistung auf verschiedenen Datensätzen bewertet. Dies führt zu einer robusteren Schätzung der Modellleistung, da das Modell nicht nur auf eine spezielle Trainings-Test-Aufteilung angewiesen ist.
• Maximale Ausnutzung der Daten: In der k-fachen Kreuzvalidierung wird jede Datenprobe mindestens einmal als Testdaten und mehrmals als Trainingsdaten verwendet. Dies maximiert die Ausnutzung der verfügbaren Daten und ermöglicht eine umfassendere Bewertung des Modells.
• Kennenlernen der Modellvariabilität: Da das Modell auf verschiedene Teilmengen der Daten trainiert und getestet wird, erhältst Du ein besseres Verständnis dafür, wie stabil und verlässlich dein Modell in verschiedenen Szenarien arbeitet. Großer Unterschied zwischen den Durchläufen kann auf Overfitting oder Dateninkonsistenz hinweisen.
• Hyperparameter-Abstimmung: Bei der Optimierung von Hyperparametern kann Kreuzvalidierung helfen, diese Parameter so einzustellen, dass das Modell besser generalisiert und nicht nur gut auf den Trainingsdaten performt.

Konkrete Beispiele/Szenarien:Betrachte die folgenden Szenarien, um den Nutzen der Kreuzvalidierung zu verdeutlichen:

• Szenario 1: Überanpassung an spezifische Trainingsdaten: Ein Modell wird auf einem bestimmten Trainingsdatensatz mit 80% Accuracy getestet. Beim Test auf einer neuen Datenmenge sinkt die Accuracy auf 60%, was auf Overfitting hindeutet. Durch die Anwendung von 5-facher Kreuzvalidierung könnte sich zeigen, dass die mittlere Accuracy nur 65% beträgt, was das Overfitting bestätigt und zeigt, dass eine Anpassung notwendig ist.
• Szenario 2: Vielfalt der E-Mail-Inhalte: Bei der Klassifikation von Spam-E-Mails können unterschiedliche E-Mail-Themen und Sprachstile vorkommen. Kreuzvalidierung sorgt dafür, dass das Modell auf diesen verschiedenen Stilen trainiert wird, indem es verschiedene Teilmengen verwendet. So kann sichergestellt werden, dass das Modell auch bei neuen E-Mails gut performt.
• Szenario 3: Begrenzter Datenumfang: In Fällen, in denen nur eine begrenzte Anzahl von E-Mails zur Verfügung steht, stellt die Kreuzvalidierung sicher, dass die gesamte Datenmenge effektiv zur Modellbewertung genutzt wird. Dies erhöht die Zuverlässigkeit der Leistungsmetriken und reduziert den Einfluss zufälliger Variation.

Zusammengefasst verbessert die Verwendung von Kreuzvalidierung die Generalisierungsfähigkeit, verringert das Risiko des Overfittings und resultiert in einem verlässlicheren und robusteren Modell für die Klassifikation von E-Mails als Spam oder Nicht-Spam.

Aufgabe 3)

Gegeben sei der folgende Datensatz mit fünf Datenpunkten:

 Datenpunkt A: X: 1.0 Y: 2.0 Datenpunkt B: X: 2.0 Y: 1.0 Datenpunkt C: X: 3.0 Y: 4.0 Datenpunkt D: X: 5.0 Y: 7.0 Datenpunkt E: X: 6.0 Y: 8.0 

b)

• Berechne den Silhouettenwert für jeden Datenpunkt basierend auf den Clustern, die Du in der vorherigen Teilaufgabe ermittelt hast. Gib den durchschnittlichen Silhouettenwert für das gesamte Clustering an. Formuliere eine kurze Schlussfolgerung zur Qualität der Clusterung.

Lösung:

Datensatz:

 Datenpunkt A: X: 1.0 Y: 2.0 Datenpunkt B: X: 2.0 Y: 1.0 Datenpunkt C: X: 3.0 Y: 4.0 Datenpunkt D: X: 5.0 Y: 7.0 Datenpunkt E: X: 6.0 Y: 8.0

• Cluster 1: A, B, CZentrum: (2, 2.33)
• Cluster 2: D, EZentrum: (5.5, 7.5)

• \( s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} \)
• wobei:
• \(a(i)\) ist die durchschnittliche Distanz des Punktes zu allen anderen Punkten im selben Cluster
• \(b(i)\) ist die durchschnittliche Distanz des Punktes zum nächsten Cluster

• \(\frac{0.67 + 0.66 + 0.27 + 0.78 + 0.82}{5} \approx 0.64 \)

• Ein durchschnittlicher Silhouettenwert von 0.64 deutet darauf hin, dass die Clusterung ziemlich gut ist.
• Ein Wert von -1 bis +1:- Bei einem Wert näher an +1 sind die Punkte gut innerhalb ihres Clusters gruppiert und weit von anderen Clustern entfernt.- Bei einem Wert näher an -1 sind die Punkte eher falsch gruppiert.- Ein Wert um 0 zeigt überlappende Cluster an.
• In diesem Fall zeigt der Wert, dass die Cluster sinnvoll sind, obwohl es noch Raum für Verbesserungen gibt. Insbesondere der niedrigere Silhouettenwert für Datenpunkt C (0.27) könnte anzeigen, dass dieser Punkt am Rand zwischen zwei Clustern liegt.

c)

• Erstelle ein Dendrogramm für die hierarchische Clusteranalyse des obigen Datensatzes, indem Du die agglomerative Methode verwendest. Beginne mit der vollständigen Linkage-Methode, und zeige die verschachtelten Cluster bei jedem Schritt. Wie viele Cluster würdest Du anhand des Dendrogramms für diesen Datensatz für sinnvoll erachten?

Lösung:

Datensatz:

 Datenpunkt A: X: 1.0 Y: 2.0 Datenpunkt B: X: 2.0 Y: 1.0 Datenpunkt C: X: 3.0 Y: 4.0 Datenpunkt D: X: 5.0 Y: 7.0 Datenpunkt E: X: 6.0 Y: 8.0

• Verwende die agglomerative Methode mit vollständiger Linkage (Maximale Distanz).
• Berechne die euklidischen Distanzen zwischen allen Punkten.
• Führe die Cluster in aufsteigender Reihenfolge der Distanzen zusammen.
• Zeige die verschachtelten Cluster bei jedem Schritt.

• Initiale Distanzen:
  • A - B: \(\sqrt{(2-1)^2 + (1-2)^2} = \sqrt{2} \approx 1.41\)
  • A - C: \(\sqrt{(3-1)^2 + (4-2)^2} = \sqrt{8} \approx 2.83\)
  • A - D: \(\sqrt{(5-1)^2 + (7-2)^2} = \sqrt{41} \approx 6.40\)
  • A - E: \(\sqrt{(6-1)^2 + (8-2)^2} = \sqrt{61} \approx 7.81\)
  • B - C: \(\sqrt{(3-2)^2 + (4-1)^2} = \sqrt{10} \approx 3.16\)
  • B - D: \(\sqrt{(5-2)^2 + (7-1)^2} = \sqrt{45} \approx 6.71\)
  • B - E: \(\sqrt{(6-2)^2 + (8-1)^2} = \sqrt{65} \approx 8.06\)
  • C - D: \(\sqrt{(5-3)^2 + (7-4)^2} = \sqrt{13} \approx 3.61\)
  • C - E: \(\sqrt{(6-3)^2 + (8-4)^2} = \sqrt{25} \approx 5.00\)
  • D - E: \(\sqrt{(6-5)^2 + (8-7)^2} = \sqrt{2} \approx 1.41\)
• Schritt 1: Führe den kürzesten Abstand zusammen:
  • Cluster A, B: Entfernung = 1.41
• Schritt 2: Führe den nächsten kürzesten Abstand zusammen:
  • Cluster D, E: Entfernung = 1.41
• Schritt 3: Führe den nächsten kürzesten Abstand zusammen:\
  • Cluster (A, B) und C: Entfernung = 2.83
• Schritt 4: Führe den nächsten kürzesten Abstand zusammen:
  • Cluster (D, E) und (A, B, C): Entfernung = 5.00
  Dendrogramm:
  Schlussfolgerung: Anhand des Dendrogramms sind zwei Hauptcluster sinnvoll:
  • Cluster 1 umfasst A, B, und C
  • Cluster 2 umfasst D und E

Aufgabe 4)

Ein Roboter befindet sich in einem quadratischen Gitter von 5x5 Feldern, wobei bestimmte Felder Hindernisse darstellen und andere Belohnungen bringen. Der Roboter kann sich in vier Richtungen bewegen: nach oben, unten, links und rechts. Jede Bewegung wird mit einer festen Wahrscheinlichkeit einer zufälligen Bewegung gestört. Ziel ist es, den optimalen Pfad zu einer Zelle mit maximaler Belohnung zu finden. Das Problem kann als Markov-Entscheidungsproblem modelliert werden.

a)

1. Erläutere den Q-Learning Algorithmus und erkläre, wie die Q-Funktion verwendet wird, um den optimalen Pfad zu finden.

Lösung:

1. Erläutere den Q-Learning Algorithmus und erkläre, wie die Q-Funktion verwendet wird, um den optimalen Pfad zu finden.

Q-Learning Algorithmus:

Q-Learning ist ein Modell-freies Verstärkungslernen-Algorithmus, der darauf abzielt, die optimale Aktion-Wert-Funktion (Q-Funktion) zu lernen. Diese Funktion gibt die erwartete Belohnung an, die man erhält, wenn man in einem bestimmten Zustand eine bestimmte Aktion wählt und dann die optimale Strategie verfolgt.

• Initialisierung: Zu Beginn werden alle Q-Werte für alle Zustands-Aktions-Paare auf einen kleinen Wert (oft 0) initialisiert.
• Agent interagiert mit der Umgebung: Der Roboter beginnt in einem zufälligen Zustand und führt die folgenden Schritte für viele Episoden (Durchläufe) aus:
• Wähle eine Aktion aus dem aktuellen Zustand basierend auf einer Strategie (z.B. \(\text{epsilon-greedy}\), wobei der Roboter mit einer kleinen Wahrscheinlichkeit eine zufällige Aktion und ansonsten die Aktion mit dem höchsten Q-Wert wählt).
• Führe die gewählte Aktion aus, bewege dich in den nächsten Zustand und erhalte die Belohnung, die mit dieser Aktion verbunden ist.
• Aktualisiere den Q-Wert für das Zustands-Aktions-Paar mit der folgenden Formel:

  Q(s, a) = Q(s, a) + \alpha * (r + \gamma \max_{a'} Q(s', a') - Q(s, a))

  wobei:
  • \(Q(s, a)\) der Q-Wert für Zustand \(s\) und Aktion \(a\) ist,
  • \(\alpha\) die Lernrate (ein Wert zwischen 0 und 1) ist, der bestimmt, wie stark neue Informationen gegenüber alten Informationen gewichtet werden,
  • \(r\) die Belohnung für das Erreichen des neuen Zustands ist,
  • \(\gamma\) der Diskontierungsfaktor (ein Wert zwischen 0 und 1) ist, der die Wichtigkeit zukünftiger Belohnungen bestimmt,
  • \(\max_{a'} Q(s', a')\) der maximale Q-Wert für den nächsten Zustand \(s'\) über alle möglichen Aktionen \(a'\) ist.
• Setze den neuen Zustand \(s'\) als aktuellen Zustand \(s\) und wiederhole die Schritte, bis ein Endzustand erreicht wird.
• Wiederholen: Diese Schritte werden für viele Episoden wiederholt, bis die Q-Werte konvergieren.

Durch das wiederholte Aktualisieren der Q-Werte lernt der Roboter, welche Aktionen in welchen Zuständen den höchsten erwarteten Belohnungswert haben. Der optimale Pfad kann dann durch das Folgen der Aktionen mit den höchsten Q-Werten in jedem Zustand gefunden werden.

Beispiel: Im gegebenen 5x5-Gitter lernt der Roboter durch Q-Learning, z.B. Hindernisse zu meiden und Belohnungen zu sammeln, indem er die Q-Werte regelmäßig aktualisiert. Wenn die Q-Werte konvergieren, hat der Roboter eine Strategie erlernt, wie er sich durch das Gitter bewegen kann, um den Weg zu einer Zelle mit maximaler Belohnung zu finden.

b)

2. Gegeben seien die Hyperparameter: Lernrate (\alpha = 0.1), Diskontfaktor (\gamma = 0.9) und Entdeckungsrate (\text{epsilon} = 0.2). Schreibe die Q-Wert-Aktualisierungsformel für einen Zustand \(s\) und eine Aktion \(a\). Wenn die aktuelle Belohnung \(R = 10\), der erwartete zukünftige maximale Q-Wert \(max_{a'} Q(s', a') = 80\) ist und der aktuelle Q-Wert \(Q(s, a) = 50\), berechne den neuen Q-Wert.

Lösung:

2. Gegeben seien die Hyperparameter: Lernrate (\(\alpha = 0.1\)), Diskontfaktor (\(\gamma = 0.9\)) und Entdeckungsrate (\(\epsilon = 0.2\)). Schreibe die Q-Wert-Aktualisierungsformel für einen Zustand \(s\) und eine Aktion \(a\). Wenn die aktuelle Belohnung \(R = 10\), der erwartete zukünftige maximale Q-Wert \(\max_{a'} Q(s', a') = 80\) ist und der aktuelle Q-Wert \(Q(s, a) = 50\), berechne den neuen Q-Wert.

Die Aktualisierungsformel für die Q-Werte lautet:

Q(s, a) = Q(s, a) + \alpha (R + \gamma \max_{a'} Q(s', a') - Q(s, a))

Setzen wir die gegebenen Werte in die Formel ein:

• \(\alpha = 0.1\)
• \(\gamma = 0.9\)
• \(R = 10\)
• \(\max_{a'} Q(s', a') = 80\)
• \(Q(s, a) = 50\)

Einsetzen in die Formel:

Q(s, a) = 50 + 0.1 (10 + 0.9 * 80 - 50)

Berechnung Schritt für Schritt:

• Berechnung des diskontierten erwarteten zukünftigen maximalen Q-Werts: \(0.9 * 80 = 72\)
• Berechnung des Unterschieds zwischen der aktuellen Belohnung und dem aktuellen Q-Wert: \(10 + 72 - 50 = 32\)
• Aktualisierung des Q-Werts: \(50 + 0.1 * 32 = 50 + 3.2 = 53.2\)

Der neue Q-Wert lautet daher:

Q(s, a) = 53.2

c)

3. Angenommen, der Roboter startet in der oberen linken Ecke des Gitters (Zellposition (0,0)) und hat die Aufgabe, einen möglichst hohen Belohnungswert zu erreichen. Wie könnte eine geeignete Strategie bei der Wahl der Aktionen aussehen, sodass sowohl eine Exploration des Gitters als auch die Nutzung des angesammelten Wissens erfolgen? Gebe eine Begründung für die Wahl der Strategie.

Lösung:

3. Angenommen, der Roboter startet in der oberen linken Ecke des Gitters (Zellposition (0,0)) und hat die Aufgabe, einen möglichst hohen Belohnungswert zu erreichen. Wie könnte eine geeignete Strategie bei der Wahl der Aktionen aussehen, sodass sowohl eine Exploration des Gitters als auch die Nutzung des angesammelten Wissens erfolgen? Gebe eine Begründung für die Wahl der Strategie.

Eine geeignete Strategie zur Wahl der Aktionen ist die \(\epsilon\)-greedy Strategie. Diese Strategie erlaubt es dem Roboter, sowohl das Gitter zu erkunden (Exploration) als auch das angesammelte Wissen (Exploitation) zu nutzen, um Belohnungen zu maximieren.

\(\epsilon\)-greedy Strategie:

• Mit einer Wahrscheinlichkeit von \(\epsilon\) wählt der Roboter eine zufällige Aktion, um neue Zustände zu erkunden. Dies fördert die Exploration.
• Mit einer Wahrscheinlichkeit von \(1-\epsilon\) wählt der Roboter die Aktion, die den höchsten Q-Wert im aktuellen Zustand hat. Dies nutzt das bisher angesammelte Wissen (Exploitation), um die Belohnungen zu maximieren.

Begründung für die Wahl der Strategie:

• Balance zwischen Exploration und Exploitation: Die \(\epsilon\)-greedy Strategie bietet eine Balance zwischen Exploration und Exploitation. Durch die Zufallsauswahl (Exploration) kann der Roboter neue Zustände entdecken und potenziell bessere Wege finden. Durch die Auswahl der besten bekannten Aktion (Exploitation) kann er seine Belohnung maximieren.
• Vermeidung von lokalem Optimum: Ohne Exploration könnte der Roboter in einem lokalen Optimum gefangen bleiben und bessere Wege übersehen. Die \(\epsilon\)-greedy Strategie stellt sicher, dass der Roboter auch andere Optionen untersucht und somit das Risiko verringert, im lokalen Optimum zu verharren.
• Dynamisches Verhalten: Zu Beginn des Lernprozesses kann \(\epsilon\) hoch gewählt werden, um mehr Exploration zu fördern. Im Laufe der Zeit kann \(\epsilon\) reduziert werden, um mehr Exploitation zu betreiben, da der Roboter nun bereits viel Wissen angesammelt hat.

Zum Beispiel könnte der Roboter mit \(\epsilon = 0.2\) starten. Das bedeutet, dass er in 20% der Fälle eine zufällige Aktion wählt und in 80% der Fälle die beste bekannte Aktion basierend auf den aktuellen Q-Werten. Diese Strategie hilft, sowohl das Gitter zu erkunden als auch das angesammelte Wissen zu nutzen, um den höchsten Belohnungswert zu erreichen.

d)

4. Beschreibe mögliche Probleme, die beim Einsatz von Q-Learning in einem dynamischen Umfeld auftreten können. Welche Anpassungen oder Erweiterungen des Q-Learning Algorithmus könntest Du vorschlagen, um diesen Problemen entgegenzuwirken?

Lösung:

4. Beschreibe mögliche Probleme, die beim Einsatz von Q-Learning in einem dynamischen Umfeld auftreten können. Welche Anpassungen oder Erweiterungen des Q-Learning Algorithmus könntest Du vorschlagen, um diesen Problemen entgegenzuwirken?

Mögliche Probleme im dynamischen Umfeld:

• Veränderliche Umgebung: In dynamischen Umgebungen können sich die Belohnungen oder die Übergangswahrscheinlichkeiten ändern. Dies führt dazu, dass die gelernten Q-Werte veraltet sind und nicht mehr die optimalen Entscheidungen widerspiegeln.
• Langsame Konvergenz: Aufgrund der Änderungen in der Umgebung kann der Q-Learning Algorithmus langsam konvergieren oder gar nicht konvergieren, da er ständig neue Informationen lernen muss.
• Explorationsprobleme: In einer dynamischen Umgebung kann es dazu kommen, dass bekannte Strategien plötzlich nicht mehr optimal sind. Dies erfordert eine kontinuierliche Exploration, um neue optimale Pfade zu finden.

Anpassungen oder Erweiterungen des Q-Learning Algorithmus:

• Decay oder Adaptive Epsilon: Anstatt einen festen \(\epsilon\)-Wert für die \(\epsilon\)-greedy Strategie zu verwenden, kann \(\epsilon\) adaptiv oder mit einem Decay-Faktor angepasst werden, um in dynamischen Umgebungen mehr Exploration zu fördern.
• Q-Wert-Erneuerung (Q-Reset): In regelmäßigen Abständen oder nach Erkennung signifikanter Änderungen in der Umgebung können die Q-Werte zurückgesetzt oder teilweise zurückgesetzt werden, um dem Algorithmus zu ermöglichen, sich besser an die neuen Gegebenheiten anzupassen.
• Experience Replay: Dies ist eine Technik, bei der der Agent seine Erfahrungen speichert und später zufällig aus diesen Erfahrungen lernt. Dadurch wird die Korrelation zwischen aufeinanderfolgenden Erfahrungen reduziert und es ermöglicht dem Algorithmus, Wissen aus der Vergangenheit effektiver zu nutzen.
• Prioritized Experience Replay: Eine Erweiterung des Experience Replay, bei der wichtigere Erfahrungen häufiger wiedergegeben werden. Dies hilft besonders in dynamischen Umgebungen, da der Algorithmus schneller aus kritischen Situationen lernen kann.
• Doppel-Q-Learning: Doppel-Q-Learning verwendet zwei Q-Wert-Sätze, um das Problem der verzerrten Q-Wert-Schätzungen durch Maximierung zu verringern. Dies kann helfen, genauere Q-Werte auch in einer dynamischen Umgebung zu erhalten.
• Deep Q-Learning (DQN): In komplexen dynamischen Umgebungen kann die Verwendung von neuronalen Netzwerken, um die Q-Funktion zu approximieren, Vorteile bieten. DQN kombiniert Q-Learning mit tiefen neuronalen Netzwerken und Techniken wie Experience Replay und fixierten Zielnetzen.
• Kontinuierliche Anpassung: Implementierung von Algorithmen, die kontinuierlich die Änderungen in der Umgebung überwachen und regelmäßig die Q-Werte anpassen, um auf neue Gegebenheiten zu reagieren.

Diese Anpassungen und Erweiterungen können dazu beitragen, die Robustheit und Effizienz des Q-Learning Algorithmus in dynamischen Umgebungen zu erhöhen und sicherzustellen, dass der Roboter auch unter wechselnden Bedingungen optimale Entscheidungen trifft.