Der Rete Algorithmus

“Jeder Narr kann eine Regel aufstellen, und jeder Narr wird sich danach richten.”

Henry David Thoreau

Der Rete Algorithmus wurde 1979 von Charles Forgy entwickelt und dient zur Auswertung von Regelbedingungen. Mit ihm ist es möglich die Vorbedingungen große Regelmengen effizient zu berechnen. Verwendet wurde der Rete Algorithmus in der regelbasierten Programmiersprache OPS 5. Aber auch heute arbeiten viele regelbasierte Systeme mit dem Rete Algorithmus oder einen seinen vielen Derivaten.

Dieser Algorithmus verfolgt mich seit meiner Studienzeit. Wie ein entfernter Verwandter mit dem man früher einmal etwas unternommen hat, sich danach aber nie wieder Gelegenheiten für gemeinsame Unternehmungen ergeben haben. Das erste Mal lernte ich ihn als studentische Hilfskraft im Projekt “HYPERCON: Modulare Wissensbasen für Hypertonie-Konsultation” an der Universität Bielefeld. Dort wurde ein Expertensystem mit einem OPS 5 nahen Regelinterpreter (Inferenzmaschine) entwickelt. Danach folgte über die Jahre hin und wieder ein Projekte, dass regelbasierte Lösungen für Kunden attraktiv machen wollte.

Die Programmiersprache OPS 5 arbeitet auf einem Faktenspeicher, dem neue Fakten hinzugefügt oder aus dem bestehende Fakten gelöscht werden können. Außerdem existiert eine Menge von Regeln, die gegen den Faktenspeicher geprüft werden. Kann eine Regel angewendet werden, dann wird ihr Aktionsteil ausgeführt und dabei ggf. der Faktenspeicher manipuliert. Danach werden wieder die Regeln gegen den Faktenspeicher geprüft und andere Aktionen ausgeführt. Diese Arbeitsweise wird Match-Resolve-Act Cycle genannt. Mit Match ist der Vergleich der Regeln gegen den Faktenspeicher gemeint, Resolve sucht die Regel aus, die ausgeführt werden soll und Act ist die Ausführung des Aktionsteil dieser Regel.

Es wird dabei sofort klar, dass die Prüfung der Regeln gegen den Faktenspeicher der teuerste Teil des gesamten Algorithmus ist. Denn bei hunderten von Regeln und hunderten von Fakten gibt es Millionen von Kombinationen zu prüfen.

An dieser Stelle setzt der Rete Algorithmus an. Statt alle Regelbedingungen einzeln und in jedem Durchgang vollständig zu prüfen, wird ein Netz (lateinisch: rete) von Verarbeitungsknoten erzeugt. Genaugenommen ist es ein azyklischer Graph, den die Fakten durchwandern.

Rete Netzwerk

Um die Arbeitsweise des Algorithmus besser zu verstehen, schauen wir uns folgende fiktive Regel an.

(R Tachykardie
  (person ^name ?name
          ^puls >= 100
          ^alter >= 18)
  (dog    ^owner ?name)
  =>
  (make diagose name Tachykardie person ?name)
) 

Die Regel besagt, wenn wir eine erwachsene Person mit Hund im Faktenspeicher finden, deren Puls über 100 liegt, dann erstellen wir eine Diagnose Tachykardie.

Jedes neue Faktum wird in den Wurzelknoten eingefügt. Dieser leitet das Faktum an einen Alphaknoten weiter, der einen einzelnen Test auf dem Faktum durchführt. Wird dieser Test bestanden, dann wird das Faktum an den nächsten Alphaknoten weitergereicht. Häufig werden die ersten Alphaknoten nach dem Wurzelknoten besonders benannt, weil sie den Typ der Fakten prüfen. Der Typ eines Faktum kann beispielsweise Person, Hund oder Diagnose sein. In weiteren Alphaknoten werden dann beispielsweise der Puls und das Alter geprüft.

Alle Fakten, die das Netz von Alphaknoten durchlaufen haben, werden im Alphaspeicher am jeweiligen Ende registriert. Manche Prüfungen sind für verschiedene Regeln identisch, daher werden diese an den Anfang des Alphaknoten Netzes geschoben und haben mehr als einen nachfolgenden Alphaknoten.

Durch den Alphaspeicher reduziert sich die Prüfung von Fakten extrem, da schon einmal geprüfte Fakten nicht noch einmal geprüft werden müssen. Insbesondere all die Fakten, die es nicht in den Alphaspeicher geschafft haben, weil sie die dazwischenliegenden Tests nicht bestanden haben. Auch das Zusammenfassen von Prüfungen für verschiedene Regeln reduziert den Prüfungsaufwand.

Nach dem Alphaspeicher gelangen die Fakten in weitere Verarbeitung durch die Betaknoten . Die Betaknoten besitzen zwei Eingänge und verknüpfen Fakten. Dabei bedient sich der linke Eingang an einem Betaspeicher bereits verknüpfter Fakten und der rechte an einem Alphaspeicher von einzelnen Fakten. In dem fiktiven Beispiel werden Fakten vom Typ Person und Hund miteinander verknüpft. Dabei werden jedoch nicht alle Kombinationen miteinander verknüpft, sondern nur die, bei denen der Name der Person und der Name des Hundehalters identisch sind.

Diese Betaknoten können dabei nur Existenzbedingungen prüfen. Die Verknüpfungen entstehen immer durch Elemente, die im Alpha- oder Betaspeicher vorhanden sind. Soll geprüft werden, ob ein Element nicht existiert, dann bietet sich ein spezieller Betaknoten an, der für jeden Eintrag aus dem Betaspeicher zählt, wie viele Kombinationen es mit den Einträgen aus dem Alphaspeicher gibt. Nur Elemente bei denen der Zähler auf 0 steht, werden an den Folgeknoten weitergereicht.

Zwischen Alphaspeicher und Betaspeicher sind spezielle Betaknoten zu finden, die aus einem Eintrag im Alphaspeicher einen entsprechenden Eintrag im Betaspeicher erzeugt. Häufig findet man hier in Abbildungen Betaknoten mit einem virtuellen Betaspeicher als Eingabe.

Nach einem Alphaspeicher oder einem Betaknoten kann ein Terminalknoten folgen. Alle Alpha- und Betaspeicher Einträge, die in einen Terminalknoten gelangen sind gleichbedeutend mit einer anwendbaren Regel.

Nachdem neue Fakten in das Netz eingefügt wurden, kann aus den Terminalknoten die Menge aller anwendbaren Regeln herausgelesen werden. Eine dieser Regeln wird ausgewählt und dann ausgeführt. Dies kann solange durchgeführt werden, bis eine Regel den Match-Resolve-Act beendet oder keine anwendbaren Regeln mehr vorhanden sind.

Zwei interessante Fragen stellt sich hier ein Entwickler natürlich. Wie können Fakten aus dem Faktenspeicher gelöscht oder geändert werden.

Der klassische Rete Algorithmus arbeitet beim Löschen eines Faktums aus dem Speicher mit einer speziellen Lösch-Markierung. Dann wird dieses Faktum dem Wurzelknoten übergeben. Da das Faktum die gleichen Werte wie beim Einfügen besitzt, läuft es auf dem identischen Weg durch das Netz. Jedoch agieren einige Knoten nun anders, weil sie die Lösch-Markierung berücksichtigen. Der Alphaspeicher löschen das Faktum aus seinem internen Speicher und gibt es weiter an die Folgeknoten. Der Betaspeicher löscht alle Kombinationen, in dem dieses Faktum vorkommt und reicht die Kombinationen mit einer Lösch-Markierung an die Folgeknoten weiter. Als letztes löschen die Terminalknoten alle Einträge mit einer Lösch-Markierung und reduzieren damit die Menge der anwendbaren Regeln.

Eine Faktum kann geändert werden, indem das Faktum zuerst aus dem Faktenspeicher gelöscht, dann geändert und zum Schluss wieder in den Faktenspeicher eingefügt wird.

Damit ist die Arbeitsweise des Rete Algorithmus auch schon erklärt und ich warte gespannt, wann er ein weiteres Mal meinen Weg kreuzt.