Как определяется энтропия дискретных случайных величин

ТИПС / Лабораторные_работы_ТИПС_3

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

Исторически первые шаги к введению понятия энтропии были сделаны в 1928 году американским инженером-связистом Хартли, предложившим характеризовать степень неопределенности опыта с k различными исходами числом log(k). Однако он считал несущественным возможность неравновероятных исходов. Ошибочность точки зрения Хартли была показана Клодом Шенноном, предложившим принять в качестве меры неопределенности опыта α с возможными исходами А₁, А₂, …, А_k величину

Он же предложил назвать это число «энтропией».

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

Энтропию дискретного опыта предлагается находить как вес всего неопределенности

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

Пример 1. Какую степень неопределенности содержит опыт извлечения карточки с простой цифрой, вынутой из разрезной цифровой азбуки?

Решение. Из десяти цифр четыре (2, 3. 5, 7) являются простыми, поэтому вероятность р₁ извлечь карточку с простой цифрой равна 0.4, а вероятность противоположного события р₂ = 1 – 0.4 = 0.6

Воспользуемся формулой Шеннона

Пример 2. Какую степень неопределенности содержит угадывание месяца рождения случайно встреченного человека?

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

Н(α) = log 12 = log4+ log3 = (2+ log3) (бит).

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

Решение. Построим граф неопределенности данного опыта:

H(α) находим как вес всего полученного графа.

Условные энтропии

Уловная энтропия H(β/A_k) опыта β относительно исхода A_k определяется следующим образом:

Условной энтропией H(β/α) опыта β относительно опыта α называется математическое ожидание условной энтропии опыта β относительно всех исходов опыта α

Условную энтропию H(β/α) предлагается находить по следующему графу:

Свойства энтропии:

Н(α)=0, если

Н(α) – max, если все

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

Поскольку карточек с простыми цифрами четыре, то

поскольку после утери карточки с простой цифрой осталось 9 карточек, и из них 3 с простой цифрой.

Решение 2. Построим граф двух независимых опытов α и β:

Пример 5. Какую неопределенность содержит опыт угадывания четности суммы очков случайно взятой кости домино, если известно, что одна кость утеряна?

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

Энтропия случайных величин

Энтропия H(X) дискретной случайной величины вычисляется по формуле:

Для непрерывной случайной величины X с плотностью вероятности f(x) определятся дифференциальная энтропия как

Здесь везде полагаем, что p_i·log(p_i j )=0,если р_i = 0 и f(x)log f(x) = 0, если f(x) = 0,так как .

Пример 6. Найти энтропию для биномиального распределения.

Пример 7. Найти дифференциальную энтропию для показательного распределения.

Вопросы для самоконтроля

Каковы основные требования к функции меры неопределенности?

Формула Хартли и ее недостатки.

В чем различие формул Хартли и Шеннона?

Какие свойства энтропии вы знаете?

В каком случае неопределенность опыта наибольшая?

Назовите основные единицы измерения энтропии и укажите их связь.

Дайте определение понятию «Бит», перечислите другие его названия.

Назовите правило сложения энтропии. При каких условиях оно выполняется?

Как изменяется правило сложения энтропии, если изменить его условия?

Как изменяется энтропия опыта, если известен результат одного из его исходов?

В каком случае мера неопределенности не изменится при проведении предварительного опыта?

Назовите свойства условных энтропий.

В каком случае условная энтропия принимает наименьшее значение?

Приведите примеры максимальных и минимальных условных энтропий.

Как определяется энтропия дискретных случайных величин?

Приведите примеры вычисления энтропии дискретной случайной величины на графе.

Чему равна энтропия индикатора события А?

В каком случае энтропия индикатора события А наибольшая?

Приведите примеры энтропий для классических законов распределения.

Для каких случайных величин задается дифференциальная энтропия?

Чему равна дифференциальная энтропия для показательного закона распределения?

I 1. Какую степень неопределенности содержит угадывание дня рождения случайно встреченного человека?

