Distributional Learning of Some Nonlinear Tree Grammars

• Autorzy: Clark A. , Kobele G. M. , Kanazawa M. , Yoshinaka R.

Identyfikatory

DOI

10.3233/FI-2016-1391

• Języki publikacji: EN

Abstrakty

EN

A key component of Clark and Yoshinaka’s distributional learning algorithms is the extraction of substructures and contexts contained in the input data. This problem often becomes intractable with nonlinear grammar formalisms due to the fact that more than polynomially many substructures and/or contexts may be contained in each object. Previous works on distributional learning of nonlinear grammars avoided this difficulty by restricting the substructures or contexts that are made available to the learner. In this paper, we identify two classes of nonlinear tree grammars for which the extraction of substructures and contexts can be performed in polynomial time, and which, consequently, admit successful distributional learning in its unmodified, original form.

Słowa kluczowe

EN

distributional learning; tree language; tree pattern; generalized context-free grammar; parallel regular tree grammar; IO context-free tree grammar

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 146, nr 4
• Strony: 339--377
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Clark A.

• Department of Philosophy, King’s College London, UK

autor

Kobele G. M.

• Department of Linguistics and Computation Institute, University of Chicago, USA

autor

Kanazawa M.

• National Institute of Informatics, Tokyo, Japan

autor

Yoshinaka R.

• Graduate School of Informatics, Kyoto University, Japan

Bibliografia

• [1] Clark A. Learning context free grammars with the syntactic concept lattice, in: Sempere and García [16], 2010:38-51. doi:10.1007/978-3-642-15488-1_5.
• [2] Yoshinaka R. Towards dual approaches for learning context-free grammars based on syntactic concept lattices, Developments in Language Theory (G. Mauri, A. Leporati, Eds.), Lecture Notes in Computer Science, Springer, 2011, doi:10.1007/978-3-642-22321-1_37.
• [3] Yoshinaka R. Polynomial-time identification of multiple context-free languages from positive data and membership queries, in: Sempere and García [16], 2010:230-244. doi:10.1007/978-3-642-15488-1_19.
• [4] Kasprzik A, Yoshinaka R. Distributional learning of simple context-free tree grammars, Algorithmic Learning Theory (J. Kivinen, C. Szepesvári, E. Ukkonen, T. Zeugmann, Eds.), 6925 Lecture Notes in Computer Science, Springer, 2011. doi:10.1007/978-3-642-24412-4_31.
• [5] Yoshinaka R, Kanazawa M. Distributional learning of abstract categorial grammars, Logical Aspects of Computational Linguistics (S. Pogodalla, J.-P. Prost, Eds.), 6th International Conference, LACL 2011, Montpellier, France, June 29 July 1, 2011. Proceedings 6736 Lecture Notes in Computer Science, Springer, 2011. doi:10.1007/978-3-642-22221-4_17.
• [6] Clark A, Yoshinaka R. Distributional learning of parallel multiple context-free grammars, Machine Learning, 2014;96(1-2):5-31. doi:10.1007/s10994-013-5403-2.
• [7] Kanazawa M, Yoshinaka R. Distributional learning and context/substructure enumerability in nonlinear tree grammars, Proceedings of Formal Grammar 2015 (A. Foret, G. Morrill, R. Muskens, R. Osswald, Eds.), to appear.
• [8] Pollard CJ. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language, Ph.D. Thesis, Stanford University, 1984.
• [9] Seki H, Matsumura T, Fujii M, Kasami T. On multiple context-free grammars, Theoretical Computer Science, 1991;88(2):191-229. doi:10.1016/0304-3975(91)90374-B.
• [10] Thatcher JW. Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, Journal of Computer and System Sciences, 1967;1(4):317-322. doi:10.1016/S0022-0000(67)80022-9.
• [11] Leiß H. Learning context free grammars with the finite context property: A correction of A. Clark’s algorithm, Formal Grammar (G. Morrill, R. Muskens, R. Osswald, F. Richter, Eds.), 8612 Lecture Notes in Computer Science, Springer, 2014. doi:10.1007/978-3-662-44121-3_8.
• [12] Osherson DN, Stob M, Weinstein S. Systems That Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists, The MIT Press, Cambridge, MA, 1986.
• [13] Engelfriet J, Schmidt EM. IO and OI, part I, The Journal of Computer and System Sciences, 1977; 15(3):328-353. doi:10.1016/S0022-0000(77)80034-2.
• [14] Fischer MJ. Grammars with Macro-Like Productions, Ph.D. Thesis, Harvard University, 1968.
• [15] Yoshinaka R. An attempt towards learning semantics: Distributional learning of IO context-free tree grammars, Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+11), September 2012, Paris, France. Available from: http://aclweb.org/anthology/W12-4611.
• [16] Sempere JM, García P. (Eds). Grammatical Inference: Theoretical Results and Applications. 10th International Colloquium, ICGI 2010, Valencia, Spain, September 13-16, 2010. Proceedings Springer-Verlag. doi:10.1007/978-3-642-15488-1.