수학

MATH / 고급 12번

르장드르–펜첼 변환과 쌍대성: 문제를 뒤집어 푸는 법

켤레함수를 접선의 절편으로 세우고 펜첼–영 부등식·이중 켤레·쌍대 노름을 증명한 뒤, 음의 엔트로피의 켤레가 log-sum-exp이고 그 기울기가 softmax라는 계산으로 KL 정규화 정책의 닫힌 해를 다시 얻습니다. 라그랑주 쌍대, 약쌍대·강쌍대, 쌍대 간극까지 다룹니다.

PALDYN Team48 MIN READ

언어 모델을 사람의 선호에 맞추는 팀이 RLHF 단계의 목적식을 리뷰하고 있습니다. 프롬프트 하나에 대해 정책 π\pi 가 답 aa 를 고를 확률을 정하고, 보상 모델이 매긴 점수 r(a)r(a) 의 기댓값을 올리되 참조 모델 πref\pi_{\text{ref}} 에서 너무 멀어지지 않도록 KL 벌점을 겁니다. 목적식은 Eπ[r]−β KL(π ∥ πref)\mathbb{E}_{\pi}[r] - \beta\,\mathrm{KL}(\pi \,\Vert\, \pi_{\text{ref}}) 이고, 그 최댓점이 π∗(a)∝πref(a) er(a)/β\pi^*(a) \propto \pi_{\text{ref}}(a)\, e^{r(a)/\beta} 라는 닫힌 해가 DPO 손실의 출발점입니다. 리뷰어 한 사람이 묻습니다. 소프트맥스 출력층도 점수를 지수에 올려 정규화하고, 볼츠만 분포도 에너지를 지수에 올려 정규화합니다. 같은 모양이 왜 이렇게 여러 곳에서 나오는가. 그리고 KL 예산을 0.3으로 걸었을 때 그에 맞는 β\beta 는 누가 정하는가.

지난 글에서 미분이 안 되는 볼록함수의 기울기를 하위미분으로 넓히고, 강볼록성과 매끄러움이 서로를 비추는 짝이라는 것을 보았습니다. 이 글은 그 짝을 만드는 변환 자체를 세웁니다. 함수 하나를 그 함수가 받는 기울기들의 함수로 바꿔 적는 변환, 곧 켤레함수입니다. 리뷰어의 두 질문은 이 변환 하나로 답이 납니다. 소프트맥스와 볼츠만과 π∗\pi^* 는 전부 음의 엔트로피를 켤레로 뒤집은 결과이고, KL 예산과 β\beta 의 짝은 원 문제를 뒤집은 쌍대 문제의 변수 짝입니다. 라그랑주 승수와 KKT에서 손으로 세운 조건들도 여기서 쌍대성의 특수한 경우로 다시 읽힙니다.

켤레함수

정의와 볼록성

함수 f:Rn→R∪{+∞}f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\} 의 켤레함수는

f∗(y)=sup⁡x(⟨x,y⟩−f(x))f^*(y) = \sup_{x} \big( \langle x, y \rangle - f(x) \big)

로 정의합니다. xx 를 하나 고정하면 괄호 안은 yy 에 대한 일차식에 상수를 더한 것, 곧 아핀 함수입니다. 그러니 f∗f^* 는 아핀 함수들의 점별 상한이고, 점별 상한은 언제나 볼록이며 에피그래프가 닫힌 반공간들의 교집합이라 닫혀 있습니다. 증명은 한 줄입니다. y1,y2y_1, y_2 와 θ∈[0,1]\theta \in [0, 1] 에 대해 각 xx 마다 ⟨x,θy1+(1−θ)y2⟩−f(x)=θ(⟨x,y1⟩−f(x))+(1−θ)(⟨x,y2⟩−f(x))≤θf∗(y1)+(1−θ)f∗(y2)\langle x, \theta y_1 + (1-\theta) y_2 \rangle - f(x) = \theta(\langle x, y_1\rangle - f(x)) + (1-\theta)(\langle x, y_2 \rangle - f(x)) \le \theta f^*(y_1) + (1-\theta) f^*(y_2) 이고, 왼쪽에서 xx 에 대한 상한을 잡으면 f∗(θy1+(1−θ)y2)f^*(\theta y_1 + (1-\theta) y_2) 가 오른쪽 이하가 됩니다. 놀라운 것은 ff 가 볼록이 아니어도 이것이 성립한다는 점입니다. 켤레는 어떤 함수를 넣어도 볼록함수를 돌려줍니다. 이 변환을 물리학에서 오래 써 온 이름으로 르장드르–펜첼 변환이라고도 부릅니다. 라그랑주 역학에서 해밀턴 역학으로 넘어갈 때 속도를 운동량으로 바꾸는 바로 그 변환입니다.

가장 먼저 계산해 볼 것은 f(x)=x2f(x) = x^2 입니다. xy−x2xy - x^2 은 xx 에 대한 아래로 열린 포물선이라 꼭짓점 x=y/2x = y/2 에서 최대이고, 값은 y2/2−y2/4=y2/4y^2/2 - y^2/4 = y^2/4 입니다. 그래서 f∗(y)=y2/4f^*(y) = y^2/4 입니다. 더 일반적으로 양의 정부호 행렬 QQ 로 f(x)=12x⊤Qxf(x) = \tfrac12 x^\top Q x 이면 f∗(y)=12y⊤Q−1yf^*(y) = \tfrac12 y^\top Q^{-1} y 이고, Q=IQ = I 이면 12∥x∥2\tfrac12 \lVert x \rVert^2 은 자기 자신의 켤레입니다. 곡률이 큰 함수의 켤레는 곡률이 작아집니다. 이 뒤집힘이 아래 강볼록–매끄러움 짝의 씨앗입니다.

계산을 줄여 주는 규칙도 몇 개 적어 둡니다. 상수를 더하면 (f+c)∗=f∗−c(f + c)^* = f^* - c 이고, 양수 α\alpha 를 곱하면 (αf)∗(y)=αf∗(y/α)(\alpha f)^*(y) = \alpha f^*(y/\alpha) 입니다. 둘째는 sup⁡x(⟨x,y⟩−αf(x))=αsup⁡x(⟨x,y/α⟩−f(x))\sup_x(\langle x, y\rangle - \alpha f(x)) = \alpha \sup_x(\langle x, y/\alpha \rangle - f(x)) 로 바로 나옵니다. 이 규칙이 뒤에서 온도와 β\beta 를 처리합니다.

접선의 절편

켤레에는 그림이 하나 붙습니다. 기울기가 yy 인 직선 ⟨x,y⟩\langle x, y \rangle 을 그래프 위에 그리고, 직선이 곡선보다 얼마나 높이 떠 있는지를 xx 마다 잽니다. 그 간격 ⟨x,y⟩−f(x)\langle x, y\rangle - f(x) 가 가장 큰 값이 f∗(y)f^*(y) 입니다. 같은 것을 거꾸로 보면, 기울기 yy 인 직선을 아래로 내려 곡선에 처음 닿게 할 때 내려야 하는 거리입니다. 닿은 직선은 접선이고 그 절편이 −f∗(y)-f^*(y) 입니다.

가로축 x, 세로축 y 의 좌표평면에 포물선 f(x)=x² 이 파랗게 그려져 있다. 원점을 지나는 보라 점선 2x 와, 그것을 1만큼 내린 초록 접선 2x−1 이 (1, 1) 에서 포물선에 닿는다. x=1 에서 점선과 포물선 사이의 빨간 선분에 간격 2·1−1=1 이 적혀 있고, 접선의 절편 −1 에 −f*(2) 라는 표시가 있다

y=2y = 2 로 확인합니다. 직선 2x2x 와 포물선 x2x^2 의 간격 2x−x22x - x^2 은 x=1x = 1 에서 가장 커서 1이고, 공식 y2/4=1y^2/4 = 1 과 같습니다. 직선을 1만큼 내린 2x−12x - 1 이 (1,1)(1, 1) 에서 포물선에 접하고 절편이 −1-1 입니다. 그러니 볼록함수 하나를 적는 방법이 둘입니다. 점들의 모임으로 적거나, 모든 기울기에 대해 그 기울기의 접선 절편을 적거나. 켤레는 둘째 방식의 표입니다. 볼록함수가 자기 접선들 위에 놓인다는 것, 곧 접선들의 위쪽 포락선이라는 것을 받아들이면 그 표만으로 원래 함수가 복원된다는 것도 예상할 수 있고, 그것이 다음 절의 이중 켤레 정리입니다.

펜첼–영 부등식

정의에서 바로 나오는 부등식이 하나 있습니다. 상한은 어느 한 항보다 크거나 같으므로 모든 x,yx, y 에 대해

f(x)+f∗(y)≥⟨x,y⟩f(x) + f^*(y) \ge \langle x, y \rangle

입니다. 이것을 펜첼–영 부등식이라 부릅니다. f(x)=12x2f(x) = \tfrac12 x^2 이면 12x2+12y2≥xy\tfrac12 x^2 + \tfrac12 y^2 \ge xy 라는 산술–기하 부등식의 한 꼴이고, f(x)=∣x∣p/pf(x) = \lvert x \rvert^p / p 이면 고전적인 영 부등식 ∣x∣p/p+∣y∣q/q≥xy\lvert x \rvert^p/p + \lvert y \rvert^q / q \ge xy (단 1/p+1/q=11/p + 1/q = 1) 이 됩니다.

등호가 언제 서는지가 더 중요합니다. 볼록함수 ff 에 대해 다음 둘은 같습니다.

f(x)+f∗(y)=⟨x,y⟩  ⟺  y∈∂f(x)f(x) + f^*(y) = \langle x, y \rangle \iff y \in \partial f(x)

증명합니다. 지난 글의 정의대로 y∈∂f(x)y \in \partial f(x) 는 모든 zz 에 대해 f(z)≥f(x)+⟨y,z−x⟩f(z) \ge f(x) + \langle y, z - x \rangle 라는 뜻입니다. 항을 옮기면 모든 zz 에 대해 ⟨x,y⟩−f(x)≥⟨z,y⟩−f(z)\langle x, y \rangle - f(x) \ge \langle z, y \rangle - f(z), 곧 xx 가 ⟨⋅,y⟩−f\langle \cdot, y \rangle - f 의 최대점이라는 뜻이고, 이는 ⟨x,y⟩−f(x)=f∗(y)\langle x, y\rangle - f(x) = f^*(y) 와 같습니다. 그래프로 읽으면 xx 에서 기울기 yy 인 직선이 접선이라는 말입니다. 이 등호 조건이 이 글 전체의 도구입니다. 켤레의 최대점을 찾는 일이 곧 기울기 방정식 y∈∂f(x)y \in \partial f(x) 를 xx 에 대해 푸는 일입니다.

이중 켤레

볼록 폐포

켤레를 두 번 취한 f∗∗=(f∗)∗f^{**} = (f^*)^* 를 이중 켤레라 부릅니다. 첫째 사실은 어떤 ff 에 대해서든 f∗∗≤ff^{**} \le f 라는 것입니다. 펜첼–영 부등식을 ⟨x,y⟩−f∗(y)≤f(x)\langle x, y \rangle - f^*(y) \le f(x) 로 옮겨 적고 왼쪽에서 yy 에 대한 상한을 잡으면 f∗∗(x)≤f(x)f^{**}(x) \le f(x) 입니다. 그리고 f∗∗f^{**} 는 켤레이니 볼록이고 닫혀 있습니다.

둘째 사실이 펜첼–모로 정리입니다. ff 가 닫힌 진볼록함수, 곧 에피그래프가 닫힌 볼록집합이고 어디선가 유한하며 −∞-\infty 를 갖지 않는 함수이면 f∗∗=ff^{**} = f 입니다. 증명의 뼈대를 적습니다. 닫힌 볼록집합은 그 밖의 점과 분리 초평면으로 갈리므로, 에피그래프 밖의 점 (x0,t0)(x_0, t_0), 곧 t0<f(x0)t_0 < f(x_0) 마다 ff 아래에 놓이면서 x0x_0 에서 t0t_0 보다 높은 아핀 함수 ⟨y,x⟩−b\langle y, x \rangle - b 를 찾을 수 있습니다(초평면이 수직이 되는 경우는 진함수 조건으로 피해 갑니다). 그런데 ⟨y,x⟩−b≤f(x)\langle y, x \rangle - b \le f(x) 가 모든 xx 에서 성립한다는 것은 b≥f∗(y)b \ge f^*(y) 와 같으므로, 기울기 yy 의 아핀 하한 가운데 가장 높은 것은 ⟨y,x⟩−f∗(y)\langle y, x\rangle - f^*(y) 입니다. 따라서 모든 아핀 하한의 상한은 sup⁡y(⟨y,x⟩−f∗(y))=f∗∗(x)\sup_y(\langle y, x\rangle - f^*(y)) = f^{**}(x) 이고, 분리 정리가 그 상한이 ff 에 닿는다고 말해 줍니다. 볼록이 아닌 ff 에서는 같은 논증이 ff 대신 ff 아래에 놓인 가장 큰 닫힌 볼록함수를 돌려줍니다. 그것을 ff 의 볼록 폐포라 부르고, f∗∗f^{**} 가 바로 그것입니다.

이중 우물 f(x)=min((x−1)², (x+1)²) 가 파란 곡선으로, x=−1 과 x=1 에서 바닥 0 에 닿고 x=0 에서 봉우리 1 을 이룬다. 두 바닥을 잇는 초록 굵은 선분이 이중 켤레 = 0 (−1 ≤ x ≤ 1) 이고, x=0 에서 봉우리와 선분 사이 간격 1 이 빨간 점선으로 표시돼 있다

이중 우물 f(x)=min⁡{(x−1)2,(x+1)2}f(x) = \min\{(x-1)^2, (x+1)^2\} 로 계산해 봅니다. 최솟값의 켤레는 켤레들의 최댓값입니다 — 상한 두 개를 한꺼번에 잡는 것이니까요. (x−1)2(x-1)^2 의 켤레는 x=1+y/2x = 1 + y/2 에서 y+y2/4y + y^2/4, (x+1)2(x+1)^2 의 켤레는 −y+y2/4-y + y^2/4 라서 f∗(y)=∣y∣+y2/4f^*(y) = \lvert y \rvert + y^2/4 입니다. 이것을 다시 뒤집습니다. ∣x∣≤1\lvert x \rvert \le 1 이면 xy−∣y∣≤0xy - \lvert y \rvert \le 0 이라 xy−∣y∣−y2/4xy - \lvert y \rvert - y^2/4 의 상한은 y=0y = 0 에서의 0입니다. x>1x > 1 이면 y>0y > 0 쪽에서 (x−1)y−y2/4(x-1)y - y^2/4 를 최대화해 y=2(x−1)y = 2(x-1), 값 (x−1)2(x-1)^2 입니다. 그러니 f∗∗f^{**} 는 두 골짜기 바깥에서는 ff 와 같고 사이에서는 0인 직선입니다. 봉우리 f(0)=1f(0) = 1 은 켤레를 두 번 거치며 사라졌습니다. 켤레가 보는 것은 접선뿐이고, 봉우리 꼭대기는 어떤 접선에도 닿지 않기 때문입니다.

하위미분의 역

닫힌 진볼록함수에서는 펜첼–영의 등호가 xx 와 yy 에 대해 대칭이라는 것이 이중 켤레 정리에서 나옵니다. f∗∗=ff^{**} = f 이니 등식 f(x)+f∗(y)=⟨x,y⟩f(x) + f^*(y) = \langle x, y\rangle 은 f∗f^* 와 그 켤레 ff 에 대한 펜첼–영의 등호이기도 하고, 따라서

y∈∂f(x)  ⟺  x∈∂f∗(y)y \in \partial f(x) \iff x \in \partial f^*(y)

입니다. 하위미분 사상 ∂f∗\partial f^* 는 ∂f\partial f 의 역입니다. ff 의 기울기가 yy 가 되는 점을 찾고 싶으면 f∗f^* 의 기울기를 yy 에서 구하면 됩니다. f(x)=x2f(x) = x^2 이면 f′(x)=2xf'(x) = 2x 의 역은 y/2y/2 이고, f∗(y)=y2/4f^*(y) = y^2/4 의 도함수가 정확히 y/2y/2 입니다. 미분이 안 되는 자리도 같습니다. f(x)=∣x∣f(x) = \lvert x \rvert 의 하위미분은 0에서 구간 [−1,1][-1, 1] 이고, 아래에서 보듯 켤레는 [−1,1][-1, 1] 의 인디케이터라 그 하위미분은 y∈(−1,1)y \in (-1, 1) 에서 {0}\{0\}, 끝점 y=1y = 1 에서 [0,∞)[0, \infty) 입니다. 「기울기가 구간 안의 아무 값이나 되는 꺾인 점」과 「값이 한 점에 몰리는 평평한 구간」이 서로의 켤레 그림입니다.

강볼록과 매끄러움

지난 글은 ff 가 μ\mu-강볼록이면 f∗f^* 가 1/μ1/\mu-매끄럽고 그 역도 성립한다는 짝을 보였습니다. 하위미분의 역이라는 관점에서 이 짝은 거의 당연합니다. 강볼록성은 기울기가 적어도 μ\mu 의 비율로 자란다는 조건, ⟨g1−g2,x1−x2⟩≥μ∥x1−x2∥2\langle g_1 - g_2, x_1 - x_2 \rangle \ge \mu \lVert x_1 - x_2 \rVert^2 이고, 역사상으로 옮기면 xx 의 변화가 gg 의 변화의 1/μ1/\mu 배를 넘지 못한다는 조건, 곧 ∇f∗\nabla f^* 의 립시츠 상수가 1/μ1/\mu 라는 조건이 됩니다. x2x^2 은 2-강볼록이고 켤레 y2/4y^2/4 의 기울기 y/2y/2 는 12\tfrac12-립시츠입니다. 이 짝이 쌍대 문제에서 힘을 씁니다. 원 문제의 목적식이 강볼록이면 쌍대 함수는 매끄러워져 경사법으로 바로 올라갈 수 있습니다.

지지함수와 쌍대 노름

지지함수

볼록집합 CC 의 인디케이터 함수 ιC\iota_C 는 CC 안에서 0, 밖에서 +∞+\infty 인 함수입니다. 제약을 목적식 안에 넣는 장치이고, 지난 글에서 확장실수값 함수로 일반화한 이유가 이것이었습니다. 그 켤레는

ιC∗(y)=sup⁡x∈C⟨x,y⟩=:σC(y)\iota_C^*(y) = \sup_{x \in C} \langle x, y \rangle =: \sigma_C(y)

이고, 이것을 CC 의 지지함수라 부릅니다. 방향 yy 로 집합을 가장 멀리 밀었을 때 그 방향의 좌표입니다. 지지함수는 양의 동차성 σC(ty)=t σC(y)\sigma_C(t y) = t\,\sigma_C(y) (t≥0t \ge 0) 를 가지고, 닫힌 볼록집합은 지지함수로 복원됩니다. 이중 켤레 정리를 인디케이터에 적용한 것이 곧 「닫힌 볼록집합은 자기를 담는 반공간들의 교집합」이라는 고전적인 사실입니다.

노름의 켤레

노름 ∥⋅∥\lVert \cdot \rVert 의 쌍대 노름을 ∥y∥∗=sup⁡∥x∥≤1⟨x,y⟩\lVert y \rVert_* = \sup_{\lVert x \rVert \le 1} \langle x, y \rangle 로 정의합니다. 정의 자체가 단위공의 지지함수입니다. 이제 노름의 켤레를 증명합니다.

f(x)=∥x∥  ⟹  f∗(y)=ι{∥y∥∗≤1}(y)f(x) = \lVert x \rVert \implies f^*(y) = \iota_{\{\lVert y \rVert_* \le 1\}}(y)

∥y∥∗≤1\lVert y \rVert_* \le 1 이면 쌍대 노름의 정의에서 ⟨x,y⟩≤∥x∥∥y∥∗≤∥x∥\langle x, y \rangle \le \lVert x \rVert \lVert y \rVert_* \le \lVert x \rVert 이므로 ⟨x,y⟩−∥x∥≤0\langle x, y \rangle - \lVert x \rVert \le 0 이고, x=0x = 0 에서 0이 되니 상한은 0입니다. ∥y∥∗>1\lVert y \rVert_* > 1 이면 ∥x0∥≤1\lVert x_0 \rVert \le 1 이면서 ⟨x0,y⟩>1\langle x_0, y \rangle > 1 인 x0x_0 가 있고, 그러면 ∥x0∥≤1\lVert x_0\rVert \le 1 이라 t>0t > 0 에 대해 ⟨tx0,y⟩−∥tx0∥≥t(⟨x0,y⟩−1)→∞\langle t x_0, y \rangle - \lVert t x_0 \rVert \ge t(\langle x_0, y \rangle - 1) \to \infty 입니다. 끝입니다. 노름의 켤레는 쌍대 노름 단위공의 인디케이터이고, 펜첼–모로로 뒤집으면 노름은 쌍대 단위공의 지지함수입니다.

x₁–x₂ 평면에 ℓ1 단위 공인 마름모가 파랗게 칠해져 있다. 원점에서 y=(2, 1) 방향으로 빨간 화살표가 뻗고, 초록 점선 2x₁+x₂=2 가 마름모의 꼭짓점 (1, 0) 에서만 마름모에 닿는다. 아래에 σ(y)=max⟨x,y⟩=max(|2|,|1|)=2=‖y‖∞ 라고 적혀 있다

구체적인 짝은 ℓ1\ell_1 과 ℓ∞\ell_\infty 입니다. ℓ1\ell_1 단위공은 꼭짓점이 ±ei\pm e_i 인 마름모이고, 일차식의 최댓값은 꼭짓점에서 나오므로 σ(y)=max⁡i∣yi∣=∥y∥∞\sigma(y) = \max_i \lvert y_i \rvert = \lVert y \rVert_\infty 입니다. y=(2,1)y = (2, 1) 이면 등고선 2x1+x2=22x_1 + x_2 = 2 가 마름모에 꼭짓점 (1,0)(1, 0) 한 점에서 닿고 값이 2입니다. ℓ2\ell_2 는 자기 자신과 짝이고, 일반적으로 1/p+1/q=11/p + 1/q = 1 인 ℓp\ell_p 와 ℓq\ell_q 가 짝입니다. 쓰임새를 하나만 들면, L1 정규화 λ∥w∥1\lambda \lVert w \rVert_1 의 켤레는 상자 {∥y∥∞≤λ}\{\lVert y \rVert_\infty \le \lambda\} 의 인디케이터라서 라쏘 문제의 쌍대가 상자 제약 문제가 됩니다. 라쏘 풀이기가 「쌍대 변수가 상자 경계에 닿은 좌표만 0이 아니다」라는 판정으로 활성 특징을 고르는 것이 이 계산에서 나옵니다. 제곱 노름은 (12∥⋅∥2)∗=12∥⋅∥∗2(\tfrac12 \lVert \cdot \rVert^2)^* = \tfrac12 \lVert \cdot \rVert_*^2 로 짝이 바뀌지 않습니다.

