§ 4. Теоремы об останове
Пусть одновременно с построением
разделяющей гиперплоскости будет выясняться качество построенной к данному
моменту гиперплоскости. Если оно высоко, то обучение прекращается; в противном
случае обучение продолжается. Таким образом, кроме алгоритма построения
разделяющей гиперплоскости имеется алгоритм проверки качества построенной
гиперплоскости. Будем пользоваться следующим критерием: процесс обучения
заканчивается, как только после некоторого (
-го) исправления решающего правила
очередные 
элементов
обучающей последовательности не приводят к изменению решающего правила. Теория
останова, по существу, исследует два вопроса:
1)
какими должны быть величина , чтобы в случае, если останов
произойдет, можно было бы утверждать, что с заданной вероятностью качество
построенного решающего правила будет не хуже требуемого;
2)
на какой длине обучающей последовательности заведомо произойдет останов.
Ответ на эти два вопроса дают
следующие теоремы.
Теорема 4.1. Если в соответствии с
критерием останова процесс обучения закончится, то с вероятностью, большей 
, можно утверждать,
что построенное решающее правило характеризуется качеством 
при условии, что
,
где
; 
– любая константа,
большая 1; 
.
Доказательство. Пусть в процессе
обучения сменяются решающие правила
Оценим вероятность того, что
останов произойдет в тот момент, когда выбрано правило 
с качеством 
.
Пусть, например, после -го исправления
выбрано правило 
с
качеством 
;
при этом условии вероятность 
того, что останов произойдет после -го (но до 
-го) исправления,
равна вероятности того, что за этим исправлением последует безошибочных опознаний, т. е.
.
Тогда вероятность 
того, что останов
произойдет после одного из исправлений, когда , оценивается так:
.
Таким
образом, справедлива оценка:
.
Выберем теперь функцию такую, что
. (4.5)
Из
равенства (4.5) может быть найдено, что
. (4.6)
Остается
определить величину 
.
Найдем ее из условия
,
т.
е.
,
где
.
Из
этого соотношения находим, что
. (4.7)
Таким
образом, из (4.6) и (4.7) следует, что при
(4.8)
вероятность
меньше
требуемой величины 
.
Оценка (4.8) справедлива для любого 
. В частности, при 
, откуда
.
Теорема доказана.
Теорема 4.2. Пусть конечно-сходящийся
алгоритм таков, что число коррекций не превосходит величину 
, а в качестве взята функция (4.8),
описанная в условии теоремы 4.1; тогда можно утверждать, что останов заведомо
произойдет на обучающей последовательности длины
.
Доказательство теоремы очевидно.
Для персептрона Розенблатта в
силу теоремы Новикова 
, поэтому останов произойдет на обучающей
последовательности длины
.
Существует некоторая тонкость в
понимании приведенных теорем об останове. Эти теоремы никак не гарантируют, что
после того, как будет сделано 
шагов, построенная разделяющая
гиперплоскость окажется требуемого качества. Теоремы гарантируют лишь то, что
до -гo шага обязательно произойдет
останов и что в момент останова построенная гиперплоскость окажется заданного
качества.
Если же алгоритм не остановить,
то, вообще говоря, может случиться, что последующие коррекции ухудшат качество
решающего правила и к -му шагу это качество будет ниже
требуемого.
