String Extension Learning Despite Noisy Intrusions

Katherine Wu, Jeffrey Heinz
Proceedings of 16th edition of the International Conference on Grammatical Inference, PMLR 217:80-95, 2023.

Abstract

We examine the conditions in which string extension learning algorithms are able to identify classes of formal languages in the limit from noisy data presentations in polynomial time. A data presentation for a formal language $L$ is noisy if it contains words belonging to the complement of $L$. In the general case, string extensions learners cannot distinguish noise from true examples and are led astray. The main result is that relative frequencies can be used to distinguish noisy examples from true examples provided the data presentations are constrained to those in which relative frequencies are uniformly present and exceed the rate at which noise is introduced.

Cite this Paper

BibTeX
@InProceedings{pmlr-v217-wu23a, title = {String Extension Learning Despite Noisy Intrusions}, author = {Wu, Katherine and Heinz, Jeffrey}, booktitle = {Proceedings of 16th edition of the International Conference on Grammatical Inference}, pages = {80--95}, 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/wu23a/wu23a.pdf}, url = {https://proceedings.mlr.press/v217/wu23a.html}, abstract = {We examine the conditions in which string extension learning algorithms are able to identify classes of formal languages in the limit from noisy data presentations in polynomial time. A data presentation for a formal language $L$ is noisy if it contains words belonging to the complement of $L$. In the general case, string extensions learners cannot distinguish noise from true examples and are led astray. The main result is that relative frequencies can be used to distinguish noisy examples from true examples provided the data presentations are constrained to those in which relative frequencies are uniformly present and exceed the rate at which noise is introduced.} }
Endnote
%0 Conference Paper %T String Extension Learning Despite Noisy Intrusions %A Katherine Wu %A Jeffrey Heinz %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-wu23a %I PMLR %P 80--95 %U https://proceedings.mlr.press/v217/wu23a.html %V 217 %X We examine the conditions in which string extension learning algorithms are able to identify classes of formal languages in the limit from noisy data presentations in polynomial time. A data presentation for a formal language $L$ is noisy if it contains words belonging to the complement of $L$. In the general case, string extensions learners cannot distinguish noise from true examples and are led astray. The main result is that relative frequencies can be used to distinguish noisy examples from true examples provided the data presentations are constrained to those in which relative frequencies are uniformly present and exceed the rate at which noise is introduced.
APA
Wu, K. & Heinz, J.. (2023). String Extension Learning Despite Noisy Intrusions. Proceedings of 16th edition of the International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 217:80-95 Available from https://proceedings.mlr.press/v217/wu23a.html.

Related Material