Машинное обучение (курс лекций, К.В.Воронцов)

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Машинное обучение возникло на стыке прикладной статистики, оптимизации, дискретного анализа, и за последние 30 лет оформилось в самостоятельную математическую дисциплину. Методы машинного обучения составляют основу ещё более молодой дисциплины — интеллектуального анализа данных (data mining).

В курсе рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.

Все методы излагаются по единой схеме:

  • исходные идеи и эвристики;
  • их формализация и математическая теория;
  • описание алгоритма в виде слабо формализованного псевдокода;
  • анализ достоинств, недостатков и границ применимости;
  • пути устранения недостатков;
  • сравнение с другими методами;
  • примеры прикладных задач.

Данный курс существенно расширяет и углубляет набор тем, рекомендованный международным стандартом ACM/IEEE Computing Curricula 2001 по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).

Курс читается студентам 3 курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2004 года и студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года. На материал данного курса существенно опираются последующие курсы, читаемые студентам на этих кафедрах.

От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.

Первый семестр

Лекция 1. Вводная лекция

Лекция 2. Байесовские алгоритмы классификации

Лекция 3. Параметрическое оценивание плотности

Лекция 4. Разделение смеси распределений

  • Смесь распределений.
  • EM-алгоритм: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
  • Стохастический EM-алгоритм.
  • Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.

Лекция 5. Линейные алгоритмы классификации, однослойный перцептрон

Лекция 6. Логистическая регрессия

  • Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
  • Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь.
  • Настройка порога решающего правила по критерию числа ошибок I и II рода, кривая ошибок (lift curve), отказы от классификации.
  • Пример прикладной задачи: кредитный скоринг и скоринговые карты.

Лекция 7. Нейронные сети

Лекция 8. Метод опорных векторов

  • Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
  • Случай линейной разделимости. Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
  • Случай отсутствия линейной разделимости. Связь с минимизацией эмпирического риска, кусочно-линейная функция потерь. Двойственная задача. Отличие от предыдущего случая. Выбор константы C.
  • Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
  • Способы построения ядер. Примеры ядер.
  • Сопоставление SVM и RBF-сети.

Лекция 9. Оптимизационные техники решения задачи SVM

  • Обучение SVM методом последовательной минимизации. Псевдокод: алгоритм SMO.
  • Обучение SVM методом активных ограничений. Псевдокод: алгоритм INCAS.
  • SVM-регрессия.

Лекция 10. Метрические алгоритмы классификации

Лекция 11. Непараметрическая регрессия

Лекция 12. Многомерная линейная регрессия

Лекция 13. Шаговая регрессия

Лекция 14. Нелинейная параметрическая регрессия

Лекция 15. Прогнозирование

  • Аддитивная модель временного ряда: тренд, сезонность, цикличность. Модель Бокса-Дженкинса. Модель ARIMA — авторегрессии и интегрированного скользящего среднего.
  • Адаптивные модели. Примеры экономических приложений.
  • Неквадратичные функции потерь, примеры прикладных задач.

Второй семестр

Лекция 1. Кластеризация

Лекция 2. Иерерхическая кластеризация и многомерное шкалирование

Потоковые (субквадратичные) алгоритмы кластеризации.

Лекция 3. Обучающееся векторное квантование (сети Кохонена)

Лекция 4. Алгоритмические композиции

Лекция 5. Бустинг, бэггинг и аналоги

Лекция 6. Метод комитетов

  • Общее понятие: комитет системы ограничений. Комитеты большинства, простое и взвешенное голосование (z,p-комитеты).
  • Теоремы о существовании комитетного решения.
  • Сопоставление комитета линейных неравенств с нейронной сетью.
  • Максимальная совместная подсистема, минимальный комитет. Теоремы об NP-полноте задачи поиска минимального комитета.
  • Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.

Лекция 7. Нелинейные алгоритмические композиции

  • Смесь экспертов, область компетентности алгоритма.
  • Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
  • Построение смесей экспертов с помощью EM-алгоритма.
  • Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.

Лекция 8. Оценивание и выбор моделей

Лекция 9. Методы отбора признаков

Лекция 10. Логические алгоритмы классификации

Лекция 11. Решающие списки и деревья

Лекция 12. Взвешенное голосование логических закономерностей

  • Принцип голосования. Проблема различности (диверсификации) закономерностей.
  • Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
  • Алгоритм бустинга. Теорема сходимости.
  • Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.

Лекция 13. Алгоритмы вычисления оценок

Лекция 14. Поиск ассоциативных правил

Файлы

Экзаменационные билеты

Практикум

Личные инструменты