게임 속 랭킹, 어떻게 정할까? (3) 실제 공식 유도과정

 

4. 논문 속 유도 과정

 지난 글에서의 유도 과정은 다소 직관에 호소했지만 여기서는 몇가지 가정 아래 수리통계적인 논증으로 유도한다.

 

(1) 기본 세팅

 한 rating period 동안 어떤 플레이어의 레이팅 $r$을 추정한다고 하자.

 

① 사전 분포(Prior distribution) :

 

$r \sim N(r_{\text{old}}, \sigma^2)$

 

 → 이 사람의 실력은 대략 $r_{\text{old}}$ 근처, 불확실성은 $\sigma$정도

 

② 관측값 : 

 $i$번째 상대와의 경기 결과 $s_i \in \{ 0, 0.5, 1 \}$

 

③ 예상 승률 : 로지스틱 근사에 의해

 

$E_i(r)=\dfrac{1}{1+10^{-g(\sigma_i)(r-r_i)/400}}$

 

$r_i$와 $\sigma_i$는 $i$번째 상대의 레이팅과 불확실성(편차), $g(\sigma_i)$는 로지스틱 근사에 의한 상대 불확실성 보정함수

 

이것들을 이용해서 우리가 하려는 것은 게임 결과 후의 진정한 확률분포를 찾는 것이다. 이를 찾기 위해서 주어진 경기 결과를 가장 잘 나타낼 수 있는, 사후 분포(Posterior distribution)의 최댓값을 찾는다. 즉,

 

$p(r | \{ s_1, s_2, \cdots, s_m \})$

 

의 최댓값을 찾아야 한다.

 

(2) 베이즈 정리

진짜 실력은 어떤 확률분포를 따르길래 이런 경기결과가 나왔을까?

 

이 질문에 답하기 위해 베이즈 정리

 

$p(X|Y)=\dfrac{p(Y|X)p(X)}{p(Y)}$

 

를 이용해서 진짜 실력을 추정해야 한다. 고등학교 확률과 통계 시간에 베이즈 정리라는 이름을 배우지는 않지만 조건부확률이라고 생각하면 된다. 다만, 조건부확률은 현재의 여러 사건들의 결과를 이용해서 미래의 결과를 예상하는 것이지만 베이즈 정리는 현재의 결과들을 이용해서 과거의 원인의 가능성을 추정하는 것이다.(기본 철학은 다르지만 사용하는 식은 같다)

 

우선, 편의를 위해 $p(s | \{ s_1, s_2, \cdots, s_m \})$을 $ p( r | \{  s_i\}) $라 하자.

 

우리는 $m$개의 경기 결과를 가지고 있으므로 베이즈 정리에 의해

 

$p(r | \{ s_i \}) \propto p(r) \displaystyle \prod_{i=1}^{m}p(s_i | r) $

 

이다. 이 식을 최적화하기 위해서 양변에 로그를 취하는 것이 좋으므로 각각의 인자를 따로 로그 취한 것을 계산해보자.

 

(3) Prior $p(r)$의 로그

 정규분포를 따른다고 가정하므로

 

$\log p(r) = -\dfrac{ (r-r_{\text{old}})^2 }{ 2\sigma^2 } + \text{const}$

 

(4) Likelihood의 로그

$i$번째 경기에 대해

 

$P(\text{win})=E_i(r)$

$P(\text{lose})=1-E_i(r)$

 

이므로

 

$\log p(s_i | r) = \begin{cases} \log E_i(r) & s_i=1 \\ \log (1-E_i(r)) & s_i=0 \\ \log(\text{혼합}) & s_i=0.5\text{(생략해도 됨)} \end{cases}$

 

하나의 식으로 쓰면

 

$ \log p(s_i | r) = s_i\log E_i(r) + (1-s_i)\log (1-E_i(r)) $

 

따라서 전체 로그 사후(Log posterior) $l(r)$은

 

$l(r) = -\dfrac{ (r-r_{\text{old}})^2 }{ 2\sigma^2 } + \displaystyle \sum_{i=1}^{m} \left [ s_i\log E_i(r) + (1-s_i)\log (1-E_i(r)) \right ] + \text{const}$

 

이다.

 

(5) 미분을 이용해서 최댓값 조건 찾기

이제 $l(r)$을 $r$에 대해 최댓값을 찾으면 되므로 $r$에 대하여 미분을 하면,

 

$l'(r) = -\dfrac{ r-r-_{\text{old}} }{ \sigma^2 } + \displaystyle \sum_{i=1}^{m}{ \left[ \dfrac{s_i}{E_i(r)}E_i'(r) - \dfrac{ 1 - s_i }{ 1 - E_i(r) }E_i'(r) \right] } $

 

대괄호 안을 정리하면

 

$ \dfrac{s_i}{E_i(r)}E_i'(r) - \dfrac{ 1 - s_i }{ 1 - E_i(r) }E_i'(r) = E_i'(r) \left( \dfrac{ s_i - E_i(r) }{ E_i(r)(1-E_i(r)) } \right) $

 

그런데 로지스틱 근사한 $E_i(r)$에 대해 미분을 하면 $E_i'(r)$은 $E_i(r)(1-E_i(r))$에 비례하므로

 

$E_i'(r) \approx q g(\sigma_i)E_i(r)(1-E_i(r))$

 

이고 이 식을 $l'(r)$에 대입하면

 

$l'(r) \approx -\dfrac{ r-r_{\text{old}} }{ \sigma^2 } + q \displaystyle \sum_{i=1}^{m}{ g(\sigma_i)(s_i - E_i(r)) } $

 

이 식이 "prior로부터의 끌어당김" + "데이터가 주는 오차 보정" 구조를 보여준다.

 

$l'(r) = 0$을 만족하는 $r$을 구해야 하지만 이것을 해석적으로 풀기는 어려우므로 수치해석을 위해 뉴턴-랩슨법을 이용한다.

 

(6) 뉴턴-랩슨으로 최적화

뉴턴-랩슨법에 의하면

 

$r_{\text{new}} = r_{\text{old}} -\dfrac{ l'(r_{\text{old}}) }{ l''(r_{\text{old}}) } $

 

이므로 second-derivative가 필요하다.

 

$ l''(r) = -\dfrac{1}{\sigma^2} + \displaystyle \sum_{i=1}^{m}{\text{(likelihood 두번째 미분항)}} $

 

인데 로지스틱 likelihood의 두번째 미분은 근사적으로

 

$-q^2g(\sigma_i)^2E_i(r)(1-E_i(r))$

 

와 같으므로

 

$l''(r) \approx -\dfrac{ 1 }{ \sigma^2 }- q^2 \displaystyle \sum_{ i=1 }^{ m }{ g(\sigma_i)^2 E_i(r)( 1 - E_i(r) ) } $

 

이다. 여기서 Glickman은 아예

 

$\dfrac{1}{d^2} := q^2 \displaystyle \sum_{i=1}^{m}{ g(\sigma_i)^2 E_i(r)( 1 - E_i(r) ) }$

 

이렇게 정의를 해버린다. 그러면

 

$l''(r) \approx -\left( \dfrac{1}{\sigma^2} + \dfrac{1}{d^2} \right)$

 

이다. 이제 뉴턴-랩슨 식을 완성시켜보자.

 

$ l'(r_{\text{old}}) \approx -\dfrac{r_{\text{old}} - r_{\text{old}}}{\sigma^2} + q \displaystyle \sum_{i=1}^{m}{ g(\sigma_i)(s_i-E_i(r_{\text{old}}) } $

 

이므로 정리하면

 

$ l'(r_{\text{old}}) \approx q \displaystyle \sum_{i=1}^{m}{ g(\sigma_i)(s_i-E_i(r_{\text{old}}) } $

 

이고

 

$l''(r_{\text{old}}) \approx -\left( \dfrac{1}{\sigma^2} + \dfrac{1}{d^2} \right)$

 

이므로 뉴턴-랩슨 식은

 

$ r_{\text{new}} = r_{\text{old}} - \dfrac{ q \displaystyle \sum_{i=1}^{m}{ g(\sigma_i)(s_i-E_i(r_{\text{old}}) } }{ -\left( \dfrac{1}{\sigma^2} + \dfrac{1}{d^2} \right) }$

 

이므로 부호 정리하면

 

$ r' = r + \dfrac{ q }{ \dfrac{1}{\sigma^2} + \dfrac{1}{d^2} } \displaystyle \sum_{i=1}^{m}{ g(\sigma_i)(s_i-E_i) }$

 

이다.

 

여기서 분자는 오차의 가중합(weighted sum)이고 분모는 사전 분포와 관측에 의한 보정이다. 완전 베이지안 같은 느낌의 구조다. 정리하면, 

 

(새로운 평균) = (기존 평균) + (정보의 신뢰도) × (관측 오차)

 

이다.

 

아래에 Glickman의 웹사이트 링크가 있으니 궁금한 사람은 직접 보길 바란다.

 

Welcome to Glicko ratings