설문지의 몇 칸이 비어 있거나, 점마다 어느 클러스터에서 왔는지 적혀 있지 않은 데이터는 흔하다. 이런 데이터로 모델을 맞출 때 오래 써 온 방법은 두 일을 번갈아 하는 것이다. 지금의 모델로 빈칸을 그럴듯하게 채우고 채운 데이터로 모델을 다시 맞추는 일을, 또 채우고 또 맞추며 되풀이한다. 이 번갈아 하기가 EM(기댓값 계산과 최대화를 번갈아 하는 알고리즘)이다.
번갈아 하기를 몇백 번 되풀이하다 보면 물음이 생긴다. 이 되풀이는 어딘가에서 멈추는가? 멈춘다면 왜, 그리고 무엇이 멈추는가? 정보기하학의 말로 바꾸면 이렇다. e-사영(e는 exponential. 확률을 곱해 잇는 e-측지선을 따라 모델 위로 내려찍기)과 m-사영(m은 mixture. 확률을 섞어 잇는 m-측지선을 따라 내려찍기)을 번갈아 하면 어디에 닿는가?
답의 앞부분은 단순하다. 두 일이 같은 목적함수 하나를 변수 하나씩 번갈아 줄이므로, 어느 일도 값을 올리지 않는다. 기하학이 하는 일은 EM의 한 스텝이 값을 “얼마나” 내렸는지 재는 것이고, 그 도구가 사영의 피타고라스 정리다.
이 장은 사영의 피타고라스 정리를 다시 꺼내 손질하고, 그 정리로 EM의 스텝을 재어 본 뒤, 무엇이 수렴하고 무엇이 수렴하지 않는지를 가른다.
피타고라스 정리: KL이 직각으로 나뉠 때
EM의 한 스텝이 목적함수를 얼마나 줄였는지 재려면, KL 발산(한 분포를 다른 분포로 대신할 때 치르는 손해)을 "가장 가까운 점까지"와 "그 점에서 다른 점까지"로 쪼갤 수 있어야 한다. KL은 대칭도 아니고 삼각부등식도 깨지는데, 가장 가까운 점으로 내려찍은 자리에서만은 직각삼각형처럼 두 조각으로 나뉜다. 이 절은 그 정리를 짧게 다시 적고, 이 장에 새로 필요한 것 하나를 더한다. 발끝이 아닌 꼭짓점에서는 무엇이 남는가.
정리 다시 적기
현실 p가 있고, 모델들의 모임 M이 있다. M은 지수족이라고 하자. 지수족은 log q = θ·t(x) − F(θ) 꼴로 쓰이는 분포 모임이고, 자연 파라미터 θ는 t(x) 앞에 곱하는 파라미터(분포를 정하는 숫자), t(x)는 충분통계량(모델이 데이터에서 보는 요약값), F는 합이 1이 되게 맞추는 로그정규화자다. 지수족은 자연 파라미터로 보면 곧은 면이라 e-평탄하다고 한다. M 위에서 KL(p‖q)가 가장 작은 점을 p의 m-사영점 qm이라 부르며, 지수족에서 이 점은 충분통계량의 평균을 p와 맞춘 점이다(모멘트 일치). 산꼭대기 p에서 들판 M으로 수직으로 내려선 발끝이 qm이고, 꼭대기에서 들판 위 아무 마을 q까지의 KL은 두 구간의 KL을 더한 것과 같다. 아래 그림의 위쪽이 그 모습이다.
위: 발끝 q_m 에서는 KL(p‖q) 가 두 조각의 합과 같다(0.578 = 0.039 + 0.539). 아래: 발끝이 아닌 꼭짓점 r 에서는 교차항만큼 어긋난다(0.578 = 0.069 + 0.309 + 0.200). 값은 이 절 파이썬의 p = (0.5, 0.2, 0.3), r = 균등분포, q = θ가 1인 모델
빗변은 p에서 q까지. 한 변은 p에서 발끝 qm까지. 다른 변은 발끝에서 M 위를 따라 q까지. 오른쪽 둘째 항은 0 이상이므로, 피타고라스 등식은 "qm이 M 위에서 p와 가장 가깝다"는 것과 "다른 q는 KL(qm‖q)만큼 더 멀다"는 것을 한꺼번에 말한다. 빗변과 첫째 항은 p가 KL의 첫 인자이고, 둘째 항은 qm이 첫 인자다.
"직각"은 p에서 qm으로 내려오는 m-측지선(덧셈의 규칙으로 가장 곧게 가는 길)이 M과 이루는 각이고, 피셔 계량(곳마다 작은 걸음의 길이와 각도를 재는 규칙)으로 잰다. 심플렉스(결과가 셋인 분포를 점으로 찍는 삼각형) 그림 위에서 눈으로 재면 90°가 아니다.
쌍대인 정리도 있다. m-평탄한 모임(혼합으로 닫힌 모임) 위에서 KL(·‖p)가 가장 작은 점, 곧 e-사영점 qe에서는 KL의 두 인자 순서가 뒤집힌 피타고라스 KL(r‖p) = KL(r‖qe) + KL(qe‖p)가 그 모임 위의 모든 r에 대해 성립한다. EM에서 빈칸을 채우는 단계(E-스텝)가 이 뒤집힌 피타고라스를 쓴다.
직각이 아니면 무엇이 남는가
발끝이 아닌 점 r을 꼭짓점으로 잡으면 위 등식이 어긋난다. 그림의 아래쪽에서는 KL(p‖q)가 두 조각의 합보다 0.2 큰데, 어긋나는 양에는 정확한 식이 있다. 지수족 안의 KL은 브레그만 발산(볼록함수와, 한 점에서 그은 접선 사이의 높이 차이)이고, 브레그만 발산에는 세 점 사이의 항등식이 있다. 1차 근사의 오차 같은 것이 아니라, 항 하나 빼지 않은 등식이다.
마지막 항이 유클리드의 c² = a² + b² − 2ab cos C 에서 코사인 항에 해당하는 "교차항"이다. 교차항의 한 인수는 θ 좌표의 차이이고, 다른 인수는 η 좌표의 차이다. η는 충분통계량의 평균 E[t(x)]로 분포를 가리키는 기댓값 파라미터이고, θ와 η는 서로의 쌍대 좌표(한쪽이 정해지면 다른 쪽이 정해지는 짝)다. θ의 차이와 η의 차이를 곱한 값이 0이 되는 것이 "쌍대 직교"이고, 피셔 계량으로 잰 직교와 같은 말이다. 교차항이 사라지는 꼭짓점에서만 피타고라스가 된다.
"거리도 아닌 것"인 KL이 피타고라스 정리를 품고 있었다. 거리가 아니어서 쓸모없는 줄 알았는데, 볼록함수 F(θ)(로그정규화자)에서 태어난 발산이기 때문에 오히려 이 분해가 가능하다. 볼록함수 F의 그래프와 그 접선 사이의 높이 차이(브레그만 발산)가 여기서 삼각형의 변이 된다.
직접 움직여 보기
불러오는 중…
파이썬
결과가 셋인 분포 위에, 곡선 하나로 된 e-평탄 모델 qθ(i) ∝ exp(θ·t(i)), t = (0, 1, 2)를 놓는다. p와 M 위의 두 점 r, q를 아무렇게나 뽑아 세 점 항등식을 확인하고, 그림의 예에서 어긋남과 교차항을 나란히 놓는다. 여기서 η는 t의 평균이다.
import numpy as np
t = np.array([0.0, 1.0, 2.0]) # 충분통계량 t(i)
def q_of(theta): # M 위의 점: q_θ(i) ∝ exp(θ·t(i))
w = np.exp(theta * t)
return w / w.sum()
def kl(a, b):
return np.sum(a * np.log(a / b))
def cross(p, th_r, th_q): # 교차항 (θ_q − θ_r)·(η_p − η_r), η = t 의 평균
return (th_q - th_r) * (p @ t - q_of(th_r) @ t)
rng = np.random.default_rng(1)
worst = 0.0
for _ in range(1000):
p = rng.dirichlet([1, 1, 1]) # 아무 현실 p
th_r, th_q = rng.normal(0, 2, 2) # M 위의 아무 두 점 r, q
r, q = q_of(th_r), q_of(th_q)
worst = max(worst, abs(kl(p, q) - (kl(p, r) + kl(r, q) - cross(p, th_r, th_q))))
print(f"세 점 1000쌍, 항등식 잔차의 최댓값 {worst:.1e}")
p, r, q = np.array([0.5, 0.2, 0.3]), q_of(0.0), q_of(1.0) # r = 균등분포
print(f"KL(p‖q) {kl(p, q):.4f} KL(p‖r) + KL(r‖q) {kl(p, r) + kl(r, q):.4f}")
print(f"어긋남 {kl(p, q) - kl(p, r) - kl(r, q):+.4f} −교차항 {-cross(p, 0.0, 1.0):+.4f}")
# 세 점 1000쌍, 항등식 잔차의 최댓값 3.9e-15
# KL(p‖q) 0.5780 KL(p‖r) + KL(r‖q) 0.3780
# 어긋남 +0.2000 −교차항 +0.2000
잔차는 부동소수점 오차 수준(10−15)이라, 이 관계는 근사가 아니라 등식이다. 그림의 예에서 KL(p‖q)가 두 조각의 합보다 0.2000 큰 차이는 교차항에 −를 붙인 값과 같다.
이 절의 결론
“사영점에서 KL은 두 조각으로 근사 없이 나뉜다. 발끝이 아닌 꼭짓점에서는 θ의 차이와 η의 차이를 곱한 교차항만큼 어긋나고, 직각은 그 곱이 0이 되는 자리다.”
문제 1. 꺾인 길의 직선거리
학교에서 편의점까지 곧게 300 m를 걸은 뒤, 편의점에서 왼쪽으로 방향을 틀어 집까지 곧게 400 m를 걸었다. (가) 직각으로 틀었다면 학교에서 집까지의 직선거리는 얼마인가? (나) 진행 방향을 60°만 틀었다면 직선거리는 얼마이고, 그 제곱은 300² + 400²과 얼마나 다른가? (다) 진행 방향을 120° 틀었다면?
학교에서 편의점까지 300 m를 걷고, 편의점에서 진행 방향을 90°, 60°, 120° 틀어 집까지 400 m를 걷는다. 초록 호는 원래 진행 방향(점선 끝)에서 잰 튼 각이고, 회색 점선이 묻는 직선거리다
함께 풀기
김민준
(가)는 500 m요. (나)는 코사인 법칙 c² = a² + b² − 2ab cos C 에 C = 60°를 넣었어요. 90,000 + 160,000 − 120,000 = 130,000이니까 360.6 m요.
선생님
300 m와 400 m를 걸었는데 학교에서 360 m밖에 안 떨어졌으면, 꽤 많이 되돌아온 거예요. 방향을 60°만 틀었는데 그럴까요?
김민준
어… 거의 똑바로 간 셈인데 700 m 가까이 떨어져 있어야 할 것 같아요. 숫자가 거꾸로 나왔어요.
이서연
코사인 법칙의 C는 꼭짓점에서 두 변이 이루는 사이각이야. 편의점에서 진행 방향을 60° 틀면 두 변 사이의 각은 180° − 60° = 120°고, cos 120° = −0.5라서 120,000을 더해. 370,000, 608.3 m.
이서연
(다)는 반대로 사이각이 60°라서 120,000을 빼고, 360.6 m예요. 민준이가 (나)에서 낸 답이 사실 (다)의 답이었네요.
선생님
300² + 400²과의 차이 ±120,000은 무엇이 정하나요?
이서연
꼭짓점인 편의점에서 두 변이 이루는 각이요. 직각이면 0, 둔각이면 더해지고, 예각이면 빠져요. 어느 점이 꼭짓점인지, 거기서 무슨 각을 재는지를 먼저 정해야 해요.
김민준
조별 보고서에서 "꺾인 각"을 방향을 튼 각으로 적었는지 사이각으로 적었는지 안 밝혀서, 조원끼리 숫자가 다르게 나왔던 거랑 같네요.
문제 2. 발끝이 아닌 꼭짓점
결과가 셋인 분포 위에 모델 M = {qθ(i) ∝ exp(θ·t(i)) : t = (0, 1, 2)}가 있고, 현실은 p = (0.2, 0.2, 0.6)이다. (가) 꼭짓점 r = qθ=0(균등분포), q = qθ=1로 두고 KL(p‖q)와 KL(p‖r) + KL(r‖q)를 비교하라. 차이는 교차항으로 설명되는가? (나) 꼭짓점 r을 M 위 어디에 두면 어떤 q를 골라도 교차항이 0이 되는가? 그 r로 (가)의 q에 대해 등식을 확인하라(위젯의 「문제 2 불러오기」는 이 p와 q를 놓는다).
결과가 셋인 분포의 심플렉스 위에 모델 M(θ를 −6에서 6까지 움직인 곡선)과 현실 분포 p = (0.2, 0.2, 0.6), 꼭짓점 r(θ = 0, 균등분포), q(θ = 1)를 찍었다. 점선은 KL을 잴 세 짝
함께 풀기
김민준
(가) 좌변은 0.0573이고, 오른쪽은 0.1483 + 0.3090 = 0.4573이에요. 빗변이 두 변의 합보다 0.4나 짧아요. KL이 삼각부등식을 안 지키는 건 알지만 이렇게 크게 어긋나요? 제 kl 함수가 이상한가 봐요.
