Künstliche Intelligenz

Einleitung zum Fachgebiet der Künstlichen Intelligenz.


Kapitel 1 - Intelligente Agenten und Problemtypen

Was macht einen "idealen rationalen Agenten" aus?

Er wählt für jede Wahrnehmungsfolge immer den optimalen nächsten Schritt. Die Festlegung dieser Aktionen (Agentenentwurf) ist eine ideale Abbildung von Wahrnehmungsfolgen auf Aktionen. Der Agent kann auf eingebauten Wissen über seine Umgebung und/oder seiner Erfahrung beruhen.

Was bedeutet eigentlich rational in Bezug auf Agenten?

Dies kann nur für einen bestimmten Zeitpunkt beschrieben werden. Vier Merkmale sind dafür maßgebend:

Was ist ein Agentenprogramm?

Ist eine Funktion, welche die Abbildung von Wahrnehmungsfolgen auf Aktionen implementiert. Die Recheneinheit, auf der das Programm läuft, wird Architektur genannt. Diese stellt über Sensoren Informationen zur Verfügung und überträgt die gewählten Aktionen auf die Effektoren.

Nachteile von Lookup-Programmen sind die extrem langen Tabellen und der hohe Zeitaufwand. Es herrscht außerdem keinerlei Autonomie (Erfahrungsabhängigkeit) und somit Unflexibilität bei Umweltänderungen. Selbst wenn der Agent Lernfähig wäre, müßte er stetig Einträge für seine Tabelle lernen.

Unterschied zwischen reflexiven und beobachtenden Agenten

reflexiv beobachtend

der Agent erfasst Daten aus seiner Umwelt

der Agent hat keinen Gedächtnisspeicher

der Agent benutzt internen Zustand, um zu entscheiden

dieser wird von der Umwelt strukturiert, bleibt ihr aber verborgen

Schema eines reflexiven Agenten

Was sind einfache Reaktive Agenten?

Einfache reaktive Agenten werden auch als Reflexive Agenten bezeichnet. "Wenn das Auto vor uns bremst, dann leite Bremsvorgang ein." einfache reaktive Agenten reagieren also nur auf spzielle Beobachtungen. Sie haben kein Gedächtnis und müssen daher oft Zufallsentscheidungen treffen.

Worin bestehen beobachtende Agenten?

Diese Agenten beobachten ihre Umwelt und arbeiten somit mit einer adaptivierten Bewertungsfunktion. So kommt es zu einer regelmäßigen Aktualisierung des internen Zustandes. Sie benötigen Informationen, wie sich die Umwelt unabhängig vom Agenten verändert und entwickelt. Agenten die die Welt beobachten sind auch reflexive Agenten.

Was sind Zielbasierte Agenten?

Um im Falle unterschiedlich möglicher Folgezustände die richtige zu wählen, benötigt der zielbasierte Agent Informationen über Ziele. Der Agent vergleicht diese Information mit dem möglichem Ergebnis und wählt so die optimale Aktion aus. Dies ist meist nicht mit einem Schritt sinnvoll möglich, sondern nur mit mehreren Ermittlung solcher Aktionsfolgen über Suchen und Planen.

Nutzenbasierte Agenten

Der Nutzen ist eine Abbildung der Menge der Zustände in die reellen Zahlen. Die zugeordnete Zahl beschreibt, wie günstig der Zustand für den Agenten ist. Um ein Ziel zu erreichen, kann der Nutzen auf zwei Arten verwendet werden:

Ein Nutzenbasierter Agent muss auch Zielbasiert sein, da laut Definition dieser mehrere Ziele hat und zwischen den verschiedenen Ebenen wechseln kann.

Welche Eigenschaften definieren Umgebungen?

Zugänglich - Unzugänglich

Eine Umgebung ist zugänglich, wenn der Agent über seine Sensoren alle Informationen aus der Umwelt erfahren kann, die für die korrekte Ausführung seiner Aktionen notwendig sind.

Deterministisch - indeterministisch

Eine Umgebung ist deterministisch, wenn der nächste Zustand vollständig durch den aktuellen Zustand und den gewählten Aktionen definiert ist.

Episodisch - nicht episodisch

Eine Umgebung ist episodisch, wenn sich die Erfahrungen des Agenten in unabhängige Episoden aufteilen lassen.

Statisch - dynamisch

Eine Umgebung ist dynamisch, wenn sie sich ändern kann, während der Agent noch am "denken" ist. Semidynamisch bedeutet nur, dass die Ausführungszeit der Aktionen beschränkt ist.

Diskret - kontinuierlich

Eine Umgebung heißt diskret, wenn es in ihr eine begrenzte und unterscheidbare Anzahl von Wahrnehmungen und Aktionen gibt.

Was sind Umgebungsprogramme?

Sie stellen eine Simulationsumgebung dar, mit der Agentenprogramme getestet werden können. Der Simulator nimmt einen oder mehrere Agenten als Eingabe und stellt den Agenten die richtigen Wahrnehmungen zur Verfügung. Der Simulator nimmt die Aktionen des Agenten entgegen und aktualisiert gegebenenfalls die Umgebung. Eine Umgebung ist bestimmt durch ihren Anfangszustand und ihre Update-Funktion.

Problemformulierung und Problemtypen

Was sind Problemlösende Agenten?

Die Zielformulierung, ausgehend von der aktuellen Situation, ist der erste Schritt beim Problemlösen. Ein Ziel wird als eine Menge von Weltzuständen betrachtet, in denen das Ziel erfüllt ist. Aktionen werden als Übergänge zwischen Weltzuständen betrachtet. Bei der Problemformulierung wird entschieden, welche Aktionen und welche Zustände betrachtet werden sollen. Sie folgt nach der Zielformulierung. Hat ein Agent mehrere mögliche Aktionen mit unbekannten Ausgang, kann er eine Entscheidung herbeiführen, indem er verschiedene mögliche Aktionsfolgen, die zu dem gewünschten Zustand führen, untersucht und die Optimale heraussucht.

Was gehört zur Problemformulierung?

Um ein Problem formulieren zu können, müssen Zustände bekannt und Aktionen definiert werden. Dafür gibt es verschiedene Problemtypen.

Welche Problemtypen gibt es?

Was ist ein Ein-Zustands-Probem?

Der Agent weiß, in welchem Zustand er sich befindet (d.h. die Umgebung zugänglich) und was jede Aktion bewirkt. So kann er ausgehend von seinem Zustand, für eine Aktionsfolge vorausberechnen, in welchem Zustand er sich nach der Ausführung der Aktionen befinden wird.

Was wird zur Definition eines Ein-Zustand-Problems benötigt?

Was ist ein Mehr-Zustands-Probem?

Der Agent weiß >nicht, in welchem Zustand er sich befindet (Umgebung unzugänglich), aber er weiß was jede Aktion bewirkt. Dann kann er trotzdem das Erreichen eines Zielzustandes vorausberechnen. Dazu muß er aber über eine Menge von Zuständen schlußfolgern und nicht nur über Einen.

Was ist ein Kontingenz-Problem?

Der Agent kann nicht im voraus eine bestimmte Aktionsfolge berechnen, die zu einem Zielzustand führt. Er benötigt während der Ausführung von Aktionen Sensorinformationen, um zu entscheiden, welche der Aktionen zum Ziel führt.

Statt einer Folge von Aktionen braucht er also einen Baum, in dem jeder Zweig von der Wurzel zu einem Blatt eine Aktionsfolge darstellt. Jede Aktionsfolge behandelt ein kontingentes Ereignis.

Was ist ein Explorations-Problem

Der Agent kennt die Auswirkungen seiner Aktionen nicht. Deshalb muß er experimentieren, um herauszufinden, was die Aktionen bewirken und welche Art von Zuständen es gibt. Dies kann er nur in der realen Welt tun. Dabei kann er aber lernen, d.h. eine interne Repräsentation der Welt aufbauen und zur Entscheidungsfindung nutzen. Eine Umgebung für so ein Problem zeichnet sich durch eine dynamische Umwelt aus. Desweiteren müssen die Aktionen Freiheitsgrade besitzen, um so näher an die reale Umwelt heranzureichen.

Kennt der Agent seinen Anfangszustand nicht oder hat dieser mehr als einen Zustand, kann es kein Einzustandsproblem sein. Benötigt der Agent Sensorinformationen, um schrittweise zu einem Ziel zu gelangen, kann es auch kein Mehrzustandsproblem sein.
Somit bleiben Kontigenz- und Explorationsproblem. Ein Kontignenzproblem besitzt ein festes Repertoire an Funktionen, deren Effekte eindeutig definiert sind. Ein Explorationsproblem zeichnet sich dadurch aus, daß sich der Agent vergangene Schritte merkt, aber sich nicht über die Auswirkungen seiner Aktionen bewußt ist.

Was ist der Anfangszustand?

Der Anfangszustand ist der Zustand, von dem der Agent weiß, dass er sich in Ihm befindet. Eine Aktion wird als Operator oder Nachfolgefunktion bezeichnet, in Verbindung mit dem Zustand, zu dem sie von einem Gegebenen aus führt.

Was gehört zum Zustandsraum?

Der Anfangszustand und die Menge der Aktionen definieren den Zustandsraum. Er besteht aus einer Menge aller Zustände, die vom Anfangszustand aus durch bestimmt Aktionsfolgen, erreichbar sind.

Was ist ein Pfad im Zustandsraum?

Ein Pfad im Zustandsraum ist einfach nur eine Aktionsfolge, die von einem Zustand in einen Anderen führt. Das Zielprädikat kann der Agent auf einen Zustand anwenden, um zu Prüfen, ob e dieser ein Zielzustand ist. Die Pfadkostenfunktion ordnet jedem Pfad im Zustandsraum einen Kostenwert zu. Dieser ist die Summe der Kosten der einzelnen Aktionen entlang eines Pfades.

Was beinhaltet der Datentyp "Problem"?

Der Datentyp Problem ist also definiert durch Anfangszustand, Operatoren, Zielprädikat und Pfadkostenfunktion. Instanzen dieses Datentyps bilden die Eingaben für Suchalgorithmen. Die Ausgabe einer Suche ist dann eine Lösung, d.h. ein Pfad von einem Ausgangszustand in einen Zustand, welcher das Zielprädikat erfüllt.

Wie sind Zustände im Mehrzustandsproblem definiert?

Beim Mehrzustandsproblem werden Zustände durch Zustandsmengen und Aktionen durch Operatormengen ersetzt, welche die Folgezustandsmenge spezifizieren. Ein Operator wird auf eine Zustandsmenge angewandt, indem er auf jeden einzelnen Zustand angewendet wird und die Ergebnisse vereinigt werden. Anstelle des Ergebnisraumes erhält man somit einen Ergebnismengenraum.

Aus welchen Merkmalen wird die Performance einer Problemlösung angegeben?

Welche Typen gehören zum Beispielproblem des "8-Puzzle"?

Zustände

Beschreibung der Plazierung aller acht Plättchen sowie der Leerstelle.

Operatoren

Bewegung der Leerstelle nach links, rechts, oben oder unten.

Zielprädikat

Zustand mit gewünschter Plazierung der Plättchen.

Pfadkosten

Jeder Schritt hat Kosten von 1. Die Kosten eines Pfades sind somit gleich der Pfadlänge.

Kapitel 2 - Problemlösen durch Suchen

Die fünft Typen der Datenstruktur eines "Knoten eines Suchbaums"

Der Rand der Suche und dessen Operationen

Zusätzlich zum Suchbaum wird eine Datenstruktur benötigt, um zwar schon erzeugte, aber noch nicht expandierte Knoten zu speichern. Diese Menge heißt Rand und wird als Liste implementiert und hat folgende Operationen:

Der allgemeine Suchalgorithmus?

Function Allgemeine Suche(Problem,Listing-FN) return Solution or Error;
Nodes = Make-List (Make-Node(Initial-State[Problem]));
Loop do
If (Empty(nodes)) return Error;
Node = Remove-Front(nodes);
If (State(node)== Zielprädikat[problem]) return node;
Nodes=Listing-FN(nodes,Expand(node,Operators[Problem]))
End     

Nennen sie alle blinden Suchverfahren?

Die Breitensuche BFS

Realisiert wird BFS über die allgemeine Suche mit einer Listenfunktion mit Tail-Insert. BFS ist vollständig, denn sie findet immer die Lösung, falls diese existiert. Außerdem findet BFS immer die Lösung mit dem kürzesten Pfad. Falls die Pfadkosten eine monoton wachsende Funktion der Tiefe des Suchbaums ist, dann ist BFS sogar optimal. Bei einem Verzweigungsfaktor von b und einer Tiefe von d liegt der Zeit- und Speicheraufwand von BFS bei O(b^d).

Optimalität: ja
Vollständigkeit: ja
Zeitaufwand : O(b^m)
Speicherplatzbedarf: O(b^m)

Die kostengesteuerte Breitensuche

Es wird immer der Knoten als nächster aus dem Rand expandiert, der die geringsten Pfadkosten besitzt. Unter Bestimmten Voraussetzungen wird so eine kostengünstige Lösung gefunden. Die kostengesteuerte BFS findet die kostengünstigste Lösung, wenn sich die Kosten entlang eines Pfades an keiner Stelle verringern.

Optimalität: ja
Vollständigkeit: ja
Zeitaufwand : O(b^m)
Speicherplatzbedarf: O(b^m)

Die Tiefensuche


Optimalität: nein
Vollständigkeit: nein
Zeitaufwand : O(b^m) (worst Case)
Speicherplatzbedarf: O(b*m)

Die tiefenbegrenzte Suche

Es wird die allgemeine Suche mit Operatoren, welche Tiefe kontrollieren implementiert. Zeitbedarf ist dann O(bl), wenn l die begrenzte Tiefe darstellt.

Optimalität: nein
Vollständigkeit: nein
Zeitaufwand : O(b^l)
Speicherplatzbedarf: O(b*l)

Die Suche mit iterativem Vertiefen

Dies stellt eine tiefenbegrenzte Suche dar, welche iterativ mehrere Tiefenschnitte anwendet, um zu einem Ergebnis zu kommen.


Optimalität: ja
Vollständigkeit: ja
Zeitaufwand : O(b^d)
Speicherplatzbedarf: O(b*d)

Die bidirektionale Suche

Bei diesem Verfahren wird simultan vom Ausgangszustand vorwärts und vom Zielzustand rückwärts gesucht, bis sich die beiden Suchpfade in der Mitte treffen. Mit einem Verzweigungsfaktor b und einer Lösungstiefe d ist O(2b^d/2)=O(b^d/2). Folgende Voraussetzungen müssen gegeben sein:



Optimalität: ja
Vollständigkeit: ja
Zeitaufwand : O(b^(d/2))
Speicherplatzbedarf: O(b^(d/2))

Was bedeutet "informiert" im Gegensatz zu blinden Suchverfahren?

Bei blinden Suchverfahren kann nicht Einfluss auf die Knotenwahl genommen werden. Informiert bedeutet, dass man dies z.B. mit heuristiken beeinflussen kann.

Heuristische Suchfunktionen

Heuristische Suchalgorithmen versuchen den Suchpfad durch "Schätzen" zu optimieren und somit die Laufzeit zu verbessern. Es wird nun eine Evaluierungsfunktion benötigt, welche die richtige Reihenfolge für die Abarbeitung bestimmt. Die Knoten werden so geordnet, daß der mit der besten Bewertung als Erster expandiert wird. Eine Heuristik ist somit eine spezielle Form einer Evaluations-Funktion.

Best-First-Search

Es wird der Knoten zuerst expandiert, welcher wahrscheinlich am schnellsten zum Ziel führt. Eine von Problem zu Problem verschiedene Evaluations-Funktion hilft hier bei der Entscheidungsfindung. Diese Evaluierungsfunktion kann auch falsch liegen. Wichig ist, dass die Suchzeit im Ganzen sich aber verkürzt. Implementiert wird die Best-First-Suche wie die Breiten- und Tiefensuche auch mittels einer Queue. Nur werden hier vor jeder Expansion die Knoten anhand der Werte der Evaluations-Funktion sortiert. Beispielalgorithmen sind zum BSP Greedy, A*-Search und SMA*...

Arten von heuristischen Suchfunktionen

Wie funktioniert die Greedy Suche?

Der Knoten, welcher dem Zielzustandsknoten als am "Naheliegendsten" eingeschätzt wird, wird als Erster expandiert. Eine Funktion, welche solche Kosten schätzt, nennt man Heuristikfunktion. Eine heuristische Funktion h(n) stellt also die Kosten des billigsten Pfades von einem Knoten n zum Zielzustand dar. Jede beliebige Funktion kann als Heuristik verwendet werden.

Es muss nur gelten h(n) = 0, falls n ein Zielknoten ist.
Die Greedy-Suche arbeitet nach dem Tiefensuchmuster und ist somit auch nicht optimal und nicht vollständig. Der Worst-Case Zeitbedarf ist O(bm), mit m als maximale Tiefe des Suchraumes.

Optimalität: nein
Vollständigkeit: nein
Zeitaufwand : O(b^m) (worst Case)
Speicherplatzbedarf: O(b*m)

Wie funktioniert die A*-Suche?

Durch Addition der heuristischen Funktion h und der Pfadkostenfunktion g erhält man die Funktion f(n) = g(n) + h(n). Dabei sind g(n) alle bisherigen Kosten und h(n) die aktuellen Kosten. Die A*-Suche arbeitet im Grunde wie Greedy. Es wird nur g(n) hinzuaddiert.

Hat die Funktion h die Eigenschaft, dass die Kosten eines Pfades bis zu einem Zielknoten nicht überschätzt werden, dann ist es eine zulässige Heuristik. Die Best-First-Suche unter Verwendung von f als Evaluierungsfunktion mit zulässigem h heißt A*-Suche. Eine heuristische Funktion, deren Werte entlang des Pfades niemals kleiner werden, nennt man monoton. Ist eine heuristische Funktion nicht monoton, dann kann sie durch die Pfadmaximierungsgleichung (Maximum bilden) in eine Monotone umgeformt werden.

Die A*-Suche ist optimal und vollständig, aber im Worst-Case exponentiell, da sie der Breitensuche ähnelt.

Optimalität: ja
Vollständigkeit: ja
Zeitaufwand : O(b^m) (worst Case)
Speicherplatzbedarf: O(b*m)

Die speicherbegrenzte A*-Suche mit iterativen Vertiefen - IDA*

Arbeitet wie Suche mit iterativen Vertiefen, nur dass die Suche nicht strikt tiefenorientiert ist, sondern kostenorieniert.

IDA* ist optimal und vollständig und benötigt nur Speicherplatz, der proportional zum längsten Pfad, der untersucht wird, ist. Somit ist Speicherplatzaufwand linear.


Optimalität: ja
Vollständigkeit: ja
Zeitaufwand : O(b^m) (worst Case)
Speicherplatzbedarf: O(b*m)

Die speicherbegrenzte Simply Memory-Bounded A* - SMA*

Der SMA* merkt sich Knoten, welche er schon mal expandiert hat. Somit wird Sucheffizienz erhöht. SMA* hat folgende Eigenschaften:

Problemlösen durch Optimieren

Abgrenzung

Der Unterschied zur Suche ist, daß bei Suche der Anfangszustand gegeben ist und die Lösung gesucht wird. Beim Optimieren ist die Lösung schon im Anfangszustand gegeben und es wird versucht eine bessere Lösung zu ermitteln.

Drei Ansätze beim Optimieren

"Bergsteigen" als Optimierung

Das Bergsteigen ist ein stures Suchen von besseren Werten. Gibt es mehrere bessere Knoten, muß via Zufallsfunktion einer selektiert werden.

Welche drei Probleme treten beim "Bergsteigen" auf?

Lokales Maximum

Stößt die Suche auf ein lokales Maximum, bleibt sie dort hängen und findet ein evtuelles globales Maximum nicht.

Plateau

Einmal auf einer Ebene sitzend, kann der Algorithmus nur raten, in welche Richtung fortgesetzt werden soll.

Grat

Man benötigt Operatoren, welche verhindern, daß die Suche entlang eines Grates hin und her pendelt.

Um diese Problemen aus dem Weg zu gehen, kann man die Suche durch Bergsteigen mehrfach von verschiedenen zufällig gewählten Startpunkten aus durchführen und die besten Werte nehmen.

Simuliertes Ausglühen

Die Idee ist, während der Suche in zufälligen Abständen Knoten mit schlechteren Werten auszuwählen, um auf diese Weise lokalen Maxima zu entgehen. Eine Variable T beschreibt im Algorithmus eine Art Temperatur (die die Wahrscheinlichkeit von Abwärtsschritten steuert)

Genetische Algorithmen

Dieser Ansatz ist aus der Evolutionstheorie abgeschaut. Man nimmt an das die Evolution immer optimale Pfade wählt und somit optimale Wesen hervorbringt.

Genetische Algorithmen laufen auf Populationen von Genomen (Folge von Genen = Bitstrings) ab. Sie erzeugen in großen Schleife neue Generationen von Genomen durch Anwendung der drei Operatoren Selektion, Kreuzung und Mutation. Dabei werden folgende Schritte durchgeführt:

Ziel des Algorithmus ist, die Fitness der Genome zu maximieren. Die Fitnessfunktion (kann beliebig sein) bewertet jedes neu entstandene Genom. Dazu muss Genom in seinen ursprünglichen Phänotyp (Erscheinungsbild eines Genotyps) umgewandelt werden, denn auf ihm operiert die Fitnessfunktion. Nachteile von genetischen Algorithmen sind die schlechte Effizienz und die Notwendigkeit einer anspruchsvollen Fitnessfunktion. Beliebtes Anwendungsgebiet sind die neuronalen Netze, wo es vor allem auf die Fitnessfunktion ankommt.

Die drei Operationen genetischer Algorithmen

Selektion

Ist das Aussondern von bestimmten Genomen zum Konstanthalten der Population.

Kreuzung

Führt das Auswählen der fittesten Genome und Verkettung bzw. Kombination dieser dar.

Mutation

Verändert ein oder mehrere zufällig gewählte Gene eines Genoms, wodurch ein neues Genom entsteht, um vor allem eventuellen lokalen Maxima entgehen zu können.

Kapitel 3 - Agenten, die logisch Schlußfolgern

Wodurch ist ein Wissensbasierter Agent definiert?

Wissensbasis

Die erste zentrale Komponente ist die Wissensbasis (repräsentiert Menge von Fakten über die Welt). Die verschiedenen Repräsentationen werden Sätze genannt, welche in einer Wissensrepräsentationssprache formuliert werden. Zwei grundlegende Funktionen sind notwendig:

Inferenzmaschine

Die zweite wichtige Komponente ist die Inferenzmaschine, welche versucht Wissen zu erschließen. Ein Wissensbasierter Agent ist den Zustandsbasierten ähnlich. Wegen der Wissensbasis und den Aktionen TELL und ASK kann er aber auf drei Ebenen besser beschrieben werden:

Das initiale Programm kann durch Einfügen von Sätzen aufgebaut werden (deklarativer Ansatz).

Was ist ein autonomer Agent?

Hat der Agent einen Lernmechanismus, dann wird er als autonom bezeichnet.

Wissensrepräsentation und Wissensrepräsentationssprache

Ziel der Wissensrepräsentation ist es, Wissen in einer für den Rechner verständlichen Form zu kodieren. Eine Wissensrepräsentationssprache definiert sich durch:

Logischer Konsequenz und Folgerung

Die Unterscheidung von Fakten und Repräsentationen ist von entscheidender Bedeutung. Da die Welt nicht in einen Agenten gebracht werden kann, muß der Agent auf den Repräsentationen schlußfolgern und kann nicht direkt auf den Fakten arbeiten.

Schlußfolgern ist also ein Prozeß, welcher neue Konfigurationen aus bestehenden ableitet.

Logische Konsequenz bzw. logische Folgerung heißt, daß man nur solche Sätze erzeugen möchte, die zwingend war sind, wenn die Ausgangssätze wahr sind. Man sagt "aus KB folgt logisch a" (Knowledge Base und gefolgerter Satz a).

Worin unterscheiden sich Korrektheit und Vollständigkeit einer Inferenzprozedur?

Unterschiede der Repräsentationen von Programmiersprachen und natürliche Sprachen

Programmiersprachen

Natürliche Sprachen

Kombination beider Sprachen

Kompositionalität

Kompositionalität ist die Beziehung zwischen Semantik und Syntax verschiedener aufeinander folgender Sätze.

Inferenzen

Inferenzen sind Schlußfolgerungsverfahren. Korrekte Inferenzen werden Deduktion genannt. Eine Logik heißt gültig oder notwendig wahr, wenn er unter allen möglichen Interpretationen in allen möglichen Welten war ist.

Ein Satz der Logik heißt erfüllbar genau dann, wenn es eine Interpretation in einer Welt gibt, unter der der Satz war ist. Ansonsten ist der Satz unerfüllbar.

Eine formale Inferenz mit einer korrekten Inferenzprozedur garantiert, daß nur korrekte Sätze abgeleitet werden.

Deduktion

Detuktion beschreibt korrekte Inferenzen.

Was sind die zwei grundlegenden Bestandteile einer Logik?

Formale Sprache zur Beschreibung eines Sachverhalts

Beweistheorie

Was unterscheidet die Aussagenlogik von der Logik erster Ordnung?

In der Aussagenlogik werden ganze Aussagen oder Fakten durch einzelne Symbole repräsentiert. Solche Symbole können durch boolesche Operatoren verknüpft werden. Die Aussagenlogik ist kaum zur Repräsentation von Objekten geeignet und deshalb als Repräsentationssprache ungeeignet. Die Logik erster Ordnung trägt wesentlich mehr zur Repräsentation der Welt bei:

Bestandteile der Syntax der Aussagenlogik

Symbolvorrat der Aussagenlogik:

Dabei gilt

Ein Literal ist ein atomarer oder negiert atomarer Satz

Die Bedeutung zusammengesetzter Sätze läßt sich über Wahrheitstabellen ermitteln. Es werden Präzedenzregeln angewendet, um Klammerungen zu sparen. Zu beachten ist die Implikation, welche keine kausalen Gegebenheiten beschreiben kann.

Wahrheitstabellen

Mit Wahrheitstabellen läßt sich die Gültigkeit testen. Sie Stellen ein Beweisverfahren dar, was unabhängig von der Bedeutung der Teilaussagen ist.

Das Modell

Jede Welt, in der ein Satz unter einer bestimmten Interpretation wahr ist, ist ein Modell des Satzes unter dieser Interpretation.

Inferenzregeln

Beweise für Gültigkeit mit Wahrheitstabellen zeigen, dass sich immer bestimmte Muster wiederholen. Jedes dieser Muster beschreibt eine Inferenzklasse und kann durch Inferenzregeln beschrieben werden. Eine Inferenzregel muß einmal bewiesen werden und kann dann beliebig oft angewendet werden. Inferenzregeln werden in der Aussagenlogik durch einen Quotienten zweier Sätze beschrieben. Alle konkreten Sätze die zu den durch die Inferenzregel vorgegebenen Strukturen passen, erfüllen die Inferenzregel.

Folgende Regeln sind gebräuchlich:

Eine Inferenzregel ist genau dann korrekt, wenn die Konklusion immer dann wahr ist, wenn alle Prämissen wahr sind.

Welche Eigenschaften gelten speziell für die aussagenlogische Inferenz?

Das Problem der Erfüllbarkeit aussagenlogischer Sätze ist NP-vollständig. Monotonizität der Logik heißt, dass alle Sätze aus einer Wissensbasis, auch aus jeder Obermenge der Wissensbasis folgbar sind.
Horn-Sätze sind Sätze, auf denen Inferenzen in polynomieller Zeit anwendbar sind.

Kapitel 4 - Logik erster Ordnung

Eigenschaften der Logik erster Ordnung

Nach der Logik erster Ordnung besteht die Welt aus Objekten, d.h. Dingen, die individuelle Identitäten und Eigenschaften haben, welche die Objekte differenzieren. Zwischen Objekten können Relationen bestehen. Einige der Relationen können Funktionen sein.

Satzaufbau in der Logik erster Ordnung

Es gibt wie in der Aussagenlogik Sätze, welche die Welt repräsentieren.

Sätze bestehen aus Thermen und Prädikatsymbolen. Terme können funktionale Ausdrücke, Variablen oder Konstanten sein. Aus einfachen Sätzen werden durch Junktoren und Quantoren komplexe Sätze gebaut.

Symbolvorrat der Logik erster Ordnung

Merkmale von Konstantensymbolen

Durch Interpretation wird festgelegt, auf welches Objekt in der Welt sich ein Konstantensymbol bezieht. Jedes Konstantensymbol benennt genau ein Objekt. Aber nicht alle Objekte der Welt müssen aber Namen haben und Mehrfachbenennungen sind zugelassen.

Prädikatsymbole

Durch Interpretation wird festgelegt, auf welche Relation in der Welt sich ein Prädikatsymbol bezieht. Eine Relation ist eine Menge von Tupeln von Objekten, die die Relation erfüllen.

Funktionssymbole

Funktionssymboel werden durch Interpretation auf spezielle Relationen abgebildet, die in einer bestimmten Stelle (üblicherweise die Letzte) eindeutig sind. Eine n-stellige Funktion kann durch eine Menge von (n+1) Tupeln definiert werden. Die letzte Stelle eines solchen Tupels stellt den Wert der Funktion unter den ersten n Stellen dar.

Terme

Ein Term ist ein logischer Ausdruck der sich auf ein Objekt in der Modellwelt bezieht. Somit sind auch Konstanten- und Variablensymbole Terme. Außer Konstantensymbolen sind Ausdrücke, gebildet aus einem Funktionssymbol und einer in Klammern eingeschlossenen Folge von Termen, wieder Terme. Ein Term der keine Variablen enthält, heißt Grundterm.

Atomare Sätze (Atome)

Atomare Sätze bestehen aus einem Prädikatsymbol gefolgt von einer in Klammern eingeschlossenen Liste von Termen. Ein atomarer Satz beschreibt einen Fakt, dessen Bedeutung entweder true oder false ist. Ein atomarer Satz ist wahr, wenn die Relation, auf die sich das Prädikatsymbol bezieht, zwischen den Objekten gilt, auf denen sich die Terme beziehen.

Zusammengesetzte Sätze

Mittels Junktoren können aus Sätzen komplexere Sätze gebildet werden. Die Teilsätze können zusammengesetzt oder auch atomar sein. Die Semantik zusammengesetzter Sätze sind Wahrheitswerte und sind analog zur Aussagenlogik definiert.

Quantorenarten

Universelle Quantifizierung über den Allquantor

Existentielle Quantifizierung

Geschachtelte Quantoren

Quantoren und Negation

Welche Merkmale definieren die Gleichheit?

Das Gleichheitszeichen kann als eine Art spezielles Prädikat verwendet werden. Sind t1 und t2 Terme, dann ist t1 = t2 ein Satz.

Zwei Anwendungsbereiche der Logik erster Ordnung

Die Verwandtschaftsdomäne

In der Verwandtschaftsdomäne gibt es Sätze in einer Wissensbasis werden als Axiome betrachtet.
Mittels Definitionen kann man aus diesen Axiomen neue Konzepte erzeugen und neue Axiome ableiten. Beim Aufbau einer Wissensbasis gibt es zwei Probleme

Die Mengendomäne

In der Mengendomäne gibt es Es gibt acht Axiome, welche die Eigenschaften einer Menge definieren Fragen und Antworten:

Repräsentation von Veränderungen in der Welt

Diachronische Regeln

Diachronische Regeln, sind Regeln, welche beschreiben, wie sich eine Welt verändert oder auch nicht verändert.

Was beschreibt ein Situationskalkül?

Die Welt wird als eine Folge von Situationen betrachtet. Jede Situation stellt einen "Schnappschuß" des Zustandes der Welt zu dem Augenblick dar. Eine Situation wird aus einer anderen durch Aktionen erstellt kann benannt werden.
Um den Wechsel einer Situation zur nächsten zu beschreiben, wird eine Funktion benutzt:

Aktionen, welche eine Wirkung auf die Folgesituation haben sind Wirkungsaxiome.
Axiome, welche Sicherstellen, dass eine Wirkung über mehrere Situationen erhalten bleibt, sind Frameaxiome. Wirkungsaxiome und Frameaxiome zusammen, beschreiben vollständig, wie sich eine Welt aufgrund der Aktionen des Agenten entwickelt.

