7. Q-러닝: 남이 둔 수로 최선의 수를 배운다

최대화 편향: 가장 좋아 보이는 값은 부풀어 있다

Q-러닝의 목표에는 $\max$가 들어 있어서 다음 칸의 네 방향 어림값 가운데 가장 큰 것을 골라 쓴다. 어림값이 참값이라면 문제가 없지만, 학습 초기의 어림값은 몇 번 겪어 본 것의 평균이라 노이즈가 크다. 노이즈 섞인 숫자 여럿 가운데 가장 큰 것을 고르면, 고른 숫자는 참값보다 클까 작을까?

맛집 앱에서 별점이 가장 높은 곳을 찾아가 봤다가 실망한 적이 있다면 이미 답을 겪어 봤다. 리뷰가 몇 개 없는 가게들 가운데 1등은, 정말 맛있어서이기도 하지만 마침 좋게 쓴 리뷰가 몰려서이기도 하다.

평균이 0 인 슬롯머신 열 대

가장 깨끗한 경우로 셈해 보자. 왜 「모두 평균이 0」일까? 참값이 모두 같으면 참 최댓값도 0이라, 고른 값이 0에서 벗어난 만큼이 그대로 고르는 일이 만든 편향이다.

슬롯머신 열 대가 있고, 한 번 당길 때마다 보상이 평균 0, 표준편차 1의 정규분포에서 나온다. 대마다 $\textcolor{#0033ff}{n}$번 당겨 평균을 어림값 $\textcolor{#00897b}{\hat Q_k}$로 삼고, 어림값이 가장 큰 기계를 고른다. 이 일을 20만 번 되풀이해 「고른 기계의 어림값」을 평균 냈다(난수 씨앗 20261023).

참 최댓값은 0인데, 다섯 번씩 당긴 어림값의 최댓값은 평균 0.688이다. 고른 기계를 다시 당기면 평균은 0으로 돌아오는데, 기계 수를 늘리면 고른 어림값은 더 부푼다. 다섯 번씩 당길 때 기계 두 대면 0.252, 백 대면 1.122였다.

부등식의 왼쪽은 「흔들리는 어림값들 가운데 가장 큰 것」의 평균이고 오른쪽은 참값들 가운데 가장 큰 것이다. 어림값 하나하나는 참값 둘레로 고르게 흔들리지만, 가장 큰 것을 고르는 순간 위로 흔들린 쪽이 뽑힌다. 그래서 왼쪽은 오른쪽보다 작을 수 없다. Q-러닝의 목표가 다음 칸의 $\max$를 쓰는 한, 어림값이 흔들리는 동안 목표는 위로 치우친다. 이 편향을 최대화 편향 (가장 큰 어림값을 고를 때 생기는 위쪽 편향 / maximization bias)이라 부른다. 여럿 가운데 가장 좋아 보여서 고른 값을 깎아서 읽어야 한다는 것은, 선호 쌍을 점수의 양 끝에서 고를 때 고른 마진을 깎아서 읽던 「마진 기반 필터링」의 교훈과 같은 이야기다. 여기서는 그 일이 학습의 목표 안에서 스텝마다 일어난다.

역사: 어림값을 두 벌 두자

네덜란드 국립 수학·정보과학 연구소(CWI)의 하도 판 하설트(Hado van Hasselt)는 2010년 학회 NeurIPS(당시 이름 NIPS)에 「Double Q-learning」을 냈다. 그는 Q-러닝이 노이즈 많은 몇몇 환경에서 유난히 못하는 원인을 이 편향에서 찾았다. 가장 큰 기댓값을 어림하려고 가장 큰 어림값을 쓰는 일이 행동 가치를 크게 부풀린다는 것이다. 그가 내놓은 처방은 어림값을 두 벌 두는 것이었다. 한 벌로는 어느 행동이 가장 좋아 보이는지를 고르고, 다른 벌로는 그 행동의 값을 읽는다. 논문은 이 「두 벌 어림」이 거꾸로 낮춰 읽을 수는 있어도 Q-러닝처럼 부풀리지는 않는다는 것, 이것으로 만든 더블 Q-러닝도 최적 정책에 다가간다는 것을 보였다.

슬롯머신 열 대로 확인해 보자. 대마다 열 번 당긴 기록을 앞 다섯 번(A)과 뒤 다섯 번(B)으로 나눈다. A로 고르고 A로 읽으면 0.687, A로 고르고 B로 읽으면 −0.0011이다. 고르는 데 쓴 노이즈와 읽는 데 쓴 노이즈가 서로 따로 놀아, 위로 흔들린 기계를 골랐어도 B에서는 그 운이 이어지지 않는다. 열 번을 다 써서 고르고 읽으면 0.486으로, 샘플이 늘어 덜 부풀 뿐 편향은 남는다. 대가도 있다. 한 대만 참 평균이 0.5이고 나머지는 0일 때, 한 벌로는 0.799로 부풀리고 두 벌로는 0.191로 낮춰 읽는다. A가 0.5짜리 기계를 고른 비율이 0.379뿐이라, 다른 기계를 골라 B로 읽으면 0 근처가 나오기 때문이다.

산책로의 Q-러닝에 이 생각을 넣으면, 표를 $\textcolor{#00897b}{Q^A}$, $\textcolor{#00897b}{Q^B}$ 두 벌 두고 스텝마다 동전을 던져 한 벌만 고친다. 걷는 방향은 두 표를 더한 값으로 고른다.

편향이 실제로 해를 끼치는 모습을 보려고 작은 갈림길을 만들었다. 퇴근길 갈림길에서 「집으로」를 고르면 보상 0을 받고 끝난다. 「골목으로」를 고르면 보상 0을 받고 포장마차 골목에 들어가, 포장마차 열 곳 가운데 하나를 고른다. 어느 포장마차든 만족도는 평균 −0.1, 표준편차 1이므로, 참값으로는 골목이 −0.1이라 집으로 가는 것이 낫다. $\textcolor{#cc00ff}{\varepsilon}$ = 0.1, $\textcolor{#993600}{\alpha}$ = 0.1로 에피소드 300번씩, 2,000번 학습시켜 「갈림길에서 골목을 고른 비율」을 쟀다.

Q-러닝은 21~30번째 에피소드에서 골목을 0.937의 비율로 골랐고, 300번째 무렵에도 0.12쯤에 머물렀다. 포장마차 열 곳의 어림값 가운데 가장 큰 것이 위로 부풀어 「골목으로」의 값을 끌어올리기 때문이다. 더블 Q-러닝은 처음 10번에 0.494로 시작해 빠르게 내려가, 마지막 50번에는 0.069였다. $\textcolor{#cc00ff}{\varepsilon}$ = 0.1의 무작위 차례만으로 골목에 들어가는 비율이 0.05이니, 거의 그만큼까지 내려왔다.

ML에서: 여러 응답 가운데 가장 높은 점수

언어 모델에서도 고른 값이 부푸는 일이 흔하다. 한 프롬프트에 응답을 $\textcolor{#5f970c}{N}$개 뽑고 보상 모델의 점수가 가장 높은 것을 고르는 방법(Best-of-N)을 생각해 보자. 보상 모델의 점수는 참 품질에 노이즈가 섞인 어림값이라서, 가장 높은 점수를 고르면 고른 응답의 점수는 참 품질보다 부풀어 있다. 고른 응답의 점수를 그대로 「이 정도 품질」로 믿거나, 그 점수를 다시 학습의 목표로 쓰면 슬롯머신의 0.688을 참값으로 믿는 것과 같다. 얼마나 부푸는지는 아래 문제 12에서 셈한다. 표를 신경망으로 바꾼 뒤에도 이 편향은 사라지지 않아, 두 벌로 고르고 읽는 처방이 거기서 다시 쓰인다.

문제 10. 리뷰 세 개짜리 1등 식당

민준 학생, 1등 식당에 가면 별점 몇 점짜리 끼니를 기대해요?

리뷰 평균이 1등이니까, 그 리뷰 평균 그대로요. 스크립트로 돌리면 1등의 리뷰 평균이 평균 4.58 이에요.

문제의 식당 20곳은 맛이 어떻다고 했죠?

똑같다고요. 그럼 1등 식당도 평균 3.5 짜리 식당이에요. 4.58 은 리뷰 세 개가 마침 좋게 몰린 거고요. 가서 먹으면 3.5 를 기대해야 하고, 차이가 1.08 이나 되네요.

(나)는 리뷰가 30개면 평균의 흔들림이 1/√30 로 줄어서, 1등이라도 3.84 쯤이야. 부푼 정도가 1.08 에서 0.34 로 줄었어. 리뷰가 많을수록 1등이 덜 부풀지만, 0 이 되지는 않아.

조교님이 퀴즈 한 번 점수로 우수 학생을 뽑으면, 다음 퀴즈에서 그 학생들 점수가 내려가는 거랑 같네요. 실력이 떨어진 게 아니라 처음 점수에 운이 섞여 있었던 거죠.

정리 (가) 1등 식당의 리뷰 평균은 평균 4.58이지만 가서 받을 별점의 기댓값은 3.50이다. 여럿 가운데 가장 좋아 보여서 고른 값은 부풀어 있다. (나) 3.84. 샘플이 늘면 덜 부풀지만 편향은 남는다.

문제 11. 기계 둘, 한 번씩

서연 학생, 두 대 모두 평균이 0 인데 큰 쪽의 평균은요?

둘 다 평균이 0 이니까 큰 쪽을 골라도 0 아닐까요? 어느 쪽이 크든 그 기계의 평균은 0 이잖아요.

「기계의 평균」 말고 「고른 값의 평균」을 물었어요. 둘 중 큰 값이 음수일 확률은 얼마죠?

둘 다 음수여야 하니까 1/4 이에요. 큰 값이 양수일 확률이 3/4 이니까 평균이 0 일 수 없네요.

그럼 얼마일까요? max 를 다루기 쉬운 꼴로 바꿀 수 있을까요?

음… 두 수 가운데 큰 쪽은 두 수의 가운데에서 두 수 사이 거리의 반만큼 위에 있어요. 그러니까 $\max(X_1, X_2) = \frac{X_1 + X_2}{2} + \frac{|X_1 - X_2|}{2}$ 요.

앞의 항은 평균이 0 이죠. 뒤의 항은요?

$X_1 - X_2$ 는 표준편차 $\sqrt 2$ 인 정규분포인데… 절댓값의 평균은 바로 안 떠오르네요.

표준정규분포라면요?

아, 그건 $\sqrt{2/\pi}$ 였어요. 그럼 $\mathbb{E}|X_1 - X_2| = \sqrt 2 \cdot \sqrt{2/\pi} = 2/\sqrt\pi$ 이고, 반을 하면 $1/\sqrt\pi$ ≈ 0.564 예요.

20만 번 돌리면 0.566 이에요. (나)는 첫 결과가 두 번째 결과와 상관없으니까 −0.0017, 그냥 0 이네요. 더블 Q-러닝이 두 벌로 나눈 게 이거구나.

(다)는요?

공식이 따로 있나요? 돌려 보면 0.847 이에요.

정규분포 세 개의 최댓값 기댓값은 $3/(2\sqrt\pi)$ ≈ 0.846 으로 알려져 있어요. 대수가 늘수록 커지네요. 순서통계량 수업에서 샘플이 많을수록 최댓값의 기댓값이 오르는 것과 같은 이야기예요.

정리 (가) $1/\sqrt\pi$ ≈ 0.564(모의실험 0.566). 큰 쪽을 고르는 순간 위로 흔들린 값이 뽑힌다. (나) 0(모의실험 −0.0017). 고르는 노이즈와 읽는 노이즈를 떼면 편향이 사라진다. (다) $3/(2\sqrt\pi)$ ≈ 0.846. 후보가 많을수록 더 부푼다.

문제 12. Best-of-N 의 점수

민준 학생, 응답이 많을수록 고른 응답이 좋아지니까 점수도 믿을 만해지겠죠?

네, 많이 뽑을수록 좋은 걸 고르니까요.

(가)에서는 응답들의 참 품질이 모두 같아요. 그러면 「좋은 걸 고른다」는 것은 무엇을 고르는 걸까요?

참 품질은 다 같으니까, 노이즈가 가장 위로 튄 걸 고르는 거네요.

얼마나 튀는지 $\textcolor{#5f970c}{N}$ 마다 돌려 볼까요.

$\textcolor{#5f970c}{N}$ = 1 에서 −0.004 로 사실상 0, 4 에서 0.514, 16 에서 0.881, 64 에서 1.173 이에요. 많이 뽑을수록 점수만 부풀어요. 아까 리뷰 1등 식당이랑 같아요.

(나)는 1.580 / 1.974 = 0.80 이니까 0.8 배로 깎으면 돼.

0.8 이라는 수는 문제의 어디에서 나왔을까요?

참 품질의 분산이 1, 노이즈 분산이 0.25 니까… 1/(1 + 0.25) = 0.8 이랑 맞아요. 점수에서 참 품질이 차지하는 분산의 몫만큼만 믿으라는 거네요.

그래요. 고른 점수를 그대로 학습의 목표로 쓰면 Q-러닝의 목표처럼 위로 치우친 값을 쫓게 돼요. 응답 하나를 따로 다시 채점하거나, 깎아서 읽어야 해요.

회귀분석에서 평균으로의 회귀를 배울 때, 첫 시험 점수로 예측한 다음 시험 점수가 늘 평균 쪽으로 당겨지던 것과 같은 계수네요.

정리 (가) −0.004(사실상 0), 0.514, 0.881, 1.173. 참 품질이 같으면 고르는 일은 노이즈를 고르는 일이고, 후보가 많을수록 더 부푼다. (나) 1.580 / 1.974 ≈ 0.80 = 1/(1 + 0.5²). 고른 응답의 점수는 참 품질이 차지하는 분산의 비율만큼 깎아서 읽는다.