Michael Collins (home)

For an up-to-date list of my publications see my profile on Google scholar

Dissertation

Head-Driven Statistical Models for Natural Language Parsing. PhD Dissertation, University of Pennsylvania, 1999.
Slides from my thesis defence.

Publications

2014

A Spectral Algorithm for Learning Class-Based n-gram Models of Natural Language.

Here

Shay B. Cohen, Karl Stratos, Michael Collins, Dean P. Foster and Lyle Ungar.
Spectral Learning of Latent-Variable PCFGs: Algorithms and Sample Complexity.
In JMLR 2014.
Shay B. Cohen and Michael Collins.
A Provably Correct Learning Algorithm for Latent-Variable PCFGs.
In proceedings of ACL 2014.
Yin-Wen Chang, Alexander M. Rush, Michael Collins, and John DeNero.
A Lagrangian Relaxation Algorithm for Bidirectional Word Alignment.
In proceedings of ACL 2014.
Arvind Neelakantan and Michael Collins.
Learning Dictionaries for Named Entity Recognition using Minimal Supervision.
In proceedings of EACL 2014.

2013

Andrei Simion, Michael Collins, and Clifford Stein.
A Convex Alternative to IBM Model 2.
In proceedings of EMNLP 2013.
Alexander M. Rush, Yin-Wen Chang, and Michael Collins.
Optimal Beam Search for Machine Translation.
In proceedings of EMNLP 2013.
Karl Stratos, Alexander M. Rush, Shay B. Cohen and Michael Collins.
Spectral Learning of Refinement HMMs.
In proceedings of CoNLL 2013.
Shay B. Cohen, Karl Stratos, Michael Collins, Dean P. Foster, and Lyle Ungar.
Experiments with Spectral Learning of Latent-Variable PCFGs.
In proceedings of NAACL 2013.
Shay B. Cohen, Giorgio Satta, and Michael Collins.
Approximate PCFG Parsing Using Tensor Decomposition.
In proceedings of NAACL 2013.

2012

Shay B. Cohen and Michael Collins.
Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs.
In proceedings of NIPS 2012.
Shay B. Cohen, Karl Stratos, Michael Collins, Dean P. Foster, and Lyle Ungar.
Spectral Learning of Latent-Variable PCFGs.
In proceedings of ACL 2012.
Here is a longer version of the paper, which includes proofs and should be more readable (less compressed, cleaner notation) than the ACL paper.
Alexander M. Rush and Michael Collins.
A tutorial on Lagrangian relaxation and dual decomposition for NLP.
In Journal of Artificial Intelligence Research.
Alexander M. Rush, Roi Reichart, Michael Collins and Amir Globerson.
Improved Parsing and POS Tagging Using Inter-Sentence Consistency Constraints.
To appear in proceedings of EMNLP 2012.
Paramveer Dhillon, Jordan Rodu, Michael Collins, Dean P. Foster and Lyle Ungar.
Spectral Dependency Parsing with Latent Variables.
To appear in proceedings of EMNLP 2012.

2011

Yin-Wen Chang and Michael Collins.
Exact Decoding of Phrase-based Translation Models through Lagrangian Relaxation.
To appear in proceedings of EMNLP 2011.
Supplementary material is here
(Similar title, similar motivation, but a very different algorithm from the ACL 2011 paper!)
Alexander M. Rush and Michael Collins.
Dual Decomposition for Natural Language Processing.
Slides for our tutorial at ACL 2011.
Alexander M. Rush and Michael Collins.
Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation.
To appear in proceedings of ACL 2011.

2010

Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag.
Dual Decomposition for Parsing with Non-Projective Head Automata.
In proceedings of EMNLP 2010. (Received Best Paper Award.)

Alexander M. Rush, David Sontag, Michael Collins, and Tommi Jaakkola.
On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing.
In proceedings of EMNLP 2010.

Terry Koo and Michael Collins.
Efficient Third-order Dependency Parsers.
In proceedings of ACL 2010.

Fadi Biadsy, Julia Hirschberg, and Michael Collins.
Dialect Recognition Using a Phone-GMM-Supervector-Based SVM Kernel.
To appear in proceedings of Interspeech 2010.
Shivani Agarwal and Michael Collins.
Maximum Margin Ranking Algorithms for Information Retrieval.
In Proceedings of the 32nd European Conference on Information Retrieval (ECIR), 2010.

2009

Natasha Singh-Miller and Michael Collins.
Learning Label Embeddings for Nearest-Neighbor Multi-class Classification with an Application to Speech Recognition.
In proceedings of NIPS 2009.

Xavier Carreras and Michael Collins.
Non-Projective Parsing for Statistical Machine Translation.
To appear in proceedings of EMNLP 2009.

Jun Suzuki, Hideki Isozaki, Xavier Carreras, and Michael Collins.
An Empirical Study of Semi-supervised Structured Conditional Models for Dependency Parsing.
To appear in proceedings of EMNLP 2009.

Luke Zettlemoyer and Michael Collins.
Learning Context-Dependent Mappings from Sentences to Logical Form.
To appear in proceedings of ACL 2009.

Ariadna Quattoni, Xavier Carreras, Michael Collins, and Trevor Darrell.
An Efficient Projection for L_1,∞ Regularization.
To appear in proceedings of ICML 2009.

2008

Ariadna Quattoni, Michael Collins, and Trevor Darrell.
Transfer Learning for Image Classification with Sparse Prototype Representations.
In Proceedings of CVPR 2008.

Xavier Carreras, Michael Collins, and Terry Koo.
TAG, Dynamic Programming and the Perceptron for Efficient, Feature-rich Parsing.
In Proceedings of CONLL 2008. (Received Best Paper Award.)

Video of an invited talk at ICML 2008, mainly focusing on work described in the CONLL 2008 paper.

Terry Koo, Xavier Carreras, and Michael Collins.
Simple Semi-supervised Dependency Parsing.
In Proceedings of ACL 2008.

Michael Collins, Amir Globerson, Terry Koo, Xavier Carreras, and Peter Bartlett.
Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks.
To appear in JMLR (the paper linked here is the submission version, the final version will be posted shortly).
This paper extends the ICML 2007 and NIPS 2004 papers on EG algorithms with additional proofs and experiments.

2007

Natasha Singh-Miller, Michael Collins, and Timothy J. Hazen. 2007.
Dimensionality Reduction for Speech Recognition using Neighborhood Components Analysis.
In Proceedings of Interspeech 2007 (ICSLP 2007).

Amir Globerson, Terry Koo, Xavier Carreras, and Michael Collins. 2007.
Exponentiated Gradient Algorithms for Log-Linear Structured Prediction.
In proceedings of ICML 2007.
See the JMLR 2008 paper listed above for new work on this topic.

Terry Koo, Amir Globerson, Xavier Carreras, and Michael Collins. 2007.
Structured Prediction Models via the Matrix-Tree Theorem.
In proceedings of EMNLP-CoNLL 2007.

Chao Wang, Michael Collins, and Philipp Koehn. 2007.
Chinese Syntactic Reordering for Statistical Machine Translation.
In proceedings of EMNLP-CoNLL 2007.

Luke Zettlemoyer and Michael Collins. 2007.
Online Learning of Relaxed CCG Grammars for Parsing to Logical Form.
In proceedings of EMNLP-CoNLL 2007.

Ariadna Quattoni, Michael Collins, and Trevor Darrell. 2007.
Learning Visual Representations using Images with Captions.
In proceedings of CVPR 2007.

Natasha Singh-Miller and Michael Collins. 2007.
Trigger-based Language Modeling using a Loss-sensitive Perceptron Algorithm.
In proceedings of ICASSP 2007.

Brian Roark, Murat Saraclar, and Michael Collins. 2007.
Discriminative n-gram language modeling.
Computer Speech and Language, 21(2):373-392.
(Follow this link for a preliminary version; the final journal version may differ slightly in typesetting etc.)

Ariadna Quattoni, Sybor Wang, Louis-Philippe Morency, Michael Collins, and Trevor Darrell. 2007.
Hidden Conditional Random Fields.
To appear in IEEE Transactions on Pattern Analysis and Machine Intelligence.

2006

Brooke Cowan, Ivona Kucerova, and Michael Collins.
A Discriminative Model for Tree-to-Tree Translation.
In proceedings of EMNLP 2006.

2005

Brooke Cowan and Michael Collins.
Morphology and Reranking for the Statistical Parsing of Spanish.
In proceedings of EMNLP 2005.

Terry Koo and Michael Collins.
Hidden-Variable Models for Discriminative Reranking.
In proceedings of EMNLP 2005.

Luke S. Zettlemoyer and Michael Collins.
Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars.
In proceedings of UAI 2005. (Received Best Paper Award.)

Michael Collins, Philipp Koehn, and Ivona Kucerova.
Clause Restructuring for Statistical Machine Translation.
In proceedings of ACL 2005.

Michael Collins, Brian Roark, and Murat Saraclar.
Discriminative Syntactic Language Modeling for Speech Recognition.
In proceedings of ACL 2005.

Michael Collins and Terry Koo.
Discriminative Reranking for Natural Language Parsing. (gzipped version)
Computational Linguistics 31(1):25-69.
(This is a preliminary version; the final journal version may differ slightly in typesetting etc.)

2004

Peter Bartlett, Michael Collins, Ben Taskar, and David McAllester.
Exponentiated gradient algorithms for large-margin structured classification.
In proceedings of NIPS 2004.
An older version of this paper, which has proofs
Slides from a talk given at CONLL 2006

Ariadna Quattoni, Michael Collins, and Trevor Darrell.
Conditional Random Fields for Object Recognition.
In proceedings of NIPS 2004.

David McAllester, Michael Collins and Fernando Pereira. 2004.
Case-factor diagrams for structured probabilistic modeling.
UAI 2004. (Received Best Paper Award.)

