Learning algebraic structures with the help of Borel equivalence relations

DOI10.1016/J.TCS.2023.113762arXiv2110.14512MaRDI QIDQ6381458

Nikolay Bazhenov, Luca San Mauro, Vittorio Cipriani

Publication date: 27 October 2021

Abstract: We study algorithmic learning of algebraic structures. In our framework, a learner receives larger and larger pieces of an arbitrary copy of a computable structure and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if the conjectures eventually stabilize to a correct guess. We prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation

E_{0}

of eventual agreement on reals. This motivates a novel research program, that is, using descriptive set theoretic tools to calibrate the (learning) complexity of nonlearnable families. Here, we focus on the learning power of well-known benchmark Borel equivalence relations (i.e.,

E_{1}

,

E_{2}

,

E_{3}

,

Z_{0}

, and

E_{s e t}

).

Mathematics Subject Classification ID

Computational learning theory (68Q32) Descriptive set theory (03E15) Computable structure theory, computable model theory (03C57)

This page was built for publication: Learning algebraic structures with the help of Borel equivalence relations