Paper Info
Title
A Trellis-based algorithm for estimating the parameters of a hidden stochastic context-free grammar
Abstract
The paper presents a new algorithm for estimating the pa- rameters of a hidden stochastic context-free grammar. In con- trast to the Inside/Outside (I/O) algorithm it does not require the grammar to be expressed in Chomsky normal form, and thus can operate directly on more natural representations of a gram- mar. The algorithm uses a trellis-based structure as opposed to the binary branching tree structure used by the I/O algorithm. The form of the trellis is an extension of that used by the For- ward/Backward algorithm, and as a result the algorithm reduces to the latter for components that can be modeled as finite-state networks. In the same way that a hidden Markov model (HMM) is a stochastic analogue of a finlte-state network, the represen- tation used by the new algorithm is a stochastic analogue of a recursive transition network, in which a state may be simple or itself contain an underlying structure.
Year
DOI
Venue
1991
10.3115/112405.112448
HLT '91 Proceedings of the workshop on Speech and Natural Language
Keywords
Field
DocType
trellis-based algorithm,hidden stochastic context-free grammar,tree structure,finite-state network,hidden markov model,chomsky normal form,underlying structure,new algorithm,trellis-based structure,stochastic analogue,o algorithm
Stochastic context-free grammar,Ramer–Douglas–Peucker algorithm,Forward algorithm,Computer science,Algorithm,Recursive transition network,Tree structure,Chomsky normal form,Hidden Markov model,Binary number
Conference
Citations 
PageRank 
References 
11
6.36
3
Authors
1
Name
Order
Citations
PageRank
Julian Kupiec11061381.10