Densité et dimension

Patrick Assouad

Annales de l'institut Fourier (1983)

  • Volume: 33, Issue: 3, page 233-282
  • ISSN: 0373-0956

Abstract

top
A class 𝒮 of subsets of a set X is called a Vapnik-Cervonenkis class if the growth of the function Δ 𝒮 : r → Sup { | A ∩ | | A ⊂ 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 ' → P ( S Δ S ' ) on the class 𝒮 , and the entropy dimension of the space ( 𝒮 , d p ) will be denoted dim ‾ ( 𝒮 , d p )  ; the class 𝒮 is a Vapnik-Cervonenkis class if and only if Sup P 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]).

How to cite

top

Assouad, Patrick. "Densité et dimension." Annales de l'institut Fourier 33.3 (1983): 233-282. <http://eudml.org/doc/74598>.

@article{Assouad1983,
abstract = {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]).},
author = {Assouad, Patrick},
journal = {Annales de l'institut Fourier},
keywords = {Vapnik-Chervonenkis class},
language = {fre},
number = {3},
pages = {233-282},
publisher = {Association des Annales de l'Institut Fourier},
title = {Densité et dimension},
url = {http://eudml.org/doc/74598},
volume = {33},
year = {1983},
}

TY - JOUR
AU - Assouad, Patrick
TI - Densité et dimension
JO - Annales de l'institut Fourier
PY - 1983
PB - Association des Annales de l'Institut Fourier
VL - 33
IS - 3
SP - 233
EP - 282
AB - 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]).
LA - fre
KW - Vapnik-Chervonenkis class
UR - http://eudml.org/doc/74598
ER -

References

top
  1. [1] R. ALEXANDER, Planes for which the lines are the shortest path, Illinois J. of Math., 22 (1978), 177-190. Zbl0379.50002MR82d:53042
  2. [2] R. ALEXANDER, Metrics on Rn which possess a Crofton formula, Notices AMS, 26 (1979), A-278. 
  3. [3] R.V. AMBARTZUMIAN, A note on pseudometrics on the plane, Z. Warscheinlich keitstheorie, 37 (1976), 145-155. Zbl0325.28020MR54 #14035
  4. [4] P. ASSOUAD, Espaces métriques, plongements, facteurs, Thèse, Université de Paris-Sud, (1977). Zbl0396.46035MR58 #30989
  5. [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. Zbl0486.54021
  6. [6] P. ASSOUAD, Sur les classes de Vapnik-Cervonenkis, C. R. A. S., Paris, 292 (1981), 921-924. Zbl0466.04002MR82i:04003
  7. [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. Zbl0446.52010MR81f:52004
  8. [8] R.G. BLAND, M. LAS VERGNAS, Orientability of matroïds, J. of Comb. Th., B. 24 (1978), 94-123. Zbl0374.05016MR58 #5294
  9. [9] K. BORSUK, W. SZMIELEW, Foundations of geometry (english transl.), North Holland (1960). Zbl0093.33301
  10. [10] H. BUSEMANN, Desarguesian Spaces, Proc. of Symp. in Pure Math., 28 (1976), 131-141. Zbl0352.50010MR55 #3940
  11. [11] P. CARTIER. Arrangements d'hyperplans : un chapitre de géométrie combinatoire, Seminaire Bourbaki (1980), exposé n° 651. Zbl0483.51011
  12. [12] L. DANZER, B. GRUNBAUM, V. KLEE, Helly's theorem and its relatives, Proc. of Symp. in Pure Math., 7 (1963), 101-180. Zbl0132.17401MR28 #524
  13. [13] P. DEMBOWSKI, Finite geometries, Springer, 1968. Zbl0159.50001MR38 #1597
  14. [14] R.M. DUDLEY, Central limit theorems for empirical measures, Ann. of Prob., 6 (1978), 899-929. Zbl0404.60016MR81k:60029a
  15. [15] R.M. DUDLEY, Balls in Rk do not cut all subsets of (k + 2) points, Advances Math., 31 (1979), 306-308. Zbl0408.05001MR81g:52010
  16. [16] R.M. DUDLEY, Vapnik-Cervonenkis Donsker classes of functions, preprint (1980). Zbl0511.60046
  17. [17] M. DURST, R.M. DUDLEY, Empirical processes, Vapnik Cervonenkis classes and Poisson processes, Probability and Math. Stat., 1 (1981) to appear. Zbl0502.60019
  18. [18] J. ECKHOFF, Radon's theorem revisited, In Contributions to geometry, Proc. of the Geometry Symp. in Siegen 1978, Birkhaüser (1979) 164-185. Zbl0445.52009MR81f:52016
  19. [19] G. FICHTENHOLZ, K. KANTOROVITCH, Sur les opérations linéaires dans l'espace des fonctions bornées, Studia Math., 5 (1934), 69-98. Zbl0013.06502JFM60.1074.05
  20. [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. Zbl0457.51006MR82m:05026
  21. [21] B. GRUNBAUM, Arrangements and spreads, CBMS Regional Conference Series in Math., n° 10 (1972). Zbl0249.50011MR46 #6148
  22. [22] B. HAJEK, Stochastic integration, Markov property and measure transformation of random fields, Ph. D. Dissertation, Berkeley (1979). 
  23. [23] R.E. JAMISON, A general theory of convexity, Doct. Dissert., Univ. of Washington (Seattle, 1974). 
  24. [24] T. KOVARI, V.T. SOS, P. TURAN, On a problem of K. Zarankiewicz, Colloquium Math., 3 (1954), 50-57. Zbl0055.00704MR16,456a
  25. [25] G.G. LORENTZ, Lower bound for the degree of approximation, Trans. Amer, Math. Soc., 97 (1960), 25-34. Zbl0128.06701MR22 #8266
  26. [26] B. REZNICK, Banach spaces with polynomial norms, Pac. J. Math., 82 (1979), 223-235. Zbl0413.46013MR83c:46007
  27. [27] G. RINGEL, Teilungen der Ebene durch Geraden oder topologische Geraden, Math. Z., 64 (1955), 79-102. Zbl0070.16108MR17,651g
  28. [28] C.A. ROGERS, Hausdorff measures, Cambridge University Press (1970). Zbl0204.37601MR43 #7576
  29. [29] H.P. ROSENTHAL, A characterization of Banach spaces containing l1, Proc. Nat. Acad. Sci. USA, 71 (1974), 2411-2413. Zbl0297.46013MR50 #10773
  30. [30] N. SAUER, On the density of families of sets, J. Comb. Th., A 13 (1972) 145-147. Zbl0248.05005MR46 #7017
  31. [31] I.J. SCHOENBERG, Metric spaces and positive definite functions, Transact. Amer. Math. Soc., 44 (1938), 522-536. Zbl0019.41502MR1501980JFM64.0617.02
  32. [32] H.S. SHAPIRO, Some negative theorems of approximation theory, Michigan Math. J., 11 (1964), 211-217. Zbl0123.09202MR29 #5041
  33. [33] S. SHELAH, A combinatorial problem ; stability and order for models and theories in infinitary languages, Pacific J. Math., 41 (1972) 247-261. Zbl0239.02024
  34. [34] G. SIERKSMA, Generalized Radon partitions in convexity spaces, preprint (1980). Zbl0489.52001
  35. [35] E.H. SPANIER, Algebric topology, Mc Graw Hill (1966). 
  36. [36] H.M. STARK, An introduction to number theory, Markham Publ. Co., 1971. 
  37. [37] E. SZPILRAJN (Marczewski), Ensembles indépendants et mesures non séparables, C.R.A.S., Paris, 207 (1938), 768-770. Zbl0020.10901JFM64.0192.03
  38. [38] H. TVERBERG, A generalization of Radon's theorem, J. of the London Math. Soc., 41 (1966), 123-128. Zbl0131.20002MR32 #4601
  39. [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. Zbl0247.60005
  40. [40] H.E. WARREN, Partitions by real algebraic varieties and applications to questions of nonlinear approximation, Bull. AMS, 73 (1967) 192-194. Zbl0223.14027MR35 #642
  41. [41] H.E. WARREN, Lower bounds for approximation by nonlinear manifolds, Trans. AMS, 133 (1968), 167-178. Zbl0174.35403MR37 #1871
  42. [42] D.J.A. WELSH, Matroïd theory, Academic Press (1976). Zbl0343.05002MR55 #148
  43. [43] R.S. WENOCUR, R.M. DUDLEY, Some special Vapnik-Cervonenkis classes, Discrete Math., 33 (1981), 313-318. Zbl0459.60008MR83f:60050
  44. B.J. BIRCH : On 3N points in a plane, Proc. Cambridge Phil. Soc., 55 (1959), 289-293. Zbl0089.38502MR22 #201
  45. J.A. BONDY : Induced subsets, J. Comb. Th., B 12 (1972), 201-202. Zbl0211.56901MR47 #8315
  46. K. GLAZEK : Some old and new problems in the independence theory, Colloquium Math., 42 (1979), 127-189. Zbl0432.08001MR82j:08006
  47. M.G. KARPOVSKY, V.D. MILMAN : Coordinate density of sets of vectors, Discrete Math., 24 (1978), 177-184. Zbl0401.05015MR80m:05004
  48. P. TOMASTA : “Dart calculus” of induced subsets, Discrete Math., 34 (1981), 195-198. Zbl0475.05002MR83f:05055

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.