CUED Publications database

The estimation of stochastic context-free grammars using the Inside-Outside algorithm

Lari, K and Young, SJ (1990) The estimation of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech and Language, 4. pp. 35-56. ISSN 0885-2308

Full text not available from this repository.

Abstract

Using an entropy argument, it is shown that stochastic context-free grammars (SCFG's) can model sources with hidden branching processes more efficiently than stochastic regular grammars (or equivalently HMM's). However, the automatic estimation of SCFG's using the Inside-Outside algorithm is limited in practice by its O(n3) complexity. In this paper, a novel pre-training algorithm is described which can give significant computational savings. Also, the need for controlling the way that non-terminals are allocated to hidden processes is discussed and a solution is presented in the form of a grammar minimization procedure. © 1990.

Item Type: Article
Subjects: UNSPECIFIED
Divisions: Div F > Machine Intelligence
Depositing User: Cron Job
Date Deposited: 07 Mar 2014 11:21
Last Modified: 14 Dec 2014 06:45
DOI: 10.1016/0885-2308(90)90022-X