Selective Reformulation of Examples in Concept Learning

J.-D. ZUCKER, J.-G. GANASCIA

IBP-Laforia 1995/08: Rapport de Recherche Laforia / Laforia research reports
9 pages - Mai/May 1995 - Document en anglais.

PostScript : 237 Ko /Kb

Titre / Title: Selective Reformulation of Examples in Concept Learning

Résumé : Les exemples constituent la matière première des algorithmes d'apprentissage symbolique automatique (ASA). Le problème de leur représentation apparaît souvent se réduire au choix, non encore résolu, d'un vocabulaire pour les décrire. Le choix et la remise en question de ce qui, parmi les exemples, constituera un exemple d'apprentissage, restent cependant très peu décrits. Nous pensons que ceci vient du fait que dans de nombreux domaines, il existe des entités naturelles (un 'patient' en médecine, un 'animal' en zoologie, etc.) qui s'imposent comme les entités à représenter. Nous présentons, sur un exemple concret, l'intérêt pour l'ASA d'une remise en cause du rapport entre les connaissances du domaine et leurs descriptions sous forme d'exemples d'apprentissage. Nous qualifions ce rapport à travers la notion de 'morion', néologisme grec, défini comme la partie du domaine sur laquelle porte la représentation des exemples d'apprentissage. Nous expliquons en quoi la reformulation des exemples d'apprentissage suivant de nouveaux morions permet de réduire la complexité du processus de généralisation en fixant les appariements. Cette reformulation, baptisée reformulation moriologique, est expérimentée dans le cadre du système REMO, dont la première application complexe est la détection de similarités sur des caractères chinois.

Abstract : The fundamental tradeoff that is well known in Knowledge Representation and Reasoning affects Concept Learning from Examples too. Representation of learning examples using attribute-value has proved to support efficient inductive algorithms but limited expressiveness whereas more expressive representation languages, typically subsets of First Order Logic (FOL), are supported by less efficient algorithms. In fact, an underlying problem is that of the number of different ways of matching examples, just one in attribute-value representation and potentially large in FOL representation. This paper describes a novel approach to perform representation shifts on learning examples. The structure of these learning examples, initially represented using a subset of FOL-based languages, is reformulated so as to produce new learning examples that are represented using an attribute-value language. What is considered to be an adequate structure varies according to the learning task. We introduce the notion of morion (from the Greek) to qualify this structure and show, through a concrete example, the advantages it offers. We then describe an algorithm which reformulates learning examples automatically and go on to analyze its complexity. This approach to deductive reformulation is implemented in the REMO system that has been experimented on the learning of the construction of Chinese characters.

Publications internes Laforia 1995 / Laforia research reports 1995