1.3. Информация, энтропия и моделирование данных

Пусть А - некоторое событие, появляющееся с вероятностью Р (А). Тогда информация, сопоставленная А, определяется как:

/(Л) = 1о^-^- = -1о^Р(Л) Р(А)

Заметим, что когда Р(А) велико, то ЦА) мало, а когда Р(А) = I то ЦА) = 0. Маловероятные события несут очень много информации, в то время как достоверные события несу! очень мало информации. Если вы скажете, что этой зимой на Аляске пойдет снег, вы не дадите много информации. Но если вы скажете, что Флорида будет покрыта снегом, то потом, возможно, станете свидетелем бума на рынке апельсинового сока.

В литературе по теории информации процесс, который поро* ждает случайные события А/, называется источником. ПреД' положим, что имеется множество независимых событий А' появляющихся с вероятностями Р(Д/). Энтропия источника, сопоставленного этим событиям, - это средняя информации

(1.3.2)

Н = ^Р(А])ЦА])

Введение

23

Для наших целей мы будем рассматривать изображения в качестве источников. Предположим, что Ajtj = 1, п представляет последовательность пикселов изображения, и пусть х, основание логарифмической функции в (1.3.1), равняется 2. Тогда энтропия изображения - это мера среднего количества бит, необходимых, чтобы закодировать значения пикселов.

Вообще, мы не можем знать истинную энтропию источника, потому что мы не знаем истинные значения P(Aj ) в (1.3.2). Лучшее, что мы можем сделать, это оценить значения P(Aj) и использовать (1.3.2), чтобы получить оценки для явной энтропии (apparent entropy) источника.

Распознавание структуры данных может уменьшать явную энтропию. Рассмотрим следующий пример из книги Клайда Сейвуда (Klaid Sayood) [40]. Начинаем с последовательности

12123333123333123312

Если мы игнорируем структуру и рассмотрим числа по отдельности, то увидим три символа 1, 2 и 3, которые появляются со следующими вероятностями:

Р(1) = 5/20 = 0.25 Р(2) = 5/20 = 0.25 Р(3) = 10/20 = 0.5

Явная энтропия будет:

-(0.25 log2(l/4) + 0.25 log2(l/4) + 0.5 log2(l/2)) = 1.5 бит на символ

Однако если мы рассмотрим числа последовательности по два, то обнаружим структуру: 12 и 33 всегда появляются вместе, и полная последовательность состоит только из этих двух символов. Кроме того,