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

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

(Различия между версиями)
Перейти к: навигация, поиск
 
(30 промежуточных версий не показаны.)
Строка 1: Строка 1:
__NOTOC__
__NOTOC__
Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
-
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
 
'''Преподаватели''': [[Участник:Kropotov|Кропотов Д.А.]], Бобров Евгений, Таскынов Ануар, Шаповалов Никита, Гадецкий Артём, Гринберг Вадим.
'''Преподаватели''': [[Участник:Kropotov|Кропотов Д.А.]], Бобров Евгений, Таскынов Ануар, Шаповалов Никита, Гадецкий Артём, Гринберг Вадим.
-
Занятия проходят: по пятницам в ауд. 605, лекция с 14-35 до 16-10, семинар с 16-20 до 17-55.
+
Занятия проходят: по пятницам, лекция с 14-35 до 16-10, семинар с 16-20 до 17-55. [https://zoom.us/j/326723048 Ссылка на zoom].
Инвайт в AnyTask: EMdZUhf
Инвайт в AnyTask: EMdZUhf
Строка 11: Строка 10:
Таблица с оценками: ???
Таблица с оценками: ???
-
Все вопросы по курсу можно задавать в Telegram группе: ???
+
Все вопросы по курсу можно задавать в [https://t.me/joinchat/FIB6dlb7a_-uAMSz_R-IMg Telegram группе]
 +
 
 +
Видеозаписи занятий в zoom: [https://www.youtube.com/playlist?list=PLVF5PzSHILHQ_bNQpo-8XXuylN2UYRVNn здесь]
 +
 
 +
== Экзамен ==
 +
Экзамен по курсу состоится 23 июня. Процедура экзамена, а также вопросы к экзамену находятся [https://drive.google.com/file/d/1WV6_HO54jH2aE4mccMv8L2ZyPOhVKhVJ/view?usp=sharing здесь].
 +
 
 +
Распределение студентов по времени на экзамене находится [https://docs.google.com/spreadsheets/d/1Jswe6ZmMKbU1lWrqKNKIQmjnXR52_SMJ7q9C0w_lkP0/edit?usp=sharing здесь]. В таблице указано время начала опроса. За час до этого времени по электронной почте придёт номер билета вместе со ссылкой на zoom конференцию.
 +
 
 +
22 июня в 12-00 состоится консультация к экзамену. [https://us02web.zoom.us/j/89453081236?pwd=UjUwZkhDZU14TFRzNTNOL1lEamFOdz09 Ссылка на zoom].
== Система выставления оценок по курсу ==
== Система выставления оценок по курсу ==
 +
В рамках курса предполагается 6 домашних заданий. За каждое задание можно получить 5 баллов, а также, возможно, дополнительные баллы за выполнение бонусных пунктов. После мягкого дедлайна задание сдаётся со штрафом 0.1 балла в день.
 +
Общая оценка по курсу вычисляется по правилу: Округл_вверх (0.3*<Оценка_за_экзамен> + 0.7*<Оценка_за_семестр>), где <Оценка_за_семестр> = min(5, <Сумма_оценок_за_задания> / 6). Итоговая оценка совпадает с общей при выполнении дополнительных условий:
 +
{| class="standard"
 +
!Итог !! Необходимые условия
 +
|-
 +
| 5 || сдано не менее 5 заданий, оценка за экзамен >= 4
 +
|-
 +
| 4 || сдано не менее 4 заданий, оценка за экзамен >= 3
 +
|-
 +
| 3 || сдано не менее 3 заданий, оценка за экзамен >= 3
 +
|-
 +
|}
== Лекции ==
== Лекции ==
Строка 25: Строка 45:
| 1
| 1
| Введение в курс. Классы функций в оптимизации. Скорости сходимости. Неточная одномерная оптимизация. || [[Media:MOMO18_Extra1.pdf‎‎|Скорости сходимости последовательностей]]
| Введение в курс. Классы функций в оптимизации. Скорости сходимости. Неточная одномерная оптимизация. || [[Media:MOMO18_Extra1.pdf‎‎|Скорости сходимости последовательностей]]
 +
|-
 +
| 2
 +
| Метод градиентного спуска. ||
 +
|-
 +
| 3
 +
| Матричные разложения и метод Ньютона. ||
 +
|-
 +
| 4
 +
| Метод сопряжённых градиентов для решения СЛАУ. ||
 +
|-
 +
| 5
 +
| Неточный/безгессианный метод Ньютона. ||
 +
|-
 +
| 6
 +
| Квазиньютоновские методы. ||
 +
|-
 +
| 7
 +
| Задачи условной оптимизации, теорема ККТ. || [https://youtu.be/oyjetycMeWY Видео]
 +
|-
 +
| 8
 +
| Метод Ньютона и метод логарифмических барьеров для выпуклых задач условной оптимизации. || [https://youtu.be/ShKWvMtisc0 Видео]
 +
|-
 +
| 9
 +
| Негладкая оптимизация. Субградиентный метод. || [https://youtu.be/SEmgm2ucBRE Видео]
 +
|-
 +
| 10
 +
| Проксимальные методы. || [https://youtu.be/dTVan-Si2VE Видео]
 +
|-
 +
| 11
 +
| Ускоренный проксимальный градиентный метод Нестерова. || [https://youtu.be/e308yJKOgyQ Видео]
 +
|-
 +
| 12
 +
| Стохастическая оптимизация || [https://youtu.be/q8VYL51DQhc Видео]
 +
|-
 +
| 13
 +
| Риманова оптимизация || [https://youtu.be/579j3ZEAlF8 Видео]<br> [http://www.eeci-institute.eu/GSC2011/Photos-EECI/EECI-GSC-2011-M5/book_AMS.pdf книга по римановой оптимизации]<br> [https://www.pymanopt.org/ библиотека для римановой оптимизации]
 +
|-
 +
| 14
 +
| Решение задач оптимизации с помощью нейронных сетей || [https://youtu.be/6N9Do9X5mxY Видео]<br> [https://arxiv.org/abs/1606.04474 Статья 1]<br> [https://arxiv.org/abs/1803.08475 Статья 2]
|-
|-
|}
|}
Строка 35: Строка 94:
! width="25%" | Материалы
! width="25%" | Материалы
|-
|-
 +
| 1
 +
| Метод градиентного спуска. ||
 +
|-
 +
| 5
 +
| Нелинейный метод сопряженных градиентов. Предобуславливание || [[Медиа:MOMO20_conjugate_gradients.pdf|Презентация]]
 +
|-
 +
| 6
 +
| Матричные преобразования в квазиньютоновских методах || [https://drive.google.com/file/d/1zlqaDmb84kfZ67BmiMinOKfYCeq68VKO/view?usp=sharing Конспект]
 +
|-
 +
| 7
 +
| Задачи условной оптимизации, теорема ККТ. || [https://youtu.be/-0TFkqqVt_A Видео] [https://yadi.sk/d/Op-nmGrl02lLnQ Конспекты]
 +
|-
 +
| 8
 +
| Двойственность, эквивалентные преобразования задач. || [https://youtu.be/eR8EXeomdN0 Видео] [https://www.dropbox.com/s/nqmcpc2qnulf7w4/Opt-Sem-Duality.pdf?dl=0 Конспект]
 +
|-
 +
| 9
 +
| Субдифференциальное исчисление || [https://youtu.be/pdUGUBzjcUI Видео] [[Медиа:MOMO20_subdifferentials.pdf|Конспект]]
 +
|-
 +
| 10
 +
| Проекции и проксимальные операторы || [https://youtu.be/buMzsBj8Rsk Видео]
 +
|-
 +
| 11
 +
| Сопряжённые функции и нормы || [https://youtu.be/g9DS3k6E3yA Видео] [[Медиа:MOMO20_Conjugate.pdf|Конспект]]
 +
|-
 +
| 12
 +
| Решение задач дискретной оптимизации непрерывными методами || [https://youtu.be/KHOxilxkhxY Видео] [https://drive.google.com/file/d/1iEXeHGZ-3gdCT7hcHreOGlBAc1tTZgE8/view?usp=sharing Презентация]
|-
|-
|}
|}

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

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

Преподаватели: Кропотов Д.А., Бобров Евгений, Таскынов Ануар, Шаповалов Никита, Гадецкий Артём, Гринберг Вадим.

Занятия проходят: по пятницам, лекция с 14-35 до 16-10, семинар с 16-20 до 17-55. Ссылка на zoom.

Инвайт в AnyTask: EMdZUhf

Таблица с оценками: ???

Все вопросы по курсу можно задавать в Telegram группе

Видеозаписи занятий в zoom: здесь

Экзамен

Экзамен по курсу состоится 23 июня. Процедура экзамена, а также вопросы к экзамену находятся здесь.

Распределение студентов по времени на экзамене находится здесь. В таблице указано время начала опроса. За час до этого времени по электронной почте придёт номер билета вместе со ссылкой на zoom конференцию.

22 июня в 12-00 состоится консультация к экзамену. Ссылка на zoom.

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

В рамках курса предполагается 6 домашних заданий. За каждое задание можно получить 5 баллов, а также, возможно, дополнительные баллы за выполнение бонусных пунктов. После мягкого дедлайна задание сдаётся со штрафом 0.1 балла в день.

Общая оценка по курсу вычисляется по правилу: Округл_вверх (0.3*<Оценка_за_экзамен> + 0.7*<Оценка_за_семестр>), где <Оценка_за_семестр> = min(5, <Сумма_оценок_за_задания> / 6). Итоговая оценка совпадает с общей при выполнении дополнительных условий:

Итог Необходимые условия
5 сдано не менее 5 заданий, оценка за экзамен >= 4
4 сдано не менее 4 заданий, оценка за экзамен >= 3
3 сдано не менее 3 заданий, оценка за экзамен >= 3

Лекции

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

Семинары

№ п/п Занятие Материалы
1 Метод градиентного спуска.
5 Нелинейный метод сопряженных градиентов. Предобуславливание Презентация
6 Матричные преобразования в квазиньютоновских методах Конспект
7 Задачи условной оптимизации, теорема ККТ. Видео Конспекты
8 Двойственность, эквивалентные преобразования задач. Видео Конспект
9 Субдифференциальное исчисление Видео Конспект
10 Проекции и проксимальные операторы Видео
11 Сопряжённые функции и нормы Видео Конспект
12 Решение задач дискретной оптимизации непрерывными методами Видео Презентация

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

  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.

Архив

2018 год

2017 год

2016 год

2015 год

2014 год

2012 год

См. также

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

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

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

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

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