Автор: Шамиль Мамедов Редактура: Дмитрий Раков
Гессиан играет большую роль в численной оптимизации. Недавно появились новые алгоритмы оптимизации (например, Sophia). Они используют Гессиан или его приближения для достижения лучших локальных минимумов и более быстрой сходимости. В этой статье мы как раз и познакомимся с Гессианом — ценным инструментом для нахождения минимума функции.
Для начала рассмотрим общую задачу оптимизации:
$$ \underset{\theta}{\text{min}} \ \mathcal{L}(\theta, y, \hat y) $$
Для наглядности мы можем представить практический сценарий, когда мы решаем задачу регрессии для прогнозирования цен на дома и используем среднеквадратичную ошибку (MSE) в качестве нашей функции потерь.
В численной оптимизации основополагающим принципом считается Условие Оптимальности Первого Порядка: если $\theta^\star$ является локальным минимумом $\mathcal L$, то
$$ \nabla \mathcal L(\theta^\star, \cdot)= 0. $$
Простыми словами, когда мы найдем решение, градиент нашей функции потерь будет равен нулю. Если $\theta$ — скаляр, то производная функции в точке решения — нуль (привет, матан). Точка, которая удовлетворяет условию $\nabla_\theta \mathcal L(\cdot)= 0$, называется стационарной точкой $\mathcal L$. Она может быть и локальным минимумом, и локальным максимумом, и седловой точкой, как показано на рисунке 1.
Рисунок 1. Виды стационарных точек
Поскольку нас интересуют только локальные минимумы, нам понадобится еще одно условие для гарантии того, что наше решение $\theta^\star$ не является максимумом. Это условие называется Необходимое Условие Оптимальности Второго Порядка: если $\theta^\star$ является локальным минимумом $\mathcal L$, то
$$ \nabla^2_\theta \mathcal L(\theta^\star,\cdot) \succeq 0. $$
Здесь $\nabla^2_\theta \mathcal L(\theta^\star,\cdot)$ представляет собой вторую производную $\mathcal{L}$ по отношению к $\theta$ и называется Гессианом.
Важно отметить: к сожалению, седловые точки также удовлетворяют необходимому условию оптимальности второго порядка, как показано на рисунке 1. Для гарантии нашего решения как локального минимума нам нужно еще более сильное условие, известное как Достаточное Условие Оптимальности Второго Порядка: $\nabla^2_\theta \mathcal L(\theta^\star,\cdot) \succ 0$.
Теперь, когда мы рассмотрели основные теоретические аспекты, давайте перейдем к алгоритмам, которые используют информацию второго порядка для оптимизации наших параметров $\theta$.
Метод Ньютона (метод Ньютона-Рафсона) — метод, в первую очередь используемый для решения задач нахождения корней нелинейной функции. Фактически, Условие Оптимальности Первого Порядка может быть сформулировано как задача нахождения корней: нам нужно найти параметры $\theta^\star$, которые делают градиент функции потерь равным нулю. Для достижения этой цели мы можем применить метод Ньютона с разложением $\nabla \mathcal{L}$ в ряд Тейлора: