The paper studies learnability from positive data for families of existentially definable subsets in a given computable structure \(\mathcal {S}\) . While provided larger and larger pieces of a subset V of the domain of \(\mathcal {S}\) , a learner tries to guess the Gödel number of an \(\exists \) -formula which defines V in \(\mathcal {S}\) . In this setting, we consider several classical learning criteria. For a computable structure \(\mathcal {S}\) , we work with the class \(\varSigma ^0_1(\mathcal {S})\) containing all \(\exists \) -definable (without parameters) subsets of \(\mathcal {S}\) . We focus on some familiar classes of structures \(\mathcal {S}\) , including equivalence structures and Boolean algebras. We establish the following results. If the \(\forall \exists \) -theory of a structure \(\mathcal {S}\) is decidable, then the notions of explanatory learnability and behaviorally correct learnability for families \(\mathcal {F} \subseteq \varSigma ^0_1(\mathcal {S})\) coincide. If \(\mathcal {S}\) is a computable equivalence structure, then the notions of vacillatory learnability and behaviorally correct learnability for such families \(\mathcal {F}\) coincide. We build a computable equivalence structure \(\mathcal {E}\) such that \(\varSigma ^0_1(\mathcal {E})\) is vacillatorily learnable but not explanatorily learnable. We prove that every computable Boolean algebra has a computable isomorphic copy \(\mathcal {C}\) such that \(\varSigma ^0_1(\mathcal {C})\) is confidently learnable. We construct a computable Heyting algebra \(\mathcal {H}\) such that for any computable copy \(\mathcal {C}\) of \(\mathcal {H}\) , the family \(\varSigma ^0_1(\mathcal {C})\) is not behaviorally correctly learnable.

On Learning Existentially Definable Subsets in a Computable Structure

会议论文
发表日期：

2025年

查看全文

Nikolay Bazhenov,
Manat Mustafa

摘要

The paper studies learnability from positive data for families of existentially definable subsets in a given computable structure \(\mathcal {S}\) . While provided larger and larger pieces of a subset V of the domain of \(\mathcal {S}\) , a learner tries to guess the Gödel number of an \(\exists \) -formula which defines V in \(\mathcal {S}\) . In this setting, we consider several classical learning criteria. For a computable structure \(\mathcal {S}\) , we work with the class \(\varSigma ^0_1(\mathcal {S})\) containing all \(\exists \) -definable (without parameters) subsets of \(\mathcal {S}\) . We focus on some familiar classes of structures \(\mathcal {S}\) , including equivalence structures and Boolean algebras. We establish the following results. If the \(\forall \exists \) -theory of a structure \(\mathcal {S}\) is decidable, then the notions of explanatory learnability and behaviorally correct learnability for families \(\mathcal {F} \subseteq \varSigma ^0_1(\mathcal {S})\) coincide. If \(\mathcal {S}\) is a computable equivalence structure, then the notions of vacillatory learnability and behaviorally correct learnability for such families \(\mathcal {F}\) coincide. We build a computable equivalence structure \(\mathcal {E}\) such that \(\varSigma ^0_1(\mathcal {E})\) is vacillatorily learnable but not explanatorily learnable. We prove that every computable Boolean algebra has a computable isomorphic copy \(\mathcal {C}\) such that \(\varSigma ^0_1(\mathcal {C})\) is confidently learnable. We construct a computable Heyting algebra \(\mathcal {H}\) such that for any computable copy \(\mathcal {C}\) of \(\mathcal {H}\) , the family \(\varSigma ^0_1(\mathcal {C})\) is not behaviorally correctly learnable.