Case-based Problem Solving with a Large Knowledge Base of Learned Cases

Wendy G. LehnertAAAI 1987

Introduction

In the late 1980s, Case-Based Reasoning (CBR) systems were often restricted to small, hand-coded "toy" domains. A primary challenge was scaling: as a system's memory grows to include thousands of cases, the likelihood of conflicting or overlapping information increases exponentially. In her 1987 paper, Wendy G. Lehnert of UMass Amherst proposed PRO, a hybrid system that addresses this bottleneck by combining the structured logic of CBR with the fluid conflict resolution of connectionist "relaxation" networks.

Using English word pronunciation as a testbed—a domain notorious for its irregular rules and context-dependent mappings—Lehnert demonstrated how numerical relaxation can efficiently arbitrate between hundreds of potentially relevant cases to find optimal solutions.

The PRO System: Timid Acquisition and Relaxation

PRO operates through two primary mechanisms: a learning mode characterized by "timid" acquisition and a test mode utilizing numerical relaxation.

Timid Acquisition

Unlike systems that attempt to learn from every example, PRO employs a "timid" strategy. It segments training words into hypotheses (substring-to-phoneme mappings) and defines a "case" as a sequence of three such hypotheses. If the system cannot find a high-confidence segmentation for a new word based on its current knowledge, it ignores the word entirely. This prevents the memory from being "polluted" with erroneous mappings, allowing the system to build a solid foundation from simpler words before tackling complex irregularities.

Numerical Relaxation

When tasked with pronouncing a word, PRO does not rely on rigid rules. Instead, it generates a search space of all possible hypothesis sequences. This space is transformed into a lateral inhibition network where overlapping substrings—which cannot both be correct—are linked by inhibitory connections.

A lateral inhibition network generated for a word, where nodes represent potential phoneme mappings and edges represent inhibitory or excitatory connections.

Context nodes from memory provide positive activation to sequences the system has encountered before. A relaxation algorithm then runs for up to 30 iterations until the network stabilizes. The path with the highest final activation determines the output pronunciation.

Experimental Results

The system was evaluated using a corpus of 850 word/pronunciation pairs. After training on 750 words, PRO achieved significant accuracy, correctly identifying 89.9% of phonemes in familiar words and 75% in novel words.

Performance of PRO on trained and novel words as the number of processed target phonemes increases.

A notable observation from the performance data is the "cost of knowledge." As the system's hypothesis base grows, the search space for any given word becomes more crowded. This increased "noise" led to a slight dip in performance on familiar words (from 94.7% at 250 words to 89.9% at 750 words), even as the system's ability to handle novel words improved.

Comparative Efficiency

PRO demonstrated remarkable efficiency compared to contemporary models. For instance, the MBRtalk system required a massively parallel "Connection Machine" and over 4,400 training words to reach 86% accuracy. In contrast, PRO achieved comparable results within a standard Lisp environment using significantly less data, highlighting the power of its hybrid architecture.

Limitations and Future Directions

While successful, PRO faced limitations regarding its fixed window size of three hypotheses, which occasionally missed long-distance linguistic dependencies. Lehnert suggested that increasing this window or moving toward "symbolic constraint propagation" could further enhance the system's robustness. Despite these challenges, PRO remains a landmark example of how symbolic indexing and connectionist dynamics can be merged to solve complex, large-scale reasoning problems.

Summary updated

BibTeX
@inproceedings{lehnert1987case,
  author = {Wendy G. Lehnert},
  title = {{Case-based Problem Solving with a Large Knowledge Base of Learned Cases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure