Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

отношению числа п (А) элементов выборки, принадлежа­ щих А, к общей длине выборки]

п(А)

I •

Теорема Бернулли утверждает, что при фиксирован­ ном событии А уклонение частоты от вероятности стре­ мится к нулю (по вероятности) с ростом объема выборки, т. е. для любого А справедливо:

Р {|І>(Л) - ѵ ( 4 ) |> е } - * 0 . l—*QO

Нас же будет интересовать максимальное по классу S уклонение частоты от вероятности:

я (Z) = sup IV1(4) — Р (Л) |. Aes

Величина я (I) является функцией точки в простран­ стве X (I). Будем предполагать, что эта функция измерима относительно меры в X (I), т. е. что я (Z) есть случайная величина.

Если величина я (Z) стремится по вероятности к нулю при неограниченном увеличении длины выборки Z, то говорят, что частота событий А S стремится (по веро­ ятности) к вероятности этих событий равномерно по классу S. Дальнейшие теоремы посвящены оценкам ве­ роятности события

lim Р {я (Z) Д> е} = 0.

I—>оо

Вотличие от обычного закона больших чисел равно­ мерная сходимость частот к вероятностям может иметь или не иметь места в зависимости от того, как выбрано

множество S и задана вероятностная мера Р (х). Приве­ дем простейший пример, когда равномерной сходимости нет.

Пусть X — интервал (0, 1) и на нем задано равномер­ ное распределение вероятностей, т. е.

Р {х < а} = а; (0 < а < 1).

208гл . X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ с х о д и м о с т и

Вкачестве системы S рассмотрим любую совокупность событий (измеримых подмножеств X), содержащую все ко­ нечные подмножества интервала (0,1). Очевидно, что ве­ роятностная мера Р (А ) каждого события, состоящего лишь из конечного числа элементов, в нашем случае равна нулю.

Пусть теперь дана выборка х1, ..., жг. Рассмотрим ко­ нечное множество А* ЕЕ S, состоящее из тех и только тех элементов х, которые встретились в этой выборке. Очевид­ но, что

ѵ(Л‘;жь . ..,ж,) = ^ - ^ - = 1,

в то время как Р (А*) = 0. Учитывая, что всегда

I Р (Л) - V (А) I < 1,

получаем

sup IV (Л; хъ ..., ж,) — Р (Л) I = 1. Aes

Это соотношение выполняется тождественно для любой выборки любой длины. Таким образом, в данном случае величина

л й ( а * , . . . , х і ) = 1

и не стремится к нулю ни в каком смысле. Совершенно аналогично показывается, что

n s ( хг , . . . , Хі) = = 1

и в более общем случае, когда X есть и-мерное евклидово пространство, Р (х) — любое распределение, обладающее плотностью, а S — любая система событий, включающая все события, состоящие из конечного чиСяа элементов. В частности, при этих предположениях в качестве S мож­ но взять полную систему событий, составляющую всю а-алгебру; тогда

л(Жі, ..., жг) =3 1

иравномерной сходимости нет. Таким образом, во многих случаях равномерная сходимость частот к вероятностям не имеет места для полной системы событий. Для того чтобы такая сходимость происходила, приходится в каче-

ствѳ S рассматривать более узкие (не полные) системы со­ бытий.

Примеры систем S, для которых выполняются условия равномерной сходимости частот к вероятностям, будут приведены ниже. Отметим лишь то, что для конечных сис­ тем S, содержащих N событий, равномерная сходимость всегда имеет место. В самом деле, из усиленного закона больших чисел известно, что для каждого А последова­ тельность

л (А; хх, ..., х г) = I Р (А) — V 1 (А) |

стремится к нулю с вероятностью единица при I -> оо. Поскольку число событий в S конечно,

ns (xj., ..., Xi) = max я (Лг; хх, ..., ,гг) Аі, ..., АJY

и также стремится к нулю с вероятностью 1. Выведем оценку вероятности

Р {ля (%, ..., Хі) > е}

для случая конечной системы S. Величина ѵ (А) распре­ делена по биномиальному закону

Р(ѵ (Л)) = CfP (Л)*Л>г (1 — Р (Л ))й-^»г.

Поэтому

р {IV (А) - Р (А) I > 8} = 2 ' С\Рк (А) (1 - Р (A ) f \

к

где штрих у суммы означает, что к пробегает значения, удовлетворяющие неравенству

к_

т - Р ( А ) > е .

Событие ns (Z)^>e означает, что по крайней мере для одного из событий А ц ..., A N справедливо |ѵ (А) — Р (А) |^>

е. Поэтому по теореме о сложении вероятностей

§3. Определение функции роста

Вэтом параграфе будет введена характеристика клас­ са событий, достаточная для выяснения факта равномер­ ной сходимости.

Пусть X — множество, S — некоторая система его подмножеств, X 1 = хг, ..., жг — последовательность эле­ ментов X длины I. Каждое множество 4 g S определя­ ет подпоследовательность Х а этой последовательности, состоящую из тех и только тех элементов, которые принад­ лежат А. Будем говорить, что А индуцирует Х а на после­ довательности X 1. Обозначим через

As (жІ5 ..., ж,)

число различных подпоследовательностей Х а , индуциро­ ванных множествами А ЕЕ S. Очевидно, что

As (хи ..., ж,) < 21.

Число As (xj, ..., Ж;) будем называть индексом системы S относительно выборки хг, ..., жг.

Определение индекса системы можно сформулировать

индекс As (Ж], ..., х г) есть число классов эквивалентности, на которые система S разбивается этим отношением экви­ валентности.

Очевидно, что эти два определения равносильны.

где максимум берется по всем последовательностям дли­ ны Z, назовем функцией роста системы S. Здесь максимум всегда достигается, так как индекс As (жх,, ..., ж г) принима­ ет лишь целые значения. Используя функцию роста, сфор­ мулируем ниже достаточные условия равномерной схо­ димости частот к вероятностям по классу событий и дадим

212 г л . X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ с х о д и м о с т и

Пусть дана последовательность точек xlf ..., Xi без пов­ торений. Изменив порядок последовательности, можно добиться того, что

А8 (жх, ..., хі) = I + 1.

Если в последовательности есть повторения, то индекс Дв (хх, ..., Хі) разве лишь уменьшается.

Поэтому

из всех множеств, каждое из которых представляет собой объединение конечного числа непересекающихся сегмен­

достаточно малыми сегментами с рациональными концами и взять их объединение. Поэтому в данном случае

т8 (I) = 21

(отметим, что система S содержит лишь счетное число эле­ ментов).

П р и м е р З . Пусть X — п-мерное (п >= 1) евклидово пространство, S — система всех подмножеств вида

{X : (ж, ф) > 0 } (ф *= 0).