2. В каком случае менее предсказуем исход: в том, когда подбрасываем монету, или в том, когда угадываем пол первого случайно встреченного человека?

3. Что более непредсказуемо:

а) исход подбрасывания двух игральных костей или

б) угадывание карты из колоды в 36 карт (32 карты)?

4. В одной группе 6 студентов из 20 получили в сессию неудовлетворительные оценки, а в другой – 8 из 24. В каком случае сложнее предсказать успевающего студента?

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

6. Что более предсказуемо: угадывание масти случайно выбранной карты из колоды в 32 карты или из колоды в 52 карты?

7. Какую степень неопределенности содержит опыт извлечения двух карт из колоды в 36 карт относительно козырных карт?

8. Найдите степень неопределенности извлечения двух шаров из урны, содержащей один белый, два черных и три красных шара.

9. В первой урне 2 белых и 4 черных шара, а во второй – 3 белых и 3 черных. Из каждой урны вынимают по два шара. Исход какого из этих двух опытов более непредсказуем?

10. В одной подгруппе 3 из 10 студентов получили неудовлетворительную оценку по немецкому языку, а в другой – 4 из 12 по английскому. В каком случае сложнее предсказать успеваемость по иностранному языку двух случайно выбранных студентов одной подгруппы?

11. Из колоды в 36 карт наугад вытаскивают 5 карт. Найти энтропию события того, что три из вытащенных карт будут пиковой масти, а две бубновой.

12. В одном ряду в кинозале 20 мест. Десять человек произвольным образом занимают места в этом ряду. Найти степень неопределенности того, что все они сядут на места с номерами от 1 до 10.

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

14. В коробке 4 различных пары ботинок. Наугад вытащены два ботинка. Какова степень неопределенности того, что вытащенные ботинки парные?

15. В коробке 10 различных пар ботинок. Наугад вытащены шесть ботинок. Какова степень неопределенности того, что вытащенные ботинки непарные?

16. Из колоды в 36 карт вытаскивают 4 карты. Что более предсказуемо: что среди них будет хотя бы две карты с «картинкой» или что среди них будет 3 карты без «картинки»?

17. Из колоды в 36 карт наугад вытаскивают 4 карты. Что более предсказуемо: что среди них будут карты только пиковой и червовой мастей или что это будут карты только с «картинкой»?

18. Из урны, содержащей 8 шаров, пронумерованных номерами от 1 до 8, четыре раза вытаскивают по одному шару без возвращения. Номера их записывают последовательно как четырехзначное число. Что более предсказуемо: что первая цифра — четная, или, что последняя — нечетная?

19. Три различных шара раскладывают случайным образом по трем ящикам. Какова энтропия события того, что ровно один ящик останется пустым?

20. В условиях игры в покер (5 карт наугад вытаскивают из колоды в 52=(13 номиналов * 4 масти) карты) найти энтропию следующей покерной комбинации: «тройка» = 3+1+1 по номиналу, масти произвольны.

II 1. Какую степень неопределенности содержит опыт извлечения двух костей домино относительно «дуплей»?

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

3. Какую степень неопределенности содержит опыт извлечения двух шаров из урны, в которой находятся два белых и три черных шара?

4. На сколько изменится энтропия опыта из предыдущей задачи, если известно, что первым был извлечен белый шар?

5. Найдите энтропию угадывания дней рождения двух случайно встреченных людей.

6. Найдите энтропию угадывания месяцев рождения двух незнакомых вам студентов.

7. Какую энтропию содержит опыт угадывания простых цифр при извлечении из цифровой азбуки двух карточек?

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

9. Найдите энтропию угадывания простых цифр при извлечении трех карточек из цифровой азбуки.

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

11. Игральная кость А имеет 4 красных и 2 белых грани, игральная кость В имеет 3 красных и 3 белых грани. Подкидывают монету. Если выпал «орёл», бросают кость А, если выпала «решка», бросают кость В. Какую энтропию содержит опыт выпадения красной грани?

12. В первой урне 2 белых и 4 черных шара, а во второй — 3 белых и 1 черный шар. Из первой урны переложили во вторую два шара. Какую энтропию содержит опыт: шар, вынутый из второй урны после перекладывания, окажется белым?

13. Из урны, в которой было 6 белых и 8 черных шаров, потеряли один шар неизвестного цвета. После этого из урны вынули два шара, и они оказались белыми. Найдите энтропию того, что потерян белый шар.

14. На вход канала связи равновероятно подаётся одна из трёх последовательностей букв: АА, ББ, ВВ. При передаче каждая из букв независимо от другой передаётся правильно с вероятностью 0.8 и с вероятностью 0.1 заменяется на любую из двух других. Принято АБ, какова энтропия того, что послано АА?

15. Стрелок А поражает мишень с вероятностью 0.5, стрелок Б с вероятностью 0.9, стрелок В с вероятностью 0.4. Три стрелка выстрелили, и одна пуля попала в мишень. Какова энтропия того, что стрелок В попал в мишень?

16. Игральная кость А имеет 5 красных и 1 белую грань, игральная кость В имеет 2 красных и 4 белых грани. Подкидывают монету. Если выпал «орёл», бросают кость А, если выпала «решка», бросают кость В. Найти энтропию того, что выпадет красная грань.

17. В первой урне 3 белых и 5 черных шара, а во второй — 2 белых и 1 черный шар. Из первой урны переложили во вторую два шара. Найти энтропию того, что шар, вынутый из второй урны после перекладывания, окажется белым.

18. Из урны, в которой было 5 белых и 9 черных шаров, потеряли два шара неизвестного цвета. После этого из урны вынули два шара, и они оказались белыми. Найти энтропию того, что потерян один белый и один черный шары.

19. На вход канала связи равновероятно подаётся одна из трёх последовательностей букв: АА, ББ, ВВ. При передаче каждая из букв независимо от другой передаётся правильно с вероятностью 0.8 и с вероятностью 0.1 заменяется на любую из двух других. Принято АВ, какова энтропия того, что послано ВВ?

20. Стрелок А поражает мишень с вероятностью 0.7, стрелок Б с вероятностью 0.3, стрелок В с вероятностью 0.8. Три стрелка выстрелили, и одна пуля попала в мишень. Какова энтропия того, что стрелок В попал в мишень?

III 1. Найдите энтропию для числа белых шаров при извлечении двух шаров из урны, содержащей два белых и один черный шар.

2. Найдите энтропию для числа козырных карт при извлечении двух карт из колоды в 36 карт.

3. Какую степень неопределенности содержит опыт угадывания суммы очков на извлеченной кости из полного набора домино?

4. Найдите энтропию для числа тузов при извлечении трех карт из карт с картинками.

5. Найдите дифференциальную энтропию для равномерного распределения.

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

7. Чему равна энтропия для геометрического закона распределения?

8. Найдите дифференциальную энтропию для распределения Коши.

9. Найдите энтропию для распределения Пуассона.

10. Найдите дифференциальную энтропию для распределения Лапласа.

11. Случайная величина Х распределена по нормальному закону с а=3 и σ=0,5. Чему равна энтропия того, что ее значение отклоняется от а по абсолютной величине не более чем на 0,7.

12. В урне 3 белых и 4 черных шара. Из урны без возвращения вытаскивают по одному шару до тех пор, пока не будет второй раз вытащен черный шар. Найдите энтропию для числа извлечений шаров до появления черного.

13. Брошены 3 игральные кости. Случайная величина равна максимальному числу из выпавших очков. Найдите энтропию данной случайной величины.

14. На станцию кольцевой линии метро в момент времени t=0 приходит человек и ожидает поезда в любом направлении. Можно считать, что время прихода поезда в каждом направлении выбирается наугад в промежутке [0, 5мин.]. Случайная величина равна времени ожидания поезда. Найдите энтропию данной случайной величины.

15. Каждый из двух человек выбирает время прихода на место встречи наугад в промежутке [0,T]. Случайная величина равна времени ожидания одним другого. Найдите энтропию данной случайной величины.

16. На катете AB длины 1 и гипотенузе BC равнобедренного прямоугольного треугольника наугад выбраны точки M и N соответственно. Случайная величина равна площади треугольника MBN. Найдите энтропию данной случайной величины.

17. Из половины колоды (2 масти по 13 карт) наугад вытащены 4 карты. Случайная величина равна числу «пар», т.е. двух карт одного номинала среди вытащенных. Найдите энтропию данной случайной величины.

18. Известно, что вероятность выпуска бракованной детали равна 0.03. В коробке 200 деталей. Из коробки без возвращения вытаскивают по одной детали до тех пор, пока не будет извлечена бракованная деталь. Найдите энтропию для числа извлечений деталей до появления бракованной.

19. Два игрока А и В бросают правильную монету. Если выпадет «орел», игрок А получает одно очко, если выпадет «решка», игрок В получает одно очко. Игра заканчивается в тот момент, когда кто-нибудь из игроков наберет 8 очков. Найти энтропию того, что игра закончится на четырнадцатом бросании.

20. Человек раздает на улице рекламные проспекты. Каждый прохожий берет у него проспект с вероятностью 1/5. Найти энтропию того, что последний 100-ый экземпляр рекламный агент отдаст 400-ому прохожему.

Энтропия дискретной случайной величины

Теория энтропии – основа современной теории информации, которая является актуальным направлением исследований в области теории вероятностей и высшей математики в целом. Энтропия является информационной характеристикой дискретной случайной величины. Вычисляется она по формуле К. Шеннона:

Для первого стихотворения H(X) = 3,282844098 бит

Для второго стихотворения H(X) = 2,675265 бит

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

Из данных результатов несложно сделать вывод, что стиль и звучание «Свободного стихотворения» Зинаиды Гиппиус намного сложнее стихотворения «The Cradle Song». Оно более вариативно и несколько труднее воспринимается на слух.

2.8 Вероятность появления гласных звуков в стихотворениях, сравнение

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

Обозначим количество гласных звуков в первом стихотворении , во втором —

По результатам подсчётов =216, = 205, но это ещё не значит, что русское стихотворение певучей английского, для этого следует рассчитать вероятности и по общей формуле

533 – для первого стихотворения, соответственно 439

Очевидно то, что в стихотворении Вильяма Блейка вероятность появления гласных звуков превышает соответствующую вероятность в стихотворении Зинаиды Гиппиус, поэтому можно с полной уверенностью утверждать, что произведение «The Cradle Song» названо автором как нельзя кстати – «колыбельная» — певучая, плавная, спокойная.

2.9 Коэффициент темпа речи

T=

Где n – количество знаменательных слов,

Р – количество подлежащих,

S – количество сказуемых,

N – количество простых предложений,

N – количество двусоставных предложений.

Для «Свободного стихотворения»:

T==9.33

T=1.23

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

3. Объединённый коэффициент синтаксической и ритмомелодической сложности

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

Общая формула выглядит следующим образом:

Сл =

Где n – количество знаменательных слов,

T— количество безударных слогов,

l – количество строк,

N =105, как нам известно из предыдущих исследований.

Сл1.0762

Сл0.314

Из данных подсчётов можно сделать вывод, что стихотворение воспринимается на слух сложнее, чем стихотворение Вильяма Блейка.

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

Сравнив «Свободное стихотворение» Зинаиды Гиппиус и «The Cradle Song» Вильяма Блейка с помощью методов математической статистики и теории вероятностей, я пришла к выводу, что стиль Зинаиды Гиппиус более разнообразный, сложный, непредсказуемый, а стихотворение английского поэта – более плавное, спокойное, певучее, мелодичное, легко воспринимающееся на слух.

5. Список литературы

1. Р.Г. Пиотровский, К.Б. Бектаев, А.А. Пиотровская, Математическая Лингвистика, — М.: Высшая школа, 1977

