imported>Nvereshagin: Migrated current public revision from wiki.cs.hse.ru

2021-01-23T13:00:58Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

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

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

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

[https://docs.google.com/spreadsheets/d/1JM6c0iIRhzfJ9kwOg8s2c7FVXG0h2rj5A3n9aseA51A/edit?usp=sharing Оценки]

Лектор: Николай Константинович Верещагин 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://www.dropbox.com/s/hb16rznbhchrjsc/program2020.pdf?dl=0 Программа экзамена.]

Запись на экзамен:
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. [https://wiki.school.yandex.ru/shad/groups/2018/Semester1/InformationTheory/Sch_Ver.pdf Н.К. Верещагин, Е.В. Щепин. Информация, кодирование и предсказание.] Москва, МНЦМО 2012.

2. [https://www.dropbox.com/s/wf05hwmzbjaelrr/main.pdf?dl=0 Конспекты лекций.]

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.

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

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

InfTheo2020-2021 - История изменений

imported>Nvereshagin: Migrated current public revision from wiki.cs.hse.ru