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

штраф равен единице).

Используя эту функцию потерь, можно подменить задачу о минимизации функционала Р (Я) задачей о ми­ нимизации другого функционала

Рі ( 4 = $ф (ю. У’ Ь)dp К »

на том основании, что точка минимума нового фукнционала доставляет минимум исходному функционалу.

означает, что если вектор у правильно классифицируется построенной к этому времени разделяющей гиперплос­ костью, то вектор коэффициентов Я (і — 1) не меняется. Если же совершается ошибка одного рода (вектор при­ надлежит первому классу, а относится правилом ко вто­ рому), то к вектору коэффициентов Я (г — 1) прибавляется вектор V (і) у{. Если же совершается ошибка другого рода

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

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

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

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

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

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

86ГЛ. ІУ. РЕКУРРЕНТНЫЕ АЛГОРИТМЫ ОБУЧЕНИЯ

т(т — размерность спрямляющего пространства), а чис­ ло шагов, необходимое для выбора нужного правила, про-

порционально величине 1 .

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

§ 6. Метод потенциальных функций

В 60-х годах М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр предложили для решения задач обучения распознаванию образов использовать разработанный ими метод потенциальных функций [1]. Этот метод также реа­ лизует идею рекуррентной процедуры минимизации сред­ него риска. Применительно к задаче обучения распо­ знаванию образов суть метода заключается в следующем. На пространстве входных векторов х задается функция, которая называется «потенциалом». Потенциал определя­ ет близость двух точек, х, xQ, и обычно задается как функ­ ция расстояния между точками. Потенциальная функция, как правило, такова, что она монотонно уменьшается с увеличением расстояния. Примерами потенциальной функции могут служить

К (х, Хо) = I г2а > К (•*-> З'о) — е г а,

/т

2 (яо — х\)2—расстояние от точки х0 = (xj,...

С помощью таких функций на пространстве X образует­ ся потенциальное поле. Считается, что вектор х относится к первому классу, если потенциал поля в точке х поло­ жителен; в противном случае вектор х относится ко вто­ рому классу. Процесс обучения, таким образом, заклю­

чается в построении с помощью обучающей последова­ тельности потенциального поля.

Геометрическая интерпретация метода построения по­ тенциального поля очень наглядна (рис. 9). Пусть для обучения машине предъявляется обучающая последова­ тельность . . ., соі%і- При появлении первого элемен­ та обучающей последовательности хх «выпускается» по­ тенциал с центром в точке х±. Знак потенциала определя­ ется тем, к какому классу относится предъявленный

пример: если к первому, то знак у потенциала положи­ тельный, если ко второму, то отрицательный. Теперь на пространстве X задан некоторый потенциал. Для второго элемента обучающей последовательности может быть вы­ числена величина потенциала К (х2, хх). Если величина потенциала положительная, а элемент обучающей по­ следовательности относится к первому классу, то потен­ циальное поле на пространстве X не меняется; если же величина потенциала в точке х2 положительная, а вектор х2 должен быть отнесен ко второму классу, то из точки х2 «выпускается» новый потенциал, но с отрицательным знаком. Теперь на пространстве X действует новый сум­ марный потенциал

Ф (х) = К (ж, хх) — К (ж, х2).

Аналогично, если при классификации элемента обучающей последовательности с помощью суммарного

88 ГЛ. IV. РЕКУРРЕНТНЫЕ АЛГОРИТМЫ ОБУЧЕНИЯ

потенциала совершается ошибка, потенциал меняется так, чтобы по возможности выправить ошибку.

Таким образом, результатом обучения в методе по­ тенциальных функций является построение на простран­ стве X потенциального поля

ф (*) = 2І ' ( - 1 ) 1""1* (?.*»)

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

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

Оказывается, что для всякого вида потенциала суще­ ствует система функций (х), . . . cpk (х), . . . (вообще говоря, бесконечная!) такая, что все возможные разделяю­ щие поверхности, которые могут быть получены с помощью метода потенциальных функций, могут быть получены с помощью персептрона Розенблатта, где соответствующее спрямляющее пространство задается преобразованиями Фі ( « ) , . . . , <рт (ж), . . .. С другой стороны, для каждого персептрона легко находится соответствующая потен­ циальная функция.

Таким образом, метод потенциальных функций близок к персептронным методам Розенблатта. Для метода по­ тенциальных функций возможны те же модификации, что и для персептрона Розенблатта.