Об обосновании логарифмической меры информации

Об обосновании логарифмической меры информации

Теория информации в настоящее время вышла за узкие рамки систем связи, где она первоначально применялась, и начала широко использоваться в таких нетрадиционных для нее областях, как физика, теория систем, теория управления, биология, математика. Особенно широкое применение она нашла в таких относительно новых областях науки, как информатика, теория автоматов, защита данных.

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

Важнейшим вопросом, на основе которого строится та или иная теория информации, является выбор меры информации.

Он во многом определяется теми объектами, на анализ которых направлена разрабатываемая теория.

В настоящее время в теории информации наибольшее распространение имеют меры Хартли и Шеннона, причем в ряде случаев меру Хартли представляют как частный случай меры Шеннона.

Однако уже по своему назначению мера Хартли имеет существенное отличие от меры Шеннона, так как первая направлена на исследование детерминированных (невероятностных) процессов конечной длины, а вторая - на анализ вероятностных процессов любой длительности, для анализа которых используются статистические методы [1, 2].

Соответственно теория информации, использующая ту или иную из указанных мер, называется структурной или статистической теорией информации.

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

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

Лежащая в основе структурной теории информации логарифмическая мера , где и - любые положительные числа конечной длины, не равные 0, а еще и не равное 1, предложенная Хартли в 1928 г., не была им логически обоснована, а вводилась на основе интуитивных соображений [1]. Причем, что существенно, в таком виде она может принимать как положительные, при , так и отрицательные, при , значения.

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

Действительно, если каждый из двух источников и генерирует соответственно и сообщений, то их общее количество

(1)

Прологарифмировав выражение (1), получим равенство

(2)

которое доказывает свойство аддитивности меры информации Хартли.

Рассмотрим другое обоснование меры Хартли применительно к задачам поиска (непрерывного и дискретного).

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

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

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

Особый случай разбиения будет тогда, когда исходные возможных объектов разбиваются на классов эквивалентности так, чтобы в них находились строго равные количества целых объектов.

Очевидно, что такие разбиения возможны только в том случае, когда

(3)

где - максимальное число разбиений до появления класса с одним объектом.

Если за меру информации в данном случае взять , то она в точности совпадает с логарифмической мерой Хартли, взятой по основанию :

 (4)

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

В общем случае при разбиении исходного множества, состоящего из объектов, на классов эквивалентности в каждом из них может содержаться объектов и соответственно вероятность нахождения искомого объекта в том или ином классе равна

(5)

При этом .

Формула Шеннона для энтропии, определяющая меру неопределенности нахождения искомого объекта в том или ином классе эквивалентности до тестирования, при первом разбиении

, (6)

где утверждает, что величина энтропии достигает максимума для первого разбиения

при нахождении искомого объекта в классах эквивалентности с равными вероятностями

.

В данном случае .

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

(7)

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

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

Так как мера Хартли применительно к рассматриваемой задаче использует именно такие разбиения, то это значит, что она определяет максимально возможное количество информации, получаемое в процессе поиска дискретного объекта, а раз это так, то число разбиений и соответственно время поиска должно быть при этом минимальным по сравнению с любыми другими возможными разбиениями. Именно в этом состоит принципиальная особенность меры информации Хартли.

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

бит,

в сумме по всем разбиениям составляющее бита.

Рисунок 1 - Дерево равномерных разбиений с ,,

Очевидно, что число равномерных разбиений для данного случая с минимально.

Другое дерево разбиений на рис. 2 для неравномерных разбиений объектов на 2 класса эквивалентности имеет среднее число разбиений по всем возможным путям разбиений

,

что больше среднего числа разбиений, равного , полученного в предыдущем примере.

Это вызвано тем, что количество информации, вырабатываемое при каждом разбиении в соответствии с формулой Шеннона (6), меньше 1 бита, то есть время поиска искомого объекта не является минимальным.

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

Количество информации , необходимое для поиска одного целого искомого объекта не зависит от способа разбиения исходного множества объектов на классы эквивалентности и остается постоянным и равным .

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

Рисунок 2 - Дерево неравномерных разбиений при , и

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

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

Основное выражение для теории информации, предложенное Шенноном, имеет вид

(8)

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

(9)

искомого объекта и остаточной

(10)

где - остаточное число объектов, среди которых имеется искомый.

Очевидно, что в процессе разбиений и тестирования число уменьшается и в конечном итоге при

(11)

Последнее выражение представляет важное условие, которое сформулировано в [4] как принцип унитарности.

Суть его сводится к тому, что полная информация об объекте будет получена тогда и только тогда, когда в процессе поиска будет найден один целый объект.

Если же , то это говорит о том, что информация об объекте передана приемнику частично.

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

(12)

Это значит, что в рассматриваемом случае, когда , при тестировании вырабатывается дополнительная информация о деталях объекта, принадлежащих теперь уже новым, ранее неисследованным классам эквивалентности. Такая процедура детализации объекта может длиться неопределенно долго. Например, в дереве разбиений на рис. 1 после вершины (класса эквивалентности), содержащий после 3-го разбиения один объект, могут идти вершины, содержащие 0,5 объекта (4-е разбиение), затем 0,25 и т.д. Каждый раз величина информации об объекте при этом увеличивается на 1 бит и может достичь любой величины.

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

Все приведенные выше рассуждения относятся и к задачам поиска с числом объектов при условии, что в получаемых в процессе разбиений классах эквивалентности допускаются нецелые числа объектов.

Из неравенства следует, что

и соответственно

или

,

где - энтропия при ;

- энтропия при .

Теорема 1. Если -е разбиение числа объектов , содержит классы эквивалентности с равным количеством объектов , то имеет место неравенство

. (13)

Доказательство. Так как , то , где - количество объектов, размещенных по классам эквивалентности -го разбиения.

Из условия и соответственно следует, что .

Теорема доказана.

Следствие 1. Энтропия -го разбиения ограничена неравенством

. (14)

Теорема 2. Если -е разбиение числа объектов при содержит классы эквивалентности с количеством объектов , то имеет место неравенство

. (15)

Доказательство. Так как , то , где - количество объектов, размещенных по классам эквивалентности -го разбиения.

Из условия и соответственно непосредственно следует, что .

Теорема доказана.

Следствие 1 Остаточная энтропия ограничена неравенством

. (16)

На рис. 3 в качестве примера к теоремам 1, 2 приведено дерево для трех разбиений с исходным количеством объектов . Из него видно, что классы второго разбиения содержат по 1,5 объекта, , а классы третьего разбиения по 0,75 объекта, . По вертикальной оси координат на рисунке расположены номера исходных объектов, а по горизонтали величина получаемой после очередного разбиения 1, 2, 3 суммарной информации и значение остаточной информации . Величина вырабатываемой на каждом шаге информации остается при этом постоянной и максимальной:

бит.

Теорема 3.

. (17)

Доказательство. Так как , то , где . Прологарифмировав последнее выражение, получим, что

.

Теорема доказана.

Рисунок 3 - Дерево разбиений при .

Теорема 4

. (18)

Доказательство. Так как , то , где . Прологарифмировав последнее выражение, получим, что .

Теорема доказана.

Следствие 1

. (19)

Так как при разбиениях числа в классах, получаемых при -м разбиении, содержится больше, а в классах -го разбиения меньше 1-го объекта, то это значит, что количество информации об объекте после -го разбиения

(20)

меньше требуемого количества, необходимого для идентификации искомого объекта, и значит он не может быть полностью определен, а после -го разбиения количество информации

(21)

поступает с избытком, и в результате определяется не только сам объект, а и некоторые его детали, что для решения задачи поиска является излишним.

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

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

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

(22)

относительно .

Например, при значение надо выбрать примерно равным . Тогда .

Это значит, что и соответственно количество получаемой за 3 разбиения информации будет равно

единицы.

В теоретических работах часто выбирают равным , а на практике наиболее часто используют значение основания логарифма , на базе которого получена такая современная мера информации, как бит, - , то есть исходное множество объектов для этой меры состоит из , а искомый объект находится за одно разбиение на 2 класса эквивалентности, каждый из которых содержит по 1 объекту. Остаточная энтропия в этом случае равна 0 и соответственно для бита соблюден принцип унитарности.

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

Основание логарифма , при котором

, (23)

где - целое число разбиений, которое можно найти из выражения

. (24)

Соответственно

. (25)

Из (25) следует, что

. (26)

Например, для ,

.

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

Определим отношение (25) как начальную плотность информации до первого разбиения:

. (27)

Очевидно, что плотность информации изменяется при изменении от 1 до в пределах от 0 до 1.

Так для , начальная плотность информации

.

После каждого разбиения плотность информации будет определяться в соответствии с выражением

. (28)

Так, для рассматриваемого выше примера после первого разбиения на два класса эквивалентности

,

а после второго

.

Из выражения (28) следует, что в случае после каждого разбиения плотность информации уменьшается и только при остается постоянной для всех разбиений и равной максимальной - 1.

Из (26) следует, что

 (29)

и соответственно при

.

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

Следствие 1 теоремы 4 показывает, что количество информации, вырабатываемой на -м последнем разбиении

(30)

или

. (31)

При этом в соответствии с (16) не равно 0.

Для получения полной информации об объекте достаточно, чтобы . Тогда выражение (31) примет вид

. (32)

Так как из (17) следует, что

, (33)

то достичь равенства (32) можно, исходя из выражения

, (34)

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

Так, например, для

и соответственно

.

Для достижения последнего равенства следует, чтобы вероятности и равнялись соответственно 0,15; 0,85 или 0,85; 0,15.

Это значит, что полученное во 2-м разбиении число в размере объекта разбивается во время 3-го разбиения на две пропорциональные вероятностям и части (0,225 и 1,275), которые затем анализируются тестом на предмет отношения одной из них к искомой. Вероятность их нахождения равна или , или в зависимости от их величины.

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

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

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

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

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

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