Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 222
Скачиваний: 4
§ 2. АСИМПТОТИЧЕСКИЕ СВОЙСТВА ЭНТРОПИИ |
245 |
Далее, в силу (11.3)
n—1
~пй tea А (х і, . . Хпіл) < —г 2 |
AS (жі/.+і>• • -I х(і+оО > |
т. е.
rs (xu .. .,Хп1о)<Ш
Поэтому, тем более,
|
|
n L s |
H s (/о) |
|
s \ ^ |
4 |
|
|
||||
|
|
|
|
— |
i r > |
6 K |
w |
|
|
|||
Полагая 6 = |
|
и учитывая, что |
|
|
|
|
|
|||||
|
|
|
|
g(W |
|
1 |
8 |
|
|
|
||
получим |
|
|
г„ |
^ |
с i " |
F ’ |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
^ { Д > с + |
^ } < - | - , |
(11.7) |
|||||||
где через (? |
обозначено |
. |
|
|
|
|
|
|
||||
+ |
Наконец, для произвольного Z)> Z0 положим Z= nZ0 + |
|||||||||||
Zc, где п — [Z/Z0], |
а &< |
Z0. |
|
|
|
|
|
|
||||
|
В силу (11.2) |
|
|
|
|
|
|
|
|
|||
|
lg2As (xlt |
... ,* ,) < |
lgj As (x15 |
xnh) + |
Ä. |
|
||||||
|
Поэтому |
|
|
|
|
|
|
|
|
|
|
|
S , |
V |
1 |
, |
л S / |
|
|
. |
. lg2AS (a:1,. . .,xnlo) + |
k |
|||
r (xi, ..., Xi) |
— |
1 |
lg2 A (xi, ..., |
xj) ^ |
niQj_ |
|
||||||
Усиливая неравенство, получим |
|
|
|
|
|
|||||||
!* (* ,.......................................... + |
|
|
= |
г f a , . . ., я„г0) + |
— • |
|||||||
|
|
|
|
nlo |
|
|
|
|
(11.8) |
|||
Предположим, что Zнастолько велико, что |
||||||||||||
|
|
|||||||||||
|
|
|
|
п |
^ |
3 |
• |
|
|
|
|
|
Тогда из (11.7) и (11.8) следует, что |
|
|
|
|||||||||
|
|
Р+(е, Z) = P { r ? > C+ |
B} < - § .. |
(11.9) |
246 ГЛ. X I. НЕОБХОДИМ Ы Е И ДОСТАТОЧНЫЕ УСЛОВИЯ
Поскольку при I —у о о |
имеет место п |
о о , то |
lim Р+(г, I) = 0. |
|
|
I—*оо |
|
|
Кроме того, |
|
|
2 Р |
+ ( 8 , і ) < о с . |
|
г=і |
|
|
Действительно, достаточно оценить сумму, начиная с до статочно больших I, для которых выполняется (11.9). Тогда
оо оо
2 |
Р+(8, |
|
|
|
і=г* |
|
п = і |
|
|
Остается показать, |
что |
Р _ (s, I) |
0 при I |
оо Пусть |
Iff таково, что для всех |
10 |
|
|
Hs (I)
Из свойств математического ожидания и того факта, что Hs (1)11 есть математическое ожидание rs (a^, ..., £ (), имеем
r= H (()/f |
r = I |
|
c |
J ^ 9 - — r?)dP(X ') = |
jj |
Jrf - |
) dP {X1). |
r= 0 |
r = H s ( l ) / l |
|
|
Обозначая первую часть равенства R v а вторую R2 и по лагая 1^> 10, получим
|
|
|
Г=С—£ |
|
|
|
|
|
|
|
R i > ~ |
^ |
dP(Xl) = ^ - p - ( 8 , l). |
|
|
(11.10) |
|
|
|
|
r=0 |
|
|
|
|
|
Далее, пусть б 0 — произвольное число. Тогда |
|
|||||||
Д .= |
Г =ТН 8 (1 )[1 |
( r f - « |
^ )' |
X ( |
r t |
- |
^ |
|
і р (х ' ) + r= c + 5 |
+ |
r=*1 |
|
x |
||||
|
|
XdP(X')<|c + 6 - ^ i ^ |
U |
|
d P ( X ) |
|||
|
|
|
|
|
|
|
|
r^c-|-8
S 2. АСИМПТОТИЧЕСКИЕ СВОЙСТВА ЭНТРОПИИ |
247 |
или, иначе, |
|
|
|
|
|
|
|
|
|
|
|
Я2< |
с -f- Ь ■ Hs (l) |
|
-Р+ (б, I). |
(11.11) |
|||||
Объединяя |
(11.10) |
и (11.11), |
имеем |
|
|
|||||
4 - Р - & і )< с + б — |
Hs (I) |
+ РЧ 8, I). |
||||||||
|
I |
|||||||||
Переходя |
к |
пределу |
при I -> оо, |
|
|
|||||
|
|
|
|
lim Р~ (8, / ) ^ |
— 6 |
|
||||
|
|
|
|
г^оо |
|
|
8 |
|
|
|
и, поскольку б^> |
0 произвольно, а Р~ (е, I) ;> 0, |
|||||||||
|
|
|
|
lim Р~ (s, I) = |
0. |
|
|
|||
|
|
|
|
/ —>оо |
|
|
|
|
|
|
Лемма |
доказана. |
|
от |
последовательности |
||||||
Замечание |
1. |
В |
отличие |
|||||||
|
l g 2 ТПа (l) |
max |
lg2 As (zi,. . , , х) |
|
||||||
|
_ * 1 ........... |
|
|
I |
|
’ |
||||
|
|
г |
|
|
— |
|
|
|
которая в силу результата § 4 главы X тгрц Z-> оо стре мится либо к нулю, либо к единице, последовательность
Hs (0 |
_ ** |
lg2 aS (Ж1........жг) |
г |
— м |
г |
может стремится к |
любому пределу с (0 ^ с ^ 1). |
Например, пусть |
X — сегмент [0, 1]. В качестве сис |
темы S рассмотрим все измеримые множества А , которые |
включаются в сегмент [0, с]. Распределение Р (х) поло жим равномерным. Тогда на последовательности хг,
(без повторов) |
будут |
индуцироваться |
множествами А |
||
те и только те |
подпоследовательности, |
которые целиком |
|||
укладываются в сегмент [0, |
с]. |
Значит, |
их число равно |
||
|
As (xlf |
..., |
xi) |
= 2п, |
|
где п — число элементов последовательности, принадле жащих [0, с]. При этом
Hs (I) = М lg2As (лгц ..., x t) — М (п) = сі
248 гл . XI. НЕОБХОДИМ Ы Е И ДОСТАТОЧНЫЕ УСЛОВИЯ
и, следовательно, |
|
Hs (I) _ |
с. |
I |
|
Заметим, однако, что поскольку всегда
1gm s(Z )> tfS (Z))
то предел
lim Hs (*)
і—>оо I
может быть отличен от нуля только в том случае, когда
оо *
или, что то же самое, |
|
|
|
]g ms (I) = . |
|
||
|
I |
— х- |
|
Замечание 2. Значение |
Hs (I) |
при любом I |
|
функции — |
|||
служит оценкой сверху для величины |
|
||
с = |
lim- Hs (l) |
|
|
т. е. |
i —»CO |
|
|
|
|
|
|
І ^ > |
1 |
і т * Ж |
|
|
|
1-+оо |
|
Доказательство этого утверждения аналогично доказа тельству леммы 1.
Отсюда следует, что если с = 1, то
HS (D = А
I —
т. е. индекс As (хг, ..., x t) равен 21 с вероятностью 1.
§ 3. Необходимые и достаточные условия равномерной сходимости (доказательство достаточности)
Введенное в предыдущих параграфах понятие энтро пии системы событий позволяет полностью охарактери зовать те случаи, когда имеет место равномерная сходи мость частот к вероятностям по классу событий. Оказыва-