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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Методы одномерной оптимизации)
Текущая версия (08:55, 7 сентября 2015) (править) (отменить)
 
(56 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
__NOTOC__
+
#REDIRECT [[Методы оптимизации в машинном обучении (курс лекций)/2015]]
-
 
+
-
{{notice|Внимание! Выложено первое практическое задание. Срок сдачи — 11 октября.}}
+
-
 
+
-
{|
+
-
|[[Изображение:Momo_intro.jpg|300px]]
+
-
| valign="top"|Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.
+
-
 
+
-
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
+
-
|}
+
-
 
+
-
Автор курса: [[Участник:Kropotov|Д.А. Кропотов]]. Вопросы и комментарии по курсу просьба оставлять на вкладке «обсуждение» к этой странице или адресовать письмом на ''bayesml@gmail.com''. В название письма просьба добавлять [МОМО12].
+
-
 
+
-
== Расписание на 2012 учебный год ==
+
-
В осеннем семестре 2012 года спецкурс читается на [[ВМиК МГУ|ВМК]] по понедельникам в ауд. 506, начало в 18-05.
+
-
 
+
-
{| class = "standard"
+
-
|+
+
-
! width="10%" | Дата
+
-
! width="60%" | Название лекции
+
-
! width="30%" | Материалы
+
-
|-
+
-
| 10 сентября 2012
+
-
| Введение в курс ||
+
-
|-
+
-
| 17 сентября 2012
+
-
| ''Лекции не будет'' ||
+
-
|-
+
-
| 24 сентября 2012
+
-
| Методы одномерной минимизации || [[Media:MOMO12_min1d.pdf|Текст (PDF)]]
+
-
|-
+
-
| 1 октября 2012
+
-
| Базовые методы многомерной оптимизации ||
+
-
|-
+
-
| 8 октября 2012
+
-
| Продвинутые методы многомерной оптимизации ||
+
-
|-
+
-
| 15 октября 2012
+
-
| Методы оптимизации с использованием глобальных верхних оценок ||
+
-
|-
+
-
| 22 октября 2012
+
-
| Задачи оптимизации с ограничениями ||
+
-
|-
+
-
| 29 октября 2012
+
-
| Методы внутренней точки ||
+
-
|-
+
-
| 5 ноября 2012
+
-
| ''Лекции не будет (праздничный день)'' ||
+
-
|-
+
-
| 12 ноября 2012
+
-
| Разреженные методы машинного обучения ||
+
-
|-
+
-
| 19 ноября 2012
+
-
| Методы cutting plane и bundle ||
+
-
|-
+
-
| 26 ноября 2012
+
-
| Стохастическая оптимизация ||
+
-
|-
+
-
|}
+
-
 
+
-
== Практические задания ==
+
-
Задание 1. [[Методы оптимизации в машинном обучении (курс лекций)/2012/Задание 1|Методы одномерной минимизации]].
+
-
 
+
-
== Оценка за курс ==
+
-
В рамках курса студентам предлагается выполнить ряд практических заданий. Для получения допуска к экзамену необходимо успешно выполнить не менее двух заданий.
+
-
 
+
-
== Программа курса ==
+
-
 
+
-
=== Основные понятия и примеры задач ===
+
-
 
+
-
* Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума;
+
-
* Матричные вычисления, примеры;
+
-
* Матричные разложения, их использование для решения СЛАУ;
+
-
* Структура итерационного процесса в оптимизации, понятие оракула;
+
-
* Примеры оракулов и задач машинного обучения со «сложной» оптимизацией.
+
-
 
+
-
=== Методы одномерной оптимизации ===
+
-
 
+
-
* Минимизация функции без производной: метод золотого сечения, метод парабол;
+
-
* Гибридный метод минимизации Брента;
+
-
* Методы решения уравнения <tex>f^\prime(x)=0</tex>: метод деления отрезка пополам, метод секущей;
+
-
* Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента;
+
-
* Поиск ограничивающего сегмента;
+
-
* Условия Голдштайна-Деккера-Флетчера для неточного решения задачи одномерной оптимизации;
+
-
* Неточные методы одномерной оптимизации, backtracking.
+
-
 
+
-
=== Методы многомерной оптимизации ===
+
-
 
+
-
* Метод покоординатного спуска;
+
-
* Методы градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, зависимость от шкалы измерений признаков;
+
-
* Метод Ньютона, подбор длины шага;
+
-
* Фазы итерационного процесса, LDL-разложение, гибридный метод Ньютона;
+
-
* Метод Levenberg-Marquardt, его использование для обучения нелинейной регрессии.
+
-
* Квази-ньютоновские методы оптимизации: BFGS и L-BFGS.
+
-
* Метод сопряженных градиентов;
+
-
* Метод сопряженных градиентов с предопределением, его использование для решения разреженных СЛАУ большого объема.
+
-
 
+
-
=== Методы оптимизации с использованием глобальных верхних оценок ===
+
-
 
+
-
* Идея метода, сходимость;
+
-
* Построение оценок с помощью неравенства Йенсена, ЕМ-алгоритм, вариационный подход;
+
-
* Построение оценок с помощью касательных, оценка Jaakkola-Jordan, nu-trick;
+
-
* Применение оценок для обучения L1-регуляризованной линейной/логистической регрессии;
+
-
* Выпукло-вогнутая процедура для задач безусловной и условной оптимизации, примеры использования.
+
-
 
+
-
=== Задачи оптимизации с ограничениями ===
+
-
 
+
-
* Выпуклые множества и функции;
+
-
* Двойственная функция Лагранжа и Фенхеля, их основные свойства.
+
-
* Необходимые и достаточные условия оптимальности в задачах условной оптимизации, теорема Куна-Таккера.
+
-
* Двойственная задача, графическая интерпретация, смысл коэффициентов Лагранжа.
+
-
* Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона.
+
-
 
+
-
=== Методы внутренней точки ===
+
-
 
+
-
* Метод внутренней точки;
+
-
* Прямодвойственный метод внутренней точки;
+
-
* Быстрые алгоритмы умножения матрицы на вектор и их использование в методе внутренней точки.
+
-
 
+
-
=== Разреженные методы машинного обучения, L1-регуляризация ===
+
-
 
+
-
* Примеры задач и виды разреженных регуляризаторов;
+
-
* Проксимальный метод;
+
-
* Метод покоординатного спуска и блочной покоординатной оптимизации;
+
-
* Метод внутренней точки.
+
-
 
+
-
=== Методы cutting plane и bundle ===
+
-
 
+
-
* Субградиент выпуклой функции;
+
-
* Метод отсекающей плоскости и его bundle расширение;
+
-
* Примеры задач распознавания, сводящихся к оптимизации регуляризованных функционалов;
+
-
* Использование bundle метода для задач оптимизации регуляризованных функционалов;
+
-
* Добавление одномерного поиска.
+
-
 
+
-
=== Стохастическая оптимизация ===
+
-
 
+
-
== Литература ==
+
-
# [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.
+
-
# S. Boyd. [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.
+
-
# 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.
+
-
 
+
-
== См. также ==
+
-
[[GM|Курс «Графические модели»]]
+
-
 
+
-
[[Bmmo|Курс «Байесовские методы в машинном обучении»]]
+
-
 
+
-
[[Спецсеминар "Байесовские методы машинного обучения"|Спецсеминар «Байесовские методы машинного обучения»]]
+
-
 
+
-
[[Математические методы прогнозирования (кафедра ВМиК МГУ)]]
+
-
 
+
-
[[Категория:Учебные курсы]]
+

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

  1. REDIRECT Методы оптимизации в машинном обучении (курс лекций)/2015
Источник — «http://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»
Личные инструменты