Wofür benötigt ein Agent eine Ortsbestimmung?

"Am Beispiel der Wumpus Welt ist die Ortsbestimmung besonders wichtig " Der Agent muss wissen, in welche Richtung er blickt o Hier einfach durch einen Winkel definiert" Der Agent benötigt eine einfache Landkarte, um aus einer Richtung und einer Ortsangabe eine neue Ortsangabe berechnen zu können.

Ableiten verborgener Eigenschaften einer Welt

Kausale und Diagnostische Regeln

Synchrone Regeln setzen verschiedene Eigenschaften desselben Weltzustandes in Relation.

Kausale Regeln

Geben die Richtung einer angenommenen Kausalität in einer Welt wieder. Systeme, die mit kausalen Regeln schlußfolgern, heißen modellbasierte Schlußfolgerungssysteme.

Diagnostische Regeln

Leiten das Vorhandensein verborgener Eigenschaften direkt aus den Wahrnehmungen ab. Man kann aber keine so aussagekräftigen Schlüsse ziehen, wie das bei Kausalen Regeln der Fall ist.

Präferenzen zwischen Aktionen bei Zielbasierte Agenten

Die Wünschbarkeit von Aktionen wird durch bestimmt Prädikate beschrieben. Prädikate können sein Gut, Mittel, Riskant oder Tödlich.
Die Auswahl einer Aktion erfolgt gemäß der Reihenfolge, welche die Prädikate auf Grund ihrer Semantik haben. Regeln dieser Art heißen Aktions-Wert-Regeln.

Mit welchen drei Methoden lassen sich Aktionsfolgen bestimmen?

Inferenz

Mit geeigneten Axiomen kann man mit ASK eine Aktionsfolge aus der Wissensbasis ableiten. Für größere Welten wäre aber der Rechenaufwand zu groß.

Suchen

Mit Best-First-Suche kann ein Pfad zum Ziel bestimmt werden. Dazu muss Wissen in eine Menge geeigneter Operatoren und Zustandsrepräsentationen umgeformt werden.

Planen

Erfolgt mit speziellen Schlußfolgerungssystemen, die entworfen wurden, über Aktionen zu folgern.

Inferenzen in der Logik erster Ordnung

Welche drei zusätzlichen Inferenzregeln gibt es?

Der verallgemeinerte Modus Ponens und Unifikation

Der Modus ponems enthält die n+1 Prämissen und die Konklusion der Substitution. Vor Anwendung werden alle Sätze in die kanonische Form (Hornsätze) umgewandelt.
Sind entweder atomare Sätze oder Implikationen mit einer Konjunktion atomarer Sätze auf der linken und einem einzelnen atomaren Satz auf der anderen Seite. Einfügen in die Wissensbasis werden alle Sätze in Hornsätze umgewandelt durch Anwendung der Inferenzregeln:

Nachteil ist aber, dass nicht alle Sätze in Hornsätze überführbar sind

Unifikation

Es wird angenommen, dass es eine Prozedur UNIFY gibt, die zwei atomare Sätze p und q zu einer Substitution überführt, die die beiden Eingabesätze identisch macht. Konflikte durch doppelte Variablennamen werden durch Umbenennung aufgelöst. Falls ein Unifikator für q und p exisitert, soll UNIFY immer den allgemeinsten Unfikator liefern.

Vorwärts- und Rückwärtsverkettung und wozu braucht man sie?

Es gibt einen Satz und man möchte diese über die Wissensbasis vergleichen.

Vorwärtsverkettung

Rückwärtsverkettung

Hiermit ist es möglich, alle Antworten auf eine Frage an eine KB zu bekommen. Realisiert wird dies über über die ASK-Funktion. Die Rückwärtsverkettung arbeitet folgendermaßen:

Resolution: Eine vollständige Inferenzprozedur

Die Inferenzregel Resolution

Diese Inferenzregel ist eine Resolution-Regel in erweiterter Form. Es wird erlaubt, dass Disjunktionen mehrere Elemente enthalten. Sie wird auf Sätze der Logik erster Ordnung erweitert:

Schritte bei der Umformungung in die implikative Normalform

  1. Beseitigung der Implikationen
  2. Negationen nach innen ziehen
  3. Umbenennung von Variablen
  4. Quantoren nach außen ziehen
  5. Skolemisierung (Entfernen der Existenzquantoren)
  6. Distribution von Konjunktion über Disjunktion (Distributivgesetz)
  7. Abflachen eingebetteter Strukturen (Assoziativgesetz)
  8. Umwandlung von Disjunktionen in Implikationen

Welche zwei Möglichkeiten gibt es zur Behandlung der Gleichheit?

Eine Möglichkeit ist die Axiomisierung, (Eigenschaften als Äquivalenzrelation).
Zweite Möglichkeit ist spezielle Inferenzregel Demodulation.

Welche vier Resolution-Strategien gibt es?

Unit-Präferenz

Führe, wenn möglich einen Inferenzschritt mit einer Klausel, die nur aus einem Literal besteht durch.

Set of support

Wähle eine Teilmenge "Set of support" der Sätze aus, und wende die Resolution Regel immer auf einen Satz an aus "Set of support" und einen anderen an und füge das Ergebnis in "Set of support" ein.

Input Resolution und Linear Resolution

Wähle die Sätze zur Problembeschreibung als Eingabe und wende die Resolution Regel immer auf einen Satz aus dieser Menge und einem anderen an. Linear Resolution ist vollständig und ist eine Verallgemeinerung der Input Resolution.

Subsumption

Entfernt alle Sätze, die von einem Satz in der Wissensbasis subsumiert werden, d.h. aus diesem Satz logisch folgen. Dadurch kann Suchraum so klein wie nur möglich gehalten werden.

Kapitel 5 - Planen

Die vier Repräsentationen eines suchorientierten Problemlösers

Repräsentation von Aktionen

Aktionen werden dargestellt durch Programme. Sie erzeugen Beschreibungen der Folgezustände.

Repräsentation von Zuständen

Gegeben ist ein vollständiger Anfangszustand. Da Aktionen vollständige Zustandsbeschreibungen erzeugen sind alle Zustände vollständig. Ein Zustand ist meistens eine einfache Datenstruktur.

Repräsentation von Zielen

Die einzige verfügbare Information über Ziel ist das Zielprädikat und heuristische Funktion. Die Informationen werden auf die Zustände angewandt, um deren Wünschbarkeit zu bestimmen.

Repräsentation von Plänen

Eine Lösung ist eine Folge von Aktionen. Eine Suche betrachtet nur zusammenhängende ununterbrochene Folgen von Aktionen, die beim Anfangszustand beginnen.

Die drei Schlüsselideen, die dem Planen zu Grunde liegen

"Öffne" die Repräsentation der Zustände, Ziele und Aktionen

Der Planer kann stets Aktionen zum Plan hinzufügen

Meist herrscht Unabhängigkeit von Teilmengen einer Welt

Zustände, Ziele und Aktionen in der STRIPS-Sprache

Zustände

Sind Konjunktionen funktionsfreier Grundliterale, bestehend aus Prädikaten angewandt auf Konstanten. Zustandsbeschreibungen müssen nicht vollständig sein, da in einer unzugänglichen Welt der Zustand so gut wie nie vollständig ist.

Ziele

Ziele sind Konjunktionen funktionsfreier Literale (Variablen zugelassen).

Aktionen

Was macht ein Situationsraum-Planer?

Er betrachtet Zustände. Ein Situationsraum-Planer ist ein Algorithmus, der im Raum der Situationen oder Zustände einen Pfad von einem Anfangs- zu einem Zielzustand durch Anwendung von der verfügbaren Operationen bestimmt. Dabei gibt es Vorwärts- und Rückwärtsplaner.

Rückswärtsplaner

Planraum

Ein Planraum betrachtet nicht die Zustände, sondern die Aktionen. Ein Planraum ist eine Menge partieller Pläne mit den dazugehörigen Operationen, die solche Pläne in ebensolche überführen können.
Bei Erstellung eines Plans für ein Problem beginnt man mit einem einfachen unvollständigen Plan und modifiziert diesen mit den Operatoren solange, bis er vollständig ist.

Solche Operatoren sind Hinzufügen eines Schrittes, das Ordnen von Schritten und das Instanziieren von Variablen.

Kausale Kanten im Planraum beschreiben den Zweck von Schritten in einem Plan.

Kausale Kanten

Sie Beschreiben den Zweck von Schritten in einem Plan, d.h. welche Vorbedingungen für einen Situationswechsel gelten müssen. Ein Planungsalgorithmus schützt kausale Kanten, so dass zwischen zwei Aktionen die durch eine kausale Kante verbunden sind, keine Aktion eingeschoben werden kann, welche die Vorbedingung aufheben würde.

Muß eine Aktion eingefügt werden, kann der Planungsalgorithmus sie entweder vor der kausalen Kante (Demotion) oder nach ihr (Promotion) einfügen.

Planen mit partiell instanziierten Operatoren

Wie kann man mögliche Bedrohungen kausaler Kanten entdecken und behandeln?

Eine Vorbedingung c stellt eine mögliche Bedrohung einer Vorbedingung c' dar, wenn es einen Unifikator gibt, so dass

