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

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

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

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

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

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

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

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

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

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

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

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

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

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

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