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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Экзамен)
 
(31 промежуточная версия не показана)
Строка 5: Строка 5:
'''Лектор''': [[Участник:Kropotov|Д.А. Кропотов]]<br>
'''Лектор''': [[Участник:Kropotov|Д.А. Кропотов]]<br>
'''Семинарист''': А.О. Родоманов<br>
'''Семинарист''': А.О. Родоманов<br>
-
'''Ассистент''': Н.А. Шаповалов
+
'''Ассистенты''': В.М. Гринберг, Н.А. Шаповалов, А.Г. Таскынов
Занятия проходят: по понедельникам в ауд. 637, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
Занятия проходят: по понедельникам в ауд. 637, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
Строка 11: Строка 11:
Инвайт в AnyTask: EyxQPxD.
Инвайт в AnyTask: EyxQPxD.
-
{{важно|Внимание! В понедельник 10 сентября занятий по курсу не будет.}}
+
Таблица с оценками: https://docs.google.com/spreadsheets/d/1Ctemm8j2ci0TRAQQBN-0_AGw_Yf_pfFn3mN1W4krLkg/edit?usp=sharing.
 +
 
 +
Все вопросы по курсу можно задавать в специальной Telegram группе, ссылку на которую можно получить у преподавателя.
 +
 
 +
== Экзамен ==
 +
Экзамен состоится 14 января в 11-00, ауд. 503. На экзамене при подготовке билета разрешается пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя.
 +
 
 +
[[Media:MOMO18_ExamQuestions.pdf‎‎|Список вопросов к экзамену]]
== Система выставления оценок по курсу ==
== Система выставления оценок по курсу ==
Строка 46: Строка 53:
|-
|-
| 7
| 7
-
| Задачи условной оптимизации: теория. ||
+
| Условия Каруша-Куна-Таккера. Двойственность Лагранжа. ||
|-
|-
| 8
| 8
Строка 61: Строка 68:
|-
|-
| 12
| 12
-
| Быстрый градиентный метод Нестерова ||
+
| Ускоренный градиентный метод || [[Media:MOMO18_Lecture12.pdf|Конспект]]
|-
|-
| 13
| 13
Строка 67: Строка 74:
|-
|-
| 14
| 14
-
| Продвинутая стохастическая оптимизация ||
+
| Ускоренный метод для минимизации конечных сумм (Katyusha) ||
|-
|-
|}
|}
Строка 79: Строка 86:
|-
|-
| 1
| 1
-
| Скорости сходимости. Матрично-векторные скалярные произведения и нормы || [[Media:MOMO17_Seminar1.pdf|Конспект]]
+
| Матрично-векторное дифференцирование (часть 1) || [[Media:MOMO18_Seminar1.pdf‎‎|Конспект]]
|-
|-
| 2
| 2
-
| Матрично-векторное дифференцирование || [[Media:MOMO17_Seminar2.pdf|Конспект]]
+
| Матрично-векторное дифференцирование (часть 2). Условия оптимальности. ||
|-
|-
| 3
| 3
-
| Методы градиентного спуска и Ньютона. Детали реализации и примеры работы || [[Media:MOMO17_Seminar3_handout.pdf|Презентация]]
+
| Методы градиентного спуска и Ньютона. Детали реализации и примеры работы || [[Media:MOMO18_Seminar3.pdf‎‎|Презентация]]
|-
|-
| 4
| 4
-
| Выпуклые множества и функции || [[Media:MOMO17_Seminar4.pdf|Конспект]]
+
| Выпуклые множества || [[Media:MOMO18_Seminar4.pdf‎‎|Конспект]]
|-
|-
| 5
| 5
-
| Самосогласованные функции и метод Ньютона || [[Media:MOMO17_Seminar5.pdf|Конспект]]
+
| Выпуклые функции || [[Media:MOMO18_Seminar5.pdf‎‎|Конспект]]
|-
|-
| 6
| 6
-
| Квазиньютоновские методы || [[Media:MOMO17_Seminar6.pdf|Конспект]]
+
| Квазиньютоновские методы || [[Media:MOMO18_Seminar6.pdf‎‎|Конспект]]
|-
|-
| 7
| 7
-
| Условия Каруша--Куна--Таккера. Эквивалентные преобразования задач || [[Media:MOMO17_Seminar7.pdf|Конспект]]
+
| Условия Каруша-Куна-Таккера. Двойственность Лагранжа. || [[Media:MOMO18_Seminar7.pdf‎‎|Конспект]]
|-
|-
| 8
| 8
-
| Сопряженные функции. Двойственность || [[Media:MOMO17_Seminar8.pdf|Конспект]]
+
| Сопряженные функции. Двойственность Фенхеля. || [[Media:MOMO18_Seminar8.pdf‎‎|Конспект]]
|-
|-
| 9
| 9
-
| Метод барьеров ||
+
| Стандартные классы выпуклых задач (LP, QP, QCQP, SOCP, SDP). Сводимость. || [[Media:MOMO18_Seminar9.pdf‎‎|Конспект]]
|-
|-
| 10
| 10
-
| Субдифференциальное исчисление ||
+
| Субдифференциальное исчисление || [[Media:MOMO18_Seminar10.pdf‎‎|Конспект]]
|-
|-
| 11
| 11
Строка 112: Строка 119:
|-
|-
| 12
| 12
-
| Коническое и полуопределенное программирование ||
+
| Сглаживание негладких функций ||
|-
|-
| 13
| 13
-
| Техника сглаживания ||
+
| Случайный координатный спуск ||
|-
|-
| 14
| 14
-
| Адаптивные длины шагов в стохастическом субградиентном методе. Метод AdaGrad ||
+
| Случайный координатный спуск (продолжение) ||
|-
|-
|}
|}
 +
 +
