Магистратура
2021/2022
Теория статистического обучения
Статус:
Курс по выбору (Науки о данных (Data Science))
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Прогр. обучения:
Науки о данных
Язык:
английский
Кредиты:
8
Контактные часы:
54
Course Syllabus
Abstract
We study a theory that inspired the development of two important families of machine learning algorithms: support vector machines and boosting. More generally, in a typical classification task we are given (1) a dataset for training and (2) a familyof classifiers, indexed by some parameters that need to be tuned. A learning algorithm uses the training set to select one of the classifiers, in other words, tune the parameters. For example, given a neural network, every choice of the weights specifies a classifier and the learning algorithm assigns values to the weights. On one side, we want to have a large set of classifiers to model all structure in the training data. This might lead to a large number of parameters to train. On the other hand a too large set of classifiers might lead to a decrease of accuracy on unseen examples. This is called overfitting. We study a theory that quantifies overfitting theoretically. Moreover, support vector machines and boosting algorithms can be seen as algorithms that optimize the trade-off discussed above under some additional assumptions. Moreover, the theory can determine good values for meta-parameters in machine learning algorithms that otherwise need to be tuned using cross-validation. We also study some recent deep boosting algorithms that were developed using the theory. These algorithms are currently among the best for classification tasks when the number of classes is high. Finally, we study the online mistake model. This model is more general but its mathematical analysis has many similarities with the theories above.
Learning Objectives
- Understanding basic concepts from statistical learning theory.
- Being able to understand the connection between these models and many machine learning algorithms.
- Training of mathematical skills such as abstract thinking, formal thinking and problem solving; with emphasis on statistics.
Expected Learning Outcomes
- Calculate sizes of trainingsets for several machinelearning tasks in the context of PAC-learning (and hence calculate VC-dimensions)
- Deeper understanding of boosting algorithms and support vector machines.
- Knowledge of several paradigms in statistical learning theory to select models (Structural risk minimization, Maximal likelihood, Minimal Description Length, etc.)
- Theoretical understanding of several online learning algorithms and learning with expert advice.
- Understand the link between cryptography and computational limitations of statistical learning.
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
Bibliography
Recommended Core Bibliography
- Mohri, M., Talwalkar, A., & Rostamizadeh, A. (2012). Foundations of Machine Learning. Cambridge, MA: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=478737
Recommended Additional Bibliography
- Vitaly Kuznetsov, Mehryar Mohri, & Umar Syed. (n.d.). Multi-Class Deep Boosting.