Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 212
Скачиваний: 4
§ 2. УКЛОНЕНИЕ ЧАСТОТ В ДВУХ ПОЛУВЫБОРКАХ 271
Оно равно
2^ т’ ^ 2l-m
кС21
где т — число выпадений событий А в полной выборке, а к — число выпадения событий в первой полувыборке. Оно пробегает значения, удовлетворяющие неравенствам
max (0 , т — I) ^ к ^ min (т, I),
I к т — к
Обозначим через б величину
j j - V i j n + і){21 — т А- \)-
Теперь можно воспользоваться неравенством (П.5), вы веденным в приложении к главе X:
Г 2 ехр |
— (z-f-i) (6^3 — 1) - |
|
(т -J- 1) (2/ — т ~\~1) |
||
|
Подставляя сюда значение б, получимі
Г ^ 2 сх и Г |
е2(г + 1) I |
1 + 1 |
1 |
||
^ |
Р L |
4 |
^ (т + 1)(2/ — |
гп+ 1) J |
|
(отметим, что эта оценка слабо зависит от т, что и оз начает «равноправие» событий).
Правая часть неравенства; достигает максимума при т = 0 или т = 21. Поэтому
|
|
|
еЧЧ-І) . 1+1 |
|
|
|
|
Г < 2 е 4 |
ui ^ |
|
|
откуда при |
0 |
< е < 1 , |
учитывая, что всегда Г < |
1 , |
|
|
|
|
_ — |
|
|
|
|
|
Г < 4 е |
4 . |
|
Возвращаясь |
теперь к |
(12.4), |
получаем |
|
|
2 |
(2/)! |
|
|
е8/ |
|
2 Ѳ |#А(7>2г) — e|l<4A S(a;1, ..., хгі) е |
. |
||||
Aes u |
t=i |
|
|
|
|
272 ГЛ. X II. ОЦЕНКИ ОТНОСИТЕЛЬНОГО УКЛОНЕНИЙ
Переходя к (12.2), получаем искомую оценку. Теорема доказана.!
Замечание." Точно так же можно получитъ оценку
|
Р ( |
sup |
lv' H ) r v.-(d)L > |
el < |
4ms {21) e |
** . |
(12.5) |
||||
|
Г |
“ |
/ ѵ м + Л . |
|
j |
|
|
|
|
|
|
Отличие состоит лишь в том, что теперь |
|
|
|
|
|||||||
|
|
|
, |
, Т т + |
1 |
|
|
|
|
|
|
|
|
|
8 = е У |
- я - - |
|
|
|
|
|
||
Подставляя эту величину в (П. 5), получаем |
|
|
|
||||||||
Г < |
2ехр ^ |
- ( Н |
і)_____ / ъЧ (т + |
1) |
, \ ] |
|
|
|
|||
1) (2 / • |
■т + 1 ) \ |
2 |
|
1)\ |
|
|
|
||||
|
|
{т |
|
|
|
|
|||||
|
|
= 2 ехр Г— |
гЧ (I + |
1) |
|
|
I + |
1 |
|
|
|
|
|
2(2/ — /и + |
1 )”* |
( т + |
1)(2/ — т + |
1) |
|||||
|
Первая часть неравенства |
достигает |
максимума |
при |
|||||||
т = 0 , откуда |
|
|
|
|
|
|
|
|
|
||
и, |
далее, |
при |
0 < е |
1, учитывая, что всегда |
Г ^ 1, |
||||||
|
|
|
|
Г < 4 е |
_еЧ |
|
|
|
|
|
|
|
|
|
|
|
4. |
|
|
|
|
|
|
Далее, повторяя рассуждения теоремы 12.1, получаем требуемую оценку.
§ 3. Оценка равномерного относительного уклонения частот от вероятностей
Переход от оценок относительного уклонения частот в двух полувыборках к относительному уклонению час тот от "вероятностей ведется по той же схеме, что и при доказательстве основной леммы § 5 главы X. Трудность
здесь состоит в том, что нормирующие делители Y Р (-4)
и Y v {А) (1 — V {А)) могут сильно отличаться при малых Р {А) для «наихудшего» события в классе. Поэтому вы водится лишь односторонняя оценка, которая, как уже указывалось, фактически касается только событий, вѳ-
274 ГЛ. X II. ОЦЕНКИ ОТНОСИТЕЛЬНОГО УКЛОН ЕН ИЯ
при условиях |
|
|
|
|
|
|
||
|
|
ѵ' (А*) < |
Р (.А*) - |
|
г Ѵ Р (Л*), |
|||
|
|
ѵ" (4*) > |
Р (А *); |
і3 (4*) > |
е2. |
|||
Для |
этого найдем минимум функции |
|
||||||
|
|
|
гр __ |
|
У |
|
|
|
|
|
|
|
|
Ѵ х+ У + с |
|
||
в области О <і а ^ х ^ |
1, 0 < |
у |
с > 0 . Имеем |
|||||
|
2 ж + |
2 |
2/ + с |
|
|
|
3 |
1 |
дТ |
|
ат_ _ |
|
- Т х ~ Т у - с < 0 , |
||||
(* + |
2/ + |
> 0 , |
|
|||||
дх |
с)8/г |
|
ду ~~ |
(я + |
У + с)'1' |
|||
следовательно, Т достигает минимума в допустимой об ласти при X = а, у = Ъ.
Поэтому величина р будет оценена снизу, если в (12.8)
ѵ' (А*) заменить на Р (И*) — е)f Р (И*), а ѵ" (А) заме нить на Р (А*). Таким образом
. |
е У 2РІА*) |
t*> - А"' |
- ■ - =Г • |
У2 Р ( Л * ) - 8 VР (/!*) + —
Далее, поскольку Р (И*) > е2 и Z |
, имеем |
|
р > |
8 У 21' (/1* ) |
= 8. |
|
||
/ 2Р(А*) — е2 + е2
Таким образом, при выполнении Qlt а также условий
Р (А*) < ѵ" {А*) и 1^> -К- выполняется и <?2.
Заметим, далее, что вторая полувыборка выбирается
независимо от первой и, как известно, при I |
. час- |
|
I* ( . т ) |
тота выпадения события И с вероятностью, большей 0,25, превышает Р (А).
Поэтому событие (12.7) выполняется при условии Q± с
вероятностью, большей Ѵ4, если только Значит,
и событие (?2 выполняется при этих условиях с вероят ностью, большей У4.
§ 3. УКЛОНЕНИЕ ЧАСТОТ ОТ ВЕРОЯТНОСТЕЙ |
275 |
Итак, при — выполняется неравенство
р (<?2) > 4 - р т -
Но вероятность события Qz оценена выражением (12.5).
Таким образом,
_ т
Р (Qi) 16ms (21) е 4
при I . Но при I ^ -^- оценка тривиальна, так как
Р(Qi) всегда не превосходит 1. Теорема доказана.
Взаключение приведем простейший пример, показы
вающий принципиальную односторонность оценок виді
( 1 2 .1 ).
Пусть X — интервал (0, 1) и на нем задано равномер ное распределение. Система S состоит из всевозможных множеств Л, каждое из которых есть интервал (а, Ъ) та кой, что 0 а <С. Ъ 1; при этом пусть мера каждого из А больше нуля. Покажем, что неравенство
|
|
|
sup |
< е |
|
|
|
|
Aes |
|
|
не выполняется ни при каком I > |
0 и ни при каком е Д> 0. |
||||
|
Действително, |
пусть хг , . . . ,xt — выборка. Рассмот |
|||
рим интервал А* |
= (хг — б, х± + |
б) при б 0. Частота |
|||
V |
( Л * ) |
не меньше 1 /I, вероятность при достаточно малых |
|||
6 |
0 |
равна |
Р (А*) = 26. |
||
Теперь |
при |
||||
|
|
||||
0 < 6 < [2/ (1 + 8) ]
получаем
V (л*) — р ( л * )> е Y Р (л*).
В то же время в главе X было показано, что равномер ная сходимость к нулю ненормированных уклонений имеет место. В силу теоремы 12.2 сходимость к нулю односторонних нормированных уклонений в этом при мере также имеет место.
