Обусловленность

Одно число

$$\htmlData{k=kappa}{\kappa = \frac{\lambda_{\max}}{\lambda_{\min}} = \frac{L}{\mu}}$$

$\kappa$ — отношение крайних собственных значений гессиана, то есть мера того, насколько ландшафт вытянут. Это то же число, что появлялось в блоке 1 (урок 080) как отношение сингулярных значений: у квадратичной задачи $f = \frac12\|Ax - b\|^2$ гессиан равен $A^\top A$, поэтому $\kappa(\nabla^2 f) = \kappa(A)^2$.

Последнее равенство стоит запомнить: обусловленность задачи наименьших квадратов — квадрат обусловленности матрицы. Матрица с $\kappa(A) = 10^3$, которая выглядит вполне рабочей, даёт задачу оптимизации с $\kappa = 10^6$.

Почему κ определяет всё

Из урока 030: число итераций градиентного спуска порядка $\frac{\kappa}{2}\ln\frac1\varepsilon$. В числах для сокращения ошибки в миллион раз:

$\kappa$	шагов
$1$	$1$
$10$	$69$
$100$	$691$
$10^4$	$\approx 7 \cdot 10^4$
$10^6$	$\approx 7 \cdot 10^6$

Зависимость линейная, и никакая настройка шага её не меняет — шаг в этих оценках уже оптимален. Отсюда главный вывод блока: если обучение идёт неприлично медленно, вопрос не «какой оптимизатор взять», а «почему задача так вытянута».

Сравните три ландшафта. Обусловленность растёт от $1$ до $100$, шаг у всех можно подобрать наилучший — и разница в числе итераций получается на два порядка.

κ = 1κ = 10κ = 100

градиентный спускмоментAdam

лосс, логарифмическая шкала

шаг α

0.019

итераций

120

f в конце

3.62e-2

обусловленность κ

1

порог 2/L

2

 

сходится

Откуда берётся плохая обусловленность

Пять источников, и каждый лечится по-своему:

источник	пример	лечение
разный масштаб признаков	возраст в годах и доход в рублях	стандартизация входов
коррелированные признаки	рост в см и в дюймах	декоррелирование, L2
разная глубина слоёв	градиенты первых слоёв меньше	нормализация, residual
разная кривизна по параметрам	эмбеддинги против bias’ов	адаптивные методы
плохо поставленная задача	почти вырожденная матрица	регуляризация

Первая строка — самый дешёвый и самый пропускаемый шаг. Признаки с масштабами $1$ и $10^4$ дают гессиан с $\kappa \approx 10^8$ до всякого обучения. Стандартизация уменьшает $\kappa$ на порядки одной строкой кода, и по соотношению эффекта к усилию ничто в этом блоке с ней не сравнится.

Предобусловливание

Общая идея всех средств: заменить шаг $\alpha$ на матрицу.

$x_{k+1} = x_k - \alpha P^{-1}\nabla f(x_k)$

Здесь $P$ — предобусловливатель, и цель одна: чтобы $P^{-1}\nabla^2 f$ имела обусловленность лучше, чем $\nabla^2 f$. Крайние случаи известны:

$P$	что получается
$I$	обычный градиентный спуск
$\nabla^2 f$	метод Ньютона, $\kappa$ становится $1$
$\text{diag}(\nabla^2 f)$	якобиево предобусловливание
$\text{diag}(\sqrt{\mathbb{E}[g^2]})$	Adam

Последняя строка — то, чем Adam на самом деле является: диагональным предобусловливателем, оценённым по вторым моментам градиента вместо гессиана. Отсюда и его сильная сторона (устойчивость к разномасштабным параметрам), и слабая (диагональ не видит корреляций между параметрами, так что повёрнутый ландшафт ему не выпрямить).

Проверьте это на виджете: переключите на Adam на ландшафте $\kappa = 100$ — он идёт почти прямо, потому что ландшафт выровнен по осям и диагонали достаточно. На банане Розенброка из прошлого урока преимущество куда скромнее: там кривизна не диагональна.

Что делать практически

Порядок действий, от самого дешёвого:

1. стандартизовать входы. Всегда. До всего остального;
2. добавить нормализацию между слоями — урок 100 объясняет, почему это тоже предобусловливание;
3. взять адаптивный метод — урок 080;
4. добавить момент — урок 070. Он не уменьшает $\kappa$, но делает зависимость $\sqrt{\kappa}$ вместо $\kappa$;
5. регуляризовать, если задача почти вырождена (урок 030 показал, во сколько раз это ускоряет);
6. менять архитектуру — residual-связи существуют в значительной мере ради этого.

Настройка learning rate в этом списке отсутствует намеренно. Она нужна, но она не устраняет причину: на задаче с $\kappa = 10^6$ идеально подобранный шаг всё равно даёт миллионы итераций.