Rank aggregation systems collect ordinal preferences fromindividuals to produce a global ranking that represents thesocial preference. Rank-breaking is a common practice to reducethe computational complexity of learning the global ranking. Theindividual preferences are broken into pairwise comparisons andapplied to efficient algorithms tailored for independent pairedcomparisons. However, due to the ignored dependencies in thedata, naive rank-breaking approaches can result in inconsistentestimates. The key idea to produce accurate and consistentestimates is to treat the pairwise comparisons unequally,depending on the topology of the collected data. In this paper,we provide the optimal rank-breaking estimator, which not onlyachieves consistency but also achieves the best error bound.This allows us to characterize the fundamental tradeoff betweenaccuracy and complexity. Further, the analysis identifies howthe accuracy depends on the spectral gap of a correspondingcomparison graph. color="gray">
展开▼
机译：等级汇总系统从个人那里收集顺序偏好，以产生代表社会偏好的整体排名。降低排名是降低学习全球排名的计算复杂度的一种常见做法。个人喜好分为成对比较，适用于针对独立配对比较量身定制的高效算法。但是，由于忽略了数据中的依赖性，幼稚的排名打破方法可能导致不一致的估计。产生准确一致的估计的关键思想是根据所收集数据的拓扑结构，不平等地对待成对比较。在本文中，我们提供了一种最佳的秩分解估计器，它不仅可以实现一致性，而且还可以实现最佳的误差范围。这使我们能够描述准确性和复杂性之间的基本权衡。此外，该分析还确定了精度如何取决于相应比较图的光谱间隙。 color =“ gray”>
展开▼
