Градиентный спуск

Есть функция стоимости $J(w,b)$ — средний штраф модели по всем обучающим примерам (откуда она берётся — в статье «Функция стоимости логистической регрессии», но для этой статьи достаточно знать: чем меньше $J$, тем лучше модель). Обучение — это поиск таких весов $w$ (w) и сдвига $b$ (b), при которых $J$ минимальна. Вопрос этой статьи: как их искать?

Почему нельзя просто решить уравнение

В школьной алгебре минимум функции ищут так: берут производную, приравнивают к нулю, решают уравнение. Для простых функций (парабола, например) это работает за один шаг. Почему для $J(w,b)$ так не сделать?

Причина — размер и форма задачи. У реальной модели весов (w) не два и не три, а тысячи или миллионы (вспомни $n_x=12288$ только для одной картинки 64×64×3 из «Бинарной классификации»). Уравнение «производная равна нулю» для функции с миллионом переменных, где сама функция $J$ — не простая парабола, а составлена из сигмоиды, логарифмов и суммы по всем примерам, — аналитически не решается никаким известным способом. Прямого пути «сразу к ответу» нет.

Зато есть другой путь: если стоять в любой точке (то есть при любых текущих $w,b$), можно посчитать, в какую сторону отсюда штраф $J$ растёт, и сделать маленький шаг в противоположную сторону. Повторить это много раз — и штраф будет становиться всё меньше. Не за один шаг, а постепенно — но зато этот путь работает для функции любой сложности и любого числа переменных. Это и есть градиентный спуск (gradient descent).

Работает ли этот путь всегда одинаково надёжно — зависит от формы поверхности штрафа. Если нарисовать $J$ как рельеф (по осям — веса, по высоте — штраф), возможны два принципиально разных вида. Первый — выпуклая функция (convex): одна гладкая чаша, как суповая тарелка. У такой поверхности ровно одно дно — единственный глобальный минимум, — и куда ни поставь шарик, скатится именно туда: несколько локальных оптимумов у выпуклой функции появиться не могут в принципе. Второй вид — невыпуклая функция (non-convex): горная гряда с несколькими ямами и холмами. Здесь у шарика появляется беда: он может провалиться в мелкую яму на полпути и застрять в ней — а это локальный оптимум, далеко не самое низкое место рельефа. Настоящее дно будет совсем в другом месте, и спуск до него из неудачной стартовой точки уже не дойдёт. Хорошая новость для логистической регрессии: с кросс-энтропией её поверхность штрафа — выпуклая чаша, поэтому спуск из любой стартовой точки приводит в единственное дно (почему квадрат разницы ломает выпуклость и как кросс-энтропия её спасает — разобрано в «Функции стоимости»).

Если можешь пересказать: у J слишком много переменных и слишком сложная форма, чтобы решить уравнение прямо — вместо этого спуск много раз шагает в сторону уменьшения штрафа; выпуклая поверхность (одна чаша) гарантирует одно дно, невыпуклая (гряда) — несколько ям-ловушек, — двигаемся дальше.

Мини-квиз: верно или неверно — «выпуклая функция всегда имеет несколько локальных оптимумов»?

Наклон: чувствовать склон под ногами

Представь, что ты спускаешься с горы в густом тумане. Видимость нулевая — карты нет, вершины и подножия не видно. Но ты чувствуешь ступнями, в какую сторону земля уходит вниз прямо там, где стоишь. Логичная стратегия: сделать шаг в сторону, где склон уходит вниз сильнее всего, потом проверить наклон снова, и повторять — рано или поздно окажешься у подножия.

Этот «наклон под ногами» в математике называется производной (dJ/dw). Обозначение $dJ/dw$ читается «насколько изменится $J$, если чуть-чуть изменить $w$» — то есть в какую сторону и насколько сильно растёт штраф прямо в текущей точке. Если $dJ/dw$ положительная — штраф растёт при увеличении $w$, то есть склон идёт вверх в сторону увеличения $w$, и вниз — в сторону уменьшения. Если $dJ/dw$ отрицательная — всё наоборот: штраф растёт при уменьшении $w$, а вниз склон идёт в сторону увеличения $w$. В коде эту производную для веса (w) обычно называют коротко dw, а для сдвига $b$ (b) — db.

Прежде чем читать дальше: если стоишь в тумане и чувствуешь, что земля уходит резко вниз влево — в какую сторону логично шагнуть?

Ответ очевиден в аналогии (влево, туда, где вниз), и с производной работает та же логика — просто выражена числом, а не ощущением в ступнях.

Если можешь пересказать: производная (dJ/dw) — это наклон штрафа в текущей точке, знак говорит, в какую сторону штраф растёт, — листай дальше.

Правило шага: минус альфа на наклон

Формула одного шага спуска:

$$w:=w-\alpha \frac{dJ}{dw}$$

Расшифровка по частям. Двоеточие со знаком равно (:=) означает «присвоить новое значение»: посчитать правую часть и записать результат в $w$. Это не уравнение (где обе части равны сами по себе) — поэтому $w$ и стоит с обеих сторон: старое значение используется, чтобы получить новое.

$\alpha$ (альфа) — скорость обучения (learning rate), число, задающее размер шага. Знакомая аналогия — ручка регулировки температуры в душе, когда стоишь с закрытыми глазами: не видишь шкалу, только чувствуешь, горячо тебе или холодно, и крутишь ручку понемногу в нужную сторону. Маленький поворот ручки — безопасно, но долго нащупывать комфортную температуру. Резкий поворот — рискуешь ошпариться, температура «перелетает» мимо нужной точки. $\alpha$ — это ровно «насколько сильно крутим ручку» на каждом шаге. Типичные значения на практике — от 0.001 до 0.1.

