Reversible Automata and Induction of the English Auxiliary System

TL;DR

This paper demonstrates that a core component of English syntax – the auxiliary verb system – can be learned efficiently using a specific type of inductive inference algorithm called k-reversible automata learning. This suggests that certain complex linguistic structures might be learnable through general induction principles, rather than requiring highly specialized linguistic knowledge.

What Problem Does This Paper Address?

Inducing formal grammars from examples is generally a computationally intractable problem, even for simple regular languages. This poses a significant challenge for computational models of language acquisition, as it's unclear how humans can learn language so effectively. The authors propose that a specific constraint, "k-reversibility," on the structure of the language being learned can make induction computationally feasible. They aim to show that the English auxiliary verb system, a known complex but structured part of English, adheres to this k-reversibility constraint, making it learnable by efficient algorithms.

Methods

The paper leverages Angluin's (1982) work on learning k-reversible regular languages. The core idea is to represent the language as a Deterministic Finite Automaton (DFA). The inference algorithm works by:

  1. Building a Prefix-Tree Automaton: Initially, a DFA is constructed that accepts exactly the observed sample strings.
  2. Merging States for K-Reversibility: The algorithm recursively merges states in the DFA based on specific criteria related to their "k-leaders" (the last k words encountered before reaching a state) and their transitions. This merging process aims to find the smallest k-reversible language that encompasses the observed data.
  3. Determining K: If negative examples (strings known not to be in the language) are available, the algorithm can iteratively increase k until the induced language no longer contains these negative examples.

The authors implemented this algorithm in MAC-LISP and tested it on both artificial and natural language examples.

Datasets

The primary dataset used is a corpus of 92 declarative statements representing variants of the English auxiliary verb system in the third person singular. This corpus covers permutations of tense, aspect, voice, do-support, and nine modals. The authors use surface forms of words as strings. They also analyze subsets of this corpus, specifically the active and passive auxiliary systems, treated as separate languages.

Key Insights and Ideas

  • K-Reversibility as a Learnability Constraint: The paper strongly suggests that k-reversibility is a crucial property that can render language induction computationally tractable, bridging the gap between theoretical intractability and practical learnability.
  • English Auxiliary System Fits the Model: The English auxiliary verb system, despite its complexity, can be faithfully modeled as a k-reversible regular language for k > 1. This is a significant finding, as it implies a structured learnability for a non-trivial linguistic subsystem.
  • Zero-Reversibility Overgeneralizes: The study highlights that zero-reversible inference (k=0) is too powerful and leads to overgeneralization, incorrectly grouping "do" with modals and generating infinite illegal variants. This underscores the importance of a non-zero k.
  • Inductive Power with Minimal Examples: Even with a relatively small k (like k=1), the system can infer a substantial portion of the language from a significantly reduced set of examples, demonstrating practical learning capabilities.
  • Psychological Plausibility: The authors suggest that k-reversible inference aligns with psychological principles of language acquisition, where simpler generalizations from examples are preferred, and children's observed errors (like combining "do" with tensed verbs) might be explained by simpler inference models.

Key Results

  • The English auxiliary system can be faithfully modeled as a k-reversible regular language for k > 1.
  • Zero-reversible inference (k=0) overgeneralizes the corpus, incorrectly grouping "do" with other modals and generating infinite illegal variants.
  • The English auxiliary system, treated as a 1-reversible language, can be inferred from a covering sample of only 48 out of 92 variants.
  • The active corpus alone requires 38 out of 46 examples for 1-reversible inference.
  • The passive corpus alone requires 28 out of 46 examples for 1-reversible inference.
  • Treating the full corpus as a 2-reversible language requires 76 examples for inference.
  • A 3+-reversible model cannot infer the corpus from any proper subset, indicating that k=2 is the upper bound for inferential power from subsets in this case.
  • A specific set of 45 verb sequences of length three or shorter were sufficient to induce the remaining nine longer strings for k-irreversible inference.

Limitations and Future Work

  • Limitations:
    • The paper focuses on a simplified, idealized model of the English auxiliary system, using surface forms and ignoring deeper syntactic or inflectional complexities.
  • The inference algorithm is applied to a specific, constrained subset of English syntax. Its applicability to broader, less structured linguistic phenomena is not directly addressed.
  • The authors acknowledge that a more complex model would be needed for a complete representation of English verb sequences.
  • Future Work:
    • Extension to Context-Free Languages: The authors suggest extending k-reversible inference methods to context-free languages, which would allow for the induction of more complex grammatical structures.
  • Integration with Larger Systems: They propose embedding the k-reversible inference algorithm within a larger linguistic processing system that might use external mechanisms (e.g., frequency-based rules, linguistic motivation) to handle exceptions or force the separate treatment of different linguistic phenomena (like active vs. passive voice).
  • Exploration of Other Linguistic Domains: The principle of k-reversibility could be applied to other areas of linguistics, such as morphology, syntax, and semantics, to induce substitution classes and simplify rule sets.

Summary updated

BibTeX
@inproceedings{1985reversible,
  title = {{Reversible Automata and Induction of the English Auxiliary System}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure