Информация. Базовые понятия теории информации

Лекция 1 Информация. Базовые понятия теории информации 1.1 Введение Теория информации является существенной, неотъемлемой частью кибернетики - науки, изучающей общие законы получения, передачи и хранения информации. Основным предметом кибернетики являются так называемые кибернетические системы. Кибернетические системы – множество взаимосвязанных объектов – элементов системы –, а также связей между ними, обеспечивающих в своей совокупности воспринятие, запоминание, переработку и обмен информацией. Под указанное определение подходит самый широкий класс систем - от систем автоматического управления на предприятиях, до биологических популяций и социумов. Подобное многообразие и широта охвата присуща и дочери кибернетики - теории информации, изучению которой и будет посвящен текущий курс лекций. Итак, теорией информации называется наука, изучающая количественные закономерности, связанные с воспринятием (получением), запоминанием (хранением), переработкой (обработкой) и обменом (передачей) информации. Приведенные здесь синонимы являются более употребляемыми в системах связи, хранения и обработки информации, которые и будут далее рассматриваться нами. Действительно, теория информации и теория связи являются чрезвычайно взаимосвязанными науками; в частности, возникновение теории информации как отдельной дисциплины чаще всего связывают с фундаментальным трудом Клода Шеннона Математическая теория связи. 11 Одной из основных задач теории информации, отображенной в заглавии нашего курса является определение оптимальных методов кодирования, позволяющих передавать и/или хранить и обрабатывать заданную информацию для заданных граничных условий - параметров канала связи; емкости запоминающих устройств; наличествующих вычислительных мощностей и пр. Что же такое информация? Одним из наиболее часто употребляемых определений является следующее: Информация - это совокупность сведений, подлежащих хранению, передаче, обработке и использованию в человеческой деятельности. К сожалению, указанное определение является как минимум незавершенным (определяемым через неопределенное понятие - совокупность сведений), а также неточным с формальной точки зрения. С точки зрения автора, понятие информации может быть максимально точно понято из контекста принципа управления, сформулированного родоначальником кибернетики Норбертом Винером: Движение и действие больших масс или передача и преобразование больших количеств энергии направляется и контролируется при помощи небольших количеств энергии, осуществляющих управление — несущих информацию. Таким образом, если рассматривать всю природу в целом как кибернетическую систему, то энергию можно определить как основное свойство, определяющее элементы системы, а информацию - как основную характеристику связей между элементами - атрибут материи, отражающий взаимосвязь и взаимозависимость явлений и существующее во Вселенной разнообразие. Указанный результат является в существенной мере философским, что, тем не менее, никак не умаляет его ценности для представленной далее прикладной дисциплины и полностью соответствует точке зрения автора. 12 1.2 Основные понятия теории информации 1.2.1 Основные термины и предмет теории информации В любой системе информация представлена в виде сообщений — совокупности знаков, либо непрерывных сигналов, являющихся переносчиком информации. Дискретные сообщения формируются в результате последовательной выдачи источником сообщений отдельных элементов - знаков. При этом все множество возможных различных знаков называют алфавитом сообщения, а размер множества - объемом алфавита. Непрерывные сообщения в свою очередь не разделены на элементы, а описываются непрерывными сигналами - функциями времени, принимающими значения из непрерывного континуума. Среда, по которой передаются сообщения между источником и приемником сообщений называется каналом связи, либо каналом передачи информации. При этом преобразование сообщения в сигнал, подходящий для передачи по заданному каналу связи, называется кодированием (в широком смысле слова); обратную операцию называют декодированием. Во время прохождения сообщения по каналу связи в данном канале могут действовать мешающие воздействия - помехи (как внешние, так и внутренние). Итак, исходя из введенных терминов, определим предмет теории информации: Теорией информации исследуются информационные системы (кибернетические системы с ярко выраженными процессами передачи, хранения и преобразования информации), подчиняющиеся следующим постулатам: 1 Источник сообщения осуществляет выбор сообщения из некоторого множества (с определенными вероятностями выбора каждого из сообщений). 2 Сообщения могут передаваться по каналу связи в закодированном виде с возможностью однозначного декодирования на приемной стороне. 13 3 Сообщения следуют друг за другом, при этом количество сообщений может быть сколь угодно большим. 4 Сообщение считается принятым при успешно осуществленной (и однозначной!) операции декодирования. При этом не имеет значения, сколько времени прошло с момента передачи сообщения и какова вычислительная сложность операций кодирования и декодирования. 5 Количество информации является математической абстракцией; не зависит от смыслового содержания сообщения, его эмоционального воздействия, полезности и отношения к реальной действительности. 1.2.2 Количественная мера информации Рассмотрим источник дискретных сообщений (дискретный источник информации). Пусть каждое отдельное i-е сообщение представляет собой информационный символ, выбираемый из ансамбля U размерности m c определенной для каждого элемента ансамбля вероятностью появления:   u1 u2 . . .um U= (1.1) p1 p2 . . .pm Представим информацию как меру неопределенности источника сообщений. Так, детерминированные (представляющие собой сингулярный случай 1.1 при m = 1 сигналы не несут в себе полезной –информационной нагрузки (величина количества информации, обозначим его I = 0). Возможно перечислить следующие естественные условия к I, как к количественной характеристике меры неопределенности: 1 Функция I(m) должна быть неотрицательной и монотонно возрастающей (за исключением введения в ансамбль вырожденных элементов с вероятностью появления p = 0). 2 Функция IX для любых сообщений X должна обладать свойством аддитивности: I (mX1 ) + I (mX2 ) = I (mX1 + mX2 ) (1.2) 3 Количество информации I должно зависеть от вероятностей появления элементов ансамбля. 14 4 Количество информации I должно зависеть от вероятностей появления элементов ансамбля. Действительно, интуитивно ясно, что более редкое событие несет в себе большее количество информации. Базовым условиям 1 и 2 удовлетворяет функция I = log m; при этом указанная формула достаточно легко расширяется на случай сообщения из n символов, каждый из которых выбирается из ансамбля размерности m. Действительно, в этом случае разнообразие N сообщений дискретного источника определяется как число перестановок с неограниченными повторениями из m по n: N = mn . Таким образом, результирующая формула, полученная Ральфом Хартли в 1928 позволяет определить количество информации в виде следующей функции: I = log N = log mn = n log m. (1.3) В формуле 1.3 возможно использовать произвольное основание логарифма; от выбранного основания зависит единица измерения количества информации1 . Наиболее распространенные основания - e, 10 и 2; соответствующие единицы измерения - нат, дит и бит. 2 В современной вычислительной технике, в связи с двоичной природой абсолютного большинства современных ЭВМ, в качестве безусловного стандарта принят бит. 1.2.3 Энтропия Для дискретного источника информации одной из ключевых характеристик является среднее количество информации, передаваемое в одном символе сообщения. Пусть вероятности pi всех i-х элементов ансамбля U различны и составляют полную систему случайных событий: m X pi = 1. (1.4) i=1 Итак, пусть путем эмпирических измерений определено, что в сообщении длины n каждый символ ui входит ni раз. В этом случае число всех возможных сообщений длины n определяется как число перестановок с повторениями из n элементов с количеством отдельных элементов 1 При равновероятных элементах исходного ансамбля. (nat) - natural digit; дит (dit) - d ecimal digit; бит (bit) - binary digit; кусочек чего-либо. 2 Нат 15 в {n1 , n2 , . . . , nn } и равно: N= K! n1 !n2 ! . . . nn ! (1.5) Таким образом, согласно формулам 1.5 и 1.3 количество информации может быть определено следующим образом: I = log N = log n! − (log n1 ! + log n2 ! + . . . + log nm !) (1.6) . Воспользовавшись формулой Стирлинга log n! ≈ n(ln n − 1) и соотношеPm нием i=1 ni = n, получаем: I = ln N = n(ln n − 1) − m X ni (ln ni − 1) = n ln n − i=1 " = −n − ln n + " = −n − ln n + m X ni i=1 m X i=1 = −n m X i=1 n m X ni ln ni = i=1 # (ln ni + ln n) = n ni ni ln + ln n n n m X ni i=1 n (1.7) # = ni ni ln . n n Переходя к вероятностям, получим учитывающую базовое условие 3 формулу Шеннона для количества информации: I = −n m X Pi log Pi . (1.8) i=1 Из указанной формулы возможно получить энтропию – среднее количество информации на 1 бит информационного сообщения от указанного дискретного источника: m X H=− Pi log Pi . (1.9) i=1 В дальнейшем в выражениях количества информации I и энтропии H по умолчанию будут пониматься логарифмы с основанием 2, если не оговорено обратного. 16 1.2.4 Информационная и физическая энтропия Предложенная мера среднего количества информации была названа Шенноном энтропией отнюдь не случайно. По легенде, родоначальник компьютерных вычислительных систем фон Нейман, изучая рукопись "Математическая теория связи"сделал замечание, что указанная величина в точности повторяет выражение для определения энтропии физической системы, определенной ранее Больцманом. Действительно, согласно второму закону термодинамики энтропия H (мера неупорядоченности) замкнутого пространства определяется выражением: N 1 X mi H=− mi ln , (1.10) Mn Mn i=1 где Mn — число молекул в данном пространстве; mi - число молекул, обладающих скоростью υ + ∆υ. Выражение 1.10 может быть также приведено к вероятностной нотации, т.к. mi /Mn есть вероятность того, что молекула имеет скорость υ + ∆υ. Таким образом, выражение для определения физической энтропии записывается в аналогичной 1.9 форме: H=− m X Pi log Pi . (1.11) i=1 Безусловно, указанное совпадение имеет глубокий физический смысл, так как в обоих случаях величина энтропии характеризует степень разнообразия состояний системы. Парадокс Демона Максвелла: Требуется отметить, что не только традиционная физика послужила примером для подражания для кибернетики. Так, именно с помощью теории информации был разрешен так называемый парадокс Демона Максвелла3 Рассматривается два сосуда с разными температурами, соединённые узкой трубкой с затворками, которыми может управлять воображаемый «демон». «Демон» может измерять скорость отдельных летящих молекул, и таким образом избирательно пропускать более быстрые в сосуд с высокой температурой, 3 Сформулирован Джеймсом Клерком Максвеллом в 1867 году для демонстрации кажущейся противоречивости второго начала термодинамики 17 а более медленные — в сосуд с низкой. Из этого мысленного эксперимента вытекает кажущееся противоречие со вторым началом термодинамики - тем, что энтропия изолированной системы не может уменьшаться. Парадокс был разрешен при помощи теории информации. Для измерения скорости молекулы «демон» должен получить информацию о её скорости. Но всякое получение информации — материальный процесс, сопровождающийся возрастанием энтропии. Количественный анализ4 показал, что приращение энтропии при измерении превосходит по абсолютной величине уменьшение энтропии, вызванное перераспределением молекул «демоном», что полностью разрешает парадокс. 1.2.5 Семантическая информация В заключении упомянем о приложении теории информации в лингвистике - определении так называемой семантической информации. Несмотря на то, что сам Шеннон однажды заметил, что смысл сообщений не имеет никакого отношения к теории информации, способ измерения количества информации был применен и для оценки содержательности предложений естественного языка. Одной из наиболее распространенных мер семантической информации является функция inf (s) = − log 2 p(s), где s – это предложение, смысловое содержание которого измеряется, p(s) – вероятность истинности s. Приведем несколько свойств этой функции-меры: 1 если s1 ⇒ s2 (из s1 следует s2 ) – истинно, то inf (s1 ) ≥ inf (s2 ); 2 inf (s) ≥ 0; 3 если s – истинно, то inf (s) = 0; 4 inf (s1 s2 ) = inf (s1 ) + inf (s2 ) ⇔ p(s1 · s2 ) = p(s1 )p(s2 ), т.е. независимость выражений s1 и s2 . Значение этой функция-меры больше для предложений, исключающих большее количество возможностей: например, из s1 — a > 3 и s2 — a = 7 следует, что s1 ⇒ s2 или inf (s1 ) ≥ inf (s2 ); ясно, что s2 исключает больше возможностей, чем s1 . 4 Проведенный в основополагающем труде Энрико Ферми "Термодинамика" 18 Еще одной достаточно используемой функцией-мерой семантической информации является функция cont(s) = 1 − p(s). Ясно, что cont(s) = 1 − 2− inf (s) или inf (s) = − log2 (1 − cont(s)). 19