Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 220
Скачиваний: 4
I 3. ДОКАЗАТЕЛЬСТВО ДОСТАТОЧНОСТИ |
249 |
ется, что для этого необходимо и достаточно, чтобы энтро пия на символ последовательности стремилась к нулю с
ростом длины |
выборки. |
|
что функции ns (хг, ..., x t), |
||||
Теорема 11.1. Допустим, |
|||||||
ps (хг, |
..., |
x t) |
и As (хх, |
..., Xi) измеримы при всех I. Тогда |
|||
, |
если |
т |
|
Hs (l) |
= |
л |
то имеет место равномерная |
а) |
lim — |
U, |
|||||
|
|
I—>оо |
1 |
|
|
|
сходимость частот к вероятностям с вероятностью 1;
S /j\
б) если lim — |
= с ]> 0, то существует число б (с)Ъ- О, |
оо |
такое, что |
не зависящее от I, |
lim Р {я^ (хі, . . ж, )> 6} = 1,
1-+0О
т. е. вероятность того, что максимальное по классу S уклонение частоты от вероятности превзойдет б, стре мится к 1.
Таким образом, необходимым и достаточным условием равномерной сходимости частот к вероятностям по классу событий в этом смысле является условие
Д о к а з а т е л ь с т в о д о с т а т о ч н о с т и (ут
в е р ж д е н и я а)). Это доказательство |
аналогично вы |
|
воду достаточных условий главы X. |
2 Л З |
|
Итак, пусть |
HS {1) = 0. |
|
lim |
|
|
1-*ОО |
I |
|
Оценим величину
Р {sup IV(И; хъ ..., Хі) — Р (И) I > е} = Р {я? > е}.
A<=S
В силу основной леммы (§ 5 главы X)
Р {л? > 8} < 2Р {pS(^, . . ., X , ) > -£-} .
В свою очередь, как было показано при доказательстве
теоремы 10.2, |
С*Р.£& £~' |
/>{p8-(*1. - . ^ |
) > - f b w Ü 2 ѳ[р8(ГіХ2,)“ т ] ^ ^ 2г)> |
|
А(го і |
250 ГЛ. X I. НЕОБХОДИМ Ы Е И ДОСТАТОЧНЫЕ УСЛОВИЯ
где Ti |
— всевозможные перестановки последовательности |
хх, ..., |
х2І. Кроме того, € у, , j ■; |
к = |
Р8 ( П Х 2г) |
6 |
|
г'(1-1) |
|
< 3AS (хх, . . х21)е |
4 |
||
2 |
Очевидно также, что к ^ |
і. |
|
|
на область |
где |
Разобьем область интегрирования |
|||||
]g 2 A s (агі, |
. . , , x 2\) |
^ |
8 2 |
|
|
21 |
|
|
|
|
|
и область Х 2, где |
|
|
|
|
|
lg 2 А Ь (а:і> . . ., X ,) |
> |
е 2 |
|
|
|
21 |
|
8 |
' |
|
Тогда, заменяя к мажорирующими выражениями, по лучим
|
£*Z |
|
Р{р!і > -г} < $ 2AS (*i. • |
• •> хп) е~ ~ |
dP {X21) + \ d P {X21). |
Л’і |
|
х% |
|
|
( 11. 12) |
В обозначениях леммы 2 предыдущего параграфа |
||
$ dP (X21) = Р+ |
21) , |
|
поскольку |
|
|
lim |
H s ( I ) = 0. |
|
I—*оо |
.1 |
|
Учтем также, что в области Х г
іЧ
А- (хѵ ..., х2і)<^ 2 4 .
Тогда
g2jr g2^
Р {pfi > 4-} < 2 ■2_Ге” “ + Р+(4 - ’ 21) ■ (И-13)
Первый член суммы стремится при I -> оо к нулю экспо ненциально, второй член также стремится к нулю соглас но лемме 2. Более того, поскольку в соответствии с этой
$ 4. До к а з а т е л ь с т в о н е о б х о д и м о с т и |
251 |
леммой
ос
2 Р+ (е, Z)< ОО,
г=і
то и
ОО
2 Wps(*ь ■••.*«)> 44 <<*,
г=і 1 |
J |
а следовательно, и
2 Р {Jts (хъ . . ж2() > е} < оо.
і=і
Отсюда следует равномерная сходимость частот к ве роятностям почти наверное.
Утверждение а) доказано (заметим, что в оценке (11.13) только член Р +(е, I) зависит от распределения).
§ 4. Доказательство необходимости условий равномерной сходимости
Пусть теперь |
IIs (О = с > 0. |
|
lim |
|
|
1-*00 |
I |
|
В силу основной леммы (§5, гл. X), если только |
|
|
lim P{ps (x1( . ..,* „)> 2 6 } = 1, |
(11.14) |
|
I—wo |
|
|
ТО И
lim Р {ля (жх, ..., х21) > 6} = 1.
ОО
Таким образом, достаточно показать справедливость (11.14) при некотором б (с) > 0.
1. Рассмотрим сначала для пояснения общего доказа тельства частный случай, когда
l i m ^ i ^ l .
і—оо 1
В этом случае, как было указано в замечании 2 § 2,
252 ГЛ. X I. НЕОБХОДИМ Ы Е И ДОСТАТОЧНЫЕ УСЛОВИЯ
HSII)
и, поскольку — есть математическое ожидание вели
чины
lga ÄS(*і. • • •. *()
---------- 1.---------- |
^ |
ТО
lg As (xi, . . xt)
Следовательно, для всякого I с вероятностью 1
As (ж^ ж,) = 2',
т. е. с вероятностью 1 всякая выборка такова, что на ней
индуцируются |
системой S |
все |
возможные подвыборки. |
||||
В частности, для выборки жх, ..., х2І |
можно найти такое |
||||||
А* (ЕЕ S, что |
s i i S i * для |
і = |
1, ..., |
I и жг |
Л* |
для |
|
і = I + 1, |
..., |
21. Тогда ѵ' (Л*) |
= 1 , |
ѵ" (Л*) = |
0 и, |
сле |
|
довательно, |
с вероятностью |
1 |
|
|
|
|
|
|
|
sup I v' (Л) — ѵ" (Л) I = |
1. |
|
|
||
|
|
A e S |
|
|
|
|
|
Тогда и подавно для всех б < 0,5
lim Р {sup I v' (Л) — ѵ"(Л) I > 26} = 1.
l-*-oo |
A e S |
Идея доказательства утверждения б) в общем случае основана на том, что при
4 « - * С> 0
почти из всякой выборки длины I можно выделить подвы борку, на которой индуцированы все подвыборки и дли на которой растет пропорционально I.
2. Для этого нам понадобится следующая
Лемма 3. Если при некотором а (0 <С а ^ 1) и Г^> А-
для некоторой выборки жх, ..., жг оказывается, что
As (жх, ..., ж,) > 2аі,
то найдется подвыборка
хи, ..., хіг
§ |
4. ДОКАЗАТЕЛЬСТВО НЕОВХОДЙМОСТЙ |
253 |
|
длины г — [grZ], zdeq(a) = |
(в — основание натуральных |
||
логарифмов), |
такая, что |
|
|
As (*„ -м xtr) = 2'.
Д о к а з а т е л ь с т в о . В силу леммы § 4 главы X требуемая подвыборка заведомо существует, если
|
г—1 |
As |
2 c j = 0(Z, г). |
|
і=0 |
Чтобы убедиться в последнем, достаточно проверить нера венство
2а1 > Ф (Z, |
г). |
(11.15) |
||
Поскольку при наших |
условиях |
г 2 и Z |
г + |
1, то |
можно воспользоваться |
оценкой функции Ф (г, |
Z), |
полу |
ченной в замечании 1 § 4 главы X:
Ф(г, г)< Ф (г, Z )< 1 ,5 ^ -.
Всвою очередь это неравенство можно усилить, применяя формулу Стирлинга:
|
Ф(г, Z)< |
1,5f e r |
еГ . |
|
|
У 2яг г2 |
|
Нетрудно убедиться, что функция |
монотонно воз |
||
растает по X при X < Z. Следовательно, |
справедливо так |
||
же |
неравенство |
|
|
|
® (г. о <(■*-)-. |
|
|
так |
как |
[g-, Z] < ql. |
|
|
г = |
|
Поэтому отношение (11.15) будет установлено, если спра ведливо неравенство
254 Гл. JCI. НЕОБХОДИМ Ы Е И ДОСТАТОЧНЫЕ УСЛОВИЙ
Логарифмированием и сокращением на I это неравенство преобразуется к следующему виду:
a > q l g 2 [ ~ y |
(11.16) |
При z )> 0 справедливо неравенство
lg2Z< 2 lg ! е / і .
Оно непосредственно следует из того, что функция — ■
V Z
достигает максимума в точке z = е2 и равна при этом
. Поэтому (11.16) следует из неравенства
а > V eq 2 ]g2 е
Подставляя сюда значение q = |
, непосредственно убеж |
|
даемся в справедливости выражения |
||
а > |
2 1 g 2 e а. |
|
3 |
|
|
Лемма доказана. |
|
|
Напомним, что, согласно лемме 2 § 2, при |
||
Hs (l) |
с > |
О |
I
оказывается, что с ростом I
lg A s (ал, . . . , х {)
c — 6
стремится к единице (6 )> 0). Следовательно, при доста точно больших I с вероятностью, сколь угодно близкой к единице,
1?2 As (хъ . . |
., xt) > 2* 1 |
(11.17) |
и, согласно только что доказанной лемме, в каждой выбор ке, удовлетворяющей условию (11.17), найдется подвы борка длины
г = [? (тг)-‘ ]'
|
S 4. ДОКАЗАТЕЛЬСТВО НЕОБХОДИМОСТИ |
255 |
на которой система S индуцирует все подвыборки. |
Длина |
|
этой подвыборки возрастает пропорционально I. |
|
|
3. |
С х е м а д о к а з а т е л ь с т в а ( у т в е р ж д е |
|
н и я |
б)). Сравнение частот выпадения событий |
в двух |
полувыборках может вестись следующим образом: берет ся выборка длины 21 и случайным образом делится на две полувыборки равной длины, после чего подсчитывается и сравнивается число появления каждого события клас са S на первой и второй полувыборках.
Рассмотрим несколько измененную схему. Допустим, что выборка двойной длины хг, ..., х2і удовлетворяет усло вию (11.17), т. е.
As (хѵ ..., x2; ) > 2 cI.
Тогда в ней можно указать подвыборку Х г длины
W ü ' l '
на которой индуцированы все подвыборки. Теперь разде лим случайно на две полувыборки сначала подвыборку
Х г, а затем (независимо) |
остаток |
ХЧХГ. Пусть Х[ и |
|
Х2 — две полувыборки, на |
которые |
распалась Х г. По |
|
построению найдется событие А* |
S |
такое, что все эле |
менты ХІ принадлежат А*, а все элементы Х2 не принад лежат А*. Для этого события «разбаланс» частот достига ет наибольшего значения. Допустим, что в оставшейся части последовательности элементы из А* встречаются т раз. При случайном разбиении остатка примерно тІ2 из них попадет в первую полувыборку и столько же во вторую. Тогда
I ѵ' (Л*) — ѵ" (Л*) I |
г |
т |
т |
г |
ІГ + ДГ |
21 |
|
||
|
|
и, следовательно,
sup I ѵ' (Л) — ѵ" (Л) I Д> q. A^S
Поскольку число q Д> 0 не зависит от длины выборки, то равномерной сходимости нет.
Измененная схема не вполне эквивалентна исходной, так как в действительности подвыборка Х Т и остаток не