§ 2. Алгоритм построения разделяющей гиперплоскости

Алгоритм ОП-1 предназначен для построения гиперплоскости, разделяющей два конечных множества векторов, либо для выяснения того факта, что безошибочное линейное разделение невозможно.

Данный алгоритм имеет две модификации. В одной из них он позволяет найти обобщенный портрет при заданном параметре ; во второй модификации алгоритм находит оптимальную разделяющую гиперплоскость (см. главу XIV). Алгоритм строит плоскость, решая двойственную задачу, как это было описано в предыдущей главе. Однако часто длина обучающей последовательности настолько велика, что обработка сразу всего материала обучения привела бы к задаче слишком высокой размерности. Поэтому обработка обучающей последовательности ведется итеративно. На каждой итерации из обучающей последовательности выделяется группа векторов, которую будем называть выделенной группой, строится разделяющая плоскость для этой группы путем решения двойственной задачи (либо устанавливается неразделимость). Затем из группы исключаются векторы, которые входят в разложение направляющего вектора гиперплоскости с нулевым весом, и добавляются векторы, неправильно опознаваемые построенной гиперплоскостью на оставшейся части обучающей последовательности. После этого снова обрабатывается выделенная группа. Так продолжается до тех пор пока либо после очередной итерации все векторы обучающей последовательности не будут опознаны правильно, либо на очередной итерации не будет установлена неразделимость выделенной группы.

Рис. 25. Блок-схема алгоритма ОП-1.

Блок ОП-1/1

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

Блок ОП-1/2

Этот блок ведает формированием выделенной группы векторов.

1. На первой итерации выделенная группа образуется из векторов первой группы, которая возникнет после разбиения материала обучения блоком ОП-1/1.

2. На очередной, -й, итерации, т. е. при очередном обращении к блоку ОП-1/2, блок просматривает векторы первых  групп, если число  не превосходит число групп , или весь материал обучения в противном случае. При этом к выделенной группе добавляются те векторы, которые неправильно опознаются с помощью решающего правила, построенного на предыдущей -й итерации, или опознаются правильно, но с недостаточным превышением порога.

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

а) в случае построения обобщенного портрета вектор заносится в выделенную группу, если

 и ,

или

 и ,

где  – обобщенный портрет, построенный на предыдущей итерации,  и  – заданные параметры, причем

,  ;

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

 и

или

 и ,

где  и  направляющий вектор и порог разделяющей плоскости, построенной на предыдущей итерации.

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

Блок ОП-1/3

Блок строит обобщенный портрет либо оптимальную решающую плоскость для выделенной системы векторов путем решения двойственной задачи. Подробнее обе модификации (ОП-1/3а и ОП-1/3б) описаны ниже. В результате работы блока либо устанавливается неразделимость векторов системы (в этом случае алгоритм прекращает работу, сообщая о неудаче), либо вычисляются направляющий вектор гиперплоскости  и его разложение

                     (15.6)

по векторам выделенной группы (а в случае оптимальной гиперплоскости определяется еще и константа ).

Блок ОП-1/4

Этот блок исключает из выделенной группы те векторы, которые входят в разложение (15.6) с нулевым весом и передает управление блоку ОП-1/2.

Перейдем к подробному описанию блока ОП-1/3 в двух модификациях.

Блок ОП-1/3а

Нахождение обобщенного портрета модифицированным методом сопряженных градиентов (рис. 26).

Рис. 26.

Целью работы этого блока является нахождение в положительном квадранте максимума функции

,

где

,

 – число векторов первого класса,  – число векторов второго класса в выделенной группе.

Каждому вектору  и  ставится в соответствие бинарная переменная  (соответственно ). Кроме того, номер текущего шага обозначен через .

В этом блоке:

1. Устанавливается , , .

2. Полагается для всех  и  ,  (восстановление размерности пространства).

3. .

4. Производится вычисление градиента функции  и квадрата его модуля в соответствующем координатном подпространстве по формулам

,

,

.

5. Проверяется условие: для всех  и

или  и ,

,                (15.7)

или  и ;

6. Если условия (15.7) выполнены и

,

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

.

7. Если условия (15.7) выполнены и

(максимум найден в подпространстве), осуществляется переход к п. 2 (для восстановления размерности).

8. Если условие (15.7) не выполнено, исполняется п. 9.

9. Если , то

,           ;

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

,

,

где

.

10. Находится вектор

.

11. Вычисляется пробная величина шага

.

12. Определяется истинная величина шага

,

где минимум берется лишь по тем  и , для которых  или .

13. Если минимум достигается при , то исполняется п. 14, если же минимум достигается при

          ,

то устанавливается   и  и далее исполняется п. 14.

14. Находятся новые значения коэффициентов  и :

                                                           ,

.

15. Находится новый вектор

.

16. Осуществляется проверка на неразделимость группы векторов. Для этого вычисляется значение функции

.

Если , осуществляется переход к п. 3, в противном случае принимается решение о неразделимости группы векторов и блок заканчивает работу.

Модификация ОП-1/3б

Эта модификация предназначена для отыскания оптимальной разделяющей гиперплоскости путем решения двойственной задачи модифицированным методом сопряженных градиентов (рис. 27).

Рис. 27.

От ОП-1/3а отличаются только первые пункты.

1. Устанавливается

, , .

2. Полагается для всех  и

; .

Кроме того, вводится бинарная переменная  и устанавливается

(указатель работы во всем пространстве или в гиперпространстве).

3. .

1. 

4.1. Находится градиент функции :

,

.

4.2. Если  исполняется 4.3, в противном случае 4.4.

4.3. а) Определяются функции от аргумента

где

,

и функция

.

б) Вычисляются числа

, .

в) Если все  и , то устанавливается

для всех , при которых . Осуществляется переход к 4.4.

г) Если не все , , то находится

,

где минимум берется лишь по тем  и , для которых  и .

д) Устанавливается

, если  и ,

, если  и .

Далее исполняется 4.4.

4.4. Вычисляется

.

4.5. Вычисляется условный градиент функции

,

.

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

.

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

,

.                (15.8)

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

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

.

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

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

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

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