Методы оптимизации в машинном обучении

Магистратура 2020/2021

Статус: Курс по выбору (Науки о данных)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Ратников Федор Дмитриевич

Прогр. обучения: Науки о данных

Язык: русский

Кредиты: 4

Контактные часы: 48

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

Аннотация

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

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

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

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

Знать основные методы непрерывной оптимизации, в том числе невыпуклой.
Уметь толковать задачи машинного обучения как задачи оптимизации и применять релевантные задаче методы.
Владеть методами теоретического исследования оптимизационного процесса.
Владеть навыками обработки и интерпретации результатов эксперимента.
Уметь находить градиенты и гессианы функций от многих переменных.
Уметь примененять методы оптимизации с использованием глобальных верхних оценок.
Уметь определять возможности применения того или иного метода оптимизации.
Уметь ориентироваться в потоке научной информации для использования новых методах оптимизации в отсекающих плоскостей.
Уметь примененять 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 * Экзамен

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