Decidability of Sample Complexity of PAC Learning in finite setting
In this short note we observe that the sample complexity of PAC machine learning of various concepts, including learning the maximum (EMX), can be exactly determined when the support of the probability measures considered as models satisfies an a-priori bound. This result contrasts with the recently discovered undecidability of EMX within ZFC for finitely supported probabilities (with no a priori bound). Unfortunately, the decision procedure is at present, at least doubly exponential in the number of points times the uniform bound on the support size.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningPAC learningSimilar Papers 제목 키워드 기반
Finite Query Answering in Expressive Description Logics with Transitive Roles
We study the problem of finite ontology mediated query answering (FOMQA), the variant of OMQA where the represented world is assumed to be finite, and thus only finite models of the ontology are considered. We adopt the …
Trakhtenbrot's Theorem in Coq, A Constructive Approach to Finite Model Theory
We study finite first-order satisfiability (FSAT) in the constructive setting of dependent type theory. Employing synthetic accounts of enumerability and decidability, we give a full classification of FSAT depending on t…
RelationUndecidability in Finite Transducers, Defense Systems and Finite Substitutions
In this manuscript we present a detailed proof for undecidability of the equivalence of finite substitutions on regular language $b\{0,1\}^*c$. The proof is based on the works of Leonid P. Lisovik.
Existential Rule Languages with Finite Chase: Complexity and Expressiveness
Finite chase, or alternatively chase termination, is an important condition to ensure the decidability of existential rule languages. In the past few years, a number of rule languages with finite chase have been studied.…
Trakhtenbrot's Theorem in Coq: Finite Model Theory through the Constructive Lens
We study finite first-order satisfiability (FSAT) in the constructive setting of dependent type theory. Employing synthetic accounts of enumerability and decidability, we give a full classification of FSAT depending on t…
Relation