Learning equivalence relations

Abstract: What does it mean for an equivalence relation on a Polish space to be learnable? Motivated by the recent work of Fokina, Kötzing, and San Mauro, who formulated a framework to learn the isomorphism relation on countable classes of structures, we introduce frameworks that aim to give a formal notion of learnability for equivalence relations on Polish spaces. Our main results characterize learnability in these frameworks via the descriptive complexity of the equivalence relations, and, using techniques from higher recursion theory and effective descriptive set theory, we calculate the complexity of the class of learnable equivalence relations. At last, we discuss the learnability of equivalence relations arising naturally in computability theory. This is joint work with Ted Slaman and Tomasz Steifer.

machine learninglogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic