Chapter 09

가장 낮은 곳 찾기

공학 설계는 거의 언제나 "어떤 값을 가장 작게(또는 크게) 만드는 손잡이 위치를 찾아라"라는 문제로 바뀝니다. 렌즈의 수차, 회로의 전력, 공정의 불량률, 신경망의 오차. 손잡이가 두세 개라면 다 돌려 보면 되지만, 수천·수십억 개라면 다 돌려 볼 수 없습니다. 이 장은 발밑의 기울기만 보고 내려가는 법에서 시작해, 내려가는 속도를 좌우하는 지형의 모양(조건수·볼록성), 그리고 "예산"이라는 울타리가 있을 때의 최적화(라그랑주 승수·선형계획)까지 지형을 직접 만지며 따라갑니다.

기울기 $\nabla f$가 가장 가파른 오르막 방향이고 등고선에 수직인 이유를 설명하고, 경사 하강법을 쓸 수 있다.
학습률이 너무 크면 발산하고 너무 작으면 느린 이유를 $|1-\eta\lambda|$로 설명하고, 조건수가 수렴 속도를 정한다는 것을 안다.
모멘텀과 Adam이 협곡 지형에서 무엇을 고치는지, 확률적 기울기의 잡음이 왜 해가 아니라 득이 되기도 하는지 안다.
볼록 문제는 국소 최소가 곧 전역 최소라서 "쉬운" 문제임을 이해한다.
최소제곱 직선 맞춤을 잔차 제곱의 넓이로 보고 정규방정식을 유도하며, 이상치에 약한 이유를 안다.
제약이 있는 최적화에서 $\nabla f=\lambda\nabla g$의 기하적 의미와 $\lambda$ = "제약의 가격"을 설명하고, 선형계획의 최적해가 꼭짓점에 있는 이유를 안다.

이 수식이 없었다면대규모 언어 모델(LLM)

신경망은 수십억~수천억 개의 손잡이(매개변수)를 가진 기계입니다(GPT-3가 1,750억 개). 학습이란 이 손잡이들을, 문장 데이터에 대한 오차가 가장 작아지는 위치로 맞추는 일입니다. 손잡이 하나씩 돌려 보며 오차를 재는 방법은 손잡이 수만큼 계산을 반복해야 하므로 처음부터 불가능합니다.

해법은 모든 손잡이를 동시에, 각자 "오차가 줄어드는 쪽"으로 조금씩 돌리는 것입니다. 그 방향이 오차 함수의 기울기(그래디언트)이고, 역전파(역방향 자동 미분)는 이 수십억 차원의 기울기를 순전파 몇 배 정도의 비용으로 한꺼번에 계산합니다. 경사 하강법과 그 후손(모멘텀, Adam)이 없었다면 오늘의 AI는 없었습니다.

수십억 개 손잡이→하나씩 시험은 불가능→기울기 하강 −η∇f→학습되는 모델

눈을 가리고 산에서 내려오기

짙은 안개 속의 하산

짙은 안개 속, 산 중턱에 서 있습니다. 지도도 없고 몇 걸음 앞도 안 보입니다. 아는 것은 발밑 땅의 기울기뿐입니다. 어떻게 하면 골짜기 바닥에 닿을 수 있을까요? 신경망 학습이 정확히 이 상황입니다. 오차 함수 $f(\boldsymbol\theta)$의 전체 모양(지도)은 알 수 없고, 지금 위치에서의 값과 기울기만 계산할 수 있습니다.

답은 직관 그대로입니다. 가장 가파르게 내려가는 방향으로 한 걸음 딛고, 거기서 다시 발밑을 확인합니다. 1차원이면 "기울기가 양수면 왼쪽, 음수면 오른쪽으로"이고, 걸음 크기를 기울기에 비례하게 하면 바닥 근처(기울기 ≈ 0)에서 저절로 보폭이 줄어듭니다.

그림 9-1. 1차원 경사 하강. 현재 위치의 접선 기울기 $f'$만 보고, 그 반대 방향으로 $\eta f'$만큼 이동한다. 기울기가 작아지는 바닥 근처에서는 보폭도 저절로 줄어 점들이 촘촘해진다.

손잡이가 여러 개($\boldsymbol\theta\in\mathbb R^n$)이면 "기울기"는 각 손잡이 방향의 편미분을 모은 벡터, 그래디언트(Gradient)가 됩니다. 1847년 코시(Cauchy)가 연립방정식을 풀려고 제안한 것으로 알려진 경사 하강법(Gradient Descent)은 한 줄입니다.

$$\boldsymbol\theta_{k+1} = \boldsymbol\theta_k - \eta\,\nabla f(\boldsymbol\theta_k), \qquad \nabla f = \left(\frac{\partial f}{\partial\theta_1}, \dots, \frac{\partial f}{\partial\theta_n}\right)$$

$\eta$: 학습률(learning rate, 보폭 계수). $-\nabla f$는 "가장 가파른 내리막" 방향(다음 절에서 증명). 이 규칙에는 전체 지형에 대한 정보가 전혀 필요 없다 — 현재 위치의 값과 기울기만 있으면 된다.

아래 지형은 2변수 함수 $f(x,y)$를 색과 등고선으로 그린 지도입니다(어두운 쪽이 낮음). 공은 이 지도를 모르고 발밑 기울기만 보며 굴러갑니다. 학습률과 지형을 바꿔 가며 경사 하강이 언제 잘 되고 언제 망가지는지 보세요.

SIMULATOR

손실 지형 위의 경사 하강

어두울수록 낮음

지형 학습률 η

재생 속도

기울기 화살표 −∇f 보기

단계 k0

f(θₖ)—

|∇f|—

상태—

지도 위 빈 곳을 클릭하거나 '시작' 점을 끌어 출발 위치를 정합니다. 해볼 것: ① '길쭉한 협곡'에서 η를 0.19 → 0.21로 넘기면 지그재그가 발산으로 바뀝니다(한계 2/λ_max = 0.2). ② '여러 골짜기'에서 '공 24개 뿌리기' — 시작점에 따라 다른 바닥에 갇힙니다. ③ '안장점'은 y = 0에서 출발하면 고개(기울기 0)에 멈추지만, 시작점을 아주 살짝 위아래로 옮기면 결국 빠져나갑니다. 모델: 기울기는 수치 중앙 차분으로 계산, 잡음 없는 전체 기울기(배치 경사 하강). 색은 높이의 순위(분위수)로 칠해 지형마다 대비를 맞췄습니다. 로젠브록은 $(1-x)^2+20(y-x^2)^2$로 원래(계수 100)보다 완만하게 했습니다.

몇 가지가 바로 보입니다. 둥근 그릇에서는 공이 바닥을 향해 곧장 갑니다. 협곡에서는 학습률을 조금만 키워도 가파른 벽 사이를 지그재그로 튀고, 정작 골짜기를 따라 내려가는 방향으로는 느릿느릿 움직입니다. 여러 골짜기 지형에서는 어디서 출발하느냐가 도착점을 정합니다. 그리고 안장점에서는 기울기가 0이라는 사실만으로는 바닥인지 고개인지 알 수 없습니다. 이 네 가지 관찰이 이 장의 나머지를 끌고 갑니다.

기울기는 등고선에 수직이다

왜 $-\nabla f$가 "가장 가파른" 내리막일까요? 현재 위치에서 아주 작은 걸음 $\mathbf d$를 디뎠을 때 높이의 변화는 1차 테일러 근사로

$$f(\boldsymbol\theta+\mathbf d) \approx f(\boldsymbol\theta) + \nabla f\cdot\mathbf d = f(\boldsymbol\theta) + |\nabla f|\,|\mathbf d|\cos\varphi$$

$\varphi$: 걸음 방향과 $\nabla f$ 사이의 각. 같은 보폭 $|\mathbf d|$라면 $\cos\varphi=-1$, 즉 $\mathbf d$가 $-\nabla f$와 같은 방향일 때 가장 많이 내려간다. $\cos\varphi=0$(기울기에 수직)으로 걸으면 높이가 변하지 않는다 — 그 방향이 바로 등고선 방향이다.

마지막 문장이 핵심입니다. 등고선은 "높이가 변하지 않는 방향"을 이은 선이고, 높이가 변하지 않는 방향은 기울기에 수직입니다. 그러므로 그래디언트는 항상 등고선에 수직이고, 그 크기는 등고선 간격이 좁을수록(가파를수록) 큽니다. 위 시뮬레이터에서 '기울기 화살표'를 켜 보면 화살표가 모든 곳에서 등고선을 직각으로 가로지르는 것을 볼 수 있습니다.

그림 9-2. 타원형 등고선과 한 점에서의 기울기. $\nabla f$는 등고선의 접선에 수직(작은 직각 표시)이며 바깥(높은 쪽)을 향한다. 타원이 길쭉하면 $-\nabla f$는 최소점을 똑바로 가리키지 않는다 — 협곡 지형에서 지그재그가 생기는 기하학적 이유다.

그림 9-2의 마지막 관찰이 중요합니다. 등고선이 동그라면 $-\nabla f$는 정확히 중심을 가리키지만, 길쭉한 타원에서는 엉뚱한 쪽(짧은 축 방향)을 가리킵니다. "가장 가파른 방향"은 국소적으로 최선일 뿐, 목적지를 가리키는 방향이 아닙니다. 이 차이가 다음 절의 주제입니다.

2차 정보: 뉴턴법 테일러 전개를 2차까지 쓰면 $f(\boldsymbol\theta+\mathbf d)\approx f+\nabla f\cdot\mathbf d+\tfrac12\mathbf d^{\mathsf T}H\mathbf d$이고($H$: 헤세 행렬, 2차 편미분), 이를 최소화하는 걸음은 $\mathbf d=-H^{-1}\nabla f$다. 이차 함수라면 한 걸음에 바닥에 닿는다. 하지만 매개변수가 $n$개면 $H$는 $n\times n$ — 10억 개면 $10^{18}$개 원소라 저장조차 못 한다. 그래서 대규모 문제는 1차(기울기) 방법과, $H$를 값싸게 흉내 내는 근사(대각 스케일링, L-BFGS 등)를 쓴다.

보폭의 딜레마: 학습률과 조건수

학습률을 얼마로 잡을까

신경망 학습을 처음 돌리면 가장 먼저 부딪히는 문제입니다. 학습률을 크게 잡으면 손실이 NaN으로 폭발하고, 작게 잡으면 며칠을 돌려도 손실이 거의 줄지 않습니다. "적당히"는 어디이며, 왜 그 폭이 지형마다 다를까요?

가장 단순한 지형, 1차원 포물선 $f(x)=\tfrac{a}{2}x^2$에서 정확히 계산할 수 있습니다. 기울기는 $f'(x)=ax$이므로

$$x_{k+1} = x_k - \eta a x_k = (1-\eta a)\,x_k \quad\Longrightarrow\quad x_k = (1-\eta a)^k x_0$$

$a$: 곡률(2차 미분). 한 걸음마다 거리가 $r=1-\eta a$배가 된다. $01$: 발산. 따라서 수렴 조건은 $0<\eta<2/a$이고, $\eta=1/a$이면 한 걸음에 도착한다.

SIMULATOR

포물선 위의 걸음: 학습률의 세 영역

f(x) = a x²/2 위의 걸음

|xₖ| (로그 눈금)

학습률 η 곡률 a

바로 가기

r = 1 − ηa—

안정 한계 2/a—

10걸음 뒤 |x|/|x₀|—

판정—

왼쪽 포물선 위의 시작점을 좌우로 끌 수 있습니다. 해볼 것: ① η를 천천히 올리며 오른쪽 그래프의 기울기(수렴 속도)가 가장 가파른 곳이 η = 1/a인지 확인. ② η가 1/a를 넘으면 점이 바닥을 건너뛰며 좌우로 번갈아 찍힙니다. ③ 곡률 a를 키우면 같은 η가 갑자기 발산 영역이 됩니다 — 가장 가파른 방향이 학습률의 상한을 정합니다. 모델: 정확한 이차 함수, 잡음 없음, 30걸음까지.

이제 2차원 협곡을 생각합시다. 등고선이 타원인 이차 함수는 주축 방향으로 돌려 놓으면 $f=\tfrac12(\lambda_1u^2+\lambda_2v^2)$처럼 두 개의 독립된 포물선이 됩니다($\lambda_i$는 헤세 행렬의 고유값, 3장). 경사 하강은 두 방향에 같은 η를 써야 하므로 딜레마가 생깁니다.

발산하지 않으려면 가장 가파른 방향에 맞춰 $\eta<2/\lambda_{\max}$여야 하고,
그러면 가장 완만한 방향은 한 걸음에 $1-\eta\lambda_{\min}\approx 1-2\lambda_{\min}/\lambda_{\max}$배밖에 줄지 않습니다.

두 고유값의 비 $\kappa=\lambda_{\max}/\lambda_{\min}$을 조건수(Condition Number)라 합니다. 최선의 고정 학습률 $\eta=2/(\lambda_{\max}+\lambda_{\min})$을 써도 한 걸음당 오차는 $(\kappa-1)/(\kappa+1)$배로만 줄어듭니다.

조건수 κ	걸음당 수렴비 (κ−1)/(κ+1)	오차를 10⁻⁶로 줄이는 걸음 수	지형 모양
1	0	1	둥근 그릇
10	0.818	≈ 69	길쭉한 타원
100	0.980	≈ 691	좁은 협곡
1000	0.998	≈ 6,900	거의 평행한 두 벽

걸음 수가 대략 $\kappa$에 비례합니다. 그래서 실무의 상당 부분은 지형을 둥글게 만드는 일입니다. 입력 특징을 평균 0, 분산 1로 맞추는 정규화, 신경망의 배치 정규화, 변수 단위를 비슷한 크기로 바꾸는 것 모두 헤세 행렬의 조건수를 줄여 경사 하강이 똑바로 내려가게 하려는 것입니다. 이 장 뒤의 최소제곱 시뮬레이터에서도 같은 협곡을 다시 만납니다.

엔지니어의 눈으로 "손실이 NaN이 됐다"는 거의 언제나 어떤 방향에서 $\eta\lambda>2$가 됐다는 뜻이다. 학습 초반에 학습률을 서서히 올리는 워밍업(warm-up), 기울기 크기를 자르는 그래디언트 클리핑은 모두 이 한계를 넘지 않게 하는 장치다.

무거운 공과 Adam

협곡에서 지그재그만 하다 끝난다

조건수가 큰 지형에서 경사 하강은 벽 사이를 튀느라 걸음을 다 쓰고, 정작 골짜기 아래로는 거의 못 갑니다. 학습률을 줄이면 지그재그는 사라지지만 더 느려집니다. 같은 기울기 정보만으로 더 잘 내려갈 수는 없을까요?

관찰: 지그재그 성분은 걸음마다 부호가 바뀌고, 골짜기를 따라가는 성분은 매번 같은 방향입니다. 지난 걸음들을 평균하면 번갈아 바뀌는 성분은 상쇄되고 꾸준한 성분은 쌓입니다. 이것이 모멘텀(Momentum, Polyak의 heavy ball, 1964)입니다. 물리적으로는 마찰 있는 무거운 공이 관성 때문에 벽에서 덜 튀고 경사를 따라 가속하는 것과 같습니다.

$$\mathbf v_{k+1} = \beta\,\mathbf v_k + \nabla f(\boldsymbol\theta_k), \qquad \boldsymbol\theta_{k+1} = \boldsymbol\theta_k - \eta\,\mathbf v_{k+1}$$

$\beta$(보통 0.9): 속도를 얼마나 기억하나(1−β가 마찰). 일정한 기울기 $g$가 계속되면 속도는 $g/(1-\beta)$, 즉 실효 보폭이 10배가 된다. 이차 지형에서 최적 계수를 쓰면 수렴비가 $(\sqrt\kappa-1)/(\sqrt\kappa+1)$로, 필요한 걸음 수가 $\kappa$가 아니라 $\sqrt\kappa$에 비례한다(κ = 100이면 약 10배 빠름).

