cshalizi + density_estimation + vc-dimension   1

A Note on the Richness of the Convex Hulls of VC Classes
"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

Copy this bookmark: