| Titre : | Les membranes linéaires par morceaux : une approche géométrique de la boucle abduction-induction dans les arbres et listes de décision |
| Titre original: | Piecewise linear membranes : a geometric study of the abduction-induction loop in decision trees and decision lists |
| Auteurs : | T. Fuhs ; CEMAGREF ANTONY DGDS ; UNIVERSITE DE CAEN UFR DE SCIENCES ; LABORATOIRE D'INGENIERIE POUR LES SYSTEMES COMPLEXES AUBIERE |
| Type de document : | thèse/mémoire |
| Année de publication : | 1998 |
| Format : | 192 p. |
| Note générale : |
Sigle : CEMAGREF Sigle : LISC |
| Langues: | = Français |
| Catégories : | |
| Mots-clés: | ALGORITHME ; APPRENTISSAGE ; ANALYSE DISCRIMINANTE ; OPTIMISATION |
| Résumé : |
L'objet de ce mémoire est l'étude de l'optimisation de surfaces discriminantes linéaires par morceaux d'un point de vue géométrique. En outre, une résolution théorique du dilemme de l'apprentissage à partir des données, dans un cadre inférentiel logique est proposée. Après une introduction au problème de la discrimination, suit la technique classique des arbres de décision qui construisent une surface de décision linéaire par morceaux. Le problème de l'apprentissage à partir d'un échantillon de taille finie est évoqué. Une interprétation logique de ce dilemme conduit à identifier le choix de l'espace d'hypothèses, c'est-à-dire de la structure de l'arbre, à une abduction, telle que l'a définie C.S.Pierce. Cette identification permet une résolution heuristique du dilemme par une boucle abduction-induction itérée. Les algorithmes gloutons classiques n'optimisant pas l'arbre construit, une approche géométrique est proposée pour cette optimisation. On établit ainsi que l'optimisation successive de chaque séparation de l'arbre sur un ensemble d'apprentissage qui lui est propre, permet d'optimiser la fonction de coût dans deux cas importants : l'erreur de classement et une erreur proche de la distance quadratique à la surface de la décision, qui est introduite et appelée erreur de dilatation. Dans ce dernier cas, une condition complémentaire de petits déplacements doit être vérifiée. La boucle abduction-induction est ensuite utilisée pour améliorer les algorithmes de développement d'arbres existants. Ensuite, on étudie le passage à la manipulation directe des convexes discriminants organisés en listes de décision et on l'illustre par l'exemple des membranes de perceptrons. Le terme générique de membranes linéaires par morceaux est alors proposé pour caractériser les structures et algorithmes introduits dans ce travail. This thesis deals with the optimization of piecewise linear classifiers from a geometric point of view. A theoretical resolution of the so-called learning dilemma, within a logical inferential framework, is also proposed. The classification problem and the decision tree technique are first presented. These trees build a piecewise linear decision surface in the input space. Then, the learning dilemma is investigated from a logical point of view. This leads first to the characterization of the choice for the hypothesis space as an abduction, as stated by C.S. Pierce in the late century, and furthermore, to a heuristic resolution of the dilemma by the means of an abduction-induction loop. The greedy top-down induction of decision trees algorithms do not optimize the built tree with respect to the cost function. A geometric approach is therefore proposed for such an optimization. It is shown that the iterated optimization of each linear separation belonging to the tree, upon a well-designed learning set, leads to the tree optimization in two main cases : misclassification error and dilatation error, an error close to the quadratic distance from the decision surface. For the latter, an additional condition of small displacements of the separations is required. The abduction-induction loop is then used to improve the existing tree induction algorithms. Furthermore, the direct handle of convex classifiers, organized as a decision list is investigated. As an example, the perceptron membrane technique is presented. Finally, the concept of a piecewise linear membrane to involve the structures and algorithms developed throughout this document is introduced. |
| Diplôme : | Thèse de doctorat en sciences spécialité Informatique, Université de Caen UFR de Sciences |
Exemplaires (1)
| Centre | Localisation | Section | Cote | Statut | Disponibilité |
|---|---|---|---|---|---|
| Jouy-en-Josas Antony | Antony | Thèses/Mémoires | TH768 | Empruntable | Disponible pour le prêt |
