Strukturlernen graphbasierter Modelle auf der Basis verteilten Wissens

Inhaltsverzeichnis

1 Einleitung
1.1 Einordnung
1.2 Ziele und Gliederung.

2 Bayes’sche Netze
2.1 Grundlagen
2.2 Definition
2.3 Beispiel eines Bayes’schen Netzes
2.4 Inferenz in Bayes’schen Netzen

3 Konstruktion Bayes’scher Netze
3.1 Der Bayes’sche Ansatz
3.2 Der frequentistische Ansatz

4 Maschinelles Lernen Bayes’scher Netze
4.1 Lernsituationen
4.2 Strukturlernen Bayes’scher Netze.
4.2.1 Qualitätsmaße..
4.2.2 Suchstrategien.
4.2.2.1 Simulated Annealing.
4.2.2.2 Greedy Hill Climbing
4.2.2.3 LAGD Hill Climbing
4.2.3 Experimentelle Ergebnisse
4.2.3.1 Datenset ALARM
4.2.3.2 Datenset MEDUSA.

5 Integration von verteiltem Wissen
5.1 Konkurrierende Fusion
5.1.1 Konkurrierende Fusion via Sampling.
5.1.2 Konkurrierende Fusion via LinOP-Aggregation
5.2 Komplementäre Fusion.
5.3 Kooperative Fusion

6 Generierung von Regelbasen anhand von Entscheidungsnetzen
6.1 Definition Entscheidungsnetz.
6.2 Beispiel eines Entscheidungsnetzes
6.3 Definition Fuzzy-Regelbasis
6.4 Ein Framework für die Kompilierung von Entscheidungsnetzen in Fuzzy-Regelbasen..
6.5 Implementierung eines Algorithmus zur automatischen Generierung einer Regelbasis anhand eines Entscheidungsnetzes
6.5.1 Experimentelle Ergebnisse für das Entscheidungsnetz „Kornproblem“..
6.5.2 Experimentelle Ergebnisse für das Entscheidungsnetz „Börsen- und Wirtschaftslage“.
6.6 Verallgemeinerung auf Fuzzy-Regelbasen

7 Zusammenfassung und Ausblick

Literaturverzeichnis

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.

Abbildungsverzeichnis

2.3.1 Spezifikation der Variablen eines Bayes’schen Netzes

2.3.2 Spezifikation der Netzstruktur eines Bayes’schen Netzes

3.1.1 Konstruktionsprozess eines Bayes’schen Netzes

4.1 Lernen Bayes’scher Netze anhand von Datenbanken

4.2.1.1 Test- und Trainingsfehler in Abhängigkeit von der Modell-Komplexität

4.2.1.2 Das Bias-Variance Dilemma

4.2.2.1 Die drei Kantenoperationen im definierten Nachbarschaftsbegriff

4.2.2.3.1 Hauptdialog von LAGD Hill Climbing zur Einstellung aller wichtigen Parameter

4.2.2.3.2 Die Hauptmethode von LAGD Hill Climbing

4.2.2.3.3 Die zentrale Methode getOptimalOperations

4.2.3.1.1 Das ALARM-Netzwerk.

4.2.3.1.2 Typische Lernkurve von LAGD Hill Climbing am Beispiel des Datensets ALARM

4.2.3.1.3 Debugausgaben von LAGD Hill Climbing, hier am Beispiel des Datensets ALARM

4.2.3.1.4 Ergebnisse des Strukturlernens mit verschiedenen Algorithmen auf dem Datenset ALARM

4.2.3.1.5 Abhängigkeit der Qualität der berechneten Netzstruktur von der Look Ahead Tiefe am Beispiel des Datensets ALARM

4.2.3.1.6 Abhängigkeit der Qualität der berechneten Netzstruktur von der Anzahl guter Operationen am Beispiel des Datensets ALARM

4.2.3.2.2 Abhängigkeit der Qualität der berechneten Netzstruktur von der Anzahl guter Operationen am Beispiel des Datensets MEDUSA.

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

5.1 Fusion von verteiltem Wissen in Form von Bayes’schen Netzen

5.1.1.1 Ergebnisse der Sampling-Aggregation im Fall des Asia-Netzwerks

5.1.1.2 Ergebnisse der LinOP-Aggregation im Fall des ALARM-Netzwerks

6.2.1 Mr. Parkers Kornproblem als einfaches Bayes’sches Netz

6.2.2 Die komplette qualitative Repräsentation von Mr. Parkers Kornproblem als Entscheidungsnetz.

6.5.1 Implementierte Methoden der Klasse DNCompiler.java

6.5.2 Die Hauptmethode compile zur Kompilierung des Entscheidungsnetzes myNet in eine effizient auswertbare Regelbasis

6.5.3 Die Methode getOptimalRuleBase zur Bestimmung einer optimalen Regelbasis

6.5.4 Die Methode getOptimalRuleToAdd zur Bestimmung einer Regel, die am meisten zur Steigerung der Qualität der Regelbasis beiträgt.

6.5.5 Die Methode getComplexityOfRuleBase zur Bestimmung der Komplexität einer Regelbasis

6.5.6 Die Methode getQualityOfRuleBase zur Bestimmung der Qualität einer Regelbasis

6.5.1.1 Die komplette qualitative Repräsentation von Mr. Parkers Kornproblem als Entscheidungsnetz

6.5.1.2 Ausgabe des DecisionNetworkCompilers zum Entscheidungsnetz „Kornproblem“

6.5.2.1 Die komplette qualitative Repräsentation des Entscheidungsnetzes „Börsen- und Wirtschaftslage“

