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

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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

	5 13. ПРИЛОЖЕНИЕ К ГЛАВЕ XIV			337
Умножим	скалярно	последнее равенство на ср:
		— ІФ 12 =	E lit e . Ф).	(П.2)
Учитывая,	что Ѵг ^	0, из равенства (П.2) имеем,		что по крайней
мере для	одного і	(xj, ф)	О,
		(xj, ф)	О,

т. е. система строго невыпукла в определении 2'.

Покажем теперь, что из 2' следует 2. Допустим, что не сущест вует вектора ф ф 0 такого, что для всех хі

СЩ, Ф) > 0.

Отсюда следует, что нуль принадлежит выпуклому конусу, порож денному х\, . . ., Хк, так как в противном случае в силу эквива лентности 1 и 1' найдется вектор <р такой, что для всех х;

(хь Ф)	0,
в противоречии с 2 .
Назовем вектор хц базовым, если существует представление
нуля вида

0 = 2 Ѵ і	(Ті>°).
i= l

в которое вектор хк входит с ненулевым весом (т. е. у^ ф 0). Выпуклый конус, порожденный всеми базовыми векторами

из X , совпадает с гиперпространством Ек, порожденным этими век торами. Действительно, если вектор хк базовый, то вектор —хц принадлежит конусу, порожденному базовыми векторами из X, так как из соотношения

0 = SVjXj (уis ф 0, Ѵі > 0)

следует, что

-*fc = -7 -2 Ѵі + Хл-	(Н-З)
* /С?И

Произвольный вектор у пространства Еj, порожденного базо выми векторами из X, представим в виде

у = І а ixit

где хі — базовые векторы; здесь некоторые аг могут быть отрица тельными.

Представим все члены суммы с отрицательными коэффициента ми осг в виде I а г- | (—х;), a (—хг-) в соответствии с (П.З) разложим по базовым векторам с неотрицательными коэффициентами.

Таким образом, получим представление

у — ІЬ іХі , bi > 0, 26j > 0

для произвольного у е Ец.

Далее рассмотрим следующие возможности.

А. Пространство Ец, порожденное базовыми векторами, сов падает со всем пространством Еп. В этом случае, как только что

338 гл. XIV .	п о с т р о е н и е р а з д е л я ю щ е й		г и п е р п л о с к о с т и
показано, выпуклый конус, порожденный X, совпадает с Еп, т. е.
выполняются	условия определения	2.	меньшую, чем Еп,
Б. Пространство Е-ц имеет размерность
и при этом все векторы из X базовые.		В этом случае рассмотрим

произвольный вектор <р из Еп, ортогональный Е^. Очевидно, что

при этом для всех	xt (Е X выполняется равенство
		(* г , Ф)	= О
в противоречии с	определением		2'.
В. Пространство		Е^ имеет размерность меньшую, чем Еп,
и не все векторы	X	базовые.

Тогда пространство Еп представим в виде произведения двух ортогональных подпространств

Еп = Efc X Еп~і(.

Рассмотрим множество проекций У небазовых векторов в пространстве Еп-

Утверждается, что множество У образует неразвернутую си стему векторов. Действительно, если это не так, то, как уже было показано, выпуклый конус, порожденный У, содержит 0, т. е.

существуют такие бг- ^ 0, 2 б г- )> 0,	что
26іУі =	О,
где уі — проекции небазовых векторов в Еп-ц.
Рассмотрим вектор		(П.4)
X = 2 бгжг-,		(П.4)

где Xi — небазовые векторы, проекции которых равны соответствен но уі.

Тогда

n Pßn-fr * ^ 2діУі = °-

Следовательно, вектор х принадлежит пространству Е/:. Поэ тому вектор —X может быть представлен как линейная комбинация базовых векторов xt с неотрицательными коэффициентами

	-	* = 2 Гі**і -		(П.5)
Суммируя (П.4) и (П.5),		имеем
	О =	26;*г +	2ух.	(П.6)
Легко видеть, что в разложении			нуля (П.6)	хотя бы один не
базовый вектор X участвует с ненулевым весом.
Полученное противоречие доказывает, что множество проекций
У не развернуто.
Покажем теперь, что это утверждение находится в противо
речии с тем,	что множество векторов X сильно развернуто в смысле
определения	2'.
Поскольку множество У не пусто и не развернуто, то, согласно
определению	в Еп~к существует такой вектор ф0, что
		ІУі, Фо) >	О,	(П.7)

§ 13. ПРИЛОЖЕНИЕ К ГЛАВЕ XIV	339
а следовательно,
(ч, Фо) = О	(П.8)
для базовых векторов и

Ы, фо) = (уи Фо) > О

для небазовых векторов, в противоречии с определением 2'. Эк вивалентность определений 2 и 2' доказана.

Фактически попутно доказана следующая теорема.

порож

Теорема П.З. Если

минимальный

выпуклый

конус,

денный

конечной

системой векторов

(жі, . . .,

ж/j}

= X, не совпа

дает со

всем пространством Еп, то

существует

вектор

ф =jfc О

такой, что

для

всех

Х(

(*і, Ф) >

О,

(П.9)

причем

для

небазовых

векторов

неравенство переходит в строгое

іхіі ф)

0. Если же система векторов X сильно

развернута,

то

всякий ее вектор является базовым.

вектор такой,

что

Замечание.

Если

ф ф 0 — произвольный

для всех і выполняется (П.9),

то для всякого

базового вектора xj

неравенство

переходит

в равенство,

т.

е.

(xh ф) =

Действительно, пусть xj — базовый вектор. В силу (П.9)

(xj, Ф ) > 0 .

(П.10)

В то же время, как показано выше ((П.З)), вектор —xj разложим по базовым векторам с неотрицательными коэффициентами

—xj = 2	у {х;	(уі >	0).
Следовательно,		(xj,	ф;) > 0.	(II.11)
— (xj, ф) =		(xj,	ф;) > 0.	(II.11)
Из (П.10) и (П.11) получаем
(xj,	ф) =	0.

2. Из теоремы П.З легко следует известная теорема Куна — Таккера.

Теорема П.4 (Куна — Таккера). Пустъ заданы дифференци руемая функция F(x) и линейные функции (х, fi) при і = 1,2, . . .

. . ., п. Пустъ х0 доставляет условный минимум F (х0) при ограни чениях

	{х, fi) >	сг.
Тогда существуют такие числа		^	0,	что выполняются условия'.
( VF (*0) =	2 %іІі,
I h Ы і ) -	Ci) = о	(i	=	1 , 2 , . . ., n).	(П.12)

Д о к а з а т е л ь с т в о . Если VF (x0) равен нулю, то утвер ждение леммы тривиально, так как можно положить все Я; равны ми нулю.

Занумеруем от 1 до р те ограничения, для которых

(*о, fi) = сг•

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

Допустим, что VF (ж0) ф 0	и утверждение теоремы неверно.
Это значит, что система векторов
— V F (*о)>	/ і і • • • I /р

такова, что —VF (х0) не является базовым вектором системы. Действительно, если бы вектор — VF (ж0) был базовым, то су

ществовало бы представление

			° =	1=1	т ^ - ѵ /•>„),
				1=1	(П.12).
а значит,	и	представление			(П.12).
а значит,	и			2			теоремой		П.З, существует
Следовательно, в соответствии с							теоремой		П.З, существует
вектор ф	такой,		что
для всех	і	(1 <	і ^ I) и	(ф, /г)		> 0
для всех	і	(1 <	і ^ I) и
			(VF (х0), Ф) <				0.		(П.13)
Рассмотрим точку х (г) =					х0+ Щ.		При достаточно малом t ^ 0
ограничения		не	нарушатся, так			как	при	1	і О р
			(х0 + Up, /)		=	t (ф, ft) >		0,