§ 10. Замечание об оценке скорости равномерной сходимости частот появления событий к их вероятностям

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

Объяснение этому частично дано в предыдущем параграфе, где формулы (5.3), (5.10) и (5.13), (5.18) определяют скорости равномерной сходимости частот появления событий к их вероятностям по различным классам событий .

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

Формально этот факт находит свое отражение в структуре формул, задающих оценку равномерной сходимости, (5.10), (5.18). Правая часть неравенств (5.10), (5.18) состоит из двух сомножителей. Первый сомножитель характеризует емкость класса событий (он идентичен, как в случае (5.10), так и в (5.18)), второй сомножитель оценивает вероятность уложиться в заданное уклонение  частоты от вероятности для любого события заданного класса (в детерминистской постановке этот класс есть , в стохастической – этот класс совпадает с ).

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

Для детерминистского варианта постановки наиболее неблагоприятное событие в классе  то, для которого . Для оценки уклонения частоты от вероятности этого события возможна более тонкая оценка (5.14).

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

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

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

Рис. 12.

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

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

Оценим требующуюся для этого длину выборки. В главе XII будет показано, что справедлива односторонняя оценка:

.                      (5.20)

Положим

.

Тогда из условия

            (5.21)

следует, что

                                         .

При  получаем

.

Таким образом, условия (5.21) достаточно для -близости эмпирически оптимального решающего правила к истинно оптимальному. Подставляя значение  в (5.20), получаем

.               (5.22)

В детерминистском случае  и мы получаем оценку, близкую к (5.18), а при  – оценку, близкую к (5.10).

Результаты главы XII позволяют получить и другую оценку качества решающего правила. Допустим, что выполняется (5.21). Тогда, разрешая (5.21) относительно , получим

.                       (5.22')

Потребуем теперь, чтобы (5.21) выполнялось для всех  с вероятностью, превышающей . Для этого достаточно правую часть (5.20) приравнять :

.

Разрешая это уравнение относительно  и подставляя найденное значение в (5.22'), получаем окончательно

.

При

.                  (5.23)

Как и раньше, примем, что в точке

.

Заметим, что для эмпирически оптимального  справедливо

.

Тогда с вероятностью

.                  (5.23')

Используя (5.22), можно получить оценку длины обучающей последовательности, которая в одном предельном случае (при ) совпадает с оценкой (5.19), а в другом предельном случае  – с оценкой (5.12). Для этого достаточно правую часть неравенства (5.22) приравнять  и разрешить относительно . Получаем

.

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

, , , , .