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