NL-117, Learning to Rank: From Pairwise Approach to Listwise Approach (2007-ICML)

◼ Comment

  • 논문의 시작은 pairwise의 단점을 해결하고자 나타난 것이다.
    • Intro에 pairwise의 몇 가지 문제점이 적혀있다.
  • 그래서 listwise의 접근법의 필요성은 알았으나 어떻게 loss function을 디자인할 것인가? 가 관점이다.
  • 전체적인 플로우를 말하자면
    • 1) query-document 쌍 마다 해당하는 score을 뽑는다.
    • 2) documents에 해당하는 score list를 하나의 permutation probability을 뽑는다.
      • 여기서 permutation의 개념이 나오는데, 이는 주어진 documents의 후보들을 어떻게 순서를 정하냐는 것이다.
      • 즉 d1, d2, d3가 있을 때 (d1,d2,d3)의 probability와 (d1,d3,d2)의 probability가 다른 것이다.
      • 따라서 모든 permutation이 하나의 instance가 되는 것
      • 여기서 permutation probability을 계산할 때, score들을 하나의 함수 태우는데 이 함수는 단조증가여야한다.
      • 논문에서 말하듯이 그냥 exponential을 쓰면 될 거 같고, 결국 그러면 softmax의 개념이 된다.
    • 3) 하지만 이러한 permutation이 너무 많으면 계산이 너무 많기 때문에 top one probability로 대체한다.
      • top one의 개념은 가장 처음 document을 고정하고 이에 따르는 모든 permutation의 probability의 합이다.
    • 4) 이렇게 각 documents에 따른 permutation probability을 예측하고, label에 따른 permutation probability을 예측한다.
      • 이 둘의 distance을 cross entropy로 계산한다.
  • 이 방법이 RankNet보다 성능도 좋고 효율적인 연산이라고 한다.
  • 아무튼 list개념으로 상대적인 관점에서 비교하는 것이기 때문에 ranking이 필요한 방법들에서 한 번 시도해볼만하다고 생각한다.

0. Abstract

  • 이 논문은 learning to rank에 연관이 있으며, 이는 모델 혹은 ranking objects에대한 function을 구성하는 것이다.
  • Learning to rank는 document retrieval, collaborative filtering 그리고 많은 다른 어플리케이션에서 유용하다.
  • learning to rank에 대한 여러 방법들은 제안되어왔고, 이는 학습에서 'instances'로써 object pairs을 취하는 것이다.
    • 우리는 이 논문에서 그들을 pairwise 접근법이라고 부른다.
    • pairwise 접근법은 장점들을 제공함에도 불구하고, 이것은 ranking이 objects의 리스트에서 prediction task인 사실을 무시한다.
  • 논문은 learning to rank가 학습에서 'instances'로 사용되는 objects의 lists에서 listwise 접근법을 적용해야한다고 가정한다.
  • 논문은 새로운 probabilistic 방법을 제안한다. 
  • 구체적으로, 이것은 두 개의 probability 모델들을 소개한다.
    • 학습에서 listwise loss function을 정의하기 위해, 각각 permutation probability와 top one probability을 참조한다.
  • Neural Network and Gradient Descent are then employed as model and algorithm in the learning method. 
  • Informatino retrieval에서 실험 결과들은 제안한 listwise 접근법이 pairwise 접근법보다 낫다는 것을 보여준다.

1. Introduction

  • 많은 어플리케이션의 중심 이슈는 ranking이다.
    • 이것들은 document retrieval, collaborative filtering, expert finding, anti web spam, sentiment analysis, product rating을 포함한다. 
  • 이 논문에서, 우리는 learning to rank을 소개하고 일반성을 잃지 않고 우리는 document retrieval을 예제로 취한다.
  • Learning to rank은 documnet retrieval을 적용할 때, 다음을 따르는 테스크이다.
    • 가정은 document의 collection이 있다는 것이다.
  • retrieval에서 (즉 ranking) query가 주어지면, ranking function은 각 document의 score을 할당하고, documents을 scores의 내림차순으로 정렬한다.
    • ranking order은 query에 관하여 documents의 연관성있는 relevance을 표현한다.
  • 학습에서, queries의 개수들은 제공된다.
    • 각 query는 document들의 완벽한 ranking list와 연동된다.
    • 그런 다음 모델이 training 데이터의 ranking list을 정확하게 예측할 수 있도록 훈련 데이터를 사용하여 ranking function가 만들어진다.
  • 중요성 때문에, learning to rank는 ML 커뮤니티에서 큰 관심을 끌고 있다.
  • 우리가 pairwise 접근법이라 부르는 몇 가지 방법들이 document retrieval에서 성공적으로 적용되어왔다.
    • 이 접근법은 학습때, instances로써 document pairs을 취하고 learning to rank의 문제를 classification의 문제로 형식화하는 것이다.
    • 구체적으로, 학습에서 이것은 ranking lists로부터 documnet pairs을 수집하고 각 document pair에 대한 label을 할당한다. (두 문서들의 연관성을 표현하는)
    • 그것은 그리고 classification model을 labeled data로 학습하고  ranking에서 classification model을 사용한다.
  • The uses of Support Vector Machines (SVM), Boosting, and Neural Network as the classification model lead to the methods of Ranking SVM (Herbrich et al., 1999), RankBoost (Freund et al., 1998), and RankNet (Burges et al., 2005). 
  • pairwise 접근법을 취하는 것에는 장점들이 있다.
    • 첫 째로, 기존의 분류 방법론들을 직접 적용할 수 있다.
    • 둘 째로, document pairs의 학습 인스턴스들은 특정 시나리오에서 쉽게 얻을 수 있다.
  • 그러나, 접근법에는 몇 가지 문제점이 있다.
    • 첫 째로, learning의 objective는 documents의 ranking의 errors의 최소하하는 것 보다는 document pairs의 classification에서의 errors의 최소화하는 것이다. 
    • 둘 째로, document pairs의 숫자가 매우 크기 대문에 학습 process는 계산량이 비싸다. (공감하나, 요즘에는 사실 하드웨어가 워낙 좋아져서 커버 가능하긴 함 ㅎㅎ)
    • 셋 째로, document pairs이 i.i.d로 생성된다는 가정이 너무 강하다. (독립 동일 분포라는 것. 즉 각 pairs이 관련이 없다는 가정을 가지고 간다는... 단점)
    • 넷 째로, 생성된 document pairs의 수는 query to query로부터 크게 다양하고, 이는 더 많은 문서쌍이 있는 queries에 대한 바이어스를 가지게 모델이 학습된다. (사실 이건 response selection에서는 가지는 문제점은 아닐 듯)
  • 이 논문에서는, 우리는 listwise 접근법이라 우리가 부르는 것을 적용하는 것을 제안하고, 이는 document paris 대신에 document lists가 학습에서 인스턴스들로 사용된다.
  • 주요 질문은 어떻게 listwise loss function을 정의하는 것이다.
    • loss function은 ground truth로 주어진 ranking list와 ranking model로부터 출력된 ranking list  사이의 차이를 표현하는 것이다.
    • 우리는 probabilistic method을 제안하여 listwise loss function을 계산한다.
    • 구체적으로, 우리는 ranking function에 의해 할당된 documents의 scores와 labels (사람이 제공한 명시적인 documents의 judgments)을 확률 분포로 변환시킨다.
  • 우리는 loss function으로써 확률 분포 사이의 어떠한 metric도 활용할 수 있다.
  • 우리는 transformation을 위해 2가지 모델 사용을 고려한다.
    • 하나는 permutation probability
    • 다른 하나는 top one probability
  • 우리는 그리고 나서 listwise loss function을 사용하는 rank method을 학습하는 것을 제안한다. (뉴럴 네트워크를 모델과 Gradient Descent 알고리즘) 
  • 우리는 이를 ListNet으로 부른다.
  • 우리는 ListNet을 document retireval에 적용하고 결과들을 기존의 pairwise 방법들과 비교한다. (Ranking SVM, RankBoost, RankNet)
  • 3가지 데이터세트에 대한 결과들은 우리의 방법이 기존것보다 뛰어남을 보여주고, 즉listwise 접근법이 pairwise보다 learning to rank에서 더 나음을 보여준다.
  • 주요 컨트리뷰션은 다음과 같다.
    • (1) proposal of the listwise approach, 
    • (2) formulation of the listwise loss function on the basis of probability models, 
    • (3) development of the ListNet method, 
    • (4) empirical verification of the effectiveness of the approach.
  • The rest of the paper is organized as follows. Section 2 introduces related work.
  • Section 3 gives a general description on the listwise approach to learning to rank. 
  • Probability models for defining a listwise loss function are introduced in Section 4 and the learning method ListNet is explained in Section 5. Section 6 reports our experimental results. 
  • Finally, Section 7 makes conclusions. 

2. Related Work 

2.1. Learning to Rank

  • 순위를 매기는 학습은 기계 학습에서 새롭고 인기있는 주제입니다.
  • 이 백서에서는 pairwise approach 방식이라고하는 순위를 지정하는 방법을 배우는 주요 접근 방식이 있습니다.
  • 다른 접근 방식은 예를 들어를 참조하십시오. 
  • pairwise approach 방식에서 학습 작업은 개체 쌍을 두 가지 범주 (올바른 순위 및 잘못된 순위)로 분류하는 형식으로 지정됩니다.
  • Herbrich (1999)는 분류 모델을 구축하기 위해 접근 방식을 채택하고 SVM 기술을 사용할 것을 제안했습니다.
    • 이 방법을 랭킹 SVM이라고합니다.
  • Freund (1998)는 같은 방식으로 그러나 Boosting을 통해 작업을 수행 할 것을 제안했습니다.
  • Burges (2005)도이 접근법을 채택하여 RankNet이라는 방법을 개발했습니다.
    • 그들은 손실 함수로 Cross Entropy를 사용하고 Neural Network 모델을 훈련하기위한 알고리즘으로 Gradient Descent를 사용했습니다. 
    • 순위를 매기는 학습, 특히 쌍별 접근 방식은 정보 검색에 연속적으로 적용되었습니다.
  • 예를 들어 Joachims (2002)는 문서 검색에 Ranking SVM을 적용했습니다.
  • 그는 사용자의 clicks-through data에서 교육용 문서 쌍을 추출하는 방법을 개발했습니다.
  • Burges (2005)는 RankNet을 대규모 웹 검색에 적용했습니다.
  • Cao (2006)는 손실 함수를 수정하여 문서 검색에 순위 SVM을 적용했습니다.
  • 또한 참조 (Matveeva et al., 2006; Yu, 2005).

2.2. Probability Models on Ranking

  • 통계에서는 객체의 순위 목록을 나타내는 확률 분포와 분포 추정 방법이 제안되었습니다.
  • 예를 들어 Luce (1959)의 작업에 따라 Plackett (1975)는 개체 순위 목록에 확률 분포를 정의했습니다.
  • 그는 확률 분포를 특성화하는 매개 변수를 추가로 도입하고 매개 변수를 추정하는 방법을 개발했습니다.
  • Plackett은 투표 결과 예측에 모델과 방법을 적용했습니다.
  • 이 논문에서는 유사한 확률 분포를 사용합니다.
  • 그러나 모델의 기본 구조 (즉, 매개 변수) 및 기본 사용 (즉, 점수를 확률 분포로 변환)은 Plackett의 것과 다릅니다.

