Bounded Context Parsing and Easy Learnability

Robert C. BerwickCOLING 1984

TL;DR

This paper bridges a long-standing gap in computational linguistics by formally linking efficient parsing (how quickly a computer can understand a sentence) with easy learnability (how easily a language can be acquired). The authors demonstrate that if a grammar is parsable using a "bounded context" approach, it's also "easily learnable" under a specific model of language acquisition. This suggests that constraints for efficient processing might be stronger than those for learning, offering a new perspective on language design.

What Problem Does This Paper Address?

Computational linguists have long assumed that natural languages must be both parsable (efficiently processable by machines) and learnable (easily acquired by humans). However, the precise relationship between these two functional demands has been unclear. It's not immediately obvious why a language that's easy for a computer to parse would also be easy for a child to learn, or vice-versa. Researchers have often prioritized one over the other, leading to a disconnect. This paper aims to formally connect these two concepts by proposing specific computational models for both "easy parsability" and "easy learnability" and then proving a relationship between them.

Methods

The authors introduce two key formal models:

  • Bounded Context Parsability (BCP): This model is based on Marcus's parser, which uses a limited "lookahead" to make parsing decisions. Instead of examining the entire sentence history, it only considers a fixed window of symbols (both to the left and right) to determine the correct grammatical rule. This is a more constrained form of parsing than, for example, LR(k) parsers, which can use the entire left context.
  • Bounded Degree of Error (BDE) Learnability: This model, adapted from Wexler and Culicover, defines "easy learnability" as the ability to learn a language from simple, positive (grammatical) sentences with a limited degree of embedding (up to two levels). The core idea is that if a learner's current hypothesis about the grammar is wrong, there must be some simple sentence that reveals this error.

The paper's central method is to prove a theorem: If a family of grammars satisfies the Bounded Context Parsability condition, then it also satisfies the Bounded Degree of Error Learnability condition. This is achieved by showing that the constraints required for BCP are strong enough to guarantee BDE. Essentially, the paper demonstrates that the mechanisms enabling efficient, bounded-context parsing are sufficient to ensure that errors can be detected with simple examples, a prerequisite for easy learning.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Parsability as a Stronger Constraint: The paper's most significant insight is that, under these specific formal definitions, efficient parsability (BCP) is a stronger constraint than easy learnability (BDE). This suggests that computational linguists might have been justified in focusing on parsability as a primary metric for evaluating linguistic theories.
  • Formalizing the Link: For the first time, the paper provides a formal, mathematical link between two distinct computational models of language processing and acquisition.
  • Extending to Other Linguistic Subsystems: The authors propose that this framework can be extended beyond syntax to other areas like morphology and phonology. They introduce the concept of "k-reversibility" as an analog of BCP for finite state systems, suggesting it could be a key to ensuring learnability in these domains.
  • Implications for Rule Systems: The work implies that linguistic theories favoring "reversible" rules (like Koskenniemi's two-level morphology) might be more conducive to learnability than those with less constrained generative approaches, as reversibility aligns with the BCP concept.

Key Results

The primary result is the formal proof that Bounded Context Parsability implies Bounded Degree of Error Learnability. This means that any grammar parsable by a Marcus-type machine is also learnable from simple, positive examples.

While no specific quantitative performance metrics (like accuracy percentages or speedup factors) are presented, the qualitative result is that the constraints for efficient parsing are sufficient to guarantee a form of easy learnability. The paper also suggests that languages like a^n b^n c^n, which are strictly context-sensitive but parsable in an extended BCP sense, would also be easily learnable under this framework.

Limitations and Future Work

  • Specific Models: The results are contingent on the specific formal definitions of BCP and BDE used. The authors acknowledge that other models of parsability or learnability might yield different relationships.
  • Scope of Learnability: The "easy learnability" defined here is specific to Bounded Degree of Error and learning from positive examples. It doesn't encompass all possible learning scenarios or error types.
  • Future Work: The authors suggest extending the analysis to other linguistic subsystems (morphology, phonology) and exploring other potential constraints for learnability, such as the "strict cycle condition" in phonology. They also hint at the need to investigate how these findings apply to different types of grammars and learning procedures.

Summary updated

BibTeX
@inproceedings{berwick1984bounded,
  author = {Robert C. Berwick},
  title = {{Bounded Context Parsing and Easy Learnability}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}
Figure