Einleitung zum Fachgebiet der Künstlichen Intelligenz.
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.
Dies kann nur für einen bestimmten Zeitpunkt beschrieben werden. Vier Merkmale sind dafür maßgebend:
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.
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 |
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.
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.
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.
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.
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.
Eine Umgebung ist deterministisch, wenn der nächste Zustand vollständig durch den aktuellen Zustand und den gewählten Aktionen definiert ist.
Eine Umgebung ist episodisch, wenn sich die Erfahrungen des Agenten in unabhängige Episoden aufteilen lassen.
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.
Eine Umgebung heißt diskret, wenn es in ihr eine begrenzte und unterscheidbare Anzahl von Wahrnehmungen und Aktionen gibt.
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.
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.
Um ein Problem formulieren zu können, müssen Zustände bekannt und Aktionen definiert werden. Dafür gibt es verschiedene Problemtypen.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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:
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
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) |
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) |
Optimalität: | nein |
Vollständigkeit: | nein |
Zeitaufwand : | O(b^m) (worst Case) |
Speicherplatzbedarf: | O(b*m) |
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) |
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) |
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)) |
Bei blinden Suchverfahren kann nicht Einfluss auf die Knotenwahl genommen werden. Informiert bedeutet, dass man dies z.B. mit heuristiken beeinflussen kann.
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.
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*...
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) |
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) |
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) |
Der SMA* merkt sich Knoten, welche er schon mal expandiert hat. Somit wird Sucheffizienz erhöht. SMA* hat folgende Eigenschaften:
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.
Das Bergsteigen ist ein stures Suchen von besseren Werten. Gibt es mehrere bessere Knoten, muß via Zufallsfunktion einer selektiert werden.
Stößt die Suche auf ein lokales Maximum, bleibt sie dort hängen und findet ein evtuelles globales Maximum nicht.
Einmal auf einer Ebene sitzend, kann der Algorithmus nur raten, in welche Richtung fortgesetzt werden soll.
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.
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)
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.
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.
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:
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).
Hat der Agent einen Lernmechanismus, dann wird er als autonom bezeichnet.
Ziel der Wissensrepräsentation ist es, Wissen in einer für den Rechner verständlichen Form zu kodieren. Eine Wissensrepräsentationssprache definiert sich durch:
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).
Kompositionalität ist die Beziehung zwischen Semantik und Syntax verschiedener aufeinander folgender Sätze.
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.
Detuktion beschreibt korrekte Inferenzen.
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:
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.
Mit Wahrheitstabellen läßt sich die Gültigkeit testen. Sie Stellen ein Beweisverfahren dar, was unabhängig von der Bedeutung der Teilaussagen ist.
Jede Welt, in der ein Satz unter einer bestimmten Interpretation wahr ist, ist ein Modell des Satzes unter dieser Interpretation.
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:
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.
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.
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.
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.
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.
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.
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 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.
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.
Diachronische Regeln, sind Regeln, welche beschreiben, wie sich eine Welt verändert oder auch nicht verändert.
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.
"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.
Synchrone Regeln setzen verschiedene Eigenschaften desselben Weltzustandes in Relation.
Geben die Richtung einer angenommenen Kausalität in einer Welt wieder. Systeme, die mit kausalen Regeln schlußfolgern, heißen modellbasierte Schlußfolgerungssysteme.
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.
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 geeigneten Axiomen kann man mit ASK eine Aktionsfolge aus der Wissensbasis ableiten. Für größere Welten wäre aber der Rechenaufwand zu groß.
Mit Best-First-Suche kann ein Pfad zum Ziel bestimmt werden. Dazu muss Wissen in eine Menge geeigneter Operatoren und Zustandsrepräsentationen umgeformt werden.
Erfolgt mit speziellen Schlußfolgerungssystemen, die entworfen wurden, über Aktionen zu folgern.
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:
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.
Es gibt einen Satz und man möchte diese über die Wissensbasis vergleichen.
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:
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:
Eine Möglichkeit ist die Axiomisierung, (Eigenschaften als
Äquivalenzrelation).
Zweite Möglichkeit ist spezielle Inferenzregel Demodulation.
Führe, wenn möglich einen Inferenzschritt mit einer Klausel, die nur aus einem Literal besteht durch.
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.
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.
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.
Aktionen werden dargestellt durch Programme. Sie erzeugen Beschreibungen der Folgezustände.
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.
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.
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.
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:
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).
Wie oben, nur dass eine bestimmte Belegung von Variablen ausgeschlossen wird, aber alle anderen erlaubt werden. Ist nur schwer zu implementieren.
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.
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.
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.
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.
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.
Behandlung von unsicherem Wissen in einem Bereich, welcher einen sehr hohen Anteil an unsicheren Wissen bereitstellt, scheitert aus drei Gründen (Bsp.: Medizin)
Es wählt externe Aktionen auf Grund von Wahrnehmungen aus. Es steht also für das, was bisher der ganze Agent war.
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.
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.
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.
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.
Der Agent kann das Ergebnis seiner Aktionen beobachten oder es wird ihm mitgeteilt. ("Lernen durch Lehrer")
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
Es müssen Maßnahmen getroffen werden, um fehlende Daten zu ergänzen. Attribute müssen mit besonderen Eigenschaften verwendbar gemacht werden.
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:
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 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.
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.
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.
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.
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:
Für die Aktivierungsfunktion kommen eine Menge verschiedenster Funktionen in Frage. Die drei gebräuchlichsten sind die Schrittfunktion, die Signumsfunktion und die Sigmoidfunktion.
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.
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.
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.
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.
Die Ausarbeitung basiert auf dem Skript von Prof. Dr. Werner Dilger