Методы оптимизации в машинном обучении (курс лекций)/2017

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Домашние задания)
(Экзамен)
 
(30 промежуточных версий не показаны.)
Строка 7: Строка 7:
'''Ассистент''': Н.А. Шаповалов
'''Ассистент''': Н.А. Шаповалов
-
Занятия проходят на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 612, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
+
Занятия проходят:
 +
* на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 612, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
 +
* на базовой кафедре [[Интеллектуальные системы (кафедра МФТИ)|Интеллектуальных систем МФТИ]] по средам в [[Вычислительный центр РАН|ВЦ РАН]] в к.355, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
Инвайты в AnyTask: UAb78YK для ВМК, YYGCLOZ для Физтеха.
Инвайты в AnyTask: UAb78YK для ВМК, YYGCLOZ для Физтеха.
Группа в Телеграмме для вопросов по курсу: [https://t.me/joinchat/EYDfykF5ez-V1D39q3zi4Q https://t.me/joinchat/EYDfykF5ez-V1D39q3zi4Q].
Группа в Телеграмме для вопросов по курсу: [https://t.me/joinchat/EYDfykF5ez-V1D39q3zi4Q https://t.me/joinchat/EYDfykF5ez-V1D39q3zi4Q].
 +
 +
'''Таблица с результатами находится [https://docs.google.com/spreadsheets/d/1TT7oVqR7hPQEVMJKWRLiOBfdkmj1927sEMPLVlXMeo4/edit?usp=sharing здесь]'''
 +
 +
== Экзамен ==
 +
 +
Экзамен для студентов ВМК состоится 13 января в ауд. 503, начало в 11-00. Экзамен для студентов МФТИ состоится 25 декабря в ВЦ РАН в к.355, начало в 11-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя.
 +
 +
[[Media:MOMO17_Exam_questions.pdf‎|Список вопросов к экзамену]].
== Система выставления оценок по курсу ==
== Система выставления оценок по курсу ==
-
В рамках курса предполагается четыре практических задания, четыре домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Домашнее задание после срока сдачи не принимается. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, через две недели после срока сдачи практическое задание не принимается.
+
В рамках курса предполагается четыре практических задания, четыре домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Домашнее задание после срока сдачи не принимается. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла (соответственно 0.2 для МФТИ), через две недели после срока сдачи практическое задание не принимается.
 +
 
 +
Итоговая оценка за курс вычисляется с помощью округления вверх взвешенной суммы оценки за экзамен (вклад 40%), оценки за практические задания (вклад 40%) и оценки за домашние задания (вклад 20%). При этом для получения итоговой оценки 5 (соответственно >= 8 для студентов МФТИ) необходимо сдать на положительный балл все практичекие и все домашние задания, а также набрать на экзамене не ниже 4 баллов (соответственно >= 5 для МФТИ); для получения итоговой оценки 4 (соответственно >= 5 для МФТИ) необходимо сдать любые три практических задания и любые два домашних задания; для получения итоговой оценки 3 (соответственно >= 3 для МФТИ) необходимо сдать любые два практических задания и любое одно домашнее задание.
 +
 
 +
При выполнении каждого задания можно получить бонусные баллы за необязательные пункты, но при этом итоговые оценки за практическую часть курса и за домашнюю часть курса не могут превысить соответствующих максимальных оценок без учета бонусов. Например, если используется пятибальная шкала и количество (скажем, домашних) заданий равно четырем, то за счет бонусов оценки за задания могут быть следующими: 1) 5.5, 4, 4, 4; или 2) 5.5, 5, 5, 5. В первом случае итоговая оценка за домашние задания составляет 17.5, а во втором --- 20.0.
== Домашние задания ==
== Домашние задания ==
-
Задание 1. [[Media:MOMO17_Homework1.pdf‎‎|Скорости сходимости и матрично-векторное дифференцирование]].
+
Задание 1. [[Media:MOMO17_Homework1.pdf‎‎|Скорости сходимости и матрично-векторное дифференцирование]] ([[Media:MOMO17_Homework1.tex.zip‎‎|TeX]]). <br />
-
Задание 2. [[Media:MOMO17_Homework2.pdf‎‎|Выпуклые множества и функции]].
+
Задание 2. [[Media:MOMO17_Homework2.pdf‎‎|Выпуклые множества и функции]] ([[Media:MOMO17_Homework2.tex.zip‎‎|TeX]]). <br />
 +
Задание 3. [[Media:MOMO17_Homework3.pdf‎‎|Условная оптимизация]] ([[Media:MOMO17_Homework3.tex.zip‎‎|TeX]]). <br />
 +
Задание 4. [[Media:MOMO17_Homework4.pdf‎‎|Субдифференциалы]] ([[Media:MOMO17_Homework4.tex.zip‎‎|TeX]]). <br />
 +
 
 +
[[Media:MOMO17_TeX_StyleFiles.zip‎‎|Стилевые файлы TeX]].
== Практические задания ==
== Практические задания ==
-
Задание 1. [[Media:MOMO17_Practice1.pdf‎‎|Методы градиентного спуска и Ньютона]].
+
Задание 1. [[Media:MOMO17_Practice1.pdf‎‎|Методы градиентного спуска и Ньютона]] ([[Media:MOMO17_Practice1.tex.zip‎‎|TeX]]). <br />
 +
Задание 2. [[Media:MOMO17_Practice2.pdf‎‎|Продвинутые методы безусловной оптимизации]] ([[Media:MOMO17_Practice2.tex.zip‎‎|TeX]]). <br />
 +
Задание 3. [[Media:MOMO17_Practice3.pdf‎‎|Метод барьеров]] ([[Media:MOMO17_Practice3.tex.zip‎‎|TeX]]). <br />
 +
Задание 4. [[Media:MOMO17_Practice4.pdf‎‎|Композитная оптимизация]] ([[Media:MOMO17_Practice4.tex.zip‎‎|TeX]]).
== Лекции ==
== Лекции ==
Строка 94: Строка 115:
|-
|-
| 5
| 5
-
| Самосогласованные функции и метод Ньютона ||
+
| Самосогласованные функции и метод Ньютона || [[Media:MOMO17_Seminar5.pdf|Конспект]]
|-
|-
| 6
| 6
Строка 103: Строка 124:
|-
|-
| 8
| 8
-
| Стандартные классы выпуклых задач и двойственность || [[Media:MOMO17_Seminar8.pdf|Конспект]]
+
| Сопряженные функции. Двойственность || [[Media:MOMO17_Seminar8.pdf|Конспект]]
|-
|-
| 9
| 9
-
| Метод внутренней точки ||
+
| Метод барьеров ||
|-
|-
| 10
| 10
Строка 115: Строка 136:
|-
|-
| 12
| 12
-
| Техника сглаживания. Часть 1 ||
+
| Коническое и полуопределенное программирование ||
|-
|-
| 13
| 13
-
| Техника сглажвания. Часть 2 ||
+
| Техника сглаживания ||
|-
|-
| 14
| 14
-
| Адаптивные длины шагов в стохастическом градиентном методе. Метод AdaGrad ||
+
| Адаптивные длины шагов в стохастическом субградиентном методе. Метод AdaGrad ||
|-
|-
|}
|}

Текущая версия

Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности. Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.

Лектор: Д.А. Кропотов
Семинарист: А.О. Родоманов
Ассистент: Н.А. Шаповалов

Занятия проходят:

Инвайты в AnyTask: UAb78YK для ВМК, YYGCLOZ для Физтеха.

Группа в Телеграмме для вопросов по курсу: https://t.me/joinchat/EYDfykF5ez-V1D39q3zi4Q.

Таблица с результатами находится здесь

Экзамен

Экзамен для студентов ВМК состоится 13 января в ауд. 503, начало в 11-00. Экзамен для студентов МФТИ состоится 25 декабря в ВЦ РАН в к.355, начало в 11-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя.

Список вопросов к экзамену.

Система выставления оценок по курсу

В рамках курса предполагается четыре практических задания, четыре домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Домашнее задание после срока сдачи не принимается. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла (соответственно 0.2 для МФТИ), через две недели после срока сдачи практическое задание не принимается.

Итоговая оценка за курс вычисляется с помощью округления вверх взвешенной суммы оценки за экзамен (вклад 40%), оценки за практические задания (вклад 40%) и оценки за домашние задания (вклад 20%). При этом для получения итоговой оценки 5 (соответственно >= 8 для студентов МФТИ) необходимо сдать на положительный балл все практичекие и все домашние задания, а также набрать на экзамене не ниже 4 баллов (соответственно >= 5 для МФТИ); для получения итоговой оценки 4 (соответственно >= 5 для МФТИ) необходимо сдать любые три практических задания и любые два домашних задания; для получения итоговой оценки 3 (соответственно >= 3 для МФТИ) необходимо сдать любые два практических задания и любое одно домашнее задание.

При выполнении каждого задания можно получить бонусные баллы за необязательные пункты, но при этом итоговые оценки за практическую часть курса и за домашнюю часть курса не могут превысить соответствующих максимальных оценок без учета бонусов. Например, если используется пятибальная шкала и количество (скажем, домашних) заданий равно четырем, то за счет бонусов оценки за задания могут быть следующими: 1) 5.5, 4, 4, 4; или 2) 5.5, 5, 5, 5. В первом случае итоговая оценка за домашние задания составляет 17.5, а во втором --- 20.0.

Домашние задания

Задание 1. Скорости сходимости и матрично-векторное дифференцирование (TeX).
Задание 2. Выпуклые множества и функции (TeX).
Задание 3. Условная оптимизация (TeX).
Задание 4. Субдифференциалы (TeX).

Стилевые файлы TeX.

Практические задания

Задание 1. Методы градиентного спуска и Ньютона (TeX).
Задание 2. Продвинутые методы безусловной оптимизации (TeX).
Задание 3. Метод барьеров (TeX).
Задание 4. Композитная оптимизация (TeX).

Лекции

№ п/п Занятие Материалы
1 Введение в курс. Классы функций в оптимизации. Скорости сходимости (Скорости сходимости) [Nocedal-Wright, pp. 617-620]
2 Неточная одномерная оптимизация. Метод градиентного спуска, выбор длины шага. [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5]
3 Метод Ньютона. Способы коррекции гессиана до положительно-определённой матрицы
4 Метод сопряженных градиентов
5 Неточный/безгессианный метод Ньютона
6 Квазиньютоновские методы. Метод L-BFGS
7 Задачи условной оптимизации: теория.
8 Метод внутренней точки
9 Прямо-двойственный метод внутренней точки
10 Негладкая оптимизация. Субградиентный метод
11 Разреженные линейный модели. Проксимальные методы.
12 Быстрый градиентный метод Нестерова
13 Стохастическая оптимизация
14 Продвинутая стохастическая оптимизация

Семинары

№ п/п Занятие Материалы
1 Скорости сходимости. Матрично-векторные скалярные произведения и нормы Конспект
2 Матрично-векторное дифференцирование Конспект
3 Методы градиентного спуска и Ньютона. Детали реализации и примеры работы Презентация
4 Выпуклые множества и функции Конспект
5 Самосогласованные функции и метод Ньютона Конспект
6 Квазиньютоновские методы Конспект
7 Условия Каруша--Куна--Таккера. Эквивалентные преобразования задач Конспект
8 Сопряженные функции. Двойственность Конспект
9 Метод барьеров
10 Субдифференциальное исчисление
11 Вычисление проекций и проксимальных отображений
12 Коническое и полуопределенное программирование
13 Техника сглаживания
14 Адаптивные длины шагов в стохастическом субградиентном методе. Метод AdaGrad

Литература

  1. S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.
  2. J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
  3. A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
  4. Б. Поляк. Введение в оптимизацию, Наука, 1983.
  5. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
  6. Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.
  7. R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
  8. A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
  9. W. Press et al.. Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.

Архив

2016 год

2015 год

2014 год

2012 год

См. также

Курс «Графические модели»

Курс «Байесовские методы в машинном обучении»

Спецсеминар «Байесовские методы машинного обучения»

Математические методы прогнозирования (кафедра ВМиК МГУ)

Личные инструменты