3. Listwise Approach 

  • 이 섹션에서, 우리는 document retrieval을 예제로 learning to rank에 대한 일반적인 설명을 제공한다.
  • 특별히, 우리는 listwise 접근법에 대한 상세한 설명을 한다.
  • 따라오는 설명들에서, 우리는 위첨자로 queries의 index을 가리키고 아래첨자로 특정한 query에 대한 documents의 index을 가리킨다.
  • 학습에서, queries 세트 가 주어진다.
  • 각 query 는 documents list 와 연관된다.
    • 여기서 는 j번째 document을 의미한다.
    • 는 의 사이즈를 의미한다. (즉 document 개수)
  • 게다가, 각 document lists 는 judgments (scores) list인 와 연관되어 있다.
    • 여기서 는 에 대하여 doucment 의 judgment을 가리킨다.
    • 는 에 대한 의 관계 정도를 표현하고 이는 명시적으로 사람들에 의해 매겨진 score일 수 있다.
    • 예를 들어, 는 을 검색하고 검색된 의 클릭 수가 될 수 있다.
    • 와 에 대해 더 높은 클릭률이 관찰 될수록 둘 사이에 더 강한 관련성이 존재한다고 가정합니다.
  • feature vector 는 각 query-document pair 로부터 생성된다.
    •  i = 1, 2, · · · , m; j = 1, 2, · · · , n(i)
  • 각 features list 와 이에 해당하는 scores list 은 instance을 형성한다.
    • 학습 set은 로 표기된다.
  • 그리고나서 우리는 ranking function f을 만든다.
    • 각 feature vector 에 대해 (document 에 해당하는) score f()을 출력한다.
  • feature vectors x(i)에 대해, 우리는 scores list 을 얻는다.
  • learning objective은 학습 데이터에 대해 total losses을 최소화하도록 형성된다.
    • L은 listwise loss function이다.
  • ranking에서, 새로운 query 와 연관된 documents 가 주어졌을 때, 우리는 그들로부터 feature vectors 을 구성하고 학습된 ranking function을 사용해서 documents 에 scores을 할당한다.
    • 마침내, 우리는 documents 을 scores의 내림차순으로 rank을 매긴다.
    • 우리는 위에서 설명한 learning 문제를 learning to rank에 대한 listwise 접근법으로 부른다.
  • 반대로, pairwise 접근법에서, 새로운 학습데이터세트 을 로부터 만든다.
    • 이는 각 feature vector pair 와 가 새로운 instance을 형성한다.
    • 여기서 j != k이고 가 보다 크면 +1, 아니면 -1로 할당한다.
    • 즉, 학습데이터 는 binary classification인 것이다.
    • SVM과 같은 classification model이 생성된다.
  • As explained in Section 1, although the pairwise approach has advantages, it also suffers from drawbacks. 
  • The listwise approach can naturally deal with the problems, which will be made clearer in Section 6.

4. Probability Models

  • 우리는 probability models을 사용해서 listwise loss function을 식 (1)처럼 계산한다.
  • 구체적으로, 우리는 scores의 list을 probability distribution으로 probability models을 사용해서 매핑한다.
  • 그리고 나서, 두 probability distributions의 어떠한 metric으로 loss function을 취할 수 있다.
    • 두 모델들은 permutation probability and top one probability이다.
  • 쉽게 생각해서 다음과 같은 과정이 필요하다., 
    • 1. document + query 쌍별로 각 features을 뽑고 
    • 2. features을 scores의 점수를 뽑고
      • 근데 여기서, features끼리 연관될 필요는 없나?
    • 3. 확률 분포로 변환
      • score list --> score 확률 분포
      • label list --> label 확률 분포
      • 여기서 label은 document 클릭 수와 같은 것이 가능
      • 확률 분포로 바꾸는 것은 이제 밑에서 다룸. 
    • 4. 두 확률 분포 사이를 loss 식으로 게산
      • 근데 3,4을 한꺼번에 해서 cross entropy을 쓰는 것이 하나의 방법 같은데?

4.1. Permutation Probability

  • 순위를 지정할 objects의 set은 숫자들 1, 2, ..., n으로 식별된다고 가정한다.
  • objects에 대한 permutation π은 그 스스로 {1, 2, ..., n}으로부터 bijection(이등분)으로 정의된다.
  • 우리는 permutation π=<π(1), π(2), ..., π(n)>으로 쓰고
    • 여기서 π(j)는 permutation에서 position j에 해당하는 object을 가리킨다.
    • 즉 document을 뒤죽박죽 섞은 뒤, π(2)는 2번째에 있는 document?
  • n개의 objects의 모든 가능한 permutation은 으로 정의된다.
  • ranking function은 n개의 objects에 scores을 할당한다고 가정한다.
    • 우리는 scores의 list을 로 정의하고 여기서 sj는 j번째 object의 score을 의미한다.
  • 이후에, 우리는 때때로 ranking function와 ranking function에 의해 주어진 scores list을 상호 교환 가능하게 만듭니다.
  • 우리는 여기에서 ranking function을 사용한 ranking lists(permutations)의 예측에서 uncertainty가 있다고 가정한다.
    • 즉, 어떠한 permuation도 가능하다고 가정하지만, 다른 permutations은 ranking function을 기반으로한 다른 likelihood을 가질 수도 있다.
  • 우리는 permutation probability가 ranking function가 주어졌을 때, permutation (ranking list)의 likelihood을 표현하는 것에 대해 원하는 속성을 가지게 정의한다.
    • 즉 document가 어떻게 순서를 가져도 (permutation이 어떻든) ranking을 매기는 것에 영향을 미치면 안된다는 것? 
  • Definition 1 
    • 가 n개의 objects에 대한 permutation이고 는 단조증가 function라라고 가정한다.
    • scores list s가 주어졌을 때, permutation  확률은 다음과 같이 정의된다.
    • Then, the probability of permutation π given the list of scores s is defined as
    • where  is the score of object at position j of permutation π. 
  • 이제 우리는 3개의 objects {1, 2, 3}와 이것이 가지는 scores s=(s1, s2, s3)에 대한 예제를 고려하자.
  • permutations의 확률 =<1,2,3>와 '=<3,2,1>들은 다음과 같이 계산된다.
  • Lemma 2 
    • permutation probabilities  ()은 permutation의 set에 대한 probability distribution을 형성한다.
    • 즉, 각 에 대해, Ps(π) > 0이고 이다.
    • 즉, 각 query-document에 대한 score가 있을 것이다.
    • documents에 대한 score list을 permutation이 () 각각 있을 텐데, 하나의 permutation당 permutation probability가 위 정의1처럼 계산된다.
    • 이 확률들을 모든 에 대해 더하면 1이 되도록 주장하는 것이다.
  • Theorem 3 
    • 두 개의 permutations 와 가 주어졌을 때, 만약
    • (1) , , p < q
    • (2) , r != p, q
    • (3) 
    • 만약 (1), (2), (3)을 만족하면  이다.
    • 쉽게 말하면 두 개의 permutation이 있는데
    • 하나는 p1=<1, 2, 3, 4, 5>이고 하나는 p2=<1, 4, 3, 2, 5>이다.
      • 즉 2와 4만 자리가 바뀐 것이다.
      • 이 때, document 2의 score가 document 4의 score보다 높다면,
      • permutation p1의 확률이 p2의 확률 보다 높다는 것이다.
  • Theorem 4 
    • n개의 objects에 대해 만약 s1 > s2 > ... > sn이면
    • Ps(<1,2,...,n>)이 가장 높은 permutation 확률을 가지고
    • Ps(<n,n-1,...,1>)이 가장 낮은 permutation 확률을 가진다.
    • 사실 정리 3하고 같은 말임.
  • 즉 정의 1처럼 처럼 설계를 하면 Lemma와 Theorem을 만족한다는 것이고 정리4는 증명이 쉽고, Lemma2와 정리3은 Appendix에 증명되어 있다.
  • 증명 3은 ranking function을 기반으로 어떠한 ranking list에 대해, 만약 우리가 점수가 높은 object의 position과 점수가 낮은 objection의 position을 바꾼다면, 우리는 더 낮은 permutation probability을 가지는 ranking list을 얻게된다는 것이다.
  • 증명 4는 ranking function이 주어졌을 때, ranking function을 기반으로 정렬된 objects lists가 가장 높은 permutation probability을 가지는 반면, inver roder로 정렬된 objects의 lists들이 가장 낮은 permutation probability을 가진다는 것이다. 
  • 즉 이말은, 모든 permutations들이 가능하다고 가정할지라도, ranking function을 사용해서 정렬된 permutation이 가장 발생할 확률이 높다.
    • 사실 직관적으로 당연한 말인데, 이를 엄밀히 증명한 것 같다.
    • 즉 각 documents에 대한 scores이 높은 순으로 정렬된 permutation이 최종의 ranking list가 된다는 말.
  • scores에 대한 두 개의 lists가 주어졌을 때, 우리는 그들로부터 두 permutation probability distributions을 계산할 수 있다.
    • 그리고 나서 listwise loss fucntion으로써 두 distributions 사이의 distance을 계산한다.
  • 그러나 permuations의 수가 n!이기 때문에, 그러나 calculation이 어려울 수 있다.
  • 학습에서 아마 이런 문제 상황을 말한 것 같다.
    • <d1, d2, d3> 식으로 document가 주어진다.
    • <l1, l2, l3>식의 클릭수가 주어졌다고 하자. 즉 이것이 label score
    • 그렇다면, <f1, f2, f3>의 feature vector을 뽑고
    • <s1, s2, s3>의 score을 뽑는다.
    • 이를 이용해 <s1,s2,s3>의 permutation에 대한 permutation probability을 계산할 수 있다.
    • 그리고 정답으로 주어진 <l1,l2,l3>로 permutation probability을 계산할 수 있다.
    • 이 구해진 두 개의 permutation probability의 distance을 listwise loss로 사용한다.
    • 하지만, 이 방식은 데이터가 <d1,d2,d3>가 주어졌을 때, 모든 permutation으로 학습할 수 있다.
    • 즉 3!=6개의 순서쌍에 대해 계산할 수 있다는 것이고 이렇게 되면 계산이 어렵다는 말
  • 이 문제를 해결하기 위해, 우리는 top one probability을 사용을 고려한다.

4.2. Top One Probability

  • object의 top one probability은 모든 objects의 scores가 주어졌을 때, 그것의 probability가 top에 랭크되는 것을 표현한다.
  • Definition 5 
    • object j의 top one probability는 다음과 같이 정의된다.

    • Ps(π)는 s가 (score) 주어졌을 때, π의 permutation probability 이다.
  • 이것은, object j의 top one probability는 object j가 top에 랭크되었을 때의 permutations들의 permutation probabilities의 합을 의미한다.
  • n top one probabilities을 계산하기 위해, 우리는 여전히 n! permutation probabilites을 계산해야한다고 할 수 있다.
  • 정리 6은 우리가 top one probability을 다른 방법으로 효율적으로 계산할 수 있음을 보여준다.
  • Theorem 6 
    • For top one probability Ps(j), we have 
    • where sj is the score of object j (j = 1, 2, ..., n.)
    • 즉, 정의 1로 을 계산하는 것에서, top 랭크를 j로 고정시키면 이와 같이 계산을 효율적으로 할 수 있다는 것이다.
  • Lemma 7 
    • Top one probabilities Ps(j) (j = 1, 2, ..., n)은 n objects의 set에 대한 probability distribution을 형성한다.
    • 즉, top 랭크가 1 부터 n까지 각각이 되었을 때 나오는 probability distribution들이 n objects의 set에 대한 확률들이라는 것?
  • Theorem 8 
    • Given any two objects j and k, if sj > sk, (j != k), j, k = 1, 2, ..., n, then Ps(j) > Ps(k).
  • 정리 6의 증명은 appendix에서 보여준다.
  • Lemma 7과 정리 8은 증명하기 쉽다.
    • top one probability의 사용과 함께, 두 개의 scores의 lists가 주어졌을 때, 우리는 어떠한 metric을 사용해서 distance (listwise loss function)을 표현한다.
      • 예를 들어, 우리가 CrossEntropy을 metric으로 사용했을 때, listwise loss function은 다음과 같다.
        • 위에서 나는 distance라길래, MSE나 그런걸 생각했는데 대표적으로 CrossEntropy을 사용하나보다.
        • 즉, 하나의 permutation이 instance가 되어, 하나의 숫자값 (permutation probability)을 떨구고 이와 label socres의 permutation probability의 숫자값이 새로운 label이 되어 cross-entropy로 비교한다.

      5. Learning Method: ListNet

      • 우리는 top one probability을 기반으로 listwise loss function을 optimizing을 위한 새로운 학습 방법을 적용한다.
        • Neural Network을 모델과 Gradient Descent optimization algorithm을 사용
      • 우리는 이 방법을 ListNet이라고 한다.
      • 다시, 우리는 document retrieval을 예제로 들어보자.
      • 우리는 뉴럴 네트워크 모델 을 기반으로 ranking function 을 표기한다.
      • feature vector 가 주어졌을 때, 는 점수를 할당한다.
      • 간단하게 하기위해, 우리는 정의 1에서의 φ을 exponential function으로 정의한다.
        • 우리는 top one probability을 정리 6에 의해 다음과 같이 다시 표현한다.
      • query 가 주어졌을 때, ranking function 은 score list 을 생성한다.
      • 그리고나서, document 의 top one probability는 다음과 같이 계산된다.
      • Cross Entropy을 metric으로 하여, query 에 대한 loss는 다음과 같이 된다.
      • 약간의 파생으로 (appendix 참고), 우리는 gradient 을 parameter 에 대해 다음과 같이 얻을 수 있다.
      • 식 3은 Gradient Descent을 사용한 것이다.
      • 알고리즘 1은 Listnet의 학습 알고리즘을 보여준다.
      • ListNet은 RankNet과 유사하다.
        • 유일한 주요 차이점은 전자(ListNet)는 document lists을 인스턴스로 사용하고 후자(RankNet)는 document pairs을 인스턴스로 사용한다는 점입니다.
        • the former utilizes a listwise loss function while the latter utilizes a pairwise loss function. 
      • 흥미롭게도, 각 query에 대해 오직 2개의 documents가 있으면 (즉 =2), ListNet의 listwise loss function은 RankNnet의 pairwise loss function과 동일하게 된다.
      • RankNet의 time complexity은 이고 여기서 m은 학습 queries의 수이고 은 query당 documents의 최대 수이다.
      • 반대로 ListNet의 time complexity은 이다.
      • 그래서 ListNet은 RankNet보다 효율적이다.

      6. Experiments

      • Ranking SVM (Herbrich et al., 1999), and RankBoost (Freund et al., 1998)을 3가지 데이터세트에 대해 학습한 것이 비교군
      • ListNet은 top one probability model을 기반으로 실험

      7. Conclusions

      • 이 논문에서, 우리는 learning to rank에대한 새로운 접근법인 listwise 접근법을 제안한다.
      • 우리는 이것이 전통적인 pairwise 접근법보다 나음을 주장한다.
      • listwise 접근법에서, instances로써 object pairs을 사용하는 대신에 우리는 object의 list을 instances로써 학습에 사용한다.
      • listwise 접근법의 key issue는 listwise loss function을 정의하는 것이다.
      • 이 논문에서, 우리는 probabilistic 방법을 제안하여 이를 해결한다.
      • 구체적으로, 우리는 probability models으로 다음을 사용한다.
        • permutation probability and top one probability 
        • 이것으로 ranking scores을 probability distributions으로 transform한다.
      • 우리는 그리고 나서, 뉴럴 네트워크와 gradient descent 기반의 학습 방식을 적용한다.
      • Experimental results with three data sets show that the method works better than the existing pairwise methods such as RankNet, Ranking SVM, and RankBoost, suggesting that it is better to take the listwise approach to learning to rank. 
      • 추후 연구에서는 다른 cross entropy외에 objective function의 성능과 linear 뉴럴 네트워크 대신에 다른 ranking model의 성능을 탐색할 것이다.
      • 우리는 또한 listwise loss function과 IR에서 사용했던 NDCG와 MAP와 같은 성능과의 관계를 조사할 것이다.

      Reference

      댓글

      댓글 쓰기