엔트로피의 켤레

log-sum-exp

이제 이 글의 중심 계산입니다. 확률 단체 Δ={p∈Rn:pi≥0,∑ipi=1}\Delta = \{p \in \mathbb{R}^n : p_i \ge 0, \sum_i p_i = 1\} 위에서 음의 엔트로피 h(p)=∑ipilog⁡pih(p) = \sum_i p_i \log p_i 를 정의하고 단체 밖에서는 +∞+\infty 로 둡니다(0log⁡0=00 \log 0 = 0). 엔트로피 H(p)=−∑ipilog⁡piH(p) = -\sum_i p_i \log p_i 에 부호를 뒤집은 것이라 볼록입니다. 그 켤레는

h∗(y)=log⁡∑ieyih^*(y) = \log \sum_i e^{y_i}

이고, 이 함수를 log-sum-exp라 부릅니다. 최대점은 pi=eyi/∑jeyjp_i = e^{y_i} / \sum_j e^{y_j}, 곧 소프트맥스입니다.

라그랑주 승수로도 풀리지만 더 짧은 길이 있습니다. Z=∑jeyjZ = \sum_j e^{y_j}, s=softmax(y)s = \mathrm{softmax}(y) 로 두면 yi=log⁡si+log⁡Zy_i = \log s_i + \log Z 이고, 단체 위의 pp 에 대해

⟨p,y⟩−h(p)=∑ipi(log⁡si+log⁡Z)−∑ipilog⁡pi=log⁡Z−∑ipilog⁡pisi=log⁡Z−KL(p ∥ s)\begin{aligned} \langle p, y \rangle - h(p) &= \sum_i p_i (\log s_i + \log Z) - \sum_i p_i \log p_i \\ &= \log Z - \sum_i p_i \log \frac{p_i}{s_i} = \log Z - \mathrm{KL}(p \,\Vert\, s) \end{aligned}

입니다. 둘째 줄에서 ∑ipi=1\sum_i p_i = 1 을 썼습니다. KL 발산은 0 이상이고 p=sp = s 일 때만 0이므로, 상한은 log⁡Z\log Z 이고 최대점은 ss 하나입니다. 증명이 끝났습니다. 확률의 양수 조건은 따로 걸 필요가 없었습니다 — 최대점이 지수의 비율이라 저절로 양수입니다.

왼쪽 상자 「확률 p (단체 위), h(p)=Σ pᵢ log pᵢ」 와 오른쪽 상자 「점수 y (실수 벡터), h*(y)=log Σ exp(yᵢ)」 사이에 화살표 둘이 오간다. 위 화살표는 ∇h(p)=log p+1, 아래 초록 화살표는 ∇h*(y)=softmax(y). 아래 상자에 y=(2,1,0) → p=(0.665, 0.245, 0.090), ⟨p,y⟩−h(p)=2.4076=log(e²+e+1) 이라고 적혀 있다

y=(2,1,0)y = (2, 1, 0) 이면 Z=e2+e+1=11.107Z = e^2 + e + 1 = 11.107, log⁡Z=2.4076\log Z = 2.4076 이고 s=(0.665,0.245,0.090)s = (0.665, 0.245, 0.090) 입니다. 하위미분의 역이 여기서 구체적인 모양을 갖습니다. log-sum-exp 의 기울기를 직접 미분하면 ∂yilog⁡Z=eyi/Z\partial_{y_i} \log Z = e^{y_i}/Z 로 소프트맥스이고, 반대 방향으로 hh 의 기울기는 log⁡p+1\log p + 1 인데 단체 위에서는 모든 좌표에 같은 상수를 더해도 같은 점이라 사실상 log⁡p\log p, 곧 로짓입니다. 소프트맥스와 로그는 이 켤레 짝의 두 기울기 사상이고, 분류 모델의 로짓이 「상수만큼 옮겨도 같은 출력」인 이유가 단체의 이 한 차원 여유입니다. 그리고 log-sum-exp 가 max⁡iyi\max_i y_i 를 매끄럽게 만든 것이라는 흔한 말도 정확한 뜻을 얻습니다. max⁡iyi=σΔ(y)\max_i y_i = \sigma_\Delta(y) 는 단체의 지지함수, 곧 인디케이터 ιΔ\iota_\Delta 의 켤레이고, log-sum-exp 는 인디케이터에 음의 엔트로피를 더한 것의 켤레입니다.

온도

음의 엔트로피에 양수 τ\tau 를 곱하면 스케일 규칙 (αf)∗(y)=αf∗(y/α)(\alpha f)^*(y) = \alpha f^*(y/\alpha) 에 따라

(τh)∗(y)=τlog⁡∑ieyi/τ(\tau h)^*(y) = \tau \log \sum_i e^{y_i/\tau}

이고 최대점은 softmax(y/τ)\mathrm{softmax}(y/\tau) 입니다. 문제로 적으면 max⁡p∈Δ⟨p,y⟩+τH(p)\max_{p \in \Delta} \langle p, y \rangle + \tau H(p), 곧 점수의 기댓값과 엔트로피 보너스의 합을 최대화하는 문제이고, 그 답이 온도 τ\tau 의 소프트맥스입니다. τ→0\tau \to 0 이면 엔트로피 보너스가 사라져 문제는 max⁡p∈Δ⟨p,y⟩=max⁡iyi\max_{p \in \Delta}\langle p, y \rangle = \max_i y_i 로 가고 답은 최고 점수 하나에 몰린 원-핫이 됩니다. τ→∞\tau \to \infty 이면 점수가 무시되어 균등분포입니다. 볼츠만 분포 pi∝e−Ei/kTp_i \propto e^{-E_i / kT} 는 y=−Ey = -E 로 둔 같은 식이고, 그때 −kTlog⁡Z-kT \log Z 가 자유 에너지입니다. 점수에 지수를 씌워 정규화하는 모양이 여러 곳에서 나오는 것은 「기댓값 더하기 엔트로피」라는 같은 문제의 답이라서입니다.

기준 분포

엔트로피 대신 기준 분포 qq 에서의 KL 발산을 벌점으로 쓰면, 단체 위의 f(p)=β KL(p ∥ q)f(p) = \beta\,\mathrm{KL}(p \,\Vert\, q) 의 켤레를 구하는 문제가 됩니다. 위와 똑같이 Zβ=∑iqieyi/βZ_\beta = \sum_i q_i e^{y_i/\beta}, πi=qieyi/β/Zβ\pi_i = q_i e^{y_i/\beta}/Z_\beta 로 두면 yi=βlog⁡(πi/qi)+βlog⁡Zβy_i = \beta \log(\pi_i / q_i) + \beta \log Z_\beta 이고

⟨p,y⟩−β KL(p ∥ q)=β∑ipilog⁡πiqi+βlog⁡Zβ−β∑ipilog⁡piqi=βlog⁡Zβ−β KL(p ∥ π)\begin{aligned} \langle p, y \rangle - \beta\,\mathrm{KL}(p \,\Vert\, q) &= \beta \sum_i p_i \log \frac{\pi_i}{q_i} + \beta \log Z_\beta - \beta \sum_i p_i \log \frac{p_i}{q_i} \\ &= \beta \log Z_\beta - \beta\,\mathrm{KL}(p \,\Vert\, \pi) \end{aligned}

