Publications

2008

An asymptotic analysis of generative, discriminative, and pseudolikelihood estimators.
Percy Liang, Michael I. Jordan.
International Conference on Machine Learning (ICML), 2008. Best student paper award.

Statistical and computational concerns have motivated parameter estimators based on various forms of likelihood, e.g., joint, conditional, and pseudolikelihood. In this paper, we present a unified framework for studying these estimators, which allows us to compare their relative (statistical) efficiencies. Our asymptotic analysis suggests that modeling more of the data tends to reduce variance, but at the cost of being more sensitive to model misspecification. We present experiments validating our analysis.

Derive general expression for the asymptotic risk of composite likelihood estimators in exponential families.
This allows us to compare the various estimators.
```
@inproceedings{liang08asymptotics,
  title = {An Asymptotic Analysis of Generative, Discriminative, and Pseudolikelihood Estimators},
  author = {P. Liang and M. I. Jordan},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2008},
}
```
[abstract] [brief] [bib] [paper] [slides]
Structure compilation: trading structure for features.
Percy Liang, Hal Daume, Dan Klein.
International Conference on Machine Learning (ICML), 2008.

Structured models often achieve excellent performance but can be slow at test time. We investigate structure compilation, where we replace structure with features, which are often computationally simpler but unfortunately statistically more complex. We analyze this tradeoff theoretically and empirically on three natural language processing tasks. We also introduce a simple method to transfer predictive power from structure to features via unlabeled data, while incurring a minimal statistical penalty.

How much do we lose by throwing out edge features in CRFs and adding node features?
Studies the approximation, estimation, computational aspects of the tradeoff.
```
@inproceedings{liang08structure,
  title = {Structure Compilation: Trading Structure for Features},
  author = {P. Liang and H. Daume and D. Klein},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2008},
}
```
[abstract] [brief] [bib] [paper] [slides]
Analyzing the errors of unsupervised learning.
Percy Liang, Dan Klein.
Association for Computational Linguistics (ACL), 2008.

We identify four types of errors that unsupervised induction systems make and study each one in turn. Our contributions include (1) using a meta-model to analyze the incorrect biases of a model in a systematic way, (2) providing an efficient and robust method of measuring distance between two parameter settings of a model, and (3) showing that local optima issues which typically plague EM can be somewhat alleviated by increasing the number of training examples. We conduct our analyses on three models: the HMM, the PCFG, and a simple dependency model.

Error decomposition: approximation, identifiability, estimation, optimization errors.
Used meta-model to analyze approximation error.
Empirically observed that more data reduces optimization error.
```
@inproceedings{liang08errors,
  title = {Analyzing the Errors of Unsupervised Learning},
  author = {P. Liang and D. Klein},
  booktitle = {Association for Computational Linguistics (ACL)},
  year = {2008},
}
```
[abstract] [brief] [bib] [paper] [slides]
Learning bilingual lexicons from monolingual corpora.
Aria Haghighi, Percy Liang, Taylor Berg-Kirkpatrick, Dan Klein.
Association for Computational Linguistics (ACL), 2008.

We present a method for learning bilingual translation lexicons from monolingual corpora. Word types in each language are characterized by purely monolingual features, such as context counts and orthographic substrings. Translations are induced using a generative model based on canonical correlation analysis, which explains the monolingual lexicons in terms of latent matchings. We show that high-precision lexicons can be learned in a variety of language pairs and from a range of corpus types.

By using CCA, can do word alignment without the usual sentence-aligned corpora.
```
@inproceedings{haghighi08lexicon,
  title = {Learning Bilingual Lexicons from Monolingual Corpora},
  author = {A. Haghighi and P. Liang and T. Berg-Kirkpatrick and D. Klein},
  booktitle = {Association for Computational Linguistics (ACL)},
  year = {2008},
}
```
[abstract] [brief] [bib] [paper]
Agreement-based learning.
Percy Liang, Dan Klein, Michael I. Jordan.
Advances in Neural Information Processing Systems (NIPS), 2008.

The learning of probabilistic models with many hidden variables and non-decomposable dependencies is an important and challenging problem. In contrast to traditional approaches based on approximate inference in a single intractable model, our approach is to train a set of tractable submodels by encouraging them to agree on the hidden variables. This allows us to capture non-decomposable aspects of the data while still maintaining tractability. We propose an objective function for our approach, derive EM-style algorithms for parameter estimation, and demonstrate their effectiveness on three challenging real-world learning tasks.

Setting: unsupervised learning.
Alternative to approximate inference: make two tractable models and train them to agree.
Advantage: maintain existing tractable inference procedures as black-boxes.
```
@inproceedings{liang08agreement,
  title = {Agreement-Based Learning},
  author = {P. Liang and D. Klein and M. I. Jordan},
  booktitle = {Advances in Neural Information Processing Systems (NIPS)},
  year = {2008},
}
```
[abstract] [brief] [bib] [paper] [poster]
A probabilistic approach to language change.
Alexandre Bouchard-Côté, Percy Liang, Tom Griffiths, Dan Klein.
Advances in Neural Information Processing Systems (NIPS), 2008.

We present a probabilistic approach to language change in which word forms are represented by phoneme sequences that undergo stochastic edits along the branches of a phylogenetic tree. This framework combines the advantages of the classical comparative method with the robustness of corpus-based probabilistic models. We use this framework to explore the consequences of two different schemes for defining probabilistic models of phonological change, evaluating these schemes by reconstructing ancient word forms of Romance languages. The result is an efficient inference procedure for automatically inferring ancient word forms from modern languages, which can be generalized to support inferences about linguistic phylogenies.

Feature-based generative model of phonemes of words in a phylogeny of languages.
```
@inproceedings{bouchard08language,
  title = {A Probabilistic Approach to Language Change},
  author = {A. Bouchard-Côté and P. Liang and T. Griffiths and D. Klein},
  booktitle = {Advances in Neural Information Processing Systems (NIPS)},
  year = {2008},
}
```
[abstract] [brief] [bib] [paper] [poster]

2007

Structured Bayesian nonparametric models with variational inference (tutorial).
Percy Liang, Dan Klein.
Association for Computational Linguistics (ACL), 2007.
[bib] [paper] [slides]

A permutation-augmented sampler for Dirichlet process mixture models.
Percy Liang, Michael I. Jordan, Ben Taskar.
International Conference on Machine Learning (ICML), 2007.

We introduce a new inference algorithm for Dirichlet process mixture models. While Gibbs sampling and variational methods focus on local moves, the new algorithm makes more global moves. This is done by introducing a permutation of the data points as an auxiliary variable. The algorithm is a blocked sampler which alternates between sampling the clustering and sampling the permutation. The key to the efficiency of this approach is that it is possible to use dynamic programming to consider all exponentially many clusterings consistent with a given permutation. We also show that random projections can be used to effectively sample the permutation. The result is a stochastic hill-climbing algorithm that yields burn-in times significantly smaller than those of collapsed Gibbs sampling.

Task: clustering.
Idea: conditioned on a permutation of the data points, one can consider all possible clusterings of those data points which are consistent with the permutation using dynamic programming.
Idea: if data are ordered, can cluster using dynamic programming.
Let this ordering be a random auxiliary variable and we get a sampler.
```
@inproceedings{liang07permdp,
  title = {A permutation-augmented sampler for {D}irichlet process mixture models},
  author = {P. Liang and M. I. Jordan and B. Taskar},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2007},
}
```
[abstract] [brief] [bib] [paper] [slides]
The infinite PCFG using hierarchical Dirichlet processes.
Percy Liang, Slav Petrov, Michael I. Jordan, Dan Klein.
Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL), 2007.

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.

A PCFG with an infinite number of states.
Learning: variational inference.
```
@inproceedings{liang07infpcfg,
  title = {The Infinite {PCFG} using Hierarchical {D}irichlet Processes},
  author = {P. Liang and S. Petrov and M. I. Jordan and D. Klein},
  booktitle = {Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL)},
  year = {2007},
}
```
[abstract] [brief] [bib] [paper] [slides]
A probabilistic approach to diachronic phonology.
Alexandre Bouchard-Côté, Percy Liang, Tom Griffiths, Dan Klein.
Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL), 2007.

We present a probabilistic model of diachronic phonology in which individual word forms undergo stochastic edits along the branches of a phylogenetic tree. Our approach allows us to achieve three goals with a single unified model: (1) reconstruction of both ancient and modern word forms, (2) discovery of general phonological changes, and (3) selection among different phylogenies. We learn our model using a Monte Carlo EM algorithm and present quantitative results validating the model.

Generative model of phonemes of words in a phylogeny of languages
```
@inproceedings{bouchard07diachronic,
  title = {A Probabilistic Approach to Diachronic Phonology},
  author = {A. Bouchard-Côté and P. Liang and T. Griffiths and D. Klein},
  booktitle = {Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL)},
  year = {2007},
}
```
[abstract] [brief] [bib] [paper]

2006

An end-to-end discriminative approach to machine translation.
Percy Liang, Alexandre Bouchard-Côté, Dan Klein, Ben Taskar.
International Conference on Computational Linguistics and Association for Computational Linguistics (COLING/ACL), 2006.

We present a perceptron-style discriminative approach to machine translation in which large feature sets can be exploited. Unlike discriminative reranking approaches, our system can take advantage of learned features in all stages of decoding. We first discuss several challenges to error-driven discriminative approaches. In particular, we explore different ways of updating parameters given a training example. We find that making frequent but smaller updates is preferable to making fewer but larger updates. Then, we discuss an array of features and show both how they quantitatively increase BLEU score and how they qualitatively interact on specific examples. One particular feature we investigate is a novel way to introduce learning into the initial phrase extraction process, which has previously been entirely heuristic.

