Обучение, предсказания, игры
Альтернативный курс, организованный кафедрой МОУ ФУПМ МФТИ и лабораторией ПреМоЛаб.
Курс читается для студентов 5-го курса по пятницам.
Лекторы: В.В. Вьюгин, А.В. Гасников
Начало в 17:05 в 516 ГК.
Задачи в задавальник
Часть I. Статистическая теория машинного обучения
- Постановка задачи классификации. Байесовский классификатор. Примеры классификаторов: персептрон, нейронные сети.
- PAC-теория ошибок. Теория обобщения Вапника – Червоненкиса. Верхние оценки ошибки классификации.
- VC-размерность. Лемма Вапника – Червоненкиса (Сауэра, Шелаха)
- VC-размерность класса линейных классификаторов. Примеры вычисления VC-размерности других классов функций
- Теория обобщения для задач классификации с помощью пороговых решающих правил. Число покрытия для классов функций. Оценка ошибки обобщения через число покрытия.
- Пороговая размерность. Оценка ошибки обобщения через пороговую размерность.
- Покрытия и упаковки в метрических пространствах. Теорема Алона, Бен-Давида, Хауслера и Чеза-Бьянки.
- Средние по Радемахеру. Равномерная оценка отклонения эмпирического среднего от математического ожидания для класса функций.
- Неравенство Мак-Диармонда и его применения..
- Среднее Радемахера композиции.
- Средние по Радемахеру и другие меры емкости классов функций (VC-размерность, число покрытия)..
- Оценка ошибки обобщения с помощью среднего по Радемахеру.
- Алгоритм построения оптимальной разделяющей гиперплоскости. Задача оптимизации. Опорные векторы.
- SVM-метод в пространстве признаков. Пространства, порожденные воспроизводящим ядром (RKHS) и их свойства.
- Построение канонического RKHS.
- Теорема о представителе.
- Случай неразделимой выборки. Вектор переменных мягкого отступа. . Оценка ошибки в случае неразделимой выборки.
- Задача оптимизации для классификации с ошибками в квадратичной норме.
- Задача оптимизации для классификации с ошибками в линейной норме.
- Многомерная регрессия с помощью SVM. Гребневая регрессия.
- Конформные предсказания. Метаалгоритм. Примеры мер неконформности.
Часть 2. Игры с предсказаниями экспертов
- Постановка задачи предсказания с использованием экспертных стратегий. Понятие (внешнего) регрета. Алгоритм взвешенного большинства. Оценка числа ошибок.
- Алгоритм оптимального распределения потерь в режиме онлайн. Оценка его регрета.
- Алгоритм следования за возмущенным лидером. Оценка его регрета. Состоятельность по Ханнану.
- Задача минимизации регрета с точки зрения теории оптимизации. Алгоритм следования за регуляризованным лидером.
- Онлайн метод градиентного спуска.
- Онлайн метод зеркального спуска.
- Неравенства больших уклонений. Варианты неравенства Хефдинга.
- Алгоритм экспоненциального взвешивания экспертных решений.
- Алгоритм экспоненциального взвешивания экспертных решений с переменным параметром обучения.
- Задача о многоруком бандите. Стохастическая и детерминированная постановки. Алгоритм для детерминированной постановки.
- Бустинг. Алгоритм Адабуст и его свойства.
- Агрегирующий алгоритм Вовка. Конечное и бесконечное множество экспертов.
- Применение агрегирующего алгоритма для различных функций потерь: логарифмической, квадратичной, простой.
- Универсальный портфель акций Ковера. Алгоритм построения портфеля. Оценка выигрыша.
- Применение агрегирующего алгоритма для многомерной регрессии в режиме онлайн.
- Калибруемость предсказаний по Дэвиду. Алгоритмы построения калибруемых предсказаний.
- Универсальные RKHS. Построение универсальных алгоритмов для онлайн регрессии на основе метода калибруемости.
- Средние Радемахера и оценка калибровочной ошибки.
- Агрегирующий алгоритм как результат построения калибруемых предсказаний.
Литература
- Вьюгин В.В. Элементы математической теории машинного обучения. – М.: МФТИ-ИППИ, 2008.
- Вьюгин В.В.. Математические основы машинного обучения и прогнозирования. – М.: МЦНМО, 2013.
- Statistical Learning Theory and Sequential Prediction (Lecture Notes)
- Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006.
Дополнительная литература
- Bousquet, O., Boucheron, S., and Lugosi, G.: Introduction to statistical learning theory. in: Advanced Lectures on Machine Learning. pp. 169--207 (2004)
- Steinwart, I.: On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research. 2, 67--93 (2001)
- Rakhlin, A., Sridharan, K., Tewari, A.: Online learning: Beyond regret. In Proceedings of the 24rd Annual Conference on Learning Theory, v/ 19 of JMLR Workshop and Conference Proceedings, pages 559--594, 2011. longer version available as arXiv:1011.3168 (2011)
- S Bubeck and N. Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. In Foundations and Trends in Machine Learning, Vol 5: No 1, 1-122, 2012.
