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

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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

§ 9. ВЫЧИСЛЕНИЕ ОПТИМАЛЬНОЙ ГИПЕРПЛОСКОСТИ

323

Из определения следует, что функция L (d) — моно тонно возрастающая непрерывная кусочно-линейная функция. Кроме того, при d —»- с» она неограниченно убы вает. Поэтому корень заведомо есть. Функция L {d) может иметь изломы (разрывы первой произвольной) только в точках

di = (хи ф) — 1, dj = (Xj, ф) + 1.

Поэтому корень L (d) можно определить так: найти ли нейный кусок, на котором лежит корень, а затем найти корень линейной функции, совпадающий с L (d) на этом куске.

Таким образом, приходим к следующему алгоритму. 1. Вычисляется значение функции L в точках dt {dj).

	2. Если при всех dt {dj) функция L {d) >							0, то корень
лежит на луче d				min {dt, dj)		и равен
		,,					Ф))
		а ~			а' + 6'
где 2 ' берется по всем векторам x t, для которых а (									0;
2 "	берется по всем векторам					а'	— число векторов х и
для которых аі				0; Ъ' — число векторов х}.
	3. Если при некоторых dt {dj) функция меньше нуля,
то	следует	найти		максимальное			dt {dj),	при котором
L {d) < 0.		Обозначим его через d*.					0 лежит на участке,
	Тогда корень уравнения L {â) ~
прилегающем справа к точке d*, и равен
				- № жі)) + S " (1 + (Ф.
		а ~~			а' + V			’
где 2 ' берется по тем векторам xt,							для которых at		0
или 1 — {xt, ф) +				d*	0; 2 "	берется по		тем векторам
Xj,	для которых				0, или 1 — d*—(Xj,			ф) >= 0;	а’ и
Ъ'	— соответственно числа слагаемых в сумме 2 ' и								2 " .
	4. ^Значение		ЛуСЛW вычисляется путем подстановки
в (44.31) корня			уравнения L {d) =				0.
	Подробнее структура алгоритма построения оптималь

ной разделяющей гиперплоскости будет рассмотрена в главе XV.

11*

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

§ 10. Построение оптимальной разделяющей гиперплоскости модифицированным методом Гаусса — Зайделя

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

хѵ . . ., ха, если

X = 2осг:гг, 2 а г = 1, а г

Аналогично точка х* принадлежит выпуклой оболочке векторов % , . . . , хь, если

X* =	2 ß j — 1, ßj > 0.

Поэтому, для того чтобы найти оптимальную разделяю щую гиперплоскость, достаточно найти минимум квадра тичной формы (ф, ф), где

ф = hctiXi — 2 ßjXj,

в области

2 а г = 1, а г > 0,

(14.32)

2 ß , = 1, ß , > 0 .

Вектор ф, доставляющий минимум, будет направляющим вектором оптимальной гиперплоскости.

В вычислительном плане эта задача никак не проще той, которая рассмотрена в предыдущем параграфе. Здесь ограничения задаются двумя условиями типа ра венства, тогда как там входило лишь одно такое условие.

Рассмотрим модифицированный метод Гаусса — Зайделя для поиска максимума (ф, ф)' в области (14.32). Модификация метода Гаусса — Зайделя направлена на то, чтобы при движении вдоль выбранной координаты, во-первых, не выйти за пределы положительного квад ранта, а во-вторых, все время оставаться на многообра

зии	2 а г = 1 (или		2ß; =	1).
Итак,		пусть в	t-й момент времени точка а (t — 1),
ß (t	— 1)	удовлетворяет		условию (14.32) и совершается

§ іо. ПОСТРОЕНИЕ МЕТОДОМ ГАУССА — ЗАЙДЕЛЯ

325

шаг вдоль координаты а,. Тогда величина шага Аа, модифицированного метода Гаусса — Зайделя опреде ляется из условия

max	\х* {t — 1) (1 — Аа,) + Аа,ж,— х* (t — 1)\|2, (14.33)
0 < Д а ,< 1	‘
где		а		Ь
		а		Ь
X* (t — 1) =		2 <*i (t — 1) XU		X* (t — 1) = 2 ßj (г — 1) Щ-
		i=l		j=1
Минимум величины (14.33)				находится при шаге
	О,	еС ЛИ	(X*(t — 1 )	— X{t— 1 ) , X ( t— 1 ) —	X,)sCC О,
	1,	если	(ж (t_i) _	ж («—1 ), ж(г—1) — ж,)	> 1 ,
Да, =	1,	если	-----;---------------;----------------		> 1 ,
Да, =			(ж (t—1) — Ж(, X (t—1) — Ж()

(ж*(г—1)—Ж*(І—1), X (f—1)—Ж()

в остальных случаях.

(ж (І—1) — Xt, X (г—1) — ж,;

Таким образом, рекуррентная процедура поиска оп тимальной разделяющей гиперплоскости задается так:

X* (t) = X* (t — 1) (1 — Да,) + ж,Да,. (14.34)

Аналогично находится значение х* (() в случае движе ния по ßt:

X* (t) = X* (t) (1 — Aßj) -f ж,Aß,,

где	если	(X* (t — 1) — X(t — 1), xt — X (t — 1)) ^ 0,
’ 0,
.	если	(ж, — ж (t — 1), X (f — 1) — ж (£ -— 1)) . .
1,		Ц — -— -------------------- —> 1 ,

(ж, — ж (£ — 1), ж, — ж (t — 1))

Aß, =

(ж, — Ж* (f — 1), X* (t — 1) — ж* (t — 1)) в остальных

(Ж, — Ж (i — 1), Ж, — Ж (f — 1))

случаях.

(14.35)

Зная X* и X*, нетрудно построить оптимальную разде ляющую гиперплоскость. Она задается парой

ф = X* — X*, с — (х , X ) — (ж , ж )

326 гл. X IV . ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ

Рекуррентная процедура (14.34), по существу, есть алгоритм Б. Н. Козинца для построения оптимальной разделяющей гиперплоскости.

Замечательная особенность этого алгоритма — пре дельная простота реализации. Однако существуют за дачи (особенно при большой размерности вектора х), для которых скорость сходимости алгоритма оказывается мед ленной (вспомним, что скорость поиска максимума в этом алгоритме определяет метод Гаусса — Зайделя). Именно для таких задач и строят значительно более сложные ал горитмы, в которых для увеличения скорости сходимости используются более эффективные методы поиска максиму ма квадратичной формы.

§11. Применение метода обобщенного портрета для нахождения оптимальной разделяющей гиперплоскости

Задача нахождения обобщенного портрета при задан ном к несколько проще, чем задача нахождения оптималь ной разделяющей гиперплоскости. В частности, при ре шении двойственной задачи в случае поиска обобщенного портрета отсутствует ограничение вида S aj = S ß;-.

Существует два способа применить метод обобщенного портрета для отыскания оптимальной разделяющей ги перплоскости.

Первый способ основан на последовательном построе нии обобщенных портретов при разных к и подборе к, близкого к к 0(теорема 14.3).

При подборе к можно исходить непосредственно из критерия

и искать максимум по к одним из известных способов по

иска экстремума функции одной переменной.		Можно так
же подбирать к из условия Sa* =	Sß*, где a,j	0 и ß;-
;> О — коэффициенты разложения	обобщенного портре

та по крайним векторам. При выполнении этого условия, как нетрудно убедиться, обобщенный портрет ф (к) коллинеарен ф 0Пт*

§11. ПРИМЕНЕНИЕ МЕТОДА ОБОБЩЕННОГО ПОРТРЕТА 327

Второй способ основан на следующем свойстве вектора фонтРассмотрим всевозможные разности вида

УИ = хі — %j ( х і GE X , X j ЕЕ X

При этом вектор фопт обладает свойством

тіп(фопт, Уіі) =	max тіп(ф, уі})
і,}	\|ч>\|=1 г,3

и поэтому, как было указано в § 2, он коллинеарен обоб щенному портрету ф класса Y — {уц} при пустом втором классе. Число векторов ytj обычно много больше, чем дли на обучающей выборки. Поэтому непосредственное по строение обобщенного портрета ф затруднительно. Вместо этого можно воспользоваться следующей итеративной про цедурой.

1. Берется произвольная пара векторов	х и, XJt. Обра
зуется класс Ух всего из одного вектора	ух ~ хи —

Строится обобщенный портрет фх этого класса (при пустом втором классе),

2. Допустим, что на <-м шаге построены класс векто

ров Yt и его	обобщенный портрет ф(. В			обучающей по
следовательности		находится вектор хім		такой, что
		СФо Ч/+х) =	min (ф(, хі),
и вектор Xj	такой, что
		(tn *Ѵг+і) =	max (^i’ *})■
Образуется вектор г/і+х			= хң+1 — 2X(+r
3. Если	(ф4,	г/(+1) < 1	— е ( с ^ >0 — параметр про