Grundlagen Statistik & Algorithmen, Teil 3 Speed für Mustererkennung mit dem Rete-Algorithmus

Geschäftsregeln halten zahlreiche Unternehmensprozesse am Laufen, deshalb können sie mitunter sehr umfangreich werden. Der Umfang macht ihre Ausführung zeitaufwendig, weshalb jede Methode, sie zu beschleunigen, willkommen ist. Der Rete-Algorithmus beschleunigte 1979 die damals bestehenden Systeme für die Verarbeitung von Business Rules um den Faktor 3.000. Er ist bis heute die Grundlage zahlreicher Expertensysteme, etwa in der Mustererkennung.

Anbieter zum Thema

Fujitsu Technology Solutions GmbH

Tableau von Salesforce

Fivetran Germany GmbH

Der Rete-Algorithmus (lateinisch rete „Netz“, „Netzwerk“) ist ein Algorithmus und Expertensystem zur Mustererkennung und zur Abbildung von Systemprozessen über Regeln. Ist eine bestimmte Menge von Bedingungen erfüllt, wird eine oder mehr Regeln ausgeführt. Aber es gibt natürlich Konflikte.

Der ganze Ablauf wird von einem Interpreter orchestriert, der die Nutzung von zwei Speicherbereichen steuert. Im ersten Speicherbereich, dem Production Memory, befindet sich eine Reihe von Regeln, die als „productions“ bezeichnet werden. Im Data Memory hingegen befindet sich eine Reihe von Fakten in einer Datenbank.

Zuerst schaut ein Mustervergleicher des Interpreters in beiden Speicherbereichen nach, welche Fakten zu den Bedingungen der Regeln passen, um sie zu erfüllen. Der Vergleicher erstellt eine Liste von erfüllten Regelbedingungen, schickt sie an den Konfliktlöser, der mithilfe eines Algorithmus untersucht, welche Regel am besten für die Lösung der Aufgabe geeignet ist.

Ist der Konflikt bereinigt, wird die ausgewählte Regel angestoßen und im geeigneten System (Arbeitsspeicher) ausgeführt. Die Regel führt Änderungen herbei, entweder im Production Memory oder im Data Memory. Dann beginnt der Zyklus von vorne. Das Zuweisen von Regeln zu Daten wird „Inferenz“ genannt, ein Vorgang, der in der Mustererkennung mittels Deep Learning heute (wieder) sehr aktuell ist. Die Inferenz muss beispielsweise beim Autonomen Fahren extrem schnell ablaufen, damit das Verhalten des KI-gestützten Systems keine Schäden verursacht.

Der Rete-Algorithmus vergleicht die Fakten und zieht Schlussfolgerungen. Liegen Fakt X und Bedingung Y im Data Memory vor, dann sollte vom Konfliktlöser eine bestimmte Regel aus dem Production Memory ausgewählt werden. Das Vergleichen im Konfliktlöser kann angesichts vieler Daten und Tausenden von möglichen Regeln sehr lange dauern.

Beispiel

Ein Detektiv kann als ein menschliches Expertensystem angesehen werden, denn er oder sie ist ein Experte für Fakten, Bedingungen und Vergleiche.

• 1. Wenn eine Person X etwas Illegales getan hat, so ist X ein Verbrecher.

• 2. Befinden sich Fingerabdrücke von X auf einem Gegenstand Y, denn hat X Objekt Y zu einem vergangenen Zeitpunkt berührt.

• 3. Falls Person X Person Y erschossen hat, dann hat Person X etwas Illegales getan.

• 4. Falls Person X (oder auch Y) tot ist, dann sollte Person X nicht zum Abendessen eingeladen werden.

• 5. Person X heißt Fred.

• 6. Person Y heißt Sam und ist tot.

• 7. Fred erschoss Sam und sollte nicht zum Abendessen eingeladen werden.

Die Konfliktmenge enthält wie oben formuliert zwei Regeln. Der Rete-Algorithmus führt sie zusammen und löst den Konflikt. Vor der Formulierung des Rete-Algorithmus prüften Systeme jede einzelne Regel daraufhin, ob sie zu den Fakten passte – in Iterationen. Durch das Indizieren der Daten und der Regelelemente in einem Index konnte der Prozess des Mustervergleichs zwar beschleunigt werden, aber erst Rete eliminiert die Iteration. Er speichert die Elemente der Konfliktmenge im Arbeitsspeicher und addiert oder löscht sie dort, je nachdem welche Datenelemente addiert oder gelöscht werden. Eine iterative Wiederholung wird überflüssig.

Grundlagen Statistik & Algorithmen, Teil 1

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Wenn beispielsweise die Regel auftaucht: „Wenn jemand eine Waffe auf mich abfeuert, ducke ich mich“, dann müssen mehrere Daten gegeben sein: Eine Waffe ist gefährlich und jemand feuert eine auf mich ab usw. Daher ist es klug und lebenserhaltend, der Kugel durch Ducken aus dem Wege zu gehen. Unter anderen Fakten und Bedingungen – etwa Geschosse, die ein automatisches Zielsuchsystem besitzen – sind andere Regeln für das Verhalten sinnvoller. Immer wenn sich etwas in dieser Konfliktmenge ändert, wird das zugehörige Muster (die Regel) geändert und alle vorherigen Muster gelöscht. Der Vorteil: Der Algorithmus muss nie im Data Memory nachschauen – und auch nicht alle potentiellen Regeln abklappern. Denn es gibt eine zweite Rete-Hälfte, die das obsolet macht.

Rete speichert die Bedingungen aller „production“-Regeln in einem Sortier-Netzwerk, das wie ein Baum aufgebaut ist. Der Algorithmus kompiliert das Netzwerk aus der Liste dieser Regeln und hält anschließend das Netzwerk auf dem laufenden, sobald Regeln zur Liste addiert oder daraus gelöscht werden.

Um zu verstehen, wie das funktioniert, schaut man sich ein paar Regeln im Expertensystem eines Süßwarenherstellers an. Zwei Production-Regeln in diesem System lauten:

• 1. Regel für ROTE__RUNDE__STÜCKE: Der Zweck besteht darin, ein. Süßwarenstück zu bestimmen. Ist das Süßwarenmuster rot und außerdem noch rund, stellt man die Hypothese auf, es sei ein runder roter Lutscher.

• 2. Regel für ROTE_ZYLINDRISCHE_STÜCKE: Gleichermaßen stellt man für ein rotes, zylindrisches Muster die Hypothese auf, es handle sich um eine Zuckerstange.

Das baumförmige Sortiernetzwerk des Algorithmus nutzt diese Redundanzen aus. Der Mustervergleicher kompiliert ein Netzwerk aus einzelnen Unterbedingungen. Er schaut jedes einzelne Element einer Regeln an und erstellt daraus eine Kette aus Gliedern, deren Attribut sich einzeln prüfen lässt. Dann schaut sich der Algorithmus Vergleiche zwischen Elementen an (er vergleicht beispielsweise die OBJEKT-Variable des ZIELs mit der NAME-Variable [„Lutscher“ etc.] des SÜSSWARENMUSTERs) und verknüpft Ketten mit neuen Gliedern. Abschließend werden Endglieder hinzugefügt, um anzuzeigen, dass alle Bedingungen für die Regel erfüllt worden sind. In einem Artikel im „Dr. Dobbs Magazine“ wird die Funktionsweise für ein OPS genauer erklärt.

Heutiger Einsatz

RETE bildet heutzutage die Grundlage für viele Regelsysteme wie etwa diverse Prolog-Interpreter oder sogenannte Business Rules Engines und hat sich für diese als De-facto-Standard etabliert. Heute wird Rete überall gelehrt, implementiert (etwa im SAP Business Rules Management und sogar im Roboter-Fußball verwendet.

Grundlagen Statistik & Algorithmen, Teil 2

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

Rete I war kostenlos, da das US-Verteidigungsministerium seine Entwicklung mit Steuergeldern finanzierte. Bislang gibt es zwei direkte Nachkömmlinge, nämlich Rete II und Rete III, die allerdings kostenpflichtig sind. Beide sind ungefähr 50-mal schneller als der ursprüngliche Ansatz. Rete III umfasst ein paar Erweiterungen, die seine Effizienz nochmals leicht erhöhen.

Er wurde vom US-amerikanischen Informatiker Charles Forgy im Rahmen seiner Doktorarbeit an der Carnegie Mellon University entwickelt, der ihn 1979 zum Titel führen sollte. Die Entwicklung war 1979 eng an die Plattform DEC XCON (DEC: Digital Equipment Corp.) angelehnt und fand ihre Implementierung zunächst in Betriebsunterstützungssystemen, speziell in OPS2 bzw. später in OPS5. Einsparungen in Millionenhöhe wurden benannt. Das implementierte Regelwerk hatte im Endausbau an die 10.000 Elemente.

Im Jahr 2010 entwickelte Forgy eine neue Generation des Rete-Algorithmus und nannte sie einfach Rete NT. In einem Benchmark-Test der Zeitschrift „InfoWorld“ wurde NT als 500-mal schneller als der ursprüngliche Algorithmus und zehnmal schneller als sein Vorgänger Rete II gemessen. NT ist jetzt an die Firma SparklingLogic lizenziert, in die Charles Forgy eintrat, und zwar als Inferenzmaschine des SMARTS-Produkts.

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

Das verbreitete Werkzeug Drools, das zusammen mit der Firma Jboss von IBM aufgekauft wurde, ist ein Beispiel für eine Business-Rule-Engine, die auf dem Rete-Algorithmus basierte. Seit Version 6.0 ist in Drools ein Nachfolge-Algorithmus namens PHREAK aktiv.

Als einziger Nachteil lässt sich nennen, dass die hohe Geschwindigkeit des Algorithmus zu Lasten des genutzten Speichers geht, doch das dürfte angesichts des heute zu Tiefpreisen verfügbaren Speichers kein Problem mehr sein. Und dass man seine Algorithmen stets möglichst effizient schreiben sollte, bedarf keiner gesonderten Erwähnung.

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 6

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

Grundlagen Statistik & Algorithmen, Teil 7

So deckt der Local Outlier Factor Anomalien auf

(ID:45349547)