Paper: An Algorithm For Estimating The Parameters Of Unrestricted Hidden Stochastic Context-Free Grammars

ACL ID C92-1060
Title An Algorithm For Estimating The Parameters Of Unrestricted Hidden Stochastic Context-Free Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1992
Authors

A new algorithm is presented for estimating the pa- rameters of a stochastic context-free grammar (SCFG) from ordinary unparsed text. Unlike the Inside/Outside I/O) algorithm which requires a grammar to be spee- fled in Chomsky normal form, the new algorithm can estimate an arbitrary SCFG without ally need for trans- formation. The algorithm has worst-case cubic com- plexity in the length of a sentence and the number of nonterminais 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 com- putation. The trellis is a generalization of that used by the Baum-Welcb algorithm which is used for estimat- ing hidden stochastic regular grammars. Tile paper de- scribes tile relationship between the trellis an...