arXiv:2610.10795v1 cs.LG

이질성 환경의 랭킹을 위해 얼마나 많은 반복 쌍체 비교가 필요한가?

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

Shashaank Aiyer, Han Shao

제출 2026-10-07

저자 비고

arXiv Comments

53 pages, 4 figures

한국어 초록

본 연구에서는 사용자와 태스크에 따라 선호도가 달라질 때, 쌍체 비교(pairwise comparisons)를 통해 모집단 평균 효용(population-average utility)을 기반으로 모델 순위를 매기는 문제를 탐구합니다. 선행 연구에 따르면 임의로 많은 사용자가 존재하더라도 사용자당 단 한 번의 비교만으로는 가장 높은 평균 효용을 가진 대안을 식별하기에 불충분할 수 있음이 밝혀졌습니다(Golz et al., 2025). 우리는 순위 복원을 위해 각 사용자-태스크 맥락(context) 내에서 얼마나 많은 반복 비교가 필요충분한지 조사합니다. 고정된 역온도(inverse temperature)를 갖는 이질적 Bradley-Terry 모델 하에서, 먼저 순위 복원을 보장하기 위해 맥락당 $Ω(1/Δ^2)$의 반복 비교를 필요로 하는 나이브한 MLE 기반 알고리즘을 살펴봅니다. 이어 맥락당 $O(\log(1/Δ))$회의 반복 비교만으로 순위를 복원하는 두 가지 MLE 기반 변형과 무작위화된 러시안 룰렛(Russian Roulette) 스타일의 알고리즘을 제시하며, 이러한 로그 의존성이 최적임을 증명합니다. 최악의 경우에 대한 이러한 요구 조건에도 불구하고, 제안하는 러시안 룰렛 알고리즘은 기대값 기준 맥락당 $O(1)$회의 비교만을 사용합니다. 합성 데이터 실험 및 Arena 데이터 기반의 준합성(semi-synthetic) 실험을 통해 다양한 수준의 선호도 이질성과 여러 맥락 분포 환경에서 네 가지 알고리즘을 비교 검증합니다.

원문 초록

We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Golz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley-Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires $Ω(1/Δ^2)$ repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using $O(\log(1/Δ))$ repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only $O(1)$ comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.10795v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2501.07437v3stat.ML공통 태그 ranking, pairwise comparison, bradley-terry model공식 코드 · Papers with Code

확률적 추이성 없는 쌍별 비교: 모델, 이론 및 응용

Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications

Bradley-Terry(BT) 모델, Thurstone 모델 및 다수의 확장 모델을 포함한 쌍별 비교를 위한 대부분의 통계 모델은 확률적 추이성(stochastic transitivity)이라는 비교적 강한 가정을 전제로 한다. 이 가정은 모든 선수/팀/아이템 간에 관측되지 않는 전역 순위가 존재하며, 해당 전역 순위에 의해 함의되는 비교 확률에 단조 제약이 부과된다는 것을 의미한다. 그러나 확률적 추이성 가정은 다양한 기술이나 전략이 관여하는 게임과 같이 실제 세계의 쌍별 비교 시나리오에서는 성립하지 않는 경우가 많다. 그 결과, 이 가정에 의존하는 모델은 예측 성능이 최적에 미치지 못할 수 있다. 본 논문에서는 확률적 추이성 가정 없이 쌍별 비교 데이터를 위한 일반적인 통계 모델 패밀리를 제안하며, 이는 BT 모델과 Thurstone 모델을 실질적으로 확장한다. 이 모델에서 쌍별 확률은 (근사적으로) 저차원 반대칭 행렬(skew-symmetric matrix)에 의해 결정된다. 관측된 쌍의 비율이 낮은 희소(sparse) 데이터에도 적용 가능한 가능도 기반 추정 방법과 계산 알고리즘을 개발하였다. 이론적 분석을 통해 제안된 추정량이 데이터의 희소성 수준에 효과적으로 적응하는 미니맥스 최적율(minimax-rate optimality)을 달성함을 보인다. 반대칭 행렬의 스펙트럼 이론은 구현 및 이론적 분석에서 핵심적인 역할을 한다. BT 모델 대비 제안 방법의 우월성 및 다양한 시나리오에 걸친 폭넓은 적용 가능성은 시뮬레이션과 실제 데이터 분석을 통해 추가로 확인된다.

arXiv:2604.04328v4cs.AI공통 태그 pairwise comparison

소프트 토너먼트 평형: 비이행적 쌍별 비교를 위한 미분 가능 집합값 추론

Soft Tournament Equilibrium: Differentiable Set-Valued Inference for Non-Transitive Pairwise Comparisons

