Densité et dimension

Assouad, Patrick

Annales de l'Institut Fourier, Tome 33 (1983), p. 233-282 / Harvested from Numdam

Résumé

Une partie ${\cal S}$ de $2^X$ est appelée une classe de Vapnik-Cervonenkis si la croissance de la fonction $\Delta ^{\cal S}:r\rightarrow {\rm Sup} \lbrace \vert A\cap \vert \vert A\subset X,\vert A\vert = r\rbrace $ est polynomiale; ces classes se trouvent être utiles en Statistique et en Calcul des Probabilités (voir par exemple Vapnik, Cervonenkis [V.N. Vapnik, A.YA. Cervonenkis, Theor. Prob. Appl., 16 (1971), 264-280], Dudley [R.M. Dudley, Ann. of Prob., 6 (1978), 899-929]).

Le présent travail est un essai de synthèse sur les classes de Vapnik-Cervonenkis. Mais il contient aussi beaucoup de résultats nouveaux, et notamment les deux résultats suivants :

- une partie ${\cal S}$ de $2^X$ est une classe de Vapnik-Cervonenkis si et seulement si le nombre d’atomes de la tribu engendrée par $r$ membres quelconques de ${\cal S}$ est majoré par un polynôme en $r$ ;

- si ${\cal S}$ est une partie de $2^X$, chaque loi de probabilité $P$ sur la tribu engendrée par ${\cal S}$ définit un écart $d_p:S,S^{\prime }\rightarrow P(S\Delta S^{\prime })$ sur la famille ${\cal S}$, et on note dim$({\cal S},d_p)$ la dimension d’entropie de l’espace $({\cal S},d_p)$; la famille ${\cal S}$ est une classe de Vapnik-Cervonenkis si et seulement si la quantité Sup$\,\overline{\rm dim}({\cal S},d_p)$ est finie.

On trouvera dans l’introduction les énoncés de plusieurs autres résultats nouveaux démontrés ici (dont certains sont indiqués sans démonstration dans ma note [P. Assouad, C.R.A.S., Paris, 292 (1981), 921-924]).

Abstract

A class ${\cal S}$ of subsets of a set $X$ is called a Vapnik-Cervonenkis class if the growth of the function $\Delta ^{\cal S}:r\rightarrow {\rm Sup} \lbrace \vert A\cap \vert \vert A\subset X,\vert A\vert = r\rbrace $ is polynomial ; these classes have proved to be useful in Statistics and Probability (see for example Vapnik, Cervonenkis [V.N. Vapnik, A.YA. Cervonenkis, Theor. Prob. Appl., 16 (1971), 264-280], Dudley [R.M. Dudley, Ann. of Prob., 6 (1978), 899-929]).

The present paper is a survey on Vapnik-Cervonenkis classes. Moreover we prove here many new results, among them the following:

- a subset ${\cal S}$ of $2^X$ is a Vapnik-Cervonenkis class if and only if the number of atoms of the $\sigma $-algebra generated by any collection of $r$ members of ${\cal S}$ if no more than $Cr^s$ (where $C$ and $s$ are two positive real numbers);

- if ${\cal S}$ is a subset of $2^X$, every probability law $P$ on the $\sigma $-algebra generated by ${\cal S}$ defines a semimetric $d_p:S,S^{\prime }\rightarrow P(S\Delta S^{\prime })$ on the class ${\cal S}$, and the entropy dimension of the space $({\cal S},d_p)$ will be denoted $\overline{\rm dim}({\cal S},d_p)$ ; the class ${\cal S}$ is a Vapnik-Cervonenkis class if and only if ${\rm Sup}_P\,\overline{\rm dim} ({\cal S},d_p)$ is finite.

The present paper contains other new results, some of them being stated without proof in my note [P. Assouad, C.R.A.S., Paris, 292 (1981), 921-924]).

Détail

Publié le : 1983-01-01

MR 86j:05022 | Zbl 0504.60006 | 1 citation dans Numdam

DOI : https://doi.org/10.5802/aif.938

Bibliographie

[1] R. Alexander, Planes for which the lines are the shortest path, Illinois J. of Math., 22 (1978), 177-190. | MR 82d:53042 | Zbl 0379.50002

