Delivered at:: Joint Department with Yandex (Big Data and Information Retrieval School)

Course type:: Elective course

When:: 1 year, 3, 4 module

Instructor

Hushchyn, Mikhail

Полная версия программы учебной дисциплины

Аннотация

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

Цель освоения дисциплины

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

Планируемые результаты обучения

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

Содержание учебной дисциплины

Основные понятия и примеры задач.
"Градиент и гессиан функции многих переменных, их свойства, необходимые и достаточные условия безусловного экстремума; Матричные разложения, их использование для решения СЛАУ; Структура итерационного процесса в оптимизации, понятие оракула, критерии останова; Глобальная и локальная оптимизация, скорости сходимости итерационных процессов оптимизации; Примеры оракулов и задач машинного обучения со «сложной» оптимизацией."
Методы одномерной оптимизации
"Минимизация функции без производной: метод золотого сечения, метод парабол; Гибридный метод минимизации Брента; Методы решения уравнения : метод деления отрезка пополам, метод секущей; Минимизация функции с известной производной: кубическая аппроксимация и модифицированный метод Брента; Поиск ограничивающего сегмента; Условия Армихо-Голдштайна-Вольфа для неточного решения задачи одномерной оптимизации; Неточные методы одномерной оптимизации, backtracking."
Методы многомерной оптимизации
"Методы линейного поиска и доверительной области; Метод градиентного спуска: наискорейший спуск, спуск с неточной одномерной оптимизацией, скорость сходимости метода для сильно-выпуклых функций с липшицевым градиентом, зависимость от шкалы измерений признаков; Сходимость общего метода линейного поиска с неточной одномерной минимизацией; Метод Ньютона: схема метода, скорость сходимости для выпуклых функций с липшицевым гессианом, подбор длины шага, способы коррекции гессиана до положительно-определённой матрицы; Метод сопряженных градиентов для решения систем линейных уравнений, скорость сходимости метода, предобуславливание; Метод сопряженных градиентов для оптимизации неквадратичных функций, стратегии рестарта, зависимость от точной одномерной оптимизации; Неточный (безгессианный) метод Ньютона: схема метода, способы оценки произведения гессиана на вектор через вычисление градиента; Применение неточного метода Ньютона для обучения линейного классификатора и нелинейной регрессии, аппроксимация Гаусса-Ньютона и адаптивная стратегия Levenberg-Marquardt; Квазиньютоновские методы оптимизации: DFP, BFGS и L-BFGS;"
Методы оптимизации с использованием глобальных верхних оценок, зависящих от параметра
"Вероятностная модель линейной регрессии с различными регуляризациями: квадратичной, L1, Стьюдента; Идея метода оптимизации, основанного на использовании глобальных оценок, сходимость; Пример применения метода для обучения LASSO; Построение глобальных оценок с помощью неравенства Йенсена, ЕМ-алгоритм, его применение для вероятностных моделей линейной регрессии; Построение оценок с помощью касательных и замены переменной; Оценка Jaakkola-Jordan для логистической функции, оценки для распределений Лапласа и Стьюдента; Применение оценок для обучения вероятностных моделей линейной регрессии; Выпукло-вогнутая процедура, примеры использования."
Методы внутренней точки.
"Необходимые и достаточные условия оптимальности в задачах условной оптимизации, условия Куна-Таккера и условия Джона, соотношение между ними; Выпуклые задачи условной оптимизации, двойственная функция Лагранжа, двойственная задача оптимизации; Решение задач условной оптимизации с линейными ограничениями вида равенство, метод Ньютона; Прямо-двойственный метод Ньютона, неточный вариант метода; Метод логарифмических барьерных функций; Методы первой фазы; Прямо-двойственный метод внутренней точки; Использование методов внутренней точки для обучения SVM."
Разреженные методы машинного обучения
"Модели линейной/логистической регрессии с регуляризациями L1 и L1/L2; Понятие субградиента выпуклой функции, его связь с производной по направлению, необходимое и достаточное условие экстремума для выпуклых негладких задач безусловной оптимизации; Метод наискорейшего субградиентного спуска; Проксимальный метод; Метод покоординатного спуска и блочной покоординатной оптимизации."
Методы отсекающих плоскостей
"Понятие отделяющего оракула, базовый метод отсекающих плоскостей (cutting plane); Надграфная форма метода отсекающих плоскостей; Bundle-версия метода отсекающих плоскостей, зависимость от настраиваемых параметров; Применение bundle-метода для задачи обучения SVM; Добавление эффективной процедуры одномерного поиска; Реализация метода с использованием параллельных вычислений и в условиях ограничений по памяти."
Стохастическая оптимизация
"Общая постановка задачи стохастической оптимизации, пример использования; Задачи минимизации среднего и эмпирического риска; Метод стохастического градиентного спуска, две фазы итерационного процесса, использование усреднения и инерции; Стохастический градиентный спуск как метод оптимизации и как метод обучения; Метод SAG; Применение стохастического градиентного спуска для SVM (алгоритм PEGASOS)."

Элементы контроля

Домашняя работа 1
Домашняя работа 2
Экзамен
Оценка за дисциплину выставляется в соответствии с формулой оценивания от всех пройденных элементов контроля. Экзамен не проводится.

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
0.3 * Домашняя работа 1 + 0.3 * Домашняя работа 2 + 0.4 * Экзамен

Master’s Programme 'Data Science'

Contacts

Optimization in Machine Learning

Instructor

Программа дисциплины

Аннотация

Цель освоения дисциплины

Планируемые результаты обучения

Содержание учебной дисциплины

Элементы контроля

Промежуточная аттестация

Список литературы

Рекомендуемая основная литература

Рекомендуемая дополнительная литература