jmlr jmlr2007 jmlr2007-67 jmlr2007-67-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alexander Clark, Rémi Eyraud
Abstract: This paper formalises the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free languages. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. It transpires that it is not necessary to identify constituents in order to learn a context-free language—it is sufficient to identify the syntactic congruence, and the operations of the syntactic monoid can be converted into a context-free grammar. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin’s notion of reversibility for regular languages. We also demonstrate that an implementation of this algorithm is capable of learning a classic example of structure dependent syntax in English: this constitutes a refutation of an argument that has been used in support of nativist theories of language. Keywords: grammatical inference, context-free languages, positive data only, reduction system, natural languages
P. Adriaans. Learning shallow context-free languages under simple distributions. In K. Vermeulen and A. Copestake, editors, Algebras, Diagrams and Decisions in Language, Logic and Computation, volume 127. CSLI Publications, 2002. P. Adriaans, M. Trautwein, and M. Vervoort. Towards high speed grammar induction on large text corpora. In SOFSEM 2000, pages 173–186. Springer Verlag, 2000. D. Angluin. Inference of reversible languages. Communications of the ACM, 29:741–765, 1982. R. Book and F. Otto. String Rewriting Systems. Springer Verlag, 1993. N. Chomsky. Systems of syntactic analysis. Journal of Symbolic Logic, 18(3):242–256, 1953. S. Crain and M. Nakayama. Structure dependence in grammar formation. Language, 63(3):522– 543, 1987. C. de la Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning, 27 (2):125–138, 1997. P. Dupont, L. Miclet, and E. Vidal. What is the search space of the regular inference? In R. C. Carrasco and J. Oncina, editors, Grammatical Inference and Applications, Second International Colloquium, ICGI-94, pages 25–37, 1994. E. M. Gold. Language identification in the limit. Information and Control, 10(5):447 – 474, 1967. Z. Harris. Distributional structure. Word, 10(2-3):146–62, 1954. X. N. C. Kam, I. Stoyneshka, L. Tornyova, J. D. Fodor, and W. G. Sakas. Non-robustness of syntax acquisition from n-grams: A cross-linguistic perspective. In The 18th Annual CUNY Sentence Processing Conference, April 2005. J. A. Laxminarayana and G. Nagaraja. Inference of a subclass of context free grammars using positive samples. In Proceedings of the Workshop on Learning Context-Free Grammars at ECML/PKDD 2003, 2003. M. Lohrey. Word problems and confluence problems for restricted semi-thue systems. In RTA, volume 1833 of LNCS, pages 172–186. Springer, 2000. E. Makinen. On inferring zero-reversible languages. Acta Cybernetica, 14:479–484, 2000. S. Pilato and R. Berwick. Reversible automata and induction of the english auxiliary system. In Proceedings of the ACL, pages 70–75, 1985. 1744 S UBSTITUTABLE L ANGUAGES L. Pitt. Inductive inference, DFA’s, and computational complexity. In AII ’89: Proceedings of the International Workshop on Analogical and Inductive Inference, pages 18–44. Springer-Verlag, 1989. G. Pullum and B. Scholz. Empirical assessment of stimulus poverty arguments. The Linguistic Review, 19(1-2):9–50, 2002. Florencia Reali and Morten H. Christiansen. Structure dependence in language acquisition: Uncovering the statistical richness of the stimulus. In Proceedings of the 26th Annual Conference of the Cognitive Science Society, Mahwah, NJ, 2004. Lawrence Erlbaum. D. Ron, Y. Singer, and N. Tishby. On the learnability and usage of acyclic probabilistic finite automata. J. Comput. Syst. Sci., 56(2):133–152, 1998. G. S´ nizergues. The equivalence and inclusion problems for NTS languages. J. Comput. Syst. Sci., e 31(3):303–331, 1985. Z. Solan, D. Horn, E. Ruppin, and S. Edelman. Unsupervised context sensitive language acquisition from a large corpus. In Proceedings of NIPS 2003, 2004. B. Starkie. Identifying Languages in the Limit using Alignment Based Learning. PhD thesis, University of Newcastle, Australia, 2004. M. van Zaanen. Implementing alignment-based learning. In Grammatical Inference: Algorithms and Applications, ICGI, volume 2484 of LNCS, pages 312–314. Springer, 2002. M. Wakatsuki and E. Tomita. A fast algorithm for checking the inclusion for very simple deterministic pushdown automata. IEICE Trans. on Information and Systems, E76-D(10):1224–1233, 1993. T. Yokomori. Polynomial-time identification of very simple grammars from positive data. Theoretical Computer Science, 298(1):179–206, 2003. 1745