§ 1. Оценка достаточной длины обучающей последовательности в задачах обучения распознаванию

Глава XIII. ПРИМЕНЕНИЕ ТЕОРИИ РАВНОМЕРНОЙ СХОДИМОСТИ К МЕТОДАМ МИНИМИЗАЦИИ ЭМПИРИЧЕСКОГО РИСКА

§ 1. Оценка достаточной длины обучающей последовательности в задачах обучения распознаванию

1. В главе X было показано, что значения риска в точках истинного и эмпирического минимумов заведомо отличаются не более чем на , если выполнено условие

Далее было показано, что в задачах распознавания образов с функцией штрафа

это условие переходит в следующее:

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

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

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

а через значение параметра, при котором достигается минимум функции

где – обучающая последовательность. Тогда на основании формулы (10.19) получаем

, (13.1)

где – функция роста класса событий вида

В этой формуле функция роста берется для событий, заданных в пространстве пар .

Рассмотрим число различных разбиений выборки на классы с помощью решающих правил . Обозначим это число

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

. (13.2)

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

С другой стороны, два множества и в соответствии с соглашением главы X, считаем эквивалентными относительно выборки , если для всех

, (13.3)

причем есть число классов эквивалентности. Очевидно, что (13.3) следует из (13.2), а в случае, когда и принимают всего два значения 0 и 1, и соотношение (13.2) следует из (13.3). Поэтому

Соответственно из (13.1) следует, что

. (13.4)

Рассмотрим более подробно дихотомический случай, когда распознаются два класса. При этом как , так и функция могут принимать всего два значения: 0 и 1.

Пусть система состоит из событий

при всевозможных .

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

Кроме того, как указано выше, в дихотомическом случае соотношения (13.2) и (13.3) равносильны. Поэтому

и соответственно

где – функция роста для системы событий вида

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

и разрешить это неравенство относительно .

Допустим, что , и пусть – такое число, что , a ; тогда, в соответствии с замечанием 1 к теореме 10.1,

или, заменяя по формуле Стирлинга,

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

Разрешим относительно неравенство

Логарифмируем:

. (13.5)

Обозначим

Тогда

и соответственно

Разрешим это неравенство относительно . Учитывая, что

получаем

откуда

. (13.6)

Эта оценка, однако, завышена.

Более точную оценку получим из следующих соображений.

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

где – событие вида .

Но для этой величины оценка получена при выводе теоремы 10.2:

Отсюда, аналогично выводу (13.6), получаем, что для того, чтобы с вероятностью, большей , частота ошибок на материале обучения и на экзамене отличалась меньше чем на , достаточно, чтобы

, (13.7)

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

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

т. е. вероятность того, что найдется событие вида

такое, что частота его выпадения на первой, полувыборке равна 0, а частота выпадения на второй полувыборке превышает . Для одного события вероятность того, что , а , равна

если число элементов в выборке превосходит , и нулю в противном случае.

Поэтому во всех случаях

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

Поэтому

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

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

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

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

Линейные решающие правила в случае двух классов (случай большего числа классов сводится к последовательной дихотомии) имеют вид:

относится к I классу, если ,

относится ко II классу, если .

Здесь -мерный вектор и константа являются параметрами класса решающих функций.

Нас интересует функция для системы событий вида

Для случая функция была найдена в примере 3 § 3 главы X. Она равна

где – размерность пространства.

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

где – размерность пространства.

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

К этому же случаю сводятся алгоритмы решающих правил, основанных на переходе к спрямляющему пространству и построении в этом новом пространстве линейного решающего правила. Соответствующие правила имеют вид:

относится к I классу, если ,

относится ко II классу, если .

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

Рассмотрим более сложный вид решающего правила:

, если ,

, если .

Здесь функции и фиксированы для класса решающих правил, а параметры (скалярные или векторные) задают конкретное решающее правило. Кроме того, предположим, что функции принимают лишь два значения: и .

Тогда, если известны функции

для класса событий , …,

для класса событий ,

то интересующая нас функция оценивается

В частности, пусть – -мерный вектор, а функции и – линейные пороговые функции, т. е.

где и – настраиваемые параметры,

Тогда

где

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

Этот класс решающих функций используется при настройке многослойных персептронов, в машинах типа «Маделин» и вообще при построении кусочно-линейных решающих правил.

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