Regularized Babington Smith ranking model

경쟁이나 선거에서 1위부터 끝까지 Ranking을 매기는 것은 당연하게 고려되는 문제이다.

“Learing to ranks” 문제는 현재 활발히 연구되는 문제로 reference ranking, 즉 대표적인 하나의 순열을 반환하기 위해 연구되는 문제이다.

즉, ranking을 item의 permutation set의 한 원소라고 생각한다면 reference ranking은 permutation set에서 정의되는 discrete probability distribution에서 가장 큰 확률을 가지는 mode일 것이다.

이러한 관점에서 나는 reference ranking이 데이터를 설명하기에 충분하지 않다고 생각한다. 이유는 mode를 통해 전체 분포를 파악하는 것은 어렵기 때문이다. 예를 들어, 정규분포에서 평균을 안다고 가정해도 전체 분포를 이해할 수는 없음은 명백하다.

본 연구는 ranking에 대한 확률 모형을 구성하고 이를 추정하는 알고리즘을 제안하고 한다. 특히, 쌍대 비교 관점에서 두 아이템의 비교에 하나의 모수를 할당하고 확률 모형을 구성하는 Babington Smith ranking 모형에 집중했다.

그러나, 확률은 1보다 작아야하고 합이 1이여야 한다는 성질을 가지고 있기 때문에 모형에서 정의한 확률에 전체 permutation set에 대한 합 항이 포함되어 있다.

이는 최적화 문제에서 커다란 문제가 된다. 왜냐하면, 단순하게도 gradient 조차 구하기 어렵기 때문이다. 이는 본질적으로 permutation set은 아이템의 factorial 만큼의 원소를 포함하고 있기 때문이다.

이러한 문제를 해결하기 위해 approximated gradient를 계산하는 새로운 방법을 고려했으며 이는 contrastive divergence method의 아이디어에 기반한다.

근사된 gradient를 가지고 gradient descent update를 진행했을 때, 추정해가 가지는 성질을 보일 수 있었으며 근사에 필요한 sampling 개수가 일정 이상 크거나, 크면 클수록 더 좋은 성질을 갖음을 확인했다.

[Working on]