Paper:Collins, ACL 2002

Citation

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

Online Version

Here is the online version of the paper.

Summary

In this paper the author describes two algorithms, wich rerank the top N hypotheses from a maximum entropy tagger, and apply them to the task of recovering named-entity boundaries. Since the task at hand can be framed as a tagging task - to tag each word as being either the start of an entity (S), a continuation of an entity (C), or not to be part of ab entity at all (N), the author uses state of the art maximum entropy tagger similar to the one described in Ratnaparkhi EMNLP 1996 as a baseline model. The same Max-ent tagger is used to generate the N=20 most probable segmentations for each input sentence, along with their probabilities. Author's aim is to come up with reranking strategies for the test data candidates in order to improve the precision and recall.

The author considers various global features for each candidate tagged sequence. Most of these features are anchored on entity boundaries in the candidate segmentation. Each candidate tagged sequence $x$, proposed by the Max-ent tagger, is represented by the log probability $L(x)$ from the tagger, as well as the values of the global features $h_{s}(x)$ for $s=1$ ... $m$, where $m$ are the no. of global features. The two algorithms described in the next section blend these two sources of information (global features and log probability) to improve upon a strategy which just takes the candidate from the tagger with the highest score for $L(x)$.

The author has shown that existing reranking methods - boosting and voted perceptron, are useful for a new domain, named-entity tagging. Another contribution is the suggestion of various global features of the candidate segmentations which give improvements on this task.

Brief description of the methods

Pairs of the form $\{s_{i},t_{i}\}$, where each $s_{i}$ is a sentence and each $t_{i}$ is the correct tag sequence for that sentence, serve as the training data. $C(s_{i})=\{x_{i1},x_{i2}...\}$ denotes the set of candidates (top N outputs from the Max-ent tagger) for each $s_{i}$, where $x_{ij}$ is the $j'$th candidate of $i'$th sentence. $Q(x_{ij})$ is the probability that the base model assigns to $x_{ij}$. Hence $L(x_{ij})$=log$Q(x_{ij})$. The set of $m$ global features are represented as $h_{s}(x)$ for $s=1$ ... $m$. The parameters of the model are a vector of $m+1$ parameters, $w=\{w_{0},w_{1}...w_{m}\}$. The ranking function is given as

$F(x,w)=w_{0}L(x)+\sum \limits _{s=1}^{m}w_{s}h_{s}(x)$

The ranking function can also be written as $F(x,w)=w.h(x)$ if $h(x)$ is defined as $\{L(x),h_{1}(x)\ldots h_{m}(x)\}$.

Boosting for ranking

The boosting algorithm in the paper is the one described in Collins 2000, where the method can be considered to be a greedy algorithm for finding the parameters $w$ that minimize the loss function

$Loss(w)=\sum \limits _{i}\sum \limits _{j\geq 2}e^{F(x_{ij},w)-F(x_{i1},w)}$

As an initial step, $w_{0}$ is set to be

$w_{0}=arg{\underset {w}{min}}\sum \limits _{i}\sum \limits _{j\geq 2}e^{w(L(x_{ij})-L(x_{i1}))}$

and all other parameters $w_{s}$ for $s=1$ ... $m$ are set to be zero. The algorithm then proceeds for N iterations. At each iteration, a single feature is chosen, and its weight is updated. Suppose the current parameter values are $w$, and a single feature $k$ is chosen, its weight being updated through an increment $\delta$, i.e., $w_{k}=w_{k}+\delta$. Then the new loss, after this parameter update, will be

$L(k,\delta )=\sum \limits _{i,j\geq 2}e^{-M_{i,j}+\delta (h_{k}(x_{ij})-h_{k}(x_{i1}))}$

where $M_{i,j}=F(x_{i,1},w)-F(x_{ij},w)$. The boosting algorithm chooses the feature/update pair $k^{*},\delta ^{*}$ which is optimal in terms of minimizing the loss function, i.e.,

$(k^{*},\delta ^{*})=arg{\underset {k,\delta }{min}}L(k,\delta )$

and then makes the update $w_{k^{*}}=w_{k^{*}}+\delta ^{*}$.

Voted Perceptron for ranking

The following steps define the perceptron training algorithm for ranking problems.

Define: $F(x,w)=w.h(x)$

Input: Examples $x_{ij}$ with feature vectors $h(x_{ij})$

Initialization: Set parameters $w^{0}=0$

For $i=1\ldots n$

$j=argmax_{j=1...n_{i}}F(x_{ij},w^{i-1})$
If $(j=1)$ Then $w^{i}=w^{i-1}$
         Else $w^{i}=w^{i-1}+h(x_{i1})-h(x_{ij})$

Output: Parameter vectors $w^{i}$ for $i=1\ldots n$

The algorithm maintains a parameter vector $w$, which is initially set to be all zeros. The algorithm then makes a pass over the training set, at each training example storing a parameter vector $w^{i}$ for $i=1\ldots m$. The parameter vector is only modified when a mistake is made on an example. The update here involves adding the difference of the offending examples' representations. In the voted perceptron all parameter vectors $w^{i}$ for $i=1\ldots n$ are stored. Each of these $n$ parameter settings "vote" for a candidate, which is the highest ranking candidate of each parameter setting given by $x_{k}$, where $k=argmax_{j}w^{i}.h(x_{j})$. The candidate with the highest no. of votes is returned as the most likely candidate.

Experimental Result

Following table shows the Precision (P), Recall (R) and F-measure (F) for the three tagging methods. Figures in parantheses are the relative improvements in error rate over the Max-ent model. All figures are percentages.

Related papers

Collins 2000 used boosting for to rerank the output of an existing probabilistic parser and compared with Markov Random fields.