# 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.
##### MSC:
 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
##### Keywords:
Vapnik-Chervonenkis (VC) dimension; convex hull; boosting
Full Text: