Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 221
Скачиваний: 4
§ 6. ВЫВОД ДОСТАТОЧНЫХ |
УСЛОВИЙ |
223 |
Как известно, последняя сумма превосходит Ѵ2, |
если |
|
2 |
|
2 |
только 1^>~.Возвращаясь к (10.18), получим для |
—: |
|
6 |
|
в |
р {ps(*і,..*«) > -г} > $ 4 - d p ^ |
= |
|
Q |
|
|
= -Y'P{ns (x1, ..., жг) > в), |
||
что и требуется.
Утверждение б) непосредственно следует из того, что если
I ѵ' (Л; жх, ..., Xі) — ѵ" (А; ж/+1, ..., ж2г) | > е,
то
либо
|ѵ'(Л; хи . . . , х І) — Р(А) |> - | - ,
либо
|ѵ"(Л; жг+1, ...,ж 2г) — Р ( Л ) |> - |- .
Учитывая, что при этом полувыборки и Х2 независимы, получаем:
Р {sup I v' (А; хъ ..., Ж;) — V' (Л; ж/+1, ..., ж2г) | > е} <
А
< 1 — ( і — р |sup I Р (Л) — V' (А) хъ ..., жг) ( > -|-J^ X
X ( l — Р jsup I Р {А) — v' {А; жг+1, . . жаг) | >
и поэтому
Р {ps (хіі ■• |
г)> е } : |
2Р [ns (хъ ..., жг) > -|-j — Р I ns (жх, . . ., жг) >
Лемма доказана.
§ 6. Вывод достаточных условий равномерной сходимости частот к вероятностям по классу событий
Итак, задача может быть сведена к оценке равномер ной близости частот в двух последующих полувыборках. Схему сравнения частот выпадения событий в двух полу выборках можно представить себе так. Берется выборка
224 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ с х о д и м о с т и
двойной длины X 21 и затем делится случайным образом на две полувыборки равной длины. Будем считать, что вы борка X 21 зафиксирована. Еісли два события Ау и А 2 не различимы на выборке X 21, т. е. всякий элемент этой вы борки, принадлежащий Ау, принадлежит А 2 и наоборот, то частоты выпадения этих событий на всякой подвыбор ке одинаковы. Поэтому для оценки максимального укло нения частот достаточно из каждой группы неразличимых событий взять по одному. Число таких событий будет ко нечно и равно индексу As (ху, ..., х2Х) системы S относи тельно выборки Х у , . . . , Х ц . Рассмотрим одно из таких со бытий А и, по-прежнему считая выборку X 21 фиксирован ной, разобьем ее случайно на две равные полувыборки и оценим уклонение частот этого события в двух полувыборках. Эта схема равноценна схеме с невозвращаемыми ша рами, а поэтому (см. [64])
|
|
'~'тУъ1-т |
Р{|ѵ'(Л; хи ■. .,хі)—ѵ"(А; x l+1, .. . , ^ г ) І > е}= 2 |
||
к: |
к |
т —к |
{ 1 |
I |
|
где т — число элементов А в выборке X 21, к — число эле ментов А в первой полувыборке.
Как показано в приложении к главе X, правая часть равенства может быть оценена сверху:
|
г<к ril-k |
|
|
|
|
2 |
°т 1-т |
;3ехр [—е2 (Z — 1)], |
|||
|
|
|
|||
к |
|
СЬ |
|
||
|
|
|
|
||
|
|
|
|
т — к |
|
|
Ч |
І |
т |
I |
> е } . |
Таким образом, |
|
|
|
||
Р {|ѵ (А, Ху, ..., |
Xi) |
V |
(А, |
Хі+у, ..., х%і) I |
|
|
|
|
|
> |
е} < 3 ехр [— е2 (I — 1)]. |
Вероятность того, что хотя бы для одного события А, из числа выбранных, окажетсяI
I V (А, Ху, ..., Xi) |
V (А, Хі+у, ..., х2і) I |
6, |
§ 6. ВЫВОД ДОСТАТОЧНЫХ УСЛОВИЙ |
225 |
по теореме о сложении вероятностей оценивается:
Р {sup IV7 (Л; х1:.. .,xt) — ѵ" (А; х м , ..., х2І) | > |
е} < |
ASS |
|
< 3AS { x i |
, х2І) е”£'(г' 1). |
В свою очередь по определению функции роста
As (%, Х21) < ms (21)
и, таким образом,
Р {sup I ѵ'(А; хъ ..., х2і) — ѵ"(Л; хиъ ..., жаг)| > е}<
AeS |
< 2ms (21) |
Очевидно, что если функция ms (Г) растет лишь степенным образом, то правая часть неравенства стремится к нулю при I —*■оо. Это и дает достаточные условия равномерной сходимости (по вероятности).
Перейдем к строгой формулировке и доказательству достаточных условий.
Теорема 10.2. Вероятность того, что частоты всех событий класса S уклонятся от соответствующих вероят
ностей в эксперименте длины I более чем на |
е, |
удовлетво |
||
ряет неравенству |
|
|
|
|
P{ns (хг, ..., Хі) |
е} |
bms (21)е |
4 |
. (10.19) |
Следствие. Для того чтобы частоты событий клас са S сходились (по вероятности) к соответствующим ве роятностям равномерно по классу S, достаточно сущест вования такого конечного п, что
ms (п) Ф 2п.
Д о к а з а т е л ь с т в о . |
В силу с основной леммы |
достаточно оценить величину |
|
Р jps (* !,..., х2і) > - х } = ^ |
ѳ (Ps (хъ • • •. Чі) — r ) dP ^ 2^' |
x m |
|
Рассмотрим отображение пространства X (21) на себя, получаемое некоторой перестановкой Гг элементов
8 В. Н. Вапник, А. Я. Червоненкис
226 |
г л . X. д о с т а т о ч н е й : |
у с л о в и я р а в н о м е р н о й с х о д и м о с т и |
|||
последовательности X 21. |
В |
силу симметрии определения |
|||
продукт-меры имеет место следующее равенство; |
|
||||
|
J j ( X 2l)dP (X21) = |
J f(TiX*l)d P (X 21) |
|
||
|
X Іи) |
|
|
хш) |
|
для любой интегрируемой функции / (ж). |
|
||||
|
Поэтому |
|
|
|
|
i5 |pS (л?!, . . .,Х2і ) У ~ I = |
|
|
|||
|
|
(21)! |
’ (T.X21) - - | - |
|
|
|
|
i=l |
|
||
|
|
|
dP(X2!), |
(10.20) |
|
|
- |
j |
|
||
|
1 Щ |
|
|||
|
|
x m |
|
|
|
где сумма берется по всем (2/)! перестановкам. |
|
||||
|
Заметим, прежде всего, что |
|
|||
Ѳ^Ps (X2) ---- |- j |
== |
|
|
|
|
= |
ѲИ р I ѵ' (А; |
хъ ..., xt) — v" ('a ; хм , . . ,,x 2l) | > — j = |
|||
|
= sup Ѳ(J v' (Л; xu ..., Xj) — v" [A; xl+1, ..., x2l) | — |
* |
|||
|
Aes |
|
|
\ |
|
Очевидно, что если два множества А ±и А 2 индуцируют на выборке xlt . . . , Х і , жг+1, . . . , x2i одну и ту же подвыборку, то справедливо
V' (Лі; |
TtX 2‘) = |
V' (Л2; |
ГгХ20, |
ѵ" (Лі; |
ГгХ2‘) = |
ѵ" (Л2; |
ТіХ 21) |
и, следовательно, |
|
|
|
РM X « ) = р Аг ( Т і Х 2' )
для любой перестановки Tt.
Иными словами, если два события эквивалентны отно сительно выборки Хі , ..., х21, то уклонение частот для этих событий одинаковы при всех перестановках Tt. Поэтому, если из каждого класса эквивалентности взять по одному
i g. ВЫВОД ДОСТАТОЧНЫХ УСЛОВИЙ |
227 |
Множеству й Образовать конечную систему S ' , то
sup рд (Т{Х 21) = sup рА (Т{Х 21).
А.S S |
А {=Я' |
Число событий в системе S' конечно и было обозначено As ( хг , . . . , х ц ). Поэтому, заменяя операцию sup суммиро ванием, получаем
supO \ул ІТ,Х'! ) — A j = sup Ѳ\уА [І\Х*1) — |
. у |
< 2 |
|
A<=S' ' |
' |
Эти соотношения позволяют оценить подынтегральное выражение в (10.20):
(20!
(2(|! 2 e [ p W ” ) - - f ] =
Ш
7=1
г (2()! |
|
РA |
( ^ ) - - f ] |
і=1 |
|
< 2 |
(20! |
AeS' |
|
Выражение в квадратных скобках означает отношение числа порядков в выборке (при фиксированном составе), для которых
| ѵ '( Л ) - Ѵ И ) | > _ £ - ,
к общему числу перестановок. Легко видеть, что оно рав но
где тп равно числу элементов выборки хг, ..., х2і, принад лежащих А.
8*
228ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ с х о д и м о с т и
Вприложении к этой главе показано, что
|
|
|
|
|
6* Д-Р |
|
|
|
|
|
|
|
|
|
Г < 3 е |
4 . |
|
|
|
|
|
||
т' |
Таким образом, |
|
A 2S S ' |
|
|
= |
|
|
|
||
(21)1 |
|
' |
^ |
е» (1-1) |
|
|
|
||||
я' г i2= l |
вL[р» (Г,Xм) - - ! - J] < |
з г |
)* |
_ |
Ea (l-1) |
||||||
|
|
|
= 3AS (Xi, ..., хг{) e |
sa(i- l) |
3ms (21) e |
||||||
|
|
|
|
|
|
|
|
4 |
|||
Подставляя эту оценку в интеграл (10.20), имеем |
|
|
|
||||||||
|
|
|
, |
|
-1 |
3ms (21) е |
г2(1~1) |
|
|
||
|
|
Р jps (хи .. ., х2і) > - |- | < |
4 |
, |
|
|
|||||
откуда в силу основной леммы |
|
|
|
|
|
|
|||||
|
|
|
Р (ns (хг, . . ., xt) )> е} ^ |
6ms (21) е |
еаД -р |
|
|
|
|||
|
|
|
4 |
|
|
|
|||||
|
Теорема доказана. |
|
с л е д с т в и я . Пусть |
су |
|||||||
|
Д о к а з а т е л ь с т в о |
||||||||||
ществует такое п, что |
|
|
|
|
|
|
|
|
|||
|
|
|
|
ms (п) ф 2” . |
|
|
|
|
|
||
Как было доказано в § 4, если только |
функция |
ms(n) не |
|||||||||
равна 2”, |
то при І'ф п справедливо: |
|
|
|
|
|
|||||
|
|
|
^ Х |
|
;(«-1) |
|
|
|
|
|
|
Поэтому: |
^ т Ь т у г |
|
|
|
|
|
|||||
|
lim Р (я5 (хъ ..., х,) > |
е} < |
|
/олп- і __ÜiLiL |
= 0 , |
||||||
|
9 lim у -—.-гг е |
4 |
|
||||||||
т. е. имеет место равномерная сходимостц по вероятности. Полученное достаточное условие не зависит от свойств распределения (единственное требование — это измери мость функций я и р), а зависит от внутренних свойств
системы S.
