Preference-Based Dynamic Ranking Structure Recognition

Nan Lu (Chinese Academy of Sciences) · Jian Shi (Academy of Mathematics and Systems Science) · Xinyu Tian (University of Minnesota - Twin Cities)

bradley-terry model dynamic programmingdynamic ranking groupsgroup inverse techniqueitem ability estimatesobjective functionpreference-based datarandom design matrixranking group recognitionranking structure recognitionreversible markov chainspectral estimationstructural changesstructure change recognitiontemporal penaltiesuncertainty quantification

Preference-based data often appear complex and noisy but may conceal underlying homogeneous structures. This paper introduces a novel framework of ranking structure recognition for preference-based data. We first develop an approach to identify dynamic ranking groups by incorporating temporal penalties into a spectral estimation for the celebrated Bradley-Terry model. To detect structural changes, we introduce an innovative objective function and present a practicable algorithm based on dynamic programming. Theoretically, we establish the consistency of ranking group recognition by exploiting properties of a random 'design matrix' induced by a reversible Markov chain. We also tailor a group inverse technique to quantify the uncertainty in item ability estimates. Additionally, we prove the consistency of structure change recognition, ensuring the robustness of the proposed framework. Experiments on both synthetic and real-world datasets demonstrate the practical utility and interpretability of our approach.