Hiermit erkläre ich, die vorliegende Arbeit selbständig verfasst und keine anderen als die angegebenen Literaturhilfsmittel benutzt zu haben. Diese Arbeit wurde bisher weder im In- noch im Ausland in gleicher oder ähnlicher Form in anderen Prüfungsverfahren vorgelegt.

3

Danksagungen

Ganz herzlich bedanken möchte ich mich bei Herrn Prof. Dr. Bernd Reusch und Herrn Dipl.-Inform. Stefan Berlik für die Unterstützung dieser Arbeit und viele wertvolle Anregungen.

Mein Dank gilt weiterhin allen am WEKA-Projekt beteiligten Mitarbeitern für die Bereitstellung der Entwicklungsumgebung für maschinelle Lern-algorithmen. Insbesondere möchte ich hier Herrn Dr. Remco Bouckaert herausheben, der mich bei der Integration von LAGD Hill Climbing in WEKA freundlich unterstützt hat und dafür mitverantwortlich ist, dass dieser Strukturlernalgorithmus für Bayes’sche Netze heute fester Bestandteil der aktuellen WEKA-Version ist.

Ganz besonders möchte ich mich auch bei Herrn Dipl.-Inform. Alexander Holland bedanken, der mir mit anregenden Diskussionen, neuen Sichtweisen und wertvollen Korrekturhinweisen während der gesamten Zeit hilfreich zur Seite stand.

5

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

7

Inhaltsverzeichnis

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

8

Inhaltsverzeichnis

Literaturverzeichnis   149

9

Abbildungsverzeichnis   

2.3.1  Spezifikation der Variablen eines Bayes’schen  

Netzes.   27

2.3.2  Spezifikation der Netzstruktur eines  

Bayes  ’schen Netzes.  28

3.1.1  Konstruktionsprozess eines Bayes’schen Netzes.  36

4.1  Lernen Bayes’scher Netze anhand von Datenbanken.  41

4.2.1.1  Test- und Trainingsfehler in Abhängigkeit von  

der  Modell-Komplexität.  47

4.2.1.2  Das Bias-Variance Dilemma.  48

4.2.2.1  Die drei Kantenoperationen im definierten  

Nachbarschaftsbegriff.   54

4.2.2.3.1  Hauptdialog von LAGD Hill Climbing zur  

Einstellung  aller wichtigen Parameter.  59

4.2.2.3.2  Die Hauptmethode von LAGD Hill Climbing.  59

4.2.2.3.3  Die zentrale Methode getOptimalOperations.  62

4.2.3.1.1  Das ALAR-MNetzwerk.  67

4.2.3.1.2  Typische Lernkurve von LAGD Hill Climbing  

am  Beispiel des Datensets ALARM.  69

11

Abbildungsverzeichnis   

4.2.3.1.3  Debugausgaben von LAGD Hill Climbing, hier  

am  Beispiel des Datensets ALARM.  70

4.2.3.1.4  Ergebnisse des Strukturlernens mit  

verschiedenen  Algorithmen auf dem Datenset ALARM.  73

4.2.3.1.5  Abhängigkeit der Qualität der berechneten  

Netzstruktur  von der Look Ahead Tiefe am Beispiel des  

Datensets  ALARM.  77

4.2.3.1.6  Abhängigkeit der Qualität der berechneten  

Netzstruktur  von der Anzahl guter Operationen am  

Beispiel  des Datensets ALARM.  79

4.2.3.2.2  Abhängigkeit der Qualität der berechneten  

Netzstruktur  von der Anzahl guter Operationen am  

Beispiel  des Datensets MEDUSA.  85

4.2.3.2.3:  Ergebnisse der Klassifikation eines auf  

Basis  von LAGD Hill Climbing gelernten Bayes’schen  

Netzes  am Beispiel einer Testreihe von 74 Fällen aus  

der  Falldatenbank MEDUSA.  87

5.1  Fusion von verteiltem Wissen in Form von  

Bayes  ’schen Netzen.  93

5.1.1.1  Ergebnisse der Sampling-Aggregation im Fall  

des  Asia-Netzwerks.  97

5.1.1.2  Ergebnisse der LinOP-Aggregation im Fall des  

ALAR  -MNetzwerks.  101

6.2.1  Mr. Parkers Kornproblem als einfaches  

Bayes  ’sches Netz.  110

6.2.2  Die komplette qualitative Repräsentation von Mr.  

Parkers  Kornproblem als Entscheidungsnetz.  111

12

Abbildungsverzeichnis   

6.5.1  Implementierte Methoden der Klasse  

DNCompiler.java.   124

6.5.2  Die Hauptmethode compile zur Kompilierung des  

Entscheidungsnetzes  myNet in eine effizient  

auswertbare  Regelbasis.  125

6.5.3  Die Methode getOptimalRuleBase zur Bestimmung  

einer  optimalen Regelbasis.  126

6.5.4  Die Methode getOptimalRuleToAdd zur Bestimmung  

einer  Regel, die am meisten zur Steigerung der  

Qualit  ät der Regelbasis beiträgt.  127

6.5.5  Die Methode getComplexityOfRuleBase zur  

Bestimmung  der Komplexität einer Regelbasis.  128

6.5.6  Die Methode getQualityOfRuleBase zur Bestimmung  

der  Qualität einer Regelbasis.  129

6.5.1.1  Die komplette qualitative Repräsentation von  

Mr.  Parkers Kornproblem als Entscheidungsnetz.  131

6.5.1.2  Ausgabe des DecisionNetworkCompilers zum  

Entscheidungsnetz  „Kornproblem“  131

6.5.2.1  Die komplette qualitative Repräsentation des  

Entscheidungsnetzes  „Börsen- und Wirtschaftslage“  135

6.5.2.2  Ausgabe des DecisionNetworkCompilers zum  

Entscheidungsnetz  „Börsen- und Wirtschaftslage“  136

6.6.1  Die komplette qualitative Repräsentation von  

Mr.  Parkers Kornproblem als Entscheidungsnetz.  139

6.6.2  Design des Fuzzy Controllers.  140

6.6.3  Definierte linguistische Terme am Beispiel der  

linguistischen  Variable „abgeknickt“  140

6.6.4  Ausgabe des DecisionNetworkCompilers zum  

Entscheidungsnetz  „Kornproblem“  142

13

Tabellenverzeichnis   

2.3.1  P(FamilieAusserHaus)  28

2.3.2  P(Magenprobleme)  28

2.3.3  P(AussenlichtAn FamilieAusserHaus)  29

2.3.4  P(HundImGarten FamilieAusserHaus,  

Magenprobleme  )  29

2.3.5  P(Hundegebell HundImGarten)  29

4.2.2.1  Die Anzahl gerichteter azyklischer Graphen  

g  (n) in Abhängigkeit von der Knotenzahl n.  53

4.2.3.1.1  Ergebnisse der Strukturlernens mit  

verschiedenen  Algorithmen auf dem Datenset ALARM.  71

4.2.3.2.1  Ergebnisse der Strukturlernens mit  

verschiedenen  Algorithmen auf dem Datenset MEDUSA.  82

6.2.1  P(Trockenheit)  112

6.2.2  P(Krankheit)  112

6.2.3  P(abgeknickt Trockenheit, Krankheit)  112

6.2.4  P(Krankheit 1 Krankheit, Behandlung)  112

6.2.5  P(Trockenheit 1 Trockenheit)  112

6.2.6  P(abgeknickt 1 Trockenheit 1, Krankheit 1)  112

15

Tabellenverzeichnis   

6.2.7  utl(Ernte)  113

6.2.8  utl(Kosten)  113

16

Kapitel 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

17

Kapitel 1. Einleitung

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 9488371302 sicherlich als eine 4

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“

18

Kapitel 1. Einleitung

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

Ein Bayes’sches Netz ist kurz gesagt ein graphisches Modell für probabilistische Beziehungen zwischen einer Menge von Variablen einer bestimmten Domäne und dient zum Schlussfolgern unter unsicherem Wissen (ähnlich dem menschlichen Schlussfolgern) und Umgang mit neuen Informationen. Hierbei geben die verwendeten Wahrscheinlichkeiten quasi die „Stärke“ der (nicht notwendigerweise) kausalen, asymmetrischen Zusammenhänge zwischen den einzelnen Variablen an. Eine ganze Klasse von Beispielen für die erfolgreiche Anwendung einfacher Bayes’scher Netze, sind so genannte Naive Bayes Nets, eingesetzt als E-Mail-Filter. Diese kommen in Anbetracht der Spam-Flut in mehr und

19

Kapitel 1. Einleitung

mehr Programmen zum Einsatz und sind meist sogar lernfähig, so dass sie sich individuell an den Benutzer und neue Spam-Mails anpassen können. Neben dem Schlussfolgern werden Bayes’sche Netze aber auch oft für das exakte Gegenteil eingesetzt: Der Bestimmung der wahrscheinlichsten Erklärung für das Auftreten bestimmter Effekte. Als komplexe Beispiele dieser Anwendung sind hier „Pathfinder“ [Hec91] und „Vista“ [Hor95] zu nennen. Pathfinder ist ein Programm zur medizinischen Diagnose von Lymphknotenerkrankungen, basiert auf einem Bayes’schen Netz, das 60 Krankheiten mit 100 Symptomen über mehr als 14000 Wahrscheinlichkeiten verknüpft, und mittlerweile die weltbesten (menschlichen) Experten in der Diagnose übertrifft. Neuere Versionen von Pathfinder sind sogar in der Lage, auf Basis der aktuellen Evidenz die Untersuchungen vorzuschlagen, welche den höchsten erwarteten Nutzen in Bezug auf eine zuverlässige Krankheitsdiagnose versprechen.

Das Vista System wurde über Jahre im NASA Mission Control Center in Houston, Texas zur zeitkritischen Auswertung von Live-Telemetrie Daten eingesetzt und liefert Wahrscheinlichkeiten von Fehlern in den Antriebssystemen eines Space Shuttles. Auch VISTA geht über ein reines Bayes’sches Netz hinaus und setzt zusätzlich auf entscheidungstheoretische Erweiterungen, die es ermöglichen, Aktionen von höchsten erwarteten Nutzen vorzuschlagen und dynamisch die relevantesten Informationen auf einem Display anzuzeigen.

1.2 Ziele und Gliederung

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

20

Kapitel 1. Einleitung

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. Dies hat den Hintergrund, dass oftmals Bayes’sche Netze aus Effizienzgründen in ressourcenbeschränkten Umgebungen nicht einsetzbar sind. Eine so genannte Kompilierung eines auf einem Bayes’schen Netz beruhenden Entscheidungsnetzes in eine Regelbasis ermöglicht in diesem Kontext den Einsatz von auf Bayes’schen Netzen basierenden Entscheidungsmodellen in zeitkritischen Domänen und trägt damit zu einer Erweiterung des Anwendungsbereichs Bayes’scher Netze bei. Aus Gründen, die noch diskutiert werden, bieten sich hier besonders Fuzzy-Regelbasen an. Nach einer kurzen Einführung von Entscheidungsnetzen 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.

Kapitel 7 fasst noch einmal in Kurzform die wesentlichen Ergebnisse der vorliegenden Arbeit zusammen und gibt einen Ausblick auf einige Aspekte, die in zukünftigen Arbeiten näher studiert werden könnten.

21

Kapitel 2

Bayes’sche Netze

In der Künstlichen Intelligenz existieren verschiedenste Ansätze zur Repräsentation von unsicherem Wissen und Inferenz unter diesem. Einer dieser Ansätze, der in den letzten Jahren verstärkt an Bedeutung gewonnen hat und momentan Gebiet der aktiven Forschung ist, sind Bayes’sche Netze. Bayes’sche Netze bieten die Möglichkeit mit Hilfe eines graphischen Modells probabilistische Zusammenhänge kompakt darzustellen und auf dieser Grundlage Inferenz durchzuführen. Da Bayes’sche Netze sehr viel Ähnlichkeit mit dem menschlichen Schlussfolgern und dem Umgang mit neuen Informationen haben, eignen sie sich besonders zum Lösen komplexer Probleme. Die einfache graphische Struktur trägt weiter dazu bei, dass einerseits die in einem Bayes’schen Netz codierten Informationen von Menschen leicht zu verstehen sind, und andererseits sich beliebige Entscheidungs-Szenarien der realen Welt ohne große Schwierigkeiten einem Computersystem vermitteln lassen.

