§ 7. Необходимые и достаточные условия равномерной сходимости частот к вероятностям
До сих пор для получения оценок скорости равномерной сходимости, мы использовали достаточно грубые емкостные характеристики множества решающих правил (число элементов множества).
В этом параграфе мы введем более тонкую емкостную характеристику — энтропию системы событий на выборках длины . С помощью этой характеристики могут быть установлены исчерпывающие, необходимые и достаточные условия равномерной сходимости частот появления событий к их вероятностям, т. е. необходимые и достаточные условия того, что для любого к выполнится равенство
Итак, пусть задано множество S решающих правил и дана выборка Эта выборка, вообще говоря, может быть разделена на два класса способами. Однако нас будут интересовать только те способы разделения выборки, которые могут быть реализованы с помощью правил . (С помощью правила множество делится на два подмножества — подмножество, на котором и подмножество, на котором
Число таких способов разделения зависит как от класса решающих правил так и от состава выборки. Будем обозначать это число через
Рассмотрим систему событий
образованную множеством решающих правил
Пусть дана случайная независимая выборка
На выборке (6.36) система событий индуцирует различных подвыборок. Очевидно, что число этих подвыборок равно
Так как случайная независимая выборка, то число разделений величина случайная.
Определение. Назовем величину энтропией системы событий на выборках длины
Оказывается, что для существования равномерной сходимости частот к их вероятностям по множеству событий необходимо и достаточно, чтобы с ростом объема выборки доля энтропии, приходящаяся на один элемент выборки, стремилась к нулю, т. е. чтобы последовательность
стремилась к нулю с ростом Иначе говоря, выполнялось условие
Доказательство этого утверждения приведено в монографии [12].
Как и всякие исчерпывающие условия, сформулированные необходимые и достаточные условия равномерной сходимости частот появления событий к их вероятностям используют тонкие понятия. В нашем случае таким понятием является энтропия системы событий на выборках длины I, которая конструируется с помощью плотности Согласно же постановке задачи распознавания образов плотность неизвестна. Поэтому, для того чтобы установить возможность минимизации среднего риска путем нахождения минимума эмпирического риска, нельзя использовать необходимые и достаточные условия (6.37).
Вот почему важно получить более грубые достаточные условия, которые, во-первых, не зависели бы от свойств меры а во-вторых, допускали бы оценку скорости равномерной сходимости. Такие условия могут быть найдены на основе емкостной характеристики системы
событий которая получается из энтропии абстрагированием от свойств меры.
Определение. Назовем функцию
где максимум берется по всем возможным выборкам длины I, функцией роста системы событий, образованной решающими правилами
Функция роста построена так, что не зависит от свойств меры и для нее всегда выполняется неравенство
Теперь, если окажется, что величина
с ростом стремится к нулю, то отношение в силу (6.38) и подавно устремится к нулю. Поэтому условие
является достаточным условием равномерной сходимости частот к вероятностям. Ниже мы покажем, что функция роста легко может быть найдена для событий, заданных различными классами решающих правил и, следовательно, может быть установлен факт равномерной сходимости. Более того, как будет показано ниже, с помощью функции роста может быть оценена и скорость равномерной сходимости.