[Paper Review] Efficient Computation of Rankings from Pairwise Comparisons

논문링크
https://jmlr.org/papers/volume24/22-1086/22-1086.pdf

 

다음 논문은 Bradly-Terry Model을 이용해서 Pairwise comparisons를 통해 여러 Class 간의 순위를 매기는 것을 이용해 우선순위를 최대 우도 추정법을 이용하여 빠르게 수렴시키는 방법에 대한 논문이며, 이에 대해 리뷰하려고 한다.

수식유도에 대해 설명을 하고 증명은 생략한다.

 

Introduction

---

우리는 각 개인 $ i $에게 수치 점수 $ \pi_i $를 할당하고 $ i $가 $ j $를 이길 확률 $p_{ij}$로 가정하며, 가장 인기 있는 Logistic function을 사용한다(확률로 표현하기 좋은 함수). $p_{ij}$를 다음과 같이 사용한다.  여기서 $\pi_i$는 $i$의 Strength라고 부른다.

$$ p_{ij} = \frac{\pi_i}{\pi_i+\pi_j} $$

N개의 팀 사이의 Pairwise competitions의 결과가 주어진다면, 결과를 바탕으로 Strength를 직접 계산할 수 있다. 일반적으로 최대 우도 추정(Maximum Likelihood Estimation, MLE)을 사용한다. $ w_{ij} $를 $ i $가 $ j $를 이긴 총횟수로 정의하거나, $ i $와 $ j $가 경쟁한 적이 없으면 0으로 정의한다. Strength의 최대 우도 값은 다음 방정식으로 수렴할 때까지 반복한다.

다음에 나오는 방정식 Zermelo에 의해 소개되고 Bradley와 Terry에 의해 다시 바뀐 Bradley-Terry Model이다.

$$ \pi^\prime_i = \frac{\sum^N_{j=1}w_{ij}}{\sum^N_{j=1}(w_{ij}+w_{ji})/(\pi_i+\pi_j)} $$

다음 방정식(Zermelo)은 수렴에 도달할 때까지 반복하며, 이 방정식은 수렴하는데 느리다고 알려져 있다. 이 논문에서는 다음 방정식 대신 빠르게 수렴하는 방법에 대한 연구를 진행한다. 

$$ \pi^\prime_i = \frac{\sum^N_{j=1}w_{ij}\pi_j/(\pi_i+\pi_j)} {\sum^N_{j=1}w_{ji}/(\pi_i+\pi_j)} $$

이 방정식은 이전의 수식보다 빠르게 수렴하는 것을 보여주며, 특별한 케이스에는 100배 이상 빠르다. 이 방정식 또한 Zermelo의 방정식과 같이 구현하기 쉽다.

이후 논문에서는 Zermelo의 원래 알고리즘과 제안된 알고리즘에 대해 설명하고 유도한다. 다음은 두 알고리즘이 수렴한다는 것을 증명하며, 수렴속도를 비교한다. 하지만, 증명에 대한 내용은 수식이 많으므로 생략한다.

 

Iterative Algorithms and the Bradley-Terry Model

---

이번 섹션에서는 이전에 제시되었던 Zermelo Algorithm과 논문에서 제시하는 알고리즘에 대해 유도하는 과정에 대해 설명한다. 여기서는 무승부에 대해 허용하지 않는다. 각 변수에 대한 설명은 다음과 같다. 선수 $ i $가 선수 $ j $를 이길 확률을 $ p_{ij} $라고 하며, 선수 $ i $의 능력을 $ \pi_i $라고 하며, 더 높은 값이 더 나은 선수이다.

승리 확률 $ p_{ij} $는 모든 $ \pi_i $를 임의의 상수로 곱해도 변하지 않는 것을 알아야 한다. (확률은 상대적이기에 똑같이 상수를 곱해도 상대적으로 동일하기 때문이다.) 그래서 논문에서는 기하 평균을 1이 되도록 고정하며 이는 $ \prod_i\pi_i = 1 $로 설정하는 것과 동일하다. 

 

Zermelo's Algorithm

토너먼트가 팀 간 총 $ M $ 게임으로 구성한다고 가정하고  선수 $ i $가 선수 $ j $를 이긴 횟수를 $ w_{ij} $라고 한다. 이 데이터를 바탕으로 Strength $ \pi_i $의 최대 우도 추정(MLE)이 가능하다. 일단 우도를 구하는 방정식으로부터 최대 우도 추정을 구하는 식을 유도한다.(각각 행렬 W = $[w_{ij}]$, 벡터 $ \pi $ = $ [\pi_i] $를 의미한다.)

