Reciprocal rank fusion outperforms condorcet and individual rank learning methods

1. Reciprocal rank fusion

비지도 학습에서 정보 검색(IR) 방법들의 결과를 결합하기 위한 방법이다.

RRF score

전체 문서들의 집합을 D, 순위 결과 집합을 R이라고 할 때
$RRFscore(d \in D) = \displaystyle\sum_{r\in R}{{1}\over{k+r(d)}}$
여기서 k = 60이라는 고정된 값으로 설정한다.

해당 식의 목표는 단 하나의 시스템에서만 높은 것이 아닌 여러 시스템에서 상위에 등장하는 문서가 가장 큰 값을 갖도록 하는 것이 목적이다. 단, 이때 하위 랭크의 문서도 무시되지 않도록 해야한다.

따라서 순위가 작을수록(높을수록) 커지도록 역수를 사용하며, 이때 등수간 너무 큰 차이가 발생하지 않도록 유리함수를 사용한다. 동시에 k값을 활용해 한 시스템에서의 결과가 전체 결과를 지배하는 것을 막는다.

최종적으로 각 시스템을 동등하게 단순 합으로 계산하여 최종 순위를 매긴다.

CMNZscore

Cordorcet Fuse는 두 문서 쌍 $(d_1, d_2)$에 대해서 $r(d_1) < r(d_2)$라는 쌍대 관계(pairwise relation)를 기준으로 문서를 정렬한다.

CombMNZ score: 각 순위 r에 대해 대응하는 점수 $s_r: D \rightarrow \mathbb R$와 cutoff rank c에 따라
$CMNZscore(d \in D) = |\{r \in R | r(d) \le c \}| \cdot \displaystyle\sum_{\{r|r(d)\le c\}}s_r(d)$
즉, (해당 문서를 좋게 본 시스템의 수) * (점수의 합) 으로 계산한다.

비교

훨씬 단순해보이는 RRF가 모든 경우에서 Condorcet Fuse보다 더 높은 점수를 보였고, 한 경우를 제외하곤 CombMNZ보다도 더 높았다. 또한 RRF는 인간이 직접 개입한 경우를 제외하고 개별 ranking들보다 더 좋은 성능을 보였다.

2.Discussion

단순히 RRF가 성능이 좋았다를 넘어 voting 알고리즘도 없고, 전역적인 정보를 저장할 필요도 없고, 시스템마다 순위들이 계산되어 누적되면 되기에 순위 결과를 저장할 필요도 없다.

RRF가 가장 성능이 좋았던 이유는 한 두개의 특정 시스템이 특정 문서를 높게 랭킹되는 것만으로도 순위가 크게 상승되기에 다양성이 보장되기 때문이라고 한다.

결론

최근에 사용하는 reranking들에 비해 성능은 떨어지지만 학습따윈 존재하지 않는 정말 간단한 휴리스틱 알고리즘이기에 경량화가 필요한 경우 활용할 수 있다.