A Diverse Dirichlet Process Ensemble for Unsupervised Induction of Syntactic Categories

Roi Reichart, Gal Elidan, Ari RappoportCOLING 2012

Abstract

Unsupervised grammar induction remains a fundamental challenge in Natural Language Processing, particularly the task of assigning meaningful syntactic labels to induced phrase structures. This paper proposes a novel "Mixture of Experts" framework that leverages the non-parametric properties of Dirichlet Process Mixture Models (DPMMs). By varying the concentration parameter of the DPMM, we generate a diverse set of clustering experts whose outputs are aggregated via a graph-based normalized cut algorithm. Our approach, DP+NC, achieves a new state-of-the-art in syntactic category induction across English, German, and Chinese, demonstrating that ensemble diversity can effectively compensate for individual expert noise.

Introduction

In the field of Natural Language Processing (NLP), grammar induction involves learning the underlying structure of a language without the aid of human-annotated data. While significant progress has been made in identifying sentence structure (bracketing), automatically assigning meaningful syntactic categories (e.g., NP, VP, PP) to those brackets remains difficult.

Existing state-of-the-art methods, such as those proposed by Reichart and Rappoport (2008), typically employ a two-stage process: generating a large set of fine-grained categories and then clustering them into a smaller, standard set of labels. However, traditional clustering techniques like K-means often converge on similar, suboptimal solutions, limiting the potential for ensemble-based improvements. This paper addresses the "diversity problem" by introducing a method to generate high-quality yet sufficiently distinct tagging experts.

Methodology

The proposed framework consists of three distinct phases designed to maximize the utility of ensemble learning.

1. Initial Induction

The process begins with Bayesian Model Merging (BMM) to produce an initial set of thousands of fine-grained categories for a given phrase structure. These categories serve as the raw material for subsequent clustering.

2. Diverse Ensemble Generation

To overcome the limitations of K-means, the authors employ Dirichlet Process Mixture Models (DPMMs). As a non-parametric Bayesian model, the DPMM does not require a pre-specified number of clusters. Crucially, the authors vary the concentration parameter ($\alpha$) of the DPMM to produce 10 different "experts." Since different $\alpha$ values influence the granularity of the resulting clusters, this variation ensures the diversity necessary for a robust ensemble.

3. Aggregation via Normalized Cut

The final phase involves combining these diverse experts into a single consensus tagging. This is framed as a graph optimization problem where nodes represent the initial BMM categories and edge weights reflect the frequency with which experts clustered those categories together. The k-way normalized cut algorithm is then applied to find optimal final clusters, effectively filtering out noise and preserving consistent relationships across the ensemble.

Experimental Setup

The model's robustness was evaluated across three distinct languages using standard datasets restricted to sentences of length 10 or less:

  • English: WSJ10 (Penn Treebank), comprising 7,422 sentences.
  • German: NEGRA10, comprising 7,542 sentences.
  • Chinese: CTB10 (Chinese Penn Treebank), comprising 4,626 sentences.

Feature representation for the categories utilized the counts of Part-of-Speech (POS) tags in the leftmost and rightmost positions of the constituent, as well as its immediate siblings.

Results and Discussion

The DP+NC model consistently outperformed the previous state-of-the-art (RR08) across multiple metrics. In terms of Information Theoretic measures, the model achieved up to a 20.6% error reduction in Normalized Variation of Information (NVI). Mapping-based accuracy also saw gains; for instance, the English (WSJ10) F-score for many-to-one mapping improved from 58.9 to 61.4.

A key insight of this research is that the ensemble's strength is derived from the lack of correlation between individual experts rather than their individual accuracy.

Performance comparison of individual experts and baselines.

As shown in the table above, individual DP experts often underperform compared to K-means (KM) or the RR08 baseline when viewed in isolation. However, because their errors are diverse, the normalized cut aggregation is able to synthesize their outputs into a result that is superior to any single component. This improvement remained consistent across various target cluster sizes (from 5 to 26), proving the method's stability.

Conclusion

This work demonstrates the power of Bayesian non-parametrics in creating diverse ensembles for unsupervised NLP tasks. By leveraging DPMMs and graph-based aggregation, the authors set a new benchmark for syntactic category induction. Future work may explore joint learning frameworks where phrase structure and labels are induced simultaneously using hierarchical Dirichlet Processes, as well as methods to automatically determine the optimal number of final output categories.

Summary updated

BibTeX
@inproceedings{reichart2012diverse,
  author = {Roi Reichart and Gal Elidan and Ari Rappoport},
  title = {{A Diverse Dirichlet Process Ensemble for Unsupervised Induction of Syntactic Categories}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2012},
}
Figure