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

Г л а в а X III

П Р И М Е Н Е Н И Е Т Е О Р И И Р А В Н О М Е Р Н О Й С Х О Д И М О С Т И

К М Е Т О Д А М М И Н И М И З А Ц И И Э М П И Р И Ч Е С К О Г О Р И С К А

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

1.В главе X было показано, что значения риска R (а

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

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

0 при со = F,

Ф(со, F) =

1 при со Ф F

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

s u p H ^ - P ^ K - l - ,

где Та — событие {(со, х): F {х , а) Ф со}, F (х, а) — решающее правило с параметром a, Q — множество до­ пустимых значений параметра а.

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

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

R (а) = § Ф (со — F (х, а)) dP\(x, со),

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

минимум функции

I

^эмп (а) = -у 2 Ф (®І—F (хх, а)),

1=1

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

где ms (I) — функция роста класса событий вида

Та = {(со, х): со ф F (X, а)}.

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

N (хѵ . . ., хх).

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

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

эквивалентности. Очевидно, что (13.3) следует из (13.2), а

As (жх, (Оі, . . ., х ь со/) < N (хи . . ., хі),

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

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

А = {х: F (х, а) = 1}

при всевозможных а ЕЕ (?.

Тогда очевидно, что число разбиений выборки хъ . . .

..., Хі на классы с помощью решающих правил F (х, а) рав­

As (xv сох, . . ., х и юг) = N (хг, . . ., xj) =

= As'(«i , • • • , хі),

ms (І)= ms' (І)

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

_ ечг-1)

P{R (а*) — R (а) > е } < 6/ns' (l)e 18 ,

где ms' (І) — функция роста для системы S ' событий вида

{х: F (х, а) = 1}.

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

580 гл. X III. ПРИМ ЕНЕНИЕ ТЕОРИИ РАВНОМЕРНОЙ СХОДИМОСТИ

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

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

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

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

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