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

Скачать файл (11,72Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 219

Скачиваний: 4

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

§ 5. ОСНОВНАЯ ЛЕММА

219

Таким образом, для того чтобы оценить поведение функции роста, достаточно выяснить, каково минималь ное число п такое, что ни на одной последовательности длины п система S не индуцирует все возможные подпо следовательности.

Замечание 2. Существуют примеры класса событий S, для которых

п—і

ms (l) = 2 СІ, i=0

где п — первое число, при котором

т8 (I) ф 21.

Пусть X — произвольное бесконечное множество, а S состоит из всех его конечных подмножеств с числом эле ментов, меньшим п. Очевидно, что

ms (I) = 21 при I < п,

п—1

ms (I) = 2 С\ при І ^ п .

і—О

Таким образом, оценка теоремы для функций ms (I), не равных тождественно 2г, может достигаться.

§5. Основная лемма

Вконце § 2, было сказано, что основная идея, на кото рой строятся условия равномерной сходимости частот к

вероятностям, состоит в том, что бесконечная система с(Р] бытий S заменяется конечной подсистемой, состоящей из | таких событий, которые различимы на конечной выборке.

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

лемой равномерной близости частот в двух следующих
друг за другом выборках одинаковой длины.
Оказывается, что равномерная сходимость к нулю раз
ности частот в двух полувыборках является необходимой
и достаточной для равномерной сходимости частот к ве
роятностям и из оценок скорости одной сходимости сле	j
дуют оценки для другой.	j

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

Итак, пусть взята выборка длины 21;

Х ^	• •«, Xi, Хі+1, ..., Х21

и подсчитаны частоты выпадения события А ЕЕ S на пер вой полувыборке Х[ = х г , ...,:% и второй полувыборке

Х 21 — х г+г, хп . Обозначим соответственно частоты че рез ѵ' (А) и ѵ" (А) и рассмотрим отклонение этих величин:

Ра ( х х , ..., x2l) = I ѵ' (А) — ѵ" {А) I.

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

		ps (xl t . ..,			= sup pA (xlt ..., x2l).
					A<=S
Напомним,			что через ns ( x lt . . . , x{)					мы обозначили
		ns {xu ..., X[) = sup I vl (Л) — P (A) \|.
					A e s
Далее	будем		полагать,		что	как	jis { х г ,		. . ., xj), так и
ps (х1,	...,	х 2і)	— измеримые функции.					величин
Основная лемма.				Распределения				величин		( х х , . . .
...,Хі)	и ps	(xi t ..., x2i) связаны следующими соотношениями:
а)	Р (ns (хь ..., хг) > е) < 2Р jps (х1;----хы) >									, если
только I > — :
	^	8
б) Р{р«(х1(...,х 2г) > е } < 2 Р {яв (*1,...,а :г)> - \| - } -
					-	[Р {я*3 (arl t ..., Xi) >				-j-J ]2 .
Д о к а з а т е л ь с т в о .					Доказательство				утверждения
а) построено по следующей схеме.							Представим			себе, что
полувыборки			х1, ...,	Хі и х [+1, ...,			х2і берутся последова
тельно и независимо.				Допустим, что первая полувыборка
оказалась такой, что
		sup I v' (Л; хъ ..., хг) — Р (Л) I >							е.	(10.16)
		Aes
Это значит, что в классе S имеется событие А* такое, что
			I V' (Л) - Р (А) I > е.
На второй		полувыборке			будем следить за отклонением

§ 5. ОСНОВНАЯ ЛЕММА

221

частоты от вероятности лишь для этого фиксированного события А*. Так как нас интересует всего одно событие, то можно воспользоваться обычным законом больших чи сел. Поэтому при достаточно большом I с достаточно вы сокой вероятностью частота ѵ" (4*) близка к вероятности

Р (А*):

К И * ) - Р ( л * ) K - f

и, следовательно,

IV' (А*) - V" (А*) I > -і- и pS(хъ

- г • (10.17)

Таким образом, условная вероятность (10.17) при усло вии (10.16) становится достаточно большой при соответст вующих I. Это и позволяет доказать утверждение а). Перейдем к формальному доказательству.

По определению

Р {Ps (Жі, • • •, Xi) > -j} = §	0 (ps (*1, • • •, Хц)	dP (X21),
X (20
где
1	при z\|> 0 ,
0	при z 0.

Учитывая, что пространство X (21) выборок длины 21 есть прямое произведение (I) и Х 2 (I) полувыборок дли ны I, согласно теореме Фуббини [36] для любой измери мой функции ф (хх, ..., х2і)

^	Ф (хи . . х2і) dXn =		jj	[ ^	Ф (хи ..., X2і) dXl2j dX[.
X Ігі)			хІ(і)	xi(i)
Поэтому имеем
р { р Ц Х ы) > т - } =
	= 5 d P ( x [ )		5 e ( p S ( ^ , . . . , ^ ) - 4 - ) d p ( ^ )
	x\(l)	xt(l)
(во	внутреннем	интеграле			первая полувыборка

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

фиксируется). Обозначим через Q событие пространства

Xi (I)

	{л (жх, ..., жг) >	е}
и, ограничивая интегрирование, получим
Р {	pS(X2' ) > - f }jj>.0 [> (* ,...,* * )•
Р {
	> \ d P { X [ )	d P ( X 2)l . (10.18)
	Хг (l)

Оценим внутренний интеграл правой части неравенст ва, обозначив его через I. Здесь хІ5 ..., жг фиксировано и таково, что я (х1, х г) е. Следовательно, существует А* GE S такое, что

Тогда	I Р (А) — V(Л;		ж1?	..., жі) I > е.
Тогда
\	Ѳ sup Ра (хи .			d P ( X ) >
	Lass
	>	[	ѳ	(Х2г) — -I-] (X1).
Пусть,	например,	X ,(!)
Пусть,	например,
	v' (А*; Жц ...,	жг) < . Р ( Л * ) — е