关键词:
成对比较
单峰强随机传递性模型
极小极大收敛速率
摘要:
成对比较在传统的体育竞赛领域有着广泛的应用.随着互联网技术的迅速发展,这一问题在推荐系统和在线决策等前沿领域的重要性愈发突出.与参数模型相比,强随机传递(strong stochastic transitivity, SST)模型因其灵活性、广泛适用性和提取复杂结构的高效率而备受关注.然而, SST模型的有限假设使得概率矩阵的估计具有挑战性,从而使得SST模型框架能否有效刻画成对比较问题充满不确定性.本文对SST模型引入了一个自然约束,提出了单峰强随机传递(unimodal SST, USST)模型.该模型保留了SST模型的灵活性,并包含许多解决成对比较问题的参数模型作为特例.本文证明了在USST模型中,约束最小二乘估计量在log(log n)的多项式因子范围内是速率最优的.本文还提出了一个用于估计概率矩阵的高效算法,在log n的多项式因子范围内速率最优.与现有的SST相关方法相比,本文的算法在收敛速度上有显著提高,在对数因子内达到了最优.通过数值模拟,本文展示了所提出算法的优越性,并使用英超联赛比赛的真实数据验证了其有效性.