Geodesic
Bracketing Entropy and VC-Dimension
Matematičeskie zametki, Tome 91 (2012) no. 6, pp. 853-860.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the relationship between two characteristics of functional classes, pseudodimension and bracketing entropy. (Pseudodimension is a generalization of VC-dimension to classes of functions. Bracket entropy characterizes the $L_1$-error of one-sided approximation of a class by finite sets.) It is shown that classes of continuous functions with finite pseudodimension possess a finite bracketing $\varepsilon$-entropy for any $\varepsilon>0$. We establish a general result concerning the relationship between the VC-dimension of classes of sets and their bracketing entropy.
Keywords: bracketing entropy, measurable function, bracketing compactness of sets, random variable, probability space.
Mots-clés : pseudodimension, VC-dimension 
@article{MZM_2012_91_6_a5,
     author = {Yu. V. Malykhin},
     title = {Bracketing {Entropy} and {VC-Dimension}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {853--860},
     publisher = {mathdoc},
     volume = {91},
     number = {6},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2012_91_6_a5/}
}
TY  - JOUR
AU  - Yu. V. Malykhin
TI  - Bracketing Entropy and VC-Dimension
JO  - Matematičeskie zametki
PY  - 2012
SP  - 853
EP  - 860
VL  - 91
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2012_91_6_a5/
LA  - ru
ID  - MZM_2012_91_6_a5
ER  - 
%0 Journal Article
%A Yu. V. Malykhin
%T Bracketing Entropy and VC-Dimension
%J Matematičeskie zametki
%D 2012
%P 853-860
%V 91
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2012_91_6_a5/
%G ru
%F MZM_2012_91_6_a5
Yu. V. Malykhin. Bracketing Entropy and VC-Dimension. Matematičeskie zametki, Tome 91 (2012) no. 6, pp. 853-860. http://geodesic.mathdoc.fr/item/MZM_2012_91_6_a5/

[1] V. N. Vapnik, A. Ya. Chervonenkis, “O ravnomernoi skhodimosti chastot poyavleniya sobytii k ikh veroyatnostyam”, DAN SSSR, 181:4 (1968), 781–783 | MR | Zbl

[2] D. Haussler, “Decision theoretic generalizations of the PAC model for neural net and other learning applications”, Inform. and Comput., 100:1 (1992), 78–150 | DOI | MR | Zbl

[3] J. R. Blum, “On the convergence of empiric distribution functions”, Ann. Math. Statist., 26:3 (1955), 527–529 | DOI | MR | Zbl

[4] J. Dehardt, “Generalizations of the Glivenko–Cantelli theorem”, Ann. Math. Statist., 42:6 (1971), 2050–2055 | DOI | MR | Zbl

[5] Yu. V. Malykhin, “Usrednennyi modul nepreryvnosti i skobochnaya kompaktnost”, Matem. zametki, 87:3 (2010), 468–471 | MR | Zbl

[6] D. Haussler, “Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik–Chervonenkis dimension”, J. Combin. Theory Ser. A, 69:2 (1995), 217–232 | DOI | MR | Zbl

[7] T. M. Adams, A. B. Nobel, Uniform Approximation and Bracketing Properties of VC Classes, arXiv: math.PR/1007.4037