2019/02/21 by Ekaterina Fokina, Fokina, Ekaterina, Timo Kötzing +3
Computer Science · Mathematics · #03C57 #68Q32 #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Machine Learning and Algorithms #math.LO #msc:03C57 #msc:68Q32 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1902.08006
22 pages, forthcoming in Proceedings of Machine Learning Research
arxiv created 2019/02/21 · openalex publication_date 2019/02/21 · arxiv updated 2019/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 InfEx-learning (explanatory learning from informant). Our main contribution is a complete characterization of which families of equivalence structures are InfEx-learnable. This characterization allows us to derive a bound of 0'' on the computational complexity required to learn uniformly enumerable families of equivalence structures. We also investigate variants of 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.