Linguistic Models at the Crossroads of Agents, Learning and Formal Languages

Abstract

This paper aims at reviewing the most relevant linguistic applications developed in the intersection between three different fields: machine learning, formal language theory and agent technologies. On the one hand, we present some of the main linguistic contributions of the intersection between machine learning and formal languages, which constitutes a well-established research area known as Grammatical Inference. On the other hand, we present an overview of the main linguistic applications of models developed in the intersection between agent technologies and formal languages, such as colonies, grammar systems and eco-grammar systems. Our goal is to show how interdisciplinary research between these three fields can contribute to better understand how natural language is acquired and processed.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Adriaans, P., 1992. Language learning from a categorial perspective. Ph.D. thesis, University of Amsterdam.

Angluin, D., 1982. Inference of reversible languages. Journal of the Association for Computing Machinery, 29(3):741–765.
http://dx.doi.org/10.1145/322326.322334

Angluin, D. and Becerra-Bonache, L., 2008. Learning Meaning Before Syntax. In ICGI: International Colloquium on Grammatical Inference, pages 1–14. Berlin.
http://dx.doi.org/10.1007/978-3-540-88009-7_1

Angluin, D. and Becerra-Bonache, L., 2010. A model of semantics and corrections in language learning. YALEU/DCS/TR-1425.

Angluin, D. and Becerra-Bonache, L., 2011. Effects of Meaning-Preserving Corrections on Language Learning. In CoNLL: International Conference on Computational Natural Language Learning, pages 97–105.

Bartlett, M. and Kazakov, D., 2004. The role of environment structure in multi-agent simulations of language evolution. In Proceedings of the Fourth Symposium on Adaptive Agents and Multi-Agent Systems. Springer.

Bayley, R., Cameron, R., and Lucas, C., 2013. The Oxford Handbook of Sociolinguistics. Oxford University Press, Oxford.
http://dx.doi.org/10.1093/oxfordhb/9780199744084.001.0001

Becerra-Bonache, L., 2006. On the Learnability of Mildly Context-Sensitive Languages using Positive Data and Correction Queries. Ph.D. thesis, Rovira i Virgili University.

Becerra-Bonache, L., Case, J., Jain, S., and Stephan, F., 2010. Iterative learning of simple external contextual languages. Theoretical Computer Science, 411:2741–2756.
http://dx.doi.org/10.1016/j.tcs.2010.04.009

Becerra-Bonache, L. and Yokomori, T., 2004. Learning Mild Context-Sensitiveness: Toward Understanding Children's Language Learning. In ICGI: International Colloquium on Grammatical Inference, pages 53–64.

Bel-Enguix, G. and Jiménez-López, M., 2008. Modelling dialogue as inter-action. International Journal of Speech Technology, 11(3/4):209–221.
http://dx.doi.org/10.1007/s10772-009-9052-6

Bel-Enguix, G., Jiménez-López, M., and Martín-Vide, C., 2009. Using finite-state methods for getting infinite languages: A preview. Romanian Journal of Information, Science and Technology, 12(2):125–137.

Bonnema, R., Bod, R., and Scha, R., 1997. A DOP Model for Semantic Interpretation. In 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pages 159–167.

Bresnan, J., Kaplan, R., Peters, S., and Zaenen, A., 1987. Cross-Serial Dependencies in Dutch. In Savitch, W., Bach, E., Marsh, W., and Safran-Naveh, G., editors, The Formal Complexity of Natural Language, pages 286–319. D. Reidel, Dordrecht.

Brooks, R., 1990. Elephants don't play chess. Robotics and Autonomous Systems, 6:3–15.
http://dx.doi.org/10.1016/S0921-8890(05)80025-9

Cangelosi, A., 2007. Adaptive agent modeling of distributed language: investigations on the effects of cultural variation and internal action representations. Language Sciences, 29(5):633–549.
http://dx.doi.org/10.1016/j.langsci.2006.12.026

Cangelosi, A. and Parisi, D., 2001. Computer simulation: A new scientific approach to the study of language evolution. In Cangelosi, A. and Parisi, D., editors, Simulating the Evolution of Language, pages 3–28. Springer.

Casacuberta, F. and Vidal, E., 2007. Learning finite-state models for machine translation. Machine Learning, 66(1):69–91.
http://dx.doi.org/10.1007/s10994-006-9612-9

Chomsky, N., 1956. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113–124.
http://dx.doi.org/10.1109/TIT.1956.1056813

Chouinard, M. and Clark, E., 2003. Adult Reformulations of Child Errors as Negative Evidence. Journal of Child Language, 30:637–669.
http://dx.doi.org/10.1017/S0305000903005701

Christiansen, M. and Kirbi, S., 2003. Language evolution: Consensus and controversy. Trends in Cognitive Sciences, 7(7):300–307.
http://dx.doi.org/10.1016/S1364-6613(03)00136-0

Clark, A. and Yoshinaka, R., 2014. Distributional learning of parallel multiple context-free grammars. Machine Learning, 96(1-2):5–31.
http://dx.doi.org/10.1007/s10994-013-5403-2

Csuhaj-Varjú, E., Dassow, J., Kelemen, J., and P?aun, G., 1994. Grammar systems: A grammatical approach to distribution and cooperation. Gordon and Breach, London.

Csuhaj-Varjú, E., Kelemen, J., Kelemenová, A., and P?aun, G., 1996. Eco-grammar systems: A grammatical framework for life-like interactions. Artificial Life, 3(1):1–28.
http://dx.doi.org/10.1162/artl.1997.3.1.1

Culy, C., 1987. The Complexity of the Vocabulary of Bambara. In Savitch, W., Bach, E., Marsh, W., and Safran-Naveh, G., editors, The Formal Complexity of Natural Language, pages 349–357.

D'Ulizia, A., Ferri, F., and Grifoni, P., 2011. A survey of grammatical inference methods for natural language learning. Artificial Intelligence Review, 36(1):1–27.
http://dx.doi.org/10.1007/s10462-010-9199-1

García, P. and Vidal, E., 1990. Inference of k-Testable Languages in the Strict Sense and Application to Syntactic Pattern Recognition. IEEE Trans. Pattern Anal. Mach. Intell., 12(9):920–925.
http://dx.doi.org/10.1109/34.57687

Gazdar, G. and Pullum, G. K., 1985. Computationally Relevant Properties of Natural Languages and Their Grammars. New Generation Computing, 3:273–306.
http://dx.doi.org/10.1007/BF03037123

Geeraerts, D. and Cuyckens, H., 2010. The Oxford Handbook of Cognitive Linguistics. Oxford University Press, Oxford.
http://dx.doi.org/10.1093/oxfordhb/9780199738632.001.0001

Gold, E., 1967. Language identification in the limit. Information and Control, 10:447–474.
http://dx.doi.org/10.1016/S0019-9958(67)91165-5

de la Higuera, C., 2010. Grammatical Inference: Learning Automata and Grammars. Cambridge University Press.
http://dx.doi.org/10.1017/cbo9781139194655

Horn, L. and Ward, G., 2005. The Handbook of Pragmatics. Blackwell, Oxford.
http://dx.doi.org/10.1111/b.9780631225485.2005.x

Jiménez-López, M., 2006. A grammar systems approach to natural language grammar. Linguistics and Philosophy, 29:419–454.
http://dx.doi.org/10.1007/s10988-006-0008-x

Jiménez-López, M., 2012. A grammar-based multi-agent system for language evolution. In Bajo Pérez, J. e. a., editor, Highlights on Practical Applications of Agents and Multiagent Systems, pages 45–52. Springer.
http://dx.doi.org/10.1007/978-3-642-28762-6_6

Joshi, A. K., 1985. How Much Context-Sensitivity is Required to Provide Reasonable Structural Descriptions: Tree Adjoining Grammars. In Dowty, D., Karttunen, L., and Zwicky, A., editors, Natural Language Parsing: Psychological, Computational and Theoretical Perspectives, pages 206–250. Cambridge University Press, New York, NY.

Joshi, A. K. and Schabes, Y., 1997. Tree-Adjoining Grammars. In Rozenberg, G. and Salomaa, A., editors, Handbook of Formal Languages, volume 3, pages 69–123. Springer-Verlag, Berlin.
http://dx.doi.org/10.1007/978-3-642-59126-6_2

Kelemen, J. and Kelemenová, A., 1992. A grammar-theoretic treatment of multiagent systems. Cybernetics and Systems, 23:621–633.
http://dx.doi.org/10.1080/01969729208927485

Kudlek, M., Martín-Vide, C., Mateescu, A., and Mitrana, V., 2002. Contexts and the concept of mild context-sensitivity. Linguistics and Philosophy, 26(6):703–725.
http://dx.doi.org/10.1023/B:LING.0000004545.49963.94

Langton, C., 1989. Artificial Life. In Langton, C., editor, Artificial Life, pages 1–47. Addison-Wesley.

Lappin, S., 1997. The Handbook of Contemporary Semantic Theory. Blackwell, Oxford.
http://dx.doi.org/10.1111/b.9780631207498.1997.x

Manaster-Ramer, A., 1999. Some Uses and Abuses of Mathematics in Linguistics. In Martín-Vide, C., editor, Issues in Mathematical Linguistics, pages 73–130. John Benjamins, Amsterdam.
http://dx.doi.org/10.1075/sfsl.47.07man

Marcus, M. P., Santorini, B., and Marcinkiewicz, M. A., 1993. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330.

Newmeyer, F., 1997. Generative Linguistics: An Historical Perspective. Routledge, London.

Oates, T., Armstrong, T., Becerra-Bonache, L., and Atamas, M., 2006. Inferring grammars for mildly context sensitive languages in polynomial-time. In ICGI: International Colloquium on Grammatical Inference, pages 137–147.
http://dx.doi.org/10.1007/11872436_12

Oncina, J. and García, P., 1992. Identifying Regular Languages In Polynomial Time. In Advances in Structural and Syntactic Pattern Recognition, pages 99–108. World Scientific.

Post, E., 1936. Finite combinatory processes-formulation. Journal of Symbolic Logic, 1:103–105.
http://dx.doi.org/10.2307/2269031

Reitter, D. and Lebiere, C., 2010. Did social networks shape language evolution? A Multi-Agent Cognitive Simulation. In Proceedings of ACL 2010, pages 9–17. ACL.

Roach, K., 1987. Formal Porperties of Head Grammars. In Manaster-Ramer, A., editor, Mathematics of Language, pages 293–348. John Benjamins, Amsterdam.
http://dx.doi.org/10.1075/z.35.15roa

Rozenberg, G. and Salomaa, A., 1997. Handbook of Dormal Languages. Springer, Berlin.

Sadock, J., 1991. Autolexical syntax. A theory of parallel grammatical representations. University of Chicago Press, Chicago.

Sakakibara, Y., 1992. Efficient learning of context-free grammars from positive structural examples. Information Processing Letters, 97:23–60.
http://dx.doi.org/10.1016/0890-5401(92)90003-x

Shieber, S., 1987. Evidence Against the Context-Freeness of Natural Languages. In Savitch, W., Bach, E., Marsh, W., and Safran-Naveh, G., editors, The Formal Complexity of Natural Language, pages 320–334. D. Reidel, Dordrecht.

Solan, Z., Horn, D., Ruppin, E., and Edelman, S., 2005. Unsupervised learning of natural languages. In Proceedings of the National Academy of Sciences of the USA, volume 102(33), pages 11629–11634.
http://dx.doi.org/10.1073/pnas.0409746102

Steedman, M., 1985. Dependency and Coordination in the grammar of Dutch and English. Language, 61:523–568.
http://dx.doi.org/10.2307/414385

Steels, L., 2006. How to do experiments in artificial language evolution and why. In Proceedings of the 6th International Conference on the Evolution of Language, pages 323–332.
http://dx.doi.org/10.1142/9789812774262_0041

Thue, A., 1906. Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Kristiania, 7:1–22.

Thue, A., 1912. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Kristiania, 1:1–67.

Turing, A., 1936. On computable numbers with an application to the Entscheidungsproblem. In Proceedings London Mathematical Society, pages 230–265.

Yoshinaka, R., 2009. Learning Mildly Context-Sensitive Languages with Multidimensional Substitutability from Positive Data. In ALT: International Conference on Algorithmic Learning Theory, pages 278–292.
http://dx.doi.org/10.1007/978-3-642-04414-4_24

van Zaanen, M., 2001. ABL: Alignment-Based Learning. CoRR, cs.LG/0104006.

van Zaanen, M., Roberts, A., and Atwell, E., 2004. A multilingual parallel parsed corpus as gold standard for grammatical inference evaluation. In In LREC: Workshop on The Amazing Utility of Parallel and Comparable Corpora, pages 58–61.
Becerra-Bonache, L., & Jiménez López, M. D. (2014). Linguistic Models at the Crossroads of Agents, Learning and Formal Languages. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 3(4), 67–87. https://doi.org/10.14201/ADCAIJ2014346787

Downloads

Download data is not yet available.

Author Biographies

Leonor Becerra-Bonache

,
Jean Monnet University
Laboratoire Hubert Curien, maitre de conference

M. Dolores Jiménez López

,
Universitat Rovira i Virgili
Departament de Filologies Romàniques. Profesor agregado
+