UNIFY( c ) = ! UNIFY( c' )

ist. Es gibt drei Wege mögliche Bedrohungen zu behandeln:

Auflösung sofort mit einem Gleichheitsconstraint

Alle möglichen Bedrohungen werden sofort aufgelöst. Dabei wird eine Variable mit einem Wert so vorbelegt, dass ein Widerspruch zu einer anderen Vorbedingung nicht entstehen kann (Gleichheitsconstraint).

Auflösung sofort mit einem Ungleichheitsconstraint

Wie oben, nur dass eine bestimmte Belegung von Variablen ausgeschlossen wird, aber alle anderen erlaubt werden. Ist nur schwer zu implementieren.

Auflösung später

Alle Bedrohungen werden solange ignoriert, bis sie notwendige Bedrohungen werden, d.h. ein expliziter Widerspruch vorliegt. Dann wird durch Demotion oder Promotion aufgelöst. Vorteil ist, dass schwache Festlegungen getroffen werden können. Nachteil ist, dass es schwer zu entscheiden ist, ob ein Plan auch eine Lösung darstellt.

Kapitel 6 - Planen und Handeln und Unsicherheit

Die zwei Wege zur Behandlung eines Problems mit unvollständigen oder inkorrekten Informationen?

Bedingtes Planen

Ausführungsüberwachung

Bedingtes Planen

Bedingtes Planen ist das Wesen bedingter Pläne. Zur Formulierung bedingter Pläne benötigt man bedingte Ausdrücke in der Form

"If (Condition,Then,Else)"

Der Agent muß während Ausführung die Bedingungen auf Wahrheit prüfen können.

Dem Agenten werden Fakten durch Wahrnehmungen bekannt, die er sich durch Sensoraktionen besorgen muß. Zusätzlich zum gewöhnlichen Planungsprozeß wird das Konzept des Kontextes eines Schritts im Plan benötigt.

Laufzeitvariable sind Variablen, welche erst während der Ausführung mit Werten belegt werden.

Zusammenhang zwischen Planung und Ausführung

Es herrscht vollständige Integration von Planung und Ausführung. Planung und Ausführung werden im folgenden nicht mehr als getrennte Prozesse betrachtet. Vielmehr werden sie zu einem situierten Planungsagenten zusammengefaßt. Dieser Agent wird selbst als Teil eines großen Plans betrachtet - seines Lebensplans.
Seine Aktivitäten sind:

Der Agent kann bereits mit der Planausführung beginnen, wenn der Plan noch nicht komplett berechnet wurde. Insbesondere wenn der Plan unabhängige Teilziele erhält, lässt sich so viel Zeit sparen.

Unsicherheit

Handeln unter Unsicherheit

Agenten haben in Realität fast nie Zugang zur vollständigen Wahrheit über ihre Umgebung. Es gibt fast immer fragen, welche kategorisch beantwortet werden können. Deshalb muß der Agent in der Lage sein, unter Unsicherheit zu handeln.
Unsicherheit kann auch dadurch entstehen, wenn der Agent seine Umwelt falsch interpretiert oder nur unvollständig wahrnimmt.

Qualifikationsprobleme

Viele Regeln über den Anwendungsbereich können auf Grund der zu großen Komplexität, oder einfach weil einige unbekannt sind, unvollständig sein.
Die Wahl der richtigen Aktion, d.h. die rationale Entscheidung ist abhängig von der Relativen Wichtigkeit verschiedener Ziele und der Wahrscheinlichkeit, daß sie und bis zu welchem Grad sie erreicht werden.

Weshalb ist die Behandlung von unsicheren Wissen notwendig?

Behandlung von unsicherem Wissen in einem Bereich, welcher einen sehr hohen Anteil an unsicheren Wissen bereitstellt, scheitert aus drei Gründen (Bsp.: Medizin)

Über welchen Ansatz wird mit unsicherem Wissen umgegangen?

Evidenz

A Priori Wahrscheinlichkeit

Was heißt A Postpriori Wahrscheinlichkeit?

Die drei Wahrscheinlichkeitsaxiome

Kombinierte Wahrscheinlichkeitsverteilung

Die Bayessche Regel

Kapitel 7 - Lernen aus Beobachten

Die Bestandteile des Allgemeinen Modells lernender Agenten

Das Performanzelement

Es wählt externe Aktionen auf Grund von Wahrnehmungen aus. Es steht also für das, was bisher der ganze Agent war.

Dsa 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.

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?

  1. Welche Komponenten des Performanzelements müssen verbessert werden?
  2. Welche Repräsentation wird für diese Komponenten benutzt?
  3. Welche Rückmeldung ist erhältlich?
  4. Welche Vorabinformation ist erhältlich?

Weitere Komponenten eines Performanzelements

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.

Drei grundlegende 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.

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:

Die einfachste Form eines lernenden Agenten ist ein reflexiver lernender Agent. Er kann (Wahrnehmung, Aktion)-Paare erlernen. Die Grundstruktur eines solchen Agenten besteht aus

Die drei Arten von Lernalgorithmen

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

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

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.

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.

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...

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:

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 8 - Neuronale Netze

Wie ist ein Gehirn aufgebaut?

Das Neuron (Nervenzelle) ist die elementare Funktionseinheit des Gehirns. Ein Neuron besteht aus einem Zellkörper (Soma), der den Zellkern enthält. An der Zelle verzweigen kurze Fasern (Dendriten) und lange Fasern (Axon). Neuronen sind über Synapsen verbunden, welche das Axon mit Dendriten oder Zellkörpern anderer Neuronen verbinden.

Wie werden Informationen im Gehirn übertragen?

Die Informationsübertragung zwischen Neuronen basiert auf einem komplizierten elektrochemischen Prozess. Wird ein elektrischer Impuls an ein Axonende übertragen, erzeugt die Synapse eine Transmittersubstanz, welcher über den Dendrit in das Neuron eindringt und dort das elektrische Potential erhöht oder erniedrigt. Falls dieses Potential einen an den Neuron gebundenen Schwellenwert erreicht, wird ein Impuls (Aktionspotential) durch das Axon geschickt, welche wieder an anderen Synapsen die Erzeugung von Transmittersubstanzen hervorrufen.

Neuronale Netze

Ein Neuronales Netz besteht aus einer Menge von Knoten (Ortsbestimmung), die durch gewichtete Kanten verbunden sind. Die Gewichte sind veränderbar. Über die Anpassung dieser Gewichte ist ein neuronales Netz lernfähig. Durch das Lernen kann das Netz seine Ausgaben, die es aufgrund bestimmter Eingaben erzeugt, ab die gewünschten Ausgaben anpassen.

Jedes Neuron (Knoten) hat Eingabekanten und Ausgabekanten, welche wieder zu anderen Knoten führen. Jeder Knoten besitzt ein Aktivierungsniveau (Schwellenwert) und ein Hilfsmittel zur Berechnung dieses Niveaus. So führt jede Einheit ihre Berechnung lokal aus. Eine globale Berechnung entfällt somit. In der Umsetzung werden aber die Berechnungen meist synchronisiert, um die Einheiten immer in einer strikten Reihenfolge abarbeiten zu können.

Was macht ein Knoten bzw. Neuron?

Hauptfunktion eines Knotens ist das Aktivierungsniveau zu berechnen und gegebenfalls die empfangenen Signale an die nächsten Einheiten weiterzuleiten. Die Berechnung erfolgt in zwei Schritten:

Welche verschiedenen Aktivierungsfunktionen sind ihnen bekannt?

Für die Aktivierungsfunktion kommen eine Menge verschiedenster Funktionen in Frage. Die drei gebräuchlichsten sind die Schrittfunktion, die Signumsfunktion und die Sigmoidfunktion.

Was ist ein Bias im neuronalen Netz?

Ein Bias ist eine Erweiterung des Netzes. Ein Bias ist mit jedem Neuron verbunden, besitzt aber keine Eingabekante. Ein Bias wird verwendet, wenn keine Aktivierungsfunktion mit Schwellenwert verwendet werden soll. Statt dessen wird über diese zusätzliche Eingabe mit einem Gewicht versehen. So wird das Lernen im Netz einfacher, da nun nur noch die Gewichte geändert werden müssen und nicht mehr zusätzlich die Schwellenwerte.

Welche zwei Netzstrukturen gibt es?

Es gibt zyklenfreie (feed forward) und rekurrente Netze. Zyklenfreie Netze haben gerichtete Kanten und sind schleifenfrei. Dagegen sind in rekurrenten Netzen beliebige Strukturen erlaubt. Graphentheoretisch ist ein zyklenfreier Graph ein DAG. Die Anordnung der Neuronen wird üblicherweise in Ebenen vorgenommen. In einem geschichteten zyklenfreien Netz führen von jeder Einheit aus nur Kanten zu Einheitenn in der nächsten Ebene. Es sind keine Kanten zu Einheiten in der selben Ebene oder Kanten, die Ebenen überspingen (außer Bias) erlaubt.

Die Berechnung in rekurrenten Netzen verläuft weniger geordnet. Solche Netze können oft instabil werden und ein chaotisches Verhalten zeigen.

Wie sind die Ebenen eingeteilt?

Einheiten, welche Eingaben aus der Umwelt aufnehmen sind Eingabeeinheiten. Ihr Aktivierungswert wird durch die Umgebung bestimmt. Die Schicht, welche nur Einheiten enthält, welche Informationen an die Umgebung abgeben, sind Ausgabeeinheiten. Zwischen Eingabe- und Ausgabeeinheiten liegen die verborgenen Einheiten (hidden units). Netze welche keine verborgen Einheiten besitzen sind Perzeptrone. Solche Netze haben einen einfachen Lernprozess, haben aber eine schlechte Repräsentationsfähigkeit.

Was ist das schwierigste Problem bei Neuronalen Netzen?

Es ist extrem schwer eine optimale Netzstruktur zu finden. Ist das Netz zu klein, kann es die gewünschte Funktion nicht repräsentieren. Ist es zu groß, kann es zwar alle Beispiele der Trainingsmenge in einer Tabelle speichern, ist aber nicht Verallgemeinerungsfähig und kann neue Beispiele nicht richtig klassifizieren. (Overfitting)

Das Problem eine gute Netzstruktur zu finden, kann als Suchproblem betrachtet werden. Genetische Algorithmen sind sehr aufwendig. Ein anderes mögliches Verfahren ist das Bergsteigen, welches das Netz schrittweise modifiziert.


Quellen

Die Ausarbeitung basiert auf dem Skript von Prof. Dr. Werner Dilger