jmlr jmlr2010 jmlr2010-115 jmlr2010-115-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alexander Clark, Rémi Eyraud, Amaury Habrard
Abstract: We present a polynomial update time algorithm for the inductive inference of a large class of context-free languages using the paradigm of positive data and a membership oracle. We achieve this result by moving to a novel representation, called Contextual Binary Feature Grammars (CBFGs), which are capable of representing richly structured context-free languages as well as some context sensitive languages. These representations explicitly model the lattice structure of the distribution of a set of substrings and can be inferred using a generalisation of distributional learning. This formalism is an attempt to bridge the gap between simple learnable classes and the sorts of highly expressive representations necessary for linguistic representation: it allows the learnability of a large class of context-free languages, that includes all regular languages and those context-free languages that satisfy two simple constraints. The formalism and the algorithm seem well suited to natural language and in particular to the modeling of first language acquisition. Preliminary experimental results confirm the effectiveness of this approach. Keywords: grammatical inference, context-free language, positive data only, membership queries
P. Adriaans. Learning shallow context-free languages under simple distributions. Algebras, Diagrams and Decisions in Language, Logic and Computation, 127, 2002. D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87–106, 1987. D. Angluin. Queries and concept learning. Mach. Learn., 2(4):319–342, 1988. ISSN 0885-6125. doi: http://dx.doi.org/10.1023/A:1022821128753. P.R.J. Asveld. Generating all permutations by context-free grammars in Chomsky normal form. Theoretical Computer Science, 354(1):118–130, 2006. L. Boasson and G. Senizergues. NTS languages are deterministic and congruential. J. Comput. Syst. Sci., 31(3):332–342, 1985. ISSN 0022-0000. doi: http://dx.doi.org/10.1016/00220000(85)90056-X. P. Boullier. A Cubic Time Extension of Context-Free Grammars. Grammars, 3:111–131, 2000. P. Boullier. From contextual grammars to range concatenation grammars. Electronic Notes on Theoretical Computer Science, 53, 2001. P. Boullier. Counting with range concatenation grammars. Theoretical Computer Science, 293(2): 391–416, 2003. 2742 U SING C ONTEXTUAL R EPRESENTATIONS R.C. Carrasco and J. Oncina. Learning stochastic regular grammars by means of a state merging method. In R.C. Carrasco and J. Oncina, editors, Proceedings ICGI’94, volume 862 of LNAI, pages 139–150. Springer, 1994. N. Chomsky. Knowledge of Language : Its Nature, Origin, and Use. Praeger, 1986. A. Clark. PAC-learning unambiguous NTS languages. In Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI), pages 59–71, 2006. A. Clark. A learnable representation for syntax using residuated lattices. In Proceedings of the conference on Formal Grammar, Bordeaux, France, 2009. A. Clark. Distributional learning of some context-free languages with a minimally adequate teacher. In Jos´ M. Sempere and Pedro Garc´a, editors, Grammatical Inference: Theoretical Results and e ı Applications, 10th International Colloquium, ICGI, pages 24–37. Springer, 2010. A. Clark and R. Eyraud. Polynomial identification in the limit of substitutable context-free languages. Journal of Machine Learning Research, 8:1725–1745, 2007. C. de la Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning, 27 (2):125–138, 1997. ISSN 0885-6125. F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using rfsas. Theor. Comput. Sci., 313(2):267–294, 2004. ISSN 0304-3975. R. Eyraud, C. de la Higuera, and J.C. Janodet. Lars: A learning algorithm for rewriting systems. Machine Learning, 66(1):7–31, 2007. G. Gazdar, E. Klein, G. Pullum, and I. Sag. Generalised Phrase Structure Grammar. Basil Blackwell, 1985. E.M. Gold. Language identification in the limit. Information and Control, 10:447–474, 1967. Z. Harris. Distributional structure. Word, 10(2-3):146–62, 1954. C. De La Higuera and J. Oncina. Inferring deterministic linear languages. In COLT ’02: 15th Annual Conference on Computational Learning Theory, pages 185–200. Springer-Verlag, 2002. J.J. Horning. A Study of Grammatical Inference. PhD thesis, Stanford University, Computer Science Department, California, 1969. A.K. Joshi and Y. Schabes. Tree-adjoining grammars. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, pages 69–124. Springer, Berlin, New York, 1997. D. Klein and C.D. Manning. Corpus-based induction of syntactic structure: models of dependency and constituency. In Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, pages 478–485, 2004. K.J. Lang, B.A. Pearlmutter, and R. Price. Results of the abbadingo one dfa learning competition and a new evidence driven state merging algorithm. In Grammatical Inference: Algorithms and Applications; 4th International Colloquium on Grammatical Inference, pages 1–12. SpringerVerlag, 1998. URL http://abbadingo.cs.unm.edu/. 2743 C LARK , E YRAUD AND H ABRARD P. Langley and S. Stromsten. Learning context-free grammars with a simplicity bias. In Proceedings of the Eleventh European Conference on Machine Learning, pages 220–228. Springer-Verlag, 2000. S. Marcus. Algebraic Linguistics; Analytical Models. Academic Press, N. Y., 1967. V. Mitrana. Marcus external contextual grammars: From one to many dimensions. Fundamenta Informaticae, 54:307–316, 2005. K. Nakamura and M. Matsumoto. Incremental learning of context-free grammars based on bottomup parsing and search. Pattern Recognition, 38(9):1384–1392, 2005. T. Oates, T. Armstrong, L. Becerra-Bonache, and M. Atamas. Inferring grammars for mildly context sensitive languages in polynomial-time. In Proceedings of the International Colloquium on Grammatical Inference (ICGI) 2006, volume 4201 of LNCS, pages 137–147. Springer, 2006. A. Okhotin. Conjunctive grammars. J. Autom. Lang. Comb., 6(4):519–535, 2001. ISSN 1430-189X. A. Okhotin. An overview of conjunctive grammars. Formal Language Theory Column, bulletin of the EATCS, 79:145–163, 2003. R. Parekh and V. Honavar. An incremental interactive algorithm for regular grammar inference. In Grammatical Inference : Learning Syntax from Sentences; 3rd International Colloquium on Grammatical Inference, pages 238–250. Springer-Verlag, 1996. L. Pitt. Inductive inference, DFA’s, and computational complexity. In Proceedings of the International Workshop on Analogical and Inductive Inference, pages 18–44. Springer-Verlag, 1989. B. Starkie, F. Coste, and M. Van Zaanen. The omphalos context-free grammar learning competition. In Grammatical Inference: Algorithms and Applications; 7th International Colloquium on Grammatical Inference, pages 16–27. Springer, 2004. URL http://www.irisa.fr/Omphalos/. B. Starkie, M. van Zaanen, and D. Estival. The Tenjinno machine translation competition. In Grammatical Inference: Algorithms and Applications, 8th International Colloquium on Grammatical Inference, volume 4201 of Lecture Notes in Computer Science, pages 214–226. Springer-Verlag, 2006. T. Yokomori. Polynomial-time identification of very simple grammars from positive data. Theoretical Computer Science, 298(1):179–206, 2003. R. Yoshinaka. Identification in the limit of k,l-substitutable context-free languages. In ICGI ’08: Proceedings of the 9th International Colloquium on Grammatical Inference, pages 266–279, Berlin, Heidelberg, 2008. Springer-Verlag. ISBN 978-3-540-88008-0. R. Yoshinaka. Learning mildly context-sensitive languages with multidimensional substitutability from positive data. In Proceedings of the 20th International Conference on Algorithmic Learning Theory (ALT), volume 5809 of LNCS, pages 278–292. Springer, 2009. 2744