[2] R. Alexander, Metrics on Rn which possess a Crofton formula, Notices AMS, 26 (1979), A-278.

[3] R.V. Ambartzumian, A note on pseudometrics on the plane, Z. Warscheinlich keitstheorie, 37 (1976), 145-155. | MR 54 #14035 | Zbl 0325.28020

[4] P. Assouad, Espaces métriques, plongements, facteurs, Thèse, Université de Paris-Sud, (1977). | MR 58 #30989 | Zbl 0396.46035

[5] P. Assouad, Pseudodistances, facteurs et dimension métrique, Séminaire d'Analyse Harmonique 1979/1980 (Orsay) Publications Mathématiques d'Orsay n° 81-07, pp. 1-33. | Zbl 0486.54021

[6] P. Assouad, Sur les classes de Vapnik-Cervonenkis, C. R. A. S., Paris, 292 (1981), 921-924. | MR 82i:04003 | Zbl 0466.04002

[7] E.G. Bajmoczy, I. Barany : On a common generalization of Borsuk's and Radon's theorems, Acta Math. Acad. Scient. Hungar., 34 (1979), 347-350. | MR 81f:52004 | Zbl 0446.52010

[8] R.G. Bland, M. Las Vergnas, Orientability of matroïds, J. of Comb. Th., B. 24 (1978), 94-123. | MR 58 #5294 | Zbl 0374.05016

[9] K. Borsuk, W. Szmielew, Foundations of geometry (english transl.), North Holland (1960).

[10] H. Busemann, Desarguesian Spaces, Proc. of Symp. in Pure Math., 28 (1976), 131-141. | MR 55 #3940 | Zbl 0352.50010

[11] P. Cartier. Arrangements d'hyperplans : un chapitre de géométrie combinatoire, Seminaire Bourbaki (1980), exposé n° 651. | Numdam | Zbl 0483.51011

[12] L. Danzer, B. Grunbaum, V. Klee, Helly's theorem and its relatives, Proc. of Symp. in Pure Math., 7 (1963), 101-180. | MR 28 #524 | Zbl 0132.17401

[13] P. Dembowski, Finite geometries, Springer, 1968. | MR 38 #1597 | Zbl 0159.50001

[14] R.M. Dudley, Central limit theorems for empirical measures, Ann. of Prob., 6 (1978), 899-929. | MR 81k:60029a | Zbl 0404.60016

[15] R.M. Dudley, Balls in Rk do not cut all subsets of (k + 2) points, Advances Math., 31 (1979), 306-308. | MR 81g:52010 | Zbl 0408.05001

[16] R.M. Dudley, Vapnik-Cervonenkis Donsker classes of functions, preprint (1980).

[17] M. Durst, R.M. Dudley, Empirical processes, Vapnik Cervonenkis classes and Poisson processes, Probability and Math. Stat., 1 (1981) to appear. | Zbl 0502.60019

[18] J. Eckhoff, Radon's theorem revisited, In Contributions to geometry, Proc. of the Geometry Symp. in Siegen 1978, Birkhaüser (1979) 164-185. | MR 81f:52016 | Zbl 0445.52009

[19] G. Fichtenholz, K. Kantorovitch, Sur les opérations linéaires dans l'espace des fonctions bornées, Studia Math., 5 (1934), 69-98. | JFM 60.1074.05 | Zbl 0013.06502

[20] J.E. Goodman, R. Pollack, Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines, J. Comb. Th, A 29 (1980), 385-390. | MR 82m:05026 | Zbl 0457.51006

[21] B. Grunbaum, Arrangements and spreads, CBMS Regional Conference Series in Math., n° 10 (1972). | MR 46 #6148 | Zbl 0249.50011

[22] B. Hajek, Stochastic integration, Markov property and measure transformation of random fields, Ph. D. Dissertation, Berkeley (1979).

[23] R.E. Jamison, A general theory of convexity, Doct. Dissert., Univ. of Washington (Seattle, 1974).

[24] T. Kovari, V.T. Sos, P. Turan, On a problem of K. Zarankiewicz, Colloquium Math., 3 (1954), 50-57. | MR 16,456a | Zbl 0055.00704

[25] G.G. Lorentz, Lower bound for the degree of approximation, Trans. Amer, Math. Soc., 97 (1960), 25-34. | MR 22 #8266 | Zbl 0128.06701

[26] B. Reznick, Banach spaces with polynomial norms, Pac. J. Math., 82 (1979), 223-235. | MR 83c:46007 | Zbl 0413.46013

[27] G. Ringel, Teilungen der Ebene durch Geraden oder topologische Geraden, Math. Z., 64 (1955), 79-102. | MR 17,651g | Zbl 0070.16108

[28] C.A. Rogers, Hausdorff measures, Cambridge University Press (1970). | MR 43 #7576 | Zbl 0204.37601

[29] H.P. Rosenthal, A characterization of Banach spaces containing l1, Proc. Nat. Acad. Sci. USA, 71 (1974), 2411-2413. | MR 50 #10773 | Zbl 0297.46013

[30] N. Sauer, On the density of families of sets, J. Comb. Th., A 13 (1972) 145-147. | MR 46 #7017 | Zbl 0248.05005

[31] I.J. Schoenberg, Metric spaces and positive definite functions, Transact. Amer. Math. Soc., 44 (1938), 522-536. | JFM 64.0617.02 | MR 1501980 | Zbl 0019.41502

[32] H.S. Shapiro, Some negative theorems of approximation theory, Michigan Math. J., 11 (1964), 211-217. | MR 29 #5041 | Zbl 0123.09202

[33] S. Shelah, A combinatorial problem ; stability and order for models and theories in infinitary languages, Pacific J. Math., 41 (1972) 247-261. | Zbl 0239.02024

[34] G. Sierksma, Generalized Radon partitions in convexity spaces, preprint (1980). | Zbl 0489.52001

[35] E.H. Spanier, Algebric topology, Mc Graw Hill (1966).

[36] H.M. Stark, An introduction to number theory, Markham Publ. Co., 1971.

[37] E. Szpilrajn (Marczewski), Ensembles indépendants et mesures non séparables, C.R.A.S., Paris, 207 (1938), 768-770. | JFM 64.0192.03 | Zbl 0020.10901

[38] H. Tverberg, A generalization of Radon's theorem, J. of the London Math. Soc., 41 (1966), 123-128. | MR 32 #4601 | Zbl 0131.20002

[39] V.N. Vapnik, A. Ya. Cervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theor. Prob. Appl., 16 (1971), 264-280. | Zbl 0247.60005

[40] H.E. Warren, Partitions by real algebraic varieties and applications to questions of nonlinear approximation, Bull. AMS, 73 (1967) 192-194. | MR 35 #642 | Zbl 0223.14027

[41] H.E. Warren, Lower bounds for approximation by nonlinear manifolds, Trans. AMS, 133 (1968), 167-178. | MR 37 #1871 | Zbl 0174.35403

[42] D.J.A. Welsh, Matroïd theory, Academic Press (1976). | MR 55 #148 | Zbl 0343.05002

[43] R.S. Wenocur, R.M. Dudley, Some special Vapnik-Cervonenkis classes, Discrete Math., 33 (1981), 313-318. | MR 83f:60050 | Zbl 0459.60008

B.J. Birch : On 3N points in a plane, Proc. Cambridge Phil. Soc., 55 (1959), 289-293. | MR 22 #201 | Zbl 0089.38502

J.A. Bondy : Induced subsets, J. Comb. Th., B 12 (1972), 201-202. | MR 47 #8315 | Zbl 0211.56901

K. Glazek : Some old and new problems in the independence theory, Colloquium Math., 42 (1979), 127-189. | MR 82j:08006 | Zbl 0432.08001

M.G. Karpovsky, V.D. Milman : Coordinate density of sets of vectors, Discrete Math., 24 (1978), 177-184. | MR 80m:05004 | Zbl 0401.05015

P. Tomasta : “Dart calculus” of induced subsets, Discrete Math., 34 (1981), 195-198. | MR 83f:05055 | Zbl 0475.05002