Automatic Learning from Repetitive Texts

Rupert Hölzl, Sanjay Jain, Philipp Schlicht, Karen Seidel, Frank Stephan
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:129-150, 2017.

Abstract

We study the connections between the learnability of automatic families of languages and the types of text used to present them to a learner. More precisely, we study how restrictions on the number of times that a correct datum appears in a text influence what classes of languages are automatically learnable. We show that an automatic family of languages is automatically learnable from fat text iff it is automatically learnable from thick text iff it is verifiable from balanced text iff it satisfies Angluin's tell-tale condition. Furthermore, many automatic families are automatically learnable from exponential text. We also study the relationship between automatic learnability and verifiability and show that all automatic families are automatically partially verifiable from exponential text and automatically learnable from thick text.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-hölzl17a, title = {Automatic Learning from Repetitive Texts}, author = {Hölzl, Rupert and Jain, Sanjay and Schlicht, Philipp and Seidel, Karen and Stephan, Frank}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {129--150}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/hölzl17a/hölzl17a.pdf}, url = {https://proceedings.mlr.press/v76/h%C3%B6lzl17a.html}, abstract = {We study the connections between the learnability of automatic families of languages and the types of text used to present them to a learner. More precisely, we study how restrictions on the number of times that a correct datum appears in a text influence what classes of languages are automatically learnable. We show that an automatic family of languages is automatically learnable from fat text iff it is automatically learnable from thick text iff it is verifiable from balanced text iff it satisfies Angluin's tell-tale condition. Furthermore, many automatic families are automatically learnable from exponential text. We also study the relationship between automatic learnability and verifiability and show that all automatic families are automatically partially verifiable from exponential text and automatically learnable from thick text.} }
Endnote
%0 Conference Paper %T Automatic Learning from Repetitive Texts %A Rupert Hölzl %A Sanjay Jain %A Philipp Schlicht %A Karen Seidel %A Frank Stephan %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-hölzl17a %I PMLR %P 129--150 %U https://proceedings.mlr.press/v76/h%C3%B6lzl17a.html %V 76 %X We study the connections between the learnability of automatic families of languages and the types of text used to present them to a learner. More precisely, we study how restrictions on the number of times that a correct datum appears in a text influence what classes of languages are automatically learnable. We show that an automatic family of languages is automatically learnable from fat text iff it is automatically learnable from thick text iff it is verifiable from balanced text iff it satisfies Angluin's tell-tale condition. Furthermore, many automatic families are automatically learnable from exponential text. We also study the relationship between automatic learnability and verifiability and show that all automatic families are automatically partially verifiable from exponential text and automatically learnable from thick text.
APA
Hölzl, R., Jain, S., Schlicht, P., Seidel, K. & Stephan, F.. (2017). Automatic Learning from Repetitive Texts. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:129-150 Available from https://proceedings.mlr.press/v76/h%C3%B6lzl17a.html.

Related Material