6.3.2. Алгоритм корректирующих приращений

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

где, как и раньше,

Как указывалось выше, минимум функции критерия по соответствует правильной классификации всех образов.

Следует определить частную производную функции критерия по вектору весов

где функция равна +1 или —1 в зависимости от знака ее аргумента.

Положив и подставив эту функцию в общее выражение алгоритма (6.3.8), получим

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

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

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

где Эта ситуация представляет случай 3 разделения нескольких классов, рассмотренный в § 2.2.

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

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

При разделении двух классов вектор весов разделяющей поверхности можно определить непосредственно. В этом случае (6.3.11) принимает вид

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

так как произведение есть некая аппроксимация плотности распределения . Алгоритм, представленный уравнением (6.3.14), легко выразить в форме (6.3.12).

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

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

в форме . Операция пополнения образов приводит к классам . Отметим, что ни в одном из классов образы не умножались на —1, как это делалось в гл. 5 для случая разделения двух классов.

Рис. 6.4. Разделяющая граница, найденная с помощью алгоритма корректирующих приращений.

Положив и воспользовавшись алгоритмом корректирующих приращений, получим

На следующем шаге предъявляется образ , так как образ также принадлежит классу имеем Следовательно,

На следующем шаге так что

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

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

Эта разделяющая граница показана на рис. 6.4.