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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Расписание на 2012 учебный год)
Строка 1: Строка 1:
__NOTOC__
__NOTOC__
-
 
-
{{stop|Страница курса находится в стадии формирования}}
 
{|
{|
|[[Изображение:Momo_intro.jpg|300px]]
|[[Изображение:Momo_intro.jpg|300px]]
-
| valign="top"|Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Предполагается, что по окончании курса слушатели смогут не только подобрать подходящий метод для своей задачи, но и разработать свой метод оптимизации, наиболее полно учитывающий особенности конкретной задачи.
+
| valign="top"|Курс посвящен классическим и современным методам решения задач непрерывной оптимизации, а также особенностям их применения в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков не только по подбору подходящего метода для своей задачи, но и по разработке своего метода оптимизации, наиболее полно учитывающего особенности конкретной задачи.
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
Курс рассчитан на студентов старших курсов и аспирантов. Знание основ машинного обучения приветствуется, но не является обязательным — все необходимые понятия вводятся в ходе лекций.
Строка 83: Строка 81:
* Неточные методы одномерной оптимизации, backtracking.
* Неточные методы одномерной оптимизации, backtracking.
-
=== Базовые методы многомерной оптимизации ===
+
=== Методы многомерной оптимизации ===
* Метод покоординатного спуска;
* Метод покоординатного спуска;
Строка 90: Строка 88:
* Фазы итерационного процесса, LDL-разложение, гибридный метод Ньютона;
* Фазы итерационного процесса, LDL-разложение, гибридный метод Ньютона;
* Метод Levenberg-Marquardt, его использование для обучения нелинейной регрессии.
* Метод Levenberg-Marquardt, его использование для обучения нелинейной регрессии.
-
 
-
=== Продвинутые методы многомерной оптимизации ===
 
-
 
* Квази-ньютоновские методы оптимизации: BFGS и L-BFGS.
* Квази-ньютоновские методы оптимизации: BFGS и L-BFGS.
* Метод сопряженных градиентов;
* Метод сопряженных градиентов;

Версия 11:49, 5 сентября 2012


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

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

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

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

В осеннем семестре 2012 года спецкурс читается на ВМК по понедельникам в ауд. 506, начало в 18-05.

Дата Название лекции Материалы
10 сентября 2012 Введение в курс
17 сентября 2012 Лекции не будет
24 сентября 2012 Методы одномерной минимизации, выдача первого практического задания
1 октября 2012 Базовые методы многомерной оптимизации
8 октября 2012 Продвинутые методы многомерной оптимизации
15 октября 2012 Методы оптимизации с использованием глобальных верхних оценок
22 октября 2012 Задачи оптимизации с ограничениями
29 октября 2012 Методы внутренней точки
5 ноября 2012 Лекции не будет (праздничный день)
12 ноября 2012 Разреженные методы машинного обучения
19 ноября 2012 Методы cutting plane и bundle
26 ноября 2012 Стохастическая оптимизация

Оценка за курс

В рамках курса студентам предлагается выполнить ряд практических заданий.

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

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

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

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

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

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

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

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

  • Идея метода, сходимость;
  • Построение оценок с помощью неравенства Йенсена, ЕМ-алгоритм, вариационный подход;
  • Построение оценок с помощью касательных, оценка Jaakkola-Jordan, nu-trick;
  • Применение оценок для обучения L1-регуляризованной линейной/логистической регрессии;
  • Выпукло-вогнутая процедура для задач безусловной и условной оптимизации, примеры использования.

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

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

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

  • Метод внутренней точки;
  • Прямодвойственный метод внутренней точки;
  • Быстрые алгоритмы умножения матрицы на вектор и их использование в методе внутренней точки.

Разреженные методы машинного обучения, L1-регуляризация

  • Примеры задач и виды разреженных регуляризаторов;
  • Проксимальный метод;
  • Метод покоординатного спуска и блочной покоординатной оптимизации;
  • Метод внутренней точки.

Методы cutting plane и bundle

  • Субградиент выпуклой функции.

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

Литература

  1. Optimization for Machine Learning. Edited by Suvrit Sra, Sebastian Nowozin and Stephen J. Wright, MIT Press, 2011.
  2. S. Boyd. Convex Optimization, Cambridge University Press, 2004.
  3. A. Antoniou, W.-S. Lu. Practical Optimization: Algorithms and Engineering Applications, Springer, 2007.
  4. R. Fletcher. Practical Methods of Optimization, Wiley, 2000.
  5. Numerical Recipes. The Art of Scientific Computing, 1992.

См. также

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

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

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

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

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