acl acl2010 acl2010-217 acl2010-217-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jeffrey Heinz
Abstract: This paper provides a unified, learningtheoretic analysis of several learnable classes of languages discussed previously in the literature. The analysis shows that for these classes an incremental, globally consistent, locally conservative, set-driven learner always exists. Additionally, the analysis provides a recipe for constructing new learnable classes. Potential applications include learnable models for aspects of natural language and cognition.
Dana Angluin. 1980a. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46–62. Dana Angluin. 1980b. Inductive inference of formal languages from positive data. Information Control, 45: 117–135. Dana Angluin. 1988. Identifying languages from stochastic examples. Technical Report 614, Yale University, New Haven, CT. D. Beauquier and J.E. Pin. 1991. Languages and scanners. Theoretical Computer Science, 84:3–21 . Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. 1989. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 36(4):929–965. J.A. Brzozowski and I. Simon. 1973. Characterization of locally testable events. Discrete Math, 4:243– 271. J.A. Brzozowski. 1962. Canonical regular expressions and minimal state graphs for definite events. In Mathematical Theory of Automata, pages 529–561 . New York. Nicola Cancedda, Eric Gaussier, Cyril Goutte, and Jean-Michel Renders. 2003. Word-sequence kernels. Journal of Machine Learning Research, 3: 1059–1082. Pascal Caron. 2000. Families of locally testable languages. Theoretical Computer Science, 242:361– 376. John Case and Sam Moelius. 2007. Parallelism increases iterative learning power. In 18th Annual Conference on Algorithmic Learning Theory (ALT07), volume 4754 of Lecture Notes in Artificial Intelligence, pages 49–63. Springer-Verlag, Berlin. John Case, Sanjay Jain, Steffen Lange, and Thomas Zeugmann. 1999. Incremental concept learning for bounded data mining. Information and Computation, 152:74–1 10. Kyle E. Chambers, Kristine H. Onishi, and Cynthia Fisher. 2002. Learning phonotactic constraints from brief auditory experience. Cognition, 83:B 13–B23. Alexander Clark, Christophe Costa Flor eˆncio, and Chris Watkins. 2006a. Languages as hyperplanes: grammatical inference with string kernels. In Proceedings of the European Conference on Machine Learning (ECML), pages 90–101 . Alexander Clark, Christophe Costa Flor eˆncio, Chris Watkins, and Mariette Serayet. 2006b. Planar languages and learnability. In Proceedings of the 8th International Colloquium on GrammaticalInference (ICGI), pages 148–160. Alejandrina Cristi´ a and Amanda Seidl. 2008. Phonological features in infants phonotactic learning: Evidence from artificial grammar learning. Language, Learning, and Development, 4(3):203–227. Colin de la Higuera. 1997. Characteristic sets for polynomial grammatical inference. Machine Learning, 27: 125–138. Matt Edlefsen, Dylan Leeman, Nathan Myers, Nathaniel Smith, Molly Visscher, and David Wellcome. 2008. Deciding strictly local (SL) languages. In Jon Breitenbucher, editor, Proceedings of the Midstates Conference for Undergraduate Research in Computer Science andMathematics, pages 66–73. Henning Fernau. 2003. Identification of function distinguishable languages. Theoretical Computer Science, 290: 1679–171 1. C.R. Gallistel and Adam Philip King. 2009. Memory and the Computational Brain. Wiley-Blackwell. Pedro Garc ı´a and Jos e´ Ruiz. 1996. Learning kpiecewise testable languages from positive data. In Laurent Miclet and Colin de la Higuera, editors, Grammatical Interference: Learning Syntax from Sentences, volume 1147 of Lecture Notes in Computer Science, pages 203–210. Springer. Pedro Garc ı´a and Jos e´ Ruiz. 2004. Learning k-testable and k-piecewise testable languages from positive data. Grammars, 7: 125–140. Pedro Garcia, Enrique Vidal, and Jos e´ Oncina. 1990. Learning locally testable languages in the strict sense. In Proceedings of the Workshop on Algorithmic Learning Theory, pages 325–338. E.M. Gold. 1967. Language identification in the limit. Information and Control, 10:447–474. J. Grainger and C. Whitney. 2004. Does the huamn mnid raed wrods as a wlohe? Trends in Cognitive Science, 8:58–59. 905 Jeffrey Heinz and James Rogers. strictly piecewise distributions. the ACL. Jeffrey Heinz. 2007. 2010. Estimating In Proceedings of The Inductive Learning of Phonotactic Patterns. Ph.D. thesis, University of California, Los Angeles. Jeffrey Heinz. 2009. On the role of locality in learning stress patterns. Phonology, 26(2):303–35 1. Jeffrey Heinz. to appear. Learning long distance phonotactics. Linguistic Inquiry. J. J. Horning. 1969. A Study of Grammatical Inference. Ph.D. thesis, Stanford University. Sanjay Jain, Daniel Osherson, James S. Royer, and Arun Sharma. 1999. Systems That Learn: An Introduction to Learning Theory (Learning, Development and Conceptual Change). The MIT Press, 2nd edition. Sanjay Jain, Steffen Lange, and Sandra Zilles. 2007. Some natural conditions on incremental learning. Information and Computation, 205(1 1): 1671–1684. Daniel Jurafsky and James Martin. 2008. Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics. Prentice-Hall, Upper Saddle River, NJ, 2nd edition. Anna Kasprzik and Timo K ¨otzing. to appear. String extension learning using lattices. In Proceedings of the 4th International Conference on Language and Automata Theory and Applications (LATA 2010), Trier, Germany. S.M. Kim, R. McNaughton, and R. McCloskey. 1991. A polynomial time algorithm for the local testability problem of deterministic finite automata. IEEE Trans. Comput., 40(10):1087–1093. Leonid (Aryeh) Kontorovich, Corinna Cortes, and Mehryar Mohri. 2008. Kernel methods for learning languages. Theoretical Computer Science, 405(3):223 236. Algorithmic Learning Theory. – Steffen Lange, Thomas Zeugmann, and Sandra Zilles. 2008. Learning indexed families of recursive languages from positive data: A survey. Theoretical Computer Science, 397: 194–232. H. Lodhi, N. Cristianini, J. Shawe-Taylor, and C. Watkins. 2002. Text classification using string kernels. Journal of Machine Language Research, 2:419–444. M. Lothaire, editor. 2005. Applied Combinatorics on Words. Cmbridge University Press, 2nd edition. Robert McNaughton and Seymour Papert. Counter-Free Automata. MIT Press. 197 1. R. McNaughton. 1974. Algebraic decision procedures for local testability. Math. Systems Theory, 8:60–76. Kristine H. Onishi, Kyle E. Chambers, and Cynthia Fisher. 2003. Infants learn phonotactic regularities from brief auditory experience. Cognition, 87:B69– B77. R. J. Parikh. 1966. On context-free languages. Journal of the ACM, 13, 570581., 13:570–581. James Rogers and Geoffrey Pullum. to appear. Aural pattern recognition experiments and the subregular hierarchy. Journal of Logic, Language and Information. James Rogers, Jeffrey Heinz, Gil Bailey, Matt Edlefsen, Molly Visscher, David Wellcome, and Sean Wibel. 2009. On languages piecewise testable in the strict sense. In Proceedings of the 11th Meeting of the Assocation for Mathematics of Language. John Shawe-Taylor and Nello Christianini. 2005. Kernel Methods for Pattern Analysis. Cambridge University Press. Imre Simon. 1975. Piecewise testable events. In Automata Theory and Formal Languages, pages 214– 222. Imre Simon. 1993. The guages. In ICALP ’93: International Colloquium and Programming, pages Springer-Verlag. product of rational lanProceedings of the 20th on Automata, Languages 430–444, London, UK. Carol Whitney and Piers Cornelissen. 2008. SERIOL reading. Language and Cognitive Processes, 23: 143–164. Carol Whitney. der of letters and selective letin Review, 2001. How the brain encodes the orin a printed word: the SERIOL model literature review. Psychonomic Bul8:221–243. 906