Intro: Was ist Künstliche Intelligenz?

Was ist (künstliche) Intelligenz?

Quelle: AvB - RoboCup 2013 - Eindhoven by RoboCup2013 on Flickr.com (CC BY 2.0)

• Was ist (künstliche) Intelligenz?
• Ist Commander Data intelligent?
• Woran erkennen Sie das?

Definition Intelligenz

Intelligenz (von lat. intellegere "verstehen", wörtlich "wählen zwischen ..." von lat. inter "zwischen" und legere "lesen, wählen") ist in der Psychologie ein Sammelbegriff für die kognitive Leistungsfähigkeit des Menschen. Da einzelne kognitive Fähigkeiten unterschiedlich stark ausgeprägt sein können und keine Einigkeit besteht, wie diese zu bestimmen und zu unterscheiden sind, gibt es keine allgemeingültige Definition der Intelligenz.

 Quelle: "Intelligenz" by Cumtempore and others on Wikipedia (CC BY-SA 3.0)

Das ist spannend: Es gibt keine allgemeingültige Definition für den Begriff "Intelligenz". Damit wird es schwierig, auch "Künstliche Intelligenz" zu definieren ...

Aber wir können aus dieser Definition auf Wikipedia mitnehmen, dass es um kognitive Fähigkeiten geht. Verstehen und im weiteren Sinne Denken sind bereits im Begriff enthalten und damit auch Teil der kognitiven Fähigkeiten.

Schauen wir uns nun noch die Definition von "kognitiven Fähigkeiten" genauer an.

Zu den kognitiven Fähigkeiten eines Menschen zählen die Wahrnehmung, die Aufmerksamkeit, die Erinnerung, das Lernen, das Problemlösen, die Kreativität, das Planen, die Orientierung, die Imagination, die Argumentation, die Introspektion, der Wille, das Glauben und einige mehr. Auch Emotionen haben einen wesentlichen kognitiven Anteil.

 Quelle: "Kognition" by Arbraxan and others on Wikipedia (CC BY-SA 3.0)

Zu den kognitiven Fähigkeiten und damit zur Intelligenz zählen also eine Reihe von Fähigkeiten, die man Menschen im allgemeinen zuschreibt. Lernen und Problemlösen und Planen sind Dinge, die vermutlich jeder direkt mit dem Begriff Intelligenz verbindet. Interessanterweise gehören auf auch Aufmerksamkeit und Wahrnehmung und Orientierung mit dazu -- Fähigkeiten, die beispielsweise in der Robotik sehr wichtig sind. Kreativität und Vorstellung zählen aber auch mit in den Bereich der kognitiven Fähigkeiten und damit zum Begriff Intelligenz. In der KI werden diese Gebiete zunehmend interessant, etwa beim Komponieren von Musik und beim Erzeugen von Bildern oder Texten. Mit Emotionen beschäftigt sich die KI-Forschung aktuell nur am Rande, etwa bei der Erkennung von Emotionen in Texten. Andere Gebiete der kognitiven Fähigkeiten wie Glaube und Wille spielen derzeit keine Rolle in der KI.

Versuch einer Definition für "KI"

Ziel der KI ist es, Maschinen zu entwickeln, die sich verhalten, als verfügten sie über Intelligenz.

 -- John McCarthy (1955)

Einwand: Braitenberg-Vehikel zeigen so etwas wie "intelligentes" Verhalten, sind aber noch lange nicht intelligent! Bezieht sich nur auf Verhalten!

KI ist die Fähigkeit digitaler Computer oder computergesteuerter Roboter, Aufgaben zu lösen, die normalerweise mit den höheren intellektuellen Verarbeitungsfähigkeiten von Menschen in Verbindung gebracht werden ...

 -- Encyclopedia Britannica

Einwand: Dann wäre aber auch Auswendig-Lernen oder das Multiplizieren langer Zahlen als intelligent zu betrachten! Bezieht sich vor allem auf "Denken"!

Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better.

 -- Elaine Rich ("Artificial Intelligence", McGraw-Hill, 1983)

Quelle: nach [Ertel2017, pp. 1-3]

Dazu gehört auch

• Anpassung an sich verändernde Situationen
• Erkennung von Bildern und Gesichtern und Emotionen
• Erkennung von Sprache
• Umgang mit kontextbehafteten, unvollständigen Informationen
• Ausräumen von Geschirrspülern ;-)
• Über Emotionen und Empathie verfügen

Alan Turing 1950: Turing-Test (begründet Zweige der KI)

• Wann verhält sich eine Maschine intelligent?

Quelle: Turing Test version 3.png by Bilby on Wikimedia Commons (Public Domain)

Zum Bestehen des Turing-Tests ist (u.a.) erforderlich:

• Wissensrepräsentation: Speichern des gesammelten Wissens => Wissensbasierte Systeme
• Logisches Schließen: Beantworten von Fragen mit Hilfe des vorhandenen Wissens => Logik, Resolution
• Maschinelles Lernen: Anpassung an veränderliches Umfeld => Musteranalyse und Mustererkennung und Mustervorhersage
• Verarbeitung natürlicher Sprache: Erfolgreiche Kommunikation, beispielsweise in Englisch => NLP

"Totaler Turing-Test": zusätzlich Computer Vision (Erkennen von Objekten) und Robotik (Manipulation von Objekten)

Damit begründet der Turing-Test die Gebiete der KI.

Problem: Der Turing-Test ist nicht reproduzierbar, nicht konstruktiv und nicht mathematisch analysierbar ... Außerdem wird durch den Turing-Test im Wesentlichen nur Funktionalität geprüft, nicht ob Intention oder Bewusstsein vorhanden ist.

Starke vs. schwache KI

"Schwache KI"

• Simulation intelligenten Verhaltens
• Lösung konkreter Probleme
• Adaptives Verhalten ("Lernen")
• Umgang mit Unsicherheit und unvollständigen Informationen

"Starke KI"

• Eigenschaften der "schwachen KI"
• Intelligenz nach menschlichen Maßstäben (auf "Augenhöhe")
• Bewusstsein
• Emotionen (?)
• Empathie

Typische Ansätze in der KI

Untersuchung von

• Verhalten vs. Denken
• Rational vs. menschlich

Motivation dabei

• Menschliche Intelligenz verstehen
• Intelligente/intelligent wirkende Systeme bauen

Damit erhält man vier Kombinationen:

• Menschliches Denken
• Rationales Denken
• Rationales Verhalten
• Menschliches Verhalten

Menschliches Denken: Kognitive Modellierung

• Welche kognitiven Fähigkeiten sind für intelligentes Verhalten nötig? Wie laufen Denkprozesse im Gehirn ab?
• Erfordert Theorien über interne Aktivitäten des Gehirns
• Ansätze:
  • top-down: Vorhersage und Test von menschlichem Verhalten
  • bottom-up: Auswertung neurobiologischer Daten
• Wissenschaftszweige: Kognitionswissenschaft (Verbindung der Computermodelle der KI mit den Experimenten und Theorien der Psychologie), Neurobiologie/-informatik

Rationales Denken: Aristoteles: Was sind korrekte Argumente und Denkprozesse? => Wie sollen wir denken?

Beispiel:

Fakt: Sokrates ist ein Mensch.
Fakt: Alle Menschen sind sterblich.
Folgerung: Sokrates ist sterblich.

• Formalisierte Problembeschreibung
• Problemlösung durch logische Prozesse
• Verbindung von moderner KI zur Mathematik und Philosophie

Rationales Verhalten: Das "Richtige" tun

• Das "Richtige": Verhalten zum Erzielen des besten (erwarteten) Ergebnisses (unter Berücksichtigung der verfügbaren Informationen)

  Ein System ist rational, wenn es das seinen Kenntnissen nach "Richtige" macht.

• Denken ist nicht unbedingt notwendig (zb. Reflexe können auch rationales Verhalten sein)

• Interessant: "richtige" Handlung unter unvollständigen/unsicheren Informationen

Menschliches Verhalten: Na ja, Sie wissen schon ;-)

Modelle, Lernen und Vorhersagen

In der Informatik allgemein und auch in der KI versuchen wir, Probleme der realen Welt mit Hilfe von künstlichen Systemen (Algorithmen, Software) zu lösen. Dafür brauchen wir zunächst ein abstraktes mathematisches Modell der Welt, in der wir uns bewegen. Das Modell sollte alle für das zu lösende Problem relevanten Aspekte der Welt repräsentieren - und möglichst nicht mehr als diese, um unnötige Komplexität zu vermeiden. Es kommt häufig vor, dass selbst die relevanten Aspekte zu umfangreich oder teilweise sogar unbekannt sind und nicht vollständig dargestellt werden können. Modelle stellen also eine Abstraktion der echten Welt dar und sind verlustbehaftet. Es gibt viele verschiedene Modelle.

Beispiel: Wir möchten von Bielefeld nach Minden fahren. Neben den offensichtlichen Parametern (Womit wollen wir fahren? Wo genau ist der Startpunkt, wo genau der Zielpunkt? Wann wollen wir fahren?) spielen in der realen Welt unendlich viele Aspekte eine Rolle: Farben, Gerüche, Licht, Beschaffenheit der einzelnen Straßen, exakte Positionen auf der Straße/im Ort ... Sind diese wirklich relevant für dieses Problem? Am Ende wird es wichtig sein, eine abstrakte Darstellung zu finden, die irgendwie die Städte und Dörfer repräsentiert und die Verbindungen dazwischen. Und vermutlich muss ich wissen, wie lang die Strecken jeweils sind (oder wie lange ich brauche oder wieviel Geld mich das Abfahren kostet). Es scheint also so zu sein, dass eine Abstraktion des Problems als Graph sinnvoll ist: Die Knoten entsprechen den Orten, die Kanten den Straßen (oder Bahnlinien o.ä.). An den Kanten sind Kosten annotiert (Kilometer, Zeit, ...). Damit ignorieren wir die Komplexität der realen Welt und fokussieren uns auf die Aspekte, die zur Lösung des Problems wichtig sind. Behalten Sie im Gedächtnis, dass unser Modell verlustbehaftet ist und wir damit tatsächlich nur das Wegeproblem lösen können! Wenn wir Wege vergessen haben oder falsch bewertet haben, wird unser Algorithmus später möglicherweise nicht die gewünschte Lösung finden! Wir schauen uns das Thema Modellierung am Beispiel des Problemlösens und insbesondere für Suchprobleme in der Lektion Problemlösen noch genauer an.

Ein Modell kann Parameter haben. Im obigen Beispiel wären dies die Werte an den Kanten. Es kann sein, dass diese Werte nicht im Vorfeld bekannt sind, sondern aus einem Datensatz extrahiert werden müssen. Dies nennt man Lernen: Das Modell wird (besser gesagt: die Parameter des Modells werden) an das Problem angepasst. Dafür gibt es unterschiedliche Algorithmen. In der Regel benötigt man ein Ziel für den Adaptionsprozess: eine sogenannte Ziel- oder Kostenfunktion. Anpassen der Modellparameter mit Hilfe von Daten und einer Zielfunktion bedeutet auch, dass man das Ziel möglicherweise nie zu 100% erreicht, sondern nur in die Nähe kommt. Je nach Problem kann man auch nur eine Modellfamilie vorgeben und den konkreten Aufbau des Modells im Trainingsprozess erarbeiten lassen.

Wichtig: Lernen bietet sich immer dann an, wenn eine analytische Lösung nicht möglich ist (fehlende Informationen, Komplexität des Problems). Das bedeutet im Umkehrschluss aber auch: Wenn eine analytische Lösung bekannt ist (oder zu finden ist), dann gibt es keinen Grund für den Einsatz von adaptiven Systemen!

Mit dem Modell der Welt kann nun das Problem gelöst werden. Dazu wird das Modell mit Daten versorgt (im obigen Beispiel: Start und Ziel) und ein passender Algorithmus kann auf dem Modell die Lösung berechnen. Dies kann eine Vorhersage sein, welchen Weg ich nehmen soll, wie lange es dauern wird, welchen Spielzug ich als nächstes machen sollte, ob in einem Bild eine Katze zu sehen ist, ... Es könnte aber auch im Fall von sogenannten generativen Modellen ein erzeugter Text oder ein erzeugtes Bild sein.

Hinweis: In manchen Quellen wird dieser Vorgang auch "Inferenz" genannt. Da dieser Begriff aus der Logik stammt und mit bestimmten Prozessen zur Schlussfolgerung verbunden ist, möchte ich in diesem Skript diesen Begriff nicht für das Generieren einer Vorhersage nutzen.

Modellkomplexität

In der KI werden sehr unterschiedliche Modelle betrachtet, die auch eine sehr unterschiedliche Komplexität aufweisen.

Besonders einfache Modelle sind Modelle, die für einen Input direkt einen Output berechnen. Für jeden Input wird eine feste Berechnung durchgeführt, es erfolgt kein Backtracking und es gibt keine (inneren) Zustände. Dies ähnelt dem reflexartigen Verhalten in biologischen Vorbildern, weshalb diese Modell oft auch "reflex-based models" genannt werden. In diese Kategorie fallen beispielsweise lineare Regression und das Perzeptron, aber auch Modelle mit vielen Parametern wie ein Multilagen-Perzeptron (MLP) oder die daraus abgeleiteten Deep Neural Networks.

In der nächst komplexeren Stufe haben die Modelle einen internen Zustand ("state-based models"). Darüber wird ein Zustand der betrachteten Welt modelliert. Zwischen den Zuständen gibt es Übergänge (sogenannte Aktionen), so dass sich hier ein Graph aufspannt (der sogenannte Problemgraph, vgl. Problemlösen). In diese Klasse fallen die typischen Suchprobleme (wie Breitensuche, Tiefensuche, A*), aber auch Spiele mit Zufallskomponente oder mit gegnerischen Mitspielern.

Noch eine Stufe komplexer sind Modelle mit Variablen ("variable-based models"). Während es bei den zustandsbasierten Modellen immer (auch) um den Weg zwischen den Zuständen geht und damit um eine prozedurale Beschreibung, wie von einem Startzustand zu einem Zielzustand zu gelangen ist, steht bei Modellen mit Variablen nur die Lösung im Vordergrund: Das Modell enthält verschiedene Variablen, denen ein passender Wert aus einem Wertebereich zugeordnet werden muss. Wie diese Belegung entsteht, ist am Ende nicht mehr so interessant. Denken Sie beispielsweise an ein Sudoku oder die Erstellung eines Stundenplans. Die Variablen sind entsprechend die einzelnen Felder, gesucht ist eine insgesamt korrekte Belegung aller Felder. In diese Klasse fallen Constraint Satisfaction Probleme (CSP), aber auch Bayes'sche Netze und die sogenannte “lokale Suche”.

Auf der höchsten Komplexitätsstufe stehen logische Modelle. Hier wird Wissen über die Welt in Form von Fakten und Regeln modelliert, und über eine entsprechende Anfrage wird daraus mit Hilfe von formal definierten Beweisen eine korrekte Antwort generiert. Dies nennt man auch "Inferenz". Hier kommt beispielsweise das Prädikatenkalkül zum Einsatz oder die Programmiersprache Prolog.

Kurzer Geschichtsüberblick -- Wichtigste Meilensteine

• 1943: McCulloch/Pitts: binäres Modell eines Neurons
• 1950: Turing-Test
• 1956: Dartmouth Workshop (Minsky, McCarthy, ...) -- McCarthy schlägt den Begriff "Artificial Intelligence" vor
• 1960er: Symbolische KI (Theorembeweiser), Blockwelt, LISP
• 1970er: Wissensbasierte System (Expertensysteme)
• 1980er: zunächst kommerzieller Erfolg der Expertensysteme, später Niedergang ("KI-Eiszeit"); Zuwendung zu Neuronalen Netzen
• 1990er: Formalisierung der KI-Methoden, Einführung probabilistischer Methoden (Bayes'sches Schließen), verstärkte mathematische Fundierung
• heute: friedliche Koexistenz verschiedener Paradigmen und Methoden; Rückkehr zu "Human-Level AI" (McCarthy, Minsky, Nilsson, Winston); Rückkehr zu Neuronalen Netzen (CNN/RNN)

Siehe auch Abbildung 1.3 in [Ertel2017, S.8] ...

Wrap-Up

• Definition von "Intelligenz" nicht ganz einfach
• Dimensionen: Denken vs. Verhalten, menschlich vs. rational
• Ziele der KI: Verständnis menschlicher Fähigkeiten, Übertragen auf künstliche Systeme

Schauen Sie sich zur Einführung auch gern das YouTube-Video Overview Artificial Intelligence Course | Stanford CS221 an. (Vorsicht: Das ist recht lang.)

Problemlösen

Motivation: Roboter in einer Bibliothek

Aufgabe: Das Buch aus der Bibliothek holen und in den Kopiererraum bringen.

Bemerkungen zur Umwelt:

• Beobachtbarkeit der Umwelt kann variieren: "voll beobachtbar" bis zu "unbeobachtbar"
• Umwelt kann "deterministisch" oder "stochastisch" sein: Führt eine Aktion in einem Zustand immer zum selben Folgezustand?
• Wann erfolgt die Rückmeldung an den Agenten über die Auswirkung der Aktionen? Sofort ("sequentiell") oder erst am Ende einer Aktionsfolge ("episodisch")?
• Wird die Umwelt nur durch die Aktionen des Agenten verändert ("statisch")? Oder verändert sich die Umwelt zwischen den Aktionen eines Agenten, beispielsweise durch andere Agenten ("dynamisch")?
• Gibt es diskrete Zustände (wie im Beispiel)?

Zustände der Bibliotheks-Welt

Problem: Gegeben einen Startzustand, wie komme ich zum Ziel?

• Welche Aktionen können in einem Zustand (zb. Nr. 4) angewendet werden?
• Welche Aktionen können in den Folgezuständen angewendet werden?

Ergebnis:

• Zustandsraum: Menge aller von den Startzuständen aus erreichbaren Zustände
• Problemgraph: Repräsentation der Zustände und Aktionen als Knoten und (gerichtete) Kanten

Suche im Problemgraphen

• Durch die Suche im Problemgraphen wird ein Suchbaum aufgespannt
• Varianten: Zustände können in einem Pfad wiederholt vorkommen vs. Wiederholungen werden ausgeschlossen

Definition Zustand und Aktion

Zustand:

(Formale) Beschreibung eines Zustandes der Welt

Aktion:

(Formale) Beschreibung einer durch Agenten ausführbaren Aktion

• Anwendbar auf bestimmte Zustände
• Überführt Welt in neuen Zustand ("Nachfolge-Zustand")

Geeignete Abstraktionen wählen für Zustände und Aktionen!

Anmerkung: [Russell2020] unterscheidet zw. Aktionen und Transitionsmodell; hier nur Aktionen! D.h. die Aktionen und das Übergangsmodell aus dem [Russell2020] werden direkt zusammen betrachtet. Bei den hier diskutierten Problemen ist das ohne Nachteile möglich, es wird lediglich etwas Flexibilität genommen bzw. Komplexität vermieden (je nach Sichtweise :-) ...

Definition Problem

Ein Problem besteht aus:

Startzustände

Menge $S_A \subset S$

Aktionen

Menge von Funktionen $\operatorname{op}: S \to S$

Zustandsraum

Menge aller Zustände $S$, die durch (wiederholte) Anwendung von Aktionen von den Startzuständen aus erreichbar sind

Zieltest

Funktion $\operatorname{goal}: S \to \{0,1\}$

Zielzustände

Menge $S_E \subseteq S$ mit $\forall x \in S_E : \operatorname{goal}(x)=1$

Kosten

Gesamtkosten: $f(n) = g(n) + h(n)$

• $n \in S$ auf dem aktuellen Weg erreichter Knoten
• $g(n)$ tatsächliche Kosten für den Weg vom Start bis zu Knoten $n$
• $h(n)$ geschätzte Restkosten für den Weg von Knoten $n$ zum Ziel

Hinweis: Unterschied Zustand und Knoten bzw. Zustandsraum und Problemgraph

• Zustände und Aktionen kann man als einen Graph darstellen: Problemgraph
  • Zustände werden als Knoten im Graphen abgebildet
  • Aktionen werden als (gerichtete) Kanten im Graphen abgebildet
• Unterscheidung "Zustand" und "Knoten":
  • Zustand: Beschreibung/Modellierung eines Zustandes der Welt
  • Knoten: Datenstruktur, Bestandteil des Graphen, symbolisiert einen Zustand

Das bedeutet, dass der Problemgraph eine Repräsentation des Zustandsraumes ist.

Die beiden Begriffe werden normalerweise synonym verwendet, sofern eindeutig ist, was gemeint ist.

Definition Problemlösen

Problemlösen

Wegesuche im Graph vom Startknoten zu einem Zielknoten

• Spannt den Suchbaum auf

Lösung

Folge von Aktionen, die Start- in Zielzustand überführen

Ergebnis des Problemlösens

Suche: Einfache Basisvariante

1. Füge Startknoten in leere Datenstruktur (Stack, Queue, ...) ein
2. Entnehme Knoten aus der Datenstruktur:
   • Knoten ist gesuchtes Element: Abbruch, melde "gefunden"
   • Expandiere alle Nachfolger des Knotens und füge diese in die Datenstruktur ein
3. Falls die Datenstruktur leer ist: Abbruch, melde "nicht gefunden"
4. Gehe zu Schritt 2

Für die in dieser Veranstaltung betrachteten deterministischen Probleme mit diskreten Zuständen ist diese Basisvariante der Suche eine Art generischer Suchalgorithmus: Durch die Variation der eingesetzten Datenstruktur und durch die Betrachtung unterschiedlicher Kosten erhält man die in den nächsten Sitzungen betrachteten verschiedenen klassischen Suchalgorithmen.

Anmerkung: Für Handsimulation besserer Überblick, wenn statt der Knoten immer partielle Wege in Datenstruktur gespeichert werden!

Anmerkung: Im [Russell2020, Abschnitt 3.3.3, S.92] wird ein Algorithmus mit den vorgestellten Eigenschaften als "tree-like search" bezeichnet. In Anlehnung an [Russell2020] wird diese Basisvariante der Suche in dieser Lehrveranstaltung kurz als "Tree-Search"-Algorithmus bezeichnet.

Anmerkung: Im [Russell2020] wird für die Datenstruktur, mit der die Suche arbeitet, auch "Frontier" genannt. Hier werden alle Knoten gehalten, die in einem der nächsten Schritte betrachtet werden sollen, d.h. diese Knoten bilden die Grenze zwischen dem bereits untersuchten Teil des Graphen und dem noch unbekannten Teil des Graphen (deshalb auch "Frontier").

Erweiterung der Suche: Vermeiden von Wiederholungen

1. Füge Startknoten in leere Datenstruktur (Stack, Queue, ...) ein
2. Entnehme Knoten aus der Datenstruktur:
   • Knoten ist gesuchtes Element: Abbruch, melde "gefunden"
   • Markiere aktuellen Knoten, und
   • Expandiere alle Nachfolger des Knotens und füge alle unmarkierten Nachfolger, die noch nicht in der Datenstruktur sind, in die Datenstruktur ein
3. Falls die Datenstruktur leer ist: Abbruch, melde "nicht gefunden"
4. Gehe zu Schritt 2

Dieser Algorithmus ist eine Erweiterung der einfachen Basisvariante der Suche:

1. Man markiert bereits besuchte (expandierte) Knoten und besucht diese nie wieder (man würde diese bei einer Expansion nicht wieder in die Datenstruktur aufnehmen).
2. Außerdem vermeidet man, dass ein Knoten mehrfach in der Datenstruktur vorkommt: Dies würde bedeuten, dass man hier verschiedene Wege vom Start zu diesem Knoten in der Datenstruktur hat, die dann auch alle weiter untersucht werden müssten. In der Regel reicht aber ein Weg vom Start zu einem Zwischenknoten (meist wird der kürzeste genommen, dazu in einer späteren Sitzung mehr).

Anmerkung: Für Handsimulation besserer Überblick, wenn statt der Knoten immer partielle Wege in Datenstruktur gespeichert werden!

Anmerkung: Im [Russell2020, Abschnitt 3.3.3, S.92] wird ein Algorithmus mit den vorgestellten Eigenschaften als "graph search" bezeichnet. In Anlehnung an [Russell2020] wird diese erweiterter Variante der Suche in dieser Lehrveranstaltung kurz als "Graph-Search"-Algorithmus bezeichnet.

Bewertung von Suchalgorithmen

Vollständigkeit

Findet der Algorithmus eine Lösung, wenn es eine gibt?

Optimalität

Findet der Algorithmus die beste Lösung?

Zeitkomplexität

Wie lange dauert es eine Lösung zu finden?

Speicherkomplexität

Wieviel Speicher benötigt die Suche?

Größen zur Bewertung:

• b: Verzweigungsfaktor
• d: Ebene (Tiefe) des höchsten Lösungsknotens
• m: Länge des längsten Pfades

Wrap-Up

• Begriffe "Problem", "Zustand", "Aktion", "Zustandsraum", "Problemgraph", "Suchbaum"

• Problemlösen: Suche in Graphen nach Weg vom Start zum Ziel

  • Suche spannt einen Suchbaum auf
  • Unterschiedliche Kostenfunktionen möglich
  • Suchalgorithmen: Einfache Basisvariante, Erweiterung mit Vermeidung von Redundanzen
  • Beurteilung der Suchverfahren: Optimalität, Vollständigkeit, Komplexität

Machine Learning 101

Was ist Lernen?

Verhaltensänderung eines Agenten in Richtung der Optimierung eines Gütefunktionals (Bewertungsfunktion) durch Erfahrung.

Warum Lernen?

• Nicht alle Situationen vorhersehbar
• Nicht alle Details modellierbar
• Lösung oder Lösungsweg unbekannt, nicht explizit programmierbar
• Data Mining: Entdeckung neuen Wissens durch Analyse der Daten
• Selbstanpassende Programme

=> Lernen wichtige Eigenschaft lebender Wesen :-)

Learning Agent

Feedback während des Lernens

• Überwachtes Lernen

  • Lernen durch Beobachtung
  • Vorgabe von Beispielen: Ein- und Ausgabewerte

  => Regression, Klassifikation

• Unüberwachtes Lernen

  • Erkennen von Mustern in den Inputdaten, Clustering
  • Kein Feedback (!)

• Reinforcement Lernen

  • Bewertung der Aktionen des Agenten am Ende einer Aktionsfolge

Beispiel Kleinkind: Lernen von Klassen/Konzepten durch Beispiele

• Zuerst ist alles "Katze" (Übergeneralisierung)
• Differenzierung durch Feedback der Umwelt; Erkennung unterschiedlicher Ausprägungen

Beispiel: Kreditrisiko

• Bankkunde beantragt Kredit

• Soll er aus Sicht der Bank den Kredit bekommen?

• Bankangestellter betrachtet (relevante) Merkmale des Kunden:

  • Alter, Einkommen, sozialer Status
  • Kundenhistorie bei der Bank
  • Höhe des Kredits

• Bewertung des Kreditrisikos:

  • Klassifikation: Guter oder schlechter Kunde (Binäre Entscheidung: 2 Klassen)
  • Regression: Vorhersage Gewinn/Verlust für die Bank (Höhe des Gewinns/Verlusts interessant)

Beispiel: Autoreparatur

• Gegeben: Eigenschaften eines Autos

  => Eigenschaften: Ausprägungen der Merkmale

• Gesucht: Diagnose und Reparaturanleitung

  => Hypothese über den Merkmalen (Funktion $\operatorname{h}$)

Lernen durch Beobachten: Lernen einer Funktion $\operatorname{f}$

Funktionsapproximation: Lernen einer Funktion $\operatorname{f}$ anhand von Beispielen

• Ein Beispiel ist ein Tupel $(\mathbf{x}, \operatorname{f}(\mathbf{x}))$, etwa $$ (\mathbf{x}, \operatorname{f}(\mathbf{x})) = \left(\begin{array}{ccc} O & O & X \\ . & X & . \\ X & . & . \end{array}, +1\right) $$

• Aufgabe: Baue Hypothese $\operatorname{h}$ auf, so dass $\operatorname{h} \approx \operatorname{f}$.

  • Benutze dazu Menge von Beispielen => Trainingsdaten.

• Ziele:

  1. Konsistente Hypothese: Übereinstimmung bei Trainingsdaten
  2. Generalisierende Hypothese: Korrekte Vorhersage bei unbekannten Daten

Anmerkung: Stark vereinfachtes Modell realen Lernens!

Konstruieren einer konsistenten Hypothese

Welcher Zusammenhang ist hier dargestellt? Offenbar eine Art Funktionsverlauf ... Wir haben für einige x-Werte die zugehörigen y-Werte vorgegeben.

Konstruieren einer konsistenten Hypothese (cnt.)

Die einfachste Approximation wäre eine lineare Funktion. Allerdings werden hierbei einige Werte mehr oder weniger stark nicht korrekt widergegeben, d.h. man hat einen relativ hohen (Trainings-) Fehler.

Konstruieren einer konsistenten Hypothese (cnt.)

Die Hyperbel erklärt die Trainingsdaten bis auf den einen Punkt sehr gut. Die Frage ist, ob dieser eine Punkt zum zu lernenden Zusammenhang gehört oder ein Ausreißer ist, den man gefahrlos ignorieren kann?

Konstruieren einer konsistenten Hypothese (cnt.)

Die grüne Hypothese ist von allen bisher gezeigten die komplexeste, erklärt aber alle Datenpunkte. D.h. hier wäre der Trainingsfehler Null. Zwischen den Trainingsdaten zeigt das Modell eine "glatte" Approximation, d.h. es wird auch neue Daten, die es beim Training nicht gesehen hat, relativ gut erklären. (Dabei liegt freilich die Annahme zugrunde, dass alle relevanten Daten in der Trainingsmenge vorhanden sind, d.h. dass es insbesondere zwischen den Datenpunkten keine Ausreißer o.ä. gibt.)

Konstruieren einer konsistenten Hypothese (cnt.)

Diese Hypothese erklärt ebenfalls sämtliche Trainingsdaten. Allerdings schwingt die Funktion zwischen den Daten stark hin und her. Vermutlich entspricht dies nicht dem zu lernenden Funktionsverlauf. Der Trainingsfehler wäre wie bei der deutlich einfacheren Hypthese aus dem letzten Schritt Null. Der Generalisierungsfehler (sprich die Abweichung, wenn man das Modell nach Daten zwischen den Trainingspunkten fragt) dürfte erheblich höher liegen.

D.h. hier hat das Modell einfach die Trainingsdaten auswendig gelernt, aber nicht den Zusammenhang zwischen den Daten! Dies ist in der Regel unerwünscht!

Occam's Razor

Bevorzuge die einfachste konsistente Hypothese!

1. Wenn es mehrere mögliche Erklärungen für einen Sachverhalt gibt, ist die einfachste Erklärung allen anderen vorzuziehen.
2. Eine Erklärung ist "einfach", wenn sie möglichst wenige Variablen und Annahmen enthält und wenn diese in klaren logischen Beziehungen zueinander stehen, aus denen der zu erklärende Sachverhalt logisch folgt.

Trainingsdaten und Merkmalsvektoren

Lehrer gibt Beispiele vor: Eingabe $\mathbf{x}$ und passende Ausgabe $\operatorname{f}(\mathbf{x})$

• Ausgabe: typischerweise Skalar (Funktionswert oder Klasse) => Beispiel: Bewertung eines Spielstandes bei TicTacToe

• Eingabe: (Beschreibung des) Objekt(s) oder Situation, die zur Ausgabe gehört => Beispiel: Spielstand bei TicTacToe

Merkmalsvektoren:

• Zusammenfassen der relevanten Merkmale zu Vektoren

Beispiel: Schwimmen im See

Beschreibung der Faktoren, wann ich im See schwimmen möchte:

1. Scheint die Sonne?
2. Wie warm ist das Wasser?
3. Wie warm ist die Luft?

• Trainingsbeispiel:
  • Eingabe: Merkmalsvektor (sonnig, warm, warm)
  • Ausgabe: Klasse ja

Dabei wird davon ausgegangen, dass jeder Faktor (jedes Merkmal) an einer bestimmten Stelle im Merkmalsvektor aufgeführt ist. Beispielsweise gehört das sonnig zur Frage "Scheint die Sonne", warm jeweils zur Wasser- und zur Lufttemperatur.

Damit hat man in einem Vektor eine Situation komplett beschrieben, d.h. einen Zustand der Welt mit den relevanten Dingen beschrieben. Diesem Zustand kann man beispielsweise ein Label (Klasse) verpassen, hier in diesem Fall "ja, in dieser Welt möchte ich schwimmen".

