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

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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

332 ГЛ. XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ

где

D = тах(|ж 4|, \щ\),

і,і

р — расстояние от начала координат до выпуклой оболоч

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

Нетрудно убедиться, что число р и модуль обобщенного портрета, полученного при к = — 1, связаны соотноше нием

1 р “ Н>(-1)Г

Если, как и раньше, воспользоваться несмещенностью оценки скользящего контроля, то для вывода (14.40) достаточно доказать следующую теорему.

Теорема 14.12. Число ошибок при скользящем контроле для метода обобщенного портрета при к= — 1 не превосхо

дит D2 I ф (— 1)

I 2.

Пусть

дана обучающая

по

Д о к а з а т е л ь с т в о .

следовательность жх, . . .,

ха, хг, . .

., хъи максимум соот

ветствующей функции

W (а,

ß)

при а ^

достига

ется в точке а; = сц°, ß;-

ß/\

Соответственно ф == 2 а ьхг — 2ß/E7-— обобщенный пор

трет.

Обозначим

через

а р,

ßp

точку,

доставляющую

максимум функции W (а,

ß) на множестве at

ß^

ар =

0. Очевидно, что ей соответствует обобщенный порт

рет,

построенный по выборке без вектора хѵ:

Фр =

аіХг — 2

ßfSj-

i = l

3=1

Обозначим через

Wp значение

функции W (а,

ß) в точке

а і =

а і (і =?ь р),

ар =

ß;- = ß®. Очевидно, что

W (ар,

ßp) >

и одновременно

Поэтому

W ( а р,

ßp) < J E ( a °

ß°).

W (а°, ß°) -

W (ар, ßp) <

W (а°, ß°) -

W p.

(14.41)

§ 12.	СТАТИСТИЧЕСКИЕ ОСОБЕННОСТИ МЕТОДА						333
Далее,
W (а®, ß°) -	W p = а°р -	± - ('Фо, Фо) + 4 - I Фо -			а>РІ2 =
		= ар	— а®	(ф0, жр) +	-і-	(а®)2 жр	I2.
Для крайнего вектора		хр	— а®		-і-	1	I2.
	W (а®, р») -	Wp = -L (dp)21жр I2.				(14.42)

Будем считать далее, что обобщенный портрет фр непра вильно опознает вектор хр. Это значит, что

(Фр, хр) < . (14.43)

Кроме того, как было показано при доказательстве преды дущей теоремы, это возможно только в том случае, когда хр является крайним вектором обобщенного портрета ф0.

Исследуем теперь левую часть неравенства (14.41). Для этого рассмотрим один шаг максимизации функции W (а, ß) из точки а р, ßp вдоль оси а р )> 0 и выберем оптимальное значение ар. Имеем

W (а, р) = W (ар,ßp)+ ар (1 - (жр,ф р))---«41Ъ Г-

Отсюда получаем оптимальное значение а р;

Увеличение W (а, ß) на этом шаге составит

AWp =	1_ (1 -(* р ,Ф р ))*
	2	I ж \|2

Так как S W P не больше, чем приращение функции при полной максимизации, то

W (а0, ß«) - W (ар, ßp) >		№ ѵ =	fl -	яЬ
W (а0, ß«) - W (ар, ßp) >		№ ѵ =	----- 1^	. (14.44)
Объединяя (14.41),	(14.42),	(14.44),	получим
1	,, ^	1 а -^ р .Ф Д "

334 ГЛ. XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ

откуда, учитывая (14.43)
	аг	1 — (*„, Ф)		1 — ft
				> 2 \|* J 2
Аналогично	оценивается			ßp:
			1 — ft
		ß p > 2\|* РІ* '
Учитывая, что	\ х р \ ^ D,		\ЯѴ \| ^		D, имеем
		(Хр ^	1 —к		’
				2D2
		ßp	1 —ft		•

Пусть теперь при скользящем контроле число непра вильно опознаваемых векторов первого и второго классов

равно соответственно		и Z2. Тогда в силу теоремы 14.10
при отрицательном к
	а	Ь		а	Ь "
сф, ф) = 2 аі ~ k 2 ßj > 2 ai — к 2
	i=l	J=1		1=1	5=1
где 2 ' и 2 "	берутся	только по тем векторам, которые
неправильно опознаются при скользящем контроле.
Далее,
	ѵ^	(1 —ft),		ft (1 — ft) т
	(Фі Ф) ^	<di %	^i	2D2	^2'
Окончательно при /с <		—1
	(*і +	h)	2(ф, ф) D2
	(*і +	h)	(1-ft) '
При 0 > /с >	- 1			2 (ф, ф) Р2
	(Zi +	Z2)		2 (ф, ф) Р2
	(Zi +	Z2)		ft (1 — ft)
				ft (1 — ft)

В случае к = — 1

( h + h ) < (Ф(-1)’ Ф(-1))^2-

Теорема доказана.

§ 13. ПРИЛОЖЕНИЕ К ГЛАВЕ XIV

335

§13. Приложение к главе ХІУ

1.Рассмотрим в евклидовом пространстве Еп конечную си стему векторов X = хг, . . ., х/£.

Множество Г векторов х, представимых в виде

х = S	Ѵ і-
і—1
Yi >	О,
к
2 т ,> о ,
І=1

образует минимальный выпуклый конус, содержащий систему векторов X, или, иначе, выпуклый конус, порожденный системой векторов X.

Определение 1. Система векторов X не раавериута, если порожденный ею выпуклый конус не содержит нуля.

Определение 2. Система векторов X сильно развернута, ес ли порожденный ею выпуклый конус Г содержит все пространство Еп.

Определения 1 и 2 эквивалентны следующим двум определениям.

Определение 1'. Система векторов	X не развернута, если
существует такой вектор ф ЕЕ Еп, что	для всех г; Е X
(^іі Ф) 0.

Определение 2'. Система векторов X сильно развернута, если для всякого ф £= Еп найдется такой вектор х; ЕЕ X, что

(хі, ф) < 0.

Докажем, что определения 1 и 2 эквивалентны 1' и 2'.

Теорема П.1. Определегше 1' эквивалентно 1.

Д о к а з а т е л ь с т в о . Пусть система векторов не развер нута в смысле 1'. Значит, существует такое ф, что

(*/, Ф) > 0

для всех Xі ЕЕ X.

Рассмотрим произвольный элемент г выпуклого конуса, по рожденного системой хі, . . ., хц:

х = 2	Vi-
і—1
Y i > 0 ,		(П.1)
2Ті > 0.
Умножим скалярно (П. 1) слева и справа на ф:
(х, ф) =	(*г. Ф)-

336 гл.	XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ	ГИПЕРПЛОСКОСТИ
Так как (xt, ф) > 0 и по крайней мере одно Ѵг >		0, то
т. е. X	(х, ф) > О,
т. е. X	0.

Таким образом, из 1' следует 1.

Пусть теперь система векторов X выпукла в смысле определе ния 1. Рассмотрим выпуклую оболочку X системы X, т. е. множество

векторов X, представимых	в	виде
* =	к	Ѵ і	е z )>
* =	2	Ѵ і	е z )>
	i=i
		У і >	о ,
		2Ті =	1.

Согласно определению 1, это множество не содержит нуля. Кроме того, оно замкнуто и ограничено. Поэтому вектор х0, на котором

достигается	min \| х\|,	не равен нулю и принадлежит множеству X.
	5сеХ	что для любого і*		£	І
Покажем теперь,
Рассмотрим	отрезок	( х* ,	ж„) > 0.

	(1 — t)x0 + tx*		(х* €Е X ,	0 <	< < 1).

Легко видеть, что этот отрезок принадлежит X. Найдем модуль произвольного вектора х, конец которого лежит на отрезке

(1 — t)x0 -)г tx*:

I X I = V	— t) Хо + tx*, (1 — t) Хо +	tx*)) —
	= У	"\|0\|»-2t (101-(•,*«,)) + О(t),

где о (t) — величина второго порядка малости по t.

Так как \| х \| ^	\| х0 \|, то коэффициент при линейном члене должен
быть неположительным,		т. е.
откуда следует	I ЩI2 —		(х*, х0) <			0,
	(х*, х0) >			I я0	\|2 >	0.

Последнее неравенство справедливо для любого х* (= X,							а следо
вательно, и для Xi,	. .	х п . Значит,			условие определения 1 выпол
нено.
Таким образом, эквивалентность 1 и 1' показана.
Теорема П.2.	Определения		2'	и	2	эквивалентны.	значит,
Д о к а з а т е л ь с т в о .			Пусть		справедливо 2. Это