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

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

Смотрите также файлы

Смотрите также файлы

Информация

Списки файлов

Дополнительно

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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

§ 4.	СВОЙСТВА ФУНКЦИИ РОСТА			213
Тогда индекс	As (х1, ..., х {)	определяет число различ
ных разбиений I	векторов хг,...,х і		на два класса с помо
щью гиперплоскостей, проходящих			через начало	коор
динат. Как было показано в главе V,
		п—г
А {хі,..., xt)		2 2	C-i»
откуда следует		i—l
	n—1
		Cli-		( 10.10)
	ms (Z)<2 2
	І~1
Можно показать, что в действительности
	п—1
	ms (l) = 2 2	CU.
	і=1

Аналогично показывается, что если X — «-мерное евкли дово пространство, а S — система подмножеств вида

{х : (х, ер) > с},

где ф — произвольный вектор, а с — произвольная ска

лярная величина, то

ms (l) = 2 2 CU-

			i—l
		§ 4. Свойства функции роста
	Функция роста класса событий S обладает следующим
замечательным свойством.
на	Теорема 10.1. Функция роста либо тождественно рав
на	21,	либо, если это	не так,	мажорируется функцией
п— 1
2	С),	где п — минимальное число I, при котором
і=0		ms (I) 2l.
		ms (I) 2l.
Иначе говоря,			■либо ~ 2 l,
			■либо ~ 2 l,
		ms (I) =		п—1
		ms (I) =	либо ^	2 С\.

і=0

214 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ СХОДИМОСТИ

Для доказательства этого утверждения нам понадо бится следующая лемма.

Лемма. Если для некоторой последовательности хъ ...

..., хі и некоторого п !> 1

	п— 1
Д (xlf ..., Хі)	2 Сь
	і=0

то существует подпоследовательность Х п длины п такая, что

As (Хп) = 2”.

Д о к а з а т е л ь с т в о . Обозначим П—1

2 сі = Ф к о

(здесь и дальше считаем, что при і^> I С\ = 0). Для этой функции, как легко убедиться, выполняются соотно шения

Ф(1, l) = 1,
Ф (п, I) = 2' при I < п - 1,	(10.11)
Ф (п, Г) = Ф (п, I — 1) + Ф (п — 1, I ~ 1)	п )> 1 ,Z 1.
при	п )> 1 ,Z 1.

Эти соотношения в свою очередь однозначно определяют функцию Ф (п, I) при Z> 0 и п > 0.

Будем доказывать лемму индукцией по I и п. Для п — І и любого I > 0 утверждение леммы очевидно. Дей ствительно, в этом случае из

As (х1ѵ ..., г,) > 1

следует, что существует элемент последовательности х , такой, что для некоторого А х ЕЕ S выполняется ij е 4 і, а для некоторого другого А 2 ЕЕ S выполняется х ( ф. А 2 и, следовательно,

А3 {хі) = 2.

Для / < п утверждение леммы верно ввиду ложности посылки. Действительно, в этом случае посылка есть

As (хи ..., хі) > 21,

	§ 4.	Св о й с тв а ф у н й ц й и		ро ста				215
что невозможно, так как
		As {хг, ...,	®,) <	2г.
Наконец, допустим, что лемма верна для п							п0 (п0 ^ »
]> 1) при всех I.		Рассмотрим теперь случай п = гс0						1.
Покажем, что лемма верна и в этом случае для всех I.
Зафиксируем п = п0 + 1			и проведем индукцию по Z.
Для I <	га0 + 1,	как указывалось, лемма верна. Предпо
ложим, что она верна при I <1 10, и покажем, что она спра
ведлива для I =		10 + 1. Действительно, пусть для некото
рой последовательности
		X±j
справедливо условие леммы:
	Л® (%, •••, хш ) > Ф («„ +			1,	/0	+ 1).
Найдем подпоследовательность длины п0 +							1;
такую,	что	Х"о+1 = Жі,	..., хПо+1
такую,	что	As (%, •••, Хпо+і) = 2”0+1.
		As (%, •••, Хпо+і) = 2”0+1.
Рассмотрим		подпоследовательность			Х?о =		ж1; ...,	х
Возможны два случая;
а)	As (х1; ..., :г/о) Д> Ф (ге0				1,	10),
б)		As (ж2, ..., хІ0) < Ф (/г„ +				1,Z0).

В случае а) в силу предположения индукции существует подпоследовательность длины п0-\-1 такая, что As (Xn»+1)= = 2П°+1, что и требуется.

Для случая б) разделим подпоследовательности после довательности Х 1°, индуцируемые множествами из S , на два типа. К первому типу отнесем такие подпоследова тельности Х г, что на полной последовательности Х 1о+1