또 다른 처방은 손잡이마다 보폭을 따로 정하는 것입니다. 기울기가 늘 큰 방향(가파른 벽)은 보폭을 줄이고, 늘 작은 방향(완만한 바닥)은 키우면 지형이 둥글게 펴진 것처럼 됩니다. Adam(Adaptive Moment Estimation, Kingma & Ba, 2014)은 기울기의 이동 평균(모멘텀)과 기울기 제곱의 이동 평균(크기 추정)을 함께 써서, 성분별로 $m/\sqrt{v}$만큼 움직입니다.

$$\mathbf m \leftarrow \beta_1\mathbf m + (1-\beta_1)\mathbf g,\quad \mathbf v \leftarrow \beta_2\mathbf v + (1-\beta_2)\mathbf g^2,\quad \boldsymbol\theta \leftarrow \boldsymbol\theta - \eta\,\frac{\hat{\mathbf m}}{\sqrt{\hat{\mathbf v}}+\epsilon}$$

$\hat{\mathbf m}=\mathbf m/(1-\beta_1^k)$, $\hat{\mathbf v}=\mathbf v/(1-\beta_2^k)$는 0에서 시작한 평균의 편향 보정. 기본값 $\beta_1=0.9,\ \beta_2=0.999,\ \epsilon=10^{-8}$. 제곱·나눗셈은 성분별. 기울기 크기와 무관하게 한 걸음이 대략 η 정도라서, 학습률을 "좌표 공간에서의 보폭"으로 해석할 수 있다.

마지막 요소는 잡음입니다. 실제 신경망 학습은 전체 데이터(수조 토큰)로 기울기를 계산하지 않고, 수백~수천 개 표본의 미니배치(Mini-batch)로 추정한 기울기를 씁니다. 이것이 확률적 경사 하강(SGD, Stochastic Gradient Descent)입니다. 추정이므로 매번 잡음이 섞이는데, 이 잡음이 얕은 국소 최소나 안장점에서 공을 흔들어 빠져나오게 돕기도 합니다.

SIMULATOR

경사 하강 vs 모멘텀 vs Adam

경사 하강(GD)모멘텀 β=0.9Adam

지형 η (GD·모멘텀) η (Adam) 기울기 잡음 σ (미니배치)

단계0

f — GD—

f — 모멘텀—

f — Adam—

'시작' 점을 끌거나 빈 곳을 클릭해 출발점을 바꿉니다. 해볼 것: ① '좁은 협곡'에서 같은 η로 GD와 모멘텀을 비교 — GD는 아직 골짜기 중간인데 모멘텀은 바닥에 도착합니다. ② '안장점'(y=0 출발)에서 잡음 σ를 0 → 0.5로: 잡음이 없으면 GD는 고개에 멈추지만 잡음이 있으면 굴러 내려갑니다. ③ '여러 골짜기'에서 σ를 1 이상으로 올리고 여러 번 '처음으로'를 눌러 보세요 — 얕은 골짜기를 탈출하는 경우가 생깁니다. 모델: 잡음은 기울기 각 성분에 더한 정규분포 $\sigma\,\mathcal N(0,1)$(실제 미니배치 잡음의 크기·상관 구조는 문제마다 다름). 모멘텀은 위 식(β = 0.9), Adam은 기본 하이퍼파라미터.

방법	갱신에 쓰는 것	매개변수당 추가 메모리	잘하는 것 / 약점
(S)GD	현재 기울기	0	단순·예측 가능 / 큰 κ에서 느림, 학습률에 민감
모멘텀	기울기의 지수 평균(속도)	1개	협곡 가속, 지그재그 상쇄 / 바닥을 지나쳤다 돌아오는 오버슈트
Adam	기울기 평균 + 제곱 평균	2개	성분별 보폭 자동 조정, 대형 신경망의 사실상 표준 / 메모리 2배, 바닥 근처 미세 진동

메모리 열이 대형 모델에서는 결정적입니다. 매개변수 1,000억 개를 32비트로 학습하면 가중치 400 GB에 Adam 상태 800 GB가 더 붙습니다. 대규모 학습 시스템이 옵티마이저 상태를 여러 GPU에 쪼개 저장하는 이유입니다(AIBook).

볼록하면 쉽다

찾은 답이 정말 최선인가

경사 하강이 멈췄습니다. 기울기는 0입니다. 하지만 첫 시뮬레이터의 '여러 골짜기'에서 봤듯이, 다른 곳에서 출발했다면 더 낮은 바닥이 있었을지도 모릅니다. 바닥이 하나뿐이라고 보증받을 방법은 없을까요?

함수 그래프 위 아무 두 점을 직선(현)으로 이었을 때, 그 현이 항상 그래프보다 위에 있으면 그 함수를 볼록(Convex)하다고 합니다. 식으로는

$$f\big(t\mathbf a+(1-t)\mathbf b\big) \;\le\; t f(\mathbf a)+(1-t)f(\mathbf b), \qquad 0\le t\le 1$$

두 번 미분 가능하면 "헤세 행렬이 모든 곳에서 양의 준정부호(모든 고유값 ≥ 0)"와 같다. 1차원이면 $f''\ge 0$ — 그래프가 어디서나 위로 휘어 있다.

그림 9-3. 볼록 함수(왼쪽)는 어느 두 점을 이어도 현이 그래프 위에 있다. 볼록하지 않은 함수(오른쪽)는 현이 그래프 아래로 내려가는 구간이 있고, 기울기 0인 점이 국소 최소일 수 있다.

