Машинное обучение

Лектор: Сергей Игоревич Николенко

Язык курса: русский

Краткое описание курса:
Курс посвящён машинному обучению — одному из самых актуальных и математически глубоких разделов современного искусственного интеллекта. На протяжении курса изучаются наиболее часто применяющиеся самообучающиеся системы (деревья принятия решений, нейронные сети, генетические алгоритмы), самые распространённые задачи (классификация, кластеризация), подробно рассматривается задача маргинализации как центральная задача теории байесовского вывода. Курс также содержит два case study, в которых конкретные практические задачи решаются при помощи различных методов машинного обучения.

1. Введение. История искусственного интеллекта. Деревья принятия решений, алгоритм ID3. Байесовский анализ задач классификации. Меры сложности булевских функций, основанные на деревьях принятия решений, основные теоремы теории сложности деревьев принятия решений.

2. Искусственные нейронные сети. Перцептроны: обучение линейного перцептрона, нелинейные перцептроны, градиентный спуск. Сети из перцептронов, алгоритм обратного распространения ошибки. Борьба с оверфиттингом.

3. Генетические алгоритмы. Кроссовер на строках бит и деревьях. Генетическое программирование. Эффект Болдуина. Оптимизация колонией муравьёв. Алгоритм имитации отжига.

4. Задача классификации. Байесовские классификаторы: оптимальный, гиббсовский, наивный. Информационно-теоретический подход: почему гиббсовский классификатор всего вдвое хуже оптимального.

5. Маргинализация: алгоритмы грубой силы, точное интегрирование. Оценки максимального правдоподобия для нормального распределения. Априорные и апостериорные распределения. Сопряжённые априорные распределения. Сопряжённые априорные распределения для распределения Бернулли.

6. Теория кодирования: коды, исправляющие ошибки, решётки кодов. Декодирование как байесовский вывод. Алгоритмы sum-product и min-sum.

7. Маргинализация в общем виде. Граф функций и переменных. Алгоритмы sum-product и min-sum в общем случае: алгоритм передачи сообщений. Приближённая маргинализация: метод Лапласа.

8. Сэмплирование. Сложность задачи сэмплирования. Сэмплирование по значимости, с отклонением, марковские методы Монте-Карло. Алгоритм Метрополиса-Гастингса, марковские цепи, slice sampling, сэмплирование по Гиббсу.

9. Алгоритм EM. EM как средство оценки параметров смеси распределений. Максимизация вариационной свободной энергии: обоснование EM.

10. Скрытые марковские модели: модель, три задачи вывода. Алгоритмы Витерби, sum-product и Баума-Велша. Обоснование алгоритма Баума-Велша. Скрытые марковские модели с непрерывными наблюдаемыми, распределение времени, проведённого в одном состоянии и другие обобщения.

11. Кластеризация: алгоритмы, основанные на теории графов, иерархическая кластеризация, FOREL, алгоритм EM, метод k-средних, метод нечётких c-средних.

12. Обучение с подкреплением: многорукие бандиты, обучение с подкреплением в известной модели, функции значений, итерации по значениям и по стратегиям. Марковские процессы принятия решений: метод Монте-Карло, TD-обучение, Sarsa. Пример: программа TD-Gammon.

13. Метод опорных векторов. Разделяющие гиперплоскости, прямая и дуальная задачи в линейном случае. Нелинейные разделяющие поверхности, kernel trick. Применения.

14. Case study: построение рекомендательной системы. Подходы: наивный байесовский классификатор, кластеризация методом k-средних, мультиномиальная модель, смесь мультиномиальных моделей, модель Aspect. EM-схемы для оценки параметров в смеси мультиномиальных моделей.

15. Case study II: рейтинг-система как задача байесовского вывода. Модель Бредли-Терри, рейтинг Эло. Алгоритмы миноризации-максимизации. Рейтинговая система TrueSkill.