Statistical Dependency Analysis using Backward Beam Search

概要

論文の詳細を見る
Dependency analysis is regarded as a standard method of Japanese syntactic analysis. As dependencies normally go from left to right, it is effective to parse from right to left, as we can analyze predicates first. There have been several proposals for such methods using rule based parsing. In this paper, we will propose a Japanese dependency analysis which combines right to left parsing and a statistical method. It performs a beam search, an effective way of limiting the search space for right to left parsing. We get a dependency accuracy of 87.2% and a sentence accuracy of 40.8% using the Kyoto University corpus. Varying the beam search width, we observed that the best performances were achieved when the width is small. Actually, 95% of the sentence analyses obtained with beam width=1 were the same as the best analyses with beam width=20. The N-best sentence accuracy for N=20 was 78.5%. The analysis speed was proportional to the square of the sentence length (number of segments), as predicted for the algorithm. The average analysis time was 0.03 second (average sentence length was 10.0) and it took 0.29 second to analyze the longest sentence, which has 41 segments.
言語処理学会の論文