엔트로피 정규화

1. 개요[편집]

엔트로피 정규화 Entropic Regularization
하는 일	목적함수에 −εH 를 더해 선형 문제를 강볼록 문제로 바꾼다
기본 항등식	단체 위 max ⟨p,z⟩ + εH(p) = ε·logsumexp(z/ε)
해의 꼴	언제나 지수족 — 소프트맥스 / 깁스 커널
최적수송	P = diag(u) K diag(v), K = exp(−C/ε) — 싱크혼
강화학습	소프트 벨만, 볼츠만 정책
게임	양자반응균형 (로짓 QRE)
대가	O(ε) 편향, ε 작을수록 반복수 증가·언더플로

엔트로피 정규화는 최적화 문제의 목적함수에 엔트로피 항을 더해(또는 음의 엔트로피를 빼) 해를 매끄럽고 유일하게 만드는 일반적인 기법이다. 확률 단체 $\Delta_n=\{p\ge0,\ \sum_i p_i=1\}$ 위의 선형계획

$$\max_{p\in\Delta_n}\ \langle p, z\rangle$$

은 해가 꼭짓점에 붙는다 — 답은 $\arg\max_i z_i$ 에 몰빵한 원핫 벡터이고, $z$ 가 조금만 흔들려도 답이 한 꼭짓점에서 다른 꼭짓점으로 점프한다. 미분이 거의 모든 곳에서 0이고 동률이면 정의조차 안 된다. 여기에 $\varepsilon\mathcal{H}(p) = -\varepsilon\sum_i p_i\log p_i$ 를 얹으면 사정이 완전히 달라진다.

$$\max_{p\in\Delta_n}\ \Bigl\{\langle p,z\rangle + \varepsilon\mathcal{H}(p)\Bigr\} = \varepsilon\log\sum_i e^{z_i/\varepsilon}, \qquad p^\star_i = \frac{e^{z_i/\varepsilon}}{\sum_j e^{z_j/\varepsilon}}$$

이 한 줄이 문서 전체의 씨앗이다. 최적값은 로그-합-지수, 최적해는 소프트맥스 함수다. 목적함수가 강볼록해졌으므로 해가 유일하고, $z$ 에 대해 무한히 매끄럽고, 자코비안이 $\frac{1}{\varepsilon}(\mathrm{diag}(p) - pp^\top)$ 로 닫힌 형태로 나온다. 즉 이 블록을 계산 그래프 한가운데에 끼워 넣고 자동 미분을 돌릴 수 있다. $\varepsilon\to0$ 이면 원래의 딱딱한 $\max$ 로 돌아간다.

정리하면 엔트로피 정규화는 “최댓값 고르기”를 “부드럽게 저울질하기”로 바꿔 주는 표준 변환이고, 대가는 $O(\varepsilon\log n)$ 만큼의 편향이다. 아래 두 무대에서 이 거래가 특히 남는 장사가 된다.

2. 최적수송 — 싱크혼[편집]

두 확률벡터 $a\in\Delta_n$, $b\in\Delta_m$ 사이의 최적 수송 문제는 결합분포(수송계획)를 찾는 선형계획이다.

$$\min_{P\in U(a,b)}\ \langle C, P\rangle, \qquad U(a,b) = \bigl\{P\ge0:\ P\mathbf{1}=a,\ P^\top\mathbf{1}=b\bigr\}$$

$C_{ij}$ 는 $i$ 에서 $j$ 로 한 단위를 옮기는 비용이고, 최적값이 와서스타인 거리(의 거듭제곱)다. 정확히 풀면 네트워크 심플렉스나 헝가리안 계열로 $O(n^3\log n)$ 급이고, 해는 꼭짓점 — 즉 극단적으로 희소한 순열 비슷한 행렬이라 미분이 안 된다. 크기 $n=10^4$ 짜리 두 이미지 히스토그램을 비교하겠다는 순간 계산량과 미분 불가능성이 동시에 벽이 된다.

쿠튀리(2013)의 처방이 바로 엔트로피 정규화다.

$$\min_{P\in U(a,b)}\ \langle C,P\rangle - \varepsilon\, \mathcal{H}(P), \qquad \mathcal{H}(P) = -\sum_{ij} P_{ij}\bigl(\log P_{ij} - 1\bigr)$$

제약 $P\mathbf{1}=a$, $P^\top\mathbf{1}=b$ 에 라그랑주 승수법으로 $f\in\mathbb{R}^n$, $g\in\mathbb{R}^m$ 을 붙이고 $\partial/\partial P_{ij}=0$ 을 풀면 해의 꼴이 강제로 결정된다.

$$P^\star_{ij} = u_i\, K_{ij}\, v_j, \qquad K_{ij} = e^{-C_{ij}/\varepsilon},\quad u_i = e^{f_i/\varepsilon},\ v_j = e^{g_j/\varepsilon}$$

$n\times m$ 개의 미지수가 $n+m$ 개로 줄었다. 남은 일은 두 주변분포 제약을 맞추도록 $u,v$ 를 찾는 것뿐이고, 그 방법이 싱크혼-크노프 반복 — 행 정규화와 열 정규화를 번갈아 하는 것이다.

$$u \leftarrow \frac{a}{Kv}, \qquad v \leftarrow \frac{b}{K^\top u} \qquad(\text{나눗셈은 성분별})$$

행렬-벡터 곱 두 번이 반복 하나의 전부다. GPU에서 밀집 행렬 곱으로 돌아가고, 여러 문제를 배치로 동시에 푸는 것도 자연스럽다. “정확한 LP 대신 exp 한 번과 곱셈 몇 줄”이라는 교환이 최적수송을 실험실 밖으로 끌어낸 결정적 계기였다.¹

3. 왜 행/열 정규화가 답이 되는가 — 브레그만 사영[편집]

싱크혼 반복이 왜 수렴하는지는 목적함수를 다시 쓰면 즉시 보인다. $K_{ij}=e^{-C_{ij}/\varepsilon}$ 을 참조 측도로 놓으면

$$\langle C,P\rangle - \varepsilon\mathcal{H}(P) = \varepsilon\,\mathrm{KL}(P\,\Vert\,K) + \text{상수}$$

이므로, 엔트로피 정규화 최적수송은 깁스 커널 $K$ 를 수송 다면체 $U(a,b)$ 위로 KL 사영한 것이다. 그런데 $U(a,b)$ 는 두 아핀 집합의 교집합이다.

$$\mathcal{C}_1=\{P: P\mathbf{1}=a\}, \qquad \mathcal{C}_2=\{P: P^\top\mathbf{1}=b\}$$

각각에 대한 KL 사영은 닫힌 형태로 나온다 — $\mathcal{C}_1$ 사영은 각 행을 $a_i$ 에 맞춰 스케일링하는 것이고, $\mathcal{C}_2$ 사영은 각 열을 $b_j$ 에 맞춰 스케일링하는 것이다. 싱크혼 반복 = 두 아핀 집합에 대한 KL(브레그만) 사영의 교대이며, 브레그만 발산에 대한 교대 사영이 아핀 집합의 교집합으로 수렴한다는 고전 결과가 그대로 적용된다.² 미러 하강 문서에서 본 “정의역의 기하에 맞는 발산을 고르면 투영이 정규화 한 번으로 끝난다”는 이야기의 가장 화려한 사례다. 브레그만 발산이 KL일 때 사영이 스케일링이 된다는 사실 하나로 알고리즘 전체가 세 줄이 된 셈.

수렴 속도는 힐베르트 사영 거리에 대한 축약으로 분석되며, 선형 수렴이되 축약 계수가 $\varepsilon$ 에 민감하다. $\varepsilon$ 이 작아질수록 $K$ 의 동적 범위가 커지면서 축약이 느려진다.

4. ε 를 얼마나 작게 잡을 것인가[편집]

$\varepsilon$ 은 정확도와 계산량을 맞바꾸는 유일한 손잡이이고, 양쪽 끝에서 서로 다른 방식으로 아프다.

• $\varepsilon\to0$. 정규화 해는 원래 최적수송의 해로 수렴한다(최적해가 여럿이면 그중 엔트로피가 최대인 것). 대신 반복 수가 늘고, 무엇보다 $K_{ij}=e^{-C_{ij}/\varepsilon}$ 이 배정밀도에서도 통째로 언더플로한다. $C_{ij}=1$, $\varepsilon=10^{-3}$ 이면 이미 $e^{-1000}$ 이라 그냥 0이고, 그 뒤 $Kv$ 를 나누는 순간 NaN이 나온다.
• 대책은 로그 영역. $u,v$ 대신 쌍대변수 $f,g$ 를 직접 갱신한다.

