5.6. ПРОЦЕДУРЫ РЕЛАКСАЦИЙ

5.6.1. АЛГОРИТМ СПУСКА

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

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

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

так что основной алгоритм спуска представляется в следующем виде:

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

где

Данный алгоритм известен под названием правила релаксаций и имеет простую геометрическую интерпретацию. Величина

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

Если то произведение остается все же меньшим, чем b; если же то будет больше b. Данные условия носят название недорелаксация и перерелаксация соответственно. Обычно выбирается из интервала

5.6.2. ДОКАЗАТЕЛЬСТВО СХОДИМОСТИ

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

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

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

и

так что

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

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

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