[LTR] Learning to Rank, Pointwise, Pairwise, Listwise ranking

Decision Focused learning:  Through the lens of learning to Rank 리뷰를 준비하던 중 LTR에 관한 내용을 잘 몰라서 ..ㅎㅎ 따로 정리한 내용이다. 읽다보니 추천시스템에서 사용되는 기술답게 많은 공통점이 있는걸 발견해서 관련 개념을 기반으로 이해하니 조금 이해가 수월했다. 추가적으로 현재 읽고 있는 논문이 LTR의 basic한 방법론들을 DFL에 적용한 논문인데 기존 추천시스템 분야에서 사용되던 기술들을 잘 적용한다면 어떨까..? 하는 생각중이다. 사설은 여기까지 하고 이제 글을 정리해보자. 

https://otzslayer.github.io/ml/2022/02/13/learning-to-rank.html#approaches-to-ltr 을 기반으로 작성하였습니다. 

Learning To Rank

Classificiation이나 Regression과 다르게 순위를 학습하는 모델을 말한다. LTR은 추천시스템, Search engine, Email search 등 파일이나 문서를 정렬하는데 주로 사용되어왔다. 

 

LTR에서 흔히 나오는 용어가 Query, Item(document)이다. 

우선 Query의 경우 사용자의 검색어를 보통 의미한다. 위의 Search engine을 예시로 들면 'Learning to Rank' 등의 검색어가 될 것이다. 

Item 혹은 document는 Ranking이 매겨지는 Query에 관한 output, 정답을 의미한다.   

정리하면 Query에 맞게 Item을 잘 정렬하는 것이 LTR이다. 

이때 Item의 ranking 점수는 Score로 매겨지게 되며, 이에 따라 Implicit data 혹은 Explicit data로 구분 가능할 것이다(이때 Explicit은 직접 표현한 data, 좋아요 개수, rating 점수, 혹은 클릭율등이 될 수 있으며, 사용자 혹은 실험자에 따라 달라진다). LTR의 대표적인 세가지 접근법은 Pointwise, Pairwise, Listwise가 있으며 하나씩 확인해보자. 

출처: ritvikmath 유튜브 채널(아래 첨부문서 링크 확인)

Pointwise 

pointwise 방법은 매우 단순한 접근법으로, 간단히 말해 (query, document) 쌍에 맞는 Rank 점수를 예측하는 Regression model을 만든다고 생각하면 된다. 아래 그림의 예시처럼 Scoring를 예측하는 f(q,d) = s 를 잘 학습시키는 것이 목적이다.  

출처: ritvikmath 유튜브 채널(아래 첨부문서 링크 확인)

이 방법의 경우 장단점은 아래와 같다. 

+) 다른 분야에서 많이 사용하고 있는 ML 기법, 모델들을 적용가능하다.

-) Query와 document간의 관계가 무시된다 

-) Label is not explicit enough 

Pairwise

Pairwise의 경우 각 document 중 어느 것이 순서, rank가 높은지를 학습하는 모델이다. 

아래의 그림과 같이 Query하나에 pair, 즉 두 개의 document가 할당되는 (Q, d1, d2) 형태이다. 

이때 d1의 rank가 d2에 비해 더 우선된다면 1을 뱉어내는 형태이다. 결국은 Binary Classification 문제로 할당이 가능하다. 

가장 대표적인 알고리즘인 RankNET [1] 에 기반을 두고 설명하면 아래와 같다.

수식적으로 풀어보면 sigmoid function을 이용해서 rank가 높은 가능성을 최대화하는 형태로 학습이 가능하다. 

출처: ritvikmath 유튜브 채널(아래 첨부문서 링크 확인)

즉 수식으로 보면 아래와 같다. i의 스코어링 함수가 j보다 크다면(연관성이 높다, rank의 순위나 높다) P(i>j)는 1에 가까운 값이 된다. 

y을 실제 label이라고 하면 Loss function은 다음과 같이 정의된다(Loss 자체로는 BPR, WARP, CLiMF 등이 존재)

HyeJinLee : [논문 리뷰] From RankNet to LambdaRank to LambdaMART: An Overview

장단점은 아래와 같다.

+) 모델이 순위를 학습한다, pair of document를 직접 학습한다

+) explicit label이 없더라도 두 item의 비교를 통해 학습가능

-) Still not fully inform ->모든 순위를, 실제 순위를 최적화 하지 않는다

Listwise

Listwise는 Pairwise에서 확장하여, 전체 목록의 순위를 최적화하는 방법이다. 

데이처의 경우 각 쿼리에 매칭된 document 목록 전체를 사용한다. 대표적으로 LambdaRank[2]를 사용하며, 이는 ranking loss 중 하나인 Normalized Discounted Cumulative Gain (NDCG)를 직접 최적화한다. 

NDGG는 불연속하여 그라디언트를 저으이할 수 없지만, LamdaRank는 이를 최적화할 수 있는 그라디언트를 설계하여 사용한다. ListMLE[3], ListNet[4] 등 기타 다양한 Listwise 기법등이 있다. 

HyeJinLee : [논문 리뷰] From RankNet to LambdaRank to LambdaMART: An Overview

 

+) 모델이 복잡한만큼 좋은 성능을 보인다

-) 매우 복잡하고, 제한된 데이터를 이용해 많은 특성을 모델이 잘 학습해야함

-) Computation cost가 큼

일부에서는 List-wise를 base로 하되, 진짜 모든 List를 최적화하려들지말고, 적절한 Top-N 개의 Items를 최적화시키려는 시도를 하기도 함

 

Metric: MAP, NDGC

LTR 모델을 평가할 때 주로 사용하는 metric은 MAP와 NDCG로 MAP는 문서의 연관성 여부(binary)를 NDCG는 그 연관성 정도까지 고려한다. 

Mean Avergae Precision(MAP)

MAP는 결국 각 Query에 관한 Precision score의 평균을 의미한다. 

각각의 쿼리에 관해, 쿼리 q가 주어졌을 때 해당하는 아이템 k개의 관한 P@k는 아래와 같다.

정밀도는 True라고 내가 분류한 것들 중 실제 True인 비율을 의미함으로 아래의 예시에서 사용자가 선호한 초록색 item이 나타낼때마다 그때까지의 정밀도를 계산한다. 이후 이들을 모두 더한 후 선호한다고 한 개수로 나눈다. 

출처: https://kgw7401.tistory.com/90

이후 최종적으로 query의 수로 나누어 Mean Average Precision at K를 구한다. 

당연히 순서에 매우 민감한 metric 중 하나이다. 

Normalized Discounted Cumulative Gain (NDCG)

NDCG의 경우 DCG의 normailzed된 값이다. 

Discounted cumulative gain은 간단히 설명하면 추천결과 중 하위에 추천된 값에 더 적은 gain을 주어 상단에 가중을 주는 방식을 의미하며, normalized ~는  이상적인 DGC인 IDGC(rel 순서대로 추천되었을 때 DCG)로 구한 DCG를 나누는 것이다. 자세한건 아래의 수식을 보자(rel은 얼마나 연관되어있는가, label이랑 같음 클 수록 좋음)

 

이때 log2(i+1)로 나누는 것은 위에서 말한것처럼 gain을 상위 랭크에 더 주기 위함이다. 

 

결국은 relevances는 높을 수록 점수를 주되, ranking에 따라 gain을 주자(잘 정렬된정도)의 식이다. 아래 그림을 보자. 

참고 자료

[1]Burges, Chris, et al. “Learning to rank using gradient descent.” Proceedings of the 22nd international conference on Machine learning. 2005.

[2] Burges, Christopher JC. “From ranknet to lambdarank to lambdamart: An overview.” Learning 11.23-581 (2010): 81.

[3] Lan, Yanyan, et al. “Position-Aware ListMLE: A Sequential Learning Process for Ranking.” UAI. 2014.
[4] Cao, Zhe, et al. “Learning to rank: from pairwise approach to listwise approach.” Proceedings of the 24th international conference on Machine learning. 2007.

[5]ritvikmath 유튜브 채널 https://www.youtube.com/watch?v=YroewVVp7SM  , https://www.youtube.com/watch?v=yKwTAcsV8K8 https://www.youtube.com/watch?v=BvRMAgx0mvA 

[6]  https://paperswithcode.com/task/learning-to-rank/latest

[7] https://otzslayer.github.io/ml/2022/02/13/learning-to-rank.html#approaches-to-ltr

[8] https://likegirl.tistory.com/13

[9] Triplet loss https://wwiiiii.tistory.com/19

[10] NDCG https://modulabs.co.kr/blog/information-retrieval-map-ndcg/