Abstract
The most popular algorithms for the estimation of the probabilities of a context-free grammar are the Inside-Outside algorithm and the Viterbi algorithm, which are Maximum Likelihood approaches. The difference between the logarithm of the likelihood of a string and the logarithm of the likelihood of the most probable parse of a string is upper bounded linearly by the length of the string and the logarithm of the number of non-terminal symbols. However, this theoretical bound is too pessimistic. For this reason, an experimental work to show the behaviour of the two functions in practical cases is necessary.
Work partially supported by the Spanish CICYT under contract TIC95/0884-C04.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J.K. Baker. Trainable grammars for speech recognition. In Klatt and Wolf, editors, Speech Communications for the 97th Meeting of the Acoustical Society of America, pages 31–35. Acoustical Society of America, June 1979.
J.M. Benedí and J.A. Sánchez. Corrective training for the estimation of stochastic context-free grammars. In A. Calvo and R. Medina, editors, Proc. VI Spanish Symposium on Pattern Recognition and Image Analysis, pages 442–450. AERFAI, Abril 1995.
T.L. Booth and R.A. Thompson. Applying probability measures to abstract languages. IEEE Transactions on Computers, C-22(5):442–450, May 1973.
F. Casacuberta. Grow transformations for probabilistic functions of stochastic grammars. IJPRAI, 10(3), 1996.
P. Dupont. Efficient integration of context-free grammars based language models in continuous speech recognition. In New Advances and Trends in Speech Recognition and Coding, pages 179–182. NATO ASI, 1993.
J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
E. Horowitz and S. Sahni. Fundamentals of Data Structures in Pascal. Computer Science Press, third edition, 1990.
F. Jelinek and J.D. Lafferty. Computation of the probability of initial substring generation by stochastic context-free grammars. Computational Linguistics, 17(3):315–323, 1991.
J. Kupiec. Hidden Markov estimation for unrestricted stochastic context-free grammars. Proc. of ICASSP'92 Vol. 1, pages 177–180. 1992.
K. Lari and S. J. Young. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer, Speech and Language, 4:35–56, 1990.
K. Lari and S.J. Young. Applications of stochatic context-free grammars using the inside-outside algorithm. Computer, Speech and Language, (5):237–257, 1991.
N. Merhav and Y. Ephraim. Hidden markov modeling using a dominant state sequence with application to speech recognition. Computer Speech and Language, 5:327–339, 1991.
N. Merhav and Y. Ephraim. Maximum likelihood hidden markov modeling using a dominant sequence of states. IEEE. Transactions on Signal Processing, 39(9):2111–2115, 1991.
H. Ney. Stochastic grammars and pattern recognition. In P. Laface and R. De Mori, editors, Speech Recognition and Understanding. Recent Advances, pages 319–344. Springer-Verlag, 1992.
S. Sahni. Concepts in Discrete Mathematics. Camelot Pub. Co., 1985.
Y. Sakakibara. Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science, 76:223–242, 1990.
Y. Sakakibara, M. Brown, R. Hughey, I.S. Mian, K. Sjölander, R.C. Underwood, and D. Haussle. The application of stochastic context-free grammars to folding, aligning and modeling homologous rna. Computer and Information Science UCSC-CRL-94-14, Univ. of California, Santa Cruz, Ca., 1993.
A. Stolcke. Bayesian Learning of Probabilistic Language Models. PhD thesis, University of California, Berkeley, CA., 1994.
A. Stolcke. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2):165–200, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sánchez, JA., Benedí, JM., Casacuberta, F. (1996). Comparison between the Inside-Outside algorithm and the Viterbi algorithm for stochastic context-free grammars. In: Perner, P., Wang, P., Rosenfeld, A. (eds) Advances in Structural and Syntactical Pattern Recognition. SSPR 1996. Lecture Notes in Computer Science, vol 1121. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61577-6_6
Download citation
DOI: https://doi.org/10.1007/3-540-61577-6_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61577-4
Online ISBN: 978-3-540-70631-1
eBook Packages: Springer Book Archive