Die Trainingsmenge baut sich dann beim überwachten Lernen aus vielen solcher Paare (Merkmalsvektor, Klasse) auf, und die Algorithmen sollen diese Zuordnung lernen, d.h. ein Modell für diese Daten erzeugen, welches die Daten gut erklärt und darüber hinaus für neue Daten aus der selben Datenquelle gute Vorhersagen macht.

Trainingsdaten -- Merkmalsvektoren

Generell: Merkmalsvektor für Objekt $v$: $$ \mathbf{x}(v) = (x_1, x_2, \ldots, x_n) $$

• $n$ Merkmale (Attribute)
• Attribut $x_t$ hat $m_t$ mögliche Ausprägungen
• Ausprägung von $v$ bzgl. $x_t$: $\quad x_t(v) = i \quad$ (mit $i = 1 \ldots m_t$)

Anmerkung: Stellen Sie sich den Merkmalsvektor vielleicht wie einen Konstruktor einer Klasse x vor: Die einzelnen Attribute $x_t$ sind die Parameter, aus denen der Merkmalsvektor aufgebaut ist/wird. Jedes der Attribute hat einen Typ und damit eine bestimmte Anzahl erlaubter Werte ("Ausprägungen") ...

Trainingsbeispiel:

• Tupel aus Merkmalsvektor und zugehöriger Klasse: $\left(\mathbf{x}(v), k\right)$

Wrap-Up

• Lernen ist Verhaltensänderung, Ziel: Optimierung einer Gütefunktion

  • Aufbau einer Hypothese, die beobachtete Daten erklären soll
  • Arten: Überwachtes Lernen, Unüberwachtes Lernen, Reinforcement Lernen

• Merkmalsvektoren gruppieren Eigenschaften des Problems bzw. der Objekte

• Trainingsdaten: Beispielobjekte (durch Merkmalsvektoren beschrieben) plus Vorgabe vom Lehrer

CAL2

Entscheidungsbäume: Klassifikation

• Attribute als Knoten im Baum
• Ausprägungen als Test (Ausgang, Verzweigung)
• Klasse (Funktionswert) als Blatt

Erinnern Sie sich an das Beispiel mit der Auto-Reparatur aus der letzten Sitzung.

Die relevanten Eigenschaften (Merkmale) eines Autos würden als Knoten im Baum repräsentiert. Beispiel: "Motor startet" oder "Farbe".

Jedes Merkmal hat eine Anzahl von möglichen Ausprägungen, diese entsprechen den Verzweigungen am Knoten. Beispiel: "startet", "startet nicht" oder "rot", "weiß", "silber", ... .

Entsprechend kann man durch Abarbeiten des Entscheidungsbaumes am Ende zu einer Diagnose gelangen (Klasse).

Eine andere Sichtweise ist die Nutzung als Checkliste für eine Reparatur ...

Definition Entscheidungsbaum

• Erinnerung: Merkmalsvektor für Objekt $v$: $$ \mathbf{x}(v) = (x_1, x_2, \ldots, x_n) $$

  • $n$ Merkmale (Attribute)
  • Attribut $x_t$ hat $m_t$ mögliche Ausprägungen
  • Ausprägung von $v$ bzgl. $x_t$: $\quad x_t(v) = i \quad$ (mit $i = 1 \ldots m_t$)

• Alphabet für Baum: $$ \lbrace x_t | t=1,\ldots,n \rbrace \cup \lbrace \kappa | \kappa = \ast,A,B,C,\ldots \rbrace \cup \lbrace (,) \rbrace $$

• Entscheidungsbaum $\alpha$: $$ \alpha = \left\lbrace \begin{array}{ll} \kappa & \text{Terminalsymbole: } \kappa = \ast,A,B, \ldots\\ x_t(\alpha_1, \alpha_2, \ldots, \alpha_{m_t}) & x_t \text{ Testattribut mit } m_t \text{ Ausprägungen} \end{array}\right. $$

Anmerkung: Stellen Sie sich die linearisierte Schreibweise wieder wie den (verschachtelten) Aufruf von Konstruktoren vor. Es gibt die Oberklasse Baum, von der für jedes Attribut eine Klasse abgeleitet wird. D.h. der Konstruktor für eine Attributklasse erzeugt letztlich ein Objekt vom Obertyp Baum. Außerdem sind die Terminalsymbole A, B, ... Objekte vom Typ Blatt, welches eine Unterklasse von Baum ist ...

Dabei wird die Anzahl der möglichen Ausprägungen für ein Attribut berücksichtigt: Jede Ausprägung hat einen Parameter im Konstruktor. Damit werden die Unterbäume beim Erzeugen des Knotens übergeben.

Induktion von Entscheidungsbäumen: CAL2

1. Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)

2. $n$-ter Lernschritt: Objekt $v$ mit Klasse $k$, Baum $\alpha^{(n-1)}$ gibt $\kappa$ aus

   • $\kappa = \ast$: ersetze $\ast$ durch $k$
   • $\kappa = k$: keine Aktion nötig
   • $\kappa \neq k$: Fehler
     • Ersetze $\kappa$ mit neuem Test: $\kappa \gets x_{t+1}(\ast, \ldots, \ast, k, \ast, \ldots, \ast)$
     • $x_{t+1}$: nächstes Attribut, auf dem aktuellen Pfad noch nicht verwendet
     • Symbol $k$ an Position $i$ wenn $x_{t+1}(v) = i$

$\alpha^{(n)}$ bezeichnet den Baum im $n$-ten Lernschritt.

CAL2 ist ein Meta-Algorithmus: Es ist ein Algorithmus, um einen Algorithmus zu lernen :-)

Beispiel mit CAL2

Ergebnis: $x_1(x_2(A, B), x_2(A, B))$

Anmerkung: Denken Sie an die Analogie von oben. $x_1$ kann als Konstruktor einer Klasse x1 betrachtet werden, die eine Unterklasse von Baum ist. Durch den Aufruf des Konstruktors wird als ein Baum erzeugt.

Es gibt in $x_1$ zwei mögliche Ausprägungen, d.h. der Baum hat in diesem Knoten zwei alternative Ausgänge. Diese Unterbäume werden dem Konstruktor von x1 direkt beim Aufruf übergeben (müssen also Referenzen vom Typ Baum sein).

CAL2: Bemerkungen

• Nur für diskrete Merkmale und disjunkte Klassen

• Zyklischer Durchlauf durch Trainingsmenge

• Abbruch:

  • Alle Trainingsobjekte richtig klassifiziert => Kein Fehler in einem kompletten Durchlauf
  • (Differenzierung nötig, aber alle Merkmale verbraucht)
  • (Lernschrittzahl überschritten)

Wrap-Up

• Darstellung der Hypothese als Entscheidungsbaum
• CAL2: diskrete Attribute, disjunkte Klassen

Pruning

Pruning: Bedingt irrelevante Attribute

Baum: $\alpha = x_1(x_2(A, B), x_2(A, B), x_2(A, B))$

$x_1$ ist bedingt irrelevant => Vereinfachung: $\alpha = x_2(A, B)$

Allgemein:

• Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
• Baum dort $\alpha/\tilde{x} = x_t(\alpha_1, \ldots, \alpha_{m_t})$
• $x_t$ ist bedingt irrelevant unter der Bedingung $\tilde{x}$, wenn $\alpha_1 = \alpha_2 = \ldots = \alpha_{m_t}$
• Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_1$

Anmerkung: Der durch das Entfernen von bedingt irrelevanten Attributen entstandene Baum hat exakt die selbe Aussage (Klassifikation) wie der Baum vor dem Pruning.

Anmerkung: $x_1$ im obigen Beispiel ist sogar global irrelevant, da es sich hier um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall der leere Weg ...

Pruning: Bedingt redundante Attribute

Baum: $\alpha = x_1(\ast, \ast, x_2(A, B))$

$x_1$ ist bedingt redundant => Vereinfachung: $\alpha = x_2(A, B)$

Allgemein:

• Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
• Baum dort $\alpha/\tilde{x} = x_t(\ast, \ldots, \ast, \alpha_i, \ast, \ldots, \ast)$ (mit $\alpha_i \neq \ast$)
• $x_t$ ist bedingt redundant unter der Bedingung $\tilde{x}$
• Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_i$

Anmerkung: Der durch das Entfernen von bedingt redundanten Attributen entstandene Baum hat eine etwas andere Klassifikation als der Baum vor dem Pruning. Wo vorher ein * ausgegeben wurde, wird nach dem Pruning u.U. ein Klassensymbol ausgegeben. Der Klassifikationsfehler erhöht sich aber nicht, da hier ein * wie ein falsches Klassensymbol zu werten ist.

Anmerkung: $x_1$ im obigen Beispiel ist sogar global redundant, da es sich hier um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall der leere Weg ...

Allgemeine Transformationsregel

Wrap-Up

• Pruning: Entfernen bedingt redundanter und irrelevanter Tests
• Transformationsregel zum Umbauen von Entscheidungsbäumen

CAL3

CAL3: Erweiterung von CAL2 für nicht-disjunkte Klassen

1. Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)

2. $n$-ter Lernschritt: Objekt $v$ mit Klasse $k$

   • Rückweisung (Endknoten mit $\ast$): Ersetze $\ast$ durch Vereinigungsklasse $/k1/$

   • Endknoten mit Vereinigungsklasse:

     • Zähler für $k$ erhöhen, bzw.
     • $k$ mit Anzahl $1$ in Vereinigungsklasse einfügen

   Falls nun die Summe aller Klassen am Endknoten größer/gleich $S_1$ (Statistikschwelle):

   • Für genau eine Klasse gilt: $P(k | \tilde{x}) \ge S_2$: => Abschluss: Ersetze Vereinigungsklasse durch $k$ (für immer!)

   • Für alle Klassen gilt: $P(k | \tilde{x}) < S_2$: => Differenzierung: Ersetze Vereinigungsklasse durch neuen Test: $\kappa \gets x_{t+1}(\ast, \ldots, \ast, /k1/, \ast, \ldots, \ast)$

     $x_{t+1}$: nächstes Attribut, auf dem aktuellen Pfad $\tilde{x}$ noch nicht verwendet Symbol $k$ mit Anzahl 1 an Position $i$ wenn $x_{t+1}(v) = i$

Beispiel mit CAL3

• $S_1 = 4, S_2 = 0.7$

Ergebnis: $x_1(A, x_2(B, A))$

Trainingsfehler: $1/5 = 0.2 < 1-S_2 = 1-0.7 = 0.3$

Hinweis: Bei nicht überlappenden Klassen erzeugt CAL3 u.U. andere Bäume als CAL2 ...

CAL3: Abbruchbedingungen und Parameter

• Parameter:

  • $S_1$: Statistikschwelle, problemabhängig wählen
  • $S_2$: $0.5 < S_2 \le 1.0$
  • Klassifikationsfehler kleiner als $1-S_2$
    • kleiner Fehler => großer Baum
    • großer Fehler => kleiner Baum

• Abbruch:

  • Alle Trainingsobjekte richtig klassifiziert => Kein Fehler in einem kompletten Durchlauf
  • Alle Endknoten mit eindeutigen Klassensymbolen belegt
  • Differenzierung nötig, aber alle Merkmale verbraucht
  • Lernschrittzahl überschritten

Wrap-Up

• CAL3: Erweiterung von CAL2 für überlappende Klassen
  • Parameter $S_1$ (Anzahl Objekte bis Entscheidung), $S_2$ (Dominanz?)
  • Trainingsfehler wg. überlappender Klassen!

Entropie

Wie Attribute wählen?

Erinnerung: CAL2/CAL3

• Zyklische Iteration durch die Trainingsmenge
• Ausschließlich aktuelles Objekt betrachtet
• Reihenfolge der "richtigen" Attributwahl bei Verzweigung unklar

=> Betrachte stattdessen die komplette Trainingsmenge!

Relevanz => Informationsgehalt

• Shannon/Weaver (1949): Entropie
  • Maß für die Unsicherheit einer Zufallsvariablen
  • Anzahl der Bits zur Darstellung der Ergebnisse eines Zufallsexperiments

Beispiele

• Münze, die immer auf dem Rand landet: keine Unsicherheit, 0 Bit
• Faire Münze: Kopf oder Zahl: Entropie 1 Bit
• Fairer 4-seitiger Würfel: 4 mögliche Ausgänge: Entropie 2 Bit
• Münze, die zu 99% auf einer Seite landet: Entropie nahe Null

=> Anzahl der Ja/Nein-Fragen, um zur gleichen Information zu kommen

Definition der Entropie $H(V)$ für Zufallsvariable $V$

• Zufallsvariable $V$ => mögliche Werte $v_k$
• Wahrscheinlichkeit für $v_k$ sei $p_k = P(v_k)$

• Nur eine Klasse: $\log_2 1 = 0$ => $H(V) = 0$ Bit
• Zwei Klassen, gleichwahrscheinlich: $\log_2 0.5 = -1$ => $H(V) = 1$ Bit

Beispiele Entropie: faire Münze

Beispiele Entropie: unfaire Münze

Beispiele Entropie: 4-seitiger Würfel

Entropie der Trainingsmenge: Häufigkeit der Klassen zählen

Mittlere Entropie nach Betrachtung von Attribut $A$

• Auswahl von Attribut $A$ partitioniert die Trainingsmenge: Je Ausprägung $v$ von $A$ erhält man eine Submenge $S_v$

• $R(S, A)$ berechnet die mittlere Entropie der Trainingsmenge, nachdem Attribut $A$ ausgewählt wurde: Unsicherheit/nötige Bits nach Auswahl von Attribut $A$

Entropie der Trainingsmenge nach Attributwahl

Ausblick: Gini Impurity

Wir haben hier die Entropie als Maß für den Informationsgehalt einer Trainingsmenge genutzt. $R(S,A)$ als die mittlere Entropie nach Betrachtung von Attribut $A$ wird von typischen Entscheidungsbaumverfahren wie ID3 und C4.5 genutzt, um bei einer Verzweigung das nächste möglichst aussagekräftige Merkmal auszuwählen.

In anderen Entscheidungsbaumlernern wird stattdessen die Gini Impurity zur Bestimmung des Informationsgehalts eingesetzt (u.a. CART). Dieses Maß sagt aus, wie oft man ein zufällig gezogenes Element des Datensatzes falsch klassifizieren würde, wenn man es mit einer zufälligen Klasse basierend auf der Verteilung der Klassen im Datensatz labeln würde.

Hierzu drei lesenswerte Blog-Einträge:

• Deep dive into the basics of Gini Impurity in Decision Trees with math Intuition
• Decision Trees, Explained
• Decision Tree Algorithm With Hands-On Example

Wrap-Up

• Begriff und Berechnung der Entropie: Maß für die Unsicherheit
• Begriff und Berechnung des Informationsgewinns
  • Entropie für eine Trainingsmenge
  • Mittlere Entropie nach Wahl eines Attributs

ID3 und C4.5

Wie Attribute wählen?

Erinnerung: CAL2/CAL3

• Zyklische Iteration durch die Trainingsmenge
• Ausschließlich aktuelles Objekt betrachtet
• Reihenfolge der "richtigen" Attributwahl bei Verzweigung unklar

=> Betrachte stattdessen die komplette Trainingsmenge!

Erinnerung Entropie: Maß für die Unsicherheit

• Entropie $H(S)$ der Trainingsmenge $S$: relative Häufigkeit der Klassen zählen

• Mittlere Entropie nach Betrachtung von Attribut $A$

  $$ R(S, A) = \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v) $$

• Informationsgewinn durch Betrachtung von Attribut $A$

  $$ \begin{array}{rcl} \operatorname{Gain}(S, A) &=& H(S) - R(S, A)\\[5pt] &=& H(S) - \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v) \end{array} $$

$R(S,A)$ ist die Unsicherheit/nötige Bits nach Auswahl von Attribut A. Je kleiner $R(S,A)$, um so kleiner die verbleibende Unsicherheit bzw. um so kleiner die Anzahl der nötigen Bits zur Darstellung der partitionierten Trainingsmenge nach Betrachtung von Attribut $A$ ...

=> Je kleiner $R(S,A)$, um so größer der Informationsgewinn

Informationsgewinn: Kriterium zur Auswahl von Attributen

1. Informationsgewinn für alle Attribute berechnen
2. Nehme Attribut mit größtem Informationsgewinn als nächsten Test

Informationsgewinn für $x_2$ am höchsten => wähle $x_2$ als nächsten Test

Entscheidungsbaumlerner ID3 (Quinlan, 1986)

def ID3(examples, attr, default):
    # Abbruchbedingungen
    if examples.isEmpty():  return default
    if examples.each(class == A):  return A  # all examples have same class
    if attr.isEmpty():  return examples.MajorityValue()

    # Baum mit neuem Test erweitern
    test = MaxInformationGain(examples, attr)
    tree = new DecisionTree(test)
    m = examples.MajorityValue()
    for v_i in test:
        ex_i = examples.select(test == v_i)
        st = ID3(ex_i, attr - test, m)
        tree.addBranch(label=v_i, subtree=st)
    return tree

[Russell2020]: Man erhält aus dem "Learn-Decision-Tree"-Algorithmus [Russell2020, S. 678, Fig. 19.5] den hier vorgestellten ID3-Algorithmus, wenn man die Funktion $\operatorname{Importance}(a, examples)$ als $\operatorname{InformationGain}(examples, attr)$ implementiert/nutzt.

Hinweis: Mit der Zeile if examples.each(class == A): return A soll ausgedrückt werden, dass alle ankommenden Trainingsbeispiele die selbe Klasse haben und dass diese dann als Ergebnis zurückgeliefert wird. Das "A" steht im obigen Algorithmus nur symbolisch für die selbe Klasse! Es kann also auch ein anderes Klassensymbol als "A" sein ...

Beispiel ID3

• $x2$ höchsten Information Gain
• $x2=0$ => Beispiele 1,2 => A
• $x2=1$ => Beispiele 3,4,5,6 => Information Gain berechnen, weiter teilen und verzweigen

Beobachtung: $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher

• Faire Münze:

  • Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$

• 4-seitiger Würfel:

  • Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$

=> $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher

Damit würden Attribute bei der Wahl bevorzugt, nur weil sie mehr Ausprägungen haben als andere.

Anmerkung: Im obigen Beispiel wurde einfach die Entropie für zwei "Attribute" mit unterschiedlich vielen Ausprägungen betrachtet, das ist natürlich kein $\operatorname{Gain}(S, A)$. Aber es sollte deutlich machen, dass Merkmale mit mehr Ausprägungen bei der Berechnung des Gain für eine Trainingsmenge einfach wegen der größeren Anzahl an Ausprägungen rechnerisch bevorzugt würden.

C4.5 als Verbesserung zu ID3

Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A)$

C4.5 kann zusätzlich u.a. auch noch mit kontinuierlichen Attributen umgehen, vgl. en.wikipedia.org/wiki/C4.5_algorithm.

In einem Paper (DOI 10.1007/s10115-007-0114-2) wurde der Algorithmus zu den "Top 10 algorithms in data mining" ausgewählt.

Im Wikipedia-Artikel Information Gain finden Sie weitere Informationen zum "Informationsgewinn" (Information Gain).

Ein anderer, relativ ähnlich arbeitender Entscheidungsbaumlerner ist der CART (Classification And Regression Tree)-Algorithmus, wobei der Begriff "CART" allerdings oft auch einfach allgemein für "Entscheidungsbaumlerner" genutzt wird.

Hierzu drei lesenswerte Blog-Einträge:

• Deep dive into the basics of Gini Impurity in Decision Trees with math Intuition
• Decision Trees, Explained
• Decision Tree Algorithm With Hands-On Example

Beispiele zur Normierung bei C4.5

• Faire Münze:

  • Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$
  • Normierung: $1/(0.5 \log_2 (1/0.5) + 0.5 \log_2 (1/0.5)) = 1/(0.5 \cdot 1 + 0.5 \cdot 1) = 1$
  • Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 1 \operatorname{Bit} \cdot 1 = 1 \operatorname{Bit}$

• 4-seitiger Würfel:

  • Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$
  • Normierung: $1/(4\cdot 0.25 \log_2 (1/0.25)) = 1/(4\cdot 0.25 \cdot 2) = 0.5$
  • Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 2 \operatorname{Bit} \cdot 0.5 = 1 \operatorname{Bit}$

=> Normierung sorgt für fairen Vergleich der Attribute

Anmerkung: Auch hier ist die Entropie natürlich kein $\operatorname{Gain}(S, A)$. Das Beispiel soll nur übersichtlich deutlich machen, dass der "Vorteil" von Attributen mit mehr Ausprägungen durch die Normierung in C4.5 aufgehoben wird.

Wrap-Up

• Entscheidungsbaumlerner ID3
  • Nutze Information Gain zur Auswahl des nächsten Attributs
  • Teile die Trainingsmenge entsprechend auf ("nach unten hin")
• Verbesserung durch Normierung des Information Gain: C4.5

NN01 - Das Perzeptron

NN02 - Lineare Regression und Gradientenabstieg

Challenges

Skalierung der Merkmale

Abbildung 1 und Abbildung 2 zeigen die Höhenlinien (Contour Lines) von zwei Kostenfunktionen.

• Erklären Sie, welcher der beiden Fälle nachteilhaft für den Gradientenabstieg Algorithmus ist. Wo liegt der Nachteil? Wie kann die Merkmalskalierung dem genannten Nachteil entgegenwirken?
• Zeigen Sie unter Verwendung Ihrer eigenen, zufällig generierten Datenpunkte aus dem Bereich $[100, 300] \times [0, 2]$, wie sich Standardisierung, Min-Max Skalierung und Normalisierung auf die Daten auswirken. Vergleichen Sie dazu die jeweiligen Streudiagramme (scatterplots). Sie können hierzu das folgende Jupyter Notebook als Startpunkt benutzen.

NN03 - Logistische Regression

NN04 - Overfitting und Regularisierung

NN05 - Multilayer Perzeptron

NN06 - Backpropagation

NN07 - Training & Testing

NN08 - Performanzanalyse

Kurze Übersicht

Performanzmetriken für Klassifizierungsprobleme

Wahrheitsmatrix (engl. Confusion Matrix)

• Gibt eine Übersicht über die Anzahl von richtig und falsch klassifizierten Datenpunkten (bei binärer Klassifizierung)
  • $TP =$ # True Positives $=$ Anzahl richtiger 1-Vorhersagen
  • $FP =$ # False Positives $=$ Anzahl falscher 1-Vorhersagen
  • $FN =$ # False Negatives $=$ Anzahl falscher 0-Vorhersagen
  • $TN =$ # True Negatives $=$ Anzahl richtiger 0-Vorhersagen
• Bei Klassifizierungsproblemen mit $N$ Klassen hat man eine $N \times N$ Matrix, die in Position $(i,j)$ die Anzahl der Klasse-$j$-Beispiele enthält, die als Klasse-$i$ vorhergesagt wurden.

Treffergenauigkeit (engl. Accuracy)

• Anzahl richtig klassifizierter Datenpunkte, Erfolgsrate (engl. correct rate) $$Accuracy = \frac{TP+TN}{TP+TN+FP+FN}$$

• Accuracy vermittelt ein falsches Bild des Erfolges bei unausgewogenen Datensätzen
  Beispiel:

  • Klasse 1 hat 10, Klasse 0 hat 990 Beispiele.
  • Ein Modell, das immer 0 ausgibt, hat $990/1000 = 0.99$ Treffergenauigkeit, ist aber offensichtlich kein gutes Modell!

Precision

• Positive Predictive Value (PPV)
• Antwort auf: Von allen positiven Vorhersagen, wie viele sind richtig? $$Precision = \frac{TP}{TP + FP}$$
• Wahrscheinlichkeit, dass ein positiv klassifiziertes Beispiel auch tatsächlich positiv ist.
• Je näher an 1, desto besser.
• Accuracy of positive predictions.

Recall

• True Positive Rate, auch Sensitivität (engl. Sensitivity)
• Antwort auf: Von allen positiven Beispielen, wie viele wurden richtig klassifiziert? $$Recall = \frac{TP}{TP + FN}$$
• Wahrscheinlichkeit, dass ein positives Beispiel tatsächlich als solches erkannt wird.
• Je näher an 1, desto besser.
• Accuracy of positive examples.

Precision-Recall Trade-off

• Ein gutes Modell sollte hohe Precision und zugleich hohes Recall haben.
• Man kann die Precision eines Modells beliebig erhöhen (durch das Vergrößern des Schwellenwertes bei der Klassifizierung), jedoch wird dabei der Recall abnehmen.
• Genau so kann man den Recall eines Modells beliebig erhöhen (durch das Verkleinern des Schwellenwertes bei der Klassifizierung), jedoch wird dabei die Precision abnehmen.
• Es gilt ein gutes Trade-off zu finden.
• Eine Zwei-Zahlen-Metrik erschwert den Entscheidungsprozess bei Evaluierung und Modellauswahl.

$F_1$-Score (Harmonisches Mittel)

• Fasst Precision (P) und Recall (R) in einer Metrik zusammen (Harmonisches Mittel von P und R): $$F_1-Score = \frac{2}{\frac{1}{P} + \frac{1}{R}} = 2 \cdot \frac{PR}{P + R}$$
• Der $F_1$-Score wird nur dann hoch sein, wenn P und R beide hoch sind.
• Je näher an 1, desto besser.
• Sehr kleine P und R Werte ziehen den $F_1$-Score sehr stark herunter. In dieser Hinsicht gibt diese Metrik ein akkurates Bild über den Erfolg eines Modells.

NN10 - Vorschau Deep Learning (CNN, RNN)

Suche mit Tiefensuche

Hole das Buch

Das Beispiel ist ein Büroflur in der Uni. Neben den Büros gibt es eine Bibliothek und einen Kopiererraum, wo auch der Roboter sich gerade aufhält. Die Aufgabe für den Roboter lautet: Hole das Buch aus der Bibliothek (und bringe es zum Kopier). (Damit das Beispiel und der sich daraus ergebende Problemgraph nicht zu groß und zu unübersichtlich werden, soll das Ziel hier darin liegen, dass der Roboter das Buch in der Bibliothek aufnimmt.)

Es stehen zwei Aktionen zur Verfügung:

1. Der Roboter kann von einem in den nächsten Raum wechseln (Kosten siehe Pfeile)
2. Der Roboter kann das Buch aufnehmen (Kosten: 3)

Dabei sind die Durchgänge teilweise nur in einer Richtung zu benutzen (Pfeilrichtung).

Problemgraph zum Kopiererbeispiel

=> Problemlösen == Suche im Graphen

Uninformierte ("blinde") Suche:

Keine Informationen über die Kosten eines Pfades: Nur die Pfadlänge (Anzahl der Schritte) zählt.

Varianten:

• Tiefensuche
• Breitensuche

Anmerkungen Wegesuche (Landkarte)

Bei der Wegesuche hat man den Problemgraphen bereits durch die Orte und die Verbindungen (Straßen) zwischen ihnen gegeben. Es gibt nur eine ausführbare Aktion: "fahre nach".

Dabei können nur die Anzahl der Zwischenstationen auf dem Weg gezählt werden ("uninformierte Suche"), oder man ordnet den Kanten Kosten zu (bei der Wegesuche wären dies die Entfernungen zwischen den Orten oder die Zeit, die man von A nach B braucht) und landet damit bei der "informierten Suche".

Normalerweise hat man eine Ordnung auf den Aktionen, d.h. für einen Knoten ergibt sich daraus eine Reihenfolge, in der die Aktionen angewendet werden und die Nachfolger expandiert werden. Bei der Wegesuche hat man dies nicht, insofern muss man willkürlich eine Ordnung festlegen. In dieser Veranstaltung ist dies die alphabetische Reihenfolge der Knoten (Orte).

Tiefensuche (TS, DFS)

Erinnerung Tree-Search

1. Füge Startknoten in leere Datenstruktur (Stack, Queue, ...) ein
2. Entnehme Knoten aus der Datenstruktur:
   • Knoten ist gesuchtes Element: Abbruch, melde "gefunden"
   • Expandiere alle Nachfolger des Knotens und füge diese in die Datenstruktur ein
3. Falls die Datenstruktur leer ist: Abbruch, melde "nicht gefunden"
4. Gehe zu Schritt 2

=> Was passiert, wenn wir einen Stack einsetzen?

Bemerkungen

• Nachfolger eines Knotens: Alle von diesem Zustand durch Aktionen erreichbare Zustände

• Suchalgorithmus mit Stack als Datenstruktur => Tiefensuche

  • Zu betrachtender Knoten in Schritt 2 wird oben vom Stack genommen
  • Expandierte Knoten werden in Schritt 2.a oben auf den Stack gelegt Dabei i.A. die vorgegebene Reihenfolge der Nachfolgeknoten beachten!

  Auswirkung: Weg wird in die Tiefe verfolgt (deshalb "Tiefensuche")

• Im [Russell2020] wird die Datenstruktur zum Halten der zu expandierenden Knoten (also hier im Fall der Tiefensuche der Stack) auch "Frontier" genannt.

• Backtracking: Wenn der Weg in eine Sackgasse führt, d.h. ein Knoten keine Nachfolger hat, werden bei der Expansion des Knotens keine Nachfolger auf den Stack gelegt. Die Evaluation des nächsten Knotens auf dem Stack bewirkt deshalb ein Zurückspringen im Suchbaum zum letzten Knoten auf dem aktuellen Weg mit noch offenen Alternativen ...

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Nicht Bestandteil der Algorithmen, dient aber der Nachvollziehbarkeit: Expandierte Knoten sollen alphabetisch sortiert an der korrekten Stelle in der Datenstruktur auftauchen, dabei soll aber natürlich die Reihenfolge der ursprünglich in der Datenstruktur enthaltenen Knoten nicht modifiziert werden. (Bei "echten" Problemen wird die Reihenfolge der expandierten Nachfolger in der Regel durch eine Reihenfolge der anwendbaren Operationen bestimmt.)

Weitere Hinweise

• Die Tiefensuche wurde zufällig am Beispiel Tree-Search eingeführt. Man kann auch Graph-Search einsetzen. Wichtig ist nur, dass als Datenstruktur ein Stack genutzt wird.

• Bei Tree-Search werden bereits besuchte Knoten u.U. immer wieder besucht. Zyklen im aktuell entwickelten Pfad sind also möglich! Außerdem sind mehrere Wege zum selben (Zwischen-/End-) Knoten in der Datenstruktur möglich!

• Im [Russell2020] wird der Begriff "Backtracking" für den rekursiven Tiefensuche-Algorithmus verwendet. Dies steht im Gegensatz zum üblichen Sprachgebrauch in der KI!

Tiefensuche (rekursive Variante)

1. Startknoten ist gesuchtes Element: Abbruch, melde "gefunden"
2. Für jeden Nachfolger des Startknotens:
   • Rufe Tiefensuche für aktuellen (Nachfolger-) Knoten auf
   • Ergebnis "gefunden": Abbruch, melde "gefunden"
3. Abbruch, melde "nicht gefunden"

Bemerkungen

• Eigenschaften wie "normale" Tiefensuche
• Einfacher zu implementieren: Nutzung des Stacks wird auf den Compiler verlagert (Funktionsaufruf, Stack des Prozesses ...)
• Speicherbedarf: Für jeden Knoten wird nur der nächste Knoten expandiert, plus Speicher für die Funktion

Eigenschaften der Tiefensuche

Siehe Breitensuche

Wrap-Up

• Uninformierte Suchverfahren
  • Keine weiteren Pfadkosten (nur Anzahl der Schritte)
  • Tiefensuche: Verfolge einen Pfad zuerst in die Tiefe
  • Backtracking bei Sackgassen (automatisch durch den Stack)

Suche mit Breitensuche

Hole das Buch

=> Problemlösen == Suche im Graphen

Uninformierte ("blinde") Suche:

Keine Informationen über die Kosten eines Pfades: Nur die Pfadlänge (Anzahl der Schritte) zählt.

Varianten:

• Tiefensuche
• Breitensuche

Breitensuche (BS, BFS)

Erinnerung Graph-Search

1. Füge Startknoten in leere Datenstruktur (Stack, Queue, ...) ein
2. Entnehme Knoten aus der Datenstruktur:
   • Knoten ist gesuchtes Element: Abbruch, melde "gefunden"
   • Markiere aktuellen Knoten, und
   • Expandiere alle Nachfolger des Knotens und füge alle unmarkierten Nachfolger, die noch nicht in der Datenstruktur sind, in die Datenstruktur ein
3. Falls die Datenstruktur leer ist: Abbruch, melde "nicht gefunden"
4. Gehe zu Schritt 2

=> Was passiert, wenn wir eine Queue einsetzen?

Bemerkungen

• Nachfolger eines Knotens: Alle von diesem Zustand durch Aktionen erreichbare Zustände

• Suchalgorithmus mit Queue als Datenstruktur => Breitensuche

  • Zu betrachtender Knoten in Schritt 2 wird vorn aus der Queue genommen
  • Expandierte Knoten werden in Schritt 2.a hinten in die Queue eingefügt Dabei i.A. die vorgegebene Reihenfolge der Nachfolgeknoten beachten!

  Auswirkung: Suchbaum wird ebenenweise aufgebaut (deshalb "Breitensuche")

• Graph-Search: Markierte Knoten müssen geeignet gespeichert werden: separate Datenstruktur => Aufwand!

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Nicht Bestandteil der Algorithmen, dient aber der Nachvollziehbarkeit: Expandierte Knoten sollen alphabetisch sortiert an der korrekten Stelle in der Datenstruktur auftauchen, dabei soll aber natürlich die Reihenfolge der ursprünglich in der Datenstruktur enthaltenen Knoten nicht modifiziert werden. (Bei "echten" Problemen wird die Reihenfolge der expandierten Nachfolger in der Regel durch eine Reihenfolge der anwendbaren Operationen bestimmt.)

Weitere Hinweise

• Die Breitensuche wurde zufällig am Beispiel Graph-Search eingeführt. Man kann auch die Tree-Search-Variante einsetzen. Wichtig ist nur, dass als Datenstruktur eine Queue genutzt wird.

• Im [Russell2020] wird die Breitensuche ebenfalls auf der Basis des Graph-Search-Algorithmus eingeführt. Allerdings wird die Abbruchbedingung modifiziert: Die Zielbedingung wird nicht erst (wie bei Graph-Search eigentlich definiert) geprüft, wenn ein Knoten aus der Queue entnommen wird, sondern bereits bei der Erzeugung der Nachfolgerknoten (vor dem Einfügen in die Queue). Dadurch spart man sich die Expansion einer zusätzlichen Ebene: Die Komplexität wäre in diesem Fall "nur" $O(b^{d})$.

Eigenschaften Breitensuche vs. Tiefensuche

• Zeitkomplexität: maximal zu expandierende Knotenzahl
• Speicher:
  • TS: in jeder Tiefe weitere $b$ Knoten speichern
  • BS: alle Knoten einer Ebene im Speicher halten³

b: Verzweigungsfaktor, d: Ebene d. höchsten Lösungsknotens, m: Länge d. längsten Pfades

Praxisvergleich Breitensuche vs. Tiefensuche

Breitensuche: Annahme: $b=10$, 10.000 Knoten/s, 1.000 Byte/Knoten

Tiefensuche: Annahme: längster Pfad (Tiefe) $m=1000$

=> Speicherbedarf ca. 10 MB

Wrap-Up

• Uninformierte Suchverfahren
  • Keine weiteren Pfadkosten (nur Anzahl der Schritte)
  • Breitensuche: Verfolge alle Pfade (baue den Suchbaum ebenenweise auf)

Suche mit Branch-and-Bound

Hole das Buch

=> Problemlösen == Suche im Graphen

Informierte Suche: Nutzung der Kostenfunktion:

Gesamtkosten: $f(n) = g(n) + h(n)$

• $n \in S$ auf aktuellem Weg erreichter Knoten
• $g(n)$ tatsächliche Kosten für Weg vom Start bis Knoten $n$
• $h(n)$ geschätzte Restkosten für Weg von Knoten $n$ zum Ziel => $h(n)$ wird auch "heuristische Funktion" oder "Heuristik" genannt

Varianten:

• Branch-and-Bound
• Best First
• A*

Branch-and-Bound (BnB)

Variante der Breitensuche mit Kosten

• Idee: Expandiere den bisher günstigsten partiellen Weg

• Kostenfunktion: $f(n) = g(n)$

• Datenstruktur: sortierte Queue (Prioritätsqueue)

• Voraussetzung: alle Aktionen haben positive Kosten (jeden Knoten $n$ gilt: $g(n) > 0$)

Hinweis: Die Branch-and-Bound-Suche taucht im [Russell2020] als Erweiterung der "Uniformen Suche" auf ...

BnB: Finde einen Weg von A nach H

Bemerkungen zu BnB mit Graph-Search

Graph-Search fordert: Expandierte Nachfolgerknoten, die schon in der Queue sind, sollen nicht (erneut) in die Queue aufgenommen werden.

• Problem dabei: Was ist mit den Kosten?! Der neu expandierte Weg könnte günstiger sein als der schon in der Queue enthaltene.

• Lösung (vgl. Optimierungsmöglichkeiten für A*):

  Füge zunächst alle neu expandierten partiellen Pfade (mit unmarkierten Endknoten) in die Queue ein, sortiere diese und behalte von mehreren Pfaden zum gleichen Knoten nur den jeweils günstigsten in der Queue

Pfade, deren Endknoten bereits früher im Pfad vorkommt (Schleifen), werden bei Graph-Search in Schritt 2 nicht in die Queue aufgenommen (der Endknoten wäre bei einer Schleife ja bereits markiert und der neue Pfad würde bei Graph-Search nicht weiter beachtet).

Das Einfärben ist kein Problem, da nur der jeweils günstigste Knoten aus der Queue genommen, gefärbt und expandiert wird. D.h. alle anderen Wege sind zu diesem Zeitpunkt bereits teurer. Wenn man nun (später) über einen anderen Weg zu einem bereits gefärbten Knoten kommt, kann der neue Weg nicht günstiger sein (positive Kosten vorausgesetzt).

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Auf dem Papier sortiert sich die Queue schlecht, deshalb können Sie darauf verzichten, wenn Sie den im nächsten Schritt zu expandierenden Weg unterstreichen. Wer nicht mit Unterstreichen arbeiten will, muss eben dann manuell sortieren ...

Wenn bei der Graph-Search-Variante ein Weg nicht in die Queue aufgenommen wird, weil bereits ein anderer (günstigerer) Weg zum selben (Zwischen-/End-) Knoten bereits in der Queue enthalten ist, schreiben Sie dies geeignet auf. Dies gilt auch für den analogen Fall, wenn ein Weg aus der Queue entfernt wird, weil ein günstigerer Weg zum selben (Zwischen-/End-) Knoten eingefügt werden soll.

Eigenschaften von BnB

Siehe A*

Wrap-Up

• Informierte Suchverfahren
  • Nutzen reale Pfadkosten und/oder Schätzungen der Restkosten
  • Branch-and-Bound: nur reale Pfadkosten $g(n)$

Suche mit Best First

Hole das Buch

=> Problemlösen == Suche im Graphen

Informierte Suche: Nutzung der Kostenfunktion:

Gesamtkosten: $f(n) = g(n) + h(n)$

• $n \in S$ auf aktuellem Weg erreichter Knoten
• $g(n)$ tatsächliche Kosten für Weg vom Start bis Knoten $n$
• $h(n)$ geschätzte Restkosten für Weg von Knoten $n$ zum Ziel => $h(n)$ wird auch "heuristische Funktion" oder "Heuristik" genannt

Varianten:

• Branch-and-Bound
• Best First
• A*

Best-First (BF, BFS)

• Idee: Expandiere den partiellen Weg, der verspricht, dem Ziel am nächsten zu sein (Heuristik)

• Kostenfunktion: $f(n) = h(n)$

• Datenstruktur: sortierte Queue (Prioritätsqueue)

• Voraussetzungen: $h(n)$ positiv, $h(n) = 0$ für den Zielknoten

Konventionen BF

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Auf dem Papier sortiert sich die Queue schlecht, deshalb können Sie darauf verzichten, wenn Sie den im nächsten Schritt zu expandierenden Weg unterstreichen. Wer nicht mit Unterstreichen arbeiten will, muss eben dann manuell sortieren ...

Wenn bei der Graph-Search-Variante ein Weg nicht in die Queue aufgenommen wird, weil bereits ein anderer (günstigerer) Weg zum selben (Zwischen-/End-) Knoten bereits in der Queue enthalten ist, schreiben Sie dies geeignet auf. Dies gilt auch für den analogen Fall, wenn ein Weg aus der Queue entfernt wird, weil ein günstigerer Weg zum selben (Zwischen-/End-) Knoten eingefügt werden soll.

Eigenschaften von BF

Siehe A*

Wrap-Up

• Informierte Suchverfahren
  • Nutzen reale Pfadkosten und/oder Schätzungen der Restkosten
  • Best-First: nur Schätzungen $h(n)$

Suche mit A*

Hole das Buch

=> Problemlösen == Suche im Graphen

Informierte Suche: Nutzung der Kostenfunktion:

Gesamtkosten: $f(n) = g(n) + h(n)$

• $n \in S$ auf aktuellem Weg erreichter Knoten
• $g(n)$ tatsächliche Kosten für Weg vom Start bis Knoten $n$
• $h(n)$ geschätzte Restkosten für Weg von Knoten $n$ zum Ziel => $h(n)$ wird auch "heuristische Funktion" oder "Heuristik" genannt

Varianten:

• Branch-and-Bound
• Best First
• A*

A*-Suche

• Kombination aus Branch-and-Bound und Best-First-Suche

• Kostenfunktion: $f(n) = g(n) + h(n)$

• Datenstruktur: sortierte Queue (Prioritätsqueue)

• Voraussetzung:

  1. Alle Aktionen haben positive Kosten ($g(n) \ge \epsilon$)
  2. Heuristik $h(n)$ muss zulässig/konsistent sein

Konventionen für diese Lehrveranstaltung

In der Beschreibung der Algorithmen werden häufig nur die letzten Knoten der partiellen Wege in den Datenstrukturen mitgeführt (das gilt auch für die Beschreibung im [Russell2020]). Dies erschwert die Nachvollziehbarkeit, wenn man die Queue oder den Stack schrittweise aufschreibt. Deshalb wird für diese Veranstaltung die Konvention eingeführt, immer die partiellen Wege aufzuschreiben.

Notieren Sie die Bestandteile der Kosten für jeden partiellen Weg in der Queue einzeln: "$g(n) + h(n) = f(n)$". Das erleichtert Ihnen die weiteren Schritte, da Sie dort ja nur mit $g(n)$ weiter rechnen dürfen. Gleichzeitig erleichtert es die Nachvollziehbarkeit.

Auf dem Papier sortiert sich die Queue schlecht, deshalb können Sie darauf verzichten, wenn Sie den im nächsten Schritt zu expandierenden Weg unterstreichen. Wer nicht mit Unterstreichen arbeiten will, muss eben dann manuell sortieren ...

Wenn bei der Graph-Search-Variante ein Weg nicht in die Queue aufgenommen wird, weil bereits ein anderer (günstigerer) Weg zum selben (Zwischen-/End-) Knoten bereits in der Queue enthalten ist, schreiben Sie dies geeignet auf. Dies gilt auch für den analogen Fall, wenn ein Weg aus der Queue entfernt wird, weil ein günstigerer Weg zum selben (Zwischen-/End-) Knoten eingefügt werden soll.

A*-Suche -- Anforderungen an Heuristik (Tree-Search)

Tree-Search-Variante: Die Heuristik muss zulässig sein:

• Seien $h^\star(n)$ die tatsächlichen optimalen Restkosten von einem Knoten $n$ zum nächsten Ziel.
• Dann muss für jeden beliebigen Knoten $n$ gelten: $$h(n) \le h^\star(n)$$
• Außerdem muss gelten:
  • $h(n) \ge 0$ für jeden Knoten $n$
  • $h(n) = 0$ für jeden Zielknoten $n$

=> Beispiel: Luftlinie als Abschätzung

Hinweis: Im der englischen Ausgabe des [Russell2020] wird die zulässige Heuristik auch "admissible heuristic" genannt.

A* ist optimal

A* (Tree-Search-Variante) mit zulässiger Heuristik ist optimal.

Beweis siehe Übung :-)

Einfache Verbesserungen A* (Tree-Search)

• Dynamische Programmierung: Behalte von mehreren Pfaden zum gleichen Knoten nur den günstigsten in der Queue

• Pfade, deren Endknoten bereits früher im Pfad vorkommt (Schleifen), werden in Schritt 2 nicht in die Queue aufgenommen

• Übergang zur Graph-Search-Variante und Markierung von Knoten

  => Achtung: Dann schärfere Anforderungen an Heuristik (Konsistenz)

A*-Suche -- Anforderungen an Heuristik (Graph-Search)

Graph-Search-Variante: Die Heuristik muss konsistent sein:

Für jeden Knoten $n$ und jeden durch eine Aktion $a$ erreichten Nachfolger $m$ gilt: $$h(n) \le c(n,a,m) + h(m)$$ mit $c(n,a,m)$ Schrittkosten für den Weg von $n$ nach $m$ mit Aktion $a$.

Außerdem muss gelten:

• $h(n) \ge 0$ für jeden Knoten $n$
• $h(n) = 0$ für jeden Zielknoten $n$

=> Eine konsistente Heuristik ist gleichzeitig zulässig.

Hinweis: Im der englischen Ausgabe des [Russell2020] wird die konsistente Heuristik auch "consistent heuristic" genannt.

Eigenschaften Branch-and-Bound, Best-First, A*

Wrap-Up

• Informierte Suchverfahren

  • Nutzen reale Pfadkosten und/oder Schätzungen der Restkosten
  • A*: komplette Kostenfunktion $f(n) = g(n)+h(n)$ => besondere Anforderungen an die Heuristik! (Tree-Search: zulässige Heuristik; Graph-Search: konsistente Heuristik)

• Ausblick auf Verbesserungen der vorgestellten Suchverfahren:

  • Beschränkung der Suchtiefe ("Depth-Limited-Search")
  • Iterative Vertiefung der Suchtiefe ("Iterative-Deepening-Search"), beispielsweise IDA* ("Iterative-Deepening A*")
  • Beschränkung des verwendeten Speichers, beispielsweise SMA* ("Simplified Memory-Bounded A*")

Lokale Suche: Gradientensuche

Unterschiede in den Suchproblemen?

Bisher betrachtete Suchverfahren:

• Systematische Erkundung des Suchraums
• Weg zur Lösung wichtig

=> Oft aber nur das Ziel an sich interessant! (Und nicht, wie man dort hin gelangt.)

Beispiel: Stundenplan

Analogie: Bergsteigen ohne Karte und Pfade

Gradienten-Suche: "Gehe in Richtung des steilsten Anstiegs der Zielfunktion."

=> Schrittweise Verbesserung des aktuellen Zustands (Lokale Suche)

• Verschiedene Namen: "Hill-climbing", "Greedy local search"
• Kann auch als Minimierung angewendet werden

Pseudoalgorithmus Gradientensuche

1. Setze currNode auf den Startknoten
2. currNode ist gesuchtes Element: Abbruch, melde "gefunden"
   • Expandiere alle Nachfolger von currNode
   • Setze nextNode auf Nachfolger mit höchster Bewertung
   • Falls Bewertung von nextNode $\leq$ Bewertung von currNode: Abbruch, melde "nicht gefunden"
   • Setze currNode auf nextNode
3. Gehe zu Schritt 2

Beispiel Gradientensuche: $n$-Damen

• Ziel: Setze $n$ Damen auf ein $n \times n$-Spielfeld ohne Konflikte
• Start: Setze $n$ Damen auf ein $n \times n$-Spielfeld (mit Konflikten)
• Suche: Bewege jeweils eine Dame so, daß die Anzahl der Konflikte reduziert wird

Schauen Sie sich auch Abb. 4.3 auf Seite 130 im [Russell2020] an!

Hinweis: Alle Damen stehen von Anfang an auf dem Brett und werden nur verschoben => "vollständige Zustandsformulierung"

Eigenschaften 8-Damen-Problem ($n=8$)

• Zustandsraum: $8^8 \approx 17$ Millionen Zustände!
• Beginnend mit zufällig erzeugtem Startzustand:
  • bleibt in 86% der Fälle stecken, d.h.
  • findet Lösung nur in 14% der Fälle.
• Beobachtung: Lösung nach durchschnittlich 4 Schritten, oder Verfahren bleibt nach durchschnittlich 3 Schritten stecken.

Quelle: nach [Russell2020, p. 131]

Eigenschaften Gradientensuche

• Vollständigkeit: nein
• Optimalität: nein
• Komplexität: linear in der Anzahl der zu expandierenden Knoten

Zielfunktion (Bewertung) nötig!

Problem: lokale Maxima und Plateaus

• Lokale Maxima/Minima: Algorithmus findet nur eine suboptimale Lösung
• Plateaus: Hier muss der Algorithmus mit zufälligen Zügen explorieren

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Gradientenverfahren: Gehe in Richtung des stärksten Anstiegs der Kostenfunktion

Lokale Suche: Simulated Annealing

Motivation

Problem: lokale Maxima und Plateaus

• Lokale Maxima/Minima: Algorithmus findet nur eine suboptimale Lösung
• Plateaus: Hier muss der Algorithmus mit zufälligen Zügen explorieren

Mögliche Lösungen:

• Neustart des Algorithmus, wenn kein Fortschritt erzielt wird
• Rauschen "injizieren"

Gedankenexperiment: Ausweg aus lokalen Minima

• "Drehen der Landschaft": Minimieren statt Maximieren
• Ball wird in Zustandsraum-Landschaft gesetzt.
• Folge:
  • rollt steilsten Abstieg hinunter
  • rollt evtl. in Tal auf halber Höhe (lokales Minimum) => bleibt dort gefangen

=> "Schütteln der Landschaft" -- Ball springt aus dem Tal und rollt in anderes Tal

Nicht zu stark schütteln -- sonst wird u.U. globales Minimum verlassen!

Analogie Härten von Metall

• Metall erhitzen bis Atome frei beweglich
• Langsam abkühlen

=> stabiles Atomgitter mit minimalem Energiezustand

Übertragen der Idee

• Starkes "Schütteln" (hohe "Temperatur") am Anfang
• Schrittweises "Abkühlen" => "Schütteln" im Laufe der Zeit verringern

=> Simulated Annealing

Pseudocode Simulated Annealing (Minimierungsproblem)

def simulated_annealing(problem):
    current = problem.startNode
    t = 0;  temp = schedule(t)

    while temp>0:
        temp = schedule(++t)
        neighbors = current.expandSuccessors()
        if not neighbors: return current
        working = random.choice(neighbors)
        dE = problem.value(current) - problem.value(working)
        if dE > 0 or probability(math.exp(dE/temp)):
            current = working

    return current

Wenn dE positiv ist, dann ist der Nachfolger "besser" (hier: kleiner bewertet) als der aktuelle Knoten und wird immer als nächster Knoten übernommen.

Wenn dE negativ ist, dann ist der betrachtete Nachfolger "schlechter" (hier: größer bewertet) als der aktuelle Knoten. Dann wird er mit einer Wahrscheinlichkeit math.exp(dE/temp) als nächster Knoten übernommen. Diese Wahrscheinlichkeit ist bei hohen Temperaturen temp eher hoch, und sinkt, je niedriger die Temperatur temp wird.

Die Temperatur temp bewegt sich dabei von hohen positiven Werten auf den Wert Null (wird also nicht negativ).

Detail: Akzeptieren von Verschlechterungen

• Wahrscheinlichkeit zum Akzeptieren einer Verschlechterung: math.exp(dE/temp)
• $dE$ negativ => $\exp\left(\text{dE}/\text{temp}\right) = \exp\left(-\frac{|\text{dE}|}{\text{temp}}\right) = \frac{1}{\exp\left(\frac{|\text{dE}|}{\text{temp}}\right)}$

$\exp(a)$ bzw. $e^a$:

• $a<0$: geht gegen 0
• $a=0$: 1
• $a>0$: steil (exponentiell) gegen Unendlich ...

Wenn $dE$ negativ ist, wird math.exp(dE/temp) ausgewertet. Damit ergibt sich wegen $dE$ negativ: $\exp\left(\text{dE}/\text{temp}\right) = \exp\left(-\frac{|\text{dE}|}{\text{temp}}\right) = \frac{1}{\exp\left(\frac{|\text{dE}|}{\text{temp}}\right)}$. Betrachtung für $dE$ (nur negativer Fall!) und $\text{temp}$:

• Temperatur $\text{temp}$ hoch: $a = \frac{|\text{dE}|}{\text{temp}}$ ist positiv und klein (nahe Null), d.h. $\exp(a)$ nahe 1 (oder größer), d.h. die Wahrscheinlichkeit $1/\exp(a)$ ist nahe 1 (oder kleiner)
• Temperatur $\text{temp}$ wird kleiner und geht gegen Null: $a = \frac{|\text{dE}|}{\text{temp}}$ ist positiv und wird größer, d.h. $\exp(a)$ geht schnell gegen Unendlich, d.h. die Wahrscheinlichkeit $1/\exp(a)$ geht gegen 0

Abkühlungsplan problemabhängig wählen

• Initiale Temperatur: So hoch, daß praktisch jede Änderung akzeptiert wird

• Abkühlen: $T_k = \alpha T_{k-1}$ mit $0.8 \le \alpha \le 0.99$

  • Ausreichend langsam abkühlen!
  • Typisch: jede Stufe so lange halten, daß etwa 10 Änderungen akzeptiert wurden

• Stop: Keine Verbesserungen in 3 aufeinander folgenden Temperaturen

Der Abkühlungsplan muss problemabhängig gewählt werden. Das Beispiel zeigt typische Elementes eines solchen Abkühlungsplans.

Eigenschaften Simulated Annealing

• Vollständigkeit: ja (mit gewisser Wahrscheinlichkeit)
• Optimalität: ja (mit gewisser Wahrscheinlichkeit)

Voraussetzung: geeigneter Abkühlungsplan

Anwendungen von Simulated Annealing

• Flugplan-Scheduling
• Layout-Probleme (Chipentwurf, Leiterplatten)
• Produktionsplanung

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Gradientenverfahren
  • Analogie Bergsteigen: Gehe in Richtung des stärksten Anstiegs der Kostenfunktion => Hill-Climbing
  • Achtung: Probleme mit lokalen Minima => Simulated Annealing

Einführung Evolutionäre Algorithmen

Evolution sehr erfolgreich bei Anpassung

Quelle: Photo by Johannes Plenio on Unsplash.com (Unsplash License)

EA -- Zutaten und Mechanismen

• Zutaten:

  • Individuen: Kodierung möglicher Lösungen
  • Population von Individuen
  • Fitnessfunktion: Bewertung der Angepasstheit

• Mechanismen ("Operatoren"):

  • Selektion
  • Rekombination (Crossover)
  • Mutation

EA -- Allgemeiner Ablauf

EA -- Beispiel

Jedes Individuum kodiert ein Spielfeld mit einer konkreten Anordnung aller Königinnen => Vollständige Zustandsbeschreibung.

Dabei korrespondiert der Index in das Array des Individuums mit der jeweiligen Spalte des Spielfelds. Die Zahl an einer Arrayposition gibt dann an, in welcher Zeile in dieser Spalte eine Königin ist.

Crossover: Die ausgewählten Individuen werden an der selben Stelle aufgetrennt und die Hälften verkreuzt zu zwei neuen Individuen zusammengesetzt. Es entstehen zwei neue Anordnungen der Königinnen (zwei neue Spielfelder).

EA -- Strömungen

1. Genetische Algorithmen (GA)

   • Holland und Goldberg (ab 1960)
   • Binäre Lösungsrepräsentation (Bitstring): $\mathbf{g} = (g_1, \dots, g_m)\in \{ 0,1\}^m$
   • Fitnessbasierte stochastische Selektion
   • $\mu$ Eltern erzeugen $\mu$ Kinder

2. Evolutionsstrategien (ES)

   • Rechenberg und Schwefel (ab 1960)
   • Kodierung reellwertiger Parameter: $\mathbf{g} = (\mathbf{x}, \mathbf{\sigma})$ mit $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{R}^n$
   • $\mu$ Eltern erzeugen $\lambda$ Kinder mit $\mu \le \lambda$

3. Evolutionäre Programmierung (EP)

Hinweis: Häufig finden sich Mischformen, beispielsweise GA mit reellwertigen Parametern

Hinweis: Im Folgenden werden Genetische Algorithmen (GA) betrachtet. Sie finden jeweils Hinweise auf die Gestaltung der Operatoren bei ES.

Anwendungsbeispiele für Evolutionäre Algorithmen

• Berechnung und Konstruktion komplexer Bauteile: beispielsweise Tragflächenprofile (Flugzeuge), Brücken oder Fahrzeugteile unter Berücksichtigung bestimmter Nebenbedingungen
• Scheduling-Probleme: Erstellung von Stunden- und Raumplänen oder Fahrplänen
• Berechnung verteilter Netzwerktopologien: Wasserversorgung, Stromversorgung, Mobilfunk
• Layout elektronischer Schaltkreise

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Evolutionäre Algorithmen: Unterschied GA und ES (grober Überblick)

Modellierung mit Genetischen Algorithmen

EA -- Allgemeiner Ablauf

Kodierung Individuen

• Binäre Lösungsrepräsentation (Bitstring): $\mathbf{g} = (g_1, \dots, g_m)\in \{ 0,1\}^m$

  • String gliedert sich in $n$ Elemente (mit $n \le m$) => jedes Segment entspricht einer Problemvariablen
  • Dekodierungsfunktion $\Gamma : \{0,1\}^m \to \mathbb{R}^n$

  Alle relevanten Aspekte des Problems müssen in die Codierung einfließen!

  Bei ES hat man einen Vektor mit reellen Zahlen, wobei jeder Eintrag einen Parameter des Problems darstellt. Eine Dekodierungsfunktion benötigt man entsprechend nicht.

  Bei der Erzeugung der Startpopulation werden die Individuen zufällig (mit zufälligen Werten) initialisiert.

• Fitnessfunktion $\Phi$ ordnet jedem Individuum $\mathbf{g}_i$ eine reelle Zahl zu: $$\Phi(\mathbf{g}_i) = F(\Gamma(\mathbf{g}_i)) - w\cdot\sum_j(Z_j(\Gamma(\mathbf{g}_i)))^2$$

  • Zielfunktion $F$: wie sehr genügt ein Individuum bereits dem Optimierungproblem
  • Strafterme $Z_j$: Anreicherung der Optimierung mit weiteren Informationen
  • Gewichte $w$: statisch oder dynamisch (Abkühlen)

  Die Wahl einer guten Fitnessfunktion ist oft eine Herausforderung, aber dennoch wichtig, da damit die Suche gesteuert wird!

Selektion: Erstelle Matingpool mit $\mu$ Individuen

• Fitnessproportionale Selektion (Roulette Wheel Selection): Auswahlwahrscheinlichkeit für Individuum $\mathbf{g}_k$: $$p_{sel}(\mathbf{g}_k) = \frac{\Phi(\mathbf{g}_k)}{\sum_j \Phi(\mathbf{g}_j)}$$ => Voraussetzung: positive Fitnesswerte

• Turnier-Selektion (Tournament Selection):

  • Turniergröße $\xi$
  • Turnier: ziehe $\xi$ Individuen gleichverteilt (mit Zurücklegen!) und kopiere fittestes Individuum in den Matingpool
  • Führe $\mu$ Turniere durch

Hinweis: Es gibt noch viele weitere Selektionsmechanismen. Die vorgestellten sind in der Praxis am gebräuchlichsten.

Über die Selektion wird der sogenannte "Selektionsdruck" aufgebaut: Wie gut muss ein Individuum sein (im Vergleich zu den restlichen Individuen in der Population), damit es eine Chance zur Reproduktion erhält? Dürfen sich nur die "Guten" fortpflanzen, oder erhalten auch die "Schlechten" eine gewisse Chance?

Da jedes Individuum einen Punkt im Suchraum darstellt, beeinflusst die Wahl der Selektion die Geschwindigkeit der Suche, begünstigt u.U. aber auch ein eventuelles Festfahren in lokalen Minima. Dies kann beispielsweise geschehen, wenn immer nur die "Guten" selektiert werden, aber die "Guten" der Population sich in der Nähe eines lokalen Minimums befinden. Dann werden auch die Nachfolger sich wieder dort aufhalten.

Crossover: Erzeuge zwei Nachkommen aus zwei Eltern

Festlegung der Crossover-Wahrscheinlichkeit $p_{cross}$ (typisch: $p_{cross} \ge 0.6$)

1. Selektiere Eltern $\mathbf{g}_a$ und $\mathbf{g}_b$ gleichverteilt aus Matingpool

2. Zufallsexperiment:

   • mit $1-p_{cross}$: Kinder identisch zu Eltern (kein Crossover)

   • mit $p_{cross}$: Crossover mit $\mathbf{g}_a$ und $\mathbf{g}_b$

     • Ziehe $i$ gleichverteilt mit $1 < i < m$
     • Kinder aus $\mathbf{g}_a$ und $\mathbf{g}_b$ zusammenbauen: $$\mathbf{g}_c = (g_{a,1}, \dots, g_{a,i}, \; g_{b,{i+1}}, \dots, g_{b,m})$$ und $$\mathbf{g}_d = (g_{b,1}, \dots, g_{b,i}, \; g_{a,{i+1}}, \dots, g_{a,m})$$

     => Trenne Eltern an gleicher Stelle auf, vertausche Bestandteile

3. Gehe zu Schritt 1, bis insg. $\mu$ Nachkommen

Anmerkung: Die Eltern werden jeweils in die Ausgangsmenge zurückgelegt.

Mit einer kleinen Wahrscheinlichkeit sind die Kinder also identisch zu den Eltern. Dies ist im Sinne der lokalen Suche wichtig, um bereits erreichte gute Positionen im Suchraum nicht zu verlieren: Es könnte sein, dass die Nachfolger alle schlechter sind ...

Varianten: $N$-Punkt-Crossover, Shuffle-Crossover

Bei ES wird parameterweise gekreuzt. Dabei gibt es verschiedene Möglichkeiten: Übernahme eines Parameters von einem Elternteil, Verrechnen (beispielsweise Mitteln) der Werte beider Eltern, ... Bei ES heißt "Crossover" deshalb oft "Rekombination".

Mutation

• Mutationswahrscheinlichkeit $p_{mut}$ (typische Werte: $p_{mut} = 0.01$ oder $p_{mut} = 0.001$)