Aufgrund der engen Verknüpfung mit der Stochastik auf der einen und der Graphentheorie auf der anderen Seite werden im folgenden zunächst einige grundlegende Begriffe kompakt definiert, um auf dieser Basis dann schließlich Bayes’sche Netze formal einzuführen und an einem Beispiel zu erläutern.

2.1 Grundlagen

Ein Graph G ist ein Paar , bestehend aus einer endlichen ) , ( E V V = Knotenmenge {

¹ Handelt es sich bei E um eine Menge, die aus geordneten Paaren

besteht, spricht man von einem gerichteten Graphen. i

23

Kapitel 2. Bayes’sche Netze

Kontext auch Elternteil von j v genannt. Die Menge aller solcher Elternteile

eines Knotens j

eine Folge von Kanten der Form

Knoten 1 v mit k

azyklischer gerichteter Graph enthält keine derartigen Zyklen.

Nachfolger von i

Eine Zufallsvariable kann im Allgemeinen mehrere Zustände x ∈ annehmen. Auch eine kontinuierliche Menge von Zuständen ist x } ,..., {

i 1 m

möglich, die vorliegende Arbeit beschränkt sich jedoch auf die Betrachtung von so genannten diskreten Zufallsvariablen, das heißt Zufallsvariablen, die = lediglich eine endliche Anzahl von Zuständen annehmen können. x X P ) (

i

bezeichnet die Wahrscheinlichkeit, dass die Zufallsvariable i X den Zustand

x annimmt. Eine vollständige gemeinsame Wahrscheinlichkeitsverteilung

i

beschreibt die Wahrscheinlichkeitswerte für alle möglichen Belegungen ∧ = x X P

( 1

vereinfacht durch

bieten die Möglichkeit, eine vollständige gemeinsame Wahrscheinlichkeitsverteilung über einer Menge von Zufallsvariablen

spezifizieren. Die bedingte Wahrscheinlichkeit

(stochastisch) unabhängig von B genau dann, wenn

Dieser Zusammenhang ist von zentraler Bedeutung in Bayes’schen Netzen. Zum Beispiel ist es mit entsprechendem Domänenwissen möglich, die Wahrscheinlichkeit, dass man ein Loch im Zahn hat, unter den Beobachtungen, dass man erstens Zahnschmerzen hat und zweitens Deutschland Fußballweltmeister wird, folgendermaßen zu vereinfachen:

Dieses Ausnutzen von bedingten Unabhängigkeiten zwischen den verschiedenen Variablen einer Domäne bildet die Grundlage für die enormen Speicherplatzeinsparungen, die mit Bayes’schen Netzen gegenüber vollständigen gemeinsamen Wahrscheinlichkeitsverteilungen erreicht werden können.

24

Kapitel 2. Bayes’sche Netze

2.2 Definition

Wie schon im vorangegangen Abschnitt angedeutet, dienen Bayes’sche Netze zur kompakten Repräsentation von vollständigen gemeinsamen Verteilungen. Nimmt man an, dass jede Zufallsvariable binär ist (also nur 2 mögliche Zustände besitzt) und setzt man weiterhin voraus, dass die Zustandsmenge lediglich aus 32 Zuständen besteht, so hat die entsprechende Tabelle, welche die gemeinsame Wahrscheinlichkeitsverteilung darstellt bereits mehr als 4 Milliarden Einträge! Allgemein liegt ein exponentieller ( n Speicherbedarf von vor, wobei d der größten Kardinalität der d O )

vorkommenden Wertebereiche und n der Anzahl der Zufallsvariablen entspricht.

Bayes’sche Netze können durch Ausnutzung von bestehenden (bedingten) Unabhängigkeiten zwischen den Zufallsvariablen der betrachteten Domäne in vielen Situationen den Speicherbedarf auf ein handhabbares Maß senken.

Definition 2.2.1 (Bayes’sches Netz): Ein Bayes’sches Netz besteht aus den folgenden Komponenten:

• eine Menge von Zufallsvariablen dargestellt durch Knoten und eine Menge von gerichteten Kanten zwischen diesen, welche zusammen einen azyklischen gerichteten Graphen bilden

bezeichnet

Hält man sich bei der Konstruktion eines Bayes’schen Netzes an die Konventionen in dem folgenden Algorithmus, ist jeder beliebige Eintrag der vollständigen gemeinsamen Verteilung einfach aus dem zugehörigen Bayes’schen Netz rekonstruierbar.

Algorithmus 2.2.1 (Formale Konstruktion eines Bayes’schen Netzes): 1. Wähle die für die betrachtete Domäne n relevanten Zufallsvariablen. = 2. FOR to n i 1 Füge i X zum Netz hinzu.

Wähle möglichst minimale Menge von Eltern

so dass

25

Kapitel 2. Bayes’sche Netze

Zur Berechnung eines beliebigen Eintrags der vollständigen gemeinsamen Verteilung auf Basis eines Bayes’schen Netzes ist es zunächst nötig, die so = genannte Produktregel einzuführen. Sie besagt, dass B P B A P B A P ) ( ) | ( ) , (

(Dies ist lediglich eine alternative Formulierung der bedingten Wahrscheinlichkeit.). Durch wiederholte Anwendung der Produktregel kann die Kettenregel hergeleitet werden:

Die einzelnen Faktoren im Produkt der letzten Zeile lassen sich aufgrund der Konstruktion eines Bayes’schen Netzes folgendermaßen vereinfachen:

Semantisch betrachtet sagt diese Gleichung nichts anderes aus, als dass jeder beliebige Eintrag der gemeinsamen Wahrscheinlichkeitsverteilung als ein Produkt von entsprechend belegten lokalen bedingten Wahrscheinlichkeitsverteilungen darstell- und berechenbar ist.

Da die conditional probability tables in den meisten Fällen deutlich weniger Speicherplatz benötigen als die entsprechende explizite Speicherung aller Einträge der vollständigen gemeinsamen Wahrscheinlichkeitsverteilung, wird es mit solch einem Bayes’schen Netz möglich, dort Inferenz zu betreiben, wo der naive Ansatz (mangels Speicherplatz) versagt. Zusammenfassend lässt sich also festhalten, dass Bayes’sche Netze eine elegante Möglichkeit bilden unsicheres Wissen kompakt zu repräsentieren, insbesondere wird meist kein exponentiell mit der Anzahl der Variablen wachsender Speicherplatz benötigt. Dies bietet auch erhebliche Vorteile bei der Konstruktion größerer und damit für praktische Anwendungen realistischerer Bayes’scher Netze.

26

Kapitel 2. Bayes’sche Netze

2.3 Beispiel eines Bayes’schen Netzes

Nach der formalen Einführung Bayes’scher Netze soll an dieser Stelle zur besseren Veranschaulichung ein einfaches Beispiel von Charniak gegeben werden, welches die wesentlichen Begriffe und Notationen plastisch verdeutlicht.

Angenommen, man kommt abends nach Hause und möchte wissen, ob die Familie zu Hause ist, bevor man das Haus betritt. Man weiß, dass die Familie oft das Außenlicht anlässt, wenn das Haus verlassen ist, manchmal aber auch, wenn ein Gast erwartet wird. Außerdem gibt es noch einen Hund in der Familie. Oft hört man ihn im Garten bellen, jedoch ist er dort meistens nur, wenn er Magenprobleme hat oder die Familie außer Haus ist. [Cha91] Soweit die Situation, nun zur Konstruktion des Bayes’schen Netzes: Zunächst legt man die für diese Domäne relevanten Variablen inklusive ihren Wertebereichen fest und ordnet sie nach Möglichkeit schon nach Kausalität an. Im Beispiel wäre da zunächst einmal die Variable „FamilieAusserHaus“, weiterhin „Magenprobleme“, „AussenlichtAn“, „HundImGarten“ und

„Hundegebell“. Alle Variablen seien binär und können die Werte „true“ oder „false“ annehmen. Abbildung 2.3.1 stellt die Variablen graphisch dar (Man beachte die Anordnung der Knoten in Ebenen, welche nach Kausalität von oben nach unten geordnet sind.).

Abbildung 2.3.1: Spezifikation der relevanten Variablen

Im nächsten Schritt legt man die Netzstruktur fest. Hierbei orientiert man sich typischerweise an der kausalen Interpretation der Kanten, muss aber

27

Kapitel 2. Bayes’sche Netze

beachten, dass der resultierende Graph keine Zyklen enthalten darf. Demnach ergibt sich in obigem Kontext folgende Netztopologie (siehe Abbildung 2.3.2). Gerichtete Kanten sind also genau zwischen Variablen (dargestellt duch cyan-farbene Ellipsen) eingefügt worden, die einen kausalen Zusammengang aufweisen. Die Orientierung der Kante ist hierbei so gewählt, dass sie von der Ursache auf die Wirkung weist.

Schließlich sind noch die so genannten a priori Wahrscheinlichkeiten der Wurzelknoten (diese drücken Überzeugungen aus bevor bzw. wenn keine weiteren Informationen vorliegen) und die bedingten Wahrscheinlichkeiten der conditional probability tables festzulegen. Die Tabellen 2.3.1 bis 2.3.5 zeigen eine mögliche Belegung.

28

In dieser Phase kommt zum Ausdruck, dass die kausalen Verbindungen nicht absolut sind, vielmehr zeigen die gerichteten Kanten lediglich mögliche (kausale) Verbindungen an. Zum Beispiel ist es durchaus möglich, dass das Außenlicht an ist, obwohl die Familie zu Hause ist. Selbstverständlich ist es auch denkbar ein so komplexes (in der Anzahl der Variablen und Dichte) Netz aufzustellen, welches nur aus absoluten kausalen Verbindungen besteht, allerdings widerspricht das dem Charakter von Bayes’schen Netzen, die gerade dann zum Einsatz kommen, wenn man nicht alle Zusammenhänge in der betrachteten Domäne versteht und deshalb

auf Wahrscheinlichkeiten angewiesen ist. Nachdem das Bayes’sche Netz einmal aufgestellt ist, kann man es beispielsweise dazu benutzen, beliebige Anfragen zu stellen und erhält als Ausgabe die Wahrscheinlichkeit dafür, dass die Abfrage-Variable einen gewissen Wert annimmt (in Abhängigkeit von den gegebenen Beobachtungen).

Auch hier zum besseren Verständnis ein kurzes Beispiel: Man beobachtet, dass das Außenlicht an ist (AussenlichtAn=true), aber hört keinen Hund bellen (Hundegebell=false), und möchte auf Basis dieser Evidenz nun wissen, wie wahrscheinlich

(FamilieAusserHaus=true). P(FamilieAusserHaus=true|AssenlichtAn=true, Hundegebell=false) (in diesem Fall etwa 0.500551727589584) kann mittels Inferenzmechanismen berechnet werden, was zum nächsten Kapitel überleitet.

29

Kapitel 2. Bayes’sche Netze

2.4 Inferenz in Bayes’schen Netzen

Bei der Durchführung von Inferenz bei gegebener vollständiger gemeinsamer Wahrscheinlichkeitsverteilung der Zufallsvariablen X hat man allgemein folgende Ausgangssituation:

Man hat eine Menge von Abfrage-Variablen Q und eine hierzu disjunkte Menge von Evidenz-Variablen E . Die Menge der verbleibenden verborgenen

(hidden) Variablen sei Typischerweise ist man interessiert an der a posteriori gemeinsamen Verteilung der Abfrage-Variablen Q bei beobachteten Belegungen e der = . Nach der Definition der bedingten Evidenz-Variablen E , also e E Q P ) | ( Wahrscheinlichkeit gilt:

Durch Aufsummieren der gemeinsamen Einträge, wobei für die verborgenen Variablen alle möglichen Belegungen eingesetzt werden, erhält man:

1

α = ( ist hier eine Normalisierungskonstante, die für die reine

P = ) ( e E

Abwägung zwischen den verschiedenen Möglichkeiten nicht relevant ist. Die einzelnen Summanden werden in diesem Zusammenhang Randwahrscheinlichkeiten genannt.) Diese Aufsummierung von Randwahrscheinlichkeiten bezeichnet man auch als Marginalisierung. Angewendet auf das Beispiel des vorangegangenen Kapitels ergibt sich damit zur Berechnung von P(FamilieAusserHaus=true|AussenlichtAn=true, Hundegebell=false) folgender Quotient:

P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=false, HundImGarten=false)

+ P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=false, HundImGarten=true)

+ P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=true, HundImGarten=false)

