2) Les connaissances et le principe du raisonnement à partir de cas

Si les bases du RàPC ont été tracées par Minsky (qui ne s'en doutait pas) et Schank, c'est à Janet Kolodner [Kolodner 83] que l'on doit d'avoir vraiment inventé le terme de Raisonnement à Partir de Cas et de l'avoir popularisé par un ouvrage pour un large public [Kolodner 93].
Du point de vue de l'exploitation du paradigme RàPC par les ingénieurs pour la résolution de problème, ce sont Agnar Aamodt et Enric Plazza qui ont fondé ce que l'on appelle le cycle de Raisonnement à Partir de Cas [Aamodt & Plazza 94].
Les années 80 ont été les années pionnières et les années 90 ont été les années .'une recherche très active dans la communauté scientifique internationale [http://www.ai-cbr.org] .

21) Qu'est-ce qu'un cas ?

Un cas est la description d'un épisode de résolution de problème. Il peut donc prendre des formes très diverses selon la nature de la tâche : diagnostic, planification, aide à la décision, conception, etc.

Il existe de nombreux travaux sur la représentation des cas, mais la représentation la plus communément reprise est la représentation structurée en liste de descripteurs (qui peuvent être des objets complexes).

Un cas est donc l'association d'un problème et de la solution de ce problème : cas=(pb,Sol(pb)). Un cas source est un cas dont on va s'inspirer pour résoudre un nouveau cas que l'on appelera un cas cible. Un cas source s'écrit : cas-source=(source,Sol(source)) et un cas cible s'écrit donc cas-cible=(cible,Sol(cible)).
Un cas, son problème et sa solution sont donc décrits par un ensemble de descripteurs. Un descripteur d est défini par une paire d=(a,v) où a est un attribut et v la valeur qui lui est associée dans ce cas. Conformément à ce vocabulaire, source et cible sont définis de la manière suivante :

source={d^s₁..d^s_n} où d^s_i est un descripteur du problème source.
Sol(source)={D^s₁..D^sm} où D^s_i est un descripteur de la solution source.
cible={d^c₁..d^c_n} où d^c_i est un descripteur du problème cible.
Sol(cible)={D^c₁..D^c_n} où D^c_i est un descripteur du problème cible.

EXEMPLE 1
Imaginons un cas de détermination de conditions de vente d'un appartement.

Partie problème
d^s₁ = Surface de l'appartement (un réel)
d^s₂ = Localisation de l'appartement (une structure de données qui peut être complexe)
d^s₃ = Etat de l'appartement (une liste de défauts par exemple)
Partie solution
D^c₁ = Prix de vente de l'appartement (un réel)
D^c₂ = Condition de vente (détail du plan financier par exemple)

EXEMPLE 2

Imaginons un cas de diagnostic de problème mécanique sur une voiture

Partie problème
d^s₁ = Symptomes sonores (une liste de symboles)
d^s₂ = Symptomes visuels (une liste de symboles)
d^s₃ = Modèle du véhicule (symbole)
d^s₄ = Annédu véhicule (date)
Partie solution
D^c₁ = Pièces mécaniques en cause (une liste de symboles)
D^c₂ = Défauts diagnostiqués sur les pièces
D^c₃ = Défauts diagnostiqués sur les pièces

22) Ontologie des attributs de descriptions

Pour permettre de comparer les cas les uns avec les autres, il faut pouvoir comparer leurs valeurs d'attributs de façon à établir à quels points ces valeurs sont proches. Chaque attribut doit donc être typé. C'est la connaissance du type qui permet de connaitre les opérations de comparaison licites et par là d'établir des similarités.
Une ontologie est un ensemble de termes reliés entre eux par des relations vérifiées (vraies en toutes circonstances). Les relations les plus classiques sont les relations d'héritage (sorte-de, est-un, a-pour-spécialité, a-pour-instance), les relations de composition (est-composé-de, composant-de). Les autres relations associant les termes n'ont pas de sémantique (règle permettant de dire ce qui est vrai si la relation est en place) implicite évidente.
En Raisonnement à Partir de Cas, il ne s'agit pas de décrire le monde (on ne peut probablement pas le faire), mais de décrire les relations qui sont vraies entre les termes utilisés pour les valeurs de descripteurs.

Ontologie a heritage multiple

Figure 1 : Exemple de représentation graphique d'une ontologie de termes descripteurs d'appartements. Noter l'héritage multiple : Villeurbanne est tout à la fois une "sorte-de" Agglomération et une "sorte-de" Agglomération du Rhône.

Ontologie de vehicules

Figure 2 : Exemple d'ontologie simple pour des descripteurs de véhicule (limitation à la relation "sorte-de"

Figure 3 : Exemple d'ontologie comportant des relations complexes entre termes. La sémantique doit être précisée par ailleurs.

Cette ontologie peut être partagée pour l'ensemble d'une base de cas à condition que les relations soient stables pour l'ensemble des cas. La notion de base de cas est donc importante car liée à une ontologie particulière.

23) Qu'est-ce qu'une base de cas ?

Une base de cas est une collection de cas de résolution du même problème. Si nous reprenons les exemples déjà présentés, nous aurons une base de cas résolus de vente d'appartements. Chaque cas est une description d'un épisode de résolution d'une vente et ses descripteurs obéissent aux relations décrites dans l'ontologie correspondante. Les lignes vertes correspondent aux descripteurs du problème et la ligne rose correspond au descripteur de la solution (dans ce cas, seul le prix de vente a été considéré).

Etiquette de l'attribut	Cas 1	Cas 2	Cas 3	Type de l'attribut
Pb_Surface	55	35	55	Réel
Pb_Département	Agglomération du Rhône	Agglomération du Rhône	Agglomération de l'Ain	Symbole (déduit)
Sol_Prix de vente	20000	45000	15000	Réel
Pb_Type d'appartement	F2	F2	F2	Sympole
Pb_Ville	Lyon	Lyon	Bourg en Bresse	Symbole

Table 1 : Exemple de cas rassemblés dans une base de cas.
Le département peut être facilement déduit de la connaissance du nom de la ville grâce à l'ontologie qui nous renseigne à ce sujet : Si Lyon est vrai Alors Agglomération du Rhône est vrai également (voir l'exemple illustré par la figure 1).

Même s'il est plus facile de constituer une base de cas qu'une base de règles, des soucis classiques de l'ingénierie des connaissances surviennent inévitablement. Ils seront précisés dans la troisième session de ce cours.

La plupart des applications industrielles du RàPC choisissent de décrire les cas comme des formulaires remplis. Les informations sont saisies quand un problème se pose et sont complétées et corrigées au fur et à mesure que le problème est résolu. Dans l'exemple des appartements, il est clair qu'il n'est pas très difficile d'obtenir des cas de vente pour peu que l'on soit une agence de vente immobilière !.

Les bases de cas peuvent contenir quelques dizaines de cas jusqu'à plusieurs dizaines de milliers. Lorsqu'il y a relativement peu de cas, il est important de posséder des connaissances relativement importantes sur le domaine. Dans le cas des bases de cas très importantes, des traitements d'apprentissage automatique peuvent être tentés si l'on sait que les cas sont réellement comparables les uns avec les autres. Dans la plupart des situations, il est utile d'associer les techniques de classification automatique et le RàPC pour des raisons de performance par exemple. La classification automatique réalise une recherche grossière de solution et le RàPC, sur un espace de solutions plus petit, procède à l'adaptation du cas source le plus susceptible de faciliter la résolution du problème cible.

A la base de cas est attachée une "métrique" permettant de projeter les cas sur l'(hyper)plan des solutions. En effet, des cas proches sont des cas qui ont des solutions proches (voir figure 4).

Base de cas projetée sur l'hyperplan des solutions

Base de cas projetée sur l'hyperplan des solutions

Figure 4 : Cas d'une base de cas projetés sur le plan des solutions. Les cas proches sont ceux qui ont des solutions proches.

24) Quel est le principe de résolution : choix d'un cas source dans la base de cas ?

Dans une base de cas assez grande, il y a peu de chances que l'on soit capable d'adapter n'importe quelle solution pour un nouveau problème car ceci signifierait que l'on saurait quasiment résoudre le problème à partir de zéro et qu'en conséquence, on n'aurait pas besoin de cas !

Il existe donc un seuil de similarité au-delà duquel on ne sait plus adapter une solution pour une autre et de plus la méthode d'adaptation peut elle-même changer selon la "zone" de solution dans laquelle on se situe. Par exemple, on n'adaptera pas de la même façon le prix d'appartements quasi neufs que le prix d'appartements anciens surtout s'ils ne sont pas du tout dans les mêmes quartiers. La figure 5 présente de telles classes de solutions avec les cas de différentes couleurs représentant les solutions s'adaptant selon les mêmes règles et les enveloppes représentant les seuils de similarité à respecter pour utiliser ces méthodes.

Figure 5 : Différentes classes de solution correspondant à différentes méthodes d'adaptation avec leurs enveloppes de similarité respectives.

Le principe de résolution est illustré par la figure 6 : on mesure la similarité d'un nouveau cas (un cas cible) avec les cas de la base (les cas sources), on choisit la classe de solution la mieux représentée dans les plus proches voisins puis on choisit le cas le plus proche dans cette classe avant d'appliquer les règles d'adaptation.

La solution source la plus proche de la classe la plus représentée est choisie

La solution source la plus proche de la classe la plus représentée est choisie

Figure 6 : Le nouveau cas cible C est proche de 4 solutions "vertes" et d'une solution "orange". C'est la classe de solution de type "orange" qui est choisie. Le cas "vert" cerclé de "jaune" est le plus proche dans la classe de solution, il est donc choisi comme cas source pour l'adaptation.

Le raisonnement à partir de cas nécessite donc une base de cas résolus sur laquelle une métrique et une mesure de similarité ont été définies.