## Abstract

We prove the existence of a class A of subsets of ℤ^{d} of vc dimension 1 such that the symmetric convex hull F of the class of characteristic functions of sets in A is rich in the following sense. For any absolutely continuous probability measure μ on ℤ^{d}, measurable set B ⊂ ℤ^{d} and ε > 0, there exists a function f ∈ F such that the measure of the symmetric difference of B and the set where f is positive is less than ε. The question was motivated by the investigation of the theoretical properties of certain algorithms in machine learning. Let A be a class of sets in ℝ^{d} and define the symmetric convex hull of A as the class of functions absconv(A) = (Σ_{i=1}^{k} a_{i} A_{i}(x): k > 0, a_{i} ∈ ℝ, Σ_{i=1}^{k}|a_{i}| = 1, A_{i}∈A) where A(x) denotes the indicator function of A. For every f ∈ absconv(A), define the set C_{f} = (x ∈ ℝ^{d}: f(x) > 0) and let C(A) = (C_{f}: f ∈ absconv(A)). We say that absconv(A) is rich with respect to the probability measure μ on ℝ^{d} if for every ε > 0 and measurable set B ⊂ ℝ^{d} there exists a C ∈ C(A) such that μ(BΔC) < ε where BΔC denotes the symmetric difference of B and C. Another way of measuring the richness of a class of sets (rather than the density of the class of sets) is the Vapnik-Chervonenkis (vc) dimension.

Original language | English |
---|---|

Pages (from-to) | 167-169 |

Number of pages | 3 |

Journal | Electronic Communications in Probability |

Volume | 8 |

DOIs | |

Publication status | Published - 1 Jan 2003 |