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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 50: Строка 50:
* Быстрые порядки обучаемости.
* Быстрые порядки обучаемости.
* Бесшумная классификация.
* Бесшумная классификация.
 +
* Фундаментальная теорема PAC обучения.
Текст: [[Медиа:SLT,_lecture_5.pdf|Пятая лекция‎]]
Текст: [[Медиа:SLT,_lecture_5.pdf|Пятая лекция‎]]
 +
 +
=== Онлайн обучение I ===
 +
* Размерность Литтлстоуна.
 +
* Оптимальный алгоритм.
 +
* Мартингальные неравенства Азумы и Чернова.
 +
* Online to batch conversion.
 +
 +
=== Онлайн обучение II ===
 +
* Размерность Литтлстоуна.
 +
* Оптимальный алгоритм.
 +
* Мартингальные неравенства Азумы и Чернова.
 +
* Online to batch conversion.
=== Нижние оценки и выбор модели ===
=== Нижние оценки и выбор модели ===
-
* Фундаментальная теорема PAC обучения.
 
* Нижние оценки для метода минимизации эмпирического риска.
* Нижние оценки для метода минимизации эмпирического риска.
* Оракульные неравенства.
* Оракульные неравенства.
Строка 63: Строка 75:
* Понятие устойчивости в среднем и его связь с переобучением.
* Понятие устойчивости в среднем и его связь с переобучением.
* Баланс эмпирического риска и устойчивости.
* Баланс эмпирического риска и устойчивости.
-
* PAC-обучаемость ограниченной линейной задачи с выпуклой и липшицевой функцией потерь.
+
* Обучаемость ограниченной линейной задачи с выпуклой и липшицевой функцией потерь.
Текст: [[Медиа:SLT,_lecture_7,_new.pdf|Девятая лекция‎]]
Текст: [[Медиа:SLT,_lecture_7,_new.pdf|Девятая лекция‎]]
 +
 +
=== Активное обучение ===
 +
* Постановка задачи.
 +
* Активное обучение интервалов.
 +
* Коэффициент разногласия.
 +
* Алгоритм CAL.
 +
* Алгоритм A² (Agnostic Active). Оценки сходимости.
=== Снижение размерности ===
=== Снижение размерности ===
Строка 77: Строка 96:
== Ссылки ==
== Ссылки ==
-
Текст: [[Медиа:SLT,_problems_up.pdf|Задачи по курсу‎]]
 
'''Основная литература'''
'''Основная литература'''

Версия 14:39, 9 февраля 2017

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Размерность Литтлстоуна.
  • Оптимальный алгоритм.
  • Мартингальные неравенства Азумы и Чернова.
  • Online to batch conversion.

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

  • Размерность Литтлстоуна.
  • Оптимальный алгоритм.
  • Мартингальные неравенства Азумы и Чернова.
  • Online to batch conversion.

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

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

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

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

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

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

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

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

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

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

Ссылки

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

  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
Личные инструменты