A New Perceptron Algorithm for Sequence Labeling with Non-Local Features

Jun’ichi Kazama, Kentaro TorisawaEMNLP 2007

TL;DR

This paper introduces a novel perceptron algorithm that effectively incorporates "non-local" features into sequence labeling tasks, overcoming limitations of existing methods that are restricted to local dependencies. The proposed algorithm achieves guaranteed convergence and demonstrates improved performance on Named Entity Recognition (NER) tasks.

What Problem Does This Paper Address?

Sequence labeling tasks, such as Named Entity Recognition (NER) and Part-of-Speech (POS) tagging, are crucial in Natural Language Processing (NLP). While discriminative models like Conditional Random Fields (CRFs) and perceptrons have achieved great success, they are typically limited to using "local" features. These features only depend on a small, fixed window of labels (e.g., the previous and current label). This limitation prevents the use of "non-local" features, which can capture dependencies across larger spans of the sequence or even the entire document. Examples of such useful non-local features include the observation that "same phrases in a document do not have different entity classes." Existing methods that attempt to incorporate non-local features often impose constraints on the types of features that can be used or require complex training procedures like Gibbs sampling or integer linear programming. This paper aims to provide a unified framework that can handle all types of non-local features alongside local ones, while ensuring efficient and guaranteed training.

Methods

The core contribution is a new perceptron algorithm designed to handle both local and non-local features. The authors extend the standard Collins' perceptron algorithm by introducing a margin-based update rule. The key challenge addressed is the intractability of exact inference when non-local features are present, which prevents the direct use of standard Viterbi or forward-backward algorithms.

The proposed solution involves a two-stage approach during training:

  1. Candidate Generation: The algorithm first generates a set of "n-best" candidate label sequences using only local features. This step is efficient and can be performed using an A* search.
  2. Scoring and Updating: The algorithm then re-scores these n-best candidates using the full feature set (both local and non-local) to find a candidate that violates the margin condition. This allows for updates to the weights of both local and non-local features.

A crucial aspect is the "aggressive" update of local features when the local model is not sufficiently good, ensuring that the correct answer is at least among the n-best candidates. This "proposed algorithm" (Algorithm 4.2) is shown to have guaranteed convergence. Additionally, the authors incorporate a "BPM initialization" technique, inspired by Bayes Point Machines, to mitigate the impact of training example order by shuffling and averaging weights from multiple passes.

Datasets

The primary dataset used for evaluation is the CoNLL 2003 English Named Entity Recognition (NER) shared task dataset. This dataset consists of newspaper articles annotated with four entity classes: PER (Person), LOC (Location), ORG (Organization), and MISC (Miscellaneous). The authors also mention using POS/chunk tags from the CoNLL 2003 dataset and, for a more rigorous evaluation, tags generated by TagChunk.

Key Insights and Ideas

  • Unified Framework for Non-Local Features: The most significant insight is the development of a perceptron algorithm that can seamlessly integrate any type of non-local feature, overcoming the limitations of previous methods that were feature-type constrained.
  • Guaranteed Convergence with Non-Local Features: The algorithm's design, particularly the margin-based updates and the two-stage candidate generation/scoring, ensures convergence even with complex non-local dependencies, which is a major theoretical advantage.
  • The Importance of Local Model Quality: The "aggressive" update of local features when the local model is weak is a key insight. It ensures that the correct answer is likely to be within the n-best candidates, making the subsequent non-local feature updates effective.
  • n-best Search as a Practical Solution: Using an n-best list generated by a local model as a proxy for exact inference is a practical and effective strategy for handling the computational complexity introduced by non-local features.
  • BPM Initialization for Robustness: The BPM initialization technique, while computationally more expensive than a single pass, is shown to improve robustness by mitigating the order-dependency of perceptron training.

Key Results

  • Improved NER Performance: The proposed algorithm with non-local features improved the F1 score on the CoNLL 2003 test set by 0.66 points over the margin perceptron with only local features.
  • Effectiveness of the "Candidate Algorithm": The initial "candidate algorithm" (Algorithm 4.1) without the aggressive local update showed limited improvement, highlighting the necessity of the modification in Algorithm 4.2.
  • Impact of n' (n-best size): Using a larger n' for testing than for training yielded higher performance, with the best improvement of 0.74 points achieved at n'=6400.
  • Comparison to Related Work: The proposed algorithm achieved performance comparable to or better than some related work (e.g., Finkel et al., 2005) when using the same POS/chunk tags. When using TagChunk tags, the performance became higher than Finkel et al. and comparable to Krishnan and Manning (2006).
  • Efficiency: The proposed algorithm was significantly faster than re-ranking approaches that use cross-validation training, while achieving similar or better performance.

Limitations and Future Work

  • Performance Gap with CRF: Despite improvements, the proposed algorithm's performance was still worse than a baseline CRF model with only local features on the CoNLL 2003 dataset. The authors suggest this might indicate limitations of perceptron-based methods, but also room for improvement in their algorithm.
  • Tuning Parameters: The algorithm has tunable parameters (local margin, total margin, n for n-best search) that require careful tuning.
  • BPM Initialization Effectiveness: While BPM initialization showed some benefits, its effect was not conclusive across all experiments, suggesting a need for further investigation.
  • Future Work: The authors express interest in investigating various new types of non-local features using their proposed algorithm. They also note that the way local and non-local updates are combined could be a key area for further improvement.

Summary updated

BibTeX
@inproceedings{kazama2007new,
  author = {Jun’ichi Kazama and Kentaro Torisawa},
  title = {{A New Perceptron Algorithm for Sequence Labeling with Non-Local Features}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure