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

ПРОГРАММА

 

по дисциплине: Математические основы машинного обучения и прогнозирования.

по направлению: 010900 «Прикладные математика и физика»

факультет: ФУПМ

кафедра: математических основ управления

курс: III

семестры: 9, 10

Трудоёмкость: базовая часть – 5 зач. ед.

вариативная часть – 5 зач. ед.

по выбору студента – 0 зач. ед.

лекции – 66 часов Экзамен – 5, 6 семестр

практические (семинарские)

занятия – 66 часа Диф. зачет – нет

лабораторные занятия – нет

Самостоятельная работа – 20 часов

ВСЕГО ЧАСОВ – 132

Программу составили:

д.ф.-м.н., профессор В.В. Вьюгин, к.ф.-м.н., доцент А.В. Гасников.

 

Программа принята на заседании

кафедры математических основ управления

26 апреля 2014 года

 

Заведующий кафедрой С. А. Гуз

Часть 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. Игры с предсказаниями экспертов

 

22. Постановка задачи предсказания с использованием экспертных стратегий. Понятие (внешнего) регрета. Алгоритм взвешенного большинства. Оценка числа ошибок.

23. Алгоритм оптимального распределения потерь в режиме онлайн. Оценка его регрета.

24. Алгоритм следования за возмущенным лидером. Оценка его регрета. Состоятельность по Ханнану.

25. Задача минимизации регрета с точки зрения теории оптимизации. Алгоритм следования за регуляризованным лидером.

26. Онлайн метод градиентного спуска.

27. Онлайн метод зеркального спуска.

28. Неравенства больших уклонений. Варианты неравенства Хефдинга.

29. Алгоритм экспоненциального взвешивания экспертных решений.

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

31. Задача о многоруком бандите. Стохастическая и детерминированная постановки. Алгоритм для детерминированной постановки.

32. Бустинг. Алгоритм Адабуст и его свойства.

33. Агрегирующий алгоритм Вовка. Конечное и бесконечное множество экспертов.

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

35. Универсальный портфель акций Ковера. Алгоритм построения портфеля. Оценка выигрыша.

36. Применение агрегирующего алгоритма для многомерной регрессии в режиме онлайн.

37. Калибруемость предсказаний по Дэвиду. Алгоритмы построения калибруемых предсказаний.

38. Универсальные RKHS. Построение универсальных алгоритмов для онлайн регрессии на основе метода калибруемости.

39. Средние Радемахера и оценка калибровочной ошибки.

40. Агрегирующий алгоритм как результат построения калибруемых предсказаний.

Литература

1. Вьюгин В.В. Элементы математической теории машинного обучения. – М.: МФТИ-ИППИ, 2008.

2. Вьюгин В.В.. Математические основы машинного обучения и прогнозирования. – М.: МЦНМО, 2013.

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

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.

ЗАДАНИЕ № 1

 

 

Подписано в печать 28.06.2013. Формат 60 ´ 84 .

Усл. печ. л. 1,0. Тираж 130 экз. Заказ №

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Московский физико-технический институт

(государственный университет)»

Отдел оперативной полиграфии «Физтех-полиграф»

141700, Московская обл., г. Долгопрудный, Институтский пер., 9

E-mail: rio@mail.mipt.ru