Урок 24. Градиентный спуск и SGD

Полный градиент честно опрашивает все данные и только потом делает один шаг. Но если данных миллионы, честность становится непозволительной роскошью. Оказывается, чтобы понять, куда идти вниз, вовсе не обязательно смотреть на всё — хватает случайной горсти примеров.

Сколько стоит один шаг

В уроке о градиенте спуск выглядел просто: посчитать $\nabla L$ , шагнуть против него, повторить. Но у потери есть строение, которое мы до сих пор прятали. Она — среднее по всем обучающим объектам:

L(w)=\frac1n\sum_{i=1}^{n}\ell_i(w),\qquad \nabla L(w)=\frac1n\sum_{i=1}^{n}\nabla\ell_i(w).

Чтобы сделать один точный шаг, надо пройти по всем $n$ объектам. Для учебной задачи это пустяк. Но в наборе о прокате велосипедов, к которому мы вернёмся ниже, строк $17\,379$ , а в настоящих задачах их бывают миллионы и миллиарды. Прикинем цену. Один шаг полного градиента — это $n$ вычислений $\nabla\ell_i$ , а спуску до минимума нужны сотни шагов. Для проката триста шагов обходятся в пять миллионов вычислений градиента; для базы в миллиард строк один-единственный шаг стоил бы миллиард. Каждый шаг просматривает всю базу целиком, прежде чем сдвинуть веса хоть на волосок. Возникает вопрос, который и породил современное обучение: нельзя ли шагать, не опрашивая всех?

Заметим важное: слагаемые в сумме похожи. Тысяча тёплых июльских часов рассказывают о связи температуры и спроса примерно одно и то же. Опросив всю тысячу, мы уточняем направление, но не меняем его. А раз так — стоит ли платить за полный опрос?

Стохастическая оценка градиента

Идея дерзкая: возьмём вместо всей суммы одно случайное слагаемое. Градиент по одному примеру $\nabla\ell_i$ — это ещё не настоящий градиент. Но если пример выбран честной монеткой, в среднем он совпадает с настоящим:

\mathbb E_i\big[\nabla\ell_i(w)\big]=\frac1n\sum_{i=1}^{n}\nabla\ell_i(w) =\nabla L(w).

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

Разберёмся, что значит «в среднем». Несмещённость — это утверждение об ожидании: если бы мы повторили случайный выбор бесконечно много раз и усреднили, получили бы точный градиент. У любого конкретного шага есть отклонение от истины — разброс, дисперсия оценки. Спуск живёт между двумя этими величинами: смещения нет, поэтому длинная серия шагов ведёт куда надо, а разброс делает путь извилистым. Вся механика SGD — это управление разбросом при сохранении несмещённости. Ключевой вопрос — насколько велик разброс? Проверим на реальных данных: возьмём случайные батчи разного размера и измерим, куда указывает их градиент по сравнению с истинным.

Столбчатая диаграмма средней близости батч-градиента к истинному направлению для батчей размера 1, 8, 64 и 512; для одного примера косинус 0,47 и вниз ведёт 80 процентов оценок, для восьми 0,87 и 99 процентов, для 64 — 0,98 и все 100 процентов, для 512 — единица — Рис. 24.1. Куда ведёт случайный батч
Даже один-единственный случайный пример указывает вниз чаще, чем вверх: в $80\%$ случаев его градиент образует острый угол с истинным. Горсть из восьми примеров почти всегда права ( $99\%$ ), а батч из $64$ совпадает с истинным направлением на $98\%$ — при том что истинный посчитан по всем $17\,379$ строкам.

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

УпражнениеНесмещённость на трёх примерах

Пусть объектов всего три, и градиенты потери по ним в текущей точке равны $\nabla\ell_1=(2,0)$ , $\nabla\ell_2=(-1,3)$ , $\nabla\ell_3=(2,-3)$ . Чему равен полный градиент? Какое среднее значение даёт случайный выбор одного примера равновероятной монеткой? Может ли отдельный выбор указать в сторону, противоположную полному градиенту?

Сверить вычисление

Полный градиент — среднее трёх: $\big((2-1+2)/3,\,(0+3-3)/3\big)=(1,0)$ . Ожидание при равновероятном выборе одного примера — то же самое среднее $(1,0)$ : оценка несмещённая. Но отдельный выбор $\nabla\ell_2=(-1,3)$ по первой координате направлен противоположно полному градиенту $(1,0)$ — именно поэтому один шаг может навредить, хотя серия шагов в среднем ведёт верно.

Мини-батч: золотая середина

Между двумя крайностями — один пример и вся база — лежит мини-батч. Его размер $m$ управляет сделкой между скоростью и точностью. Оценка градиента по $m$ независимым примерам имеет разброс, убывающий как $1/m$ , а типичное отклонение направления — как $1/\sqrt m$ . Учетверив батч, мы вдвое уменьшаем шум, но вчетверо повышаем цену шага. Диаграмма выше — это правило в числах: переход от одного примера к восьми поднял точность резче, чем от $64$ к $512$ . Первые примеры сообщают о направлении много, следующие — всё меньше нового.