2. В.В. Савченко, Теория вероятностей и математическая статистика: Конспект лекций, — Н. Новгород: НГЛУ, 2003

3. В.В. Савченко, В. В. Ретивина, Математика и информатика для лингвистов, краткий конспект лекций, — Н. Новгород: НГЛУ, 2006

4. ВВ Власов, Конспект лекций по высшей математике, — М.: Айрис, 1997

5. Р.Г. Пиотровский, К.Б. Бектаев, Математические методы в языкознании. Часть 2. математическая статистика и моделирование текста, Алма-ата: КазГУ, 1973

Как определяется энтропия дискретных случайных величин

$$log_b n=log_b а\cdot log_a n $$

$$\frac log_2 n = — \frac log_2 \frac = -p \cdot log_2 p $$

$$H=-p \cdot log_2 p

1. группа реализаций, вероятность P(C) которых удовлетворяет неравенству |[1/n]⋅log(P(C))+H| < ε
2. группа реализаций, вероятности которых этому неравенству не удовлетворяют.

1. независимо от того, каковы вероятности символов и каковы статистические связи между ними, все реализации высоковероятной группы приблизительно равновероятны. Это следствие, в частности, означает, что при известной вероятности P(C) одной из реализаций высоковероятной группы можно оценить число N₁ реализаций в этой группе: N₁ = 1 / P(C).
2. Энтропия H_n с высокой точностью равна логарифму числа реализаций в высоковероятной группе: H_n = n * H = log N₁
3. При больших n высоковероятная группа обычно охватывает лишь ничтожную долю всех возможных реализаций (за исключением случая равновероятных и независимых символов, когда все реализации равновероятны и и H = log m).

1. полезный (передаваемый) сигнал является последовательностью статистически независимых символов с вероятностями p(x_i),i = 1,m ;
2. принимаемый сигнал является последовательностью символов Y_k того же алфавита;
3. если шумы (искажения) отсутствуют, то принимаемый сигнал совпадает с отправленным Y_k=X_k ;
4. если шум имеется, то его действие приводит к тому, что данный символ либо остается прежним (i-м), либо подменен любым другим (k-м) с вероятностью p(y_k/x_i) ;
5. искажение данного символа является событием статистически независимым от того, что произошло с предыдущим символом.

1. Количество информации в случайном объекте Х относительно объекта Y равно количеству информации в Y относительно Х: I(X,Y) = I(Y,X)
2. Количество информации неотрицательно: I(X,Y) > 0. Это можно доказать по-разному. Например, варьированием p(x,y) при фиксированных p(x) и p(y) можно показать, что минимум I, равный нулю, достигается при p(x,y) = p(x) p(y).
3. Для дискретных Х справедливо равенство I(X,X) = H(X).
4. Преобразование y (.) одной случайной величины не может увеличить содержание в ней информации о другой, связанной с ней, величине: I[y (X),Y] < I(X,Y) (9)
5. Для независимых пар величин количество информации аддитивно: I( i,Y_i>) = ∑ I(X_i,Y_i)

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

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

Определение 5.12 Условная энтропия задаётся формулой:

:

1. Теория информации + ML. Энтропия

Давно хотел сделать учебные материалы по теме Теория Информации + Machine Learning. Нашёл старые черновики и решил довести их до ума здесь, на хабре.

Теория Информации и Machine Learning мне видятся как интересная пара областей, глубокая связь которых часто неизвестна ML инженерам, и синергия которых раскрыта ещё не в полной мере.

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

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

Начнём с базовых понятий Энтропии, Информации в сообщении, Взаимной Информации (Mutual Information), пропускной способности канала. Далее будут материалы про схожесть задач максимизации Mutual Information и минимизации Loss-а в регрессионных задачах. Затем будет часть про Information Geometry: метрику Фишера, геодезические, градиентные методы, и их связь с гауссовскими процессами (движение по градиенту методом SGD — это движение по геодезической с шумом).

Также нужно затронуть AIC, Information Bottleneck, поговорить про то, как устроен поток информации в нейронных сетях – Mutual Information между слоями (Information Theory of Deep Learning, Naftali Tishby) и многое другое. Не факт, что получится всё перечисленное охватить, но попробую начать.

1. Базовые определения

Есть три более менее разных способа прийти к формуле энтропии распределения

Давайте их опишем. Начнём с базовых определений.

Опр. 1.1: Неопределенность — это логарифм по основанию 2 от числа равновероятных вариантов: . Измеряется в битах. Например, неопределенность неизвестного битового слова длины k равна k.

Логарифм числа по основанию 2 – это то, сколько раз нужно делить число на 2, чтобы получить число меньше либо равно 1. Например,

Для не степеней двойки эта функция гладко продолжается. Например,

Важное свойство логарифма:

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

Битовые слова длины – это последовательности нулей и единиц длины . Каждый знак в битовом слове называется битом. Например, вот битовые слова длины 5:

00000, 00001, 00010, 00011, 00100, 00101, . , 11100, 11101, 111110, 11111

Их 32 штуки. , то есть неопределённость слова длины 5 равна 5.
Именно столько неизвестных бит в неизвестном битовом слове длины 5.

Таким образом, каждый знак в битовом слове называется битом, но ещё бит – это единица измерения неопределённости. И из этого примера понятно почему.

Для краткости везде далее обозначается просто как .

Опр. 1.2: Информация в сообщении — это разница неопределенностей до получения сообщения и после

Тоже измеряется в битах.

Например, Ваня загадал число от 1 до 100. Нам сообщили, что оно меньше либо равно 50. Неопределённость до сообщения равна , а после — . То есть в этом сообщении 1 бит информации. Умело задавая бинарные вопросы (вопросы, на которые ответ ДА или НЕТ), можно извлекать ровно 1 бит информации.

Некоторые вопросы неэффективны, например, вопрос «верно ли, что число меньше либо равно 25?» уменьшит неопределенность на бита с вероятностью 0.25, а с вероятностью 0.75 только на бит, то есть в среднем на бит. Если вы своим вопросом разбиваете множество вариантов в пропорции , то среднее количество бит информации в ответе равно .

Это выражение будем обозначать через или . Здесь мы как программисты перегрузим функцию H так, чтобы она работала для двух случаев — когда на вход поступает пара чисел, сумма которых равна 1, и когда одно число из отрезка [0, 1].

Опр. 1.3:

