Теория статистического обучения (курс лекций, Н. К. Животовский)

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

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

Содержание

Курс знакомит студентов с теорией статистического обучения (Statistical Learning Theory), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным.

В весеннем семестре 2017 года на кафедре Интеллектуальные системы ФУПМ МФТИ данный курс читается вместо курса Теория надёжности обучения по прецедентам, являющегося третьей частью трёхсеместрового курса Теория обучения машин, а также как альтернативный курс кафедры МОУ МФТИ.

Примерная программа курса

Постановки задач распознавания

  • PAC (Probably Approximately Correct) обучение.
  • Задачи классификации, регрессии и общая задача статистического оценивания.
  • Функции потерь, риск, избыточный риск.
  • No Free Lunch Theorem.
  • Онлайн постановка.
  • Алгоритм Halving.

Текст: Первая лекция‎

Неравенства концентрации меры

  • Доказательство No Free Lunch Theorem
  • Методы, основанные на производящих функциях моментов.
  • Неравенства Маркова и Чебышева.
  • Неравенство Хеффдинга и Чернова.
  • Неравенство ограниченных разностей.
  • Доказательство обучаемости конечных классов.

Текст: Вторая лекция‎

Радемахеровский анализ

Текст: Третья лекция‎

Размерность Вапника-Червоненкиса (ёмкость)

  • Понятие ёмкости.
  • Функция роста семейства алгоритмов.
  • Ёмкость семейства линейных разделяющих правил.
  • Теорема Радона.
  • Доказательство верхней оценки для чисел покрытия в классах с конечной ёмкостью.
  • Верхние оценки Радемахеровской сложности классов конечной ёмкости.
  • Теорема Дворецкого-Кифера-Вольфовитца

Текст: Четвертая лекция‎

Условия малого шума

  • Энтропийная верхняя оценка Радемахеровской сложности.
  • Неравенство Бернштейна.
  • Условие малого шума Массара.
  • Быстрые порядки обучаемости.
  • Бесшумная классификация.

Текст: Пятая лекция‎

Онлайн обучение I

  • Схемы сжатия выборок. Оценки обобщающей способности.
  • Размерность Литтлстоуна.
  • Оптимальный алгоритм.
  • Онлайн алгоритмы и сжатие некоторых классов.

Текст: Шестая лекция‎

Онлайн обучение II

  • Алгоритм экспоненциального большинства.
  • Мартингальные неравенства Азумы и Чернова.
  • Неправенство Чернова и его применения.
  • Online to batch conversion.

Текст: Шестая лекция‎

Нижние оценки и выбор модели

  • Нижние оценки для метода минимизации эмпирического риска.
  • Оракульные неравенства.
  • Структурная минимизация эмпирического риска.

Текст: Восьмая лекция‎

Регуляризация и устойчивость

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

Текст: Девятая лекция‎

Активное обучение

  • Постановка задачи.
  • Активное обучение пороговых классификаторов.
  • Коэффициент разногласия.
  • Алгоритм CAL.
  • Алгоритм A² (Agnostic Active). Оценки сходимости.

Снижение размерности

Текст: Десятая лекция

Домашние задания

Первое: Задание 1

Второе: Задание 2

Третье: Задание 3

Выбранные проекты.

Текущие дедлайны

Третье задание -- 17 апреля.

Ссылки

Основная литература

  1. Introduction to Statistical Learning Theory // Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Advanced Lectures on Machine Learning. Lecture Notes in Computer Science Volume 3176, 2004, pp 169-207
  2. Understanding Machine Learning: From Theory to Algorithms // Shai Shalev-Shwartz and Shai Ben-David. Cambridge University Press, 2014
  3. Prediction, Learning, and Games // Nicolo Cesa-Bianchi and Gábor Lugosi. Cambridge University Press, 2006
  4. Theory of Classification: a Survey of Some Recent Advances // Olivier Bousquet, Stéphane Boucheron, Gábor Lugosi. ESAIM: Probability and Statistics / Volume 9 / 2005
  5. Concentration Inequalities: A Nonasymptotic Theory of Independence // Stéphane Boucheron, Gábor Lugosi, Pascal Massart. Oxford University Press, 2013
  6. A Probabilistic Theory of Pattern Recognition // Luc Devroye, László Györfi, Gábor Lugosi. Springer Verlag, 1997.
  7. Theory of Disagreement-Based Active Learning // Foundations and Trends in Machine Learning, Volume 7 Issue 2-3, 2014

Дополнительная литература

  1. High dimensional statistics // M. Wainwright, Cambridge University Press, 2017
  2. High Dimensional Probability. An Introduction with Applications in Data Science. // Roman Vershynin, 2017
  3. Concentration Inequalities and Model Selection. // Pascal Massart Ecole d’Et´e de Probabilit´es de Saint-Flour XXXIII – 2003. Springer Verlag, 2007
  4. Risk bounds for statistical learning // Pascal Massart, Élodie Nédélec. Ann. Statist. Volume 34, Number 5 2006
Личные инструменты