In der vorliegenden Arbeit werden zunächst die nötigen fundamentalen wahrscheinlichkeitstheoretischen Grundlagen bezüglich Bayes’scher Netze erläutert, um diese dann formal einzuführen.
Auf dieser Basis wird dann auf Konstruktionsmethoden für Bayes’sche Netze im Allgemeinen und den Einsatz maschineller Lernverfahren im Besonderen eingegangen. Speziell soll in diesem Kontext der Aspekt des Strukturlernens Bayes’scher Netze studiert werden. Nach einer Strukturierung der in der Literatur vorkommenden Ansätze werden aktuell erforschte Strukturlernalgorithmen diskutiert und gegenübergestellt, aber auch die Entwicklung und anschließende Implementierung eines eigenen Algorithmus wird dargelegt. Eine Laufzeitanalyse und empirische Tests an einer synthetisch erzeugten Datenbank und einer akquirierten Datenbank aus dem Anwendungsbereich Medizin runden dieses zentrale Kapitel ab.
In einem weiteren Kapitel werden Möglichkeiten der Einbringung von Expertenwissen diskutiert, insbesondere die Fusion von verteiltem Wissen ist in diesem Zusammenhang interessant. Hierbei geht es um die Integration von dem – möglicherweise sich widersprechenden – Wissen von mehreren (menschlichen) Experten codiert in Bayes’schen Netzen auf der einen Seite und auf der Basis maschineller Lernverfahren generierter (Teil-)Netze (die auf empirisch gewonnen Daten in Case-Datenbanken beruhen) auf der anderen Seite. Beispielsweise ist dies oft der Fall, wenn mehrere Ärzte mit verteiltem Wissen (teilweise auch dezentral an verschiedenen Orten ansässig) ein Spezialistenteam bilden und Entscheidungen treffen müssen.
Anschließend werden Möglichkeiten diskutiert, wie auf Basis eines (gelernten) Entscheidungsnetzes regelbasierte Systeme wie IF-THEN Regelbasen generiert werden können. Nach einer kurzen Einführung von Entscheidungs-netzen auf der einen Seite und Fuzzy-Regelbasen auf der anderen Seite, schließt sich ein Kapitel an, welches sich mit der Kompilierung von Entscheidungsnetzen in Fuzzy-Regelbasen auseinandersetzt. In diesem Zusammenhang wird ein Framework zur Kompilierung hergeleitet und ein Pseudo-Algorithmus zur Lösung dieses Problems vorgestellt. Eine konkrete Implementierung eines auf diesem Framework basierenden Algorithmus wird zusammen mit ersten Ergebnissen in den letzten beiden Unterkapiteln dargelegt.
Universität Dortmund
Strukturlernen graphbasierter Modelle auf der Basis verteilten Wissens
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 LinOPAggregation ... 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
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 Wurzel(94883713024) 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
[...]
- Quote paper
- Manuel Neubach (Author), 2005, Strukturlernen graphbasierter Modelle auf der Basis verteilten Wissens, Munich, GRIN Verlag, https://www.grin.com/document/57547