입니다. 그러니 켤레는 βlog⁡∑iqieyi/β\beta \log \sum_i q_i e^{y_i/\beta} 이고 최대점은 π∝q ey/β\pi \propto q\, e^{y/\beta} 입니다. yy 를 보상 rr, qq 를 πref\pi_{\text{ref}} 로 읽으면 이것이 첫머리의 π∗\pi^* 이고, KL 제약 최적 정책에서 라그랑지안을 세우고 미분해 양수 조건과 정규화를 따로 챙기며 얻었던 닫힌 해가 켤레 계산 한 번으로 나옵니다. 최적값 βlog⁡Zβ\beta \log Z_\beta 도 함께 나왔다는 점이 이 길의 덤입니다.

라그랑주 쌍대

쌍대 함수

이제 제약이 있는 문제로 갑니다. 원 문제를

min⁡xf0(x)s.t.fi(x)≤0  (i=1..m),hj(x)=0  (j=1..k)\min_x f_0(x) \quad \text{s.t.} \quad f_i(x) \le 0 \;(i = 1..m), \quad h_j(x) = 0 \;(j = 1..k)

로 적고 최적값을 p∗p^* 라 합니다. 제약마다 승수 λi≥0\lambda_i \ge 0, νj\nu_j 를 붙인 라그랑지안 L(x,λ,ν)=f0(x)+∑iλifi(x)+∑jνjhj(x)L(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \sum_j \nu_j h_j(x) 은 중급 56번에서 세운 것과 같습니다. 새로운 것은 그 다음입니다. xx 에 대해 라그랑지안의 하한을 먼저 잡은 함수

g(λ,ν)=inf⁡xL(x,λ,ν)g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)

를 쌍대 함수라 부르고, λ≥0\lambda \ge 0 위에서 gg 를 최대화하는 문제를 쌍대 문제, 그 최적값을 d∗d^* 라 합니다. xx 를 고정하면 LL 은 (λ,ν)(\lambda, \nu) 에 대한 아핀 함수이고 쌍대 함수는 그것들의 점별 하한이라, 원 문제가 볼록이든 아니든 gg 는 언제나 오목입니다. 쌍대 문제는 늘 볼록 최적화 문제입니다. 켤레가 어떤 함수든 볼록으로 돌려주던 것과 같은 이유입니다.

약쌍대성

약쌍대성은 d∗≤p∗d^* \le p^* 라는 부등식입니다. 증명합니다. 실현 가능한 xx, 곧 모든 제약을 만족하는 xx 와 λ≥0\lambda \ge 0 을 아무거나 잡으면 λifi(x)≤0\lambda_i f_i(x) \le 0, νjhj(x)=0\nu_j h_j(x) = 0 이므로

