Paper Info
Title
An algorithm for estimating the parameters of unrestricted hidden stochastic context-free grammars
Abstract
A new algorithm is presented for estimating the parameters of a stochastic context-free grammar (SCFG) from ordinary unparsed text. Unlike the Inside/Outside (I/O) algorithm which requires a grammar to be specified in Chomsky normal form, the new algorithm can estimate an arbitrary SCFG without any need for transformation. The algorithm has worst-case cubic complexity in the length of a sentence and the number of nonterminals in the grammar. Instead of the binary branching tree structure used by the I/O algorithm, the new algorithm makes use of a trellis structure for computation. The trellis is a generalization of that used by the Baum-Welch algorithm which is used for estimating hidden stochastic regular grammars. The paper describes the relationship between the trellis and the more typical parse tree representation.
Year
DOI
Venue
1992
10.3115/992066.992129
COLING
Keywords
DocType
Volume
stochastic context-free grammar,tree structure,trellis structure,chomsky normal form,typical parse tree representation,arbitrary scfg,new algorithm,unrestricted hidden stochastic context-free,hidden stochastic regular grammar,baum-welch algorithm,o algorithm,baum welch,stochastic context free grammar,normal form
Conference
C92-1
Citations 
PageRank 
References 
1
0.36
4
Authors
1
Name
Order
Citations
PageRank
Julian Kupiec11061381.10