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

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

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

В настоящее время страница находится в стадии наполнения.


Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комбинаторная теория переобучения

  • Комбинаторная постановка задачи оценивания вероятности переобучения.
  • Одноэлементное семейство. Гипергеометрическое распределение.
  • Произвольное семейство. Оценка вапниковского типа.
  • Эксперимент с четырьмя модельными семействами алгоритмов. Свойства расслоения и связности.
  • Оценка расслоения-связности. Принцип порождающих и запрещающих множеств.
  • Частные оценки для модельных семейств алгоритмов.
  • Использование комбинаторных оценок для выбора модели и отбора признаков.
  • Оценки скользящего контроля для метода ближайших соседей. Понятие профиля компактности.
  • Оценки скользящего контроля для монотонных классификаторов.

Учебное пособие по шестой и седьмой лекции: Voron-2011-tnop.pdf, 3МБ. Презентация: Voron-2015-tnop.pdf, 1.9МБ.

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

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

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

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

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

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

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

Ссылки

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

  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. Concentration Inequalities: A Nonasymptotic Theory of Independence // Stéphane Boucheron, Gábor Lugosi, Pascal Massart. Oxford University Press, 2013
  4. A Probabilistic Theory of Pattern Recognition // Luc Devroye, László Györfi, Gábor Lugosi. Springer Verlag, 1997.

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

  1. Concentration Inequalities and Model Selection. Ecole d’Et´e de Probabilit´es de Saint-Flour XXXIII – 2003. Springer Verlag, 2007.
  2. Risk bounds for statistical learning // Pascal Massart, Élodie Nédélec. Ann. Statist. Volume 34, Number 5 (2006), 2326-2366.
Личные инструменты