거리 아닌 거리, 직선 아닌 직선

출발 문제

동전 두 개를 비교해 보자. 앞면 확률이 0.5인 동전과 0.8인 동전이다. KL 발산(두 분포가 얼마나 다른지 한 방향으로 재는 양)으로 재면 0.5 동전에서 0.8 동전 쪽으로는 0.223, 거꾸로 재면 0.193이 나온다. 어느 쪽에서 재느냐에 따라 값이 달라서, 기호로 쓰면 $D_\text{KL}(p \| q) \neq D_\text{KL}(q \| p)$ 다. 세로 두 줄 앞에 적은 분포가 기준이어서, $D_\text{KL}(p \| q)$ 는 " $p$ 에서 $q$ 쪽으로 잰 값"으로 읽는다. 아래에서는 같은 양을 $D(p \| q)$ 로 줄여 적기도 한다.

동전을 하나 더 넣으면 더 이상한 일이 생긴다. 0.2 동전에서 0.8 동전으로 곧장 재면 0.832인데, 0.5 동전을 거쳐 가면 0.193 + 0.223 = 0.416이다. 돌아가는 길이 곧장 가는 길의 절반밖에 안 된다. 보통의 거리라면 돌아가는 길이 더 짧을 수 없다(삼각부등식). 거리라면 당연히 지킬 대칭성과 삼각부등식을 KL 발산은 둘 다 어긴다. 그렇다면 KL 발산을 "거리"라고 부를 수 있는가?

그런데 KL 발산은 거리의 자격이 없는데도 실제로는 거리보다 더 많이 쓰인다. 기계학습의 손실 함수로, 변분추론의 최적화 목표로, 강화학습에서 정책 사이의 차이를 재는 잣대로, 정보이론의 채널 용량 계산에 KL 발산이 쓰인다. 거리의 조건을 어기는 것이 "결함"보다 오히려 "특징"이라면?

더 근본적인 질문을 해 보자. 비대칭이 실제로 의미를 갖는 상황이 있는가? " $p$ 가 참인데 $q$ 로 근사하는 것"과 " $q$ 가 참인데 $p$ 로 근사하는 것"은 같은 일일까? 봉우리가 둘인 분포 $p$ 를 봉우리 하나짜리 정규분포 $q$ 로 근사한다고 하자. 봉우리 하나로는 두 봉우리를 다 맞출 수 없으니 어딘가에서는 틀려야 한다. 아무것도 없는 골짜기에 확률을 쏟는 틀림과 봉우리 하나를 전부 놓치는 틀림 가운데 어느 쪽을 더 무겁게 볼 것인가? 발산을 어느 방향으로 재느냐가 이 선택을 정할까?

KL 발산: 방향이 있는 떨어짐

거리의 자격이 없는 양이 왜 이렇게 널리 쓰일까? 그 답을 찾으려면 먼저 KL 발산이 애초에 무엇을 재려고 만들어졌는지부터 알아야 한다.

역사: 아브라함 발트(Abraham Wald, 1902–1950)와 쌓이는 증거

제2차 세계대전 중 미국 해군은 포탄 설계 A와 B 가운데 어느 쪽이 나은지 가리려고 시험 사격을 했다. 당시의 통계 방법대로라면 쏠 발수를 미리 정해 두고 다 쏜 뒤에 판정해야 했는데, 해군 대령 개릿 스카일러(Garret L. Schuyler)는 이것이 낭비라고 반대했다. 노련한 장교라면 처음 몇천 발, 어쩌면 몇백 발만 보고도 결론이 났다는 것을 알 텐데 정해진 수를 채우느라 포탄과 시간을 버린다는 것이다. 스카일러의 반대를 들은 컬럼비아 대학 통계 연구 그룹(SRG)의 앨런 월리스(W. Allen Wallis)와 밀턴 프리드먼(Milton Friedman)은 도중에 멈춰도 되는 검정을 붙들었지만 다 풀지 못해, 같은 그룹의 수학자 발트에게 넘겼다.

발트는 판정을 미리 정한 발수에 묶지 않았다. 관측이 하나 들어올 때마다 그 관측이 두 가설에 준 확률의 비에 로그를 씌운 값(로그 우도비)을 지금까지의 합에 더하고, 합이 위 문턱에 닿으면 한쪽으로, 아래 문턱에 닿으면 다른 쪽으로 판정한 뒤 멈춘다. 이 방법이 순차 확률비 검정(SPRT, sequential probability ratio test)이다. 전쟁에 쓸모가 커서 「제한」 등급으로 묶였다가 1945년 논문과 1947년 책 『순차 분석(Sequential Analysis)』으로 나왔다.

