Построение оценок энтропии стационарных случайных процессов

• Автор: Тимофеева, Нина Евгеньевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Ярославль
• Количество страниц: 73 с. : ил.

Введение
В настоящей работе предлагаются три новые статистические оценки энтропии, основанные на методе "расстояния до ближайших соседей "(см. раздел 1.2.2). Принципиальные преимущества новых оценок это:

1) степенной порядок точности дисперсии:

2) при оценивании энтропии динамических систем значения оценок не зависят от разбиения пространства;
3) в ряде случаев удается показать степенной порядок убывания смещения (для оценки из главы 2).
При выполнении определенных условий показан прием уменьшения смещения оценки (глава 3). В работе также приведен эффективный алгоритм вычисления оценки по экспериментальным данным.

Напомним определение энтропии (см. папр. [2], [32], [29]).

Пусть дан конечный алфавит А. Пусть есть случайная последовательность

символов этого алфавита. Тогда энтропией случайной последовательности £ (энтропией па символ) называется величина

/г = ІІШ (і)

77—ОЭ П

# = #(&
В этой формуле логарифм обычно берегся но основанию 2.
Впервые эго понятие ввел К.Шеннон в 1948 г. (см. [37]). Он использовал его для измерения количества информации и показал, что энтропия определяет границу степени сжатия текста. Это одно из важных практических применений энтропии: почти любой текст £і
В 50-е и А.Н. Колмогоров перенес понятие энтропии на динамические системы (см. например [2], [29], [32], [26]).
Пусть (М,д,Т) — динамическая система: М — множество, р — мера на М и Т — измеримое преобразование множества М, сохраняющее меру, т.е.
р(Т _1(2І)) = р{Л). для любого измеримого А.
Будем рассматривать конечные или счетные измеримые разбиения пространства М, т.е. наборы множеств а = {Д}, Д - измеримое, таких, что
д(|Р Д) = м(-0 11 м(Д Р| Л]) = 0 для любых і и у

Считается, что р(Аг) > 0 при всех г.
Энтропией разбиения а = {Ai} называется число
Н(а) = - KAi) log(ß(Ai)).

Для разбиений а — {Д}, ß = {В,} их произведением aJ ß назовем разбиение, элементами которого служат всевозможные множества вида Д [") В
Энтропией на символ разбиения а называется величина
h(a, Т) = lim -Н{а /Та/ ... / Тпа).
п->оо п v v V
Энтропией динамической системы (М.ц.Т) называется величина
h(T) = sup h(a, Г),
где верхняя грань берегся но всем конечным п-in счетным измеримым разбиениям а пространства М.
А.Н. Колмогоров показан, чт для многих разбиений энтропия на символ разбиения совпадает с энтропией динамической системы, А.11. Колмогоров доказал, что энтропия есть инвариант динамической системы, изоморфные динамические системы имеют одинаковую энтропию. В частности, А.Н. Колмогоров применил понятие энтропии для решения задачи об изоморфности сдвигов Бернулли.
В 1971 г. Д.Орнстейн доказал утверждение, обратное теореме Колмогорова: если энтропии сдвигов Бернулли одинаковы, то эти сдвиги изоморфны (см. [30], |29|). Эти исследования показывают важное теоретическое значение энтропии.
Как говорилось выше, энтропия определяет границу сжатия информации. Поэтому в прикладных задачах нужно оценить значение энтропии по экспериментальным данным. В терминах определения (1) задача формулируется следующим образом: дан текст из п символов £i
Задаче построения оценок энтропии посвящено большое число работ. Приведем краткий обзор известных в настоящее время результатов.
Существуют два основных подхода к построению оценок: построение эмпирической функции распределения и неиараметрические оценки. Рассмотрим эти два подхода.
0.1 Построение эмпирической функции распределения
Определение (1) можно переписать в виде:
- X] = *!’ = 6.)logP( = гь = /„)
h,-- ,i7iG«4
= Е(—log РЦЬ... ,£,))

Эта формула показывает, что наибе ice ex гествснный способ построения оценки — это прямое вычисление математического ожидания логарифма эмпирической функции распределения. Этот способ удобен, если число параметров, от которых завпепг распределение, конечно.
Рассмотрим, например, бесконечную случайную последовательность £„. которая принимает значения 0 и 1 независимо с вероятностями а и /3 соотвественно Тогда, как показано в работе Шеннона [37], формула (1) принимает вид:
h = —a log а — /3 log Р.
Если значения а и Р неизвестны, то оценку энтропии можно посчитать простейшим способом. Рассмотрим достаточно длинную последовательность Пусть /„(0) и /„(1) счетчики, сколько раз встретился 0 и 1 в конечной последовательности £ъ
>>,, = /.,(0) log/n(0) - /„(1) log/„(l).
Последовательность случайных величин Л„ сходится по вероятности к энтропии к. Также можно показать схочнмосгь ноши nuo.uk п справедливость центральной предельной теоремы: нормированные величины /к, сходшея к нормальному распределению (см. [24|).
Если число параметров бесконечно или неизвестен вид завнепмоети от параметров, то этот подход применяется следующим образом.
Пусть -4 — конечный алфавит и пусть w = ад .. wm € Л"'. Обозначим д(ш) = Р(ф = = w,H). По теореме Шешюпа-МакМиллапа-Бреймаиа (см. [37]). случайные
величины
нт = Y] fi(w)ogn{w).
т z—'
weA't
сходятся к энтропии h для почти всех W.
Если процесс эргодический, то частота появления слова w сходится к величине ц(ш). Таким образом, предлагается следующий способ построения оценки энтропии.
1) фиксируем бо 1ЫПОС число т:
2) рассмотрим достаточно длинную последовательность ф
3) оценим числа /i(w), w 6 Ат, т.е. найдем частоты fn(w) всех слов ш, w е Ат в рассматриваемой нос юдова,цельности, и, наконец, получим оценку h но формуле:
Фет 'У Jn(w) Фё Iп(к?)
w£/lm
При 77, —с ОО И VI —> оо величины кпт СХОДЯТСЯ к /;.
Но в этом методе есть ряд существенных недостатков: неизвестно, что точно означают слова "большое"тп; что точно означает "большое"??; двойной переход к бесконечности (по п и т).
Эти три недостатка делают этот метод неудобным д ш теоретических исследований. Впервые такой подход к построению оценок энтропии описан Г. 11.Башариным [24]. Если же число возможных слов w £ Ат экспоненциально растет, то этот метод становится не применим и в прикладных задачах.
Например, пусть |Л| = 2 и рассмотрим всевозможные слова длины 50. Число таких слов равно 2"°. Будем считать, что все эти слова возможны. Однако, современная

Доказательство. Доказательство аналогично доказательству предыдущей леммы.
Пусть £ - случайная точка в П распределенная по мере д и пусть со - некоторая не случайная точка в П. Тогда рУп<м,£) является случайной величиной, принимающей значения из отрезка [ет, 1] и
РЫсщ £) Поэтому для п независимых, одинаково рненределепых но мере д точек .. Дп имеем:
1<г<п
Следовательно.
Г ЕЕ (1)тиУ [і - Р(хМ,і))Г‘ ; * > о.
£ < ЕТ,
- тт (ь+1)1п рт)(&,$,) Є,
0<7<7? и
= [ Р (- тіп ('с|1) 1пд(гт)(&.6) > і І (11 ~
- 1II £»т

1 - Е Г Е(АМ,е-‘Г [1 -/3(Л(щ),е-‘))]г

По формуле условного математического ожидания:

Ег?-т)
/п ./0
аИ йд(со).
Сделав замену переменных и — е1 г = А(со), получим (2.12). Доказа I ельство закончено. □
(2.13)
(2.14)
Лемма 13. Пусть мера д удовлетворяет условию
Нш 1Л\и(1,х) = 0, Уж,
С—»0 '
тогда
»?-ГмїУ-ги
где /:?(.-. н — А: + 1) бета-фующия, т.с.
Б(п.п — к + 1) = Доказательство. Перепишем (2.12) как Ег<Я = /" Г
В(к,п — к + 1)
(/с - 1)!(п - А;)!
1 - Е ()0(х>иУ (х - У(л'"))"
.7=0 '