6.5.2.2 Ausgabe des DecisionNetworkCompilers zum Entscheidungsnetz „Börsen- und Wirtschaftslage“

6.6.1 Die komplette qualitative Repräsentation von Mr. Parkers Kornproblem als Entscheidungsnetz

6.6.2 Design des Fuzzy Controllers

6.6.3 Definierte linguistische Terme am Beispiel der linguistischen Variable „abgeknickt“

6.6.4 Ausgabe des DecisionNetworkCompilers zum Entscheidungsnetz „Kornproblem“

Tabellenverzeichnis

2.3.1 P(FamilieAusserHaus)

2.3.2 P(Magenprobleme)

2.3.3 P(AussenlichtAn|FamilieAusserHaus).

2.3.4 P(HundImGarten|FamilieAusserHaus, Magenprobleme)

2.3.5 P(Hundegebell|HundImGarten)

4.2.2.1 Die Anzahl gerichteter azyklischer Graphen g(n) in Abhängigkeit von der Knotenzahl n

4.2.3.1.1 Ergebnisse der Strukturlernens mit verschiedenen Algorithmen auf dem Datenset ALARM.

4.2.3.2.1 Ergebnisse der Strukturlernens mit verschiedenen Algorithmen auf dem Datenset MEDUSA

6.2.1 P(Trockenheit).

6.2.2 P(Krankheit)

6.2.3 P(abgeknickt|Trockenheit, Krankheit)

6.2.4 P(Krankheit_1|Krankheit, Behandlung)

6.2.5 P(Trockenheit_1|Trockenheit)

6.2.6 P(abgeknickt_1|Trockenheit_1, Krankheit_1).

6.2.7 utl(Ernte).

6.2.8 utl(Kosten)

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 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[Abbildung in dieser Leseprobe nicht enthalten]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] .

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 Zusammen-hä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 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 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 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 dar-gelegt.

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.

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 [Abbildung in dieser Leseprobe nicht enthalten]ist ein Paar Abbildung in dieser Leseprobe nicht enthalten, bestehend aus einer endlichen Knotenmenge[Abbildung in dieser Leseprobe nicht enthalten]und einer Kantenmenge Abbildung in dieser Leseprobe nicht enthalten. Handelt es sich bei[Abbildung in dieser Leseprobe nicht enthalten]um eine Menge, die aus geordneten Paaren[Abbildung in dieser Leseprobe nicht enthalten]besteht, spricht man von einem gerichteten Graphen. [Abbildung in dieser Leseprobe nicht enthalten]wird in diesem Kontext auch Elternteil von[Abbildung in dieser Leseprobe nicht enthalten]genannt. Die Menge aller solcher Elternteile eines Knotens[Abbildung in dieser Leseprobe nicht enthalten]wird mit[Abbildung in dieser Leseprobe nicht enthalten]bezeichnet. Ein (gerichteter) Pfad in[Abbildung in dieser Leseprobe nicht enthalten]ist eine Folge von Kanten der Form Abbildung in dieser Leseprobe nicht enthalten; er verbindet den Knoten[Abbildung in dieser Leseprobe nicht enthalten]mit Abbildung in dieser Leseprobe nicht enthalten. Im Fall[Abbildung in dieser Leseprobe nicht enthalten]handelt es sich um einen Zyklus. Ein azyklischer gerichteter Graph enthält keine derartigen Zyklen.[Abbildung in dieser Leseprobe nicht enthalten]ist Nachfolger von[Abbildung in dieser Leseprobe nicht enthalten]genau dann, wenn ein Pfad von[Abbildung in dieser Leseprobe nicht enthalten]nach[Abbildung in dieser Leseprobe nicht enthalten]existiert.

Eine Zufallsvariable kann im Allgemeinen mehrere Zustände [Abbildung in dieser Leseprobe nicht enthalten]annehmen. Auch eine kontinuierliche Menge von Zuständen ist 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.[Abbildung in dieser Leseprobe nicht enthalten]bezeichnet die Wahrscheinlichkeit, dass die Zufallsvariable[Abbildung in dieser Leseprobe nicht enthalten]den Zustand[Abbildung in dieser Leseprobe nicht enthalten]annimmt. Eine vollständige gemeinsame Wahrscheinlichkeitsverteilung beschreibt die Wahrscheinlichkeitswerte für alle möglichen Belegungen Abbildung in dieser Leseprobe nicht enthalten. Hierbei wird[Abbildung in dieser Leseprobe nicht enthalten]oft vereinfacht durch[Abbildung in dieser Leseprobe nicht enthalten]dargestellt. Bayes’sche Netze bieten die Möglichkeit, eine vollständige gemeinsame Wahrscheinlich-keitsverteilung über einer Menge von Zufallsvariablen[Abbildung in dieser Leseprobe nicht enthalten]kompakt zu spezifizieren. Die bedingte Wahrscheinlichkeit [Abbildung in dieser Leseprobe nicht enthalten]ist definiert als[Abbildung in dieser Leseprobe nicht enthalten]falls Abbildung in dieser Leseprobe nicht enthalten. Die Zufallsvariable[Abbildung in dieser Leseprobe nicht enthalten]ist (stochastisch) unabhängig von[Abbildung in dieser Leseprobe nicht enthalten]genau dann, wenn Abbildung in dieser Leseprobe nicht enthalten.[Abbildung in dieser Leseprobe nicht enthalten]und[Abbildung in dieser Leseprobe nicht enthalten]heißen bedingt unabhängig gegeben Abbildung in dieser Leseprobe nicht enthalten, wenn Abbildung in dieser Leseprobe nicht enthalten.

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:

