§ 10. Замечания об оценке скорости равномерной сходимости частот к вероятностям
Итак, в этой главе мы получили оценки скорости равномерной сходимости частот к вероятностям
и оценки равномерного одностороннего относительного уклонения частот от вероятностей
С помощью этих оценок были получены теоремы 6.1, 6.3 и 6.7, 6.8, которые позволили оценить качество решающего правила, минимизирующего величину эмпирического риска.
Все полученные оценки имеют одну и ту же структуру — они состоят из двух сомножителей, один из которых оценивает вероятность соответствующего уклонения для каждого (в отдельности) события в классе, другой
характеризует разнообразие класса решающих правил.
В оценке используются различные характеристики разнообразия класса решающих правил. Наиболее примитивная — число решающих правил в классе. Примитивность такой характеристики заключается в том, что она, например, никак не учитывает, состоит ли класс решающих правил из «существенно различных» правил, или же все правила в классе «эквивалентны».
Адекватная мера разнообразия класса решающих правил, с помощью которой и удается построить необходимые и достаточные условия равномерной сходимости частот к вероятностям, — энтропия системы событий, заданной решающими правилами. Однако вычислить энтропию системы событий на выборках длины I можно, лишь зная плотность 
которая, согласно постановке задачи обучения распознаванию образов, считается неизвестной. Поэтому была введена новая мера разнообразия, которая получается из энтропии выбором наиболее неблагоприятного распределения. Эта мера разнообразия выражается через емкость класса решающих правил и легко может быть вычислена.
Различные определения меры разнообразия класса решающих правил порождают разные теоремы о качестве алгоритмов, минимизирующих эмпирический риск.
Однако во всех этих теоремах утверждается один и тот же факт: если мера разнообразия класса решающих правил мала по сравнению с объемом выборки, то метод минимизации эмпирического риска позволяет выбрать правило, близкое к наилучшему в классе.
Характерной особенностью изложенной теории минимизации эмпирического риска является полное отсутствие каких бы то ни было указаний на конструктивную возможность построения алгоритмов. Такая особенность имеет как отрицательные, так и положительные стороны.
С одной стороны, построенная теория не указывает на регулярные процедуры минимизации эмпирического риска, которые должна реализовать соответствующая программа.
С другой стороны, теория минимизации эмпирического риска весьма обща. Метод минимизации эмпирического риска может быть применен для самых различных классов решающих правил: линейных дискриминантных функций, кусочно-линейных дискриминантных функций,
логических функций определенного вида и др. Это связано с тем, что теория метода минимизации эмпирического риска отвечает на вопрос, «что надо делать», оставляя в стороне вопрос «как это сделать». Поэтому для минимизации эмпирического риска могут быть применены различные методы, в том числе и эвристические.
Применение эвристических методов в этом случае имеет теоретическое оправдание: если в классе решающих правил, емкость которого невелика по сравнению с объемом выборки, выбрать правило, которое хотя и не минимизирует эмпирический риск, но доставляет ему достаточно малую величину, то в силу доказанных теорем выбранное решающее правило будет иметь достаточно высокое качество.
Конструктивные идеи таких алгоритмов имеют наглядную геометрическую интерпретацию: в пространстве X надо построить гиперповерхность, принадлежащую заданному классу гиперповерхностей, которая, по возможности, с меньшим количеством ошибок отделит векторы обучающей последовательности одного класса от векторов обучающей последовательности другого класса.
Отнесение векторов (в том числе и не входящих в обучающую последовательность) к тому или иному классу производится в зависимости от того, по какую сторону от разделяющей гиперповерхности он находится.
Методы построения разделяющих гиперповерхностей составляют конструктивную часть теории обучения распознаванию образов. Эти методы будут изложены в главе XI.
