[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

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:

SYSTEM: EBG (Explanation-Based Generalization)

generalization from a single example

The EBG method can be used to deduce specialized, easily computed ("operationlized") definitions of concepts given a complete (and thus potentially intractable) domain theory.

Keywords: Explanation, Operationality, Learning

SYSTEM: An example uses LEX and there is some discussion of Winston's ANALOGY and Lebowitz's UNIMEM.

Summary

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.

terminology:

concept: a predicate over some universe of instances that characterizes some subset of those instances
instance: defined by "ground literals" representing features and values
concept definition: necessary and sufficient conditions for category membership
example: positive example: an instance that qualifies for membership according to a concept definition (if it doesn't qualify it's a negative example)
explanation: a proof showing why the instance satisfies the conditions of membership
operationality criterion: "A predicate over concept definitions, specifying the form in which the learned concept definition must be expressed."

EBG's process:

explain why the given example satisfies the input goal concept. Must satisfy the operationality criterion. determines relevent features.
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:

The page numbers are from the reprint in the Readings in Machine Learning book.
The following summaries are the completely unedited and often hastily composed interpretations of a single individual without any sort of systematic or considered review. As such it is very likely that at least some of the following text is incomplete, inadequate, misleading, or simply wrong. One might view this as a very preliminary draft of a survey paper that will probably never be completed. The author disclaims all responsibility for the accuracy or use of this document; this is not an official publication of the Georgia Institute of Technology or the College of Computing thereof, and the opinions expressed here may not even fully match the fully considered opinions of the author much less the general opinions of the aformentioned organizations.

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:

JimDavies (jim@jimdavies.org)