$dJ/dw$ — тот самый наклон из предыдущего раздела. Всё правило целиком: сдвинуть $w$ на маленький шаг (размер шага задаёт $\alpha$) в сторону, противоположную наклону.

Если можешь пересказать: w := w − α · dJ/dw — из старого веса вычитаем шаг размера α в направлении наклона, — листай дальше.

Почему минус, а не плюс

Это не случайная деталь формулы — это её суть. Производная $dJ/dw$ показывает, в какую сторону штраф растёт. Чтобы штраф уменьшать, нужно идти в противоположную сторону — отсюда минус.

Проверим на конкретных числах, что происходит при разных знаках наклона. Возьмём простую чашу $J(w)=w^2$, у которой наклон — $dJ/dw=2w$ (производная $w^2$).

Случай 1: $w=5$ (справа от дна чаши, дно — в нуле). Наклон: $dJ/dw=2\cdot 5=10$ — положительный, штраф растёт при увеличении $w$, значит вниз — в сторону уменьшения $w$. При $\alpha =0.1$: $w:=5-0.1\cdot 10=4.0$. Вес уменьшился, придвинулся к дну (к нулю) — правильное направление.

Случай 2: $w=-5$ (слева от дна). Наклон: $dJ/dw=2\cdot (-5)=-10$ — отрицательный, штраф растёт при уменьшении $w$, значит вниз — в сторону увеличения $w$. При $\alpha =0.1$: $w:=-5-0.1\cdot (-10)=-5+1=-4.0$. Вес увеличился, тоже придвинулся к дну — и снова правильное направление, потому что минус перед $\alpha \cdot dJ/dw$ автоматически развернул шаг в нужную сторону при смене знака наклона.

Если бы формула была с плюсом ($w:=w+\alpha dJ/dw$), оба случая сработали бы в противоположную сторону — вес убегал бы от дна чаши всё дальше, а штраф только рос.

Мини-квиз: наклон $dJ/dw=-4$ в некоторой точке, $\alpha =0.5$. Вес увеличится или уменьшится после шага?

Если можешь пересказать: минус в формуле разворачивает шаг против направления роста штрафа, поэтому одна и та же формула верно ведёт к дну и справа, и слева от него, — листай дальше.

Числовой пример: сходимость и расхождение

Продолжим ту же одномерную чашу $J(w)=w^2$ (наклон $dJ/dw=2w$), стартуя с $w=5$, и посмотрим, что даёт разный выбор $\alpha$.

При разумном шаге $\alpha =0.1$: наклон в точке $w=5$ равен $2\cdot 5=10$, следующий вес $5-0.1\cdot 10=4.0$. Дальше так же: $4.0\to 3.2\to 2.56\to 2.048\to \dots$ — веса (w) плавно сходятся к нулю (дну чаши).

При слишком большом шаге $\alpha =1.1$ та же чаша: наклон в точке $w=5$ тот же, $10$, но шаг $5-1.1\cdot 10=-6.0$ — перелетаем через дно на другую сторону. Дальше только хуже: $-6.0\to 7.2\to -8.64\to 10.37\to \dots$ — числа не уменьшаются, а раскачиваются всё сильнее. Как с душем: слишком резкий поворот ручки — и вместо комфортной температуры получаем то ледяную, то кипящую воду, с каждым разом хуже.

Твоя очередь: возьми $\alpha =0.05$, наклон $10$ при $w=5$ — как в примере выше. Посчитай сам, каким получится следующий $w$.

Прежде чем читать дальше ещё раз: при слишком большом шаге $\alpha =1.1$ вес $w$ просто медленнее подходит ко дну чаши, или перелетает через него на другую сторону? Сформулируй ответ сам, а потом сверься с абзацем выше.

Практический вывод: если после нескольких шагов штраф $J$ не падает, а растёт или скачет — первое, что стоит проверить, это не веса (w), а саму $\alpha$.

Если можешь пересказать: маленькая α сходится ко дну плавно, слишком большая — перелетает через дно и расходится, — листай дальше.

И вес, и сдвиг — по одной схеме

Всё, что было сказано про вес $w$, буквально в тех же словах применяется и к сдвигу $b$:

$$b:=b-\alpha \frac{dJ}{db}$$

Обозначения зеркальные: $dJ/db$ (в коде — db) — наклон штрафа по $b$ (b), тот же смысл, что и $dw$, только для другого параметра. Причина, по которой формула для $b$ выглядит настолько же просто, как для $w$, — обе они выведены из одной и той же идеи «сдвинуться против направления роста штрафа», просто применённой к разным числам, от которых зависит $J$. В реальной модели с тысячами весов (w) каждый вес и сдвиг обновляются этим же правилом одновременно, на одном и том же шаге.

Если можешь пересказать: b обновляется той же формулой, что и w, просто со своим наклоном dJ/db, — листай дальше.

Что дальше

Мы разобрали идею спуска целиком: наклон (dJ/dw) показывает направление роста штрафа, шаг делается в противоположную сторону, а размер шага регулирует $\alpha$ (α). Осталось применить это к настоящей модели — логистической регрессии, где сам наклон $dJ/dw$ раскладывается через ещё один важный сигнал у выхода модели, который получил собственное имя — $dz$. Как он выводится и что означает — тема следующих статей, начиная с «Логистической регрессии — градиентного спуска».

Markdown source: /notes/gradient-descent-intro/index.md · more at /notes