$$f_i \leftarrow \varepsilon\log a_i - \varepsilon\log\sum_j \exp\!\Bigl(\frac{g_j - C_{ij}}{\varepsilon}\Bigr)$$

즉 곱셈 갱신을 log-sum-exp 갱신으로 바꾸고, 최댓값을 빼내는 표준 안정화를 쓴다. 대신 밀집 행렬 곱의 이점이 줄어 느려진다. $\varepsilon$ 을 크게 시작해 점점 줄이는 $\varepsilon$-스케일링(어닐링)이 실무 표준 조합이다.

• $\varepsilon$ 이 크면. 수송계획이 뭉개져서 흐릿해진다. 극단적으로 $\varepsilon\to\infty$ 면 $P\to ab^\top$, 즉 아무 구조도 없는 독립 결합이다. 비용값에도 편향이 남아 $\mathrm{OT}_\varepsilon(a,a)\ne0$ 이라는 성가신 성질이 생긴다 — 같은 분포끼리 비교했는데 거리가 0이 아니다.

마지막 문제를 정면으로 고친 것이 싱크혼 발산(Sinkhorn divergence)이다.

$$S_\varepsilon(a,b) = \mathrm{OT}_\varepsilon(a,b) - \tfrac12\mathrm{OT}_\varepsilon(a,a) - \tfrac12\mathrm{OT}_\varepsilon(b,b)$$

자기 자신과의 항을 빼서 디바이어싱하면 $S_\varepsilon(a,a)=0$ 이 회복되고, $S_\varepsilon$ 은 $\varepsilon\to0$ 에서 최적수송으로, $\varepsilon\to\infty$ 에서 에너지 거리(MMD 계열)로 보간하는 양이 된다. 생성모형 학습의 손실로 쓸 때는 사실상 이쪽이 기본형이다.

미분 가능성도 여기서 값을 한다. 싱크혼 반복은 그 자체가 미분 가능한 연산의 유한 합성이라 반복을 그대로 펼쳐 역전파할 수 있고, 메모리가 아까우면 포락선 정리나 음함수 미분으로 쌍대해에서 기울기를 뽑는다. 최적수송이 손실 함수·신경망 계층·미분 가능한 정렬 연산으로 쓰이게 된 것이 전부 이 성질 덕이다.

5. 강화학습과 게임 — 같은 항등식, 다른 무대[편집]

개요의 항등식에서 $z$ 자리에 행동가치 $Q(s,\cdot)$ 를 넣고 상태마다 하나씩 풀면 그대로 소프트 벨만 방정식이 된다. 최적 정책은 $\pi(a\mid s)\propto\exp(Q(s,a)/\alpha)$ 인 볼츠만 꼴이고, 최적값은 $\max$ 대신 로그-합-지수다. 이 각도는 최대 엔트로피 강화 학습 문서가 온도 자동조절·SAC 구현까지 다루고 있으니 그쪽으로 넘긴다. 여기서 강조할 것은 구조의 동일성뿐이다.

무대	정규화 대상	참조 측도	해의 꼴
최적수송	결합분포 P	깁스 커널 exp(−C/ε)	diag(u) K diag(v)
강화학습	상태별 정책 π	균등분포 (또는 사전정책)	exp(Q/α) 정규화
게임	각 참가자의 혼합전략	균등분포	exp(u/λ) 정규화
분류 손실	예측 분포 p	균등분포	소프트맥스

전부 “선형 목적 + 엔트로피 = 지수족 해” 라는 하나의 사실이다. 지수족의 자연모수 좌표에서 보면 이 갱신들은 전부 직선 이동이고, 원시 좌표에서 보면 곱셈 갱신이다. 미러 하강이 이 공통 뼈대를 최적화 알고리즘 쪽에서 서술한 것이며, 엔트로피 거울을 쓴 미러 하강의 갱신식과 위 표의 해들이 같은 형태인 것은 우연이 아니다. 정규화 세기 $\varepsilon$ 은 미러 하강에서 스텝 크기의 역수 역할을 한다.

게임 쪽 이름은 양자반응균형(quantal response equilibrium, QRE)이다. 맥켈비와 팰프리(1995)가 제안한 것으로, 참가자가 최선반응을 정확히 고르는 대신 기대이득에 로짓 확률로 반응한다고 본다.