Оттого почти всегда выбирают именно мини-батч: он ловит выгоду параллельного железа и держит шум умеренным. Чистый SGD по одному примеру интересен как предельный случай, обнажающий природу шума.

Заодно уточним словарь. Один проход по всем данным называют эпохой. Обычно данные перед каждой эпохой перемешивают и режут на мини-батчи, так что за эпоху веса обновляются $n/m$ раз: при $n=17\,379$ и батче $64$ — двести семьдесят раз за один проход, тогда как полный градиент за тот же проход шагнёт единожды.

УпражнениеНасколько тише большой батч

Типичное отклонение оценки градиента от истинного направления убывает как $1/\sqrt m$ . Во сколько раз спокойнее батч из $100$ примеров по сравнению с одиночным SGD? А во сколько дороже обходится его шаг? Стоит ли увеличивать батч со $100$ до $400$ ?

Сверить рассуждение

Шум падает как $1/\sqrt m$ : батч $100$ тише одиночного в $\sqrt{100}=10$ раз, а его шаг в $100$ раз дороже. Переход со $100$ до $400$ учетверяет цену, но снижает шум лишь вдвое ( $\sqrt{400}/\sqrt{100}=2$ ). Отдача от роста батча тает — оттого батчи и держат умеренными, редко больше нескольких сотен.

На реальных данных: спуск по прокату велосипедов

Спустимся по настоящей чаше. Возьмём почасовые данные о прокате велосипедов и будем предсказывать число поездок по температуре, обе величины приведём к общему масштабу. Потеря MSE над двумя параметрами (сдвиг $w_0$ и наклон $w_1$ ) — выпуклая чаша с минимумом в наклоне $0{,}40$ : это та же корреляция температуры и спроса. Пустим из одной точки три спуска.

Контурная карта чашеобразной потери; из общей стартовой точки идут три траектории к минимуму: гладкая ломаная полного градиента, слегка дрожащая линия мини-батча из 64 и сильно петляющее облако одиночного SGD, которое всё же вьётся вокруг минимума — Рис. 24.2. Три спуска по одной чаше
Полный градиент (чёрный) катится к минимуму гладко. Мини-батч из $64$ (синий) идёт почти по той же дороге с лёгким дрожанием. Одиночный SGD (золотой) петляет диким облаком — но и оно вьётся вокруг минимума, а не разбегается. Шум сбивает каждый отдельный шаг, однако общее направление выдержано.

Теперь сравним не по числу шагов, а по числу просмотренных строк — это и есть настоящая цена вычислений.

Потеря на всех данных против числа обработанных примеров в логарифмическом масштабе; мини-батч и SGD резко снижают потерю уже в пределах первого прохода по данным, тогда как полный градиент к этому моменту сделал лишь один шаг и почти не сдвинулся; вертикальная линия отмечает один проход по данным — Рис. 24.3. Кто быстрее спускается на единицу вычислений
Пунктир отмечает один полный проход по данным. К этому моменту мини-батч уже почти на дне (потеря $0{,}84$ при минимуме $0{,}84$ ), а полный градиент сделал всего один шаг и едва тронулся с места (потеря $1{,}36$ ). Стохастический спуск вытаскивает хорошую модель из первого же прохода, пока полный градиент только разминается.

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

УпражнениеКто просмотрел больше строк

Полный градиент делает $50$ шагов по базе из $17\,379$ строк. Одиночный SGD делает один проход по данным. Сколько строк просмотрел каждый и сколько обновлений весов сделал? Что это говорит о цене одного обновления?

Сверить подсчёт

Полный градиент: $50$ шагов, каждый читает все $17\,379$ строк — это $868\,950$ просмотров и всего $50$ обновлений. SGD: один проход — $17\,379$ просмотров и $17\,379$ обновлений. За одну пятидесятую вычислительной работы SGD сделал в $347$ раз больше обновлений. Каждое из них грубее, но их несопоставимо больше, и в сумме модель улучшается быстрее на единицу потраченных вычислений.

Скорость обучения и её угасание

У шума есть цена. Одиночный SGD с постоянным шагом не оседает в минимуме, а вечно пляшет вокруг него: даже у самого дна очередной случайный пример толкает вес в сторону. Чтобы спуск успокоился, шаг $\eta_t$ нужно постепенно гасить.

Точное требование к расписанию шагов сформулировали Роббинс и Монро:

\sum_{t=1}^{\infty}\eta_t=\infty,\qquad \sum_{t=1}^{\infty}\eta_t^2<\infty.

Первое условие велит не тормозить слишком рано, чтобы дойти до минимума из любой точки. Второе велит гасить достаточно быстро, чтобы шум в пределе затих. Расписание $\eta_t=\eta_0/t$ обоим условиям отвечает; постоянный шаг — нет, оттого он и дрожит.

УпражнениеКакое расписание успокоится

