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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (Нижние оценки и выбор модели)
(Ссылки)
Строка 83: Строка 83:
== Ссылки ==
== Ссылки ==
-
Текст: [[Медиа:SLT,_problems.pdf|Задачи по курсу‎]]
+
Текст: [[Медиа:SLT,_problems_up.pdf|Задачи по курсу‎]]
'''Основная литература'''
'''Основная литература'''

Версия 10:24, 6 июня 2016

Содержание

Курс знакомит студентов с теорией статистического обучения (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. Theory of Classification: a Survey of Some Recent Advances // Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. ESAIM: Probability and Statistics / Volume 9 / 2005
  4. Concentration Inequalities: A Nonasymptotic Theory of Independence // Stéphane Boucheron, Gábor Lugosi, Pascal Massart. Oxford University Press, 2013
  5. A Probabilistic Theory of Pattern Recognition // Luc Devroye, László Györfi, Gábor Lugosi. Springer Verlag, 1997.

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

  1. Concentration Inequalities and Model Selection. // Pascal Massart 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
Личные инструменты