Explanation-based learning

Explanation-based learning (EBL) is a form of machine learning that exploits a very strong, or even perfect, domain theory to make generalizations or form concepts from training examples.[1]

Details

An example of EBL using a perfect domain theory is a program that learns to play chess by being shown examples. A specific chess position that contains an important feature, say, "Forced loss of black queen in two moves," includes many irrelevant features, such as the specific scattering of pawns on the board. EBL can take a single training example and determine what are the relevant features in order to form a generalization.[2]

A domain theory is perfect or complete if it contains, in principle, all information needed to decide any question about the domain. For example, the domain theory for chess is simply the rules of chess. Knowing the rules, in principle it is possible to deduce the best move in any situation. However, actually making such a deduction is impossible in practice due to combinatoric explosion. EBL uses training examples to make searching for deductive consequences of a domain theory efficient in practice.

In essence, an EBL system works by finding a way to deduce each training example from the system's existing database of domain theory. Having a short proof of the training example extends the domain-theory database, enabling the EBL system to find and classify future examples that are similar to the training example very quickly.[3] The main drawback of the method---the cost of applying the learned proof macros, as these become numerous---was analyzed by Minton.[4]

Basic formulation

EBL software takes four inputs:

Application

An especially good application domain for an EBL is natural language processing (NLP). Here a rich domain theory, i.e., a natural language grammar---although neither perfect nor complete, is tuned to a particular application or particular language usage, using a treebank (training examples). Rayner pioneered this work.[6] The first successful industrial application was to a commercial NL interface to relational databases.[7] The method has been successfully applied to several large-scale natural language parsing system,[8] where the utility problem was solved by omitting the original grammar (domain theory) and using specialized LR-parsing techniques, resulting in huge speed-ups, at a cost in coverage, but with a gain in disambiguation. EBL-like techniques have also been applied to surface generation, the converse of parsing.[9]

When applying EBL to NLP, the operationality criteria can be hand-crafted,[10] or can be inferred from the treebank using either the entropy of its or-nodes[11] or a target coverage/disambiguation trade-off (= recall/precision trade-off = f-score).[12] EBL can also be used to compile grammar-based language models for speech recognition, from general unification grammars.[13] Note how the utility problem, first exposed by Minton, was solved by discarding the original grammar/domain theory, and that the quoted articles tend to contain the phrase grammar specialization---quite the opposite of the original term explanation-based generalization. Perhaps the best name for this technique would be data-driven search space reduction. Other people who worked on EBL for NLP include Guenther Neumann, Aravind Joshi, Srinivas Bangalore, and Khalil Sima'an.

References

  1. ↑ "Special issue on explanation in case-based reasoning". Artificial Intelligence Review. 24 (2). October 2005.
  2. ↑ Black-queen example from Mitchell, Tom (1997). Machine Learning. McGraw-Hill. pp. 308–309. ISBN 0-07-042807-7.
  3. ↑ Mitchell, Tom (1997). Machine Learning. McGraw-Hill. p. 320. ISBN 0-07-042807-7. In its pure form, EBL involves reformulating the domain theory to produce general rules that classify examples in a single inference step.
  4. ↑ Minton, Steven (1990). "Quantitative Results Concerning the Utility Problem in Explanation-Based Learning". Artificial Intelligence. 42 (2-3): 363–392. doi:10.1016/0004-3702(90)90059-9.
  5. ↑ Keller, Richard (1988). "Defining operationality for explanation-based learning" (PDF). Artificial Intelligence. 35 (2): 227–241. doi:10.1016/0004-3702(88)90013-6. Retrieved 2009-02-22. 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.
  6. ↑ Rayner, Manny (1988). "Applying Explanation-Based Generalization to Natural Language Processing". Procs. International Conference on Fifth Generation Computing, Kyoto. pp. 1267–1274.
  7. ↑ Samuelsson, Christer; Manny Rayner (1991). "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. pp. 609–615.
  8. ↑ Samuelsson, Christer (1994). Fast Natural-Language Parsing Using Explanation-Based Learning. Stockholm: Doctoral Dissertation, Royal Institute of Technology.
  9. ↑ Samuelsson, Christer (1996). "Example-Based Optimization of Surface-Generation Tables". in R. Mitkov and N. Nicolov (eds.) "Recent Advances in Natural Language Processing," vol. 136 of "Current Issues in Linguistic Theory": John Benjamins, Amsterdam.
  10. ↑ Rayner, Manny; David Carter (1996). "Fast Parsing using Pruning and Grammar Specialization". Procs. ACL, Santa Cruz.
  11. ↑ Samuelsson, Christer (1994). "Grammar Specialization through Entropy Thresholds". Procs. ACL, Las Cruces. pp. 188–195.
  12. ↑ Cancedda, Nicola; Christer Samuelsson (2000). "Corpus-based Grammar Specialization". Procs 4th Computational Natural Language Learning Workshop.
  13. ↑ Rayner, Manny; Beth Ann Hockey; Pierrette Bouillon (n.d.). Putting Linguistics into Speech Recognition: The Regulus Grammar Compiler. ISBN 1-57586-526-2.
This article is issued from Wikipedia - version of the 10/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.