A SNoW Based Supertagger with Application to NP Chunking

A SNoW based Supertagger with Application to NP Chunking Libin Shen and Aravind K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104, USA � libin,joshi � @linc.cis.upenn.edu Abstract Supertagging is the tagging process of assigning the correct elementary tree of LTAG, or the correct supertag, to each word of an input sentence1. In this pa- per we propose to use supertags to expose syntactic dependencies which are unavail- able with POS tags. We first propose a novel method of applying Sparse Network of Winnow (SNoW) to sequential models. Then we use it to construct a supertagger that uses long distance syntactical depen- dencies, and the supertagger achieves an accuracy of ���� � . We apply the su- pertagger to NP chunking. The use of su- pertags in NP chunking gives rise to al- most � absolute increase (from ���  to ����� ) in F-score under Transforma- tion Based Learning(TBL) frame. The surpertagger described here provides an effective and efficient way to exploit syn- tactic information. 1 Introduction In Lexicalized Tree-Adjoining Grammar (LTAG) (Joshi and Schabes, 1997; XTAG-Group, 2001), each word in a sentence is associated with an el- ementary tree, or a supertag (Joshi and Srinivas, 1994). Supertagging is the process of assigning the correct supertag to each word of an input sentence. The following two facts make supertagging attrac- tive. Firstly supertags encode much more syntac- tical information than POS tags, which makes su- pertagging a useful pre-parsing tool, so-called, al- most parsing (Srinivas and Joshi, 1999). On the 1By the correct supertag we mean the supertag that an LTAG parser would assign to a word in a sentence. other hand, as the term ’supertagging’ suggests, the time complexity of supertagging is similar to that of POS tagging, which is linear in the length of the in- put sentence. In this paper, we will focus on the NP chunk- ing task, and use it as an application of supertag- ging. (Abney, 1991) proposed a two-phase pars- ing model which includes chunking and attaching. (Ramshaw and Marcus, 1995) approached chuck- ing by using Transformation Based Learning(TBL). Many machine learning techniques have been suc- cessfully applied to chunking tasks, such as Regular- ized Winnow (Zhang et al., 2001), SVMs (Kudo and Matsumoto, 2001), CRFs (Sha and Pereira, 2003), Maximum Entropy Model (Collins, 2002), Memory Based Learning (Sang, 2002) and SNoW (Mu˜noz et al., 1999). The previous best result on chunking in literature was achieved by Regularized Winnow (Zhang et al., 2001), which took some of the parsing results given by an English Slot Grammar-based parser as input to the chunker. The use of parsing results contributed �� absolute increase in F-score. However, this approach conflicts with the purpose of chunking. Ideally, a chunker geneates n-best results, and an at- tacher uses chunking results to construct a parse. The dilemma is that syntactic constraints are use- ful in the chunking phase, but they are unavail- able until the attaching phase. The reason is that POS tags …

Content truncated to 500 words