Задания для спецпрактикума "Анализ временных рядов"

Лабораторная работа No.5

Главная К52

Теоретические сведения к лабораторной работе No. 5
практикума "Анализ временных рядов":

Меры сложности. Расчет энтропии источника.

Энтропия источника

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

Исторически понятие энтропии было введено Больцманом в термодинамике. В 40-х годах 20-го века концепция Больцмана была обобщена Шенноном на случай символьных последовательностей для того, чтобы иметь возможность охарактеризовать последовательность символов с точки зрения ее упорядоченности.

Предположим, что мы рассматриваем символьную последовательность, составленную из алфавита, содержащего $\lambda$ возможных символов. Предположим также для простоты, что все символы являются независимыми и равновероятными. В этом случае энтропия $H$ интерпретируется как информация о получении некоторого символа $S$ с вероятностью $1/\lambda$. Формула для энтропии записывается с учетом нескольких обстоятельств, а именно:

• Допустим, что мы получаем по буквам какой-то текст. Пока мы его еще не получили целиком, существует неопределенность о последующих символах. Получение каждого нового символа $S$ эту неопределенность уменьшает. При этом считается, что неопределенность, которая устраняется при получении символа $S$, будет тем меньше, чем больше вероятность символа ($P$). Редко встречающиеся (мало ожидаемые) символы несут больше информации, чем часто встречающиеся (более ожидаемые) символы. С точки зрения математики это означает, что
  
  $$H = f \left({1 \over P} \right),$$
  
  
  где $P$ - вероятность, $f$ - некоторая функция, которая будет монотонно увеличиваться с ростом $1/P$.
• Количество информации, которое несут $N$ независимых символов $S_1$, $S_2$, $\ldots$, $S_N$, должно определяться следующим образом:
  
  $$H(S_1, S_2, \ldots, S_N) = H(S_1) + H(S_2) + \ldots + H(S_N)$$
  
  

  
  

  $$f \left({1 \over P^N} \right) = N f \left({1 \over P} \right),$$
  
  
  а такими свойствами обладает логарифмическая функция.

Следовательно, формула для $H$ должна иметь вид:

$$H = \log \left({1 \over P} \right) = - \log P.$$

Если символы не являются равновероятными, то необходимо провести усреднение по всем возможным $\lambda$ символам, чтобы получить величину, которая характеризует среднюю меру неопределенности о символе (сообщении) до его приема:

$$H = \left< - \log P_i \right> = - \sum_{i=1}^{\lambda} P_i \log P_i.$$

Обычно логарифмы берутся по основанию $\lambda$.

Что может сообщить энтропия о последовательности символов? Здесь нужно обратить внимание на одно обстоятельство. Меры сложности (и, в частности, энтропия) широко применяются при анализе структуры не только текстов и ''естественных'' символьных последовательностей (таких как цепочка нуклеотидов ДНК), но и временных рядов самого различного происхождения. Часто расчет энтропии проводится в целях получения количественной характеристики сложности изучаемого процесса; при этом используется символьное представление сигналов (в простейшем случае сигнал преобразуется в бинарный код). Например, если наблюдаемая переменная в данный момент времени принимает значение больше среднего, то в качестве очередного символа бинарного кода выбирается ``1'', если меньше среднего - ``0'' и т.п. Анализ последовательностей символов вместо временного ряда осуществляется в рамках так называемой символьной динамики. В данной работе для простоты мы ограничимся только рассмотрением случая бинарных кодов.

Итак, пусть анализируется последовательность из ``0'' и ``1''; вероятности данных символов соответственно равны $P_0$ и $P_1=1-P_0$. Если логарифм вычисляется по основанию 2, то энтропия будет принимать значения в интервале от 0 до 1. $H=1$, если вероятности одинаковы $P_0=P_1=0.5$; $H=0$, если постоянно генерируется только один символ ($P_1=1$ или $P_1=0$). Энтропии в диапазоне от 0 до 1 характеризуют степень порядка в последовательности. Значения вблизи нуля указывают на то, что один символ доминирует, например, $H \approx 0.08$ для $P_0=0.01$ и $P_1=0.99$. Если же вероятности почти одинаковы, то значение $H$ близко к 1, например, $H \approx 0.992$ для $P_0=0.45$ и $P_1=0.55$.

Однако, рассматриваемое определение энтропии дает не так уж много полезной информации. Например, принципиально различные процессы могут иметь одно и то же значение энтропии. Рассмотрим две последовательности:

$$A_1 = \ldots 1010101010 \ldots$$

и

$$A_2 = \ldots 1101110000 \ldots,$$

Если в обоих случаях $P_0=P_1=0.5$, то $H=1$ как для периодической ($A_1$), так и для случайной последовательности ($A_2$).

Данный недостаток можно устранить, если вычислять блочные энтропии (или энтропии высокого порядка). Рассмотрим вначале вероятности встретить различные блоки из 2-х символов: ``00'', ``01'', ``10'', ``11''. Если мы будем анализировать вероятности данных блоков для последовательностей $A_1$ и $A_2$, то получатся различные величины. Можно ввести более общую характеристику - $n$-блочную энтропию:

$$H_n = - \sum_{i=1} P_i^{(n)} \log_{\lambda} P_i^{(n)},$$

которая определяет среднее количество информации, содержащееся в блоке из $n$ символов. Здесь $P_i^{(n)}$ - вероятности блоков из $n$ символов ( $S_1,\ldots,S_n$), а суммирование проводится по всем встречающимся блокам.

Если энтропии отдельных символов не позволяют получать много информации об особенностях анализируемых последовательностей, то блочные энтропии $H_1, H_2, \ldots, H_n$ служат более информативными характеристиками структуры последовательностей символов. В частных случаях может наблюдаться характерное поведение для блочных энтропий:

• Для последовательности Бернулли (последовательности, в которой любые блоки из $n$ символов имеют равные вероятности $P^{(n)} = 1/\lambda^n$):
  
  $$H_n=n\log(\lambda).$$
  
  

• Для марковских процессов порядка $k$ наблюдается линейный рост энтропий при $n \geq k$:
  
  $$H_n=H_k + (n-k)(H_{k+1}-H_k); \hspace{1cm} n \geq k.$$
  
  

• Для периодических последовательностей с периодом $q$ достаточно знать только $q$ символов, поскольку остальные не несут новой информации. Вследствие этого
  
  $$H_n=H_q; \hspace{1cm} n \geq q.$$
  
  

Символьные последовательности, несущие какую-либо полезную информацию, должны находиться между случаем полной неупорядоченности и периодическими последовательностями. Для них приращения $H_{n+1}-H_{n}$ уменьшаются при возрастании $n$, что является следствием эффектов ``длительной памяти''. Чтобы охарактеризовать приращения блочных энтропий, рассматривают так называемые разностные блочные энтропии (называемые также динамическими энтропиями):

$$h_n = H_{n+1} - H_n.$$

Их можно интерпретировать как среднюю неопределенность о символе, если известны $n$ предшествующих символов. Поскольку чем больше символов мы знаем, тем меньше неопределенность о сообщении (в среднем), то значения $h_n$ монотонно уменьшаются. Предел

$$h = \lim_{n \rightarrow \infty} \frac{H_n}{n} = \lim_{n \rightarrow \infty} h_n$$

называется энтропией источника. $h$ принимает максимальное значение ($h=1$) для полностью случайного процесса (белого шума) и минимальное ($h=0$) для периодических процессов. Для последовательностей, несущих полезную информацию, $0 < h < 1$.

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

$$P_i = {k_i \over M},$$

где $M$ - число блоков, $k_i$ - число появлений интересующего нас блока. При работе с конечными последовательностями символов оценки вероятностей больших блоков будут очень неточными из-за сильно возрастающего числа вариантов всевозможных блоков. В этом случае возникают недостоверные оценки энтропий, например, при $n > 6$ (в случае последовательности из 10000 символов), либо $n>9$ (в случае 100000 символов). На практике предел $n \rightarrow \infty$ является бессмысленным, и реально можно оценивать блочные энтропии для относительно небольших $n$ (причем, эти оценки будут давать весьма ценную информацию об особенностях сложной структуры последовательности символов или исходного временного ряда).

Энтропию источника иногда определяют другим способом (без расчета блочных энтропий). В качестве примера рассмотрим определение сложности Лемпеля-Зива. Идея предложенного ими алгоритма состоит в следующем. Последовательность символов разбивается на фрагменты, и метками отмечаются фрагменты, которые ранее еще не были идентифицированы. Например, пусть есть последовательность $100110$ и мы определяем различные фрагменты: $1 \cdot 0 \cdot 01 \cdot 10$. Число полученных таким способом фрагментов $C$ может служить мерой сложности. Естественно, что в общем случае $C$ будет увеличиваться с ростом числа символов $N$ последовательности. Для случайных бинарных кодов ($P_0=P_1=0.5$) с ростом $N$ наблюдается следующее поведение для числа фрагментов:

$$C(N) \rightarrow {N \over \log_2(N)}.$$

Для не совсем случайных последовательностей

$$C(N) \rightarrow h {N \over \log_2(N)},$$

где $h$ - энтропия источника. Чтобы характеристика сложности не зависела от $N$, проводят нормировку на значение $N / \log_2(N)$. В этом случае подход Лемпеля-Зива позволяет непосредственно оценивать значение $h$.

Возможность разбить последовательность символов на участки по определенным правилам имеет важное значение в задачах сжатия данных. Одним из потенциальных приложений задач об исследовании мер сложности является создание алгоритмов оптимального архивирования данных. В частности, подход Лемпеля-Зива реализован в известной программе ``gzip''.