автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Построение оценок энтропии стационарных случайных процессов

На правах рукописи

0046И23<:

Тимофеева Нина Евгеньевна

ПОСТРОЕНИЕ ОЦЕНОК ЭНТРОПИИ СТАЦИОНАРНЫХ СЛУЧАЙНЫХ ПРОЦЕССОВ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Ярославль - 2010

2 0 идя 20Ш

004602399

Работа выполнена на кафедре теории функций и функционального анализа Ярославского государственного университета им. П.Г. Демидова

Научный руководитель -

Официальные оппоненты:

Ведущая организация

доктор физико-математических наук, профессор Дольников Владимир Леонидович

доктор физико-математических паук, профессор Соколов Валерий Анатольевич доктор физико-математических наук, доцент Райгородский Андрей Михайлович

Учреждение Российской академии наук Институт программных систем имени А.К.Айламазяна РАН

Защита состоится МОЛ/ 2010 г. в ^Й^час.ов на заседании диссертационного совета Д 212.002.05 при Ярославском государственном университете имени П. Г. Демидова по адресу: 150000, г. Ярославль, ул. Советская, д. 14.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета имени П.Г. Демидова по адресу: 150000, г. Ярославль, ул. Полушкина роща, д. 1.

Автореферат разослан " ^ " О^релЯ 2010 г.

Ученый секретарь диссертационного советаХ'лыът С.Д.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Математическое понятие энтропии впервые ввел К.Шеннон в 1948 г. Он использовал его дпя измерения количества информации, показал, что энтропия определяет границу степени сжатия текста.

В 50-е гг. А.Н. Колмогоров перенес понятие энтропии на динамические системы и доказал, что энтропия есть инвариант динамической системы: изоморфные динамические системы имеют одинаковую энтропию ([11])- Он применил понятие энтропии для решения задачи об изоморфности сдвигов Бернулли.

В 1971 г. Д.Орнстейн доказал утверждение, обратное теореме Колмогорова: если энтропии сдвигов Бернулли одинаковы, то эти сдвиги изоморфны[12].

Эти исследования энтропии имеют важное теоретическое значение для математики, в частности, для информатики.

В прикладных задачах возникает проблема нахождения значения энтропии, поскольку она определяет границ}' сжатия информации. По экспериментальным данным можно только ценить энтропию. Существуют два основных подхода к построению оценок энтропии: построение эмпирической функции распределения и непараметрнче-ские оценки.

В первом подходе на прямую вычисляется математическое ожидание логарифма эмпирической функции распределения. Этот способ удобен, если число параметров, от которых зависит распределение, конечно. Впервые такой подход описан Г.П.Башариным[10].

Непараметричсские оценки энтропии могут быть поделены на два больших класса. Первый класс, использует алгоритмы сжатия данных Лемпеля-3ива[1]. Основываясь на результате Лемпеля-Зива, П.Грасбергер предложил свою первую оценку величины обратной к энтропии[2]. Используя результаты Д.С.Орпстейна и Б.Вейса, П.Шилдс доказал, что эта оценка не является сходящейся для общих эргодических процессов, но при наложении определенных условий будет состоятельной [9]. Основываясь на этом результате, И.Контояннис и Ю.М.Сухов показали состоятельность оценки для

более широкого класса стационарных эргодических процессов [3].

Второй класс оценок основан на "методе расстояния до ближайших соседей". Р.Л.Добрушин первым предложил оценку энтропии, использующую этот метод.[5). Основная идея заключается в следующем: если ранее рассматривалась одна бесконечная последовательность, то при новом подходе рассматривается бесконечное число конечных последовательностей и вычисляется расстояние между ними. В.А.Ватутин и В.Г.Михайлов нашли смещение оценки Р.Л.Добрушина, оценили значение ее дисперсии и доказали состоятельность [6]. Позднее исследователи перенесли идею Р.Л.Добрушина на пространство случайных последовательностей. Опираясь на полученные результаты, Р.Вадии и А.Полити. предложили оценивать размерность Хаусдорфа в общем метрическом пространстве [7]. П.Виллингслей показал, что при выборе подходящей метрики энтропия совпадает с размерностью Хаусдорфа (8). Основываясь на результатах Р.Бадии и А.Полити, П.Грассбергер ввел свою вторую оценку энтропии на пространстве случайных последовательностей [2]. П.Шилдс построил пример, который показывает, что оценка П.Грассбергера несостоятельна для общего эргодического процесса.Также он показал, что предлагаемая П.Грасбергером оценка состоятельна для неприводимых непериодических марковских цепей |9]. В работе В.В.Майорова и Е.А.Тимофеева было введено обобщение оценки П.Грасбергера[13].

Таким образом, теория энтропии является одной из активно развивающихся областей математики и находит применение во многих областях современной науки.

Цель работы. Построение новых статистических оценок энтропии. Исследование свойств этих оценок, а именно: смещенности, состоятельности, порядка убывания дисперсии. Построение эффективного алгоритма для вычисления энтропии динамических систем по их траекториям.

Методы исследования. В работе используются методы теории вероятности, теории динамических систем, теории информации, линейной алгебры.

Научная новизна. Основные результаты диссертации являются

новыми и состоят в следующем.

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

Исследованы свойства этих оценок: смещенность, состоятельность. Доказано, что первая из предложенных оценок сходится ц-ночти всюду. Описан прием уменьшения смещения оценки. Проведены вычислительные эксперименты, подтверждающие точность предложенных оценок.

В работе также приведен эффективный алгоритм вычисления оценки по экспериментальным данным.

Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты диссертации могут быть полезны при изучении задач построения оценок энтропии, а также при изучении динамических систем.

Апробация диссертации. Основные диссертации докладывались на XI симпозиуме по проблемам избыточности в информационных и управляющих системах, г.Санкт-Петербург, 2007 г.. на 45 ежегодной конференции университета штата Иллинойс США. 2007 г., на IEEE Information Theory Workshop, Lake Tahoe, California, USA, 2007 г., на Международной конференции "Компьютерные технологии в электротехнике и радиоэлектронике", Новосибирск, 2008г., па семинаре кафедры математического моделирования Ярославского государственного университета им. П.Г. Демидова.

Публикации. По теме диссертации опубликовано 10 научных работ, из них 5 в журналах из перечня ВАК. Список публикаций приведен в конце автореферата. Работы, написанные совместно с другими исследователями, выполнены в нераздельном соавторстве.

Структура диссертации. Диссертация состоит из введения и 4-х глав. Список литературы содержит 39 наименований. Общий объем

диссертации составляет 03 страницы.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Рассматривается пространство последовательностей П = .Д1*. Пусть ¡1 — эргодическая, инвариантная относительно сдвига мера на пространстве 1). Пусть ..., ~ независимые, одинаково распределенные по мере ц случайные точки из П.

В прикладных задачах задано п слов длины т. В этом случае, считаем, что эти слова совпадают с первыми т символами точек -... £п и будем обозначать эти слова через .... ^потребуется построить оценку величины обратной к энтропии. Эта замена энтропии на обратную величину сделана для удобства формулировки и доказательства теорем. Глава 1.

В главе 1 на пространстве И рассматривается метрика

Ро(х,у)^-. . 1——г. (1)

тт{А;: хк ф ук)

Предлагается следующая оценка:

где

р(т)(х,у)=тах|1 А.(Х,У)}- (3)

Замечание. Подчеркнем, что предлагаемая оценка использует только первые т символов последовательностей ....

