Теория статистического обучения (курс лекций, Н. К. Животовский)
Материал из MachineLearning.
|
Курс знакомит студентов с теорией статистического обучения (Statistical Learning Theory), исследующей проблему надёжности восстановления зависимостей по эмпирическим данным.
В весеннем семестре 2017 года на кафедре Интеллектуальные системы ФУПМ МФТИ данный курс читается вместо курса Теория надёжности обучения по прецедентам, являющегося третьей частью трёхсеместрового курса Теория обучения машин, а также как альтернативный курс кафедры МОУ МФТИ.
Примерная программа курса
Постановки задач распознавания
- PAC (Probably Approximately Correct) обучение.
- Задачи классификации, регрессии и общая задача статистического оценивания.
- Функции потерь, риск, избыточный риск.
- No Free Lunch Theorem.
- Онлайн постановка.
- Алгоритм Halving.
Текст: Первая лекция
Неравенства концентрации меры
- Доказательство No Free Lunch Theorem
- Методы, основанные на производящих функциях моментов.
- Неравенства Маркова и Чебышева.
- Неравенство Хеффдинга.
- Неравенство ограниченных разностей.
- Доказательство обучаемости конечных классов.
Текст: Вторая лекция
Радемахеровский анализ
- Метод минимизации эмпирического риска.
- Классы Гливенко-Кантелли.
- Равномерные оценки отклонения частоты от вероятности.
- Оценки максимумов случайных величин.
- Верхние оценки избыточного риска.
- Радемахеровская сложность.
- Оценки избыточного риска, основанные на Радемахеровской сложности.
Текст: Третья лекция
Размерность Вапника-Червоненкиса (ёмкость)
- Понятие ёмкости.
- Функция роста семейства алгоритмов.
- Ёмкость семейства линейных разделяющих правил.
- Теорема Радона.
- Доказательство верхней оценки для чисел покрытия в классах с конечной ёмкостью.
- Верхние оценки Радемахеровской сложности классов конечной ёмкости.
- Теорема Дворецкого-Кифера-Вольфовитца
Текст: Четвертая лекция
Условия малого шума
- Энтропийная верхняя оценка Радемахеровской сложности.
- Неравенство Бернштейна.
- Условие малого шума Массара.
- Быстрые порядки обучаемости.
Текст: Пятая лекция
Нижние оценки и выбор модели
- Фундаментальная теорема PAC обучения.
- Нижние оценки для метода минимизации эмпирического риска.
- Оракульные неравенства.
- Структурная минимизация эмпирического риска.
Текст: Восьмая лекция
Регуляризация и устойчивость
- Понятие устойчивости в среднем и его связь с переобучением.
- Баланс эмпирического риска и устойчивости.
- PAC-обучаемость ограниченной линейной задачи с выпуклой и липшицевой функцией потерь.
Текст: Девятая лекция
Снижение размерности
- Метод главных компонент. Подход с SVD разложением и без него.
- Лемма Джонсона-Линденштраусса
- Compressed sensing
- Restricted isometry property
- Условия точного восстановления разреженного вектора.
Текст: Десятая лекция
Ссылки
Текст: Задачи по курсу
Основная литература
- 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
- Understanding Machine Learning: From Theory to Algorithms // Shai Shalev-Shwartz and Shai Ben-David. Cambridge University Press, 2014
- 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
- Concentration Inequalities: A Nonasymptotic Theory of Independence // Stéphane Boucheron, Gábor Lugosi, Pascal Massart. Oxford University Press, 2013
- A Probabilistic Theory of Pattern Recognition // Luc Devroye, László Györfi, Gábor Lugosi. Springer Verlag, 1997.
Дополнительная литература
- Concentration Inequalities and Model Selection. // Pascal Massart Ecole d’Et´e de Probabilit´es de Saint-Flour XXXIII – 2003. Springer Verlag, 2007
- Risk bounds for statistical learning // Pascal Massart, Élodie Nédélec. Ann. Statist. Volume 34, Number 5 2006
