Solving multiple-instance and multiple-part learning problems with decision trees and decision rules. Application to the mutagenesis problem

J.-D. Zucker, Y. Chevaleyre

LIP6 2000/018: Rapport de Recherche LIP6 / LIP6 research reports
9 pages - Mai/May 2000 - Document en anglais.

Get it : 159 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Apprentissage et Acquisition de Connaissances

Titre français : Comprendre et résoudre les problèmes multi-instances et multi-parties avec des arbres et des listes de décision. Application a la prédiction de mutagénécité
Titre anglais : Solving multiple-instance and multiple-part learning problems with decision trees and decision rules. Application to the mutagenesis problem

Résumé : Récemment, Dietterich et al. (1997) ont introduit un nouveau problème d'apprentissage : l'induction à partir de données multi-instances. Ils ont de plus proposé une solution sous la forme d'un algorithme générant des hyper-rectangles parallèles aux axes. Typiquement, ce problème apparaît lorsqu'un objet possède différentes configurations, et que chacune d'entres elles peut être représentée par un vecteur attribut-valeurs.
Cet article présente le problème multi-parties, qui est plus général que le problème multi-instances, et montre comment le résoudre à l'aide d'algorithmes d'apprentissage multi-instances. Ces deux problèmes "multi" pourraient jouer un rôle crucial dans l'élaboration d'algorithmes efficaces pour l'apprentissage de relations "structure-activité", notamment dans le domaine de la chimie, ainsi que pour la programmation logique inductive.
Cet article analyse et tente de clarifier la résolution des problèmes multi. Il montre ensuite comment étendre des algorithmes d'apprentissage propositionnels classiques afin qu'il puissent gérer les données multi. En particulier, il présente une version multi-instances de la mesure d'entropie ainsi que de la mesure de couverture. Enfin, l'un des algorithmes multi présentés est utilisé avec succès pour résoudre le problème de la prédiction de mutagénécité.

Abstract : In recent work, Dietterich et al. (1997) have presented the problem of supervised multiple-instance learning and how to solve it by building axis-parallel rectangles. This problem is encountered in contexts where an object may have different possible alternative configurations, each of which is described by a vector. This paper introduces the multiple-part problem, which is more general than the multiple-instance problem, and shows how it can be solved using the multiple-instance algorithms. These two so-called "multiple" problems could play a key role both in the development of efficient algorithms for learning the relations between the activity of a structured object and its structural properties and in inductive logic programming. This paper analyzes and tries to clarify multiple-problem solving. It goes on to propose multiple-instance extensions of classical learning algorithms to solve multiple-problems by learning multiple-decision trees (ID3-M, C4.5-M) and multiple-decision rules (AQ-M, CN2-M,Ripper-M). In particular, it suggests a new multiple-instance entropy function and a multiple-instance coverage function. Finally, it successfully applies the multiple-part framework on the well-known mutagenesis prediction problem.

Mots-clés : Supervised learning, multiple-instance learning, decision tree, decision rules, mutagenesis problem, multiple-part problem, entropy, language biais, inductive logic programming, ILP

Key-words : Apprentissage supervisé, apprentissage multi-instances, arbre de décision, liste de décision, mutagénèse, problème multi-parties, entropie, biais de langage, programmation logique inductive

Publications internes LIP6 2000 / LIP6 research reports 2000

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr