h t t p s : / / l i n k . s p r i n g e r . c o m / c o n t e n t / p d f / 1 0 . 1 0 2 3 / A : 1 0 2 2 6 9 1 1 2 0 8 0 7 . p d f

Ingest: Explanation-Based Generalization: A Unifying View

Type: kb/sources/types/ingest-report.md

Classification

A scientific paper presenting a general algorithm, worked examples, comparisons with earlier systems, and open research problems. Its main contribution is a unifying formal account rather than a controlled performance evaluation. Authors Tom M. Mitchell, Richard M. Keller, and Smadar T. Kedar-Cabelli were Rutgers machine-learning researchers and participants in several of the research programs being compared. Published in Machine Learning 1 (1986), pp. 47–80.

Summary

Explanation-based generalization (EBG) takes a goal concept, one positive example, a domain theory, and an operationality criterion specifying a usable output form. It proves that the example satisfies the concept, then regresses the goal through that proof to derive operational sufficient conditions. The result generalizes the example but usually specializes the goal concept: it covers cases supported by the selected explanation, not every possible instance. The supplied theory licenses the derivation; EBG compiles consequences already implicit in it rather than empirically repairing it. Examples involving stacking objects, recognizing cups, and learning search heuristics show how this can produce complex relevant constraints without searching arbitrary feature combinations. The paper also identifies incomplete, intractable, and inconsistent theories, multiple-example learning, and automatic task formulation as unresolved problems, distinguishing the core method from related systems and proposed extensions.

Quotes

  • Source extract (verbatim): 1. Explain: Construct an explanation in terms of the domain theory that proves how the training example satisfies the goal concept definition. • This explanation must be constructed so that each branch of the explanation structure terminates in an expression that satisfies the operationality criterion. 2. Generalize: Determine a set of sufficient conditions under which the explanation structure holds, stated in terms that satisfy the operationality criterion. • This is accomplished by regressing the goal concept through the explanation structure. The conjunction of the resulting regressed expressions constitutes the desired concept definition.

  • Source location: Section 2.2, “The EBG method,” printed p. 52, steps 1–2.

  • Source extract (verbatim): A final point illustrated by this example is that the final concept definition produced by EBG is typically a specialization of the goal concept rather than a direct reexpression of the concept. This is largely due to the fact that the explanation structure is created for the given training example, and does not explain every possible example of the goal concept.

  • Source location: Section 2.3, printed p. 57, final paragraph.

  • Source extract (verbatim): Thus, although the EBG method is restricted to compiling the deductive consequences of its existing domain theory, this kind of learning is often nontrivial (as is the case for learning chess strategies).

  • Source location: Section 4.1, printed p. 68, “EBG as Reformulating/Operationalizing/Deducing from what is already known.”

  • Source extract (verbatim): Thus, a major research issue for explanation-based generalization is to develop methods that utilize imperfect domain theories to guide generalization, as well as methods for improving imperfect theories as learning proceeds.

  • Source location: Section 4.2.1, printed p. 69, opening paragraph.

Connections Found

This source is a technical anchor and boundary for the EBG portion of reflective theory refinement's lineages: it establishes theory-guided inference and example-guided operationalization, while treating improvement of imperfect theories as further research. That supports a precursor relation on how supplied knowledge guides learning, without attributing empirical theory repair or a reflective self-target to EBG. It also supports learning beyond generality, since making an entailed consequence usable can matter without adding independent knowledge. Its compilation remains within symbolic representational form; it therefore provides a comparison boundary for codification, whose registered meaning requires a natural-language-to-symbolic crossing.

Extractable Value

  1. Identify the changed artifact and the retained premises. EBG produces an operational predicate or rule for future recognition or search control. The domain theory, goal concept, and operationality criterion are supplied inputs to this derivation, not objects empirically revised by the core algorithm. This makes the lineage comparison precise without an umbrella learning category. [quick-win]
  2. Separate derivation from theory repair. Sections 4.1 and 4.2.1 distinguish compiling deductive consequences from learning with and improving imperfect theories. Use that boundary to limit what EBG contributes to the lineage account: guidance by explicit knowledge is established; empirical repair requires a separate mechanism and source. [quick-win]
  3. State the direction of generalization. A rule can cover more instances than its training example while covering fewer than the supplied goal concept. Section 2.3 attributes this restriction both to the chosen explanation and to regression that preserves only sufficient conditions. A KB account should not equate generalizing one experience with expanding the learner's underlying theory. [quick-win]
  4. Explain why experience still matters when conclusions are entailed. Examples focus operationalization on cases encountered in the learner's environment; unguided derivation could expend effort on possibilities never used. Section 4.1 supplies a mechanism for useful learning through selective compilation, complementing the KB's distinction between generality and speed or cost. [just-a-reference]
  5. Keep transformation and form separate. Deriving a symbolic recognition rule from symbolic premises changes usability without crossing representational forms. Calling this compilation is faithful to the paper; calling it codification in the KB's technical sense would conceal the different transition. [quick-win]

Limitations (our opinion)

The worked examples illustrate the mechanism, but they do not establish comparative performance, robustness, or general usefulness across realistic domains. The example descriptions, inference rules, goal concepts, and operationality criteria are supplied. The learner can compose constraints licensed by those rules; these examples do not demonstrate acquisition or correction of the supplied premises and criteria.

Deductive justification is conditional on the theory. The stacking example itself includes a default weight rule, and section 4.2.1 explains how defaults can produce inconsistent explanations. A formally derived rule should therefore not be treated as independently validated knowledge about the world. Generalization also remains bounded by the selected proof and by what the representation can express.

Related systems discussed in the paper do not all implement core EBG. ANALOGY uses plausible explanations from precedents rather than the required deductive rules. METALEX uses performance diagnostics and approximating transformations; its discussion does not establish that EBG itself repairs a domain theory from empirical failure. Likewise, the paper's comparisons with earlier work support named mechanism relationships, not a complete historical priority claim.

The full-paper text extraction contains damaged mathematical notation and omits graphical proof trees. The prose and tabular definitions support this analysis, but this capture is insufficient for checking every displayed derivation or reconstructing an implementation from the figures alone.

Revise the EBG paragraph in reflective theory refinement's lineages to identify EBG as proof-guided operationalization under a supplied theory, explicitly separating that precursor from empirical theory refinement.