Содержание

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

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

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

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

[ Оценки]

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

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

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

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

Новости

Выложена таблица для записи на экзамен: https://docs.google.com/spreadsheets/d/1NaH3kYaV5Y_ndwK-1-3b9qi1diWlR4NnveeBKJ2abks/edit?usp=sharing

Экзамен для студентов ВШЭ состоится 22 декабря в 10:00.

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

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

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

Оценка за курс складывается из оценки за домашние задания и оценки за экзамен с коэффициентами 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.

Экзамен

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

Запись на экзамен: https://docs.google.com/spreadsheets/d/1NaH3kYaV5Y_ndwK-1-3b9qi1diWlR4NnveeBKJ2abks/edit?usp=sharing Экзамен проводится на платформе Зум, каждый присоединяется к конференции в то время, на которое записался. В начале ответа Вы получите билет, в котором будет два теоретических вопроса из программы экзамена. Отвечать надо будет без подготовки в режиме реального времени: рассуждать и вспоминать нужно будет устно в присутствии экзаменатора. При доказательстве теоремы можно расшарить свою запись или конспект и аннотировать их при необходимости. Оценка формируется следующим образом. Полный ответ на каждый из первых двух вопросов оценивается в 5 баллов (всего 10 баллов). При ответе на вопрос можно пользоваться любыми документами (электронными или бумажными).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 1.

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

Лекция 2.

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

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

Лекция 3.

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

Лекция 4.

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

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

Лекция 5.

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

Лекция 6.

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

Лекция 7.

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

Лекция 8.

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

Лекция 9.

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

Лекция 10.

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

Лекция 11.

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

Лекция 12.

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

Лекция 13.

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

Лекция 14.

Теорема Колмогорова - Левина о сложности пары. Количество информации. Сложность и энтропия Шеннона. Теорема Ромащенко о совпадении классов неравенств.

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

Видеолекции

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

InfTheory2021