Text Chunking using Regularized Winnow

Text Chunking using Regularized Winnow Tong Zhang � and Fred Damerau � and David Johnson � IBM T.J. Watson Research Center Yorktown Heights New York, 10598, USA � tzhang@watson.ibm.com � damerau@watson.ibm.com � dejohns@us.ibm.com Abstract Many machine learning methods have recently been applied to natural lan- guage processing tasks. Among them, the Winnow algorithm has been ar- gued to be particularly suitable for NLP problems, due to its robustness to ir- relevant features. However in theory, Winnow may not converge for non- separable data. To remedy this prob- lem, a modification called regularized Winnow has been proposed. In this pa- per, we apply this new method to text chunking. We show that this method achieves state of the art performance with significantly less computation than previous approaches. 1 Introduction Recently there has been considerable interest in applying machine learning techniques to prob- lems in natural language processing. One method that has been quite successful in many applica- tions is the SNoW architecture (Dagan et al., 1997; Khardon et al., 1999). This architecture is based on the Winnow algorithm (Littlestone, 1988; Grove and Roth, 2001), which in theory is suitable for problems with many irrelevant at- tributes. In natural language processing, one of- ten encounters a very high dimensional feature space, although most of the features are irrele- vant. Therefore the robustness of Winnow to high dimensional feature space is considered an impor- tant reason why it is suitable for NLP tasks. However, the convergence of the Winnow al- gorithm is only guaranteed for linearly separable data. In practical NLP applications, data are of- ten linearly non-separable. Consequently, a di- rect application of Winnow may lead to numer- ical instability. A remedy for this, called regu- larized Winnow, has been recently proposed in (Zhang, 2001). This method modifies the origi- nal Winnow algorithm so that it solves a regular- ized optimization problem. It converges both in the linearly separable case and in the linearly non- separable case. Its numerical stability implies that the new method can be more suitable for practical NLP problems that may not be linearly separable. In this paper, we compare regularized Winnow and Winnow algorithms on text chunking (Ab- ney, 1991). In order for us to rigorously com- pare our system with others, we use the CoNLL- 2000 shared task dataset (Sang and Buchholz, 2000), which is publicly available from http://lcg- www.uia.ac.be/conll2000/chunking. An advan- tage of using this dataset is that a large number of state of the art statistical natural language pro- cessing methods have already been applied to the data. Therefore we can readily compare our re- sults with other reported results. We show that state of the art performance can be achieved by using the newly proposed regu- larized Winnow method. Furthermore, we can achieve this result with significantly less compu- tation than earlier systems of comparable perfor- mance. The paper is organized as follows. In Section 2, we describe the Winnow algorithm and the reg- ularized Winnow method. Section 3 describes the CoNLL-2000 shared …

Content truncated to 500 words