Algorithme de Rete
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 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, Drools, Ilog JRules, Soar...etc
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. D'autres algorithmes ont depuis été conçus, d'une part basés sur Rete ou d'autre part complètement nouveaux, qui exigent moins de mémoire.
Description
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 effectué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 des 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
Les graphes de Rete commencent par les nœuds alpha dont le rôle est d'exclure les faits sur des conditions simples. Par conséquent, les nœuds alpha ne portent que sur un fait (par opposition aux nœuds beta). À titre d'exemple, si une règle porte sur une instance d'une classe Personne, on aura un nœud 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 nœud.
Beta network
Contrairement aux nœuds alpha, les nœuds 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 » donne lieu à un nœud beta. La partie beta du graphe de Rete commence après les nœuds alpha. La raison est que les nœuds alpha ont déjà supprimés les faits non pertinents pour cette règle.