Введение в кибернетику - Эшби У.Р.
Скачать (прямая ссылка):
такое подмножество Мп, что: а) вероятность попадания вектора длины п в это подмножество Мп больше, чем 1 — е; б) отношение числа векторов в Мп к общему числу векторов длины п стремится к нулю, когда п стремится к бесконечности. — Прим. ред.
Щ1
ЭНТРОПИЯ
249
что это условие (нулевого ограничения разнообразия) дает возможность источнику информации, если он ведет себя как цепь Маркова, передавать максимальное количество информации (в данное время).
Шеннон ввел меру количества разнообразия, обнаруживаемого на каждом шаге цепью Маркова. Эта .мера, называемая энтропией, представляет, как выяснилось, огромную важность для многих вопросов, связанных с непрекращающейся передачей. Эта мера вводится следующим образом.
Если множество имеет некоторое разнообразие и мы выбираем из этого множества один элемент посредством некоторого определенного процесса выбора, то различные возможные результаты этого выбора будут связаны с различными соответствующими вероятностями. Так, пусть огни светофора имеют разнообразие в четыре элемента, обнаруживая комбинации:
1) красныь;
2) красный и желтый;
3) зеленый;
4) желтый.
Пусть они горят соответственно в течение 25, 5, 25 и 5 сек. Тогда автомобилист, появляющийся неожиданно через нерегулярные промежутки времени, будет заставать светофор в различных состояниях с частотой примерно в 42,8,42 и 8%, соответственно. Взятые как вероятности, эти частоты будут иметь значения 0,42; 0,08; 0,42 и 0,08. Таким образом, состояние «зеленый свет» имеет (если применяется именно этот способ выбора) вероятность 0,42, и аналогично — другие состояния.
Обратно, любое множество вероятностей, т. е. положительных дробей, в сумме составляющих 1, может рассматриваться как соответствующее некоторому множеству, члены которого обнаруживают разнообразие. От вероятностей ри р2, Рп Шеннон переходит к вычислению величины
— А ЩРх — р2 10ё/72 — . . . — рп \OgPn*
которую он называет энтропией множества вероятностей и обозначает символом //. Так, если взять десятичные
250 ГЛАВА 9. НЕПРЕКРАЩАЮЩАЯСЯ ПЕРЕДАЧА 4 9/12
логарифмы, то энтропия множества, связанного с огнями светофора, будет равна
—0,42 logio 0,42—0,08 logio 0,08—0,42 logi00,42—0,08 logio0,08, что в_свою очередь равняется 0,492. [Заметим, что logio 0,42 = 1,6232 = — 1,0000 + 0,6232 = —0,3768; поэтому первый член равняется (—0,42) • (—0,3768), что дает +0,158; и аналогично для других членов.] Если бы логарифмы были взяты по основанию 2 (§7/7), то результат был бы равен 1,63 бита.
Слово «энтропия» будет применяться в этой книге, лишь в том смысле, в каком оно употреблялось Шенноном; любое более широкое понятие будет называться «разнообразием» или как-нибудь иначе.
Упр. I. Из 80 случаев, когда я проезжал определенный железнодорожный переезд, он был закрыт в 14 случаях. Чему равна энтропия множества вероятностей?
Упр. 2. Из перетасованной колоды вытаскивается карта. Различаются три случая: Е\ — вытащен король треф; Еч — вытащена любая карта пик; ?з — вытащена любая другая карта. Какова энтропия разнообразия различаемых случаев?
Упр. 3. Чему равна энтропия разнообразия одного бросания игральной кости?
Упр. 4. Чему равна энтропия разнообразия множества возможных исходов (с сохранением порядка) двух последовательных бросаний игральной кости?
Упр. 5. (Продолжение.) Чему равна энтропия п последовательных бросаний?
*Упр. 6. Чему равен предел — р log р, когда р стремится к нулю?
9/12. Вычисляемая таким образом энтропия имеет несколько важных свойств. Во-первых, она имеет максимальное значение для данного числа (п) вероятностей, когда все вероятности равны. Энтропия Н в этом случае равна log п, т. е. она в точности равна мере разнообразия, определенной в § 7/7. (Как отмечалось в § 9/10, равенство вероятностей в каждом столбце необходимо для того, чтобы ограничение разнообразия было минимальным и, следовательно, разнообразие — максимальным.)! Во-вторых, различные величины Я, выведенные из различных множеств, могут — с соответствующими дополнениями — комбинироваться для получения средней энтропии.
9/12
энтропия
251
Такая комбинация используется для нахождения энтропии, которая соответствует цепи Маркова. Каждый столбец (или строка, если матрица написана в транспонированной форме) содержит множество вероятностей, дающих в сумме 1. Следовательно, каждый из них обладает энтропией. Шеннон определяет энтропию (одного шага в цепи) как среднее значение этих энтропии, причем каждая из них берется с весом, пропорциональным той относительной частоте, с которой состояние, соответствующее этому столбцу, будет встречаться, когда последовательность пришла к равновесию (§ 9/6). Так, переходным вероятностям в примере, рассмотренном в § 9/6, соответствуют следующие энтропии и равновесные относительные частоты (коэффициенты взвешивания) :
1 В Р
в 1 3 1
4 4 8
3 4 0 3 4
р 0 1 4 1
8
Энтропия Равновесная относительная частота 0,811 0,449 0,811 0,429 1,061 0,122
Тогда средняя энтропия (для одного шага в последовательности) равняется
