zbMATH — the first resource for mathematics

A note on the richness of convex hulls of VC classes. (English) Zbl 1095.28006
Summary: We prove the existence of a class \(\mathcal A\) of subsets of \(R^d\) of VC dimension 1 such that the symmetric convex hull \(\mathcal F\) of the class of characteristic functions of sets in \(\mathcal A\) is rich in the following sense. For any absolutely continuous probability measure \(\mu\) on \(R^d\), measurable set \(B\subset \mathbb R^d\) and \(\varepsilon>0\), there exists a function \(f \in \mathcal F\) such that the measure of the symmetric difference of \(B\) and the set where \(f\) is positive is less than \(\epsilon\). The question was motivated by the investigation of the theoretical properties of certain algorithms in machine learning.
28A05 Classes of sets (Borel fields, \(\sigma\)-rings, etc.), measurable sets, Suslin sets, analytic sets
68T05 Learning and adaptive systems in artificial intelligence
68Q32 Computational learning theory
Full Text: DOI EuDML