Abbildung in dieser Leseprobe nicht enthalten

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.

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 Speicherbedarf von[Abbildung in dieser Leseprobe nicht enthalten]vor, wobei[Abbildung in dieser Leseprobe nicht enthalten]der größten Kardinalität der vorkommenden Wertebereiche und[Abbildung in dieser Leseprobe nicht enthalten]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
- zu jeder Zufallsvariablen[Abbildung in dieser Leseprobe nicht enthalten]existiert eine assoziierte Tabelle bedingter Wahrscheinlichkeiten (conditional probability table, CPT) Abbildung in dieser Leseprobe nicht enthalten, wobei[Abbildung in dieser Leseprobe nicht enthalten]die Menge der Eltern von[Abbildung in dieser Leseprobe nicht enthalten]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 [Abbildung in dieser Leseprobe nicht enthalten ]relevanten Zufallsvariablen.
2. FOR [Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten.

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[Abbildung in dieser Leseprobe nicht enthalten](Dies ist lediglich eine alternative Formulierung der bedingten Wahrscheinlichkeit.). Durch wiederholte Anwendung der Produktregel kann die Kettenregel hergeleitet werden:

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten.

Semantisch betrachtet sagt diese Gleichung nichts anderes aus, als dass jeder beliebige Eintrag der gemeinsamen Wahrscheinlichkeitsverteilung als ein Produkt von entsprechend belegten lokalen bedingten Wahrscheinlich-keitsverteilungen 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.

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 in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3.2: Spezifikation der Netzstruktur

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.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.3.1: P(FamilieAusserHaus)

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.3.2: P(Magenprobleme)

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.3.3: P(AussenlichtAn|FamilieAusserHaus)

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.3.4: P(HundImGarten|FamilieAusserHaus, Magenprobleme)

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.3.5: P(Hundegebell|HundImGarten)

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 Beobach-tungen).

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 es ist, dass die Familie außer Haus ist (FamilieAusserHaus=true). Der konkrete Wahrscheinlichkeitswert P(FamilieAusserHaus=true|AssenlichtAn=true, Hundegebell=false) (in diesem Fall etwa 0.500551727589584) kann mittels Inferenzmechanismen berechnet werden, was zum nächsten Kapitel überleitet.

2.4 Inferenz in Bayes’schen Netzen

Bei der Durchführung von Inferenz bei gegebener vollständiger gemeinsamer Wahrscheinlichkeitsverteilung der Zufallsvariablen[Abbildung in dieser Leseprobe nicht enthalten]hat man allgemein folgende Ausgangssituation:

Man hat eine Menge von Abfrage-Variablen[Abbildung in dieser Leseprobe nicht enthalten]und eine hierzu disjunkte Menge von Evidenz-Variablen Abbildung in dieser Leseprobe nicht enthalten. Die Menge der verbleibenden verborgenen (hidden) Variablen sei Abbildung in dieser Leseprobe nicht enthalten.

Typischerweise ist man interessiert an der a posteriori gemeinsamen Verteilung der Abfrage-Variablen[Abbildung in dieser Leseprobe nicht enthalten]bei beobachteten Belegungen[Abbildung in dieser Leseprobe nicht enthalten]der Evidenz-Variablen Abbildung in dieser Leseprobe nicht enthalten, also Abbildung in dieser Leseprobe nicht enthalten. Nach der Definition der bedingten Wahrscheinlichkeit gilt:

Abbildung in dieser Leseprobe nicht enthalten.

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

Abbildung in dieser Leseprobe nicht enthalten.

([Abbildung in dieser Leseprobe nicht enthalten] ist hier eine Normalisierungskonstante, die für die reine Abwägung zwischen den verschiedenen Möglichkeiten nicht relevant ist. Die einzelnen Summanden werden in diesem Zusammenhang Randwahr-scheinlichkeiten genannt .) Diese Aufsummierung von Randwahrscheinlich-keiten 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:

Abbildung in dieser Leseprobe nicht enthalten

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[Abbildung in dieser Leseprobe nicht enthalten]beantwortet werden. Insofern geht diese wichtige Eigenschaft von 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[Abbildung in dieser Leseprobe nicht enthalten]über alle Ausprägungen der verborgenen Variablen[Abbildung in dieser Leseprobe nicht enthalten]aufsummiert werden muss und dies können je nach Kardinalität von[Abbildung in dieser Leseprobe nicht enthalten]exponentiell (in der Anzahl der Variablen) viele sein.

Kapitel 3 Konstruktion Bayes’scher Netze

Eine Voraussetzung in den vorangegangen Kapiteln war immer, dass die vollständige gemeinsame Wahrscheinlichkeitsverteilung bereits gegeben war. Woher aber kommen diese Wahrscheinlichkeiten?

Im einführenden Beispiel in Kapitel 2.3 wurden die benötigten Wahrscheinlichkeiten relativ willkürlich festgelegt. Allgemein existieren zwei grundlegend verschiedene Ansätze: Auf der einen Seite stehen die „ Frequentisten “, die der Auffassung sind, dass die Wahrscheinlichkeiten nur aus Experimenten bestimmt werden dürfen, auf der anderen Seite stehen die „ Subjektivisten “ (so genannte „ Bayesianer “), die den Standpunkt vertreten, dass die Wahrscheinlichkeiten die (subjektiven) Überzeugungen eines Agenten charakterisieren und somit nicht notwendigerweise die Verhältnisse in der realen Welt widerspiegeln müssen. Die Grenzen zwischen diesen beiden gegensätzlichen Auffassungen sind fließend. Beispielsweise könnte man bei der Bestimmung der Wahrscheinlichkeit, dass die Sonne morgen noch existiert, folgendermaßen argumentieren [Hum46]:

- Die Wahrscheinlichkeit ist undefiniert, da es noch kein Experiment gegeben hat, das die Existenz der Sonne morgen (also an dem konkreten Tag) überprüft.
- Die Wahrscheinlichkeit ist 1, da bei allen Experimenten in der Vergangenheit (Existiert die Sonne heute?) die Sonne existierte.
- Die Wahrscheinlichkeit ist Abbildung in dieser Leseprobe nicht enthalten, wobei[Abbildung in dieser Leseprobe nicht enthalten]der Anteil der Sterne im Universum ist, die pro Tag explodieren.
- Die Wahrscheinlichkeit ist Abbildung in dieser Leseprobe nicht enthalten, wobei[Abbildung in dieser Leseprobe nicht enthalten]die Anzahl der Tage, die die Sonne bereits existierte, ist. (nach Laplace)
- Die Wahrscheinlichkeit kann abgeschätzt werden von Typ, Alter, Größe und Temperatur der Sonne, obwohl man noch nie einen anderen Stern mit exakt solchen Eigenschaften gesehen hat.

Bei den ersten drei Ansätzen handelt es sich um Frequentistische, während die letzten beiden dem Bayes’schen Ansatz zuzuordnen sind. Interessant ist hierbei, dass auch bei den frequentistischen Ansätzen teilweise subjektive Annahmen getroffen werden müssen, was die fließenden Grenzen zwischen den beiden Extremen verdeutlicht.

3.1 Der Bayes’sche Ansatz

Bei diesem nach seinem Erfinder Thomas Bayes (1702-1763) benannten Ansatz werden Wahrscheinlichkeiten als Maß für die Einschätzung (degree of belief) einer Person bezüglich des Eintreffens bestimmter Ereignisse (die durch die jeweiligen Zufallsvariablen modelliert werden) interpretiert. Hierdurch stellt eine Wahrscheinlichkeit keine objektive Eigenschaft mehr dar, welche durch physikalische Experimente ermittelt werden kann, sondern mutiert zu einer subjektiven Größe, die abhängig von der sie festsetzenden Person ist.

Dennoch wird gerade dieser Ansatz bevorzugt eingesetzt, da er den nicht zu unterschätzenden Vorteil bietet auch Ereignissen Wahrscheinlichkeiten zuordnen zu können, für die keine wiederholten Zufallsexperimente durchgeführt werden können.

In den meisten Fällen werden die Wahrscheinlichkeiten durch eine Expertengruppe (subjektiv) festgelegt, so zum Beispiel auch beim zuvor erwähnten Pathfinder System. Natürlich stellt sich bei größeren Bayes’schen Netzen direkt wieder das Problem, dass nicht nur exponentiell in der Anzahl der verwendeten Zufallsvariablen viele Wahrscheinlichkeiten im Speicher gehalten werden müssen, sondern diese zunächst einmal festgelegt werden müssen. Weiterhin ist es angesichts der immensen Anzahl benötigter Wahrscheinlichkeiten durchaus möglich, dass die Expertengruppe Schwierig-keiten bei der Festlegung bestimmter Einträge der vollständigen gemeinsamen Verteilung hat.

Die Lösung liegt in der kompakten Repräsentation der vollständigen gemeinsamen Verteilung mit Hilfe eines Bayes’schen Netzes. Statt jeden einzelnen Eintrag der vollständigen gemeinsamen Verteilung festzulegen, legt man nur die für die conditional probability tables benötigten Wahrscheinlichkeiten fest. Diese sind für gewöhnlich ohne größere Schwierigkeiten von Experten aufzustellen (schon alleine aufgrund der Tatsache, dass es zumeist erheblich weniger sind als im Falle der gemeinsamen Verteilung) und genügen wie zuvor gezeigt um jeden beliebigen Eintrag der vollständigen gemeinsamen Verteilung berechnen zu können.

Insofern werden zur Konstruktion eines Bayes’schen Netzes typischerweise die folgenden Phasen durchlaufen:

1. Spezifikation der Variablen: Zunächst werden die für die Domäne relevanten Zufallsvariablen von einer Expertengruppe festgelegt. Schon in diesem Schritt gilt es abzuwägen zwischen einer (zu) hohen Anzahl von Variablen, die im Extremfall die Inferenz im resultierenden Bayes’schen Netz unmöglich macht, und einer moderaten Anzahl von Variablen, die möglicherweise zu einem Bayes’schen Netz führt, mit dem bestimmte Zusammenhänge nicht ausreichend erklärt werden können.
2. Spezifikation der Graphstruktur: Geschieht durch das Einfügen bzw. Weglassen von gerichteten Kanten zwischen den in 1. aufgestellten Knoten. Typischerweise orientiert man sich hier an der kausalen Interpretation einer gerichteten Kante zwischen zwei Zufallsvariablen und fügt die entsprechende Kante dann und nur dann ein, wenn die Expertengruppe einen direkten kausalen Zusammenhang zwischen den zwei beteiligten Variablen sieht. Beim Einfügen der Kanten ist insbesondere darauf Acht zu geben, dass keine Zyklen entstehen.
3. Spezifikation der conditional probability tables: Die bedingten Wahrscheinlichkeiten der conditional probability tables, die sich aus der in 2. aufgebauten Struktur ergeben, werden von einer Expertengruppe festgesetzt. Diese Phase entscheidet oft darüber, ob das Bayes’sche Netz aufgestellt werden kann oder aufgrund unsicherer bzw. fehlender Einträge in den CPTs (mangels Expertenwissen) zumindest lokal überarbeitet werden muss.
4. Anwendung des Bayes’schen Netzes: Nach der im Anschluss an die drei Hauptkonstruktionsphasen folgenden Anwendung des Bayes-schen Netzes können die so gewonnen Erfahrungen eventuell zur Revision des konstruierten Netzes eingesetzt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1.1 verdeutlicht den Konstruktionsprozess graphisch.

