Self-Correcting Generalization

Stephen B. WhitehillAAAI 1980

Abstract

This paper presents a system for incremental generalization that autonomously recovers from "over-generalization" by maintaining a ledger of positive and negative evidence for every rule it creates. By treating its rule set as a dynamic hypothesis, the system can reorganize its internal logic to handle exceptions and correct itself when initially misled by a biased sequence of data. Evaluation on English and French morphology demonstrates the system's ability to converge on correct linguistic rules regardless of the order in which examples are presented.

Introduction

In the late 1970s and early 1980s, a major hurdle in machine learning (then often called "incremental generalization") was the "order effects" problem. If a program sees a series of standard examples first, it might form a broad, "greedy" rule that works for those cases but fails on exceptions. Conversely, if it sees exceptions first, it might fail to find the broader pattern. Most systems of the era lacked "self-knowledge"—they couldn't remember why they made a generalization or how to undo it without starting over. Whitehill addresses this by creating a system that treats its rule set as a living hypothesis, capable of being demoted or promoted as new evidence trickles in.

Methods

The author utilizes a Concept Description Language based on production rules (string transformations).

Rule Structure

Rules use a wildcard (*) to match character strings. For example, the rule * -> *ED transforms "walk" to "walked." The system organizes rules based on two key operators: Rule Containment (does the input of Rule A match a subset of the inputs of Rule B?) and "Is-a-generalization-of" (does Rule A contain Rule B and produce the same result for those inputs?).

Examples of string transformation rules for English plurals.

Evidence Trees and Dynamic Reorganization

This is the core innovation of the system. Every rule is associated with an "evidence list":

  • Positive evidence: Examples that the rule correctly transformed.
  • Negative evidence: Examples where a more specific rule (an exception) was required.

The system maintains a "rule list" ordered by specificity. When the system encounters a word, it uses the first rule that matches. If a rule produces an error, the system creates a more specific rule and inserts it earlier in the list. If the evidence for a "blocked" (lower priority) rule eventually outweighs the evidence for the rule blocking it, the system swaps their positions.

Evaluation

The system was evaluated on two primary linguistic domains: English Morphology (past tense verbs and plural nouns) and French Adjective Pluralization. French was chosen because its morphology is significantly more complex than English, featuring "exceptions to exceptions."

Key Results

  • English Plurals: The system successfully learned to distinguish between the general +s rule and the +es rule for words ending in "ch" or "s." It correctly identified that while * -> *S is a generalization of *K -> *KS, it is not a generalization of *CH -> *CHES because they produce different outputs.
  • French Complexity: The system successfully replicated the rules found in standard French-English dictionaries for pluralizing adjectives, proving it could handle nested layers of morphological exceptions.
  • Trace Analysis: The paper provides a step-by-step trace showing the system initially over-generalizing the +es plural to the word "cars" (producing "cares"), then correcting itself once it received the correct "cars" input and re-weighting the evidence.

Discussion and Insights

  • Exceptions as "Negative Evidence": The system doesn't just see an exception as a failure. It treats the existence of a specific rule (like *CH -> *CHES) as negative evidence against a broader, simpler rule (like * -> *S).
  • Self-Correction via Re-ranking: Instead of deleting "bad" rules, the system re-ranks them. A rule that was once thought to be a universal "regular" rule might be demoted to an "exception" or vice versa based on the volume of direct evidence.
  • Order Independence: While the system is incremental, its ability to undo generalizations means it eventually converges on the "most reasonable" set of rules regardless of the order in which examples are presented.

Limitations

The system relies on the "maximal common generalization" being unique, which may not hold true for all concept description languages. Additionally, maintaining evidence trees for every rule could become memory-intensive as the rule set grows, and the current design is limited to string-to-string productions rather than more abstract semantic generalizations.

Summary updated

BibTeX
@inproceedings{whitehill1980self,
  author = {Stephen B. Whitehill},
  title = {{Self-Correcting Generalization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure