Бакалавриат
2022/2023
Теория статистического обучения
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
английский
Кредиты:
5
Контактные часы:
54
Course Syllabus
Abstract
This course studies mathematical explanations for the learning ability of important machine learning algorithms such as support vector machines, AdaBoost, and over parameterized neural nets. The course has 3 parts. The first is about "online learning". Important ideas and techniques are introduced in a simpler probability free setting, such as margins and bias-complexity trade-off. In the lectures about multi-armed bandits, probability theory is reviewed, (also this is important in reinforcement learning). The 2nd part, present the main definitions (VC-dimension and Rademacher complexity), and prove the main risk bounds, (using various measure concentration results). In the 3rd part, the theory is used to derive margin risk bounds. This is applied to SVM-classification, AdaBoost, and implicit regularization in over parameterized neural nets. Neural tangent kernels are introduced and the connection with kernel SVM is explained. See HTTP://wiki.cs.hse.ru/Statistical_learning_theory_2023 for the full lecture notes.
Learning Objectives
- Understand theoretical explanations for the success of drop-out regularization in neural nets.
- Know various measures of model capacity, such as VC-dimension and Demarche complexity. Use them to derive risk bounds and bounds on sample complexity. Both in the realizable and the agnostic setting.
- Apply important results from measure concentration, such as the Chernozem bound, Holding's bound, and the bounded differences inequality.
- Prove upper and lower bounds on the number of mistakes made by basic algorithms in online learning, such as the weighted majority algorithm, perception algorithms. Similar for learning with expert advice and multi-armed bandits.
Course Contents
- Probably approximately correct learning
- VC-dimensions
- Structural risk minimization and variants
- The time complexity of learning and cryptography
- Boosting
- Rademacher complexities
- Support vector machines and margin theory
- Mutliclass classification and DeepBoost
- Online learning
- Reinforcement learning
