Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 213
Скачиваний: 4
200 ГЛ. |
IX . О СХОДИМОСТИ РЕ К У РРЕ Н Т Н Ы Х АЛГОРИТМОВ |
§ 5. |
Еще одно условие сходимости рекуррентных |
|
алгоритмов |
В условиях теоремы 1 не предполагалось, что сущест вует минимум функционала R (а). Достаточно было того, что функционал ограничен снизу и, следовательно, су ществует точная нижняя грань. Сходимость к точной нижней грани и утверждала теорема.
Сейчас будем предполагать, что минимум функционала существует. Это позволит ослабить требования к порядку роста модуля градиента функции потерь.
Теорема 9.2. (Б. М. Литваков [44]). Пустъ выполнены
следующие |
условия'. |
|
|
|
1) функционал R (а) ограничен снизу и существует |
||||
непустое |
множество |
Т = {а: |
R (а) = inf R (а)}, |
|
'2) M{|V0 <?(z, а )|2} < 0 |
(1 + I а |2), |
|||
3) М {£2 I а} |
< £> |
(1 + I а |2). |
||
Тогда |
при |
любом |
а нач |
с вероятностью единица |
справедливо: R (а (і)) -—> inf R (а).
і —►СО |
Выберем произвольную |
Д о к а з а т е л ь с т в о . |
точку а 0 €Е Т. Оценим долю б тех последовательностей, которые хоть раз выйдут из гипершара G с центром в а 0 и радиуса г. Для этого положим, что рекуррентные соот
ношения (9.13) выполняются лишь для |
I а — а 0 |
| |
г |
|||
и вне гипершара G последовательность «залипает», |
т. |
е. |
||||
а (і — 1), если |
I а (г — 1) — а 0 |
| ^> г, |
|
|
|
|
а (і — 1) — у (г) [Ѵ0 Q (z, |
а (і — 1)) + |
£,], |
|
|
||
І |
если |
I а (і — 1) — |
а 0 |
| |
г. |
Таким образом, последовательность, выйдя из гипершара, не может войти обратно.
Аналогично теореме 9.1, учитывая условия выпукло сти Q (z, а) и условия теоремы 9.2, можно показать, что
справедливо |
неравенство |
|
|
|
|
||
М {(а (і) |
- |
а 0)2} < М {(а (і - |
1) - а 0)2} + |
|
|||
|
|
+ |
2f (i)DМ {(1 + |
а 2 (і - |
1))}. (9.24) |
||
Усилим |
неравенство |
(9.24), |
для |
чего |
оценим величину |
||
М (1 + а 2 (г - |
1)} = |
1 + |
М {а2 (і - |
1)}. |
§ 5. ЕЩ Е ОДНО УСЛОВИЕ |
СХОДИМОСТИ |
201 |
||
Воспользовавшись |
неравенством |
а2 ^ |
2 (а — Ъ)2 + 2Ъ2, |
|
получим |
|
|
|
|
М {1 + а 2 (і - 1)} < 1 + 2М {(а (і - |
1) - а 0)2} + |
|||
Подставляя (9.25) в (9.24), получим |
+ 2аІ (9.25) |
|||
|
|
|||
М {(а (і) - а 0)2} < |
(1 + 4у2 (і) £>)М {(а (і - |
1 ) - а 0)2}+ |
||
|
+ 2у2 (i)D (1 + |
2а%). (9.26) |
Из неравенства (9.26) следует, что величина М {(а (і) —
—а 0)2} ограничена числом L, |
не зависящим от номера і. |
||||
Покажем это. |
|
|
2D (1 -f |
2аІ) = |
Ъ. По |
Обозначим |
( а Нач — “ о)2 = |
а, |
|||
кажем, что справедливо неравенство |
|
|
|||
|
г |
|
г |
|
|
М {(а (0 - а0)2} < |
П (1 + 4Т2 (/) D) ( а + Ъ 2 |
Т2 (/))• |
(9.27) |
||
|
з'=і |
' |
з=і |
' |
|
Для і = 1 |
справедливость неравенства легко проверяется: |
|
М {(а (1) - |
а 0)2} < (1 + 4у2 |
(1) D )a + y 2 (1) Ъ< |
|
< |
(1 + 4у2 (1) D) {а + у2 (1) Ь). |
По индукции легко доказывается справедливость нера венства и для любого і, если оно справедливо для і — 1:
|
|
|
|
|
|
•і—1 |
|
|
|
|
М {(а (і) — а0)2} < |
(1 + |
4т2 (і) D) |
П (* + |
4?2 (Д D) х |
|
|||||
|
і—1 |
|
|
і |
3 = 1 |
|
|
і |
|
|
|
|
|
|
|
|
|
||||
X |
|
Т2(І)) + b r2( 0 < n ( l + 4720')ö )(a + |
3=1 |
Т* (7)) • |
||||||
' |
3=1 |
' |
|
3=1 |
|
|
' |
' |
||
|
|
|
|
|
|
|
|
|
||
|
Остается показать, что величина |
М {(а (і) — а 0)2} |
||||||||
ограничена, т. е. |
|
оо |
|
|
|
|
||||
|
|
оо |
|
|
|
|
|
|
|
|
|
|
П (1 + 4т2 (Д D) (а + |
Ъ 2 |
Г2 О)) < |
|
(9.28) |
||||
|
|
3=1 |
|
|
' |
3=1 |
|
1 |
|
|
В |
самом |
деле, |
в |
произведении |
(9.28) сомножитель |
|||||
|
оо |
|
|
|
|
|
|
ОО |
|
|
(а + Ъ 2 |
Т2(Д) |
|
ограничен, так как |
2 г 2(/)<С°°. |
' |
з=і |
' |
з=і |
202 Г Л . ІХ . О СХОДИМ ОСТИ Р Е К У Р Р Е Н Т Н Ы Х АЛГОРИТМ ОВ
Сомножитель
со
11(1 - И г 2 (/) г)
3=1
также ограничен, так как бесконечное произведение
оо
П ( 1 + 4 т 2(У) D)
3 = 1
ограничено тогда и только тогда, когда сумма
оо
2 4 Т 2(/)Я і—1
ограничена.
Таким образом,
М {(ос (і) - а0)2} < L.
Используя |
неравенство Чебышева, можно получить |
неравенство |
6 < ^ у . |
На множестве G функция М {Q (z, а)} ограничена. Рассмотрим процесс, отличающийся от (9.13) лишь тем, что при выходе за пределы G он «залипает». Очевидно, что все реализации исходного процесса, не покидающие G, при этом сохранятся и вероятность «залипания» меньше б. Применительно к новому процессу можно повторить все рассуждения теоремы (9.1) и показать, что с вероят ностью, превышающей 1 — б, для этого процесса
R(a(i)) — > inf R (а).
г — оо а
Отличие лишь в том, что в лемме 2 величина бг есть вероятность того, что процесс за первые і шагов ни разу не вышел из области G и не вошел в Gt. Получая, далее, что lim öt = 0, приходим к выводу, что с вероятностью,
і —*оо
превышающей 1 — б, процесс входит в Gt. Остальные рассуждения повторяются, по существу, без изменения.
Далее, соответствующим выбором г величина б может быть сделана сколь угодно малой, откуда и следует ут верждение теоремы.
Гл а в а X
Д О С Т А Т О Ч Н Ы Е У С Л О В И Я Р А В Н О М Е Р Н О Й С Х О Д И М О С Т И Ч А С Т О Т
Е В Е Р О Я Т Н О С Т Я М Н О К Л А С С У
СО Б Ы Т И Й
§1. О близости минимума эмпирического риска
кминимуму среднего риска
Перейдем теперь к анализу методов, основанных на минимизации эмпирического риска. Пусть задана выборка
zx, • • •! Z;,
полученная в серии независимых испытаний при неизмен ном распределении Р (z), и известна функция Q (z, а). Требуется найти минимум функционала
R (а) = § Q (z, а) dP (г).
В дальнейшем будем полагать, что минимум R (а) суще ствует и достигается при а = а 0.
Рассматриваются методы, где в качестве приближения берется значение а*, доставляющее минимум функции
I
Дэмп (о) = -у- 2 Q (г,, а).
І = 1
Естественно, в качестве меры близости а 0 и а* взять разность значений функционала R (а) в этих точках:
р (а0, а*) = R (а*) — R (а„).
Как было указано в главе V, |
близость значений а 0 |
и а* в этом смысле может быть |
гарантирована, если |
204 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ с х о д и м о с т и
функция Дэмп (а) равномерно по параметру а приближает функцию Д (а). В самом деле, если
sup I R (а) — Дэмп (а) | < е,
|
|
а |
|
|
|
|
|
|
то |
|
R (а*) — ДЭМп (а*) < |
е, |
|
(10.1) |
|||
|
|
ДЭмп Ю |
— R Ю |
< |
е. |
|
(10.2) |
|
Кроме |
того, |
поскольку а 0 и |
а* — точки минимума |
|||||
соответственно |
функций |
Д (а) и Дэмп (а), |
то |
|
||||
|
|
Д (а0) < |
Д (а*), |
|
|
(10.3) |
||
|
|
■^эмп (а*) < |
І ? Э М П Ю - |
|
(10.4) |
|||
Из (10.1) — (10.4) непосредственно вытекает, |
что |
|||||||
Или, иначе, |
Д (а*) — Д (а0) <1 2е. |
|
|
|||||
|
|
|
|
|
|
|
||
|
Д (а‘) — Д (а0) < |
2 sup | Д (а) — Дэмп (а) |. |
(10.5) |
|||||
Таким |
образом, если |
отклонение |
функций |
Дэмп (а) |
||||
и Д (а) при всех значениях |
параметра не |
превосходит |
8, то значение истинного риска Д (а) в точке эмпириче ского оптимума а* не более чем на 2е отклоняется от минимального. Если же максимальное по а уклонение риска Д (а) и его эмпирической оценки велико, то, вообще говоря, замена истинного минимума эмпирическим может привести к большим ошибкам.
В задаче обучения распознаванию образов функция Q (z, а) в функционале Д (а) имеет специальный вид. Здесь каждый элемент z есть пара х, ю, где х — описание ситуации, а © — указатель класса, к которому в действи тельности относится эта ситуация. Обычно число классов невелико, т. е. со может принимать конечное небольшое число значений 0, 1, . . к. Каждому значению параметра а соответствует решающее правило F (х, а), причем функция F (х, а) принимает те же дискретные значения, что И (О.
В качестве критерия Д (а) обычно берется вероятность неправильной классификации с помощью правила F (х,а). Это значит, что определена функция штрафа
0 при (а = F,
Ф (CD, F) = {1 при © ф F
§ 1. ОБ УКЛОНЕНИИ МИНИМУМА ЭМПИРИЧЕСКОГО РИСКА 205
и функционал R (а) задан в виде
R (а) =■ J Ф (со, F (X, а)) dP (х , со).
Функция Ф (со, F) есть характеристическая функция множества
Та. = {х, со: F (X, а) ф со}.
Соответственно функционал R (а) при каждом значении а есть вероятность события Таі
R (а) = Р {F (х, со) Ф со} = Р (Гя).
Эмпирическая оценка Дэмп (а) равна частоте ѵ (Га) появлений этого события в обучающей выборке, т. е. частоте ошибок на материале обучения. Пусть теперь параметр а принимает всевозможные допустимые значе ния а 6Е Q. Соответствующие события Та образуют класс событий S. Равномерная близость функций Л (а) и R mn(a) означает равномерную близость частот и вероятностей событий Та по классу S.
Применяя формулу (10.5) в данном случае, имеем
R (а) - R Ы < 2 sup I у (Гв) - Р (Та) |. (10.5') xaes
В более общем случае проблема равномерной сходи мости функций ЛЭмп (а) и Л (а) также может быть све дена к равномерной сходимости частот к вероятностям в определенном классе событий (§ 2 главы XIII).
Перейдем теперь к выводу условий, которым должен удовлетворять класс событий S для того, чтобы выполня лась равномерная по классу сходимость частот появления событий к их вероятностям. Существенно, что при опре деленных условиях удается получить оценку равномерной близости частот к вероятностям, не зависящую от рас пределения Р (X, со), которое обычно неизвестно, и опре деляемую только внутренней структурой класса S. Эта оценка не содержит произвольных констант и позволяет эффективно оценить близость эмпирического оптималь ного решающего правила к истинному для заданного класса решающих правил при фиксированной длине обучающей последовательности.
206 ГЛ, X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ с х о д и м о с т и
§2. Определение равномерной сходимости частот
квероятностям
Согласно классической теореме Бернулли, частота появления некоторого события А сходится (по вероят ности) в последовательности независимых испытаний к вероятности этого события. Выше мы убедились, что возникает необходимость судить одновременно о вероят ностях событий целого класса S по одной и той же вы борке. При этом требуется, чтобы частота событий схо дилась к вероятности равномерно по всем событиям клас са S. Точнее, требуется, чтобы вероятность того, что максимальное по классу уклонение частоты от вероят ности превзойдет заданную сколь угодно малую поло жительную константу, стремилась к нулю при неограни ченном увеличении числа испытаний.
Оказывается, что даже в простейших примерах такая равномерная сходимость моясет не иметь места. Поэтому хотелось бы найти критерий, по которому можно было бы судить, есть ли такая сходимость или же ее нет.
В этой главе будут найдены достаточные условия такой равномерной сходимости, не зависящие от свойства распределения, и дана оценка скорости такой сходимости. В главе XI мы введем необходимые и достаточные усло вия равномерной сходимости частоты к вероятностям. Эти условия уже будут зависеть от свойств распределения.
Пусть X — множество элементарных событий, на ко тором задана вероятностная мера Р (х). Пусть S — неко торая совокупность случайных событий, т. е. подмножеств пространства X, измеримых относительно меры Р (х) (S включается в а-алгебру случайных событий, но не обя зательно совпадает с ней). Обозначим через X (I) про странство выборок из X длины I. Тот факт, что выборка является повторной, т. е. получена в последовательности независимых испытаний при неизменном распределении, формализуется заданием вероятностной продукт-меры на X (I) из условия
Р Ы г X |
. . . X А,] |
= Р (AJ . . . Р (At), |
|
где А — измеримые подмножества X. |
события |
||
Для каждой |
выборки |
X 1 = хх, . . ., ж, и |
|
определена частота выпадения событий А, |
равная |