Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Gold-Style Learning Theory Read chapter Read first chapter

2016 | OriginalPaper | Chapter

6. Distributional Learning of Context-Free and Multiple Context-Free Grammars

Authors : Alexander Clark, Ryo Yoshinaka

Published in: Topics in Grammatical Inference

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter reviews recent progress in distributional learning in grammatical inference as applied to learning context-free and multiple context-free grammars. We discuss the basic principles of distributional learning, and present two classes of representations, primal and dual, where primal approaches use nonterminals based on strings or sets of strings and dual approaches use nonterminals based on contexts or sets of contexts. We then present learning algorithms based on these two models using a variety of learning paradigms, and then discuss the natural extension to mildly context-sensitive formalisms, using multiple context-free grammars as a representative formalism.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Learning Probability Distributions Generated by Finite-State Machines
next chapter Learning Tree Languages
Footnotes
1
See Learning Grammars and Automata with Queries, de la Higuera (Chap. 3).
 
2
The original paper defining this [12] unfortunately contains some errors.
 
3
An infinite language L is said to have the constant-growth property if \(\exists k \in \mathbb {N}. \forall u \in L. \exists v \in L.\ 0< |v|-|u| \le k\).
 
4
It is worth noting that MCFGs may be much larger than the smallest equivalent Minimalist Grammar.
 
5
The notation adopted in this chapter follows Smullyan’s elementary formal systems [55] rather than [48].
 
6
We only consider non-deleting productions in this chapter.
 
7
Technically speaking, the OT for the highest dimension subsumes the other ones for lower dimensions, since m-contexts and m-words can be seen as special cases of n-contexts and n-words, respectively, for \(m < n\): e.g., \(l \Box r \Box \odot _2 \langle u,\lambda \rangle = l \Box r \odot u\). However, there are cases where it is more reasonable to exclude the empty string from consideration.
 
8
The original definition [66] has a slightly weaker form, where strings \(m,u_1,u_2,v_1,v_2\) are restricted to be non-empty strings. \(ab^*cd^*e\) is 2d-substitutable according to the original definition, but it is not the case in our simplified definition.
 
