 |
|
|
| | | | | |
|
|
|
|
|
A note on the richness of convex hulls of VC classes
|
Gàbor Lugosi, Pompeu Fabra University, Spain
Shahar Mendelson, The Australian National University, Australia
Vladimir Koltchinskii, The University of New Mexico, USA
|
Abstract
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.
|
Full text: PDF
Pages: 167-169
Published on: December 17, 2003
|
Bibliography
|
Blanchard, G.; Lugosi, G.;
Vayatis, N.
On the rate of convergence of regularized boosting classifiers.
newblock Journal of Machine Learning Research, 4
(2003), 861-894. |
|
Breiman, L. Bagging predictors.
Machine Learning, 24 (1996), 123--140.
|
|
Breiman, L.
Bias, variance, and arcing classifiers.
newblock Technical report, Department of Statistics, University of California
at Berkeley, Report 460, 1996.
|
| Cybenko, G. Approximation by superpositions of a sigmoidal function.
Math. Control Signals Systems 2 (1989), no. 4, 303--314. MR1015670 (90m:41033) |
| Freund, Yoav. Boosting a weak learning algorithm by majority.
Inform. and Comput. 121 (1995), no. 2, 256--285. MR1348530 (96h:68166) |
|
Hornik, K.; Stinchcombe, M.;
White, H.
Multi-layer feedforward networks are universal approximators.
Neural Networks, 2 (1989), 359--366.
|
| Koltchinskii, V.; Panchenko, D. Empirical margin distributions and bounding the generalization error of combined classifiers.
Ann. Statist. 30 (2002), no. 1, 1--50. MR1892654 (2003g:62063) |
|
Lugosi, G.; Vayatis, N.
On the bayes-risk consistency of regularized boosting methods.
Annals of Statistics, 2003, to appear.
|
| Royden, H. L. Real analysis.
Third edition.
Macmillan Publishing Company, New York, 1988. xx+444 pp. ISBN: 0-02-404151-3 MR1013117 (90g:00004) |
Schapire, R. E.
The strength of weak learnability.
Machine Learning, 5 (1990), 197--227.
|
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context