Hierarchical Partial-Order Models for Ranking

기술 요약: 계층적 부분 순서 모델 (Hierarchical Partial-Order Models for Ranking)

문제 정의

순위 집계(Rank aggregation)는 다양한 출처로부터 오는 정렬된 리스트들을 결합하여 하나의 합의된 구조를 만드는 것을 목표로 한다. Mallows나 Plackett–Luce와 같은 고전적인 파라미터 모델들은 선호도가 하나 또는 여러 개의 완전한 합의 순위(전순서, total orders) 주변에 집중되어 있다고 가정한다. 그러나 많은 응용 분야에서 실제 선호 구조가 전순서라는 가정은 정당화되지 않을 수 있다. 즉, 평가자들이 특정 항목들을 비교 불가능한 것으로 간주할 수 있기 때문이다. 또한, 선호 데이터는 종종 그룹 구조(예: 서로 다른 평가자, 별도의 시나리오, 또는 시계열 세그먼트)를 나타내지만, 기존 모델들은 부분 순서(poset) 구조를 보존하면서 이러한 구조를 수용하는 데 어려움을 겪는다.

최근 연구들이 전순서 가정을 완화하여 부분 순서(posets)를 허용하거나, 전순서를 위한 계층적 확장을 도입하기도 했으나, **계층적 그룹화(hierarchical grouping)**와 **부분 순서 합의(partial-order consensus)**를 결합한 통합된 프레임워크는 부재한 실정이다. 부분 순서를 위한 기존의 계층적 모델들(예: Arcagni et al., 2022)은 생성적 베이지안 추론(generative Bayesian inference)보다는 손실 기반의 점 추정치(loss-based point estimates)에 의존한다.

방법론

본 논문은 계층적 부분 순서(HPO) 모델과 그 비지도 클러스터링 확장형인 HCPO를 소개한다.

1. HPO 프레임워크

HPO 모델은 레이블이 지정된 그룹(예: $A$ 명의 평가자)으로 들어오는 순위 데이터에 맞게 설계되었다. 이 모델은 "글로벌" 부분 순서를 나타내는 루트 노드와 평가자별 부분 순서를 나타내는 리프 노드로 구성된 트리 구조를 가진다.

• 잠재 변수 구성: 모델은 연속적인 잠재 변수를 사용하여 부분 순서를 파라미터화한다. 선택의 유니버스에 있는 각 항목 $j$에 대해, 선호 가중치 벡터 $U_j \in \mathbb{R}^K$가 존재한다. 부분 순서는 이 가중치들로부터 유도된 $K$개의 완전한 순서들의 교집합으로 형성된다.
• 생성 과정:
  • 글로벌 레벨: 글로벌 잠재 가중치 행렬 $U^{(0)}$은 상관 구조 $\rho$에 의해 제어되는 다변량 정규 분포에서 추출된다.
  • 로컬 레벨: 각 평가자 $a$에 대해, 잠재 가중치 $U^{(a)}$는 상관 파라미터 $\tau$를 통해 $U^{(0)}$에 조건부로 추출된다. 이 파라미터 $\tau \in (0, 1]$는 평가자별 포셋(poset)이 글로벌 포셋으로 수렴하는 정도(shrinkage)를 제어한다.
  • 포셋으로의 매핑: 잠재 가중치는 Gumbel 구성(정규 CDF에 Gumbel 분포의 역함수를 적용)을 통해 선호 점수 $\eta$를 생성한다. 부분 순서 $h^{(a)}$는 이 점수들에 의해 유도된 순서들의 교집합으로 정의된다.
• 관측 모델: 순위 $y$가 포셋 $h$가 주어졌을 때 관측될 확률에 대해 세 가지 가능도(likelihood)를 제안한다:
  1. 노이즈 없는 모델 (Noise-free): 선형 확장(linear extensions)으로부터 균등 샘플링을 수행한다 (항목 $M$이 클 경우 계산 비용이 높음).
  2. 큐 점핑 (Queue-jumping): 반복적인 선택 모델로, 확률 $p$로 항목이 무작위로 선택(노이즈)되거나, 그렇지 않으면 포셋 제약 조건에 따라 선택된다.
  3. 가중 큐 점핑 (Weighted Queue-jumping): 무작위 선택이 잠재 점수 $\eta$에 의해 편향되는 확장형으로, 이를 통해 선호 격차가 큰 항목에 대해서는 오류 발생 가능성을 낮춘다.
  4. 프런티어 소프트맥스 (Frontier-softmax): 유틸리티 기반 모델로, 남은 부분 순서의 "프런티어"(최대 원소들)에서 항목을 선택하며, 해당 항목이 지배하는 항목의 수에 따라 가중치를 부여한다. 이는 계산 효율적($M$당 $O(M)$)이며 대규모 데이터셋에 적합하다.

2. HCPO 프레임워크

그룹 레이블을 알 수 없는 경우, 논문은 HPO를 계층적 클러스터링 부분 순서(HCPO) 모델로 확장한다.

• 클러스터링: 리스트(또는 평가자)를 $G$개의 잠동적인 그룹으로 나누는 파티션에 피트맨-요르 프로세스(Pitman-Yor process) 사전 분포를 배치한다.
• 추론: 그룹의 수 $G$와 클러스터 할당은 포셋 계층 구조와 함께 마르코프 체인 몬테카를로(MCMC)를 통해 공동으로 추론된다.
• 평가자 vs 리스트 클러스터링: 모델은 개별 리스트를 클러스터링하거나, 전체 평가자를 클러스터링(해당 평가자의 모든 리스트를 함께 이동)할 수 있다.

3. 베이지안 추론

추론은 MCMC를 사용하여 수행된다. 사후 분포는 상관 파라미터($\rho, \tau$), 잠재 가중치 행렬($U$), 회귀 계수($\beta$), 그리고 파티션($C$)에 대한 것이다. 잠재 공간의 차원 $K$ 또한 가역 점프 MCMC(reversible jump MCMC)를 통해 추론될 수 있다.

주요 기여

1. HPO 및 HCPO 모델: 그룹화된 순위 데이터에 대해 명시적으로 부분 순서 합의 구조를 모델링하는 생성적 베이지안 프레임워크를 도입하였으며, 이는 Plackett–Luce 모델을 포셋 영역으로 확장한 것이다.
2. 이론적 특성:
   • Plackett–Luce 모델과 그 계층적 변형들이 ($K=1$일 때) HPO의 특수 사례임을 증명하였다.
   • 모델이 **한계적으로 일관됨(marginally consistent)**을 입증하여, 부분 순서에 대한 사전 분포가 전체 유니버스에 대한 사전 분포와 일치함을 보여준다.
   • $K \ge \lfloor M/2 \rfloor$인 경우 모델이 임의의 포셋 계층을 표현할 수 있음을 증명하였다.
3. 새로운 관측 모델: 가중 큐 점핑(Weighted Queue-jumping) 및 프런티어 소프트맥스(Frontier-softmax) 가능도를 개발하여, 생성적 해석을 유지하면서도 노이즈를 허용하고 계산 효율성을 확보하였다.
4. 비지도 클러스터링: 레이블이 없는 순위 데이터에서 잠재적인 그룹 구조를 발견하기 위해 HCPO로 확장하였다.

실험 결과

논문은 합성 데이터 및 실제 데이터를 사용하여 모델을 평가한다:

• 합성 데이터 (HPO): 레이블이 지정된 그룹 환경에서, HPO는 잠재적인 포셋 계층 구조를 성공적으로 복구하였다. 복구 정확도는 주로 관측된 리스트의 길이(선택 집합 크기)와 결합 강도($\tau$)에 의해 결정된다. 프런티어 소프트맥스 가능도는 정확한 선형 확장 방법을 사용할 때보다 상당한 계산 속도 향상을 제공하며, 이는 $M \ge 50$인 경우 정확한 방법이 시간 초과를 일으키는 것과 대조적이다.
• 합성 데이터 (HCPO): 레이블이 없는 환경에서, HCPO는 잠재적인 클러스터링 구조와 클러스터별 포셋을 모두 정확하게 복구하였다. 클러스터링의 이점은 그룹 간의 결합이 약할 때(높은 이질성) 가장 두드러졌다.
• 클라우드 프로비저닝 트레이스 (LLM 에이전트): LLM 에이전트의 실행 트레이스(Aliyun Cloud-IaC-6)에 적용하였다. HPO 모델은 서로 다른 시나리오를 그룹으로 취급했을 때, 독립적인 단일 포셋 베이스라인보다 밑단 구조(dependency graphs/workflow structures)를 복구하는 데 더 우수한 성능을 보였다. 계층적 풀링은 데이터가 희소한 시나리오에서 선행 제약 조건을 복구하는 능력을 개선하였다.
• 인간 선호 데이터 (3D 사운드): 청취자들이 순환 패턴(전순서를 위반함)을 보이는 쌍체 음향 선호 데이터에 적용하였다. HCPO 모델은 예측 적합도(WAIC) 측면에서 전순서 베이스라인(Plackett–Luce 및 Mallows 혼합 모델)을 유의미하게 앞질렀다. 결정적으로, HCPO 요약은 클러스터 내에 비교 불가능한 아이템들이 넓은 "상위 레이어"를 형성하는 해석 가능한 구조를 드러냈는데, 이는 전순서를 강제하지 않고서는 표현할 수 없는 특징이다.

의의 및 주장

본 논문은 제안된 HPO 및 HC로 프레임워크가 선호가 불완전하거나 비교 불가능할 수 있는 그룹화된 순위 데이터를 처리하는 원칙적인 방법을 제공한다고 주장한다.

• 구조적 해석 가능성: 모델은 실제적인 비교 불가능성을 반영하는 부분 순서 구조를 복구할 수 있게 하여, 데이터를 전순서로 강제함으로써 발생하는 인위적인 결과물을 방지한다.
• 정보 공유: 계층적 구조는 그룹 간의 원칙적인 정보 공유(shrinkage)를 가능하게 하여, 저데이터 환경에서도 추정을 개선하는 동시에 그룹별 고유한 특성을 보존한다.
• 계산 가능성: 프런티어 소프트맥스 가능도를 통해, 정확한 선형 확장 계산이 불가능한 더 큰 아이템 세트에도 모델을 적용할 수 있게 한다.
• 일반성: 본 프레임워크는 기존의 계층적 Plackett–Luce 모델을 포섭하며, 이를 부분 순서 영역으로 확장하여 레이블이 있거나 없는 그룹화된 순위 데이터 모두에 적용 가능한 통합된 접근 방식을 제공한다.

저자들은 제안된 방식이 전체적인 베이지안 사후 분포를 제공함으로써, 불확실성 정량화와 WAIC를 통한 원칙적인 모델 비교를 가능하게 한다는 점에서 기존의 손실 기반 부분 순서 방법보다 우월하다고 강조한다.