Direkt zum Inhalt

Tiefschürfen in Datenbanken: Unsicheres Wissen nutzen

Probabilistische Schlussfolgerungsnetze sind ein probates Mittel, unsicheres Wissen sauber und mathematisch fundiert zu verarbeiten. In neuerer Zeit wurden Verfahren entwickelt, um sie automatisch aus Beispieldaten zu erlernen.


Ein hoher Blutdruckwert allein sagt noch nicht viel, ein hoher Pulswert mag ganz banale Ursachen haben, die Gesichtsfarbe des Patienten ist nicht objektiv einzuschätzen, viele diagnostische Verfahren sind ungenau – aber der Arzt stellt regelmäßig aus der Gesamtheit der Befunde die richtige Diagnose.

Wie ein Experte aus derart unsicheren Daten Schlussfolgerungen zieht, ist nur sehr schwer in einem Algorithmus zu formalisieren. Dem Computer angemessen und Grundlage seines Funktionierens ist die klassische zweiwertige Logik. Die aber unterscheidet nur zwischen wahr und falsch und kann folglich mit nur wahrscheinlich wahren Aussagen und Regeln nicht umgehen. Es hilft daher wenig, dass für das Schlussfolgern mit klassischer Logik sehr leistungsfähige Programme zur Verfügung stehen.

Wie wäre ein solches Programm auf die Verarbeitung unsicheren und vagen Wissens zu erweitern? Zur Modellierung von vagem Wissen mit Begriffsunschärfen (wieviel ist ein hoher Pulswert?) haben sich Methoden der Fuzzy Logic (Spektrum der Wissenschaft 06/1995, S. 34) bewährt. Komplizierter wird es, wenn unsicheres Wissen in Form von Schlussregeln vorliegt: "Wenn der Rasen nass ist, dann hat es mit 90-prozentiger Sicherheit geregnet." Derartige Schlussfolgerungen sind stark vom Kontext abhängig: Der Sicherheitsfaktor 90 Prozent sinkt dramatisch, sowie ich erfahre, dass es einen Rasensprenger gibt.

Um derartige (und kompliziertere) Abhängigkeiten angemessen wiederzugeben, konstruiert man so genannte Schlussfolgerungsnetze. Das sind abstrakte Graphen, deren Knoten aus Variablen bestehen und deren Kanten den Abhängigkeiten zwischen diesen Variablen entsprechen.

So enthält ein Schlussfolgerungsnetz für medizinische Zwecke Knoten für Eigenschaften des Patienten wie Alter, Geschlecht und Gewicht, für Symptome wie Fieber, Blutdruck und Schmerzen sowie für verschiedene Krankheiten. Die Kanten geben dann explizit an, welche Krankheiten mit welcher Wahrscheinlichkeit welche Symptome hervorrufen, wodurch die oben angedeuteten Probleme vermieden werden.

Die bekanntesten Netztypen sind
– Markow-Netze, nach dem russischen Mathematiker Andrej Andrejewitsch Markow (1856-1922), der wesentliche Beiträge zur Beschreibung von Zufallsprozessen mithilfe der nach ihm benannten Markow-Ketten leistete, und
– Bayes-Netze, nach dem englischen Geistlichen Thomas Bayes (1702-1761), der in einem posthum veröffentlichten Aufsatz eine noch unvollständige Formulierung des nach ihm benannten Bayes'-schen Satzes gab.

Während in Markow-Netzen die Kanten ungerichtet sind, haben sie in Bayes-Netzen eine definierte Richtung (von Ursache nach Wirkung). Mit dem Bayes'schen Satz kann man einen Schluss von der Ursache auf die Wirkung in einen Schluss in umgekehrter Richtung umrechnen und somit Schlussfolgerungen auch gegen die Richtung einer Kante ziehen.

Als Beispiel betrachten wir einen Abstammungstest, der in deutlich komplexerer Form bei dänischen Rindern durchgeführt wird. Es soll nachgeprüft werden, ob ein Kalb tatsächlich die Eltern hat, die der Züchter angibt; denn da für ein Kalb je nach Stammbaum mehr oder weniger hohe Preise zu erzielen sind, besteht ein gewisser Anreiz für die Züchter, falsche Elterntiere anzugeben.

Vom Kalb und von den vom Züchter angegebenen Elterntieren werden Blutproben genommen und fotometrisch untersucht. Je Blutprobe werden vier Werte gemessen (die Messgröße heißt "Lysis", aber darauf kommt es hier nicht an), die indirekt Aufschluss über die genetische Ausstattung und damit über die Abstammungsbeziehung geben. Aus diesen zwölf Werten sind die Wahrscheinlichkeiten dafür abzuleiten, dass Vater und Mutter korrekt angegeben wurden.

Gesucht ist also die Funktion, die zu beliebigen zwölf Messwerten die beiden Wahrscheinlichkeiten angibt. Aber kein Experte könnte sie angeben und kein Computerprogramm sie aus Daten der Vergangenheit schätzen; zu unübersichtlich ist die Vielzahl der denkbaren Abhängigkeiten. Vielmehr müssen wir unser theoretisches Wissen in das Verfahren einbringen. Dazu sind zusätzliche Variable einzuführen, die man nicht beobachten kann, was zunächst das Problem noch zu verschärfen scheint; in Wirklichkeit wird es jedoch dadurch erst handhabbar, weil die gegenseitigen Abhängigkeiten und vor allem Unabhängigkeiten klar dargestellt werden können. Das wiederum erlaubt es uns, das große Problem in mehrere kleinere zu zerlegen.

Das Netz der Abhängigkeitsstruktur (Kasten rechts) zeigt keine direkten Verbindungen zwischen den zwölf Eingangsgrößen (Lysis A bis D für Stier, Kuh und Kalb) und den zwei Ausgangsgrößen ("Stier korrekt angegeben?" und "Kuh korrekt angegeben?"). Gleichwohl ist die von den Eingangsgrößen bereitgestellte Information über die Verbindungen des Netzes übertragbar, und zwar sowohl in Pfeilrichtung als auch in Gegenrichtung, bis sie bei den Ausgangsknoten anlangt. Die Übertragung geschieht mit speziellen Berechnungsvorschriften, die wesentlich auf dem Bayes'schen Satz beruhen. Dabei werden auch indirekte Abhängigkeiten zwischen Variablen korrekt berücksichtigt. Das Endergebnis gibt an, mit welcher Wahrscheinlichkeit Stier und Kuh korrekt angegeben wurden.

In diesem Beispiel gibt es zwischen zwei Knoten nur genau einen Pfad entlang der eingezeichneten Verbindungen. Es ist daher klar, auf welchem Wege die Informationen übertragen werden müssen. Dagegen kann zum Beispiel in einem Bayes-Netz, das der Überwachung von Patienten auf der Intensivstation dient, Information auf mehreren Wegen von einem Knoten zu einem anderen fließen. Manche Information bekommt dadurch fälschlich doppeltes Gewicht, was zu fehlerhaften Ergebnissen führen kann. Eine Lösung des Problems besteht darin, das Netz durch geschicktes Verschmelzen von Knoten in eine gleichwertige, aber einfach verbundene Struktur zu überführen. Dafür stehen effiziente Algorithmen zur Verfügung.

Bayes'sche Netze sind heutzutage in der Industrie bereits sehr weit verbreitet. Bei der Volkswagen AG werden sie zur Eigenschafts- und Teilebedarfsplanungeingesetzt, bei dem Telekommunikationsunternehmen AT&T dienen sie zur Betrugserkennung. Microsoft bietet zur Unterstützung bei der Diagnose von Druckerproblemen ein Programm an, das auf einem Bayes'schen Netz beruht.

Nicht immer ist jedoch das zu modellierende System so einfach, dass ein Experte ohne weiteres ein Bayes-Netz aufstellen könnte. Wenn man aber über Datensätze von Beispielfällen aus der Vergangenheit verfügt, kann man versuchen, den Computer aus diesen Daten ein Schlussfolgerungsnetz lernen zu lassen.

Die einfachere Form dieses Lernens ist das quantitative oder Parameterlernen: Die Struktur des Netzes ist bekannt, etwa durch einen menschlichen Experten festgelegt worden. Es fehlen nur noch einige Wahrscheinlichkeitswerte in den Tabellen; die sind durch Rückgriff auf die Daten zu schätzen. Dafür hält die klassische Statistik, insbesondere die Schätztheorie, ein großes Methodenarsenal bereit. Die einzige Schwierigkeit besteht darin, dass die in der Praxis vorliegenden Datensätze oft unvollständig sind. Doch steht mit dem Expectation-Maximization-Algorithmus, der als eine Erweiterung der in der Statistik wohlbekannten Maximum-Likelihood-Schätzung gelten kann, eine Kompensationsmöglichkeit zur Verfügung.

