Численные методы оптимизации

Оптимальные веса модели находятся методом минимизации средних потерь на выборке $L(\mathbf{w})$. В общем случае потерь и регуляризатора это нельзя сделать аналитически и приходится использовать численные методы оптимизации.

Применение, даже если аналитическое решение существует

Применение численных методов может быть вычислительно эффективнее, даже когда аналитическое решение существует. Например, решение линейной регрессии

$$\hat{\beta}=(X^T X)^{-1}X^T Y$$

хоть и можно выразить аналитически, но для расчёта оно требует обращения матрицы $D\times D$, имеющее порядок сложности $O(D^3)$. Численные методы могут найти приближённое решение, используя меньший объём вычислений.

Численные методы, описанные в этом разделе, основаны на вычислении градиента $\nabla L(\mathbf{w})$, представляющего собой вектор из частных производных потерь по каждому параметру модели:

$$\nabla L(\mathbf{w})= \begin{pmatrix} \frac{\partial L}{\partial w_0} \\ \frac{\partial L}{\partial w_1} \\ \frac{\partial L}{\partial w_2} \\ \cdots \\ \frac{\partial L}{\partial w_D} \\ \end{pmatrix}$$

Градиент полезен, поскольку он указывает направление максимального возрастания функции $L(\mathbf{w})$ в пространстве весов, а антиградиент $-\nabla L(\mathbf{w})$ - направление максимального убывания $L(\mathbf{w})$.

Почему?

Разложим $L(\mathbf{w})$ в ряд Тейлора первого порядка, чтобы получить локально линейную аппроксимацию функции потерь:

$$L(\mathbf{w}+\varepsilon\Delta \mathbf{w}) = L(\mathbf{w})+\varepsilon\nabla L(\mathbf{w})^T(\Delta \mathbf{w}) + o(\varepsilon)$$

Если перебирать всевозможные направления $\Delta \mathbf{w}$ единичной длины, то из неравенства Коши-Буняковского получим, что наибольший локальный рост (для малых $\varepsilon$) достигается, когда $\Delta \mathbf{w}$ сонаправлен $\nabla L(\mathbf{w})$, а максимальный спад - когда $\Delta \mathbf{w}$ и $\nabla L(\mathbf{w})$ направлены в противоположные стороны.

Используя это свойство, градиентные методы оптимизации уменьшают функцию потерь, многократно сдвигая веса в направлении антиградиента функции потерь с малым шагом.

Оптимизация без градиента

Иногда приходится оптимизировать функцию, не располагая её градиентом. Такая ситуация возникает, когда мы можем функцию вычислить в каждой точке, но не можем представить в аналитическом виде, чтобы её можно было продифференцировать. Например, это может быть выручка магазина при различных расположениях товаров на полках или качество решения задачи машинного обучения при различных значениях гиперпараметров. В этом случае используются безградиентные методы оптимизации (gradient free methods), такие как Байесовская оптимизация, генетические (эволюционные) алгоритмы, метод Tree-structured Parzen Estimator, алгоритм имитации отжига, случайный поиск или перебор по сетке значений.