5.2.2. Доказательство сходимости

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

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

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

При этих условиях алгоритм (5.2.5) принимает следующий вид:

причем вектор выбирается произвольным образом. Пусть для простоты Это допущение не нарушает общности

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

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

и

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

После введения этих упрощений доказательство сходимости алгоритма состоит в следующем. Из (5.2.9) получаем

Скалярное произведение вектора с обеими частями уравнения (5.2.11) дает

Так как из условия (5.2.7) следует, что каждый член , больше пороговой величины Т, то

Неравенство Коши — Шварца приводит к выражению

где обозначает квадрат модуля вектсра а. Неравенство (5.2.14) можно переписать в виде

После подстановки неравенства (5.2.13) в (5.2.15) получим неравенство

Другая ветвь рассуждений приводит к противоречию, касающемуся величины Из (5.2.9) заключаем, что

или

Используя неравенство (5.2.10) и полагая придем к

Суммируя эти неравенства по всем , получим

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

Согласно (5.2.21), — конечная величина, из чего следует сходимость алгоритма перцептрона за конечное число шагов при условии линейной разделимости заданных классов. Это завершает доказательство сходимости алгоритма перцептрона.

Замечания. Частный случай при доказывается несколько иначе. Неравенство (5.2.13) принимает вид

где

Так как согласно нашей гипотезе — вектор решения, то . Кроме того, поскольку неравенство (5.2.19) превращается в

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

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