Paper: Backward Beam Search Algorithm For Dependency Analysis Of Japanese

ACL ID C00-2109
Title Backward Beam Search Algorithm For Dependency Analysis Of Japanese
Venue International Conference on Computational Linguistics
Session Main Conference
Year 2000
Authors

Backward beam search tbr dependency analy- sis of Japanese is proposed. As dependencies normally go fl'om left to right in Japanese, it is effective to analyze sentences backwards (from right to left). The analysis is based on a statisti- cal method and employs a bemn search strategy. Based on experiments varying the bemn search width, we found that the accuracy is not sen- sitivc to the bemn width and even the analysis with a beam width of 1 gets ahnost the stone de- pendency accuracy as the best accuracy using a wider bemn width. This suggested a determin- istic algorithm for backwards Japanese depen- dency analysis, although still the bemn search is eitbctive as the N-best sentence accuracy is quite high. The time of analysis is observed to be quadratic in the sentence length.