**cshalizi + density_estimation + vc-dimension**
1

"We prove the existence of a class A of subsets of Rd 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 Rd, measurable set B and ε >0, there exists a function f in 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." --- I see it, but I don't believe it! (The proof would seem to extend to arbitrary complete separable metric spaces, not just R^d.)

learning_theory
density_estimation
statistics
have_read
vc-dimension
analysis
measure_theory
march 2009 by cshalizi

**related tags**

Copy this bookmark: