§ 6. e-сеть множества

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

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

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

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

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

В этом параграфе для бесконечного множества решающих правил, допускающих покрытие конечной -сетью, мы получим утверждения, аналогичные утверждениям теорем 6.1 и 6.3.

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

расстоянии, не превышающем то качества этих правил различаются не более чем на величину

Иначе говоря, малая вариация решающего правила приводит к малому изменению качества классификации.

В этих условиях теоремы 6.1, 6.3 допускают следующие обобщения.

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

где - ближайший к элемент -сети.

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

где ближайший к элемент -сети.

Замечание. Теоремы 6.4 и 6.5 справедливы для любой -сети, заданной априорно (до появления обучающей последовательности). В частности, величина задающая -сеть, может быть выбрана в теореме 6.4 из условия минимума выражения

а в теореме 6.5 — из условия минимума выражения

где константа (например, ).

Доказательство теорем 6.4 и 6.5 проводится по одной и той же схеме.

1°. На множестве решающих правил задается конечная -сеть, состоящая из элементов

Согласно теореме 6.1 (6.3) с вероятностью 1—г) одновременно для всех элементов (6.33) выполнятся неравенства

2°. Для всякого решающего правила а (в том числе и того, которое минимизирует в величину эмпирического риска) найдется ближайший элемент -сети и для него

Из неравенств (6.34) и (6.35) следует, что для решающего правила с вероятностью справедливо

Теоремы доказаны.

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

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

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