기술 요약: 데이터셋 분류 체계 전반에 걸친 추천 시스템을 위한 Bradley-Terry 랭킹

문제 정의

추천 알고리즘의 순위를 매기는 것은 매우 복잡한 과제인데, 모델의 성능이 희소성(sparsity), 순차적 구조(sequential structure), 규모(scale)를 포함한 데이터셋 특성에 매우 민감하기 때문이다. 결과적으로, 특정 알고리즘은 특정 데이터셋 하위 집합에서는 뛰어난 성능을 보이지만 다른 곳에서는 저조한 성능을 보일 수 있다. 이러한 가변성은 실무자가 직접적이고 철저한 비교라는 높은 비용을 치르지 않고도 특정 작업에 가장 적합한 방법을 선택하는 것을 어렵게 만든다.

전통적인 평가 방법은 종종 성능 지표의 단순 집계(예: 벤치마크 전체의 NDCG 평균)에 의존한다. 저자들은 이러한 접근 방식이 서로 다른 데이터셋에서 상대방(opponent)의 역량 차이를 고려하지 못하며, 누락된 데이터나 데이터셋 특유의 맥락을 처리하는 원칙적인 방법을 제공하지 못하기 때문에 오해의 소지가 있거나 불안정한 순위를 생성할 수 있다고 주장한다. 따라서 데이터셋을 고려한 공정한 알고리즘 비교 및 선택을 가능하게 하는 방법론에 대한 절실한 필요성이 존재한다.

방법론

본 논문은 Bradley-Terry (BT) 모델과 그 확장 모델을 기반으로 한 데이터 주도형 랭킹 프레임워크를 제안한다. 핵심 접근 방식은 추천 알고리즘의 평가를 다양한 데이터셋에서 알고리즘들이 서로 "경쟁"하는 토너먼트로 간주하는 것이다.

1. 쌍체 비교 프레임워크 (Pairwise Comparison Framework)

원시 지표 점수를 집계하는 대신, 저자들은 알고리즘 $i$가 알고리즘 $j$를 능가한 데이터셋의 수를 나타내는 토너먼트 테이블 $W$를 구성한다 ($W_{ij}$).

• 무승부 처리: 두 알고리즘의 성능 지표가 특정 데이터셋에서 정의된 신뢰 구간($metric \pm std$) 내에서 겹치는 경우, 해당 비교는 무승부로 처리된다. 저자들은 이 경우 $W_{ij}$와 $W_{ji}$ 모두에 0.5를 더한다.
• 추정 (Estimation): 저자들은 세 가지 추정 방법을 평가한다:
  • Classic Zermelo (MLE): 우도(likelihood)의 반복적 극대화.
  • Bayesian BT: 파라미터를 샘플링하기 위해 Metropolis-Hastings를 사용하며, 이를 통해 신뢰 구간과 불확실성 정량화를 제공한다.
  • Rank Centrality (Spectral Method): 그래프 상의 랜덤 워크(random walk)로 비교를 모델링하여 정상 상태 측도(stationary measures)를 추정한다.
  • 참고: 완전한 벤치마크 데이터에 대해 세 방법 모두 동일한 순위에 수렴했다. 신뢰 구간 제공 능력 때문에 베이지안(Bayesian) 방식이 선택되었다.

2. 검증 지표 (Validation Metrics)

순위의 품질과 견고성을 평가하기 위해 저자들은 "이행적 삼조항(transitive triplets)" 지표를 도입한다.

• 삼조항 $(i, j, k)$는 $i \succ j$, $j \succ k$, 그리고 $i \succ k$를 만족할 때 이행적(transitive)이라고 한다.
• 이 지표는 모든 데이터셋에 걸친 이행적 삼조항의 비율을 계산한다. 비율이 높을수록 순위가 더 일관되고 안정적임을 의미한다.
• 이 지표는 Kendall의 $\tau$와 같은 표준 순위 상관도 측정법의 한계인 누락된 데이터에 대한 견고성을 평가하기 위해 특별히 설계되었다.

3. 데이터셋 인식 확장 (Dataset-Aware Extensions)

글로벌 랭킹이 보지 못한(unseen) 데이터셋에는 적용되지 않을 수 있다는 한계를 해결하기 위해, 본 논문은 프레임워크를 확장한다:

• 공변량 조정 BT (Covariate-Adjusted BT): 밀도, 사용자-아이템 비율, 순차성 등 데이터셋 특성(공변량)을 모델에 포함한다. $i$가 $j$를 이길 확률은 알고리즘 강도와 데이터셋 공변량의 함수로 모델링된다: $P(i \succ j | x) = \sigma(\beta_{i0} - \beta_{j0} + \langle x, \beta_i \rangle - \langle x, \beta_j \rangle)$. 과적합을 방지하기 위해 L1 규제가 사용된다.
• Bradley-Terry Trees: 공변량(예: 순차성)에 따라 데이터셋을 재귀적으로 분할하여 동질적인 선호 스케일링을 가진 그룹을 식별하는 비매개변수(non-parametric) 접근 방식이다.

실험 설정

• 데이터셋: APS 벤치마크 및 추가 소스에서 가져온 89개의 다양한 추천 데이터셋을 사용하였으며, 5-core 필터링 기법으로 전처리하였다.
• 알고리즘: 단순 휴리스틱(Random, PopRandom)부터 이웃 기반(KNN 변형), 행렬 분해(ALS, BPR, PureSVD), 그래프 기반(LightGCN, UltraGCN), 순차 모델(SASRec, GASATF)에 이르는 14개의 알고리즘을 포함한다.
• 프로토콜: 글로벌 시간적 분할(90/5/5)을 적용하였으며, 하이퍼파라미터 최적화는 Optuna를 통해 수행되었다. 지표는 신뢰 구간을 확립하기 위해 10개의 무작위 시드에 대해 평균을 냈다.

주요 결과

1. 집계 베이스라인 대비 우월성

BT 기반 랭킹은 단순 집계 방식(평균 및 합계)에 비해 현저히 높은 안정성과 일관성을 보여주었다.

• 이행적 삼조항 (Transitive Triplets): BT 모델은 (모든 데이터셋에서 무승부를 고려했을 때) 0.631의 이행적 삼조항 비율을 달성하여, Mean(0.613) 및 Sum(0.613) 방식보다 높은 비율을 기록했다.
• 누락된 데이터에 대한 견고성: 누락된 쌍체 비교의 비율이 증가함에 따라 Mean 및 Sum 랭킹의 이행적 삼조항 비율은 급격히 떨어졌다. 반면, BT 및 Plackett-Luce (PL) 랭킹은 상당한 데이터 공백이 있는 상황에서도 높은 이행적 삼조항 비율을 유지하며 안정성을 보였다.

2. 맥락 의존적 성능 (Context-Dependent Performance)

실험 결과, 보편적으로 최적인 단일 알고리즘은 존재하지 않으며, 랭킹은 데이터셋 분류 체계에 따라 극적으로 변화함을 밝혔다:

• 순차성 (Sequentiality): 순차적 데이터셋에서는 순차 모델(SASRec, GASATF)이 지배적이지만(순위 1, 2위), 비순차적 데이터셋에서는 순위가 크게 하락한다(10, 11위). 반대로 ALS 및 UltraGCN과 같은 전통적 모델은 비순차적 데이터에서 더 나은 성능을 보인다.
• 이력 길이 (History Length): 사용자 이력이 긴 데이터셋에서는 Seq-KNN과 GASATF가 앞서며, 이력이 짧은 데이터셋에서는 LightGCN이 최고 성능을 보인다.
• 희소성 (Sparsity): GASATF와 User-KNN은 밀집된 데이터셋에 비해 희소한 데이터셋에서 상대적 성능이 향상된다.

3. 미지의 데이터셋에 대한 예측 능력

저자들은 모델을 실행하지 않고도 홀드아웃(holdout) 데이터셋의 랭킹을 예측하는 능력을 평가했다:

• 공변량 조정 모델: 공변량 조정 BT 모델과 BT 트리는 단순 집계 및 글로벌 BT 모델보다 미지의 데이터셋에 대한 Top-1 알고리즘 예측 성능이 뛰어났다 (Top-1 적중률: Cov. BT 0.28 vs. global BT 0.24).
• 베이스라인 선택의 충분성: 공변량 모델이 정밀한 랭킹 예측에서 더 높은 정확도를 보임에도 불구하고, 저자들은 글로벌 BT 랭킹(공변량 없는)이 강력한 상위 5개 베이스라인 세트를 선택하는 데 충분하다는 것을 발견했다 (Top-5 중첩도 ~3.32로, 더 복잡한 모델의 성능과 대등함).

의의 및 주장

본 논문은 단순한 지표 집계를 넘어 공정한 알고리즘 비교를 위한 원칙적이고 이론적으로 근거가 있는 방법론을 제공한다고 주장한다. 주요 기여는 다음과 같다:

1. 견고한 랭킹 프레임워크: BT 기반 랭킹이 전통적인 집계 방식보다 특히 누락된 데이터가 존재하는 상황에서 더 안정적이고 일관적임을 입증했다.
2. 데이터셋 인식 선택: 알고리즘 성능이 맥락 의존적임을 확립했다. 제안된 프레임워크를 통해 실무자는 특정 데이터셋 분류(예: 희소 vs 밀집, 순차적 vs 비순차적)에 적합한 알고리즘이 무엇인지 이해할 수 있다.
3. 예측 유용성: 공변량 조정 모델이 미지의 데이터셋에 대해 정밀한 랭킹 예측을 제공하지만, 글로벌 BT 랭킹만으로도 강력한 베이스라인 알고리즘 세트를 식별하기에 충분하며, 이는 철저한 평가에 드는 계산 비용을 줄여준다.
4. 재현성: 저자들은 14개 알고리즘의 구현, 하이퍼파라미터 최적화 프레임워크, 89개 데이터셋에 대한 결과를 포함하는 오픈 저장소를 제공하여 추천 시스템 연구의 재현성을 촉진한다.

결론적으로, 제안된 접근 방식은 데이터셋의 이질성과 평가의 불안정성 문제를 해결함으로써, 추천 시스템의 알고리즘 비교를 위한 더욱 신뢰할 수 있고 해석 가능한 토대를 제공한다.