Асимптотическая несмещенность оценки доказана в следующей теореме.

Теорема 1. Пусть /х — инвариантная относительно сдвига боре-левская вероятностная эргодическая мера, удовлетворяющая условию:

За > О, Ь КСД*)) ^ е~05+г>, > 0,х б П (4)

Тогда для всех т ^ - In п существует предел:

lim = l (5)

где определена е (2).

Отметим, что условия теоремы выполняются для гиббсовских мер.

По сравнению с ранее известным результатом П.Шилдса сходимость оценки (2) показана для более широкого класса мер.

Для любого s 6 1 и произвольной вещественной функции ф : R —> SL определим ее конечную разность Аф(з) как

Аф(з) = ф(з) ~ ф(з - 1) (6)

и к-ю разность как

А{к]ф{-я) = - - !)• (7)

Обозначим:

m-1 /

флп) = Е и - / [1 - мед)]* dß(x)

5=0 \ ß

ф(п) = Е (1 - / [1 - dß(x)

s=0 V я

(8)

Лемма 1.

(8)

Лемма 2. Пусть мера ц удовлетворяет условию (4)- Тогда, для т > ¿\пп и заданного к, существует такая константа С, что следующее неравенство выполнено:

-щ^исп1.

Неравенство для параметра т, полученное в этой лемме; ранее было доказано П.Шилдсом для мер с условием свободной энергии. Условие леммы 2 является более широким.

В следующей теореме найдено ограничение сверху для дисперсии оценки.

Теорема 2. Пусть ц удовлетворяет, условиям теоремы 1. Тогда выполнено следующее неравенство:

Замечание. Для т — и фиксированного параметра к

оценка (10) равняется 0(гГ1).

Полученное неравенство для дисперсии в теореме 2 при т — 0(\ogn), улучшает ранее известный результат— 0(тГс). Более того, полученный порядок убывания оценки по параметру п совпадает с. порядком классической нижней границы Рао-Крамера для дисперсии.

Таким образом, предложенная в главе 1 оценка является наилучшей в настоящий момент по порядку убывания дисперсии по п и этот порядок, скорее всего, неулучшаем.

Из теорем 1 и 2 легко выводится состоятельность оценки.

Сходимость почти всюду была доказана П.Шилдсом [9] для марковских мер, а в данной работе получена сходимость для более широкого класса мер.

Теорема 3. Пусть мера ¡л удовлетворяет условиям теоремы 1. Тогда оценка определенная в (2), сходится к ^ ц-почти всюду.

В работе проведен эксперимент для нескольких динамических систем, энтропия которых известна. Результаты эксперимента подтверждают эффективность оценки (2) для нахождения энтропии.

(10)

где щ, определена в (2).

Глава 2. На пространстве П рассматривается метрика '-1

рЛХ,У) =

И-1

к= 1 А=1

(11)

где параметр 0 > — число символов алфавита А.

Построена следующая оценка энтропии:

= -й^-- (12)

где

г(к."

¿1п I (13)

(п +1)

метрика р\ определена по формуле (11) и через у) обознача-

ется усечение метрики:

р{Г\х,у) = тах . (14)

Так как

1цр1(ж,у) :

то метрику ро можно рассматривать как частный случай метрики рх при в = оо. Поэтому при в —> оо оценка (12) совпадает с оценкой, рассмотренной в главе 1.

Подчеркнем, что предлагаемая оценка (12) использует только т первых координат заданных случайных точек П. Эта естественная модификация оценки из работы [14] позволила улучшить оценку дисперсии.

Через А обозначим отображение А : П —> [0; 1]

(9-1 00

аи-шгтЕ^- (15) ' ' к=1

При 9 > |Д| это отображение будет вложением и изоморфизмом компакта П и компакта Л(Г2) С [0.1]. При в = |.А| это отображение будет метрическим изоморфизмом.

Отображение Л переносит меру ц на Л(П). Распространим полученную меру на весь отрезок [0.1] и обозначим через соответствующую меру отрезка [0,.т] (функцию распределения). Будем считать, что Д(х) = 0 при х < 0, и Д(х) = 1 при х > 1.

Р(х, г) = Цх + г)-Щх-г), 0 < г < 1, -1 < х < 2. (16)

Р(х, г) = ц ({ш 6 П : |А(ш)) - х| < г}), 0 < г < 1, -1 < х < 2.

Через г — и(х, £) обозначим обратную (по г) функцию к функции Ь =Р(х, г).

Через ^ будем обозначать лексикографический порядок на пространстве П.

Нетрудно видеть, что метрика р1 согласована с порядком, т.е.

Пусть

Ясно, что

(17)

Положим

(18)

Р\(х,у) < рг{х,г) Vx4y4z. Обозначим ЕгР = Ег^00*, =

(19)

Лемма 3.

Ег« =

йи

и

(20)

Лемма 4.

Er"fc'm) = /1 i1 1 ~ § (j)ß{X'4)3 (1 ~ ß{X'и)Г

где

0-1

dfiix)—, и

(21)

-т \А\ -1 " Лемма 5. Пусть мера /I удовлетворяет условию

lim t In v[t, x) = 0, Vx, (22)

тогда i

ErW = k(^j Jo X{t)tk~lil - t)n"kdt. (23)

=гп*(!•) 110(х■и)к (1 - ^и)Гк (24)

Теорема 4. Пусть ц - инвариантная относительно сдвига боре-лсвская вероятностная мера и ... - независимые случайные точки в П распределенные по мере ц, тогда справедливо неравенство

- 4(п + 1)

где г^'7"' определено в (13).

(25)

Следствие 1. Пусть ц - инвариантная относительно сдвига боре-левская вероятностная мера и .... - независимые случайные точки в О распределенные по мере /л, тогда справедливо неравенство

п+ 1

Правило выбора параметра т установлено в следующих утверждениях.

Лемма 6. Пусть /х - инвариантная относительно сдвига борелев-ская вероятностная мера, удовлетворяющая условию

За > О, С > О : ß{x, t) < Cta, Vi > 0, x € [0,1]. (27)

Тогда существует константа С\ такая, что:

Е r^,oo) - Е rgri < Clnke'mk.

Следствие 2. Пусть ß - инвариантная относительно сдвига боре-левская. вероятностная мера, удовлетворяющая условию (27), тогда для т > In пи фиксированного к, существует константа Сг такая, что:

Ет^-Еv4'm) <С2п~1.

Доказана сходимость оценки (12) почти всюду.

Теорема 5. Пусть ¡1 - инвариантная относительно сдвига боре-левсхая вероятностная мера, удовлетворяющая условию (27), тогда,

lim 17^fc,m> - = 0 почти всюду

п—*оо L J

при ^¡^Inn <т < СЫп, где С - некоторая константа.

Для симметричной меры Бернулли смещение оценки (12) является степенным по п.

т.е. при Ii —> оо математическое ожидание оценки стремится к 1 fh (h = |1пЛ| для симметрической меры Бернулли).

Итак, скорость сходимости оценки (12) для симметричной меры Бернулли при 0 = |.А| равна 0(п~г) при т. — ö(lnn).

Таким образом, предложенная в главе 2 оценка энтропии для этой меры лучше, чем оценка из первой главы, у которой смещение равно 0(1). Ее недостаток, по сравнению с оценкой (2) первой главы, — не доказан факт сходимости к 1 fh почти всюду. Глава 3.

В этой главе описан общий подход к построению эвристических оценок энтропии и исследованы их свойства.

Опишем основную идею предлагаемого подхода. Исследованная в главе 1 оценка содержит целочисленный параметр к. Новые оценки энтропии строятся как линейная комбинация этих оценок при различных значениях параметра к. Коэффициенты линейной комбинации подбираются так, чтобы формальный ряд по п смещения оценки имел заданное число нулевых случайных слагаемых.

Этот подход справедлив не только для метрики ро, но и для произвольной метрики р, поэтому рассматривается произвольная метрика р на пространстве последовательностей. Исследуемая оценка задается формулой

к

vik'm) = J2airnm)> <29)

1=1

где

^(-irli-iJ^.'j1), (30)

а Гп'т' определена в формуле (13) и для простоты будем считать, что m = с». Для краткости будем обозначать rffi = г^ = rik',nK

Выбор коэффициентов объясняется в следующем утверждении.

Утверждение 1. Пусть величина Ет^ представлена формальным рядом по п-1 и коэффициенты сц в формуле (29) определены согласно формуле (30). Тогда форлшлъный ряд для Еrffi имеет вид:

Положим

ф(п) = Erl1'. (31)

Сходимость оценки (29) показана в следующей теореме.

Теорема 6. Предположим, что существуют константы h > 0 и а > 0 такие, что для некоторого к = > 0 верно

А^ф(п) = (-l)*-^-1^-^! + С7(п-«)). (32) hrv.

Тогда константа h из (32) равна энтропии меры /1 для всех k < Kq и верно следующее равенство:

lim EqW = у.

п—*оо h

Доказательство теоремы основано на двух, интересных на наш взгляд, леммах.

Лемма 7. Если условие (32) выполнено для некоторого к = ко > О, то оно выполнено также для 0 < к < ко и

ф(п) = ^ + С0 + О(п'а): (33)

где

30 ( 1 = £ (м-) - ь

Лемма 8. Предположим, что существуют константы h > 0. а > О и С > 0 такие, что

выполнено для некоторого k = kQ > 0, где

\Фк{п)\ < СгГа. (35)

Тогда условия (34) и (35) верны для всех 0 < к < ко с некоторой константой С и справеддливы следующие равенства:

tf») = :£ + СЬ+ *,(«), (36)

где фо(п) определена в (35) и Со определена в лемме 7.

Вычислительный эксперимент подтвердил эффективность предложенного подхода.

Глава 4.

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

(37)

j=о N '

где ф — некоторая монотонная функция.

Предлагаемый в диссертации алгоритм позволяет находить величины ri^ для всех значений s ( пс такой же трудоемкостью (по порядку роста) как и величину r\k\

Трудоемкость алгоритма равна ö(mn), где т — длина слов. Нахождение оценок для различных значений п позволяет визуально наблюдать смещение, которое может зависеть от п.

Постановка задачи.

Пусть заданы п + 1 последовательностей £о = (з-оь ■ • •, Хот), -£n = (x„i,..., хпт), где Xij = {1,2,..., а}.

Будем предполагать, что применяемая метрика р на П она согласована с лексикографическим порядком, т.е.

р(х,у) < р(х, z} Ух ^ у =4 z. (38)

Алгоритм находит величины rf\ определенные по формуле (37), для всех k < s < п, 1 < I < к, где к - заданное число.

Описание алгоритма.

Работа алгоритма состоит из трех шагов.

1. Выполним сортировку слов ... ,£„ в возрастающем порядке. Пусть

- отсортированные слова, а а - перестановка такая, что

= t =0,1.... .п. Организуем слова щ, .... г/п в список с двумя связями.

2. Для j = 0,1,..., п и / = 1,2...., к находим

glj= min Wp(.Vi,4j)- (39)

Затем находим

(40)

г(0

п + ■ п

j=0

где I = 1,2.... ,к.

3. Для в — п,п — I,.... к делаем следующее:

(a) удаляем слова г/^ = из списка,

(b) для I — 1,2,... ,к и 3 = о., — I,... ,а3 + I находим величины <7у по формуле (39), нумерация по у идет но списку с двумя связями;

(c) для I = 1,2,..., к пересчитываем величины заменяя в формуле (40) величины дУ для ] = а$ — I,... 4-1.

Отметим, что величины дУ находятся последовательно для I — 1,2,..., к, поэтому для нахождения каждой величины дУ по формуле (39) достаточно находить минимум только из двух расстояний.

Легко видеть, что трудоемкость алгоритма равна 0{к2пт). Таким образом, при небольших к (не зависящих от п) трудоемкость алгоритма равна 0(пт).

Свойство согласованности (38) выполнено для метрик ро и р\ (см. формулы (1) и (11) соответственно), однако подчеркнем, что оно не выполнено для метрики

тп к=1

где в > 1.

Список литературы

1. A. Wyuer and J. Ziv. Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression. / A. Wyner and J. Ziv. - IEEE Trans. Inform. Theory, 1989. - No 35.

- pp. 1250-1258.

2. Grassberger, P. Estimating the information content of symbol sequences abd efficient codes. /Р. Grassberger - IEE Trans. Inform. Theory, 1989. - No 35. - pp. 669-675.

3. I. Kontoyiannis and Yu. M. Suhov. Prefixes and the entropy rate for long-range sources /' I. Kontoyiannis and Yu. M. Suhov. - Probability Statistics and Optimization; ed. P.P. Kelly. - Wiley, New York, 1994.

- pp. 89-98.

4. I. Kontoyiannis, P. H. Algoet, Yu. M. Suhov and A. J. Wyner. Nonpararnetric entropy estimation for stationary processes and random fields, with applications to English text. /I. Kontoyiannis, P. H. Algoet, Yu. M. Suhov and A. J. Wyner. - IEEE Trans. Inform! Theory, 1998. - N 44. - pp. 1319-1327.

5. Dobrushin, R.L. The simplified method of experimental estimatation of the entropy of stationary sequence. / R.L. Dobrushin. - Theor. Prob. AppL, 1958, - No 3. - pp. 462-464.

С. V. A. Vatutin and V. G. Mikhallov. Statistical estimation of the entropy of discrete random variables with a large number of outcomes. /V. A. Vatutin and V. G. Mikhallov. - Uspekhi Mat. Nauk, 1995. - No 55. - pp. 121-134.

7. R. Badii and A. Politi. Hausdorff dimension and uniformity factor of strange attractors. /R. Badii and A. Politi. - Pliys. Rev. Lett., 1984. - No 55. - pp. 1661-1664.

8. Billingsley. P. Ergodic Theory and Information. / P.Billingsley. -Wiley, New York, 1965. - pp. 120.

9. Shields, P.C.. Entropy and prefxes. /Р.С. Shields. - Annals of Probability, 1992. - No 20. - pp. 403-409.

10. Башарин, Г.П. О статистическом оценивании энтропии последовательности независимых случайных величин. /Т.П. Башарин. Теория вероятности и ее применение, 1959. - Т. IV, No 3. - С.361-364.

11. Колмогоров, А.Н. Теория информации и теория алгоритмов./ А.Н. Колмогоров. - М.: Наука, 1987. - 300 с.

12. Орнстейн, Д. Эргодическая теория, случайность и динамические системы. / Д. Орнстейн. - М.: Мир, 1971. - 166 с.

13. В.В. Майоров, Е.А.Тимофеев. Статистическая оценка обобщенных размерностей. /В.В. Майоров, Е.А.Тимофеев. // Мат. заметки. - 2002. - Т. 71. № 5. - С.679 - 712.

14. Тимофеев, Е.А. Статистически оцениваемые инварианты мер. / Е.А. Тимофеев // Алгебра и анализ. - 2005. - Т.17. No 3. - С.204-236.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в журналах из перечня ВАК:

1. Тимофеева, Н.Е. Экономный алгоритм нахождения средних минимальных расстояний / Н.Е. Тимофеева //' Моделирование и анализ информационных систем / Яросл. гос. ун-т. - Ярославль: Яр-ГУ, 2007. - Т. 14, No 3. - С.50-52.

2. A. Kaltchcnko, N. Timofeeva. Entropy Estimators with Almost Sure Convergence and an 0(n-1) Variance /' A. Kaltchenko and N. Timofeeva // Advances in Mathematics of Communications. - 2008. - Vol. 2, No 1. - pp. 1-13

3. A. Kaltchenko, N. Timofeeva, and E. Timofeev. Bias Reduction of the Nearest Neighbor Entropy Estimator /А. Kaltchenko, N. Timofeeva, and E. Timofeev // International Journal of Bifurcation and Chaos. -2008. - pp.3781-3787.

4. Тимофеева, Н.Е. Линейная метрика для оценивания энтропии / Н.Е. Тимофеева // Моделирование и анализ информационных систем / Яросл. гос. ун-т. - Ярославль: ЯрГУ, 2009. - Т. 16, No 1. -С.39-48.

5. A. Kaltchenko and N. Timofeeva. Rate of convergence of the Nearest Neighbor Entropy Estimator / A. Kaltchenko and N. Timofeeva // International Journal of Electronics and Communications. - 2010. -Vol.64. - pp.75-79.

Работы, опубликованные в других журналах:

6. A. Kaltchenko, Е-Н. Yang, and N. Timofeeva. Entropy Estimators with Almost Sure Convergence and an 0(n~l) Variance / A. Kaltchenko, E-H. Yang, and N. Timofeeva // Proceedings of the 2007 IEEE Information Theory Workshop / Lake Tahoe, California, USA, 2007. -pp.644 - 649.

7. A. Kaltchenko, I. Kotsireas, E-H. Yang, and N. Timofeeva. Entropy Rate Estimators with a Near-Optimal Upper Bound on Variance / A. Kaltchenko, I. Kotsireas, E-H. Yang, and N. Timofeeva // Proceedings of the XI International Symposium on Problems of Redundancy in Information and Control Systems / Saint Petersburg, Russia, 2007. -pp. 18 - 21.

8. A. Kaltchenko, E-H. Yang, and N. Timofeeva. Exact Analysis of the Bias of the Nearest Neighbor Entropy Estimator for I.I.D. Information Sources / A. Kaltchenko, E-H. Yang, and N. Timofeeva // Proceedings of the Forty-Fifth Annual Allerton Conference / University of Illinois at, Urbana-Champaign, IL, USA, 2007. - pp. 165- 168.

9. A. Kaltchenko. E-H. Yang, and N. Timofeeva. Bias Reduction of the Nearest Neighbor Entropy Estimator / A. Kaltchenko, E-H. Yang, and N. Timofeeva // Proceedings of the 2008 IEEE International Conference on Computational Technologies in Electrical and Electronics Engineering / Novosibirsk, Russia, 2008. - pp. 261 - 265.

10. A. Kaltchenko, N. Timofeeva. Bias Reduction via Linear Combination of Nearest Neighbor Entropy Estimators/ A. Kaltchenko, N. Timofeeva // International Journal of Information and Coding Theory. - 2009. - pp.39-56.

Оригинал-макет подготовлен в редакционно-издательском отделе ЯрГУ

Отпечатано на ризографе

Ярославский государственный университет 150000 Ярославль, ул. Советская. 14.

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

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

2) при оценивании энтропии динамических систем значения оценок не зависят от разбиения пространства;

3) в ряде случаев удается показать степенной порядок убывания смещения (для оценки из главы 2).

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

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

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

И = 1пп (1) л—*-1ЛО п где

Н = Я- • •, = ~ ]Г = ■ • ■. & = гп) \ogPfa = ¿1, .,£„ = О

11,.,<„6-4

В этой формуле логарифм обычно берегся по основанию 2.

Впервые эго понятие ввел К.Шеннон в 1948 г. (см. [37]). Он использовал его для измерения количества информации и показал, что энтропия определяет границу степени сжатия текста. Это одно из важных практических применений энтропии: почти любой текст £ь . нельзя закодировать менее, чем Нп символами.

В 50-е гг. А.П. Колмогоров перенес понятие энтропии на динамические системы (см. например [2], [29], [32], [26]).

Пусть (М,ц,Т) — динамическая система: Л/ — множество, // — мера па МиГ — измеримое преобразование множества М, сохраняющее меру, т.е. ц(Т — Для любого измеримого А.

Будем рассматривать конечные или счетные измеримые разбиения пространства М, т.е. наборы множеств а = {Аг}, Д- - измеримое, таких, что г((^| /1г) = ц(М) и /1(Лг Р) Л3) = 0 для любых 1 и

Считается, что ц(Аг) > 0 при всех i.

Энтропией разбиения а = {Ai} называется число i

Для разбиений а = {Ai}, ß = {В,} их произведением a\J ß назовем разбиение, элементами которого служат всевозможные множества вида Aif]Bj. Энтропией на символ разбиения а называется величина h(a, Т) = lim -Н(а \/ Та \/ . \/ Тпа). п-'ОО п V V V

Энтропией динамической системы (А/,/¿,Т) называется величина

ЦТ) = вир h(a,T), n где верхняя грань берегся по всем конечным птп счетным измеримым разбиениям а пространства М.

А.Н. Колмогоров показан, чю для многих разбиений энтропия на символ разбиения совпадает с энтропией динамической системы. А.Н. Колмогоров доказал, что энтропия есть инвариант динамической системы, изоморфные динамические системы имеют одинаковую энтропию. В частности, A.Ii. Колмогоров применил понятие энтропии для решения задачи об изоморфности сдвигов Вернул ли.

В 1971 г. Д.Орнстейп доказал утверждение, обратное теореме Колмогорова: если энтропии сдвигов Бериуллн одинаковы, то эти сдвиги изоморфны (см. [30], |29|). Эти исследования показывают важное теоретическое значение энтропии.

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

Задаче построения оценок энтропии посвящено большое число работ. Приведем краткий обзор известных в настоящее время результатов.

Существуют два основных подхода к построению оценок: построение эмпирической функции распределения и непараметрические оценки. Рассмотрим эти два подхода.

0.1 Построение эмпирической функции распределения

Определение (1) можно переписать в виде:

1,. ,гп ел E(-logP(eb.,£„)).

Эта формула показывает, что наибо ice естественный способ построения оценки — это прямое вычисление математического ожидания логарифма эмпирической функции распределения. Этот способ удобен, если число параметров, от которых зависит распределение, конечно.

Рассмотрим, например, бесконет шую случайную последовательность , которая принимает значения 0 и 1 независимо с вероятностями а и ¡3 соотвеетвенно Тогда, как показано в работе Шеннона [37], формула (1) принимает вид: h — —a log а — р log (3.

Если значения а и (3 неизвестны, то оценку энтропии можно посчитать простейшим способом. Рассмотрим достаточно длинную последовательность Пусть /„(0) и /п( 1) счетчики, сколько раз встретился 0 и I в конечной последовательности ., соответственно. Тогда оценка энтропии считается по формуле: h„ = —/„ (0) log /„(0) - /„(l)log/n(l).

Последовательность случайных величии hп сходится по вероятности к энтропии h. Также можно показать схочпмосгь почт ниол\ и справедливость центральной предельной теоремы: нормированные величины /;,, сходшся к нормальному распределению (см. [24]).

Если число параметров бесконечно или неизвестен вид зависимости от параметров, то этот подход применяется следующим образом.

Пусть Л — конечный алфавит и пусть w = и<\ . wm G Л7". Обозначим ц(и>) = Р(£i = wi,.,£m = wm). По теореме Шепнопа-МлкМиллапа-Брепмапа (см. [37]). случайные величины

Нт =--V fi(w) log fj.(w). rn ' we A1" сходятся к энтропии h для почти всех w.

Если процесс эргодический, то частота появления слова ги сходится к величине ¡-i(w). Таким образом, предлагается следующий способ построения оценки энтропии.

1) фиксируем бо 1ЫПОС число т:

2) рассмотрим достаточно длинную последовательность .

3) оценим числа fi{w), w € Лт, т.е. найдем частоты fn(w) всех слов w, w £ Ат в рассматриваемой нос 1едовательности, н, наконец, получим оценку h по формуле:

Кт = - Y1 /«И1оё/пИweAm

При п —> оо и т • оо величины hnm сходятся к /;.

Но в этом методе есть ряд существенных недостатков: неизвестно, что точно означают слова "болыное"т; что точно означает "болыпое"?7; двойной переход к бесконечности (по п и т).

Эти три недостатка делают этот метод неудобным д ш -теоретических исследований. Впервые такой подход к построению оценок энтропии описан Г.И.Башарииым [24]. Если же число возможных слов w G Лт экспоненциально растет, то этот метод становится не применим и в прикладных задачах.

Например, пусть |Д| = 2 и рассмотрим всевозможные слова длины 50. Число таких слов равно 2d0. Будем считать, что все эти слова возможны. Однако, современная техника позволяет получить последовательность длины п = 230 -т- 240 символов. Таким образом, вероятность получения каждого слова оценить невозможно, т.к. какие-то слова просто получены не будут. Значит оценить математическое ожидание эмпирической функции распределения также невозможно и об оценке энтропии речь идти не может.

Таким образом, этот метод не всегда возможно применить в прикладных задачах и он не слишком удобен, по вышеуказанным причинам, для теоретических исследовании. Более подробно на этом методе останавливаться не будем. Перейдем к рассмотрению второго метода

0.2 Непараметрические оценки.

Ненараметрические оценки энтропии могут быть поделены на два больших класса. Первый класс использует алгоритмы сжатия данных Лемпеля-Зива [22]. [23]. Второй класс основан на методе "расстояния до ближайших соседей".

0.2.1 Класс оценок, основанный на алгоритме Лемпеля-Зива.

Обзор этого алгоритма можно найти в работе [21]. Приведем краткое описание алгоритма.

Пусть а = ((in)neiv — последовательность элементов алфавита Л. Определим разложение Зива последовательности а как последовали1 1ьноеть (гип) = (ши(а)) пои, определяемых по индукции:

1. г/'о = а0

2. Пусть wi, u)2, ■ ■ ■ ,ii'k определены и wqU)\ . . w^ = o-oaj . an. Тогда

Пн = ftn-ii"ui2 • • Л|т, где т — наименьшее целое такое, что a„+1a„, 2. ■. ап+т {»'о, и)\,. Wk}- Для всех а 6 и для всех к £ N иотожим к п(к,а) = |^1(a)«;2(a) . . ?n(a)| = ^ |шг(а)|, 1 где через |ш| обозначена длина слова w.

Основной резул1>гат Лемпеля-Зива формулируется следующим образом:

Теорема 1. Если п —> оо, то случайная величина ^ц^а) сх°дится по вероятности к h — энтропии стационарного эргодического процесса.

П.Грасбергер, основываясь на этом алгоритме, предложил оценку величины обратной к энтропии, т.е. величины 1/h. |б[: у-п гп

К = , \ (2)

V logn где L" — наименьший префикс всех слов, начиная с г-го символа текста до п-го. Также он предположил, что у^п j-n ^ lim ———L = — почти всюду. (3)

-►оо /¿logn II

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

Используя результаты Д.С.Орнстеина и Б.Вейса [17], П.Шилдс (см. [18]) доказал, что эта оценка не является сходящейся дчя общих эргодических процессов.

В этой же рабо1 е П.Шилдс доказа ь ч 1 о при наложении определенных условий предложенная П.Грасбергером оценка (2) 6\дет состоятельной.

Теорема 2. Равенство

7 = 1 1 lim

П >эс П lüg П II, верно для независимых одинаково распределенных процессов, для перемещивающих цепей Маркова и для процессов с нулевой энтропией (в этом случае предел полагается равным -J-oo)

Основываясь на этом результате И.Контояннис п 10.М.Сухов [13] распространили оценку па более широкий класс стационарных эргодических процессов.

Теорема 3. Равенство

Em*) lim

7 = 1 1 п log п h верно для стационарных эргодичесиил процессов £ = (£„). построенных •над конечным, алфавитом, которые удовлетворяют условию Деблина: с уществует такое г ^ 1, что для почти вес л■ процессов inf Р{ХпЛ г = п\х „, = а о----,xn = an+m) ^ а > 0. о, ■

В работе [14] предложены три модификации оценки П.Грасбергера (2). Похожие оценки энтропии появляются в [19], |5|, где их работоспособность показана на обработке английских текстов.

0.2.2 Метод "расстояния до ближайших соседей".

Первую оценку такого рода предложил Р.Л.Добрунштт [4]. Он сделал это следующим образом.

Рассмотрим класс последова течьиостей, образованный конечно зависимыми величинами ц1. • • •• т.е. пусть л' — параметр конечной зависимости, тогда если ,., и — наборы случайных величии и ¿1 <.<%).< < . < го при

3\ ~ 1к > величины . не зависят от .

