Theory-Based Inductive Learning: An Integration of Symbolic and Quantitative Methods

Spencer StarUAI 1987

TL;DR

This paper introduces Theory-Based Inductive Learning (T-BIL), a novel approach that merges symbolic reasoning (Explanation-Based Generalization - EBG) with quantitative methods (Bayesian decision theory) to create systems that can generate causal explanations for observed events, make decisions based on these explanations, and adaptively revise both as new information becomes available. This integration aims to overcome the limitations of purely deductive or inductive learning methods, enabling more robust and context-aware decision-making in uncertain environments.

What Problem Does This Paper Address?

Traditional machine learning approaches often fall into two camps: purely deductive methods, which are truth-preserving but not ampliative (they don't learn new information beyond what's implicitly known), and purely inductive methods, which are ampliative but not truth-preserving (their generalizations can be wrong). Explanation-Based Generalization (EBG), a prominent deductive learning technique, excels at generating explanations from a single training example and domain knowledge but struggles with noisy or probabilistic data and doesn't inherently link learning to decision-making utility. On the other hand, quantitative methods like Bayesian decision theory handle uncertainty and utility maximization well but often lack the explanatory power of symbolic approaches.

This paper addresses the challenge of building intelligent systems that can:

  1. Generate causal explanations for observed events in uncertain, dynamic environments.
  2. Make decisions based on these explanations, considering the utility of outcomes.
  3. Adapt and revise both explanations and decisions incrementally as new information (observation reports) arrives.

Essentially, it seeks to bridge the gap between understanding why something happened and what to do next in a way that is both logically sound and practically useful in the face of uncertainty.

Methods

T-BIL integrates several key components:

  • Explanation-Based Generalization (EBG): Used to construct a specific, then generalized, explanation of a training example. This explanation is framed as a proof tree, which is then transformed into an influence diagram. The generalization process is guided by a "training example" that provides contextual constraints, ensuring the explanation is relevant.
  • Influence Diagrams: These acyclical directed graphs (with chance and decision nodes) serve as the graphical representation of the causal explanations. They explicitly model probabilistic dependencies and conditional independencies, offering a more intuitive representation than decision trees for complex problems.
  • Bayesian Decision Theory: This quantitative framework is used for decision-making. It incorporates utilities (preferences for outcomes) and probabilities (beliefs about states of the world). T-BIL uses observation reports to update these beliefs via Bayes' theorem, leading to incremental revision of explanations and subsequent decisions.
  • Operational Explanation: A key constraint where the terms used in the generalized explanation must be reducible to observable and measurable features in the problem context. This grounds theoretical explanations in empirical reality.
  • Goal Regression: A technique borrowed from EBG, used to generalize the specific explanation derived from the training example to cover a broader class of instances.

The core novelty lies in the synergistic combination: EBG provides the structure and context for explanations, influence diagrams visualize these probabilistic causal relationships, and Bayesian updating allows for continuous learning and adaptation based on observed outcomes.

Datasets

The paper does not discuss specific datasets used for training or evaluation in a formal sense. Instead, it presents a detailed case study of a "Robot's Choice-Of-Path Problem" as a running example to illustrate the T-BIL methodology. This problem is a synthetic benchmark designed to showcase the integration of symbolic and quantitative methods in a dynamic, stochastic environment.

Key Insights and Ideas

  • Bridging Deductive and Inductive Learning: The paper argues that T-BIL offers a way to combine the strengths of both deductive (truth-preserving) and inductive (ampliative) learning, creating a more powerful and flexible learning paradigm.
  • Contextualized Explanations: The use of a training example in EBG is crucial not just for efficiency but for providing the necessary contextual constraint to ensure the generated explanation is relevant and meaningful, rather than just a valid logical proof.
  • Operational Explanations Grounded in Observation: The requirement for "operational explanations" ensures that abstract concepts are tied to observable phenomena, making the system's reasoning more transparent and verifiable.
  • Iterative Learning and Decision-Making: T-BIL's iterative process of deciding, observing, and updating allows for adaptive behavior in stochastic environments, where decisions are continuously refined based on feedback.
  • Influence Diagrams as Explanatory Tools: The paper highlights influence diagrams as a powerful graphical tool for representing complex probabilistic causal relationships, making explanations more accessible and interpretable.

Key Results

The paper primarily focuses on demonstrating the methodology through a detailed example: a robot navigating a path with uncertain obstacles.

  • Explanation Generation: T-BIL successfully generates both specific (Figure 1) and generalized (Figure 2) influence diagrams that explain why a particular decision (taking the short path) was made and why an outcome (table resisting) occurred, based on the training example and domain theory.
  • Decision Support: The generalized explanation is used to construct a decision tree (Figure 3) that guides the robot's decisions, considering factors like density measurement and table strength.
  • Value of Information: The example quantifies the value of perfect information and the value of obtaining additional information (density measurement), demonstrating how T-BIL can inform optimal information gathering strategies. For instance, density measurement provided an expected utility gain of 3.7 utils in the example.
  • Inductive Learning and Belief Revision: The paper illustrates how observed outcomes (e.g., a table resisting) lead to updated beliefs about underlying states (e.g., table strength), showing a drop in the probability of the table being fragile from .80 to .78. It also calculates the number of state transformations required on average for beliefs to shift sufficiently to alter decisions.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges the potential for "combinatorial explosion" in dynamic programming problems, though it notes that the multistage approach helps manage this. The complexity of generating and updating explanations in very large state spaces is an implicit challenge.
  • Domain Knowledge Requirements: EBG, and by extension T-BIL, requires substantial domain knowledge to construct initial explanations.
  • Implementation and Real-World Applications: The authors state that the next steps involve implementing T-BIL as a working program and finding suitable real-world applications. They suggest areas like scientific hypothesis testing and financial trading programs as potential avenues.
  • Updating Procedures: While Bayes' theorem is mentioned for updating, the paper notes that specific proposed procedures for updating probabilities can be used, implying that the exact mechanism for updating might require further refinement or selection.
  • Disjunct Representation: The paper mentions that T-BIL can represent disjuncts (e.g., a table being either fragile or sturdy), which is an improvement over basic EBG.

The authors express an optimistic view that integrating symbolic and quantitative methods will be synergistic, leading to powerful problem-solving paradigms.

Summary updated

BibTeX
@inproceedings{star1987theory,
  author = {Spencer Star},
  title = {{Theory-Based Inductive Learning: An Integration of Symbolic and Quantitative Methods}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1987},
}
Figure