Efficient Word Lattice Generation for Joint Word Segmentation and POS Tagging in Japanese

International Joint Conference on Natural Language Processing, pages 153–161, Nagoya, Japan, 14-18 October 2013. Efficient Word Lattice Generation for Joint Word Segmentation and POS Tagging in Japanese Nobuhiro Kaji∗ and Masaru Kitsuregawa∗† ∗Institute of Industrial Science, The University of Tokyo †National Institute of Informatics {kaji, kitsure}@tkl.iis.u-tokyo.ac.jp Abstract This paper investigates the importance of a word lattice generation algorithm in joint word segmentation and POS tagging. We conducted experiments on three Japanese data sets to demonstrate that the previ- ously proposed pruning-based algorithm is in fact not efficient enough, and that the pipeline algorithm, which is introduced in this paper, achieves considerable speed- up without loss of accuracy. Moreover, the compactness of the lattice generated by the pipeline algorithm was investigated from both theoretical and empirical per- spectives. 1 Introduction Many approaches to joint word segmentation and POS tagging can be interpreted as reranking with a word lattice (Jiang et al., 2008), wherein a small lattice is generated for an input sentence, and then the lattice paths are reranked to obtain the optimal one. Examples of such a method include (Asahara and Matsumoto, 2000; Kudo et al., 2004; Kru- engkrai et al., 2006; Jiang et al., 2008). In such a framework, it is crucial to develop an efficient lattice generation algorithm. Since there are n+1C2 = O(n2) word candidates, where n is the number of characters in the sentence, to be in- cluded in the lattice, it is prohibitively expensive to check all of them exhaustively. Such a naive method constitutes a severe bottleneck in a rerank- ing system. Accordingly, in practice, it is neces- sary to resort to some technique to speed-up lattice generation. It is, however, not straightforward to speed-up lattice generation for reranking, because there are requirements that the lattice has to satisfy and it is necessary to achieve a speed-up while satisfy- ing those requirements. Most importantly, the lat- tice should contain a sufficient amount of correct words; otherwise, the accuracy of the reranking system will be seriously degraded. Moreover, the lattice should be small: an excessively large lat- tice spoils the efficiency of the reranking system because it is expensive to find the optimal path of such a lattice. For the reasons stated above, it is not readily obvious what sort of technique is effective for lat- tice generation. Despite its practical importance, this question, however, has not been well studied. For example, (Kudo et al., 2004) used a dictionary to filter word candidates. While indeed efficient, such a method is obviously prone to removing out- of-vocabulary (OOV) words from a lattice and de- grade accuracy (Uchimoto et al., 2001). Jiang et al. (2008) employed a pruning-based algorithm to reduce the O(n2) cost, but they did not investigate computational time required. Given the above issues, the present study revis- its lattice reranking by exploring the effectiveness of the lattice generation algorithm. Specifically, large-scale experiments were conducted on three Japanese data sets. The results of the experiments show that the pruning-based algorithm (Jiang et al., 2008) in …

Content truncated to 500 words