Efficient Grammar Induction Algorithm with Parse Forests from Real Corpora

DOI Web Site Web Site 20 References
  • KURIHARA Kenichi
    Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology
  • KAMEYA Yoshitaka
    Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology
  • SATO Taisuke
    Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology

Bibliographic Information

Other Title
  • 構文森を用いた実コーパスからの大規模な文脈自由文法の高速学習法
  • コウブン モリ オ モチイタ ジツ コーパス カラ ノ ダイキボ ナ ブンミャク ジユウ ブンポウ ノ コウソク ガクシュウホウ

Search this article

Abstract

The task of inducing grammar structures has received a great deal of attention. The reasons why researchers have studied are different; to use grammar induction as the first stage in building large treebanks or to make up better language models. However, grammar induction has inherent computational complexity. To overcome it, some grammar induction algorithms add new production rules incrementally. They refine the grammar while keeping their computational complexity low. In this paper, we propose a new efficient grammar induction algorithm. Although our algorithm is similar to algorithms which learn a grammar incrementally, our algorithm uses the graphical EM algorithm instead of the Inside-Outside algorithm. We report results of learning experiments in terms of learning speeds. The results show that our algorithm learns a grammar in constant time regardless of the size of the grammar. Since our algorithm decreases syntactic ambiguities in each step, our algorithm reduces required time for learning. This constant-time learning considerably affects learning time for larger grammars. We also reports results of evaluation of criteria to choose nonterminals. Our algorithm refines a grammar based on a nonterminal in each step. Since there can be several criteria to decide which nonterminal is the best, we evaluate them by learning experiments.

Journal

References(20)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top