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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Литература)
(начало редактирования страницы 2014 года)
Строка 1: Строка 1:
__NOTOC__
__NOTOC__
 +
 +
{{stop|Страница курса находится в стадии разработки. Архив 2012 года находится [[Методы оптимизации в машинном обучении (курс лекций)/2012|здесь]].}}
{|
{|
Строка 8: Строка 10:
|}
|}
-
Автор курса: [[Участник:Kropotov|Д.А. Кропотов]]. Вопросы и комментарии по курсу просьба оставлять на вкладке «обсуждение» к этой странице или адресовать письмом на ''bayesml@gmail.com''. В название письма просьба добавлять [МОМО12].
+
Автор курса: [[Участник:Kropotov|Д.А. Кропотов]]. Вопросы и комментарии по курсу просьба адресовать письмом на ''bayesml@gmail.com''. В название письма просьба добавлять [МОМО14].
-
== Расписание на 2012 учебный год ==
+
== Расписание на 2014 учебный год ==
-
В осеннем семестре 2012 года спецкурс читается на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 506, начало в 18-10.
+
В осеннем семестре 2014 года спецкурс читается на [[ВМиК МГУ|ВМК]] по ??? в ауд. ???, начало в ???.
{| class = "standard"
{| class = "standard"
Строка 19: Строка 21:
! width="30%" | Материалы
! width="30%" | Материалы
|-
|-
-
| 10 сентября 2012
+
| ?? сентября 2014
| Введение в курс ||
| Введение в курс ||
-
|-
 
-
| 17 сентября 2012
 
-
| ''Лекции не было'' ||
 
-
|-
 
-
| 24 сентября 2012
 
-
| Методы одномерной минимизации || [[Media:MOMO12_min1d.pdf|Текст (PDF, 185Кб)]]
 
-
|-
 
-
| 1 октября 2012
 
-
| Базовые методы многомерной оптимизации || [[Media:MOMO12_minnd_basic.pdf|Текст (PDF, 1.13Мб)]]
 
-
|-
 
-
| 8 октября 2012
 
-
| Продвинутые методы многомерной оптимизации || [[Media:MOMO12_minnd_advanced.pdf|Текст (PDF, 667Кб)]]
 
-
|-
 
-
| 15 октября 2012
 
-
| Методы оптимизации с использованием глобальных верхних оценок || [[Media:MOMO12_upper_bounds.pdf|Текст (PDF, 248Кб)]]
 
-
|-
 
-
| 22 октября 2012
 
-
| Задачи оптимизации с ограничениями ||
 
-
|-
 
-
| 29 октября 2012
 
-
| Методы внутренней точки || rowspan="3"|[[Media:MOMO12_ipm.pdf|Текст (PDF, 241Кб)]]
 
-
|-
 
-
| 5 ноября 2012
 
-
| ''Лекции не было (праздничный день)''
 
-
|-
 
-
| 12 ноября 2012
 
-
| Примеры применения методов внутренней точки
 
-
|-
 
-
| 19 ноября 2012
 
-
| Методы оптимизации для разреженных линейных моделей классификации и регрессии || [[Media:MOMO12_sparse_methods.pdf|Текст (PDF, 229Кб)]]
 
-
|-
 
-
| 26 ноября 2012
 
-
| Методы отсекающих плоскостей ||
 
-
|-
 
-
| 3 декабря 2012
 
-
| Стохастическая оптимизация ||
 
-
|-
 
-
| 10 декабря 2012
 
-
| ''Лекции не было'' ||
 
-
|-
 
-
| 17 декабря 2012
 
-
| Экзамен || [[Media:MOMO12_exam.pdf|Вопросы к экзамену (PDF, 99Кб)]]
 
|-
|-
|}
|}
-
 
-
== Практические задания ==
 
-
 
-
Задание 1. [[Методы оптимизации в машинном обучении (курс лекций)/2012/Задание 1|Методы одномерной минимизации]].<br>
 
-
 
-
Задание 2. [[Методы оптимизации в машинном обучении (курс лекций)/2012/Задание 2|Методы многомерной минимизации для логистической регрессии]].
 
-
 
-
Задание 3. [[Методы оптимизации в машинном обучении (курс лекций)/2012/Задание 3|Методы внутренней точки для линейной регрессии]].
 
-
 
-
== Экзамен ==
 
-
 
-
Экзамен состоится 17 декабря в ауд. 506, начало в 16-20. К экзамену допускаются только те студенты, кто успешно выполнил не менее одного практического задания. На экзамене при подготовке разрешается пользоваться любыми материалами.
 
-
 
-
[[Media:MOMO12_exam.pdf|Вопросы к экзамену + теоретический минимум (PDF, 99Кб)]]
 
-
 
-
== Оценки ==
 
-
 
-
{|class = "standard sortable"
 
-
! Студент !! Группа !! Задание 1 !! Задание 2 !! Задание 3 !! Экзамен !! Итог
 
-
|-
 
-
| Сокурский || align="center"|317 || на проверке || || || ||
 
-
|-
 
-
| Чистякова || align="center"|422 || align="center"|4.0 || || || align="center"|5 || align="center"|5
 
-
|-
 
-
| Артюхин || align="center"|517 || align="center"|4.9 || || || ||
 
-
|-
 
-
| Елшин || align="center"|517 || на проверке || || || ||
 
-
|-
 
-
| Зимовнов || align="center"|517 || align="center"|5.0 || align="center"|4.3 || align="center"|4.4 || || align="center"|5
 
-
|-
 
-
| Кириллов || align="center"|517 || align="center"|4.0 || || || ||
 
-
|-
 
-
| Некрасов || align="center"|517 || align="center"|3.8 || || || align="center"|3 || align="center"|3
 
-
|-
 
-
| Новиков П. || align="center"|517 || || align="center"|3.8 || || align="center"|4 || align="center"|4
 
-
|-
 
-
| Соколов || align="center"|517 || align="center"|5.0 || align="center"|4.8 || align="center"|4.4 || || align="center"|5
 
-
|-
 
-
| Фигурнов || align="center"|517 || на проверке || || || ||
 
-
|-
 
-
| Сайко || align="center"|мех-мат || align="center"|3.6 || || || ||
 
-
|-
 
-
|}
 
== Система выставления оценок за курс ==
== Система выставления оценок за курс ==
Строка 144: Строка 61:
* Метод сопряженных градиентов для оптимизации неквадратичных функций, зависимость от точной одномерной оптимизации;
* Метод сопряженных градиентов для оптимизации неквадратичных функций, зависимость от точной одномерной оптимизации;
* Квази-ньютоновские методы оптимизации: DFP, BFGS и L-BFGS;
* Квази-ньютоновские методы оптимизации: DFP, BFGS и L-BFGS;
-
* Соотношения между различными методами решения СЛАУ.
 
=== Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра ===
=== Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра ===
Строка 203: Строка 119:
== Литература ==
== Литература ==
# [http://www.ebook3000.com/Programming/General/Optimization-for-Machine-Learning_151684.html Optimization for Machine Learning]. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
# [http://www.ebook3000.com/Programming/General/Optimization-for-Machine-Learning_151684.html Optimization for Machine Learning]. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
 +
# J. Nocedal, S.J. Wright. [http://www.twirpx.com/file/724235/ Numerical Optimization]. Springer, 2006.
# 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.
# A. Antoniou, W.-S. Lu. [http://www.twirpx.com/file/602599/ Practical Optimization: Algorithms and Engineering Applications], Springer, 2007.
# A. Antoniou, W.-S. Lu. [http://www.twirpx.com/file/602599/ Practical Optimization: Algorithms and Engineering Applications], Springer, 2007.
Строка 208: Строка 125:
# Ю. Нестеров. [http://premolab.ru/sites/default/files/nesterovfinal.pdf Методы выпуклой оптимизации], МЦМНО, 2010.
# Ю. Нестеров. [http://premolab.ru/sites/default/files/nesterovfinal.pdf Методы выпуклой оптимизации], МЦМНО, 2010.
# R. Fletcher. [http://www.twirpx.com/file/515359/ Practical Methods of Optimization], Wiley, 2000.
# R. Fletcher. [http://www.twirpx.com/file/515359/ Practical Methods of Optimization], Wiley, 2000.
-
# [http://astronu.jinr.ru/wiki/upload/d/d6/NumericalRecipesinC.pdf Numerical Recipes. The Art of Scientific Computing], 1992.
+
# [http://www.twirpx.com/file/1442975/ Numerical Recipes. The Art of Scientific Computing], Cambridge University Press, 2007.
 +
 
 +
== Архив ==
 +
[[Методы оптимизации в машинном обучении (курс лекций)/2012|2012 год]]
== См. также ==
== См. также ==

Версия 15:24, 21 августа 2014


Страница курса находится в стадии разработки. Архив 2012 года находится здесь.


Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.

Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.

Автор курса: Д.А. Кропотов. Вопросы и комментарии по курсу просьба адресовать письмом на bayesml@gmail.com. В название письма просьба добавлять [МОМО14].

Расписание на 2014 учебный год

В осеннем семестре 2014 года спецкурс читается на ВМК по ??? в ауд. ???, начало в ???.

Дата Название лекции Материалы
 ?? сентября 2014 Введение в курс

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

В рамках курса предполагается три практических задания и экзамен. Каждое задание и экзамен оцениваются по пятибалльной шкале. Итоговая оценка за курс получается путем взвешенного суммирования оценок за задания и экзамен с дальнейшим округлением в сторону ближайшего целого. Вес каждого задания составляет 1/3. Таким образом, если студент успешно выполнил все три практических задания, то он получает оценку за курс без экзамена. Минимально студент должен выполнить одно практические задание. В этом случае он сдает экзамен, оценка за который идет в итоговую сумму с весом 2/3. Если студент выполнил два практических задания, то он также сдает экзамен, но по облегченной схеме (меньше вопросов в билете, меньше дополнительных вопросов). В этом случае оценка за экзамен идет в итоговую сумму с весом 1/3. За каждый день просрочки при сдаче задания начисляется штраф в 0.1 балла, но не более 2 баллов.

Программа курса

Основные понятия и примеры задач

  • Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
  • Матричные вычисления, примеры;
  • Матричные разложения, их использование для решения СЛАУ;
  • Структура итерационного процесса в оптимизации, понятие оракула;
  • Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.

Методы одномерной оптимизации

  • Минимизация функции без производной: метод золотого сечения, метод парабол;
  • Гибридный метод минимизации Брента;
  • Методы решения уравнения f^\prime(x)=0: метод деления отрезка пополам, метод секущей;
  • Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
  • Поиск ограничивающего сегмента;
  • Условия Голдштайна-Деккера-Флетчера для неточного решения задачи одномерной оптимизации;
  • Неточные методы одномерной оптимизации, backtracking.

Методы многомерной оптимизации

  • Метод покоординатного спуска;
  • Методы градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, зависимость от шкалы измерений признаков;
  • Метод Ньютона, подбор длины шага;
  • Теоретические результаты относительно скорости сходимости градиентного спуска и метода Ньютона;
  • Фазы итерационного процесса, LDL-разложение, гибридный метод Ньютона;
  • Метод Levenberg-Marquardt, его использование для обучения нелинейной регрессии;
  • Метод сопряженных градиентов для решения систем линейных уравнений;
  • Метод сопряженных градиентов для оптимизации неквадратичных функций, зависимость от точной одномерной оптимизации;
  • Квази-ньютоновские методы оптимизации: DFP, BFGS и L-BFGS;

Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра

  • Вероятностная модель линейной регрессии с различными регуляризациями: квадратичной, L1, Стьюдента;
  • Идея метода оптимизации, основанного на использовании глобальных оценок, сходимость;
  • Пример применения метода для обучения LASSO;
  • Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностных моделей линейной регрессии;
  • Построение оценок с помощью касательных и замены переменной;
  • Оценка Jakkola-Jordan для логистической функции, оценки для распределений Лапласа и Стьюдента;
  • Применение оценок для обучения вероятностных моделей линейной регрессии;
  • Выпукло-вогнутая процедура, примеры использования.

Задачи оптимизации с ограничениями, понятие двойственности

  • Векторные и матричные нормы, примеры, двойственная норма;
  • Выпуклые множества и функции, сопряженная функция Фенхеля, понятие двойственности;
  • Двойственная функция Лагранжа, ее связь с сопряженной функцией Фенхеля, двойственная задача оптимизации;
  • Геометрическая интерпретация двойственности;
  • Необходимые и достаточные условия оптимальности в задачах условной оптимизации, теорема Куна-Таккера;
  • Возмущенная задача оптимизации, экономический смысл коэффициентов Лагранжа.

Методы внутренней точки

  • Условия Куна-Таккера для выпуклых задач оптимизации, общая структура прямо-двойственных методов оптимизации;
  • Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона;
  • Прямо-двойственный метод Ньютона;
  • Метод логарифмических барьерных функций, поиск допустимой стартовой точки;
  • Прямо-двойственный метод внутренней точки;
  • Использование методов внутренней точки для обучения SVM.

Разреженные методы машинного обучения

  • Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2;
  • Понятие субградиента выпуклой функции, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации, примеры;
  • Проксимальный метод;
  • Метод покоординатного спуска и блочной покоординатной оптимизации;
  • Метод active set на примере регрессии наименьших углов.

Методы отсекающих плоскостей

  • Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane);
  • Надграфная форма метода отсекающих плоскостей;
  • Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров;
  • Применение bundle-метода для задачи обучения SVM;
  • Добавление эффективной процедуры одномерного поиска;
  • Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти.

Стохастическая оптимизация

  • Общая постановка задачи стохастической оптимизации, пример использования;
  • Задачи минимизации среднего и эмпирического риска;
  • Метод стохастического градиентного спуска, его отличия от метода градиентного спуска;
  • Стохастический градиентный спуск как метод оптимизации и как метод обучения;
  • Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS);
  • Модели автокодировщика и глубинного автокодировщика, особенности процедуры обучения и использование стохастического градиентного спуска.

Литература

  1. Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
  2. J. Nocedal, S.J. Wright. Numerical Optimization. Springer, 2006.
  3. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
  4. A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
  5. Б. Поляк. Введение в оптимизацию, Наука, 1983.
  6. Ю. Нестеров. Методы выпуклой оптимизации, МЦМНО, 2010.
  7. R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
  8. Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, 2007.

Архив

2012 год

См. также

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

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

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

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

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