Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

Обе оценки зависят только от свойств класса решаю­ щих функций и никак не связаны с распределением ве­ роятностей на множестве пар х, и. Требуется лишь, чтобы ситуации возникали независимо и с неизменным распределением. Полудим еще оценку для задачи'*’обучения распознаванию в детерминированной постановке. В этом случае среди решающих правил заведомог есть правило, обеспечивающее безошибочное распознавание. Алгоритм, минимизирующий эмпирический риск, выбе­ рет решающее правило, которое всю обучающую после­ довательность классифицирует безошибочно. Оценим ве­ роятность Р (е, Z) того, что решающее правило, выбран­ ное таким алгоритмом по обучающей последовательности длины I, сделает более гі ошибок на экзамене длины I. Очевидно, что вероятность Р (е, Z) не превосходит

Р (sup (ѵ (А; хѵ . . ., Х[) = 0) и (ѵ (А; х [+ь . . ., x2t) > е)}, AeS

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

{х, ca: F (х, a) =f=со}

такое, что частота его выпадения на первой полувыборке равна 0, а частота выпадения на второй полувыборке пре­ вышает е. Для одного события А вероятность того, что ѵ'(А) = 0, а ѵ"(Л)^>8, равна

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

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

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

282 ГЛ. X III. ПРИМ ЕНЕНИЕ ТЕОРИИ РАВНОМЕРНОЙ СХОДИМОСТИ

Поэтому

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

W = (і — ln -J- — ln - p j ,

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

Эта величина является характеристической. Все оценки при фиксированных е и ц являются линейными функция­ ми п. В ряде случаев оказывается, что с вероятностью 1 As (хг , . . . ,Хі) = ms (1). В этом случае, рассуждая аналогично доказательству необходимости в теореме 11.1, можно показать, что с вероятностью, близкой к единице, максимальное по классу S уклонение частот в двух следующих друг за другом полувыборках длины I

функций.

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

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

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

{(х, ф) > с].

§ 1. ОЦЕНКА ДЛИНЫ ОБУЧАЮЩЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ 283

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

тҢ1) = 2 % С 1 1< 3 - g ^ j - ,

і=0 ' '

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

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

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

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

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

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

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

і е і , если К (Ѳо.фі (ж, Ѳ^.фг (ж,Ѳ2), . . . , фь {x,Qh)) > О,

ж еІІ, если К (Ѳ0, фі (ж, Ѳх), ф2 {х, Ѳ2), ..., фь (ж, Ѳь))< 0 .

284 ГЛ. X III. ПРИМ ЕНЕНИЕ ТЕОРИИ РАВНОМЕРНОЙ СХОДИМОСТИ

f десь функции Ä”и фі фиксированы для класса решаю­ щих правил, а параметры Ѳ0, Ѳь . . . ,Ѳк (скалярные или векторные) задают конкретное решающее правило. Кро­ ме того, предположим, что функции фі принимают лишь два значения: —1 и - fl.

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

ms0 (I) для класса событий {у: К (Ѳ0, уи . . ., у к) > 0}, . . .,

mfi (I) для класса событий {х\ фг (£0г) = 1}.

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

к -

гпЧІХЦт-Ні)-

і=0І

В частности, пусть х — m-мерный вектор, а функции Фі и К — линейные пороговые функции, т. е.

к = sgn2 ѳог/д

т

Уі = Фі(я) = SgH 2 QiXP

3=1

где Ѳ{ и Ѳо — настраиваемые параметры,

® (m,z) = 2 2 c U

i=l

к

Ф ( к , 0= 22 с ц .

Я= 1

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

п = тк -f к.