A Stochastic Japanese Morphological Analyzer Using a Forward-DP Backward-A* N-Best Search Algorithm

A Stochastic Japanese Morphological Analyzer Using a Forward-DP Backward-A* N-Best Search Algorithm Masa.aki NAGATA NTT Network Information Systems l~,~bor~ttorics 1-2356 Take, Yokosuka-Shi, Kanagaw~t, 238-03 Japan (tel) 4-81-468-59-2796 (fax) +81-468-59-3428 (e-mail) nagata@nttnly.ntt.jl) Abstract We present a novel method for segmenting the input sentence into words and assigning parts of speech to the words. It consists of a statistical language model and an efficient two-pa~qs N-best search algorithm. The algorithm does not require delimiters between words. Thus it is suitable for written Japanese. q'he proposed Japanese morphological analyzer achieved 95. l% recall and 94.6% precision for open text when it was trained and tested on the ATI'¢ Corpus. 1 Introduction In recent years, we have seen a fair number of l)al)ers re- porting accuracies of more than 95% for English part of speech tagging with statistical language modeling tech- niques [2-4, 10, 11]. On the other hand, there are few works on stochastic Japanese morphological analysis [9, 12, 14], and they don't seem to have convinced the Japanese NLP community that the statistically-based teclmiques are superior to conventional rule-based tech- niques such as [16, 17]. We show in this paper that we can buihl a stochastic Japanese morphological analyzer that offers approxi- mately 95% accuracy on a statistical language model- ing technique and an efficient two-pass N-best search strategy. We used tile simple tri-POS model as the tagging model for Japanese. Probability estimates were ob- tained after training on the ATI{ l)ialogue Database [5], whose word segmentation and part of speech tag assignment were laboriously performed by hand. We propose a novel search strategy for getting the N best morphological analysis hypotheses for the in- put sentence. It consists of the forward dynamic pro- gramming search and the backward A* search. The proposed algorithm amalgamates and extends three well-known algorithms in different fields: the Minimum Connective-Cost Method [7] for Japanese morphologi- cal analysis, Extended Viterbi Algorithm for charac- ter recognition [6], and "l~'ee-Trellis N-Best Search for speech recognition [15]. We also propose a novel method for handling un- known words uniformly within the statistical approach. Using character trigrams ms tim word model, it gener- ates the N-best word hypotheses that match the left- most substrings starting at a given position in the input senten ce. Moreover, we propose a novel method for evaluat- ing the performance of morphological analyzers. Un- like English, Japanese does not place spaces between words. It is difficult, even for native Japanese, to place word boundaries consistently because of the aggluti- native nature of the language. Thus, there were no standard performance metrics. We applied bracketing accuracy measures [1], which is originally used for En- glish parsers, to Japanese morphological analyzers. We also slightly extended the original definition to describe the accuracy of tile N-best candidates. In the following sections, we first describe the tech- niques used in the proposed morphological analyzer, we then explain the cwduation metrics and show the system's performance by experimental results. 2 Tagging Model 2.1 Tri-POS Model and Relative Fre- quency Training We …

Content truncated to 500 words