Statistical ranking and combinatorial Hodge theory
Statistical ranking and combinatorial Hodge theory
复制标题
DOI：
10.1007/s10107-010-0419-x
复制
发表时间：
2011-03-01
影响因子：
2.7
通讯作者：
Ye, Yinyu
中科院分区：
文献类型：
--
作者：
Jiang, Xiaoye;Lim, Lek-Heng;Ye, Yinyu
我们提出了一种称为HodgeRank的技术，用于对可能不完整和不平衡的数据进行排名，这些数据在来自电子商务和互联网应用程序的现代数据集中很常见。我们主要对基于分数或评级的基数数据感兴趣，尽管我们的方法也对序数数据有具体的见解。从原始的排名数据，我们构建成对的排名，表示为一个适当的图上的边流。我们的统计排序方法利用了图亥姆霍兹算子，这是亥姆霍兹算子或向量拉普拉斯算子的图论模拟，以同样的方式，图拉普拉斯算子是拉普拉斯算子或标量拉普拉斯算子的模拟。我们将使用组合Hodge理论来研究图Helmholtzian，该理论提供了一种从边缘流中解开排名信息的方法。特别是，我们表明，每一个边流表示成对排名可以分解成两个正交分量，梯度流表示的l（2）-最优的全球排名和无发散流（循环），措施的有效性，全球排名获得如果这是大的，那么它表明数据没有一个良好的全球排名。这种无发散流可以进一步正交分解为旋度流（局部循环）和谐波流（局部非循环但全局循环）;这些提供了关于排名数据中的不一致性是局部还是全局出现的信息。当应用于统计排名问题时，霍奇分解揭示了给定数据集是否可以以有意义的方式进行全局排名，或者数据是否本质上不一致，因此无法进行任何合理的全局排名;在后一种情况下，它提供了关于不一致性性质的信息。一个明显的优势，超过NP-硬度的Kemeny优化是，HodgeRank可以很容易地计算通过线性最小二乘回归。我们还讨论了与著名的序数排序技术，如凯梅尼优化和Borda计数从社会选择理论的连接。
We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian, which is the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We shall study the graph Helmholtzian using combinatorial Hodge theory, which provides a way to unravel ranking information from edge flows. In particular, we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the l(2)-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained-if this is large, then it indicates that the data does not have a good global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency in the ranking data arises locally or globally. When applied to statistical ranking problems, Hodge decomposition sheds light on whether a given dataset may be globally ranked in a meaningful way or if the data is inherently inconsistent and thus could not have any reasonable global ranking; in the latter case it provides information on the nature of the inconsistencies. An obvious advantage over the NP-hardness of Kemeny optimization is that HodgeRank may be easily computed via a linear least squares regression. We also discuss connections with well-known ordinal ranking techniques such as Kemeny optimization and Borda count from social choice theory.