Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 225
Скачиваний: 4
§ 8. ПРИМЕРЫ И ДОПОЛНИТЕЛЬНЫ Е ЗАМЕЧАНИЯ |
235 |
при любом распределении имеет место равномерная схо димость. Поэтому настоящее замечание означает, что при ms (Z) = 2г без сведений о распределении Р (х) невозмож но оценить скорость равномерной сходимости.
В заключение этого параграфа докажем теорему.
Теорема 10.4. Допустим, что все одноточечные мно жества пространства X измеримы и задана система со бытий S такая, что
7?lS (I) = 2».
Тогда по заданным I, е можно указать такое распределе ние Р (X), что с вероятностью 1 будет выполняться не равенство
sup IV (Л) — Р (Л) I > 1 — 8.
Д о к а з а т е л ь с т в о . Выберем любое целое число п, превышающее I / е. Поскольку ms (п) = 2п, можно ука зать п точек
..., хп
так, что события А ее S индуцируют на этой последова тельности все подпоследовательности. Обозначим через Хп конечное множество, состоящее из точек хх, ..., хп.
Определим распределение Р (х) следующим образом: распределение Р (х) сосредоточено в точках хх, ..., хп, причем все они равновероятны; иными словами,
|
0, |
если А не содержит ни одной точки из X, |
|
1 |
. |
Р{А) = |
—, если А содержит только одну точку, |
|
|
|
|
|
1, |
если А содержит все точки Х п. |
Пусть теперь дана выборка хх, ..., х х. С вероятностью 1 эта выборка состоит лишь из элементов X". Рассмотрим конечное множество X ', состоящее из всех тех точек мно жества Х п, которые не вошли в выборку. Очевидно, что их число не меньше чем п — I.
Поскольку
Д8(*і, 2",
найдется событие А 0 ge S, которое содержит все точки из множества X ' и ни одной из выборки хѵ ..., х\. Это
236 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ сходимости
значит, что
V ( Л о ) = 0
ив то же время
Всилу выбора числа п, получаем
|ѵ (Л 0) - Р ( Л 0) 1> 1 — е
и, следовательно, с вероятностью 1
sup IV (А; хъ . . хі) — Р (А) | > 1 — е.
A e s
§ 9. Приложение к главе X
Оценим величину
/ік ril—k
2S ^ т У 2І- т
к С2І
где к пробегает значения, удовлетворяющие неравенствам
к |
т — к |
> 8 |
в шах (0,т — I) ^ к ^ mm (m, l) |
|
I |
I |
|||
|
|
или, что то же самое, неравенствам
вI
к — - > - у и max(0,m—l)^.k^.mia (т, I),
аI и m ^ 21 — произвольные положительные целые числа. Разложим Г на два слагаемых:
Г= Гі + Г„
/~ік ril-k l-m
г - 3
к
rik sil^k
г*= 2
с *1
___si |
m |
при к > |
+ — , |
при , . m |
el |
Введем обозначения:
г*к пі-к
ѵпУъІ-т
/>(*) = Г1 (II.1) °21
q (к) = |
р ( к ± 1) |
(m — к) (I — к) |
(П:2) |
|
p(k) |
{к “I- 1) {I 4” к ~b 1 |
|||
|
|
|
5 |
9. |
ПРИЛОЖЕНИЕ К ГЛАВЕ X |
237 |
|||
Д Н Я |
|
|
|
|
|
|
|
|
max (0, то — I) |
< |
к < |
min (то, I). |
|
||
Далее |
обозначим |
|
|
|
|
|
|
|
S = |
min (то, I), |
Т = max (0, то — I), |
|
|||
|
|
|
|
|
S |
|
|
|
|
|
« (А) = |
2 |
(О- |
|
|
|
|
|
|
i |
/С |
|
|
Очевидно, |
что имеет |
место соотношение |
|
||||
|
|
S |
S - 1 |
S - 1 |
|
||
« (а+1) = |
2 |
р W = 2 ^ |
^ = 2 р w ? |
(П.З) |
|||
|
|
і = / с + 1 |
г = /£ |
i= J c |
|
||
Далее из (П.2) непосредственно следует что при і < /
7 (і) > 7 (/'),
т. е. g (і) монотонно убывает. Поэтому из (П.З) следует неравенство
S - 1 S
« (А + 1) = 2 Я (0 7 (0 < 7 (А) 2 т*(г)
г=й і=/£
и, по определению а (к), имеем
а (к + 1) < а (к) q (к).
Применяя последовательно это соотношение, получим для произ вольных к и /, удовлетворяющих условию Т ^ / < к < S,
к - 1
|
« (А) < |
а (/) Д g (г). |
|
||
|
|
|
і=У |
|
|
Наконец, поскольку |
а (;') ^ |
1, |
fc-i |
|
|
|
|
|
|
(П.4) |
|
|
а (А) < |
Д 7 (0. |
|
||
|
|
|
і=У |
|
|
где і — любое целое |
число, |
меньшее чем |
|
||
Положим |
|
|
то — 1 |
|
|
|
t — к — |
’ |
|
||
тогда |
2 |
|
|||
то + 1 |
|
|
то — 1 |
|
|
|
t |
|
— г |
||
7 lft) = |
2 |
|
|
2 |
|
то + 1 |
t |
|
то — 1 |
+ * |
|
|
—2 |
|
2 |
||
238 ГЛ. X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ сходимости
При этом, |
очевидно, пока Т < |
к < |
S , |
|
|||
|
|
|
[ m + 1 |
m — 1 |
|
||
|
|
I і I < min I— 2— |
’ |
1 ~ — 2— |
|
||
Для |
аппроксимации |
q (к) исследуем функцию |
|
||||
|
|
/(0 = |
а — t |
Ъ— < |
|
||
|
|
і + |
а ' |
b + t ’ |
|
||
считая, |
что а и Ъ больше |
нуля. |
|
|
|||
При |
I |
г I < min (а, Ъ) |
|
|
|
|
|
ln F (г) = In (а — і) + ln (b — г) — ln (г -f а) — ln (t + 6). |
|||||||
Далее, |
|
|
ln F (0) = |
0, |
|
||
|
|
|
|
||||
dt ■ln/1 |
1 |
|
1 |
|
1 |
- |
|
■t ' |
b — t |
> t 4- а'+ t + ь] |
|||||
|
|
|
|
|
|
Г 2a |
2b 1 |
|
|
|
|
|
|
— Laa—<*+ 6*—1гJ' |
|
Отсюда |
следует, что при |
| 1 1< |
min (a, b) |
|
|||
dГ 1 1 1
—l n F ( t ) < - 2 [ — + X J.
Соответственно |
при |
| f | < min (a, 6) и г ^ 0 |
|
|
|
|||
|
|
i - '( o < - 2 [ 4 - + 4 - ] f . |
|
|
|
|||
Возвращаясь к q (г), |
получаем, |
что при f^ O |
і + і |
|
|
|||
. |
-Г |
2 |
|
|
|
|
|
|
ln q |
m + 1 |
21 _ |
т + |
1 ] г -------- 8 (n t - f l ) |
(21 — |
иг + |
1 ) U |
|
Оценим |
теперь |
|
|
к-і\ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ln |
Д |
(q( i )), |
|
|
|
|
т — 1 |
|
i=j |
|
|
|
|
|
|
|
|
|
|
|
|
||
считая, |
что ■ 2 |
■< / < * —1: |
|
|
|
|
||
к- 1 |
fc-i |
|
|
|
А—1 |
|
|
|
Т-і |
TZ, |
|
(m -I- IK -i - - ^ + 1 ) " |
\ |
2 |
1 |
||
l=l |
г=1 |
|
|
|
|
|
|
|
t — j |
г— j |
|
|
|
|
|
|
|
Возвращаясь к (П.4), получим
ln а (к) < . |
■ 8(1 + 1) |
|
(то + 1) (21 — т + 1) |
||
|
■ Ь - ^ у
