Статистическая теория обучения

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

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

Содержание

Курс знакомит студентов с теорией статистического обучения (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, оценки на риск.

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

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

Четрвертое задание — 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

Факультет компьютерных наук ВШЭ

Факультет компьютерных наук был создан в 2014 году. Яндекс разработал концепцию факультета и вместе с ВШЭ формирует образовательную программу. Сейчас на ФКН действует восемь научных лабораторий, около десяти крупных компаний из России и других стран входят в число индустриальных партнеров. На факультете действует стипендиальная программа имени сооснователя Яндекса Ильи Сегаловича. Также для первокурсников, отличившихся на Всероссийских олимпиадах школьников по математике, информатике и физике, ждет стипендия от Яндекса.

Бакалавриат

Программа нацелена на подготовку исследователей, инженеров-исследователей и инженеров-разработчиков в области теоретической и прикладной информатики.

«Прикладная математика и информатика» была разработана в 2014 году с учётом опыта ведущих факультетов компьютерных наук университетов EPFL в Швейцарии и Стэнфорда в США, а также Школы анализа данных Яндекса. Кроме профессионального цикла (major) студент может пройти обучение по дополнительному профилю (minor). На старших курсах студенты выбирают в качестве специализации «Машинное обучение и приложения», «Распределённые системы», «Анализ и принятие решений» и «Анализ данных и интеллектуальные системы».

Программа готовит ведущих разработчиков и архитекторов программного обеспечения, менеджеров проектов, менеджеров по качеству программного обеспечения и менеджеров процессов его разработки. Договоры более чем со 100 компаниями открывают перед студентами возможности получения практического опыта в работе над реальными IT-проектами.

Программа полностью соответствует международным рекомендациям по преподаванию программной инженерии в высших учебных заведениях в областях Computing, Computer Science и Software Engineering и международному профессиональному стандарту SWEBOK. В 2011 году программа получила престижную награду IBM Faculty Award.

Совместная программа Высшей школы экономики и Лондонского университета. Всё обучение проходит на английском языке, а выпускники получают два диплома: диплом бакалавра по направлению «Прикладная математика и информатика» НИУ ВШЭ и диплом Bachelor of Science (BSc) in Data Science and Business Analytics, University of London. Программа готовит аналитиков и специалистов в области Data Science, понимающих задачи экономики и финансовой сферы. Выпускник сможет стать ведущим специалистом в современных финансовых организациях, в консалтинге, в IT-компаниях и в стартапах.

Разработчиком и куратором британской части программы является London School of Economics and Political Science (LSE), один из ведущих университетов мира. ФКН дополняет программу традиционно сильными математикой, программированием и машинным обучением. В процессе обучения студенты получают возможность принять участие в летних школах LSE, познакомиться с жизнью британских студентов.

Магистратура

Программа направлена на подготовку специалистов в области вычислительной биологии, способных применять математический аппарат для решения биологических и медицинских задач.

Программа посвящена подготовке специалистов в области современных методов анализа данных, математических методов моделирования и прогнозирования. В рамках этой программы действует совместная специализация Школы анализа данных и ФКН «Анализ интернет-данных» где студенты изучают современные методы работы с большими данными, машинное обучение, анализ изображений и текстов. В ходе обучения они посещают часть занятий и участвуют в научных семинарах ШАДа.

Программа готовит специалистов в области разработки программного обеспечения и информационно-коммуникационных технологий, в том числе облачных и мобильных приложений.

Программа направлена на подготовку разработчиков и исследователей, способных развивать новейшие технологии создания системного программного обеспечения.

Программа выпускает специалистов на стыке математики и компьютерных наук, математической статистики, машинного обучения, оптимизации, теории информации и теории сложности.

Созданная ФКН и Сбербанком программа готовит профессионалов в области анализа данных и предиктивной аналитики, готовых создавать стоимость для бизнеса с помощью математических моделей.