Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability

James Scicluna, Colin de la Higuera
The 12th International Conference on Grammatical Inference, PMLR 34:139-152, 2014.

Abstract

Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning (Clark, 2010b). 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 typical context-free languages and artificial natural language grammars give positive results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v34-scicluna14a, title = {Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability}, author = {Scicluna, James and de la Higuera, Colin}, booktitle = {The 12th International Conference on Grammatical Inference}, pages = {139--152}, year = {2014}, editor = {Clark, Alexander and Kanazawa, Makoto and Yoshinaka, Ryo}, volume = {34}, series = {Proceedings of Machine Learning Research}, address = {Kyoto, Japan}, month = {17--19 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v34/scicluna14a.pdf}, url = {https://proceedings.mlr.press/v34/scicluna14a.html}, abstract = {Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning (Clark, 2010b). 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 typical context-free languages and artificial natural language grammars give positive results.} }
Endnote
%0 Conference Paper %T Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability %A James Scicluna %A Colin de la Higuera %B The 12th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2014 %E Alexander Clark %E Makoto Kanazawa %E Ryo Yoshinaka %F pmlr-v34-scicluna14a %I PMLR %P 139--152 %U https://proceedings.mlr.press/v34/scicluna14a.html %V 34 %X Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning (Clark, 2010b). 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 typical context-free languages and artificial natural language grammars give positive results.
RIS
TY - CPAPER TI - Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability AU - James Scicluna AU - Colin de la Higuera BT - The 12th International Conference on Grammatical Inference DA - 2014/08/30 ED - Alexander Clark ED - Makoto Kanazawa ED - Ryo Yoshinaka ID - pmlr-v34-scicluna14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 34 SP - 139 EP - 152 L1 - http://proceedings.mlr.press/v34/scicluna14a.pdf UR - https://proceedings.mlr.press/v34/scicluna14a.html AB - Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning (Clark, 2010b). 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 typical context-free languages and artificial natural language grammars give positive results. ER -
APA
Scicluna, J. & de la Higuera, C.. (2014). Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability. The 12th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 34:139-152 Available from https://proceedings.mlr.press/v34/scicluna14a.html.

Related Material