Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 218
Скачиваний: 4
256 ГЛ. XI. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ
обязательно делятся точно пополам при делении полной выборки X 1, но при достаточно больших I (а значит, и г) это условие почти всегда выполняется достаточно точно. Приводимое дальше формальное доказательство позволя ет строго учесть все сделанные здесь допущения и прибли жения.
4. |
Д о к а з а т е л ь с т в оу т в е р ж д е н и я б). |
|||
Итак, |
пусть |
я5 (I) |
|
|
|
Н т |
с > 0. |
||
|
1—>СО |
I |
|
|
При доказательстве достаточных условий (§ 6 главы X) |
||||
было установлено, что |
|
|
|
|
Р{рЯ(п1, . . . , Жгг)> 2 0 } = |
1і уг |
$ |
[ S e ^ x V s ö j d P C X 2'), |
|
|
|
‘ |
xW |
1 |
|
|
|
|
(11.18) |
где Ті — всевозможные перестановки последовательности
Ху, |
..., х21. Обозначив |
через К (хг, |
..., х2І) подынтеграль |
|||
ное выражение, сократим область интегрирования: |
||||||
P |p s (x1, . . ., х2і) > -|- j |
> |
|
|
|
|
|
|
> Щ і - |
5 |
|
|
|
K ( x y , . . . , x 2l)dP(X21). |
|
1Ң2A®(x,t . |
. |
^ |
c |
|
|
|
|
21 |
|
^ |
Y |
|
Оценим величину К, полагая, что |
|
|||||
|
lga As (xi,. . . , |
ж2г) |
^ |
с |
||
т. |
е. |
21 |
|
|
' >~2' |
|
|
|
|
|
|
||
|
As {ху, ..., |
х21) > |
|
2е'. |
||
|
При этом выберем -ft Д> Q(с) |
|
0 так, чтобы в соот |
|||
ветствии с леммой 3 при достаточно больших I существо вала подвыборка Хп длины п ]> ql, на которой система S индуцирует все возможные подвыборки (т. е. As (Ху, ...
..., хп) =2"), и положим б (с) = • Примем, что п |
I, |
и заметим, что числа q и б не зависят от I.
s 4. ДОКАЗАТЕЛЬСТВО НЕОБХОДИМОСТИ |
257 |
Сгруппируем перестановки Tt так, что в каждую груп пу Rs входят перестановки, соответствующие одному и тому же разбиению на первую и вторую^ полувыборку. Очевидно, что
Р ® (7Ѵ *і, • • -I *8|) =
=sup |v '(4 ; Tr xu ..., xt) — V(A\ Тѵ хь ..., x2l)\ Aes
зависит только от Rs и в пределах [каждой группы постоян на. Поэтому
К = —(—2® ІР8 (^s’ жі» • • •>*az) — 26]. °аг. s
Сумма берется по всем возможным разбиениям хѵ . . .
. . ., Xzi на первую и вторую полувыборки.
Пусть, далее, Х п — та самая подвыборка длины п, на
которой S |
индуцирует все возможные подвыборки. Обоз |
|||
начим ее |
дополнение в |
X 21 через |
X (длина X |
равна |
21 — п). |
|
полностью |
задано, если |
заданы |
Разбиение Rs будет |
||||
разбиение |
R h подвыборки Х п на часть, попадающуюся |
|||
первую полувыборку, и часть, попадающую во вторую полувыборку, и соответствующие разбиение R j подвы борки X .
Обозначим для данного разбиения число элементов из Х п, попадающее в первую полувыборку, через г и пред ставим К (X1) в следующей форме:
К = —^21 г к і |
І Р { R k R j '* х ъ •••> х ы ) — 26]. |
|
|
Здесь суммирование'по г ведется в пределах 0 |
г |
п. |
|
Суммирование по к ведется по всем разбиениям Хп6таким, что к первой полувыборке]^относится точно г элементов из"Х", суммирование по / — по всем разбиениям X таким, что к первой полувыборке относится I — г элементов из X .
Для фиксированного к, т. |
е. разбиения подвыборки |
Х п, иайдется^такое А (к) е* S, |
что все элементы хи отно |
симые этим разбиением к первой полувыборке, принадле жат А (к), а все элементы x t, отнесенные ко второй полувыборке, не принадлежат А (к). Это следует из того,
9 В. Ң. Вапник, А. Я. Червонещщс
258 ГЛ. XI. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ
что |
S индуцирует |
на Х п все |
подвыборки. При этом |
|||
ps (RhRj; X lf |
. . ., |
X 2l) > ps (A |
(k); R hRj; хг , |
. . . ,x2l) |
||
и, |
следовательно, |
|
|
|
|
|
|
к > - i - S |
S |
2 |
Ѳ[ps (А (к); В Д ; ^ , ..., x2l) - |
25]. |
|
|
^ 2 1 r |
Je |
j |
|
|
|
Пусть, далее, P (к) — число элементов подвыборки X, принадлежащих"^ г(к), и t — число элементов подвыборки X, принадлежащих А (к) и отнесенных разбиением R j к первой полувыборке. Тогда для фиксированных г, к, j
\'(А(к)і хъ ..., xt) = |
, |
|
||
у"{А (к); хиі, ..., x2l) = |
, |
|
||
I ѵ' (А (к); хъ ..., хі) — ѵ"(А (к); хм , ..., х21) | = 1г + 2*— — |
||||
Соответственно |
|
|
I г -j- 21—р [ |
|
|
1, |
если |
> 2 5 , |
|
Ѳ[ps (А (к); хъ ..., х2{) — 25] |
|
|
► № |
|
л |
если |
I **“Ь 2^ — Р I |
о ч |
|
|
О, |
■—2__— — |
25. |
|
Наконец, сгруппируем разбиения Rj, соответствующие одному и тому же t (при фиксированных г л к). Число
таких |
разбиений равно |
а |
|
|
|
|
|
|
|
f\t |
/nl—T—t |
|
|
|
|
|
|
|
*Wl-n-p(/c)« |
|
|
|
|
Тогда оценка для К примет вид |
|
|
|
||||
|
V |
^ ^ |
XI XI |
(il—T—t |
|
|
|
|
л |
|
2л Za |
*^2г-п-р(*с). |
|
|
|
|
|
°2І г к t |
|
|
|
|
|
После |
элементарных преобразований получим |
|
|||||
|
V |
/^Г /-г/-Г |
V 1 |
/і( |
f t l - r - t |
|
|
|
°n°2!-n |
V |
ril—2 |
’ |
(11.19) |
||
|
71 ^ Z l |
^2? |
Z j |
Z i |
|||
|
r |
й |
t |
° 2f-n |
|
|
|
где суммирование по t ведется в пределах, задаваемых выражением
| / + 2 t - p l |
(11.20) |
|
§ 4. ДОКАЗАТЕЛЬСТВО НЕОБХОДИМОСТИ |
259 |
Положим теперь0 |
8 |
и рассмотрим величину К', |
|||
отличающуюся от |
правой |
части |
(11.19) |
лишь иными |
|
пределами суммирования, |
|
|
|
||
Г, |
р Т р І - Г |
. |
p t p l - r - t |
|
|
|
|
1 V |
°P(kVv 2l-n-p(k) |
||
Л |
Z j |
p l |
p r Z j |
p l - r |
' |
|
r |
к |
|
l-n |
|
где г и t пробегают значения, удовлетворяющие следую щим неравенствам:
|
п |
< еп , |
(11.21) |
|
|
г — ~2 |
|||
t |
р(к) ( 1 - г ) |
<^81. |
(11.22) |
|
21- |
|
|||
|
|
|
|
|
При r u t , удовлетворяющих (11.21) и (11.22), автомати чески выполняется (11.20). Действительно, при этом
r | 2 l - f . |
і Г л |
. |
2р |
[j |
п |
\ |
|
|
----- 1— |
|
+ |
|
|
|
|
»)] |
|
|
- 2 d - P\ > - r [ i r - B(n + 2l+wz: |
|
||||||
Поскольку было принято, что] ql<C.n<^l, 6 = |
, е |
, |
||||||
то
Так как область суммирования в выражении для К ' вкла дывается в область суммирования (11.19), то
|
К > К '. |
|
Далее, для всякого г] > 0 найдется |
10, зависящее |
|
только от ц и д, такое, что для всех Z> |
10 |
|
2 |
С;' т :П> 1 - П |
(11.23) |
г |
°21 |
|
(суммирование ведется по г, удовлетворяющим (11.21)) и
2 |
Ctp(S Lp > 1 - 4 |
(11.24) |
t |
° 2 l - n |
|
(суммирование ведется по t, удовлетворяющим (11.22)).
9*
