RàPC Session 3

3) Le cycle du raisonnement à partir de cas

31) Le carré d'analogie

Le RàPC est un raisonnement analogique qui satisfait globalement ce que l'on appelle le carré d'analogie tel qu'illustré dans la figure suivante.

Figure 3-1 Le carré d'analogie

La base de cas est composée de "cas source" qui sont structurés en deux parties : "problème source" et "solution source".

Le carré d'analogie se lit de la manière suivante : à partir des valeurs de descripteurs du problème cible et en utilisant la mesure de similarité alpha, un cas source est sélectionné. Les relations de dépendance Béta entre valeurs de descripteurs problème cible et valeur de descripteurs solution permettent de mettre en évidence les descripteurs solution qui doivent être adaptés car dépendant de descripteurs problèmes source différents des descripteurs problèmes cibles. En d'autres termes, si une valeur de descripteur source dépend d'une valeur de descripteur problème, une modification de la valeur du descripteur problème entraînera une modification "analogue" à la dépendance du descripteut solution correspondant. Cette connaissance est nécessaire pour l'adaptation.
En fonction de ces dépendances et des écarts alpha constatés à corriger, l'adaptation permet de proposer une solution cible candidate qui pourra être vérifiée par la vérification de sa conformité aux dépendances particulières qui pourraient exister entre problème et solution cible.

Ce carré d'analogie cache en réalité plusieurs phases dans le raisonnement à partir de cas qui sont particulièrement importantes à identifier dans le cadre de l'ingénierie des connaissances.

32) Les étapes du raisonnement à partir de cas

Ce sont Aamodt & Plaza qui ont proposé en 1994 un cycle de raisonnement qui a été repris par l'ensemble de la communauté comme une référence. Nous en présentons ici une version légèrement complétée sur la phase d'élaboration d'un cas qui se révèle être un aspect d'ingénierie de la connaissance important.

cycle des étapes du RAPC

Figure 3-2 Le cycle d'étapes du Raisonnement à Partir de Cas

321) Elaborer

L'élaboration d'un nouveau cas consiste à faciliter la description du problème pour permettre la recherche d'un cas dont la solution sera la plus facilement adaptable. L'adaptabilité d'un cas se mesure à "l'effort" d'adaptation qui sera nécessaire pour que la solution passée (du cas source) puisse servir de base à la solution courante (du cas cible).

La méthode générale consiste à compléter ou filtrer la description d'un problème en se fondant sur la connaissance du domaine pour inférer tout ce qu'il est possible à partir d'une description éventuellement incomplète, et pondérer (mettre des poids) les descripteurs en fonction des dépendances identifiées entre les descripteurs problème cible et les descripteurs de la solution recherchée.

C'est ainsi que l'on va utiliser l'ontologie du domaine pour compléter les descripteurs importants et d'une manière générale, l'on va considérer l'ensemble des règles définies sur le domaine.

Illustration sur la base de cas des véhicules d'occasion :

Soit le cas cible suivant :

Nom de l'attribut	Type de l'attribut	Exemple de valeur du de l'attribut
Etat Général	Symbole (déduit)	??
Kilométrage	Réel	198000
Age du véhicule	Réel	10
Marque	Symbole (déduit)	??
Modèle	Symbole	206
Type de véhicule	Symbole	Coupé
Liste de défauts constatés	Liste de Symboles	(Corrosion superficielle)
tPrix de vente (solution)	Réel	???

Table 3-1 Cas cible non élaboré

Seuls les descripteurs connus (par un formulaire par exemple) sont renseignés. L'état général, la marque du véhicule (et naturellement le prix puisqu'il s'agit de la solution) ne sont pas élaborés encore.
L'ontologie décrite ci-desssous (figure 3-3) permet de faire les déductions liées aux règles d'héritage. La marque est donc Peugeot puisque le modèle est 206.

Elaboration à partir de l'ontologie

Figure 3-3 Ontologie du domaine de la vente de véhicules d'occasion

C'est une déduction un peu plus complexe qui nous permet d'estimer l'état général du véhicule à partir de la liste des défauts constatés.

Dans le cas cible courant, la liste de défauts n'est pas vide, mais reste inférieure à 3, donc l'état est considéré comme Bon conformément à la règle qui formalise cette connaissance dans le système. La règle appliquée est illustrée par la figure 3-4.

Elaboration Etat Général à partir d'une règle

Elaboration Etat Général à partir d'une règle

Figure 3-4 Règle d'élaboration de l'état général d'un véhicule à partir de la connaissance de la liste des défauts décrits

Le cas élaboré est donc le cas cible initial complété grâce aux connaissances du domaine disponibles. Ces connaissances sont particulièrement centrées sur l'adaptabilité : il y a une forte dépendance entre la marque d'un véhicule et son prix d'occasion ; il y a une forte dépendance entre l'état d'un véhicule et son prix d'occasion. Il est donc important de disposer de ces informations pour retrouver un cas source susceptible d'être adaptable.
Le cas cible élaboré est maintenant le suivant (figure 3-2).

Nom de l'attribut	Type de l'attribut	Exemple de valeur du de l'attribut
Etat Général	Symbole (déduit)	Bon
Kilométrage	Réel	198000
Age du véhicule	Réel	10
Marque	Symbole (déduit)	Peugeot
Modèle	Symbole	205
Type de véhicule	Symbole	Coupé
Liste de défauts constatés	Liste de Symboles	(Corrosion superficielle)
Prix de vente (solution)	Réel	???

Table 3-2 Cas cible élaboré

322) Retrouver

L'étape de recherche de cas sources similaires est naturellement essentielle dans le cycle. Nous rappelons que le cas source qui sera choisi sera normalement le cas ayant la description de problème la plus proche possible de la description du problème cible dans la classe de solution la plus représentée (voir la session 2 de ce cours RàPC pour une illustration graphique de ce principe).

En pratique, il est nécessaire de définir une mesure de similarité qui tiendra compte de l'influence d'une variation d'une valeur de descripteur problème sur une variation de valeur d'un descripteur solution. Intuitivement, on comprend bien qu'il faurdra donner un "poids" important aux descripteurs problèmes qui ont beaucoup d'influence sur la solution et une valeur faible aux descripteurs ayant une faible influence sur la solution

Il existe de nombreuses mesures de similarités dans la littérature adaptées à la comparaison d'épisodes de résolution de problème tenant compte de spécificités des descriptions : mesures faisant intervenir le temps, l'espace, des structures complexes, des plans, des séries, etc... Il n'est pas question ici d'en faire le tour, mais il est important de se rappeler qu'il ne faut pas hésiter à étudier cette mesure qui fait partie intégrante de la connaissance nécessaire pour mettre en place un système fondé sur le RàPC.

Pour des raisons de simplicité, nous allons considérer une mesure de similarité la plus répandue fondée sur la distance d

distance euclidienne

la distance entre deux descriptions de problèmes est donc constituée de la somme pondérée des distances des attributs décrivant les problèmes. Ce sont les poids p_i qui portent la connaissance sur l'importance de l'influence du descripteur d_i sur la solution.

Nom de l'attribut	Type de l'attribut	Poids de l'influence de l'attribut sur la solution
Etat Général	Symbole (déduit)	20%
Kilométrage	Réel	35%
Age du véhicule	Réel	25%
Marque	Symbole (déduit)	5%
Modèle	Symbole	5%
Type de véhicule	Symbole	10%
Liste de défauts constatés	Liste de Symboles	Pas pris en compte
Prix de vente (solution)	Réel	???

Table 3-2 Poids des différents attributs = importance de l' influence relative de ces attributs sur la solution.
La phase de recherche consiste donc à utiliser ces poids dans la mesure de similarité pour choisir d'une part la classe de solution prédite pour ce cas et d'autre part quel est le cas source de cette classe de solution qui devrait être le plus facile à adapter.

L'algorithme le plus habituellement utilisé pour faire cette recherche est celui des K plus proches voisins.

Remarque importante : il est tout à fait habituel de considérer qu'il y a autant de classes de solutions que de solutions différentes dans la base de cas. Dans ce cas, K=1 et seul le seuil de similarité permet de considérer un cas comme éligible.

Cet algorithme est décrit ci-dessous :

Début
{Initialiser la valeur de T // T est le seuil (Threshold) de similarité minimum pour être considéré comme voisin de ce cas cible
// en toute théorie, il pourrait y avoir autant de seuils différents que de cas cibles
Initialiser la valeur de K // K représente le nombre de cas voisins nécessaire et suffisant pour qu'une classe de solution soit éligible comme candidate pour la solution cible
Initialiser liste_cas_voisins // la liste est vide au départ
Tant_que (il reste des cas à comparer)
{Comparer la description du cas cible avec la description du cas source suivant de la base de cas;
Si (la similarité cas_cible/cas_source > T) Alors (Insérer le cas source dans liste_cas_voisins);
Passer au cas suivant;
} Fin_Tant_que
Choisir la classe solution éligible la plus représentée dans liste_cas_voisin;
Si (aucune classe de solution éligible) Alors (conclure au manque d'expérience pour ce type de cas cible); FIN;
Choisir le cas source le plus similaire de la classe solution élue;
}
Fin

Plusieurs situations typiques sont illustrées par les figures suivantes (figures 3-5, 3-6 et 3-7). Le seuil S est illustrépar le rayon Rs de la boule autour de la description du problème cible.

scenario_kppv_jaune

Figure 3-5 Scénario de déroulement de l'algorithme KPPV sélectionnant le cas 1 (de classe solution "jaune") pour le cas cible C.
Seule la solution jaune était éligible (représentation > 3).

Scénario_kppv_jaune_rouge

Figure 3-6 Même scénario qu'en 3-5, mais avec un seuil plus bas (Rs plus grand) la solution "rouge" devient éligible. Elle n'est pas la plus représentée. Le cas 1 (jaune) est encore sélectionné.

scénario_kppv_pas_de_solution

Figure 3-7 Dans ce scénario, aucune solution n'est éligible. Aucune expérience ne peut être rationnellement remémorée. Ce cas cible devra être résolu par une autre méthode.

323) Adapter

L'adaptation termine 'l'inférence analogique" en calculant quelle pourrait être la solution au problème du cas cible inspirée de la solution du cas source le plus similaire.

La figure 3-8 rappelle qu'une zone d'appartenance à une classe de solution correspond à une zone de règles d'adaptation communes lorsqu'un cas source doit être adapté pour un cas cible considéré comme similaire en terme de solution potentielle.

zone d'adaptation

Figure 3-8 Les règles d'adaptation dépendent de la zone de regroupement des cas d'une même classe de solution. Ce regroupement est précisément réalisé sur la base des connaissances d'adaptation.

Les règles d'adaptation de la solution s'expriment en fonction des écarts relevés entre les descritpion des problèmes cibles et source.

Le schéma suivant (figure 3-9) illustre les connaissances et l'inférence analogique ainsi menée~:

Formules de dépendances et opérateurs d'adaptation

Formules de dépendances et opérateurs d'adaptation

Figure 3-9 Schéma général des connaissances et opérateurs d'adaptation

Dans le cas d'une variation simple, le calcul d'un descripteur solution cible à partir de descripteurs solution solution et selon l'influence des écarts sur les descripteurs problème correspond aux formules suivantes :

Formule d'adaptation

Cette formule signifie simplement qu'il faudra calculer un écart à appliquer au descripteur solution qui dépendra directement de l'influence d'un écart élémentaire entre les descripteurs cible et source correspondant sur la valeur du descripteur source, cet influence dépendant naturellement de l'importance de l'écart.

Bien entendu, un descripeur solution ne dépend pas en général d'un seul descripteur problème et le schéma plus général est alors le suivant :
Schéma d'adaptation avec influences multiples

Schéma d'adaptation avec influences multiples

Figure 3-10 Schéma général d'adaptation d'un cas source en fonction des influences pb/sol et des opérateurs d'adaptation associés

avec

Nous pouvons illustrer cette phase d'adaptation avec l'exemple des cas d'estimation du prix de vente de véhicules d'occasion.

Si nous retenons le vecteur de similarité illustré par une copie d'écran de l'outil REMIND (figure 3-11)

vecteur similarité pb voitures

Figure 3-11 Le descripteur solution "Prix de vente" est influencé par des écarts sur l'état général, le kilométrage et le modèle. Il y aura des rgèles différentes pour chaque marque de véhicule.

La règle d'adaptation du prix pourrait alors (naivement !) être la suivante :

Règle simplifiée d'adaptation du prix du véhicule

Règle simplifiée d'adaptation du prix du véhicule

Dans cette règle nous n'avons retenu que deux (2) influences de descripteurs problèmes sur des descripteurs solution : l'influence du kilométrage et l'influence de l'état du véhicule.
Chaque kilomètre de différence a une influence de 0,1 euros, tandis que le fait de passer de mauvais à très bon autorise une plus value de 1000 euros et l'inverse une moins value de 1000 euros symétriquement.

Pour faciliter les formules d'adaptation, il est courant de tenter de passer du symbolique au numérique pour exprimer des différences. Par exemple pour exprimer une différence entre mauvais et très bon, on aurait pu exprimer une échelle d'état entre 1 et 10 et rendre notre règle plus simple à exprimer.

A l'issue de l'adaptation, une solution hypothétique est donc proposée. Sa valeur n'est pas garantie puisqu'il s'agit d'un raisonnement analogique sur l'expérience et bien entendu les connaissances utilisées pour décrire ces connaissances d'adaptation peuvent avoir à être révisées.
Une originalité importante du RàPC est que le cycle de raisonnement prévoit explicitement cette révision.

324) Réviser

La révision consiste à continuer éventuellement l'élaboration de la solution cible en cas de besoin.
Pour réviser, on peut :

essayer la solution dans le monde "réel". Dans l'illustration des véhicules d'occasion, on essaye de vendre son véhicule au prix résultant de l'adaptation.
faire une introspection dans la base de cas en utilisant cette fois ci l'ensemble des descripteurs problème + solution pour vérifier que les cas similaires ont bien donné toute satisfaction . Par exemple, on vérifierait qu'il y a bien eu des véhicules similaires vendus au prix calculé.
utiliser une autre méthode d'évaluation de la solution (simulateur, système expert classique, etc...)

Dans tous les cas, en cas de divergence entre ce qui a été construit comme solution et ce qu'il aurait fallu faire, il est important :

de corriger, de façon à ce que le cas soit un cas avec une solution correcte ;
éventuellement, tracer l'écart et l'expiliquer sous forme d'exception (ce qui revient à particulariser une forme d'adaptation à une zone plus petite pour la classe de solutions)

Ce cas, avec les explications de révision, devient une source d'apprentissage importante pour faire évoluer les connaissances mobilisées par le raisonnement.
Il n'existe pas encore de méthode standardisée pour rendre compte de la tâche de révision dans le RàPC.

325) Mémoriser

La mémorisation du nouveau cas résolu est l'occasion d'enrichir la base de connaissances :

naturellement, un cas supplémentaire résolu augmente l'expérience du système,
en cas de révision, la connaissance générale peut être modifiée et en particulier les connaissances duales liées aux tâches "retrouver" et "adapter".

la mesure de similarité peut être raffinée pour éviter de sélectionner une classe de solution erronée ;
les connaissances d'influences peuvent être raffinées pour piloter l'adaptation. Ces connaissances d'influence sont duales des connaissances de similarité ; elles sont directement liées aux poids utilisés pour pondérer la mesure globale de similarité.
des dépendances nouvelles peuvent être découvertes, etc...

il peut être utile de garder la "trace" de l'ensemble du cycle avec le détail des corrections faites. Même si on n'a pas encore pu mettre à jour les connaissances du système, cette trace pourra être utilisée pour considérer ce cas comme un modèle pour "corriger" en s'inspirant de cette correction une nouvelle adaptation qui se ferait avec le même type de similarité (on découvrirait ce cas résolu et corrigé au moment de la révision).