§ 3. Конечно-сходящиеся рекуррентные процедуры

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

.

По-прежнему рассматривается детерминистская постановка задачи; геометрически это значит, что множества векторов  и , которые должны быть отнесены к первому и второму классам соответственно, разделяются гиперплоскостью

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

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

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

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

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

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

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

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