Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Gold-Style Learning Theory Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

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

verfasst von : Alexander Clark, Ryo Yoshinaka

Erschienen in: Topics in Grammatical Inference

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Learning Probability Distributions Generated by Finite-State Machines
Nächstes Kapitel Learning Tree Languages
Fußnoten
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.
 
Literatur
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.
Boasson, L., Sénizergues, S.: NTS languages are deterministic and congruential. J. Comput. Syst. Sci. 31(3), 332–342 (1985)MathSciNetCrossRefMATH
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.
Clark, A.: The syntactic concept lattice: Another algebraic theory of the context-free languages? Journal of Logic and Computation (2013). doi:10.​1093/​logcom/​ext037
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)
Metadaten
Titel
Distributional Learning of Context-Free and Multiple Context-Free Grammars
verfasst von
Alexander Clark
Ryo Yoshinaka
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Topics in Grammatical Inference

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

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

Copyright-Jahr: 2016

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