Grammatical Inference of PCFGs Applied to Language Modelling and Unsupervised Parsing

Issue title: Grammatical Inference

Guest editors: Rémi Eyraud, Colin de la Higuera, Makoto Kanazawa and Ryo Yoshinaka

Article type: Research Article

Authors: Scicluna, James | de la Higuera, Colin^{*; †}

Affiliations: Université de Nantes, CNRS, LINA, UMR6241, F-44000, France. [email protected]; [email protected]

Correspondence: [†] Address for correspondence: Université de Nantes, CNRS, LINA, UMR6241, F-44000, France

Note: [*] The authors acknowledge partial support by the Région des Pays de la Loire.

Abstract: Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning [1]. However, these results are still not extended to probabilistic grammars. In this work, we give a practical algorithm, with some proven properties, that learns a subclass of probabilistic grammars from positive data. A minimum satisfiability solver is used to direct the search towards small grammars. Experiments on well-known context-free languages and artificial natural language grammars give positive results. Moreover, our analysis shows that the type of grammars induced by our algorithm are, in theory, capable of modelling context-free features of natural language syntax. One of our experiments shows that our algorithm can potentially outperform the state-of-the-art in unsupervised parsing on the WSJ10 corpus.

Keywords: Grammatical Inference, Probabilistic Context-Free Grammars, Minimum Satisfiability, Congruential Grammars, Small Grammars

DOI: 10.3233/FI-2016-1392

Journal: Fundamenta Informaticae, vol. 146, no. 4, pp. 379-402, 2016