+ P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=true, HundImGarten=true)

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ≈ 0.5006.

P(FamilieAusserHaus=false, AussenlichtAn=true, Hundegebell=false, Magenprobleme=false, HundImGarten=false)

+ P(FamilieAusserHaus=false, AussenlichtAn=true, Hundegebell=false, Magenprobleme=false, HundImGarten=true)

+ P(FamilieAusserHaus=false, AussenlichtAn=true, Hundegebell=false, Magenprobleme=true, HundImGarten=false)

+ P(FamilieAusserHaus=false, AussenlichtAn=true, Hundegebell=false, Magenprobleme=true, HundImGarten=true)

+ P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=false, HundImGarten=false)

+ P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=false, HundImGarten=true)

+ P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=true, HundImGarten=false)

+ P(FamilieAusserHaus=true, AussenlichtAn=true, Hundegebell=false, Magenprobleme=true, HundImGarten=true)

30

Kapitel 2. Bayes’sche Netze

Im Falle eines Bayes’schen Netzes gibt es bei der Inferenz keine großen Unterschiede im Vergleich zum Fall der vollständigen gemeinsamen Verteilung, denn diese kann - wie zuvor erläutert - durch Multiplikation einzelner bedingter Wahrscheinlichkeiten berechnet werden. Mit Hilfe der gemeinsamen Verteilung können dann beliebige Anfragen der Form = beantwortet werden. Insofern geht diese wichtige Eigenschaft von P ) | (

vollständigen gemeinsamen Verteilung beim Übergang zu Bayes’schen Netzen also nicht verloren.

Oft ist man auch in der Situation, dass man ein Bayes’sches Netz aufgestellt, gewisse Evidenzen bereits eingetragen hat und dann neues Wissen in eine so genannte Knowledge Base einfließt. Diese neuen Evidenzen sind dann in das Bayes’sche Netz einzutragen und durchzupropagieren, so dass die (bedingten) Wahrscheinlichkeiten aller CPTs auf dem neuesten Stand sind (auf Basis der aktuellen Evidenz in der Knowledge Base). Hier geht es also nicht um das konkrete Abfragen bestimmter Wahrscheinlichkeiten, sondern um ein Update aller Wahrscheinlichkeiten des gesamten Netzes. Dieser Vorgang ist in der Literatur unter Belief Updating zu finden, und es sind sowohl exakte Algorithmen als auch effiziente Approximationsalgorithmen bekannt. Vergleiche hierzu beispielsweise [Jen01]. Festzuhalten ist noch, dass das Problem allgemeiner Anfragen in beliebigen Bayes’schen Netzen (und damit das Belief Updating eines ganzen Netzes erst recht) NP-vollständig ist, was man sich leicht klarmachen kann,

wenn man bedenkt, dass in

Ausprägungen der verborgenen Variablen H aufsummiert werden muss und dies können je nach Kardinalität von H exponentiell (in der Anzahl der Variablen) viele sein.

31