Interessanter ist das qualitative Lernen, bei dem man versucht, die Abhängigkeitsstruktur selbst aus den gegebenen Daten abzuleiten. Dazu gibt es im Wesentlichen drei Ansätze:
– Erstens: Man probiere verschiedene Netze durch, messe für jedes nach, wie gut es zu den Daten passt, und wähle dann das beste aus. Es gibt brauchbare Messmethoden für diese Passgenauigkeit, doch scheitert dieser Ansatz in der Praxis an der Vielzahl möglicher Netze.
– Zweitens: Man beginnt mit einem vollständig verbundenen Netz mit ungerich-teten Verbindungen: Jeder Knoten ist mit jedem anderen verbunden. Stellt man eine bedingte Unabhängigkeit zwischen zwei Variablen fest, so entfernt man die Verbindung zwischen den Variablen, und das so oft, bis sich eine möglichst einfache Abhängigkeitsstruktur ergibt. Anschließend versieht man die übrig gebliebenen Verbindungen, ebenfalls auf der Grundlage festgestellter bedingter Unabhängigkeiten, mit Pfeilen. Für den Test auf bedingte Unabhängigkeit kann man den Shannon'-schen Informationsgewinn zum Maßstab nehmen (nach Claude E. Shannon, 1916-2001) oder das in der Statistik wohl bekannte c2-(Chi-Quadrat-)Maß. Allerdings sind die erforderlichen Tests recht aufwendig und nur bei sehr vielen verfügbaren Datensätzen hinreichend verlässlich. Außerdem ist die Abgrenzung zwischen "bedingt unabhängig" und dem Gegenteil schwierig (natürlich zeigen sich in realen Daten nie exakte mathematische Unabhängigkeiten); so kommen gelegentlich fehlerhafte Abhängigkeitsstrukturen zu Stande.
– Der dritte Ansatz beruht auf der nahe liegenden Idee, dass direkte Abhängigkeiten im Allgemeinen stärker sind als indirekte. Indem man die Stärke der Abhängigkeit zwischen Variablen bestimmt – auch hier können wieder der Shannon'sche Informationsgewinn und das c2-Maß zum Einsatz kommen –, kann man die Verbindungen auswählen, die wahrscheinlich in einer Abhängigkeitsstruktur vorhanden sind. So versucht man die Vorgänger einer Variablen in der zu bestimmenden Abhängigkeitsstruktur zu finden, indem man schritt-weise die Variablen auswählt, von denen sie am stärksten abhängt.

Allerdings ist allein durch ein statistisches Maß nicht entscheidbar, ob man eine Variable zum Vorgänger oder Nachfolger einer anderen erklären sollte. Man muss daher die Pfeilrichtungen durch andere Kriterien festlegen. Außerdem findet das Verfahren nur dann mit Sicherheit das beste Netz, wenn dieses ein Baum ist, es also von jedem Knoten zu jedem anderen nur genau einen Pfad gibt (wie in dem oben betrachteten Abstammungstest).

In allen beschriebenen Ansätzen geht man davon aus, dass zumindest die Menge der Variablen bekannt ist. Bisher gibt es nur relativ wenige Ansätze, zu gegebenen Daten vermittelnde Variablen automatisch "hinzuzuerfinden", so wie wir im Beispiel der Abstammungsprüfung zusätzliche Variablen eingeführt haben.

Trotz der angedeuteten Probleme sind sowohl der zweite als auch der dritte Ansatz praxistauglich und inzwischen in recht ausgereiften Implementierungen verfügbar.

In einer Anwendung aus unserer eigenen Forschung geht es um die Fehlerdiagnose bei Mercedes-Fahrzeugen. Da die echten Ergebnisse vertraulich sind, geben wir ein fiktives Beispiel. Gesucht sind Abhängigkeiten zwischen den Ausstattungsmerkmalen eines Fahrzeugs (Motor- und Getriebebaureihe, Reifentyp, Sonderausstattungen und so weiter) und aufgetretenen Schäden. Durch Messen der Abhängigkeitsstärke zwischen entsprechenden Variablen kann so ein zweischichtiges Netz gelernt werden. Ein Beispiel für ein mögliches Lernergebnis zeigt das Bild links oben. Bei einem solchen Ergebnis wäre zu vermuten, dass Klimaanlage und elektrisches Schiebedach zusammen die Batterie zu stark belasten; durch eine stärkere Batterie, wenn beide Sonderausstattungen gewählt werden, wäre Abhilfe zu schaffen.

Allgemein sind Lernverfahren für Bayes'sche Netze immer dann einsetzbar, wenn es um die Analyse von Abhängigkeiten zwischen einer großen Anzahl von Variablen geht. Ziel einer solchen Analyse ist ein Schlussfolgerungssystem, das anschließend für Vorhersagen über den Wert bestimmter Variablen dient. Aber schon die Struktur des Netzes allein kann wertvolle Aufschlüsse geben, wie die beschriebene Anwendung bei Mercedes-Benz zeigt.

Literaturhinweise


Unsicheres und vages Wissen. Von Christian Borgelt, Heiko Timm und Rudolf Kruse in: Handbuch der Künstlichen Intelligenz. Von G. Görz et al. (Hg.). Oldenbourg, München 2000, S. 291

Graphical Models – Methods for Data Analysis and Mining. Von Christian Borgelt und Rudolf Kruse. J. Wiley & Sons, Chichester 2002.

Bayesian Networks and Decision Graphs. Von Finn V. Jensen. Springer, New York 2001.

Aus: Spektrum der Wissenschaft 11 / 2002, Seite 82
© Spektrum der Wissenschaft Verlagsgesellschaft mbH

Kennen Sie schon …

15/2021

Spektrum - Die Woche – 15/2021

Jetzt neu: @spektrum hat das Wichtigste der Woche für Sie gebündelt. Wieso manche Impfstoffe erst nach zwei Dosen so richtig wirken und warum alles immer komplizierter wird, lesen Sie in dieser Ausgabe (€).

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Infos