Limit Learning Equivalence Structures

Ekaterina Fokina, Timo Kötzing, Luca San Mauro
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:383-403, 2019.

Abstract

While most research in Gold-style learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In our core model the learner gets more and more information about which pairs of elements of a structure are related and which are not. The aim of the learner is to find (an effective description of) the isomorphism type of the structure presented in the limit. In accordance with language learning we call this learning criterion $\mathbf{InfEx}$-learning (explanatory learning from informant). Our main contribution is a complete characterization of which families of equivalence structures are $\mathbf{InfEx}$-learnable. This characterization allows us to derive a bound of $\mathbf{0”}$ on the computational complexity required to learn uniformly enumerable families of equivalence structures. We also investigate variants of $\mathbf{InfEx}$-learning, including learning from text (where the only information provided is which elements are related, and not which elements are not related) and finite learning (where the first actual conjecture of the learner has to be correct). Finally, we show how learning families of structures relates to learning classes of languages by mapping learning tasks for structures to equivalent learning tasks for languages.

Cite this Paper

BibTeX
@InProceedings{pmlr-v98-fokina19a, title = {Limit Learning Equivalence Structures}, author = {Fokina, Ekaterina and K{\"o}tzing, Timo and San Mauro, Luca}, booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory}, pages = {383--403}, year = {2019}, editor = {Garivier, Aurélien and Kale, Satyen}, volume = {98}, series = {Proceedings of Machine Learning Research}, month = {22--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v98/fokina19a/fokina19a.pdf}, url = {https://proceedings.mlr.press/v98/fokina19a.html}, abstract = {While most research in Gold-style learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In our core model the learner gets more and more information about which pairs of elements of a structure are related and which are not. The aim of the learner is to find (an effective description of) the isomorphism type of the structure presented in the limit. In accordance with language learning we call this learning criterion $\mathbf{InfEx}$-learning (explanatory learning from informant). Our main contribution is a complete characterization of which families of equivalence structures are $\mathbf{InfEx}$-learnable. This characterization allows us to derive a bound of $\mathbf{0”}$ on the computational complexity required to learn uniformly enumerable families of equivalence structures. We also investigate variants of $\mathbf{InfEx}$-learning, including learning from text (where the only information provided is which elements are related, and not which elements are not related) and finite learning (where the first actual conjecture of the learner has to be correct). Finally, we show how learning families of structures relates to learning classes of languages by mapping learning tasks for structures to equivalent learning tasks for languages.} }
Endnote
%0 Conference Paper %T Limit Learning Equivalence Structures %A Ekaterina Fokina %A Timo Kötzing %A Luca San Mauro %B Proceedings of the 30th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Aurélien Garivier %E Satyen Kale %F pmlr-v98-fokina19a %I PMLR %P 383--403 %U https://proceedings.mlr.press/v98/fokina19a.html %V 98 %X While most research in Gold-style learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In our core model the learner gets more and more information about which pairs of elements of a structure are related and which are not. The aim of the learner is to find (an effective description of) the isomorphism type of the structure presented in the limit. In accordance with language learning we call this learning criterion $\mathbf{InfEx}$-learning (explanatory learning from informant). Our main contribution is a complete characterization of which families of equivalence structures are $\mathbf{InfEx}$-learnable. This characterization allows us to derive a bound of $\mathbf{0”}$ on the computational complexity required to learn uniformly enumerable families of equivalence structures. We also investigate variants of $\mathbf{InfEx}$-learning, including learning from text (where the only information provided is which elements are related, and not which elements are not related) and finite learning (where the first actual conjecture of the learner has to be correct). Finally, we show how learning families of structures relates to learning classes of languages by mapping learning tasks for structures to equivalent learning tasks for languages.
APA
Fokina, E., Kötzing, T. & San Mauro, L.. (2019). Limit Learning Equivalence Structures. Proceedings of the 30th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 98:383-403 Available from https://proceedings.mlr.press/v98/fokina19a.html.

Related Material