== Дополнительный материал ==
 +
# [[Media:MOMO18_Extra1.pdf‎‎|Скорости сходимости последовательностей]].
 +
# [[Media:MOMO18_Extra2.pdf‎‎|Матрично-векторные скалярные произведения и нормы]].
 +
# [[Media:MOMO18_Extra3.pdf‎‎|Методы сопряженных градиентов]].
 +
# [[Media:MOMO18_Extra4.pdf‎‎|Самосогласованные функции и метод Ньютона]].
 +
# [[Media:MOMO18_Extra5.pdf‎‎|Метод зеркального спуска]].
 +
 +
== Домашние задания ==
 +
Задание 1. [[Media:MOMO18_Homework1.pdf‎‎|Дифференцирование]] ([[Media:MOMO18_Homework1.tex.zip‎‎|TeX]]). <br />
 +
Задание 2. [[Media:MOMO18_Homework2.pdf‎‎|Выпуклые множества и функции]] ([[Media:MOMO18_Homework2.tex.zip‎‎|TeX]]). <br />
 +
Задание 3. [[Media:MOMO18_Homework3.pdf‎‎|Условия Каруша-Куна-Таккера. Двойственность.]] ([[Media:MOMO18_Homework3.tex.zip‎‎|TeX]]). <br />
 +
Задание 4. [[Media:MOMO18_Homework4.pdf‎‎|Субдифференциалы]] ([[Media:MOMO18_Homework4.tex.zip‎‎|TeX]]). <br />
 +
 +
[[Media:MOMO18_TeX_StyleFiles.zip‎‎|Стилевые файлы TeX]].
 +
 +
== Практические задания ==
 +
Задание 1. [[Media:MOMO18_Practice1.pdf‎‎|Методы градиентного спуска и Ньютона]]. <br />
 +
Задание 2. [[Media:MOMO18_Practice2.pdf‎‎|Продвинутые методы безусловной оптимизации]]. <br />
 +
Задание 3. [[Media:MOMO18_Practice3.pdf‎‎|Метод барьеров]]. <br />
 +
Задание 4. [[Media:MOMO18_Practice4.pdf‎‎|Композитная оптимизация]]. <br />
== Литература ==
== Литература ==
-
# S. Sra et al.. [http://libgen.io/book/index.php?md5=9799B67D2A9C45DCAC9D323252054DAF Optimization for Machine Learning], MIT Press, 2011.
 
# J. Nocedal, S. Wright. [http://libgen.io/book/index.php?md5=7016B74CFE6DC64C75864322EE4AA081 Numerical Optimization], Springer, 2006.
# J. Nocedal, S. Wright. [http://libgen.io/book/index.php?md5=7016B74CFE6DC64C75864322EE4AA081 Numerical Optimization], Springer, 2006.
# A. Ben-Tal, A. Nemirovski. [http://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2015.pdf Optimization III. Lecture Notes], 2013.
# A. Ben-Tal, A. Nemirovski. [http://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2015.pdf Optimization III. Lecture Notes], 2013.
-
# Б. Поляк. [http://lab7.ipu.ru/files/polyak/polyak-optimizationintro.pdf Введение в оптимизацию], Наука, 1983.
 
-
# S. Boyd, L. Vandenberghe. [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization], Cambridge University Press, 2004.
 
