Densité et dimension

Assouad, Patrick

Annales de l'Institut Fourier, Tome 33 (1983) no. 3, pp. 233-282.

Une partie $𝒮$ de $2^X$ est appelée une classe de Vapnik-Cervonenkis si la croissance de la fonction ${\Delta }^{𝒮}:r\to \mathrm{Sup}\left\{\right|A\cap \left|\right|A\subset X,\left|A\right|=r\}$ 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 $𝒮$ 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 $𝒮$ est majoré par un polynôme en $r$ ;

- si $𝒮$ est une partie de $2^X$, chaque loi de probabilité $P$ sur la tribu engendrée par $𝒮$ définit un écart $d_p:S,S^{\prime }\to P(S\Delta S^{\prime })$ sur la famille $𝒮$, et on note dim$(𝒮,d_p)$ la dimension d’entropie de l’espace $(𝒮,d_p)$; la famille $𝒮$ est une classe de Vapnik-Cervonenkis si et seulement si la quantité Sup$\overline{\dim }(𝒮,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]).

A class $𝒮$ of subsets of a set $X$ is called a Vapnik-Cervonenkis class if the growth of the function ${\Delta }^{𝒮}:r\to \mathrm{Sup}\left\{\right|A\cap \left|\right|A\subset X,\left|A\right|=r\}$ 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 $𝒮$ 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 $𝒮$ if no more than $C{r}^s$ (where $C$ and $s$ are two positive real numbers);

- if $𝒮$ is a subset of $2^X$, every probability law $P$ on the $\sigma$-algebra generated by $𝒮$ defines a semimetric $d_p:S,S^{\prime }\to P(S\Delta S^{\prime })$ on the class $𝒮$, and the entropy dimension of the space $(𝒮,d_p)$ will be denoted $\overline{\dim }(𝒮,d_p)$ ; the class $𝒮$ is a Vapnik-Cervonenkis class if and only if ${\mathrm{Sup}}_P\overline{\dim }(𝒮,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]).

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

[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 | Zbl

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

[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

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

[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 | Zbl

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

[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 | Zbl

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

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

[13] P. Dembowski, Finite geometries, Springer, 1968. | MR | Zbl

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

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

[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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

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

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

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

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

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

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

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

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

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

[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 | Zbl

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

[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

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

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

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

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

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

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

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

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

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