관측된 게임의 우도는 다음과 같다.

$$ P(W|\pi) =\Pi_{ij}p_{ij}^{w_{ij}} =\Pi_{ij}(\frac{\pi_i}{\pi_i+\pi_j})^{w_{ij}} $$

따라서 $ \text {log} $우도는 다음과 같다.

$$ \text {log}P(W|\pi) = \sum_{ij}w_{ij}\text{log}\frac{\pi_i}{\pi_i+\pi_j} = \sum_{ij}w_{ij}\text{log}\pi_i-\sum_{ij}w_{ij}\text{log}(\pi_i+\pi_j).  $$

$ \pi_i $에 대해 미분하고 결과를 0으로 설정하면 다음을 얻는다. 

여기서 미분을 하고 $ \pi_i $에 대해 미분하는 이유는 $ \pi_i $에 대한 극값을 찾으면 그 값이 $ \pi_i $가 최대를 갖는 값이며, 최대 우도값이 된다.

$$  \frac{1}{\pi_i}\sum_jw_{ij}-\sum_j\frac{w_{ij}+w_{ji}}{\pi_i+\pi_j}=0  $$

이는 다음과 같이 재배열될 수 있다.

$$ \pi_i = \frac{\sum_jw_{ij}}{\sum_j(w_{ij}+w_{ji})/(\pi_i+\pi_j)}. $$

이 방정식은 닫힌 형태의 해를 갖지 않는다(방정식으로 정확한 해를 찾을 수 없음). 하지만 반복을 통해 수치를 수렴할 수 있다. $\pi_i $에 대해 음수가 아닌 값(랜덤 값)을 선택하고 그리도 다음과 같은 새로운 값 $ \pi^\prime_i $를 계산한다.

$$ \pi^\prime_i = \frac{\sum_jw_{ij}}{\sum_j(w_{ij}+w_{ji})/(\pi_i+\pi_j)}. $$ 

이 과정을 반복하면, $ \text {log} $우도의 최댓값으로 수렴한다. 따라서 Strength $ \pi_i $에 대해 추정치를 얻을 수 있으며 이 값을 정렬하여 선수들의 순위를 매기거나 평가할 수 있게 된다.

 

An Alternative Algorithm

Bradley-Terry 모델에 대해 최대 우도 추정치(MLE)를 계산하는 것은 단순한 문제이지만, 속도가 느리므로 이에 대해 빠른 알고리즘을 찾기 위해 노력해 왔다. 이 중 일부는 복잡하지만, 논문에서는 매우 효율적인 접근 방식을 제안한다.

$$ \frac{1}{\pi_i}\sum_jw_{ij}-\sum_j\frac{w_{ij}+w_{ji}}{\pi_i+\pi_j}=0 $$

위의 식을 다르게 그룹화하면 다음과 같이 작성할 수 있다.

$$ \frac{1}{\pi_i}\sum_jw_{ij}\frac{\pi_j}{\pi_i+\pi_j} - \sum_j\frac{w_{ji}}{\pi_i+\pi_j} = 0, $$

다시 배열하면

$$ \pi^\prime_i = \frac{\sum_jw_{ij}\pi_j/(\pi_i+\pi_j)}{\sum_jw_{ji}/(\pi_i+\pi_j)} $$

이는 Bradley-Terry 모델에 대한 다른 반복 알고리즘을 제안한다. 다시 적절한 시작 값(랜덤 값)을 선택한다, 그리고 우리는 수렴할 때까지 다음 형태를 반복한다.

이 알고리즘을 통해 이전에 제시한 Zermelo 알고리즘보다 "매우" 빠르게 최대 우도에 수렴하는 것이다. 

 

Conclusion

---

$ \alpha $의 값에 따라 알고리즘이 정해진다.

다음은 논문에서 제시하는 반복 알고리즘의 일반식이고 $\alpha $가 1이면 Zermelo알고리즘이며 $ \alpha $가 0이면 논문에서 제시하는 알고리즘이다.

$ \alpha $값에 따른 수렴속도

$ \alpha $의 값에 따라 수렴속도를 보여주고 있으며 0일 때 매우 빠르게 수렴하고 있는 것을 볼 수 있다.

 

이 논문을 통해 BT 모델의 수렴속도가 매우 빠른 식에 대해 알 수 있었다.