5.12.2. ПРАВИЛО ПОСТОЯННЫХ ПРИРАЩЕНИЙ

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

является бесконечное множество раз. Обозначим через линейную машину с весовыми векторами &i{k), . . . , &c{k)- Начиная с исходной, произвольно выбранной линейной машины Li и используя последовательность выборок, сформируем последовательность линейных машин, сходяш,уюся к решающей линейной машине, причем эта последняя будет классифицировать все выборки правильно. Предложим правило коррекции ошибок, в соответствии с которым изменения весов производятся только в том случае, если текущая линейная машина делает ошибку при классификации одной из выборок. Обозначим k-ю выборку, которой необходима коррекция, через у* и предположим, что у* ^ З/,-. Поскольку коррекция вызвана ошибкой при классификации у*, то должно существовать по крайней мере одно }фі, для которого

Тогда правило постоянных приращений для коррекции примет вид

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

Для каждой выборки существуют с—1 выборок ііг; (пра

вило их формирования описано в предыдущем пункте). В частности, для вектора у*, удовлетворяющего неравенствам (91), существует вектор

удовлетворяющий условию

Более того, правило постоянных приращений для коррекции Lft в точности совпадает с таким же правилом для коррекции т. е.

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

1ll^ . . ., щ*, ... и последовательность весовых векторов «і, «2, ..... «ft, ... . В соответствии с результатами, полученными для случая двух классов, последняя из указанных последовательностей не может быть бесконечной и должна заканчиваться вектором решения. Следовательно, и последовательность h, . . . ... , Lft, . . . должна приходить к решающей машине после конечного числа коррекции.

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