• Für alle Individuen:

  • Mutiere jedes Gen eines Individuums mit $p_{mut}$:

    $$ g_i^{(t+1)} = \left\{ \begin{array}{ll} \neg g_i^{(t)} & \mbox{ falls } \chi_i \le p_{mut}\\[5pt] \phantom{\neg} g_i^{(t)} & \mbox{ sonst } \end{array} \right. $$

    =>$\chi_i$ gleichverteilte Zufallsvariable (Intervall $[0,1]$), für jedes Bit $g_i$ neu bestimmen

Anmerkung: Die optimale Mutationsrate $p_{mut}^*$ ist von Länge $m$ des Bitstrings abhängig; annäherbar durch $p_{mut}^* \approx 1/m$.

Die beim Crossover erstellten Nachfolger liegen im Suchraum in der Nähe der Eltern. Durch die Mutationsrate bestimmt man, ob und wie weit sich ein Kind entfernen kann. Dies entspricht dem Bild des "Schüttelns" der Zustandslandschaft.

Bei ES unterscheidet man Mutationswahrscheinlichkeit und Mutationsrate. Es wird parameterweise mutiert.

Bewertungskriterien

Vorsicht: Es handelt sich um Zufallsexperimente. Wenn man nicht nur direkt nach einer Lösung sucht, sondern beispielsweise Parametereinstellungen oder die Wahl der Fitnessfunktion für ein Problem vergleichen will, muss man jeweils mehrere Experimente mit der selben Einstellung machen und Kenngrößen berechnen.

Geschwindigkeit: AES Average Evaluations to a Solution $$ \mbox{AES } = \frac{\sum\limits_{i \in \mbox{erfolgreiche Läufe}} \mbox{Generationen von Lauf } i}{\mbox{Anzahl der erfolgreichen Läufe}} $$

Die AES liegt im Intervall $[0, maxGen]$.

Lösungswahrscheinlichkeit: SR Success Rate $$ \mbox{SR } = \frac{\mbox{Anzahl der erfolgreichen Läufe}}{\mbox{Anzahl aller Läufe}} $$

Die SR liegt im Intervall $[0, 1]$.

Typische Läufe

• Populationsgröße $\mu=15$
• Anzahl Nachfahren $\lambda=100$
• Abbruch nach $maxGen=200$ Generationen

Stochastischer Algorithmus! Ausreichend Wiederholungen durchführen und mitteln!

Hinweis: Die Parameter müssen problemabhängig gewählt werden. Zu hohe Werte für $\mu$ und $\lambda$ führen dazu, dass man bei kleinen Problemen mit hoher Wahrscheinlichkeit bereits am Anfang eine Lösung "würfelt", also gar kein GA nutzt. Wenn dies allerdings nicht passiert, sorgt eine hohe Populationsgröße dafür, dass jeder Schritt sehr lange dauert. Die Abbruchgrenze ist ebenfalls mit Augenmaß zu wählen: Ein zu kleiner Wert sorgt für zu frühen Abbruch (keine Lösung!), ein zu hoher Wert sorgt beim Festfressen des Algorithmus für eine unnötige weitere "Suche" ...

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Evolutionäre Algorithmen:
  • Begriffe: Individuum, Population, Kodierung
  • Operationen: Selektion, Rekombination, Mutation
  • Bewertung mit Fitnessfunktion

Einführung Optimale Spiele

Backgammon: Zwei Spieler, was ist der beste Zug?

Quelle: "position-backgammon-decembre" by serialgamer_fr on Flickr.com (CC BY 2.0)

Zwei Spieler, ein Spielstand und ein Würfelergebnis: Was ist jetzt der beste Zug?!

Motivation: Unterschied zu Suche?!

=> Mehrere konkurrierende Agenten an Suche beteiligt!

=> (Re-) Aktion des Gegners unbekannt/nicht vorhersehbar.

Spiele und Umgebungen

=> Bis auf Roboterfußball in KI traditionell keine physischen Spiele!

Brettspiele sind interessant für KI

• Brettspiele gut abstrakt darstellbar:

  • Zustände einfach repräsentierbar
  • Aktionen wohldefiniert (und i.d.R. sehr einfach)
  • Realisierung als Suchproblem möglich

• Problem: Suchbäume werden in Praxis riesig

  Beispiel Schach:

  • Im Mittel 35 Aktionen (branching factor) von jeder Position
  • Oft mehr als 40 Züge pro Spieler => Suchbäume mit mehr als 80 Ebenen
  • $35^{80} \approx 10^{123}$ mögliche Knoten!
  • (Aber "nur" rund $10^{40}$ verschiedene Zustände)

  Quelle: [Russell2020, pp. 193-196]

Eigenschaften guter Spielalgorithmen

• Zeit begrenzt

  • Irgendeine gute Entscheidung treffen! => Bewertungsfunktion (auch für Zwischenzustände)

• Speicher begrenzt

  • Evaluierungsfunktion für Zwischenzustände
  • Löschen von irrelevanten Zweigen

• Strategien nötig

  • Vorausschauend spielen (Züge "vorhersehen")

Wrap-Up

• Spiele kann man als Suchproblem betrachten
• Merkmale:
  • Mehrere Agenten beteiligt
  • Beobachtbarkeit der Umgebung
  • Zufallskomponente
  • Spielstrategie
• Problem: Riesige Spielbäume
• Umgang mit begrenzten Ressourcen (Zeit, Speicher)

Minimax

Spiele als Suchproblem: Minimax

Terminologie

• Zwei abwechselnd spielende Spieler: MAX und MIN, wobei MAX beginnt

  • Beide Spieler spielen in jedem Zug optimal
  • Spielergebnis wird aus Sicht von MAX bewertet:
    • $+1$, wenn Spieler MAX gewinnt
    • $-1$, wenn Spieler MIN gewinnt
    • $0$, wenn unentschieden
  • Spieler MAX versucht, das Spielergebnis zu maximieren
  • Spieler MIN versucht, das Spielergebnis zu minimieren

• Startzustand: Initialer Zustand des Spielbrettes

• Aktionen: Legale Züge, abhängig vom Spielzustand

• Zieltest: Ist das Spiel vorbei?

  => Startzustand und anwendbare Aktionen definieren den Zustandsraum.

• Nutzenfunktion: $\operatorname{UTILITY}(s,p)$: Wert des Spiels für Spieler $p$ im Spielzustand $s$

• Strategie: Spieler benötigen Strategie, um zu gewünschtem Endzustand zu kommen (unabhängig von den Entscheidungen des Gegenspielers) => einfacher Pfad von Start zu Ziel reicht nicht

Hinweis: Nullsummenspiel! (Der Gewinn des einen Spielers ist der Verlust des anderen Spielers.)

Eine mit dem Minimax-Algorithmus berechnete Strategie wird auch Minimax-Strategie genannt. Sie sichert dem betreffenden Spieler den höchstmöglichen Gewinn, der unabhängig von der Spielweise des Gegners erreichbar ist.

Bei Nicht-Nullsummenspielen, bei denen die Niederlage des Gegners nicht zwangsläufig mit dem eigenen Gewinn zusammenfällt (d.h. Gewinn des einen Spielers $\ne$ Verlust des anderen Spielers), liefert der Minimax-Algorithmus nicht unbedingt eine optimale Strategie.

Spielbaum TTT

Minimax (Idee)

1. Erzeuge kompletten Suchbaum mit Tiefensuche
2. Wende Nutzenfunktion (Utility) auf jeden Endzustand an
3. Ausgehend von Endzuständen => Bewerte Vorgängerknoten:
   • Knoten ist Min-Knoten: Nutzen ist das Minimum der Kindknoten
   • Knoten ist Max-Knoten: Nutzen ist das Maximum der Kindknoten
4. Startknoten: Max wählt den Zug, der zum Nachfolger mit der höchsten Bewertung führt

Annahme: Beide spielen perfekt. Fehler verbessern das Resultat für den Gegner.

Minimax-Algorithmus: Funktionen für MAX- und MIN-Knoten

def Max-Value(state):
    if Terminal-Test(state): return Utility(state)

    v = -INF
    for (a, s) in Successors(state):
        v = MAX(v, Min-Value(s))
    return v

def Min-Value(state):
    if Terminal-Test(state): return Utility(state)

    v = +INF
    for (a, s) in Successors(state):
        v = MIN(v, Max-Value(s))
    return v

Hinweis I: Auf wikipedia.org/wiki/Minimax finden Sie eine Variante mit einem zusätzlichen Tiefenparameter, um bei einer bestimmten Suchtiefe abbrechen zu können. Dies ist bereits eine erweiterte Version, wo man beim Abbruch durch das Erreichen der Suchtiefe statt Utility() eine Eval()-Funktion braucht (vgl. Minimax: Heuristiken).

Wenn man ohne Suchtiefenbeschränkung arbeiten will, braucht man diesen Parameter nicht! Der Algorithmus terminiert auch ohne Suchtiefenbeschränkung!

Hinweis II: Im [Russell2020, S. 196, Abb. 6.3] findet sich eine Variante, die die auf der nächsten Folien gezeigte Startfunktion mit den hier gezeigten Min-Value()- und Max-Value()-Funktionen verschmilzt. Dabei wird in den beiden Hilfsfunktionen nicht nur der min- bzw. max-Wert optimiert, sondern auch der jeweils beste Zug gespeichert und als Rückgabe zurückgeliefert.

Minimax-Algorithmus: Sonderbehandlung Startknoten

def Minimax(state):
    (val, action) = (-INF, null)
    for (a, s) in Successors(state):
        v = Min-Value(s)
        if (val <= v):
            (val, action) = (v, a)
    return action

• Startknoten ist ein MAX-Knoten
• Nicht nur Kosten, sondern auch die zugehörige Aktion speichern

Minimax Beispiel

Aufwand Minimax

• maximale Tiefe des Spielbaums: $m$
• in jedem Zustand $b$ gültige Züge
• => Zeitkomplexität $O(b^m)$

Gedankenexperiment:

• erster Zug: $b$ Möglichkeiten,
• zweiter Zug: jeweils wieder $b$ Möglichkeiten $\rightarrow$ $b \star b = b^2$,
• dritter Zug: jeweils wieder $b$ Möglichkeiten $\rightarrow$ $b \star (b \star b) = b^3$,
• ...,
• $m$. Zug: jeweils wieder $b$ Möglichkeiten $\rightarrow$ $b^m$

Wrap-Up

• Minimax: Entwickelt Spielbaum, bewertet Zustände entsprechend Max und Min
  • Gewinn von Max: +1, Gewinn von Min: -1
  • Max wählt das Maximum der möglichen Züge von Min
  • Min wählt das Minimum der möglichen Züge von Max
  • Spielbaum wird bis zu den Blättern entwickelt, Bewertung mit Utility

Heuristiken

Wenn die Zeit nicht reicht: Suchtiefe begrenzen

• Einführung neuer Funktionen:

  1. Cutoff-Test statt Terminal-Test

     Beispielsweise bei erreichter Tiefe oder Zeitüberschreitung

  2. Eval statt Utility

     Bewertung der erreichten Position (statt nur Bewertung des Endzustandes)

• Bedingungen an Eval:

  1. Endknoten in selber Reihenfolge wie bei Utility
  2. Schnell zu berechnen (!)

Beispiel Schach

• Mögliche Evaluierungskriterien:

  • Materialwert: Bauer 1, Läufer/Springer 3, Turm 5, Dame 9
  • Stellungsbewertung: Sicherheit des Königs, Stellung der Bauern
  • Daumenregeln: 3 Punkte Vorteil => sicherer Sieg

• Nutzung gewichteter Features $f_i$: $\operatorname{Eval}(s) = w_1f_1(s) + w_2f_2(s) + \ldots$

  • Beispiel: $w_1 = 9$ und $f_1(s)$ = (# weiße Königinnen) - (# schwarze Königinnen)

• Alternativ: Speicherung von Positionen plus Bewertung in Datenbanken => Lookup mit $\operatorname{Eval}(s)$ (statt Berechnung zur Laufzeit)

Minimax mit mehreren Spielern

Hier maximiert jeder Spieler sein eigenes Ergebnis. Im Grunde müsste diese Variante dann besser "Maximax" heissen ...

Wenn es an einer Stelle im Suchbaum mehrere gleich gute (beste) Züge geben sollte, kann der Spieler Allianzen bilden: Er könnte dann einen Zug auswählen, der für einen der Mitspieler günstiger ist.

Zufallsspiele

Quelle: "position-backgammon-decembre" by serialgamer_fr on Flickr.com (CC BY 2.0)

Backgammon: Was ist in dieser Situation der optimale Zug?

Minimax mit Zufallsspielen: ZUFALLS-Knoten

Zusätzlich zu den MIN- und MAX-Knoten führt man noch Zufalls-Knoten ein, um das Würfelergebnis repräsentieren zu können. Je möglichem Würfelergebnis $i$ gibt es einen Ausgang, an dem die Wahrscheinlichkeit $P(i)$ dieses Ausgangs annotiert wird.

=> Für Zufallsknoten erwarteten Minimax-Wert (Expectimax) nutzen

Minimax mit Zufall: Expectimax

Expectimax-Wert für Zufallsknoten $C$:

• $i$ mögliches Würfelergebnis
• $P(i)$ Wahrscheinlichkeit für Würfelergebnis
• $s_i$ Nachfolgezustand von $C$ gegeben Würfelergebnis $i$

Für die normalen Min- und Max-Knoten liefert Expectimax() die üblichen Aufrufe von Min-Value() bwz. Max-Value().

Auf wikipedia.org/wiki/Expectiminimax finden Sie eine Variante mit einem zusätzlichen Tiefenparameter, um bei einer bestimmten Suchtiefe abbrechen zu können. Dies ist bereits eine erweiterte Version, wo man beim Abbruch durch das Erreichen der Suchtiefe statt Utility() eine Eval()-Funktion braucht. Zusätzlich kombiniert der dort gezeigte Algorithmus die Funktionen Expectimax(), Min-Value() und Max-Value() in eine einzige Funktion.

Eine ähnliche geschlossene Darstellung finden Sie im [Russell2020, S. 212].

Hinweis: Üblicherweise sind die Nachfolger der Zufallsknoten gleich wahrscheinlich. Dann kann man einfach mit dem Mittelwert der Bewertung der Nachfolger arbeiten.

Wrap-Up

• Minimax:
  • Kriterien zur Begrenzung der Suchtiefe, Bewertung Eval statt Utility
  • Erweiterung auf $>2$ Spieler
  • Erweiterung auf Spiele mit Zufall: Expectimax

Alpha-Beta-Pruning

Verbesserung Minimax-Algorithmus

=> Minimax-Baum: Verbesserungen möglich?

Alpha-beta-Pruning

Minimax-Algorithmus mit zusätzlichen Informationen:

• $\alpha$: bisher bester Wert für MAX (höchster Wert)
• $\beta$: bisher bester Wert für MIN (kleinster Wert)

=> Beobachtungen:

1. $\alpha$ für MAX-Knoten wird nie kleiner
2. $\beta$ für MIN-Knoten wird nie größer

Pruning-Regeln

1. Schneide (unter) MIN-Knoten ab, deren $\beta$ $\le$ dem $\alpha$ des MAX-Vorgängers ist.

2. Schneide (unter) MAX-Knoten ab, deren $\alpha$ $\ge$ dem $\beta$ des MIN-Vorgängers ist.

Alpha-beta-Pruning -- Der Algorithmus (Skizze)

def Max-Value(state, alpha, beta):
    if Terminal-Test(state): return Utility(state)

    v = -INF
    for (a, s) in Successors(state):
        v = MAX(v, Min-Value(s, alpha, beta))
        if (v >= beta): return v
        alpha = MAX(alpha, v)
    return v

def Min-Value(state, alpha, beta):
    if Terminal-Test(state): return Utility(state)

    v = +INF
    for (a, s) in Successors(state):
        v = MIN(v, Max-Value(s, alpha, beta))
        if (v <= alpha): return v
        beta = MIN(beta, v)
    return v

Initialer Aufruf von Max-Value() mit $\alpha = -\infty$ und $\beta = +\infty$

Achtung: Es kursieren Varianten von diesem Algorithmus, bei denen auf die Hilfsvariable v verzichtet wird und stattdessen alpha bzw. beta direkt modifiziert werden und als Rückgabewert dienen. Das kann zu anderen oder falschen Ergebnissen führen! Sie können das in der Aufgabe auf Blatt 03 gut beobachten.

Alpha-beta-Pruning -- Eigenschaften

1. Pruning beeinflusst nicht das Endergebnis!

2. Sortierung der Nachfolger spielt große Rolle

3. Perfekte Sortierung: $O(b^{d/2})$ => Verdopplung der Suchtiefe möglich

Für Schach immer noch zu aufwändig ...

Verbesserungen für Alpha-beta-Pruning

• "Killer-Move": Maximale Effizienz nur wenn optimaler Zug immer zuerst untersucht => Zu untersuchende Züge sortieren/priorisieren, zb. Schach: a) Figuren schlagen b) Drohen c) Vorwärts ziehen d) Rückwärts ziehen

• Verändern der Suchtiefe nach Spielsituation

• Bewertungsfunktion Eval:

  • Datenbanken mit Spielsituationen und Expertenbewertung:
    • Eröffnungsspiele (besonders viele Verzweigungen)
    • Endspiele
  • Lernen der optimalen Gewichte für Eval-Funktion
  • Berücksichtigung von Symmetrien

Beispiel DeepBlue (IBM, 1997)

• Alpha-beta-Pruning mit Tiefenbeschränkung: ca. 14 Halbzüge
• Dynamische Tiefenbeschränkung (stellungsabhängig, max. ca. 40 Züge)
• Heuristische Stellungsbewertung Eval:
  • mehr als 8.000 Features
  • ca. 4.000 Eröffnungsstellungen
  • ca. 700.000 Spielsituationen (von Experten bewertet)
  • Endspiel-Datenbank: alle Spiele mit 5 Steinen, viele mit 6 Steinen

Quelle: [Russell2014, p. 185]

Beispiel AlphaGo (Google, 2016)

• Beschränkung der Suchtiefe: Bewertung der Stellung durch "Value Network"

• Beschränkung der Verzweigungsbreite: Bestimmung von Zugkandidaten durch "Policy Network"

• Training dieser "Deep Neural Networks":

  • Überwachtes Lernen: "Analyse" von Spiel-Datenbanken
  • Reinforcement-Lernen: Self-Play, Bewertung am Ende
    • Züge mit Monte-Carlo-Baumsuche ausgewählt

Quelle: [Silver2016], siehe auch deepmind.com/research/alphago/

Wrap-Up

• Alpha-beta-Pruning:

  • Mitführen der bisher besten Werte für MAX und MIN: $\alpha$ und $\beta$
  • Abschneiden von Pfaden, die Verschlechterung bewirken würden
  • Endergebnis bleibt erhalten
  • Effizienzsteigerung abhängig von Sortierung der Nachfolger

• Viele Verbesserungen denkbar:

  • Zu untersuchende Züge "richtig" sortieren (Heuristik)
  • Suchtiefe begrenzen und Bewertungsfunktion (statt Nutzenfunktion)
  • Positionen mit Datenbank abgleichen

Einführung Constraints

Motivation: Einfärben von Landkarten

Die Skizze soll eine Landkarte mit verschiedenen Ländern darstellen. Die Aufgabe lautet: Färbe jedes Land mit einer Farbe ein, um die Übersichtlichkeit zu erhöhen. Verwende dabei so wenig wie möglich unterschiedliche Farben. Aneinander grenzende Länder müssen unterschiedliche Farben bekommen (=> Constraint).

