On the Uniform Convergence of the Frequencies of Occurrence of Events to Their Probabilities
This chapter is a translation of Vapnik and Chervonenkis’s pathbreaking note В. Н. Вапник, А. Я. Червоненкис, О равномерной сходимости частот появления событий к их вероятностям, Доклады Академии Наук СССР 181(4), 781-783 (1968)
- PDF / 114,496 Bytes
- 6 Pages / 439.36 x 666.15 pts Page_size
- 104 Downloads / 169 Views
On the Uniform Convergence of the Frequencies of Occurrence of Events to Their Probabilities Vladimir N. Vapnik and Alexey Ya. Chervonenkis
Abstract This chapter is a translation of Vapnik and Chervonenkis’s pathbreaking note В. Н. Вапник, А. Я. Червоненкис, О равномерной сходимости частот появления событий к их вероятностям, Доклады Академии Наук СССР 181(4), 781–783 (1968)
essentially following the excellent translation ˇ V. N. Vapnik, A. Ya. Cervonenkis, Uniform Convergence of Frequencies of Occurrence of Events to Their Probabilities, Soviet Mathematics Doklady 9(4), 915–918 (1968)
by Lisa Rosenblatt (the editors only corrected a few minor mistakes and in some places made the translation follow more closely the Russian original). (Presented by Academician V. A. Trapeznikov, 6 October 1967)
2.1 Introduction According to the classical theorem of Bernoulli, the frequency of occurrence of an event A converges (in probability, in a sequence of independent trials to the probability of this event). In some applications, however, it is necessary to draw conclusions about the probabilities of the events of an entire class S from one and the same sample. (In particular, this is necessary in the construction of learning algorithms.) Here it is important to find out whether the frequencies converge to the probabilities uniformly over the entire class of events S . More precisely, it is important to find out whether the probability that the maximal deviation of frequency from the corresponding probability over the class S exceeds a given small number approaches zero in an unbounded number of trials. It turns out that even in the simplest examples such uniform convergence may not take place. Therefore we would like to have a criterion by which we can decide whether there is such B. Schölkopf et al. (eds.), Empirical Inference, DOI 10.1007/978-3-642-41136-6__2, © Springer-Verlag Berlin Heidelberg 2013
7
8
V.N. Vapnik and A. Ya. Chervonenkis
convergence or not. In this note we consider sufficient conditions for such uniform convergence which do not depend on the properties of the distribution but are related only to the internal properties of the class S , and we give a bound on the rate of convergence also not depending on the distribution, and finally we point out necessary and sufficient conditions for the uniform convergence of the frequencies to the probabilities over the class of events S .
2.2 Statement of the Problem Let X be a set of elementary events on which a probability measure is defined. Let S be a collection of random events, i.e., of subsets of the space X measurable relative to the measure (the system S belongs to a Borel system but does not necessarily coincide with it). Let X .l/ denote the space of samples from X of length l. On the space X .l/ we define the probability product measure by the condition P .Y1 Y2 : : : Yl / D P .Y1 / P .Y2 / : : : P .Yl /, where Yi are measurable subsets of X . This formalises the fact that sampling is repeated, i.e., the elements are chosen indepen
Data Loading...
