4.11. Алгоритм построения оптимальной разделяющей гиперплоскости

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

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

Рассмотрим итерационный алгоритм Б. Н. Козинца минимизации перцептронной функции критерия для случая двух классов, который находит оптимальную разделяющую гиперплоскость с направляющим вектором си смещениемс₀, либо устанавливает, что выпуклые оболочки разделяемых множеств пересекаются. Здесь, как было определено ранее, оптимальной называется гиперплоскость, наиболее удаленная от выпуклых оболочек разделяемых множеств.

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

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

,

проходящая ортогонально через середину вектора . Если, где- достаточно малая наперед заданная величина, то считается, что разделяющая гиперплоскость не существует.

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

к множествуи

к множеству(рис. 4.9).

Рис. 4.9. Оптимальная разделяющая гиперплоскость.

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

,

где

.

Обозначим и получим

и.

Если , то, и пересчитывается точка. Если после очередного просмотра множествавекторыине изменились, то они принимаются за окончательныеи.

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

На рис. 4.10 рассмотрены три случая предъявления объекта из первого класса. Для каждого из них приведены значения соответствующих параметров алгоритма:

1. ;

2. ;

3. .

Рис. 4.10. Алгоритм Б.Н. Козинца построения

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