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

§ 9. Оценка уклонения эмпирически оптимального решающего правила

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

Оценка (6.41) имеет тот же вид, что и раньше, - она образуется произведением емкостной характеристики системы событий и оценкой вероятности того, что уклонение частоты от вероятности превзойдет

Если емкость класса решающих правил бесконечна , то оценка (6.41) травиальна, так как при всех к правая часть неравенства больше единицы. Оценка (6.41) становится содержательной, когда емкость класса

решающих правил конечна:

В этом случае она принимает вид

С ростом правая часть неравенства (6.42) стремится к нулю и притом тем быстрее, чем меньше емкость класса Потребуем, чтобы вероятность

не превышала . Это во всяком случае произойдет, если выполняется равенство

Равенство (6.43) можно разрешить относительно к (используя формулу Стирлинга):

И тогда из (6.42) — (6.44) следует справедливость следующей теоремы.

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

Замечание. Из теоремы 6.7 следует, что для правила минимизирующего эмпирический риск, с

вероятностью справедлива оценка сверху

В приложении к главе показано, что наряду с (6.41) справедлива и оценка

которая для класса решающих правил ограниченной емкости является нетривиальной:

Потребуем, чтобы правая часть неравенства равнялась

Это произойдет, если

С другой стороны, неравенство (6.45) можно переписать в виде утверждения: с вероятностью одновременно для всех а справедливо неравенство

Из (6.46) и (6.47) следует справедливость следующей теоремы.

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

правил класса имеет место оценка

Замечание. Из теоремы 6.8 следует, что для правила минимизирующего эмпирический риск, справедлива оценка

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