Ben Taskar, Dan Klein, Michael Collins, Daphne Koller, and Christopher Manning.
Max-Margin Parsing.
EMNLP 2004. (Received Best Paper Award.)

Michael Collins and Brian Roark.
Incremental parsing with the Perceptron algorithm.
ACL 2004.

Brian Roark, Murat Saraclar, Michael Collins, and Mark Johnson.
Discriminative language modeling with conditional random fields and the perceptron algorithm.
ACL 2004.

Brian Roark, Murat Saraclar, and Michael Collins.
Corrective language modeling for large vocabulary ASR with the perceptron algorithm.
ICASSP 2004.

Michael Collins. 2004.
Parameter Estimation for Statistical Parsing Models: Theory and Practice of Distribution-Free Methods.
Book chapter in Harry Bunt, John Carroll and Giorgio Satta, editors, New Developments in Parsing Technology, Kluwer. (Revised version of the paper that appeared at IWPT 2001.)

2003

Michael Collins. 2003.
Head-Driven Statistical Models for Natural Language Parsing.
In Computational Linguistics.
(This is a preliminary version; the final journal version may differ slightly in typesetting etc.)

2003 Talks

COLT 2003 Tutorial Slides. .ps, .pdf.

2002

Michael Collins.
Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms.
EMNLP 2002. (Received Best Paper Award.)
(This paper includes theorems and proofs which apply to the algorithms in the ACL 2002 papers.)
Michael Collins and Nigel Duffy.
New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron
ACL 2002.

Michael Collins.
Ranking Algorithms for Named-Entity Extraction: Boosting and the Voted Perceptron.
ACL 2002.

2002 Talks

UAI 2002 Tutorial Slides. .ps, .pdf.
Slides for a talk on the EMNLP 2002 paper.
Slides for a talk on the material in the two ACL 2002 papers.

2001

Michael Collins and Nigel Duffy.
Convolution Kernels for Natural Language.
NIPS 2001.

Michael Collins, Sanjoy Dasgupta and Robert E. Schapire.
A Generalization of Principal Component Analysis to the Exponential Family.
NIPS 2001.

Michael Collins.
Parameter Estimation for Statistical Parsing Models: Theory and Practice of Distribution-Free Methods .
Paper written to accompany invited talk at IWPT 2001.

Michael Collins, Robert E. Schapire and Yoram Singer. 2001.
Logistic Regression, AdaBoost and Bregman Distances.
In Machine Learning, Special Issue on New Methods for Model Selection and Model Combination. (Journal version of COLT 2000 paper.)

2000

Michael Collins.
Discriminative Reranking for Natural Language Parsing.
ICML 2000.

Michael Collins, Robert E. Schapire and Yoram Singer.
Logistic Regression, AdaBoost and Bregman Distances.
COLT 2000.

Steven Abney, Michael Collins and Amit Singhal.
Answer Extraction.
ANLP 2000.

Regina Barzilay, Michael Collins, Julia Hirschberg and Steve Whittaker.
The Rules Behind Roles: Identifying Speaker Role in Radio Broadcasts.
AAAI 2000.

1999

Michael Collins and Yoram Singer.
Unsupervised Models for Named Entity Classification.
EMNLP/VLC-99.

Michael Collins, Jan Hajic, Lance Ramshaw and Christoph Tillmann.
A Statistical Parser for Czech.
ACL 99.

1995-1998

Michael Collins and Scott Miller. 1998.
Semantic Tagging using a Probabilistic Context Free Grammar.
In Proceedings of the Sixth Workshop on Very Large Corpora.

Michael Collins. 1997.
Three Generative, Lexicalised Models for Statistical Parsing.
Proceedings of the 35th Annual Meeting of the ACL (jointly with the 8th Conference of the EACL), Madrid.

Michael Collins. 1996.
A New Statistical Parser Based on Bigram Lexical Dependencies.
Proceedings of the 34th Annual Meeting of the ACL, Santa Cruz.

Michael Collins and James Brooks. 1995.
Prepositional Phrase Attachment through a Backed-off Model.
Proceedings of the Third Workshop on Very Large Corpora.

Other Papers

Michael Collins and Nigel Duffy. 2000. Parsing with a Single Neuron: Convolution Kernels for Natural Language Problems Draft version: please do not cite or distribute.

Parsing the WSJ Penn Treebank

Identifying head-words in the WSJ Penn treebank (code used in the ACL96/97 parsing models)
Scoring code for the Wall Street Journal Penn treebank, written by Satoshi Sekine (New York University)
Parser output for section 0 of the treebank

Talks

Slides for my talk at ACL/EACL97

Other Papers

I wrote a paper on the EM (Expectation Maximization) Algorithm as one of my PhD requirements. It's a review of three papers: (Dempster, Laird and Rubin 1977), (Wu 1983), and (Jamshidian and Jennrich 1993).

Some Links

Computational Linguistics