# Y. Nesterov. [http://libgen.io/book/index.php?md5=049F85DF4693D7C3DC27DDDD0720A096 Introductory Lectures on Convex Optimization: A Basic Course], Springer, 2003.
# Y. Nesterov. [http://libgen.io/book/index.php?md5=049F85DF4693D7C3DC27DDDD0720A096 Introductory Lectures on Convex Optimization: A Basic Course], Springer, 2003.
-
# R. Fletcher. [http://libgen.io/book/index.php?md5=CAFE400511F96424029AB1DCDB1E39F7 Practical Methods of Optimization], Wiley, 2000.
+
# Ю.Е. Нестеров. [https://mipt.ru/dcam/upload/abb/nesterovfinal-arpgzk47dcy.pdf Методы выпуклой оптимизации], МЦНМО, 2010
-
# A. Antoniou, W.-S. Lu. [http://libgen.io/book/index.php?md5=5F2D534ED4F5F26608F21866E9A3ABD5 Practical Optimization: Algorithms and Engineering Applications], Springer, 2007.
+
# S. Boyd, L. Vandenberghe. [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization], Cambridge University Press, 2004.
-
# W. Press et al.. [http://libgen.io/book/index.php?md5=0EDC79280D53EF968FFA05D63DFD5E55 Numerical Recipes. The Art of Scientific Computing], Cambridge University Press, 2007.
+
# J.-P. Hiriart-Urruty, C. Lemaréchal. [http://libgen.io/book/index.php?md5=3D79DA4685F6B25C9111F8DF1A41DFD0 Convex Analysis and Minimization Algorithms I: Fundamentals] and [http://libgen.io/book/index.php?md5=4EAC7D94D7664FA3DAD900A9410C48E5 Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods], Springer-Verlag Berlin Heidelberg, 1993.
 +
# D. Bertsekas. [http://libgen.io/book/index.php?md5=D0DDDF4CF756D16AE5AA77C87ECDEDDA Convex Analysis and Optimization], Athena Scientific, 2003.
 +
# Б.Т. Поляк. [http://premolab.ru/sites/default/files/polyak-optimizationintro.djvu Введение в оптимизацию], Наука, 1983.
 +
# J. Duchi. [https://stanford.edu/~jduchi/PCMIConvex/Duchi16.pdf Introductory Lectures on Stochastic Optimization], Graduate Summer School Lectures, 2016.
 +
# S. Sra et al.. [http://libgen.io/book/index.php?md5=9799B67D2A9C45DCAC9D323252054DAF Optimization for Machine Learning], MIT Press, 2011.
== Архив ==
== Архив ==

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

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

Лектор: Д.А. Кропотов
Семинарист: А.О. Родоманов
Ассистенты: В.М. Гринберг, Н.А. Шаповалов, А.Г. Таскынов

Занятия проходят: по понедельникам в ауд. 637, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.

Инвайт в AnyTask: EyxQPxD.

Таблица с оценками: https://docs.google.com/spreadsheets/d/1Ctemm8j2ci0TRAQQBN-0_AGw_Yf_pfFn3mN1W4krLkg/edit?usp=sharing.

Все вопросы по курсу можно задавать в специальной Telegram группе, ссылку на которую можно получить у преподавателя.

Экзамен

Экзамен состоится 14 января в 11-00, ауд. 503. На экзамене при подготовке билета разрешается пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя.

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

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

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

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

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

Лекции

№ п/п Занятие Материалы
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 Ускоренный метод для минимизации конечных сумм (Katyusha)

Семинары

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

Дополнительный материал

  1. Скорости сходимости последовательностей.
  2. Матрично-векторные скалярные произведения и нормы.
  3. Методы сопряженных градиентов.
  4. Самосогласованные функции и метод Ньютона.
  5. Метод зеркального спуска.

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

Задание 1. Дифференцирование (TeX).
Задание 2. Выпуклые множества и функции (TeX).
Задание 3. Условия Каруша-Куна-Таккера. Двойственность. (TeX).
Задание 4. Субдифференциалы (TeX).

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

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

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

Литература

  1. J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
  2. A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
  3. Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.
  4. Ю.Е. Нестеров. Методы выпуклой оптимизации, МЦНМО, 2010
  5. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
  6. J.-P. Hiriart-Urruty, C. Lemaréchal. Convex Analysis and Minimization Algorithms I: Fundamentals and Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, Springer-Verlag Berlin Heidelberg, 1993.
  7. D. Bertsekas. Convex Analysis and Optimization, Athena Scientific, 2003.
  8. Б.Т. Поляк. Введение в оптимизацию, Наука, 1983.
  9. J. Duchi. Introductory Lectures on Stochastic Optimization, Graduate Summer School Lectures, 2016.
  10. S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.

Архив

2017 год

2016 год

2015 год

2014 год

2012 год

См. также

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

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

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

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

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