소프트 토너먼트 평형(Soft Tournament Equilibrium, STE)은 상호 쌍 확률로부터 Top-Cycle(TC)과 Uncovered-Set(UC) 추론을 수행하는 미분 가능 층(layer)이다. 정규화된 log-sum-exp 도달 가능성과 커버링은 근사, 교란, 마진(margin) 복구 경계를 갖는 매끄러운 점수를 제공한다. 우리는 통제된 합성 연구와 기록된 순서형 프로파일의 재구성을 통해 구조적 지도(supervision), 사후 불확실성, 그리고 최종 집합 결정을 구분한다. 매칭된 에포크(epoch) 학습은 공통 구조적 판독(readout) 하에서 F1을 향상시키지만, 별도의 동일 예산 soft-UC 비교에서는 우위가 나타나지 않는다. 전향적인 동일 예산 hard-UC 연구는 24개 대안에서 선택적 F1을 ordinary/relational 네이티브 헤드의 0.6327/0.6292에서 0.6676으로 향상시키지만, 정확한 복구(exact recovery)는 여전히 1.16%에 불과하다. 소스별로 홀드아웃된 36개의 인간 프로파일에 대해, 별도의 탐색적 비교는 네이티브 기대 F1 디코딩에서 Jeffreys 사후 추론이 학습된 독립-엣지 및 혼합 분포보다 우수함을 보여준다(0.8742 대 0.8704/0.8366). 비단일(non-singleton) 선택적 코어를 갖는 참조는 단 세 개뿐이다. 완성 증명서(completion certificate)와 전체 깊이 TC 진단은 추가적인 식별, 평활화(smoothing), 계산적 한계를 명확히 한다. 이 증거는 조건부 합성 중첩 이득을 지지하는 동시에, soft-set 널(null)을 유지하고, 강력한 카운트 기반 인간 프로파일 대조군에 대한 학습 우위가 입증되지 않았음을 보존한다.

arXiv:2607.22221v1stat.ML공통 태그 ranking

Bradley--Terry 모델에 대한 Zermelo형 반복법 계열의 수렴 분석

Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model

Zermelo 알고리즘은 Bradley--Terry(BT) 모델에서 최대 가능도 추정량을 계산하는 고전적인 방법이지만, 실무에서 그 수렴이 느릴 수 있다. 계산을 가속하기 위해 Newman은 $α$로 매개변수화된 Zermelo형 고정점 반복법 계열을 도입했으며, $α=1$에서 Zermelo 알고리즘이 복원된다. 경험적 증거는 $α=0$ 선택이 종종 상당히 더 빠르게 수렴함을 시사하여 유망한 대안이 되지만, 이러한 가속의 기저 메커니즘은 여전히 불명확하다. 본 논문은 체계적인 국소 수렴 분석을 통해 이 현상에 대한 이론적 통찰을 제공한다. 우리는 동기 및 비동기 업데이트 하에서 국소 수렴 인자에 대한 닫힌 형태 표현을 유도하고, 관련 야코비안 행렬의 스펙트럼 분석을 통해 $α$에 대한 의존성을 분석한다. 동기 업데이트의 경우, $α<1$일 때 알고리즘이 수렴하지 못할 수 있음을 보이며, 모집단 BT 모델 하에서 국소 수렴 인자가 $α$에 대해 준볼록(quasi-convex)임을 보인다. 반면 비동기 업데이트는 항상 국소적으로 수렴하며, 일관된 순서의 이분 비교 그래프에 대한 모집단 BT 모델 하에서 국소 수렴 인자가 $α$에 대해 단조 증가함을 증명하여, 이 설정에서 $α=0$의 최적성을 확립한다. 우리는 또한 BT 모델 하에서 모집단 수렴 인자에 대한 점근 근사 결과를 확립하여 그 실용적 관련성을 정당화한다. 합성 및 실제 데이터셋에 대한 수치 실험이 이론을 확인한다. 우리의 분석은 기존 수렴 결과를 보완하며, $α=0$의 가속이 매개변수 선택뿐 아니라 더 중요하게는 비동기 업데이트 사용에서 기인함을 보여준다.

arXiv:2607.02672v2cs.AI공통 태그 pairwise comparison

내적 다원주의와 쌍별 비교의 한계

Internal Pluralism and the Limits of Pairwise Comparisons