볼록 함수의 결정적인 성질은 이것입니다. 국소 최소는 곧 전역 최소다. 증명은 한 줄입니다. 국소 최소 $\mathbf a$보다 낮은 점 $\mathbf b$가 있다면, $\mathbf a$에서 $\mathbf b$로 가는 현 위의 점들은 볼록성 때문에 $f(\mathbf a)$보다 낮아야 하고, 그 점들은 $\mathbf a$에 얼마든지 가까이 있으므로 $\mathbf a$가 국소 최소라는 데 모순입니다. 그래서 볼록 문제에서는

어디서 출발하든 경사 하강은 같은 최솟값에 도달하고(학습률만 적당하면),
"기울기 = 0"이 곧 최적이라는 증명서가 되며,
내점법 같은 알고리즘으로 수백만 변수 문제도 다항 시간 안에 신뢰성 있게 풀 수 있습니다.

그래서 공학자는 문제를 볼록하게 만들려고 애씁니다. 최소제곱(다음 절), 선형계획(마지막 절), 포트폴리오 분산 최소화, 많은 신호 복원 문제가 볼록입니다. 첫 시뮬레이터에서 '둥근 그릇'이나 '협곡'을 고르고 '공 24개 뿌리기'를 눌러 보면 모든 공이 한 바닥에 모입니다. '여러 골짜기'와 대비해 보세요.

그런데 신경망은 볼록이 아니다 신경망 손실 지형은 매우 비볼록이고 안장점이 넘쳐난다. 그런데도 SGD 계열이 실용적으로 좋은 해를 찾는 이유는 아직 완전히 규명되지 않았다. 고차원에서는 "모든 방향으로 올라가는" 진짜 국소 최소보다 어떤 방향으론 내려갈 수 있는 안장점이 훨씬 흔하다는 관찰, 과매개변수화된 모델에서는 좋은 최소들이 넓게 연결돼 있다는 관찰 등이 부분적인 설명으로 연구되고 있다.

측정점에 직선 맞추기: 최소제곱

센서 교정 곡선

온도 센서를 교정합니다. 기준 온도 $x_i$ 몇 개에서 센서 출력 $y_i$를 쟀더니 점들이 대략 직선 위에 있지만 잡음 때문에 정확히 한 직선에 놓이지는 않습니다. 점이 직선 정의에 필요한 두 개보다 많으니 방정식 $y_i=mx_i+b$는 해가 없습니다(과결정계). "가장 잘 맞는" 직선은 무엇이고, 어떻게 구할까요?

"잘 맞는다"를 숫자로 정해야 최적화 문제가 됩니다. 각 점의 세로 오차 잔차(Residual) $r_i=y_i-(mx_i+b)$를 모두 제곱해 더한 값을 최소화하는 것이 최소제곱법(Least Squares)입니다. 1805년 르장드르가 처음 출판했고, 가우스는 1795년부터 썼다고 주장하며 1801년 소행성 세레스의 궤도 예측에 사용한 것으로 유명합니다.

$$S(m,b) = \sum_{i=1}^{n} \big(y_i - m x_i - b\big)^2$$

기하적으로는 각 잔차를 한 변으로 하는 정사각형 넓이의 합이다. 아래 시뮬레이터에서 그 정사각형들이 보인다.

왜 제곱일까요? 첫째, 부호를 없앱니다. 둘째, $S$가 $m,b$에 대한 볼록 이차 함수(위로 열린 그릇)라서 바닥이 유일하고 미분이 선형 방정식이 됩니다. 셋째, 잡음이 정규분포라면 최소제곱 해가 최대가능도 추정과 같습니다(7장). 기울기를 0으로 놓으면

$$\frac{\partial S}{\partial m}=0,\ \frac{\partial S}{\partial b}=0 \;\Longrightarrow\; \begin{pmatrix}\sum x_i^2 & \sum x_i\\ \sum x_i & n\end{pmatrix}\begin{pmatrix}m\\ b\end{pmatrix}=\begin{pmatrix}\sum x_iy_i\\ \sum y_i\end{pmatrix} \quad\Big(A^{\mathsf T}A\,\boldsymbol\beta = A^{\mathsf T}\mathbf y\Big)$$

이것이 정규방정식(normal equations)이다. $A$는 $[x_i\ \ 1]$을 행으로 쌓은 $n\times2$ 행렬. 반복 없이 2×2 연립방정식 한 번으로 답이 나온다. 기하적으로는 $\mathbf y$를 $A$의 열공간에 수직 정사영한 것 — 잔차 벡터가 열공간에 수직($A^{\mathsf T}\mathbf r=0$)이 되는 점이다.

SIMULATOR

잔차 제곱의 넓이를 최소로

데이터와 직선 (점을 끄세요)

손실 지형 S(m, b)

최적 직선내 직선(오른쪽 점)잔차²

오차 척도

이상치 하나 추가 잔차 정사각형 보기

최적 m, b—

최적 손실—

내 직선 손실—

헤세 행렬 κ—

왼쪽의 점을 끌면 최적 직선과 오른쪽 손실 지형이 실시간으로 바뀝니다. 오른쪽 지형의 주황 점(내 직선의 m, b)을 끌어 손으로 맞춰 본 뒤, 경사 하강 버튼으로 바닥까지 굴려 보세요. 해볼 것: ① '이상치 추가'를 켜고 그 점을 멀리 끌어 보면 제곱 넓이가 폭발적으로 커지면서 L2 직선이 끌려갑니다. L1로 바꾸면 거의 꿈쩍하지 않습니다. ② 손실 지형이 가늘고 비스듬한 타원(κ가 큼)이라 경사 하강이 지그재그하는 것을 보세요 — x가 0에서 멀리 있기 때문입니다. 모델: 세로 오차만 고려(x는 정확하다고 가정). L1 해는 반복 재가중 최소제곱(IRLS)으로 근사.

시뮬레이터의 두 가지 관찰이 실무 교훈입니다. 첫째, 제곱은 큰 잔차를 크게 벌주므로 이상치 하나가 직선 전체를 끌고 갑니다. 잔차가 3배면 넓이는 9배입니다. 측정 데이터에 튀는 값이 섞일 수 있으면 L1(절댓값)이나 후버 손실처럼 큰 잔차를 덜 벌주는 로버스트 회귀(Robust Regression)를 씁니다. 대가는 미분이 매끄럽지 않고 닫힌 해가 없다는 것입니다. 둘째, x 값들이 원점에서 멀리 떨어져 있으면 기울기 m과 절편 b가 강하게 얽혀 손실 지형이 비스듬한 협곡이 됩니다. x에서 평균을 빼 두면(중심화) $\sum x_i=0$이 되어 정규방정식 행렬이 대각 행렬이 되고, 협곡이 축에 나란해집니다 — 앞 절의 조건수 이야기 그대로입니다.

직선만이 아니다 모델이 매개변수에 대해 선형이기만 하면($y\approx\sum_j\beta_j\phi_j(x)$) 같은 정규방정식이 된다. 다항식 맞춤, 카메라 색 보정 행렬(CCM) 추정, 렌즈 왜곡 계수 추정, FIR 필터 설계가 모두 최소제곱이다. 실제 계산에서는 $A^{\mathsf T}A$의 조건수가 $A$의 조건수의 제곱이 되어 수치 오차가 커지므로, $A^{\mathsf T}A$를 직접 만들지 않고 QR 분해나 SVD로 푼다(10장).

예산이 있을 때: 라그랑주 승수

전력 예산 나누기

칩 하나에 쓸 수 있는 전력이 $c$ 와트로 정해져 있습니다. 이 전력을 CPU 블록($x$)과 GPU 블록($y$)에 나눠 주는데, 각 블록의 성능은 전력을 늘릴수록 오르지만 점점 덜 오릅니다(수확 체감). 총성능 $f(x,y)$를 최대로 하는 배분은? 그리고 예산을 1와트 더 받으면 성능이 얼마나 오를까요?

제약 $g(x,y)=x+y=c$가 없다면 그냥 전력을 무한히 주면 됩니다. 제약 때문에 우리는 평면 전체가 아니라 제약 곡선 위에서만 움직일 수 있습니다. 곡선을 따라 걷는 사람을 상상합시다. 그 위치에서 $f$의 기울기 $\nabla f$가 곡선 방향 성분을 조금이라도 가지면, 그쪽으로 걸어서 $f$를 더 키울 수 있습니다. 더 이상 나아질 수 없는 점은 $\nabla f$에 곡선 방향 성분이 전혀 없는 점, 즉 $\nabla f$가 곡선에 수직인 점입니다. 그런데 곡선 $g=c$에 수직인 벡터는 $\nabla g$입니다(그것도 등고선이니까요!). 그래서 최적점에서는

$$\nabla f = \lambda\,\nabla g, \qquad g(x,y)=c$$

$\lambda$: 라그랑주 승수(Lagrange multiplier). 미지수 3개($x,y,\lambda$)에 식 3개. 같은 말로, $f$의 등고선이 제약 곡선에 접하는 점이다. 라그랑주가 『해석 역학』(1788)에서 역학의 구속 조건을 다루며 체계화했다.

그림 9-4. 원 모양 제약 위에서 선형 함수 $f$(등고선은 평행 직선)를 최대화. A와 B에서는 $\nabla f$(파랑)와 $\nabla g$(주황, 원에 수직)가 각을 이루므로 원을 따라 더 나아질 여지가 있다. 최적점에서는 두 기울기가 평행하고, $f$의 등고선(실선)이 원에 접한다.

여기까지는 "최적점의 조건"입니다. 라그랑주 승수의 진짜 선물은 $\lambda$ 자체의 의미입니다. 예산 $c$를 조금 늘리면 최적값 $f^*(c)$가 얼마나 늘어날까요? 답은

$$\frac{d f^*}{d c} = \lambda$$

$\lambda$는 제약의 가격, 경제학 용어로 그림자 가격(shadow price)이다. "예산 1단위를 더 얻으면 목적이 λ만큼 좋아진다." λ가 크면 그 제약이 병목이다. λ = 0이면 그 제약은 사실상 걸리지 않는다(예산을 다 쓰지 않아도 최적).

이유는 짧습니다. 최적점에서 $\nabla f=\lambda\nabla g$이므로, 예산이 $dc$만큼 늘어 최적점이 $d\mathbf p$만큼 움직이면 $df = \nabla f\cdot d\mathbf p = \lambda\,\nabla g\cdot d\mathbf p = \lambda\,dg = \lambda\,dc$입니다. 아래 시뮬레이터에서 직접 확인해 봅시다. 성능 모델은 $f=a\sqrt{x}+b\sqrt{y}$(가상의 수확 체감 모델)입니다.

SIMULATOR

제약 곡선 위의 최적점과 그림자 가격

∇fλ∇g (제약 x+y=c)f 등고선

전력 예산 c (W) GPU 효율 b (a = 1) 예산 미만도 허용 (x+y ≤ c 영역 표시)

배분 (x, y)—

성능 f / 최대 f*—

∇f와 ∇g 사이 각—

λ (최적점)—

Δf*/Δc (수치)—

주황 직선(예산을 다 쓰는 배분) 위의 점을 끌어 보세요. 해볼 것: ① 점을 움직이며 '∇f와 ∇g 사이 각'이 0°가 되는 곳에서 f가 최대인지 확인. 그 점에서 점선 등고선이 예산선에 접합니다. ② 예산 c를 올리면 λ가 줄어듭니다 — 수확 체감이라 예산 1 W의 가치가 떨어집니다. 'Δf*/Δc'(최적값을 c±0.01에서 다시 풀어 차분)와 λ가 같은지 비교. ③ b를 키우면 최적 배분이 GPU 쪽으로 옮겨 가며 비율 $y^*/x^*=b^2/a^2$을 따릅니다. 모델: $f=a\sqrt x+b\sqrt y$, $g=x+y$; 이 모델의 해는 $x^*=ca^2/(a^2+b^2)$, $f^*=\sqrt{c(a^2+b^2)}$, $\lambda=\sqrt{a^2+b^2}/(2\sqrt c)$. 단위는 임의.

부등식 제약과 KKT 조건 실제 예산은 "$x+y\le c$"처럼 부등식이다. 최적점이 경계 안쪽이면 제약은 무의미하고($\lambda=0$), 경계 위에 있으면 위와 같다($\lambda\ge0$). 이 두 경우를 한 번에 쓴 것이 카루시–쿤–터커(KKT) 조건 $\nabla f=\sum_i\lambda_i\nabla g_i,\ \lambda_i\ge0,\ \lambda_i\,(g_i-c_i)=0$이다. 마지막 식(상보성)은 "가격이 붙은 제약은 꽉 차 있고, 여유가 있는 제약은 가격이 0"이라는 뜻이다. 신경망의 가중치 감쇠, SVM의 서포트 벡터, 전력망의 송전 혼잡 가격 모두 이 언어로 쓴다.

선형계획: 최적은 꼭짓점에 있다

생산 계획

공장에서 제품 A($x$개)와 B($y$개)를 만듭니다. 기계 시간은 $2x+y\le100$, 원자재는 $x+y\le60$, 조립 인력은 $x+3y\le120$으로 제한됩니다. 개당 이익이 A 30만 원, B 40만 원이면 무엇을 몇 개 만들어야 할까요? 이익이 바뀌면 계획은 어떻게 바뀔까요?

목적과 제약이 모두 1차식인 최적화를 선형계획(Linear Programming, LP)이라 합니다. 1939년 칸토로비치가 생산 계획 문제로 정식화했고, 1947년 단치그(Dantzig)가 심플렉스법을 내놓은 뒤 물류·생산·통신망·전력 계통 운용의 일상 도구가 되었습니다.

기하적으로 보면 답이 바로 보입니다. 제약들은 평면을 반평면으로 자르고, 그 교집합인 가능 영역(Feasible Region)은 볼록 다각형입니다. 목적 $p_Ax+p_By$의 등고선은 평행한 직선들이고, 기울기 $(p_A,p_B)$는 어디서나 같은 방향입니다. 그 방향으로 직선을 밀어 가다가 다각형을 마지막으로 스치는 곳 — 그것은 반드시 꼭짓점입니다(등고선이 한 변과 평행하면 그 변 전체가 최적).

SIMULATOR

생산 계획: 이익 직선을 밀어 꼭짓점 찾기

A 개당 이익 (만 원) B 개당 이익 (만 원) 등이익선 보기

최적 계획 (A, B)—

최대 이익—

꽉 찬(활성) 제약—

현재 계획 이익—

가능 영역 안의 '계획' 점을 끌어 이익을 확인하세요(영역 밖으로는 나갈 수 없습니다). 해볼 것: ① p_A를 0에서 80까지 천천히 올리면 최적점이 (0,40) → (30,30) → (40,20) → (50,0)으로 점프합니다. 연속적으로 미끄러지지 않습니다. ② p_A = p_B로 두면 등이익선이 원자재 제약(x+y=60)과 평행해져 그 변 전체가 최적. ③ 심플렉스 버튼: 원점에서 출발해 이웃 꼭짓점 중 이익이 오르는 쪽으로만 옮겨 갑니다. 모델: 개수를 연속량으로 취급(정수 조건 없음). 정수 조건이 붙으면 정수계획(훨씬 어려움)이 된다.

심플렉스법은 바로 이 그림을 고차원에서 수행합니다. 변수가 수천 개면 가능 영역은 수천 차원의 다면체이고 꼭짓점 수는 천문학적이지만, 심플렉스는 이웃 꼭짓점 중 목적이 나아지는 쪽으로만 옮겨 가므로 실제 문제에서는 대개 꼭짓점의 극히 일부만 방문합니다. 그리고 각 제약에도 라그랑주 승수(그림자 가격)가 있습니다. 이 예에서 원자재 제약의 그림자 가격은 "원자재 1단위를 더 사면 이익이 얼마나 늘어나나"이고, 그 값보다 싸게 원자재를 살 수 있다면 사는 것이 이득입니다. LP 솔버가 최적해와 함께 이 값(쌍대 변수)을 함께 보고하는 이유입니다.

이 도구가 쓰이는 곳

"무엇을 최소화하는가"(목적 함수)와 "무엇을 지켜야 하는가"(제약)를 적고 나면, 공학의 많은 설계 문제가 같은 도구 상자로 들어옵니다.

