Discriminative training methods for hidden Markov models

Published 1 January 2002Open access

Michael Collins

Citations1,889

TL;DR

Experimental results on part-of-speech tagging and base noun phrase chunking are given, in both cases showing improvements over results for a maximum-entropy tagger.

Abstract

We describe new algorithms for training tagging models, as an alternative to maximum-entropy models or conditional random fields (CRFs). The algorithms rely on Viterbi decoding of training examples, combined with simple additive updates. We describe theory justifying the algorithms through a modification of the proof of convergence of the perceptron algorithm for classification problems. We give experimental results on part-of-speech tagging and base noun phrase chunking, in both cases showing improvements over results for a maximum-entropy tagger.

Keywords

Computer Science

ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

12,978 Citations2001John Lafferty, Andrew McCallum +1 more

This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.

View PDF

Psychological ReviewThe perceptron: A probabilistic model for information storage and organization in the brain.

11,746 Citations1958Frank F. Rosenblatt

This article will be concerned primarily with the second and third questions, which are still subject to a vast amount of speculation, and where the few relevant facts currently supplied by neurophysiology have not yet been integrated into an acceptable theory.

Building a Large Annotated Corpus of English: The Penn Treebank

7,528 Citations1993Mitchell P. Marcus

Transformation-based error-driven learning and natural language processing: a case study in part-of-speech tagging

1,531 Citations1995Eric Brill

This paper describes a simple rule-based approach to automated learning of linguistic knowledge that has been shown for a number of tasks to capture information in a clearer and more direct fashion without a compromise in performance.

Maximum Entropy Markov Models for Information Extraction and Segmentation

1,333 Citations2000Andrew McCallum, Dayne Freitag +1 more

A new Markovian sequence model is presented that allows observations to be represented as arbitrary overlapping features (such as word, capitalization, formatting, part-of-speech), and defines the conditional probability of state sequences given observation sequences.

Maximum Entropy Model for Part-Of-Speech Tagging

1,276 Citations1996Adwait Ratnaparkhi

A statistical model which trains from a corpus annotated with Part Of Speech tags and assigns them to previously unseen text with state of the art accuracy and discusses the corpus consistency problems discovered during the implementation of these features.

Text, speech and language technologyText Chunking Using Transformation-Based Learning

1,257 Citations1999Lance Ramshaw, Mitchell P. Marcus

This work has shown that the transformation-based learning approach can be applied at a higher level of textual interpretation for locating chunks in the tagged text, including non-recursive “baseNP” chunks.

Large margin classification using the perceptron algorithm

1,099 Citations1998Yoav Freund, Robert E. Schapire

The MIT Press eBooksConvolution Kernels for Natural Language

812 Citations2002Michael J. Collins, Nigel Duffy

It is shown how a kernel over trees can be applied to parsing using the voted perceptron algorithm, and experimental results on the ATIS corpus of parse trees are given.

New ranking algorithms for parsing and tagging

505 Citations2001Michael Collins, Nigel Duffy

New learning algorithms for natural language processing based on the perceptron algorithm are introduced, showing how the algorithms can be efficiently applied to exponential sized representations of parse trees, such as the "all subtrees" (DOP) representation described by (Bod 1998).

View PDF