При оценивании энтропии этой последовательности можно применить следующий прием. Для некоторого натурального числа Т из последовательности {&} выбираются отрезки длины Т с пропусками длины я между ними и формируется последовательность векторов длины Т: где = (£(74-0(7-1) I 1----1 непоследовательность образована независимыми одинаково распределенными случайными величинами. Энтропия этой последовательности совпадает с энтропией /г исходной послсдова1 етьностн ([4]).

Таким образом, энтропия оценивается следующим образом.

Рассмотрим последовательность серий независимых одинаково распределенных случайных величин и положим N = \Л\1. v

Р{£ = к} = рь /с = 1. 2.N ]Г> = 1. с=1

Величины рк и /V зависят от Т: р*. = рА (7-1) иАС-»^ при Г —> оо. Требуется оцепить эитропшо к. Положим

71 =шш{?(, ^ 1 Ч'чи =£1'}, г, = тш{п ^ 1 : = Г ^ 2, о = 1, = Г! + . -г гг1 4- 1, г = 2, 3,---

В качестве оценки /г берется выражение;

- 1 г, = — ^ 1 пт7 + С. т

1 — 1 где С - константа, Эйлера. С = 0.5772157., а т вычисляется в процессе работы и зависит от числа символов исходной последовательности.

Таким образом, Р. I Добрушпн предложил следующий прием построения оценок: если ранее рассматривалась одна бесконечная последовательность (как в определение (2)), то при новом подходе рассматривается бесконечное число конечных последовательностей.

В.А.Ватутин и В.Г.Михайлов [20] нашли смещение оценки Р.Л.Добрушина, оценили значение ее дисперсии и доказали соеюятепьность.

Теорема 4. Для некоторого вг 6 (0.13, 0.578)

ЕЙ = Н+\ь\ + вхР2.

Теорема 5. Пусть р ^ 0.377. Тогда

ВЫ = — [В2 - /г + П + -А - (/г + 1Ж - вхНР2 + в2Р2) , т \ 2 ) где вх £ (0.13, 0.578) и в2 е (-3.83, 2.202).

Теорема 6. Пусть при Т —» ос параметры схемы меняются так, чти

1 1 + Я, - 4Д,/1 + 6Б2Л2 - З/г4 т2 3 1 -т- (Zi2 - Д2)2

0. тогда распределение случайной величины (Н — EiH)(Dh) 112 сходится при Т —► оо к: нормальному стандартному распределению.

В формулировках теорем Р2, В2, D, Вз, В.х — это константы, определенные в работе [20].

Позднее исследователи развили идею Р.Л.Добрушина следующим образом.

Пусть Q — пространство последовательностей, р — некоторая метрика на Q. ¡л — мера на Q, . ., — независимые одинаково распределенные по мере д случайные точки из Г2.

Расстояние между точками определяется по формуле:

Гп = -- V*lo s (minpte.i,)) . (4) п ' )

Тогда оценка энтропии считается по формуле:

К = -т^—- (5) log п

В этих формулах логарифм может браться по любому основанию.

В случае произвольной метрики р величина hn оценивает обратную размерность меры ц. В работе [33] приведен следующий пример, который показывает, что в обычном евклидовом пространстве предлагаемая оценка совпадает с размерностью.

Пример. Пусть Q — .ч-мерный куб с обычной метрикой и лебеговой мерой /л. Пусть ■ • • Лп — независимые точки равномерно распределенные в Q, тогда среднее минимальное расстояние ги между точками si, £2, ^-мерном кубе равно 0(n~ll/s). Оценка энтропии совпадает величиной i/s.

Р.Бадии и А.Полити [1] предложили оценивать размерность Хаусдорфа в общем метрическом пространстве, основываясь на величине

П.Биллингслей [2] показал, что при выборе подходящей метрики энтропия совпадает с размерностью Хаусдорфа.

Основываясь на результатах Р.Бадии и А.Полити, П.Грассбергер ввел свою вторую оценку энтропии на пространстве = 4N (см. [6]) hu = -ГТ~Г JZ 1о& С?)) ' (6)

71 log 77 ^ где метрика р(х,у) = 2-m'm{k:Xh^Vk],

И X = {хиХ2, . . .), У = {?Уь 1/2, - - •}•

Он также предположил существование следующего предела: lini hn = — почти всюду. п—> ОО h

Пример, приведенный П.Шилдсом в работе [18], показывает, что оценка П.Грасс-бергера (6) несостоятельна для общего эргодического процесса.

В этой же работе П.Шилдс показал, что предлагаемая П.Грасбергером оценка (5) состоятельна для неприводимых непериодических марковских цепей. В работах [28], |33] было введено обобщение оценки (5): —

-¿logLm(fcV(eb^)V (7) п log п где для любого упорядоченного множества хх ^ х2 ^ . . . ^ xN min^jx'i,. . , xN} полагается равным Хк. Было показано (ем.|33|), что дисперсия оценки (7) имеет порядок 0(п~с), где с — некоторая константа:

Теорема 7. Пусть выполнено условие

Ч-'ОО In и u->ос In и

Тогда для с < min{fi2, d/d, 1}«

Здесь B(x.r) — шар с центром в точке х радиуса г.

Отметим, что оба класса непараметрических оценок связаны между собой. Действительно, оцеика( 2) связана с оцопкой( 6) следующим образом. Если

К =--;п log п где

Ра = i ' "J ' min{A : хк ф <д.}'

Тогда величина (м)(ч,.ч;)) 1 равна длине наименьшего префикса между словами и увеличенного на единицу.

0.3 Результаты диссертации

Перейдем к описанию результатов диссертации.

Рассматривается пространство нос. юдователышетеп О = Пусть ¡1 — эргодпче-ская. инвариантная относительно сдвига мера на пространстве Пусть — независимые, одинаково распределенные по мере /./ случайные точки из П.

Если рассматривается прикладная задача, то задано п слов длины т. В этом случае, считаем, что эти слова совпадают с первыми т символами точек ¿д,.,^ и будем обозначать эти слова через . -. чп"1

Нужно построить оценку величины обратной к энтропии.

В каждой главе предлагается сном оценка энтропии, в зависимости от того какая метрика задана на пространстве П.

3.4 Заключение

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

Глава 4

Для построения оценок энтропии в главах 1-3 и построения оценок размерности в работе [28] нужно находить следующую величину:

Г"Л) = ^ТТ ^ ф (-Й(к)р{^ ' ^ где ф — некоторая монотонная функция. В этой главе предлагается алгоритм нахождения величин для всех значении я ^ п. Результат опубликован в работе |36].

Трудоемкость алгоритма равна 0(гип), где т —длина строк. Таким образом, нахож

О (к) (к^ дение всех величин гк .гк+1.г„ имеет такую же трудоемкость но порядку роста как и нахождение одной величины . Нахождение оценок различных для значений п позволяет определить смещение, которое зависит от п.

4.1 Постановка задачи

Пусть заданы и + 1 последовательностей £0 = (®оь • • •, х0т).= • -.Хлт), г,те х,3 € Л ={1,2,., а}.

Будем обозначать лексикографический порядок на пространстве = Л"1 через х =<: У

Пусть на задана метрика р, п])о которую будем предполагать, что она согласована с порядком, т.е. у) < р(х, г) Ух 4 г. (4.2)

Требуется найти величины г[1\ заданные по формуле (4.1), для всех к < я < п, 1 < I < к, где к - заданное число.

4.2 Описание алгоритма

На вход алгоритма подается последовательность ■ - - функция ф, параметр к. к1

В результате работы алгоритма получаем величины 7^ для всех к < в ^ п. Работа алгоритма состоит из трех шагов.

1. Выполним сортировку строк £„, в возрастающем порядке. Пусть

7]0 =4 ■ ■ • Г]п

- отсортированные строки, а а - перестановка такая, что

Пег, = г = 0,1,., п. Организуем строки г]0, . г}п в двусвязаииый список. 2. Для j = 0, 1,. . , п и / = 1, 2,. . . , к находим величины

9j= min Mpirn.Tij). (4.3)

Затем считаем величины где / = 1,2.к.

3 Для 5 = п. п — 1. . . , к делаем следующее: a) удаляем строку г)СГв — из двусвязанного списка, потому что для нахождения г{к^ величина £а не нужна, ее уже нет в формуле (4.1). b) для / = 1.2, . . ., к и j = I. . . , а3 + 1 находим величины д1- по формуле (4.3); c) для I = 1.2.к пересчитываем величины заменяя в формуле (4.4) величины д13 д. ш ] = ст., — /. , стЛ + I.

Отметим, что нумерация по 7 на шаге ЗЬ идет по двусвязанному списку. Отметим также, что поскольку величины д' находятся последовательно для I = 1,2.,/с, то для нахождения каждой величины д^ по формуле (4.3) достаточно находить минимум только из двух расстояний.

Пример работы алгоритма будет приведен в п.4.6.

4.3 Обоснование алгоритма

Покажем, что в результате работы алгоритма были найдены значения величин i-k, определенные в формуле (4.1), где s ^ vi. Действительно, по свойству согласованности (2.9) min ik)p(rjh rfc) = . min . {k)р{тц, rjj). r.lyij iT3'J^kS^S3+k

Т.к. на этапе (Зс) в (формуле (4.4) поменялись значения величии дк только для j = as — /,., CTj,. + /, то для подсчета нужно заменить в формуле (4.4) только значения этих

1 1 'л (к) величин и поменять множитель —цт па Это озпачаел-, что величины Гп , панде

S+1 иные по формулам (4.4) и (4.1), совпадают'.

4.4 Трудоемкость алгоритма

Трудоемкость шага 1 равна 0(пт). Приведем алгоритм, с помощью которого можно получить названную трудоемкость.

Вспомним, что координаты точки принадлежат Л. Воспользуемся этим. Пусть А = [а.\., o.q}, £oi - ■ - ■ , — первые координаты точек . . . , Сделаем следующее: 1. Посчитаем величины кг — сколько раз а, встречается в последовательности оъ • • • j 12. Посчитаем "границы": (7г = О, G2 = к\. G¿ = к\ + к2, ■ ■., Gm^ i = ki + . kq = n + 1. 3. Для каждого О г ^ q делаем следующее: если == аь то ставим на место G¿, G¿ заменяем на + 1, остальные границы пе меняем.

В результате получаем последовательность точек . ., отсортированных по первой координате. Всего т координат, значит трудоемкость первого niara равна 0(пт). На остальных шагах наиболее трудоемкой операцией является нахождение расстояния между двумя строками. Будем считать, что ее трудоемкость равна 0(т), т.к. метрика произвольна:.

Трудоемкость шага 2 равна 0(k2vm). Действительно, для нахождения (]13 нужно выполнить 21 + 1 нахождение расстояний, которое по предположению делаются с трудоемкостью 0(т). Это повторяется пк раз Значит, трудоемкость равна

2к + 1)пкО(т), как и утверждалось.

Трудоемкость шага 3 равна 0(кгпт), г к. для каждого s пересчптывается 2к + 1 значение в формуле (4.4).

Итак, трудоемкость алгоритма равна 0(к2пт).

Подчеркнем, что при небольших к (не зависящих от п) трудоемкость алгоритма равна 0(пт).

4.5 Свойство согласованности

Нетрудно видеть, что свойство согласованности (2.9) выполняется для метрики

Ро(я,у)= , 1-г-(4.5) mm {к : :гк ф ук} где х — (х\,х-2, ■ ■ ■), и у = 0/1,г/2> • • • )• Действительно, пусть х, у, z — три точки, связанные соотношением:

Распишем это: х 3 У <=> X! = /Уь .То - У2,---, -П < Ук

У -< z г/i = zuy2 = г2,. ,ут < =т.

Рассмотрим два случая. Случай 1: т < к. Тогда

Х\ = Z1, . . . . Хп!— 1 — Zrn \, хт — ут ^ . следовательно. 1

Л)(х, z) = —. m

Значит свойство сог тсовапности имеет вид 11 , Ро(х,у) = - < — = А)(х, z), с 1 п что верно, т.к. по предположению m < к. Сличай 2: m ^ к. Тогда

Xi = zu . . . ,.ТА! = zk-i,xk < ук <= zk,---

Следовательно.

Po(x. z) = и свойство согласованности иереписывае геи следующим образом

N 1 / N 1

Ро(х,у) = j ^ Po(x.z) = -, чю. очевидно, верно. Для метрики m px{x,ij) = J2e~k\xk-Vk\, (4.6) fc=i где в > 1, свойство согласованности не выполнено.

4.6 Пример работы алгоритма

Положим к = 2, ф = х"1. Рассмотрим десять точек. = (0,0,0,0,0); = (0,0,1,1,0); 6 = (0,0.0,1,0); ^ = (0,0,1,0,0); ^ = (0.1,1,1,0); (0,1,1,1,1); & = (0,0, 0,0,1); & = (1,1,1,1,1). & = (0,0,0,1.1); = (0,0,1,1,1);

На первом шаге работы алюритма нужно эти точки упорядочить. Сделаем это: = (0,0,0,0,0); (0.0,0.0,1) т - (0.0,0. 1,0) ш = (0,0,0.1,1)

Ц\ = (0.0,1,0,0) т> = (0.0.1.1,0)

Vg = (0,0,1,1,1)

V- = (0,1,1,1,0)

Пя = (0,1,1,1,1)

Щ = (1,L, 1,1,1)

Выпишем перестановку: ст0 = 0, сг\ = 5, а2 = 2, сг3 = 4. <74 = 7, сг5 = 8, сте = П "г = <т8 = 3,а9 = 6.

Перейдем ко второму шагу: j = 0,., 9, I = 1,2. Посчитаем д^р. Пусть 1 = 1.

Тогда д[р = min 7/i) = pfao, 7?i) = о = min(1){p(//o,/?i),/y(77b?72)) = р{-П2,т) = р g¡1} = тт(1){р(?]1,г/2),р(772,г?з)} = О r/.^ = min(1){p(77o. '/з),р(т,щ)} = l] О g[1] = mm(1){/4'M-//i). p(??4, %)} = min ll1{/4'/i-= 7; O g£l) = min (n{/'(//;,.//„)■ /Ч'А- ^7)} = 7: O min(1){/)(//í;, ?/7),/;(//7л/8)} = 7; O

1} = min(1){p(í/7. '/s),p('/s,7]9)} = 7: min(1V(//8 , 779) = 1.

Следовательно, x) 1 1 5 + 5 + 5 + 5 + 4 + 5 + 5 + 5 + 5+1

7-9 10 ~ '5j=o

Выполним второй шаг алгоритма для I = 2. дР = min (2){р(?]о, /7г), р(г?0, %)} = 5G gW =inin [2) {р(т]о,т)- ('Uli - П2)* pOh- Пз)} = p(vi,V 2) = I', 0 gf] = тт{2){р(гю,г]2), p(rii,V2), p(V2iih)- p(V2^]i)} == minj/^b щ), 774)} = = min {2){p(t]i, 77.0, = rain(2){p(7?4,?y6);p(7?5,7/6),p(7/7^6),p(7/8,776)} = с/72) = mill (2){р(??5, Г)7), p(r/G, Г]7),р{щ, 777), /3(779,777)} =

722) = min (2) {^('/'/0, '/2). /0(771. П2),р(г}2, m),P(V2, V4)} =

Огмогим, нто при вычислении второго минимума из четырех чисел достаточно вычис-1ягь минимум только из двух чисел. Действительно, число, на котором достигается первый минимум, в сравнении не участвует, т.к. второй минимум больше либо равен первом>'. Из оставшихся трех чисел достаточно сравнить два близ лежащих, т.к. точки упорядочены п чем дальше точки лежат- друг от друга, тем больше расстояние между ними

Теперь легко вычислить 4 + 4 + 44-4 + 4 — 4 + 5 + 2 + 2 + 1 n „ г\' =---= 3,4.

9 10

Прежде чем переходить к третьему шаг\ а п оритма посчитаем вспомогательные суммы: 41) = г^ • 10 - ((£>) ' - (г/,п) 1 - "l = 4, 5 • 10 - 5 - 5 - 5 = 30.

42) = = Ю-3,4-4-4-4-2-4 = 16.

Третий шаг. s = {

Пусть I = 1, тогда

Третий шаг. s = 9. Удаляем = щ. Пересчитываем д^ для / = 1, 2 и j — 6 — 1,. , 6+/. ш (1).1 gl = min{р(/71. //;,), р(//5. i/o)} дР = min{/5(?77,i/-,), /7(777, %)} = го

1).1 5

Теперь можно найти г^.

-г ) -г [д7 ) 30 + 5 + 5 40

Гя1) " 9 " 9 " У'

2)

Теперь сделаем тоже самое для I = 2. Пересчитываем дк для j = 4,., 8. gf] = min {2){p(r] 4,772), р(щ. Пъ),р{щ- ф), р(щ, щ)} =

Тогда

7^2) = т1П(2){р(г)7,1]Г1),р(1];-щ),р(г17,щ),р(г]71г]9)} = = тт (2){Мг/8, 77, т),р(ш, Ла)} =

Х2) + 1 + 16 + 3 + 3 + 2 + 2.

7 о — „ — , 1),

8 9 9

Далее слюна находится г)г, которую нужно удалить из списка и действия повторяются, рассмотрение примера закончено.

1. Badii, R. Hauhdorif dimension and uniiormity factor of strange attractors // Badii R., Politi A. / Pins Rev. Lett. - 198 1. - ,Y" 52. - pp. 1661-1664.

2. Billingsley, P. Ergodio Theory and Information / Billingsley P. Wiley, New York, 1965.

3. Devroye, L Exponential meqnalties in nonparametric estimation // Devroye L., G. Roussas, editor Xonpaiamei i i ic Functional Estimation and Related Topics, NATO ASI Series. Kluwer Academic PubLshei>. Dordrecht. -1991. pp. 31-44.

4. Dobrushin. R.L. The simplified method of experimental estimatation of the entropy of stationary sequence Dobrushin R L ' Theor. Prob. Appl. 1958. - JVs 3. - pp. 462-464.

5. Grassberger, P. Estimating the information content of sybol sequences abd efficient codes

6. Giassberger P. / 1EE Trans. Inform. Theory. 1989. - 35 - pp. 669-675.

7. Kaltchenko, A., Timofeeva. N. Entropy Estimators with Almost Sure Convergence and an O(n-l) Variance // Kaltchenko A., Timofeeva N. / Advances in Mathematics of Communications. Feb. 2008. - Vol. 2, No. 1. - pp. 1-13.

8. Kaltchenko, A., Timofeeva, N., Timofeev, E. Bias Reduction of the Nearest Neighbor Entropy Estimator // Kaltchenko A., Timofeeva N., Timofeev E. / International Journal of Bifurcation and Chaos. 2008. - pp. 3781 -8787.

9. Kaltchcnko, A., Timofceva, N. Rate of convergence of the nearest neighbor entropy estimator // Kaltchenko A., Timofeeva N. ' Int. Л. Electron. Conmnm. (AEU). 2008.- V. 62, No 12.

10. Kontoyiannis, I., Suhov, Yu.M. Prefixes and the entropy rate for long-range sources // Kontoyiannis I., Suhov Yu.M. / Probability Statistics and Optimization (cd. F.P. Kelly).- Wiley, New York. 1994. - pp. 89-98.

11. Marsaglia, G. Zainan. A. A New Class of Random Number Generators // Marsaglia G., Zaman A. ' Annals of Applied Piobabilitv. 1991. - V.3, Л'а.З. - pp. 462-480.

12. McDiarmid. С On the method of bounded differences. / McDiarmid C. Surveys in Combinatorics. Cambridge Univeinity Press, Cambridge, 1989. pp. 148-188.

13. Ornstein, 13.S. Weiss. B. Entrop\ and data compression schemes // Ornstein D.S., Weiss B. / IEEE Trans. Inform. Theory. 1993. - № 39. - pp. 78-83.

14. Shields, P.O. Entropy and prefxes Shields P.C. / Annals of Probability. 1992. -20. - pp. 403-409.

15. Schurmann, Т., Grassbergcr, P. Entropy estimation of symbol sequences // Schurmann Т., Grassberger P. / Chaos. 1996. - .V* 6. - pp. 414-427.

16. Yatutin. V.A. Mikhailov, V.G. Statistical estimation of the entropy of discrete random variables with a large number of outcomes // Vatutin V.A., Mikhailov V.G. / Uspekhi Mat. Nauk. 1995. - ,\s 50. - pp. 121-134.

17. Wvner. A., Ziv, ,J. Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression // Wyner A. Ziv J. / IEEE Trans. Inform. Theory. 1989. 35. - pp. 1250-1258.

18. Ziv. J. Lempel, A. A universal algorithm for sequential data compression // Ziv J., Lempel A. / IEEE Trans. Inform. Theory. 1977. - № 23. - pp. 337-343.

19. Ziv. J. Lempel, A. Compression of individual sequences via variable-rate coding // Ziv J. Lempel A. / IEEE Trans. Inform. Theory. 1978. - № 24. - pp. 530-536.

20. Башарин, Г.П. О статистическом оценивании энтропии последовательности независимых случайных величин. // Башарин Г.П. / Теория вероятности и ее применение.- 1959. Т. IV, Лг-°3. - с. 361-364.

21. Грапдштейп, И.С., Рыжик, И.М. Таблица интегралов, рядов и производных // Грандштейн И.С., Рыжик И.М. Академическое издеине, пятая редация, 1994.

22. Колмогоров, А.Н. Теория информации и теория алгоритмов. / Колмогоров А.Н. -М.: Наука, 1987.

23. Крамер, Г. .Математические методы статистики. / Крамер Г. М.: Мир, 1975.

24. Майоров. В.В., Тимофеев, Е.А. Статистическая оценка обобщенных размерностей // Майоров В.В., Тимофеев Е.Л 1 Мат. заметки 2002. - Т. 71. Лг» 5. - с. 679 - 712.

25. Мартин, Н. Инг. юнд, Дж. Математическая теория энтропии. / Мартин Ii., Ингленд Дж. М.:Мнр. 1988.

26. Ористейн, Д. Эргодическая теория, случайность и динамические системы. Орн-стейн Д. М.: Мир.

27. Синай, Я.Г. Современные проблемы эргодичеекой теории. / Сипай Я.Г. М.:Физ,-мат чпт., 1995.

28. Синап. Я.Г. Введение в эргодическую теорию. / Синай Я.Г. М.:ФАЗИС, 1996.

29. Тимофеев. Е.А. Состоятельная оценка энтропии мер и динамических систем. // Тимофеев Е.А. ,/ Мат. заметки 2005. - .X'- 77. - с. 903-916.

30. Тимофеев, Е.А. Статистически оцениваемые инварианты мер // Тимофеев Е.А. / Алгебра и анализ. 2005. - Т. 17. .\'о 3. - с. 204-236.

31. Тимофеева, Н.Е. Линейная метрика для оценивания энтропии. // Тимофеева Н.Е.

32. Модсл. и анализ пнформ. систем. 2009. - Т.16, №1. - с.39-48.36. 'Тимофеева, Н.Е. Эффективный алгоритм нахождения средних минимальных расстояний // Тимофеева Н.Е. / Модсл. и анализ информ. систем. 2007. - Т.14, No 3. - с.50-52.

33. Шеннон, К. Работы по теории информации и кибернетике./ Шеннон К. М.: Изд-во иностр. литерачуры, 1963.1. Глава 5