§ 11. Применение метода обобщенного портрета для нахождения оптимальной разделяющей гиперплоскости

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

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

Первый способ основан на последовательном построении обобщенных портретов при разных  и подборе , близкого к  (теорема 14.3).

При подборе  можно исходить непосредственно из критерия

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

Второй способ основан на следующем свойстве вектора . Рассмотрим всевозможные разности вида

 .

При этом вектор  обладает свойством

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

1. Берется произвольная пара векторов . Образуется класс  всего из одного вектора . Строится обобщенный портрет  этого класса (при пустом втором классе).

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

,

и вектор  такой, что

.

Образуется вектор .

3. Если  ( – параметр процедуры), то класс  пополняется вектором . Далее находится обобщенный портрет  образовавшегося класса  и процесс продолжается дальше.

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

.

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

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