Task: machine translation.
Idea: treat machine translation as a structured classification task (learn a map from input sentence to output sentence). Use a Perceptron-like algorithm: decode and update towards maximum BLEU scoring translation on the n-best list.
```
@inproceedings{liang06discrimative,
  title = {An End-to-End Discriminative Approach to Machine Translation},
  author = {P. Liang and A. Bouchard-Côté and D. Klein and B. Taskar},
  booktitle = {International Conference on Computational Linguistics and Association for Computational Linguistics (COLING/ACL)},
  year = {2006},
}
```
[abstract] [brief] [bib] [paper] [slides]
Alignment by agreement.
Percy Liang, Ben Taskar, Dan Klein.
Human Language Technology and North American Association for Computational Linguistics (HLT/NAACL), 2006.

We present an unsupervised approach to symmetric word alignment in which two simple asymmetric models are trained jointly to maximize a combination of data likelihood and agreement between the models. Compared to the standard practice of intersecting predictions of independently-trained models, joint training provides a 32% reduction in AER. Moreover, a simple and efficient pair of HMM aligners provides a 29% reduction in AER over symmetrized IBM model 4 predictions.

Task: unsupervised word alignment.
Idea: Jointly train two HMM models (one in each direction) to encourage agreement. Uses a simple EM-like algorithm for training.
Result: performance competitive with supervised methods (4.9 AER on Hansards).
```
@inproceedings{liang06alignment,
  title = {Alignment by Agreement},
  author = {P. Liang and B. Taskar and D. Klein},
  booktitle = {Human Language Technology and North American Association for Computational Linguistics (HLT/NAACL)},
  year = {2006},
}
```
[abstract] [brief] [bib] [paper] [slides] [code]

2005

Semi-supervised learning for natural language.
Percy Liang.
Massachusetts Institute of Technology, 2005.

Task: named-entity recognition and Chinese word segmentation
Idea: create features based on unlabeled data to use in Perceptron learning in Markov or semi-Markov models
```
@mastersthesis{liang05meng,
  school = {Massachusetts Institute of Technology},
  title = {Semi-Supervised Learning for Natural Language},
  author = {P. Liang},
  year = {2005},
}
```
[brief] [bib] [paper]
A data structure for maintaining acyclicity in hypergraphs.
Percy Liang, Nathan Srebro.
2005.

We introduce the first definition of hyperacyclicity for hypergraphs, a generalization of acyclicity in graphs.
We provide a dynamic data structure for maintaining hyperacyclicity, a generalization of Tarjan's Union-Find algorithm.
```
@misc{liang05hypercycle,
  title = {A Data Structure for Maintaining Acyclicity in Hypergraphs},
  author = {P. Liang and N. Srebro},
  year = {2005},
}
```
[brief] [bib] [paper] [code]

Linear programming in bounded tree-width Markov networks.
Percy Liang, Nathan Srebro.
Mathematical Programing for Data Mining and Machine Learning Workshop at McMaster University, 2005.
[bib] [slides] [code]

Efficient geometric algorithms for parsing in two dimensions.
Percy Liang, Mukund Narasimhan, Michael Shilman, Paul Viola.
International Conference on Document Analysis and Recognition (ICDAR), 2005.

In parsing sequences using dynamic programming, the subproblems are continguous subsequences (quadratic in number of terminals). In parsing documents or images, the subproblems would be subsets of the terminals (exponential in number of terminals). We introduce (and unify) several ways to constrain these subsets using the geometric structure of the terminals.
```
@inproceedings{liang05geometric,
  author = {P. Liang and M. Narasimhan and M. Shilman and P. Viola},
  title = {Efficient Geometric Algorithms for Parsing in Two Dimensions},
  booktitle = {International Conference on Document Analysis and Recognition (ICDAR)},
  year = {2005},
}
```
[brief] [bib] [paper]

2004

Methods and experiments with bounded tree-width Markov networks.
Percy Liang, Nathan Srebro.
Massachusetts Institute of Technology Technical Report, 2004.

Use a greedy procedure to find the maximum likelihood (or MDL) bounded tree-width Markov network (for tree-width 1, equivalent to Chow-Liu maximum spanning trees).
```
@techreport{liang04markov,
  institution = {Massachusetts Institute of Technology},
  author = {P. Liang and N. Srebro},
  title = {Methods and Experiments With Bounded Tree-width {M}arkov Networks},
  year = {2004},
}
```
[brief] [bib] [paper] [code]

2003

How much of a hypertree can be captured by windmills?
Percy Liang, Nathan Srebro.
Massachusetts Institute of Technology Technical Report, 2003.

Use linear programming to find worst case inputs to a dynamic program in order to explore the tightness of a bound for approximating maximum weight hypertrees with windmill farms.
```
@techreport{liang03maxwmfarm,
  institution = {Massachusetts Institute of Technology},
  author = {P. Liang and N. Srebro},
  title = {How Much Of A Hypertree Can Be Captured By Windmills?},
  year = {2003},
}
```
[brief] [bib] [paper] [code]