В этом разделе мы поговорим о том, как оптимизировать негладкие функции в ситуациях, когда «плохую» составляющую удаётся локализовать и она сравнительно несложная.
Проксимальная минимизация
Для того, чтобы подступиться к проксимальным методам, посмотрим на градиентный спуск с другой стороны. Для простоты рассмотрим константный размер шага . Перепишем шаг градиентного спуска следующим образом:
Посмотрим на это уравнение по-другому. Рассмотрим функцию , равную при ( мы будем воспринимать, как некоторый временной параметр). Тогда при :
Теперь слева не что иное, как аппроксимация производной! Если мы устремим к нулю, то получится так называемое уравнение градиентного потока:
Эта динамика в случае выпуклой функции сходится к точке минимума из любой начальной точки при . Сравнение между динамикой градиентного спуска и градиентного потока можно увидеть на следующем изображении:
Первый состоит из дискретных шагов, второй же представляет из себя непрерывный процесс.
Нетрудно осознать физический смысл динамики : маленькое тело скатывается по склону графика функции так, что в любой момент её скорость совпадает с антиградиентом, то есть оно катится по направлению наискорейшего спуска.
Теперь представим, что мы сейчас занимается не машинным обучением, а численными методами. Перед нами есть обыкновенное дифференциальное уравнение (ОДУ), и его надо решить. Одним из численных методов решения ОДУ (более стабильным, чем обычная схема Эйлера) является обратная схема Эйлера (backward Euler scheme):
В обратной схеме Эйлера мы делаем градиентный спуск, только градиент смотрим не в текущей точке (как было бы в обычной схеме Эйлера), а буквально в будущей. Занятная идея, только вот напрямую выразить из этого уравнения не получится. Нужно поступить чуть хитрее. Заметим, что
Это позволяет нам сказать, что весь вектор является градиентом функции , посчитанном в точке . Тогда получаем, что удовлетворяет следующему условию:
Если функция выпуклая, то тоже выпуклая, и её стационарная точка будет точкой минимума. Стало быть, можно высчитывать по формуле
Определим прокс-оператор следующим образом:
Тогда, поскольку умножение на внутри арг-минимума не влияет на саму точку минимума, получаем следующую итеративную схему:
Итеративный процесс называется методом проксимальной минимизации. Вы можете спросить себя: зачем он нужен? Ведь теперь на каждом шаге мы должны решать задачу оптимизации:
Если выпуклая, нам есть, что ответить: наличие второго слагаемого гарантирует сильную выпуклость задачи, то есть она решается достаточно эффективно. Но если не является выпуклой, то мы ничего не достигли этой модификацией.
Композитная оптимизация, проксимальный градиентный метод (PGM)
Чтобы понять, зачем нам понадобилась проксимальная оптимизация, рассмотрим оптимизацию функций вида
где – это гладкая функция, а – это функция, для которой прокс-оператор считается аналитически. Воспользуемся следующим трюком: по мы совершим градиентный шаг, а по – проксимальный. Получаем следующую итеративную процедуру:
Эта процедура определяет так называемый проксимальный градиентный метод (Proximal Gradient Method, PGM), который может использоваться, например, для решения задачи регрессии с -регуляризацией.
ISTA (Iterative Shrinkage-Thresholding Algorithm)
Теперь решим конкретную задачу -регрессии. Она выглядит следующим образом:
Мы хотим применить PGM к этой задаче, для этого нужно научиться вычислять прокс-оператор для -нормы. Проделаем эту операцию:
Заметим, что каждое слагаемое зависит только от одной координаты. Это значит, что каждую координату мы можем прооптимизировать отдельно и получить одномерных задач минимизации вида
Решение такой одномерной задачи записывается в виде функции soft thresholding:
Тогда мы получаем следующий алгоритм для -регрессии, которые называются Iterative Shrinkage-Thresholding Algorithm (ISTA):
w = normal(0, 1) # инициализация
repeat S times: # другой вариант: while abs(err) > tolerance
f = X.dot(w) # посчитать предсказание
delta = f - y # посчитать отклонение предсказания
grad = 2 * X.T.dot(delta) / n # посчитать градиент
w_prime = w - alpha * grad # считаем веса, которые отправим в прокс
for i in range(d):
w[i] = soft_threshold(w_prime[i], alpha * llambda) # вычисляем прокс
Заметим одну крутую особенность этого алгоритма -- мы явно видим, что решение получается разреженное, ведь какие-то координаты будут явно зануляться при применении soft threshold! Причем чем больше размер и шага, и параметра регуляризации, тем больше прореживается координат.
Конкретно этот метод не применяется на практике, но используются его вариации. Например, статья, которая указана в параграфе про линейные модели о том, как работало предсказание CTR в google в 2012 году, также базируется на вычислении soft threshold как прокс-оператора.
Общие выводы
Подытожим все вышесказанное:
- Проксимальные методы – теоретически интересная идея для выпуклой оптимизации, которая должна давать более численно стабильные алгоритмы.
- Проксимальные методы позволяют достаточно эффективно решать задачи композитной оптимизации, в частности, -регуляризованную задачу регрессии. Более того, используемые на практике решения задачи -регуляризованной регрессии так или иначе базируются на идее ISTA.
- Также есть попытки использовать проксимальные методы для более сложных моделей. Например, статья о применении их в нейросетях.
Кроме того, имеются применения проксимальных методов для построения распределенных алгоритмов. Все подробности можно найти в монографии Neal Parikh и Stephen Boyd, мы же только привели применение этих идей в машинном обучении.