144 lines
7.9 KiB
Markdown
144 lines
7.9 KiB
Markdown
# 2. GD, SGD, momentum, RMSProp и Adam
|
||
|
||
> Оптимизаторы различаются тем, какие данные используют на шаге и как преобразуют историю градиентов.
|
||
|
||
## Мотивация
|
||
|
||
Полный градиент точен, но дорог на миллионах объектов. Стохастический градиент дешёв, но шумен. Momentum сглаживает направление, RMSProp адаптирует масштаб координат, Adam сочетает обе идеи. Выбор шага и корректная реализация зачастую важнее названия оптимизатора.
|
||
|
||
## Интуиция
|
||
|
||
GD измеряет наклон по всей выборке. SGD использует один случайный объект, mini-batch — компромисс, хорошо использующий векторные вычисления. Шум mini-batch мешает точной сходимости, но ускоряет ранний прогресс. Momentum накапливает «скорость». RMSProp делит шаг на корень из недавних квадратов градиента. Adam ведёт экспоненциальные средние градиента и его квадрата и исправляет их начальное смещение к нулю.
|
||
|
||
## Определения и обозначения
|
||
|
||
Пусть \(L(\boldsymbol\theta)=n^{-1}\sum_i\ell_i(\boldsymbol\theta)\), итерация \(t\), learning rate \(\eta_t>0\), mini-batch \(\mathcal B_t\) размера \(m\):
|
||
|
||
\[
|
||
\mathbf g_t=\frac1m\sum_{i\in\mathcal B_t}\nabla\ell_i(\boldsymbol\theta_t).
|
||
\]
|
||
|
||
При равномерной выборке \(\mathbb E[\mathbf g_t\mid\boldsymbol\theta_t]=\nabla L(\boldsymbol\theta_t)\). Эпоха — обработка примерно \(n\) примеров.
|
||
|
||
## Вывод алгоритмов
|
||
|
||
**GD/SGD/mini-batch:**
|
||
|
||
\[
|
||
\boldsymbol\theta_{t+1}=\boldsymbol\theta_t-\eta_t\mathbf g_t.
|
||
\]
|
||
|
||
GD берёт \(m=n\), классический SGD — \(m=1\). Для квадратичной \(L(\theta)=a\theta^2/2\):
|
||
|
||
\[
|
||
\theta_{t+1}=(1-\eta a)\theta_t.
|
||
\]
|
||
|
||
Сходимость требует \(|1-\eta a|<1\), то есть \(0<\eta<2/a\). В многомерной квадратичной задаче безопасный постоянный шаг связан с \(2/\lambda_{\max}(\mathbf H)\).
|
||
|
||
**Momentum** в одной распространённой записи:
|
||
|
||
\[
|
||
\mathbf v_t=\beta\mathbf v_{t-1}+(1-\beta)\mathbf g_t,\qquad
|
||
\boldsymbol\theta_{t+1}=\boldsymbol\theta_t-\eta\mathbf v_t.
|
||
\]
|
||
|
||
Некоторые библиотеки не используют множитель \(1-\beta\); тогда эффективный масштаб \(\eta\) другой.
|
||
|
||
**RMSProp:**
|
||
|
||
\[
|
||
\mathbf s_t=\rho\mathbf s_{t-1}+(1-\rho)\mathbf g_t\odot\mathbf g_t,
|
||
\qquad
|
||
\boldsymbol\theta_{t+1}=\boldsymbol\theta_t-
|
||
\eta\frac{\mathbf g_t}{\sqrt{\mathbf s_t}+\varepsilon}.
|
||
\]
|
||
|
||
**Adam:**
|
||
|
||
\[
|
||
\begin{aligned}
|
||
\mathbf m_t&=\beta_1\mathbf m_{t-1}+(1-\beta_1)\mathbf g_t,\\
|
||
\mathbf v_t&=\beta_2\mathbf v_{t-1}+(1-\beta_2)\mathbf g_t^2,\\
|
||
\hat{\mathbf m}_t&=\mathbf m_t/(1-\beta_1^t),\\
|
||
\hat{\mathbf v}_t&=\mathbf v_t/(1-\beta_2^t),\\
|
||
\boldsymbol\theta_{t+1}
|
||
&=\boldsymbol\theta_t-\eta\hat{\mathbf m}_t/
|
||
(\sqrt{\hat{\mathbf v}_t}+\varepsilon).
|
||
\end{aligned}
|
||
\]
|
||
|
||
Операции во второй момент и делении поэлементные. Bias correction нужен, потому что нулевая инициализация занижает ранние моменты.
|
||
|
||
## Разобранный пример
|
||
|
||
**Дано.** \(L(\theta)=\frac12(\theta-3)^2\), \(\theta_0=0\), \(\eta=0{,}5\).
|
||
|
||
**Решение.** \(g_t=\theta_t-3\). GD:
|
||
\(\theta_1=0-0{,}5(-3)=1{,}5\);
|
||
\(\theta_2=1{,}5-0{,}5(-1{,}5)=2{,}25\);
|
||
\(\theta_3=2{,}625\).
|
||
Ошибка каждый шаг умножается на \(1-\eta=0{,}5\), поэтому стремится к нулю геометрически.
|
||
|
||
**Проверка.** При \(\eta=2\) параметры чередуются между 0 и 6 и не сходятся; при \(\eta>2\) расходятся.
|
||
|
||
## Связь с Python и NumPy
|
||
|
||
```python
|
||
import numpy as np
|
||
|
||
rng = np.random.default_rng(42)
|
||
X = rng.normal(size=(200, 2))
|
||
true_w = np.array([2.0, -1.0])
|
||
y = X @ true_w + rng.normal(scale=0.2, size=200)
|
||
w = np.zeros(2)
|
||
m = np.zeros(2)
|
||
v = np.zeros(2)
|
||
beta1, beta2, lr, eps = 0.9, 0.999, 0.05, 1e-8
|
||
|
||
for t in range(1, 501):
|
||
idx = rng.choice(len(y), size=32, replace=False)
|
||
residual = X[idx] @ w - y[idx]
|
||
g = X[idx].T @ residual / len(idx)
|
||
m = beta1 * m + (1 - beta1) * g
|
||
v = beta2 * v + (1 - beta2) * (g * g)
|
||
m_hat = m / (1 - beta1 ** t)
|
||
v_hat = v / (1 - beta2 ** t)
|
||
w -= lr * m_hat / (np.sqrt(v_hat) + eps)
|
||
|
||
print("weights:", w, "full loss:", np.mean((X @ w - y) ** 2) / 2)
|
||
```
|
||
|
||
Перемешивание и seed делают стохастический эксперимент контролируемым. Loss для мониторинга лучше считать отдельно на train и validation.
|
||
|
||
## Практический выбор
|
||
|
||
Начните с масштабирования признаков и baseline. Для гладких небольших выпуклых задач полный GD или L-BFGS может быть эффективнее. Mini-batch выбирают по памяти и пропускной способности устройства. SGD с momentum часто даёт хорошую обобщающую способность; Adam быстро получает рабочий результат при разном масштабе градиентов. Learning-rate schedule (warmup, step decay, cosine) обычно важен. Gradient clipping ограничивает норму при взрывающихся градиентах, но не лечит первопричину.
|
||
|
||
## Типичные ошибки и ограничения
|
||
|
||
- Сравнивать оптимизаторы при разных бюджетах вычислений и без настройки \(\eta\).
|
||
- Считать Adam гарантированно лучшим или сходящимся во всех задачах.
|
||
- Забывать bias correction, \(\varepsilon\) или поэлементный квадрат.
|
||
- Использовать один случайный порядок данных и делать сильный вывод.
|
||
- Путать batch size с числом эпох.
|
||
- Оценивать качество только train loss: оптимизация и обобщение — разные задачи.
|
||
- Смешивать L2 в loss и decoupled weight decay: AdamW обновляет decay отдельно.
|
||
|
||
## Краткое резюме
|
||
|
||
- Mini-batch даёт несмещённый, но шумный градиент.
|
||
- Learning rate управляет устойчивостью и скоростью.
|
||
- Momentum усредняет направление, RMSProp — квадрат масштаба, Adam — оба момента.
|
||
- Оптимизатор нужно сравнивать по validation-метрике и вычислительному бюджету.
|
||
|
||
## Связанные материалы
|
||
|
||
- Практика: [`../assignments/01_gradient_descent.md`](../assignments/01_gradient_descent.md).
|
||
- Практика: [`../assignments/02_logistic_from_scratch.md`](../assignments/02_logistic_from_scratch.md).
|
||
|
||
- Поверхности: [`01_derivatives_and_loss_surfaces.md`](01_derivatives_and_loss_surfaces.md).
|
||
- Следующая глава: [`03_regularization_bias_variance.md`](03_regularization_bias_variance.md).
|
||
- Численная устойчивость: [`../../../common/foundations/numerical_stability.md`](../../../common/foundations/numerical_stability.md).
|
||
- Термины: [`glossary.md`](glossary.md).
|