5.7.  ПОВЕДЕНИЕ ПРОЦЕДУР В СЛУЧАЕ НЕРАЗДЕЛЯЕМЫХ МНОЖЕСТВ

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

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

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

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

Был предложен и изучен на практике ряд подобных эвристических модификаций для правил коррекции ошибок. Цель этих модификаций состоит в получении приемлемых характеристик для задач с неразделяемыми множествами при сохранении возможности определения разделяющего вектора для задач с разделяемыми множествами. В качестве общего подхода может быть предложено использование переменного приращения pk, которое стремится к нулю при k-+<x>. Скорость, с которой pft приближается к нулю, является весьма важным фактором. Если скорость слишком мала, результаты будут оставаться зависящими от тех выборок, которые делают множество неразделяемым. Если скорость слишком велика, то вектор веса может сходиться слишком быстро, и процесс закончится до того, как будут достигнуты оптимальные результаты. Один из способов выбора pk состоит в представлении его в виде функции нового показателя качества, убывающей по мере улучшения данного показателя. Другой путь выбора pft — это задание его в виде Pk—Pilk. Когда мы будем изучать методы стохастической аппроксимации, то увидим, что последний способ выбора pft представляет собой теоретическое решение аналогичной задачи. Однако прежде, чем обратиться к данной теме, рассмотрим подход, при котором жертвуют {возможностью получения разделяющего вектора, с целью достижения нужного компромисса между обеими задачами — как с разделяемыми, так и с неразделяемыми множествами.