Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 199
Скачиваний: 4
300 ГЛ. XIV . ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ
И обратно, если для некоторой точки х 0 выполняются условия (14.8) и можно найти числа А,г!>0, удовлетворяю щие условиям (14.9) и (14.10), то в точке х 0 достигается условный минимум F (X) при ограничениях (14.8).
Доказательство этой теоремы приведено в приложении. Введем еще одно определение.
Определение. Будем говоритъ, что вектор x t (xf) явля ется крайним вектором множества X (X) для вектора і|), удовлетворяющего (14.3) при константе к, если вы полняется равенство
(Хі, і|?) = 1
((Xj, i|)) = к) .
Справедлива следующая важная для дальнейшего теорема.
Теорема 14.5. Обобщенный портрет может бытъ представлен в виде линейной комбинации крайних векто ров. Причем крайние векторы множества X входят в это разложение вектора с неотрицательными коэффициента ми, а крайние векторы множества X — с неположитель ными коэффициентами.
Иначе говоря, минимальный по модулю вектор "ф, удов летворяющий (14.3) может бытъ представлен как
аЬ
|
|
Ч5= |
2 |
« л — 2 |
РА'- |
|
|
|
|
|
|
|
i ~ |
l |
j = l |
|
|
|
|
|
|
а * > 0 |
|
(г = 1 , 2 , . . ., а), |
|
|
|||
|
|
ßi > 0 |
' |
(/ — 1 , 2 , . . . , |
Ъ), |
|
(14Л1) |
||
причем |
|
|
|
|
|
|
|
|
|
|
«г {(х і> Ч?) — 1) = |
0(г |
= 1, 2, . .., а), |
(14 12) |
|||||
|
ßj (&—(xJt 40) = |
0(/ |
=1 , 2 ,.. ., Ь). |
|
|
||||
Д о к а з а т е л ь с т в о . |
Для |
доказательства |
тео |
||||||
ремы |
14.5 |
воспользуемся |
теоремой 14.4, где |
положим |
|||||
ft |
|
F (40 = |
(4?, 4?). |
|
1, 2, . . ., a), |
||||
(4?) = ((*i. 4?) — 1) > 0 |
(i = |
||||||||
f i |
(4?) = |
(ko — (Xj, |
4?)) |
> 0 |
(/ = |
1 , 2 , . . ., |
b). |
|
|
§ 3. НЕКОТОРЫ Е СВОЙСТВА ОБОБЩ ЕННОГО ПОРТРЕТА 301
Согласно утверждению теоремы 14.4 существуют такие
неотрицательные І,- (1 < |
і < |
а) и |
(1 < / |
^ Ъ), что |
М ь ’Ю — 1) = 0 (і = 1, 2, . . |
а), |
|||
Xj (к — (Xj, ф)) |
= 0 |
(/ = |
1, 2, . . |
b) |
И |
|
|
|
|
а |
|
|
Ь |
|
grad (ф, ф) = 2 |
grad ({х{, ф) — 1) + 2 h grad (к — (ж,-, ф)). |
І= 1 |
j = 1 |
Вычисляя градиент, имеем
аЬ
2т|) = 2 M i — 2 Mi-
i —1 |
; = i |
|
Полагая |
|
|
получаем |
|
b |
a |
|
|
ф = 2 |
ал — 2 |
|
i = |
l |
j ~ l |
|
а* > |
0, |
|
ß, > |
0; |
«iMplO — l] = o,
ß;- [к — (ж/ф)] = 0.
Теорема доказана.
Справедлива обратная теорема.
Теорема 14.6. Всякий вектор ф, удовлетворяющий (14.3) и допускающий разложение вида (14.11) по своим крайним векторам, совпадает с обобщенным портретом.
Д о к а з а т е л ь с т в о немедленно следует из об ратного утверждения теоремы 14.4 (Куна — Танкера) и единственности обобщенного портрета, если функции F (X) и / г (х) интерпретировать так же, как при доказатель стве предыдущей теоремы.
Замечание. В теореме 14.2 была доказана един ственность обобщенного портрета. Однако обобщенный портрет, вообще говоря, не единственным образом разла гается по своим крайним векторам- в виде (14.11).
302 ГЛ. XIV . ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ
§4. Двойственная задача
Вэтом параграфе будет рассмотрена частная задача квадратичного программирования, решение которой эк вивалентно построению обобщенного портрета.
Введем пространство параметров а, ß и рассмотрим в нем функцию
аЬ
w > ,ß ) = S |
ß ; - 4-О М О ’ |
i=l |
3—1 |
где вектор ф есть |
|
а |
Ь |
ф = 2 щщ — 2 ßj% - |
|
І= 1 |
3=1 |
Будем искать максимум этой функции в положитель |
|
ном квадранте а г > 0, ß^ > |
0. |
Для построения разделяющих гиперплоскостей су |
|
щественным оказывается то, |
что точка максимума а 0, ß0 |
функции W (а, ß) в положительном квадранте определяет |
|
обобщенный портрет для заданного параметра к, а значе ние максимума W (сс0, ß0) определяет расстояние между проекциями векторов первого и второго классов на нап равление обобщенного портрета.
Итак, рассмотрим точку максимума а, ß функции
W(а, ß) в положительном квадранте.
Необходимыми и достаточными условиями максимума
функции W (а, ß) в точке а? > 0, ß? > 0 являются ус ловия:
dW(a°, ß°) |
j |
0’ |
если af^>0, |
||
даі |
|
0, если а? = 0, |
|||
dW (я», ß?) |
_ j |
0, |
если |
ß? > |
0, |
ößj |
i<^ 0 , |
если |
ß ° = |
0 . |
|
Выпишем эти условия, обозначив
ф° = 2 « ? x t — S ß ?
