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

358 і'Л . XV. АЛГОРИТМЫ МЕТОДА ОБОБЩЕННОГО ПОРТРЕТА

4.5. Вычисляется условный градиент функции W (a,ß)

«/ (t) = (<*; (*) + .P (*)) dt,

ßj (t) = (ßi « + ^ («)) 4

4.6. Вычисляется квадрат условного градиента

ga(0 = 2«?(0 + Zßf(0-

i І

5. Проверяются условия

I ßi (t) I < e.

6. Если условия (15.8) выполнены и q = 1, то услов­ ный максимум функции W (а, ß) при ограничениях (14.27) найден. Вектор

а Ь

принимается за направляющий вектор ф0 оптимальной гиперплоскости. Константа

с0 =p( t) .

7.Если условия (15.8) выполнены и q ~ 0, то услов­ ный максимум найден только в координатном подпростран­ стве. В этом случае осуществляется переход к п.2 (восста­ новление размерности).

8.Если условия (15.8) не выполнены, то устанавли­

вается

7 = 0

и исполняется п. 9.

Остальные пункты совпадают с модификацией ОП-1/За.

§ 3. АЛГОРИТМ, МИНИМИЗИРУЮЩИЙ ЧИСЛО ОШИБОК 359

§ 3. Алгоритм построения разделяющей гиперплоскости, минимизирующей число ошибочно классифицируемых векторов

В результате работы программ ОП-1 либо будет по­ строена разделяющая гиперплоскость, либо будет установ­ лено, что построить разделяющую гиперплоскость невоз­ можно. В последнем случае необходимо построить разде­ ляющую гиперплоскость, минимизирующую число не­ правильно классифицируемых векторов.

Такая задача принципиально может быть решена, од­ нако требует достаточно большого объема вычислений. В самом деле, если установлено, что а векторов первого класса и b векторов второго класса не могут быть разде­ лены гиперплоскостью, то возникает естественная идея исключить из обучающей последовательности минималь­ ное число векторов с тем, чтобы оставшиеся векторы могли быть разделены гиперплоскостью.

Найти минимальное число векторов, которые надо исключить, можно с помощью следующей процедуры.

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

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

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

скости необходимо, вообще говоря, С] раз использовать программу ОП-1.

Ясно, что, действуя согласно этой процедуре, в конце концов, можно будет найти гиперплоскость, минимизирую­ щую число ошибок на материале обучения.

360 ГЛ. XV. АЛГОРИТМЫ МЕТОДА ОБОБЩЕННОГО ПОРТРЕТА

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

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

Алгоритм ОП-2 использует следующий стандартный эвристический прием: из множества векторов обучающей последовательности исключается один элемент, «наиболее препятствующий разделению», затем, если разделение невозможно, из оставшегося множества исключается еще один элемент и т. д.

Специфика алгоритма заключается в определении эле­ мента, «наиболее препятствующего разделению множеств».

Вкачестве такого элемента определяется вектор х (или

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

вует максимальное значение а или (3.

Программа ОП-2 исключает из множества векторов вектор, «наиболее препятствующий разделению», делит оставшееся множество векторов и, если разделение все еще невозможно, исключает очередной вектор, делит осставшиеся и т. д.

Программа ОП-2 включает в себя как составную часть ОП-1.

§ 4. Алгоритм построения кусочно-линейной разделяющей поверхности

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

§ 4. ПОСТРОЕНИЕ КУСОЧНО-ЛИНЕЙНОЙ ПОВЕРХНОСТИ 361

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

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

Поэтому при решении такой задачи также применяют­ ся эвристические приемы. В частности, используется тот же стандартный прием, что и в алгоритме ОП-2. Сначала строится одна, в некотором смысле «наилучшая», разделяющая гиперплоскость. Затем к ней достраивается еще одна «наилучшая» гиперплоскость и т. д.

Алгоритм ОП-3 основан на том, что в качестве наилуч­ шей гиперплоскости выбирается такая ориентированная гиперплоскость, которая делит обучающую последователь­ ность с минимальным числом ошибок (гиперплоскость строится с помощью алгоритма ОП-2). Затем эта гипер­ плоскость фиксируется и к ней достраивается еще одна (также с помощью алгоритма ОП-2).

Достраивается «наилучшая» разделяющая гиперплос­ кость по следующему правилу.

Пусть к моменту времени т построена (с помощью ОП-2) разделяющая гиперплоскость, которая на части векторов обучающей последовательности делает ошибки. Образуем с помощью построенной разделяющей гипер­ плоскости и векторов обучающей последовательности но­ вый массив векторов размерности т + 2 по следующему правилу.

Каждому вектору х обучающей последовательности становится в соответствие вектор % в пространстве раз­ мерности т + 2, у которого первые т координат совпа­ дают с координатами вектора х, а т - \ - 1 п т - { - 2 коорди­ наты суть соответственно 1,0, если вектор х лежит по одну сторону от построенной гиперплоскости (т. е. (х, фД с), или 0,1, если вектор х лежит по другую от нее сторону

((*> Фі) < с).

Полученное множество векторов {х} проиндексируем по правилу: вектор х относится к первому классу, если соответствующий ему вектор х принадлежал первому