브레그만 발산

통계 수치해석 최적설계 마지막 수정: 2026-08-08 04:36:41

1. 개요[편집]

브레그만 발산 Bregman Divergence
제안	Lev M. Bregman (1967)
정의	D_φ(x, y) = φ(x) − φ(y) − ⟨∇φ(y), x − y⟩
기하	볼록함수와 그 접평면 사이의 간격
거리인가	아니다(비대칭 + 삼각부등식 불성립)
특수 사례	제곱거리, KL 발산, 이토쿠라-사이토, 스타인 손실

브레그만 발산은 미분가능한 엄격 볼록함수 $\varphi$ 를 하나 고정한 뒤, 함수값과 접평면 값의 차이로 두 점의 어긋남을 재는 척도다.

D_\varphi(x, y) = \varphi(x) - \varphi(y) - \langle \nabla\varphi(y),\, x - y\rangle

$y$ 에서 $\varphi$ 에 접평면을 긋고, 그 접평면을 $x$ 까지 연장했을 때 진짜 함수값이 접평면보다 얼마나 위에 있는가 — 그게 $D_\varphi(x,y)$ 다. 볼록성이 곧 “접평면은 함수 아래에 있다”이므로 $D_\varphi \ge 0$ 은 정의에서 바로 나오고, 엄격 볼록이면 $x = y$ 에서만 0이다.

대신 거리 공리는 대부분 포기한다. 대칭이 아니고( $D_\varphi(x,y)\ne D_\varphi(y,x)$ ), 삼각부등식도 없다. 그럼에도 이 물건이 최적화·통계·군집화에서 표준 도구가 된 이유는, 거리 공리 대신 훨씬 쓸모 있는 항등식 두 개를 주기 때문이다. 첫째 인수에 대해 볼록하고, 곧 볼 삼점 항등식을 만족한다. 이 두 개면 수렴 증명이 굴러간다.¹

2. 왜 $\varphi$ 를 바꾸면 아는 것들이 다 나오나[편집]

$\varphi$ 를 갈아 끼우면 서로 관계없어 보이던 척도들이 한 가족으로 묶인다.

$\varphi(x) = \frac{1}{2}\lVert x\rVert_2^2$ → $D_\varphi(x,y) = \frac{1}{2}\lVert x-y\rVert_2^2$ . 유클리드 제곱거리. 이때만 대칭이고, 사실상 유일한 대칭 사례다.
$\varphi(x) = \sum_i x_i\log x_i$ (음의 엔트로피) → $D_\varphi(x,y) = \sum_i \bigl(x_i\log\frac{x_i}{y_i} - x_i + y_i\bigr)$ . 확률 심플렉스 위에서는 $\sum x_i = \sum y_i = 1$ 이라 뒤 두 항이 상쇄되어 정확히 **쿨백-라이블러 발산**이 된다. KL이 왜 비대칭인지가 “어느 점에서 접평면을 그었나”의 문제로 환원된다.
$\varphi(x) = -\sum_i \log x_i$ (버그 엔트로피) → 이토쿠라-사이토 발산 $\sum_i (\frac{x_i}{y_i} - \log\frac{x_i}{y_i} - 1)$ . 음성·오디오 스펙트럼 정합에서 스케일 불변성이 필요할 때 쓴다.
$\varphi(X) = -\log\det X$ (양정부호 행렬 위) → 스타인 손실(로그디트 발산) $\mathrm{tr}(XY^{-1}) - \log\det(XY^{-1}) - n$ . 공분산 추정과 행렬 근접법의 기본 손실.
$\varphi(x) = \lVert x\rVert_A^2 = x^\top A x$ ( $A \succ 0$ ) → 마할라노비스 제곱거리.

$\ell_1$ 노름은 브레그만 발산을 만들지 못한다. 미분불가능이기도 하지만 근본적으로 볼록성이 엄격하지 않아서다. 브레그만 틀은 “매끄럽고 엄격 볼록한 생성함수” 위에서만 산다.

3. 삼점 항등식 — 수렴 증명의 주력 도구[편집]

유클리드 공간에서 최적화 증명을 하다 보면 평행사변형 항등식 $\lVert a-c\rVert^2 = \lVert a-b\rVert^2 + \lVert b-c\rVert^2 + 2\langle b-a, c-b\rangle$ 을 끝없이 쓴다. 브레그만 세계에서 그 자리를 대신하는 것이 삼점 항등식이다.

D_\varphi(x, z) = D_\varphi(x, y) + D_\varphi(y, z) + \langle \nabla\varphi(y) - \nabla\varphi(z),\; x - y\rangle

정의를 그대로 대입하면 세 줄 만에 증명되는데, 이 한 줄로 미러 하강·근접법·온라인 학습의 후회(regret) 상한이 거의 다 나온다. 세 항이 각각 “현재 오차 / 이번 스텝 이동량 / 내적으로 남는 교차항”에 대응해서, 교차항만 코시-슈바르츠로 처리하면 되기 때문이다.

교차항이 사라지는 특수한 경우가 일반화 피타고라스 정리다. 볼록집합 $C$ 위로의 브레그만 사영 $y^\star = \arg\min_{y\in C} D_\varphi(y, z)$ 에 대해 모든 $x \in C$ 에서

D_\varphi(x, z) \ \ge\ D_\varphi(x, y^\star) + D_\varphi(y^\star, z)

가 성립한다( $C$ 가 아핀이면 등호). 유클리드 사영의 피타고라스 정리를 그대로 옮긴 것이며, 정보 기하에서 e-측지선과 m-측지선의 직교 조건으로 등장하는 그 정리다.

4. 평균은 언제나 산술평균 — 지수족과의 1:1 대응[편집]

브레그만 발산의 가장 놀라운 성질. 데이터 $x_1,\dots,x_n$ 에 대해 두 번째 인수를 최소화하면

\arg\min_{z}\ \sum_i w_i\, D_\varphi(x_i, z) \;=\; \sum_i w_i\, x_i

즉 $\varphi$ 가 무엇이든 답은 가중 산술평균이다. 증명은 그래디언트를 잡으면 $\nabla^2\varphi(z)\bigl(z - \sum w_i x_i\bigr) = 0$ 이 되어 한 줄로 끝난다. 그리고 바네르지 등(2005)이 역도 참임을 보였다 — 최소점이 항상 평균이 되는 손실함수는 브레그만 발산뿐이다. 최대우도추정에서 “표본평균이 답”이라는 상황이 반복해서 나오는 데는 이런 배후가 있다.

평균이 정해지면 “평균에서 얼마나 흩어져 있는가”도 정의된다. 브레그만 정보 $I_\varphi(X) = \mathbb{E}\bigl[D_\varphi(X, \mathbb{E}[X])\bigr]$ 는 $\varphi = \frac12\lVert\cdot\rVert^2$ 일 때 그냥 분산이고, 심플렉스 위 음의 엔트로피를 쓰면 젠센-섀넌 발산·상호정보량이 된다. 분산과 상호정보량이 사실 같은 양의 두 사례였다는 뜻이며, 군집화의 목적함수(군집 내 분산 합)가 그대로 “브레그만 정보 손실”로 번역되는 것도 이 때문이다.

여기서 한 걸음만 더 가면 지수족과의 전단사가 나온다. 자연모수 $\theta$ , 로그분배함수 $\psi(\theta)$ 인 정칙 지수족의 밀도는

p(x\mid\theta) = \exp\bigl(\langle x,\theta\rangle - \psi(\theta)\bigr) p_0(x) = \exp\bigl(-D_\varphi(x, \mu)\bigr)\, b_\varphi(x)

로 다시 쓸 수 있다. 여기서 $\varphi = \psi^*$ 는 르장드르-펜셸 변환으로 얻은 켤레이고 $\mu = \nabla\psi(\theta)$ 는 기댓값 모수다. 즉 “정칙 지수족 ↔ 정칙 브레그만 발산”이 1:1 대응이며, 지수족의 최대우도추정이 곧 브레그만 발산 최소화, 그래서 답이 표본평균이다. 가우시안↔제곱오차, 베르누이↔로지스틱 손실, 푸아송↔일반화 KL이 전부 이 대응의 항목이다.²

켤레와의 관계는 발산 자체에서도 나타난다.

D_\varphi(x, y) = D_{\varphi^*}\bigl(\nabla\varphi(y),\, \nabla\varphi(x)\bigr)

