Titre:                                         
Apprentissage de RŹgles a partir de DonnŽes Multi-Instances

Doctorant:
	Yann Chevaleyre
Sous la direction de:
	Jean-Daniel Zucker

{Yann.Chevaleyre;Jean-Daniel.Zucker}@lip6.fr
LIP6-CNRS, University Paris VI,
4, place Jussieu, F-75252 Paris Cedex 05, France


Resume:

Avec la representation multi-instances, chaque exemple d'apprentissage est 
represente par un "sac" de vecteurs attributs-valeurs. De par son 
expressivite et sa simplicite, cette representation offre une bonne 
alternative aux representations propositionnelles et relationnelles. De 
plus, grace au biais de linearite [chevaleyre&zucker01], un algorithme 
d'apprentissage multi-instance peut-etre utilise conjointement a des
techniques propositionalisations [zucker98],[alphonse01] pour resoudre
efficacement des problemes d'apprentissage relationnels. Il n'existe 
malheureusement pas d'algorithme efficace d'apprentissage de regles ou d'arbre de 
decision a partir de donnees multi-instances exploitant le biais de 
linearite.
Le but de notre recherche a ete de concevoir des algorithmes 
d'apprentissage de regles a partir de donnees multi-instances capables de 
generer rapidement des modeles concis, resistants au bruit, et utilisant le 
bias de linearite. Pour mieux comprendre les problemes poses par la conception
de tels algorithmes, une etude theorique du probleme a ete conduite. Divers 
modeles generatifs originaux dont il a ete montre qu'ils correspondaient
a des problemes multi-instances typiques ont ete 
developpes et etudies formellement, notamment a l'aide des outils de la 
theorie de l'apprentissage PAC. Puis, une methode generique permettant d'adapter un 
algorithme d'apprentissage propositionnel au cas multi-instances a ensuite 
ete proposee et implementee dans l'algorithme d'induction de regles Ripper 
(Cohen 95). L'analyse basee sur les modeles generatifs a ete mise a profit 
pour montrer que cette extension de Ripper, nomme Naive-RipperMi, 
presentait des defauts majeurs. Afin d'y palier, des modifications ont ete 
apportes a cette methode, notamment sous la forme d'une nouvelle mesure de 
couverture multi-instances probabiliste. Ces modifications ont ensuite ete implementees
a nouveau dans Ripper. Les performances de cette nouvelle extension, nommee RipperMi, sont 
finalement analyses experimentalement a l'aide de bases de donnees artificielles.

En plus de la linearite, d'autres biais multi-instances ont ete etudies. En 
particulier, un nouveau biais nomme p-linearite est definit. Contrairement 
au biais lineaire, ce biais est adapte au problemes d'apprentissage pour 
lesquels les instances sont tres correlees entre elles. Il est montre 
que l'algorithme Relic (Ruffo 2000) utilise implicitement ce biais, et que 
de petites modifications algorithmiques permettent de le rendre 
presque-optimal.

Des resultats experimentaux montrant l'interet et l'efficacite de notre
approche par rapport aux outils d'apprentissage classiques sont presentes.
En particulier, l'algorithme RipperMi est applique a un probleme de
classification d'images par le contenu.



Mots Clefs: Problemes d'apprentissage multi-instances, induction de regles, 
propositionalisation, apprentissage relationnel, theorie PAC