没有合适的资源?快使用搜索试试~ 我知道了~
15230偏序超图上的学习0新加坡国立大学冯福利fulifeng93@gmail.com0何向南 �0新加坡国立大学向南何xiangnanhe@gmail.com0清华大学刘义群yiqunliu@tsinghua.edu.cn0山东大学聂立强nieliqiang@gmail.com0新加坡国立大学蔡达成chuats@comp.nus.edu.sg0摘要0基于图的学习方法明确考虑两个实体(即顶点)之间的关系,以学习预测函数。它们广泛应用于半监督学习、流形排序和聚类等任务。超图通过将边界表示为指向多个顶点的链接来增强简单图的表达能力,以便对实体之间的高阶关系进行建模。例如,超图中的超边可以用于编码顶点之间的相似性。据我们所知,所有现有的超图结构都将超边表示为无序顶点集,而不考虑顶点之间的可能排序关系。在现实世界的数据中,常常存在排序关系,例如在分级分类特征(例如用户对电影的评级)和数值特征(例如客户的月收入)中。在构建超图时,忽略实体之间的这种排序关系将导致严重的信息丢失,从而导致后续学习算法的性能不佳。在这项工作中,我们通过提出一种名为“偏序超图”的新数据结构来解决现有超图的固有局限性,该数据结构专门将顶点之间的部分排序关系注入超边。我们通过将编码部分排序关系的逻辑规则纳入常规超图学习中,开发了基于正则化的偏序超图学习理论。我们将我们提出的方法应用于两个应用程序:基于Web数据的大学排名和在线内容的流行度预测。大量实验证明了我们提出的偏序超图的优越性,其在常规超图方法上持续改进。0CCS概念0• 信息系统 → 网络挖掘;网络应用;• 计算方法 →谱方法;半监督学习设置;• 应用计算 → 教育;0�何向南为通讯作者。该研究是NExT++项目的一部分,该项目得到了新加坡国家研究基金会总理办公室的支持,属于其IRC@Singapore资助计划。0本文发表在知识共享署名4.0国际(CC BY4.0)许可下。作者保留在个人和公司网站上传播作品的权利,并附上适当的归属。WWW2018,2018年4月23日至27日,法国里昂© 2018IW3C2(国际万维网会议委员会),根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31860640关键词0超图,偏序超图,基于图的学习,大学排名,流行度预测0ACM参考格式:Fuli Feng,Xiangnan He,Yiqun Liu,LiqiangNie和Tat-Seng Chua。2018年。偏序超图上的学习。在WWW2018:2018年Web会议上,2018年4月23日至27日,法国里昂。ACM,纽约,纽约,美国,10页。https://doi.org/10.1145/3178876.318606401 引言0图自然地表示关系数据,并广泛用于模拟实体之间的关系。简单图直观地将两个顶点(即感兴趣的实体)用一条边连接起来(即要建模的关系),根据实体之间的成对关系是否对称,边可以是无向的或有向的。例如,给定一组具有特征向量的实体,我们可以通过使用相似性度量构建邻接矩阵来构建一个无向图[45,48]。万维网是一个众所周知的有向图实例,其中顶点表示网页,边表示超链接。有了这样的实体和它们关系的图表示,就可以开发许多基于图的学习方法来解决各种任务,例如半监督学习[11, 32, 37,47],流形排序[20, 30, 31, 49]和聚类[4, 8, 40],个性化推荐[17,23]等。超图是简单图的一种推广,其中一条边(又名超边)可以连接任意数量的顶点,而不仅仅是两个。因此,它可以模拟简单图无法自然表示的多个实体之间的高阶关系。图1显示了使用图方法解决大学排名任务的示例[9]。每个大学都有两个特征:所在城市和其毕业生的薪资水平(图1a)。可以通过将大学与其两个最近邻连接起来构建一个简单图(图1b);然后在简单图上进行流形排序可以获得一个大学的排序列表。此外,我们可以通过连接具有相同属性的大学来构建超图(图1c),例如位于同一城市的大学,这是简单图所错过的大学之间的高阶关系。在现有研究中,超图中的超边通常是通过链接相似的实体形成的 -全局相似,例如彼此靠近的实体的一个簇[27, 36,38],或者局部相似,例如共享相同属性[3, 35,43]。然而,我们认为许多现实世界的应用需要处理比相似性更复杂的关系。一种特殊类型是0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France15240图1:使用图方法解决大学排名任务的示例。(a)输入数据,每行表示一所大学及其特征:城市和薪水水平;对于薪水水平,较小的索引表示较高的薪水(即s1 > s2 > s3 > s4)。(b)简单图,其中一条边连接一个顶点和其两个最近的顶点。(c)超图,其中一个超边连接具有相同属性的顶点:要么在同一个城市,要么具有相同的薪水水平。(d)偏序超图,其中超边内的有向边表示顶点在薪水水平上的部分排序关系。0实体之间的排序关系通常存在于分级分类特征和数值特征中。以图1中的大学排名任务为例。两所大学u5和u6位于同一个城市,而u5的薪水水平远高于u6,这是u5可能排名高于u6的证据。不幸的是,图1c中构建的超图仅编码了相似性信息,因此无法捕捉到薪水的排序信息。为了解决这个限制,一个直观的解决方案是通过在超边的实体之间添加有向边来纳入排序关系,如图1d所示。值得注意的是,并不是每两个超边内的实体都有排序关系;例如,两个实体可能具有相同的分级分类特征(见图1d中的u1和u2),或者目标数值特征的差异不足够显著。因此,我们将具有顶点偏序关系的广义超图称为偏序超图(POH),这是一种新的数据结构,以前从未被探索过。在这项工作中,我们对POH的概念进行了形式化,并进一步在其上发展了基于正则化的图学习理论。我们用逻辑规则来表示偏序关系,这可以用于编码先前的领域知识。在前面的大学排名示例中,一个领域知识的例子是对于同一个城市中的两所大学ui和uj,如果ui的薪水水平高于uj,那么ui倾向于排在uj之前。相应的逻辑规则可以写成:0city = (ui, uj) ∧ salary > (ui, uj) → score > (ui, uj). (1)0我们将传统的超图学习[38,48]扩展到POH上,以便有效地学习逻辑规则。除了提高准确性外,我们还可以通过验证逻辑规则来进一步提高超图学习的可解释性。具体而言,我们可以通过验证逻辑规则来解释学习结果,而不仅仅依赖于平滑因子。为了验证我们提出的偏序超图和学习方法,我们将它们应用于大学排名[9]和流行度预测[5,16]这两个应用领域;这两个任务分别代表了无监督排序和半监督回归这两个机器学习任务。广泛的结果证明了我们的优越性。0提出的方法明显优于现有的简单图和超图方法。本文的主要贡献总结如下。0•我们提出了一种新的偏序超图,用于表示顶点之间的偏序关系,这是传统超图所缺失的。•我们将现有的基于图的学习方法推广到偏序超图中,以逻辑规则的形式编码领域知识。•我们通过两个无监督排序和半监督回归的机器学习任务实证了我们的POH和学习方法的有效性。0本文的剩余部分组织如下。第2节介绍了一些预备知识。第3节介绍了我们提出的方法,然后在第4节回顾了相关工作。在第5节和第6节中,我们采用POH学习来解决大学排名和流行度预测这两个任务。我们在第7节总结了这项工作。02 预备知识0首先,我们引入一些符号。我们使用粗体大写字母(例如,X)和粗体小写字母(例如,x)分别表示矩阵和向量。标量和超参数分别表示为普通小写字母(例如,x)和希腊字母(例如,λ)。如果没有另外说明,所有向量都是列形式的,Xij表示X的第i行第j列的元素。02.1 超图0如前所述,超图的顶点和超边分别表示感兴趣的实体和它们的关系。给定具有特征X=[x1, x2, ∙ ∙ ∙ ,xN]T∈RN×D的N个实体,我们可以构建一个具有N个顶点和M个超边的超图,其结构可以表示为一个关联矩阵H∈RN×M。与简单图的关联矩阵类似,H是一个二进制矩阵,其中Hij=1表示第i个顶点由第j个超边连接,否则Hij=0。有0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France). Given the weightsdegree of a vertex i:M.(4)Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France15250两种方法可以定义现有工作中的超边:基于属性[3, 22, 35,43]和基于邻居[27, 36,38]。基于属性的超边连接具有相同值的一个或多个目标属性(即特征)的顶点。基于邻居的超边连接附近的顶点,基于这些顶点的相似度大于阈值或仅使用k个最近邻。此外,我们使用对角矩阵E∈RM×M表示超边的度,即Ejj=∑Ni=1Hij表示第j个超边连接的顶点数。类似于简单图中边通常具有权重来模拟关系的强度,超图中的超边也具有权重来表示连接的顶点的密度。这些权重表示为对角矩阵W∈RM×M。为了估计超边的权重,已经提出了许多方法,其中最流行的方法是使用超边连接的顶点之间的平均配对相似度:0Wjj = 1/Ejj0�0Hij = 1/д(xi, xj),(2)0其中д表示特征向量上的相似性函数。在基于图的方法中,д的一个常见选择是径向基函数(RBF)核,即д(xi, xj) = exp(−∥xi−xj∥2/2σ2)。给定超边的权重,我们可以进一步推导出一个顶点的度:Vii=∑Mj=1WjjHij,即连接该顶点的超边的权重之和。0(RBF)核,即д(xi, xj) = exp(−∥xi − xj∥2)0用V∈RN×N表示顶点度矩阵的对角矩阵。02.2 超图上的学习0基于图的学习已经应用于各种机器学习任务,如流形排序、半监督学习和聚类[1, 26, 44]。一般的问题设置是学习一个预测函数ˆy =f(x),它将特征空间中的实体映射到目标标签空间。通常通过最小化一个抽象的目标函数来实现:0Γ = G + λL,(3)0其中L是一个任务特定的损失函数,用于衡量预测值ˆy和真实值y之间的误差,G是一个图正则化项,用于使预测在图上平滑,λ是一个超参数,用于平衡这两个项。正则化项通常实现了相似顶点倾向于具有相似预测的平滑性假设。对于超图,一个广泛使用的G是超图拉普拉斯项,定义如下:0G =0N/A0i = 10N/0j = 1 д(xi,xj)0M是0k = 1 HikWkkHjk0的平滑性强度是通过特征向量接0平滑性强度0平滑性强度0Vjj0的平滑性强度是通过特征向量之间的相似性д(xi,xj的0平滑性0正则化项对每对实体进行平滑处理,使它们的预测(在归一化后)彼此接近。平滑性的强度由特征向量д(xi,xj)和连接两个顶点的超边上的相似性决定。它可以等价地以更简洁的矩阵形式表示:0G = trace(ˆY(S⊙L)ˆYT), (5)0其中ˆY = [ˆy1, ˆy2, ∙ ∙ ∙ , ˆyN],S的每个元素是Sij =д(xi,xj),L定义为L = V−1/2(V−HWHT)V−1/2,称为超图拉普拉斯矩阵。请注意,L通常是一个稀疏矩阵,其中只有当顶点i和j由至少一个超边连接时,Lij的条目才为非零。因此,计算G的时间复杂度与L中的非零条目数成线性关系,远小于N2。03 偏序超图0与超图学习的典型问题设置不同,我们进一步将问题与一组逻辑规则关联起来,这些规则可以用来编码实体之间的偏序关系:0其中r表示一个偏序关系,对于一个问题可以有多个关系(总共R个)。例如,在大学排名任务中,我们可以根据薪水水平、学生人数、研究经费等特征建立一个偏序关系。对于每个偏序关系r,qr是一个二元函数,指示两个实体的预测是否满足某个关系。例如,在排名/回归任务中,qr可以指示fi(xi)是否高于fi(xj);在分类任务中,qr可以指示xi属于某个类的概率是否高于xj。pr(xi,xj)表示xi和xj是否具有偏序关系r。偏序关系是一种满足以下基本属性的成对关系,这些属性是由任何超边连接的实体之间的关系确定的:0• 非自反性:非pr(xi,xi)。•非对称性:如果pr(xi,xj),则非pr(xj,xi)。•传递性:pr(xi,xj)和pr(xj,xk)蕴含pr(xi,xk)。0接下来,我们首先介绍如何构建和表示一个偏序超图。然后详细说明我们提出的偏序超图上的正则化学习方法。最后,我们分析其时间复杂度。03.1 构建和表示0为了共同表示实体之间的偏序关系和高阶关系,我们首先构建一个正常的超图,然后使用有向边连接具有任何偏序关系的顶点。请注意,两个顶点之间可能存在多条边,因为考虑了多个偏序关系。为了保证下游基于图的学习应用的效率,我们限制只有至少连接一个超边的顶点之间才存在有向边。这样的约束保证了从偏序关系构建的有向边的数量不会超过超图拉普拉斯矩阵中的非零条目数。因此,一个枚举所有有向边的学习算法不会增加计算超图拉普拉斯项的时间复杂度。如第2.1节所述,在构建超图之后,我们使用几个矩阵来表示它,例如关联矩阵H和超图拉普拉斯矩阵L。除了这些矩阵之外,我们还引入了一个偏序关系r的部分关联矩阵Hr∈RN×N来表示有向边。如图2所示,给定一个偏序关系r,我们首先构建一个二元关系矩阵Pr∈RN×N,其中Pr ij = 1,如果pr(xi,xj)为真。=P1 =R�r=1ar|Hr| {i,j�0}(1 − qr ( ˆyi, ˆyj))Hrij,(10)P =Rar|Hr|i,j�0sr ( ˆyi, ˆyj)Hrij,(11)15260图2:用于说明构建偏序超图矩阵表示的玩具示例。给定特征矩阵 X和偏序关系 r,我们分别构建超图的关联矩阵 H 和二元关系矩阵 Pr。然后我们从 H 生成共现矩阵 C,并将 C 和 P r进行逐元素乘积得到偏序关联矩阵 H r。根据超图的关联矩阵H,我们进一步构建共现矩阵 C ∈ R N × N,其中每个元素 C ij表示连接顶点 i 和 j 的超边数量。然后可以得到偏序关联矩阵 H r,0H r = P r ⊙ C, (7)0其中 ⊙ 表示逐元素矩阵乘法。在偏序关联矩阵中,非零条目 H r ij表示第 i 个和第 j 个顶点具有第 r 个偏序关系,并且它们同时由 H r ij个超边连接。换句话说,我们给通过更多超边连接的顶点对分配更高的权重,考虑到具有更高共现性的顶点对更重要。03.2 偏序超图学习0构建偏序超图后,我们有几个矩阵来表示它,包括描述传统超图的一般矩阵(例如,关联矩阵 H 和边权重矩阵W),以及用于建模偏序关系的特定偏序关联矩阵 {H r | r = 1, 2, ∙ ∙ ∙,R}。现在我们考虑如何将偏序关系和相应的逻辑规则扩展到方程(3)的学习框架中。一般来说,有两种解决方案——要么将规则注入到预测模型中(即 f(x)的定义),要么使用规则对学习进行正则化(即增加目标函数Γ)。第一种解决方案可能需要针对不同的预测模型(如逻辑回归、分解机 [15] 和神经网络[14])采用不同的方式来编码规则。因此,我们选择第二种解决方案,旨在提供一个通用的偏序超图学习方法。0偏序超图学习的解决方案是附加一个额外的正则化项P,用于编码偏序规则到目标函数中:0Γ = G + λL + βP, (8)0其中 β 是一个超参数,用于平衡 P 和其他两个项。与平滑正则化项G 类似,P也应该在预测标签空间上操作,以正则化学习过程。我们将 P定义为:0P 0 =0r = 1 a r E(i, j)�H r ij ≠ 0 1 - q r (ˆyi, ˆy j),0R个0a r|H r|0{i, j | H r ij ≠ 0} 1 - q r (ˆy i, ˆy j), (9)0其中 ˆy i = f(x i) 是 x i 的预测值,|H r| 表示 H r中非零条目的数量,a r 是超参数,用于控制第 r个偏序关系的逻辑规则的重要性。这个正则化项的核心思想是强制具有偏序关系的顶点的预测与相应的规则一致。具体而言,如果 q r (ˆyi, ˆy j) 等于 1,即 p r (x i, x j) 为真(由 H r ij ≠ 0 证明),且规则 pr (x i, x j) → q r (f(x i), f(x j)) 得到满足,那么可以实现 P 0的小值。然而,这个定义将偏序关系的所有顶点对待之为平等,没有考虑它们的相对强度。这个假设可能会降低实际应用中的建模准确性。为了解决这个问题,我们将正则化项修改为:0�0这个公式将 H r ij作为系数,用于重新调整顶点对的正则化强度。通过这样的公式,我们对通过更多超边连接的顶点对强制执行更强的偏序正则化。最后,为了摆脱离散优化中的困难,我们用连续函数 s r替换了二值逻辑函数 q r,并对其进行了近似。这种近似技巧可以实现稳定的优化,并且在概率软逻辑中被广泛使用[2]。这导致了我们提出的偏序正则化器的最终版本:0r = 10�0其中sr是一个针对不同问题可调整的自定义函数。例如,在排序问题中,sr 可能是预测排名ˆy i − ˆy j 的差值,而在分类问题中,s r可能是特定类别上预测概率之间的差距。03.2.1优化。通过最小化方程(8)的目标函数,我们可以得到在超图上平滑且满足偏序关系的预测函数。请注意,正则化项 L 和 P仅对预测的标签空间进行操作,不引入额外的模型参数。因此,我们只需要从预测模型 f (x ) 中学习模型参数。鉴于 f是可微的函数(例如,逻辑回归和神经网络),我们可以使用标准的基于梯度的方法(如随机梯度下降或批量梯度下降[12])来优化目标函数。此外,我们还可以直接学习 f ( x ),而不需要指定预测模型的显式形式。这将使预测函数在最大程度上符合正则化要求。我们将在第6节中通过实证研究来探讨这对下游应用的预测性能产生的影响。0Track: Web Search and Mining WWW 2018, 2018年4月23日至27日,法国里昂In this subsection, we analyze the time complexity of POH learningby comparing with conventional hypergraphs. As discussed in [21]and Section 2.2, the computational complexity of conventional hy-pergraph learning methods are O(J), where J denotes the numberof nonzero entries in the sparse hypergraph Laplacian matrix L.In contrast, the additional computational cost of our POH learn-ing comes from the construction of the partial incidence matrices{Hr|r = 1, 2, · · · ,R} and the partial-order regularization term P.To compute Hr, we need to obtain the co-occurrence matrix C first,and then evaluate the element-wise product C ⊙ Pr. For C, we canachieve it by traversing all nonzero entries on the incidence matrixH, for which the complexity is O(J). Then for each nonzero elementCij in C, we check whether pr (xi, xj) is true or not to obtain C⊙Pr.As such, the complexity of constructing a Hr is O(J), and the overallcomplexity of constructing all R partial incidence matrices is O(RJ).Similarly, the computation of P can be done in O(RJ) time. In areal-world application, the number of partial-order relations R istypically a small number, since we need to account for the mostprominent numerical or graded categorical features only. As such,the overall time complexity of our POH learning is essentially O(J),which is the same as that of conventional hypergraph learning.R�r=115270在本小节中,我们通过与传统超图的比较分析了POH学习的时间复杂度。如[21]和第2.2节所讨论的,传统超图学习方法的计算复杂度为O(J),其中J表示稀疏超图拉普拉斯矩阵L中非零元素的数量。相比之下,我们的POH学习的额外计算成本来自于部分关联矩阵{H r | r = 1 , 2 , ∙ ∙ ∙ ,R}的构建和偏序正则化项P的计算。要计算H r,我们首先需要获得共现矩阵C,然后计算元素级乘积C ⊙ P r。对于C,我们可以通过遍历关联矩阵H上的所有非零元素来实现,其复杂度为O(J)。然后对于C中的每个非零元素C ij ,我们检查p r ( x i , x j ) 是否为真,以获得C ⊙ P r 。因此,构建H r的复杂度为O(J),构建所有R个部分关联矩阵的总体复杂度为O(RJ)。类似地,计算P的复杂度为O(RJ)。在实际应用中,偏序关系的数量R通常是一个较小的数,因为我们只需要考虑最重要的数值或分级分类特征。因此,我们的POH学习的总体时间复杂度实质上是O(J),与传统超图学习的时间复杂度相同。03.3 时间复杂度分析04 相关工作0我们的工作与超图的最新研究直接相关,可以分为两个主要类别:超图构建和超图利用。自从在[48]中提出以来,研究人员一直非常关注如何构建超图。例如,Wang等人利用实体特征空间的稀疏表示生成超边,并学习超边与连接的顶点之间的关系。刘等人不仅仅学习了稀疏表示,还采用了弹性网络来调节表示学习。此外,Feng等人通过进一步鼓励不同超图表示之间的一致性,共同学习了多个超图的超图表示。然而,上述工作都没有能够在构建超图过程中纳入存在于分级分类特征和数值特征中的实体之间的偏序关系。它们因此导致了严重的信息损失,并限制了构建超图的表达能力。此外,超图和基于超图的学习已广泛应用于许多机器学习任务,包括聚类、嵌入、排名、半监督分类和回归。例如,[22]的作者构建了一个超图,表示新闻读者、新闻文章、主题和命名实体之间的相关性,然后进行排名。0利用超图来表示候选句子之间的关系,并进行基于图的提取式文档摘要。Yoshida和Yuichi使用超图来估计顶点的中介中心性和重要性。Huang等人构建了一个图像的超图,并使用基于超图的标签传播预测图像的属性。Tran等人构建了一个超图,其中顶点和超边分别表示特征和训练样本,以表示训练数据的稀疏模式。Hmimida和Kanawati描述了社交用户、资源和用户分配的资源标签之间的关系。然后,他们采用基于超图的排名来为资源推荐候选标签。这些文章表明了超图及其学习的流行性和可用性。然而,它们只使用了传统的超图,而没有同时改进传统超图的表示能力和相应的学习方法。05 大学排名0根据之前的工作[9],我们将大学排名问题定义为无监督排名(即重新排名)问题。给定 N 所大学的特征矩阵 X ∈ R N × M和历史排名结果 y ∈ R N,目标是学习一个新的排名 f ∈ RN。为了解决这个问题,我们手动选择了几个偏序关系,并构建了一个偏序超图(POH)来表示给定的大学。在构建的POH上,我们通过最小化POH学习目标函数的排名实例来学习f。具体而言,我们将方程(8)中的损失项设置为 L = ∥y -f∥2F,这鼓励学习到的排名与历史排名一致且平滑。此外,我们将软逻辑函数 { s r | r = 1, 2, ∙ ∙ ∙ , R } 设置为 s r ( f i , f j ) = f i - fj,即如果两个大学具有选定的偏序关系,则鼓励大学 i 排在大学 j之前。通过指定上述应用特定的术语,我们得到了该任务的目标函数,0Γ = f T Lf + λ ∥ f - y ∥ 2 F+ β0一个r | Hr |0{ i , j | H r ij ≠ 0 } ReLU (( f i − f j )H r ij ) , (12)0此外,我们还在偏序正则化项上使用了修正线性单元函数(ReLU)[13],以确保目标函数在稳定优化时为非负。05.1 实验设置05.1.1数据集。为了研究所提出方法的有效性,我们采用了由[9]收集的中国大学排名数据集。该数据集包含743所中国大学的数据,收集时间为2015年1月1日至2016年5月1日。对于每所大学,我们收集了来自五个渠道的网络数据,包括官方、大众媒体、学术、就业和普通用户渠道。官方渠道包含大学的主要信息,如学生质量、官方活动和发展计划。在大众媒体渠道中,我们收集了提及给定大学的新闻报道。学术和就业渠道分别包含大学的学术状况和研究生就业统计数据。普通用户渠道包含社交媒体帖子中分享的大学公众印象、态度和情感极性。为了描述大学,我们还使用了[9]作者提取的丰富特征集。在743所大学中,我们选择了中国的438所一流大学,因为它们有更多的学术和研究活动。对于历史排名结果y,我们合并了中国四个知名大学排名系统(CUAA、WSL、WH和iPIN)2015年的排名结果。排名的真实结果以相同的方式生成,但基于2016年四个系统的排名。因此,这个任务可以理解为使用去年的排名和今年的特征来预测今年大学的排名。我们将构建的历史排名结果和真实结果归一化到[0,1]范围内,通过将它们与1/N进行缩放。0Track: Web Search and Mining WWW 2018,2018年4月23日至27日,法国里昂user channel contains public impressions, attitudes, and sentimentpolarities of universities shared in social media posts. To describethe universities, we also employed the rich set of features extractedby the authors of [9]. Among the 743 universities, we selected 438top-tier ones in China1 since they have more academic and researchactivities. Towards the historical ranking result y, we merged theranking results in 2015 from four well-known ranking systems ofChinese universities, namely, CUAA, WSL, WH, and iPIN2. Theranking ground-truth is generated in the same way, but based onthe rankings of the four systems in the year 2016. As such, thetask can be understood as using the past year’s ranking and thisyear’s features to predict the ranking of universities in this year.We normalized the constructed historical ranking result and theground-truth into range [0, 1] by scaling them with 1/N.Simple Graph0.074 ± 9e-30.870 ± 2e-20.970 ± 8e-3Hypergraph0.067 ± 7e-30.876 ± 9e-30.974 ± 5e-3GMR0.065 ± 7e-30.871 ± 3e-20.970 ± 1e-2POH-Salary0.054 ± 1e-2∗0.892 ± 1e-2∗0.979 ± 5e-3∗POH-NCEE0.055 ± 1e-2∗0.893 ± 9e-3∗0.978 ± 5e-3∗POH-All0.0531e-2∗0.8981e-2∗∗0.9806e-3∗∗152805.1.2评估。我们进行了5折交叉验证,使用三个指标来评估排名性能:平均绝对误差(MAE)[41],肯德尔τ(Tau)[28]和斯皮尔曼等级(Rho)[34]。这三个指标被广泛用于评估点对点、对比和列表排序方法[25]。需要注意的是,较小的MAE、较大的Tau和Rho得分表明更好的性能。此外,我们进行了学生t检验,并在必要时报告了p值。05.1.3方法。我们与以下基线进行了比较4:•简单图[49]:它首先构建一个简单图来表示大学,其中两个顶点之间的边权重使用RBF核进行评估。我们将半径参数σ设置为所有配对的欧氏距离的中位数。然后,该方法通过最小化目标函数fL T f + λ ∥ y − f ∥ 2来计算拉普拉斯矩阵L,学习f。我们尝试了不同的λ值,并报告了最佳性能。•超图[3]:它首先计算大学之间的相似度,然后使用基于邻居的方法构建超图。具体而言,第i个超边连接与大学i最相似的k个大学。通过最小化方程(3)来进行f的学习。我们调整了两个超参数k和λ。•GMR[9]:这是大学排名任务的最先进方法。它从每个渠道的特征构建一个简单图,建模渠道之间的关系以达到对所有简单图的共识排名。我们使用了他们论文中报告的相同超参数设置。我们评估了几种在超图结构Hypergraph上融合不同偏序关系的POH方法:•POH-Salary:该方法考虑了薪资特征上的偏序关系。我们编码了逻辑规则salary > ( x i , x j ) → rank < ( x i , x j ),意味着如果x i的薪资特征高于x j ,那么x i 往往排名更高。01 在中国,大学被教育部正式分为三个层次(https://tinyurl.com/moe-univ-list/)。2CUAA: http://www.cuaa.net/cur/. WSL: http://edu.sina.com.cn/gaokao/wushulian/.WH: http://www.nseac.com/html/168/. iPIN:https://www.wmzy.com/api/rank/schList/. 3 注意,我们省略了像Precision@ K [ 6],Recall@ K [39]和NDCG@ K[29]这样的整体排序评估指标,因为它们对于选择K是敏感的。4注意,我们省略了第6.1.3节中提到的与TMALL和GCN的比较。因为[ 9]已经表明TMALL(类似于他们论文中的JL基线)比GMR效果差;GCN不适用于这个无监督排序任务,因为它是为半监督和监督任务设计的[21]。0表1:大学排名的性能比较。0方法 MAE Tau Rho0� 和 �� 表示相应的性能显著优于所有基线和其他所有方法( p -value < 0.05)。0• POH-NCEE :该方法考虑了NCEE特征上的偏序关系,NCEE代表大学对全国高考成绩的录取要求。要编码的逻辑规则自然地是 NCEE > ( x i , x j ) →rank < ( x i , x j),意味着NCEE分数较高的大学往往具有更好的质量。• POH-All :在这种方法中,我们同时建模了POH-Salary和POH-NCEE中编码的偏序关系。我们将两个规则的正则化器的重要性超参数分别设置为 a1 和 1 − a 1 。05.1.4超参数调优。我们采用网格搜索来选择POH方法的最佳超参数,基于Tau的结果。比较方法的最佳超参数设置和实现可以公开访问5。对于POH-Salary和POH-NCEE,我们调整了一个隐式超参数(k)和两个显式超参数(λ和β)。为了验证我们提出的POH相对于传统超图的优势,我们将k和λ设置为基线Hypergraph的最佳值,然后在[1e-4,1e1]范围内搜索β。对于POH-All,我们调整了另一个超参数a1,它控制逻辑规则的重要性,取值范围为[0,1]。注意,我们故意将k和λ固定为Hypergraph的最佳值,这也简化了调整过程。根据POH方法的性能进一步调整k和λ可以获得更好的性能(参见图4)。图3显示了POH-All相对于β和a1的性能。这是通过改变一个参数并将另一个参数固定为最佳值来完成的。可以看出,我们的方法对于超参数在其最佳设置附近是相当不敏感的。05.2 实验结果05.2.1方法比较。表1总结了大学排名的性能比较,从中我们得出以下观察结果:(1)Hypergraph的性能优于SimpleGraph,这验证了考虑大学之间的高阶关系对于排名任务是有效的。(2)所有基于POH的方法都比基线方法有很大的改进(例如,POH-All相对于GMR的改进分别为18.46%,3.10%和1.03%)。这证明了我们提出的POH和正则化学习在整合偏序关系方面的有效性。(3)POH-All优于POH-Salary和POH-NCEE。这进一步验证了基于POH的学习方法的优势,并反映了联合建模多个偏序关系和规则的帮助。(4)p值05 https://github.com/hennande/Partial_Order_Hypergraph0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, FranceTrack: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France15290图3:POH-All调整β和a1的过程。红色虚线标记了最佳设置。0图4:Hypergraph和POH-based方法在不同k下Tau性能的比较。0POH-based方法与其他所有方法之间的学生t检验的p值都小于0.05,表明性能改进的显著性。我们通过将一个顶点与其k个最近的顶点连接来构建超图,较大的k使得POH-based方法考虑更多具有给定偏序关系的顶点对(如果顶点对没有被任何超边连接,则会被排除)。因此,有趣的是看看k的设置如何影响POH学习的性能。图4显示了Hypergraph和我们的POH-based方法在不同k上的Tau性能。注意,其他超参数已经针对每个k的设置进行了公平调整。可以看到,所有的POH-based方法在所有设置上都优于Hypergraph。这表明所提出的POH学习方法在不考虑底层超图结构的情况下始终优于传统的超图方法。此外,所有的
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)