Теория Информации 2018/2019
Курс Теория информации проходит по пятницам в аудитории Кембридж ШАД Яндекса, лекция 18:00 - 19:30, семинар 19:30 - 21:00. Первая лекция 14 сентября.
Содержание
Новости
24.09.18 Лекции и семинара в пятницу 28 сентября не будет
Всем студентам, сдающим курс, надо зайти на страничку курса в системе Anytask https://anytask.org/course/399 и ввести инвайт 3XJw8Ia.
Лектор
Николай Константинович Верещагин nikolay.vereshchagin@gmail.com
Семинарист
Александр Козачинский kozlach@mail.ru
Контакты
nikolay.vereshchagin@gmail.com, kozlach@mail.ru, группа в телеграме для вопросов
Краткое описание
В науке не существует единого подхода к определению понятия информации. В разных областях это понятие трактуется по-разному. Имеются информация по Хартли, энтропия Шеннона, Колмогоровская сложность, коммуникационная сложность. Каждое из этих понятий отражает некоторую грань интуитивного понятия информации. В курсе будет рассказано об этих понятиях и как они применяются в решении разных задач.
Отчётность по курсу и критерии оценки
Для того, чтобы сдавать домашние задания, необходимо зарегистрироваться на него в системе AnyTask. Чтобы сделать это, зайдите на страничку курса https://anytask.org/course/399 и введите инвайт O6OW7bx. Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ) и коллоквиум, оцениваемый тоже по 10-балльной системе. Оценка за каждое ДЗ будет выставляться в общую ведомость (в системе Any Task) примерно через неделю после дедлайна. Домашние задания можно сдать перед началом семинара (но не на самом семинаре или после него) семинаристу или послать по электронной почте в виде PDF по адресу kozlach@mail.ru или через систему Any Task. Вопросы по оценке за ДЗ просьба присылать не в Any Task, а на kozlach@mail.ru или в телеграм (проще отвечать).
Среднее арифметическое оценок за домашние задания составляет накопленную оценку.
Коллоквиум состоит из двух теоретических вопросов, которые оцениваются в 5 баллов и состоится в сессию после второго модуля.
Итоговая оценка равна сумме накопленной оценки и оценки за коллоквиум с коэффициентами 2/3 и 1/3. Таким образом, каждое домашнее задание входит в итоговую оценку с коэффициентом 1/9.
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать коллоквиум, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.
Правила округления
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок. Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.
Контрольные мероприятия и их сроки
По курсу будет 6 домашних заданий, контрольных и экзаменов не будет.
Примерные сроки сдач заданий:
Первое домашнее задание 5 октября.
Второе домашнее задание 19 октября.
Третье домашнее задание 2 ноября.
Четвертое домашнее задание 16 ноября.
Пятое домашнее задание 30 ноября.
Шестое домашнее задание 14 декабря.
Сдача домашних заданий после их срока невозможна.
Коллоквиум
состоится с 20 по 26 декабря.
Домашние задания
Домашнее задание № 1 - дедлайн 5 октября
Домашнее задание № 2 - дедлайн 19 октября
Домашнее задание № 3 - дедлайн 2 ноября
Домашнее задание № 4 - дедлайн 16 ноября
Программа курса
Информация по Хартли (двоичный логарифм количества возможных исходов).
Применения информационного подхода для решения задач о взвешиваниях (сортировки): нижняя оценка n log n для количества сравнений, необходимых для сортировки n чисел, оценка количества сравнений необходимых для нахождения фальшивой монетки (или радиоактивного элемента).
Применения информационного подхода в коммуникационной сложности: метод прямоугольников.
Распределения вероятностей на буквах данного алфавита (случайные величины со значениями в данном конечном множестве). Однозначные и префиксные бинарные коды букв данного алфавита. Средняя длина кода одной буквы.
Определение энтропии Шеннона и ее связь со средней длинной оптимального префиксного кода. Код Шеннона-Фано.
Неравенство Крафта-Макмиллана и нижняя оценка средней длины любого однозначного кода.
Реальные тексты, как марковские цепи небольшого порядка и верхняя оценка количества информации в них. Избыточность.
Пары совместно распределенных случайных величин с конечными множествами исходов. Неравенство для энтропии Шеннона пары.
Условная энтропия Шеннона и ее свойства.
Независимость и энтропия. Информация в одной случайной величине о другой. Коммутативность информации.
Игра по угадыванию исхода случайной величины. Стоимость инсайдерской информации и энтропия Шеннона. Использование экспертов и аггрегационный алгоритм Вовка.
Информационные неравенства. Базисные неравества и их следствия (шенноновские неравенства).
Близкие случайные величины и неравенство Фано.
Классификаторы и их информативность.
Теорема Шеннона о блочном кодировании (Shannon noiseless coding theorem).
Пропускная способность канала с шумом и теорема о блочном кодировании для каналов с шумом (без полного доказательтсва).
Передача информации при наличии исходной информации у потребителя. Теорема Вольфа-Слепяна (без полного доказательтсва).
Предсказание с использованием экспертов
PAC learning: нахождение значения одной одной случайной величины по известному значению другой при неизвестном заранее совместном распределении вероятностей. Размерность Вапника-Червоненкиса. Бустинг.
Сжатие информации и универсальные декомпрессоры. Количество информации в данном тексте (файле) по Колмогорову (колмогоровская сложность)
Свойства колмогоровской сложности: сложность не превосходит длины, сложность не увеличивается при алгоритмических преобразованиях, сложность невычислима, но перечислима сверху.
Количество слов малой сложности, несжимаемые слова.
Применения колмогоровской сложности для оценки времени работы алгоритмов (оценка количества шагов для копирования одноленточной машиной Тьюринга)
Условная колмогоровская сложность. Сложность пары слов и теорема Колмогорова-Левина.
Аналогия между колмогороской сложностью, шенноновской энтропией и информацией по Хартли.
Связь колмогоровской сложности и энтропии Шеннона: колмогоровская сложность слова, состоящего из последовательности независимых одинаково распределенных букв равна его энтропии Шеннона.
Подход Р. Соломонова к прогнозировании битов последовательности, случайной по данному неизвестному распределению вероятностей; универсальные предсказатели.
Проведенные лекции
Лекция 1. (14 сентября)
Информация по Хартли в сообщении неизвестного исхода (двоичный логарифм количества возможных исходов). Информация в данном сообщении. Аддитивность информации при двух последовательных сообщениях. Применение информации по Хартли для получения верхних и нижних оценок в задачах сортировки (нижняя оценка для n монет, верхняя оценка для 5 монет) и поиска фальшивой монетки на чашечных весах (нижняя и верхняя оценка для n монет, верхняя оценка для 12 монет)
Лекция 2. (21 сентября)
Коммуникационные протоколы. Разбиение матрицы функции на прямоугольники. Метод трудных множеств, метод размера прямоугольников и метод ранга матрицы. Оценки этими методами коммуникационной сложности предикатов EQ, GT, DISJ, GT.
Лекция 3. (5 октября)
Определение энтропии Шеннона. Задача о префиксном кодировании. Неравенство Крафта. Теорема Макмиллана. Нижняя и верхняя оценки средней длины префиксного кода с помощью энтропии.
Лекция 4. (12 октября)
Сбалансированные коды. Код Шеннона-Фано и арифметический код. Совместно распределенные случайные величины. Условная энтропия. Теорема об энтропии пары (она не превосходит суммы энтропий). Независимость и энтропия. Условная энтропия и её свойства (она неотрицательна и не превосходит безусловной энтропии, она равна разности двух безусловных).
Лекция 5. (19 октября)
Понятие количества информации и его свойства. Информационные неравенства: метод релятивизации, метод диаграмм. Общая информация тройки слов и пример, когда она отрицательна. Базисное неравенство, неравенство треугольника. Цепное правило. Неравенство Шерера и вывод из него неравенства Лумиса-Уитни. Неравенство Ромащенко-Каседа и вывод из него неравенства для количества квадратов.
Лекция 6. (26 октября)
Марковская цепь и ее свойство. Теорема Шеннона об идеальном шифре. Неравенство Фано. Неравенство Фано для классификаторов. Количество слов с данными частотами. Сбалансированные слова и их количество.
Проведённые семинары
Семинар 1 (14 сентября)
Семинар 2 (21 сентября)
Семинар 3 (5 октября)
Семинар 4 (12 октября)
Семинар 5 (19 октября)
Семинар 6 (26 октября)
Рекомендуемая литература
1. ((https://www.dropbox.com/s/zyxfaiqyqqm1gmn/information.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.
