5.9. ПРОЦЕДУРЫ ХО—КАШЬЯПА

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

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

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

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

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

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

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

получая тем самым и минимизируя по а за один шаг. Больших возможностей для изменения b, однако, не имеется, поскольку нужно придерживаться условия так что следует избегать процедуры спуска, которая приводит . Один из способов, препятствующий сходимости b к 0, заключается в том, чтобы положить вначале и впоследствии не уменьшать никакую из его компонент. Этого можно достичь при сохранении отрицательного градиента, если вначале все положительные компоненты взять равными 0. Таким образом, если через обозначить вектор, компоненты которого суть абсолютные величины компонент вектора v, то придем к рассмотрению такой процедуры спуска:

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

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

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

и

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

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

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

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

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

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

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

Для доказательства того, что вектор ошибки всегда сходится к нулю, используется тот факт, что матрица симметрична, положительно полуопределена и удовлетворяет соотношению

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

матрица таким образом, при любом b, и матрица является по крайней мере положительно полуопределенной. Итак, соотношение (66) вытекает из следующего:

Чтобы показать, что должно сходиться к нулю, исключим из и получим следующее выражение:

Затем, используя (62), получим рекуррентную формулу

так что

Как второй, так и третий члены значительно упрощаются. Поскольку второй член представляется в виде

ненулевые компоненты вектора являются положительными компонентами вектора Поскольку матрица симметрична и равна произведению , третий член упростится до следующего выражения:

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

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

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

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

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

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

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

Что получается, если образы неразделяемы, а никогда не обращается в нуль? В данном случае все же выполняются

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

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

Если записать равенство и использовать соотношение то алгоритм Хо — Кашьяпа можно представить в виде

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

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

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

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

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

и

где

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

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

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

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

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

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

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

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

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

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

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

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