Raisonnement par cas - Définition

Représentation des cas

La représentation des cas prend une place importante dans la réalisation d’un système RàPC. En effet cette représentation va déterminer l’efficacité et la rapidité de la recherche des cas dans la base. Il est donc nécessaire de choisir les informations à stocker dans chaque cas et de trouver sous quelle forme.

Structure d'un cas

Un cas est décrit par de nombreuses caractéristiques représentant différents types d’informations :

• La description du problème
• La solution et les étapes qui y ont mené
• Le résultat de l’évaluation
• L’explication des échecs

Tous les RàPC n’utilisent pas forcément chacun des types d’informations. La description du problème et la solution apportée sont des éléments indispensables. Certaines caractéristiques (les plus discriminantes) seront utilisées en tant qu’index lors de la recherche et l’ajout de cas. Les index doivent être suffisamment concret et abstrait à la fois pour qu’ils concernent un maximum de cas et qu’ils soient réutilisables dans les raisonnements futurs. Ils doivent aussi permettre de déduire rapidement les cas.

Généralement on considère les cas comme une liste de couples attribut-valeur. Chaque couple correspondant à une caractéristique. Les attributs sont typés, voici par exemple les types utilisés dans ReMind :

• Types classiques : texte, entier, réel, booléen, date.

• Type symbole : il permet d’énumérer une liste de symboles qui seront stockés dans un arbre. La racine de l’arbre contiendra le symbole le plus général et les feuilles les symboles les plus spécifiques.

• Type cas : il permet de référencer des cas qui sont des sous parties du cas considéré.

• Type formule : la valeur de cet attribut est le résultat du calcul d’une formule.

• Type liste : ce type est une liste d’objets utilisant les types précédents.

Organisation de la mémoire

Ensuite il faut construire un modèle d’organisation et d’indexation pour relier les cas entre eux. Ce modèle doit posséder certaines qualités. Tout d’abord il est nécessaire que l’ajout assure l’accessibilité aux anciens cas. La recherche de cas similaires doit conserver une complexité constante au fur et à mesure que la base de cas se remplit. Un système de RàPC n’étant intéressant qu’avec une base importante de cas, il faut évidemment envisager une solution permettant de retrouver rapidement les cas similaires. Généralement on utilise l’indexation pour cette raison.

Il existe de nombreuses façons d’ordonner les cas, nous allons étudier rapidement l’ensemble des modèles existants. Nous nous attarderons sur deux modèles en particulier :

• Le modèle à mémoire dynamique
• Le modèle à base de catégories

Modèle simple

Commençons tout d’abord par le modèle le plus simpliste : l’organisation linéaire. Cette organisation n’est pas utilisée pour gérer l’ensemble de la mémoire des cas. Cependant elle peut être implicitement combinée à d’autres modèles plus complexes au niveau de petits sous ensembles de cas.

Il est possible d’organiser la mémoire sous la forme d’un arbre de décision : chaque nœud correspond à une question sur l’un des index et les fils correspondent aux différentes réponses. Pour être le plus efficace possible l’arbre doit poser les questions dans le bon ordre et être le moins profond possible. Cet arbre doit être construit dynamiquement. La meilleure méthode pour le construire est d’utiliser le data mining.

Un autre modèle consiste à construire la mémoire sous la forme d’une hiérarchie de prototypes. Un prototype permet de décrire des conditions sur des caractéristiques des cas. Tous les cas vérifiant ces conditions sont associés à ce prototype. Les prototypes sont organisés dans une hiérarchie d’héritage. On peut ainsi spécifier des prototypes généraux desquels héritent des prototypes plus spécifiques. En combinant les arbres de décision à cette hiérarchie de prototypes, on obtient une structure intéressante. Les prototypes « terminaux » ne stockent alors plus leurs cas dans une liste mais dans un arbre de décision. La hiérarchie de prototype représente la connaissance a priori du système et les arbres de décision générés dynamiquement permettent une structure assez flexible.

Modèle à mémoire dynamique

Le modèle à mémoire dynamique a été introduit par Roger Schank et Janet Kolodner. Dans ce modèle, les cas sont stockés dans une structure hiérarchique appelée épisode généralisé. On parle aussi de MOP pour Memory Organisation Packets. Les différents cas ayant des propriétés similaires sont regroupés dans une structure plus générale, un épisode généralisé. Ils contiennent trois types objets :

• Les normes : Les caractéristiques communes à chacun des cas indexés sous l’épisode généralisé.
• Les index : Les éléments discriminant les cas contenus dans l’épisode généralisé. Un index possède deux champs : son nom et sa valeur. Il peut pointer vers un autre épisode ou simplement vers un cas.
• Les cas : La connaissance du système. On y accède donc par l’intermédiaire d’index.

Le schéma donne une idée du modèle à mémoire dynamique. Il possède une structure proche d’un arbre. On retrouve bien les trois types d’objets énoncés, à la différence près qu’une distinction est faite entre les index et les valeurs. On peut remarquer aussi qu’il est possible d’atteindre certains cas de différentes manières. Ce modèle est donc redondant.

La recherche des cas similaires s’effectue à partir du nœud racine. On va chercher l’épisode généralisé possédant le plus de caractéristiques en commun avec le problème courant. Ensuite on parcoure les index, qui représentent les caractéristiques absentes de la norme de l’épisode généralisé sur lequel on travaille. Le couple index-valeur sélectionné est celui qui est le plus similaire avec le problème. À partir de celui-ci, soit on arrive à un autre épisode généralisé, dans ce cas, on recommence le processus, soit on obtient un cas similaire au problème posé.

La procédure d’ajout de nouveaux cas fonctionne d’une manière proche à la recherche de cas similaires. En effet le parcourt du graphe est identique. Lorsque l’on a trouvé l’épisode généralisé ayant le plus de normes en commun avec le cas courant, on effectue l’ajout. Pour cela, il faut générer un couple index-valeur distinguant le nouveau cas aux autres fils de l’épisode généralisé. S’il existe déjà un cas possédant le même couple, on crée un nouvel épisode généralisé contenant ces deux cas.

On obtient donc un réseau discriminant à l’aide des index qui permettent de retrouver les cas. Les épisodes généralisés sont principalement des structures d’indexation. Les normes permettent de représenter une connaissance générale des cas sous-jacents alors que les couples index-valeur définissent les spécificités.

Cependant, ce processus d’indexation peut mener à une croissance exponentielle du nombre d’index par rapport au nombre de cas. On adjoint donc généralement certaines limites dans le choix des index même si cela entraîne une baisse de performances.

Modèle à base de catégories

Ce modèle est une alternative au modèle précédent. Ici, un cas est aussi appelé exemple. L’idée directrice est que la réalité devrait être définie de manière extensive par des cas. Les caractéristiques décrites généralement par un nom et une valeur, possèdent un niveau d’importance fonction de l’adhésion d’un cas à une catégorie.

Dans ce modèle, la base de cas est un réseau de catégories et de cas. Les index sont des liens qui peuvent être de trois sortes :

• De rappel : reliant une caractéristique à une catégorie ou un cas.
• D’exemple : reliant une catégorie aux cas auxquels elle est associée.
• De différence : reliant deux cas ne différant que d’un nombre restreint de caractéristiques.

Le schéma ci-dessous illustre les différents types de liens disponibles. Cependant il ne représente qu’une seule catégorie. Il faut donc ajouter que les exemples peuvent appartenir à plusieurs catégories.

La recherche des cas similaires consiste à retrouver la catégorie qui possède les caractéristiques les plus proches du nouveau problème. Lorsqu’elle est trouvée, on retourne les cas les plus prototypiques.