Learning Arithmetic Problem Solver

Masamichi Shimura, Seiichiro SakuraiAAAI 1986

TL;DR

This paper introduces LAPS, a system that learns to solve arithmetic word problems by acquiring knowledge through interaction with a teacher and by synthesizing rules from its own problem-solving experiences. It tackles the challenge of knowledge acquisition in AI systems, aiming to create a more flexible and adaptable problem solver.

What Problem Does This Paper Address?

Building intelligent systems that can understand and solve problems presented in natural language is a long-standing goal in AI. A major hurdle is the "knowledge acquisition bottleneck" – the difficulty of providing these systems with the vast amount of knowledge they need. Existing systems often require complete, pre-programmed knowledge, making them brittle and unable to handle novel situations. This paper addresses the problem of creating an AI system that can learn to solve arithmetic word problems, specifically by acquiring new knowledge when it encounters problems it doesn't yet know how to solve. The goal is to move beyond systems that are merely programmed to solve problems and towards systems that can genuinely learn and improve.

Methods

LAPS is built around a modular architecture consisting of:

  • Natural Language Processor: This component translates natural language problem statements into an internal, structured representation called a "fact-graph," which is a type of semantic network. It uses an extended LINGOL parser for syntactic analysis and a semantic analyzer to build the fact-graph.
  • Problem Solver: This module uses the fact-graph and a knowledge base of "equation extraction rules" to derive equations and solve the problem. These rules specify how to translate problem components into mathematical expressions.
  • Rule Generator: When LAPS encounters a problem it cannot solve, this module interacts with a teacher. It takes the teacher's advice (also in natural language) and generates a new, generalized rule.
  • Rule Modifier: This component refines rules, either generalizing them or specializing them based on teacher feedback, to ensure they are applicable and correct.
  • Knowledge Base: This stores the learned rules and hierarchical concept knowledge.

A key innovation is LAPS's ability to learn in two ways:

  1. Learning from a Teacher: When LAPS lacks knowledge, it asks a teacher for help. The teacher's explanation is converted into a generalized rule. This process involves translating the advice into an internal format and then applying generalization techniques (like dropping conditions or replacing constants with variables) to create a rule that can be applied to a broader range of problems.
  2. Learning from Execution: LAPS can also synthesize new rules by combining existing rules that were successfully applied during problem-solving. This involves traversing the internal tree structure representing the solution process and composing equations. This synthesized rule is then generalized and added to the knowledge base.

Datasets

Not discussed in the paper. The system learns from direct interaction with a user/teacher and from solving example problems.

Key Insights and Ideas

  • Bridging the Knowledge Gap: LAPS demonstrates a practical approach to overcoming the knowledge acquisition bottleneck by allowing the system to learn from its own failures and from human guidance.
  • Generalization is Key: The system doesn't just store specific solutions; it actively generalizes rules. This allows it to solve new, similar problems without explicit programming for each one. The paper highlights techniques for generalization, including dropping conditions and replacing constants with variables.
  • Two-Pronged Learning: The combination of learning from a teacher (data-driven) and learning from execution (model-driven) provides a robust learning mechanism. Learning from execution is noted as being more efficient as it relies on existing domain knowledge.
  • Rule Modification for Robustness: The inclusion of a rule modifier that can specialize or generalize rules based on feedback is crucial. This prevents the system from making incorrect assumptions or over-generalizing, ensuring more reliable learning.

Key Results

The paper presents LAPS as a functional system capable of learning. While specific quantitative results (like accuracy percentages or speedups) are not detailed, the paper illustrates LAPS's learning capabilities through example dialogues:

  • Example 1 (Weight/Concentration): LAPS fails to solve a problem about solution concentration, asks the user for the formula, learns a rule, and then successfully solves it.
  • Example 2 (Cranes and Turtles): LAPS solves a problem involving the number of legs of cranes and turtles. After solving, it generates a new, more generalized equation (Figure 7) that can be applied to similar problems involving different animals and leg counts.

The system's ability to synthesize new rules from applied ones is demonstrated, showing how it can build more complex problem-solving strategies.

Limitations and Future Work

The authors acknowledge several limitations:

  • Disjunctive Concepts: LAPS's generalization process, based on Mitchell's candidate elimination algorithm, struggles with acquiring disjunctive concepts.
  • Over-Generalization: If the maximally specific condition is overly generalized, LAPS may fail to restore discarded information, leading to learning failures.
  • Efficiency of Generalization: While LAPS restricts the hypothesis search space for efficiency, the paper notes that Mitchell's algorithm itself can be data-driven and less efficient.
  • Rule Modification Necessity: Rules generated through problem-solving, like those from teacher advice, still require modification and revision.

Future work could involve exploring more advanced generalization techniques, improving the efficiency of the learning process, and extending LAPS to handle more complex problem domains beyond arithmetic. The paper suggests that by altering the domain-dependent knowledge (the initial rules), the system's applicability can be extended.

Summary updated

BibTeX
@inproceedings{shimura1986learning,
  author = {Masamichi Shimura and Seiichiro Sakurai},
  title = {{Learning Arithmetic Problem Solver}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure