Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

| Autor / Redakteur: Michael Matzer / Nico Litzel

Prinzipbild des Rete-Algorithmus. Deutlich sind zwei Netzwerke (Alpha, Beta) zu erkennen und dass darin jeweils sehr viel Speicher benötigt wird. Dieser hohe Speicherbedarf ist einer der wenigen Nachteile des Rete-Algorithmus.
Prinzipbild des Rete-Algorithmus. Deutlich sind zwei Netzwerke (Alpha, Beta) zu erkennen und dass darin jeweils sehr viel Speicher benötigt wird. Dieser hohe Speicherbedarf ist einer der wenigen Nachteile des Rete-Algorithmus. (Bild: gemeinfrei / CC0)

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.

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.

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Grundlagen Statistik & Algorithmen, Teil 1

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

18.06.18 - Ob beim Design von künstlichen Neuronalen Netzwerken fürs Deep Learning, in der Logistik oder beim Layout von Leiterplatten – überall stößt man auf das mathematisch lösbare Problem des Handlungsreisenden: Wie lässt sich eine Tour mit mehreren Stationen auf dem kürzesten Weg und mit dem geringsten Aufwand bewältigen? lesen

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.

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

Grundlagen Statistik & Algorithmen, Teil 2

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

25.06.18 - Mithilfe des Satzes von Bayes lassen sich Parameter schätzen und Hypothesen induktiv testen. In einem Spamfilter können so wahrscheinliche Spam-Mails ermittelt werden. Und aus den Symptomen, die bei einem bekannten Test auftreten, lassen sich wahrscheinliche Krankheitsursachen aufspüren. Der Satz von Bayes, der bedingte Wahrscheinlichkeiten beschreibt, ist also ein nahezu universell nutzbares Werkzeug der Statistik. lesen

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.

Der Monte-Carlo-Algorithmus und -Simulationen

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

10.09.18 - Eine Reihe von Algorithmen dient der Suche von Lösungen, ohne vorher die Antwort zu kennen, und von Entscheidungen, die nach „wahrscheinlich richtig oder falsch“ beurteilt werden. Das ist sinnvoll für das Risiko-Management, aber auch für die Nutzung von Supercomputern. Ein solcher Algorithmus ist der Monte-Carlo-Algorithmus und die darauf basierenden Simulationen lesen

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.

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

19.11.18 - Der k-Means-Algorithmus ist ein Rechenverfahren, das sich für die Gruppierung von Objekten, die sogenannte Clusteranalyse, einsetzen lässt. Dank der effizienten Berechnung der Clusterzentren und dem geringen Speicherbedarf eignet sich der Algorithmus sehr gut für die Analyse großer Datenmengen, wie sie im Big-Data-Umfeld üblich sind, so etwa in der Bildverarbeitung und in der Kundensegmentierung. lesen

Kommentare werden geladen....

Kommentar zu diesem Artikel abgeben

Der Kommentar wird durch einen Redakteur geprüft und in Kürze freigeschaltet.

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45349547 / Analytics)