Стохастический градиентный спуск (SGD)
- Автор метода
- Robbins, H. & Monro, S.
- Год
- 1951
- Тип
- First-order iterative optimization algorithm
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Стохастический градиентный спуск (SGD) — это итерационный алгоритм оптимизации первого порядка, основанный на каркасе стохастической аппроксимации, введенном Роббинсом и Монро в 1951 году, который минимизирует целевую функцию путем обновления параметров модели с использованием градиента, вычисленного на одном случайно выбранном обучающем примере (или небольшом мини-батче) на каждом шаге.
Это основной оптимизационный механизм современных машинного обучения и глубокого обучения, позволяющий обучать модели на наборах данных, слишком больших для размещения в памяти.
Интуиция метода
Обычный градиентный спуск вычисляет точный градиент потерь по всем обучающим примерам перед выполнением одного обновления параметра — это корректно, но непомерно медленно на больших наборах данных. SGD жертвует точностью ради скорости: он выбирает один пример (или небольшой пакет) случайным образом, вычисляет зашумленную оценку градиента и немедленно обновляет параметры. Шум — это не просто помеха; он действует как неявная регуляризация, помогая оптимизатору избежать мелких локальных минимумов и седловых точек. За многие итерации зашумленные шаги усредняются, и параметры сходятся к минимуму потерь, подобно блужданиям пьяного, который все же достигает пункта назначения.
История
Теоретическая основа SGD была заложена Гербертом Роббинсом и Саттоном Монро в их статье 1951 года «Метод стохастической аппроксимации», в которой было доказано, что итеративные зашумленные обновления с затухающим размером шага сходятся к корню регрессионной функции. Связь с оптимизацией на основе градиента была явно установлена Кифером и Вольфовицем (1952), а затем правилом LMS Видроу и Хоффа (1960) для адаптивной фильтрации. SGD приобрел известность в машинном обучении благодаря работе ЛеКуна и его коллег в конце 1980-х и 1990-х годов по обучению нейронных сетей с помощью обратного распространения ошибки. Публикация крупномасштабных экспериментов Ботту и его коллег в 2000-х годах продемонстрировала превосходство SGD над пакетными методами на промышленных наборах данных. Современная формулировка мини-батч SGD стала универсальной с ренессансом глубокого обучения около 2012 года (AlexNet), и алгоритм остается доминирующим оптимизатором в этой области, с вариантами, такими как Adam (Kingma & Ba, 2014), построенными непосредственно на его правиле обновления.
Когда применять
SGD является предпочтительным методом, когда обучающий набор данных достаточно велик, чтобы вычисление полного градиента за одно обновление было слишком затратным, что охватывает практически все современные методы обучения нейронных сетей и подгонки линейных моделей в большом масштабе. Он применим к любой дифференцируемой функции потерь. Ключевые предположения: потери дифференцируемы (или субдифференцируемы) по отношению к параметрам, точки данных выбираются независимо, и оценщик градиента несмещен. Для сильно выпуклых целевых функций SGD достигает сходимости O(1/T); для общих невыпуклых целевых функций (например, глубоких сетей) на практике он находит стационарные точки, хотя гарантии глобальной оптимальности не существует. Мини-батч SGD (размеры пакетов 32–512) обычно предпочтительнее чистого SGD по одному примеру, поскольку он обеспечивает оценки градиента с меньшей дисперсией и использует параллелизм на современном оборудовании. Когда набор данных достаточно мал для градиентного спуска по полному пакету, а целевая функция хорошо обусловлена, методы второго порядка, такие как L-BFGS, могут сходиться быстрее.
Ограничения и замечания
- Оценки градиента зашумлены, что приводит к колебаниям потерь, а не к их монотонному снижению, затрудняя диагностику сходимости.
- Очень чувствителен к скорости обучения: слишком большая вызывает расходимость; слишком маленькая делает обучение непомерно медленным.
- Сходимость к глобальному минимуму не гарантируется для невыпуклых целевых функций, таких как глубокие нейронные сети.
- Изотропные обновления обрабатывают все размерности параметров одинаково, что делает его плохо подходящим для поверхностей потерь с очень разной кривизной вдоль разных осей — что мотивирует варианты с адаптивной скоростью.
- Требует тщательной настройки расписания скорости обучения; плохие расписания существенно ухудшают конечную производительность.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Масштабируется до произвольно больших наборов данных, поскольку каждое обновление требует только одного примера или мини-батча, сохраняя постоянный объем памяти и вычислений на шаг.
- Встроенный шум обеспечивает неявную регуляризацию и помогает избежать мелких локальных минимумов и седловых точек в невыпуклых ландшафтах.
- Чрезвычайно универсален: применим к любым дифференцируемым потерям, включая перекрестную энтропию, среднеквадратичную ошибку, шарнирную потерю и пользовательские целевые функции.
- Является основой почти всех современных оптимизаторов (Adam, RMSProp, AdaGrad, Nesterov momentum) — понимание SGD является предпосылкой для их понимания.
- Прост в реализации и распараллеливании на GPU с использованием мини-батчей.
Применение
- Обучение глубоких нейронных сетей для классификации изображений, распознавания речи и обработки естественного языка.
- Подгонка крупномасштабных моделей логистической регрессии и линейных SVM в задачах классификации текста и рекомендательных системах.
- Параметры онлайн-обучения, где примеры поступают последовательно, и модель должна обновляться в реальном времени.
- Методы градиента политики в обучении с подкреплением, где ожидаемая награда оптимизируется с использованием выборочных траекторий.
- Факторизация матриц для коллаборативной фильтрации в рекомендательных системах.
Как это работает
Как это работает
Цель обучения — средние потери по всем n примерам. Для таких задач, как классификация с перекрестной энтропией или регрессия с квадратичной ошибкой, эта сумма может содержать миллиарды членов, что делает полную оценку на каждой итерации непрактичной.
Формула
L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(x_i; \theta),\, y_i)На шаге t случайным образом равномерно выбирается один обучающий пример (или мини-батч). Градиент потерь по этому образцу является несмещенной оценкой истинного градиента, поэтому в среднем обновление указывает в правильном направлении, хотя и является зашумленным для любого отдельного шага.
Формула
\hat{g}_t = \nabla_\theta \ell(f(x_{i_t}; \theta_t),\, y_{i_t})Вектор параметров перемещается в направлении, противоположном оценке градиента, масштабированной скоростью обучения eta_t. Меньшая скорость обучения делает обновления осторожными, но медленными; большая скорость ускоряет сходимость, но рискует перескочить минимум. Эта одна строка — обновление Роббинса–Монро — является сердцем почти каждого современного оптимизатора.
Формула
\theta_{t+1} = \theta_t - \eta_t \, \hat{g}_tУсловия Роббинса–Монро (сумма скоростей расходится, сумма квадратов скоростей сходится) гарантируют сходимость для выпуклых целевых функций. На практике распространенные расписания включают пошаговое снижение, косинусное отжиг и теплые перезапуски; условия обеспечивают теоретическое обоснование того, почему необходимо затухающее расписание.
Формула
\sum_{t=1}^{\infty} \eta_t = \infty, \quad \sum_{t=1}^{\infty} \eta_t^2 < \inftyЧастые ошибки
- Использование постоянной скорости обучения на протяжении всего обучения без какого-либо расписания затухания, что приводит к колебаниям оптимизатора вокруг минимума, а не к его достижению.
- Выбор размера пакета без учета эффекта неявной регуляризации: очень большие пакеты уменьшают шум и могут ухудшить обобщение по сравнению с меньшими пакетами при том же количестве эпох.
- Забывание перемешать обучающие данные перед каждой эпохой, что может привести к систематической ошибке, когда данные упорядочены по классам или времени.
- Настройка скорости обучения только по потерям валидации один раз вместо мониторинга кривых обучения, пропуск признаков расходимости или преждевременного плато.
- Рассмотрение SGD как оптимизатора «черного ящика» без понимания его свойств сходимости, а затем слепое переключение на Adam, когда сходимость кажется медленной, без диагностики первопричины.
Часто задаваемые вопросы
В чем разница между SGD, мини-батч SGD и градиентным спуском по полному пакету?
Градиентный спуск по полному пакету вычисляет точный градиент по всем n обучающим примерам за одно обновление — точная, но затратная по O(n) стоимость за шаг. Чистый SGD использует ровно один случайно выбранный пример за обновление — стоимость O(1), но очень зашумленный. Мини-батч SGD использует небольшую случайную подвыборку (обычно 32–512 примеров) — практический компромисс, который уменьшает шум, сохраняя при этом управляемую стоимость и используя параллелизм GPU. В современном использовании «SGD» почти всегда означает мини-батч SGD.
Как следует установить скорость обучения?
Универсального ответа нет, но распространенной практикой является начало с умеренного значения (например, 0.01 или 0.1), мониторинг кривой потерь обучения и применение расписания затухания, такого как пошаговое снижение, косинусное отжиг или теплые перезапуски. Поиск скорости обучения (проверка скоростей на нескольких пакетах и наблюдение за потерями) может помочь определить хорошее начальное значение. Теория Роббинса–Монро требует, чтобы скорость затухала до нуля, но на практике затухание часто применяется мягко, чтобы избежать преждевременного замедления.
Почему SGD иногда обобщает лучше, чем Adam?
Адаптивные оптимизаторы, такие как Adam, часто сходятся быстрее, но могут переобучаться больше, особенно в задачах классификации изображений. Более высокий шум в SGD — особенно при малых размерах пакетов — действует как неявная регуляризация, помогая модели находить более плоские минимумы, которые лучше обобщаются. Несколько эмпирических исследований (например, Wilson et al., 2017) задокументировали это явление, поэтому SGD с моментом по-прежнему предпочтителен для обучения моделей компьютерного зрения, таких как ResNet.
Гарантирует ли SGD нахождение глобального минимума?
Только для строго выпуклых целевых функций при условиях размера шага Роббинса–Монро. Для невыпуклых целевых функций (практически все глубокие сети) SGD обеспечивает сходимость к стационарной точке (где градиент равен нулю), которая на практике, как правило, является хорошим локальным минимумом, а не седловой точкой или глобальным минимумом. Эмпирически найденные решения часто оказываются достаточно хорошими для достижения передовых результатов.
Похожие методы
Источники
Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.
Открыть ссылку DOIСкопировано.Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning (Ch. 8). MIT Press.
ISBN: 978-0-262-03561-3Скопировано.