Densité et dimension

Assouad, Patrick

doi:10.5802/aif.938

Assouad, Patrick

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

Résumé
Abstract

Une partie $𝒮$ de $2^{X}$ est appelée une classe de Vapnik-Cervonenkis si la croissance de la fonction $Δ^{𝒮} : r \to Sup {| A \cap | | A \subset X, | A | = 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^{'} \to P (S Δ S^{'})$ 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 $\bar{\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 $Δ^{𝒮} : r \to Sup {| A \cap | | A \subset X, | A | = 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 $σ$ -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 $σ$ -algebra generated by $𝒮$ defines a semimetric $d_{p} : S, S^{'} \to P (S Δ S^{'})$ on the class $𝒮$ , and the entropy dimension of the space $(𝒮, d_{p})$ will be denoted $\bar{\dim} (𝒮, d_{p})$ ; the class $𝒮$ is a Vapnik-Cervonenkis class if and only if ${Sup}_{P} \bar{\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]).

EuDML MR Zbl | 4 citations dans Numdam

DOI : 10.5802/aif.938

@article{AIF_1983__33_3_233_0,
     author = {Assouad, Patrick},
     title = {Densit\'e et dimension},
     journal = {Annales de l'Institut Fourier},
     pages = {233--282},
     publisher = {Institut Fourier},
     address = {Grenoble},
     volume = {33},
     number = {3},
     year = {1983},
     doi = {10.5802/aif.938},
     mrnumber = {86j:05022},
     zbl = {0504.60006},
     language = {fr},
     url = {https://www.numdam.org/articles/10.5802/aif.938/}
}

TY  - JOUR
AU  - Assouad, Patrick
TI  - Densité et dimension
JO  - Annales de l'Institut Fourier
PY  - 1983
SP  - 233
EP  - 282
VL  - 33
IS  - 3
PB  - Institut Fourier
PP  - Grenoble
UR  - https://www.numdam.org/articles/10.5802/aif.938/
DO  - 10.5802/aif.938
LA  - fr
ID  - AIF_1983__33_3_233_0
ER  -

%0 Journal Article
%A Assouad, Patrick
%T Densité et dimension
%J Annales de l'Institut Fourier
%D 1983
%P 233-282
%V 33
%N 3
%I Institut Fourier
%C Grenoble
%U https://www.numdam.org/articles/10.5802/aif.938/
%R 10.5802/aif.938
%G fr
%F AIF_1983__33_3_233_0

Assouad, Patrick. Densité et dimension. Annales de l'Institut Fourier, Tome 33 (1983) no. 3, pp. 233-282. doi : 10.5802/aif.938. https://www.numdam.org/articles/10.5802/aif.938/

Bibliographie
Cité par

[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

Cité par Sources :