CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS
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
Full Text:
PDFReferences
begin{thebibliography}{10}
bibitem{berger1997fourth}
Bonnie Berger.
newblock The fourth moment method.
newblock {em SIAM Journal on Computing}, 26(4):1188--1207, 1997.
bibitem{Booth_Thompson_73}
T.~L. Booth and R.~A. Thompson.
newblock Applying probability measures to abstract languages.
newblock {em IEEE Trans. Comput.}, 22:442--450, May 1973.
bibitem{Calera_Carrasco_98}
Jorge Calera-Rubio and Rafael~C. Carrasco.
newblock Computing the relative entropy between regular tree languages.
newblock {em Information Processing Letters}, 68(6):283 -- 289, 1998.
bibitem{Chi_99}
Zhiyi Chi.
newblock Statistical properties of probabilistic context-free grammars.
newblock {em Comput. Linguist.}, 25(1):131--160, March 1999.
bibitem{Cohen_11}
Shay~B. Cohen, Robert~J. Simmomns, and Noah~A. Smith.
newblock {Products of weighted logic programs}.
newblock {em Theory and Practice of Logic Programming}, 11:263--296, 2011.
bibitem{Cortes_Mohri_04}
Corinna Cortes and Mehryar Mohri.
newblock Distribution kernels based on moments of counts.
newblock In {em In proceedings of the twenty-first international conference on machine learning (ICML 2004}, 2004.
bibitem{Cortes_et_al_08}
Corinna Cortes, Mehryar Mohri, Ashish Rastogi, and Michael Riley.
newblock On the computation of the relative entropy of probabilistic automata.
newblock {em Int. J. Found. Comput. Sci.}, 19(1):219--242, 2008.
bibitem{Goodman_99}
Joshua Goodman.
newblock {Semiring parsing}.
newblock {em Comput. Linguist.}, 25(4):573--605, 1999.
bibitem{Horn_Johnson_85}
Roger~A. Horn and Charles~R. Johnson.
newblock {em Matrix analysis}.
newblock Cambridge University Press, New York, NY, USA, 1985.
bibitem{Hutchins_72}
Sandra~E. Hutchins.
newblock Moments of string and derivation lengths of stochastic context-free
grammars.
newblock {em Information Sciences}, 4(2):179 -- 191, 1972.
bibitem{Hwa_00}
Rebecca Hwa.
newblock Sample selection for statistical grammar induction.
newblock In {em 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.
bibitem{ilic2012gradient}
Velimir~M Ili{'c}, Dejan~I Man{v{c}}ev, Branimir~T Todorovi{'c}, and
Miomir~S Stankovi{'c}.
newblock Gradient computation in linear-chain conditional random fields using
the entropy message passing algorithm.
newblock {em Pattern Recognition Letters}, 33(13):1776--1784, 2012.
bibitem{Ilic_et_al_11}
Velimir~M. Ilic, Miomir~S. Stankovic, and Branimir~T. Todorovic.
newblock Entropy message passing.
newblock {em IEEE Transactions on Information Theory}, 57(1):219--242, 2011.
bibitem{Ilic_et_all_12hmm}
Velimir~M. Ili'c, Miomir~S. Stankovi'c, and Branimir~T. Todorovi'c.
newblock Entropy semiiring forward-backward algorithm for {HMM} entropy
computation.
newblock {em Transactions on Advanced Research}, 8(2):8--15, 2012.
bibitem{Lari_Young_90}
K.~Lari and S.~J. Young.
newblock The estimation of stochastic context-free grammars using the
inside-outside algorithm.
newblock {em Computer Speech & Language}, 4(1):35 -- 56, 1990.
bibitem{Li_Eisner_09}
Zhifei Li and Jason Eisner.
newblock First- and second-order expectation semirings with applications to
minimum-risk training on translation forests.
newblock In {em 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.
bibitem{Nederhof_Satta_08c}
Mark-Jan Nederhof and Giorgio Satta.
newblock Computation of distances for regular and context-free probabilistic
languages.
newblock {em Theor. Comput. Sci.}, 395(2-3):235--254, April 2008.
bibitem{Nederhof_Satta_08a}
Mark-Jan Nederhof and Giorgio Satta.
newblock Computing partition functions of pcfgs.
newblock {em Research on Language and Computation}, 6:139--162, 2008.
newblock 10.1007/s11168-008-9052-8.
bibitem{Nederhof_Satta_08b}
Mark-Jan Nederhof and Giorgio Satta.
newblock Probabilistic parsing.
newblock In {em New Developments in Formal Languages and Applications},
volume 113 of {em Studies in Computational Intelligence}, pages 229--258.
Springer Berlin / Heidelberg, 2008.
bibitem{Protter_98}
M.H. Protter.
newblock {em Basic Elements of Real Analysis}.
newblock S.Axler and others. Springer, 1998.
bibitem{Raymond_91}
Xavier~Saint Raymond.
newblock {em Elementary Introduction to the Theory of Pseudodi«erential
Operators (Studies in Advanced Mathematics)}.
newblock CRC Press, Boca Raton, 1991.
bibitem{Lund_04}
Lund R.B.
newblock Elementary probability theory with stochastic processes and an
introduction to mathematical finance (4th ed.).
newblock {em The American Statistician}, 58:173--174, May 2004.
bibitem{Ilic_et_al_12}
Velimir M. {Ili'c}; Miomir~S. {Stankovi'c} and Branimir~T. {Todorovi'c}.
newblock {Computation of cross-moments using message passing over factor
graphs.}
newblock {em {Adv. Math. Commun.}}, 6(3):363--384, 2012.
bibitem{Tendeau_98}
FrÚdÚric Tendeau.
newblock Computing abstract decorations of parse forests using dynamic
programming and algebraic power series.
newblock {em Theoretical Computer Science}, 199(1-2):145 -- 166, 1998.
bibitem{Thaheema_Laradjia_03}
A.~B. Thaheema and A.~Laradjia.
newblock Classroom note: A generalization of leibniz rule for higher
derivatives.
newblock {em International Journal of Mathematical Education in Science and
Technology}, 34(6):905--907, 2001.
bibitem{Wetherell_80}
C.~S. Wetherell.
newblock Probabilistic languages: A review and some open questions.
newblock {em ACM Comput. Surv.}, 12:361--379, December 1980.
DOI: https://doi.org/10.22190/FUMI1902289I
Refbacks
- There are currently no refbacks.
ISSN 0352-9665 (Print)