[ CogSci Summaries home | UP | email ]

Mitchell, T., R. Keller, and S. Kedar-Cabelli, Explanation-Based Generalization: A Unifying View. Machine Learning, 1, 1982.

@article = { mitchell86explanation-based,
    author = "Tom M. Mitchell and Richard M. Keller and Smadar T. Kedar-Cabelli",
    title = "Explanation-Based Generalization: {A} Unifying View",
    journal = "Machine Learning",
    volume = "1",
    publisher = "Kluwer Academic Publishers, Boston",
    pages = "47--80",
    year = "1986"

Author of the summary: Jim R. Davies, 2000, jim@jimdavies.org
and J. William Murdock, 1997, murdock@cc.gatech.ed

Cite this paper for:


Contrasts relatively weak "similarity-based generalization" (standard supervised learning) with "explanation-based" methods that rely on a powerful domain theory to produce deductively justifiable concept definitions. Argues that a single compact, well-defined algorithm encompasses all of the relevant features of all past work in explanation based methods. Presents this algorithm in two steps, explanation by application of deductive rules and generalization by variablizing features. Illustrates the algorithm on the safe-to-stack and cup problems. Compares EBG to Winston's ANALOGY program which also constructs generalizations but goes so using concrete examples with causal relationships encoded. Describes an example of learning search heuristics in LEX (which solves integral calculus problems). Contrasts this with a variety of single purpose heuristic learning systems. Presents different views of EBG (learning, generalization, operationalized reformulation, etc.). Discusses open research problems such as imperfect theories, combining EBG with similarity-based methods (e.g. UNIMEM which verifies empirical generalizations by attempting to construct explanations), integrating EBG into larger problems (discussing LEX2 and METALEX). In an appendix, describes DeJong's work on explanation-based generalization for story understanding.

More Detail...

similarity-based generalization: generate a class concept based on the similar properties of some input examples. Needs lots of examples. Relies on inductive bias.

explanation-based generalization: generalizing from one example. It does this by using knowledge of the domain to pick out the essential features. [p435] They can justify the generalizations (something similarity based methods cannot do.)

SYSTEM: EBG (Explanation-Based Generalization) unifies all previous work in the area. [p436]

system input: a single positive example, a domain theory, "a definition of the concept under study," (which doesn't satisfy the following:) a description of the form in which the learned concept must be expressed."

output: a generalization and a justification. See table 1 in the paper.


EBG's process:
  1. explain why the given example satisfies the input goal concept. Must satisfy the operationality criterion. determines relevent features.
  2. generalize find the sufficient conditions for the explanaion structure in terms that satisfy the operationality criterion. Determines acceptable ranges for relevent features' values.
Since it takes relations from the given explanation, it doesn't have to search through all of the relations it knows about (like the SEX of the OWNER of the cup, e.g.) [p440]

The system uses logic, and in the form written up in this paper, it will have problems when domain theories are inconsistent, incomplete, intractable, etc. A scruffier EBG is needed.

Summary author's notes:

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies (jim@jimdavies.org)
Last modified: Tue Mar 7 13:52:50 EST 2000