Методы оптимизации (курс лекций)

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{stop| Страница курса находится в стадии формирования}} __NOTOC__ Настройка модели алгоритмов по данным — э...)
 
(44 промежуточные версии не показаны)
Строка 1: Строка 1:
-
{{stop| Страница курса находится в стадии формирования}}
 
-
 
__NOTOC__
__NOTOC__
-
Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения которой зависит практическая применимость метода машинного обучения. В эпоху больших данных многие классические алгоритмы оптимизации становятся неприменимы, т.к. здесь требуется решать задачи оптимизации функций за время меньшее, чем необходимо для вычисления значения функции в одной точке. Таким требованиям можно удовлетворить в случае грамотного комбинирования известных подходов в оптимизации с учётом конкретной специфики решаемой задачи. Курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Наличие у слушателей каких-либо предварительных знаний по оптимизации не предполагается, все необходимые понятия разбираются в ходе занятий. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
+
Методы оптимизации лежат в основе решения многих задач компьютерных наук. Например, в машинном обучении задачу оптимизации необходимо решать каждый раз при настройке какой-то модели алгоритмов по данным. Причём от эффективности решения соответствующей задачи оптимизации зависит практическая применимость самого метода машинного обучения. Данный курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклой), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
-
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
+
Занятия проходят на ФКН ВШЭ.
Занятия проходят на ФКН ВШЭ.
Строка 11: Строка 8:
'''Семинаристы''':
'''Семинаристы''':
{| class="standard"
{| class="standard"
-
! Группа !! Семинарист !! Расписание
+
! Группа !! Семинарист !! Расписание !! Почта для ДЗ
|-
|-
-
| 141 (МОП) || Родоманов Антон Олегович || вторник, 15:10 – 16:30, ауд. 513
+
| 141 (МОП) || Родоманов Антон Олегович || вторник, 15:10 – 16:30, ауд. 513 || opt.homework+141@gmail.com
|-
|-
-
| 142 (МОП) || Хальман Михаил Анатольевич || вторник, 15:10 – 16:30, ауд. 501
+
| 142 (МОП) || Хальман Михаил Анатольевич || вторник, 15:10 – 16:30, ауд. 501 || opt.homework+142@gmail.com
|-
|-
-
| 145 (РС) || Дойков Никита Владимирович || вторник, 15:10 – 16:30, ауд. 503
+
| 145 (РС) || Дойков Никита Владимирович || вторник, 15:10 – 16:30, ауд. 503 || opt.homework+145@gmail.com
|-
|-
|}
|}
-
== Система выставления оценок по курсу ==
+
[https://docs.google.com/spreadsheets/d/10ThdXos3CHqErNLCGKr05GC6ndCiBrJFNb9VQFjfbls/edit?usp=sharing Таблица с оценками]
-
В рамках курса предполагается четыре практических задания, несколько домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. В итоговой оценке 45% составляют баллы за практические задания, 25% — баллы за домашние задания и 30% — оценка за экзамен. Для получения финального результата (0, 3, 4, 5) итоговая оценка по курсу округляется в большую сторону. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, но суммарно не более 3 баллов.
+
 +
[[Media:MO17_Exam_Questions_.pdf‎|'''Вопросы к коллоквиуму''']]
 +
== Система выставления оценок по курсу в 3-м модуле ==
 +
# В рамках курса в 3-м модуле (непрерывная оптимизация) предполагается три практических задания, четыре домашних заданий и коллоквиум. Каждое задание и коллоквиум оцениваются по десятибалльной шкале.
 +
# В оценке за модуль 50% составляют баллы за домашние задания и 50% – баллы за практические задания. Для получения финального результата (0–10) оценка округляется в большую сторону.
 +
# Сдача коллоквиума является необязательной и позволяет получить до 2 дополнительных баллов в оценку за модуль (оценка за коллоквиум берётся с весом 0.2).
 +
# Оценка за модуль не может быть больше, чем 10 баллов.
 +
 +
== Формирование итоговой оценки по курсу по итогам 3-го и 4-го модулей ==
 +
# За 3-й модуль выставляется оценка «Накопленная_непрерывная» как описано выше.
 +
# За 4-й модуль выставляется оценка «Накопленная_дискретная» и проводится экзамен. На экзамене будет спрашиваться только материал 4-го модуля (дискретная оптимизация).
 +
# Итоговая оценка по курсу вычисляется по формуле:
 +
#* «Накопленная_итоговая» = 0.625 * «Накопленная_непрерывная» + 0.375 * «Накопленная_дискретная»
 +
#* «Итоговая_оценка» = 0.8 * «Накопленная_итоговая» + 0.2 * «Экзамен»
 +
# При вычислении итоговой оценки проводится округление к ближайшему целому (.5 округляется к единице)
 +
--------------------------------
 +
 +
== Правила сдачи заданий ==
 +
В рамках курса предполагается сдача нескольких домашних и практических заданий. Домашнее задание сдаётся к началу очередного семинара на листочках или (по согласованию с семинаристом) по почте в виде скана или pdf-файла. Домашние задания после срока сдачи не принимаются. Практические задания сдаются по почте. Эти задания могут быть присланы после срока сдачи, при этом начисляется штраф из расчёта 0.2 балла в день, но суммарно не более 6 баллов.
 +
 +
Все домашние и практические задания выполняются самостоятельно. Если задание выполнялось сообща или использовались какие-либо сторонние коды и материалы, то об этом должно быть написано в отчёте. В противном случае «похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) будут сурово наказаны.
== Лекции ==
== Лекции ==
{| class = "standard"
{| class = "standard"
|+
|+
-
! width="5%" | № п/п
+
! № п/п
-
! width="10%" | Дата
+
! Дата
-
! width="55%" | Занятие
+
! Занятие
-
! width="30%" | Материалы
+
! Материалы
|-
|-
-
| 1
+
| align="center"|1
-
| 5 сентября 2016
+
| 10 января 2017
-
| Введение в курс. Скорости сходимости и дифференцирование || <b>(Скорости сходимости)</b> [Nocedal-Wright, pp. 617-620] <br /> <b>(Дифференцирование)</b> [Ben-Tal-Nemirovski, Section A.6]
+
| Введение в курс. Необходимое условие экстремума. Оракулы, скорости сходимости итерационных процессов. ||
|-
|-
-
| 2
+
| align="center"|2
-
| 12&nbsp;сентября&nbsp;2016
+
| 17&nbsp;января&nbsp;2017
-
| Методы одномерной оптимизации. Неточная одномерная оптимизация || <b>(Одномерная оптимизация)</b> [[Media:MOMO16_min1d.pdf|Текст]] <br /> <b>(Неточная одномерная оптимизация)</b> [Nocedal-Wright, pp. 30-37] + [Ben-Tal-Nemirovski, pp. 164-166]
+
| Точная одномерная оптимизация. ||
|-
|-
-
| 3
+
| align="center"|3
-
| 19&nbsp;сентября&nbsp;2016
+
| 24&nbsp;января&nbsp;2017
-
| Базовые методы многомерной оптимизации || [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5]
+
| Неточная одномерная оптимизация. Классы функций для оптимизации. Метод градиентного спуска. ||
|-
|-
-
| 4
+
| align="center"|4
-
| 26&nbsp;сентября&nbsp;2016
+
| 31&nbsp;января&nbsp;2017
-
| Методы сопряженных градиентов || [[Media:Momo16_Sem4_presentation_final.pdf|Презентация]] + [Nocedal-Wright, Chapter 5]
+
| Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач. ||
|-
|-
-
| 5
+
| align="center"|5
-
| 3&nbsp;октября&nbsp;2016
+
| 7&nbsp;февраля&nbsp;2017
-
| Неточный метод Ньютона. Автоматическое дифференцирование || <b>(Неточный метод Ньютона)</b> [Nocedal-Wright, pp. 184-189] <br /> <b>(Автоматическое дифференцирование)</b> [Nocedal-Wright, Section 8.2]
+
| Линейный метод сопряжённых градиентов. ||
|-
|-
-
| 6
+
| align="center"|6
-
| 10&nbsp;октября&nbsp;2016
+
| 14&nbsp;февраля&nbsp;2017
-
| Квазиньютоновские методы. Метод L-BFGS || <b>(Квазиньютоновские методы)</b> [Nocedal-Wright, Section 6] <br /> <b>(Метод L-BFGS)</b> [Nocedal-Wright, pp. 176-180]
+
| Неточный метод Ньютона. Разностные производные. ||
|-
|-
-
| 7
+
| align="center"|7
-
| 17&nbsp;октября&nbsp;2016
+
| 21&nbsp;февраля&nbsp;2017
-
| Задачи условной оптимизации: теория. || [Поляк, Глава 9] + [Boyd-Vandenberghe, Sections 4 and 5]
+
| Квазиньютоновские методы. Метод L-BFGS. ||
|-
|-
-
| 8
+
| align="center"|8
-
| 24&nbsp;октября&nbsp;2016
+
| 28&nbsp;февраля&nbsp;2017
-
| Метод Ньютона для задач с ограничениями вида равенств, метод барьеров || [Boyd-Vandenberghe, pp. 521-531, 561-571]
+
| Задачи условной оптимизации: условия ККТ. ||
|-
|-
-
| 9
+
| align="center"|9
-
| 31&nbsp;октября&nbsp;2016
+
| 7&nbsp;марта&nbsp;2017
-
| Прямо-двойственный метод внутренней точки || [Boyd-Vandenberghe, pp. 609-615]
+
| Выпуклые задачи оптимизации. Двойственность. Метод барьеров. ||
|-
|-
-
| 10
+
| align="center"|10
-
| 7&nbsp;ноября&nbsp;2016
+
| 14&nbsp;марта&nbsp;2017
-
| Негладкая безусловная оптимизация. Субградиентный метод || [Поляк, Разделы 5.1-5.3] + [Nesterov, Sections 3.1-3.2.3]
+
| Негладкая безусловная оптимизация. Субградиентный метод. Проксимальные методы. ||
|-
|-
-
| 11
+
| align="center"|11
-
| 14&nbsp;ноября&nbsp;2016
+
| 21&nbsp;марта&nbsp;2017
-
| Проксимальный градиентный метод. Сопряженные функции по Фенхелю || <b>(Проксимальный градиентный метод)</b> [http://www.seas.ucla.edu/~vandenbe/236C/lectures/proxgrad.pdf Слайды] <br /> <b>(Сопряженные функции)</b> [Boyd-Vandenberghe, Section 3.3] + [http://www.seas.ucla.edu/~vandenbe/236C/lectures/conj.pdf Слайды]
+
| Стохастическая оптимизация. ||
|-
|-
-
| 12
+
|}
-
| 21&nbsp;ноября&nbsp;2016
+
 
-
| Суррогатная оптимизация || [[Media:MOMO12_upper_bounds.pdf|Текст]]
+
== Семинары ==
 +
{| class = "standard"
 +
|+
 +
! № п/п
 +
! Дата
 +
! Занятие
 +
! Материалы
 +
|-
 +
| align="center"|1
 +
| 10&nbsp;января&nbsp;2017
 +
| Скорости сходимости. Матричные вычисления. || [[Media:MO17_seminar1.pdf|Конспект]]
 +
|-
 +
| align="center"|2
 +
| 17&nbsp;января&nbsp;2017
 +
| Производные и условия оптимальности. Теория || [[Media:MO17_seminar2.pdf|Конспект]]
 +
|-
 +
| align="center"|3
 +
| 24&nbsp;января&nbsp;2017
 +
| Производные и условия оптимальности. Решение задач || [[Media:MO17_seminar3.pdf|Конспект]]
 +
|-
 +
| align="center"|4
 +
| 31&nbsp;января&nbsp;2017
 +
| Методы градиентного спуска и Ньютона || [[Media:MO17_seminar4.pdf|Конспект]]
 +
|-
 +
| align="center"|5
 +
| 7&nbsp;февраля&nbsp;2017
 +
| Методы градиентного спуска, Ньютона и сопряженных градиентов. Подготовка к практическому заданию 1 || [[Media:MO17_seminar5.pdf|Презентация]]
 +
|-
 +
| align="center"|6
 +
| 14&nbsp;февраля&nbsp;2017
 +
| Выпуклые множества и функции || [[Media:MO17_seminar6.pdf|Конспект]]
 +
|-
 +
| align="center"|7
 +
| 21&nbsp;февраля&nbsp;2017
 +
| Усеченный метод Ньютона. Квазиньютоновские методы || [[Media:MO17_seminar7.pdf|Конспект]]
 +
|-
 +
|-
 +
| align="center"|8
 +
| 28&nbsp;февраля&nbsp;2017
 +
| Условная оптимизация. Условия ККТ. Эквивалентные преобразования задач. || [[Media:MO17_seminar8.pdf|Конспект]]
 +
|-
 +
|-
 +
| align="center"|9
 +
| 7&nbsp;марта&nbsp;2017
 +
| Стандартные классы выпуклых задач и двойственность. || [[Media:MO17_seminar9.pdf|Конспект]]
|-
|-
-
| 13
 
-
| 28&nbsp;ноября&nbsp;2016
 
-
| Рандомизированные методы оптимизации: SGD, SAG, SVRG и RCDM || <b>(SGD)</b> [http://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf Nemirovski (Sections 14.0-14.1)] <br /> <b>(SAG)</b> [https://arxiv.org/pdf/1309.2388v2.pdf Schmidt et al., 2015] <br /> <b>(SVRG)</b> [https://papers.nips.cc/paper/4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.pdf Johnson-Zhang, 2013] + [https://github.com/bayesgroup/team/blob/master/rodomanov/talks/Rodomanov_OptimizationForBigSums_Skoltech_2016.pdf Презентация] <br /> <b>(RCDM)</b> [http://www1.se.cuhk.edu.hk/~sqma/SEEM5121_Spring2015/Nesterov-CD-2012.pdf Nesterov, 2010]
 
|-
|-
-
| 14
+
| align="center"|10
-
| 5&nbsp;декабря&nbsp;2016
+
| 14&nbsp;марта&nbsp;2017
-
| Быстрый градиентный метод Нестерова || [http://premolab.ru/e_files/e7/2zmgs9dvnJ.pdf Нестеров, 2013 (Разделы 1.2.2 и 2.3.4)] + [[Media:Rodomanov_FGM.pdf|Текст]]
+
| Методы внутренней точки. || -
|-
|-
-
| 15
 
-
| 12&nbsp;декабря&nbsp;2016
 
-
| Доклады студентов ||
 
|-
|-
-
| 16
+
| align="center"|11
-
| 19&nbsp;декабря&nbsp;2016
+
| 21&nbsp;марта&nbsp;2017
-
| Переписывание контрольных работ и разбор практических заданий ||
+
| Субградиенты и проксимальные операторы. || -
|-
|-
|}
|}
-
== Программа курса ==
+
== Домашние задания ==
-
=== Основные понятия и примеры задач ===
+
Задание 1. [[Media:MO17_homework1_correct.pdf‎‎|Скорости сходимости и матричные вычисления]]. Срок сдачи: '''17 января 2017 (на семинаре)'''.
-
* Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
+
Задание 2. [[Media:MO17_homework2.pdf‎‎|Производные и условия оптимальности]]. Срок сдачи: '''31 января 2017 (на семинаре)'''.
-
* Матричные разложения, их использование для решения СЛАУ;
+
-
* Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
+
-
* Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации.
+
-
=== Методы одномерной оптимизации ===
+
Задание 3. [[Media:MO17_homework3.pdf‎‎|Выпуклые множества и функции]]. Срок сдачи: '''22 февраля 2017 (23:59)'''.
-
* Минимизация функции без производной: метод золотого сечения, метод парабол;
+
Задание 4. [[Media:MO17_homework4.pdf‎‎|Условная оптимизация]]. Срок сдачи: '''22 марта 2017 (23:59)'''.
-
* Гибридный метод минимизации Брента;
+
-
* Методы решения уравнения <tex>f^\prime(x)=0</tex>: метод деления отрезка пополам, метод секущей;
+
-
* Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
+
-
* Поиск ограничивающего сегмента;
+
-
* Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации;
+
-
* Неточные методы одномерной оптимизации, backtracking.
+
-
=== Методы многомерной оптимизации ===
+
== Практические задания ==
-
* Методы линейного поиска и доверительной области;
+
Задание 1. [[Media:MO17_practice1.pdf‎‎|Методы градиентного спуска и Ньютона]]. Срок сдачи: '''22 февраля 2017 (23:59)'''.
-
* Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
+
-
* Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
+
-
* Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
+
-
* Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
+
-
* Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
+
-
* Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS.
+
-
=== Методы внутренней точки ===
+
Задание 2. [[Media:MO17_practice2.pdf‎‎| Продвинутые методы безусловной оптимизации]]. Срок сдачи: '''9 марта 2017 (23:59)'''.
-
* Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера;
+
Задание 3. [[Media:MO17_practice3.pdf‎‎| Негладкая и условная оптимизация]]. Срок сдачи: '''7 апреля 2017 (23:59)'''.
-
* Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
+
-
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
+
-
* Прямо-двойственный метод Ньютона, неточный вариант метода;
+
-
* Метод логарифмических барьерных функций;
+
-
* Прямо-двойственный метод внутренней точки;
+
-
* Методы первой фазы.
+
-
 
+
-
=== Разреженные методы машинного обучения ===
+
-
 
+
-
* Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
+
-
* Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
+
-
* Метод наискорейшего субградиентного спуска;
+
-
* Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов.
+
-
 
+
-
=== Стохастическая оптимизация ===
+
-
 
+
-
* Задачи минимизации среднего и эмпирического риска;
+
-
* Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции;
+
-
* Метод SAG;
+
-
* Комбинирование стохастической оптимизации и проксимального метода.
+
-
 
+
-
=== Суррогатная оптимизация ===
+
-
 
+
-
* Вероятностная модель логистической регрессии;
+
-
* Общая идея метода суррогатной оптимизации;
+
-
* Применение метода для стохастической оптимизации: метод MISO;
+
-
* Пример применения метода для обучения LASSO;
+
-
* Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии;
+
-
* Построение оценок с помощью касательных и замены переменной;
+
-
* Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии;
+
-
* Выпукло-вогнутая процедура, примеры использования.
+
-
 
+
-
=== Методы оптимизации для глубинного обучения ===
+
-
 
+
-
* Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов;
+
-
* Модель глубинного автокодировщика;
+
-
* Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
+
-
* Неточный метод Ньютона с предобуславливанием через L-BFGS.
+
== Литература ==
== Литература ==
 +
# J. Nocedal, S. Wright. [http://libgen.io/book/index.php?md5=7016B74CFE6DC64C75864322EE4AA081 Numerical Optimization], Springer, 2006.
 +
# S. Boyd, L. Vandenberghe. [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization], Cambridge University Press, 2004.
# S. Sra et al.. [http://libgen.io/book/index.php?md5=9799B67D2A9C45DCAC9D323252054DAF Optimization for Machine Learning], MIT Press, 2011.
# 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.
 
# 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://premolab.ru/sites/default/files/polyak-optimizationintro.djvu Введение в оптимизацию], Наука, 1983.
# Б. Поляк. [http://premolab.ru/sites/default/files/polyak-optimizationintro.djvu Введение в оптимизацию], Наука, 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.
# R. Fletcher. [http://libgen.io/book/index.php?md5=CAFE400511F96424029AB1DCDB1E39F7 Practical Methods of Optimization], Wiley, 2000.

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

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

Занятия проходят на ФКН ВШЭ.

Лектор: Кропотов Дмитрий Александрович. Лекции проходят по вторникам в ауд. 622 с 13:40 до 15:00.

Семинаристы:

Группа Семинарист Расписание Почта для ДЗ
141 (МОП) Родоманов Антон Олегович вторник, 15:10 – 16:30, ауд. 513 opt.homework+141@gmail.com
142 (МОП) Хальман Михаил Анатольевич вторник, 15:10 – 16:30, ауд. 501 opt.homework+142@gmail.com
145 (РС) Дойков Никита Владимирович вторник, 15:10 – 16:30, ауд. 503 opt.homework+145@gmail.com

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

Вопросы к коллоквиуму

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

  1. В рамках курса в 3-м модуле (непрерывная оптимизация) предполагается три практических задания, четыре домашних заданий и коллоквиум. Каждое задание и коллоквиум оцениваются по десятибалльной шкале.
  2. В оценке за модуль 50% составляют баллы за домашние задания и 50% – баллы за практические задания. Для получения финального результата (0–10) оценка округляется в большую сторону.
  3. Сдача коллоквиума является необязательной и позволяет получить до 2 дополнительных баллов в оценку за модуль (оценка за коллоквиум берётся с весом 0.2).
  4. Оценка за модуль не может быть больше, чем 10 баллов.

Формирование итоговой оценки по курсу по итогам 3-го и 4-го модулей

  1. За 3-й модуль выставляется оценка «Накопленная_непрерывная» как описано выше.
  2. За 4-й модуль выставляется оценка «Накопленная_дискретная» и проводится экзамен. На экзамене будет спрашиваться только материал 4-го модуля (дискретная оптимизация).
  3. Итоговая оценка по курсу вычисляется по формуле:
    • «Накопленная_итоговая» = 0.625 * «Накопленная_непрерывная» + 0.375 * «Накопленная_дискретная»
    • «Итоговая_оценка» = 0.8 * «Накопленная_итоговая» + 0.2 * «Экзамен»
  4. При вычислении итоговой оценки проводится округление к ближайшему целому (.5 округляется к единице)

Правила сдачи заданий

В рамках курса предполагается сдача нескольких домашних и практических заданий. Домашнее задание сдаётся к началу очередного семинара на листочках или (по согласованию с семинаристом) по почте в виде скана или pdf-файла. Домашние задания после срока сдачи не принимаются. Практические задания сдаются по почте. Эти задания могут быть присланы после срока сдачи, при этом начисляется штраф из расчёта 0.2 балла в день, но суммарно не более 6 баллов.

Все домашние и практические задания выполняются самостоятельно. Если задание выполнялось сообща или использовались какие-либо сторонние коды и материалы, то об этом должно быть написано в отчёте. В противном случае «похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) будут сурово наказаны.

Лекции

№ п/п Дата Занятие Материалы
1 10 января 2017 Введение в курс. Необходимое условие экстремума. Оракулы, скорости сходимости итерационных процессов.
2 17 января 2017 Точная одномерная оптимизация.
3 24 января 2017 Неточная одномерная оптимизация. Классы функций для оптимизации. Метод градиентного спуска.
4 31 января 2017 Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач.
5 7 февраля 2017 Линейный метод сопряжённых градиентов.
6 14 февраля 2017 Неточный метод Ньютона. Разностные производные.
7 21 февраля 2017 Квазиньютоновские методы. Метод L-BFGS.
8 28 февраля 2017 Задачи условной оптимизации: условия ККТ.
9 7 марта 2017 Выпуклые задачи оптимизации. Двойственность. Метод барьеров.
10 14 марта 2017 Негладкая безусловная оптимизация. Субградиентный метод. Проксимальные методы.
11 21 марта 2017 Стохастическая оптимизация.

Семинары

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

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

Задание 1. Скорости сходимости и матричные вычисления. Срок сдачи: 17 января 2017 (на семинаре).

Задание 2. Производные и условия оптимальности. Срок сдачи: 31 января 2017 (на семинаре).

Задание 3. Выпуклые множества и функции. Срок сдачи: 22 февраля 2017 (23:59).

Задание 4. Условная оптимизация. Срок сдачи: 22 марта 2017 (23:59).

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

Задание 1. Методы градиентного спуска и Ньютона. Срок сдачи: 22 февраля 2017 (23:59).

Задание 2. Продвинутые методы безусловной оптимизации. Срок сдачи: 9 марта 2017 (23:59).

Задание 3. Негладкая и условная оптимизация. Срок сдачи: 7 апреля 2017 (23:59).

Литература

  1. J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
  2. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
  3. S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.
  4. A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
  5. Б. Поляк. Введение в оптимизацию, Наука, 1983.
  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.
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29»
Личные инструменты