§ 5. Алгоритмы персептронного типа

1. В главе I был сформулирован алгоритм построения разделяющей гиперплоскости персептрона. В этом параграфе рассмотрим различные модификации метода Гаусса– Зайделя для поиска максимума в положительном квадранте и покажем, что алгоритм построения разделяющей гиперплоскости персептрона отражает одну из модификаций этого метода.

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

Рассмотрим модифицированный метод Гаусса–Зайделя. Модификация метода направлена на то, чтобы искать максимум функции в положительном квадранте. Изменение метода Гаусса–Зайделя состоит в следующем:

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

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

3) процесс поиска максимума прекращается, когда выполнятся неравенства

, если ,

, если .

2. Применение модифицированного метода Гаусса– Зайделя для максимизации функции в области , приводит к следующему алгоритму построения обобщенного портрета. Если на -м шаге производится движение вдоль координаты , то

Аналогично в случае движения вдоль координаты

Значения остальных координат сохраняются.

Приращения , доставляющие максимум по направлению шага, определяются из условий

где положено

Учитывая, что шаг не должен выводить за пределы ограничений, получаем

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

В первом случае останов производится по условию

, если ,

, если

(, если ,

, если ).

Во втором случае критерием останова служит выполнение неравенства (14.15)

где – допустимый зазор.

Алгоритм можно реализовать и в такой форме:

при движении вдоль ,

при движении вдоль .

3. С помощью метода Гаусса – Зайделя удается достигнуть максимума и тем самым построить обобщенный портрет. Однако часто требуется найти просто разделяющую гиперплоскость (не обязательно экстремальную) такую, что

. (14.16)

Построение такой гиперплоскости обеспечит следующая огрубленная модификация метода Гаусса – Зайделя:

1) движение вдоль каждой из координат происходит только в сторону от ограничений тогда, когда

В случае выполнения этих условий значение вектора вычисляется по формулам

где шаг по-прежнему выбирается из условия максимизации функции по направлению

;

2) процесс подъема по функции прекращается, когда будут выполнены все неравенства (14.16). Легко видеть, что при л полученный алгоритм совпадает с алгоритмом построения разделяющей гиперплоскости, предложенным Уидроу (см. главу IV).

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

где

Поэтому, учитывая, что, согласно (14.14),

где – расстояние между проекциями классов на направление обобщенного портрета , получаем, что максимальное число исправлений в алгоритме Уидроу ограничено величиной

(Здесь принято, что .) Оценка аналогична оценке числа исправлений для персептрона (глава I, теорема Новикова).

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