6. 시간차 학습: 끝까지 기다리지 않고 예측으로 예측을 고친다

부트스트랩의 값: 편향과 분산

일곱 칸 랜덤 워크에서 시간차 학습은 몬테카를로보다 빨리 참값에 다가갔지만, 시간차 학습의 목표에는 아직 배우는 중인 예측이 들어 있다. 틀린 예측을 목표로 삼고도 어떻게 더 빨리 맞힐 수 있었으며, 예측이 크게 틀려 있다면 예측을 목표로 삼은 대가는 무엇일까?

역사: 서튼의 「처음 보는 판면」

서튼은 1988년 논문에서 「다음 예측이 결과보다 나은 목표일 수 있는가」를 게임으로 풀었다. 게임을 하다가 처음 보는 판면에 이르렀고, 그다음 판면은 지금까지 열에 아홉은 졌던 「나쁜 판면」이었다. 그런데 이번 판은 우연히 이겼으므로, 결과를 목표로 삼는 방법은 처음 보는 판면을 「이기는 판면」으로 배운다. 시간차 방법은 처음 보는 판면을 바로 뒤의 나쁜 판면과 맞춰 「나쁜 판면」으로 배운다. 서튼은 「나쁜 판면」을 제대로 알고 있다면 시간차 방법의 결론이 옳다고 봤다. 처음 보는 판면은 대개 진다고 알려진 판면으로 이어졌고, 그 뒤에 일어난 일은 상관이 없기 때문이다. 나중 판면의 평가는 그 뒤에 결과를 흔드는 운에 오염되지 않았기 때문에 실제 결과보다 나은 잣대라고 그는 적었다.

서튼은 같은 예로 시간차 방법이 실패하는 경우도 적었다. 나쁜 판면이 대개 지는 판면이지만, 처음 보는 판면을 거쳐 왔을 때만은 늘 이긴다고 하자. 이 이상한 경우에는 시간차 방법이 결과를 목표로 삼는 방법보다 나을 수 없고 더 못할 수도 있다고 그는 인정했다. 시간차 방법은 상태가 이어지는 순서에 담긴 정보를 쓰는데, 그 정보가 잘못 이끌 수도 있다는 것이다. 다만 그는 그 정보가 더 흔하게는 도움이 된다고 덧붙였다.

열흘 동안 적은 등굣길

서튼의 게임을 손으로 셈할 크기로 줄여 보자. 학생 하나가 열흘 동안 등굣길을 적었다. 친구 집에서 자고 나온 이틀은 친구 집에서 적기 시작했고, 두 번 다 환승역을 거쳐 지각했다. 집에서 나온 여드레는 환승역부터 적었고 정시 도착이 6번, 지각이 2번이었는데, 계산에서는 정시를 1, 지각을 0으로 친다.

이 기록만으로 「친구 집」의 가치, 곧 친구 집에서 출발해 정시에 닿을 확률을 어림하면 얼마일까? 몬테카를로는 친구 집에서 출발한 날의 결과만 보므로, 두 번 다 지각한 친구 집의 값은 0이다. 시간차 학습으로 이 열흘의 기록을 값이 더는 바뀌지 않을 때까지 되풀이해 학습하면 다른 답이 나온다. 환승역의 값은 환승역을 지난 열 번 가운데 정시 6번이라 0.6이 되고, 친구 집의 값은 늘 다음에 오는 환승역의 값을 목표로 삼으니 친구 집도 0.6이 된다(스크립트로 기록을 5,000번 되풀이해 학습한 값이 0.0000과 0.6000, 0.6000과 0.6000이다).

시간차 학습의 답은 기록에서 세상의 모델을 먼저 세운 것으로 읽을 수 있다. 「친구 집 다음은 늘 환승역(2번 중 2번)」, 「환승역 다음은 정시 10번 중 6번」. 그리고 그 모델이 정확히 맞다고 믿고 가치를 셈하면 친구 집의 가치는 1 × 0.6 = 0.6이다. 추정한 모델을 참이라고 믿고 셈한 이 답을 확실성 등가 추정(certainty-equivalence estimate)이라 부른다. 같은 데이터를 되풀이해 학습한 시간차 학습은 이 답으로 간다.

어느 답이 나을까? 환승역 뒤의 일이 어디서 왔는지와 상관없이 정해지는 세상(정시 확률이 늘 0.6)에서, 이런 꼴의 열흘 기록을 20만 번 새로 만들어 두 답을 비교했다. 둘 다 평균은 참값 0.6이었다. 그러나 친구 집의 값이 기록마다 흔들리는 폭(표준편차)은 몬테카를로가 0.347, 시간차 학습이 0.155였다. 몬테카를로는 친구 집에서 출발한 이틀만 쓰고, 시간차 학습은 환승역을 지난 열 번을 모두 쓰기 때문이다.

이처럼 자기가 가진 추정치를 목표에 넣어 그 추정치를 고쳐 가는 일을 부트스트랩 (자기 추정으로 자기 추정을 고친다 / bootstrapping)이라 한다. 신발 뒤축의 고리(bootstrap)를 잡아당겨 제 몸을 들어 올린다는 영어 표현에서 온 말이다. 통계학에서 데이터를 다시 뽑아 추정치의 표준편차를 재는 「부트스트랩」과는 다른 뜻으로 쓴다.

목표의 편향과 분산

부트스트랩이 무엇을 얻고 무엇을 치르는지는 한 칸의 목표를 들여다보면 보인다. 일곱 칸 랜덤 워크의 칸 6(참값 0.75)에서 한 스텝을 간다고 하자. 말은 반반으로 칸 5나 칸 7로 간다.

몬테카를로의 목표인 리턴은 0 아니면 1이다. 평균은 참값 0.75와 같지만, 목표 하나하나는 0.75에서 크게 떨어져 있다(분산 0.1875, 표준편차 0.433). 참값을 아는 시간차 학습의 목표는 0.625(칸 5의 값) 아니면 0.875(칸 7의 값)이다. 평균은 똑같이 0.75이고 분산은 0.015625로 몬테카를로의 12분의 1이다. 목표에 섞이는 운이 한 스텝치뿐이기 때문이다. 그러나 처음 값 0.5를 그대로 믿는 시간차 학습의 목표는 늘 0.5여서, 분산은 0이지만 참값 0.75보다 0.25 낮다.

추정치의 평균이 참값에서 벗어난 정도를 편향(bias), 추정치가 평균 둘레로 흩어진 정도를 분산이라 한다. 몬테카를로의 목표는 평균이 참값과 같은 편향 없는(unbiased) 목표이지만 분산이 크다. 시간차 학습의 목표는 분산이 작지만 다음 상태의 값이 틀린 만큼 치우치고, 이 편향은 학습이 진행되어 값이 참값에 다가가면 줄어든다. 일곱 칸 랜덤 워크에서 시간차 학습이 이긴 것은 처음 값 0.5가 크게 틀리지 않아 편향이 금방 줄었고, 그동안 작은 분산의 덕을 봤기 때문이다.

마지막 줄이 서튼이 적은 실패의 경우다. 등굣길의 확실성 등가 추정은 「환승역 다음의 일은 어디서 왔는지와 상관없다」는 가정 위에 서 있다. 그 가정이 깨지면 무슨 일이 생기는지는 아래 문제 5에서 셈한다.

학습률: 줄여 가야 참값에 모인다

일곱 칸 랜덤 워크에서 학습률 0.15의 시간차 학습은 에피소드 50개 뒤에도 100개 뒤에도 RMS 오차가 0.06~0.07 근처에 머물렀다. 학습률을 고정한 채 오래 학습하면 어떻게 되는지 보려고, 시간차 학습을 에피소드 5,000개까지 돌려 50줄 평균한 RMS 오차를 쟀다. 칸마다 그 칸을 지난 횟수로 1을 나눈 학습률($\textcolor{#536020}{\alpha}$ = 1/방문 횟수)도 함께 비교했다.

고정 학습률은 0.1이면 0.045 근처, 0.02이면 0.02 근처에서 멈춘다. 스텝마다 새 목표의 운이 $\textcolor{#536020}{\alpha}$만큼 섞여 들어오므로, 값은 참값 둘레를 그 폭으로 계속 흔들린다. 학습률을 줄여 가면 오차가 계속 내려간다.

어떻게 줄여야 하는지는 확률적 근사 이론이 답한다. 노이즈 섞인 목표를 하나씩 보며 값을 옮기는 일이 참값에 모이려면, 학습률의 합은 끝없이 커지고($\sum_n \textcolor{#536020}{\alpha_n} = \infty$, 어디서 출발해도 닿을 만큼 멀리 갈 수 있다) 학습률 제곱의 합은 유한해야 한다($\sum_n \textcolor{#536020}{\alpha_n}^2 < \infty$, 노이즈가 쌓여 계속 흔드는 일이 멈춘다). 1/n은 두 조건을 모두 만족하고, 고정 학습률은 둘째 조건을 어긴다. 서튼은 1988년 논문에서 표 꼴의 TD(0)가 평균에서 참값에 모인다는 것을 보였고, 피터 다얀(Peter Dayan)이 1992년에 확률 1로 모인다는 것을 보였다. 1994년에는 토미 야콜라(Tommi Jaakkola)·마이클 조던(Michael Jordan)·사틴더 싱(Satinder Singh)과 존 치치클리스(John Tsitsiklis)가 확률적 근사 이론을 넓혀 TD(0)가 참값에 모인다는 결과를 더 일반적인 경우로 늘렸다.

1/방문 횟수가 에피소드 5,000개 뒤에 고정 학습률 0.02보다 오차가 컸다는 것도 눈여겨보자. 조건은 언젠가 모인다는 것만 보장하고 얼마나 빨리 모이는지는 말하지 않는다. 시간차 학습의 목표는 학습 초기에 크게 틀려 있는데, 1/n은 초기의 틀린 목표들에 큰 무게를 준 뒤 학습률을 빨리 줄여 버린다. 실제 학습은 대개 작은 고정 학습률이나 천천히 줄이는 학습률 스케줄로 이 사이를 탄다.

ML에서: 비평가가 틀린 동안

언어 모델의 가치 모델(비평가)은 학습 초기에 거의 아무것도 모른다. 시간차 목표를 쓰면 그 틀린 예측이 목표로 들어가, 비평가는 자기의 틀린 값에 맞춰 배운다. 몬테카를로 목표는 이 편향이 없는 대신, 응답 끝의 점수 하나가 응답 앞부분 수백 개의 목표를 모두 흔든다. 비평가의 학습률을 고르는 일도 같은 저울질이다. 학습률이 크면 비평가가 빨리 따라오지만 응답 하나하나의 운에 크게 흔들리고, 작으면 덜 흔들리지만 정책이 바뀌는 속도를 놓친다. 고정 학습률에서 비평가 값의 표준편차가 얼마나 되는지는 아래 문제 6에서 셈한다.

문제 4. 내비게이션의 도착 예정 시각

민준 학생, 어느 목표를 쓰겠어요?

당연히 A요. 진짜로 걸린 시간이잖아요. 내비게이션은 늘 2분씩 짧게 말하니까 B는 틀린 목표예요.

A의 날마다의 값은 얼마나 흔들리죠? 사흘 평균이면요?

두 구간의 분산을 더하면 9 + 25 = 34 라서 표준편차 5.83분이에요. 사흘 평균이면 5.83 / √3 = 3.37분이고요.

B는요? B는 평균부터 틀려 있어요.

평균이 38분이라 2분 치우치고, 흔들림은 앞 구간의 3분뿐이니까 사흘 평균이면 3 / √3 = 1.73분 …

치우친 2분과 흔들림 1.73분을 RMS 오차 하나로 합치면요?

제곱해서 더하고 루트를 씌우면 되니까 √(2² + 3) = 2.65분이네요.

사흘이면 틀린 목표인 B가 오차가 더 작아요.

100일이면 A는 5.83 / 10 = 0.58분, B는 √(4 + 0.09) = 2.02분이야. 평균을 아무리 많이 내도 B의 2분 편향은 안 없어지니까, 날이 쌓이면 A가 이겨.

그래요. 바뀌는 날은 언제죠?

34 / n < 4 + 9 / n 을 풀면 n > 6.25, 그러니까 7일째부터 A가 나아요.

선배 말만 듣고 수강 신청하면 처음 몇 학기는 시행착오가 적은데, 선배가 늘 쉬운 과목만 추천하는 버릇이 있으면 그 버릇은 몇 학기를 다녀도 안 고쳐지는 거네요.

정리 (가) A: 평균 40분, 표준편차 √34 = 5.83분. B: 평균 38분(2분 편향), 표준편차 3분. (나) 사흘: A 3.37분, B √(4 + 9/3) = 2.65분. 100일: A 0.58분, B 2.02분. (다) 7일째부터 A가 낫다. 치우친 목표는 데이터가 적을 때 작은 분산으로 이기고, 데이터가 쌓이면 줄지 않는 편향 때문에 진다.

문제 5. 친구 집에서 온 날은 다른 버스

서연 학생, 두 방법의 평균부터 볼까요.

몬테카를로는 친구 집에서 온 이틀의 결과만 보니까 평균이 참값 0.2예요. 시간차 학습은 친구 집의 값을 환승역의 값에 맞추는데, 환승역의 값은 지나간 열 번의 정시 비율이라 평균이 (2 × 0.2 + 8 × 0.7) / 10 = 0.6이에요.

민준 학생, 그래도 시간차 학습이 분산이 작으니까 낫지 않을까요?

분산은 작겠죠. 그런데 0.6과 0.2면 0.4나 치우쳐요. 이틀치 데이터의 흔들림보다 그게 더 커요. 그래서 RMS 오차가 0.424로 몬테카를로의 0.283보다 크네요.

등굣길의 첫 계산에서는 시간차 학습이 이겼어요. 무엇이 달라졌죠?

그때는 환승역 뒤의 일이 어디서 왔는지와 상관없었어요. 지금은 같은 「환승역」인데 친구 집에서 온 날과 집에서 온 날의 앞날이 달라요.

그럼 「환승역」이라는 상태가 담지 못한 건 무엇이죠?

어느 길로 왔는지요. 앞날에 필요한 것을 다 담지 못하니까, 마르코프 성질이 깨진 거예요. 서튼의 처음 보는 판면에서 나쁜 판면이 처음 보는 판면을 거쳐 올 때만 이기는 경우랑 같아요.

그래요. (다)는요?

상태에 「어느 노선으로 왔나」를 넣으면 돼요. (환승역, 친구 집 노선)과 (환승역, 집 노선)을 다른 상태로 두면, 친구 집의 목표는 앞의 상태 값이 되니까 다시 0.2 쪽으로 가요.

수학 시간에 쓰는 조건부 기댓값이랑 같네. 조건을 빼먹고 평균 내면 다른 조건의 값이 섞여 들어와.

정리 (가) 참값 0.2. 몬테카를로는 평균 0.2(편향 없음), 시간차 학습은 평균 (2 × 0.2 + 8 × 0.7) / 10 = 0.6. (나) 「환승역」이 마르코프 상태가 아니라서, 시간차 학습이 다른 길로 온 날들의 앞날까지 섞은 값을 목표로 쓴다. 부트스트랩의 작은 분산(표준편차 0.142)보다 편향 0.4가 커서 RMS 오차가 0.424로 몬테카를로의 0.283보다 크다. (다) 앞날을 가르는 정보(어느 노선으로 왔나)를 상태에 넣어 마르코프 성질을 되찾는다. 시간차 학습은 상태가 마르코프일 때 데이터를 가장 잘 쓰고, 그렇지 않으면 몬테카를로보다 못할 수 있다.

문제 6. 비평가의 학습률

민준 학생, 학습률 0.1이면 오래 학습한 뒤 비평가의 값이 어디 있을까요?

0.7에 모이겠죠. 오래 학습하면 결국 정답에 닿잖아요.

오래 학습한 뒤에도 응답 하나가 오답이면 값이 얼마나 움직이죠?

0.7에서 0.1 × (0 − 0.7) = 0.07이나 내려가요. 다음이 정답이면 0.03 오르고요. 계속 그만큼씩 흔들리네요.

얼마나 흔들리는지는 힌트의 식에 넣어 보면 돼요.

√(0.1 / 1.9 × 0.21) = 0.105, 학습률 0.01이면 √(0.01 / 1.99 × 0.21) = 0.033이에요. 모의실험으로도 0.106과 0.033이 나왔어요.

1/n이면 $\textcolor{#00897b}{V}$는 지금까지 본 점수의 평균 그 자체야. 표준편차는 √(0.21 / n)이라 100개면 0.046, 1,000개면 0.015로 계속 줄어.

로빈스–먼로의 두 조건으로 보면요?

학습률의 합 1 + 1/2 + 1/3 + … 은 끝없이 커지고, 제곱의 합은 π²/6에 모이니까… 둘 다 만족해요.

그래요. 그럼 (다)는요?

정책이 바뀌면 이 앞부분에서 맞힐 확률 자체가 0.7에서 0.8로 바뀌어요.

그때 1,000번째 응답은 평균에 얼마나 들어가죠?

1/1,000의 무게밖에 안 들어가요. 옛날 정책의 점수 999개가 평균을 붙잡고 있어서 바뀐 값을 거의 못 따라가요.

그래서 실제로는 작은 고정 학습률을 쓰는 거네요. 조금 흔들리는 값을 감수하고 따라오는 속도를 사는 거고요. 학기 초 퀴즈까지 다 평균 내면 기말 직전 내 실력을 못 보여 주는 거랑 같아요.

정리 (가) 학습률 0.1: √(0.1/1.9 × 0.21) = 0.105, 학습률 0.01: 0.033. 고정 학습률은 참값 둘레에 학습률에 따라 커지는 분산을 남긴다. (나) 지금까지 본 점수의 표본 평균이 되고, 표준편차는 100개 뒤 0.046, 1,000개 뒤 0.015로 계속 준다. 1/n 은 로빈스–먼로의 두 조건을 만족한다. (다) 참값이 움직이는 문제에서 1/n 은 옛 데이터를 너무 오래 붙잡으므로, 정책과 함께 움직이는 비평가는 값의 분산을 감수하고 고정 학습률이나 천천히 줄이는 학습률 스케줄을 쓴다.