Source Selection for Analogical Reasoning: An Empirical Approach

AAAI 1996

TL;DR

This paper introduces SCAVENGER, an analogical reasoning system that tackles the challenge of selecting relevant "source" knowledge for new problems, especially when the problem domain is poorly understood. SCAVENGER uses an assumption-based retrieval mechanism and empirical learning to build and refine its knowledge organization, demonstrating improved efficiency and effectiveness in diagnosing student errors.

What Problem Does This Paper Address?

Analogical reasoning is a powerful problem-solving technique where knowledge from a well-understood "source" domain is applied to a novel "target" problem. However, a major hurdle is selecting the right source. Traditional methods often require significant prior knowledge about the target problem, rely on restricted vocabularies for matching, use static similarity measures, and fail to adapt their knowledge organization based on problem-solving experience. This leaves a gap in how to effectively find relevant analogies in poorly understood domains or when problem contexts change. The authors aim to address these limitations by developing a system that can infer relevant analogies even with limited initial target information and learn from its own problem-solving successes.

Methods

SCAVENGER employs two core techniques:

  • Assumption-Based Retrieval: Instead of strictly requiring all target properties to match a source, SCAVENGER allows unknown target properties to assume values that facilitate a match. This "assumption-based" approach helps eliminate irrelevant sources rather than strictly selecting relevant ones, integrating inference with retrieval.
  • Empirical Learning for Memory Organization: After successfully solving a problem using an analogy, SCAVENGER updates its hierarchical knowledge base. It uses a variation of the ID3 learning algorithm to identify properties that best distinguish successful analogies from unsuccessful ones. These properties are then used to refine the index hierarchy, making future source selection more efficient and context-aware.

Datasets

The paper uses data from previous research on diagnosing children's errors in simple subtraction problems, specifically drawing from the work of Brown and VanLehn (1980) and VanLehn (1990).

  • Source Base: A set of LISP functions representing various subtraction bugs (e.g., borrow-no-decrement, transpose-error) was created. This source base contained 67 operators for the evaluation.
  • Test Problems: 500 buggy subtraction problems were randomly chosen from VanLehn's (1990) study, with correct solutions added. This resulted in a set of 575 potential test problems.
  • Training/Testing Split: The 575 problems were divided into a training set of 75 problems and a test set of 86 problems for evaluation.

Key Insights and Ideas

  • Assumption-based retrieval is powerful for underspecified problems: By allowing assumptions about unknown target properties, SCAVENGER can make progress even when initial information is scarce, effectively filtering out irrelevant sources.
  • Learning from success is crucial for efficient analogy: SCAVENGER's ability to refine its knowledge hierarchy based on successful analogies significantly improves future performance, demonstrating the value of empirical learning in analogical reasoning.
  • Context-aware memory organization beats static structures: Unlike traditional clustering methods, SCAVENGER's learning mechanism incorporates problem-solving context, leading to more adaptive and effective retrieval.
  • Analogy as "analogize-test-remember" is viable: The paper suggests that for poorly understood domains, a strategy of remembering useful analogies, rather than deep analytic reasoning, can be a powerful and practical approach.

Key Results

  • Significant Speedup: The untrained SCAVENGER algorithm took approximately 1600 seconds per problem. After training on 75 problems, the average time dropped to about 11 seconds per problem.
  • Scalability: The algorithm scales well as the source base grows. While the untrained version shows exponential complexity, the trained version's performance remains nearly flat.
  • Efficiency on Novel Problems: Even on unseen test problems, the trained algorithm achieved an average solution time of under 11 seconds (excluding a few particularly novel problems).
  • Reduced Analogy Generation: The untrained algorithm generated an average of 3096 candidate analogies per problem, while the trained version generated only 78.

Limitations and Future Work

  • Assumption Overhead: The paper acknowledges that assumption-based retrieval might lead to many potentially contradictory matches, and the overhead of maintaining these hypotheses could offset its advantages.
  • Analogy as Unsound Inference: The authors note that analogy is an unsound inference method, meaning a property useful in one context might not be in another. Using ID3 with such data violates some of its underlying assumptions, and its effectiveness in this context is a point of consideration.
  • Future Work: The paper suggests that the "analogize-test-remember" approach could be particularly useful in domains where failures are complex and interact in poorly understood ways, offering a potential tool for discovering and recording patterns of interacting failures.

Summary updated

BibTeX
@inproceedings{1996source,
  title = {{Source Selection for Analogical Reasoning: An Empirical Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure