Текущая версия на 16:00, 23 января 2021

Теория информации

Cпециальный курс ШАД Яндекса.

Проходит по пятницам онлайн, лекция 18:00 - 19:25, семинар 19:35 - 21:00. Первая лекция и семинар 11 сентября. Этот курс также могут посещать и сдавать студенты пециальности ПМИ ФКН ВШЭ.

Оценки

Лектор: Николай Константинович Верещагин nikolay.vereshchagin@gmail.com

Семинарист: Алексей Милованов almas239@gmail.com

Консультации: meet.google.com/vru-rkzp-gnv

Контакты: группа в телеграме для вопросов https://t.me/joinchat/GQufoBG426wgd6dMrZZocg

Краткое описание

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

Новости

• 23 января. Пересдача 25 января в 15:00 по ссылке: https://zoom.us/j/92864977568
• 16 января. Пересдачи назначены на 18 и 25 января в 15:00. Пересдача комиссии - 1 февраля в 15:00.
• 22 декабря. Открыта запись на экзамен.
• 9 декабря. Выложена программа экзамена 24 декабря.

Отчётность по курсу и критерии оценки

Оценка за курс складывается из оценки за домашние задания и оценки за экзамен с коэффициентами 0.6 и 0.4, соответственно. Таким образом, каждое домашнее задание входит в итоговую оценку с коэффициентом 0.1.

Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ). Оценка за каждое ДЗ будет выставляться в общую ведомость примерно через неделю после дедлайна. Домашние задания можно послать по электронной почте в виде PDF по адресу almas239@gmail.com или через систему LMS.Крайне рекомендуется использовать TeX. Вопросы по оценке за ДЗ просьба присылать на almas239@gmail.com или в телеграм (проще отвечать).

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

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

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

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

Правила округления

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления оценки за ДЗ и итоговой оценок. Округление при выставлении обоих оценок арифметическое. Т.е. 5,49 округляется до 5, а 5,5 – до 6.

Экзамен

Экзамен состоится 24 декабря с 9:30 до 13:30. Программа экзамена.

Запись на экзамен: https://docs.google.com/spreadsheets/d/1qYknpvPPAYcfJZyXD55qiG53hYwfvOp8CmQ4v-5QmgA/edit?usp=sharing

Пересдачи назначены на 20 января (10:00) и 25 января (15:00). Пересдача комиссии - 1 февраля в 15:00.

Пересдача 25 января в 15:00 по ссылке: https://zoom.us/j/92864977568

Домашние задания

Программа курса

Информация по Хартли (двоичный логарифм количества возможных исходов).

Применения информационного подхода для решения задач о взвешиваниях (сортировки): нижняя оценка n log n для количества сравнений, необходимых для сортировки n чисел, оценка количества сравнений необходимых для нахождения фальшивой монетки (или радиоактивного элемента).

Применения информационного подхода в коммуникационной сложности: метод прямоугольников.

Распределения вероятностей на буквах данного алфавита (случайные величины со значениями в данном конечном множестве). Однозначные и префиксные бинарные коды букв данного алфавита. Средняя длина кода одной буквы.

Определение энтропии Шеннона и ее связь со средней длиной оптимального префиксного кода. Код Шеннона-Фано.

Неравенство Крафта-Макмиллана и нижняя оценка средней длины любого однозначного кода.

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

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

Условная энтропия Шеннона и ее свойства.

Независимость и энтропия. Информация в одной случайной величине о другой. Коммутативность информации.

Игра по угадыванию исхода случайной величины. Стоимость инсайдерской информации и энтропия Шеннона. Использование экспертов и аггрегационный алгоритм Вовка.

Информационные неравенства. Базисные неравества и их следствия (шенноновские неравенства).

Близкие случайные величины и неравенство Фано.

Классификаторы и их информативность.

Теорема Шеннона о блочном кодировании (Shannon noiseless coding theorem).

Пропускная способность канала с шумом и теорема о блочном кодировании для каналов с шумом (без полного доказательтсва).

Передача информации при наличии исходной информации у потребителя. Теорема Вольфа-Слепяна (без полного доказательтсва).

Предсказание с использованием экспертов

PAC learning: нахождение значения одной одной случайной величины по известному значению другой при неизвестном заранее совместном распределении вероятностей. Размерность Вапника-Червоненкиса. Бустинг.

Сжатие информации и универсальные декомпрессоры. Количество информации в данном тексте (файле) по Колмогорову (колмогоровская сложность)

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

Количество слов малой сложности, несжимаемые слова.

Применения колмогоровской сложности для оценки времени работы http://199.188.201.61 алгоритмов (оценка количества шагов для копирования одноленточной машиной Тьюринга)

Условная колмогоровская сложность. Сложность пары слов и теорема Колмогорова-Левина.

Аналогия между колмогороской сложностью, шенноновской энтропией и информацией по Хартли.

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

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

Планируемые лекции

Лекция 1. (11 сентября)

Информация по Хартли в сообщении неизвестного исхода (двоичный логарифм количества возможных исходов). Информация в данном сообщении. Аддитивность информации при двух последовательных сообщениях. Применение информации по Хартли для получения верхних и нижних оценок в задачах сортировки (нижняя оценка для n монет, верхняя оценка для 5 монет) и поиска фальшивой монетки на чашечных весах (нижняя и верхняя оценка для n монет, верхняя оценка для 12 монет)

Лекция 2. (18 сентября)

Деревья разрешения.

Коммуникационные протоколы. Разбиение матрицы функции на прямоугольники. Метод трудных множеств и метод размера прямоугольников. Оценки этими методами коммуникационной сложности предикатов EQ, GT, IT (без доказательства).

Лекция 3. (25 сентября)

Определение энтропии Шеннона. Задача о префиксном кодировании. Неравенство Крафта. Теорема Макмиллана. Нижняя и верхняя оценки средней длины префиксного кода с помощью энтропии.

Лекция 4. (2 октября)

Когда энтропия распределения на n исходах максимальна. Применение энтропии для нижней оценки среднего количества вопросов для деревьев разрешения.

Сбалансированные коды. Код Шеннона-Фано и арифметический код. Код Хаффмана. Совместно распределенные случайные величины. Теорема об энтропии пары (она не превосходит суммы энтропий). Независимость и энтропия.

Лекция 5. (9 октября)

Условная энтропия и её свойства (она неотрицательна и не превосходит безусловной энтропии, она равна разности двух безусловных). Понятие количества информации и его свойства. Информационные неравенства: метод релятивизации, метод диаграмм. Общая информация тройки слов и пример, когда она отрицательна. Неравенство треугольника. Цепное правило. Неравенство Шерера и вывод из него неравенства Лумиса-Уитни.

Лекция 6. (16 октября)

Неравенство Ромащенко-Каседа и вывод из него неравенства для количества квадратов. Марковская цепь и ее свойство. Теорема Шеннона об идеальном шифре. Неравенство Фано. Неравенство Фано для классификаторов.

Лекция 7. (23 октября)

Количество слов с данными частотами. Сбалансированные слова и их количество. Кодирование, основанное на частотах диграмм. Оценки количества слов с данным набором диграмм.

Лекция 8. (30 октября)

Стационарные источники. Теорема Шеннона о бесшумном канале.

Лекция 9. (6 ноября)

Теорема Вольфа-Слепяна (c доказательством). Каналы с шумом и их пропускная способность.

Лекция 10. (13 ноября)

Теорема Шеннона о канале с шумом (без подробного доказательства). Игры по предсказанию битов данной последовательности. Мартингалы. Теорема об определении мартингалов стратегиями.

Лекция 11. (20 ноября)

Предсказания с экспертами. Логарифмический штраф и предсказатель Соломонова. Выпуклые функции штрафа. Условие Блэквела. Линейный предсказатель.

Лекция 12. (27 ноября)

Полиномиальный и экспоненциальный предсказатели. PAC learning и размерность Вапника - Червоненкиса. Лемма Зауэра - Шелаха.

Лекция 13. (11 декабря)

Декомпрессоры. Колмогоровская сложность и теорема Колмогорова-Соломонова. Оценка на число слов колмогоровской сложности не больше n. Сложность и длина. Неубывание колмогоровской сложности при алгоритмических преобразований. Неравенство для сложности пары. Условная сложность. Теорема Колмогорова - Левина о сложности пары. Количество информации. Сложность и энтропия Шеннона. Теорема Ромащенко о совпадении классов неравенств.

Проведённые семинары

Семинар 1 (13 сентября)

Нахождение фальшивой монеты из 12 за 3 взвешивания. Есть 6 камней, 1 кам < 2 кам, 3 кам < 4 кам < 5 кам < 6 кам. Сколько нужно взвешиваний, чтобы их упорядочить? Угадать число, если можно спрашивать бинарные вопросы, причем ответ ДА стоит 2 рубля, ответ НЕТ --- 1 рубль.

Семинар 2 (20 сентября)

Деревья разрешения: нижняя оценка для функции голосования и конъюнкции. Формализация метода противника. Нижняя оценка для функций, у которых прообраз единицы имеет нечетный размер. Нижняя оценка для свойства графов не иметь циклов. Минимальная вопросная сложность функции, существенно зависящей от n переменных, есть примерно \log_2(n) (пример --- адресная функция). Пример свойства графов, тестируемого за линейное от количества вершин число запросов.

Семинар 3 (27 сентября)

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

Семинар 4 (4 октября)

Алгоритм Хаффмана, fix-free коды, оптимальная средняя длина префиксного кода как функция.

Семинар 5 (11 октября)

Поведение H(X|Y) при применении функции к X или Y, алгоритм проверки общезначимости для линейных неравенств с энтропиями двух или трех случайных величин, 3 попарно независимых бита с энтропией 2, 7 попарно независимых бита с энтропией 3, матожидание случайной величины, принимающей целые положительные значения, не меньшее ее энтропии.

Семинар 6 (18 октября)

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

Семинар 7 (25 октября)

Неравенство |I(X:Y) - I(X:Z)| \le h(\Pr[Y \neq Z]) для бернуллиевских Y, Z. Минимальная информативность классификатора для данной точности и покрытия.

Семинар 8 (1 ноября)

Пример на подсчет количества слов с данными наборами биграмм (и с данной точностью). Статистическое расстояние.

Семинар 9 (8 ноября)

Статистическое расстояние, спаривание случайных величин, стационарные источники.

Семинар 10 (15 ноября)

Конструкции попарно независимых хеш-функций.

Материалы по курсу

Видеолекции

https://wiki.school.yandex.ru/shad/Videocollections2.0/FirstYear/videoInformationTheory/

Рекомендуемая литература

1. Н.К. Верещагин, Е.В. Щепин. Информация, кодирование и предсказание. Москва, МНЦМО 2012.

2. Конспекты лекций.

3. А.M. Яглом, И.М. Яглом. Вероятность и информация.

4. В.А. Успенский, Н.К. Верещагин, А. Шень. Колмогоровская сложность. http://www.mccme.ru/free-books/shen/kolmbook.pdf

5. Li M., Vitanyi P., An Introduction to Kolmogorov Complexity and Its Applications, Second Edition, Springer, 1997. (638 pp.)

6. Кернер, Чисар. Теория информации.

7. Nicolo Cesa-Bianchi, Gabor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.

Полезные ссылки

Материалы иного рода.