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

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

(Различия между версиями)
Перейти к: навигация, поиск
 
(35 промежуточных версий не показаны.)
Строка 8: Строка 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 Таблица с оценками]
 +
 +
[[Media:MO17_Exam_Questions_.pdf‎|'''Вопросы к коллоквиуму''']]
== Система выставления оценок по курсу в 3-м модуле ==
== Система выставления оценок по курсу в 3-м модуле ==
-
# В рамках курса предполагается три практических задания, четыре домашних заданий и экзамен. Каждое задание и экзамен оцениваются по десятибалльной шкале.
+
# В рамках курса в 3-м модуле (непрерывная оптимизация) предполагается три практических задания, четыре домашних заданий и коллоквиум. Каждое задание и коллоквиум оцениваются по десятибалльной шкале.
-
# В итоговой оценке 50% составляют баллы за домашние задания и 50% – баллы за практические задания. Для получения финального результата (0, 4–10) итоговая оценка по курсу округляется в большую сторону.
+
# В оценке за модуль 50% составляют баллы за домашние задания и 50% – баллы за практические задания. Для получения финального результата (0–10) оценка округляется в большую сторону.
-
# Сдача экзамена является необязательной и позволяет получить до 2 дополнительных баллов в итоговую оценку.
+
# Сдача коллоквиума является необязательной и позволяет получить до 2 дополнительных баллов в оценку за модуль (оценка за коллоквиум берётся с весом 0.2).
-
# Для получения итоговой оценки >= 8 баллов необходимо сдать все домашние и практические задания на положительный балл, для получения итоговой оценки >= 6 баллов необходимо сдать не менее двух практических и трех домашних заданий, для получения итоговой оценки >= 4 баллов необходимо сдать не менее одного практического и двух домашних заданий.
+
# Оценка за модуль не может быть больше, чем 10 баллов.
== Формирование итоговой оценки по курсу по итогам 3-го и 4-го модулей ==
== Формирование итоговой оценки по курсу по итогам 3-го и 4-го модулей ==
-
# За каждый из двух модулей выставляется независимая оценка в шкале 0, 4-10.
+
# За 3-й модуль выставляется оценка «Накопленная_непрерывная» как описано выше.
-
# Итоговая оценка по курсу вычисляется как среднее арифметическое двух оценок за каждый из модулей с дальнейшим округлением к ближайшему целому (.5 округляется к единице).
+
# За 4-й модуль выставляется оценка «Накопленная_дискретная» и проводится экзамен. На экзамене будет спрашиваться только материал 4-го модуля (дискретная оптимизация).
-
# Если по одному из модулей оценка 0 баллов, то итоговая оценка за курс – также 0 баллов.
+
# Итоговая оценка по курсу вычисляется по формуле:
 +
#* «Накопленная_итоговая» = 0.625 * «Накопленная_непрерывная» + 0.375 * «Накопленная_дискретная»
 +
#* «Итоговая_оценка» = 0.8 * «Накопленная_итоговая» + 0.2 * «Экзамен»
 +
# При вычислении итоговой оценки проводится округление к ближайшему целому (.5 округляется к единице)
 +