Zum Zeitaufwand der einzelnen Phasen sei folgendes Beispiel erwähnt: Zur Aufstellung des Bayes’schen Netzes für das in der Einleitung erwähnte Pathfinder System wurden 8 Stunden benötigt, um die Variablen festzulegen, 35 Stunden um die Netztopologie aufzustellen und weitere 40 Stunden zum Festlegen der benötigten bedingten Wahrscheinlichkeiten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1.1: Konstruktionsprozess eines Bayes’schen Netzes

Obwohl derartige subjektive Festlegungen der Netzstruktur (Phase 2) und bedingten Wahrscheinlichkeiten (Phase 3) merkwürdig anmuten, haben Studien ergeben, dass Experten im Aufstellen dieser Dinge im Allgemeinen recht gut sind. In einer Studie [SFB89] wurden die Wahrscheinlichkeiten, die zur Aufstellung eines Bayes’schen Netzes von Ärzten festgelegt wurden mit den Wahrscheinlichkeiten verglichen, die auf Basis einer in der Praxis akquirierten Case-Datenbank berechnet wurden. Das Ergebnis: Die Expertengruppe war sehr nah an den experimentell bestimmten Wahrscheinlichkeiten dran, es fiel jedoch auf, dass die Ärzte typischerweise zu schnell waren in Hinsicht darauf, dass bestimmte Dinge Wahrscheinlichkeit 0 haben.

Auf der anderen Seite kann man aber genügend andere Studien anführen, die belegen, dass selbst Experten der betrachteten Domäne Schwierigkeiten bei der Spezifikation der exakten bedingten Wahrscheinlichkeiten haben, insbesondere dann, wenn die Anzahl der Elternknoten groß ist (vergleiche hierzu [DGa00] und [KST82]).

Oft ist man aber auch in der Lage, auf Datenbanken mit gewissen Trainings-fällen zurückzugreifen. Diese meist experimentell gewonnenen Daten können dann bei der Konstruktion Bayes’scher Netze eingebracht werden, was zum Maschinellem Lernproblem für Bayes’sche Netze führt:

Definition 3.1.1 (Maschinelles Lernproblem für Bayes’sche Netze): Seien folgende Mengen und Maße gegeben:

1. eine Menge von Zufallsvariablen Abbildung in dieser Leseprobe nicht enthalten
2. eine Menge von Trainingsfällen Abbildung in dieser Leseprobe nicht enthalten
3. ein Gütemaß Abbildung in dieser Leseprobe nicht enthalten

Ziel ist es nun, ein Bayes’sches Netz[Abbildung in dieser Leseprobe nicht enthalten](also eine Struktur[Abbildung in dieser Leseprobe nicht enthalten]und entsprechende conditional probability tables Abbildung in dieser Leseprobe nicht enthalten) zu finden, das die gegebenen Trainingsfälle[Abbildung in dieser Leseprobe nicht enthalten]in Bezug auf das Gütemaß[Abbildung in dieser Leseprobe nicht enthalten]optimal erklärt. Die einzelnen Trainingsfälle[Abbildung in dieser Leseprobe nicht enthalten]haben hierbei die Form Abbildung in dieser Leseprobe nicht enthalten, wobei Abbildung in dieser Leseprobe nicht enthalten, können also durchaus auch unvollständig sein.

Der Bayes’sche Ansatz setzt auf den folgenden Satz von Bayes auf:

Satz 3.1.1 (Satz von Bayes): Abbildung in dieser Leseprobe nicht enthalten.

Dieser Zusammenhang folgt direkt aus der in Kapitel 2.2 definierten Produktregel und einem Symmetrieargument:

Abbildung in dieser Leseprobe nicht enthalten. Division durch Abbildung in dieser Leseprobe nicht enthalten liefert den Satz.

Der Satz von Bayes kommt insbesondere dann zum Einsatz, wenn man diagnostische Wahrscheinlichkeiten (Wahrscheinlichkeiten der Form Abbildung in dieser Leseprobe nicht enthalten) von kausalen Wahrscheinlichkeiten (Abbildung in dieser Leseprobe nicht enthalten) ableiten will, denn letztere sind oft einfacher zu bestimmen.

Beim maschinellen Lernen ist man interessiert an der a posteriori-Wahrscheinlichkeitsverteilung der Modelle Abbildung in dieser Leseprobe nicht enthalten, welche mit dem Satz von Bayes berechnet werden kann mit Hilfe der so genannten Likelihood der Trainingsdaten Abbildung in dieser Leseprobe nicht enthalten, der a priori-Wahrscheinlichkeitsverteilung Abbildung in dieser Leseprobe nicht enthalten, und der Wahrscheinlichkeit der Trainingsdaten Abbildung in dieser Leseprobe nicht enthalten. Die Likelihood gibt hierbei die Wahrscheinlichkeit des Auftretens der Daten[Abbildung in dieser Leseprobe nicht enthalten]bei gegebenem Modell[Abbildung in dieser Leseprobe nicht enthalten]an.

Man beachte, dass der subjektive Faktor hier in Form der a priori-Wahrscheinlichkeitsverteilung Abbildung in dieser Leseprobe nicht enthalten einfließt, die nichts anderes beschreibt als die subjektiven Wahrscheinlichkeiten für die möglichen Modelle, wenn keine empirischen Daten bekannt sind.

Da man typischerweise nur das beste Modell bestimmen möchte, und nicht eine ganze Wahrscheinlichkeitsverteilung aller Modelle benötigt, ergibt sich:

Abbildung in dieser Leseprobe nicht enthalten.

Aufgrund der Tatsache, dass es sich bei der (a priori-) Wahrscheinlichkeit der Trainingsdaten[Abbildung in dieser Leseprobe nicht enthalten]bezüglich der Bestimmung eines optimalen Modells[Abbildung in dieser Leseprobe nicht enthalten]lediglich um eine Konstante handelt, kann man zur reinen Abwägung vereinfachen zu:

Abbildung in dieser Leseprobe nicht enthalten.

Diese Approximation ist in der Literatur (vergleiche [Wit02]) als Maximum-a-posteriori-Lernen (MAP -Lernen) bekannt.

3.2 Der frequentistische Ansatz

Im Gegensatz zum Bayes’schen Ansatz werden die Wahrscheinlichkeiten hier als physikalische Eigenschaft der betrachteten Domäne angesehen und können somit im Prinzip mit Hilfe von beliebig oft wiederholbaren aber voneinander unabhängigen Zufallsexperimenten bestimmt werden. Es werden also an keiner Stelle subjektive Annahmen über bestimmte Wahrscheinlichkeiten getroffen. Daher findet man in diesem Kontext auch oft den Begriff der „ objektiven Wahrscheinlichkeit “ in der Literatur [Wit02].

Typischerweise hat man eine Datenbank mit experimentell bestimmten Trainingsdaten vorliegen und hat das gleiche maschinelle Lernproblem wie zuvor in Definition 3.1.1 erläutert. Im Gegensatz zum Bayes’schen Ansatz wird es jedoch vermieden, subjektive Wahrscheinlichkeiten in das Modell einzubringen. Infolgedessen geht es bei diesem Ansatz um die Maximierung der Likelihood (daher auch Maximum-Likelihood-Methode) der gegebenen Trainingsdaten[Abbildung in dieser Leseprobe nicht enthalten]bei gegebenen Modell Abbildung in dieser Leseprobe nicht enthalten. Die Likelihood aller Trainingsdaten Abbildung in dieser Leseprobe nicht enthalten wird hierbei als Produkt der Likelihoods einzelner Trainingsfälle berechnet:

Abbildung in dieser Leseprobe nicht enthalten.

Ein optimales Modell kann dann beschrieben werden als Element der Menge der Modelle Abbildung in dieser Leseprobe nicht enthalten, welches unter allen möglichen Modellen den Ausdruck Abbildung in dieser Leseprobe nicht enthalten maximiert:

Abbildung in dieser Leseprobe nicht enthalten.

Oft geht man aus technischen Gründen zur so genannten Log-Likelihood über und maximiert diese:

Abbildung in dieser Leseprobe nicht enthalten.

Bei dem frequentistischen Ansatz fließt also an keiner Stelle ein subjektiv festgelegter Faktor wie im Bayes’schen Ansatz ein. Vielmehr wird im Lernprozess das Modell ermittelt, welches auf Basis der gegebenen Trainingsdaten die größte Wahrscheinlichkeit besitzt diese erzeugt zu haben.

Abschließend sei erwähnt, dass das Maximum-a-posteriori-Lernen und die Maximum-Likelihood-Methode mit zunehmender Anzahl von Trainingsfällen gegeneinander konvergieren, was letztendlich zurückzuführen ist auf den mit steigender Anzahl Trainingsfälle abnehmenden Einfluss des subjektiven Faktors beim MAP-Lernen.

Kapitel 4 Maschinelles Lernen Bayes’scher Netze

In vielen Fällen ist man in der Lage auf Datenbanken zurückzugreifen, mit deren Hilfe dann schließlich ein Bayes’sches Netz nach den im vorangegangen Kapitel vorgestellten Ansätzen aufgestellt werden kann. Abbildung 4.1 verdeutlicht die Transformation einer so genannten Case-Datenbank in ein Bayes’sches Netz.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.1: Lernen Bayes’scher Netze anhand von Datenbanken

Dieses Gebiet fällt in der Literatur (vergleiche [BKr02], [Bor00] und [Ste03]) unter den Begriff „Maschinelles Lernen Bayes’scher Netze“ (anhand einer gegebenen Datenbank) und führt zum zentralen Thema der vorliegenden Arbeit.

Der Konstruktionsprozess eines Bayes’schen Netzes verläuft ähnlich wie in Abbildung 3.1.1 dargestellt, jedoch werden an zwei Stellen maschinelle Lernverfahren eingesetzt, nämlich bei der Festlegung der Netzstruktur (Phase 2) und der Spezifikation der bedingten Wahrscheinlichkeiten (Phase 3).

4.1 Lernsituationen

