Phylogenetic Grammar Induction

Taylor Berg-Kirkpatrick, Dan KleinACL 2010 · OpenReview

Abstract

We present an approach to multilingual grammar induction that exploits a phylogeny-structured model of parameter drift. Our method does not require any translated texts or token-level alignments. Instead, the phylogenetic prior couples languages at a parameter level. Joint induction in the multilingual model substantially outperforms independent learning, with larger gains both from more articulated phylogenies and as well as from increasing numbers of languages. Across eight languages, the multilingual approach gives error reductions over the standard monolingual DMV averaging 21.1% and reaching as high as 39%.

Introduction

Unsupervised grammar induction—the task of discovering syntactic structure from raw text—is a fundamental challenge in natural language processing. Traditional successful methods often rely on parallel corpora (bitexts) to align structures across languages. However, such data is scarce for the vast majority of the world's languages. This paper introduces a method for multilingual unsupervised induction that operates without bitexts by leveraging the evolutionary relationships between languages.

Methodological Innovation: The Phylogenetic Prior

The core innovation is the use of a phylogenetic prior to regularize the parameters of a Dependency Model with Valence (DMV). Rather than treating languages as independent or identical, the model assumes that grammar parameters "drift" down the branches of a language family tree.

The linguistic phylogeny used to structure parameter drift across eight languages.

The model is implemented as a log-linear DMV, allowing for the use of features like "Noun-Verb attachment." To enable cross-lingual sharing, language-specific parts-of-speech (POS) tags are mapped to a universal coarse tagset. The phylogenetic prior is defined as a hierarchical Gaussian prior where a root ancestral parameter vector evolves into family-specific vectors (e.g., Germanic, Italic), which then drift into the observed parameters of modern languages.

Experimental Setup

The researchers evaluated the model on dependency parsing datasets for eight languages: English (Penn Treebank), Chinese (Chinese Treebank), and six languages from the CoNLL-X (2006) shared task (Dutch, Danish, Swedish, Spanish, Portuguese, and Slovene). The experiments focused on sentences of length 10 or less. Crucially, no parallel data was used; the sentences for each language were entirely independent.

Key Results

The multilingual approach significantly outperformed monolingual baselines. The "Linguistic" model, which utilizes the full phylogeny, achieved an average 21.1% relative error reduction over the standard monolingual DMV.

Performance comparison across monolingual and multilingual models.

As shown in the results table, the linguistic model consistently outperformed both the monolingual baseline and simpler multilingual configurations like "GLOBAL" (a flat tree) or "ALLPAIRS" (where all languages are tied to each other). For English, the error reduction reached as high as 39%. These results demonstrate that the specific topology of the language tree provides a powerful constraint that prevents the model from being confused by unrelated languages.

Discussion and Future Work

The success of this approach highlights how evolutionary regularization acts as a "tie-breaker" in unsupervised learning. By observing patterns across many related languages, the model can resolve structural ambiguities that are difficult to settle with data from a single language alone.

While effective, the current work is limited to short sentences and relies on a predefined phylogeny and manual POS mapping. Future research could explore automatically inducing the phylogeny from text data or scaling the model to handle the complexity of longer, more diverse prose.

Summary updated

Abstract

We present an approach to multilingual grammar induction that exploits a phylogeny-structured model of parameter drift. Our method does not require any translated texts or token-level alignments. Instead, the phylogenetic prior couples languages at a parameter level. Joint induction in the multilingual model substantially outperforms independent learning, with larger gains both from more articulated phylogenies and as well as from increasing numbers of languages. Across eight languages, the multilingual approach gives error reductions over the standard monolingual DMV averaging 21.1% and reaching as high as 39%.
BibTeX
@inproceedings{bergkirkpatrick2010phylogenetic,
  author = {Taylor Berg-Kirkpatrick and Dan Klein},
  title = {{Phylogenetic Grammar Induction}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=S1E6gneubB},
}
Figure