Apprentissage fondé sur l'explication

L'apprentissage fondé sur l'explication (en anglais explanation-based learning (EBL)) est une forme d'apprentissage automatique reposant sur la théorie des domaines et particulièrement l'induction de généralisations ou de canevas à partir d'exemples proposés comme entrainement[1].

Principe

Les programmes d'EBL s'attachent à quatre variables en entrée :

  • une caractérisation des limites de l'espace, base de l'ensemble de toutes les conclusions possibles ;
  • une théorie sur le domaine regroupant un ensemble d'axiomes propres au domaine d'application de l'apprentissage ;
  • des exemples d'application, soient des faits spécifiques excluant toutes les autres hypothèses ;
  • des critères opérationnels, déterminant les caractéristiques effectivement identifiables du domaine ; par exemple, quels sont les paramètres détectables au moyen de capteurs[2].

Théorie des domaines

Une théorie des domaines est dite parfaite ou complète si elle contient, en principe, toutes les informations nécessaires pour pouvoir répondre à toutes les questions concernant le domaine. Par exemple, la théorie des domaines dans le domaine des échecs complète est simplement les règles des échecs. En connaissant les règles, il est en principe possible de déduire le meilleur coup dans n'importe quelle situation. En pratique toutefois, faire ce genre de déduction est impossible à cause de l'explosion combinatoire. En pratique, l'EBL utilise des exemples d'application pour chercher à déduire des conséquences dans une théorie des domaines.

De par sa nature même, un système fondé sur l'EBL tente de chercher une manière d'induire des règles de chaque exemple d'application donné en entrée, et de les stocker dans une base de connaissances de la théorie des domaines étudiée. En trouvant des simples preuves pour chaque exemple, le système étend cette base de données et peut chercher puis classifier de futurs exemples qui seraient similaires à ce premier, et ce de manière très rapide[3].

L'un de principaux désavantages de cette méthode reste son cout global, résultant de la complexité d'une multitude de macros présentes dans le système pour trouver lesdites preuves. Cette propriété est analysée par Minton dans ses publications[4].

Applications

Un exemple d'application à l'EBL est un programme de jeu d'échecs qui apprendrait à partir d'exemples de jeu. Une position spécifique du jeu d'échecs qui contient une combinaison importante, par exemple, "perdre la reine noire en deux coups", contient aussi des informations inutiles, par exemple la disposition des pièces qui n'interviennent pas dans ladite combinaison. EBL peut, à partir d'un seul exemple d'application, déterminer les informations importantes pour induire des règles de généralisation[5]

Un autre domaine d'application très répandu de l'EBL est la recherche dans le TALN, ou traitement automatique du langage naturel, initialement entreprises par le chercheur Manny Rayner[6]. Dans cet exemple, une théorie des domaines étudiée très riche ---la grammaire d'une langue---, est utilisée pour créer certaines phrases spécifiques, créant du même coup une base de connaissances d'exemples d'application. Les premières applications industrielles à ces recherches aboutirent sur l'optimisation d'une base de données relationnelle dans le domaine[7]. La méthode EBL a été appliquée à grande échelle pour des systèmes d'analyse de langue naturelle[8], où le problème d'explosion de données a été résolu en faisant abstraction de la grammaire originale (le domaine) et en utilisant des techniques d'analyse particulières (LR-parsing), résultant en une accélération significative du processus, notamment en gagnant sur le cout des opérations, mais en perdant en désambiguation sémantique.

Lorsque la méthode d'apprentissage fondée sur l'explication est appliquée au TALN, les critères d'opérationalité peuvent-être entrés à la main[9], ou peuvent-être inférés de la base de connaissances en utilisant soit l'entropie de ses nœuds[10], soit la désambiguïsation de la cible par défaut[11].

L'EBL peut aussi être appliqué pour compiler des modèles de grammaire linguistique afin de faire de la reconnaissance de parole[12].

Des techniques similaires à l'EBL ont enfin été appliquées à la génération de surfaces[13].

Références

  1. ↑ (en) « Special Issue on Explanation in Case-Based Reasoning Â», Artificial Intelligence Review, vol. 24, no 2,‎
  2. ↑ (en) Richard Keller, « Defining operationality for explanation-based learning Â», Artificial Intelligence, vol. 35, no 2,‎ , p. 227–241 (DOI 10.1016/0004-3702(88)90013-6, lire en ligne [PDF], consulté le ) — Current Operationality Defn.: A concept description is operational if it can be used efficiently to recognize instances of the concept it denotes. After stating the common definition, the paper actually argues against it in favor of more-refined criteria.
  3. ↑ (en) Tom Mitchell, Machine Learning, McGraw-Hill, , 414 p. (ISBN 978-0-07-042807-2) — « In its pure form, EBL involves reformulating the domain theory to produce general rules that classify examples in a single inference step. Â»
  4. ↑ (en) Steven Minton, « Quantitative Results Concerning the Utility Problem in Explanation-Based Learning Â», Artificial Intelligence, vol. 42, nos 2-3,‎ , p. 363–392 (DOI 10.1016/0004-3702(90)90059-9)
  5. ↑ (en) Tom Mitchell, Machine Learning : Black-queen example, McGraw-Hill, , 414 p. (ISBN 978-0-07-042807-2), p. 308–309
  6. ↑ (en) Manny Rayner, « Applying Explanation-Based Generalization to Natural Language Processing Â», Procs. International Conference on Fifth Generation Computing, Kyoto,‎ , p. 1267–1274
  7. ↑ (en) Christer Samuelsson et Manny Rayner, « Quantitative Evaluation of Explanation-Based Learning as an Optimization Tool for a Large-Scale Natural Language System Â», Procs. 12th International Joint Conference on Artificial Intelligence, Sydney,‎ , p. 609–615
  8. ↑ (en) Christer Samuelsson, Fast Natural-Language Parsing Using Explanation-Based Learning, Stockholm, Doctoral Dissertation, Royal Institute of Technology,
  9. ↑ (en) Manny Rayner et David Carter, « Fast Parsing using Pruning and Grammar Specialization Â», Procs. ACL, Santa Cruz,‎
  10. ↑ (en) Christer Samuelsson, « Grammar Specialization through Entropy Thresholds Â», Procs. ACL, Las Cruces,‎ , p. 188–195
  11. ↑ (en) Nicola Cancedda et Christer Samuelsson, « Corpus-based Grammar Specialization Â», Procs 4th Computational Natural Language Learning Workshop,‎
  12. ↑ (en) Manny Rayner, Beth Ann Hockey et Pierrette Bouillon, Putting Linguistics into Speech Recognition : The Regulus Grammar Compiler, ???, 305 p. (ISBN 978-1-57586-526-3)
  13. ↑ (en) Christer Samuelsson, R. Mitkov (dir.) et N. Nicolov (dir.), « Example-Based Optimization of Surface-Generation Tables Â», Current Issues in Linguistic Theory, Amsterdam, John Benjamins, vol. 136 « Recent Advances in Natural Language Processing Â»,‎