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

Скачать файл
Заказать решение

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

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

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

Добавлен: 11.04.2024

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

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

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

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

вует нормально ориентированная гиперплоскость, кото­ рая отделяет либо множество X от множества X , либо множество X от X.

Рассмотрим систему неравенств

(хі: of) > 1 (г = 1, . . ., а),

(14.3)

(Xj, я|>) < к (і = 1, . . ., b).

Будем считать величину к допустимой, если система (14.3) имеет хотя бы одно решение. Очевидно, что если к 0 — до­ пустимое значение параметра, то и любое значение к^> кд также допустимо.

Каждому значению т|), удовлетворяющему (14.3), по­ ставим в соответствие гиперплоскость

(х, Ф) = .

Очевидно, что при к < 1 эта гиперплоскость нормально ориентирована и отделяет I от I . Обратно, если множе­ ства X и X разделимы нормально ориентированной гипер­ плоскостью, то существует допустимое значение /с < 1.

Действительно, пусть <р — направляющий вектор этой гиперплоскости; при этом сг (ф) > 0 и С] (ф) > сг (ф). Тогда

 

Ф

и k =

ъ (Ф)

 

сі(ф)

 

а (ф )

удовлетворяют

(14.3), причем к

1.

Определение.

Назовем минимальный по модулю вектор

о|), удовлетворяющий неравенствам (14.3) при заданном допустимом к, обобщенном портретом множества X от­ носительно X для данного значения к.

Поясним это понятие.

Рассмотрим случай, когда класс X пуст. Тогда ми­ нимальный по модулю вектор, удовлетворяющий нера­ венствам

(хі, яр) > 1,

(14.4)

коллинеарен единичному вектору ф, доставляющему

max min (ф, ж4) =

max сх (ф)

*)

| ф | = 1 г

| ф | = 1

 

*) Действительно, поставим в соответствие всякому единично-

Ф

му вектору ф , д л я которого еД ф ) > 0 , вектор ф — сі (ф ')~ ‘ Очевидно,

§ 2. ОДНОПАРАМЕТРИЧЕСКОЕ СЕМЕЙСТВО

297

Иными словами, вектор ф задает среднее в минимакс­ ном смысле направление векторов класса X (рис. 24). Это обстоятельство оправдывает название «обобщенный портрет».

Приведенное определение обобщенного портрета явля­ ется естественным обобщением этого понятия на случай, когда в обучающей выборке представле­ ны оба класса.

Теорема

14.2. При

каждом допусти­

 

мом значении к обобщенный портрет су­

 

ществует и единствен.

 

Поскольку

 

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

 

значение

к

допустимо,

найдется

вектор

 

ф*, удовлетворяющий (14.3). Рассмотрим

 

множество

 

векторов ф,

удовлетворяющих

 

наряду с

(14.3)

условию

|ф | ^

|ф *|.

 

Это множество не пусто,

ограничено, зам-

 

кнууо и выпукло. Поэтому сильно выпук­

Рис. 24.

лая функция (ф, ф)

имеет на нем единст­

венный минимум ф0.

Очевидно также, что

 

вне шара

| ф |

| ф* |

все

векторы имеют модуль боль­

ше ф0. Отсюда следует доказываемое утверждение.

Таким образом, обобщенные портреты,

имеющие раз­

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

При к < 1 ему соответствует семейство разделяющих

гиперплоскостей

 

(*, Ф (*)) = -Ц р ' •

(14.5)

что получившийся вектор удовлетворяет неравенствам

(14.4).

Обратно, всякому вектору ф, удовлетворяющему (14.4) и такому, что по крайней мере одно из неравенств переходит в равенство, по­

ставим в соответствие единичный вектор <р = г - г т . При этом с і (ср) =

1

~ ПФТ • ■^етРудн0 Убедиться, что эти соответствия взаимно обратны.

Далее, поскольку минимум (ф, ф) при ограничениях (14.4) достигается на границе ограничений, то для обобщенного портрета

по крайней мере одно из неравенств действительно переходит в ра-

1

венство. Поэтому максимуму сд (ф) соответствует максимум y-^-j.

т. е, минимум (ф, ф).

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

Теорема 14.3. Если оптимальная разделяющая гипер­ плоскость нормально ориентирована, то она принадлежит однопараметрическому семейству (14.5).

Д о к а з а т е л ь с т в о . Пусть ф 0Пт — направляю­ щий вектор оптимальной разделяющей гиперплоскости и при этом сх (фопт) > 0. Положим

ко — С2

(Фопт)

< 1 ,

Фопт

(14.6)

Сі

(Фопт)

 

С1 (Фопт)

 

и покажем, что вектор і|э* совпадает с обобщенным порт­

ретом

(fco)-

 

убедимся, что пара ty*,

к 0 удовлетворя­

Прежде всего,

 

ет (14.3). Действительно,

 

 

 

 

 

 

 

(*і, Г )

(Фопт)

 

 

 

 

(і

— 1, ... , а),

 

 

 

1

 

<

1

(с

 

 

 

 

=

Сі

&>'

 

 

 

 

 

 

 

 

 

 

 

 

Сі

 

=

fco

(7 = 1,---, Ъ).

(фопт)

 

 

фопт)

 

ГД

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Далее, если if)*

 

яр (fc0), то в силу единственности обоб­

щенного

портрета

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l $ *

I

> 1 4 ?

(fco)

I-

 

( 1 4 .7 )

Рассмотрим вектор ф0 =

j фД^°)Г '

 

 

слеДУет,

что

 

 

 

 

С і

 

^

I ф ( к о) I

’

 

 

 

и, значит,

 

 

 

 

 

 

 

 

 

 

 

 

ут / ч ^

 

1 — к о

 

 

Сі (Фопт)

С2 (Фопт)

__

 

^ (Фопт)

 

1А(фо ) ^

|ф (* о )|

“

 

СІ (Фопт) I Ф (*о) I

_

сі(ф ОПІ)|ф (/с о )|

•

Далее, в силу (14.7)

п (фо) >

П (Фопт)

Сі (Фопт) I V I

Окончательно, поскольку | г|5* | = —----- г-, получаем П(ф0) >

С і ( Ф О П Т '

> П (Фопт)) что противоречит определению оптимальной разделяющей гиперплоскости. Итак, ij^* = -ф (fc0). Теперь

§ 3. НЕКОТОРЫ Е СВОЙСТВА ОБОБЩЕННОГО ПОРТРЕТА 299

из определения

Ä и Tfj* (14.6)

немедленно

следует,

что

гиперплоскости

 

 

 

 

 

(^(&0),ж) = . Ц р !

 

 

и

 

 

 

 

 

Сі (Ч’опт) “f' Сг (Ф<Шт)

 

 

(фо пт 5 X ) —

£

 

 

совпадают. Теорема доказана.

 

следует,

что

Замечание. Из

доказательства теоремы

п (*»'> = r a w -

§ 3. Некоторые свойства обобщенного портрета

Нахождение обобщенного портрета, очевидно, сво­ дится к задаче квадратичного программирования: найти минимум функции (ф, ф) при линейных ограничениях

(14.3).

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

Для дальнейшего нам понадобится следующая теорема. Теорема 14.4 (Куна — Таккера). Пустъ заданы диф­ ференцируемая выпуклая функция F (х) и линейные функ­

ции ft (х); і — 1, . .., I.

Пустъ х 0

доставляет минимум

F (х) при ограничениях

 

 

 

 

 

 

/ , ( * ) > 0

(г = 1,2,

. . . , I).

 

(14.8)

Тогда существуют такие числа Яі

> 0,

удовлетворяю­

щие условиям

 

 

 

 

 

 

h fl (») =

о

(г = 1,

2,

. . .,

I),

(14.9)

что справедливо равенство

I

 

 

 

 

 

 

 

 

 

(14.10)

Ѵ ^ Ы =

2 VF/г Ы

 

 

 

г—I

 

 

 

 

(V — знак оператора градиента).

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