§ 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 шага обязательно произойдет останов и что в момент останова построенная гиперплоскость окажется заданного качества.

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