17

Le cheminement conceptuel

d'élargissement des valeurs possibles, etc.) et en tenant compte d'heuristiques pour contrôler la recherche multi-directionnelle.

G(e₁, CE) est appelé l'étoile de e₁et représente l'ensemble de toutes les descriptions les plus générales qui couvrent le noyau (complétude) et ne couvrent pas les exemples négatifs (cohérence). Comme cela représente un nombre trop élevé de descriptions dans la pratique, l'algorithme effectue une recherche en faisceau pendant la génération de l'étoile pour produire une étoile bornéeG(e₁, CE/m) ne contenant que les m meilleures descriptions selon certains critères et seuils de tolérance fixés au départ. Les exemples positifs qui ne sont pas couverts par l'étoile sont éliminés et le processus de départ est répété jusqu'à ce que tous les exemples soient couverts.

Contrairement à Neddie, Main utilise une stratégie hybride (en faisceau) ascendante guidée par les données (lors du choix d'un exemple) et descendante guidée par un modèle (lors de la génération de l'étoile bornée). C'est un système à la fois numérique et symboliquequi exploite une représentation plus ou moins orientée objets : VL₂(Variable-Valued Logic) comme sous-ensemble de la logique du premier ordre [Michalski, 1980]. Main ne savait pas traiter les attributs à valeur numérique.

1.2.3 Maggy

Maggyest une implantation de l'algorithme d'appariement structurel et un descendant du système Agape [Kodratoff & Ganascia, 1986]. Il prend un ensemble d'exemples positifs et produit les généralisations conjonctives les plus spécifiques [Michalski, 1983]. Maggy utilise une représentation des connaissances fondée sur les framespermettant de décrire les observations (les observés) sous forme d'objets structurés ainsi que d'autres connaissances initiales de bon sens sur le domaine (hiérarchies d'objets, propriétés déductives, etc.) constituant le modèle descriptif (l'observable). Maggy peut être utilisé pour trouver toutes les généralisations conjonctives possibles d'un ensemble d'exemples (étant donné un modèle descriptif) ou sélectionner une généralisation fondée sur la quantité d'information perdue pendant la procédure. Considérons l'exemple suivant :

E₁: [objet1 <classe pourriture> <couleur blanc>] & [objet2 <classe tache> <couleur brun>] E₂: [objet1 <classe pourriture> <couleur jaune>] & [objet2 <classe tache> <couleur blanc>]

En faisant l'hypothèse qu'il y a une taxonomie des couleurs et que les pourritures et les taches sont des sortes de symptômes, Maggy extrait la généralisation "il y a une pourriture de couleur claire et une tache" plutôt que "il y a un symptôme blanc et un autre symptôme". Ceci provient du fait que davantage d'information est perdue en produisant la seconde généralisation [Manago, 1986]. Maggy renvoie à la fois la généralisation et une mesure de la quantité d'information perdue pendant le processus de généralisation.