CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS

Velimir M. Ilić, Miroslav D. Ćirić, Miomir S. Stanković

DOI Number
10.22190/FUMI1801041I
First page
041
Last page
061

Abstract


In this paper we consider the problem of efficient computation of cross-moments of a vector random variable represented by a stochastic context-free grammar. Two types of cross-moments are discussed. The sample space for the first one is the set of all derivations of the context-free grammar, and the sample space for the second one is the set of all derivations which generate a string belonging to the language of the grammar. In the past, this problem was widely studied, but mainly for the cross-moments of scalar variables and up to the second order. This paper presents new algorithms for computing the cross-moments of an arbitrary order, while the previously developed ones are derived as special cases.


Keywords

Cross-moments, stochastic context-free grammar, language of the grammar.

Keywords


stochastic context-free grammar, cross-moments, semiring, %moment-generating function, partition function, inside-outside algorithm

Full Text:

PDF

References


Bonnie Berger. The fourth moment method. SIAM Journal on Computing, 26(4):1188–1207,1997.

T. L. Booth and R. A. Thompson. Applying probability measures to abstract languages. IEEE Trans. Comput., 22:442–450, May 1973.

Jorge Calera-Rubio and Rafael C. Carrasco. Computing the relative entropy between regular tree languages. Information Processing Letters, 68(6):283 – 289, 1998.

Zhiyi Chi. Statistical properties of probabilistic context-free grammars. Comput. Linguist., 25(1):131–160, March 1999.

Shay B. Cohen, Robert J. Simmomns, and Noah A. Smith. Products of weighted logic programs. Theory and Practice of Logic Programming, 11:263–296, 2011.

Corinna Cortes and Mehryar Mohri. Distribution kernels based on moments of counts. In IN PROCEEDINGS OF THE TWENTY-FIRST INTERNATIONAL CONFERENCE ON MACHINE LEARNING (ICML 2004, 2004.

Corinna Cortes, Mehryar Mohri, Ashish Rastogi, and Michael Riley. On the computation of the relative entropy of probabilistic automata. Int. J. Found. Comput. Sci., 19(1):219–242, 2008.

Joshua Goodman. Semiring parsing. Comput. Linguist., 25(4):573–605, 1999.

Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge University Press, New York, NY, USA, 1985.

Sandra E. Hutchins. Moments of string and derivation lengths of stochastic context-free grammars. Information Sciences, 4(2):179 – 191, 1972.

Rebecca Hwa. Sample selection for statistical grammar induction. In Proceedings of the 2000 Joint SIGDAT conference on Empirical methods in natural language processing and very large corpora: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics - Volume 13, pages 45–52, Morristown, NJ, USA, 2000. Association for Computational Linguistics.

Velimir M Ilic, Dejan I Mancev, Branimir T Todorovic, and Miomir S Stankovi´c. Gradient

computation in linear-chain conditional random fields using the entropy message passing algorithm. Pattern Recognition Letters, 33(13):1776–1784, 2012.

Velimir M. Ilic, Miomir S. Stankovic, and Branimir T. Todorovic. Entropy message passing. IEEE Transactions on Information Theory, 57(1):219–242, 2011.

Velimir M. Ilic, Miomir S. Stankovic, and Branimir T. Todorovic. Entropy semiiring forward-backward algorithm for HMM entropy computation. Transactions on Advanced Research, 8(2):8–15, 2012.

K. Lari and S. J. Young. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech & Language, 4(1):35 – 56, 1990.

Zhifei Li and Jason Eisner. First- and second-order expectation semirings with applications to minimum-risk training on translation forests. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 1, EMNLP ’09, pages 40–51, Morristown, NJ, USA, 2009. Association for Computational Linguistics.

Mark-Jan Nederhof and Giorgio Satta. Computation of distances for regular and context free probabilistic languages. Theor. Comput. Sci., 395(2-3):235–254, April 2008.

Mark-Jan Nederhof and Giorgio Satta. Computing partition functions of pcfgs. Research on Language and Computation, 6:139–162, 2008. 10.1007/s11168-008-9052-8.

Mark-Jan Nederhof and Giorgio Satta. Probabilistic parsing. In New Developments in Formal Languages and Applications, volume 113 of Studies in Computational Intelligence, pages 229–258. Springer Berlin / Heidelberg, 2008.

M.H. Protter. Basic Elements of Real Analysis. S.Axler and others. Springer, 1998.

Xavier Saint Raymond. Elementary Introduction to the Theory of Pseudodierential Operators (Studies in Advanced Mathematics). CRC Press, Boca Raton, 1991.

Lund R.B. Elementary probability theory with stochastic processes and an introduction to mathematical finance (4th ed.). The American Statistician, 58:173–174, May 2004.

Velimir M. Ilic; Miomir S. Stankovic and Branimir T. Todorovic. Computation of crossmoments using message passing over factor graphs. Adv. Math. Commun., 6(3):363–384,

Frdric Tendeau. Computing abstract decorations of parse forests using dynamic programming and algebraic power series. Theoretical Computer Science, 199(1-2):145 – 166, 1998.

A. B. Thaheema and A. Laradjia. Classroom note: A generalization of leibniz rule for higher derivatives. International Journal of Mathematical Education in Science and Technology,

(6):905–907, 2001.

C. S. Wetherell. Probabilistic languages: A review and some open questions. ACM Comput. Surv., 12:361–379, December 1980.




DOI: https://doi.org/10.22190/FUMI1801041I

Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)