5.9.1. ПРОЦЕДУРА СПУСКА

Процедуры, рассмотренные до сих пор, различались в разных отношениях. При методе персептрона и процедуре релаксаций разделяющий вектор определялся в случае линейно разделяемых множеств, однако в случае неразделяемых множеств сходимости не наблюдалось. Процедуры нахождения решения по методу наименьших квадратов дают весовой вектор как в случае линейно разделяемых, так и в случае линейно неразделяемых выборок, однако нет гарантии, что указанный вектор будет разделяющим вектором в случае разделяемых множеств. Если вектор допуска Ь выбран произвольным образом, то можно сказать, что процедуры для решения по методу наименьших квадратов минимизируют выражение ЦУа— —Ь|!“. Тогда, если взятые выборки линейно разделяемы, существуют такие а и Ь, что выполняется следующее условие;

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

могут изменяться (при условии, что Ь>0), то минимальное значение Js равно О, а а, которое достигается при данном минимуме, является разделяющим вектором.

Для минимизации будем использовать модифицированную процедуру градиентного спуска. Градиент функции J^, взятый относительно а, записывается в виде

а градиент, взятый относительно Ь, задается в виде

При любой величине Ь можно всегда принять

получая тем самым Ѵ» ./^=0 и минимизируя по а за один шаг. Больших возможностей для изменения Ь, однако, не имеется, поскольку нужно придерживаться условия Ь>0, так что следует избегать процедуры спуска, которая приводит кЬ=0. Один из способов, препятствующий сходимости Ь к О, заключается в том, чтобы положить вначале Ь>0 и впоследствии не уменьшать никакую из его компонент. Этого можно достичь при сохранении отрицательного градиента, если вначале все положительные компоненты Ѵь./* взять равными 0. Таким образом, если через |ѵ| обозначить вектор, компоненты которого суть абсолютные величины компонент вектора V, то придем к рассмотрению такой процедуры спуска;

Используя соотношения (60) и (61) и несколько более конкретизируя, получим алгоритм Ко — Кашьяпа минимизации функции /Да, Ь):

где е* является вектором ошибки;

а tt — положительная составляющая вектора ошибки:  и

Поскольку весовой вектор полностью определяется вектором допуска bft, то это, по существу, и есть алгоритм для образования последовательности векторов допуска. Вектор Ьі, с которого начинается последовательность, положителен, и если р>0, то все последующие векторы будут положительны. Мы можем опасаться, что если ни одна из компонент вектора не положительна, так что изменениеbfe прекращается, то мы не получим решения. Однако, как мы увидим, в этом случае либо е^=0 и решение получено, либо eft<0 и можно доказать, что выборки линейно не разделяемы.