§ 2. Детерминистская и стохастическая постановки задачи обучения распознаванию образов

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

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

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

.

Предположим, что существует точное решение задачи распознавания, т. е. существует такое , что , и, кроме того, для всех векторов  первого класса справедливо

,

а для векторов второго класса

.

Построим новый функционал, например, со следующей функцией потерь:

                 (4.3)

График этой функции при фиксированных  и  приведен на рис. 7.

Рис. 7.

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

.

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

,

то штраф численно равен ; если же  должен быть отнесен ко второму классу, а

,

то величина штрафа численно равна  (сравним с функцией потерь персептрона, где при любой ошибке штраф равен единице).

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

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

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

Соответствующая рекуррентная процедура

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

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

Конечно,  не единственный функционал, которым можно подменить функционал . Можно рассмотреть, например, функционал, который задается такой функцией потерь:

                      (4.4)

График этой функции потерь для фиксированных , приведен на рис. 8.

Рис. 8.

Для такого функционала определяется рекуррентная процедура

,

в которой вектор-функция  имеет вид

Такой алгоритм (при условии, что  и ) предложил в свое время американский ученый Уидроу для настройки весов сконструированных им пороговых элементов (адалинов).

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

Исторически, однако, алгоритмы обучения распознаванию образов были получены не так. Авторы каждого из алгоритмов находили законы поиска разделяющей гиперплоскости, исходя из различных соображений. Поэтому сразу же после сообщений о персептроне Розенблатта появился целый ряд алгоритмов, обеспечивающих выбор нужной гиперплоскости. Только в середине 60-х годов Я. 3. Цыпкин заметил, что все эти алгоритмы могут быть получены по одной и той же схеме и различаются между собой так как различаются функционалы, экстремум которых достигается на одной и той же решающей функции.