Билеты по курсу «Математические основы машинного обучения», Вьюгин ВВ, Семестр 2, 2020г.
Билеты по по курсу "Онлайн методы машинного обучения" Семестр 2 (2020г.)
Билеты по курсу "Колмогоровская сложность и ее приложения", 2019, Семестр 1
-------------------------------------------------------------------------------------------------------------------------------------------------
"Колмогоровская сложность и ее приложения", 2019, Семестр 1
Задачи 3 Link
Программа и билеты для зачета
I. Элементы вероятностной теории информации.
1. Алфавиты, коды. Однозначно декодируемые коды, безпрефиксные коды. Неравенство и теорема Крафта. Теорема Макмиллана.
2. Энтропия Шеннона и ее свойства. Энтропия пары случайных величин, условная энтропия и их свойства. Правило цепи.
3. Относительная энтропия (расхождение Кульбака-Лейблера), ее свойства. Количество информации, связь с энтропией.
4. Энтропия стационарного стохастического процесса. Опыты с текстами естественного языка.
5. Алгоритм универсального сжатия информации Зива—Лемпеля. Лемма Каца. Упрощенный вариант теоремы об оптимальности сжатия.
II. Определение колмогоровской сложности и ее свойства.
1. Алфавиты, конструктивные объекты, кодирование натуральных чисел, пар, троек строк. Понятие алгоритма, вычислимые функции, Формализация понятия алгоритма: вычислимые функции, машины Тьюринга и др. Идея построения универсальной машины Тьюринга. Универсальная функция. Перечислимые и разрешимые множества. Пример перечислимого и неразрешимого множества. Проблема остановки.
2. Простая колмогоровская сложность. Теорема инвариантности (теорема существования). Простейшие свойства колмогоровской сложности. Невычислимость сложности. Верхние оценки сложности. Теорема о неполноте.
3. Сложность пары конечных объектов. Условная сложность. Теорема Колмогорова -- Левина о сложности пары.
4. Количество информации. Свойство симметричности функции информации.
5. Несжимаемые последовательности и их свойства. Связь сложности и энтропии Шеннона. Простейший закон больших чисел.
II. Бесконечные случайные последовательности и колмогоровская сложность
1. Конструктивный анализ теории вероятностей. Пространство бесконечных двоичных последовательностей, задание мер на нем. Вычислимые меры. Эффективно нулевые множества. Существование максимального по включению эффективно-нулевого множества. Случайность по Мартин-Лефу. Примеры эффективно нулевых множеств..
2. Логика теории вероятностей. Законы теории вероятностей, их формулировки для индивидуальных случайных последовательностей. Доказательство усиленного закона больших чисел для случайных по Мартин-Лефу последовательностей.
3. Безпрефиксные методы кодирования. Префиксная сложность, ее существование и свойства. Обобщенное неравенство Крафта.
4. Перечислимые множества и предельно вычислимые функции. Априорная полумера на конечных последовательностях и ее связь с префиксной сложностью. Префиксные машины Тьюринга (машины с самоограниченным входом). Соотношение между префиксной и простой колмогоровской сложностью. Различные верхние и нижние оценки для префиксной сложности.
5. Условная префиксная сложность. Представление префиксной сложности пары. Количество информации и префиксная сложность. Симметричность функции информации (в 2016г. не входит в зачет).
6. Вычислимые монотонные операции на последовательностях. Монотонная сложность, ее существование. Соотношение между монотонной, префиксной и простой колмогоровской сложностями.
7. Эквивалентные определения случайной по Мартин-Лефу последовательности с помощью префиксной и монотонной сложности (теорема Левина -- Шнорра).
8. Вычислимые меры. Определение последовательности случайной по Мартин-Лефу относительно произвольной вычислимой меры. Теорема Левина-Шнорра для последовательностей, случайных относительно произвольных вычислимых мер.
9. Априорная перечислимая полумера на дереве двоичных последовательностей, ее построение и свойства. Связь с монотонной сложностью. Определение случайной последовательности с помощью априорной полумеры.
Перечислимые снизу супермартингалы, их интерпретация. Связь с полумерами. Определение случайной последовательности с помощью супермартингала (в 2016г. не входит в зачет)..
10. Универсальный предиктор Соломонова: определение и доказательство его асимптотической состоятельности.
Список литературы
1. Вьюгин В.В. Колмогоровская сложность и алгоритмическая случайность. МФТИ (учебное пособие), 2012. Доступно онлайн: http://www.iitp.ru/upload/publications/6027/vyugin_kolm.pdf
2. В.А.Успенский, Н.К.Верещагин, А.Шень Колмогоровская сложность и алгоритмическая случайность М.: МЦНМО, 2010, 556с. . Доступно онлайн: http://www.lif.univ-mrs.fr/~ashen/nafit/kolmbook.pdf
4. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed. New York: Springer--Verlag, 1997.
5. V"yugin V.V. Algorithmic complexity and stochastic properties of finite binary sequences. The Computer Journal, 1999, v.42, N4, p.294--317. Доступно онлайн: http://www.iitp.ru/upload/publications/1629/surv3.pdf
6. Колмогоров А.Н. Три подхода к определению понятия <<количество информации>>. Проблемы передачи информации, 1965, т.1, N1, с.3--11.
7. Cover, T., Thomas, J. Elements of information theory, Wiley
Контроль: Зачет с оценкой
Оценка складывется в равной мере из оценок за домашние задания из файла (см. ниже) и оценки за устный ответ..
Зачет происходит в устной форме по вопросам выше. Кроме этого, будут задаваться дополнительные вопросы.
Билеты и задачи к дифф. зачету по курсу «Математические основы машинного обучения», Вьюгин ВВ, 2020г.
1. Байесовский классификатор. Персептрон, алгоритм Розенблатта, оценка числа итераций. Постановка задачи восстановления зависимости в теории машинного обучения. Равномерое уклонение ошибки от среднего. PAC-форма неравенств больших уклонений. Задача классификации, постановка задачи, ошибка классификации, эмпирическая ошибка.
2. Задача классификации, постановка, основные проблемы. Теоремы об оценке предсказательной способности алгоритмов классификации (формулировки). Схема доказательства. Доказательство леммы 1 о симметризации для случая разделения без ошибок.
3. Теорема об оценке предсказательной способности алгоритмов классификации через функцию роста. Схема доказательства. Доказательство второй леммы.
4. Определение функции роста класса индикаторных функций и VC-размерности. Лемма Зауэра с доказательством. Примеры классов функций классификации и их VC-размерность.
5. VC-размерность классов всех линейных и однородных функций в n-мерном эвклидовом пространстве (с доказательствами).
6. Определение нейронной сети. VC-размерность класса всех нейронных сетей (доказательство леммы о декартовом произведении и композиции, применение к вычислению оценки для нейронных сетей).
7. Оптимальная разделяющая гиперплоскость, ее существование, единственность и свойства. Разделение без ошибок: постановки задачи, граничные гиперплоскости.
8. Алгоритм построения оптимальной гиперплоскости для случая разделения без ошибок. Опорные векторы и их свойства.
9. Переход к разделению с помощью ядер. Соответствующая оптимизационная задача. Примеры ядер. Ядра и отображения. Их примеры.
10. Положительно определенные ядра. Гильбертово пространство, порожденное воспроизводящим ядром. Построение канонического гильбертова пространства по положительно определенному ядру. Теорема о представителе. (раздел 2.5)
11. Задача построения оптимальной разделяющей гиперплоскости для случая неразделимой выборки. Случаи квадратичной и линейной нормы. Свойства опорных векторов для обоих случаев (раздел 2.6.2).
12. Средние по Радемахеру. Основная теорема о равномерной оценке разности между выборочным средним и математическим ожиданием. Ее следствия (раздел 1.4).
13. Среднее по Радемахеру и функция роста: неравенство между ними (раздел 1.5).
14. Неравенство Хефдинга. Основная форма неравенства с доказательством. Вывод неравенства Чернова (раздел 10).
15. Определение мартингал-разности. Неравенство Адзумы – Хефдинга с доказательством. Мартингальный закон больших чисел (раздел 10).
16. Неравенство Мак-Диармонда с доказательством. Его следствия для равномерной оценке разности между выборочным средним и математическим ожиданием (раздел 10).
17. Среднее по Радемахеру и оценка ошибки обобщения для классификаторов из RKHS в общем случае разделения с ошибками (раздел 2.7).
18. Постановка задачи предсказания с использованием экспертных стратегий. Алгоритм взвешенного большинства. Оценка числа ошибок. Постановка задачи предсказания с использованием экспертных стратегий. Алгоритм WMA, оценка числа его ошибок. Алгоритм Hedge оптимального распределения потерь. Оценки его регрета (раздел 4.1, 4.2).
19. Алгоритм AdaBoost. Схема применения алгоритма. Оценка его ошибки (раздел 4.3) .
20. Теория алгоритмов экспоненциального смешивания. Mixloss, связь кумулятивного mixloss-а и потерь алгоритма Hedge. Алгоритм Hedge с переменным параметром обучения (раздел 4.5).
Лабораторная работа
Провести обучение и классификацию массива данных из базы UCI repository http://archive.ics.uci.edu/ml/
Использовать какую-нибудь стандартную программу SVM. Представить отчет этой программы о числе ошибок на обучающей и тестовой выборках.
Задачи (сдать большую часть в тетради).
Привести примеры ядер и соответствующих RKHS и отображений.
Вычислить VC-размерность класса всех характеристических функций множеств {A: |A|<=k}, A – подмножества некоторого фиксированного бесконечного множества (см. книгу раздел 1.6).
Вычислить VC-размерность класса функций {sign(sin(tx)):t\in R} (см. книгу раздел 1.6).
Почему при построении оптимальной разделяющей гиперплоскости с ошибками в квадратичной норме ни один опорный вектор не лежит на граничных гиперплоскостях.
Почему при построении оптимальной разделяющей гиперплоскости с ошибками в линейной норме хотя бы один опорный вектор лежит на граничной гиперплоскостях и для него коэффициент Лагранжа больше 0.
Привести примеры ядер и соответствующих RKHS и отображений.
Доказать, что экспонента K(x,y)=exp(-xy) и гауссова функция K(x,y)=exp(-|x-y|^2).являются положительно определенными (т.е. ядром). (см. задачу 6 из книги). Как устроено соответствующее каноническое RKHS. (см. книгу раздел 1.6).
Литература
1. Вьюгин В.В.. Математические основы машинного обучения и прогнозирования. – М.: МЦНМО, 2018. (имеется также расширенная онлайн версия, http://iitp.ru/upload/publications/8071/vyugin1.pdf)
Билеты 2019г. Семестр 2.
«Онлайн методы машинного обучения» Семестр 2 (2019г.)
Исторические алгоритмы
Алгоритм WMA взвешенного большинства (экспертов). Оценка числа ошибок.
Постановки задачи предсказания с использованием экспертных стратегий: 1) для потерь общего вида; 2) для функции потерь. Понятие регрета.
Алгоритм Hedge Фройнда и Шапире оптимального распределения потерь в режиме онлайн. Оценка его регрета.
Усиление слабых классификаторов: Бустинг (на основе алгоритма Hedge). Алгоритм AdaBoost и его свойства.
Онлайн выпуклая оптимизация
Постановка задачи онлайн выпуклой оптимизации. Алгоритм следования за лидером и его свойства его регрета. Онлайн квадратичная оптимизация и оценка регрета.
Регуляризация. Алгоритм следования за регуляризованным лидером. Применение к линейной оптимизации. Алгоритм онлайн градиентного спуска. Оценка его регрета.
Линеаризация выпуклых функций. Алгоритм градинтного спуска с переменным параметром обучения (Алгоритм Зинкевича)..
Строго выпуклые функции и строго выпуклая оптимизиция. Примеры регуляризаторов: эвклидов регуляризатор, энтропийный регуляризатор.
Оценки регрета алгоритма следования за регуляризованным лидером для строго выпуклого регуляризатора. Оценки для случая эвклидова регуляризатора и энтропийного регуляризатора.
Онлайн зеркальный спуск в упрощенном виде. Алгоритм и оценка его регрета. Частные случаи: онлайн градиентный спуск и алгоритм экспоненциального смешивания.
Расстояние Брэгмана и его свойства. Преобразование Лежандра - Фенхеля. Алгоритм зеркального спуска. Оценка его регрета. Частные случаи: градиентный спуск, экспоненциальное взвешивание.
Логарифмическая оценка регрета для строго выпуклой функции потерь.
Предсказания с использованием экспертных стратегий (Prediction with Expert Advice). Алгоритмы экспоненциального смешивания.
Постановки задачи предсказания с использованием экспертных стратегий: 1) для потерь общего вида; 2) для функции потерь. Понятие регрета. Алгоритм экспоненциального взвешивания экспертных решений. Mixloss и его связь с оценкой потерь и регрета.
Алгоритм экспоненциального смешивания экспертных прогнозов для выпуклых функций потерь. Вероятностный алгоритм для произвольных функций потерь.
Состоятельность по Ханнану.
Схемы смешивания апостериорных распределений экспертов Буске и Вармута. Оценка регрета. Алгоритм Fixed Share и оценка его регрета. Связь алгоритма Sixed Shsre и алгоритма Hedge.
Агрегирующий алгоритм Вовка: конечное множество экспертов. Смешиваемые функции потерь. логарифмическая, квадратичная, вычисление предсказаний алгоритма для них.
Агрегирующий алгоритм Вовка для несмешиваемых функций потерь: абсолютная и простая функции потерь.
Агрегирующий алгоритм Вовка для континуума экспертов. Универсальный портфель Ковера. Алгоритм вычисления портфеля. Гарантийная оценка выигрыша данного портфеля.
Предсказания с экспертами в условиях ограниченной информации (Задача о многоруком бандите). Вероятностный подход: алгоритм USB и оценка регрета. Предсказания с экспертами в условиях ограниченной информации (Задача о многоруком бандите). Минимаксный случай: алгоритм Exp3 и оценка его регрета.
Прогнозирование индивидуальных последовательностей.
Задача универсального предсказания в режиме онлайн. Тестирование предсказаний (Пример: предсказатель погоды). Калибруемость предсказаний по Дэйвиду. Случайное округление. Вероятностный алгоритм построения калибруемых предсказаний для произвольной последовательности исходов. Калибруемость с ядром.
Бесконечно повторяющиеся игры
Элементы теории игр. Антагонистическая игра двух лиц с нулевой суммой.Верхняя и нижняя цена игры. Седловая точка. Достаточное условие существования седловой точки.
Достаточное условие существования решения антогонистической игры (доказательство на основе алгоритма экспоненциального смешивания). Смешанное расширение игры. Минимаксная теорема Дж. Фон Неймана. Чистые стратегии и минимаксная теорема. Решение игр типа (2xM).
Бесконечно повторяющиеся игры. Состоятельные по Ханнану стратегии. Построение такой стратегии для игры двух лиц с нулевой суммой на основе методов предсказания с экспертами.
Бесконечно повторяющиеся игры. Теоремы 1 и 2 Блекуэлла о достижимости. Применения для построения состоятельной по Ханнану онлайн стратегии.
Литература
Вьюгин В.В.. Математические основы машинного обучения и прогнозирования. – М.: МЦНМО, 2013. (имеется также расширенная онлайн версия).
Shai Shalev-Shwartz Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning Vol. 4, No. 2 (2011) 107–194 DOI: 10.1561/2200000018
Sґebastien Bubeck and Nicol`o Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Foundations and Trends in Machine Learning Vol. 5, No. 1 (2012) 1–122. DOI: 10.1561/2200000024
Cesa-Bianchi, Lugosi Prediction, Learning and Games, Cambridge university press, 2006
Cover, T., Thomas, J. Elements of information theory, Wiley
Контроль: Зачет с оценкой
Студенты с высокой оценкой самостоятельной работы (список объявлен на прошлых занятиях) сдают только теорию по билетам.
Остальные студенты, которые сдавали самостоятельные работы, но не вошли в список, получают дополнительно задачи.
Все остальные для получения допуска к зачету предварительно сдают задачи (в письменном виде) из файла (см. ниже). Надо представить решения для не менее 75% задач.
Зачет происходит в устной форме по вопросам выше. Кроме этого, будут задаваться доолнительные вопросы и задачи.
Сроки сдачи -- г. г.Долгопрудный, в 9-45
Идеи решения задач периодически разбираются на практических занятиях.
-------------------------------------------------------
Дополнительный зачет (по договоренности) по адресу г.Москва Б.Каретный 19, ИППИ РАН, к.413 (4 этаж)
|