§ 8. Алгоритм построения разделяющей гиперплоскости с оценкой ее качества методом скользящего контроля

Алгоритм ОП-8 предусматривает одновременно с построением обобщенного портрета оценку его качества методом скользящего контроля.

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

В результате работы алгоритма ОП-8 кроме разделяющей гиперплоскости будет найдена еще оценка.

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

В самом деле, согласно главе XIV, вектор , задающий направление разделяющей гиперплоскости, образуется линейной комбинацией части векторов обучающей последовательности. Эти векторы обучающей последовательности назывались крайними. Напомним, что среди векторов обучающей последовательности крайними векторами для построенной разделяющей гиперплоскости назывались те, на которых достигалось равенство

или

,

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

или

.

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

Таким образом, в нашей случае заранее известно, что при проведении скользящего контроля все не крайние векторы обучающей последовательности будут опознаны правильно и поэтому скользящий контроль следует проводить только на крайних векторах. Это обстоятельство значительно сокращает время проведения скользящего контроля (обычно число крайних векторов в несколько раз (5–7 раз) меньше числа всех векторов обучающей последовательности).

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

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

2. Затем из множества крайних векторов исключается первый крайний вектор (этот вектор исключается также и из обучающей последовательности). На место исключенного крайнего вектора  записывается ближайший к нему вектор  обучающей последовательности.

3. Строится новая разделяющая гиперплоскость, причем в качестве начальных условий выбирается вектор , полученный как линейная комбинация векторов ;  (здесь вектор  заменил вектор ) с весами ; . При таких начальных условиях поиск новой разделяющей гиперплоскости проводится значительно быстрее.

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

Алгоритм ОП-8 использует алгоритм ОП-1.