Bayesian probability

Tree (set theory)

Hierarchical Dirichlet process

Dirichlet distribution

Inference

Dirichlet process

Mathematics

Latent Dirichlet allocation

Rule-based machine translation

Algorithm

Mathematical analysis

Philosophy

Boundary value problem

Artificial intelligence

Topic model

Parsing

Grammar

Computer science

Linguistics

Theoretical computer science

Grammar induction

Context-free grammar

We present a nonparametric Bayesian model of tree structures based on the hierarchical Dirichlet process (HDP). Our HDP-PCFG model allows the complexity of the grammar to grow as more training data is available. In addition to presenting a fully Bayesian model for the PCFG, we also develop an efficient variational inference procedure. On synthetic data, we recover the correct grammar without having to specify its complexity in advance. We also show that our techniques can be applied to full-scale parsing applications by demonstrating its effectiveness in learning state-split grammars.

The Infinite PCFG Using Hierarchical Dirichlet Processes