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

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

Содержание 1 Примерная программа курса 1.1 Постановки задач распознавания 1.2 Неравенства концентрации меры 1.3 Радемахеровский анализ 1.4 Размерность Вапника-Червоненкиса (ёмкость) 1.5 Условия малого шума 1.6 Онлайн обучение I 1.7 Онлайн обучение II 1.8 Нижние оценки и выбор модели 1.9 Регуляризация и устойчивость 1.10 Активное обучение 1.11 Снижение размерности и разреженность 2 Домашние задания 3 Текущие дедлайны 4 Ссылки

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

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

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

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

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

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

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

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

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

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

• Метод минимизации эмпирического риска.
• Классы Гливенко-Кантелли.
• Равномерные оценки отклонения частоты от вероятности.
• Оценки максимумов случайных величин.
• Верхние оценки избыточного риска.
• Радемахеровская сложность.
• Оценки избыточного риска, основанные на Радемахеровской сложности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Метод главных компонент. Подход с SVD разложением и без него.
• Лемма Джонсона-Линденштраусса
• Compressed sensing
• Restricted isometry property
• Условия точного восстановления разреженного вектора.
• Модель гауссовской последовательности. Hard Thresholding, оценки на риск.

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

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

Первое: Задание 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