Nach Definition 2.2.1 besteht ein Baye’sches Netz aus zwei Komponenten, zum einen aus der Graphtopologie (Netzstruktur) und zum anderen aus den Parametern der jeweiligen durch die Netzstruktur induzierten conditional probability tables. Es ist möglich beide Komponenten anhand von gegebenen Daten zu lernen. Einige Autoren (siehe z. B. [BKr02]) unterscheiden in diesem Kontext auch zwischen dem Lernen der globalen Struktur und dem Lernen der lokalen Struktur. Die globale Struktur bezieht sich auf die Topologie des Netzes, während es beim Lernen der lokalen Struktur um das Festlegen der Parameter der CPTs geht. Hierbei ist zu differenzieren, ob die zur Verfügung stehenden Trainingsdaten vollständig oder unvollständig sind. Unvollständige Trainingsdaten liegen immer dann (aber nicht ausschließlich) vor, wenn es versteckte Variablen im Netz gibt. Beispielsweise ist es in der medizinischen Diagnose oft so, dass man gewisse Vorfaktoren und einige Symptome beobachten kann, jedoch ist die eigentliche Krankheit nicht beobachtbar. Natürlich könnte man diese Variable dann einfach weglassen, dagegen spricht jedoch, dass man auf der einen Seite häufig am Wert dieser versteckten Variablen interessiert ist und auf der anderen Seite diese versteckten Knoten typischerweise die Komplexität (gemessen an der Anzahl der benötigten bedingten Wahrscheinlichkeiten zur Spezifikation der CPTs) des Bayes’schen Netzes erheblich vermindern können.

Je nachdem, ob die Struktur des zu erlernenden Bayes’schen Netzes bereits bekannt bzw. von einer Expertengruppe spezifiziert ist oder nicht, lassen sich somit folgende Lernsituationen unterscheiden:

1. Bekannte Struktur und vollständige Trainingsdaten: Dies ist der einfachste aller Fälle, denn es brauchen lediglich mit Hilfe der vollständigen Trainingsdaten die durch die Struktur schon vorgegebenen conditional probability tables[Abbildung in dieser Leseprobe nicht enthalten]mit Parametern (den entsprechenden bedingten Wahrscheinlichkeiten) gefüllt zu werden. Sowohl für den frequentistischen als auch für den Bayes’schen Ansatz existieren analytische Lösungen dieses Problems, welches als Teilproblem auch in den anderen noch zu diskutierenden Lernsituationen auftritt.

2. Bekannte Struktur und unvollständige Trainingsdaten: Auch hier stellt sich das Problem des Lernens der bedingten Wahrscheinlichkeiten in den bereits (durch die spezifizierte Struktur) vorgegebenen CPTs Abbildung in dieser Leseprobe nicht enthalten, jedoch kommt erschwerend hinzu, dass zumindest einzelne Trainingsfälle[Abbildung in dieser Leseprobe nicht enthalten]der Trainingsdaten[Abbildung in dieser Leseprobe nicht enthalten]unvollständig sind. Das heißt es gibt für einige der Variablen des Bayes’schen Netzes keine Beobachtungen. Im Prinzip ist es möglich diese speziellen Trainingsfälle zu verwerfen und auf Basis der vollständigen Trainingsfälle nach 1. die CPTs aufzubauen, allerdings verwirft man so unter Umständen einen großen Anteil wertvoller Trainingsdaten, der nicht in die Modellbildung einfließt. Daher existieren verschiedene Verfahren, welche auch die unvollständigen Trainingsfälle mit einbeziehen. Eines der bekanntesten ist hier die so genannte Expectation-Maximization-Methode, vergleiche hierzu bei-spielsweise [DLR77].

3. Unbekannte Struktur und vollständige Trainingsdaten: Hier besteht das Hauptproblem in der Festlegung der Netzstruktur, bei fester Topologie lässt sich dann das Teilproblem der Spezifikation der Parameter der CPTs mit den in 1. angesprochenen analytischen Ansätzen lösen. Man unterscheidet zwischen drei verschiedenen Ansätzen. Bei dem in der Literatur am häufigsten angeführten - da vielversprechendsten - Ansatz legt man zunächst ein Qualitätsmaß für die Bewertung einer spezifizierten Netzstruktur fest und führt dann eine lokale Suche im Raum aller möglichen Netzstrukturen durch. Hierbei kommen verschiedenste Suchstrategien zum Einsatz, wobei sich eine erschöpfende Suche aufgrund der exponentiellen Anzahl verschiedener gerichteter azyklischer Graphen bei steigender Knotenzahl verbietet. Daher greift man oft auf heuristische Verfahren wie gradienten-basiertes Greedy Hill-climbing zurück, um zumindest ein lokales Optimum (bezüglich des Qualitätsmaßes) im Raum der Netzstrukturen zu finden. Simulated Annealing stellt eine alternative Möglichkeit dar, um auch das globale Optimum zu bestimmen, vorausgesetzt man fährt die Temperatur langsam genug herunter und kalkuliert genügend Rechenzeit ein.

4. Unbekannte Struktur und unvollständige Trainingsdaten: Dieser Fall stellt die komplexeste Lernsituation dar, denn es müssen nicht nur die Netzstruktur und die entsprechenden Parameter der CPTs bestimmt werden, sondern man hat zusätzlich noch das Problem, dass die Trainingsdaten unvollständig sind. Als approximative Lösung hat sich hier eine Erweiterung des bereits erwähnten Expectation Maximization Algorithmus, der sogenannte strukturelle EM-Algorithmus herauskristallisiert. Es existieren Varianten für den frequentistischen als auch für den Bayes’schen Ansatz, ihnen gemein ist die alternierende Verbesserung der Struktur und der Parameter der assoziierten conditional probability tables (siehe hierzu auch [Fri98]).

