5.9.4. НЕКОТОРЫЕ СВЯЗАННЫЕ ПРОЦЕДУРЫ

Если записать равенство = {Y*Y)~^Y* и использовать соотношение y^eh=0, то алгоритм Хо — Кашьяпа можно представить в виде

где, как обычно,

Данный алгоритм отличается от алгоритмов персептрона и релаксаций для решения линейных неравенств по крайней мере тремя свойствами: 1) он изменяет как весовой вектор а, так и вектор допуска Ь, 2) он явно обнаруживает наличие неразделяемости, однако 3) требует псевдообраш,ения Y. Даже при однократном проведении указанного вычисления необходимо затратить некоторое время и применить специальную обработку, если матрица У'У вырождена. Другой алгоритм, представляющий интерес, имеет сходство с (69), но исключает необходимость вычисления yt. Он записывается следующим образом:

где R является произвольно выбранной постоянной положительно определенной матрицей размера dxd. Покажем, что при правильном выборе р данный алгоритм также будет давать вектор решения за конечное число шагов, при условии что решение существует. Более того, если решение не существует, вектор УМс/іІ либо обращается в нуль, указывая на неразделяемость, либо сходится к нулю.

Доказательство проводится весьма непосредственно. В случае, когда выборки либо линейно разделяемы, либо линейно неразделяемы, соотношения (70) и (71) показывают, что

Таким образом,  и

где

Очевидно, что если р положительно, но достаточно мало, матрица А будет приблизительно равна 2pR и, следовательно, будет положительно определенной. Таким образом, если получим

Здесь следует провести различие между случаями разделяемых и неразделяемых множеств. При наличии разделяемого множества существуют векторы а и Ь>0, удовлетворяющие выражению Уа=Ь. Таким образом, если lefe|=?^, то справедливо соотношение

так что вектор У‘|ел| не может быть нулевым, если не равно нулю. Таким образом, последовательность Цвіір, llea|l^ . . . является монотонно убывающей и должна сходиться к некоторому предельному значению Однако в условиях рассматриваемой сходимости вектор У‘ ICftl должен сходиться к нулю, откуда вытекает, что |е^ I и, следовательно, также должен сходиться к иулю. Поскольку вй начинается с положительного значения и никогда не убывает, отсюда следует, что должен сходиться к разделяющему вектору. Более того, при использовании вышеприведенного утверждения решение фактически получается после конечного числа шагов.

В случае неразделяемых множеств вектор может либо быть ненулевым, либо не сходиться к нулю. Может оказаться, что на некотором шаге будет У*|е^|=0; это доказывает наличие неразделяемости множеств. Однако возможна и другая ситуация, при которой коррекции никогда не прекращаются. В данном случае из этого опять следует, что последовательность ||еіЦ% ЦеаІР, ... должна сходиться к предельному значению ||е|рт^ и что вектор У^Не^Ц должен сходиться к нулю. Таким образом, опять получаем очевидность неразделяемости в случае неразделяемых множеств.

Заканчивая разбор данной темы, коротко рассмотрим вопрос выбора р и і?. Простейшим вариантом выбора R является единичная матрица, в случае которой Л=2р/ — р^У^У. Данная матрица будет положительно определенной, что гарантирует условие сходимости, если 0<р<2Д„ах. где ^тах является наи^льшим собственным значением матрицы У‘У. Поскольку след матрицы У‘У представляется как суммой собственных значений матрицы У*У, так и суммой квадратов элементов матрицы У, то при выборе величины р может быть использована пессимистическая граница, а именно <2||у,.|Р.

Более интересный подход состоит в выборе такого значения р на каждом шаге, которое минимизирует выражение ,||ей||^—||е/і+іІ1*.

Из соотношений (72) и (73) получаем

Дифференцируя по р, получаем оптимальную величину р^, выражаемую отношением

которое при /? = / упрощается до выражения

Такой же подход можно применить для выбора матрицы R. Заменяя R в соотношении (74) симметричной матрицей R-\-6R и отбрасывая члены второго порядка, получаем выражение

Таким образом, уменьшение вектора квадратичной ошибки максимизируется при выборе

и, поскольку  , алгоритм спуска становится, по существу,

аналогичным первоначальному алгоритму Хо — Кашьяпа.