emnlp emnlp2013 emnlp2013-195 emnlp2013-195-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Raphael Bailly ; Xavier Carreras ; Franco M. Luque ; Ariadna Quattoni
Abstract: We derive a spectral method for unsupervised learning of Weighted Context Free Grammars. We frame WCFG induction as finding a Hankel matrix that has low rank and is linearly constrained to represent a function computed by inside-outside recursions. The proposed algorithm picks the grammar that agrees with a sample and is the simplest with respect to the nuclear norm of the Hankel matrix.
Pieter Adriaans, Marten Trautwein, and Marco Vervoort. 2000. Towards high speed grammar induction on large text corpora. In SOFSEM 2000: Theory and Practice of Informatics, pages 173–186. Springer. Rapha ¨el Bailly, Franois Denis, and Liva Ralaivola. 2009. Grammatical inference as a principal component analysis problem. In L e´on Bottou and Michael Littman, editors, Proceedings of the 26th International Conference on Machine Learning, pages 33–40, Montreal, June. Omnipress. Rapha ¨el Bailly, Amaury Habrard, and Fran ¸cois Denis. 2010. A spectral approach for probabilistic grammatical inference on trees. In Proceedings of the 21st International Conference Algorithmic Learning Theory, Lecture Notes in Computer Science, pages 74–88. Springer. Rapha ¨el Bailly, Xavier Carreras, and Ariadna Quattoni. 2013. Unsupervised spectral learning of finite-state transducers. In Advances in Neural Information Processing Systems 26. James K. Baker. 1979. Trainable grammars for speech recognition. In D. H. Klatt and J. J. Wolf, editors, Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, pages 547–550. Borja Balle, Ariadna Quattoni, and Xavier Carreras. 2011. A spectral learning algorithm for finite state transducers. In Proceedings of ECML PKDD, pages 156–171. Borja Balle, Ariadna Quattoni, and Xavier Carreras. 2012. Local loss optimization in operator models: A new insight into spectral learning. In John Langford and Joelle Pineau, editors, Proceedings of the 29th International Conference on Machine Learning (ICML2012), ICML ’ 12, pages 1879–1886, New York, NY, USA, July. Omnipress. Amir Beck and Marc Teboulle. 2009. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Img. Sci., 2(1): 183–202, March. Stanley F Chen. 1995. Bayesian grammar induction for language modeling. In Proceedings of the 33rd annual meeting on Association for Computational Linguistics, pages 228–235. Association for Computational Linguistics. Alexander Clark. 2001 . Unsupervised induction of stochastic context-free grammars using distributional clustering. In Proceedings of the 2001 workshop on Computational Natural Language Learning-Volume 7, page 13. Association for Computational Linguistics. Alexander Clark. 2007. Learning deterministic context free grammars: The omphalos competition. Machine Learning, 66(1):93–1 10. 634 Shay B. Cohen, David M. Blei, and Noah A. Smith. 2010. Variational inference for adaptor grammars. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 564– 572, Los Angeles, California, June. Association for Computational Linguistics. Shay B. Cohen, Karl Stratos, Michael Collins, Dean P. Foster, and Lyle Ungar. 2012. Spectral learning of latent-variable pcfgs. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 223–23 1, Jeju Island, Korea, July. Association for Computational Linguistics. Shay B. Cohen, Karl Stratos, Michael Collins, Dean P. Foster, and Lyle Ungar. 2013. Experiments with spectral learning of latent-variable pcfgs. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 148–157, Atlanta, Georgia, June. Association for Computational Linguistics. Matthew Gormley and Jason Eisner. 2013. Nonconvex global optimization for latent-variable models. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL), Sofia, Bulgaria, August. 11pages. Daniel Hsu, Sham M. Kakade, and Tong Zhang. 2009. A spectral algorithm for learning hidden markov models. In Proceedings of the Annual Conference on Computational Learning Theory (COLT). Daniel Hsu, Sham Kakade, and Percy Liang. 2012. Identifiability and unmixing of latent parse trees. In P. Bartlett, F.C.N. Pereira, C.J.C. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1520–1528. Dan Klein and Christopher D Manning. 2002. A generative constituent-context model for improved grammar induction. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, pages 128–135. Association for Computational Linguistics. Kenichi Kurihara and Taisuke Sato. 2006. Variational bayesian grammar induction for natural language. In Grammatical Inference: Algorithms and Applications, pages 84–96. Springer. Karim Lari and Steve J Young. 1990. The estimation of stochastic context-free grammars using the insideoutside algorithm. Computer speech & language, 4(1):35–56. Percy Liang, Slav Petrov, Michael IJordan, and Dan Klein. 2007. The infinite PCFG using hierarchical dirichlet processes. In EMNLP-CoNLL, pages 688– 697. Franco M. Luque, Ariadna Xavier Carreras. deterministic Quattoni, 2012. dependency of the 13th Conference Borja Balle, and Spectral learning parsing. for non- In Proceedings of the European Chapter of the Association for Computational Linguistics, pages 409–419, Avignon, France, April. Association for Computational Linguistics. Fernando Pereira and Yves Schabes. 1992. Insideoutside reestimation from partially bracketed corpora. In Proceedings of the 30th Annual Meeting of the Association for Computational Linguistics, pages 128– 135, Newark, Delaware, USA, June. Association for Computational Linguistics. Slav Petrov, Dipanjan Das, and Ryan McDonald. 2012. A universal part-of-speech tagset. In Proceedings of LREC, May. Kewei Tu and Vasant Honavar. 2008. Unsupervised learning of probabilistic context-free grammar using iterative biclustering. In Grammatical Inference: Algorithms and Applications, pages 224–237. Springer. Menno Van Zaanen. 2000. Abl: Alignment-based learning. In Proceedings of the 18th conference on Computational linguistics-Volume 2, pages 961–967. Association for Computational Linguistics. 635