5장. 경사하강법과 뉴턴 방법

임계점을 연립방정식 $\nabla f = \mathbf{0}$ 으로 풀 수 없을 때(신경망은 파라미터가 수십억 개입니다), 컴퓨터는 산을 내려가듯 조금씩 움직여 최솟값을 찾습니다. 이 장에서는 가장 기본적인 방법인 경사하강법을 다루고, 학습률을 어떻게 고르는지, 왜 길쭉한 골짜기에서 느린지(조건수), 이를 고치는 모멘텀과 뉴턴 방법을 봅니다. 머신러닝 논문의 “optimizer” 부분이 모두 이 장의 이야기입니다.

5.1 경사하강법

2장의 정리 2.8에 따라 $-\nabla f$ 는 가장 가파르게 내려가는 방향입니다. 그 방향으로 조금씩 움직입니다.

정의 5.1 (경사하강법). 시작점 $\mathbf{x}_0$ 에서

\mathbf{x}_{k+1} = \mathbf{x}_k - \eta\,\nabla f(\mathbf{x}_k)

를 되풀이하는 방법을 경사하강법(gradient descent)이라 하고, 보폭 $\eta > 0$ 을 학습률(learning rate)이라 합니다.

예제 5.2. $f(x) = x^2$ (한 변수), $\eta = 0.1$ , $x_0 = 1$ : $x_{k+1} = x_k - 0.2x_k = 0.8x_k$ 이므로 $x_k = 0.8^k \to 0$ . $\eta = 1.1$ 이면 $x_{k+1} = -1.2x_k$ 로 부호를 바꾸며 커져 발산합니다.

5.2 이차함수에서의 수렴

이차함수는 모든 함수의 극소점 근처 모습(4장의 이차 근사)이므로, 이차함수에서의 행동이 일반적인 행동을 대표합니다.

정리 5.3. $f(\mathbf{x}) = \frac12\mathbf{x}^TA\mathbf{x}$ ( $A$ 는 대칭·양정치, 고윳값 $0 < \lambda_{\min} \le \cdots \le \lambda_{\max}$ )이면 경사하강법은

\mathbf{x}_{k+1} = (I - \eta A)\mathbf{x}_k

이고, $0 < \eta < 2/\lambda_{\max}$ 일 때 그리고 그때만 $\mathbf{0}$ 으로 수렴합니다.

증명. $\nabla f = A\mathbf{x}$ 입니다. $A$ 의 고유벡터 좌표에서 각 성분은 $(1 - \eta\lambda_i)$ 배씩 줄어듭니다. 모든 $i$ 에서 $|1 - \eta\lambda_i| < 1$ , 곧 $0 < \eta\lambda_i < 2$ 이어야 하고, 가장 엄격한 조건은 $\lambda_{\max}$ 에서 나옵니다. □

가장 좋은 $\eta$ 를 골라도, 가장 느린 방향의 수축 비율은

\frac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} = \frac{\kappa - 1}{\kappa + 1}, \qquad \kappa = \frac{\lambda_{\max}}{\lambda_{\min}}

입니다. $\kappa$ 는 조건수(condition number, 선형대수 30장)입니다. 등위선이 원에 가까우면( $\kappa \approx 1$ ) 한두 번에 도착하고, 길쭉한 타원이면( $\kappa$ 가 크면) 가파른 방향으로는 튀고 평평한 방향으로는 기어서 지그재그로 느립니다. 위젯에서 $x^2 + 3y^2$ ( $\kappa = 3$ )와 $x^2 + y^2$ ( $\kappa = 1$ )을 비교해 보면 보입니다.

예제 5.4. $f = \frac12(x^2 + 9y^2)$ , 곧 $A = \operatorname{diag}(1, 9)$ . 수렴하려면 $\eta < 2/9 \approx 0.222$ 입니다. $\kappa = 9$ 이므로 가장 좋은 $\eta = 2/(1 + 9) = 0.2$ 에서도 매번 $\frac{8}{10} = 0.8$ 배씩만 줄어듭니다.

