скачать министерство образования и науки российской федерации Федеральное агентство по образованиюГосударственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет) УТВЕРЖДАЮ проректор по учебной работе д.т.н. Е.В. Глухова «___» _____________ 200__ г. П Р О Г Р А М М Акурса ИССЛЕДОВАНИЕ ОПЕРАЦИЙ по направлению 010600 «Прикладные математика и физика» по магистерской программе 010656 факультет РТК кафедра проблем передачи и обработки информации курс IV ^ лекции 34 часа Экзамен 7 семестр (осенний) семинары нет Зачёт нет лабораторные занятия 34 часасамостоятельная работа 2 часа в неделю ВСЕГО ЧАСОВ 68^ проблем передачи и обработки информации02 июня 2008 года^ чл.-корр. РАН А.П. Кулешов I. Элементы теории классификации и регрессии с опорными векторами. 1. Постановка задачи классификации. Байесовский классификатор. Линейные классификаторы: персептрон. Алгоритм Розенблатта. Теорема Новикова о сходимости. 2. Теория обобщения Вапника–Червоненкиса. Верхняя оценка вероятности ошибки классификации через VC-размерность класса функций классификации. 3. VC-размерность, определение, основное свойство. VC-размерность класса всех линейных (однородных) классификаторов. 4. Метод опорных векторов. Оптимальная гиперплоскость. Алгоритм построения оптимальной гиперплоскости. Оценка вероятности ошибки обобщения через число опорных векторов. 5. SVM - метод в пространстве признаков, примеры. Ядра. 6. Случай неотделимой выборки. Вектор переменных мягкого отступа. Оценка вероятности ошибки обобщения. Оптимизационная задача для классификации с ошибками в квадратичной норме. 7. Случай неотделимой выборки. Вектор переменных мягкого отступа. Оценка вероятности ошибки обобщения. Оптимизационная задача для классификации с ошибками в линейной норме. Оптимизационная задача для классификации с ошибками в форме задачи линейного программирования. 8. Задача многомерной регрессии. Простая линейная регрессия. Гребневая регрессия. 9. Задача многомерной регрессии. Регрессия с опорными векторами. Ошибка обобщения при регрессии. Решение задачи гребневой регрессии с помощью SVM. 10. Гребневая регрессия в прямой форме и в двойственной форме как частный случай регрессии с опорными векторами в случае квадратичной функции потерь. Нелинейная многомерная гребневая регрессия (с ядром). ^ 11. Задача универсального прогнозирования в режиме он-лайн: статистический подход. 12. Калибруемость прогнозов. Алгоритм вычисления хорошо калибруемых прогнозов. 13. Прогнозирование с произвольным ядром. III. Элементы сравнительной теории машинного обучения. 14. Алгоритм оптимального распределения потерь в режиме он-лайн. 15. Задача нахождения оптимальных решений с учетом экспертных стратегий. Алгоритм экспоненциального взвешивания экспертных решений. 16. Рандомизированные прогнозы. 17. Усиление простых классификаторов – Boosting. Алгоритм AdaBoost. ^ 18. Антагонистические игры двух игроков. Достаточное условие существования седловой точки. 19. Достаточное условие существования седловой точки. Смешанные расширения матричных игр. Минимаксная теорема. 20. Чистые стратегии. Решение матричной игры типа 2 x M. Решение игры типа N x M. 21. Бесконечные игры с рандомизированными предсказаниями. Построение выигрышной стратегии предсказателя с использованием минимаксной теоремы. 22. Хорошо калибруемые предсказания. Универсальная калибруемость со счетным числом правил выбора. ^ 23. Экспоненциально выпуклые функции потерь. Агрегирующий алгоритм для конечного числа экспертов. 24. Агрегирующий алгоритм для бесконечного пространства экспертов. Агрегирующий псевдоалгоритм, функция подстановки. 25. Агрегирующий алгоритм для конечного числа экспертов. Игра с логарифмической функцией потерь. Построение функции подстановки. 26. Агрегирующий алгоритм для конечного числа экспертов. Простая игра на предсказания. Построение функции подстановки. 27. Агрегирующий алгоритм для конечного числа экспертов. Игра с квадратичной функцией потерь. Построение функции подстановки. 28. Многомерная он-лайн регрессия с помощью агрегирующего алгоритма. Алгоритм многомерной линейной регрессии, Оценки ошибки предсказания. 29. Универсальный портфель. Применение агрегирующего алгоритма для построения универсального портфеля. ^ 1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «РХД», 2001. 288 с. 2. Оуэн Г. Теория игр. М.: Издательство «ЛКИ» (Editorial URSS), 2008. 218 с. 3. Вьюгин В.В. Алгоритмическая энтропия (сложность) конечных объектов и ее применения к определению случайности и количества информации. – В сб. «Семиотика и информатика» Вып. 16. М.: ВИНИТИ, 1981. С. 14-43. СПИСОК ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ 1. Shafer, G., Vovk, V., Probability and Finance. It's Only a Game! New York: Wiley, 2001. 414 p. 2. Vladimir Vovk, Glenn Shafer, Good randomized sequential probability forecasting is always possible // J. Royal Stat. Soc. B, 67 (2005), p. 747-763. 3. Cristianini N., Shawe-Taylor J. An introduction to support vector machines (and other kernel-based learning method), Cambridge UP, 2000. 187 p. 4. Nicolo Cesa-Bianchi, Gabor Lugosi. Prediction, Learning and Games. Cambridge University Press, New York, 2006. 394 p. 5. Sipser M. Theory of computation. Massachusetts Institute of Technology (MIT) Press, 2006. 6. Sipser M. Theory of computation. PWS Publ. Comp., Boston, 1996.
|