Algorithme de Rete

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme de Rete est un algorithme performant de filtrage par motif (« pattern matching ») intervenant dans l'implémentation de systèmes de règles de production. L'algorithme a été conçu par le Dr Charles L. Forgy de l'Université Carnegie-Mellon, tout d'abord publié comme une note de travail en 1974, puis plus tard élaboré dans sa thèse de doctorat en 1979 et dans une publication de 1982. Rete est devenu la base de nombreux systèmes experts tels que Clips, Jess, JBoss Rules, et Soar.

Une implémentation naïve d'un système expert pourrait vérifier chaque règle en la confrontant aux faits de la base de connaissance, éliminant les règles au fur et à mesure, puis passant à la règle suivante (et rebouclant à la première règle une fois terminé). Même pour des règles et des bases de connaissance de taille réduite, cette approche naïve est bien trop longue.

L'algorithme de Rete (habituellement prononcé en Europe, « re-té » d'après la prononciation latine, du latin « rete » pour réseau) fournit la base pour une exécution plus efficace d'un système expert. Un système expert basé sur Rete établit un réseau des nœuds, où chaque nœud (excepté la racine) correspond à un modèle se produisant dans le « côté gauche » d'une règle. Le chemin du nœud racine à un nœud externe (leaf node) définit un « côté gauche » complet de règle. Chaque nœud a une mémoire des faits qui satisfont ce modèle. Cette structure est essentiellement un trie généralisé.

Lorsque de nouveaux faits sont affirmés ou modifiés, ils se propagent le long du réseau, annotant les nœuds quand les faits correspondent au modèle. Quand un fait ou une combinaison des faits satisfait tous les modèles d'une règle donnée, un nœud externe (leaf node) est atteint et la règle correspondante est déclenchée.

L'algorithme de Rete est conçu pour sacrifier la mémoire au profit de la vitesse. Dans la plupart des cas, l'augmentation de la vitesse par rapport à une implémentation naïve est de plusieurs ordres de grandeur (parce que l'exécution de Rete est théoriquement indépendante du nombre de règles dans le système). Dans les systèmes experts très grands, cependant, l'algorithme de Rete original tend à rencontrer des problèmes de consommation de mémoire. On a depuis conçu d'autres algorithmes, basés sur Novel d'une part et Rete d'autre part, qui exigent moins de mémoire.

Description[modifier | modifier le code]

L'algorithme de Rete fournit la représentation logique globale d'une fonctionnalité d'un système de connaissance expert à partir de l'association d'une base des faits(« working memory ») avec une base de règles (« production memory ») dans un système de production de filtrage par motif (pattern matching system, une catégorie de moteur de règle). Une production se compose d'une ou plusieurs conditions et d'un ensemble d'actions qui peuvent être entreprises pour chaque ensemble complet de faits répondant aux conditions.

Des conditions testent les attributs des faits, y compris le type specifiers/identifiers. L'algorithme de Rete montre les caractéristiques principales suivantes :

  • il réduit ou élimine certains types de redondance par l'utilisation du partage de nœud ;
  • il stocke les correspondances partielles quand l'exécution se rejoint entre différents types de fait. Ceci, alternativement, permet à des systèmes de production d'éviter la réévaluation complète de tous les faits chaque fois que des changements sont effecués dans la « working memory » du système de production. Au lieu de cela, le système de production doit évaluer seulement les changements (deltas) dans la « working memory » ;
  • il permet une libération efficace des éléments de mémoire quand des faits sont retirés de la « working memory ».

L'algorithme de Rete est largement répandu pour mettre en application la fonctionnalité de matching les moteurs de « pattern matching » qui exploitent un cycle « match-resolve-act » (« correspondre-résoudre-agir ») pour assurer le chaînage avant et l'inférence.

Alpha Network[modifier | modifier le code]

Les graphes de Rete commencent par les noeuds alpha dont le rôle est d'exclure les faits sur des conditions simples. Par conséquent, les noeuds alpha ne portent que sur un fait (par opposition aux noeuds beta). A titre d'exemple, si une règle porte sur une instance d'une classe Personne, on aura un noeud alpha qui teste si l'instance d'un fait est de la classe Personne ou pas. Si tel est le cas, cette instance sera validée par le noeud.

Beta Network[modifier | modifier le code]

Contrairement aux noeuds alpha, les noeuds Beta portent sur plusieurs faits. On peut les considérer comme des tests sur des produits cartésiens de fait. Par exemple, une condition sur deux faits de type "l'attribut a du fait 1 égale l'attribut a du fait 2" donnera lieu à un noeud beta. La partie beta du graphe de Rete commence après les noeuds alpha. La raison est que les noeuds alpha ont déjà supprimés les faits non pertinents pour cette règle.

Résolution de conflits[modifier | modifier le code]