수학

MATH / 고급 5번

조건부 기댓값은 사영이다, 그리고 마팅게일

σ-대수에 대한 조건부 기댓값을 정의하고 그것이 L² 직교 사영과 같음을 증명해, 확산 모델의 최적 디노이저가 조건부 평균인 이유와 손실의 바닥을 계산합니다. 타워 성질·전분산·조건부 젠센에서 마팅게일, 옵셔널 스토핑, 수렴 정리, 둡 부등식, 아주마–회프딩까지 갑니다.

PALDYN Team60 MIN READ

확산 모델을 학습하는 팀이 있습니다. 깨끗한 데이터 x0x_0 에 표준편차 σ\sigma 의 가우스 잡음을 더해 xt=x0+σεx_t = x_0 + \sigma \varepsilon 을 만들고, 디노이저 Dθ(xt,σ)D_\theta(x_t, \sigma) 가 x0x_0 를 맞히도록 제곱오차 ∥Dθ(xt,σ)−x0∥2\lVert D_\theta(x_t, \sigma) - x_0 \rVert^2 를 줄입니다. 구현이 맞는지 보려고 가장 작은 장난감부터 돌립니다. 데이터는 +1+1 과 −1-1 이 반반인 실수 하나이고 잡음은 σ=1\sigma = 1 입니다. 작은 MLP를 오래 학습해도 검증 손실이 0.45 근처에서 더 내려가지 않습니다. 참고하던 논문에는 이런 줄이 있습니다.

The optimal denoiser is the conditional expectation, D∗(x;σ)=E[x0∣xt=x]D^*(x; \sigma) = \mathbb{E}[x_0 \mid x_t = x].

리뷰에서 질문이 셋 나옵니다. 첫째, xtx_t 는 연속이라 xt=xx_t = x 라는 사건의 확률이 0인데, 확률 0인 사건으로 조건을 건 기댓값이 무슨 뜻인가요. 둘째, 0.45는 모델이 덜 배운 것인가요, 아니면 더 내려갈 수 없는 바닥인가요. 셋째, 잡음을 한 번 뽑아 둔 경로에서 σ\sigma 를 줄여 가며 디노이저를 읽으면 예측이 이리저리 출렁이다가 ±1\pm 1 로 갑니다. 그 출렁임에 방향이 있나요, 그리고 「예측이 충분히 확신하면 멈추는」 샘플러는 결과를 한쪽으로 치우치게 하나요. 이 글은 셋에 답하는 데 필요한 말을 세웁니다. 앞의 둘은 조건부 기댓값을 측도론으로 정의하고 그것이 직교 사영이라는 정리로 답하고, 셋째는 그 위에 마팅게일을 쌓아 답합니다.

조건부 기댓값

분할 위의 평균

지난 글에서 쓴 확률공간 (Ω,F,P)(\Omega, \mathcal{F}, P) 에서 시작합니다. 「고급 3번 · 측도와 르베그 적분」에서 σ-대수는 확률을 매길 수 있는 사건의 모음이었습니다. 이 글에서는 σ-대수를 하나 더, 정보의 모음으로 읽습니다. 부분 σ-대수 G⊂F\mathcal{G} \subset \mathcal{F} 는 「관측자가 일어났는지 아닌지를 아는 사건들」입니다.

가장 단순한 경우는 Ω\Omega 를 유한 개의 칸 B1,…,BkB_1, \dots, B_k 로 나눈 분할이 만드는 σ-대수입니다. 그 σ-대수의 원소는 칸 몇 개의 합집합이고, 관측자는 결과가 어느 칸에 떨어졌는지만 압니다. 그 관측자가 XX 를 가장 잘 짐작하는 방법은 칸마다 평균을 내는 것입니다.

E[X∣G](ω)=E[X1Bi]P(Bi)(ω∈Bi)\mathbb{E}[X \mid \mathcal{G}](\omega) = \frac{\mathbb{E}[X \mathbf{1}_{B_i}]}{P(B_i)} \quad (\omega \in B_i)

결과가 숫자가 아니라 확률변수라는 점이 중요합니다. 칸마다 값이 하나씩 정해진 함수이고, 칸 안에서는 상수입니다. 주사위를 던져 눈 ω\omega 가 나오면 X=ω2X = \omega^2 을 받는다고 합시다. 관측자가 「1·2 / 3·4 / 5·6」 가운데 어느 묶음인지만 안다면, 조건부 기댓값은 첫 칸에서 (1+4)/2=2.5(1 + 4)/2 = 2.5, 둘째 칸에서 12.512.5, 셋째 칸에서 30.530.5 입니다. 관측자가 아무것도 모른다면, 곧 σ-대수가 {∅,Ω}\{\varnothing, \Omega\} 뿐이라면 칸이 하나라서 전체 평균 91/6=15.1791/6 = 15.17 하나가 남습니다.

측도론적 정의

칸 평균은 확률이 0인 칸에서 무너집니다. 첫 질문의 {xt=x}\{x_t = x\} 가 정확히 그런 칸입니다. 그래서 측도론은 칸마다 나누는 대신 칸 평균이 만족하는 성질을 정의로 삼습니다. 칸 평균 ZZ 는 칸 위에서 적분하면 XX 를 적분한 것과 같습니다. 이것을 모든 사건으로 넓힙니다.

XX 가 적분 가능하고 G⊂F\mathcal{G} \subset \mathcal{F} 일 때, 다음 둘을 만족하는 확률변수 ZZ 를 XX 의 G\mathcal{G} 에 대한 조건부 기댓값이라 부르고 E[X∣G]\mathbb{E}[X \mid \mathcal{G}] 로 적습니다.

  1. ZZ 는 G\mathcal{G}-가측이고 적분 가능하다.
  2. 모든 A∈GA \in \mathcal{G} 에서 E[Z1A]=E[X1A]\mathbb{E}[Z \mathbf{1}_A] = \mathbb{E}[X \mathbf{1}_A] 이다.

첫 조건은 「ZZ 는 관측자가 아는 것만으로 계산된다」이고, 둘째 조건은 「관측자가 아는 어떤 사건 위에서도 평균이 틀리지 않는다」입니다. XX 자신은 둘째를 만족하지만 보통 첫째를 못 만족합니다. 관측자가 모르는 정보로 계산된 값이기 때문입니다.

유일성은 지난 글의 라돈–니코딤 도함수와 같은 논증입니다. Z1,Z2Z_1, Z_2 가 둘 다 조건을 만족하면 A={Z1>Z2}A = \{Z_1 > Z_2\} 는 G\mathcal{G} 에 들고, E[(Z1−Z2)1A]=0\mathbb{E}[(Z_1 - Z_2) \mathbf{1}_A] = 0 인데 적분하는 함수가 AA 에서 양수이므로 P(A)=0P(A) = 0 입니다. 자리를 바꿔도 같으니 Z1=Z2Z_1 = Z_2 가 거의 확실히 성립합니다. 그래서 조건부 기댓값은 확률변수 하나가 아니라 거의 확실히 같은 확률변수들의 묶음이고, 그 묶음의 원소 하나하나를 판본이라 부릅니다.

확률변수에 대한 조건

확률변수 YY 로 조건을 거는 것은 YY 가 만드는 σ-대수 σ(Y)={Y−1(B)}\sigma(Y) = \{Y^{-1}(B)\} 로 거는 것입니다. E[X∣Y]:=E[X∣σ(Y)]\mathbb{E}[X \mid Y] := \mathbb{E}[X \mid \sigma(Y)] 이고, 관측자가 YY 의 값을 보고 아는 것이 전부라는 뜻입니다. 여기에 둡–딘킨 보조정리가 붙습니다. σ(Y)\sigma(Y)-가측인 실수 확률변수는 언제나 어떤 가측함수 hh 로 h(Y)h(Y) 꼴로 적힌다는 정리입니다. 그래서 E[X∣Y]=m(Y)\mathbb{E}[X \mid Y] = m(Y) 인 함수 mm 이 있고, 우리가 E[X∣Y=y]\mathbb{E}[X \mid Y = y] 라고 적는 것은 이 m(y)m(y) 입니다.

첫 질문의 절반이 여기서 풀립니다. E[x0∣xt=x]\mathbb{E}[x_0 \mid x_t = x] 는 확률 0인 사건 하나로 조건을 건 값이 아니라, 함수 mm 을 xx 에서 읽은 값입니다. mm 은 사건 하나하나가 아니라 σ(xt)\sigma(x_t) 전체 위의 적분 조건으로 정해집니다. 대가도 있습니다. 판본이 거의 확실히만 유일하므로 mm 은 xtx_t 의 분포로 재서 거의 어디서나만 정해지고, 점 하나에서의 값은 아무 판본이나 골라도 됩니다. 「그 점에서의 값」이 뜻을 가지려면 연속인 판본을 따로 찾아야 하는데, 가우스 잡음에서는 그런 판본이 있다는 것을 뒤에서 봅니다.

존재

정의는 했지만 그런 ZZ 가 있다는 보장은 아직 없습니다. 길이 둘이고, 하나가 지난 글의 라돈–니코딤 정리입니다. 먼저 X≥0X \ge 0 이라 합시다. G\mathcal{G} 위에서 ν(A)=E[X1A]\nu(A) = \mathbb{E}[X \mathbf{1}_A] 로 측도를 만들면, P(A)=0P(A) = 0 인 A∈GA \in \mathcal{G} 에서 ν(A)=0\nu(A) = 0 이니 ν\nu 는 PP 를 G\mathcal{G} 로 좁힌 P∣GP|_{\mathcal{G}} 에 대해 절대연속입니다. 둘 다 유한 측도이니 라돈–니코딤 도함수 Z=dν/dP∣GZ = d\nu / dP|_{\mathcal{G}} 가 있고, 그것은 G\mathcal{G} 위의 도함수라서 G\mathcal{G}-가측이며, 정의 그대로 E[Z1A]=ν(A)=E[X1A]\mathbb{E}[Z \mathbf{1}_A] = \nu(A) = \mathbb{E}[X \mathbf{1}_A] 입니다. 부호가 있는 XX 는 X+−X−X^+ - X^- 로 갈라 각각에 씁니다.

이 증명에서 핵심은 「G\mathcal{G} 로 좁힌다」입니다. 같은 ν\nu 를 F\mathcal{F} 위에서 보면 도함수는 XX 자신이고, 그것은 G\mathcal{G}-가측이 아닙니다. σ-대수를 좁히면 측도가 구별할 수 있는 사건이 줄어들고, 그 거친 눈으로 본 밀도가 조건부 기댓값입니다. 다른 길은 다음 절의 사영입니다. 그 길은 리스 표현 정리를 거쳐 라돈–니코딤 정리를 증명하던 길과 같은 뿌리를 가지고, 기하가 한눈에 보인다는 장점이 있습니다.

직교 사영

L² 부분공간

제곱 적분 가능한 확률변수의 공간 L2(F)L^2(\mathcal{F}) 는 내적 ⟨X,Y⟩=E[XY]\langle X, Y \rangle = \mathbb{E}[XY] 를 가진 힐베르트 공간입니다. 원소는 거의 확실히 같은 확률변수의 묶음이고, 완비성은 「고급 3번」의 수렴 정리들에서 나옵니다. 그 안에서 G\mathcal{G}-가측인 원소만 모은 L2(G)L^2(\mathcal{G}) 를 봅니다. 선형 결합이 G\mathcal{G}-가측이니 부분공간입니다.

닫혀 있다는 것도 보여야 합니다. Zn∈L2(G)Z_n \in L^2(\mathcal{G}) 가 L2L^2 에서 ZZ 로 가면, 부분수열이 거의 확실히 ZZ 로 갑니다. G\mathcal{G}-가측 함수열의 lim sup⁡\limsup 은 G\mathcal{G}-가측이므로 ZZ 는 거의 확실히 G\mathcal{G}-가측 함수와 같고, 그래서 ZZ 의 묶음이 L2(G)L^2(\mathcal{G}) 에 듭니다. 「고급 2번 · 힐베르트 공간과 무한차원 스펙트럼 정리」의 사영 정리가 요구한 조건이 닫힌 부분공간이었고, 그 조건이 갖춰졌습니다. 모든 X∈L2(F)X \in L^2(\mathcal{F}) 에 대해 ∥X−Z∥\lVert X - Z \rVert 를 가장 작게 하는 Z∈L2(G)Z \in L^2(\mathcal{G}) 가 하나 있고, 그것은 X−ZX - Z 가 L2(G)L^2(\mathcal{G}) 의 모든 원소와 직교한다는 조건으로 판정됩니다.

사영과의 등가

정리는 다음과 같습니다. X∈L2(F)X \in L^2(\mathcal{F}) 이고 PGP_{\mathcal{G}} 가 L2(G)L^2(\mathcal{G}) 위로의 직교 사영이면

E[X∣G]=PGX(거의 확실히)\mathbb{E}[X \mid \mathcal{G}] = P_{\mathcal{G}} X \quad \text{(거의 확실히)}

입니다. 증명합니다. Z=PGXZ = P_{\mathcal{G}} X 로 둡니다. Z∈L2(G)Z \in L^2(\mathcal{G}) 이니 G\mathcal{G}-가측이고, 확률공간에서 E∣Z∣≤(E[Z2])1/2\mathbb{E}\lvert Z \rvert \le (\mathbb{E}[Z^2])^{1/2} 이니 적분 가능합니다. 정의의 첫 조건이 섭니다. 둘째 조건을 봅니다. A∈GA \in \mathcal{G} 이면 지시함수 1A\mathbf{1}_A 는 유계이고 G\mathcal{G}-가측이라 L2(G)L^2(\mathcal{G}) 의 원소입니다. 사영의 판정 조건으로 X−Z⊥1AX - Z \perp \mathbf{1}_A, 곧 E[(X−Z)1A]=0\mathbb{E}[(X - Z) \mathbf{1}_A] = 0 이고, 이것이 바로 E[Z1A]=E[X1A]\mathbb{E}[Z \mathbf{1}_A] = \mathbb{E}[X \mathbf{1}_A] 입니다. ZZ 가 정의의 두 조건을 다 만족하므로, 앞 절의 유일성으로 조건부 기댓값과 거의 확실히 같습니다.

거꾸로도 섭니다. Z=E[X∣G]Z = \mathbb{E}[X \mid \mathcal{G}] 가 L2(G)L^2(\mathcal{G}) 에 든다는 것을 따로 알면, 둘째 조건이 지시함수에 대한 직교를 주고, 선형성으로 단순함수, 극한으로 L2(G)L^2(\mathcal{G}) 전체에 대한 직교가 되어 ZZ 가 사영의 판정 조건을 만족합니다. 첫 증명이 이미 PGXP_{\mathcal{G}} X 가 조건부 기댓값임을 보였으니, 유일성이 이 방향을 덤으로 줍니다. 조건부 기댓값은 L2L^2 위에서 정확히 직교 사영이고, 따라서 선형이고 PG2=PGP_{\mathcal{G}}^2 = P_{\mathcal{G}} 이며 노름을 늘리지 않습니다.

세로 화살표 X 가 바닥 평면 L²(G) 위로 수직으로 떨어진 발이 E[X|G] 이고, 그 차 X − E[X|G] 가 평면과 직각을 이룬다. 평면 위의 다른 두 점 y/2 와 3차식까지의 거리 제곱 0.500 과 0.462 가 발까지의 거리 제곱 0.450 보다 크다

사영 쪽 길은 존재의 둘째 증명도 줍니다. X≥0X \ge 0 이면 PGX≥0P_{\mathcal{G}} X \ge 0 입니다. A={PGX<0}A = \{P_{\mathcal{G}} X < 0\} 는 G\mathcal{G} 에 들고 E[PGX 1A]=E[X1A]≥0\mathbb{E}[P_{\mathcal{G}} X \, \mathbf{1}_A] = \mathbb{E}[X \mathbf{1}_A] \ge 0 인데 왼쪽은 P(A)>0P(A) > 0 이면 음수이기 때문입니다. 그러니 적분 가능한 X≥0X \ge 0 에 대해 Xn=min⁡(X,n)X_n = \min(X, n) 의 사영은 nn 에 따라 늘어나는 수열이고, 그 극한을 단조수렴 정리로 둘째 조건에 넘기면 L1L^1 의 조건부 기댓값이 됩니다.

회귀함수

이 정리를 G=σ(Y)\mathcal{G} = \sigma(Y) 에 쓰면 머신러닝의 가장 흔한 문장 하나가 정확해집니다. L2(σ(Y))L^2(\sigma(Y)) 는 둡–딘킨 보조정리로 제곱 적분 가능한 g(Y)g(Y) 들의 모음이고, 사영은 그 모음에서 XX 에 가장 가까운 원소입니다. 그러니 m(Y)=E[X∣Y]m(Y) = \mathbb{E}[X \mid Y] 는 모든 가측함수 gg 가운데 E[(X−g(Y))2]\mathbb{E}[(X - g(Y))^2] 을 가장 작게 만듭니다. 이 mm 을 회귀함수라 부릅니다. 직교성이 그 차이까지 정확히 적어 줍니다. X−m(Y)X - m(Y) 가 m(Y)−g(Y)m(Y) - g(Y) 와 직교하므로 피타고라스로

E[(X−g(Y))2]=E[(X−m(Y))2]+E[(m(Y)−g(Y))2]\mathbb{E}[(X - g(Y))^2] = \mathbb{E}[(X - m(Y))^2] + \mathbb{E}[(m(Y) - g(Y))^2]

입니다. 어떤 예측자의 제곱오차든 「회귀함수가 남기는 오차」와 「회귀함수에서 떨어진 거리」의 합입니다. 앞의 것은 예측자와 무관한 상수이고, 학습이 줄일 수 있는 것은 뒤의 것뿐입니다.

디노이저가 바로 이 경우입니다. 학습 손실 E∥D(xt)−x0∥2\mathbb{E}\lVert D(x_t) - x_0 \rVert^2 은 x0x_0 를 xtx_t 의 함수로 예측하는 제곱오차이고, 그 최소점은 D∗(xt)=E[x0∣xt]D^*(x_t) = \mathbb{E}[x_0 \mid x_t] 입니다. 논문의 한 줄은 이 정리를 확산 모델의 기호로 다시 적은 것입니다. 장난감에서 계산해 봅니다. 베이즈 정리로 xt=yx_t = y 일 때 x0=1x_0 = 1 일 사후확률과 x0=−1x_0 = -1 일 사후확률의 비가 e2y/σ2e^{2y/\sigma^2} 이므로

m(y)=ey/σ2−e−y/σ2ey/σ2+e−y/σ2=tanh⁡(y/σ2)m(y) = \frac{e^{y/\sigma^2} - e^{-y/\sigma^2}}{e^{y/\sigma^2} + e^{-y/\sigma^2}} = \tanh(y / \sigma^2)

입니다. 이 식이 정말 조건부 기댓값의 판본이라는 것은 정의로 확인합니다. 잡음 밀도를 φσ\varphi_\sigma 로 적으면 E[x01B(xt)]=∫B∑s=±112s φσ(y−s) dy\mathbb{E}[x_0 \mathbf{1}_B(x_t)] = \int_B \sum_{s = \pm 1} \tfrac{1}{2} s \, \varphi_\sigma(y - s) \, dy 이고, 적분 안이 정확히 m(y)m(y) 곱하기 xtx_t 의 밀도이니 토넬리 정리로 E[m(xt)1B(xt)]\mathbb{E}[m(x_t) \mathbf{1}_B(x_t)] 와 같습니다. 이 판본은 연속이고, 첫 질문의 「점에서의 값」은 이 연속 판본을 읽은 것입니다.

같은 계산을 다르게 정리하면 트위디 공식 m(y)=y+σ2ddylog⁡p(y)m(y) = y + \sigma^2 \frac{d}{dy} \log p(y) 가 나옵니다. 여기서 pp 는 xtx_t 의 밀도입니다. 장난감에서 ddylog⁡p(y)=tanh⁡(y)−y\frac{d}{dy} \log p(y) = \tanh(y) - y 이니 σ=1\sigma = 1 에서 y+tanh⁡(y)−y=tanh⁡(y)y + \tanh(y) - y = \tanh(y) 로 맞습니다. 디노이저를 학습하는 것과 점수 함수 ∇log⁡p\nabla \log p 를 학습하는 것이 같은 일이라는 확산 모델의 또 다른 한 줄이 이것입니다.

계산 규칙

타워 성질

조건부 기댓값의 계산은 몇 가지 규칙으로 거의 다 됩니다. 선형성과 단조성(거의 확실히 X≤X′X \le X' 이면 E[X∣G]≤E[X′∣G]\mathbb{E}[X \mid \mathcal{G}] \le \mathbb{E}[X' \mid \mathcal{G}])은 정의와 유일성에서 바로 나옵니다. 그다음이 「아는 것은 밖으로 꺼낸다」는 규칙입니다. WW 가 유계이고 G\mathcal{G}-가측이면

E[WX∣G]=W E[X∣G]\mathbb{E}[W X \mid \mathcal{G}] = W \, \mathbb{E}[X \mid \mathcal{G}]

입니다. 오른쪽이 G\mathcal{G}-가측인 것은 분명하니 둘째 조건만 봅니다. W=1BW = \mathbf{1}_B (B∈GB \in \mathcal{G}) 이면 A∈GA \in \mathcal{G} 에서 E[1BE[X∣G]1A]=E[E[X∣G]1A∩B]=E[X1A∩B]\mathbb{E}[\mathbf{1}_B \mathbb{E}[X \mid \mathcal{G}] \mathbf{1}_A] = \mathbb{E}[\mathbb{E}[X \mid \mathcal{G}] \mathbf{1}_{A \cap B}] = \mathbb{E}[X \mathbf{1}_{A \cap B}] 이고, 이것이 E[1BX1A]\mathbb{E}[\mathbf{1}_B X \mathbf{1}_A] 입니다. 선형성으로 단순함수에서 서고, 유계 가측함수는 단순함수로 고르게 다가갈 수 있어 지배수렴 정리로 극한을 넘깁니다. 반대 끝은 독립입니다. XX 가 G\mathcal{G} 와 독립이면 E[X1A]=E[X]P(A)\mathbb{E}[X \mathbf{1}_A] = \mathbb{E}[X] P(A) 라서 상수 E[X]\mathbb{E}[X] 가 조건부 기댓값입니다. 관측자의 정보가 XX 에 대해 아무것도 말해 주지 않는 경우입니다.

가장 많이 쓰는 규칙은 타워 성질입니다. H⊂G\mathcal{H} \subset \mathcal{G}, 곧 H\mathcal{H} 가 더 거친 정보이면

E[E[X∣G] ∣ H]=E[X∣H]=E[E[X∣H] ∣ G]\mathbb{E}\big[\mathbb{E}[X \mid \mathcal{G}] \,\big|\, \mathcal{H}\big] = \mathbb{E}[X \mid \mathcal{H}] = \mathbb{E}\big[\mathbb{E}[X \mid \mathcal{H}] \,\big|\, \mathcal{G}\big]

입니다. 증명합니다. 왼쪽 등식에서 Z=E[X∣G]Z = \mathbb{E}[X \mid \mathcal{G}], V=E[X∣H]V = \mathbb{E}[X \mid \mathcal{H}] 로 두고, VV 가 E[Z∣H]\mathbb{E}[Z \mid \mathcal{H}] 의 정의를 만족함을 보입니다. VV 는 H\mathcal{H}-가측입니다. A∈HA \in \mathcal{H} 이면 A∈GA \in \mathcal{G} 이기도 하므로 E[V1A]=E[X1A]=E[Z1A]\mathbb{E}[V \mathbf{1}_A] = \mathbb{E}[X \mathbf{1}_A] = \mathbb{E}[Z \mathbf{1}_A] 이고, 첫 등호는 VV 의 정의, 둘째 등호는 ZZ 의 정의입니다. 유일성으로 끝납니다. 오른쪽 등식은 VV 가 H⊂G\mathcal{H} \subset \mathcal{G} 라서 이미 G\mathcal{G}-가측이라는 데서 나옵니다. 아는 것의 조건부 기댓값은 자기 자신입니다. H={∅,Ω}\mathcal{H} = \{\varnothing, \Omega\} 로 두면 E[E[X∣G]]=E[X]\mathbb{E}[\mathbb{E}[X \mid \mathcal{G}]] = \mathbb{E}[X] 입니다.

주사위 눈 1 부터 6 의 값 1, 4, 9, 16, 25, 36 이 맨 윗줄에 있고, 가운데 줄은 두 칸씩 평균한 2.5, 12.5, 30.5, 그 아래 줄은 앞 네 칸과 뒤 두 칸을 평균한 7.5 와 30.5, 맨 아래는 전체 평균 15.17 이다. 가운데 줄을 거쳐 내려가도 바로 내려가도 같은 값에 닿는다

주사위에서 보면 모양이 분명합니다. 칸 「1·2 / 3·4 / 5·6」 의 평균 2.5,12.5,30.52.5, 12.5, 30.5 를 다시 거친 칸 「14 / 5·6」 으로 평균하면, 앞 칸은 (2.5+12.5)/2=7.5(2.5 + 12.5)/2 = 7.5 이고 이것은 처음부터 14의 값을 평균한 (1+4+9+16)/4=7.5(1 + 4 + 9 + 16)/4 = 7.5 와 같습니다. 사영으로 읽으면 L2(H)⊂L2(G)L^2(\mathcal{H}) \subset L^2(\mathcal{G}) 라 PHPG=PHP_{\mathcal{H}} P_{\mathcal{G}} = P_{\mathcal{H}} 이고, 큰 평면에 먼저 떨어뜨렸다가 그 안의 직선으로 다시 떨어뜨려도 처음부터 직선으로 떨어뜨린 발과 같다는 말입니다.

전분산 공식

조건부 분산을 Var(X∣G)=E[(X−E[X∣G])2∣G]\mathrm{Var}(X \mid \mathcal{G}) = \mathbb{E}[(X - \mathbb{E}[X \mid \mathcal{G}])^2 \mid \mathcal{G}] 로 둡니다. X∈L2X \in L^2 이면 전분산 공식

Var(X)=E[Var(X∣G)]+Var(E[X∣G])\mathrm{Var}(X) = \mathbb{E}[\mathrm{Var}(X \mid \mathcal{G})] + \mathrm{Var}(\mathbb{E}[X \mid \mathcal{G}])

이 섭니다. Z=E[X∣G]Z = \mathbb{E}[X \mid \mathcal{G}] 로 두고 X−EX=(X−Z)+(Z−EX)X - \mathbb{E}X = (X - Z) + (Z - \mathbb{E}X) 로 가릅니다. 뒤의 항은 상수를 뺀 G\mathcal{G}-가측 함수라 L2(G)L^2(\mathcal{G}) 에 들고, 앞의 항은 사영의 잔차라 그것과 직교합니다. 피타고라스로 Var(X)=E[(X−Z)2]+E[(Z−EX)2]\mathrm{Var}(X) = \mathbb{E}[(X - Z)^2] + \mathbb{E}[(Z - \mathbb{E}X)^2] 이고, 타워 성질로 앞의 항이 E[Var(X∣G)]\mathbb{E}[\mathrm{Var}(X \mid \mathcal{G})] 입니다. 뒤의 항의 평균이 EZ=EX\mathbb{E}Z = \mathbb{E}X 라는 것도 타워 성질입니다.

주사위에서 Var(X)=149.14\mathrm{Var}(X) = 149.14 는 칸 안의 분산 2.25,12.25,30.252.25, 12.25, 30.25 의 평균 14.9214.92 와 칸 평균들의 분산 134.22134.22 로 정확히 나뉩니다. 장난감 디노이저에서는 x0=±1x_0 = \pm 1 이라 Var(x0∣xt)=1−m(xt)2\mathrm{Var}(x_0 \mid x_t) = 1 - m(x_t)^2 이고, 전체 분산 1이 E[1−tanh⁡2(xt)]=0.4496\mathbb{E}[1 - \tanh^2(x_t)] = 0.4496 과 Var(tanh⁡(xt))=0.5504\mathrm{Var}(\tanh(x_t)) = 0.5504 로 나뉩니다. 앞의 수가 회귀함수가 남기는 오차, 곧 어떤 디노이저도 내려갈 수 없는 바닥입니다. 둘째 질문의 답이 여기 있습니다. 0.45는 덜 배운 것이 아니라 σ=1\sigma = 1 에서 xtx_t 를 보고도 남는 불확실성의 크기입니다. 비교로 가장 좋은 일차식 디노이저 y/(1+σ2)y / (1 + \sigma^2) 는 σ2/(1+σ2)=0.5\sigma^2 / (1 + \sigma^2) = 0.5 에 머뭅니다.

조건부 젠센

조건부 젠센 부등식은 볼록함수 ϕ\phi 와 적분 가능한 X,ϕ(X)X, \phi(X) 에 대해

ϕ(E[X∣G])≤E[ϕ(X)∣G](거의 확실히)\phi(\mathbb{E}[X \mid \mathcal{G}]) \le \mathbb{E}[\phi(X) \mid \mathcal{G}] \quad \text{(거의 확실히)}

라는 것입니다. 볼록함수는 자기 아래에 놓인 직선들의 상한이고, 기울기와 절편이 유리수인 가산 개의 직선 anx+bna_n x + b_n 으로 충분합니다. 직선마다 ϕ(X)≥anX+bn\phi(X) \ge a_n X + b_n 이니 단조성과 선형성으로 E[ϕ(X)∣G]≥anE[X∣G]+bn\mathbb{E}[\phi(X) \mid \mathcal{G}] \ge a_n \mathbb{E}[X \mid \mathcal{G}] + b_n 이 영집합 NnN_n 밖에서 섭니다. 가산 개의 영집합을 합쳐도 영집합이니, 그 밖에서 모든 nn 에 대해 동시에 섭니다. nn 에 대한 상한을 잡으면 왼쪽 ϕ(E[X∣G])\phi(\mathbb{E}[X \mid \mathcal{G}]) 이 나옵니다. 가산 개로 줄여 두는 이유가 바로 이 영집합 합치기입니다. 직선이 비가산 개면 「거의 확실히」를 모아 붙일 수 없습니다.

ϕ(x)=x2\phi(x) = x^2 이면 E[X∣G]2≤E[X2∣G]\mathbb{E}[X \mid \mathcal{G}]^2 \le \mathbb{E}[X^2 \mid \mathcal{G}] 이고, 양변을 평균하면 사영이 노름을 줄인다는 사실이 다시 나옵니다. ϕ(x)=∣x∣p\phi(x) = \lvert x \rvert^p (p≥1p \ge 1) 이면 조건부 기댓값이 모든 LpL^p 에서 노름을 줄인다는 것이 나옵니다.

데이터 처리 부등식

지난 글이 미뤄 둔 것을 닫습니다. 데이터 처리 부등식은 가측사상 TT 를 거친 두 분포의 KL이 원래 KL을 넘지 않는다는 것, 곧 DKL(P∘T−1 ∥ Q∘T−1)≤DKL(P ∥ Q)D_{\mathrm{KL}}(P \circ T^{-1} \,\|\, Q \circ T^{-1}) \le D_{\mathrm{KL}}(P \,\|\, Q) 입니다. 오른쪽이 무한이면 할 일이 없으니 P≪QP \ll Q 이고 w=dP/dQw = dP/dQ 라 합시다. G=σ(T)\mathcal{G} = \sigma(T) 로 두면 TT 의 분포끼리의 KL은 P∣GP|_{\mathcal{G}} 와 Q∣GQ|_{\mathcal{G}} 의 KL과 같습니다. G\mathcal{G} 의 사건이 정확히 T−1(B)T^{-1}(B) 들이기 때문입니다.

열쇠는 QQ 아래에서 잰 조건부 기댓값 EQ[w∣G]\mathbb{E}_Q[w \mid \mathcal{G}] 가 좁힌 두 측도의 도함수라는 것입니다. A∈GA \in \mathcal{G} 에서 ∫AEQ[w∣G] dQ=∫Aw dQ=P(A)\int_A \mathbb{E}_Q[w \mid \mathcal{G}] \, dQ = \int_A w \, dQ = P(A) 이니 정의 그대로입니다. 존재를 보인 앞 절의 논증을 거꾸로 읽은 셈입니다. 이제 ϕ(t)=tlog⁡t\phi(t) = t \log t 는 볼록하고 아래로 −1/e-1/e 에 묶여 있으니 조건부 젠센과 타워 성질로

DKL(P∣G ∥ Q∣G)=EQ[ϕ(EQ[w∣G])]≤EQ[EQ[ϕ(w)∣G]]=EQ[ϕ(w)]D_{\mathrm{KL}}(P|_{\mathcal{G}} \,\|\, Q|_{\mathcal{G}}) = \mathbb{E}_Q\big[\phi(\mathbb{E}_Q[w \mid \mathcal{G}])\big] \le \mathbb{E}_Q\big[\mathbb{E}_Q[\phi(w) \mid \mathcal{G}]\big] = \mathbb{E}_Q[\phi(w)]

이고, 마지막이 DKL(P ∥ Q)D_{\mathrm{KL}}(P \,\|\, Q) 입니다. 정보를 거칠게 하면 도함수가 조건부 평균으로 고르게 다듬어지고, 볼록한 ϕ\phi 의 평균은 다듬을수록 줄어듭니다. 지난 글에서 잘린 두 정규분포의 KL 0.114가 자르기 전의 0.125보다 작았던 것이 이 부등식의 한 예입니다. 거기서 본 분할 하한도 같은 정리를 분할이 만드는 σ-대수에 쓴 것입니다.

마팅게일

여과와 적응 과정

이제 정보가 시간에 따라 늘어나는 상황으로 갑니다. σ-대수의 열 F0⊂F1⊂⋯⊂F\mathcal{F}_0 \subset \mathcal{F}_1 \subset \cdots \subset \mathcal{F} 를 여과라 부릅니다. Fn\mathcal{F}_n 은 nn 번째 걸음까지 관측자가 아는 사건들이고, 아는 것이 잊히지 않으니 늘어나기만 합니다. 확률변수의 열 XnX_n 이 걸음마다 Fn\mathcal{F}_n-가측이면 그 열이 여과에 적응했다고 합니다. nn 번째 값은 nn 번째까지의 정보로 계산된다는 뜻입니다.

셋째 질문의 상황이 여과입니다. 잡음 수준을 σ02=4\sigma_0^2 = 4 에서 시작해 걸음마다 반으로 줄여 σ72=1/32\sigma_7^2 = 1/32 까지 여덟 단계를 둡니다. 잡음은 한 번만 뽑습니다. 브라운 운동 WW 를 하나 두고 Yk=x0+W(σk2)Y_k = x_0 + W(\sigma_k^2) 로 두면, 각 YkY_k 는 잡음 σk\sigma_k 의 입력이고 여덟 입력이 한 경로 위에 있습니다. Fk=σ(Y0,…,Yk)\mathcal{F}_k = \sigma(Y_0, \dots, Y_k) 가 여과이고, 디노이저의 출력 Mk=E[x0∣Fk]M_k = \mathbb{E}[x_0 \mid \mathcal{F}_k] 가 적응 과정입니다.

한 가지를 확인해 둡니다. MkM_k 는 여덟 개 중 앞 k+1k + 1 개를 다 본 조건부 기댓값인데, 디노이저가 실제로 보는 것은 지금의 YkY_k 하나입니다. 둘은 같습니다. j<kj < k 이면 Yj=Yk+(W(σj2)−W(σk2))Y_j = Y_k + (W(\sigma_j^2) - W(\sigma_k^2)) 이고, 괄호 안의 증분은 브라운 운동의 독립 증분이라 x0x_0 와도 YkY_k 와도 독립입니다. 지금보다 잡음이 큰 과거의 입력은 지금의 입력에 순수한 잡음을 더한 것이라 x0x_0 에 대해 새로 말해 주는 것이 없습니다. 그래서 Mk=tanh⁡(Yk/σk2)M_k = \tanh(Y_k / \sigma_k^2) 입니다.

마팅게일의 세 갈래

적응 과정 MnM_n 이 걸음마다 적분 가능하고

E[Mn+1∣Fn]=Mn\mathbb{E}[M_{n+1} \mid \mathcal{F}_n] = M_n

이면 마팅게일이라 부릅니다. 지금까지의 정보로 본 다음 값의 최선의 예측이 지금 값이라는 것, 곧 공정한 게임의 누적 자산입니다. 등호 대신 ≥\ge 이면 서브마팅게일, ≤\le 이면 슈퍼마팅게일입니다. 서브는 평균적으로 오르고 슈퍼는 평균적으로 내립니다. 타워 성질로 걸음을 몇 개 건너뛰어도 같은 관계가 섭니다. m>nm > n 이면 E[Mm∣Fn]=Mn\mathbb{E}[M_m \mid \mathcal{F}_n] = M_n 이고, 특히 평균 E[Mn]\mathbb{E}[M_n] 이 모든 nn 에서 같습니다.

가장 중요한 예는 타워 성질 자체에서 나옵니다. 적분 가능한 XX 하나를 두고 Mn=E[X∣Fn]M_n = \mathbb{E}[X \mid \mathcal{F}_n] 으로 두면, Fn⊂Fn+1\mathcal{F}_n \subset \mathcal{F}_{n+1} 이라 E[Mn+1∣Fn]=E[X∣Fn]=Mn\mathbb{E}[M_{n+1} \mid \mathcal{F}_n] = \mathbb{E}[X \mid \mathcal{F}_n] = M_n 입니다. 이렇게 정보가 늘어날 때마다 같은 대상을 다시 예측한 열을 둡 마팅게일이라 부릅니다. 디노이저의 출력 MkM_k 가 정확히 이것입니다. 셋째 질문의 첫 절반이 풀렸습니다. 출렁임에는 방향이 없습니다. 지금 Mk=0.6M_k = 0.6 이면 다음 걸음 값의 평균도 0.6이고, 이 뒤로 어떻게 움직일지를 지금의 정보로 내다볼 길이 없습니다.

가로축은 σ² 를 4 에서 1/32 까지 반씩 줄인 여덟 단계이고 세로축은 디노이저 출력 M_k 가 −1 에서 1 까지이다. 다섯 경로가 출렁이다가 ±1 로 가고, ±0.9 의 점선 띠에 처음 닿은 자리에 점이 찍혀 있다. 한 경로는 둘째 단계에서 −0.912 로 띠에 닿았지만 결국 +1 로 간다

다른 예도 몇 있습니다. 평균이 0인 독립 확률변수의 부분합 Sn=ξ1+⋯+ξnS_n = \xi_1 + \dots + \xi_n 은 Fn=σ(ξ1,…,ξn)\mathcal{F}_n = \sigma(\xi_1, \dots, \xi_n) 에 대해 마팅게일입니다. 마팅게일 MnM_n 에 볼록함수 ϕ\phi 를 씌운 ϕ(Mn)\phi(M_n) 은 적분 가능하면 조건부 젠센으로 서브마팅게일이고, 그래서 ∣Mn∣\lvert M_n \rvert 과 Mn2M_n^2 이 서브마팅게일입니다. 승률이 절반보다 낮은 게임에서 일정한 금액을 거는 도박사의 자산은 슈퍼마팅게일입니다.

마팅게일 변환

HnH_n 이 Fn−1\mathcal{F}_{n-1}-가측이면, 곧 nn 번째 걸음이 일어나기 전에 정해지면 가예측이라 부릅니다. 가예측인 유계 HH 와 마팅게일 MM 으로

(H⋅M)n=∑k=1nHk(Mk−Mk−1)(H \cdot M)_n = \sum_{k=1}^{n} H_k (M_k - M_{k-1})

을 만들면 이것도 마팅게일이고, 이것을 마팅게일 변환이라 부릅니다. 한 줄로 증명됩니다. E[Hn(Mn−Mn−1)∣Fn−1]=Hn E[Mn−Mn−1∣Fn−1]=0\mathbb{E}[H_n (M_n - M_{n-1}) \mid \mathcal{F}_{n-1}] = H_n \, \mathbb{E}[M_n - M_{n-1} \mid \mathcal{F}_{n-1}] = 0 이고, 첫 등호가 아는 것을 꺼내는 규칙입니다. 공정한 게임에서는 지난 결과를 보고 거는 금액을 아무리 영리하게 바꿔도 기대 이득이 0이라는 말입니다. 여기서 Mk−Mk−1M_k - M_{k-1} 처럼 조건부 평균이 0인 증분을 마팅게일 차분이라 부릅니다.

「중급 54번 · 베이스라인과 어드밴티지: 편향 없이 분산만 줄이기」가 이 변환의 한 경우입니다. 정책 경사에서 tt 번째 걸음까지의 이력을 hth_t 로, 점수를 ψt=∇θlog⁡πθ(At∣ht)\psi_t = \nabla_\theta \log \pi_\theta(A_t \mid h_t) 로 적습니다. 행동이 유한 개라면

E[ψt∣ht]=∑aπθ(a∣ht) ∇θlog⁡πθ(a∣ht)=∇θ∑aπθ(a∣ht)=∇θ1=0\mathbb{E}[\psi_t \mid h_t] = \sum_a \pi_\theta(a \mid h_t) \, \nabla_\theta \log \pi_\theta(a \mid h_t) = \nabla_\theta \sum_a \pi_\theta(a \mid h_t) = \nabla_\theta 1 = 0

이라 ψt\psi_t 들은 이력의 여과에 대한 마팅게일 차분입니다. 베이스라인 btb_t 가 hth_t 로 계산되면 ψt\psi_t 앞에서 가예측이고, 그래서 ∑tbtψt\sum_t b_t \psi_t 는 마팅게일 변환이라 평균이 0입니다. 중급 54번은 상태의 함수 b(s)b(s) 를 다뤘는데, 이 논증은 훨씬 넓은 것을 허락합니다. 지난 보상들의 이동 평균, 앞선 행동, 앞선 에피소드의 결과처럼 AtA_t 를 뽑기 전에 정해지는 것이면 무엇이든 베이스라인이 될 수 있습니다. 반대로 AtA_t 나 그 뒤의 무엇에 기대는 순간 가예측이 깨지고 무편향의 근거가 사라집니다.

정지 시각과 수렴

정지 시각

셋째 질문의 둘째 절반은 「확신하면 멈춘다」입니다. 언제 멈출지를 미래를 보지 않고 정해야 한다는 조건을 적으면, 값이 {0,1,2,…,∞}\{0, 1, 2, \dots, \infty\} 인 확률변수 τ\tau 가 모든 nn 에서 {τ=n}∈Fn\{\tau = n\} \in \mathcal{F}_n 을 만족한다는 것입니다. 이런 τ\tau 를 정지 시각이라 부릅니다. 「∣Mk∣≥0.9\lvert M_k \rvert \ge 0.9 가 처음 되는 kk, 없으면 마지막 단계」는 정지 시각입니다. 지금까지의 값만 보고 정하기 때문입니다. 「MkM_k 가 가장 커지는 kk」는 정지 시각이 아닙니다. 그 걸음에서는 뒤에 더 커질지 모르기 때문입니다.

멈춘 과정 Mτ∧nM_{\tau \wedge n} 은 그 자체로 마팅게일 변환입니다. Hk=1{τ≥k}H_k = \mathbf{1}\{\tau \ge k\} 로 두면 Mτ∧n=M0+(H⋅M)nM_{\tau \wedge n} = M_0 + (H \cdot M)_n 이고, {τ≥k}={τ≤k−1}c\{\tau \ge k\} = \{\tau \le k - 1\}^c 는 Fk−1\mathcal{F}_{k-1} 에 드니 HH 가 가예측입니다. 그러니 멈춘 과정도 마팅게일이고 E[Mτ∧n]=E[M0]\mathbb{E}[M_{\tau \wedge n}] = \mathbb{E}[M_0] 이 모든 nn 에서 섭니다.

옵셔널 스토핑 정리

옵셔널 스토핑 정리는 이것을 n→∞n \to \infty 로 보내도 되는 조건을 줍니다. MM 이 마팅게일이고 τ\tau 가 정지 시각일 때, 다음 가운데 하나가 성립하면 E[Mτ]=E[M0]\mathbb{E}[M_\tau] = \mathbb{E}[M_0] 입니다.

  1. τ\tau 가 어떤 상수 NN 이하이다.
  2. τ<∞\tau < \infty 가 거의 확실히 성립하고, 상수 KK 가 있어 모든 nn 에서 ∣Mτ∧n∣≤K\lvert M_{\tau \wedge n} \rvert \le K 이다.
  3. E[τ]<∞\mathbb{E}[\tau] < \infty 이고, 증분이 ∣Mk−Mk−1∣≤c\lvert M_k - M_{k-1} \rvert \le c 로 묶인다.

증명의 줄기만 적습니다. 첫 경우는 n=Nn = N 이면 Mτ∧N=MτM_{\tau \wedge N} = M_\tau 이라 바로 끝납니다. 둘째 경우는 Mτ∧n→MτM_{\tau \wedge n} \to M_\tau 가 거의 확실히 성립하고 KK 가 지배함수 노릇을 하므로 지배수렴 정리로 평균의 극한을 넘깁니다. 셋째 경우는 ∣Mτ∧n−M0∣≤cτ\lvert M_{\tau \wedge n} - M_0 \rvert \le c \tau 이고 cτc\tau 가 적분 가능하니 같은 정리를 씁니다. 공통된 뼈대는 「멈춘 과정은 언제나 마팅게일이고, 극한을 넘기는 데 지배함수가 필요하다」입니다.

조건이 장식이 아니라는 것은 대칭 랜덤워크로 봅니다. ±1\pm 1 걸음의 SnS_n 을 0에서 시작해 +1+1 에 처음 닿을 때 멈추면, τ\tau 는 거의 확실히 유한하지만 Sτ=1S_\tau = 1 이라 E[Sτ]=1≠0\mathbb{E}[S_\tau] = 1 \ne 0 입니다. 멈추기 전 Sτ∧nS_{\tau \wedge n} 이 아래로 끝없이 내려갈 수 있어 지배함수가 없고, E[τ]=∞\mathbb{E}[\tau] = \infty 입니다. 「이길 때까지 판을 늘리는」 전략이 실제로는 무한한 자금을 요구한다는 말이기도 합니다. 반대로 −3-3 또는 +2+2 에 닿으면 멈추는 시각은 둘째 조건을 만족합니다. p=P(Sτ=2)p = P(S_\tau = 2) 로 두면 0=2p−3(1−p)0 = 2p - 3(1 - p) 이라 p=3/5p = 3/5 입니다. Sn2−nS_n^2 - n 도 마팅게일이니 같은 정리로 E[τ]=E[Sτ2]=4⋅0.6+9⋅0.4=6\mathbb{E}[\tau] = \mathbb{E}[S_\tau^2] = 4 \cdot 0.6 + 9 \cdot 0.4 = 6 입니다.

디노이저로 돌아가면 τ\tau 는 여덟 단계 안에서 멈추니 첫 조건에 해당하고, E[Mτ]=E[M0]=E[x0]=0\mathbb{E}[M_\tau] = \mathbb{E}[M_0] = \mathbb{E}[x_0] = 0 입니다. 확신하면 멈추는 규칙은 예측의 평균을 치우치게 하지 않습니다. 더 강한 것도 섭니다. 멈춘 시각까지의 정보를 모은 σ-대수 Fτ\mathcal{F}_\tau 에 대해 E[x0∣Fτ]=Mτ\mathbb{E}[x_0 \mid \mathcal{F}_\tau] = M_\tau 입니다. 멈춘 자리에서 디노이저가 0.95라고 말하면 x0=1x_0 = 1 일 확률이 정말 (1+0.95)/2(1 + 0.95)/2 라는 것, 곧 멈춘 예측이 보정되어 있다는 것입니다. 그림의 한 경로처럼 −0.912-0.912 로 멈췄는데 답이 +1+1 인 경우는 그 확률만큼 정확히 일어납니다.

마팅게일 수렴 정리

마팅게일 수렴 정리는 sup⁡nE∣Mn∣<∞\sup_n \mathbb{E}\lvert M_n \rvert < \infty 인 마팅게일(서브마팅게일도 같다)이 거의 확실히 적분 가능한 극한 M∞M_\infty 로 수렴한다는 것입니다. 증명의 열쇠는 상향 교차입니다. a<ba < b 를 두고, 과정이 aa 아래에서 bb 위로 올라간 횟수를 nn 걸음까지 센 것을 UnU_n 이라 합니다. aa 아래로 내려가면 사고 bb 위로 올라가면 파는 전략 HH 는 가예측이고, 그 전략의 이득은 완성된 상향 교차마다 b−ab - a 이상이며 마지막에 들고 있는 몫에서 잃는 것은 (Mn−a)−(M_n - a)^- 이하입니다. 마팅게일 변환의 평균이 0이므로

(b−a) E[Un]≤E[(Mn−a)−]≤sup⁡nE∣Mn∣+∣a∣(b - a) \, \mathbb{E}[U_n] \le \mathbb{E}[(M_n - a)^-] \le \sup_n \mathbb{E}\lvert M_n \rvert + \lvert a \rvert

입니다. 오른쪽이 nn 과 무관하니 전체 상향 교차 수가 거의 확실히 유한합니다. 수렴하지 않는 열은 lim inf⁡<a<b<lim sup⁡\liminf < a < b < \limsup 인 유리수 a,ba, b 를 가지고, 그 사이를 무한히 오가야 하므로 이런 열은 확률 0입니다. 극한이 적분 가능하다는 것은 파투 보조정리가 줍니다.

둡 마팅게일에는 극한의 정체까지 알려 주는 정리가 있습니다. Mn=E[X∣Fn]M_n = \mathbb{E}[X \mid \mathcal{F}_n] 이면 MnM_n 은 거의 확실히 그리고 L1L^1 에서 E[X∣F∞]\mathbb{E}[X \mid \mathcal{F}_\infty] 로 갑니다. 여기서 F∞\mathcal{F}_\infty 는 모든 Fn\mathcal{F}_n 을 담는 가장 작은 σ-대수입니다. 잡음을 끝없이 반으로 줄이면 Yk→x0Y_k \to x_0 이라 x0x_0 가 F∞\mathcal{F}_\infty-가측이고, 그래서 Mk→x0M_k \to x_0 입니다. 출렁이던 디노이저 출력이 결국 정답으로 가는 이유가 이 정리입니다. 아래 코드에서 ∣Mk−x0∣\lvert M_k - x_0 \rvert 의 평균이 0.80에서 0까지 줄어드는 것으로 확인합니다.

둡 부등식

마팅게일의 끝값만이 아니라 지나온 길 전체의 최댓값도 통제됩니다. 둡 부등식은 음이 아닌 서브마팅게일 XnX_n 과 λ>0\lambda > 0 에 대해

P(max⁡k≤nXk≥λ)≤E[Xn]λP\Big(\max_{k \le n} X_k \ge \lambda\Big) \le \frac{\mathbb{E}[X_n]}{\lambda}

이라는 것입니다. 마르코프 부등식은 한 시각의 값에 대해 같은 경계를 주는데, 둡 부등식은 그것을 최댓값으로 공짜로 올려 줍니다. 증명합니다. A={max⁡k≤nXk≥λ}A = \{\max_{k \le n} X_k \ge \lambda\} 로, τ\tau 를 Xk≥λX_k \ge \lambda 가 처음 되는 kk (없으면 nn) 로 둡니다. τ≤n\tau \le n 인 정지 시각이고, 가예측인 1{τ<k}≥0\mathbf{1}\{\tau < k\} \ge 0 으로 만든 변환 Xn−XτX_n - X_\tau 는 서브마팅게일 위에서 평균이 0 이상이라 E[Xτ]≤E[Xn]\mathbb{E}[X_\tau] \le \mathbb{E}[X_n] 입니다. AA 위에서는 Xτ≥λX_\tau \ge \lambda 이고 AA 밖에서는 τ=n\tau = n 이니

E[Xn]≥E[Xτ]≥λP(A)+E[Xn1Ac]\mathbb{E}[X_n] \ge \mathbb{E}[X_\tau] \ge \lambda P(A) + \mathbb{E}[X_n \mathbf{1}_{A^c}]

이고, 정리하면 λP(A)≤E[Xn1A]≤E[Xn]\lambda P(A) \le \mathbb{E}[X_n \mathbf{1}_A] \le \mathbb{E}[X_n] 입니다. 같은 뼈대에서 L2L^2 판 E[max⁡k≤nMk2]≤4 E[Mn2]\mathbb{E}[\max_{k \le n} M_k^2] \le 4 \, \mathbb{E}[M_n^2] 도 나옵니다.

음이 아닌 슈퍼마팅게일에서는 같은 증명이 P(sup⁡nXn≥λ)≤E[X0]/λP(\sup_n X_n \ge \lambda) \le \mathbb{E}[X_0]/\lambda 를 줍니다. 귀무가설 아래에서 우도비의 누적곱은 평균이 1인 음이 아닌 마팅게일이라 P(sup⁡nLn≥1/α)≤αP(\sup_n L_n \ge 1/\alpha) \le \alpha 이고, 데이터를 보면서 아무 때나 멈춰도 거짓 양성이 α\alpha 를 넘지 않는 검정이 이 한 줄에서 나옵니다. 「고급 A13」의 e-값과 항시 유효 신뢰수열이 이 부등식 위에 섭니다.

아주마–회프딩 부등식

지수 모멘트

둡 부등식은 평균만 쓰는 경계라 느슨합니다. 증분의 크기를 알면 꼬리가 지수적으로 줄어든다는 것까지 말할 수 있습니다. 먼저 증분 하나에 대한 보조정리입니다. E[D∣G]=0\mathbb{E}[D \mid \mathcal{G}] = 0 이고 상수 cc 에 대해 ∣D∣≤c\lvert D \rvert \le c 이면, 모든 실수 λ\lambda 에서

E[eλD∣G]≤cosh⁡(λc)≤eλ2c2/2\mathbb{E}[e^{\lambda D} \mid \mathcal{G}] \le \cosh(\lambda c) \le e^{\lambda^2 c^2 / 2}

입니다. eλxe^{\lambda x} 는 xx 에 대해 볼록하므로 [−c,c][-c, c] 위에서 양 끝을 잇는 현 아래에 있습니다. 곧 eλx≤c−x2ce−λc+c+x2ceλce^{\lambda x} \le \frac{c - x}{2c} e^{-\lambda c} + \frac{c + x}{2c} e^{\lambda c} 입니다. x=Dx = D 를 넣고 조건부 기댓값을 잡으면 DD 의 항이 평균 0으로 사라져 cosh⁡(λc)\cosh(\lambda c) 가 남습니다. 둘째 부등호는 급수를 항별로 견줘 나옵니다. cosh⁡u=∑u2j/(2j)!\cosh u = \sum u^{2j}/(2j)! 이고 eu2/2=∑u2j/(2jj!)e^{u^2/2} = \sum u^{2j}/(2^j j!) 인데, (2j)!≥2jj!(2j)! \ge 2^j j! 이기 때문입니다.

이 보조정리는 증분이 평균 0이고 유계라는 것만 씁니다. 같은 분포를 따를 필요도, 서로 독립일 필요도 없습니다. 「고급 8번 · 집중부등식: 표본 하나가 기댓값에서 얼마나 벗어나는가」는 범위가 [a,b][a, b] 인 증분에서 지수의 상수를 (b−a)2/8(b - a)^2 / 8 로 줄이는 판을 비롯해 이 계산을 일반적으로 다룹니다. 이 글에서는 마팅게일 차분에 필요한 만큼만 씁니다.

꼬리 경계

아주마–회프딩 부등식(Azuma–Hoeffding)은 마팅게일 MnM_n 의 증분이 ∣Mk−Mk−1∣≤ck\lvert M_k - M_{k-1} \rvert \le c_k 로 묶이면, 모든 t>0t > 0 에서

P(Mn−M0≥t)≤exp⁡ ⁣(−t22∑k=1nck2)P(M_n - M_0 \ge t) \le \exp\!\left( -\frac{t^2}{2 \sum_{k=1}^{n} c_k^2} \right)

이라는 것입니다. 아래 꼬리도 같고, 양쪽을 합치면 오른쪽에 2가 붙습니다. 증명은 보조정리를 걸음마다 한 번씩 씁니다. Dk=Mk−Mk−1D_k = M_k - M_{k-1} 로 두면 eλ(Mn−1−M0)e^{\lambda(M_{n-1} - M_0)} 는 Fn−1\mathcal{F}_{n-1}-가측이라 꺼낼 수 있으니

E[eλ(Mn−M0)]=E[eλ(Mn−1−M0) E[eλDn∣Fn−1]]≤eλ2cn2/2 E[eλ(Mn−1−M0)]\mathbb{E}[e^{\lambda(M_n - M_0)}] = \mathbb{E}\big[e^{\lambda(M_{n-1} - M_0)} \, \mathbb{E}[e^{\lambda D_n} \mid \mathcal{F}_{n-1}]\big] \le e^{\lambda^2 c_n^2 / 2} \, \mathbb{E}[e^{\lambda(M_{n-1} - M_0)}]

이고, 이것을 nn 번 되풀이하면 exp⁡(λ2S/2)\exp(\lambda^2 S / 2) 가 남습니다(S=∑ck2S = \sum c_k^2). 마르코프 부등식으로 P(Mn−M0≥t)≤e−λt+λ2S/2P(M_n - M_0 \ge t) \le e^{-\lambda t + \lambda^2 S / 2} 이고, λ=t/S\lambda = t/S 로 두면 지수가 −t2/(2S)-t^2/(2S) 가 됩니다. 독립 합에 대한 회프딩 부등식이 쓰던 증명을 걸음마다 조건부로 바꾼 것뿐인데, 그 덕에 증분이 과거에 따라 바뀌어도 됩니다.

가로축은 걸음 수 k 가 0 에서 100 까지, 세로축은 마팅게일 M_k 이다. 지난 값에 따라 거는 크기를 1 과 0.5 사이에서 바꾸는 서른 경로가 옅게 그려져 있고, 그 위에 ±2√k 의 곡선 띠가 있다. 띠는 k = 100 에서 ±20 이고, 그 자리에서 위 띠를 넘는 비율은 0.0195 로 경계 e⁻² = 0.135 보다 훨씬 작다

증분이 과거에 기대는 예를 봅니다. 공정한 동전을 백 번 던지는데, 지금까지의 누적이 0 이상이면 1을 걸고 음수이면 0.5를 거는 도박사가 있습니다. 거는 크기가 과거로 정해지니 가예측이고, 누적 자산은 증분이 1 이하인 마팅게일입니다. 각 증분은 독립도 아니고 같은 분포도 아닙니다. 아주마–회프딩은 P(M100≥20)≤e−400/200=e−2=0.135P(M_{100} \ge 20) \le e^{-400/200} = e^{-2} = 0.135 를 주고, 이십만 번 흉내 낸 실제 비율은 0.0195입니다. 거는 크기가 0.5로 줄어드는 걸음을 경계가 1로 셈하니 느슨할 수밖에 없지만, 걸음마다 다른 무게를 미리 몰라도 된다는 것이 이 부등식의 값입니다.

온라인 학습의 후회 경계가 이 모양을 씁니다. 매 라운드 손실이 [0,1][0, 1] 안에 있으면 실제로 겪은 손실과 그 라운드의 조건부 기대 손실의 차는 크기가 1 이하인 마팅게일 차분입니다. 천 라운드 뒤 누적 차이가 2⋅1000⋅log⁡20=77.4\sqrt{2 \cdot 1000 \cdot \log 20} = 77.4 를 넘을 확률이 5% 이하이고, 그래서 기댓값으로 증명한 후회 경계를 높은 확률의 경계로 옮길 때 n\sqrt{n} 짜리 항 하나가 붙습니다. SGD의 수렴 증명이 기울기 잡음을 ∑kηk(g^k−∇f(θk))\sum_k \eta_k (\hat g_k - \nabla f(\theta_k)) 로 따로 떼어 내는 것도 같은 이유입니다. 그 합이 마팅게일이라 평균에서는 사라지고, 크기는 둡 부등식이나 아주마–회프딩이 묶습니다. 이 분해는 「고급 A4」가 다룹니다.

다시 디노이저로

세 질문

첫머리의 논문 한 줄을 이제 정확히 읽을 수 있습니다. 「The optimal denoiser is the conditional expectation」은 제곱오차를 줄이는 문제가 L2(σ(xt))L^2(\sigma(x_t)) 위로의 사영 문제이고, 그 사영이 조건부 기댓값이라는 정리를 말합니다. 디노이저의 함수 모양을 무엇으로 고르든, 그것이 고를 수 있는 함수 집합이 xtx_t 의 함수들의 일부인 한 이 사영을 넘어설 수 없습니다.

첫째 질문의 답은 「확률 0인 사건 하나에 거는 것이 아니다」입니다. 조건부 기댓값은 σ(xt)\sigma(x_t) 전체에 대한 적분 조건으로 정해지는 확률변수이고, 둡–딘킨 보조정리가 그것을 함수 m(xt)m(x_t) 로 적게 해 줍니다. 점 하나에서의 값은 판본에 따라 바뀌지만, 가우스 잡음에서는 베이즈 공식이 주는 연속 판본 tanh⁡(x/σ2)\tanh(x / \sigma^2) 가 있어 그 값을 읽습니다. 둘째 질문의 답은 「바닥이다」입니다. 전분산 공식이 1을 0.4496과 0.5504로 나누고, 앞의 것이 회귀함수가 남기는 오차입니다. MLP의 0.45는 그 바닥에 닿은 것입니다. 셋째 질문의 답은 둘입니다. 한 경로 위의 디노이저 출력은 둡 마팅게일이라 출렁임에 방향이 없고, 유계인 정지 시각에서 옵셔널 스토핑 정리가 「확신하면 멈추기」의 평균을 그대로 둡니다. 멈춘 예측은 보정되어 있고, 끝까지 가면 수렴 정리가 정답으로 데려갑니다.

코드로 확인하기

백만 표본으로 세 디노이저의 손실과 직교성, 전분산을 보고, 이십만 개의 경로에서 마팅게일과 멈춘 예측을 확인합니다.

import numpy as np
from scipy import integrate
from scipy.stats import norm

rng = np.random.default_rng(0)
N = 1_000_000
x0 = rng.choice([-1.0, 1.0], N)                    # 데이터: ±1 이 반반
y = x0 + rng.normal(0.0, 1.0, N)                   # 잡음 σ = 1 을 더한 입력

m = np.tanh(y)                                     # E[x0 | y] = tanh(y / σ²)
lin = y / 2                                        # 가장 좋은 일차식 y/(1+σ²)
A = np.vander(y, 4)                                # 3차 다항식 공간으로 사영
coef = np.linalg.lstsq(A, x0, rcond=None)[0]
cub = A @ coef

mse = lambda d: np.mean((x0 - d) ** 2)
print(mse(lin), mse(cub), mse(m))                  # 0.5001... 0.4616... 0.4495...
print(mse(cub) - mse(m), np.mean((m - cub) ** 2))  # 0.01211... 0.01186...  ← 피타고라스
for g in (np.sign(y), y ** 3, np.cos(y)):          # 잔차는 y 의 어떤 함수와도 직교
    print(np.mean((x0 - m) * g))                   # 0.0007... -0.0018... 0.0007...

print(np.var(x0), np.mean(1 - m**2) + np.var(m))   # 0.99999... 0.99999...  ← 전분산

f = lambda t: (1 - np.tanh(t)**2) * 0.5 * (norm.pdf(t - 1) + norm.pdf(t + 1))
print(integrate.quad(f, -12, 12)[0])               # 0.4495995...  ← 바닥 E[Var(x0|y)]

# 같은 앞방향 경로에서 σ² 을 4 → 1/32 로 줄이며 디노이저를 읽는다
s2 = 4.0 / 2.0 ** np.arange(8)
n = 200_000
x = rng.choice([-1.0, 1.0], n)
inc = rng.normal(0, 1, (n, 8)) * np.sqrt(np.diff(np.r_[0, s2[::-1]]))
W = np.cumsum(inc, axis=1)[:, ::-1]                # W(σ²) 를 큰 σ² 부터
M = np.tanh((x[:, None] + W) / s2)                 # M_k = E[x0 | F_k]
print(np.round(M.mean(axis=0), 4))
# [-0.0013 -0.0011 -0.0018 -0.0018 -0.0037 -0.0032 -0.0028 -0.0028]
print(np.round(np.mean(np.abs(M - x[:, None]), axis=0), 4))
# [7.952e-01 6.496e-01 4.487e-01 2.317e-01 6.840e-02 7.300e-03 1.000e-04 0.000e+00]

hit = np.abs(M) >= 0.9                             # 확신하면 멈춘다
tau = np.where(hit.any(1), hit.argmax(1), 7)
Mt = M[np.arange(n), tau]
print(Mt.mean())                                   # -0.0026...  ← E[M_τ] = E[M_0] = 0
up = Mt >= 0.9
print(np.mean(x[up] == 1), np.mean((1 + Mt[up]) / 2))  # 0.98430... 0.98413...

일차식 디노이저는 0.500, 3차 다항식은 0.462, 조건부 기댓값은 0.450에 멈추고, 적분으로 구한 바닥 0.4496과 맞습니다. 3차식이 바닥보다 높은 몫 0.0121은 3차식과 회귀함수 사이의 거리 제곱 0.0119와 표본 잡음 안에서 같습니다. 피타고라스가 말한 그대로입니다. 잔차 x0−m(y)x_0 - m(y) 와 yy 의 세 함수의 곱은 평균이 모두 0.002 안쪽이고, 분산 1은 두 몫의 합으로 되돌아옵니다. 경로 쪽에서는 여덟 단계의 평균이 모두 0 근처에 머물러 방향 없는 출렁임을 보이고, 정답까지의 평균 거리가 0.80에서 0으로 줄어 수렴 정리를 보입니다. 확신하면 멈추는 규칙의 평균은 0에서 표본 잡음 이상 벗어나지 않고, +0.9+0.9 이상에서 멈춘 경로 가운데 정답이 +1+1 인 비율 0.9843이 멈춘 예측이 말한 확률 0.9841과 맞습니다.

연습

  1. 주사위 눈 ω\omega 에 대해 X=ωX = \omega 이고, 관측자는 눈이 3 이하인지만 압니다. E[X∣G]\mathbb{E}[X \mid \mathcal{G}] 를 적고, 전분산 공식의 세 항을 각각 구해 맞는지 확인하세요.
    {1,2,3}\{1, 2, 3\} 에서 2, {4,5,6}\{4, 5, 6\} 에서 5입니다. Var(X)=35/12=2.917\mathrm{Var}(X) = 35/12 = 2.917 이고, 칸 안의 분산은 둘 다 2/32/3 이라 평균이 0.6670.667, 칸 평균 2와 5의 분산은 1.52=2.251.5^2 = 2.25 입니다. 0.667+2.25=2.9170.667 + 2.25 = 2.917 로 맞습니다.
  2. X∼U[0,1]X \sim U[0, 1] 이고 Y=X2+εY = X^2 + \varepsilon 이며 ε\varepsilon 은 XX 와 독립이고 평균 0, 분산 0.01입니다. YY 를 XX 의 함수로 예측할 때 가장 작은 제곱오차와, a+bXa + bX 꼴로만 예측할 때 가장 작은 제곱오차를 구하세요.
    회귀함수는 E[Y∣X]=X2\mathbb{E}[Y \mid X] = X^2 이고 오차는 E[ε2]=0.01\mathbb{E}[\varepsilon^2] = 0.01 입니다. 일차식은 b=Cov(X,X2)/Var(X)=(1/12)/(1/12)=1b = \mathrm{Cov}(X, X^2)/\mathrm{Var}(X) = (1/12)/(1/12) = 1, a=1/3−1/2=−1/6a = 1/3 - 1/2 = -1/6 이고, 피타고라스로 오차가 0.01+E[(X2−X+1/6)2]=0.01+1/180=0.015560.01 + \mathbb{E}[(X^2 - X + 1/6)^2] = 0.01 + 1/180 = 0.01556 입니다. 백만 표본으로 0.01000과 0.01556이 나옵니다.
  3. ±1\pm 1 걸음의 대칭 랜덤워크를 0에서 시작해 −1-1 또는 +4+4 에 처음 닿을 때 멈춥니다. +4+4 에서 멈출 확률과 멈추기까지의 걸음 수의 평균을 구하세요.
    SnS_n 에 옵셔널 스토핑을 쓰면 0=4p−(1−p)0 = 4p - (1 - p) 라 p=1/5p = 1/5 입니다. Sn2−nS_n^2 - n 에 쓰면 E[τ]=16⋅0.2+1⋅0.8=4\mathbb{E}[\tau] = 16 \cdot 0.2 + 1 \cdot 0.8 = 4 입니다. 멈춘 과정이 [−1,4][-1, 4] 안에 묶여 둘째 조건이 섭니다(둘째 마팅게일은 τ∧n\tau \wedge n 에서 평균을 잡은 뒤 단조수렴과 지배수렴으로 넘깁니다).
  4. 같은 랜덤워크의 처음 100걸음에서 max⁡k≤100∣Sk∣≥30\max_{k \le 100} \lvert S_k \rvert \ge 30 일 확률을 둡 부등식으로 위에서 누르세요.
    Sk2S_k^2 이 음이 아닌 서브마팅게일이라 P(max⁡k≤100Sk2≥900)≤E[S1002]/900=100/900=0.111P(\max_{k \le 100} S_k^2 \ge 900) \le \mathbb{E}[S_{100}^2] / 900 = 100/900 = 0.111 입니다. 이십만 번 흉내 낸 실제 비율은 0.0054로, 평균만 쓰는 경계는 느슨합니다.
  5. 증분이 ∣Mk−Mk−1∣≤0.5\lvert M_k - M_{k-1} \rvert \le 0.5 인 마팅게일을 400걸음 돌립니다. 아주마–회프딩으로 P(M400−M0≥t)≤0.01P(M_{400} - M_0 \ge t) \le 0.01 이 보장되는 가장 작은 tt 를 구하세요.
    ∑ck2=400⋅0.25=100\sum c_k^2 = 400 \cdot 0.25 = 100 이라 exp⁡(−t2/200)≤0.01\exp(-t^2/200) \le 0.01 이면 되고, t=200log⁡100=30.35t = \sqrt{200 \log 100} = 30.35 입니다.

이 글이 세운 것은 「예측」이라는 말의 기하입니다. 조건부 기댓값은 관측자의 정보가 만드는 부분공간 위로의 직교 사영이고, 제곱오차의 최소점, 전분산의 분해, KL이 정보를 거칠게 하면 줄어드는 이유가 전부 이 사영의 성질입니다. 정보가 늘어나는 열에서 사영을 되풀이하면 마팅게일이 되고, 정지 시각, 수렴, 최댓값, 지수 꼬리가 그 열을 통제합니다. 이토 적분이 마팅게일이라는 성질은 「고급 A7」이 이 언어를 연속시간으로 옮겨 세웁니다. 다음 글 「고급 6번 · 스케치와 행렬 집중부등식: 큰 행렬을 줄여도 스펙트럼이 남는 이유」는 확률에서 대규모 선형대수로 넘어가는 A2 단원의 첫 편입니다. 큰 행렬에 무작위 행렬을 곱해 줄여도 스펙트럼이 남는다는 것을 보이는데, 그 증명이 기대는 행렬 집중부등식은 이 글의 아주마–회프딩을 행렬로 올린 것과 같은 뼈대를 가집니다.


읽어주셔서 감사합니다. 😊

LATEST

수학의 최신 글

수학2026.11.17

다양체 위의 최적화: 직교 제약과 Muon의 직교화가 하는 일

차트·접공간·리만 계량·측지선·후퇴로 다양체를 세우고, 스티펠·그라스만·양정치 행렬·확률 단체의 접공간과 사영을 계산한 뒤, 리만 그래디언트가 유클리드 그래디언트의 접공간 사영임을 증명하고 극분해 후퇴와 뉴턴–슐츠 반복의 수렴 조건을 다룹니다.

고급46 MIN
수학2026.11.17

프리컨디셔닝의 이론: Adam에서 K-FAC·Shampoo·Muon까지 한 줄로

갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.

고급41 MIN
수학2026.11.17

확률적 근사와 SGD의 연속 극한: 수렴한다는 말의 정확한 뜻

로빈스–먼로 조건과 마팅게일 잡음으로 SGD의 수렴을 정확히 정의하고, 볼록·강볼록·PL·비볼록에서의 수렴률과 오라클 하한을 계산한 뒤, SGD를 확률미분방정식으로 읽어 학습률/배치가 온도가 되는 관점과 안정성의 가장자리를 다룹니다.

고급48 MIN