View source for Chelba and Acero, EMNLP 2004: Adaptation of Maximum Entropy Capitalizer: Little Data Can Help A Lot

== Citation ==

C. Chelba and A. Acero. '''Adaptation of maximum entropy capitalizer: little data can help a lot''', ''Proceedings of EMNLP'', 2004.

== Online Version ==

[http://acl.ldc.upenn.edu/acl2004/emnlp/pdf/Chelba.pdf PDF version]

== Summary ==

This [[Category::paper]] takes a maximum entropy Markov model (MEMM) for capitalization trained with a large amount of data for one domain, and adapts it to another domain with a relatively small amount of data.

=== Capitalization ===

This problem addressed by this paper is automatic [[AddressesProblem::capitalization]] of uniformly cased text, which can be useful in the post-processing of speech recognition transcripts. This problem can be considered as a task of sequence labeling: for each word in a sequence, we need to decide its capitalization among the following cases:

* LOC: lower case
* CAP: first letter capitalized
* AUC: all upper case
* MXC: mixed case (e.g. MaxEnt)
* PNC: punctuation

A baseline approach is 1-gram capitalization: for each word, choose the most frequent capitalization seen in the training corpus. As an overriding rule, the first word of a sentence is always capitalized.

=== MEMMs for capitalization ===

A popular sequential model for capitalization is the [[UsesMethod::Maximum Entropy Markov Model]] (MEMM). In an MEMM, the capitalization label <math>y_i</math> for the <math>i</math>-th word <math>w_i</math> depends on several words around <math>w_i</math> (including <math>w_i</math> itself), and the capitalization labels of several previous words. In this paper, <math>y_i</math> is chosen to depend on <math>\{ w_{i-1}, w_i, w_{i+1}, y_{i-2}, y_{i-1} \}</math>, which are collectively denoted by <math>x_i</math> (in the paper the <math>x</math> has an underline, which is omitted here).

The conditional probability of the capitalization label <math>y</math> given the observation <math>x</math> is defined as:

<math>p_\Lambda(y|x) = Z^{-1}(x;\Lambda) \cdot \exp \left[ \sum_{i=1}^F \lambda_i f_i(x,y) \right]</math>

<math>Z^{-1}(x;\Lambda) = \sum_y \exp \left[ \sum_{i=1}^F \lambda_i f_i(x,y) \right]</math>

In these formulas, <math>f_i(x,y)</math> are features of the union of <math>x</math> and <math>y</math>. In this paper, the features are all binary-valued. They encode the identity of the labels and words, as well the sub-word information such as prefixes and suffixes. The <math>\lambda_i</math> are the weights of the features, and need to be trained.

=== Training an MEMM ===

The MEMM is usually trained for maximum conditional likelihood of the training data. One can also perform [[UsesMethod::maximum a posteriori]] (MAP) training by imposing a zero-mean diagonal Gaussian prior <math>\Lambda \sim \mathcal{N}(0, \text{diag}(\sigma_i^2))</math> on the feature weights, which results in a quadratic regularization term in the objective function:

<math>L(\Lambda) = \sum_{x,y} \tilde{p}(x,y) \log p_\Lambda(y|x) - \sum_{i=1}^F \frac{\lambda_i^2}{2\sigma_i^2} + \text{const}(\Lambda)</math>

where <math>\tilde{p}</math> represents the empirical distribution (i.e. that of the training data), and <math>p_\Lambda</math> represents the distribution given by the model.

This objective function can be maximized with the [[UsesMethod::Improved Iterative Scaling]] (IIS) algorithm. In each iteration of this algorithm, <math>\lambda_i</math> is increased by <math>\delta_i</math>, which is determined by the following equation:

<math>\sum_{x,y} \tilde{p}(x,y) f_i(x,y) - \frac{\lambda_i}{\sigma_i^2} = \frac{\delta_i}{\sigma_i^2} + \sum_{x,y} \tilde{p}(x) p_\Lambda(y|x) f_i(x,y) \exp(\delta_i f^\#(x,y))</math>

where <math>f^\#(x,y)</math> is the total number of features activated by <math>(x,y)</math>.

=== MAP adaptation of MEMMs ===

An MEMM trained for one domain usually works less well for a different domain. Even if we have only a little data of the new domain, it may be beneficial to adapt the MEMM to the new domain. This can be realized by training on the new-domain data with a Gaussian prior centered at the parameters of the old model <math>\Lambda \sim \mathcal{N}(\Lambda^0, \text{diag}(\sigma_i^2))</math>.

The training procedure with this new prior is almost the same as that with a zero-mean prior. The objective function becomes:

<math>L(\Lambda) = \sum_{x,y} \tilde{p}(x,y) \log p_\Lambda(y|x) - \sum_{i=1}^F \frac{(\lambda_i - \lambda_i^0)^2}{2\sigma_i^2} + \text{const}(\Lambda)</math>

And the increment <math>\delta_i</math> in each iteration is determined by:

<math>\sum_{x,y} \tilde{p}(x,y) f_i(x,y) - \frac{\lambda_i - \lambda_i^0}{\sigma_i^2} = \frac{\delta_i}{\sigma_i^2} + \sum_{x,y} \tilde{p}(x) p_\Lambda(y|x) f_i(x,y) \exp(\delta_i f^\#(x,y))</math>

== Experiments ==

=== Dataset ===

{| border=1 cellpadding=3 align=right
! &nbsp;
! Training
! Develop.
! Testing
|-
! WSJ
| align=center | 20M
| align=center | &nbsp;
| align=center | &nbsp;
|-
! CNN
| align=center | 73k
| align=center | 73k
| align=center | 73k
|-
! ABC
| align=center | 25k
| align=center | 8k
| align=center | 8k
|}

Three data sets are used:

* The [[UsesDataset::Wall Street Journal]] is used as in-domain training data.
* Two broadcast news datasets (CNN and ABC) are used as out-of-domain data. Both of the two are divided into training, development and test data. The development data is used for tuning parameters such as the covariance of the prior.

The sizes of the datasets (in words) are listed in the table on the right.

=== Criterion ===

The evaluation criterion is the labeling error rate.

=== Results ===

[[File:MEMM_cap_result.png|right]]

Evaluation is carried out on the CNN and ABC test sets. Four systems are evaluated: the 1-gram capitalizer (baseline), the unadapted MEMM trained on WSJ, and two MEMMs adapted from WSJ to CNN and ABC. The error rates are shown in the table to the right. Two conclusions can be drawn:

* MEMM performs better than the 1-gram baseline.
* Adapted MEMMs perform best for their target domain.

== [[User:yunwang|Maigo]]'s Comment ==

To fully justify adaptation, I think it's still necessary to compare an adapted MEMM with an MEMM trained solely on the data of the second domain (even though the amount of data is small). Unfortunately the authors didn't give the results for the second scenario.