--------------------------------
== Правила сдачи заданий ==
== Правила сдачи заданий ==
-
В рамках курса предполагается сдача нескольких домашних и практических заданий. Домашнее задание сдаётся к началу очередного семинара на листочках или (по согласованию с семинаристом) по почте в виде скана или pdf-файла. Домашние задания после срока сдачи не принимаются. Практические задания сдаются по почте. Эти задания могут быть присланы после срока сдачи, при этом начисляется штраф из расчёта 0.2 балла в день, но суммарно не более 6 баллов. При сдаче задания позже срока его проверка гарантируется только в случае, если оно было прислано не позже одной недели до официального окончания сессии.
+
В рамках курса предполагается сдача нескольких домашних и практических заданий. Домашнее задание сдаётся к началу очередного семинара на листочках или (по согласованию с семинаристом) по почте в виде скана или pdf-файла. Домашние задания после срока сдачи не принимаются. Практические задания сдаются по почте. Эти задания могут быть присланы после срока сдачи, при этом начисляется штраф из расчёта 0.2 балла в день, но суммарно не более 6 баллов.
Все домашние и практические задания выполняются самостоятельно. Если задание выполнялось сообща или использовались какие-либо сторонние коды и материалы, то об этом должно быть написано в отчёте. В противном случае «похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) будут сурово наказаны.
Все домашние и практические задания выполняются самостоятельно. Если задание выполнялось сообща или использовались какие-либо сторонние коды и материалы, то об этом должно быть написано в отчёте. В противном случае «похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) будут сурово наказаны.
Строка 99: Строка 107:
| 10 января 2017
| 10 января 2017
| Скорости сходимости. Матричные вычисления. || [[Media:MO17_seminar1.pdf|Конспект]]
| Скорости сходимости. Матричные вычисления. || [[Media:MO17_seminar1.pdf|Конспект]]
 +
|-
 +
| align="center"|2
 +
| 17 января 2017
 +
| Производные и условия оптимальности. Теория || [[Media:MO17_seminar2.pdf|Конспект]]
 +
|-
 +
| align="center"|3
 +
| 24 января 2017
 +
| Производные и условия оптимальности. Решение задач || [[Media:MO17_seminar3.pdf|Конспект]]
 +
|-
 +
| align="center"|4
 +
| 31 января 2017
 +
| Методы градиентного спуска и Ньютона || [[Media:MO17_seminar4.pdf|Конспект]]
 +
|-
 +
| align="center"|5
 +
| 7 февраля 2017
 +
| Методы градиентного спуска, Ньютона и сопряженных градиентов. Подготовка к практическому заданию 1 || [[Media:MO17_seminar5.pdf|Презентация]]
 +
|-
 +
| align="center"|6
 +
| 14 февраля 2017
 +
| Выпуклые множества и функции || [[Media:MO17_seminar6.pdf|Конспект]]
 +
|-
 +
| align="center"|7
 +
| 21 февраля 2017
 +
| Усеченный метод Ньютона. Квазиньютоновские методы || [[Media:MO17_seminar7.pdf|Конспект]]
 +
|-
 +
|-
 +
| align="center"|8
 +
| 28 февраля 2017
 +
| Условная оптимизация. Условия ККТ. Эквивалентные преобразования задач. || [[Media:MO17_seminar8.pdf|Конспект]]
 +
|-
 +
|-
 +
| align="center"|9
 +
| 7 марта 2017
 +
| Стандартные классы выпуклых задач и двойственность. || [[Media:MO17_seminar9.pdf|Конспект]]
 +
|-
 +
|-
 +
| align="center"|10
 +
| 14 марта 2017
 +
| Методы внутренней точки. || -
 +
|-
 +
|-
 +
| align="center"|11
 +
| 21 марта 2017
 +
| Субградиенты и проксимальные операторы. || -
|-
|-
|}
|}
Строка 104: Строка 156:
== Домашние задания ==
== Домашние задания ==
-
Задание 1. [[Media:MO17_homework1.pdf‎‎|Скорости сходимости и матричные вычисления]]
+
Задание 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)'''.
 +
 
 +
== Практические задания ==
 +
 
 +
Задание 1. [[Media:MO17_practice1.pdf‎‎|Методы градиентного спуска и Ньютона]]. Срок сдачи: '''22 февраля 2017 (23:59)'''.
 +
 
 +
Задание 2. [[Media:MO17_practice2.pdf‎‎| Продвинутые методы безусловной оптимизации]]. Срок сдачи: '''9 марта 2017 (23:59)'''.
-
Срок сдачи: 17 января 2017 (на семинаре).
+
Задание 3. [[Media:MO17_practice3.pdf‎‎| Негладкая и условная оптимизация]]. Срок сдачи: '''7 апреля 2017 (23:59)'''.
== Литература ==
== Литература ==

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

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

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

Лектор: Кропотов Дмитрий Александрович. Лекции проходят по вторникам в ауд. 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.