Beyond Chomsky Normal Form: Extending Strong Learning Algorithms for PCFGs

Alexander Clark
Proceedings of the Fifteenth International Conference on Grammatical Inference, PMLR 153:4-17, 2021.

Abstract

We extend a recent consistent strong learning algorithm for a subclass of probabilistic context-free grammars in Chomsky normal form, (Clark and Fijalkow, 2020) to a much larger class of grammars by weakening the normal form constraints to allow for a richer class of derivation structures that are not necessarily binary branching, including among other possibilities unary branching trees which introduce some technical difficulties. By modifying the structural conditions appropriately we obtain an algorithm which is computationally efficient, and a consistent estimator for the class of grammars defined.

Cite this Paper

BibTeX
@InProceedings{pmlr-v153-clark21a, title = {Beyond Chomsky Normal Form: Extending Strong Learning Algorithms for PCFGs}, author = {Clark, Alexander}, booktitle = {Proceedings of the Fifteenth International Conference on Grammatical Inference}, pages = {4--17}, year = {2021}, editor = {Chandlee, Jane and Eyraud, Rémi and Heinz, Jeff and Jardine, Adam and van Zaanen, Menno}, volume = {153}, series = {Proceedings of Machine Learning Research}, month = {23--27 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v153/clark21a/clark21a.pdf}, url = {https://proceedings.mlr.press/v153/clark21a.html}, abstract = {We extend a recent consistent strong learning algorithm for a subclass of probabilistic context-free grammars in Chomsky normal form, (Clark and Fijalkow, 2020) to a much larger class of grammars by weakening the normal form constraints to allow for a richer class of derivation structures that are not necessarily binary branching, including among other possibilities unary branching trees which introduce some technical difficulties. By modifying the structural conditions appropriately we obtain an algorithm which is computationally efficient, and a consistent estimator for the class of grammars defined.} }
Endnote
%0 Conference Paper %T Beyond Chomsky Normal Form: Extending Strong Learning Algorithms for PCFGs %A Alexander Clark %B Proceedings of the Fifteenth International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2021 %E Jane Chandlee %E Rémi Eyraud %E Jeff Heinz %E Adam Jardine %E Menno van Zaanen %F pmlr-v153-clark21a %I PMLR %P 4--17 %U https://proceedings.mlr.press/v153/clark21a.html %V 153 %X We extend a recent consistent strong learning algorithm for a subclass of probabilistic context-free grammars in Chomsky normal form, (Clark and Fijalkow, 2020) to a much larger class of grammars by weakening the normal form constraints to allow for a richer class of derivation structures that are not necessarily binary branching, including among other possibilities unary branching trees which introduce some technical difficulties. By modifying the structural conditions appropriately we obtain an algorithm which is computationally efficient, and a consistent estimator for the class of grammars defined.
APA
Clark, A.. (2021). Beyond Chomsky Normal Form: Extending Strong Learning Algorithms for PCFGs. Proceedings of the Fifteenth International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 153:4-17 Available from https://proceedings.mlr.press/v153/clark21a.html.

Related Material