아래 문제 1의 두 동전(보통 동전 p, 깎은 동전 q)으로 돌린 순차 확률비 검정. 한 번 던질 때마다 증거 log(p/q)를 더하다가 ±log 100 문턱에 닿으면 멈춘다. 청록 경로는 보통 동전이 참일 때, 주황 경로는 깎은 동전이 참일 때이고, 점선은 한 번 던질 때마다 평균으로 쌓이는 양을 이은 선이다

포탄 한 발이나 동전 한 번의 결과는 약한 증거라서 모아야 판정할 수 있고, 그래서 물음은 관측 하나가 평균 얼마만큼의 증거를 보태느냐가 된다. 두 분포 $p$ , $q$ 가운데 $p$ 가 참이면 로그 우도비 $\log \frac{p(x)}{q(x)}$ 의 합은 관측마다 평균 $D_\text{KL}(p \| q) = \sum_x p(x) \log \frac{p(x)}{q(x)}$ 씩 늘어, 문턱까지 걸리는 관측 수가 대략 (문턱) / $D_\text{KL}(p \| q)$ 다. $q$ 가 참이면 $D_\text{KL}(p \| q)$ 대신 $D_\text{KL}(q \| p)$ 가 들어가므로, 같은 문턱이라도 두 경우의 평균 시험 횟수가 다르다. KL 발산의 비대칭이 시험 비용의 차이로 나타나는 것이다. 이 평균 증거를 1951년 쿨백과 라이블러가 「판별을 위한 평균 정보」로 정의했고, 논문은 두 방향을 더한 대칭 합에 「발산」이라는 이름을 붙였다(쿨백은 뒤에 한 방향 양을 「방향이 있는 발산」이라 불렀다).

문제 1의 두 동전으로 십만 번씩 돌려 보면, 틀린 판정을 1% 아래로 묶는 데 미리 횟수를 정하는 검정은 60번을 던져야 하지만 순차 검정은 평균 22.5번(보통 동전이 참일 때)과 24.6번(깎은 동전이 참일 때)에 멈춘다. 스카일러 대령의 불평은 숫자로도 옳았다. 「 $p$ 가 참인데 $q$ 라고 착각하는 것」과 「 $q$ 가 참인데 $p$ 라고 착각하는 것」은 질적으로 다른 실수이고, 이 장은 두 실수의 차이가 어디서 쓸모를 갖는지 따라간다.

문제 1의 두 동전으로 순차 확률비 검정을 십만 번씩 돌렸을 때 판정이 날 때까지 던진 횟수. 같은 오류율(틀린 판정 1% 아래)을 지키려면 횟수를 미리 정하는 검정은 60번(점선)을 던져야 하지만, 순차 검정은 평균 22.5번(보통 동전이 참)과 24.6번(깎은 동전이 참)에 멈춘다. 계산: sources/ch11/sprt_coin.py

지금 같으면 문턱을 몇 개 바꿔 가며 십만 번씩 돌려 보고 제일 싼 걸 고르면 끝이잖아요. 위 그림도 그렇게 만든 거고요.

1943년의 통계 연구 그룹에는 십만 번을 돌릴 기계가 없었어요. 그러면 「도중에 멈춰도 틀린 판정이 1% 아래」라는 약속은 무엇으로 보장해야 했을까요?

음, 종이 위의 식으로요? 발수를 미리 정하면 이항분포 표를 찾으면 되는데… 언제 멈출지를 데이터가 정하면 던진 횟수 자체가 그때그때 달라지네요.

월리스와 프리드먼이 막힌 곳이 거기예요. 그때의 검정 이론은 샘플 수를 미리 정해 둔다는 전제 위에 서 있었거든요. 발트는 원하는 오류율로 두 문턱을 정하는 근사 식을 따로 세워야 했어요.

관측 하나가 평균 얼마나 보태는지도 부를 이름이 없었겠네요. KL 발산은 1951년에 나왔으니까요.

섀넌의 정보 이론도 1948년에야 나와요. 발트는 그 평균을 이름 없이 평균 시험 횟수 계산에 썼어요.

그 평균 증거는 어느 쪽이 참이냐에 따라 달랐잖아요. 식으로 적으면 어느 자리가 「참인 쪽」을 맡아요?

식으로 적은 KL 발산

KL 발산을 식으로 다시 적어 두자. 이산 분포라면 다음과 같고, 연속 분포라면 합이 적분으로 바뀐다.

\textcolor{#7a5c1e}{D}_\text{KL}(\textcolor{#2e8b3a}{p} \,\|\, \textcolor{#2e8b3a}{q}) = \sum_{\textcolor{#007a72}{x}} \textcolor{#2e8b3a}{p}(\textcolor{#007a72}{x}) \log \frac{\textcolor{#2e8b3a}{p}(\textcolor{#007a72}{x})}{\textcolor{#2e8b3a}{q}(\textcolor{#007a72}{x})}

\begin{array}{ll} \textcolor{#7a5c1e}{D}_\text{KL} & \text{KL 발산 (방향이 있는 떨어짐)} \\ \textcolor{#2e8b3a}{p}, \textcolor{#2e8b3a}{q} & \text{두 확률분포 (점 하나가 분포 하나인 휘어진 공간인 통계적 매니폴드의 두 점)} \\ \textcolor{#007a72}{x} & \text{관측값} \end{array}

$\textcolor{#7a5c1e}{D}_\text{KL}(\textcolor{#2e8b3a}{p} \| \textcolor{#2e8b3a}{q})$ 를 KL 발산 (방향 있는 떨어짐 / Kullback–Leibler Divergence)이라 부른다. 합의 모든 항에 $\textcolor{#2e8b3a}{p}$ 가 곱해져 있다는 점이 비대칭의 원인이다. $\textcolor{#2e8b3a}{p}$ 가 큰 곳에서 $\textcolor{#2e8b3a}{q}$ 가 작으면 큰 페널티가 붙지만, $\textcolor{#2e8b3a}{q}$ 가 큰 곳에서 $\textcolor{#2e8b3a}{p}$ 가 작으면 그 $\textcolor{#007a72}{x}$ 의 항은 합에 거의 들어가지 않는다.

아래 그림은 정규분포 한 쌍 $\textcolor{#2e8b3a}{p} = N(0, 1)$ , $\textcolor{#2e8b3a}{q} = N(1, 2^2)$ 로 두 방향을 나란히 그린 것으로, 갈색 곡선 아래 넓이가 발산 값이다. (가)에서는 로그 앞에 곱하는 분포가 $\textcolor{#2e8b3a}{p}$ 라서 $\textcolor{#2e8b3a}{p}$ 가 거의 없는 오른쪽 꼬리는 셈에 거의 들어가지 않는다. (나)에서는 곱하는 분포가 $\textcolor{#2e8b3a}{q}$ 로 바뀌어, $\textcolor{#2e8b3a}{p}$ 가 거의 없는데 $\textcolor{#2e8b3a}{q}$ 는 아직 큰 오른쪽 꼬리가 크게 쌓인다.

같은 두 정규분포 p = N(0, 1)(실선)과 q = N(1, 2²)(점선)로 잰 KL 발산의 두 방향. 갈색 곡선이 합(적분)에 들어가는 항이고 그 아래 넓이가 발산 값이다. (가) p를 앞에 두면 넓이 0.443, (나) q를 앞에 두면 p가 거의 없는 오른쪽 꼬리가 크게 쌓여 넓이 1.307

ML에서: 손실 함수 속의 KL

분류 모델을 학습시킬 때 쓰는 크로스 엔트로피 손실 $-\mathbb{E}_{\textcolor{#2e8b3a}{p}}[\log \textcolor{#2e8b3a}{q}]$ (데이터 분포 $\textcolor{#2e8b3a}{p}$ 아래에서 모델이 매긴 로그확률을 평균 내고 부호를 바꾼 값)도 KL 발산과 이어져 있다. 여기서 움직이는 것은 모델 파라미터가 정하는 분포 $\textcolor{#2e8b3a}{q}$ 이고, 둘이 어떻게 이어지는지는 아래 문제 3에서 숫자로 확인한다.

방향을 거꾸로 쓰는 곳도 있다. InstructGPT(Ouyang 등, 2022)처럼 사람의 선호로 언어 모델을 파인튜닝하는 RLHF(사람의 피드백으로 하는 강화학습)에서는, 학습 중인 정책(문장을 내놓는 모델)이 처음 모델에서 너무 멀어지지 않도록 학습 중인 정책에서 뽑은 문장으로 잰 KL 발산을 보상에서 뺀다. 어느 쪽을 앞에 두느냐에 따라 모델이 받는 압력이 달라진다.

문제 1: 깎은 동전인가

확인 친구가 동전 하나를 건네며 "앞면이 80% 나오게 깎은 동전"이라고 하지만, 나는 보통 동전(앞면 50%)이라고 의심한다. 한 번 던질 때마다 "보통 동전이면 방금 나온 면이 나올 확률 ÷ 깎은 동전이면 방금 나온 면이 나올 확률"을 계산해 지금까지의 값에 곱해 간다. 앞면이면 0.5/0.8 = 0.625를, 뒷면이면 0.5/0.2 = 2.5를 곱한다. (가) 동전이 실제로 보통 동전이면, 이 곱은 한 번 던질 때마다 평균 몇 배씩 커지는가? 곱이 100배가 되려면 대략 몇 번 던져야 하는가? (나) 동전이 실제로 깎은 동전이면, 거꾸로 깎은 동전 쪽을 100배 지지하기까지 대략 몇 번 던져야 하는가?

문제 1의 설정. 왼쪽은 두 가설의 동전이 앞면과 뒷면을 낼 확률, 오른쪽은 던질 때마다 곱하는 값(로그 눈금)으로, 처음 1에서 뒷면이면 2.5배, 앞면이면 0.625배가 되고 점선이 100배다

같이 풀기 세션 1

앞면과 뒷면이 반반 나오니까 평균은 $(0.625 + 2.5)/2 = 1.5625$ 배예요. $1.5625^{10}$ 이 87쯤이니까 10번 남짓이면 되겠네요.

그럼 앞면 한 번, 뒷면 한 번이 나온 뒤에는 곱이 얼마예요?

$0.625 \times 2.5 = 1.5625$ … 두 번 던져서 1.56배예요. 한 번에 1.56배가 아니라 두 번에 1.56배네요. 곱해 가는 걸 더하기 평균으로 냈어요.

곱은 로그를 씌우면 합이 되니까 평균도 로그로 내야 해. 한 번에 $0.5\log 0.625 + 0.5\log 2.5 \approx 0.223$ 이니까 $e^{0.223} = 1.25$ 배씩이야. $\log 100 \approx 4.61$ 이니까 $4.61 / 0.223 \approx 21$ 번. (나)는 깎은 동전이 참이니까 평균을 0.8과 0.2로 내야지. $0.8\log 1.6 + 0.2\log 0.4 \approx 0.193$ 이라 $4.61/0.193 \approx 24$ 번. 같은 두 동전인데 세 번 더 걸리네.

0.223과 0.193, 어디서 본 숫자죠?

출발 문제의 두 KL 값이에요. KL 발산이 한 번 관측할 때 쌓이는 증거의 평균이었구나. 어느 쪽이 참이냐에 따라 평균을 내는 확률이 달라서 두 방향의 값이 다른 거고요.

발트의 포탄 시험도 이렇게 셌어요. 어느 설계가 참으로 나으냐에 따라 평균 시험 횟수가 21번, 24번처럼 달라지죠. 실제로 돌려 보면 마지막 한 번이 문턱을 조금 넘어선 뒤에 멈추니까 이보다 한두 번 더 걸려요.

문제 2: 동전 두 개의 KL

확인 앞면 확률이 0.5인 동전 $\textcolor{#2e8b3a}{p} = \text{Bern}(0.5)$ 와 0.9인 동전 $\textcolor{#2e8b3a}{q} = \text{Bern}(0.9)$ 에 대해 $\textcolor{#7a5c1e}{D}(\textcolor{#2e8b3a}{p} \| \textcolor{#2e8b3a}{q})$ 와 $\textcolor{#7a5c1e}{D}(\textcolor{#2e8b3a}{q} \| \textcolor{#2e8b3a}{p})$ 를 자연로그로 계산하라. 계산 도중 음수인 항이 나오면 그것이 무엇을 뜻하는지도 설명하라.

문제 2의 두 동전. 앞면 확률이 0.5인 p(진한 막대)와 0.9인 q(옅은 막대)가 앞면과 뒷면에 주는 확률

같이 풀기 세션 2

numpy로 바로 했어요. $\textcolor{#7a5c1e}{D}(\textcolor{#2e8b3a}{p} \| \textcolor{#2e8b3a}{q}) = 0.5\log\frac{0.5}{0.9} + 0.5\log\frac{0.5}{0.1} \approx 0.511$ 이고, $\textcolor{#7a5c1e}{D}(\textcolor{#2e8b3a}{q} \| \textcolor{#2e8b3a}{p}) = 0.9\log 1.8 + 0.1\log 0.2 \approx 0.368$ 이에요. 역시 비대칭이네요.

잠깐, 두 번째 항 $0.1\log 0.2$ 가 $-0.161$ 이야. 첫 번째 식에서도 $0.5\log\frac{0.5}{0.9}$ 가 음수고. 발산은 0 이상이어야 하잖아. 음수가 섞이면 어디가 틀린 거 아닐까?

좋은 의심이에요. 발산이 0 이상이라는 건 어디에 대한 약속이죠? 항 하나하나예요, 합 전체예요?

합 전체요. 아, $\log\frac{\textcolor{#2e8b3a}{p}}{\textcolor{#2e8b3a}{q}}$ 는 $\textcolor{#2e8b3a}{p} < \textcolor{#2e8b3a}{q}$ 인 칸에서 당연히 음수가 되는구나. 확률의 합이 둘 다 1이니까 어떤 칸에서 $\textcolor{#2e8b3a}{p}$ 가 더 크면 다른 칸에선 반드시 $\textcolor{#2e8b3a}{q}$ 가 더 커야 하고, 그러니 음수 항은 피할 수가 없네.

그래도 합이 0 이상인 이유는 $\log$ 가 오목함수라서예요. 젠센 부등식으로 $-\textcolor{#7a5c1e}{D}(\textcolor{#2e8b3a}{p} \| \textcolor{#2e8b3a}{q}) = \sum \textcolor{#2e8b3a}{p} \log\frac{\textcolor{#2e8b3a}{q}}{\textcolor{#2e8b3a}{p}} \leq \log\sum \textcolor{#2e8b3a}{p}\,\frac{\textcolor{#2e8b3a}{q}}{\textcolor{#2e8b3a}{p}} = \log 1 = 0$ 이 되죠.

해석학 시간에 적분값이 양수라고 적분하는 함수까지 어디서나 양수인 건 아니라고 몇 번이나 들었는데, 합으로 바뀌니까 또 헷갈렸어요.

문제 3: 정답 모델의 손실은 왜 0이 아닌가

계산 앞면과 뒷면이 반반인 동전 던지기 기록(데이터 분포 $\textcolor{#2e8b3a}{p} = \text{Bern}(0.5)$ )으로 앞면 확률 하나를 내놓는 모델을 학습시킨다. 모델 A는 $\textcolor{#2e8b3a}{q} = \text{Bern}(0.8)$ , 모델 B는 $\textcolor{#2e8b3a}{q} = \text{Bern}(0.6)$ 을 내놓는다. (가) 두 모델의 크로스 엔트로피 손실 $-\mathbb{E}_{\textcolor{#2e8b3a}{p}}[\log \textcolor{#2e8b3a}{q}]$ 와 KL 발산 $\textcolor{#7a5c1e}{D}(\textcolor{#2e8b3a}{p} \| \textcolor{#2e8b3a}{q})$ 를 자연로그로 구하라. (나) 손실이 가장 작은 모델은 무엇이고, 그때 손실은 얼마인가?

문제 3의 데이터 분포 p = Bern(0.5)와 두 모델이 내놓는 분포 q. 모델 A는 앞면에 0.8, 모델 B는 0.6을 준다

같이 풀기 세션 3

손실은 A가 $-(0.5\log 0.8 + 0.5\log 0.2) \approx 0.916$ , B가 $0.714$ 예요. KL은 A가 0.223, B가 0.020이고요. (나)는 $\textcolor{#2e8b3a}{q} = \text{Bern}(0.5)$ 가 데이터와 똑같으니까 손실이 0이겠죠.

$\textcolor{#2e8b3a}{q} = \text{Bern}(0.5)$ 를 넣어서 계산해 볼래요?

$-(0.5\log 0.5 + 0.5\log 0.5) = \log 2 \approx 0.693$ … 0이 아니네요. 데이터랑 똑같은 모델인데요?

손실에서 KL을 빼 봐. A는 $0.916 - 0.223$ , B는 $0.714 - 0.020$ , 어느 쪽이든 약 0.693이야. 모델을 바꿔도 손실과 KL의 차이는 그대로네.

그 0.693은 모델이 정하는 값일까요, 데이터가 정하는 값일까요?

모델을 바꿔도 그대로였으니까… 데이터요. 반반인 동전 자체의 엔트로피 $H(\textcolor{#2e8b3a}{p}) = \log 2$ 예요.

그럼 크로스 엔트로피를 두 조각으로 적어 볼래요?

$H(\textcolor{#2e8b3a}{p}) + \textcolor{#7a5c1e}{D}(\textcolor{#2e8b3a}{p} \| \textcolor{#2e8b3a}{q})$ 요. 모델이 줄일 수 있는 건 뒤의 KL 항뿐이네요. 크로스 엔트로피를 줄이는 일이 데이터 분포 $\textcolor{#2e8b3a}{p}$ 에서 모델 분포 $\textcolor{#2e8b3a}{q}$ 로 가는 KL을 줄이는 일이었어요.

과제에서 학습 손실이 0.69 아래로 안 내려가서 버그를 찾느라 밤샌 적이 있어요. 레이블이 거의 반반 무작위인 데이터였는데, 그게 데이터 자체의 엔트로피였네요.