Einfärben von Landkarten: Formalisierung

• Variablen: A, B, C, D, E, F

• Werte: $\lbrace red, green, blue \rbrace$

• Constraints: Benachbarte Regionen müssen unterschiedliche Farben haben

• Mögliche Lösung: Zuweisung an Variablen ("Belegung") $\lbrace \operatorname{A} = red, \operatorname{B} = blue, \operatorname{C} = green, \operatorname{D} = red, \operatorname{E} = blue, \operatorname{F} = blue \rbrace$

Definition: Constraint Satisfaction Problem (CSP)

• Ein CSP $\langle V, D, C \rangle$ besteht aus:

  • Menge von Variablen $V = \lbrace V_1, V_2, \ldots, V_n \rbrace$
  • Je $V_i$ nicht leere Domäne $D_i = \lbrace d_{i,1}, d_{i,2}, \ldots, d_{i,m_i} \rbrace$
  • Menge von Constraints $C = \lbrace C_1, C_2, \ldots, C_p \rbrace$ (Randbedingungen, Abhängigkeiten zwischen Variablen)

• Zuweisung/Belegung (Assignment) $\alpha$:

  • Zuweisung von Werten an (einige/alle) Variablen: $\alpha = \lbrace X=a, Y=b, \ldots \rbrace$ (aus den jeweiligen Wertebereichen)
  • Konsistente Belegung: Randbedingungen sind nicht verletzt
  • Vollständige Belegung: Alle Variablen sind belegt

• Lösung eines CSP: Vollständige und konsistente Belegung

Constraint-Graph

Ein CSP kann man auch als Constraint-Graph darstellen. Die Variablen werden zu Knoten im Graph, die Constraints zu Kanten zwischen den Knoten. Dadurch kann man die aus dem Problemlösen bekannten Algorithmen anwenden ...

Constraints -- Arität

Die Arität betrifft hier die "Stelligkeit": Wie viele Variablen stehen in einem Constraint miteinander in Beziehung? (Also wie viele Parameter hat ein Constraint?)

• unär: betrifft einzelne Variablen Beispiel: $\operatorname{A} \neq red$

• binär: betrifft Paare von Variablen Beispiel: $\operatorname{A} \neq \operatorname{B}$

• höhere Ordnung: betrifft 3 oder mehr Variablen

• Präferenzen: "soft constraints" Beispiel: "rot ist besser als grün"

  Abbildung über Gewichtung => Constraint-Optimierungsproblem (COP)

Constraints -- Wertebereiche

• Endliche Domänen: $d$ Werte => $O(d^n)$ mögliche Zuweisungen (exponentiell in der Zahl der Variablen)

• Unendliche Domänen: reelle Zahlen, natürliche Zahlen => Keine Auflistung der erlaubten Wertekombinationen mehr möglich => Übergang zu Gleichungen/Ungleichungen: $job_1+5

  • lineare Constraints
  • nichtlineare Constraints

Historische Unterscheidung:

• Constraint Satisfaction: endliche Domänen, kombinatorische Methoden
• Constraint Solving: unendliche Domänen

CSP sind überall ...

• Stundenpläne (Klassen, Räume, Zeiten)
• Konfiguration (Computer, Autos, ...)
• Fahrpläne (Zug, Flug, ...)
• Planung von komplexen Projekten
• Sudoku :-)
• ...

Wrap-Up

• Definitionen und Begriffe:
  • Variable, (un-) endliche Domänen, Wertemenge
  • Constraint, Arität, CSP
  • Zuweisung, Lösung, ...

Lösen von diskreten CSP

Einfärben von Landkarten als CSP

Endliche Domänen: Formulierung als Suchproblem

def BT_Search(assignment, csp):
    if complete(assignment): return assignment

    var = VARIABLES(csp, assignment)

    for value in VALUES(csp, var):
        if consistent(value, var, assignment, csp):
            assignment += {var = value}

            if INFERENCE(csp, assignment, var) != failure:
                result = BT_Search(assignment, csp)
                if result != failure: return result

            assignment -= {var = value}

    return failure

Quelle: Eigener Code basierend auf einer Idee nach [Russell2020, p. 176, fig. 5.5]

Hierbei handelt es sich um eine etwas angepasste Tiefensuche: Starte mit leerem Assignment und weise schrittweise Variablen passende Werte zu und mache notfalls Backtracking.

BT-Suche für CSP am Beispiel Landkartenfärbeproblem

Wrap-Up

• Lösung von CSP mit endlichen Domänen mit Hilfe der Backtracking-Suche

Heuristiken

VARIABLES: Variablen-Sortierung, Welche Variable soll betrachtet werden?

VARIABLES: Welche Variable zuerst ausprobieren?

Minimum Remaining Values (MRV): (vgl. [Russell2020, S. 177])

• Wähle Variable mit wenigsten freien Werten (die am meisten eingeschränkte Variable)

  => reduziert den Verzweigungsgrad

Beispiel:

1. Freie Auswahl, alle haben gleich viele freie Werte (jeweils 3) => wähle A
2. B und C haben nur noch zwei freie Werte => wähle B (oder C)
3. C hat nur noch einen Wert, D noch zwei, der Rest drei => wähle C

VARIABLES: Gleichstand bei MRV

VARIABLES: Welche Variable zuerst ausprobieren?

Gradheuristik: Erweiterung von MRV bei Gleichstand (vgl. [Russell2020, S. 177])

• Wähle Variable mit meisten Constraints auf offene (noch nicht zugewiesene) Variablen

  => reduziert den Verzweigungsgrad in späteren Schritten

Beispiel:

1. MRV: Alle haben gleich viele freie Werte (jeweils 3) => Gradheuristik: B, C und D haben die meisten Verbindungen (Constraints) auf offene Variablen => wähle B (oder C oder D)
2. MRV: A, C und D haben nur noch zwei freie Werte => Gradheuristik: C und D haben je zwei Constraints auf noch offene Variablen => wähle C (oder D)
3. MRV: A und D haben beide nur noch einen Wert => Gradheuristik: D hat die meisten Verbindungen (Constraints) auf offene Variablen => wähle D

VALUES: Werte-Sortierung, Welchen Wert soll ich ausprobieren?

VALUES: Welchen Wert zuerst ausprobieren?

Least Constraining Value (LCV): (vgl. [Russell2020, S. 177])

• Wähle Wert, der für verbleibende Variablen die wenigsten Werte ungültig macht

  => verringert die Wahrscheinlichkeit für Backtracking

Beispiel:

1. Sei A gewählt: Alle Werte machen in den anderen Variablen einen Wert ungültig => freie Wahl des Wertes => wähle beispielsweise rot
2. Sei B gewählt: Alle Werte machen in den anderen Variablen einen Wert ungültig => freie Wahl des Wertes => wähle beispielsweise grün
3. Sei D gewählt: Verbleibende Werte rot und blau
   • Wahl von rot würde für C einen Wert übrig lassen (blau)
   • Wahl von blau würde für C keinen Wert übrig lassen => LCV: Wahl von rot!

Hinweis: Diese Heuristik ist in der Praxis sehr aufwändig zu berechnen! Man müsste für jeden Wert die noch offenen Constraints anschauen und berechnen, wie viele Werte damit jeweils ungültig gemacht werden. Die Idee ist aber dennoch interessant, und möglicherweise kann man sie für ein reales Problem so adaptieren, dass bei der Umsetzung nur wenig zusätzlicher Aufwand entsteht.

Wrap-Up

• Verbesserung der BT-Suche mit Heuristiken: MRV, Gradheuristik, LCV

Kantenkonsistenz und AC-3

Problem bei BT-Suche

Zuweisung eines Wertes an Variable $X$:

• Passt zu aktueller Belegung
• Berücksichtigt aber nicht restliche Constraints => macht weitere Suche u.U. unmöglich/schwerer

Lösung: Nach Zuweisung alle nicht zugewiesenen Nachbarvariablen prüfen

INFERENCE: Vorab-Prüfung (Forward Checking)

Inference: Frühzeitiges Erkennen von Fehlschlägen! (vgl. [Russell2020, S. 178])

Nach Zuweisung eines Wertes an Variable $X$:

• Betrachte alle nicht zugewiesenen Variablen $Y$:
  • Falls Constraints zw. $X$ und $Y$, dann ...
  • ... entferne alle inkonsistenten Werte aus dem Wertebereich von $Y$.

Beispiel:

1. Sei A auf rot gesetzt => entferne rot in B und C
2. Sei D auf grün gesetzt => entferne grün in B und C und E

Problem: Für B und C bleibt nur noch blau; sind aber benachbart!

Forward Checking findet nicht alle Inkonsistenzen!

• Nach $\lbrace A=red, D=green \rbrace$ bleibt für B und C nur noch blue
• B und C sind aber benachbart

Übergang von Forward Checking zu Kantenkonsistenz

• Forward Checking erzeugt Konsistenz für alle Constraints der gerade betrachteten (belegten) Variablen.

• Idee: Ausdehnen auf alle Kanten ... => Einschränken der Wertemengen

Definition Kantenkonsistenz (Arc Consistency)

Eine Kante von $X$ nach $Y$ ist "konsistent", wenn für jeden Wert $x \in D_X$ und für alle Constraints zwischen $X$ und $Y$ jeweils ein Wert $y \in D_Y$ existiert, so dass der betrachtete Constraint durch $(x,y)$ erfüllt ist.

Ein CSP ist kanten-konsistent, wenn für alle Kanten des CSP Konsistenz herrscht.

Beispiel Kantenkonsistenz

$D_a=D_b=D_c=\lbrace 1,2,3 \rbrace$, $D_d=\lbrace 1,2 \rbrace$, $D_e=\lbrace 1,2,3 \rbrace$

Einschränkung der Ausgangswertemengen (kanten-konsistent)

$D_a=\lbrace 1,2,3 \rbrace$, $D_b=\lbrace 1,2 \rbrace$, $D_c=\lbrace 1,2 \rbrace$, $D_d=\lbrace 1,2 \rbrace$, $D_e=\lbrace 2,3 \rbrace$

Anmerkung: $((a,b), \ne)$ ist Kurzform für $\left((a,b), \lbrace (x,y) \in D_a \times D_b | x \ne y \rbrace\right)$

AC-3 Algorithmus: Herstellen von Kantenkonsistenz

def AC3(csp):
    queue = Queue(csp.arcs)
    while not queue.isEmpty():
        (x,y) = queue.dequeue()
        if ARC_Reduce(csp,x,y):
            if D_x.isEmpty(): return false
            for z in x.neighbors(): queue.enqueue(z,x)
    return true

def ARC_Reduce(csp, x, y):
    change = false
    for v in D_x:
        if not (any w in D_y and csp.C_xy(v,w)):
            D_x.remove(v);  change = true
    return change

Quelle: Eigener Code basierend auf einer Idee nach [Russell2020, p. 171, fig. 5.3]

Anmerkung: Die Queue in AC-3 ist wie eine (mathematische) Menge zu betrachten: Jedes Element kann nur genau einmal in einer Menge enthalten sein. D.h. wenn man bei queue.enqueue(z,x) die Rückkanten von den Nachbarn in die Queue aufnimmt, sorgt die Queue eigenständig dafür, dass es keine doppelten Vorkommen einer Kante in der Queue gibt. (Falls die verwendete Queue in einer Programmiersprache das nicht unterstützt, müsste man bei queue.enqueue(z,x) stets abfragen, ob die Kante (z,x) bereits in der Queue ist und diese dann nicht erneut hinzufügen.) AC-3 hat eine Laufzeit von $O(d^3n^2)$ ($n$ Knoten, maximal $d$ Elemente pro Domäne). Leider findet auch AC-3 nicht alle Inkonsistenzen ... (NP-hartes Problem).

Hinweis: In gewisser Weise kann man Forward Checking als ersten Schritt bei der Herstellung von Kantenkonsistenz interpretieren.

Einsatz des AC-3 Algorithmus

1. Vorverarbeitung: Reduktion der Wertemengen vor BT-Suche

   • Nach AC-3 evtl. bereits Lösung gefunden (oder ausgeschlossen)

2. Propagation: Einbetten von AC-3 als Inferenzschritt in BT-Suche (MAC -- Maintaining Arc Consistency)

   • Nach jeder Zuweisung an $X_i$ Aufruf von AC-3-Variante:
     • Initial nur Kanten von $X_i$ zu allen noch nicht zugewiesenen Nachbarvariablen
   • Anschließend rekursiver Aufruf von BT-Suche

Wrap-Up

• Anwendung von Forward Checking und ...
• ... die Erweiterung auf alle Kanten: AC-3, Kantenkonsistenz

Wiederholung Wahrscheinlichkeitstheorie

Ereignisse und Wahrscheinlichkeit

Hinweis: Die folgende Darstellung zur Einführung in die Wahrscheinlichkeitstheorie dient dem Verständnis des Naive Bayes Klassifikationsalgorithmus und ist teilweise eher oberflächlich gehalten. Sie kann und soll keine entsprechende mathematische Einführung ersetzen!

Ereignisse

• Ereignisse $\Omega = \lbrace \omega_1, \omega_2, \ldots, \omega_n \rbrace$: endliche Menge der Ausgänge eines Zufallsexperiments

• Elementarereignis: Die $\omega_i \in \Omega$

  • decken alle möglichen Versuchsergebnisse ab, und
  • schließen sich gegenseitig aus

Regeln

• Wenn $A$ und $B$ Ereignisse sind, dann auch $A \cup B$
• $\Omega$ wird als sicheres Ereignis bezeichnet: Enthält definitionsgemäß alle Versuchsausgänge, d.h. ein in der Menge enthaltenes Ereignis muss auftreten
• Die leere Menge $\emptyset$ wird als unmögliches Ereignis bezeichnet
• Die Variablen $A$ und $B$ heißen auch Zufallsvariablen

Im Rahmen dieser Veranstaltung betrachten wir nur diskrete Zufallsvariablen mit endlichem Wertebereich!

Wahrscheinlichkeit

• Wahrscheinlichkeit:

  Sei $\Omega = \lbrace \omega_1, \omega_2, \ldots, \omega_n \rbrace$ endlich. Die Wahrscheinlichkeit $P(A)$ für ein Ereignis $A$ ist dann definiert als

  $$ P(A) = \frac{|A|}{|\Omega|} = \frac{\text{Anzahl der für A günstigen Fälle}}{\text{Anzahl der möglichen Fälle}} $$

  Man könnte auch schreiben: $P(A) = \sum_{\omega \in A} P(\omega)$

  Hinweis: Diese Definition von Wahrscheinlichkeit geht von gleich wahrscheinlichen Elementarereignissen aus! Die allgemeine Definition geht über einen entsprechenden Grenzwert.

Verteilung

Den Vektor mit den Wahrscheinlichkeiten aller Elementarereignisse nennt man auch Verteilung.

Beispiel: $\mathbf{P}(A) = (P(A=1), P(A=2), \ldots, P(A=6)) = (1/6, 1/6, \ldots, 1/6)$

Hinweis: Wir betrachten hier nur diskrete Zufallsvariablen. Für kontinuierliche Variablen wird die Verteilung mit Hilfe einer Dichtefunktion dargestellt, beispielsweise der Gauss'schen Funktion.

Beispiel

• Einmaliges Würfeln mit einem Spielwürfel: $\Omega = \lbrace 1,2,3,4,5,6 \rbrace$
• Elementarereignisse: $\lbrace 1,2,3,4,5,6 \rbrace$
• Das Würfeln einer geraden Zahl ($A = \lbrace 2,4,6 \rbrace$) ist kein Elementarereignis, ebenso wie das Würfeln einer Zahl kleiner 5 ($B = \lbrace 1,2,3,4 \rbrace$), da $A \cap B = \lbrace 2,4 \rbrace \ne \emptyset$
• Wahrscheinlichkeit, eine 1 zu würfeln: $P(A \in \lbrace 1 \rbrace) = P(A=1) = \frac{1}{6}$. Anmerkung: Man schreibt statt $P(A \in \lbrace 1 \rbrace)$ oft einfach $P(1)$.
• Wahrscheinlichkeit, eine gerade Zahl zu würfeln: $P(A \in \lbrace 2,4,6 \rbrace) = P(A=2 \vee A=4 \vee A=6) = \frac{|\lbrace 2,4,6 \rbrace|}{|\lbrace 1,2,3,4,5,6 \rbrace|} = \frac{3}{6} = 0.5$