Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 223
Скачиваний: 4
5 9. ПРИЛОЖЕНИЕ К ГЛАВЕ X |
238 |
здесь j — любое число меньшее к. Поэтому для к > — ^— можно
положить / = |
т — 1 |
---- 2----Для т нечетного и j = ml2 для т четного, полу |
чив наиболее сильную оценку. Суммируя, далее, арифметическую прогрессию, получим
In а (к) <
|
4(1 + 1) |
|
|
+ 1 |
для четного т ■, |
(т + |
1) (21 — т + |
1) |
|
||
< |
4(1 + 1) |
|
к |
т — 1 |
1 А |
(т + |
1) (21 — т + |
1) |
2 |
для нечетного т.
Наконец, Гі есть а (к) при к первом целом таком, что
те21
к—— > 2 ’
откуда
1ц Гі < - (m -j_ i)(2l"— m + 1) (йЧ* ~~
Точно так же оценивается величина Г2, так как распределение (П.1) симметрично с центром т /2 .
Таким образом,
|
|
Г< 2 “ ■>[ - |
(„ + !)і І - т - |
і) («*'’ - |
«] • |
<П'5> |
||||||
(О < |
Далее, |
|
рассмотрим |
сначала |
случай, |
когда |
е2 (I — 1 ) ^ 1 |
|||||
е < |
1). |
При этом |
заведомо 1 ^ 2 |
и |
е2!2 |
2. |
|
|
||||
т = |
Правая часть (П.5) |
в этом случае достигает максимума при |
||||||||||
I и, |
следовательно, |
|
|
|
< Зе" ,(і_1)' |
<п-6> |
||||||
|
При |
е2 |
г < 2 ехР [ - |
ТГТіГ + 7 Т г ] |
||||||||
|
|
|
|
(1—1)< 1 оценка |
(П.6) |
тривиальна, |
поскольку |
левая |
||||
часть неравенства не превосходит |
единицу, а правая всегда боль |
|||||||||||
ше единицы. |
|
(П.6) |
справедлива при любых целых |
|||||||||
I и |
Таким образом, оценка |
|||||||||||
е в |
пределах 0 < е ^ |
1. |
|
|
|
|
|
|
||||
Г л а в а X I
Н Е О Б Х О Д И М Ы Е И Д О С Т А Т О Ч Н Ы Е У С Л О В И Я Р А В Н О М Е Р Н О Й
С Х О Д И М О С Т И Ч А С Т О Т К В Е Р О Я Т Н О С Т Я М Н О К Л А С С У
СО Б Ы Т И Й
§1. Энтропия системы событий
Большинство практически интересных приложений ох ватывается изложенными в предыдущей главе достаточ ными условиями. Интересно, однако, получить и , исчер пывающие необходимые и достаточные условия. Сущест венно, что это удается сделать в терминах, введенных в
§3 главы X.
Вотличие от достаточных условий, сформулирован ных в § 6 главы X, необходимые и достаточные условия, вообще говоря, зависят от задания вероятностной меры на множестве X, но схема, по которой они строятся, оста ется прежней. Идея, как и раньше, состоит в том, чтобы заменить бесконечную систему событий S конечной под системой, состоящей лишь из различимых на выборке со бытий. Число таких событий зависит от выборки и равно индексу системы S относительно выборки
As (хг, ..., Хі).
При выводе достаточных условий использовалась функция роста ms (Z), оценивающая сверху значение индекса для выборок длины I. Такая оценка оказывается слишком грубой для получения необходимых и достаточных усло вий. Последние удается сформулировать, если ввести не которую усредненную характеристику величины As (arl t ...
..., Хі).
§ 1. ЭНТРОПИЯ СИСТЕМЫ СОБЫТИЙ |
241 |
|
Рассмотрим функцию |
|
|
Hs (I) = М Zg2 A®(xx, ..., хі) |
|
|
(М — символ математического |
ожидания). |
|
Здесь и дальше предполагается, что функция А® (xj,... |
||
хі) измерима и этого достаточно для существования |
||
математического ожидания, поскольку |
|
|
1< As(*і, •••,а;г)< 2' |
|
|
и соответственно |
хг)< г. |
(ИЛ) |
о < ig2AS(^, |
||
В силу этих же соотношений очевидно, что
О < Я® (I) < I.
Функция Я® (I) обладает свойством полуаддитивности,
что позволяет назвать ее энтропией системы событий
Sотносительно выборок длины I.
Всамом деле, рассмотрим выборку
Х^, . . . , Х й , Х й+Х, . . . , X;.
Каждая подвыборка, индуцированная некоторым собы тием Л £ S на этой выборке, состоит из подвыборки, ин дуцированной А на
|
Хі , |
•••> Х й , |
|
и подвыборки, |
индуцированной А на |
|
|
|
%h+1і |
х 1' |
|
Поэтому число As (хх, ..., x h, x h+l, |
..., хг) не превосхо |
||
дит числа пар подвыборок, |
каждая из которых состоит из |
||
— одной подвыборки, индуцированной |
некоторым А е S |
||
на хх, ..., xft, |
и одной подвыборки, |
индуцированной на |
|
хй+1, ..., хг. Следовательно, |
|
||
А® (хх, ..., Хй, Хд+j, ..., X;)
и соответственно
А® (Хц • • •, Xft) А® (xfe+1, ..., Xi)
( 11.2)
lg2 А® (хх, ..., x k, xft+1, .... |
я:г) < lgjj А® (хх, |
..., |
хй) + |
+ |
lg* А® (хй+1, .... |
хі). |
(11.3) |
242 ГЛ. XI. НЕОБХОДИМ Ы Е И ДОСТАТОЧНЫЕ УСЛОВИЯ
Усредняя соотношение (11.3), получим
Н8 (h + h) < H8 (k) + H8 (l2), |
(Ц.4) |
T.e. свойство полуаддитивности. Применяя (11.4) многократно, получаем
Н8 (nl) < nlis (l). |
(11.5) |
§ 2. Асимптотические свойства энтропии
Энтропия системы событий относительно выборки хг,...
..., Хі обладает рядом свойств, аналогичных свойствам энтропии п-членных цепочек, рассматриваемых в теории информации. В этом параграфе будет сформулировано и доказано несколько утверждений относительно асимпто тического поведения и оценок энтропии, которые пона добятся при выводе необходимых и достаточных условий
равномерной сходимости.
Hs /j\
Лемма 1. Последовательность — ~ ~ имеет при I -> оо
предел с (0 с ^ 1).
Приводимое доказательство совпадает с доказатель ством аналогичного утверждения для энтропии п-член- ных цепочек в теории информации [66].
|
Д о к а з а т е л ь с т в о . |
В самом деле, поскольку |
|
U |
^ 1, то существует |
нижнии предел |
|
|
с = lim |
ІГ- |
( 0 < с < 1 ) . |
|
tS(1) |
||
|
1—>ОО |
I |
|
Тогда для любого е >> О найдется 10 такое, что
|
- |
^ < с + |
е. |
(11.6) |
Произвольное |
10 представим |
в виде |
|
|
|
I |
= nl0 + |
к, |
|
где п )> 0 и к < |
10. |
|
|
|
Далее, в силу (11.2), (11.4) и (11.5) |
|
|||
Н8 (I) = Н8 (nl0+ |
к) < Н8 (nl0) + |
Н8 (к) < |
|
|
|
< |
nHs (l0) + Н8 {к) < |
пН8 (10) + к. |
|
I 2. АСИМПТОТИЧЕСКИЕ СВОЙСТВА ЭНТРОПИИ |
243 |
Поэтому
Hs (I) < n H s (Іо ■n lls (Іо) + к _ IIs (к) +
Воспользовавшись теперь условием (11.6), получим
Нь (I) |
< с + е |
I |
|
Далее, поскольку при I -> оо также и тг-ѵоо, имеем
lim -Hs (I)■ < с + е
l —* оо |
г |
|
и ввиду произвольности е
Н т я 8 (*) = с.
|
I—*ОО |
г |
|
Лемма доказана. |
|
|
|
В теории информации величину |
называют энтро |
||
пией на символ. Сохраним этот термин и для величины
ңБ п\
—р-і-. Несмещенной оценкой этой величины служит слу
чайная величина
Г ( Х \ , . . . , — —j — I g a Д ( % ъ • • •> • £ /) •
Покажем, |
что эта случайная |
величина стремится по |
вероятности |
г |
# s ( I ) |
при I — оо к тому же пределу, что и — |
||
(аналогичное утверждение для эргодических источников доказывается и в теории информации, но на этот раз до
казательства |
различны). |
|
|
Лемма 2. |
Пустъ |
Hs (I) |
тогда |
— р-^- —> с, |
|||
|
' S |
_ lg AS (a;1......... |
x t) |
сходится к с по вероятности, т. е.
lim Р (I rs (жі,..., xt) — с I > е} = О,
1-*Op
244 ГЛ. X I. НЕОБХОДИМ Ы Е И ДОСТАТОЧНЫЕ УСЛОВИЯ |
|
||||||
Более того, если обозначитъ |
|
|
|
|
|
||
Р +(е, |
I) |
= P{rs (xlt |
..., хі) — с > |
е}, |
|
||
Р - (е, |
I) |
= Р { с — rs {хѵ ..., |
х,) > |
е}, |
|
||
то |
|
|
|
|
|
|
|
|
|
2 р +(8, г)< оо. |
|
|
|
||
|
|
г=і |
|
|
|
|
|
Д о к а з а т е л ь с т в о . |
Оценим |
сначала Р +(г, |
I). |
||||
Поскольку |
|
|
|
|
|
|
|
|
|
lim H s |
( l ) |
= с, |
|
|
|
найдется Z0 такое, |
что |
|
|
|
|
|
|
|
|
(Z„) |
|
|
|
|
|
|
|
h |
|
|
|
|
|
Рассмотрим случайную |
последовательность |
|
|||||
п —1 |
|
|
|
|
|
|
|
2 lg 2 A S (x i(o+1.......... * (і+ 1 )^ |
n - 1 |
|
|
|
|||
ч (п) — —------------- fa----------------— 2 r |
(^i'o+i. • • •> |
• |
|||||
|
|
|
|
i = 0 |
|
|
|
Таким образом, q(n)ln есть среднее арифметическое слу чайной величины rs (х1? ..., xZ|>), полученное в серии неза висимых испытаний длины п.
Математическое ожидание rs (xlt ..., х,[) равно Hs(l0)/l0, поэтому математическое ожидание q (п) In также равно Hs (Z0)/Z0; случайная величина rs (xlt ..., х,0) огра ничена (0 ^ г ^ 1) и потому обладает центральными мо ментами любого порядка. Пусть П2 и П4 — ее централь ные моменты соответственно второго и четвертого порядка. Очевидно, что Di и П2 меньше 1. Тогда центральный мо мент четвертого порядка величины q (п)/п есть
п3 1 п3
Применяя неравенство Чебышева для моментов чет вертого порядка, получим при любом б > О
Р |
' Ч(п) |
4 |
|
п |
пѢ* * |