지역적 쌍별 비교(local pairwise comparison)는 참여적 설계(participatory design)나 정렬(alignment) 등에서 사람들이 의사결정 규칙이 어떻게 작동하기를 원하는지 학습하기 위한 표준적인 도구다. 그러나 이 방법의 사용은 두 가지 강한 가정을 내포한다: 지역적 비교가 자동화된 의사결정 규칙의 동작 방식에 대한 개인의 선호를 파악하기에 충분한 증거가 된다는 것과, 사람들이 항상 해당 비교에 결정적으로 답할 수 있다는 것이다. 우리는 이러한 가정들이 내적 다원주의(internal pluralism) 하에서 어떻게 훼손될 수 있는지를 탐구한다. 내적 다원주의란 개인이 규칙이 어떻게 동작해야 하는지에 대한 복수의 권위 있는 우선순위에 따라 의사결정 규칙을 평가한다는 개념이다. 우리는 의사결정 규칙에 대한 이러한 다원적 선호의 형식적 모델을 제시하고, 이를 통해 강제적 지역적 쌍별 비교 데이터의 두 가지 명확한 실패 유형을 규명한다. 첫째, 비례성(proportionality), 평등주의(egalitarianism), 동등 처우(equal treatment)와 같은 우선순위는 본질적으로 전역적(global)이다: 한 사례에서 이들이 함의하는 바는 다른 곳에서 일어나는 일에 따라 달라질 수 있으므로, 지역적 비교로는 이를 포착하지 못할 수 있다. 둘째, 우선순위가 지역적으로 표현 가능한 경우에도, 강하게 견지되는 우선순위들 사이의 긴장이 내적 갈등을 야기하여, 비교가 강제될 때 잠재적으로 비용이 큰 행동 왜곡을 초래할 수 있다. 이어서 우리는 대안, 즉 사람들이 결정 불능(indecision)을 보고하도록 허용하는 방안을 우리의 모델을 통해 탐구하며, 그 결과 이러한 방식이 선호를 정확하게 학습하는 데 필요한 질의(query) 수를 상당히 줄일 수 있음을 시사한다. 마지막으로, 우리의 모델이 이러한 우선순위를 직접 도출하는 선호 학습(preference-learning) 방법을 어떻게 지향하는지를 설명하며, 이를 통해 사람들이 가치 있게 여기는 것에 대한 보다 충실하고 해석 가능한 설명을 도출할 수 있음을 논의한다.

arXiv:2607.14408v1cs.AI공통 태그 pairwise comparison

쌍대 검증자를 통한 보상 없는 진화 에이전트

Reward-Free Evolving Agents via Pairwise Validator

자기 진화(self-evolving) 에이전트 루프는 에이전트(프롬프트 템플릿 또는 프로그램)의 수정된 버전을 반복적으로 제안하고, 반복(iteration)마다의 품질 신호에 따라 변경을 수락하거나 거부한다. 이 신호를 설계하는 것이 프로젝트에서 종종 비용이 큰 부분이다. 신뢰할 수 있는 스칼라 보상은 도메인 전문성과 라벨이 달린 예시가 필요하며, 이 예시들을 구축하는 비용 자체가 에이전트의 기본 과제만큼 비싸다. 우리는 수락/거부 게이트의 스칼라를 쌍대 검증자(pairwise validator)로 대체할 것을 제안한다. 쌍대 검증자는 고정된(frozen) LLM으로, 부모 후보와 자식 후보가 주어지면 어느 쪽이 더 나은지에 대한 이진 판정을 반환한다. 쌍대 판단은 대조적(contrastive) 특성 때문에 절대 점수화보다 일반적으로 더 쉽고 안정적이며, 엄격한 스케일 보정(calibration)의 필요성을 완화한다. 검증자 또한 별도의 학습(training)이 필요하지 않다. 우리는 검증자를 세 가지 공개된 자기 진화 엔진(GEPA, ADRS, ShinkaEvolve)에 통합하고 두 가지 변형을 보고한다. Adaptive Focus는 엔진의 기존 검증 집합(val-set) 부모 선택을 유지하고, Soft Elo는 검증자의 판정이 부모 선택을 주도하게 하여 검증 집합 보상도 제거한다. 여러 에이전트와 두 가지 산출물 기판(프롬프트와 코드)에 걸쳐, 우리 방법은 평가한 설정의 대부분에서 전체 보상(full-reward) 기준선(baseline)과 동등하거나 이를 초과하며, 이 패턴은 교차 계열(cross-family) 검증자 교체에도 유지된다. 따라서 쌍대 게이트는 라벨링 비용 없이 경쟁력 있는 과제 정확도에서 단계별 보상 설계를 대체할 수 있는 즉시 교체형(drop-in replacement) 솔루션이다.

arXiv:2607.10038v1stat.ME공통 태그 pairwise comparison

기준값을 활용한 기하평균 기반 쌍별 비교 방법 -- 통계적 접근법

Geometric mean-based pairwise comparison method with the reference values -- statistical approach

수년간 쌍별 비교(pairwise comparison) 방법은 전문가가 참여하는 의사결정에 널리 활용되어 왔다. 이 방법의 가장 잘 알려진 사례는 계층분석과정(AHP, Analytic Hierarchy Process)이다. 이 고전적 접근법에서는 비교 행렬의 주 고유벡터를 이용하여 대안들의 가중치(weight)를 산출한다. 본 논문에서는 기준값과 기하평균을 활용하여 대안 우선순위를 계산하는 쌍별 비교 방법의 통계적 관점을 제시한다. 이 접근법을 통해 쌍별 비교에서의 비일관성(inconsistency) 현상과 대안 간 선호 거리를 동시에 포착할 수 있다. 또한 본 논문에서는 산출된 가중치 벡터의 품질을 측정하는 지표를 정의하며, 이 지표들은 통계적 접근법 덕분에 명확하고 직관적인 해석이 가능하다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.