§ 6. Условия остановки алгоритма

В соответствии с теоремами предыдущего раздела предложенный выше алгоритм приводит к точному разделению множеств с вероятностью единица для каждой конкретной задачи и в каждой реализации за конечное число шагов. Однако, как бы ни была длинна обучающая последовательность и на каком бы шаге процесс обучения ни был приостановлен, теоремы предыдущего параграфа не дают никаких гарантий относительно того, произошло уже разделение множеств или нет. Ниже предлагаются два варианта остановки процедуры (4), (5), при выполнении которых хотя и не гарантируется точное разделение множеств, но обеспечивается достаточно малая вероятность ошибки в последующем экзамене, если только статистики появления точек в процессе обучения и в процессе экзамена совпадают.

Вариант 1. Дополним алгоритм (4), (5) следующим условием остановки: процесс обучения заканчивается, как только после очередного исправления ошибки следующие за ним подряд показов не приводят к новому исправлению ошибки. Здесь произвольное, наперед заданное целое число. Доопределенная так процедура (4), (5) в силу теоремы II приведет к окончанию процесса обучения не позже чем после показов в процессе обучения, где максимальное число исправлений ошибок, оцениваемое теоремой II. Коль скоро процесс обучения в соответствии с приведенным выше условием остановки закончен, качество последующего экзамена можно гарантировать оценкой, приведенной в следующей теореме.

Теорема IV. Пусть вероятность ошибки в процессе экзамена, проводимого после окончания процесса обучения. Тогда, каковы бы ни были вероятность того, что больше чем если удовлетворяет неравенству

Доказательство теоремы IV. Рассмотрим событие заключающееся в том, что при использовании предложенного алгоритма и введенного условия

остановки общее количество исправлений ошибок не меньше чем заданное целое число Введем в рассмотрение функцию такую, что означает вероятность события: вероятность ошибки на следующем после исправления ошибки шаге лежит между до и до при условии, что событие имеет место.

Если на каждом шаге вероятность ошибки равна до, то вероятность того, что в течение шагов подряд ошибка не возникает, в силу независимости показов равна Поэтому вероятность того, что в течение показов после исправления ошибки новая ошибка не наступает и вероятность ошибки лежит между до и до равна

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

где вероятность наступления события

Остановка процесса обучения после разного числа исправлений ошибок — несовместные события. Поэтому вероятность такой остановки, что в последующем экзамене вероятность ошибки больше равна

Оценим это выражение сверху:

или, учитывая, что

получим

Но

если удовлетворяет неравенству (42). Поэтому

Рассматриваемая в теореме величина есть вероятность события при условии, что остановка произошла на каком-либо шаге (т. е. условная вероятность). Вероятность же совместная вероятность событий и «остановка произошла». Однако поскольку последнее событие всегда наступает (причем самое большее через шагов), то

Теорема доказана.

Таким образом, если из каких-либо соображений известна оценка числа максимально возможного количества исправлений ошибок, то теорема IV позволяет выбрать число так, чтобы гарантировать при использовании первого варианта условий остановки нужное качество процесса обучения. Однако обычно число заранее не известно: оценка (38) не может быть практически использована, так как множества также не известны заранее. В этом заключается недостаток первого варианта условий остановки. Описываемый ниже второй вариант условий остановки обходит это затруднение.

Вариант 2. При первом варианте «доверительное» число показов без исправлений ошибки, после которого заканчивается процесс обучения, не зависит от числа предыдущих исправлений ошибок. Во втором варианте принимается, что число зависит от числа имевшихся ранее исправлений ошибок и равно

где наперед заданное число. Таким образом, во втором варианте увеличивается на единицу после каждого исправления ошибки.

При таком доопределении в силу теоремы II остановка обязательно произойдет за конечное число показов, не превышающее

Задача состоит теперь в выборе такого числа чтобы гарантировалось требуемое качество процесса обучения.

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

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

Доказательство теоремы Дословно повторяя начало доказательства теоремы IV, получаем

где

Оценим сверху:

Поэтому

если удовлетворяет неравенству (43). Учитывая последнее замечание в доказательстве теоремы IV, можно написать что и требовалось доказать.

В варианте 2 условий остановки вместо можно принять любую другую монотонно растущую по функцию лишь бы ряд сходился. Доказательство теоремы V при этом сохраняется полностью, но оценка зависит от выбора функции