Видно, что задавая бинарные вопросы, в можно извлекать максимум 1 бит информации в среднем (максимальное значение функции . Ещё раз: да, можно сразу задавать вопросы типа «Число равно 57?» и если повезёт, получать log(100) бит информации. Но если не повезёт, вы получите лишь log(100/99) бит информации. Среднее число бит информации для такого сорта вопросов равно что заметно меньше 1.

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

Если мы будем задавать не бинарные вопросы, а вопросы, которые подразумевают в качестве ответа натуральное число от 1 до M, то мы сможем в одном ответе получать более, чем один бит информации. Если мы задаём такой вопрос, для которого все M ответов равновероятны, то в среднем мы будем получать бит. Если же вероятность ответа i равна p(i), то среднее число бит в ответе будет равно:

Опр. 1.4: Энтропия дискретного распределения задаётся формулой (1) выше.

Здесь мы перегрузили функцию H для случая, когда на вход поступает дискретное распределение.

ИТАК: Первый простой способ прийти к формуле энтропии — это посчитать среднее число бит информации в ответе на вопрос с разновероятными ответами.

Давайте пойдём дальше. Пусть Ваня не загадывает число, а сэмплирует его из распределения . Сколько бинарных вопросов нужно задать Ване, чтобы узнать выпавшее число? Интуитивно понятно, что нужно разбить множество вариантов на два подмножества уже равных не по количеству элементов, а по суммарному значению вероятности, и спросить Ваню, в каком из двух находится выпавшее число. Получить ответ и продолжить в том же духе с новым уменьшенным множеством вариантов — снова разбить его на два с примерно равным весом, спросить в каком из двух находится выпавшее число и так далее. Идея хорошая, но не совсем рабочая. Оказывается, правильнее поступать с конца и начать строить дерево разбиений снизу, а именно, найти два самых мало вероятных варианта и объединить их в один новый вариант, тем самым уменьшив число вариантов на 1. Потом снова найти два самых маловероятных и снова объединить их в один новый, и так далее, построив конечном итоге бинарное дерево. В листьях этого дерева находятся числа. Внутренние вершины помечены множеством чисел из поддерева, корнем которого они являются. Корень дерева помечен множеством всех чисел. Это дерево и даёт алгоритм того, как нужно задавать вопросы Ване. Нужно двигаться с корня дерева и спрашивать Ваню, куда по этому дереву идти — влево или вправо (в каком из двух множеств вершин детей находится выпавшее число). Это дерево даёт не только рецепт самого быстрого в среднем метода угадывания числа, но ещё и алгоритм Хаффмана сжатия данных.

Задача 1.1: Изучите код Хаффмана. Докажите, что текст с исходной длиной символов N имеет в сжатом виде длину, ограниченную снизу величиной бит и при удачных обстоятельствах её достигает.

ИТАК: Формула возникает при решении задачи о минимальном среднем числе бинарных вопросов, которые нужно задать, чтобы выведать выпавшее значение случайной величины с распределением

Это второй способ прийти к формуле (1).

Для случайной величины будем использовать такие обозначения для энтропии его распределения (ещё раз «перегрузим» функцию H):

Есть ещё один, третий, простой способ прийти к формуле энтропии, но нужно знать формулу Стирлинга.

Задача 1.2: Есть неизвестное битовое слово длины k (последовательность единиц и ноликов, всего k символов). Нам сообщили, что в нём 35% единичек. Чему равно при больших k?

Задача 1.3: У Вани есть неизвестное слово длины в алфавите длины M. Он сообщил доли всех букв в слове — .
Чему равно при больших ?

ИТАК: Задача 1.3 и есть третий способ прийти к формуле (1).

Опр. 1.5: Информация в сообщении по некоторую случайную величину — это разница энтропий:

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

Задача 1.4: Чему равна энтропия дискретного распределения ?Сколько информации содержится в сообщении где имеет распределение ?

Этот результат требует принятия. Как же так? – Нам сообщили ненулевую на первый взгляд информацию, отсекли самый вероятный вариант из возможных. Но неопределённость на множестве оставшихся вариантах осталась прежней, поэтому формула даёт ответ 0.

Задача 1.5: Приведите пример конечного распределения и сообщения, которое не уменьшает, а увеличивает неопределённость.

, а сообщение message = «это не первый элемент». Тогда

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

Дискретные распределения на счётном множестве значений, которые затухают по экспоненциальному закону (геометрические прогрессии), обладают свойством неизменности неопределённости при получении информации, что среди первых элементов нет правильного ответа. Менее, чем экспоненциальные затухания (например, ), только растят неопределённость при откидывании первых элементов.

Задача 1.6: Напишите формулу для энтропии распределения Пуассона

Найдите простое приближение для больших .

Задача 1.7: Дано распределение вещественной случайной величины. Пусть — это сколько бинарных вопросов в среднем нужно задать, чтобы узнать какое-то выпавшее значение случайной величины с точностью до . Найдите приближённое выражение для малых значений .

Нужно разбить ось x на корзинки длиной посчитать вероятности каждой корзинки и посчитать Если значениедостаточно мало, то ответ можно приблизить интегралом:

(см. определение энтропии непрерывного распределения ниже).

Опр. 1.6: Энтропия непрерывного распределения равна

Здесь мы ещё раз перегрузили значение символа H для случая, когда аргумент есть функция плотности вероятности (PDF).

Задача 1.8: Даны два распределения и двух вещественных случайных величин. К чему стремится разница при ?

Задача 1.9: Чему равна энтропия нормального распределения ?

Задача 1.10: Напишите формулу для энтропии экспоненциального распределения .

Задача 1.11: Случайная величина является смесью двух случайных величин, то есть её распределение есть взвешенная сумма распределений:

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

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

В этой задаче хотелось показать, что даже в простом случае непересекающихся носителей энтропии не просто складываются с соответствующими весами, а появляется добавка . Если веса равны 1/2, то эта добавка равна 1.

Интерпретация формулы такая: результат измерения с вероятностью находится в и с вероятностью – в и соответственно нам достанется неопределённость значений на множестве или неопределённость на множестве . Но чтобы выяснить, в каком из них находится измерение мы потратим в среднемвопросов.

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

Задача 1.12: Случайная величина равновероятно равна 0 или 1. Случайная величина зависит от : если , то сэмплируется из , а если , то сэмплируется из . Сколько бит информацию про случайную величину содержится в сообщении (как функция от )?

Есть такой численный ответ:

Понятно, что график начинается с 0 и стремится к 1:

при два гаусса одинаковые и сообщение про то, какой из них был выбран ничего не даёт;

при имеем смесь (mixture) двух гауссовских распределений с сильно разнесёнными центрами; сообщение про значение говорит, в каком из двух «гауссовских колпаков» находится ответ, и число вариантов уменьшается примерно в два раза, а неопределённость уменьшается на 1; «примерность» связана с тем, что «колпаки» перекрываются, но размер перекрытия быстро уменьшается с ростом .

в окрестности рост квадратичный, примерно .

а приближение к 1 происходит примерно по закону

Задача 1.13: Случайная величина устроена так: сначала сэмплируется число из экспоненциального распределения со средним , а потом сэмплируется случайное число из распределения Пуассона, с параметром . Мы получили сообщение, что одно измерение дало . Сколько бит информации мы получили про случайную величину ? Дайте численный ответ. Сколько бит информации даст последовательность измерений 10, 9, 11, 8, 10?

Задача 1.14: Случайная величина устроена так: сначала один раз сэмплируется число из бета-распределения с параметрами , а потом сэмплируется случайное число из биномиального распределения с параметрами . Мы получили сообщение, что одно измерение дало 10 (то есть 10 из 100 бросаний монетки выпали орлом). Сколько бит информации мы получили про скрытую случайную величину ? Дайте численный ответ. Сколько бит информации даст последовательность измерений 10, 9, 11, 8, 10?

Задача 1.15: Случайные величины сэмплированы из бета-распределения с параметрами . Сами нам неизвестны, но нам дали 10 измерений из 10 биномиальных распределений с параметрами и это наше знание про . Сколько бит информации мы получим в среднем про случайную биномиальную величину с параметрами и когда нам назовут значение ? А если известны абсолютно точно (случай )? А если 10 заменить на ?

Эту задачу можно сформулировать на языке ML так: у нас есть категориальная фичадля прогноза булевой величины (‘кликнет пользователь на баннер или нет’). Насколько хорош будет наш прогноз, если в обучающих данных нам известны лишь исторические данные про количество кликов и некликов по этим 10 категориям?

Задача 1.16. Случайная величина имеет распределение . Величина нам неизвестна, но мы знаем, что она была сэмплирована из распределения . Сколько информации про мы в среднем получим от первого измерения величины ? Как будет расти количество полученной информации с числом измерений?

Начальная дисперсия равна . После измерений дисперсия уменьшается до величины
.

Из начальной энтропии вычитаем конечную энтропию и и получаем

Таким образом, при больших информация растёт как , а погрешность уменьшается примерно пропорционально .

То есть число верных знаков в десятичной записи числа растёт как . Если вам хочется получить ещё один верный десятичный знак числа необходимо увеличить число измерений в 100 раз

Часть 2 – Mutual Information. В ней рассказывается про Взаимную Информацию – концепцию, которая открывает двери в помехоустойчивое кодирование, алгоритмы сжатия, а также даёт новый взгляд на задачи Машинного Обучения.

Часть 3 – ML & Mutual Information. Основы ML в контексте теории информации.