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

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

Алгоритм ОП-Ю реализует такую последовательность операций:

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

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

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

4)с помощью найденного правила классифицируется вектор.

Алгоритм ОП-Ю включает в себя как составную часть алгоритм ОП-9.

§ 10. О работе с алгоритмами

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

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

малыше кусочно-линейные разделяющие поверхности, используя оценку «скользящий контроль».

Какой же алгоритм выбрать для решения конкретной задачи? Выбор того или иного алгоритма зависит от раз­ ных причин. Если заранее известен весь материал экзаме­ национной последовательности и имеются достаточно мощ­ ные вычислительные средства, то, вероятно, разумней всего использовать алгоритм ОП-Ю. Этот алгоритм строит экстремальные кусочно-линейные решающие прави­ ла, пытаясь полностью учесть особенности данной кон­ кретной задачи. При этом теоретически не исключена возможность, что рекомендация, полученная с помощью ОП-Ю, полностью совпадет с рекомендацией, получен­ ной с помощью ОП-1.

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

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

Как и всякие алгоритмы, система алгоритмов ОП имеет свои константы, которые необходимо задать при использовании той или иной программы. Величины этих констант следует задавать, исходя из класса вычисли­ тельных машин.

Г л а в а XVI

МЕ Т О Д С О П Р Я Ж Е Н Н Ы Х

НА П Р А В Л Е Н И Й

§1. Идея метода

Рассмотрим задачу о нахождении максимума квадра­ тичной функции

максимум, минуя решение системы линейных уравнений или получение обратной матрицы. Напротив, эти алгорит­ мы могут быть использованы для решения систем урав­ нений.

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

Пусть х 0 — произвольная точка пространства Е п. Обо­

дящая через ж0 в направлении gu т. е. иными словами, множество векторов вида х0 + Kg (— оо <; + оо).

374 ГЛ. XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

Найдем точку хъ в которой достигается условный мак­ симум функции F (х) на прямой Е ѵ Продолжим это по­ строение по индукции. Пусть уже построено /с-мерное гиперпространство E k и в нем найдена точка х к, в которой функция F (X) достигает условного максимума.

Обозначим gk+1 = Ъ —■A x k градиент функции F (х)

По индукции легко показывается, что гиперпростран­ ство E k может рассматриваться как множество векторов вида

ортогонален гиперпространству. Применительно к наше­ му построению отсюда следует, что gk+1 ортогонален вся­ кому вектору вида х — у, где х жу принадлежат E k, т. е.

Отсюда следует, что если gh+x ф 0, то вектор gk+1 невыра­ зим линейно через gx, . . ., gh и поэтому пространство E k+1 имеет размерность на 1 большую, чем E h.

Таким образом, размерность пространства Е к последо­ вательно нарастает с ростом к до тех пор, пока gh+x не обратится в нуль. Но последнее означает, что в точке x h достигнут уже абсолютный максимум F (х). Действитель­ но, поскольку F (X) — выпуклая гладкая функция, то обращение в нуль ее градиента является необходимым и достаточным условием максимума.

После обращения в нуль gh+x процесс зацикливается,

ваясь каждый раз на 1, на п-м шаге достигнет размерно­ сти всего пространства Е п, т. е. Е к совпадает с Е п, и тем самым условный максимум на Е к, естественно, совпадет

с абсолютным.

Рассмотренный процесс, конечно, не является удоб­ ным алгоритмом, для нахождения максимума, так как формально на каждом шаге требуется находить условный максимум F (х) в пространствах последовательно нара­ стающей размерности вплоть до полной размерности всего пространства. Однако оказывается, что в действительно­ сти можно искать условный максимум на каждом шаге в гиперпространстве размерности 2, т. е. на обыкновенных двумерных гиперплоскостях, или даже в гиперпростран­ стве размерности 1, т. е. на прямой.

3.Для обоснования этого положения установим сле

376 ГЛ. XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЯ

В самом деле, процесс продолжается лишь до тех пор, пока gh не обратится в нуль. Поэтому достаточно показать

{Уи Ayj) = (г/г, A (xj — х3ф).

После очевидного преобразования получим

(Уі, Ayj) = (Уі , (Axj — Ъ)) — (Уі, (Axj-j — b)),

но для любого к

Sh+l ^ AXfc,

поэтому

(Уі, Ayj) = (Уі, gj) — (Уі, gj+1).

Далее, вектор yt = Xi — жг_х есть разность двух векторов из Е і, и так как при г < /' Е { а Е ^ г, можно применить соотношение (16.2)

{Уи gj) = (fa - Xi-i), gj) = О

и

Окончательно,

(Уi, Ayj) = 0 при i Ф j.