индуцируется как Х т, так и Х г, х гаП.				Ко второму — такие
Х г,	что на последовательности Хг°+1			индуцируется либо
Х т,	либо	Х т, ж/0+1. Обозначим	число подпоследова
тельностей		первого типа Кг, а	второго типа К 2■Легко
видеть, что
As (жх,		х и) = К х + К2, As (хѵ		х ш ) = 2Кі + К г,

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

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

As fa , ..., х ш ) = As (xx, ..., x lo) + К г.

(10.12)

Обозначим через S' систему всех подмножеств А Е S таких, что на последовательности Х !о они индуцируют подпоследовательности первого типа. Тогда, если

б') Кг = А«' (хг, ..., хі0) > Ф (п0, 10),

то в силу предположения индукции существует подпосле довательность Х ‘п* = хи, ..., Хі такая, что

Д5(жг„ ...,ж ч ) = 2П° и Xn°CZX\

Но тогда для последовательности xilt ..., ж,- , х ш имеем

А8(Хіі, . . . , хІщ, х ш ) = 2"0+1,

так как для каждой подпоследовательности X 9, индуциро

ванной на последовательности X		найдутся две подпо
следовательности, индуцированные		на Х 7^,	Ж/0+1, а имен
но X 9 и X q, ХіоП. Таким образом, в случае б')			искомая под
последовательность найдена.
Если же
б*)	Кг = As' (хг, ..., x h) <	Ф (п0, 10),
то получим в силу (10.12) и б)
As (хг,	..., жго+1) < Ф ( п 0 + 1, 10) + ф (п0, 10),
откуда в силу свойств (10.11) функции Ф (п, I)
As (xlt ..., ж,0+1) < Ф (п0 +		1, 10 +	1)

в противоречии с предположением, т. е. б") невозможно. Лемма доказана.

Теперь докажем теорему. Как уже отмечалось, ms (I) ^ 21. Пусть ms (Г) не равно тождественно 21и пусть п —

первое значение I, при котором ms (I) ф 21.

Тогда для любой выборки длины I, большей п, спра ведливо

As (xlt ..., хі) < Ф (п, I).

§ 4. СВОЙСТВА ФУНКЦИИ РОСТА

217

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

As (хі, ■■■, хп) = 2”.

Ыо это равенство невозможно, так как по допущению

ms (п) Ф 2”.

Таким образом, функция ms (I) либо тождественно рав

на 2г, либо мажорируется Ф (п, Г).
Теорема доказана.	может		бытъ оценена
Замечание 1. Функция Ф (п, I)	может		бытъ оценена
сверху при п > 1 и I Д> п следующим образом:
п—1		п_^
Ф ( М )= 2 c l < l , 5 TJ ^ ITr.			(10.18)
і=0	'	'

Поскольку для функции Ф (п, I) выполняются соотно шения (10.11), для доказательства (10.13) достаточно убе

диться, что при	п > 1	и	1^> п справедливо неравенство
	г"'1	,	£_	(I + 1)п		(10.14)
	(га — 1)!	'	га! ^	га!	’

и проверить (10.13) на границе, т. е. при п = і, I = п							і.
Неравенство (10.14), очевидно, равносильно неравен
ству
Г - i ( „ + I ) — ( I + i f					< 0 ,
справедливость	которого		следует		из формулы бинома
Ньютона.

Остается проверить соотношение (10.13) на границе. При п = 1 оно проверяется непосредственно. Далее про

218 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ СХОДИМОСТИ

Теперь, чтобы проверить (10.13) при п							5,	восполь
зуемся формулой Стирлинга для оценки сверху Л;
	1\ <	/ 2 л	11+ 2 е 1+12і ,
откуда при I = п		1
Г-1		(г		(г- і )
(я— і)і			и	^	ѴШі
и, далее, при	6
		Г-1	> 0,8	V 2лі
	(п - 1 ) !			V 2лі
С другой стороны, всегда
		Ф (п, V) <		2'.
Поэтому достаточно проверить,				что при I			6
		21< 1 ,2 - 7 4 = -
С ростом I (при I >		2) это неравенство усиливается и по
этому достаточно его проверить при I =						6,	в чем и убеж
			даемся			непосредственно.
				Итак, оказывается, что
				функция роста либо тож
				дественно равна 2г, либо
			при		некотором п впервые
			нарушается равенство, т.е.
			ms (Г)			21,	и тогда		при
				I >	п функция роста				ма
			жорируется				степенной
				функцией
					1,5	t■П-1		(10.15)
					1,5	(«-1)1 •		(10.15)

Это положение проиллюстрировано на рис. 21, где сплошной линией изображен график 1g2 ms (l) для случая, когда ms (I) = 2г, а пунктирными — мажорирующие функции для различных «,

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

5 Расчет центрально нагруженного фундамента под колонну.docx

Задача Проанализируйте движение и техническое состояние основных фондов, рассчитав при этом.docx

Как накопить деньги на мечту Что такое мечта.pptx

1. Основные направления работы с семьей, имеющей больного ребенка. Информационное направление.docx

верим оценку

при малых п и I: