Личный кабинет
Адрес e-mail:
Регистрация Забыли пароль?

Обучение, предсказания, игры

Печать DOC PDF

Альтернативный курс, организованный кафедрой МОУ ФУПМ МФТИ и лабораторией ПреМоЛаб.

Курс читается для студентов 5-го курса по пятницам. 
Лекторы: В.В. Вьюгин, А.В. Гасников 
Начало в 17:05 в 516 ГК.  

Задачи в задавальник

Часть I. Статистическая теория машинного обучения

  1. Постановка задачи классификации. Байесовский классификатор. Примеры классификаторов: персептрон, нейронные сети.
  2. PAC-теория ошибок. Теория обобщения Вапника – Червоненкиса. Верхние оценки ошибки классификации.
  3. VC-размерность. Лемма Вапника – Червоненкиса  (Сауэра, Шелаха)
  4. VC-размерность класса линейных классификаторов. Примеры вычисления VC-размерности других классов функций
  5. Теория обобщения для задач классификации с помощью пороговых решающих правил. Число покрытия для классов функций. Оценка ошибки обобщения через число покрытия.
  6.  Пороговая размерность. Оценка ошибки обобщения через пороговую размерность.
  7. Покрытия и упаковки  в метрических пространствах. Теорема Алона, Бен-Давида, Хауслера и Чеза-Бьянки.
  8. Средние по Радемахеру. Равномерная оценка отклонения эмпирического среднего от математического ожидания для класса функций.
  9. Неравенство Мак-Диармонда и его применения..
  10. Среднее Радемахера композиции.
  11. Средние по Радемахеру и другие меры емкости классов функций (VC-размерность, число покрытия)..
  12. Оценка ошибки обобщения с помощью среднего по Радемахеру.
  13. Алгоритм построения оптимальной разделяющей гиперплоскости. Задача оптимизации. Опорные векторы.
  14. SVM-метод в пространстве признаков. Пространства, порожденные воспроизводящим ядром (RKHS) и их свойства.
  15. Построение канонического RKHS.
  16. Теорема о представителе.
  17. Случай неразделимой выборки. Вектор переменных мягкого отступа. . Оценка ошибки в случае неразделимой выборки.
  18. Задача оптимизации для классификации с ошибками в квадратичной норме.
  19. Задача оптимизации для классификации с ошибками в линейной норме.
  20. Многомерная регрессия с помощью SVM. Гребневая регрессия.
  21. Конформные предсказания. Метаалгоритм. Примеры мер неконформности.

Часть 2. Игры с предсказаниями экспертов

  1. Постановка задачи предсказания с использованием экспертных стратегий. Понятие (внешнего) регрета. Алгоритм взвешенного большинства. Оценка числа ошибок.
  2. Алгоритм оптимального распределения потерь в режиме онлайн. Оценка его регрета.
  3. Алгоритм следования за возмущенным лидером. Оценка его регрета. Состоятельность по Ханнану.
  4. Задача минимизации регрета с точки зрения теории оптимизации.  Алгоритм следования за регуляризованным лидером.
  5. Онлайн метод градиентного спуска.
  6. Онлайн  метод зеркального спуска.
  7. Неравенства больших уклонений. Варианты неравенства Хефдинга.
  8. Алгоритм экспоненциального взвешивания  экспертных решений.
  9. Алгоритм экспоненциального взвешивания  экспертных решений с переменным параметром обучения.
  10. Задача о многоруком бандите. Стохастическая и детерминированная постановки. Алгоритм для детерминированной постановки.
  11. Бустинг. Алгоритм Адабуст и его свойства.
  12. Агрегирующий алгоритм Вовка. Конечное и бесконечное множество экспертов.
  13. Применение агрегирующего алгоритма для различных функций потерь: логарифмической, квадратичной, простой.
  14. Универсальный портфель акций Ковера. Алгоритм построения портфеля. Оценка выигрыша.
  15. Применение агрегирующего алгоритма для многомерной регрессии в режиме онлайн.
  16. Калибруемость предсказаний по Дэвиду. Алгоритмы построения калибруемых предсказаний.
  17. Универсальные RKHS. Построение универсальных алгоритмов для онлайн регрессии на основе метода калибруемости.
  18. Средние Радемахера и оценка калибровочной ошибки.
  19. Агрегирующий алгоритм как результат построения калибруемых предсказаний.

Литература

  1. Вьюгин В.В. Элементы математической теории машинного обучения. – М.: МФТИ-ИППИ, 2008.
  2. Вьюгин В.В.. Математические основы машинного обучения и прогнозирования. – М.: МЦНМО, 2013.
  3. Statistical Learning Theory and Sequential Prediction (Lecture Notes)
  4. Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006. 

Дополнительная  литература

  1. Bousquet, O., Boucheron, S., and Lugosi, G.: Introduction to statistical learning theory. in: Advanced Lectures on Machine Learning. pp. 169--207 (2004)
  2. Steinwart, I.: On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research. 2, 67--93 (2001)
  3. 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)
  4. 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.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

МФТИ в социальных сетях