Le raisonnement à partir de cas (RàPC) (nommé en anglais case-based reasoning (CBR)) est un type de raisonnement qui copie le comportement humain qui consiste à faire naturellement appel à l'expérience pour résoudre les problèmes de la vie quotidienne, en se remémorant les situations semblables déjà rencontrées et en les comparant à la situation actuelle pour construire une nouvelle solution qui, à son tour, s’ajoutera à l'expérience.
Ce type de raisonnement résout les problèmes en retrouvant des cas analogues dans sa base de connaissances et en les adaptant au cas considéré. Cette technologie est apparue il y a une mais les travaux initiaux sur le sujet remontent cependant aux expériences de Schank et Abelson en 1977 à l'Université Yale. Elle reste pourtant encore assez méconnue par rapport à d’autres technologies appartenant au domaine des sciences cognitives comme le data mining. Elle diffère de cette dernière par son approche. En effet, ici, on n’utilise qu’indirectement les données pour retrouver les cas proches, à partir desquels on va générer une solution.
Étapes du processus
Un système RàPC dispose d’une base de cas. Chaque cas possède une description et une solution. Pour utiliser ces informations, un moteur est aussi présent. Celui-ci va retrouver les cas similaires au problème posé. Après analyse, le moteur fournit une solution adaptée qui doit être validée. Enfin le moteur ajoute le problème et sa solution dans la base de cas.
Ce schéma présente bien les principales étapes dans le processus d’un système de raisonnement par cas. De ces étapes se dégagent trois problèmes majeurs : La représentation des cas La recherche des cas La création de la fonction d’adaptation
Pour développer un système de raisonnement par cas digne de ce nom, il est donc nécessaire de trouver une solution efficace à chacun de ces problèmes. La révision et l’apprentissage sont deux autres problèmes qui découlent des trois premiers.
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 concrets et abstraits à 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 parcourt 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 parcours 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.
Recherche de cas similaire
Avant la recherche des cas similaires, il est nécessaire d’étudier le problème posé. Il faut identifier ses caractéristiques mais aussi son contexte si cela est possible. Si certaines informations sont manquantes, il est possible de négliger certaines caractéristiques ou d’interroger l’utilisateur. C’est au cours de cette étape, préambule à la recherche à proprement parler, que le système RàPC doit essayer de déterminer et corriger les données bruitées ou incohérentes. Pour cela, on peut faire appel à des outils de datacleaning. Il est aussi possible d’essayer de déduire des caractéristiques à partir d’autres à l’aide d’un modèle de connaissance. Toutes ces opérations requièrent généralement l’approbation de l’utilisateur avant de passer à l’étape suivante.
La recherche se décompose en deux phases : le filtrage et la sélection. Au cours de ces deux étapes, on fait appel à des index statiques et dynamiques. Il existe différentes façons de déterminer quelles caractéristiques seront choisies en tant qu’index. On peut utiliser :
Toutes les caractéristiques Certaines caractéristiques Les caractéristiques déterminantes dans le passé Les caractéristiques les plus discriminantes
Il est possible de choisir les index lors de la réalisation du système RàPC, on parle alors d’index statiques. Lorsqu’ils sont sélectionnés automatiquement ou par l’intermédiaire d’une interface homme-machine, ils sont qualifiés de dynamiques. Enfin certains RàPC donnent une importance aux différents index.
Filtrage