Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T03:14:11.916Z Has data issue: false hasContentIssue false

A fast method for statistical grammar induction

Published online by Cambridge University Press:  01 September 1998

WIDE R. HOGENHOUT
Affiliation:
Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-01, Japan
YUJI MATSUMOTO
Affiliation:
Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-01, Japan
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The statistical induction of stochastic context free grammars from bracketed corpora with the Inside Outside Algorithm is an appealing method for grammar learning, but the computational complexity of this algorithm has made it impossible to generate a large scale grammar. Researchers from natural language processing and speech recognition have suggested various methods to reduce the computational complexity and, at the same time, guide the learning algorithm towards a solution by, for example, placing constraints on the grammar. We suggest a method that strongly reduces that computational cost of the algorithm without placing constraints on the grammar. This method can in principle be combined with any of the constraints on grammars that have been suggested in earlier studies. We show that it is feasible to achieve results equivalent to earlier research, but with much lower computational effort. After creating a small grammar, the grammar is incrementally increased while rules that have become obsolete are removed at the same time. We explain the modifications to the algorithm, give results of experiments and compare these to results reported in other publications.

Information

Type
Research Article
Copyright
© 1998 Cambridge University Press