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

i 7. ЭКСТРЕМАЛЬНАЯ КУСОЧНО -ЛИНЕЙНАЯ ПО ВЕРХНОСТЬ 367

а в качестве начальных условий взять соответствующие значения ах, . . ., а а; ßl5 . . ßb.

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

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

Алгоритм ОП-7 подробно описан в § 11 главы VI. Идея алгоритма состоит в том, что каждый раз для клас­ сификации вектора х строится свое экстремальное решающее правило. Для этого с помощью метрики р (х, у) упорядочиваются элементы обучающей последовательно­ сти по близости к вектору х.

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

где d определяется (15.9). Естественно считать ту гипер­ плоскость наилучшей, для которой величина V (d, I) минимальна.

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

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

2)выбирается экстремальный объем выборки и стро­ ится соответствующая разделяющая гиперплоскость.

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

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

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

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

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

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

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

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

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

(жг,ф) = 1

или

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

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

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

§ 9. Алгоритмы построения экстремальных разделяющих гиперповерхностей с помощью процедуры

скользящий контроль

Алгоритм ОП-9 предназначен для построения гипер­ плоскости в экстремальном подпространстве признаков, т. е. преследует те же цели, что и алгоритм ОП-6. Разница заключается в том, что при поиске экстремального решаю­ щего правила в алгоритме ОП-6 использовалась верхняя оценка качества решающего правила в соответствующих подпространствах, в то время как в алгоритме ОП-9 оцен­ ка качества решающего правила проводится методом скользящего контроля.

Схема алгоритма ОП-9, таким образом, аналогична схеме алгоритма ОП-6. В исходном бинарном пространст­ ве методом перебора ищется такое «объединение» соседних градаций параметра, при котором «качество» полученного решающего правила наилучшее. Оценка качества, как уже указывалось, проводится методом скользящего конт­ роля (а не по формуле (15.9), как в алгоритме ОП-6). Алгоритмически это осуществляется следующим образом:

1) объединяются соседние градации параметра (пере­ кодируются аналогично ОП-6 векторы обучающей после­ довательности) ;

4)выбирается такое объединение градаций, при кото­ ром качество получаемой гиперплоскости наивысшее;

5)процесс объединения градаций продолжается до тех пор, пока любое объединение не приведет к ухудшению качества получаемой разделяющей гиперплоскости (при этом, если в ходе объединения градаций какой-либо пара­