$$\sigma_i(a) \propto \exp\bigl(\lambda\, u_i(a,\sigma_{-i})\bigr)$$

$\lambda\to\infty$ 면 내시 균형으로, $\lambda\to0$ 이면 균등 무작위로 간다. 실험경제학에서 “사람이 균형에서 살짝 벗어난 선택을 하는” 현상을 설명하는 표준 모형이자, 계산 쪽에서는 균형이 유일하고 매끄러워지므로 연속법(homotopy)으로 $\lambda$ 를 0에서 키워 가며 내시 균형을 추적할 수 있게 해 주는 장치다. 여기서도 엔트로피가 하는 일은 똑같다 — 꼭짓점에 붙는 딱딱한 해를 내부의 매끄러운 해로 밀어 넣는 것.

6. 한계와 대안[편집]

엔트로피 정규화가 만능은 아니다. 세 가지를 기억하면 된다.

• 해가 절대 희소하지 않다. 지수 함수는 0을 만들지 않으므로 모든 $P_{ij}>0$ 이다. 진짜 희소한 매칭(할당 문제, 이분 매칭)이 필요하면 잘못된 도구다. 이 지점의 대안이 스파스맥스나 트살리스 엔트로피 정규화로, 제곱 노름 벌점을 쓰면 해가 유클리드 사영이 되어 정확히 0인 성분이 생긴다.
• 편향이 남는다. $\varepsilon$ 을 0으로 보내지 않는 한 답은 원래 문제의 답이 아니다. 디바이어싱(싱크혼 발산)이나 $\varepsilon$-스케일링으로 줄일 수는 있어도 공짜는 아니다.
• 수치적으로 예민하다. 로그 영역 안정화 없이 작은 $\varepsilon$ 을 쓰면 조용히 NaN이 난다. 그리고 첫 반복에서 터지지 않고 한참 뒤에 터지는 것이 더 성가시다.³

그럼에도 이 기법이 표준이 된 이유는 단순하다. 조합적이거나 미분 불가능한 문제를 매끄럽고 유일하며 미분 가능한 문제로 바꾸는 데 필요한 코드가 몇 줄뿐이고, 그 몇 줄이 어떤 무대에서든 같은 형태이기 때문이다.

7. 관련 문서[편집]

• 최적 수송 · 와서스타인 거리 · 쿨백-라이블러 발산
• 브레그만 발산 · 미러 하강 · 르장드르-펜셸 변환
• 소프트맥스 함수 · 지수족 · 최대 엔트로피 원리
• 최대 엔트로피 강화 학습 · 강화 학습
• 게임 이론 · 내시 균형 · 선형계획법 · 이분 매칭
• 볼록 최적화 · 라그랑주 승수법 · 자동 미분

8. Footnotes[편집]

1. Cuturi, M. (2013). “Sinkhorn Distances: Lightspeed Computation of Optimal Transport”, NeurIPS. 제목의 “lightspeed”가 과장이 아닌 게, 당시 기준 수백 배 가속이었다. 정작 싱크혼-크노프 반복 자체는 1960년대 통계학에서 분할표를 주변합에 맞추는 반복 비례 맞춤(IPF, 1940년대 데밍-스테판)으로 이미 굴러다니던 물건이다. 새 이론이 아니라 오래된 알고리즘의 재발견이었다는 점이 오히려 이 논문의 매력. ↩

2. 아핀 집합이 두 개라서 단순 교대 사영으로 충분하다는 점이 중요하다. 제약이 셋 이상이거나 볼록집합이 아핀이 아니면 교대 사영은 교집합의 사영으로 안 가고 딕스트라 보정이 필요해진다. 불균형 최적수송(주변분포 제약을 KL 벌점으로 완화한 버전)이 여전히 싱크혼 꼴 반복으로 풀리는 것도 이 구조가 유지되기 때문이다. ↩

3. 실무에서 싱크혼이 안 도는 이유의 8할은 (가) 비용행렬을 최대값으로 정규화하지 않아 $\varepsilon$ 의 스케일 감각이 무너졌거나 (나) 주변분포 $a,b$ 의 합이 1이 아니거나 (다) 로그 영역을 안 썼거나다. 셋 다 아니라면 진짜 알고리즘 문제일 수 있으니 그때 논문을 열자. ↩