켤레로 넘어가면 두 인수의 순서가 뒤집힌다. KL의 비대칭성이 정보 기하에서 e-접속과 m-접속의 쌍대성으로 번역되는 지점이 여기다.

5. 알고리즘 — 미러 하강과 브레그만 군집화[편집]

브레그만 발산은 “제곱거리 근접항”이 등장하는 모든 알고리즘에서 그 자리를 그대로 대체할 수 있다.

미러 하강. $x^{k+1} = \arg\min_x \{\langle g_k, x\rangle + \frac{1}{\eta_k} D_\varphi(x, x^k)\}$ . $\varphi = \frac12\lVert\cdot\rVert^2$ 이면 그냥 경사하강법이고, 심플렉스 위 음의 엔트로피를 쓰면 갱신이 $x^{k+1}_i \propto x^k_i e^{-\eta g_{k,i}}$ — 지수 가중 갱신(곱셈 가중치)이 된다. 정의역의 기하에 맞는 $\varphi$ 를 고르면 차원 의존성이 $\sqrt{n}$ 에서 $\sqrt{\log n}$ 으로 떨어지는 것이 이 방법의 존재 이유다.
브레그만 근접법 / 상대 매끄러움. 목적함수가 표준 립시츠 그래디언트 조건을 못 만족해도, 어떤 $\varphi$ 에 대해 $L\varphi - f$ 가 볼록이기만 하면(상대 매끄러움) 수렴률이 회복된다. 포아송 역문제나 D-최적 설계처럼 그래디언트가 경계에서 폭발하는 문제에 필수.
브레그만 교대방향 승수법. 이차 벌점항을 브레그만 항으로 갈아 끼워 부분문제를 닫힌 형태로 만드는 변형. 압축센싱의 선형화 브레그만이 대표.
브레그만 군집화. k-평균 군집화의 로이드 알고리즘이 왜 임의의 브레그만 발산으로 그대로 일반화되는지는 위의 “평균이 답” 성질 하나면 설명된다 — 할당 단계는 발산 비교, 갱신 단계는 언제나 산술평균이라 코드가 한 줄도 안 바뀐다. 그래서 가우시안 혼합 모형의 EM과 브레그만 k-평균이 같은 뼈대를 공유한다.

마지막으로 한 가지 주의. 브레그만 발산은 첫째 인수에 대해서는 항상 볼록이지만 둘째 인수에 대해서는 볼록이 아닐 수 있다. ” $D_\varphi(x, y)$ 를 $y$ 로 최소화하는 볼록 문제”라고 무심코 쓰면 틀린다 — KL을 두 번째 인수로 최소화하는 변분추론의 여러 정식화가 비볼록인 것도 이 때문이다.³

6. 관련 문서[편집]

Bregman, L. M. (1967). “The relaxation method of finding the common point of convex sets…”. 원 논문의 목적은 발산을 정의하는 게 아니라 볼록집합들의 교집합 위 점을 찾는 완화법이었다. 척도는 그 알고리즘을 굴리려고 만든 부산물이었는데, 지금은 부산물이 본체보다 훨씬 유명하다. 학계에서 흔한 일이다. ↩
Banerjee, Merugu, Dhillon, Ghosh (2005), Clustering with Bregman Divergences, JMLR 6. 같은 저자들의 자매 논문이 “조건부 기댓값이 최적 예측자가 되는 손실은 브레그만뿐”임을 보인다. 회귀에서 MSE를 쓰면 조건부 평균이, MAE를 쓰면 조건부 중앙값이 나오는 이유가 바로 이 정리 — MAE는 브레그만이 아니다. ↩
그래서 “KL을 최소화한다”는 문장을 보면 항상 어느 인수인지부터 확인해야 한다. $D(q\Vert p)$ 를 $q$ 로 최소화하면(역방향 KL) 모드 추적(mode-seeking), $D(p\Vert q)$ 를 $q$ 로 최소화하면(정방향 KL) 질량 덮기(mass-covering). 변분추론이 사후분포를 자주 과소평가하는 것도 관행적으로 역방향을 쓰기 때문이지, 알고리즘이 고장 나서가 아니다. ↩