On computable learning of continuous features
We introduce definitions of computable PAC learning for binary classification over computable metric spaces. We provide sufficient conditions for learners that are empirical risk minimizers (ERM) to be computable, and bound the strong Weihrauch degree of an ERM learner under more general conditions. We also give a presentation of a hypothesis class that does not admit any proper computable PAC learner with computable sample function, despite the underlying class being PAC learnable.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationPAC learningSimilar Papers 제목 키워드 기반
Algorithmic learning of probability distributions from random data in the limit
We study the problem of identifying a probability distribution for some given randomly sampled data in the limit, in the context of algorithmic learning theory as proposed recently by Vinanyi and Chater. We show that the…
Learning TheoryOn the Complexity of Computing Gödel Numbers
Given a computable sequence of natural numbers, it is a natural task to find a G\"odel number of a program that generates this sequence. It is easy to see that this problem is neither continuous nor computable. In algori…
Learning TheoryChromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications
We establish closed-form enumeration formulas for chromatic feature vectors of 2-trees under the bichromatic triangle constraint. These efficiently computable structural features derive from constrained graph colorings w…
Deep Parametric Continuous Convolutional Neural Networks
Standard convolutional neural networks assume a grid structured input is available and exploit discrete convolutions as their fundamental building blocks. This limits their applicability to many real-world applications. …
Motion EstimationPoint Cloud SegmentationSemantic SegmentationA RAD approach to deep mixture models
Flow based models such as Real NVP are an extremely powerful approach to density estimation. However, existing flow based models are restricted to transforming continuous densities over a continuous input space into simi…
Density Estimation