Algorithmus

Ein derartiger Plan beinhaltet die Vorgabe, nach welcher Struktur vorgegangen wird und wie ein Fehler zu suchen ist. Demzufolge dient der Algorithmus dazu, die Wahrscheinlichkeiten zu berechnen, durch das Netz zu propagieren und eine Entscheidung zu treffen bezüglich der weiteren Schritte und Vorgehensweise.

In einer Vorgängerarbeit [Klin 98] wurde dieser, von Siemens in der Abteilung ZT IK 4 in Anlehnung an [HeBr 95] und mit einer Benutzerschnittstelle über das Internet ausgestattete und implementierte, Algorithmus vorgestellt. Anwendung findet er in einem Modell für die Reparatur und Wartung der Siemens Telefonanlagen. Dabei wurde die Vorausplanung verallgemeinert und erfolgt in mehr als einem Schritt. Zusätzlich besitzt die Siemens-Variante noch eine Benutzerschnittstelle über das Internet.
Der Algorithmus wird in Bereichen eingesetzt, in welchen die Fehlerursachen auch direkt abgeprüft werden können. In einem Rechnernetz kann z.B. der Ausfall einer Komponente durch ping oder traceroute überprüft werden. Die Konfiguration einer Komponente, die sich in einem Rechnernetz befindet, kann durch weiteren Managementeinsatz ermittelt werden. Es können auch mehrere Variable für eine Komponente definiert werden, die einzelne Konfigurationsparameter beschreiben.
Wenn der Anlaß für die Diagnose ein Verbindungsproblem zwischen zwei Komponenten ist, gibt es die Möglichkeit, die Variablen noch aufzuspalten, in: z.B. Konfiguration des Startpunktes und Konfiguration des Zielpunktes. Andernfalls kann die Einbindung der Konfiguration der Rechnernetzekomponenten das Bayessche Netz ausufern lassen.
Zu jeder fragbaren Variable werden Kosten definiert, die anfallen, wenn der Benutzer diese Frage beantworten muß. Sie sollen den Aufwand für den Rest der Diagnose beschreiben, den es erfordert, diese Frage zu beantworten.
Der Fragealgorithmus stellt von allen möglichen Fragen diejenige, mit dem kleinsten Erwartungswert der Kosten bis zum Abschluß der Diagnose. Um diese zu ermitteln, wird für jeden Zustand jeder fragbaren Variable berechnet, welche Rest-Kosten (im Schnitt) später noch anfallen werden, wenn diese Variable erfragt wurde, und die dem Zustand entsprechende Antwort gegeben wurde. Die erwarteten Restkosten werden über die möglichen Antworten zu einer Frage gemittelt, gewichtet nach der Wahrscheinlichkeit, daß die entsprechende Antwort gegeben wird (durch Inferenz aus den bisher gegebenen Antworten).
Die Frage, bei der die Summe aus den eigenen Kosten und den zu erwartenden Restkosten minimal ist, wird gestellt.
Um die Restkosten zu ermitteln, kann man neu propagieren und dann wieder alle möglichen Fragen durchspielen, diese immer wiederholen, solange bis man die Ursache des Fehlers in der durchgespielten Variante gefunden hat, oder alles gefragt hat.
Da dies aufgrund der großen Anzahl von Schritten zu langsam ist, bricht man das Durchspielen nach wenigen Schritten ab (geringe Suchtiefe) und schätzt die Restkosten dadurch ab, daß man nur noch die Fehlerursachen in der Reihenfolge ihrer Wahrscheinlichkeit, unter Berücksichtigung der bisherigen Evidenz, also sicheren Annahmen, durchspielt.
Können die Ursachen, wie etwa Krankheiten in der Medizin, nicht erfragt werden, dann wird zu jeder Frage und jeder möglichen Antwort die verbleibende Entropie (Restkosten) auf den Ursachen abgeschätzt. Die Frage, die in Erwartung die Entropie am stärksten reduziert, wird gestellt.
Bei Ursachenknoten, die nicht abgefragt werden können, ändert sich am Aufbau des Bayesschen Netzes nichts. Über einen modifizierten Fragealgorithmus werden sehr hohe Kosten für die entsprechenden Ursachen-Knoten angesetzt. Damit wird diese Ursache erst dann gefragt, wenn sie eindeutig identifiziert ist, und die Kosten sich lohnen oder keine weitere Frage die Eindeutigkeit eines Ergebnisses verbessern kann.
Der Algorithmus sieht insgesamt sechs Schritte vor, um für eine Anzahl von Variablen die Wahrscheinlichkeiten zu berechnen, wenn bei gegebenem Zustand Aktionen und Tests durchgeführt bzw. Fragen beantwortet werden:

1.

In einem ersten Schritt wird ein Bayessches Netz konstruiert. Jede Variable wird in der Weise gekennzeichnet, ob sie für einen durchzuführenden Test oder Frage verantwortlich ist oder nicht.

2.

Werden für jede Variable ein Abbildungsknoten 66#66 eingeführt, der die möglichen Abbildungen von den Elternknoten von x_i auf sich selbst repräsentiert. Wird festgestellt, daß 67#67 Ursachen der Variablen x_i sind, ist jede derartige Abbildungsvariable nicht für eine Aktion verantwortlich.

3.

Werden die wahrscheinlichen Abhängigkeiten aller unverantwortlicher Variablen, einschließlich der Abbildungsvariablen abgeschätzt.

4.

Jede verantwortliche Variable wird kopiert, ähnlich den Influenzdiagrammen in HUGIN. Die erste und zweite Instanz jeder Variable zeigt den Zustand vor und nach einer durchzuführenden Aktion.

5.

Für die zweite Instanz, das gespiegelte Netz, werden die gleichen Abhängigkeiten wie im originalen Netz hergestellt.

6.

Im letzten Schritt werden in dem Netz der zweiten Instanz die Knoten identifiziert, die von der durchgeführten Aktion direkt betroffen waren. Ihre Verbindung zu den Elternknoten wird getrennt und die Zustände dieser Knoten werden auf die Werte gesetzt, die die Aktion festgelegt hat.

Die so entwickelten Bayesschen Netze werden als Antwortnetze, in HUGIN z.B. als Inferenzdiagramme, bezeichnet. Dabei ist zu beachten, daß die Bayesschen Netze nicht nur Abhängigkeiten hinsichtlich einer Wahrscheinlichkeit aufzeigen, sondern auch kausale Wechselbeziehungen.

Das Problem in der Konstruktion derartiger Antwortnetze liegt in der Anzahl der Zustände eines jeden einzelnen Abbildungsknotens. Diese kann sehr groß werden und damit die Einschätzung der Wahrscheinlichkeiten unhandlich machen.