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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Снижение размерности)
м (Снижение размерности)
 
(5 промежуточных версий не показаны.)
Строка 86: Строка 86:
* Активное обучение пороговых классификаторов.
* Активное обучение пороговых классификаторов.
* Коэффициент разногласия.
* Коэффициент разногласия.
-
* Алгоритм CAL.
+
* Алгоритм CAL. Оценка сходимости.
-
* Алгоритм A² (Agnostic Active). Оценки сходимости.
+
* Примеры коэффициентов разногласия.
-
=== Снижение размерности ===
+
=== Снижение размерности и разреженность ===
* [[Метод главных компонент|Метод главных компонент]]. Подход с SVD разложением и без него.
* [[Метод главных компонент|Метод главных компонент]]. Подход с SVD разложением и без него.
* [http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma Лемма Джонсона-Линденштраусса]
* [http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma Лемма Джонсона-Линденштраусса]
Строка 95: Строка 95:
* [http://en.wikipedia.org/wiki/Restricted_isometry_property Restricted isometry property]
* [http://en.wikipedia.org/wiki/Restricted_isometry_property Restricted isometry property]
* Условия точного восстановления разреженного вектора.
* Условия точного восстановления разреженного вектора.
 +
* Модель гауссовской последовательности. Hard Thresholding, оценки на риск.
Текст: [[Медиа:SLT,_lecture_8.pdf|Десятая лекция]]
Текст: [[Медиа:SLT,_lecture_8.pdf|Десятая лекция]]
Строка 104: Строка 105:
Третье: [[Медиа:SLTsetofproblems3.pdf|Задание 3]]
Третье: [[Медиа:SLTsetofproblems3.pdf|Задание 3]]
 +
 +
Четвертое: [[Медиа:SLTsetofproblems4.pdf|Задание 4]]
[https://docs.google.com/spreadsheets/d/1B5ELKtAFoIK3co8dfbikA-9ReZKAadx5UGlOcY6PwAg/edit#gid=0| Выбранные проекты.]
[https://docs.google.com/spreadsheets/d/1B5ELKtAFoIK3co8dfbikA-9ReZKAadx5UGlOcY6PwAg/edit#gid=0| Выбранные проекты.]
Строка 109: Строка 112:
== Текущие дедлайны ==
== Текущие дедлайны ==
-
Третье задание -- 17 апреля, 2.00 Мск.
+
Четрвертое задание -- 24 мая, 2.00 Мск.
-
Почти полная версия текста проекта -- 2 мая, 2.00 Мск.
+
Проверка 3-его задания -- 24 мая, 2.00 Мск.
== Ссылки ==
== Ссылки ==

Текущая версия

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Текст: Седьмая лекция‎

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Четвертое: Задание 4

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

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

Четрвертое задание -- 24 мая, 2.00 Мск.

Проверка 3-его задания -- 24 мая, 2.00 Мск.

Ссылки

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

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