Extending Distributional Learning from Positive Data and Membership Queries

Makoto Kanazawa, Ryo Yoshinaka
Proceedings of 16th edition of the International Conference on Grammatical Inference, PMLR 217:8-22, 2023.

Abstract

We consider an extension of distributional learning of context-free languages (from positive data and membership queries), where nonterminals are represented by extended regular expressions (allowing all Boolean operations) augmented by atoms corresponding to membership queries. These nonterminals classify a string based not just on its distribution, but also on the distributions of its substrings. The learning algorithm for this extension works in essentially the same way as in previous works on distributional learning, while targeting a significantly larger class of context-free languages.

Cite this Paper


BibTeX
@InProceedings{pmlr-v217-kanazawa23a, title = {Extending Distributional Learning from Positive Data and Membership Queries}, author = {Kanazawa, Makoto and Yoshinaka, Ryo}, booktitle = {Proceedings of 16th edition of the International Conference on Grammatical Inference}, pages = {8--22}, year = {2023}, editor = {Coste, Fran├žois and Ouardi, Faissal and Rabusseau, Guillaume}, volume = {217}, series = {Proceedings of Machine Learning Research}, month = {10--13 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v217/kanazawa23a/kanazawa23a.pdf}, url = {https://proceedings.mlr.press/v217/kanazawa23a.html}, abstract = {We consider an extension of distributional learning of context-free languages (from positive data and membership queries), where nonterminals are represented by extended regular expressions (allowing all Boolean operations) augmented by atoms corresponding to membership queries. These nonterminals classify a string based not just on its distribution, but also on the distributions of its substrings. The learning algorithm for this extension works in essentially the same way as in previous works on distributional learning, while targeting a significantly larger class of context-free languages.} }
Endnote
%0 Conference Paper %T Extending Distributional Learning from Positive Data and Membership Queries %A Makoto Kanazawa %A Ryo Yoshinaka %B Proceedings of 16th edition of the International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2023 %E Fran├žois Coste %E Faissal Ouardi %E Guillaume Rabusseau %F pmlr-v217-kanazawa23a %I PMLR %P 8--22 %U https://proceedings.mlr.press/v217/kanazawa23a.html %V 217 %X We consider an extension of distributional learning of context-free languages (from positive data and membership queries), where nonterminals are represented by extended regular expressions (allowing all Boolean operations) augmented by atoms corresponding to membership queries. These nonterminals classify a string based not just on its distribution, but also on the distributions of its substrings. The learning algorithm for this extension works in essentially the same way as in previous works on distributional learning, while targeting a significantly larger class of context-free languages.
APA
Kanazawa, M. & Yoshinaka, R.. (2023). Extending Distributional Learning from Positive Data and Membership Queries. Proceedings of 16th edition of the International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 217:8-22 Available from https://proceedings.mlr.press/v217/kanazawa23a.html.

Related Material