Literature
1.
Adriaans, P.: Learning shallow context-free languages under simple distributions. Tech. Rep. ILLC Report PP-1999-13, Institute for Logic, Language and Computation, Amsterdam (1999)
2.
3.
4.
5.
Brill, E., Magermann, D., Marcus, M., Santorini, B.: Deducing linguistic structure from the statistics of large corpora. In: Proceedings of the Third DARPA Workshop on Speech and Natural Language, pp. 275–282 (1990)
6.
Chomsky, N.: The logical structure of linguistic theory. Ph.D. thesis, MIT (1955)
7.
Chomsky, N.: Language and mind, 3rd edn. Cambridge University Press (2006)
8.
Clark, A.: PAC-learning unambiguous NTS languages. In: Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino, E. Tomita (eds.) Grammatical Inference: Algorithms and Applications, Lecture Notes in Computer Science, vol. 4201, pp. 59–71. Springer Berlin Heidelberg (2006)CrossRef
9.
10.
Clark, A.: Distributional learning of some context-free languages with a minimally adequate teacher. In: J. Sempere, P. García (eds.) Proceedings of ICGI, no. 6339 in LNCS, pp. 24–37. Springer (2010)
11.
Clark, A.: Efficient, correct, unsupervised learning of context-sensitive languages. In: Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pp. 28–37. Association for Computational Linguistics, Uppsala, Sweden (2010)
12.
Clark, A.: Learning context free grammars with the syntactic concept lattice. In: J. Sempere, P. García (eds.) Grammatical Inference: Theoretical Results and Applications. Proceedings of the International Colloquium on Grammatical Inference, pp. 38–51. Springer (2010)
13.
Clark, A.: Inference of inversion transduction grammars. In: Proceedings of ICML. Bellevue, Washington (2011)
14.
15.
Clark, A.: Learning trees from strings: A strong learning algorithm for some context-free grammars. Journal of Machine Learning Research 14, 3537–3559 (2014)MathSciNetMATH
16.
Clark, A., Eyraud, R.: Polynomial identification in the limit of substitutable context-free languages. Journal of Machine Learning Research 8, 1725–1745 (2007)MathSciNetMATH
17.
Clark, A., Eyraud, R., Habrard, A.: Using contextual representations to efficiently learn context-free languages. Journal of Machine Learning Research 11, 2707–2744 (2010)MathSciNetMATH
18.
Clark, A., Yoshinaka, R.: Beyond semilinearity: Distributional learning of parallel multiple context-free grammars. In: J. Heinz, C. de la Higuera, T. Oates (eds.) Proceedings of the Eleventh International Conference on Grammatical Inference, JMLR Workshop and Conference Proceedings, vol. 21, pp. 84–96 (2012)
19.
20.
Dediu, A.H., Martín-Vide, C. (eds.): Language and Automata Theory and Applications - 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7183. Springer (2012)
21.
Eyraud, R., Janodet, J., Oates, T.: Learning substitutable binary plane graph grammars. In: Proceedings of ICGI, vol. 21, pp. 114–128 (2012)
22.
Fisher, M.J.: Grammars with macro-like productions. Ph.D. thesis, Harvard University (1968)
23.
Gold, E.M.: Language identification in the limit. Information and Computation 10(5), 447–474 (1967)MATH
24.
Harris, Z.: Distributional structure. Word 10(2-3), 146–62 (1954)
25.
26.
Huybrechts, R.A.C.: The weak inadequacy of context-free phrase structure grammars. In: G. de Haan, M. Trommelen, W. Zonneveld (eds.) Van Periferie naar Kern. Foris, Dordrecht, Holland (1984)
27.
Joshi, A.K.: Tree adjoining grammars: how much context-sensitivity is required to provide reasonable structural descriptions? In: D.R. Dowty, L. Karttunen, A. Zwicky (eds.) Natural Language Parsing, pp. 206–250. Cambridge University Press, Cambridge, MA (1985)CrossRef
28.
Joshi, A.K., Vijay-Shanker, K., Weir, D.J.: The convergence of mildly context-sensitive grammar formalisms. In: P. Sells, S.M. Shieber, T. Wasow (eds.) Foundational Issues in Natural Language Processing, pp. 31–81. MIT Press, Cambridge, MA (1991)
29.
Kaji, Y., Nakanishi, R., Seki, H., Kasami, T.: The universal recognition problems for parallel multiple context-free grammars and for their subclasses. IEICE Transaction on Information and Systems E75-D(7), 499–508 (1992)
30.
Kanazawa, M., Salvati, S.: The copying power of well-nested multiple context-free grammars. In: Language and Automata Theory and Applications, pp. 344–355. Springer (2010)
31.
Kanazawa, M., Salvati, S.: Mix is not a tree-adjoining language. In: ACL (1), pp. 666–674. The Association for Computer Linguistics (2012)
32.
Kasprzik, A., Yoshinaka, R.: Distributional learning of simple context-free tree grammars. In: J. Kivinen, C. Szepesvári, E. Ukkonen, T. Zeugmann (eds.) Algorithmic Learning Theory, Lecture Notes in Computer Science, vol. 6925, pp. 398–412. Springer (2011)
33.
Keller, B., Lutz, R.: Evolutionary induction of stochastic context free grammars. Pattern Recognition 38(9), 1393–1406 (2005)CrossRefMATH
34.
Klein, D., Manning, C.D.: A generative constituent-context model for improved grammar induction. In: Proceedings of the 40th Annual Meeting of the ACL (2002)
35.
Kracht, M.: The Mathematics of Language, Studies in Generative Grammar, vol. 63, pp. 408–409. Mouton de Gruyter (2003)
36.
Kulagina, O.S.: One method of defining grammatical concepts on the basis of set theory. Problemy Kiberneticy 1, 203–214 (1958). (in Russian)
37.
Kunze, J.: Versuch eines objektivierten Grammatikmodells I, II. Z. Zeitschriff Phonetik Sprachwiss. Kommunikat 20-21 (1967–1968)
38.
Langley, P., Stromsten, S.: Learning context-free grammars with a simplicity bias. In: R. López de Mántaras, E. Plaza (eds.) Machine Learning: ECML 2000, Lecture Notes in Computer Science, vol. 1810, pp. 220–228. Springer Berlin Heidelberg (2000)CrossRef
39.
Leiss, H.: Learning CFGs with the finite context property: A note on A. Clark’s algorithm (2012). Manuscript
40.
Luque, F.M., Infante-Lopez, G.: PAC-learning unambiguous \(k,l\)-NTS\(^{\le }\) languages. In: J.M. Sempere, P. García (eds.) Grammatical Inference: Theoretical Results and Applications, Lecture Notes in Computer Science, vol. 6339, pp. 122–134. Springer Berlin Heidelberg (2010)CrossRef
41.
Marcus, S.: Algebraic Linguistics; Analytical Models. Academic Press, New York (1967)
42.
Myhill, J.: Review of On Syntactical Categories by Yehoshua Bar-Hillel. The Journal of Symbolic Logic 15(3), 220 (1950)CrossRef
43.
Oncina, J., García, P., Vidal, E.: Learning subsequential transducers for pattern recognition interpretation tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence 15, 448–458 (1993)CrossRef
44.
Pitt, L.: Inductive inference, DFAs, and computational complexity. In: Proceedings of 2nd Workshop on Analogical and Inductive Inference, Lecture Notes in Computer Science, vol. 397, pp. 18–44 (1989)
45.
Rambow, O., Satta, G.: Independent parallelism in finite copying parallel rewriting systems. Theor. Comput. Sci. 223(1-2), 87–120 (1999)MathSciNetCrossRefMATH
46.
Sakakibara, Y.: Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science 76(2-3), 223–242 (1990)MathSciNetCrossRefMATH
47.
48.
Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoretical Computer Science 88(2), 191–229 (1991)MathSciNetCrossRefMATH
49.
Sénizergues, G.: The equivalence and inclusion problems for NTS languages. Journal of Computer and System Sciences 31(3), 303–331 (1985)MathSciNetCrossRefMATH
50.
Sestier, A.: Contribution à une théorie ensembliste des classifications linguistiques. In: Premier Congrès de l’Association Française de Calcul, pp. 293–305. Grenoble (1960)
51.
Shibata, C., Yoshinaka, R.: PAC learning of some subclasses of context-free grammars with basic distributional properties from positive data. In: S. Jain, R. Munos, F. Stephan, T. Zeugmann (eds.) ALT, Lecture Notes in Computer Science, vol. 8139, pp. 143–157. Springer (2013)
52.
Shieber, S.M.: Evidence against the context-freeness of natural language. Linguistics and Philosophy 8, 333–343 (1985)CrossRef
53.
Shinohara, T.: Rich classes inferrable from positive data – length-bounded elementary formal systems. Information and computation 108(2), 175–186 (1994)MathSciNetCrossRefMATH
54.
Shirakawa, H., Yokomori, T.: Polynomial-time MAT learning of c-deterministic context-free grammars. Transactions of the Information Processing Society of Japan 34, 380–390 (1993)
55.
Smullyan, R.: Theory of Formal Systems. Princeton University Press (1961)
56.
Stabler, E.: Derivational minimalism. In: C. Retoré (ed.) Logical aspects of computational linguistics (LACL 1996), pp. 68–95. Springer (1997)
57.
van Helden, W.: Case and gender: Concept formation between morphology and syntax (II volumes). Studies in Slavic and General Linguistics. Rodopi, Amsterdam-Atlanta (1993)
58.
van Zaanen, M.: ABL: Alignment-based learning. In: COLING 2000 - Proceedings of the 18th International Conference on Computational Linguistics, pp. 961–967 (2000)
59.
Vijay-Shanker, K., Weir, D.J.: The equivalence of four extensions of context-free grammars. Mathematical Systems Theory 27(6), 511–546 (1994)MathSciNetCrossRefMATH
60.
Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Characterizing structural descriptions produced by various grammatical formalisms. In: Proceedings of the 25th annual meeting of Association for Computational Linguistics, pp. 104–111. Stanford (1987)
61.
62.
Wurm, C.: Completeness of full Lambek calculus for syntactic concept lattices. In: Proceedings of the 17th conference on Formal Grammar 2012 (FG) (2012)
63.
Yoshinaka, R.: Identification in the limit of \(k,l\)-substitutable context-free languages. In: A. Clark, F. Coste, L. Miclet (eds.) ICGI, Lecture Notes in Computer Science, vol. 5278, pp. 266–279. Springer (2008)
64.
Yoshinaka, R.: Learning mildly context-sensitive languages with multidimensional substitutability from positive data. In: R. Gavaldà, G. Lugosi, T. Zeugmann, S. Zilles (eds.) ALT, Lecture Notes in Computer Science, vol. 5809, pp. 278–292. Springer (2009)
65.
Yoshinaka, R.: Polynomial-time identification of multiple context-free languages from positive data and membership queries. In: J.M. Sempere, P. García (eds.) ICGI, pp. 230–244. Springer (2010)
66.
Yoshinaka, R.: Efficient learning of multiple context-free languages with multidimensional substitutability from positive data. Theoretical Computer Science 412(19), 1821–1831 (2011)MathSciNetCrossRefMATH
67.
Yoshinaka, R.: Towards dual approaches for learning context-free grammars based on syntactic concept lattices. In: G. Mauri, A. Leporati (eds.) Developments in Language Theory, Lecture Notes in Computer Science, vol. 6795, pp. 429–440. Springer (2011)
68.
Yoshinaka, R.: Integration of the dual approaches in the distributional learning of context-free grammars. In: Dediu and Martín-Vide [20], pp. 538–550
69.
Yoshinaka, R., Clark, A.: Polynomial time learning of some multiple context-free languages with a minimally adequate teacher. In: P. de Groote, M.J. Nederhof (eds.) Formal Grammar: 15th and 16th International Conference on Formal Grammar, pp. 192–206. Springer (2012)
70.
Yoshinaka, R., Kanazawa, M.: Distributional learning of abstract categorial grammars. In: S. Pogodalla, J.P. Prost (eds.) LACL, Lecture Notes in Computer Science, vol. 6736, pp. 251–266. Springer (2011)
Metadata
Title
Distributional Learning of Context-Free and Multiple Context-Free Grammars
Authors
Alexander Clark
Ryo Yoshinaka
Copyright Year
2016
Publisher
Springer Berlin Heidelberg
Book
Topics in Grammatical Inference

Print ISBN: 978-3-662-48393-0

Electronic ISBN: 978-3-662-48395-4

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-662-48395-4_6

Premium Partner

    Image Credits