이것이 데이터의 특징을 정규화(평균 0, 분산 1로 맞춤)하면 학습이 빨라지는 이유입니다. 정규화는 손실의 등위선을 원에 가깝게 만들어 $\kappa$ 를 줄입니다.

5.3 확률적 경사하강법과 모멘텀

머신러닝의 손실은 데이터 하나하나의 손실의 평균 $L = \frac1N\sum_{i=1}^N\ell_i$ 입니다. $N$ 이 수백만이면 $\nabla L$ 을 정확히 구하는 것이 비쌉니다.

정의 5.5 (확률적 경사하강법). 매 단계 데이터 몇 개(미니배치 $B$ )를 무작위로 골라 $\frac{1}{|B|}\sum_{i\in B}\nabla\ell_i$ 로 그래디언트를 어림해 씁니다. 이것을 확률적 경사하강법(stochastic gradient descent, SGD)이라 합니다.

미니배치 그래디언트의 기댓값은 진짜 그래디언트와 같습니다(이산수학 13강의 기댓값의 선형성). 대신 잡음이 섞이므로 학습률을 점점 줄여 가는 일이 많습니다.

정의 5.6 (모멘텀). 속도 $\mathbf{v}$ 를 두고

\mathbf{v}_{k+1} = \beta\mathbf{v}_k + \nabla f(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k - \eta\mathbf{v}_{k+1}

로 움직입니다( $0 \le \beta < 1$ , 보통 0.9). 지그재그 방향의 그래디언트는 서로 상쇄되고, 꾸준한 방향은 쌓여 빨라집니다. 무거운 공이 골짜기를 굴러 내려가는 모습입니다.

논문에 자주 나오는 Adam은 모멘텀에 더해 성분마다 그래디언트 크기의 이동평균으로 나눠 보폭을 맞추는 방법입니다. 성분마다 학습률을 따로 정해 조건수 문제를 줄이려는 것입니다.

5.4 뉴턴 방법

이차 근사(4장)를 쓰면 한 번에 그 근사의 최소점으로 갈 수 있습니다.

정의 5.7 (뉴턴 방법). $\mathbf{x}_{k+1} = \mathbf{x}_k - H(\mathbf{x}_k)^{-1}\nabla f(\mathbf{x}_k)$ .

$f(\mathbf{x}_k + \mathbf{h}) \approx f + \nabla f\cdot\mathbf{h} + \frac12\mathbf{h}^TH\mathbf{h}$ 를 $\mathbf{h}$ 로 미분해 0으로 두면 $H\mathbf{h} = -\nabla f$ 이기 때문입니다. 미적분학 6장의 뉴턴 방법( $f'$ 의 근 찾기)을 여러 변수로 넓힌 것입니다.

이차함수에서는 한 번에 최소점에 도착합니다(조건수와 상관없이).
극소점 근처에서는 2차 수렴(맞는 자릿수가 매번 두 배)합니다.
대신 매 단계 $n \times n$ 헤세 행렬을 구하고 연립방정식을 풀어야 하므로, 변수가 많으면 비쌉니다. 그래서 큰 신경망에는 경사하강법 계열을, 변수가 적은 문제(통계 모델 적합 등)에는 뉴턴 방법을 씁니다.

예제 5.8. $f = \frac12(x^2 + 9y^2)$ , $\mathbf{x}_0 = (1, 1)$ . $\nabla f = (1, 9)$ , $H = \operatorname{diag}(1, 9)$ 이므로 $\mathbf{x}_1 = (1, 1) - (1, 1) = (0, 0)$ . 한 번에 도착합니다.

5.5 이 장의 요약

경사하강법 $\mathbf{x} \leftarrow \mathbf{x} - \eta\nabla f$ . 이차함수에서 $\eta < 2/\lambda_{\max}$ .
수렴 속도는 조건수 $\kappa$ 가 정합니다. 길쭉한 골짜기에서 느립니다.
SGD는 그래디언트를 미니배치로 어림합니다. 모멘텀은 지그재그를 줄입니다. 뉴턴 방법은 헤세 행렬로 한 번에 갑니다.

쓰이는 곳. 머신러닝 논문의 학습 설정(optimizer: SGD, momentum, Adam, learning rate schedule, warmup)은 모두 이 장의 개념입니다. 학습이 발산하면 학습률이 $2/\lambda_{\max}$ 보다 크지 않은지 의심합니다. 배치 정규화와 입력 정규화는 조건수를 줄이는 장치로 해석됩니다. 물리 시뮬레이션의 에너지 최소화와 통계의 최대우도 추정도 같은 알고리즘을 씁니다.

문제

5.1 [계산] · 확인 문제

$f(x, y) = x^2 + 3y^2$ 에 시작점 $(2, 1)$ , 학습률 $\eta = 0.1$ 로 경사하강법을 한 번 적용한 점을 씁니다.

좌표	값
$x_1$	[?]
$y_1$	[?]

정답

1.6
0.4

풀이

$\nabla f = (2x, 6y) = (4, 6)$ 이므로 $(2, 1) - 0.1(4, 6) = (1.6, 0.4)$ 입니다.

5.2 [계산] · 확인 문제

$f(x, y) = 2x^2 + 8y^2$ 에 경사하강법이 수렴하는 학습률 $\eta$ 의 상한( $\eta <$ 이 값)은?

힌트 1

$f = \frac12\mathbf{x}^TA\mathbf{x}$ 로 쓰면 $A = \operatorname{diag}(4, 16)$ 입니다.

정답

1/8

풀이

$\lambda_{\max} = 16$ 이므로 $\eta < 2/16 = 1/8$ 입니다.

5.3 [계산] · 확인 문제

$f = \frac12\mathbf{x}^TA\mathbf{x}$ 의 $A$ 고윳값이 1과 100일 때, 가장 좋은 학습률에서 한 단계마다 줄어드는 비율 $\frac{\kappa - 1}{\kappa + 1}$ 은?

정답

99/101

풀이

$\kappa = 100$ 이므로 $\frac{99}{101} \approx 0.980$ 입니다. 오차를 절반으로 줄이는 데 약 35단계가 듭니다.

5.4 [계산]

$f(x, y) = x^2 + xy + y^2 - 3x$ (4장 문제 4.1)에 시작점 $(0, 0)$ 에서 뉴턴 방법을 한 번 적용한 점을 씁니다.

좌표	값
$x_1$	[?]
$y_1$	[?]

정답

2
-1

풀이

$\nabla f(0, 0) = (-3, 0)$ , $H = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ . $H\mathbf{h} = (3, 0)$ 을 풀면 $\mathbf{h} = (2, -1)$ 이므로 $\mathbf{x}_1 = (2, -1)$ 입니다. 이차함수라 한 번에 최소점(4장의 답)에 도착합니다.

5.5 [증명]

한 변수 $f(x) = \frac a2x^2$ ( $a > 0$ )에 경사하강법을 쓸 때 $x_k = (1 - \eta a)^kx_0$ 임을 보이고, 수렴 조건 $0 < \eta < 2/a$ 를 유도합니다. $\eta = 1/a$ 이면 어떻게 되는지도 씁니다.

풀이

$f'(x) = ax$ 이므로 $x_{k+1} = x_k - \eta ax_k = (1 - \eta a)x_k$ 이고, 귀납법으로 $x_k = (1 - \eta a)^kx_0$ 입니다. $x_0 \ne 0$ 일 때 $x_k \to 0$ 일 필요충분조건은 $|1 - \eta a| < 1$ , 곧 $0 < \eta a < 2$ 입니다. $\eta = 1/a$ 이면 $1 - \eta a = 0$ 이라 한 번에 $x_1 = 0$ 에 도착합니다. 이것은 뉴턴 방법( $\eta = 1/f''$ )과 같습니다.