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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: __NOTOC__ Настройка модели алгоритмов по данным — это задача оптимизации, от эффективности решения котор...)
(→Практические задания)
(41 промежуточная версия не показана)
Строка 4: Строка 4:
'''Лектор''': [[Участник:Kropotov|Д.А. Кропотов]]<br>
'''Лектор''': [[Участник:Kropotov|Д.А. Кропотов]]<br>
-
'''Семинарист''': А.О. Родоманов
+
'''Семинарист''': А.О. Родоманов<br>
 +
'''Ассистент''': Н.А. Шаповалов
-
Вопросы и комментарии по курсу просьба адресовать письмом на ''bayesml@gmail.com''. В название письма просьба добавлять [ВМК МОМО16].
+
Занятия проходят:
 +
* на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 612, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
 +
* на базовой кафедре [[Интеллектуальные системы (кафедра МФТИ)|Интеллектуальных систем МФТИ]] по средам в [[Вычислительный центр РАН|ВЦ РАН]] в к.355, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
-
Занятия проходят на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 612, лекция с 10-30 до 12-05, семинар с 12-15 до 13-50.
+
Инвайты в AnyTask: UAb78YK для ВМК, YYGCLOZ для Физтеха.
-
== Система выставления оценок по курсу ==
+
Группа в Телеграмме для вопросов по курсу: [https://t.me/joinchat/EYDfykF5ez-V1D39q3zi4Q https://t.me/joinchat/EYDfykF5ez-V1D39q3zi4Q].
-
В рамках курса предполагается четыре практических задания, несколько домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. В итоговой оценке 45% составляют баллы за практические задания, 25% — баллы за домашние задания и 30% — оценка за экзамен. Для получения финального результата (0, 3, 4, 5) итоговая оценка по курсу округляется в большую сторону. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, но суммарно не более 3 баллов.
+
-
[https://docs.google.com/spreadsheets/d/1OZkzt3a1vfLXhK6lSwTXxh8xAayKp7_yaH6bGLQZzro/edit?usp=sharing Таблица с оценками].
+
'''Таблица с результатами находится [https://docs.google.com/spreadsheets/d/1TT7oVqR7hPQEVMJKWRLiOBfdkmj1927sEMPLVlXMeo4/edit?usp=sharing здесь]'''
 +
 
 +
== Система выставления оценок по курсу ==
 +
В рамках курса предполагается четыре практических задания, четыре домашних заданий и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Домашнее задание после срока сдачи не принимается. За каждый день просрочки при сдаче практического задания начисляется штраф 0.1 балла, через две недели после срока сдачи практическое задание не принимается.
-
== Экзамен ==
+
Итоговая оценка за курс является взвешенной суммой оценки за экзамен (вклад 40%), оценки за практические задания (вклад 40%) и оценки за домашние задания (вклад 20%). При этом для получения итоговой оценки 5 (соответственно >= 8 для студентов МФТИ) необходимо сдать на положительный балл все практичекие и все домашние задания, а также набрать на экзамене не ниже 4 баллов (соответственно >= 5 для МФТИ); для получения итоговой оценки 4 (соответственно >= 5 для МФТИ) необходимо сдать любые три практических задания и любые два домашних задания; для получения итоговой оценки 3 (соответственно >= 3 для МФТИ) необходимо сдать любые два практических задания и любое одно домашнее задание.
-
Экзамен по курсу состоится 19 января в ауд. 508, начало в 12-00. На экзамене при подготовке билета можно пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя. Просьба обратить внимание на теоретический минимум. Незнание ответов на вопросы из теор. минимума автоматически влечёт неудовлетворительную оценку за экзамен.
+
-
[[Media:MOMO16_exam_questions.pdf| Вопросы к экзамену]]
+
При выполнении каждого задания можно получить бонусные баллы за необязательные пункты, но при этом итоговые оценки за практическую часть курса и за домашнюю часть курса не могут превысить соответствующих максимальных оценок без учета бонусов. Например, если используется пятибальная шкала и количество (скажем, домашних) заданий равно четырем, то за счет бонусов оценки за задания могут быть следующими: 1) 5.5, 4, 4, 4; или 2) 5.5, 5, 5, 5. В первом случае итоговая оценка за домашние задания составляет 17.5, а во втором --- 20.0.
== Домашние задания ==
== Домашние задания ==
-
* Задание 1. [[Media:MOMO16_home1_problems.pdf|Скорости сходимости и дифференцирование]]. Срок сдачи: '''12 сентября (понедельник), 10:30.'''
+
Задание 1. [[Media:MOMO17_Homework1.pdf‎‎|Скорости сходимости и матрично-векторное дифференцирование]] ([[Media:MOMO17_Homework1.tex.zip‎‎|TeX]]). <br />
-
* Задание 2. [[Media:Momo16_home2_problems.pdf|Задачи условной оптимизации]]. Срок сдачи: '''31 октября (понедельник), 10:30.'''
+
Задание 2. [[Media:MOMO17_Homework2.pdf‎‎|Выпуклые множества и функции]] ([[Media:MOMO17_Homework2.tex.zip‎‎|TeX]]). <br />
-
* Задание 3. [[Media:Momo16_home3_problems.pdf|Субградиенты]]. Срок сдачи: '''14 ноября (понедельник), 10:30.'''
+
Задание 3. [[Media:MOMO17_Homework3.pdf‎‎|Условная оптимизация]] ([[Media:MOMO17_Homework3.tex.zip‎‎|TeX]]). <br />
-
* Задание 4. [[Media:Momo16_home4_problems.pdf|Сопряженные функции и проекции]]. Срок сдачи: '''21 ноября (понедельник), 10:30.'''
+
Задание 4. [[Media:MOMO17_Homework4.pdf‎‎|Субдифференциалы]] ([[Media:MOMO17_Homework4.tex.zip‎‎|TeX]]). <br />
-
* Бонусное задание. [[Media:Momo16_bonus_task.pdf|Проекция на симплекс]]. Срок сдачи: '''5 декабря (понедельник), 23:59.''' Выполняется по желанию.
+
-
<span style="color:red; font-weight: bold">Объявление: Все домашние задания и контрольные проверены. Если у Вас не стоит оценки (или стоит неправильная), сообщите нам об этом по e-mail.</span>
+
[[Media:MOMO17_TeX_StyleFiles.zip‎‎|Стилевые файлы TeX]].
== Практические задания ==
== Практические задания ==
-
* Задание 1. ([[Media:Momo16_ass1_v1.zip|Вариант 1]]) ([[Media:Momo16_ass1_v2.zip|Вариант 2]]). Срок сдачи: <b>28 сентября (среда), 23:59</b>. Вариант для выполнения выбирается самостоятельно.
+
Задание 1. [[Media:MOMO17_Practice1.pdf‎‎|Методы градиентного спуска и Ньютона]] ([[Media:MOMO17_Practice1.tex.zip‎‎|TeX]]). <br />
-
* [[Media:Momo16_ass2.zip|Задание 2]]. Срок сдачи: <b>19 октября (среда), 23:59</b>.
+
Задание 2. [[Media:MOMO17_Practice2.pdf‎‎|Продвинутые методы безусловной оптимизации]] ([[Media:MOMO17_Practice2.tex.zip‎‎|TeX]]). <br />
-
* [[Media:Momo16_ass3.zip|Задание 3]]. Срок сдачи: <b>30 ноября (среда), 23:59</b>.
+
Задание 3. [[Media:MOMO17_Practice3.pdf‎‎|Метод барьеров]] ([[Media:MOMO17_Practice3.tex.zip‎‎|TeX]]). <br />
-
* [[Media:Momo16_ass4.zip|Задание 4]]. Срок сдачи: <b>28 декабря (среда), 23:59</b>.
+
Задание 4. [[Media:MOMO17_Practice4.pdf‎‎|Композитная оптимизация]] ([[Media:MOMO17_Practice4.tex.zip‎‎|TeX]]).
-
== Расписание ==
+
== Лекции ==
{| class = "standard"
{| class = "standard"
|+
|+
-
! width="10%" | Дата
+
! width="5%" | № п/п
! width="60%" | Занятие
! width="60%" | Занятие
-
! width="30%" | Материалы
+
! width="35%" | Материалы
|-
|-
-
| 5&nbsp;сентября&nbsp;2016
+
| 1
-
| Введение в курс. Скорости сходимости и дифференцирование || <b>(Скорости сходимости)</b> [Nocedal-Wright, pp. 617-620] <br /> <b>(Дифференцирование)</b> [Ben-Tal-Nemirovski, Section A.6]
+
| Введение в курс. Классы функций в оптимизации. Скорости сходимости || <b>(Скорости сходимости)</b> [Nocedal-Wright, pp. 617-620]
|-
|-
-
| 12&nbsp;сентября&nbsp;2016
+
| 2
-
| Методы одномерной оптимизации. Неточная одномерная оптимизация || <b>(Одномерная оптимизация)</b> [[Media:MOMO16_min1d.pdf|Текст]] <br /> <b>(Неточная одномерная оптимизация)</b> [Nocedal-Wright, pp. 30-37] + [Ben-Tal-Nemirovski, pp. 164-166]
+
| Неточная одномерная оптимизация. Метод градиентного спуска, выбор длины шага. || [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5]
|-
|-
-
| 19&nbsp;сентября&nbsp;2016
+
| 3
-
| Базовые методы многомерной оптимизации || [Nocedal-Wright, Chapter 3] + [Поляк, Разделы 1.4 и 1.5]
+
| Метод Ньютона. Способы коррекции гессиана до положительно-определённой матрицы ||
|-
|-
-
| 26&nbsp;сентября&nbsp;2016
+
| 4
-
| Методы сопряженных градиентов || [[Media:Momo16_Sem4_presentation_final.pdf|Презентация]] + [Nocedal-Wright, Chapter 5]
+
| Метод сопряженных градиентов ||
|-
|-
-
| 3&nbsp;октября&nbsp;2016
+
| 5
-
| Неточный метод Ньютона. Автоматическое дифференцирование || <b>(Неточный метод Ньютона)</b> [Nocedal-Wright, pp. 184-189] <br /> <b>(Автоматическое дифференцирование)</b> [Nocedal-Wright, Section 8.2]
+
| Неточный/безгессианный метод Ньютона ||
|-
|-
-
| 10&nbsp;октября&nbsp;2016
+
| 6
-
| Квазиньютоновские методы. Метод L-BFGS || <b>(Квазиньютоновские методы)</b> [Nocedal-Wright, Section 6] <br /> <b>(Метод L-BFGS)</b> [Nocedal-Wright, pp. 176-180]
+
| Квазиньютоновские методы. Метод L-BFGS ||
|-
|-
-
| 17&nbsp;октября&nbsp;2016
+
| 7
-
| Задачи условной оптимизации: теория. || [Поляк, Глава 9] + [Boyd-Vandenberghe, Sections 4 and 5]
+
| Задачи условной оптимизации: теория. ||
|-
|-
-
| 24&nbsp;октября&nbsp;2016
+
| 8
-
| Метод Ньютона для задач с ограничениями вида равенств, метод барьеров || [Boyd-Vandenberghe, pp. 521-531, 561-571]
+
| Метод внутренней точки ||
|-
|-
-
| 31&nbsp;октября&nbsp;2016
+
| 9
-
| Прямо-двойственный метод внутренней точки || [Boyd-Vandenberghe, pp. 609-615]
+
| Прямо-двойственный метод внутренней точки ||
|-
|-
-
| 7&nbsp;ноября&nbsp;2016
+
| 10
-
| Негладкая безусловная оптимизация. Субградиентный метод || [Поляк, Разделы 5.1-5.3] + [Nesterov, Sections 3.1-3.2.3]
+
| Негладкая оптимизация. Субградиентный метод ||
|-
|-
-
| 14&nbsp;ноября&nbsp;2016
+
| 11
-
| Проксимальный градиентный метод. Сопряженные функции по Фенхелю || <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 Слайды]
+
| Разреженные линейный модели. Проксимальные методы. ||
|-
|-
-
| 21&nbsp;ноября&nbsp;2016
+
| 12
-
| Суррогатная оптимизация || [[Media:MOMO12_upper_bounds.pdf|Текст]]
+
| Быстрый градиентный метод Нестерова ||
|-
|-
-
| 28&nbsp;ноября&nbsp;2016
+
| 13
-
| Рандомизированные методы оптимизации: 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]
+
| Стохастическая оптимизация ||
|-
|-
-
| 5&nbsp;декабря&nbsp;2016
+
| 14
-
| Быстрый градиентный метод Нестерова || [http://premolab.ru/e_files/e7/2zmgs9dvnJ.pdf Нестеров, 2013 (Разделы 1.2.2 и 2.3.4)] + [[Media:Rodomanov_FGM.pdf|Текст]]
+
| Продвинутая стохастическая оптимизация ||
|-
|-
-
| 12&nbsp;декабря&nbsp;2016
+
|}
-
| Доклады студентов ||
+
 
 +
== Семинары ==
 +
{| class = "standard"
 +
|+
 +
! width="5%" | № п/п
 +
! width="70%" | Занятие
 +
! width="25%" | Материалы
|-
|-
-
| 19&nbsp;декабря&nbsp;2016
+
| 1
-
| Переписывание контрольных работ и разбор практических заданий ||
+
| Скорости сходимости. Матрично-векторные скалярные произведения и нормы || [[Media:MOMO17_Seminar1.pdf|Конспект]]
 +
|-
 +
| 2
 +
| Матрично-векторное дифференцирование || [[Media:MOMO17_Seminar2.pdf|Конспект]]
 +
|-
 +
| 3
 +
| Методы градиентного спуска и Ньютона. Детали реализации и примеры работы || [[Media:MOMO17_Seminar3_handout.pdf|Презентация]]
 +
|-
 +
| 4
 +
| Выпуклые множества и функции || [[Media:MOMO17_Seminar4.pdf|Конспект]]
 +
|-
 +
| 5
 +
| Самосогласованные функции и метод Ньютона ||
 +
|-
 +
| 6
 +
| Квазиньютоновские методы || [[Media:MOMO17_Seminar6.pdf|Конспект]]
 +
|-
 +
| 7
 +
| Условия Каруша--Куна--Таккера. Эквивалентные преобразования задач || [[Media:MOMO17_Seminar7.pdf|Конспект]]
 +
|-
 +
| 8
 +
| Двойственность || [[Media:MOMO17_Seminar8.pdf|Конспект]]
 +
|-
 +
| 9
 +
| Метод внутренней точки ||
 +
|-
 +
| 10
 +
| Субдифференциальное исчисление ||
 +
|-
 +
| 11
 +
| Вычисление проекций и проксимальных отображений ||
 +
|-
 +
| 12
 +
| Коническое и полуопределенное программирование ||
 +
|-
 +
| 13
 +
| Техника сглажвания ||
 +
|-
 +
| 14
 +
| Адаптивные длины шагов в стохастическом градиентном методе. Метод AdaGrad ||
|-
|-
|}
|}
-
 
-
== Программа курса ==
 
-
 
-
=== Основные понятия и примеры задач ===
 
-
 
-
* Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
 
-
* Матричные разложения, их использование для решения СЛАУ;
 
-
* Структура итерационного процесса в оптимизации, понятие оракула, критерии останова;
 
-
* Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации.
 
-
 
-
=== Методы одномерной оптимизации ===
 
-
 
-
* Минимизация функции без производной: метод золотого сечения, метод парабол;
 
-
* Гибридный метод минимизации Брента;
 
-
* Методы решения уравнения <tex>f^\prime(x)=0</tex>: метод деления отрезка пополам, метод секущей;
 
-
* Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
 
-
* Поиск ограничивающего сегмента;
 
-
* Условия Армихо и Вольфа для неточного решения задачи одномерной оптимизации;
 
-
* Неточные методы одномерной оптимизации, backtracking.
 
-
 
-
=== Методы многомерной оптимизации ===
 
-
 
-
* Методы линейного поиска и доверительной области;
 
-
* Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков;
 
-
* Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы;
 
-
* Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание;
 
-
* Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации;
 
-
* Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента;
 
-
* Квазиньютоновские методы оптимизации: SR1, BFGS и L-BFGS.
 
-
 
-
=== Методы внутренней точки ===
 
-
 
-
* Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера;
 
-
* Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации;
 
-
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
 
-
* Прямо-двойственный метод Ньютона, неточный вариант метода;
 
-
* Метод логарифмических барьерных функций;
 
-
* Прямо-двойственный метод внутренней точки;
 
-
* Методы первой фазы.
 
-
 
-
=== Разреженные методы машинного обучения ===
 
-
 
-
* Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
 
-
* Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации;
 
-
* Метод наискорейшего субградиентного спуска;
 
-
* Проксимальный метод, вычисление prox-оператора для L1- и L1/L2-регуляризаторов.
 
-
 
-
=== Стохастическая оптимизация ===
 
-
 
-
* Задачи минимизации среднего и эмпирического риска;
 
-
* Метод стохастического градиентного спуска, две фазы итерационного процесса, использование инерции;
 
-
* Метод SAG;
 
-
* Комбинирование стохастической оптимизации и проксимального метода.
 
-
 
-
=== Суррогатная оптимизация ===
 
-
 
-
* Вероятностная модель логистической регрессии;
 
-
* Общая идея метода суррогатной оптимизации;
 
-
* Применение метода для стохастической оптимизации: метод MISO;
 
-
* Пример применения метода для обучения LASSO;
 
-
* Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностной модели логистической регрессии;
 
-
* Построение оценок с помощью касательных и замены переменной;
 
-
* Оценка Jaakkola-Jordan для логистической функции, её применение для обучения вероятностной модели логистической регрессии;
 
-
* Выпукло-вогнутая процедура, примеры использования.
 
-
 
-
=== Методы оптимизации для глубинного обучения ===
 
-
 
-
* Адаптивная стратегия Левенберга-Марквардта для задачи минимизации суммы квадратов;
 
-
* Модель глубинного автокодировщика;
 
-
* Алгоритм обратного распространения ошибки и его обобщения для быстрого умножения гессиана на произвольный вектор;
 
-
* Неточный метод Ньютона с предобуславливанием через L-BFGS.
 
== Литература ==
== Литература ==
Строка 167: Строка 144:
# 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://premolab.ru/sites/default/files/polyak-optimizationintro.djvu Введение в оптимизацию], Наука, 1983.
+
# Б. Поляк. [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.
# 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.

Версия 17:20, 23 ноября 2017

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

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

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

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

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

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

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

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

Итоговая оценка за курс является взвешенной суммой оценки за экзамен (вклад 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 год

См. также

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

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

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

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

Источник — «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_%D0%B2_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%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/2017»
Личные инструменты