§ 4. Частный случай

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

.                     (5.2)

Нас, однако, интересует случай равномерной сходимости, т. е. вероятность одновременного выполнения всех неравенств  . Такая вероятность может быть оценена, коль скоро оценена вероятность выполнения отдельно каждого неравенства (5.2), а именно

.

Учитывая (5.2), получим

.                    (5.3)

Неравенство (5.3) означает, что имеет место равномерная сходимость

.

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

не превосходила величины , т. е.

.                   (5.4)

Неравенство (5.4) во всяком случае будет иметь место, если величины , , ,  связаны соотношением

.              (5.5)

Разрешая равенство (5.5) относительно , найдем для данных , ,  оценку максимального уклонения частоты от вероятности в рассматриваемом классе событий:

.

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

.

Иначе говоря, выше была доказана следующая теорема.

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

.                      (5.6)

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

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

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

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

Ниже будет показано, что , и тогда, согласно теореме, оценка достаточной длины обучающей последовательности будет равна

,

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