4.2 Strukturlernen Bayes’scher Netze

Da bei bekannter Struktur bereits analytische Verfahren zum Erlernen der bedingten Wahrscheinlichkeiten in den conditional probability tables existieren, liegt der Hauptfokus der vorliegenden Arbeit auf dem Lernen der Struktur eines Bayes’schen Netzes anhand einer Case-Datenbank.

Wie schon in der Einleitung skizziert, handelt es sich hierbei um ein hochdimensionales Suchproblem, für das momentan die verschiedensten Lösungsansätze studiert werden. Effiziente exakte Algorithmen darf man in diesem Bereich jedoch nicht erwarten, denn einige Teilprobleme im Bereich Strukturlernen Bayes’scher Netze sind bereits als NP-vollständig bekannt, so zum Beispiel das Finden von am höchsten bewerteten legalen Netzstrukturen mit Hilfe einer Scoring-Funktion (vergleiche hierzu [Chi96]).

Folgende drei Ansätze zum Strukturlernen werden unterschieden:

- Local Score Metriken: Das Strukturlernen eines Bayes’schen Netzes[Abbildung in dieser Leseprobe nicht enthalten]wird hier als Optimierungsproblem betrachtet, wobei ein so genanntes Qualitätsmaß [Abbildung in dieser Leseprobe nicht enthalten]bei gegebenen Trainingsdaten[Abbildung in dieser Leseprobe nicht enthalten]zu maximieren ist. Entscheidender Vorteil von Local Score Metriken ist, dass der Score der gesamten Netzstruktur aufgesplittet werden kann als Summe oder Produkt von einzelnen lokalen Scores für bestimmte Teilstrukturen des Bayes’schen Netzes. Dies ermöglicht den Einsatz von lokalen Suchstrategien wie Hill Climbing oder Simulated Annealing. Weiterhin können hierbei Scores von Teilstrukturen, welche beim Traversieren des Suchraums auftreten, in einem Cache zwischengespeichert und bei späteren Bewertungen von ähnlichen Netzstrukturen wieder verwendet werden. Dies führt zu erheblichen Rechenzeiteinsparungen, auf die im Falle von Global Score Metriken verzichtet werden muss.

- Global Score Metriken: Auch bei diesem Ansatz wird eine gegebene Netzstruktur mit Hilfe eines Qualitätsmaßes bewertet. Entscheidender Unterschied zu den Local Score Metriken ist die Nichtzerlegbarkeit des Gesamtscores in einzelne Summanden beziehungsweise Faktoren, das heißt lokale Teilstrukturen können nicht bewertet werden, und somit auch nicht für spätere schnellere Berechnungen von ähnlichen Netzstrukturen ausgenutzt werden. Stattdessen wird die Performance eines Bayes’schen Netzes gemessen an der Fähigkeit, nicht im Trainingsset vorkommende Datensätze vorherzusagen. Typischerweise teilt man die Menge der Trainingsdaten wiederholt in Trainingssets und Testsets auf und führt dann eine Cross Validation durch, um die Qualität eines gesamten Netzes an der Vorhersage-genauigkeit des auf Basis des Trainingssets gelernten Netzes zu schätzen. Die durchschnittliche Performance eines betrachteten Bayes’schen Netzes über einem Testset induziert hierbei eine Metrik für die Güte eines Netzes. Diese Metrik kann dann wie schon im Falle von Local Score Metriken ausgenutzt werden, um den Suchraum gestützt durch eine heuristische Suchstrategie wie Hill Climbing oder Simulated Annealing zu traversieren.

- Conditional Independence Tests: Dieser Ansatz basiert auf dem Entdecken von (bedingten) Unabhängigkeiten zwischen Variablen der zum Training gegebenen Case-Datenbank. Es wird angenommen, dass ein gerichteter azyklischer Graph existiert, der genau die (bedingten) Unabhängigkeiten in den Trainingsdaten widerspiegelt. Ziel ist es daher genau das Bayes’sche Netz zu finden, dessen Struktur die bedingten Unabhängigkeiten in der Verteilung codiert, welche die Trainingsdaten generiert hat. Durch diverse Tests zur Verifikation der (bedingten) Unabhängigkeit zwischen mehreren Variablen der betrachteten Domäne wird dann das (Nicht-)einfügen von Kanten zwischen diesen festgelegt. Natürlich kann man bei in der Praxis gewonnenen Trainingsdaten nicht davon ausgehen, dass sich exakte (bedingte) Unabhängigkeiten aufdecken lassen, vielmehr gibt man einen Parameter[Abbildung in dieser Leseprobe nicht enthalten]vor, der festlegt, wie unabhängig zwei Variablen voneinander sein müssen, damit keine Kante zwischen Ihnen eingefügt wird. Sind die Orte der Kanten gefunden, werden diese so orientiert, dass sie die aufgedeckten (bedingten) Unabhängigkeiten in den Trainingsdaten optimal repräsentieren.

Im weiteren Verlauf der vorliegenden Arbeit wird genauer auf Verfahren im Bereich Local Score Metriken eingegangen. Allen Methoden für das Strukturlernen Bayes’scher Netze in diesem Gebiet sind die folgenden Komponenten gemein:

- Ein Qualitätsmaß zur Bewertung der Qualität einer gegebenen Netzstruktur
- Eine Suchstrategie im Raum der möglichen Netzstrukturen

Diese beiden Komponenten werden in den folgenden Unterkapiteln detailliert betrachtet.

[...]