σ-대수에 대한 조건부 기댓값을 정의하고 그것이 L² 직교 사영과 같음을 증명해, 확산 모델의 최적 디노이저가 조건부 평균인 이유와 손실의 바닥을 계산합니다. 타워 성질·전분산·조건부 젠센에서 마팅게일, 옵셔널 스토핑, 수렴 정리, 둡 부등식, 아주마–회프딩까지 갑니다.
PALDYN Team//60 MIN READ
05MATH
고급
조건부 기댓값 · 직교 사영
확산 모델을 학습하는 팀이 있습니다. 깨끗한 데이터 x0 에 표준편차 σ 의 가우스 잡음을 더해 xt=x0+σε 을 만들고, 디노이저 Dθ(xt,σ) 가 x0 를 맞히도록 제곱오차 ∥Dθ(xt,σ)−x0∥2 를 줄입니다. 구현이 맞는지 보려고 가장 작은 장난감부터 돌립니다. 데이터는 +1 과 −1 이 반반인 실수 하나이고 잡음은 σ=1 입니다. 작은 MLP를 오래 학습해도 검증 손실이 0.45 근처에서 더 내려가지 않습니다. 참고하던 논문에는 이런 줄이 있습니다.
The optimal denoiser is the conditional expectation, D∗(x;σ)=E[x0∣xt=x].
리뷰에서 질문이 셋 나옵니다. 첫째, xt 는 연속이라 xt=x 라는 사건의 확률이 0인데, 확률 0인 사건으로 조건을 건 기댓값이 무슨 뜻인가요. 둘째, 0.45는 모델이 덜 배운 것인가요, 아니면 더 내려갈 수 없는 바닥인가요. 셋째, 잡음을 한 번 뽑아 둔 경로에서 σ 를 줄여 가며 디노이저를 읽으면 예측이 이리저리 출렁이다가 ±1 로 갑니다. 그 출렁임에 방향이 있나요, 그리고 「예측이 충분히 확신하면 멈추는」 샘플러는 결과를 한쪽으로 치우치게 하나요. 이 글은 셋에 답하는 데 필요한 말을 세웁니다. 앞의 둘은 조건부 기댓값을 측도론으로 정의하고 그것이 직교 사영이라는 정리로 답하고, 셋째는 그 위에 마팅게일을 쌓아 답합니다.
조건부 기댓값
분할 위의 평균
지난 글에서 쓴 확률공간 (Ω,F,P) 에서 시작합니다. 「고급 3번 · 측도와 르베그 적분」에서 σ-대수는 확률을 매길 수 있는 사건의 모음이었습니다. 이 글에서는 σ-대수를 하나 더, 정보의 모음으로 읽습니다. 부분 σ-대수 G⊂F 는 「관측자가 일어났는지 아닌지를 아는 사건들」입니다.
가장 단순한 경우는 Ω 를 유한 개의 칸 B1,…,Bk 로 나눈 분할이 만드는 σ-대수입니다. 그 σ-대수의 원소는 칸 몇 개의 합집합이고, 관측자는 결과가 어느 칸에 떨어졌는지만 압니다. 그 관측자가 X 를 가장 잘 짐작하는 방법은 칸마다 평균을 내는 것입니다.
E[X∣G](ω)=P(Bi)E[X1Bi](ω∈Bi)
결과가 숫자가 아니라 확률변수라는 점이 중요합니다. 칸마다 값이 하나씩 정해진 함수이고, 칸 안에서는 상수입니다. 주사위를 던져 눈 ω 가 나오면 X=ω2 을 받는다고 합시다. 관측자가 「1·2 / 3·4 / 5·6」 가운데 어느 묶음인지만 안다면, 조건부 기댓값은 첫 칸에서 (1+4)/2=2.5, 둘째 칸에서 12.5, 셋째 칸에서 30.5 입니다. 관측자가 아무것도 모른다면, 곧 σ-대수가 {∅,Ω} 뿐이라면 칸이 하나라서 전체 평균 91/6=15.17 하나가 남습니다.
측도론적 정의
칸 평균은 확률이 0인 칸에서 무너집니다. 첫 질문의 {xt=x} 가 정확히 그런 칸입니다. 그래서 측도론은 칸마다 나누는 대신 칸 평균이 만족하는 성질을 정의로 삼습니다. 칸 평균 Z 는 칸 위에서 적분하면 X 를 적분한 것과 같습니다. 이것을 모든 사건으로 넓힙니다.
X 가 적분 가능하고 G⊂F 일 때, 다음 둘을 만족하는 확률변수 Z 를 X 의 G 에 대한 조건부 기댓값이라 부르고 E[X∣G] 로 적습니다.
Z 는 G-가측이고 적분 가능하다.
모든 A∈G 에서 E[Z1A]=E[X1A] 이다.
첫 조건은 「Z 는 관측자가 아는 것만으로 계산된다」이고, 둘째 조건은 「관측자가 아는 어떤 사건 위에서도 평균이 틀리지 않는다」입니다. X 자신은 둘째를 만족하지만 보통 첫째를 못 만족합니다. 관측자가 모르는 정보로 계산된 값이기 때문입니다.
유일성은 지난 글의 라돈–니코딤 도함수와 같은 논증입니다. Z1,Z2 가 둘 다 조건을 만족하면 A={Z1>Z2} 는 G 에 들고, E[(Z1−Z2)1A]=0 인데 적분하는 함수가 A 에서 양수이므로 P(A)=0 입니다. 자리를 바꿔도 같으니 Z1=Z2 가 거의 확실히 성립합니다. 그래서 조건부 기댓값은 확률변수 하나가 아니라 거의 확실히 같은 확률변수들의 묶음이고, 그 묶음의 원소 하나하나를 판본이라 부릅니다.
확률변수에 대한 조건
확률변수 Y 로 조건을 거는 것은 Y 가 만드는 σ-대수 σ(Y)={Y−1(B)} 로 거는 것입니다. E[X∣Y]:=E[X∣σ(Y)] 이고, 관측자가 Y 의 값을 보고 아는 것이 전부라는 뜻입니다. 여기에 둡–딘킨 보조정리가 붙습니다. σ(Y)-가측인 실수 확률변수는 언제나 어떤 가측함수 h 로 h(Y) 꼴로 적힌다는 정리입니다. 그래서 E[X∣Y]=m(Y) 인 함수 m 이 있고, 우리가 E[X∣Y=y] 라고 적는 것은 이 m(y) 입니다.
첫 질문의 절반이 여기서 풀립니다. E[x0∣xt=x] 는 확률 0인 사건 하나로 조건을 건 값이 아니라, 함수 m 을 x 에서 읽은 값입니다. m 은 사건 하나하나가 아니라 σ(xt) 전체 위의 적분 조건으로 정해집니다. 대가도 있습니다. 판본이 거의 확실히만 유일하므로 m 은 xt 의 분포로 재서 거의 어디서나만 정해지고, 점 하나에서의 값은 아무 판본이나 골라도 됩니다. 「그 점에서의 값」이 뜻을 가지려면 연속인 판본을 따로 찾아야 하는데, 가우스 잡음에서는 그런 판본이 있다는 것을 뒤에서 봅니다.
존재
정의는 했지만 그런 Z 가 있다는 보장은 아직 없습니다. 길이 둘이고, 하나가 지난 글의 라돈–니코딤 정리입니다. 먼저 X≥0 이라 합시다. G 위에서 ν(A)=E[X1A] 로 측도를 만들면, P(A)=0 인 A∈G 에서 ν(A)=0 이니 ν 는 P 를 G 로 좁힌 P∣G 에 대해 절대연속입니다. 둘 다 유한 측도이니 라돈–니코딤 도함수 Z=dν/dP∣G 가 있고, 그것은 G 위의 도함수라서 G-가측이며, 정의 그대로 E[Z1A]=ν(A)=E[X1A] 입니다. 부호가 있는 X 는 X+−X− 로 갈라 각각에 씁니다.
이 증명에서 핵심은 「G 로 좁힌다」입니다. 같은 ν 를 F 위에서 보면 도함수는 X 자신이고, 그것은 G-가측이 아닙니다. σ-대수를 좁히면 측도가 구별할 수 있는 사건이 줄어들고, 그 거친 눈으로 본 밀도가 조건부 기댓값입니다. 다른 길은 다음 절의 사영입니다. 그 길은 리스 표현 정리를 거쳐 라돈–니코딤 정리를 증명하던 길과 같은 뿌리를 가지고, 기하가 한눈에 보인다는 장점이 있습니다.
직교 사영
L² 부분공간
제곱 적분 가능한 확률변수의 공간 L2(F) 는 내적 ⟨X,Y⟩=E[XY] 를 가진 힐베르트 공간입니다. 원소는 거의 확실히 같은 확률변수의 묶음이고, 완비성은 「고급 3번」의 수렴 정리들에서 나옵니다. 그 안에서 G-가측인 원소만 모은 L2(G) 를 봅니다. 선형 결합이 G-가측이니 부분공간입니다.
닫혀 있다는 것도 보여야 합니다. Zn∈L2(G) 가 L2 에서 Z 로 가면, 부분수열이 거의 확실히 Z 로 갑니다. G-가측 함수열의 limsup 은 G-가측이므로 Z 는 거의 확실히 G-가측 함수와 같고, 그래서 Z 의 묶음이 L2(G) 에 듭니다. 「고급 2번 · 힐베르트 공간과 무한차원 스펙트럼 정리」의 사영 정리가 요구한 조건이 닫힌 부분공간이었고, 그 조건이 갖춰졌습니다. 모든 X∈L2(F) 에 대해 ∥X−Z∥ 를 가장 작게 하는 Z∈L2(G) 가 하나 있고, 그것은 X−Z 가 L2(G) 의 모든 원소와 직교한다는 조건으로 판정됩니다.
사영과의 등가
정리는 다음과 같습니다. X∈L2(F) 이고 PG 가 L2(G) 위로의 직교 사영이면
E[X∣G]=PGX(거의확실히)
입니다. 증명합니다. Z=PGX 로 둡니다. Z∈L2(G) 이니 G-가측이고, 확률공간에서 E∣Z∣≤(E[Z2])1/2 이니 적분 가능합니다. 정의의 첫 조건이 섭니다. 둘째 조건을 봅니다. A∈G 이면 지시함수 1A 는 유계이고 G-가측이라 L2(G) 의 원소입니다. 사영의 판정 조건으로 X−Z⊥1A, 곧 E[(X−Z)1A]=0 이고, 이것이 바로 E[Z1A]=E[X1A] 입니다. Z 가 정의의 두 조건을 다 만족하므로, 앞 절의 유일성으로 조건부 기댓값과 거의 확실히 같습니다.
거꾸로도 섭니다. Z=E[X∣G] 가 L2(G) 에 든다는 것을 따로 알면, 둘째 조건이 지시함수에 대한 직교를 주고, 선형성으로 단순함수, 극한으로 L2(G) 전체에 대한 직교가 되어 Z 가 사영의 판정 조건을 만족합니다. 첫 증명이 이미 PGX 가 조건부 기댓값임을 보였으니, 유일성이 이 방향을 덤으로 줍니다. 조건부 기댓값은 L2 위에서 정확히 직교 사영이고, 따라서 선형이고 PG2=PG 이며 노름을 늘리지 않습니다.
사영 쪽 길은 존재의 둘째 증명도 줍니다. X≥0 이면 PGX≥0 입니다. A={PGX<0} 는 G 에 들고 E[PGX1A]=E[X1A]≥0 인데 왼쪽은 P(A)>0 이면 음수이기 때문입니다. 그러니 적분 가능한 X≥0 에 대해 Xn=min(X,n) 의 사영은 n 에 따라 늘어나는 수열이고, 그 극한을 단조수렴 정리로 둘째 조건에 넘기면 L1 의 조건부 기댓값이 됩니다.
회귀함수
이 정리를 G=σ(Y) 에 쓰면 머신러닝의 가장 흔한 문장 하나가 정확해집니다. L2(σ(Y)) 는 둡–딘킨 보조정리로 제곱 적분 가능한 g(Y) 들의 모음이고, 사영은 그 모음에서 X 에 가장 가까운 원소입니다. 그러니 m(Y)=E[X∣Y] 는 모든 가측함수 g 가운데 E[(X−g(Y))2] 을 가장 작게 만듭니다. 이 m 을 회귀함수라 부릅니다. 직교성이 그 차이까지 정확히 적어 줍니다. X−m(Y) 가 m(Y)−g(Y) 와 직교하므로 피타고라스로
E[(X−g(Y))2]=E[(X−m(Y))2]+E[(m(Y)−g(Y))2]
입니다. 어떤 예측자의 제곱오차든 「회귀함수가 남기는 오차」와 「회귀함수에서 떨어진 거리」의 합입니다. 앞의 것은 예측자와 무관한 상수이고, 학습이 줄일 수 있는 것은 뒤의 것뿐입니다.
디노이저가 바로 이 경우입니다. 학습 손실 E∥D(xt)−x0∥2 은 x0 를 xt 의 함수로 예측하는 제곱오차이고, 그 최소점은 D∗(xt)=E[x0∣xt] 입니다. 논문의 한 줄은 이 정리를 확산 모델의 기호로 다시 적은 것입니다. 장난감에서 계산해 봅니다. 베이즈 정리로 xt=y 일 때 x0=1 일 사후확률과 x0=−1 일 사후확률의 비가 e2y/σ2 이므로
m(y)=ey/σ2+e−y/σ2ey/σ2−e−y/σ2=tanh(y/σ2)
입니다. 이 식이 정말 조건부 기댓값의 판본이라는 것은 정의로 확인합니다. 잡음 밀도를 φσ 로 적으면 E[x01B(xt)]=∫B∑s=±121sφσ(y−s)dy 이고, 적분 안이 정확히 m(y) 곱하기 xt 의 밀도이니 토넬리 정리로 E[m(xt)1B(xt)] 와 같습니다. 이 판본은 연속이고, 첫 질문의 「점에서의 값」은 이 연속 판본을 읽은 것입니다.
같은 계산을 다르게 정리하면 트위디 공식m(y)=y+σ2dydlogp(y) 가 나옵니다. 여기서 p 는 xt 의 밀도입니다. 장난감에서 dydlogp(y)=tanh(y)−y 이니 σ=1 에서 y+tanh(y)−y=tanh(y) 로 맞습니다. 디노이저를 학습하는 것과 점수 함수 ∇logp 를 학습하는 것이 같은 일이라는 확산 모델의 또 다른 한 줄이 이것입니다.
계산 규칙
타워 성질
조건부 기댓값의 계산은 몇 가지 규칙으로 거의 다 됩니다. 선형성과 단조성(거의 확실히 X≤X′ 이면 E[X∣G]≤E[X′∣G])은 정의와 유일성에서 바로 나옵니다. 그다음이 「아는 것은 밖으로 꺼낸다」는 규칙입니다. W 가 유계이고 G-가측이면
E[WX∣G]=WE[X∣G]
입니다. 오른쪽이 G-가측인 것은 분명하니 둘째 조건만 봅니다. W=1B (B∈G) 이면 A∈G 에서 E[1BE[X∣G]1A]=E[E[X∣G]1A∩B]=E[X1A∩B] 이고, 이것이 E[1BX1A] 입니다. 선형성으로 단순함수에서 서고, 유계 가측함수는 단순함수로 고르게 다가갈 수 있어 지배수렴 정리로 극한을 넘깁니다. 반대 끝은 독립입니다. X 가 G 와 독립이면 E[X1A]=E[X]P(A) 라서 상수 E[X] 가 조건부 기댓값입니다. 관측자의 정보가 X 에 대해 아무것도 말해 주지 않는 경우입니다.
가장 많이 쓰는 규칙은 타워 성질입니다. H⊂G, 곧 H 가 더 거친 정보이면
E[E[X∣G]H]=E[X∣H]=E[E[X∣H]G]
입니다. 증명합니다. 왼쪽 등식에서 Z=E[X∣G], V=E[X∣H] 로 두고, V 가 E[Z∣H] 의 정의를 만족함을 보입니다. V 는 H-가측입니다. A∈H 이면 A∈G 이기도 하므로 E[V1A]=E[X1A]=E[Z1A] 이고, 첫 등호는 V 의 정의, 둘째 등호는 Z 의 정의입니다. 유일성으로 끝납니다. 오른쪽 등식은 V 가 H⊂G 라서 이미 G-가측이라는 데서 나옵니다. 아는 것의 조건부 기댓값은 자기 자신입니다. H={∅,Ω} 로 두면 E[E[X∣G]]=E[X] 입니다.
주사위에서 보면 모양이 분명합니다. 칸 「1·2 / 3·4 / 5·6」 의 평균 2.5,12.5,30.5 를 다시 거친 칸 「14 / 5·6」 으로 평균하면, 앞 칸은 (2.5+12.5)/2=7.5 이고 이것은 처음부터 14의 값을 평균한 (1+4+9+16)/4=7.5 와 같습니다. 사영으로 읽으면 L2(H)⊂L2(G) 라 PHPG=PH 이고, 큰 평면에 먼저 떨어뜨렸다가 그 안의 직선으로 다시 떨어뜨려도 처음부터 직선으로 떨어뜨린 발과 같다는 말입니다.
전분산 공식
조건부 분산을 Var(X∣G)=E[(X−E[X∣G])2∣G] 로 둡니다. X∈L2 이면 전분산 공식
Var(X)=E[Var(X∣G)]+Var(E[X∣G])
이 섭니다. Z=E[X∣G] 로 두고 X−EX=(X−Z)+(Z−EX) 로 가릅니다. 뒤의 항은 상수를 뺀 G-가측 함수라 L2(G) 에 들고, 앞의 항은 사영의 잔차라 그것과 직교합니다. 피타고라스로 Var(X)=E[(X−Z)2]+E[(Z−EX)2] 이고, 타워 성질로 앞의 항이 E[Var(X∣G)] 입니다. 뒤의 항의 평균이 EZ=EX 라는 것도 타워 성질입니다.
주사위에서 Var(X)=149.14 는 칸 안의 분산 2.25,12.25,30.25 의 평균 14.92 와 칸 평균들의 분산 134.22 로 정확히 나뉩니다. 장난감 디노이저에서는 x0=±1 이라 Var(x0∣xt)=1−m(xt)2 이고, 전체 분산 1이 E[1−tanh2(xt)]=0.4496 과 Var(tanh(xt))=0.5504 로 나뉩니다. 앞의 수가 회귀함수가 남기는 오차, 곧 어떤 디노이저도 내려갈 수 없는 바닥입니다. 둘째 질문의 답이 여기 있습니다. 0.45는 덜 배운 것이 아니라 σ=1 에서 xt 를 보고도 남는 불확실성의 크기입니다. 비교로 가장 좋은 일차식 디노이저 y/(1+σ2) 는 σ2/(1+σ2)=0.5 에 머뭅니다.
조건부 젠센
조건부 젠센 부등식은 볼록함수 ϕ 와 적분 가능한 X,ϕ(X) 에 대해
ϕ(E[X∣G])≤E[ϕ(X)∣G](거의확실히)
라는 것입니다. 볼록함수는 자기 아래에 놓인 직선들의 상한이고, 기울기와 절편이 유리수인 가산 개의 직선 anx+bn 으로 충분합니다. 직선마다 ϕ(X)≥anX+bn 이니 단조성과 선형성으로 E[ϕ(X)∣G]≥anE[X∣G]+bn 이 영집합 Nn 밖에서 섭니다. 가산 개의 영집합을 합쳐도 영집합이니, 그 밖에서 모든 n 에 대해 동시에 섭니다. n 에 대한 상한을 잡으면 왼쪽 ϕ(E[X∣G]) 이 나옵니다. 가산 개로 줄여 두는 이유가 바로 이 영집합 합치기입니다. 직선이 비가산 개면 「거의 확실히」를 모아 붙일 수 없습니다.
ϕ(x)=x2 이면 E[X∣G]2≤E[X2∣G] 이고, 양변을 평균하면 사영이 노름을 줄인다는 사실이 다시 나옵니다. ϕ(x)=∣x∣p (p≥1) 이면 조건부 기댓값이 모든 Lp 에서 노름을 줄인다는 것이 나옵니다.
데이터 처리 부등식
지난 글이 미뤄 둔 것을 닫습니다. 데이터 처리 부등식은 가측사상 T 를 거친 두 분포의 KL이 원래 KL을 넘지 않는다는 것, 곧 DKL(P∘T−1∥Q∘T−1)≤DKL(P∥Q) 입니다. 오른쪽이 무한이면 할 일이 없으니 P≪Q 이고 w=dP/dQ 라 합시다. G=σ(T) 로 두면 T 의 분포끼리의 KL은 P∣G 와 Q∣G 의 KL과 같습니다. G 의 사건이 정확히 T−1(B) 들이기 때문입니다.
열쇠는 Q 아래에서 잰 조건부 기댓값 EQ[w∣G] 가 좁힌 두 측도의 도함수라는 것입니다. A∈G 에서 ∫AEQ[w∣G]dQ=∫AwdQ=P(A) 이니 정의 그대로입니다. 존재를 보인 앞 절의 논증을 거꾸로 읽은 셈입니다. 이제 ϕ(t)=tlogt 는 볼록하고 아래로 −1/e 에 묶여 있으니 조건부 젠센과 타워 성질로
이고, 마지막이 DKL(P∥Q) 입니다. 정보를 거칠게 하면 도함수가 조건부 평균으로 고르게 다듬어지고, 볼록한 ϕ 의 평균은 다듬을수록 줄어듭니다. 지난 글에서 잘린 두 정규분포의 KL 0.114가 자르기 전의 0.125보다 작았던 것이 이 부등식의 한 예입니다. 거기서 본 분할 하한도 같은 정리를 분할이 만드는 σ-대수에 쓴 것입니다.
마팅게일
여과와 적응 과정
이제 정보가 시간에 따라 늘어나는 상황으로 갑니다. σ-대수의 열 F0⊂F1⊂⋯⊂F 를 여과라 부릅니다. Fn 은 n 번째 걸음까지 관측자가 아는 사건들이고, 아는 것이 잊히지 않으니 늘어나기만 합니다. 확률변수의 열 Xn 이 걸음마다 Fn-가측이면 그 열이 여과에 적응했다고 합니다. n 번째 값은 n 번째까지의 정보로 계산된다는 뜻입니다.
셋째 질문의 상황이 여과입니다. 잡음 수준을 σ02=4 에서 시작해 걸음마다 반으로 줄여 σ72=1/32 까지 여덟 단계를 둡니다. 잡음은 한 번만 뽑습니다. 브라운 운동 W 를 하나 두고 Yk=x0+W(σk2) 로 두면, 각 Yk 는 잡음 σk 의 입력이고 여덟 입력이 한 경로 위에 있습니다. Fk=σ(Y0,…,Yk) 가 여과이고, 디노이저의 출력 Mk=E[x0∣Fk] 가 적응 과정입니다.
한 가지를 확인해 둡니다. Mk 는 여덟 개 중 앞 k+1 개를 다 본 조건부 기댓값인데, 디노이저가 실제로 보는 것은 지금의 Yk 하나입니다. 둘은 같습니다. j<k 이면 Yj=Yk+(W(σj2)−W(σk2)) 이고, 괄호 안의 증분은 브라운 운동의 독립 증분이라 x0 와도 Yk 와도 독립입니다. 지금보다 잡음이 큰 과거의 입력은 지금의 입력에 순수한 잡음을 더한 것이라 x0 에 대해 새로 말해 주는 것이 없습니다. 그래서 Mk=tanh(Yk/σk2) 입니다.
마팅게일의 세 갈래
적응 과정 Mn 이 걸음마다 적분 가능하고
E[Mn+1∣Fn]=Mn
이면 마팅게일이라 부릅니다. 지금까지의 정보로 본 다음 값의 최선의 예측이 지금 값이라는 것, 곧 공정한 게임의 누적 자산입니다. 등호 대신 ≥ 이면 서브마팅게일, ≤ 이면 슈퍼마팅게일입니다. 서브는 평균적으로 오르고 슈퍼는 평균적으로 내립니다. 타워 성질로 걸음을 몇 개 건너뛰어도 같은 관계가 섭니다. m>n 이면 E[Mm∣Fn]=Mn 이고, 특히 평균 E[Mn] 이 모든 n 에서 같습니다.
가장 중요한 예는 타워 성질 자체에서 나옵니다. 적분 가능한 X 하나를 두고 Mn=E[X∣Fn] 으로 두면, Fn⊂Fn+1 이라 E[Mn+1∣Fn]=E[X∣Fn]=Mn 입니다. 이렇게 정보가 늘어날 때마다 같은 대상을 다시 예측한 열을 둡 마팅게일이라 부릅니다. 디노이저의 출력 Mk 가 정확히 이것입니다. 셋째 질문의 첫 절반이 풀렸습니다. 출렁임에는 방향이 없습니다. 지금 Mk=0.6 이면 다음 걸음 값의 평균도 0.6이고, 이 뒤로 어떻게 움직일지를 지금의 정보로 내다볼 길이 없습니다.
다른 예도 몇 있습니다. 평균이 0인 독립 확률변수의 부분합 Sn=ξ1+⋯+ξn 은 Fn=σ(ξ1,…,ξn) 에 대해 마팅게일입니다. 마팅게일 Mn 에 볼록함수 ϕ 를 씌운 ϕ(Mn) 은 적분 가능하면 조건부 젠센으로 서브마팅게일이고, 그래서 ∣Mn∣ 과 Mn2 이 서브마팅게일입니다. 승률이 절반보다 낮은 게임에서 일정한 금액을 거는 도박사의 자산은 슈퍼마팅게일입니다.
마팅게일 변환
Hn 이 Fn−1-가측이면, 곧 n 번째 걸음이 일어나기 전에 정해지면 가예측이라 부릅니다. 가예측인 유계 H 와 마팅게일 M 으로
(H⋅M)n=∑k=1nHk(Mk−Mk−1)
을 만들면 이것도 마팅게일이고, 이것을 마팅게일 변환이라 부릅니다. 한 줄로 증명됩니다. E[Hn(Mn−Mn−1)∣Fn−1]=HnE[Mn−Mn−1∣Fn−1]=0 이고, 첫 등호가 아는 것을 꺼내는 규칙입니다. 공정한 게임에서는 지난 결과를 보고 거는 금액을 아무리 영리하게 바꿔도 기대 이득이 0이라는 말입니다. 여기서 Mk−Mk−1 처럼 조건부 평균이 0인 증분을 마팅게일 차분이라 부릅니다.
「중급 54번 · 베이스라인과 어드밴티지: 편향 없이 분산만 줄이기」가 이 변환의 한 경우입니다. 정책 경사에서 t 번째 걸음까지의 이력을 ht 로, 점수를 ψt=∇θlogπθ(At∣ht) 로 적습니다. 행동이 유한 개라면
이라 ψt 들은 이력의 여과에 대한 마팅게일 차분입니다. 베이스라인 bt 가 ht 로 계산되면 ψt 앞에서 가예측이고, 그래서 ∑tbtψt 는 마팅게일 변환이라 평균이 0입니다. 중급 54번은 상태의 함수 b(s) 를 다뤘는데, 이 논증은 훨씬 넓은 것을 허락합니다. 지난 보상들의 이동 평균, 앞선 행동, 앞선 에피소드의 결과처럼 At 를 뽑기 전에 정해지는 것이면 무엇이든 베이스라인이 될 수 있습니다. 반대로 At 나 그 뒤의 무엇에 기대는 순간 가예측이 깨지고 무편향의 근거가 사라집니다.
정지 시각과 수렴
정지 시각
셋째 질문의 둘째 절반은 「확신하면 멈춘다」입니다. 언제 멈출지를 미래를 보지 않고 정해야 한다는 조건을 적으면, 값이 {0,1,2,…,∞} 인 확률변수 τ 가 모든 n 에서 {τ=n}∈Fn 을 만족한다는 것입니다. 이런 τ 를 정지 시각이라 부릅니다. 「∣Mk∣≥0.9 가 처음 되는 k, 없으면 마지막 단계」는 정지 시각입니다. 지금까지의 값만 보고 정하기 때문입니다. 「Mk 가 가장 커지는 k」는 정지 시각이 아닙니다. 그 걸음에서는 뒤에 더 커질지 모르기 때문입니다.
멈춘 과정 Mτ∧n 은 그 자체로 마팅게일 변환입니다. Hk=1{τ≥k} 로 두면 Mτ∧n=M0+(H⋅M)n 이고, {τ≥k}={τ≤k−1}c 는 Fk−1 에 드니 H 가 가예측입니다. 그러니 멈춘 과정도 마팅게일이고 E[Mτ∧n]=E[M0] 이 모든 n 에서 섭니다.
옵셔널 스토핑 정리
옵셔널 스토핑 정리는 이것을 n→∞ 로 보내도 되는 조건을 줍니다. M 이 마팅게일이고 τ 가 정지 시각일 때, 다음 가운데 하나가 성립하면 E[Mτ]=E[M0] 입니다.
τ 가 어떤 상수 N 이하이다.
τ<∞ 가 거의 확실히 성립하고, 상수 K 가 있어 모든 n 에서 ∣Mτ∧n∣≤K 이다.
E[τ]<∞ 이고, 증분이 ∣Mk−Mk−1∣≤c 로 묶인다.
증명의 줄기만 적습니다. 첫 경우는 n=N 이면 Mτ∧N=Mτ 이라 바로 끝납니다. 둘째 경우는 Mτ∧n→Mτ 가 거의 확실히 성립하고 K 가 지배함수 노릇을 하므로 지배수렴 정리로 평균의 극한을 넘깁니다. 셋째 경우는 ∣Mτ∧n−M0∣≤cτ 이고 cτ 가 적분 가능하니 같은 정리를 씁니다. 공통된 뼈대는 「멈춘 과정은 언제나 마팅게일이고, 극한을 넘기는 데 지배함수가 필요하다」입니다.
조건이 장식이 아니라는 것은 대칭 랜덤워크로 봅니다. ±1 걸음의 Sn 을 0에서 시작해 +1 에 처음 닿을 때 멈추면, τ 는 거의 확실히 유한하지만 Sτ=1 이라 E[Sτ]=1=0 입니다. 멈추기 전 Sτ∧n 이 아래로 끝없이 내려갈 수 있어 지배함수가 없고, E[τ]=∞ 입니다. 「이길 때까지 판을 늘리는」 전략이 실제로는 무한한 자금을 요구한다는 말이기도 합니다. 반대로 −3 또는 +2 에 닿으면 멈추는 시각은 둘째 조건을 만족합니다. p=P(Sτ=2) 로 두면 0=2p−3(1−p) 이라 p=3/5 입니다. Sn2−n 도 마팅게일이니 같은 정리로 E[τ]=E[Sτ2]=4⋅0.6+9⋅0.4=6 입니다.
디노이저로 돌아가면 τ 는 여덟 단계 안에서 멈추니 첫 조건에 해당하고, E[Mτ]=E[M0]=E[x0]=0 입니다. 확신하면 멈추는 규칙은 예측의 평균을 치우치게 하지 않습니다. 더 강한 것도 섭니다. 멈춘 시각까지의 정보를 모은 σ-대수 Fτ 에 대해 E[x0∣Fτ]=Mτ 입니다. 멈춘 자리에서 디노이저가 0.95라고 말하면 x0=1 일 확률이 정말 (1+0.95)/2 라는 것, 곧 멈춘 예측이 보정되어 있다는 것입니다. 그림의 한 경로처럼 −0.912 로 멈췄는데 답이 +1 인 경우는 그 확률만큼 정확히 일어납니다.
마팅게일 수렴 정리
마팅게일 수렴 정리는 supnE∣Mn∣<∞ 인 마팅게일(서브마팅게일도 같다)이 거의 확실히 적분 가능한 극한 M∞ 로 수렴한다는 것입니다. 증명의 열쇠는 상향 교차입니다. a<b 를 두고, 과정이 a 아래에서 b 위로 올라간 횟수를 n 걸음까지 센 것을 Un 이라 합니다. a 아래로 내려가면 사고 b 위로 올라가면 파는 전략 H 는 가예측이고, 그 전략의 이득은 완성된 상향 교차마다 b−a 이상이며 마지막에 들고 있는 몫에서 잃는 것은 (Mn−a)− 이하입니다. 마팅게일 변환의 평균이 0이므로
(b−a)E[Un]≤E[(Mn−a)−]≤supnE∣Mn∣+∣a∣
입니다. 오른쪽이 n 과 무관하니 전체 상향 교차 수가 거의 확실히 유한합니다. 수렴하지 않는 열은 liminf<a<b<limsup 인 유리수 a,b 를 가지고, 그 사이를 무한히 오가야 하므로 이런 열은 확률 0입니다. 극한이 적분 가능하다는 것은 파투 보조정리가 줍니다.
둡 마팅게일에는 극한의 정체까지 알려 주는 정리가 있습니다. Mn=E[X∣Fn] 이면 Mn 은 거의 확실히 그리고 L1 에서 E[X∣F∞] 로 갑니다. 여기서 F∞ 는 모든 Fn 을 담는 가장 작은 σ-대수입니다. 잡음을 끝없이 반으로 줄이면 Yk→x0 이라 x0 가 F∞-가측이고, 그래서 Mk→x0 입니다. 출렁이던 디노이저 출력이 결국 정답으로 가는 이유가 이 정리입니다. 아래 코드에서 ∣Mk−x0∣ 의 평균이 0.80에서 0까지 줄어드는 것으로 확인합니다.
둡 부등식
마팅게일의 끝값만이 아니라 지나온 길 전체의 최댓값도 통제됩니다. 둡 부등식은 음이 아닌 서브마팅게일 Xn 과 λ>0 에 대해
P(maxk≤nXk≥λ)≤λE[Xn]
이라는 것입니다. 마르코프 부등식은 한 시각의 값에 대해 같은 경계를 주는데, 둡 부등식은 그것을 최댓값으로 공짜로 올려 줍니다. 증명합니다. A={maxk≤nXk≥λ} 로, τ 를 Xk≥λ 가 처음 되는 k (없으면 n) 로 둡니다. τ≤n 인 정지 시각이고, 가예측인 1{τ<k}≥0 으로 만든 변환 Xn−Xτ 는 서브마팅게일 위에서 평균이 0 이상이라 E[Xτ]≤E[Xn] 입니다. A 위에서는 Xτ≥λ 이고 A 밖에서는 τ=n 이니
E[Xn]≥E[Xτ]≥λP(A)+E[Xn1Ac]
이고, 정리하면 λP(A)≤E[Xn1A]≤E[Xn] 입니다. 같은 뼈대에서 L2 판 E[maxk≤nMk2]≤4E[Mn2] 도 나옵니다.
음이 아닌 슈퍼마팅게일에서는 같은 증명이 P(supnXn≥λ)≤E[X0]/λ 를 줍니다. 귀무가설 아래에서 우도비의 누적곱은 평균이 1인 음이 아닌 마팅게일이라 P(supnLn≥1/α)≤α 이고, 데이터를 보면서 아무 때나 멈춰도 거짓 양성이 α 를 넘지 않는 검정이 이 한 줄에서 나옵니다. 「고급 A13」의 e-값과 항시 유효 신뢰수열이 이 부등식 위에 섭니다.
아주마–회프딩 부등식
지수 모멘트
둡 부등식은 평균만 쓰는 경계라 느슨합니다. 증분의 크기를 알면 꼬리가 지수적으로 줄어든다는 것까지 말할 수 있습니다. 먼저 증분 하나에 대한 보조정리입니다. E[D∣G]=0 이고 상수 c 에 대해 ∣D∣≤c 이면, 모든 실수 λ 에서
E[eλD∣G]≤cosh(λc)≤eλ2c2/2
입니다. eλx 는 x 에 대해 볼록하므로 [−c,c] 위에서 양 끝을 잇는 현 아래에 있습니다. 곧 eλx≤2cc−xe−λc+2cc+xeλc 입니다. x=D 를 넣고 조건부 기댓값을 잡으면 D 의 항이 평균 0으로 사라져 cosh(λc) 가 남습니다. 둘째 부등호는 급수를 항별로 견줘 나옵니다. coshu=∑u2j/(2j)! 이고 eu2/2=∑u2j/(2jj!) 인데, (2j)!≥2jj! 이기 때문입니다.
이 보조정리는 증분이 평균 0이고 유계라는 것만 씁니다. 같은 분포를 따를 필요도, 서로 독립일 필요도 없습니다. 「고급 8번 · 집중부등식: 표본 하나가 기댓값에서 얼마나 벗어나는가」는 범위가 [a,b] 인 증분에서 지수의 상수를 (b−a)2/8 로 줄이는 판을 비롯해 이 계산을 일반적으로 다룹니다. 이 글에서는 마팅게일 차분에 필요한 만큼만 씁니다.
꼬리 경계
아주마–회프딩 부등식(Azuma–Hoeffding)은 마팅게일 Mn 의 증분이 ∣Mk−Mk−1∣≤ck 로 묶이면, 모든 t>0 에서
P(Mn−M0≥t)≤exp(−2∑k=1nck2t2)
이라는 것입니다. 아래 꼬리도 같고, 양쪽을 합치면 오른쪽에 2가 붙습니다. 증명은 보조정리를 걸음마다 한 번씩 씁니다. Dk=Mk−Mk−1 로 두면 eλ(Mn−1−M0) 는 Fn−1-가측이라 꺼낼 수 있으니
이고, 이것을 n 번 되풀이하면 exp(λ2S/2) 가 남습니다(S=∑ck2). 마르코프 부등식으로 P(Mn−M0≥t)≤e−λt+λ2S/2 이고, λ=t/S 로 두면 지수가 −t2/(2S) 가 됩니다. 독립 합에 대한 회프딩 부등식이 쓰던 증명을 걸음마다 조건부로 바꾼 것뿐인데, 그 덕에 증분이 과거에 따라 바뀌어도 됩니다.
증분이 과거에 기대는 예를 봅니다. 공정한 동전을 백 번 던지는데, 지금까지의 누적이 0 이상이면 1을 걸고 음수이면 0.5를 거는 도박사가 있습니다. 거는 크기가 과거로 정해지니 가예측이고, 누적 자산은 증분이 1 이하인 마팅게일입니다. 각 증분은 독립도 아니고 같은 분포도 아닙니다. 아주마–회프딩은 P(M100≥20)≤e−400/200=e−2=0.135 를 주고, 이십만 번 흉내 낸 실제 비율은 0.0195입니다. 거는 크기가 0.5로 줄어드는 걸음을 경계가 1로 셈하니 느슨할 수밖에 없지만, 걸음마다 다른 무게를 미리 몰라도 된다는 것이 이 부등식의 값입니다.
온라인 학습의 후회 경계가 이 모양을 씁니다. 매 라운드 손실이 [0,1] 안에 있으면 실제로 겪은 손실과 그 라운드의 조건부 기대 손실의 차는 크기가 1 이하인 마팅게일 차분입니다. 천 라운드 뒤 누적 차이가 2⋅1000⋅log20=77.4 를 넘을 확률이 5% 이하이고, 그래서 기댓값으로 증명한 후회 경계를 높은 확률의 경계로 옮길 때 n 짜리 항 하나가 붙습니다. SGD의 수렴 증명이 기울기 잡음을 ∑kηk(g^k−∇f(θk)) 로 따로 떼어 내는 것도 같은 이유입니다. 그 합이 마팅게일이라 평균에서는 사라지고, 크기는 둡 부등식이나 아주마–회프딩이 묶습니다. 이 분해는 「고급 A4」가 다룹니다.
다시 디노이저로
세 질문
첫머리의 논문 한 줄을 이제 정확히 읽을 수 있습니다. 「The optimal denoiser is the conditional expectation」은 제곱오차를 줄이는 문제가 L2(σ(xt)) 위로의 사영 문제이고, 그 사영이 조건부 기댓값이라는 정리를 말합니다. 디노이저의 함수 모양을 무엇으로 고르든, 그것이 고를 수 있는 함수 집합이 xt 의 함수들의 일부인 한 이 사영을 넘어설 수 없습니다.
첫째 질문의 답은 「확률 0인 사건 하나에 거는 것이 아니다」입니다. 조건부 기댓값은 σ(xt) 전체에 대한 적분 조건으로 정해지는 확률변수이고, 둡–딘킨 보조정리가 그것을 함수 m(xt) 로 적게 해 줍니다. 점 하나에서의 값은 판본에 따라 바뀌지만, 가우스 잡음에서는 베이즈 공식이 주는 연속 판본 tanh(x/σ2) 가 있어 그 값을 읽습니다. 둘째 질문의 답은 「바닥이다」입니다. 전분산 공식이 1을 0.4496과 0.5504로 나누고, 앞의 것이 회귀함수가 남기는 오차입니다. MLP의 0.45는 그 바닥에 닿은 것입니다. 셋째 질문의 답은 둘입니다. 한 경로 위의 디노이저 출력은 둡 마팅게일이라 출렁임에 방향이 없고, 유계인 정지 시각에서 옵셔널 스토핑 정리가 「확신하면 멈추기」의 평균을 그대로 둡니다. 멈춘 예측은 보정되어 있고, 끝까지 가면 수렴 정리가 정답으로 데려갑니다.
코드로 확인하기
백만 표본으로 세 디노이저의 손실과 직교성, 전분산을 보고, 이십만 개의 경로에서 마팅게일과 멈춘 예측을 확인합니다.
일차식 디노이저는 0.500, 3차 다항식은 0.462, 조건부 기댓값은 0.450에 멈추고, 적분으로 구한 바닥 0.4496과 맞습니다. 3차식이 바닥보다 높은 몫 0.0121은 3차식과 회귀함수 사이의 거리 제곱 0.0119와 표본 잡음 안에서 같습니다. 피타고라스가 말한 그대로입니다. 잔차 x0−m(y) 와 y 의 세 함수의 곱은 평균이 모두 0.002 안쪽이고, 분산 1은 두 몫의 합으로 되돌아옵니다. 경로 쪽에서는 여덟 단계의 평균이 모두 0 근처에 머물러 방향 없는 출렁임을 보이고, 정답까지의 평균 거리가 0.80에서 0으로 줄어 수렴 정리를 보입니다. 확신하면 멈추는 규칙의 평균은 0에서 표본 잡음 이상 벗어나지 않고, +0.9 이상에서 멈춘 경로 가운데 정답이 +1 인 비율 0.9843이 멈춘 예측이 말한 확률 0.9841과 맞습니다.
연습
주사위 눈 ω 에 대해 X=ω 이고, 관측자는 눈이 3 이하인지만 압니다. E[X∣G] 를 적고, 전분산 공식의 세 항을 각각 구해 맞는지 확인하세요.
{1,2,3} 에서 2, {4,5,6} 에서 5입니다. Var(X)=35/12=2.917 이고, 칸 안의 분산은 둘 다 2/3 이라 평균이 0.667, 칸 평균 2와 5의 분산은 1.52=2.25 입니다. 0.667+2.25=2.917 로 맞습니다.
X∼U[0,1] 이고 Y=X2+ε 이며 ε 은 X 와 독립이고 평균 0, 분산 0.01입니다. Y 를 X 의 함수로 예측할 때 가장 작은 제곱오차와, a+bX 꼴로만 예측할 때 가장 작은 제곱오차를 구하세요.
±1 걸음의 대칭 랜덤워크를 0에서 시작해 −1 또는 +4 에 처음 닿을 때 멈춥니다. +4 에서 멈출 확률과 멈추기까지의 걸음 수의 평균을 구하세요.
Sn 에 옵셔널 스토핑을 쓰면 0=4p−(1−p) 라 p=1/5 입니다. Sn2−n 에 쓰면 E[τ]=16⋅0.2+1⋅0.8=4 입니다. 멈춘 과정이 [−1,4] 안에 묶여 둘째 조건이 섭니다(둘째 마팅게일은 τ∧n 에서 평균을 잡은 뒤 단조수렴과 지배수렴으로 넘깁니다).
같은 랜덤워크의 처음 100걸음에서 maxk≤100∣Sk∣≥30 일 확률을 둡 부등식으로 위에서 누르세요.
Sk2 이 음이 아닌 서브마팅게일이라 P(maxk≤100Sk2≥900)≤E[S1002]/900=100/900=0.111 입니다. 이십만 번 흉내 낸 실제 비율은 0.0054로, 평균만 쓰는 경계는 느슨합니다.
증분이 ∣Mk−Mk−1∣≤0.5 인 마팅게일을 400걸음 돌립니다. 아주마–회프딩으로 P(M400−M0≥t)≤0.01 이 보장되는 가장 작은 t 를 구하세요.
∑ck2=400⋅0.25=100 이라 exp(−t2/200)≤0.01 이면 되고, t=200log100=30.35 입니다.
이 글이 세운 것은 「예측」이라는 말의 기하입니다. 조건부 기댓값은 관측자의 정보가 만드는 부분공간 위로의 직교 사영이고, 제곱오차의 최소점, 전분산의 분해, KL이 정보를 거칠게 하면 줄어드는 이유가 전부 이 사영의 성질입니다. 정보가 늘어나는 열에서 사영을 되풀이하면 마팅게일이 되고, 정지 시각, 수렴, 최댓값, 지수 꼬리가 그 열을 통제합니다. 이토 적분이 마팅게일이라는 성질은 「고급 A7」이 이 언어를 연속시간으로 옮겨 세웁니다. 다음 글 「고급 6번 · 스케치와 행렬 집중부등식: 큰 행렬을 줄여도 스펙트럼이 남는 이유」는 확률에서 대규모 선형대수로 넘어가는 A2 단원의 첫 편입니다. 큰 행렬에 무작위 행렬을 곱해 줄여도 스펙트럼이 남는다는 것을 보이는데, 그 증명이 기대는 행렬 집중부등식은 이 글의 아주마–회프딩을 행렬로 올린 것과 같은 뼈대를 가집니다.
갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.