AIBOOK신경망 학습
역전파로 구한 기울기 + SGD·Adam, 학습률 스케줄, 정규화로 조건수 낮추기 LITHOBOOKOPC · 광원–마스크 최적화
웨이퍼 패턴 오차를 목적 함수로, 마스크 모양과 조명을 매개변수로 하는 대규모 역문제 OPTICSBOOK렌즈 설계
곡률·두께·간격을 손잡이로 수차의 가중 제곱합을 최소화(감쇠 최소제곱) DESIGNBOOK배치 · 배선
배선 길이·혼잡도를 최소화하는 셀 배치, 타이밍 제약 아래 게이트 크기 결정 STOCKBOOK포트폴리오 최적화
기대 수익 제약 아래 분산 최소화 — 볼록 이차계획과 라그랑주 승수 YIELDBOOK공정 창 · 수율 최적화
측정 데이터에 반응 표면을 최소제곱으로 맞추고 수율이 최대인 공정 조건 찾기 SENSORBOOK센서 교정
암전류·게인·비선형 보정 계수를 최소제곱으로 추정 COLORBOOK색 보정 행렬
색표 측정값과 목표 색의 오차를 최소화하는 3×3 행렬 NETWORKBOOK라우팅 · 대역 배분
링크 용량 제약 아래 흐름 최적화 — 선형계획과 그림자 가격

핵심 정리

경사 하강 $\boldsymbol\theta\leftarrow\boldsymbol\theta-\eta\nabla f$는 지형 전체를 몰라도 현재 위치의 기울기만으로 내려간다. 기울기 계산이 값싸면(역전파) 수십억 변수에도 쓸 수 있다.
$\nabla f$는 가장 가파른 오르막이고 등고선에 수직이다. 길쭉한 지형에서는 $-\nabla f$가 목적지를 가리키지 않는다.
이차 지형에서 한 걸음의 수렴비는 $1-\eta\lambda$. 발산하지 않으려면 $\eta<2/\lambda_{\max}$, 수렴 걸음 수는 조건수 $\kappa=\lambda_{\max}/\lambda_{\min}$에 비례한다. 정규화·중심화는 κ를 줄이는 일이다.
모멘텀은 지그재그를 상쇄하고 골짜기 방향으로 가속해 걸음 수를 $\sqrt\kappa$ 수준으로 줄인다. Adam은 성분별 보폭을 기울기 크기로 정규화한다. 미니배치 잡음은 안장점·얕은 골짜기 탈출을 돕기도 한다.
볼록 함수에서는 국소 최소가 전역 최소다. 최소제곱·선형계획이 "쉬운" 이유이며, 공학자는 문제를 볼록하게 만들려고 애쓴다.
최소제곱은 잔차 제곱(정사각형 넓이)의 합을 최소화하고, 정규방정식 $A^{\mathsf T}A\boldsymbol\beta=A^{\mathsf T}\mathbf y$로 한 번에 풀린다. 큰 잔차를 크게 벌주므로 이상치에 약하다.
제약 $g=c$ 아래 최적점에서는 $\nabla f=\lambda\nabla g$(등고선이 제약에 접함). λ = df*/dc는 제약의 가격(그림자 가격)이다. 선형계획의 최적은 가능 영역(볼록 다각형)의 꼭짓점에 있다.

확인 퀴즈

1. $f(x)=2x^2$(곡률 $a=4$)에 경사 하강을 쓴다. 다음 중 발산하는 학습률은?

한 걸음 배율이 $r=1-\eta a=1-4\eta$이다. η = 0.6이면 r = −1.4로 |r| > 1이라 발산한다. 한계는 2/a = 0.5. η = 0.25는 r = 0으로 한 걸음에 도착하고, η = 0.45는 r = −0.8로 진동하며 수렴한다.

2. 지도 위 한 점에서 $\nabla f$와 그 점을 지나는 등고선의 관계는?

등고선 방향으로 움직이면 높이가 변하지 않으므로 $\nabla f\cdot\mathbf d=0$, 즉 $\nabla f$는 등고선에 수직이다. 최소점을 가리키는 것은 등고선이 원일 때뿐이다.

3. 조건수 κ = 1000인 이차 지형에서 경사 하강이 느린 이유로 가장 알맞은 것은?

η < 2/λ_max로 묶이면 완만한 방향의 걸음당 감소는 약 $1-2/\kappa$에 불과하다. 이차 함수는 볼록이라 국소 최소 문제는 없다. 처방은 모멘텀, 성분별 스케일링(Adam), 변수 정규화.

4. 볼록 함수에 대한 설명으로 옳은 것은?

볼록이면 국소 최소 = 전역 최소다. 하지만 최솟값이 없을 수도 있고(예: $e^x$), 최소점이 여러 개(평평한 바닥)일 수도 있으며, 학습률이 너무 크면 볼록 함수에서도 발산한다.

5. 전력 예산 c 아래 성능을 최대화한 결과 라그랑주 승수가 λ = 3 (성능/W)이었다. 이 값의 의미는?

$df^*/dc=\lambda$ — 제약의 그림자 가격이다. λ = 0이었다면 제약이 걸려 있지 않다는 뜻이다. 이 값으로 "예산을 늘리는 데 드는 비용이 그만한 가치가 있나"를 판단한다.

6. 측정점 여섯 개에 최소제곱 직선을 맞췄는데 한 점만 크게 튀는 이상치였다. 무슨 일이 생기며, 대책은?

잔차가 k배면 제곱 넓이는 k²배라 이상치 하나가 합을 지배한다. 해는 여전히 유일하게 존재하고 문제도 볼록이지만, 답이 대표성을 잃는다. 절댓값합(L1)은 큰 잔차를 선형으로만 벌주므로 덜 끌려간다.