켤레함수를 접선의 절편으로 세우고 펜첼–영 부등식·이중 켤레·쌍대 노름을 증명한 뒤, 음의 엔트로피의 켤레가 log-sum-exp이고 그 기울기가 softmax라는 계산으로 KL 정규화 정책의 닫힌 해를 다시 얻습니다. 라그랑주 쌍대, 약쌍대·강쌍대, 쌍대 간극까지 다룹니다.
PALDYN Team//48 MIN READ
12MATH
고급
켤레함수 · 르장드르–펜첼 변환
언어 모델을 사람의 선호에 맞추는 팀이 RLHF 단계의 목적식을 리뷰하고 있습니다. 프롬프트 하나에 대해 정책 π 가 답 a 를 고를 확률을 정하고, 보상 모델이 매긴 점수 r(a) 의 기댓값을 올리되 참조 모델 πref 에서 너무 멀어지지 않도록 KL 벌점을 겁니다. 목적식은 Eπ[r]−βKL(π∥πref) 이고, 그 최댓점이 π∗(a)∝πref(a)er(a)/β 라는 닫힌 해가 DPO 손실의 출발점입니다. 리뷰어 한 사람이 묻습니다. 소프트맥스 출력층도 점수를 지수에 올려 정규화하고, 볼츠만 분포도 에너지를 지수에 올려 정규화합니다. 같은 모양이 왜 이렇게 여러 곳에서 나오는가. 그리고 KL 예산을 0.3으로 걸었을 때 그에 맞는 β 는 누가 정하는가.
지난 글에서 미분이 안 되는 볼록함수의 기울기를 하위미분으로 넓히고, 강볼록성과 매끄러움이 서로를 비추는 짝이라는 것을 보았습니다. 이 글은 그 짝을 만드는 변환 자체를 세웁니다. 함수 하나를 그 함수가 받는 기울기들의 함수로 바꿔 적는 변환, 곧 켤레함수입니다. 리뷰어의 두 질문은 이 변환 하나로 답이 납니다. 소프트맥스와 볼츠만과 π∗ 는 전부 음의 엔트로피를 켤레로 뒤집은 결과이고, KL 예산과 β 의 짝은 원 문제를 뒤집은 쌍대 문제의 변수 짝입니다. 라그랑주 승수와 KKT에서 손으로 세운 조건들도 여기서 쌍대성의 특수한 경우로 다시 읽힙니다.
켤레함수
정의와 볼록성
함수 f:Rn→R∪{+∞} 의 켤레함수는
f∗(y)=supx(⟨x,y⟩−f(x))
로 정의합니다. x 를 하나 고정하면 괄호 안은 y 에 대한 일차식에 상수를 더한 것, 곧 아핀 함수입니다. 그러니 f∗ 는 아핀 함수들의 점별 상한이고, 점별 상한은 언제나 볼록이며 에피그래프가 닫힌 반공간들의 교집합이라 닫혀 있습니다. 증명은 한 줄입니다. y1,y2 와 θ∈[0,1] 에 대해 각 x 마다 ⟨x,θy1+(1−θ)y2⟩−f(x)=θ(⟨x,y1⟩−f(x))+(1−θ)(⟨x,y2⟩−f(x))≤θf∗(y1)+(1−θ)f∗(y2) 이고, 왼쪽에서 x 에 대한 상한을 잡으면 f∗(θy1+(1−θ)y2) 가 오른쪽 이하가 됩니다. 놀라운 것은 f 가 볼록이 아니어도 이것이 성립한다는 점입니다. 켤레는 어떤 함수를 넣어도 볼록함수를 돌려줍니다. 이 변환을 물리학에서 오래 써 온 이름으로 르장드르–펜첼 변환이라고도 부릅니다. 라그랑주 역학에서 해밀턴 역학으로 넘어갈 때 속도를 운동량으로 바꾸는 바로 그 변환입니다.
가장 먼저 계산해 볼 것은 f(x)=x2 입니다. xy−x2 은 x 에 대한 아래로 열린 포물선이라 꼭짓점 x=y/2 에서 최대이고, 값은 y2/2−y2/4=y2/4 입니다. 그래서 f∗(y)=y2/4 입니다. 더 일반적으로 양의 정부호 행렬 Q 로 f(x)=21x⊤Qx 이면 f∗(y)=21y⊤Q−1y 이고, Q=I 이면 21∥x∥2 은 자기 자신의 켤레입니다. 곡률이 큰 함수의 켤레는 곡률이 작아집니다. 이 뒤집힘이 아래 강볼록–매끄러움 짝의 씨앗입니다.
계산을 줄여 주는 규칙도 몇 개 적어 둡니다. 상수를 더하면 (f+c)∗=f∗−c 이고, 양수 α 를 곱하면 (αf)∗(y)=αf∗(y/α) 입니다. 둘째는 supx(⟨x,y⟩−αf(x))=αsupx(⟨x,y/α⟩−f(x)) 로 바로 나옵니다. 이 규칙이 뒤에서 온도와 β 를 처리합니다.
접선의 절편
켤레에는 그림이 하나 붙습니다. 기울기가 y 인 직선 ⟨x,y⟩ 을 그래프 위에 그리고, 직선이 곡선보다 얼마나 높이 떠 있는지를 x 마다 잽니다. 그 간격 ⟨x,y⟩−f(x) 가 가장 큰 값이 f∗(y) 입니다. 같은 것을 거꾸로 보면, 기울기 y 인 직선을 아래로 내려 곡선에 처음 닿게 할 때 내려야 하는 거리입니다. 닿은 직선은 접선이고 그 절편이 −f∗(y) 입니다.
y=2 로 확인합니다. 직선 2x 와 포물선 x2 의 간격 2x−x2 은 x=1 에서 가장 커서 1이고, 공식 y2/4=1 과 같습니다. 직선을 1만큼 내린 2x−1 이 (1,1) 에서 포물선에 접하고 절편이 −1 입니다. 그러니 볼록함수 하나를 적는 방법이 둘입니다. 점들의 모임으로 적거나, 모든 기울기에 대해 그 기울기의 접선 절편을 적거나. 켤레는 둘째 방식의 표입니다. 볼록함수가 자기 접선들 위에 놓인다는 것, 곧 접선들의 위쪽 포락선이라는 것을 받아들이면 그 표만으로 원래 함수가 복원된다는 것도 예상할 수 있고, 그것이 다음 절의 이중 켤레 정리입니다.
펜첼–영 부등식
정의에서 바로 나오는 부등식이 하나 있습니다. 상한은 어느 한 항보다 크거나 같으므로 모든 x,y 에 대해
f(x)+f∗(y)≥⟨x,y⟩
입니다. 이것을 펜첼–영 부등식이라 부릅니다. f(x)=21x2 이면 21x2+21y2≥xy 라는 산술–기하 부등식의 한 꼴이고, f(x)=∣x∣p/p 이면 고전적인 영 부등식 ∣x∣p/p+∣y∣q/q≥xy (단 1/p+1/q=1) 이 됩니다.
등호가 언제 서는지가 더 중요합니다. 볼록함수 f 에 대해 다음 둘은 같습니다.
f(x)+f∗(y)=⟨x,y⟩⟺y∈∂f(x)
증명합니다. 지난 글의 정의대로 y∈∂f(x) 는 모든 z 에 대해 f(z)≥f(x)+⟨y,z−x⟩ 라는 뜻입니다. 항을 옮기면 모든 z 에 대해 ⟨x,y⟩−f(x)≥⟨z,y⟩−f(z), 곧 x 가 ⟨⋅,y⟩−f 의 최대점이라는 뜻이고, 이는 ⟨x,y⟩−f(x)=f∗(y) 와 같습니다. 그래프로 읽으면 x 에서 기울기 y 인 직선이 접선이라는 말입니다. 이 등호 조건이 이 글 전체의 도구입니다. 켤레의 최대점을 찾는 일이 곧 기울기 방정식 y∈∂f(x) 를 x 에 대해 푸는 일입니다.
이중 켤레
볼록 폐포
켤레를 두 번 취한 f∗∗=(f∗)∗ 를 이중 켤레라 부릅니다. 첫째 사실은 어떤 f 에 대해서든 f∗∗≤f 라는 것입니다. 펜첼–영 부등식을 ⟨x,y⟩−f∗(y)≤f(x) 로 옮겨 적고 왼쪽에서 y 에 대한 상한을 잡으면 f∗∗(x)≤f(x) 입니다. 그리고 f∗∗ 는 켤레이니 볼록이고 닫혀 있습니다.
둘째 사실이 펜첼–모로 정리입니다. f 가 닫힌 진볼록함수, 곧 에피그래프가 닫힌 볼록집합이고 어디선가 유한하며 −∞ 를 갖지 않는 함수이면 f∗∗=f 입니다. 증명의 뼈대를 적습니다. 닫힌 볼록집합은 그 밖의 점과 분리 초평면으로 갈리므로, 에피그래프 밖의 점 (x0,t0), 곧 t0<f(x0) 마다 f 아래에 놓이면서 x0 에서 t0 보다 높은 아핀 함수 ⟨y,x⟩−b 를 찾을 수 있습니다(초평면이 수직이 되는 경우는 진함수 조건으로 피해 갑니다). 그런데 ⟨y,x⟩−b≤f(x) 가 모든 x 에서 성립한다는 것은 b≥f∗(y) 와 같으므로, 기울기 y 의 아핀 하한 가운데 가장 높은 것은 ⟨y,x⟩−f∗(y) 입니다. 따라서 모든 아핀 하한의 상한은 supy(⟨y,x⟩−f∗(y))=f∗∗(x) 이고, 분리 정리가 그 상한이 f 에 닿는다고 말해 줍니다. 볼록이 아닌 f 에서는 같은 논증이 f 대신 f 아래에 놓인 가장 큰 닫힌 볼록함수를 돌려줍니다. 그것을 f 의 볼록 폐포라 부르고, f∗∗ 가 바로 그것입니다.
이중 우물 f(x)=min{(x−1)2,(x+1)2} 로 계산해 봅니다. 최솟값의 켤레는 켤레들의 최댓값입니다 — 상한 두 개를 한꺼번에 잡는 것이니까요. (x−1)2 의 켤레는 x=1+y/2 에서 y+y2/4, (x+1)2 의 켤레는 −y+y2/4 라서 f∗(y)=∣y∣+y2/4 입니다. 이것을 다시 뒤집습니다. ∣x∣≤1 이면 xy−∣y∣≤0 이라 xy−∣y∣−y2/4 의 상한은 y=0 에서의 0입니다. x>1 이면 y>0 쪽에서 (x−1)y−y2/4 를 최대화해 y=2(x−1), 값 (x−1)2 입니다. 그러니 f∗∗ 는 두 골짜기 바깥에서는 f 와 같고 사이에서는 0인 직선입니다. 봉우리 f(0)=1 은 켤레를 두 번 거치며 사라졌습니다. 켤레가 보는 것은 접선뿐이고, 봉우리 꼭대기는 어떤 접선에도 닿지 않기 때문입니다.
하위미분의 역
닫힌 진볼록함수에서는 펜첼–영의 등호가 x 와 y 에 대해 대칭이라는 것이 이중 켤레 정리에서 나옵니다. f∗∗=f 이니 등식 f(x)+f∗(y)=⟨x,y⟩ 은 f∗ 와 그 켤레 f 에 대한 펜첼–영의 등호이기도 하고, 따라서
y∈∂f(x)⟺x∈∂f∗(y)
입니다. 하위미분 사상 ∂f∗ 는 ∂f 의 역입니다. f 의 기울기가 y 가 되는 점을 찾고 싶으면 f∗ 의 기울기를 y 에서 구하면 됩니다. f(x)=x2 이면 f′(x)=2x 의 역은 y/2 이고, f∗(y)=y2/4 의 도함수가 정확히 y/2 입니다. 미분이 안 되는 자리도 같습니다. f(x)=∣x∣ 의 하위미분은 0에서 구간 [−1,1] 이고, 아래에서 보듯 켤레는 [−1,1] 의 인디케이터라 그 하위미분은 y∈(−1,1) 에서 {0}, 끝점 y=1 에서 [0,∞) 입니다. 「기울기가 구간 안의 아무 값이나 되는 꺾인 점」과 「값이 한 점에 몰리는 평평한 구간」이 서로의 켤레 그림입니다.
강볼록과 매끄러움
지난 글은 f 가 μ-강볼록이면 f∗ 가 1/μ-매끄럽고 그 역도 성립한다는 짝을 보였습니다. 하위미분의 역이라는 관점에서 이 짝은 거의 당연합니다. 강볼록성은 기울기가 적어도 μ 의 비율로 자란다는 조건, ⟨g1−g2,x1−x2⟩≥μ∥x1−x2∥2 이고, 역사상으로 옮기면 x 의 변화가 g 의 변화의 1/μ 배를 넘지 못한다는 조건, 곧 ∇f∗ 의 립시츠 상수가 1/μ 라는 조건이 됩니다. x2 은 2-강볼록이고 켤레 y2/4 의 기울기 y/2 는 21-립시츠입니다. 이 짝이 쌍대 문제에서 힘을 씁니다. 원 문제의 목적식이 강볼록이면 쌍대 함수는 매끄러워져 경사법으로 바로 올라갈 수 있습니다.
지지함수와 쌍대 노름
지지함수
볼록집합 C 의 인디케이터 함수 ιC 는 C 안에서 0, 밖에서 +∞ 인 함수입니다. 제약을 목적식 안에 넣는 장치이고, 지난 글에서 확장실수값 함수로 일반화한 이유가 이것이었습니다. 그 켤레는
ιC∗(y)=supx∈C⟨x,y⟩=:σC(y)
이고, 이것을 C 의 지지함수라 부릅니다. 방향 y 로 집합을 가장 멀리 밀었을 때 그 방향의 좌표입니다. 지지함수는 양의 동차성 σC(ty)=tσC(y) (t≥0) 를 가지고, 닫힌 볼록집합은 지지함수로 복원됩니다. 이중 켤레 정리를 인디케이터에 적용한 것이 곧 「닫힌 볼록집합은 자기를 담는 반공간들의 교집합」이라는 고전적인 사실입니다.
노름의 켤레
노름 ∥⋅∥ 의 쌍대 노름을 ∥y∥∗=sup∥x∥≤1⟨x,y⟩ 로 정의합니다. 정의 자체가 단위공의 지지함수입니다. 이제 노름의 켤레를 증명합니다.
f(x)=∥x∥⟹f∗(y)=ι{∥y∥∗≤1}(y)
∥y∥∗≤1 이면 쌍대 노름의 정의에서 ⟨x,y⟩≤∥x∥∥y∥∗≤∥x∥ 이므로 ⟨x,y⟩−∥x∥≤0 이고, x=0 에서 0이 되니 상한은 0입니다. ∥y∥∗>1 이면 ∥x0∥≤1 이면서 ⟨x0,y⟩>1 인 x0 가 있고, 그러면 ∥x0∥≤1 이라 t>0 에 대해 ⟨tx0,y⟩−∥tx0∥≥t(⟨x0,y⟩−1)→∞ 입니다. 끝입니다. 노름의 켤레는 쌍대 노름 단위공의 인디케이터이고, 펜첼–모로로 뒤집으면 노름은 쌍대 단위공의 지지함수입니다.
구체적인 짝은 ℓ1 과 ℓ∞ 입니다. ℓ1 단위공은 꼭짓점이 ±ei 인 마름모이고, 일차식의 최댓값은 꼭짓점에서 나오므로 σ(y)=maxi∣yi∣=∥y∥∞ 입니다. y=(2,1) 이면 등고선 2x1+x2=2 가 마름모에 꼭짓점 (1,0) 한 점에서 닿고 값이 2입니다. ℓ2 는 자기 자신과 짝이고, 일반적으로 1/p+1/q=1 인 ℓp 와 ℓq 가 짝입니다. 쓰임새를 하나만 들면, L1 정규화 λ∥w∥1 의 켤레는 상자 {∥y∥∞≤λ} 의 인디케이터라서 라쏘 문제의 쌍대가 상자 제약 문제가 됩니다. 라쏘 풀이기가 「쌍대 변수가 상자 경계에 닿은 좌표만 0이 아니다」라는 판정으로 활성 특징을 고르는 것이 이 계산에서 나옵니다. 제곱 노름은 (21∥⋅∥2)∗=21∥⋅∥∗2 로 짝이 바뀌지 않습니다.
엔트로피의 켤레
log-sum-exp
이제 이 글의 중심 계산입니다. 확률 단체 Δ={p∈Rn:pi≥0,∑ipi=1} 위에서 음의 엔트로피h(p)=∑ipilogpi 를 정의하고 단체 밖에서는 +∞ 로 둡니다(0log0=0). 엔트로피 H(p)=−∑ipilogpi 에 부호를 뒤집은 것이라 볼록입니다. 그 켤레는
h∗(y)=log∑ieyi
이고, 이 함수를 log-sum-exp라 부릅니다. 최대점은 pi=eyi/∑jeyj, 곧 소프트맥스입니다.
라그랑주 승수로도 풀리지만 더 짧은 길이 있습니다. Z=∑jeyj, s=softmax(y) 로 두면 yi=logsi+logZ 이고, 단체 위의 p 에 대해
입니다. 둘째 줄에서 ∑ipi=1 을 썼습니다. KL 발산은 0 이상이고 p=s 일 때만 0이므로, 상한은 logZ 이고 최대점은 s 하나입니다. 증명이 끝났습니다. 확률의 양수 조건은 따로 걸 필요가 없었습니다 — 최대점이 지수의 비율이라 저절로 양수입니다.
y=(2,1,0) 이면 Z=e2+e+1=11.107, logZ=2.4076 이고 s=(0.665,0.245,0.090) 입니다. 하위미분의 역이 여기서 구체적인 모양을 갖습니다. log-sum-exp 의 기울기를 직접 미분하면 ∂yilogZ=eyi/Z 로 소프트맥스이고, 반대 방향으로 h 의 기울기는 logp+1 인데 단체 위에서는 모든 좌표에 같은 상수를 더해도 같은 점이라 사실상 logp, 곧 로짓입니다. 소프트맥스와 로그는 이 켤레 짝의 두 기울기 사상이고, 분류 모델의 로짓이 「상수만큼 옮겨도 같은 출력」인 이유가 단체의 이 한 차원 여유입니다. 그리고 log-sum-exp 가 maxiyi 를 매끄럽게 만든 것이라는 흔한 말도 정확한 뜻을 얻습니다. maxiyi=σΔ(y) 는 단체의 지지함수, 곧 인디케이터 ιΔ 의 켤레이고, log-sum-exp 는 인디케이터에 음의 엔트로피를 더한 것의 켤레입니다.
온도
음의 엔트로피에 양수 τ 를 곱하면 스케일 규칙 (αf)∗(y)=αf∗(y/α) 에 따라
(τh)∗(y)=τlog∑ieyi/τ
이고 최대점은 softmax(y/τ) 입니다. 문제로 적으면 maxp∈Δ⟨p,y⟩+τH(p), 곧 점수의 기댓값과 엔트로피 보너스의 합을 최대화하는 문제이고, 그 답이 온도τ 의 소프트맥스입니다. τ→0 이면 엔트로피 보너스가 사라져 문제는 maxp∈Δ⟨p,y⟩=maxiyi 로 가고 답은 최고 점수 하나에 몰린 원-핫이 됩니다. τ→∞ 이면 점수가 무시되어 균등분포입니다. 볼츠만 분포 pi∝e−Ei/kT 는 y=−E 로 둔 같은 식이고, 그때 −kTlogZ 가 자유 에너지입니다. 점수에 지수를 씌워 정규화하는 모양이 여러 곳에서 나오는 것은 「기댓값 더하기 엔트로피」라는 같은 문제의 답이라서입니다.
기준 분포
엔트로피 대신 기준 분포 q 에서의 KL 발산을 벌점으로 쓰면, 단체 위의 f(p)=βKL(p∥q) 의 켤레를 구하는 문제가 됩니다. 위와 똑같이 Zβ=∑iqieyi/β, πi=qieyi/β/Zβ 로 두면 yi=βlog(πi/qi)+βlogZβ 이고
입니다. 그러니 켤레는 βlog∑iqieyi/β 이고 최대점은 π∝qey/β 입니다. y 를 보상 r, q 를 πref 로 읽으면 이것이 첫머리의 π∗ 이고, KL 제약 최적 정책에서 라그랑지안을 세우고 미분해 양수 조건과 정규화를 따로 챙기며 얻었던 닫힌 해가 켤레 계산 한 번으로 나옵니다. 최적값 βlogZβ 도 함께 나왔다는 점이 이 길의 덤입니다.
라그랑주 쌍대
쌍대 함수
이제 제약이 있는 문제로 갑니다. 원 문제를
minxf0(x)s.t.fi(x)≤0(i=1..m),hj(x)=0(j=1..k)
로 적고 최적값을 p∗ 라 합니다. 제약마다 승수 λi≥0, νj 를 붙인 라그랑지안 L(x,λ,ν)=f0(x)+∑iλifi(x)+∑jνjhj(x) 은 중급 56번에서 세운 것과 같습니다. 새로운 것은 그 다음입니다. x 에 대해 라그랑지안의 하한을 먼저 잡은 함수
g(λ,ν)=infxL(x,λ,ν)
를 쌍대 함수라 부르고, λ≥0 위에서 g 를 최대화하는 문제를 쌍대 문제, 그 최적값을 d∗ 라 합니다. x 를 고정하면 L 은 (λ,ν) 에 대한 아핀 함수이고 쌍대 함수는 그것들의 점별 하한이라, 원 문제가 볼록이든 아니든 g 는 언제나 오목입니다. 쌍대 문제는 늘 볼록 최적화 문제입니다. 켤레가 어떤 함수든 볼록으로 돌려주던 것과 같은 이유입니다.
약쌍대성
약쌍대성은 d∗≤p∗ 라는 부등식입니다. 증명합니다. 실현 가능한 x, 곧 모든 제약을 만족하는 x 와 λ≥0 을 아무거나 잡으면 λifi(x)≤0, νjhj(x)=0 이므로
입니다. 왼쪽 부등식은 하한의 정의이고 오른쪽은 방금의 부호입니다. 실현 가능한 x 에 대해 하한을 잡으면 g(λ,ν)≤p∗, 다시 (λ,ν) 에 대해 상한을 잡으면 d∗≤p∗ 입니다. 볼록성은 한 번도 쓰지 않았습니다. 쌍대 함수의 값 하나하나가 원 문제 최적값의 하한 증명서입니다.
손으로 따라갈 예를 하나 둡니다. minx2 s.t. x≥1, 곧 f1(x)=1−x≤0 입니다. 답은 x∗=1, p∗=1 입니다. 라그랑지안 x2+λ(1−x) 는 x=λ/2 에서 최소이고 쌍대 함수는
g(λ)=4λ2+λ−2λ2=λ−4λ2
입니다. λ=2 에서 최대이고 값이 1이라 d∗=p∗=1 입니다.
켤레로 쓴 쌍대
선형 제약 문제에서는 쌍대 함수가 켤레로 바로 적힙니다. minf(x) s.t. Ax=b 이면
입니다. 원 문제의 목적식을 켤레로 뒤집어 제약 행렬의 전치로 끌어온 것이 쌍대 문제입니다. 예로 최소노름 문제 min21∥x∥2 s.t. Ax=b 를 뒤집으면 21∥⋅∥2 이 자기 켤레이므로 g(ν)=−b⊤ν−21∥A⊤ν∥2 이고, 기울기를 0으로 두면 ν=−(AA⊤)−1b, 원 변수는 라그랑지안의 최소점 x=−A⊤ν=A⊤(AA⊤)−1b 입니다. 이중 하강에서 피타고라스 정리로 증명했던 최소노름 보간 해가 쌍대 문제의 해로 다시 나왔습니다. 보간 문제에서 원 변수의 차원은 특징 수이고 쌍대 변수의 차원은 제약 수, 곧 표본 수라서 특징이 많을수록 쌍대 쪽이 작은 문제입니다. 커널 방법이 쌍대에서 푸는 이유가 이것입니다.
강쌍대와 KKT
슬레이터 조건
d∗=p∗ 가 성립하면 강쌍대성이 성립한다고 말합니다. 위의 x2 예가 그랬습니다. 볼록 문제라고 늘 성립하는 것은 아니지만, 충분조건 가운데 가장 흔히 쓰는 것이 슬레이터 조건입니다. 원 문제가 볼록이고(각 fi 볼록, hj 아핀), 부등식 제약을 엄격하게 만족하는 점, 곧 fi(x)<0 이면서 hj(x)=0 인 x 가 하나라도 있으면 강쌍대성이 성립하고 d∗ 를 주는 λ∗ 도 존재합니다.
증명의 줄기만 적습니다. 등식 제약은 빼고 생각합니다. 집합 A={(u,t):∃x,fi(x)≤ui,f0(x)≤t} 는 볼록 문제에서 볼록이고, 점 (0,p∗) 는 그 경계에 있습니다 — t 를 p∗ 보다 조금이라도 낮추면 u=0 에서 도달할 수 없으니까요. 그래서 그 점에서 A 를 받치는 초평면 (λ,μ)=0 이 있고, A 가 u 와 t 를 키우는 방향으로 열려 있으므로 λ≥0, μ≥0 입니다. 초평면이 수직, 곧 μ=0 이면 ∑iλifi(x)≥0 이 모든 x 에서 성립해야 하는데, 슬레이터 점에서는 그 합이 음수라 모순입니다. 그래서 μ>0 이고, μ=1 로 정규화한 λ 가 모든 x 에서 f0(x)+∑iλifi(x)≥p∗, 곧 g(λ)≥p∗ 를 줍니다. 약쌍대성과 합치면 등호입니다. 슬레이터 조건이 하는 일은 받침 초평면이 서지 못하게 막는 것 하나입니다.
조건이 깨지면 무슨 일이 생기는지도 봅니다. minx s.t. x2≤0 은 실현 가능한 점이 x=0 하나라 p∗=0 이고 엄격히 만족하는 점이 없습니다. 쌍대 함수는 λ>0 에서 infx(x+λx2)=−1/(4λ) 이라 상한은 0이지만 어떤 λ 에서도 닿지 않습니다. 값은 같아도 승수가 존재하지 않는 경우이고, 이런 문제에서는 KKT 조건을 만족하는 점이 없습니다.
쌍대 간극
실현 가능한 x 와 λ≥0 하나씩을 손에 쥐면 차이 f0(x)−g(λ,ν) 를 쌍대 간극이라 부릅니다. 약쌍대성에서
f0(x)−p∗≤f0(x)−g(λ,ν)
이므로 간극은 x 가 최적에서 얼마나 떨어져 있는지의 상한입니다. p∗ 를 모르면서도 계산할 수 있는 상한이라는 것이 요점입니다. 앞의 예에서 x=1.5, λ=1 을 쥐면 f0=2.25, g=0.75 라 간극은 1.5이고, 실제 차이 2.25−1=1.25 가 그 안에 듭니다. 원 변수와 쌍대 변수를 함께 개선해 간극이 10−6 아래로 내려가면 멈추는 것이 내부점법과 SVM 풀이기의 종료 조건이고, 그때 「최적에서 10−6 이내」라는 말은 근사가 아니라 증명입니다. 간극이 0이 되는 쌍 (x,λ) 를 찾으면 둘 다 최적이라는 것이 동시에 증명됩니다.
KKT 조건
강쌍대성이 성립하고 x∗ 와 (λ∗,ν∗) 가 각각 최적이라고 합시다. 약쌍대성 증명의 부등식 사슬을 다시 쓰면
이고 양 끝이 같으니 가운데 부등식이 전부 등식입니다. 첫째 등식은 x∗ 가 L(⋅,λ∗,ν∗) 의 최소점이라는 뜻이라 정상 조건 0∈∂xL(x∗,λ∗,ν∗) 을 줍니다. 둘째 등식은 ∑iλi∗fi(x∗)=0 인데 각 항이 0 이하이므로 항마다 λi∗fi(x∗)=0, 곧 상보 여유입니다. 여기에 원 실현 가능성과 λ∗≥0 을 더하면 중급 56번의 KKT 조건 넷이 정확히 나옵니다. 거꾸로 볼록 문제에서는 KKT를 만족하는 쌍이 간극 0을 만들므로 최적의 충분조건입니다. KKT는 따로 외울 조건 목록이 아니라 「간극이 0이다」를 풀어 쓴 것입니다. 예에서는 x∗=1, λ∗=2 가 정상 조건 2x∗−λ∗=0 과 상보 여유 λ∗(1−x∗)=0 을 둘 다 만족합니다. 승수 2는 제약을 1 에서 1+δ 로 옮길 때 최적값 (1+δ)2 이 늘어나는 비율이기도 합니다.
KL 예산의 쌍대
예산과 온도의 짝
첫머리의 둘째 질문으로 돌아갑니다. 벌점 대신 예산을 거는 원 문제는
maxπ∈ΔEπ[r]s.t.KL(π∥πref)≤ε
입니다. 최대화 문제이고 목적식이 선형, 제약이 볼록이라 볼록 문제이며, π=πref 에서 KL이 0이라 ε>0 이면 슬레이터 조건이 섭니다. 승수 β≥0 의 라그랑지안은 Eπ[r]−β(KL−ε) 이고, π 에 대한 상한은 앞 절의 켤레 계산 그대로 βlogZβ+βε 입니다. 그래서 쌍대 문제는
minβ≥0βε+βlog∑aπref(a)er(a)/β
라는 일차원 볼록 문제입니다. 강쌍대성으로 그 최솟값이 예산 아래의 최대 보상과 같고, 상보 여유가 그 β∗ 에서 KL이 정확히 ε 이라고 말합니다. 예산과 온도는 원 변수와 쌍대 변수의 짝이고, 예산 하나를 정하면 그에 맞는 β 는 이 일차원 문제를 풀어 얻습니다. PPO의 적응형 KL 계수가 측정한 KL이 목표보다 크면 β 를 올리고 작으면 내리는 것은 이 쌍대 문제에서 한 걸음씩 기울기를 따라가는 일입니다. 쌍대 목적식을 β 로 미분하면 ε−KL(πβ∥πref) 이 나오기 때문입니다.
코드로 확인하기
위의 계산을 격자와 무작위 표본으로 맞춰 봅니다. 켤레의 공식, log-sum-exp 의 최대점, KL 정규화 정책의 최적값, x2 예의 쌍대, 그리고 KL 예산의 쌍대를 차례로 확인합니다.
import numpy as nprng = 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, 최대점은 softmaxdef 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.5Z = np.sum(ref * np.exp(r / beta))pi = ref * np.exp(r / beta) / Zobj = 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/4lams = np.linspace(0, 4, 4001)g = lams - lams**2 / 4k = np.argmax(g)print(f"쌍대 최댓값 g = {g[k]:.4f} (lam = {lams[k]:.3f}), 원 문제 p* = 1.0000")x_feas, lam_try = 1.5, 1.0print(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.3bs = 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.2500f*(+2) 격자 = 1.0000, 공식 y^2/4 = 1.0000f*(+5) 격자 = 6.2500, 공식 y^2/4 = 6.2500softmax(y) = [0.6652 0.2447 0.09 ]<p,y> - h(p) = 2.407606logsumexp(y) = 2.407606임의의 p 10만 개 중 최댓값 = 2.407604pi* = [0.7322 0.2477 0.0201]목적식(pi*) = 0.351155beta * 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) 과 참조 분포 (0.2,0.5,0.3) 에서 KL 예산 0.3을 걸면 쌍대 문제가 β∗=0.868 을 고르고, 그 β 의 정책은 KL을 정확히 0.3 쓰며 기대 보상 0.4385가 쌍대 값과 같습니다. 상보 여유와 강쌍대성이 둘 다 숫자로 섰습니다.
암묵적 보상
마지막으로 DPO가 서 있는 자리를 켤레의 언어로 적습니다. 펜첼–영의 등호 조건은 최대점 π∗ 와 점수 r 이 하위미분의 짝, 곧 r∈∂(βKL(⋅∥πref))(π∗) 라는 것입니다. KL의 기울기는 βlog(π/πref) 에 단체 방향의 상수를 더한 것이므로
r(a)=βlogπref(a)π∗(a)+βlogZβ
입니다. 중급 57번이 「보상을 정책으로 적기」라고 부른 식이 바로 하위미분의 역입니다. 정책에서 보상으로 가는 사상은 켤레 짝의 기울기이고, 상수 βlogZβ 는 단체 위에서 기울기가 상수만큼 정해지지 않는 그 한 차원 여유입니다. DPO가 같은 프롬프트의 두 답을 빼서 이 상수를 지우는 것은 켤레 짝이 상수 방향을 보지 못한다는 사실을 그대로 이용한 것입니다. 첫머리 리뷰어의 두 질문은 이렇게 닫힙니다. 지수에 올려 정규화하는 모양은 기댓값에 엔트로피나 KL을 더한 문제를 켤레로 뒤집은 답이고, 예산과 β 는 슬레이터 조건이 보장하는 강쌍대성 아래 원 문제와 쌍대 문제의 변수 짝입니다.
연습
f(x)=ex 의 켤레 f∗(y) 를 y>0, y=0, y<0 세 경우로 나눠 구하고, y=1 에서 펜첼–영의 등호를 주는 x 를 확인하세요.
y>0 이면 xy−ex 의 최대점이 ex=y, 곧 x=logy 라 f∗(y)=ylogy−y 입니다. y=0 이면 sup(−ex)=0 이고(0log0 = 0으로 같은 식), y<0 이면 x→−∞ 에서 xy→∞ 라 +∞ 입니다. y=1 에서 x=0 이고 f(0)+f∗(1)=1+(0−1)=0=0⋅1 로 등호입니다.
f(x)=2x2 의 켤레를 구하고, (x,y)=(1,4) 와 (1,2) 에서 펜첼–영 부등식의 양변을 각각 계산하세요.
스케일 규칙이나 xy−2x2 의 꼭짓점 x=y/4 에서 f∗(y)=y2/8 입니다. (1,4) 에서 2+2=4=1⋅4 로 등호인데, f′(1)=4 라 y 가 기울기와 같기 때문입니다. (1,2) 에서는 2+0.5=2.5>2 입니다.
y=(1,0) 과 온도 τ=0.5 에서 maxp∈Δ⟨p,y⟩+τH(p) 의 최적값과 최대점을 구하세요.
min(x−3)2 s.t. x≤1 의 쌍대 함수 g(λ) 를 구하고, d∗=p∗ 인지와 KKT 조건을 확인하세요.
L=(x−3)2+λ(x−1) 은 x=3−λ/2 에서 최소이고 g(λ)=λ2/4+λ(2−λ/2)=2λ−λ2/4 입니다. λ∗=4 에서 d∗=4 이고, 원 문제는 x∗=1 에서 p∗=4 라 같습니다. 정상 조건 2(1−3)+4=0, 상보 여유 4⋅(1−1)=0 이 둘 다 섭니다.
최소노름 문제 min21∥x∥2 s.t. x1+2x2+2x3=9 를 쌍대로 풀어 ν∗, x∗, 최적값을 구하세요.
a=(1,2,2), ∥a∥2=9 라 g(ν)=−9ν−21⋅9ν2 이고 ν∗=−1, d∗=9−4.5=4.5 입니다. 원 변수는 x∗=−ν∗a=(1,2,2) 이고 21∥x∗∥2=4.5 로 쌍대 값과 같습니다.
답이 둘인 프롬프트에서 보상 r=(0,2), 참조 분포 (0.8,0.2), β=1 일 때 KL 정규화 정책 π∗ 와 최적값을 구하고, 기대 보상에서 KL을 뺀 값이 그 최적값과 같은지 확인하세요.
Z=0.8+0.2e2=2.2778 이라 π∗=(0.8,0.2e2)/Z=(0.3512,0.6488), 최적값은 logZ=0.8232 입니다. 기대 보상은 2×0.6488=1.2976, KL은 0.3512log(0.3512/0.8)+0.6488log(0.6488/0.2)=0.4744 라 차가 0.8232 로 같습니다.
이 글은 문제를 뒤집는 도구를 세웠습니다. 켤레는 함수를 기울기의 언어로 옮기고, 쌍대 문제는 제약을 승수의 언어로 옮기며, 둘 다 원래가 무엇이든 볼록한 문제를 돌려줍니다. 다음 글 고급 13번 · 「근접 연산자와 거울 하강: 기하를 바꿔서 내려가기」는 이 도구로 알고리즘을 만듭니다. 이 글의 하위미분의 역이 근접 연산자로, 음의 엔트로피와 log-sum-exp 의 짝이 단체 위의 거울 하강으로 이어지고, KL 정규화 정책 π∗ 가 거울 하강의 한 걸음이라는 관점이 거기서 나옵니다.
갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.