Главная > Математика > Восстановление зависимостей по эмпирическим данным
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 4. Детерминистская постановка задачи

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

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

Введем функцию

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

(а не события как в теореме 6.1).

Так как число функций, на которых достигается нуль величины эмпирического риска, не превосходит (числа всех функций в классе), то справедливо неравенство

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

Подставляя оценку в (6.21), получаем

Для того чтобы вероятность

не превосходила величину достаточно выполнения равенства

Разрешим относительно это равенство

Так как для малых х справедливо

то формула (6.25) может быть представлена в виде

В отличие от оценки (6.20), здесь знаменатель равен х, а не т. е. в детерминистской постановке достаточная длина обучающей последовательности оказывается меньшей, чем в общем случае. Разрешая (6.24) относительно к,

получим

Таким образом, справедлива теорема.

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

где

<< Предыдущий параграф Следующий параграф >>
Оглавление