Strukturlernen
graphbasierter Modelle auf der Basis verteilten Wissens
Diplomarbeit
Fachbereich Informatik, Lehrstuhl I
(Automaten- und Schaltwerktheorie, Computational Intelligence)
Endversion vom 25.09.2005
von
Manuel Neubach
Inhaltsverzeichnis
1 Einleitung ... 17
1.1 Einordnung ... 19
1.2 Ziele und Gliederung ... 20
2 Bayes’sche Netze ... 23
2.1 Grundlagen ... 23
2.2 Definition ... 25
2.3 Beispiel eines Bayes’schen Netzes ... 27
2.4 Inferenz in Bayes’schen Netzen ... 30
3 Konstruktion Bayes’scher Netze ... 33
3.1 Der Bayes’sche Ansatz ... 34
3.2 Der frequentistische Ansatz ... 38
4 Maschinelles Lernen Bayes’scher Netze ... 41
4.1 Lernsituationen ... 42
4.2 Strukturlernen Bayes’scher Netze ... 44
4.2.1 Qualitätsmaße ... 46
4.2.2 Suchstrategien ... 52
4.2.2.1 Simulated Annealing ... 54
4.2.2.2 Greedy Hill Climbing ... 55
4.2.2.3 LAGD Hill Climbing ... 57
4.2.3 Experimentelle Ergebnisse ... 66
4.2.3.1 Datenset ALARM ... 66
4.2.3.2 Datenset MEDUSA ... 80
5 Integration von verteiltem Wissen ... 91
5.1 Konkurrierende Fusion ... 94
5.1.1 Konkurrierende Fusion via Sampling ... 95
5.1.2 Konkurrierende Fusion via LinOP-Aggregation ... 98
5.2 Komplementäre Fusion ... 102
5.3 Kooperative Fusion ... 103
6 Generierung von Regelbasen anhand von Entscheidungsnetzen ... 105
6.1 Definition Entscheidungsnetz ... 108
6.2 Beispiel eines Entscheidungsnetzes ... 110
6.3 Definition Fuzzy-Regelbasis ... 114
6.4 Ein Framework für die Kompilierung von Entscheidungsnetzen in Fuzzy-Regelbasen ... 116
6.5 Implementierung eines Algorithmus zur automatischen Generierung einer Regelbasis anhand eines Entscheidungsnetzes ... 122
6.5.1 Experimentelle Ergebnisse für das Entscheidungsnetz „Kornproblem“ ... 131
6.5.2 Experimentelle Ergebnisse für das Entscheidungsnetz „Börsen- und Wirtschaftslage“ ... 134
6.6 Verallgemeinerung auf Fuzzy-Regelbasen ... 138
7 Zusammenfassung und Ausblick ... 145
Literaturverzeichnis ... 149
Kapitel 1
1. Einleitung
Eines der interessantesten Gebiete der Künstlichen Intelligenz ist das Thema „Rationales Handeln“. Nach dem PAGE-Konzept [RNo95] lebt ein Agent in einer Umgebung (Environment) und bildet Wahrnehmungssequenzen (Percepts) auf Aktionen (Actions) ab, um ein bestimmtes Ziel (Goal) zu erreichen. Offensichtlich zeichnen sich verschiedene Agenten durch die Funktion aus, die Percepts auf Actions abbildet. Was versteht man nun unter „Rationalem Handeln“?
Kurz gesagt heißt „Rationales Handeln“ nichts anderes als das „Richtige“ zu tun. Was aber ist in einer gegebenen Situation das „Richtige“? Muss der Agent dafür allwissend und nach Ausführung der „richtigen“ Aktionen zwingend erfolgreich sein? Sicherlich nicht, „Rationales Handeln“ bedeutet vielmehr auf Basis der gegebenen Informationen die Aktionen auszuführen, die erwartungsgemäß das Maximale zum Erreichen des Ziels beitragen.
Das Schachspiel war über Jahrzehnte einer der Benchmarks in der Künstlichen Intelligenz. Auch hier lässt sich das PAGE-Konzept anwenden: Die Umgebung besteht aus dem Spielfeld, der Zeit, dem Gegenspieler, zur Wahrnehmung gehören vergangene und aktuelle Stellungen auf dem Spielfeld, die durch das Bewegen von Figuren (den Aktionen) zustande kommen. Ziel ist selbstverständlich das Gewinnen, vielleicht noch in möglichst wenigen Zügen oder möglichst elegant.
Nun ist es beim Schach so, dass die gesamte Umgebung beobachtbar ist, der Agent also Zugang zu sämtlichen Informationen der Umgebung hat, weiterhin ist die Umgebung deterministisch, das heißt, der nächste Zustand der Umgebung kann zuverlässig aus dem aktuellen Zustand und dem aktuellen Eingriff vorausgesagt werden.
In der realen Welt können aber gerade diese Eigenschaften meist nicht garantiert werden, der Agent hat es mit einer partiellen Beobachtbarkeit der Umgebung, ungenauen Sensordaten und der Ungewissheit im Resultat seiner Aktionen zu tun. Unter diesen Bedingungen muss er unter unsicherem Wissen (statt eines konkreten Zustands liegt z. B. nur eine Wahrscheinlichkeitsverteilung der möglichen Zustände vor) Aktionssequenzen wählen, die das Maximale (typischerweise orientiert man sich in diesem Kontext an Scoring-Funktionen, welche einzelnen Aktionen Scores zuordnen) zum Erreichen seines Ziels beitragen – offensichtlich eine deutlich schwierigere Situation als beim Schachspiel.
Diese Situation spiegelt sich auch in aktuellen Benchmarks wider. Nachdem 1997 der legendäre IBM-Computer Deep Blue den amtierenden Schachweltmeister Garry Kasparow erstmalig geschlagen hat, wurde nach neuen Bereichen gesucht, in denen man Computer mit menschlichen Leistungen messen kann. Ein aktueller Benchmark in der künstlichen Intelligenz ist Roboter-Fußball.
Roboter-Fußball ist ein perfektes Beispiel für ein Real World-Szenario, bei dem es auf Schlussfolgern unter Unsicherheit ankommt. Die einzelnen Roboter-Fußballer (Agenten) haben in den meisten der am RoboCup (der jährlich stattfindenden Weltmeisterschaft im Roboter-Fußball) teilnehmenden Ligen nur die Möglichkeit, Ausschnitte aus der Umgebung wahrzunehmen; haben also kein komplettes Weltbild. Weiterhin sind die Sensordaten, die auf Basis der Kamerabilder berechnet werden oft nicht nur sehr ungenau, sondern können im Extremfall sogar schlichtweg falsch sein. Auch das Resultat von angestrebten Aktionen, beispielsweise einer Drehung um 90°, kann nicht deterministisch vorausgesagt werden, vielmehr hat man mehr oder weniger große Abweichungen (bei einer Drehung z. B. von 3° und mehr) hinzunehmen. Zusätzlich zu der beschriebenen partiellen Beobachtbarkeit der Umgebung, den ungenauen Sensordaten und der Ungewissheit im Resultat der Aktionen kommt beim Roboter-Fußball noch ein weiterer erschwerender Faktor hinzu: Es handelt sich um ein so genanntes Multi-Agenten-System [Mer99]. Das heißt, es sind nicht nur die Aktionssequenzen eines einzelnen Agenten so zu wählen, dass sie das Maximale zum Erreichen des Ziels beitragen, sondern das komplette Verhalten des Teams ist in die zu optimierende Funktion mit einzubeziehen.
Versetzt man sich zurück in die Zeit bevor es die ersten Rechner gab, so wäre das Lösen einer Rechenaufgabe wie [...] sicherlich als eine Form von Intelligenz angesehen worden, insbesondere dann, wenn man in der Lage ist, das Radizieren zeitlich sehr schnell durchzuführen. Nachdem jeder einen Rechner hatte, welcher diese Aufgabe in kürzester Zeit löste, hat dies niemand mehr als Intelligenz bezeichnet. Ähnlich ist es mit dem Schachspiel: Bevor der amtierende menschliche Weltmeister im Schach durch eine Maschine geschlagen wurde, galt das Bestehen gegen einen Gegner von der Klasse Kasparows als Beweis für künstliche Intelligenz. Spätestens seit 1997 wird dies nicht mehr als Intelligenz angesehen, sondern von bösen Zungen als „simples Ausführen einer vorher festgelegten Folge von Befehlen“ abgewertet. Aber unterscheidet sich das menschliche Denken so sehr hiervon?
Aktuell wird das Bestehen gegen den menschlichen Weltmeister im Fußball als Form von künstlicher Intelligenz betrachtet. Bis dato hat noch keine Robotermannschaft gegen ein menschliches Team gewonnen oder auch nur gespielt. Dieses Fernziel soll 2050 erreicht sein (siehe z. B. [BMa03]). Bis die Schwelle was als Intelligenz angesehen wird (und was nicht), auf dieses Niveau angehoben ist, müssen im softwaretechnischen Bereich allerdings noch viele Probleme, gerade auch im Umgang mit unsicherem Wissen gelöst werden.
1.1 Einordnung
Noch vor einigen Jahrzehnten galt es in der Wissenschaft im Allgemeinen und der Künstlichen Intelligenz im Besonderen den Faktor Unsicherheit möglichst zu vermeiden. Diese Einstellung hat sich jedoch in den letzten Jahren grundlegend geändert. Vielmehr wird heute die Auseinandersetzung mit Unsicherheit als wichtiger Faktor in der Modellbildung betrachtet, was es in vielen Situationen erst ermöglicht, passende approximative Modelle zu kreieren, deren Komplexität sich in Grenzen hält.
Die Künstliche Intelligenz bietet verschiedenste Ansätze zur Behandlung von Unsicherheit. Stichworte sind beispielsweise: Nichtmonotone Logik, Regeln mit Unsicherheitsfaktoren, Fuzzy-Logik oder graphbasierte Repräsentationen wie Bayes’sche Netze und Entscheidungsnetze, welche die zentralen Studienobjekte der vorliegenden Arbeit darstellen.
Gerade Bayes’sche Netze werden in den letzten Jahren als das graphische Framework gehandelt, das verschiedenste Aspekte der Künstlichen Intelligenz vereint, die Unzulänglichkeiten der eng verwandten Neuronalen Netze (z. B. in Bezug auf ihre Interpretierbarkeit) überwindet und einmal der Schlüssel für erfolgreiche intelligente Anwendungen und Produkte sein wird. Bill Gates selbst fasste es 1996 in einem Interview mit der LA Times so zusammen: „Microsoft′s competitive advantage is its expertise in Bayesian networks.“ [Hel96].
[....]