Разберите три расписания шага: постоянное $\eta_t=\eta_0$ , «корневое» $\eta_t=\eta_0/\sqrt t$ и «обратное» $\eta_t=\eta_0/t$ . Для каждого скажите, уводит ли сумма шагов сколь угодно далеко и сходится ли сумма их квадратов. Какое из трёх гарантирует, что SGD осядет в минимуме?

Сверить разбор

Постоянный шаг: $\sum\eta_0=\infty$ (годится), но $\sum\eta_0^2=\infty$ — второе условие нарушено, спуск дрожит вечно. Корневой: $\sum 1/\sqrt t$ расходится (годится), а $\sum 1/t$ тоже расходится — второе условие снова нарушено. Обратный $\eta_0/t$ : $\sum 1/t$ расходится (годится), $\sum 1/t^2$ сходится (годится) — оба условия выполнены, только он и гарантирует оседание в минимуме. Оттого гармонический ряд, расходящийся чуть-чуть, и оказался золотой серединой между «дойти» и «затихнуть».

Шум как помощник

Есть у стохастического шума и неожиданная польза. В прошлых уроках мы видели, что потеря настоящей сети невыпукла: она изрыта мелкими локальными ямами-ловушками, а в многомерном ландшафте — ещё и сёдлами, где спуск замирает на плоском гребне (о них — урок про седловые задачи). Гладкий полный градиент, скатившись в такую яму, застревает — вокруг всё идёт вверх. А шумный шаг SGD может случайно перескочить невысокий бугор и выбраться к более глубокому минимуму.

Здесь виден и смысл угасающего шага с другой стороны. В начале обучения крупный шумный шаг полезен: он широко рыщет по ландшафту и не даёт застыть в первой попавшейся яме. Ближе к концу шум только мешает точной посадке, и его гасят. Это напоминает отжиг в металлургии: разогретый металл свободно перестраивает решётку, а медленное остывание закрепляет её в низкоэнергетическом состоянии. Стохастический спуск с убывающим шагом — такой же отжиг, только в пространстве весов.

Так недостаток оборачивается достоинством. Дешевизна, скорость на больших данных и способность выбираться из ловушек — из-за них стохастический спуск и стал рабочей лошадью обучения нейросетей.

Русская линия: обучение как стохастическая аппроксимация

Метод Роббинса и Монро $1951$ года родился в статистике, вдали от нейросетей. Связать его с обучением машин выпало советскому учёному Якову Залмановичу Цыпкину. В книгах об адаптации и обучении в автоматических системах он показал, что настройка почти любой обучающейся системы — распознавателя, регулятора, фильтра — сводится к рекуррентной стохастической аппроксимации оптимума по зашумлённым наблюдениям.

Единый взгляд Цыпкина объяснил, почему один и тот же приём — маленький шаг против шумной оценки градиента — годится и для линейной регрессии, и для перцептрона, и для глубокой сети. Современный SGD с мини-батчами и расписанием шага — прямой потомок этой идеи.

Русская линия на этом не кончается. Уже знакомый по прошлому уроку Борис Поляк предложил простой способ погасить дрожание, не жертвуя скоростью: усреднять не саму траекторию, а пройденные точки. Пока веса пляшут вокруг минимума, их скользящее среднее указывает на дно куда точнее любого отдельного шага. Этот приём — усреднение Поляка — лежит в основе и того сглаживания, которым мы получили аккуратные кривые потерь выше, и приёмов вроде экспоненциального среднего в современных оптимизаторах.

Лаборатория стохастического спуска

Порядок опытов. Перед вами чаша потерь настоящих данных о прокате. Выберите размер батча и посмотрите на характер спуска: полный градиент идёт гладко, но каждый его шаг просматривает все строки; батч из $64$ почти так же меток и куда дешевле; один пример мчится, но петляет. Прокрутите скорость обучения: слишком большая — траектория разлетается, слишком малая — ползёт. Наконец, переключите шаг на убывающий и убедитесь, что дрожащий у дна SGD успокаивается и оседает в минимуме. Табло считает, сколько строк уже просмотрено и на сколько проходов по данным это тянет.

Сборка: горсть примеров вместо всей базы

Стохастический спуск вырос из одной догадки: чтобы шагнуть вниз, не нужно опрашивать все данные — хватает случайной горсти. Её градиент шумен, но несмещён, и даже один пример указывает вниз чаще, чем вверх; батч из $64$ почти неотличим от истинного направления. Оттого мини-батчевый спуск вытягивает хорошую модель из первого же прохода по данным, тогда как полный градиент только делает первый шаг. Платой служит вечное дрожание у дна — его лечат угасанием шага по условиям Роббинса—Монро, а Цыпкин показал, что всё это и есть обучение как стохастическая аппроксимация. Тот же шум, что мешает осесть, помогает выбираться из мелких ловушек невыпуклой потери. Осталась последняя, самая техническая деталь: как вообще посчитать $\nabla\ell_i$ для сети из многих слоёв? Ответ — обратное распространение ошибки, и с него начинается следующий разговор.

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