Multilayer Sequence Labeling

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 628–637, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Multilayer Sequence Labeling Ai Azuma Yuji Matsumoto Graduate School of Information Science Nara Institute of Science and Technology Ikoma, Nara 630-0192, Japan {ai-a,matsu}@is.naist.jp Abstract In this paper, we describe a novel approach to cascaded learning and inference on sequences. We propose a weakly joint learning model on cascaded inference on sequences, called multilayer sequence labeling. In this model, inference on sequences is modeled as cas- caded decision. However, the decision on a sequence labeling sequel to other decisions utilizes the features on the preceding results as marginalized by the probabilistic models on them. It is not novel itself, but our idea central to this paper is that the probabilis- tic models on succeeding labeling are viewed as indirectly depending on the probabilistic models on preceding analyses. We also pro- pose two types of efficient dynamic program- ming which are required in the gradient-based optimization of an objective function. One of the dynamic programming algorithms re- sembles back propagation algorithm for mul- tilayer feed-forward neural networks. The other is a generalized version of the forward- backward algorithm. We also report experi- ments of cascaded part-of-speech tagging and chunking of English sentences and show ef- fectiveness of the proposed method. 1 Introduction Machine learning approach is widely used to clas- sify instances into discrete categories. In many tasks, however, some set of inter-related labels should be decided simultaneously. Such tasks are called structured prediction. Sequence labeling is the simplest subclass of structured prediction prob- lems. In sequence labeling, the most likely one among all the possible label sequences is predicted for a given input. Although sequence labeling is the simplest subclass, a lot of real-world tasks are modeled as problems of this simplest subclass. In addition, it might offer valuable insight and a toe- hold for more general and complex structured pre- diction problems. Many models have been proposed for sequence labeling tasks, such as Hidden Markov Models (HMM), Conditional Random Fields (CRF) (Lafferty et al., 2001), Max-Margin Markov Net- works (Taskar et al., 2003) and others. These models have been applied to lots of practical tasks in natural language processing (NLP), bioinformatics, speech recognition, and so on. And they have shown great success in recent years. In real-world tasks, it is often needed to cascade multiple predictions. A cascade of predictions here means the situation in which some of predictions are made based upon the results of other predictions. Sequence labeling is not an exception. For exam- ple, in NLP, we perform named entity recognition or base-phrase chunking for given sentences based on part-of-speech (POS) labels predicted by another se- quence labeler. Natural languages are especially in- terpreted to have a hierarchy of sequential structures on different levels of abstraction. Therefore, many tasks in NLP are modeled as a cascade of sequence predictions. If a prediction is based upon the result of another prediction, we call …

Content truncated to 500 words