Généralisation en apprentissage à partir d'exemples
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis treats two aspects of the problem of generalization in machine learning. First, we give a formal definition of the relation "more general" which we deduce from our notion of an example that is accepted by a description. We present also a methodology for determining if one description is more general than another. In the second part, we describe the generalization algorithm AGAPE based on structural matching. This algorithm tries to preserve a maximum of information common to the examples by transforming the descriptions of the examples until they match structurally, i. E. Until the descriptions are almost identical. At the end of this thesis, we present some extensions of this algorithm especially designed for enabling the treatement of counter-examples.
Abstract FR:
Cette thèse traite essentiellement du problème de la généralisation, en tant l'accent sur deux de ces aspects. Dans la première partie nous précisons ce que nous entendons par un exemple accepté par une description, ce qui nous conduit à donner une définition formelle de "plus général". Nous présentons aussi une méthode destinée à déterminer si une description est plus générale qu'une autre. La deuxième partie est consacrée à la présentation d'un algorithme de généralisation fondé sur l'appariement structurel. Nous décrivons d'abord la méthode de l'appariement structurel qui sert à transformer les descriptions des exemples jusqu'à ce qu'elles se ressemblent le plus possible. Cette opération a pour but de préserver un maximum d'information pendant la généralisation. Ensuite, nous présentons AGAPE, un algorithme de généralisation à partir d'exemples, ainsi que son implémentation. La tâche principale de cet algorithme est de mettre les exemples en appariement structurel ce qui rend triviale l'opération de la généralisation elle-même. A la fin de cette thèse, nous propo sons quelques extensions de cet algorithme. Surtout afin qu'il puisse également traiter des contre-exemples.