본 논문은 웹 검색에서 사용자의 검색 기록과 웹 문서간의 연관 관계를 동시에 이용하여 적합한 랭킹 함수를 학습하는 방법을 소개한다. 제안하는 방법은 그래프 기반의 준지도 학습(semi supervised learning) 기법을 선호도 학습(preference learning) 에 적용한 기계학습 알고리즘으로, 그래프의 가중치 행렬 (weight matrix)을 직접적으로 계산할 필요가 없는 matrix-free 알고리즘을 고안하여 대규모 데이터를 다룰 수 있도록 하였다. 또한 새로운 검색 기록들이 추가될 때마다 이미 학습된 랭킹 함수를 효율적으로 업데이트할 수 있도록 점진적 (incremental) 학습 알고리즘을 개발하였다. Microsoft Research Asia에서 약 400만개 질의어에 대해 수집한 MSN Live Search의 검색 기록 데이터에 본 방법을 적용한 결과, 주어진 질의어에 적합함에도 Live Search에서 순위가 낮게 책정되었던 웹 페이지들의 검색 순위를 크게 향상시킴으로써(평균 11-20위 ${ ightarrow}$ 3-12위로 향상) 더욱 정확한 검색 결과를 산출하였으며, 이를 위해 질의어당 실시간으로 소요된 처리 시간은 불과 1.4 밀리초였다.
In this paper, we present a novel method for learning to rank, which is capable of semi-supervised learning by utilizing both click-through logs and the similarities between web pages simultaneously. To achieve web-scale semi-supervised learning, we develop a matrix-free algorithm that extracts latent features from a given set of web pages, where the huge similarity matrix of the web pages is not needed. Moreover, we present an incremental algorithm for our semi-supervised preference learning framework. Experiments on the Microsoft Live Search query log data show that our method effectively improves the ranks of relevant web pages of a given query, which are underestimated by Microsoft Live Search.