g(λ,ν)≤L(x,λ,ν)=f0(x)+∑iλifi(x)+∑jνjhj(x)≤f0(x)g(\lambda, \nu) \le L(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \sum_j \nu_j h_j(x) \le f_0(x)

입니다. 왼쪽 부등식은 하한의 정의이고 오른쪽은 방금의 부호입니다. 실현 가능한 xx 에 대해 하한을 잡으면 g(λ,ν)≤p∗g(\lambda, \nu) \le p^*, 다시 (λ,ν)(\lambda, \nu) 에 대해 상한을 잡으면 d∗≤p∗d^* \le p^* 입니다. 볼록성은 한 번도 쓰지 않았습니다. 쌍대 함수의 값 하나하나가 원 문제 최적값의 하한 증명서입니다.

손으로 따라갈 예를 하나 둡니다. min⁡x2\min x^2 s.t. x≥1x \ge 1, 곧 f1(x)=1−x≤0f_1(x) = 1 - x \le 0 입니다. 답은 x∗=1x^* = 1, p∗=1p^* = 1 입니다. 라그랑지안 x2+λ(1−x)x^2 + \lambda(1 - x) 는 x=λ/2x = \lambda/2 에서 최소이고 쌍대 함수는

g(λ)=λ24+λ−λ22=λ−λ24g(\lambda) = \frac{\lambda^2}{4} + \lambda - \frac{\lambda^2}{2} = \lambda - \frac{\lambda^2}{4}

입니다. λ=2\lambda = 2 에서 최대이고 값이 1이라 d∗=p∗=1d^* = p^* = 1 입니다.

가로축 λ 에 쌍대 함수 g(λ)=λ−λ²/4 가 파란 포물선으로 그려져 있고 λ=2 에서 최대 1 에 닿는다. 빨간 점선 p*=1 과 보라 점선 f(1.5)=2.25 가 수평으로 그어져 있고, λ=1 에서 g(1)=0.75 와 보라 점선 사이에 간격 1.5 가 표시돼 있다

켤레로 쓴 쌍대

선형 제약 문제에서는 쌍대 함수가 켤레로 바로 적힙니다. min⁡f(x)\min f(x) s.t. Ax=bAx = b 이면

g(ν)=inf⁡x(f(x)+ν⊤(Ax−b))=−b⊤ν−sup⁡x(⟨x,−A⊤ν⟩−f(x))=−b⊤ν−f∗(−A⊤ν)g(\nu) = \inf_x \big( f(x) + \nu^\top (Ax - b) \big) = -b^\top \nu - \sup_x \big( \langle x, -A^\top \nu \rangle - f(x) \big) = -b^\top \nu - f^*(-A^\top \nu)

입니다. 원 문제의 목적식을 켤레로 뒤집어 제약 행렬의 전치로 끌어온 것이 쌍대 문제입니다. 예로 최소노름 문제 min⁡12∥x∥2\min \tfrac12 \lVert x \rVert^2 s.t. Ax=bAx = b 를 뒤집으면 12∥⋅∥2\tfrac12 \lVert \cdot \rVert^2 이 자기 켤레이므로 g(ν)=−b⊤ν−12∥A⊤ν∥2g(\nu) = -b^\top \nu - \tfrac12 \lVert A^\top \nu \rVert^2 이고, 기울기를 0으로 두면 ν=−(AA⊤)−1b\nu = -(AA^\top)^{-1} b, 원 변수는 라그랑지안의 최소점 x=−A⊤ν=A⊤(AA⊤)−1bx = -A^\top \nu = A^\top (AA^\top)^{-1} b 입니다. 이중 하강에서 피타고라스 정리로 증명했던 최소노름 보간 해가 쌍대 문제의 해로 다시 나왔습니다. 보간 문제에서 원 변수의 차원은 특징 수이고 쌍대 변수의 차원은 제약 수, 곧 표본 수라서 특징이 많을수록 쌍대 쪽이 작은 문제입니다. 커널 방법이 쌍대에서 푸는 이유가 이것입니다.

강쌍대와 KKT

슬레이터 조건

d∗=p∗d^* = p^* 가 성립하면 강쌍대성이 성립한다고 말합니다. 위의 x2x^2 예가 그랬습니다. 볼록 문제라고 늘 성립하는 것은 아니지만, 충분조건 가운데 가장 흔히 쓰는 것이 슬레이터 조건입니다. 원 문제가 볼록이고(각 fif_i 볼록, hjh_j 아핀), 부등식 제약을 엄격하게 만족하는 점, 곧 fi(x)<0f_i(x) < 0 이면서 hj(x)=0h_j(x) = 0 인 xx 가 하나라도 있으면 강쌍대성이 성립하고 d∗d^* 를 주는 λ∗\lambda^* 도 존재합니다.

증명의 줄기만 적습니다. 등식 제약은 빼고 생각합니다. 집합 A={(u,t):∃x,  fi(x)≤ui,  f0(x)≤t}\mathcal{A} = \{(u, t) : \exists x,\; f_i(x) \le u_i,\; f_0(x) \le t\} 는 볼록 문제에서 볼록이고, 점 (0,p∗)(0, p^*) 는 그 경계에 있습니다 — tt 를 p∗p^* 보다 조금이라도 낮추면 u=0u = 0 에서 도달할 수 없으니까요. 그래서 그 점에서 A\mathcal{A} 를 받치는 초평면 (λ,μ)≠0(\lambda, \mu) \ne 0 이 있고, A\mathcal{A} 가 uu 와 tt 를 키우는 방향으로 열려 있으므로 λ≥0\lambda \ge 0, μ≥0\mu \ge 0 입니다. 초평면이 수직, 곧 μ=0\mu = 0 이면 ∑iλifi(x)≥0\sum_i \lambda_i f_i(x) \ge 0 이 모든 xx 에서 성립해야 하는데, 슬레이터 점에서는 그 합이 음수라 모순입니다. 그래서 μ>0\mu > 0 이고, μ=1\mu = 1 로 정규화한 λ\lambda 가 모든 xx 에서 f0(x)+∑iλifi(x)≥p∗f_0(x) + \sum_i \lambda_i f_i(x) \ge p^*, 곧 g(λ)≥p∗g(\lambda) \ge p^* 를 줍니다. 약쌍대성과 합치면 등호입니다. 슬레이터 조건이 하는 일은 받침 초평면이 서지 못하게 막는 것 하나입니다.

조건이 깨지면 무슨 일이 생기는지도 봅니다. min⁡x\min x s.t. x2≤0x^2 \le 0 은 실현 가능한 점이 x=0x = 0 하나라 p∗=0p^* = 0 이고 엄격히 만족하는 점이 없습니다. 쌍대 함수는 λ>0\lambda > 0 에서 inf⁡x(x+λx2)=−1/(4λ)\inf_x (x + \lambda x^2) = -1/(4\lambda) 이라 상한은 0이지만 어떤 λ\lambda 에서도 닿지 않습니다. 값은 같아도 승수가 존재하지 않는 경우이고, 이런 문제에서는 KKT 조건을 만족하는 점이 없습니다.

쌍대 간극

실현 가능한 xx 와 λ≥0\lambda \ge 0 하나씩을 손에 쥐면 차이 f0(x)−g(λ,ν)f_0(x) - g(\lambda, \nu) 를 쌍대 간극이라 부릅니다. 약쌍대성에서

f0(x)−p∗≤f0(x)−g(λ,ν)f_0(x) - p^* \le f_0(x) - g(\lambda, \nu)

이므로 간극은 xx 가 최적에서 얼마나 떨어져 있는지의 상한입니다. p∗p^* 를 모르면서도 계산할 수 있는 상한이라는 것이 요점입니다. 앞의 예에서 x=1.5x = 1.5, λ=1\lambda = 1 을 쥐면 f0=2.25f_0 = 2.25, g=0.75g = 0.75 라 간극은 1.5이고, 실제 차이 2.25−1=1.252.25 - 1 = 1.25 가 그 안에 듭니다. 원 변수와 쌍대 변수를 함께 개선해 간극이 10−610^{-6} 아래로 내려가면 멈추는 것이 내부점법과 SVM 풀이기의 종료 조건이고, 그때 「최적에서 10−610^{-6} 이내」라는 말은 근사가 아니라 증명입니다. 간극이 0이 되는 쌍 (x,λ)(x, \lambda) 를 찾으면 둘 다 최적이라는 것이 동시에 증명됩니다.

KKT 조건

강쌍대성이 성립하고 x∗x^* 와 (λ∗,ν∗)(\lambda^*, \nu^*) 가 각각 최적이라고 합시다. 약쌍대성 증명의 부등식 사슬을 다시 쓰면

f0(x∗)=g(λ∗,ν∗)≤L(x∗,λ∗,ν∗)=f0(x∗)+∑iλi∗fi(x∗)≤f0(x∗)f_0(x^*) = g(\lambda^*, \nu^*) \le L(x^*, \lambda^*, \nu^*) = f_0(x^*) + \sum_i \lambda_i^* f_i(x^*) \le f_0(x^*)

이고 양 끝이 같으니 가운데 부등식이 전부 등식입니다. 첫째 등식은 x∗x^* 가 L(⋅,λ∗,ν∗)L(\cdot, \lambda^*, \nu^*) 의 최소점이라는 뜻이라 정상 조건 0∈∂xL(x∗,λ∗,ν∗)0 \in \partial_x L(x^*, \lambda^*, \nu^*) 을 줍니다. 둘째 등식은 ∑iλi∗fi(x∗)=0\sum_i \lambda_i^* f_i(x^*) = 0 인데 각 항이 0 이하이므로 항마다 λi∗fi(x∗)=0\lambda_i^* f_i(x^*) = 0, 곧 상보 여유입니다. 여기에 원 실현 가능성과 λ∗≥0\lambda^* \ge 0 을 더하면 중급 56번의 KKT 조건 넷이 정확히 나옵니다. 거꾸로 볼록 문제에서는 KKT를 만족하는 쌍이 간극 0을 만들므로 최적의 충분조건입니다. KKT는 따로 외울 조건 목록이 아니라 「간극이 0이다」를 풀어 쓴 것입니다. 예에서는 x∗=1x^* = 1, λ∗=2\lambda^* = 2 가 정상 조건 2x∗−λ∗=02x^* - \lambda^* = 0 과 상보 여유 λ∗(1−x∗)=0\lambda^*(1 - x^*) = 0 을 둘 다 만족합니다. 승수 2는 제약을 11 에서 1+δ1 + \delta 로 옮길 때 최적값 (1+δ)2(1+\delta)^2 이 늘어나는 비율이기도 합니다.

KL 예산의 쌍대

예산과 온도의 짝

첫머리의 둘째 질문으로 돌아갑니다. 벌점 대신 예산을 거는 원 문제는

max⁡π∈ΔEπ[r]s.t.KL(π ∥ πref)≤ε\max_{\pi \in \Delta} \mathbb{E}_\pi[r] \quad \text{s.t.} \quad \mathrm{KL}(\pi \,\Vert\, \pi_{\text{ref}}) \le \varepsilon

입니다. 최대화 문제이고 목적식이 선형, 제약이 볼록이라 볼록 문제이며, π=πref\pi = \pi_{\text{ref}} 에서 KL이 0이라 ε>0\varepsilon > 0 이면 슬레이터 조건이 섭니다. 승수 β≥0\beta \ge 0 의 라그랑지안은 Eπ[r]−β(KL−ε)\mathbb{E}_\pi[r] - \beta(\mathrm{KL} - \varepsilon) 이고, π\pi 에 대한 상한은 앞 절의 켤레 계산 그대로 βlog⁡Zβ+βε\beta \log Z_\beta + \beta\varepsilon 입니다. 그래서 쌍대 문제는

min⁡β≥0  βε+βlog⁡∑aπref(a) er(a)/β\min_{\beta \ge 0} \; \beta\varepsilon + \beta \log \sum_a \pi_{\text{ref}}(a)\, e^{r(a)/\beta}

라는 일차원 볼록 문제입니다. 강쌍대성으로 그 최솟값이 예산 아래의 최대 보상과 같고, 상보 여유가 그 β∗\beta^* 에서 KL이 정확히 ε\varepsilon 이라고 말합니다. 예산과 온도는 원 변수와 쌍대 변수의 짝이고, 예산 하나를 정하면 그에 맞는 β\beta 는 이 일차원 문제를 풀어 얻습니다. PPO의 적응형 KL 계수가 측정한 KL이 목표보다 크면 β\beta 를 올리고 작으면 내리는 것은 이 쌍대 문제에서 한 걸음씩 기울기를 따라가는 일입니다. 쌍대 목적식을 β\beta 로 미분하면 ε−KL(πβ ∥ πref)\varepsilon - \mathrm{KL}(\pi_\beta \,\Vert\, \pi_{\text{ref}}) 이 나오기 때문입니다.

코드로 확인하기

위의 계산을 격자와 무작위 표본으로 맞춰 봅니다. 켤레의 공식, log-sum-exp 의 최대점, KL 정규화 정책의 최적값, x2x^2 예의 쌍대, 그리고 KL 예산의 쌍대를 차례로 확인합니다.

import numpy as np

rng = np.random.default_rng(0)

# 1) x^2 의 켤레를 격자 위의 sup 으로 계산해 y^2/4 와 견준다
xs = np.linspace(-10, 10, 200001)
for y in [-3.0, 2.0, 5.0]:
    num = np.max(y * xs - xs**2)
    print(f"f*({y:+.0f}) 격자 = {num:.4f}, 공식 y^2/4 = {y*y/4:.4f}")

# 2) 음의 엔트로피의 켤레는 log-sum-exp, 최대점은 softmax
def logsumexp(y):
    m = y.max()
    return m + np.log(np.exp(y - m).sum())

def softmax(y):
    e = np.exp(y - y.max())
    return e / e.sum()

def neg_entropy(p):
    return np.sum(p * np.log(p))

y = np.array([2.0, 1.0, 0.0])
p = softmax(y)
print("softmax(y)      =", np.round(p, 4))
print("<p,y> - h(p)    =", round(float(p @ y - neg_entropy(p)), 6))
print("logsumexp(y)    =", round(float(logsumexp(y)), 6))
others = rng.dirichlet(np.ones(3), size=100000)
vals = others @ y - np.sum(others * np.log(others), axis=1)
print("임의의 p 10만 개 중 최댓값 =", round(float(vals.max()), 6))

# 3) KL 정규화 정책: max E_pi[r] - beta*KL(pi||ref)
r = np.array([1.0, 0.0, -1.0])
ref = np.array([0.2, 0.5, 0.3])
beta = 0.5
Z = np.sum(ref * np.exp(r / beta))
pi = ref * np.exp(r / beta) / Z
obj = lambda q: q @ r - beta * np.sum(q * np.log(q / ref))
print("pi*             =", np.round(pi, 4))
print("목적식(pi*)     =", round(float(obj(pi)), 6))
print("beta * log Z    =", round(float(beta * np.log(Z)), 6))
qs = rng.dirichlet(np.ones(3), size=100000)
best = max(obj(q) for q in qs)
print("임의 정책 최댓값 =", round(float(best), 6))

# 4) min x^2  s.t. x >= 1 의 쌍대 함수 g(lam) = lam - lam^2/4
lams = np.linspace(0, 4, 4001)
g = lams - lams**2 / 4
k = np.argmax(g)
print(f"쌍대 최댓값 g = {g[k]:.4f} (lam = {lams[k]:.3f}), 원 문제 p* = 1.0000")
x_feas, lam_try = 1.5, 1.0
print(f"간극 증명서: f(1.5) - g(1) = {x_feas**2 - (lam_try - lam_try**2/4):.4f}")

# 5) KL 예산 eps 를 거는 원 문제와 그 쌍대: min_b  b*eps + b*log Z(b)
eps = 0.3
bs = np.linspace(0.05, 5, 99001)
dual = np.array([b * eps + b * np.log(np.sum(ref * np.exp(r / b))) for b in bs])
b_star = bs[np.argmin(dual)]
pb = ref * np.exp(r / b_star); pb /= pb.sum()
print(f"쌍대 최적 beta = {b_star:.4f}, 쌍대 값 = {dual.min():.4f}")
print(f"그 beta 의 정책: KL = {np.sum(pb*np.log(pb/ref)):.4f}, E[r] = {pb @ r:.4f}")
f*(-3) 격자 = 2.2500, 공식 y^2/4 = 2.2500
f*(+2) 격자 = 1.0000, 공식 y^2/4 = 1.0000
f*(+5) 격자 = 6.2500, 공식 y^2/4 = 6.2500
softmax(y)      = [0.6652 0.2447 0.09  ]
<p,y> - h(p)    = 2.407606
logsumexp(y)    = 2.407606
임의의 p 10만 개 중 최댓값 = 2.407604
pi*             = [0.7322 0.2477 0.0201]
목적식(pi*)     = 0.351155
beta * log Z    = 0.351155
임의 정책 최댓값 = 0.351153
쌍대 최댓값 g = 1.0000 (lam = 2.000), 원 문제 p* = 1.0000
간극 증명서: f(1.5) - g(1) = 1.5000
쌍대 최적 beta = 0.8677, 쌍대 값 = 0.4385
그 beta 의 정책: KL = 0.3000, E[r] = 0.4385

넷째 블록까지는 본문의 계산을 숫자로 다시 본 것입니다. 무작위로 뽑은 확률 벡터와 정책 십만 개가 켤레의 값에 아래에서 다가가기만 하고 넘지 못합니다. 마지막 두 줄이 첫머리의 둘째 질문에 대한 답입니다. 보상 (1,0,−1)(1, 0, -1) 과 참조 분포 (0.2,0.5,0.3)(0.2, 0.5, 0.3) 에서 KL 예산 0.3을 걸면 쌍대 문제가 β∗=0.868\beta^* = 0.868 을 고르고, 그 β\beta 의 정책은 KL을 정확히 0.3 쓰며 기대 보상 0.4385가 쌍대 값과 같습니다. 상보 여유와 강쌍대성이 둘 다 숫자로 섰습니다.

암묵적 보상

마지막으로 DPO가 서 있는 자리를 켤레의 언어로 적습니다. 펜첼–영의 등호 조건은 최대점 π∗\pi^* 와 점수 rr 이 하위미분의 짝, 곧 r∈∂(β KL(⋅ ∥ πref))(π∗)r \in \partial(\beta\,\mathrm{KL}(\cdot \,\Vert\, \pi_{\text{ref}}))(\pi^*) 라는 것입니다. KL의 기울기는 βlog⁡(π/πref)\beta \log(\pi/\pi_{\text{ref}}) 에 단체 방향의 상수를 더한 것이므로

r(a)=βlog⁡π∗(a)πref(a)+βlog⁡Zβr(a) = \beta \log \frac{\pi^*(a)}{\pi_{\text{ref}}(a)} + \beta \log Z_\beta

입니다. 중급 57번이 「보상을 정책으로 적기」라고 부른 식이 바로 하위미분의 역입니다. 정책에서 보상으로 가는 사상은 켤레 짝의 기울기이고, 상수 βlog⁡Zβ\beta \log Z_\beta 는 단체 위에서 기울기가 상수만큼 정해지지 않는 그 한 차원 여유입니다. DPO가 같은 프롬프트의 두 답을 빼서 이 상수를 지우는 것은 켤레 짝이 상수 방향을 보지 못한다는 사실을 그대로 이용한 것입니다. 첫머리 리뷰어의 두 질문은 이렇게 닫힙니다. 지수에 올려 정규화하는 모양은 기댓값에 엔트로피나 KL을 더한 문제를 켤레로 뒤집은 답이고, 예산과 β\beta 는 슬레이터 조건이 보장하는 강쌍대성 아래 원 문제와 쌍대 문제의 변수 짝입니다.

연습

  1. f(x)=exf(x) = e^x 의 켤레 f∗(y)f^*(y) 를 y>0y > 0, y=0y = 0, y<0y < 0 세 경우로 나눠 구하고, y=1y = 1 에서 펜첼–영의 등호를 주는 xx 를 확인하세요.
    y>0y > 0 이면 xy−exxy - e^x 의 최대점이 ex=ye^x = y, 곧 x=log⁡yx = \log y 라 f∗(y)=ylog⁡y−yf^*(y) = y\log y - y 입니다. y=0y = 0 이면 sup⁡(−ex)=0\sup(-e^x) = 0 이고(0log0 = 0으로 같은 식), y<0y < 0 이면 x→−∞x \to -\infty 에서 xy→∞xy \to \infty 라 +∞+\infty 입니다. y=1y = 1 에서 x=0x = 0 이고 f(0)+f∗(1)=1+(0−1)=0=0⋅1f(0) + f^*(1) = 1 + (0 - 1) = 0 = 0 \cdot 1 로 등호입니다.
  2. f(x)=2x2f(x) = 2x^2 의 켤레를 구하고, (x,y)=(1,4)(x, y) = (1, 4) 와 (1,2)(1, 2) 에서 펜첼–영 부등식의 양변을 각각 계산하세요.
    스케일 규칙이나 xy−2x2xy - 2x^2 의 꼭짓점 x=y/4x = y/4 에서 f∗(y)=y2/8f^*(y) = y^2/8 입니다. (1,4)(1, 4) 에서 2+2=4=1⋅42 + 2 = 4 = 1 \cdot 4 로 등호인데, f′(1)=4f'(1) = 4 라 yy 가 기울기와 같기 때문입니다. (1,2)(1, 2) 에서는 2+0.5=2.5>22 + 0.5 = 2.5 > 2 입니다.
  3. y=(1,0)y = (1, 0) 과 온도 τ=0.5\tau = 0.5 에서 max⁡p∈Δ⟨p,y⟩+τH(p)\max_{p \in \Delta} \langle p, y \rangle + \tau H(p) 의 최적값과 최대점을 구하세요.
    최적값은 τlog⁡(e1/τ+e0)=0.5log⁡(e2+1)=0.5×2.1269=1.0635\tau \log(e^{1/\tau} + e^{0}) = 0.5 \log(e^2 + 1) = 0.5 \times 2.1269 = 1.0635 입니다. 최대점은 softmax(2,0)=(e2,1)/(e2+1)=(0.8808,0.1192)\mathrm{softmax}(2, 0) = (e^2, 1)/(e^2 + 1) = (0.8808, 0.1192) 입니다.
  4. min⁡(x−3)2\min (x - 3)^2 s.t. x≤1x \le 1 의 쌍대 함수 g(λ)g(\lambda) 를 구하고, d∗=p∗d^* = p^* 인지와 KKT 조건을 확인하세요.
    L=(x−3)2+λ(x−1)L = (x-3)^2 + \lambda(x - 1) 은 x=3−λ/2x = 3 - \lambda/2 에서 최소이고 g(λ)=λ2/4+λ(2−λ/2)=2λ−λ2/4g(\lambda) = \lambda^2/4 + \lambda(2 - \lambda/2) = 2\lambda - \lambda^2/4 입니다. λ∗=4\lambda^* = 4 에서 d∗=4d^* = 4 이고, 원 문제는 x∗=1x^* = 1 에서 p∗=4p^* = 4 라 같습니다. 정상 조건 2(1−3)+4=02(1 - 3) + 4 = 0, 상보 여유 4⋅(1−1)=04 \cdot (1 - 1) = 0 이 둘 다 섭니다.
  5. 최소노름 문제 min⁡12∥x∥2\min \tfrac12 \lVert x \rVert^2 s.t. x1+2x2+2x3=9x_1 + 2x_2 + 2x_3 = 9 를 쌍대로 풀어 ν∗\nu^*, x∗x^*, 최적값을 구하세요.
    a=(1,2,2)a = (1, 2, 2), ∥a∥2=9\lVert a \rVert^2 = 9 라 g(ν)=−9ν−12⋅9ν2g(\nu) = -9\nu - \tfrac12 \cdot 9 \nu^2 이고 ν∗=−1\nu^* = -1, d∗=9−4.5=4.5d^* = 9 - 4.5 = 4.5 입니다. 원 변수는 x∗=−ν∗a=(1,2,2)x^* = -\nu^* a = (1, 2, 2) 이고 12∥x∗∥2=4.5\tfrac12 \lVert x^* \rVert^2 = 4.5 로 쌍대 값과 같습니다.
  6. 답이 둘인 프롬프트에서 보상 r=(0,2)r = (0, 2), 참조 분포 (0.8,0.2)(0.8, 0.2), β=1\beta = 1 일 때 KL 정규화 정책 π∗\pi^* 와 최적값을 구하고, 기대 보상에서 KL을 뺀 값이 그 최적값과 같은지 확인하세요.
    Z=0.8+0.2e2=2.2778Z = 0.8 + 0.2 e^2 = 2.2778 이라 π∗=(0.8,0.2e2)/Z=(0.3512,0.6488)\pi^* = (0.8, 0.2e^2)/Z = (0.3512, 0.6488), 최적값은 log⁡Z=0.8232\log Z = 0.8232 입니다. 기대 보상은 2×0.6488=1.29762 \times 0.6488 = 1.2976, KL은 0.3512log⁡(0.3512/0.8)+0.6488log⁡(0.6488/0.2)=0.47440.3512 \log(0.3512/0.8) + 0.6488 \log(0.6488/0.2) = 0.4744 라 차가 0.82320.8232 로 같습니다.

이 글은 문제를 뒤집는 도구를 세웠습니다. 켤레는 함수를 기울기의 언어로 옮기고, 쌍대 문제는 제약을 승수의 언어로 옮기며, 둘 다 원래가 무엇이든 볼록한 문제를 돌려줍니다. 다음 글 고급 13번 · 「근접 연산자와 거울 하강: 기하를 바꿔서 내려가기」는 이 도구로 알고리즘을 만듭니다. 이 글의 하위미분의 역이 근접 연산자로, 음의 엔트로피와 log-sum-exp 의 짝이 단체 위의 거울 하강으로 이어지고, KL 정규화 정책 π∗\pi^* 가 거울 하강의 한 걸음이라는 관점이 거기서 나옵니다.


읽어주셔서 감사합니다. 😊

LATEST

수학의 최신 글

수학2026.11.17

다양체 위의 최적화: 직교 제약과 Muon의 직교화가 하는 일

차트·접공간·리만 계량·측지선·후퇴로 다양체를 세우고, 스티펠·그라스만·양정치 행렬·확률 단체의 접공간과 사영을 계산한 뒤, 리만 그래디언트가 유클리드 그래디언트의 접공간 사영임을 증명하고 극분해 후퇴와 뉴턴–슐츠 반복의 수렴 조건을 다룹니다.

고급46 MIN
수학2026.11.17

프리컨디셔닝의 이론: Adam에서 K-FAC·Shampoo·Muon까지 한 줄로

갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.

고급41 MIN
수학2026.11.17

확률적 근사와 SGD의 연속 극한: 수렴한다는 말의 정확한 뜻

로빈스–먼로 조건과 마팅게일 잡음으로 SGD의 수렴을 정확히 정의하고, 볼록·강볼록·PL·비볼록에서의 수렴률과 오라클 하한을 계산한 뒤, SGD를 확률미분방정식으로 읽어 학습률/배치가 온도가 되는 관점과 안정성의 가장자리를 다룹니다.

고급48 MIN