Kapitel 7 - Lernen aus Beobachten
Nennen Sie die Bestandteile des Allgemeinen Modells lernender Agenten!
- Performanzelement
- Lernelement
- Kritik
- Problemgenerator
Was macht das Performanzelement?
Es wählt externe Aktionen auf Grund von Wahrnehmungen aus. Es steht also für
das, was bisher der ganze Agent war.
Was macht das Lernelement?
Das Lernelement ist dafür zuständig Verbesserungen vorzunehmen. Es nimmt als
Input Wissen über das Performanzelement und die Rückmeldung aus der Kritikeinheit.
Es gibt Verbesserungen an das Performanzelement aus, so daß sich der Agent in
Folgeaktionen besser verhält.
Was macht die Kritik-Einheit?
Sie beurteilt das Verhalten des Agenten und sagt dem Lernelement, wie gut sich
der Agent verhält. Sie verwendet als Referenz einen fixen extern eingegebenen
Performanzstandart, welcher nicht Teil des Agenten ist. Diese Referenz ist
notwendig, weil die Wahrnehmungen des Agenten alleine nicht ausreichen, um Aussagen
über die Qualität des Agenten treffen zu können. Wäre der Performanzstandard
Bestandteil des Agenten, könnte er den Standard an sein Verhalten anpassen.
Was soll der Problemgenerator bewirken?
Er Schlägt Aktionen vor, die zu neuen und informativen Erfahrungen führen.
Diese Einheit verleit dem Agenten ein exploratives Verhalten. Ohne
diese Einheit, würde der Agent nie etwas neues probieren, sondern immer nur
Aktionen basierend auf seinem aktuellen Wissen ausführen.
An welchen vier Punkten orientiert sich der Entwurf des Lernelements?
- Welche Komponenten des Performanzelements müssen verbessert werden?
- Welche Repräsentation wird für diese Komponenten benutzt?
- Welche Rückmeldung ist erhältlich?
- Welche Vorabinformation ist erhältlich?
Welche weiteren Komponenten hat ein Performanzelement?
- Direkte Abbildung von Bedingungen auf Aktionen über den aktuellen Zustand
- Hilfsmittel zur Ableitung relevanter Eigenschaften der Welt aus den
Wahrnehmungsfolgen
- Informationen über Art und Weise, wie sich Welt verändert
- Informationen über Ergebnisse möglicher Aktionen des Agenten
- Nützlichkeitsinformationen, die die Wünschbarkeit von Weltzuständen anzeigen
- Action-Wert-Informationen, welche die Wünschbarkeit spezieller Aktionen in
speziellen Weltzuständen anzeigen
- Ziele, die Klassen von Zuständen definieren, deren Erreichen den Nutzen des
Agenten Maximieren
Jede dieser Komponenten kann gelernt werden, wenn der Agent das entsprechende
Feedback erhält. Die Komponenten können unterschiedlich repräsentiert werden
(logische Sätze oder probabilistische Formalismen wie Bayessche
Netze). Es gibt verschiedenste Lernalgorithmen, welche aber alle auf der
gleichen Grundlage operieren.
Nennen Sie die drei grundlegenden Methoden des Lernens!
Überwachendes Lernen
Der Agent kann das Ergebnis seiner Aktionen beobachten oder es wird ihm
mitgeteilt. ("Lernen durch Lehrer")
Reinforcement Learning
Der Agent erhält eine Reaktion als Belohnung oder Bestrafung. Es wird ihm aber
nicht gesagt, was die richtige Aktion ist. Das muß Agent selbst erforschen.
Nicht überwachendes Lernen
Der Agent erhält kein Feedback über die Wirkungen seiner
Aktionen. Er kann nur Beziehungen zwischen seinen Wahrnehmungen lernen. Falls er
keine Nutzenfunktion hat, kann der Agent nicht lernen was er tun soll.
Wodurch definiert sich induktives Lernen?
Beim überwachenden Lernen bekommt der Lehrer eine Menge von
Beispielen vorgelegt und soll daraus eine Funktion erlernen. Beispiele haben die
Form
(x,f(x))
, mit x als Eingabe und f(x) als Ausgabe der zu lernenden Funktion.
Eine reine induktive Inferenz (Induktion) besteht aus der Aufgabe:
- Bestimme auf Basis einer Menge von Beispielen von f eine Funktion h, genannt
die Hypothese, welche f approximiert
- Im Allgemeinen können viele Hypothesen aus Beispielen generiert werden
- Wird einer Hypothese einer anderen bevorzugt, so heißt dies ein
Bias
- Da es meist immer eine Großzahl konsistenter Hypothesen gibt, haben
Lernalgorithmen einen irgendwie gearteten Bias
Die einfachste Form eines lernenden Agenten ist ein reflexiver lernender
Agent. Er kann (Wahrnehmung, Aktion)-Paare erlernen. Die Grundstruktur eines
solchen Agenten besteht aus
- REFLEX-PERFORMANCE-ELEMENT
- REFLEX-LEARNING-ELEMENT
Klassifizieren Sie die drei Arten von Lernalgorithmen!
- Lernalgorithmen auf Basis Logischer Sätze als Entscheidungsbäume oder
Versionsraum-Ansatz
- Lernalgorithmen auf Basis nicht linearer numerischer Funktionen als neuronale
Netze
- Lernalgorithmen auf Basis Bayesscher Netze
Lernen von Entscheidungsbäumen
Was wissen Sie über Entscheidungsbäume als Performanzelemente?
Ein Entscheidungsbaum nimmt als Eingabe ein Beschreibung eines Objekt oder
einer Situation. Er gibt als Ausgabe ein Wahr oder Falsch an und repräsentiert
somit eine boolesche Funktion. Eine Repräsentation höherwertiger Funktionen aber
auch möglich. Ein innerer Knoten entspricht einen Test auf den Wert einer der
Eigenschaften. Ein Blattknoten entspricht einem booleschen Wert.
Welche Ausdruckskraft haben Entscheidungsbäume?
Entscheidungsbäume repräsentieren Mengen von Implikationen. Sie können nicht
beliebige Mengen von Sätzen der Logik erster Stufe repräsentieren. Sie können nur
Aussagen über einzelne Objekte (Knoten) treffen. Aussagen über eine Objektmenge
sind nicht möglich.
Deshalb ist die Entscheidungsbaumsprache im wesentlichen auch aussagenlogisch. Die
Ausdruckskraft von Entscheidungsbäumen entspricht genau der der
Aussagenlogik.
Jede boolesche Funktion oder aussagenlogischer Satz kann als Baum dargestellt
werden. Man braucht nur die Wahrheitstabelle zu iterieren und jede Zeile als Pfad
im Baum interpretieren. Nachteilig ist die hohe Komplexität bei bestimmten
Eingaben, welche schnell eine exponentielle Größe erreicht.
Was heißt Induktion von Entscheidungsbäumen aus Beispielen und wie geht dies von
statten?
Es wird versucht aus einer Menge von Datensätzen einen Baum zu generieren. Ein
Beispiel wird durch die Belegung der Attribute und des Zielprädikates spezifiziert.
Der Wert des Zielprädikates heißt Klassifikation des Beispiels.
Ist ein Wert des Beispiels wahr so ist es eine positive, sonst
eine negative Klassifikation. Die gesamte Menge der Beispiele
heißt Trainingsmenge.
Bei der Erstellung eines Entscheidungsbaums soll ein Muster extrahiert werden,
welches möglichst viele Fälle in knapper Form darstellen kann.
Ein Allgemeines Prinzip induktiven Lernens ist Ockhams Rasiermesser.
"Die wahrscheinlichste Hypothese ist die einfachste, die mit allen Beobachtungen
konsistent ist."
Den kleinstmöglichen Entscheidungsbaum zu finden ist nicht lösbar. Aber mit
DECITION-TREE-LEARNING ist es möglich, einen kleinen Baum zu
finden. Dieser Algorithmus testet immer das wichtigste Attribut
zuerst. Damit ist das Attribut gemeint, nach dem sich die Beispiele am meisten
unterscheiden.
Verwendung der Informationstheorie
Erklären Sie das Prinzip des Informationsgewinns!
Die Implementierung der CHOOSE-ATTRIBUTE Funktion ist grundlegend wichtig. Man
benötigt eine Einteilung in gute und unnütze Attribute. Beste Werte sollten
perfekten Attributen zugeschrieben werden und kleinste den wertlosen Attributen.
Information
- Ist im Sinne der Shannonschen Informationstheorie zu
verstehen
- In diesem Sinn ist eine Information eine Antwort auf eine Frage
- Informativ ist eine Antwort dann, wenn sie neue Erkenntnisse bringt
Der Gehalt einer Information wird in Bits gemessen. Ein Bit
genügt, um eine Ja/Nein-Frage zu beantworten. Beim Entscheidungsbaum-Lernen wird
die Wichtigkeit der einzelnen Attribute in Abhängigkeit von der Anzahl enthaltener
positiver und negativer Beispiele berechnet.
Der Informationsgewinn aus dem Attributtest ist definiert durch
die Differenz zwischen dem ursprünglichen Informationsbedarf und dem neuen
(Gain(a)).
Die in der CHOOSE-ATTRIBUT genutzte Heuristik ist genau die, die das Attribut mit
dem größten Informationsgewinn selektiert.
Was ist rauschen Rauschen und Overfitting?
Ist ein allgemeines Problem und tritt nicht nur beim Entscheidungsbaum-Lernen
auf. Wenn eine große Menge möglicher Hypothesen gegeben ist, besteht die Gefahr,
daß man bedeutungslose Regelmäßigkeiten in den Daten entdeckt, welche die Laufzeit
stark verschlechtern. Overfitting kann durch Pruning vermieden
werden.
Wie funktioniert das Pruning?
Entdeckte Attribute, welche für Informationsgehalt irrelevant sind werden
ignoriert. Dazu müssen aber irrelevante Attribute von relevanten unterschieden
werden können. Angenommen man teilt eine Menge von Beispielen mit einem
irrelevanten Attribut auf...
Die entstehenden Teilmengen haben dann in der Regel etwa die selbe Verteilung von
positiven und negativen Beispielen wie die ursprüngliche Menge. Damit ist der
Informationsgewinn annähernd null.
Damit stellt sich aber die Frage, ab wann es sich lohnt ein Attribut zur Aufteilung
einer Menge zu verwenden und wann nicht.
Dazu werden Signifikanztests herangezogen...
- Er beginnt mit Annahme, es gebe kein zugrundeliegendes Muster
(Nullhypothese)
- Dann wird berechnet, wie weit die Daten vom vollständigen Fehlen eines
Musters abweichen
- Wenn der Grad der Abweichung statistisch unwahrscheinlich ist, dann besteht
beträchtliche Evidenz für das Vorliegen eines signifikanten
Musters in den Daten
Im Fall der Entscheidungsbäume ist die Nullhypothese, daß das gerade
betrachtete Attribut irrelevant ist und so der Informationsgewinn für eine
unendlich große Menge Beispielen null ist. Nun muß die Wahrscheinlichkeit dafür
berechnet werden, daß unter Annahme der Nullhypothese eine Beispielmenge die
beobachtete Abweichung von der beobachteten Verteilung der positiven und negativen
Beispiele vergleicht.
Puring liefert bei stark vertauschten Daten bessere Ergebnisse.
Welche Erweiterungen der Anwendbarkeit von Entscheidungsbäumen sind notwendig?
Es müssen Maßnahmen getroffen werden, um fehlende Daten zu ergänzen. Attribute
müssen mit besonderen Eigenschaften verwendbar gemacht werden.
Fehlende Daten
Oft sind nicht alle Attributwerte für jedes Beispiel bekannt, da sie entweder
nicht erfaßt oder erfaßbar sind. Dabei treten zwei Probleme treten auf:
- Wie soll man den Baum konstruieren, wenn bei einigen Beispielen die Werte
fehlen?
- Wie soll ein neues Beispiel klassifiziert werden, wenn eins der Testattribute
nicht anwendbar ist?
Attribute mit fehlenden Werten
Ist Zahl der Werte eines Attributes sehr hoch, kann es passieren, daß der
Informationsgehalt als sehr hoch eingeschätzt wird, obwohl dies nicht der Fall ist.
Solche Attribute müssen mit der Gain Ratio behandelt werden.
Attribute mit kontinuierlichen Werten
Attribute wie Größe oder Gewicht haben kontinuierliche Wertebereiche. Um sie
für Entscheidungsbaum-Lernen verwendbar zu machen, müssen die Wertebereiche
diskretisiert werden. Dies wird meist manuell gemacht.
Eine bessere Möglichkeit ist, die Attribute im Rahmen des Lernprozesses vorab zu
untersuchen und eine sinnvolle Unterteilung des Wertebereiches zu finden.
|
|
|
Kapitel 1
|
Intelligente Agenten
|
|
Agententypen, Eigenschaften einer Agentenumgebung, Problemformulierung,
Problemtypen, Zustandsraum
|
|
Kapitel 2
|
Lösen durch Suchen
|
|
Knoten, Rand, allgemeiner Suchalgorithmus, blinde Suchverfahren, heuristische
Suchfunktionen, Optimierung
|
|
Kapitel 3
|
Schlußfolgern
|
|
Wissensbasis, Inferenzmaschine, autonom, Wissensrepräsentation, Konsequenz,
Inferenzen, Aussagenlogik
|
|
Kapitel 4
|
Logik 1. Ordnung
|
|
Eigenschaften und Bestandteile, Symbole und Sätze,Ortsbestimmung, Ableiten,
Vorwärts- und Rückwärtsverkettung
|
|
Kapitel 5
|
Planen
|
|
Repräsentationen, Ziele und Aktionen, Situationsraum, Planraum, Kausale Kanten,
Promotion, Demotion
|
|
Kapitel 6
|
Handeln
|
|
Bedingtes Planen, Ausführungsüberwachung, Unsicherheit, Evidenz,
Wahrscheinlichkeitsaxiome, Bayessche Regel
|
|
Kapitel 7
|
Beobachten
|
|
Modell lernender Agenten, Performanzelement, Lernelement, Kritik, Problemgenerator,
induktives Lernen
|
|
Kapitel 8
|
Neuronale Netze
|
|
Struktur, Begriffe, Rechenelemente, Perzeptron, Anwendungen
|
|
|
Quelle: Die Ausarbeitung basiert auf dem Skript von Prof. Dr.
Werner Dilger
|
|
|
|
|
Merkblatt