Using Left-corner Parsing to Encode Universal Structural Constraints in Grammar Induction

Hiroshi Noji, Yusuke Miyao, Mark JohnsonEMNLP 2016 · OpenReview

Abstract: This paper explores the intersection of cognitive science and machine learning by leveraging human memory limitations to improve unsupervised grammar induction. By employing left-corner parsing to constrain stack depth—a proxy for center-embedding—the authors achieve state-of-the-art results across 25 languages. (Hiroshi Noji, Yusuke Miyao, Mark Johnson. Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. 2016.)

Introduction

Grammar induction, the unsupervised learning of syntactic structure from raw text, remains a fundamental challenge in natural language processing. The primary difficulty lies in the vast search space of possible grammars. To constrain this space, researchers often rely on universal linguistic biases. While previous work has focused on dependency length (the distance between related words), this paper introduces a constraint based on a different universal: the avoidance of complex center-embedding.

Cognitive Constraints as Structural Biases

Human language rarely features deeply nested structures, such as "The reporter [who the senator [who Mary met] attacked] ignored the president." These center-embedded constructions are cognitively taxing because they require significant working memory. The authors hypothesize that machine learning models should similarly find such structures "implausible" during training. By using the inherent limitations of human memory as a mathematical regularizer, the model can more effectively prune the search space for valid grammars.

Methodology: Left-Corner Parsing and Stack Depth

The core innovation is the use of Left-corner (LC) Parsing to formalize this cognitive constraint. In an LC parser, the depth of the stack directly corresponds to the degree of center-embedding in a sentence. A shallow stack represents a simple structure, while a deep stack indicates complex nesting.

Standard vs. Left-corner tree representations with stack depth annotations.

The authors integrated this constraint into the Dependency Model with Valence (DMV), a classic generative model for grammar induction. During the Expectation-Maximization (EM) learning process, the search space was restricted to trees requiring a stack depth below a certain threshold (typically 1).

Formal transition rules for tracking stack depth.

To account for short, manageable nested phrases (e.g., "the cat's dinner"), the authors introduced a length-based relaxation hyperparameter ($\xi$). This allows the stack depth to increase only if the nested constituent exceeds a specific word count, ensuring the model doesn't over-penalize simple, common structures.

Experimental Results

The model was evaluated on the Universal Dependencies (UD) v1.2 dataset across 25 diverse languages, including English, Japanese, Arabic, and Ancient Greek. Models were trained on short sentences ($\le 15$ words) and tested on sentences up to 40 words.

Key findings include:

  • Consistent Performance Gains: The stack-depth constraint (DEP) consistently improved the Unlabeled Attachment Score (UAS) over the baseline across nearly all languages.
  • Synergy of Biases: The "anti-center-embedding" bias (DEP) and "short-dependency" bias (LEN) were found to be orthogonal. DEP excels at identifying constituent boundaries (like noun phrases), while LEN is better at capturing core head-dependent relationships (like verbs to nouns).
  • Competitive Accuracy: When combined with a simple root constraint (identifying the sentence root as a verb or noun), the model achieved an average UAS of 50.1%, outperforming many systems that rely on extensive hand-crafted rules.

Conclusion

This research demonstrates that cognitive limitations, specifically human memory capacity, can serve as powerful mathematical regularizers for machine learning. By encoding these universal structural constraints through left-corner parsing, the authors developed a robust, language-independent approach to unsupervised grammar induction. Future work may extend these constraints to constituent induction, where unsupervised learning has traditionally struggled.

Summary updated

BibTeX
@inproceedings{noji2016using,
  author = {Hiroshi Noji and Yusuke Miyao and Mark Johnson},
  title = {{Using Left-corner Parsing to Encode Universal Structural Constraints in Grammar Induction}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2016},
  url = {https://openreview.net/forum?id=gsY_JmCDDwc},
}
Figure