排序测度的直接优化

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
网页排序和协同过滤需要优化复杂的性能度量。目前的支持向量方法不能直接优化它们，而是侧重于两两比较。我们提出了一种新的方法，它允许直接优化相关的损失函数。这是通过Hilbert空间中的结构化估计来实现的。与最大边际马尔可夫网络优化多变量性能指标关系最密切。该方法的关键在于，在训练过程中，排序问题可以看作是一个线性分配问题，可以用匈牙利婚姻算法求解。在测试时，一个排序操作就足够了，因为我们的算法为每个（文档、查询）对分配一个相关性分数。实验表明，该算法速度快，效果良好。
---
英文标题：
《Direct Optimization of Ranking Measures》
---
作者：
Quoc Le and Alexander Smola
---
最新提交年份：
2007
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Information Retrieval        信息检索
分类描述：Covers indexing, dictionaries, retrieval, content and analysis. Roughly includes material in ACM Subject Classes H.3.0, H.3.1, H.3.2, H.3.3, and H.3.4.
涵盖索引，字典，检索，内容和分析。大致包括ACM主题课程H.3.0、H.3.1、H.3.2、H.3.3和H.3.4中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  Web page ranking and collaborative filtering require the optimization of sophisticated performance measures. Current Support Vector approaches are unable to optimize them directly and focus on pairwise comparisons instead. We present a new approach which allows direct optimization of the relevant loss functions. This is achieved via structured estimation in Hilbert spaces. It is most related to Max-Margin-Markov networks optimization of multivariate performance measures. Key to our approach is that during training the ranking problem can be viewed as a linear assignment problem, which can be solved by the Hungarian Marriage algorithm. At test time, a sort operation is sufficient, as our algorithm assigns a relevance score to every (document, query) pair. Experiments show that the our algorithm is fast and that it works very well.
---
PDF下载：
--> English_Paper.pdf (299.43 KB)

2022-4-15 09:58:09 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Optimization Intelligence Presentation Multivariate performance

排名的直接优化MeasuresQuoc v.Le*和Alex J.Smola 2008年2月5日AbstractWeb页面排名和协作配置需要优化复杂的性能指标。目前的支持向量方法不能直接优化它们，而是侧重于两两比较。我们提出了一种新的方法，通过Hilbert空间中的结构化估计来直接优化相关的损失函数。其中与多变量性能测度的MaxMargy-Markov网络优化最为相关。我们的方法的关键在于，在训练过程中，排序问题可以被看作是一个线性分配问题，可以用匈牙利婚姻算法来解决。在测试时，sortoperation是su-cient，因为我们的算法为每个（文档、查询）对分配一个相关性分数。实验表明，本文提出的算法速度快，效果好。1.介绍排名，特别是网页排名，一直是机器学习领域的一个研究热点。现在人们普遍认为，排序可以被看作是一个有监督的学习问题，比单独使用一个特征具有更好的性能[Burges et al.，2005，Caoet al.，2006]。学习排名可以被看作是学习数据（例如网页）排序的尝试。虽然理想情况下，人们可能希望有一个学习所有匹配web页面的分区排序的ranker，但用户最关心的是系统返回的最高（部分）结果。例如，参见[Cao et al.，2006]的讨论。这在信息检索中发展的相应的性能度量中表现出来，如归一化贴现累积增益(NDCG)、平均倒数秩(MRR)、精度@n或期望秩效用(ERU)。它们被用来解决评估者、搜索引擎或推荐系统的问题[Voorhees,2001,Jarvelin和Kekalainen,2002,Breese et al.,1998,Basilico和Hofmann,2004]。从矢量空间模型[Salton，1971,Salton and McGill,1983]开始，人们提出了各种基于特征的方法[Lee et al.，1997]。流行的特性集包括BM25[Robertson et al.，1994]或其变体[Robertson and Hull，2000]。遵循理查森等人的意图。[2006]表明，将这些方法与机器学习相结合，可以显著提高ranker的性能。在过去的十年里，人们提出了许多机器学习方法。序数回归[Herbrich et al.，2000,Chu and Keerthi，2005]使用类似SVM的大边界方法和神经网络[Burges et al.，2005]是一些常见的方法。紧随其后的是感知器[Crammer and Singer，2002]和在线方法，如[Crammer and Singer，2005，Basilico and Hofmann，2004]。最先进的技术基本上是描述部分*quoc.le@tuebingen.mpg.de，马克斯·普朗克生物控制论研究所，SPEMANNSTR。38,72076 t-Ubingen,Germanize@alex.smola@NICTA.com.au,统计机器学习程序，NICTA和ANU,Canberra,2600 ACT,Australiaa通过一个有向无环图排序，并将错误排序引起的成本与该图的边相关联。这些方法的目的是在已注册的文档上找到最佳的排序函数。然而，在这一框架中表达复杂的（但常用的）度量是不可取的，直到最近才有两篇理论论文[Rudin,2006,Cossock和Zhang,2006]讨论了学习排名优先于得分最高的文档的问题。然而，[Rudin，2006]中的成本函数与评估管理者绩效时使用的成本函数仅有模糊的联系。

[Cossock and Zhang,2006]认为，在大样本的限制下，标签上的回归可能是可行的。我们的工作使用支持向量机的结构化输出框架[Tsochantaridis et al.，2005，Joachims，2005，Taskar et al.，2004]来处理排序中性能度量固有的非凸性。由于内核方法中固有的容量控制，SIT很好地推广到测试观测[Schéolkopf和Smola，2002]。我们提出的优化问题非常普遍：它以一种即插即用的方式涵盖了广泛的现有标准。它扩展到位置相关的排序和基于多样性的得分。特别相关的是最近的两篇论文[Joachims，2005，Burges et al.，2007]解决了信息检索损失函数的复杂性。更为具体的是，[Joachims，2005]表明，两个与排序相关的分数，精度@n和ROC曲线下的面积，可以通过使用结构化输出支持向量机（SVMStruct）来优化。我们在算法中使用类似的策略，利用[Tsochantaridis et al.，2005]中提出的不等式来获得排序度量的直接优化（DORM）。[Burges et al.，2007]在没有凸松弛的情况下考虑了一个类似的问题，相反，他们直接通过处理凸成本函数的梯度来优化凸成本函数。概述：在对结构化估计的总结之后，我们讨论了信息检索中的性能度量（第3节），并将它们表示为内积。在第4节中，我们计算了性能准则的凸松弛，并说明了如何利用线性赋值来求解它。在web搜索和协作搜索上的实验表明，DORM是快速的，并且工作良好。2结构化估计在下面，我们将开发一种方法，通过某种函数g(d，q)来对隶属于q的对象（如文档d）进行排序。显然，我们希望确保高度相关的文档将具有较高的分数，即较大的G值。同时，我们要保证得到的排序相对于相关排序得分是最优的。对于instancefor NDCG@10，即只有10个检索到的文档很重要的分数，如果分数g将给高度无关的页面分配什么特定值并不非常重要，只要它们保持在接受阈值以下。显然，我们可以使用工程技术来构造一个合理的函数（PageRank就是这样一个函数的例子）。然而，我们也可以使用统计和机器学习来指导我们找到一个为此目的优化的函数。这就产生了一种更优化的方法来定义这样一个函数，而不需要经过深思熟虑的猜测。weuse的特殊工具是最大边际结构估计，正如Tsochantaridis等人所描述的那样。[2005]。关于更详细的讨论见原始参考文献。2.1问题解决大裕度结构估计，由[Taskar et al.，2004，Tsochantaridis et al.，2005]提出，是通过筛选相关的优化问题来解决映射X→Z的估计问题的一般策略。更具体地说，它解决了从给定模式x∈x的（结构化的）估计集合中，通过对函数f(x，Z)进行修正，从而使Z*(x):=argmaxz∈ZF(x，Z)成为一个匹配gz∈Z的估计问题，这类函数f(x，Z):=argmaxz∈ZF(x，Z):f(x，Z):f(x，Z):f(x，Z):f(x，Z):f(x，Z):f(x，Z)。（1）这意味着不是直接定义映射X→Z，而是将问题简化为定义X×Z上的实值函数。在排序情况下，X∈X对应于一组具有相应查询的文档，而Z对应于对文档进行排序以使最相关的文档被排序的置换。因此f将是一个函数的文档，查询，anda排列。然后我们的目标是找出这样一个f，使其为“正确的”排列最大化。为了评估估计z*(x)表现得有多好，我们需要引入一个损失函数(y，z)，这取决于z和一些参考标签y，它决定了z的损失。

例如，如果我们要解决二元分类问题y,z∈{±1}，其中y是观察标号，z是估计值，我们可以选择Δ(y,z)=1-δy,z。也就是说，如果我们犯了一个错误，我们会招致1的惩罚，而如果我们估计y=z，则不会招致惩罚。在回归的情况下，这可能是(y,z)=(y-z)。最后，在序列注释的情况下，y和z都是二进制序列，[Taskar et al.，2004，Tsochantaridis et al.，2005]使用Hamming损失。在我们将在第3节中讨论的排序案例中，损失@将对应于以次优方式对WTA、MRR、DCG、NDCG、ERU或类似标准进行排序的文件所产生的关系。总之，我们的目标是构造一个函数f来最小化f对观察值X={X,...,xm}和参考标签y={y,...,ym}remp[f,X,y]:=mxi=1(yi,argmaxz∈ZF(xi,z))的aset引起的误差。（2）我们将REMP[f,X,Y]称为经验风险。后者关于f的直接极小化是一个高度非凸优化问题。对于经验风险remp[f,X,Y]而言，良好的性能并不能在一个看不见的测试集上得到良好的性能。在实践中，经验风险的严格最小化实际上确保了测试集的糟糕性能，这是由于过度配置造成的。这个问题在机器学习文献中已经被广泛地讨论过（参见[Vapnik，1982])。为了处理第二个问题，我们将在经验风险中添加一个正则化项（这里是二次惩罚）。为了解决这个问题，我们将计算损失的一个凸上界(yi，)，Argmaxz∈ZF(xi,2.2凸上界我们利用一个关键不等式得到了损失最小化问题的凸上界引理1设f:X×z→R和:Y×z→R且设z∈z。在此情况下，如果ζ满足f(X，z)-f(X，z)≥(Y，z)-(Y，z)-(Y，z)-ζ对于所有的z∈X，则ζ≥(Y，argmaxz∈Zf(X，z))-(Y，z).此外，对ζ和f的约束是线性的，证明线性是明显的，因为ζ和f只是作为单独的项出现。为了查看声明，用z*(x):=argmaxz∈ZF(x，z)表示。由于这个不等式需要对所有z成立，所以它对z*(x)尤其成立。这意味着0≥f(x，z)-f(x，z*(x))≥ut(y，z*(x))-ut(y，z)-ζ。通过构造z*(x)这个不等式成立。重排证明索赔。通常，选择zto为z的最小值，并假定损失为zvanish，在这种情况下，ζ≥(z*)。注意，这个凸上界对于z=z*是紧的，如果满足这个不等式的极小ζ是选择的。2.3核。得到凸优化问题的最后一个成分是f的一个合适的函数类。原则上，任何类，如决策树、神经网络、Boosting中出现的弱学习者的凸组合等，都是可以接受的。为方便起见，我们选择f viaf(x，z)=hΦ(x，z)，wi。（3）这里Φ(x，z)是特征映射，w是相应的权向量。这一公式的优点是通过选择直接映射Φ，可以很好地结合先验知识。此外，可以用核函数SK((x，z),(x，z))=Φ(x，z),Φ(x，z)(4)来表示所产生的优化和估计问题，而不需要显式求Φ(x，z)。这使得我们可以在保持优化问题的数量参数的同时，处理informnite-dimensionalfeature空间。此外，我们可以通过保持kwk su_ciently小来控制f的复杂度（对于二进制分类，这相当于大的边距分类）。用z的zithe值表示，对于该值，θ(yi，z)是最小的。

此外，设C>0为Gularization常数，指定经验风险最小化与求一个“简单”函数F之间的交易。结合(2)、引理1和（3）得到如下优化问题:minimizew，ζkwk+cmxi=1ζi(5a)服从hw，Φ(xi，zi)-Φ(xi，z)i≥(yi，z)-ζi(5b)对于所有ζi≥0和z∈z和i∈{1,...,m}。在排序情况下，我们假定（在不丧失一般性的情况下）文档是按相关性递减的顺序进行排序的。在这种情况下，zi将对应于保持文档顺序不变的单位排列。2.4优化可以表明[Taskar et al.，2004](5)的解是由f(x，z)=x，zαizk((x，z)，(x，z))给出的。（6）算法1列生成输入：数据十一、标签易，样本量m,公差初始化所有i的si=,且w=0。重复i=1 to m dow=pipz∈SiαizΦ(xi,z)z==argmaxz∈zhw,Φ(xi，z)i+(yi，z)ζ=max(0,maxz∈sihw,Φ(xi，z)i+(yi，z))如果hw,Φ(xi，z^)i+(yi，z)>ζ只使用αIz来增加约束集sièsiz^优化（7）,其中z∈si.end ifend直到在这个迭代中S没有改变，这一事实也通常被称为表示定理[Schéolkopf和Smola,2002]。通过求解（5）的对偶优化问题得到了结论:α-Iz:α-xi,j,z,zαizαjzk((xi,z）,(xj,z))-xi,z(yi，z)αiz(7a)主题toxzαIz≤C,αIz≥0。(7b)解决优化问题（7）是一个艰巨的挑战。特别是，对于largeZ（例如，在一组文档上的所有排列的空间）来说，变量的数量大得令人望而却步，而且在实际时间内基本上不可能找到最优解。相反，可以使用列生成[Tsochantaridis et al.，2005]在多项式时间内获得近似解。其中的关键思想是检查约束(5b)，以找出当前参数集违反了哪些约束，并使用这些信息来提高优化问题的值。也就是说，我们需要对gmaxz∈z(yi，z)+hw，Φ(xi，z)i，(8)，因为这是约束(5b)变得最紧的项。如果Z是一个小的值集，这最好通过强力计算来实现。对于二进制序列，通常使用动态编程。在排序的情况下，其中Z是置换空间，我们可以看到（8）可以转化为线性分配问题。算法1具有良好的收敛性。根据[Tsochantaridis et al.，2005]，它在最多添加2n\\\\\\/之后终止，8c}r/步，式中，“}”是损失“}”的上界，z）和R是KΦ(xi，z)上的一个上界，为了使上述框架适应排名设置，我们需要解决三个问题：a）我们需要导出一个损失函数来进行排序，b）我们需要开发一个适当的特征图Φ，它考虑到文档集合、查询和排列，以及c）我们需要找到一个算法来解决(8)e_ciently.3排序和丢失函数3.1 e_ciently的正式描述，商业排名者、搜索引擎或推荐系统通常采用一次一个文档的方法来回答查询q：通过评估变量意义=(q,D）文档-查询对的相关性来评估候选文档列表（同时保留n个得分最高的文档堆）。..,dili}文档的qirij∈[0,....,rmax]相关文档dijyi={ri1,...,rili}引用labelf（x,π)全局评分函数（qi,dij）个体评分函数m用于训练的查询数a（文档，查询）-pari一次一个。为此，需要一个评分函数g(d，q)，它为给定查询的每个文档分配一个评分。评分器的性能通常通过一组标签y:={r,...,rl},其中RI∈[0,....,rmax],其中0对应于“不相关”,rmax对应于“高度相关”。

训练实例containdocument由专家标记的查询对。对于商业搜索引擎或推荐系统来说，这样的数据通常只有不到十个层次的相关性。在训练时，我们给出了m个查询的实例qi，文档集合Diof cardinalityli，并用yi=di标记yi。在上一节的上下文中，一组文档diincomposition和一个匹配查询qi将扮演模式的角色，即xi:=(qi,diq,...,dili）。同样，文档dij的相应专家评级的引用标签rij∈yiconsist。我们希望找到一些映射f，以便对一个新的documentsd集合进行排序。.。，通过排序g(di，q)与y在预期中符合得很好。与[Matveeva et al.，2006]不同，我们希望获得一个对给定性能度量的查询表现良好的单个排序。注意，还有一个与排序文档相关联的处理步骤：对于每个文档查询对(d，q)，我们必须构造一个特征向量x。本文假定特征向量是给定的，并用(d，q)表示x。例如BM25[Robertson et al.，1994,Robertson and Hull,2000]、date、click-through logs[Joachims，2002]已经被证明是一组完备的特征。基于排列的方法是指通过比较两组排序来计算性能度量。例如，\'winnertakes all\'(WTA)、平均倒数秩(MRR)[Voorhees，2001]、平均平均精度(MAP)和归一化折现累积增益(NDCG)[Jarvelin and Kekalainen，2002]都充分利用了这一特性。我们将删除参数D，q，g，只要上下文清楚。另外，给定一个向量v∈Rmwe用v(π)表示v按π的排列，即v(π)i=vπ(i)。最后，在不丧失一般性的情况下（为了方便表示），我们假设y按降序排序，即最相关的文档。也就是说，相同的置换π=1将对应于相对于引用标签返回最相关文档的排序。同样地，我们将用π来表示所有排列的空间（即Z=π)。对于计算的e-ciency（不是出于理论上的原因），不希望f联合依赖于{d,....,dl}。3.2分数和输者全取(WTA)：如果firefrst文档相关，即如果y(π)=r，则分数为1，否则为0。我们可以重写asWTA(π，y)=ha(π)，b(y)i(9)，其中ai=δ(i,1）和bi=δ(ri,r）。注意，可能有不止一个文档被认为是相关的。在这种情况下，WTA(π，y)对于几类排列将是最大的。平均倒数秩(MRR)：我们假设只有一个顶级排序文档。我们有Emrr(π,y)=ha(π),b(y)i(10),其中ai=1/i和bi=δ(i,1）。换句话说，倒数秩是分配给文档d的秩的逆，文档d是最相关的文档。MRR的名字来源于这样一个事实，即这个数量在几个查询中的典型平均。贴现累积增益（DCG和DCG@n):WTA和MRR只使用π的一个条目，即π(1)来评估排名的质量。贴现累积量是一个更平衡的分数:DCG(π，y)=ha(π)，b(y)i(11)，其中AI=1/log(i+1)和BI=2RI-1。在这里，如果检索到的相关文档排名较高，则会支付费用，因为COE_Cients AI-1是单调递减的。不考虑所有等级的DCG变体是DCG@n。这里，如果i≤n，ai=1/log(i+1)，否则ai=0。也就是说，我们只关心排名靠前的n个条目。

在搜索引擎中，截断级别n通常是10，因为这构成了搜索的第一页上返回的点击数。归一化贴现累积增益(NDCG)：DCG的缺点是它的数值范围取决于y（例如。一个包含许多相关文档的集合在最优情况下会产生比只包含无关文档的集合大得多的值）。因为y已经排序了，所以对于身份置换π=1:NDCG(π，y):=DCG(π,y)DCG(1，y)(12)和ndcg@n(π,y):=DCG@n(π,y)ndcg@n(1，y)。这使得我们可以得到cg(π,y)=ha(π),b(y)i(13),其中ai=log(i+1)和bi=ri-1dcg(1，y)。最后，本文重点讨论的测度ndcg@n由ha(π),b(y)i给出，其中ai=(log(i+1),如果i≤n0,bi=ri-1 DCG@n(1，y)。（14）精度@n:注意，这个测度也可以用ha(π),b(y)i表示。在这里，我们定义ai=(1/n，如果i≤n0其他，bi=(1，如果ricorrect0其他，15)对NDCG的主要作用是精度@n没有衰减因子，相等地权衡topn的答案。预期秩效用：它在排名靠前的项中有指数衰减，它可以被表示为u(π，y)=ha(π)，b(y)i(16)，其中ai=21-iα-1和bi=max(Ri-d，0)，这里d是中性投票，α是观看hal-ife。归一化的ERU也可以以类似于NDCG的方式进行填充。（规范化的）ERU经常用于推荐系统的协作筛选，其中项目列表通常非常短。人们普遍认为NDCG@N是一个人对搜索引擎的判断的良好模型：关于页面的结果，它们之间应该有一个衰减因子。NDCG的另一个优点是它比WTA和MRR更结构化和更通用。对于协作和内容筛选，ERU更受欢迎[Breese et al.，1998，Basilico andHofmann，2004]。由于我们开始设计一个损失函数，如第2.1节所述，我们现在对ha(π)，b(y)I形式的任何分数所引起的损失进行分析。为了方便起见，我们（再次）假定π=1是最优置换:(y，π):=ha(1)，b(y)I-HA(π)，b(y)i。（17）3.3评分函数在我们的问题设置中的步骤是求出一个适当的函数f(x，π)（其中x=(q，D))，它对于“最优”排列是最大的。正如第3.1节所述，我们需要一个函数(d，q)，它将在测试时独立地为每个（文档，查询）对分配一个相关性分数。Polya-Littlewood-Hardy不等式告诉我们，在给定G的情况下，如何得到一个合适的类函数f：定理2设a，b∈Rn，设π∈π。而且，假设a按denceingorder排序。因此，如果对于递减序列c，f（x,π)=xig（di,q)c(π)i(18)，则f的最大值将是由g（di,q)分配的按相关顺序递减排序的文档的最大值。当涉及到设计特征映射Φ(x，π)时，展开式（18）也起到指导作用，该特征映射将把所有文档di、queryq和置换π共同映射到特征空间中。更重要的是，它只需要将分解重新定义为与单个对（di,q）相关的项。3.4一般位置Dep endent损失在我们通过定义一个合适的特征映射来解决排序问题之前，让我们考虑一下在我们的框架中能够处理的最一般的情况。假设我们给出了文档{d,....,dl}的排序π，我们将损失定义为(π,y):=lxi,jπijcij(y)+const。（19）也就是说，对于每一个位置j，我们都有一个成本Cij(y)，它是由将文档i放置在位置j而引起的。显然（17）属于这一类：只需选择cij=aib(y)j。例如，wemight有一个网页排名问题，其中figurrst位置应该包含来自ZF相关网站的结果，第二页应该包含来自用户创建网站的相关页面，等等。

换句话说，这种设置将适用于在rankedlist中的特定位置被赋予特定意义的情况。然而，这种过程的问题是，估计和优化比仅仅排序相关性得分列表的成本更高：我们希望为每个位置设置一个di-heverentscoring函数。换句话说，计算成本大大增加了，无论是从计算元素得分所需的函数数目方面，还是从寻找使损失最小化的置换所需的优化方面。4学习排名4.1特征现在我们在（18）的ansatz上展开。由（3）给出的内积f(x，π)=hΦ(x，π)，wi的线性性要求我们能够将Φ写为Φ(x，π)=lxi=1c(π)iφ(di，q)，其中c∈Rm。（20）在这种情况下，hw，Φ(D，q，π)i=hc(π)，pii，其中pi=hw，φ(di，q)i。选择φ(di，q)的问题最终取决于数据，因为我们通常不知道文档和查询是由什么数据类型组成的。我们将在第6节的实验中讨论几种选择。（20）表明f为f(x，π)=hΦ(x，π),wi=lxi=1c(π)ihφ(di，q),wi。（21）因此，我们可以应用Polya-Littlewood-Hardy不等式，并观察到通过对项Hφ(di，q)，wi按递减顺序排序而使其最大化。注意，通过在O（l log l）时间内应用QuickSort可以很容易地获得这种排列。为了只获得n个顶级项，wecan做得更好，并且只需要花费O(l+n，logn)时间，使用快速排序风格的分叉和征服过程，这就留下了选择C的问题。一般而言，我们希望选择这样一种方法：a）使（5）的边际最大化；b）使平均长度KΦ(x，π)Ki小，以便具有良好的推广性和快速的实现收敛性。由于Φ在c中是线性的，我们可以使用核优化技术来获得c的最优值，如[Bousquet and Herrmann,2002,Ong et al.，2003]中所提出的。在更一般的情况下，例如位置的二次依赖，虽然可能，但通常会导致在多项式时间内无法解决的优化问题。原理不是不可能的，这不可避免地导致一个高度约束（最坏情况下是半定）的c和W的优化问题。针对这一更为普遍的问题，获得一个e-cient算法是当前研究的主题。我们在第6节中给出了c的最优选择的实验结果。上述推理有助于将第2节中所述的优化问题应用于排序问题。与一般情况相比，所有的变化都是对损失函数的选择和特征映射Φ(x，π)的选择。为了获得一个e-cient优化算法，我们需要克服最后一个障碍：我们需要在（8）中找到一个e-cient算法，用于发现constraintviolators。4.2发现违反的constraintsrecorn(8)。在排序的上下文中，这意味着我们需要构造置换π，其中maximizeshΦ(x，π),wi+(y，π)=lxi=1hφ(di，q),wic(π)i+ha(1)，b(y)i-ha(π),b(y)i(22)=hc(π),gi-ha(π),b(y)i+const。（23）其中gi=hφ(di，q)，wi。注意，(23)是一个所谓的线性指派问题，可以用匈牙利联姻法：三次Kuhn-Munkres算法求解。最大化（23）等于解argmaxπ∈πmxi=1ci，πi，其中cij=cjgi-ajbi。（24）注意有一个特例，其中问题（8）可以通过一个简单的排序操作来解决：每当a=c时，问题归结为最大化ha(π)，G-b(y)i。然而，这种选择并不总是可取的，因为a可能是相当退化的（即。

4.3求解线性指派问题众所周知，将pici，πii极大化为一个线性问题存在凸松弛，从而得到一个最优解。最大πtrπ>C(25)主题xiπij=1和xjπij=1和πij∈0,1}。更详细地说，由于约束矩阵是随机单模的，可以通过将积分约束πij∈0,1}替换为πij≥0而不改变解来松弛整线性规划。因此可行多面体的顶点是积分的，因此解也是积分的。对偶是Minimizeu、VXIUI+visubject到UI+VI≥CIJ。（26）线性指派问题的求解是一个研究得很好的课题。最初的论文byKuhn[1955]和Munkres[1957]暗示了一个在时间数上具有O(l)代价的算法。后来，Karp[1980]提出了一个期望二次时间为算法2大小的算法，直接优化排序度量输入：文档集合Di,查询qi,秩yi,样本量m,公差初始化si=é对所有i,w=0.repeatfori=1 to m dow=pipπ∈SiαiπΦ(xi,π)π=argmaxπ∈hw,Φ(xi,π)i+(π,yi)ζ=max(0,maxπ∈Si)hw,Φ(xi,π)i+(π,yi)>ζ,则仅使用αiπ增加约束集sièsiíππ优化（7）,其中π∈Si。在此迭代指派问题中，直到S没有改变（忽略对数因子）。最后，Orlin和Lee[1993]提出了求解大型问题的线性时间算法。由于在我们的例子中页面数量相当少（大约50到200)，我们使用了Jonker和Volgenant[1987]的现有实现。有关运行时详细信息，请参见6.3。后者使用现代技术来计算（26）中出现的shortestpath问题，这意味着我们可以检查特定的文档集和相关查询(Di，qi)是否满足结构化估计问题（5）的不等式约束。因此，我们有必要的子程序，使第2节的算法工作。特别是，这是我们在SVMStruct中唯一需要替换的子程序[Tsochantaridis et al.，2005]。4.4简单地说，在描述实验之前，让我们总结一下算法的总体结构。完全类比于(5)，原始优化问题可以说为最小化，ζkwk+cmxi=1ζi(27a)服从hw,Φ(xi，1)-Φ(xi，π)i≥(yi，π)-ζi≥i∈{1,....,m}(27b)。（5）的对偶问题是对所有i和π最小化αxi，j，π，π∈παiπαjπk((xi，π),(xj，π))-xi，πππ(yi，π)αiπ(28a)服从xπ∈παiπ≤C和αiπ≥0。(28b)该问题由算法2求解。最后，对一个测试集上的文档按g(d，q)=hw,φ(d，q)i进行排序，其中w=pi,παiπΦ(xi，π)。5扩展5.1多样性限制在以下情况下：当搜索“乔丹”时，我们会发现许多包含该主题信息的相关网页。他们将涵盖一个大范围的主题，如abasketball运动员（迈克乔丹），一个国家（约旦王国），一条河（在中东），一个电视节目（穿越约旦），一个科学家（迈克乔丹），一个城市（在明尼苏达州和犹他州），以及更多。显然，为用户提供不同的引用组合是可取的，而不是只提供来自同一站点、域或主题范围的多个页面。实现这一目标的一种方法是在Beranked项之间包含一个交互项。这就导致了形式最小化π∈πxijklπijπklcij，kl(29)的优化问题，其中cij，kl将编码项之间的相互作用。这显然是不可取的，因为上述类型的问题不能在多项式时间内解决。然而，我们可以采取一种更简单的方法，在实践中获得同样好的性能，而不会产生指数级的代价。

这种方法非常适合于只考虑前n个文档的评分排序。我们将要求在前n个检索的文件中不超过其中一个可能来自同一个来源（例如，主题，领域，子领域，个人主页）。尽管如此，我们还是想在这个条件下尽量减少分数。在形式上，我们想构造一个矩阵π∈{0,1}l×n，使得xi,jπijaib(y)j(30)是最大的，但对所有j∈{1,n}(31)xjxi∈bsπij≤1,对所有bs的约束是xiπij=1。（32）这里形成{1,...l}分区的不相交集BS，对应于不能同时检索的文档（或网页）的子集。例如，在上面的示例中，从域http://www.jordan.govo"ece.com检索的所有网页将被集中到一个集BS中。另一个集合Bsp将覆盖，例如http：//www.cs.berkeley.edu/éjordan/上的所有网页。在训练过程中，我们需要解决一个最大πtrπ>C(33a)的优化问题，其中π∈{0,1}l×n,xjxi∈bsπij≤1,且xjxi∈bsπij≤1。(33b)我们将在下面证明（33）的约束矩阵是完全么模的。这意味着对约束集进行线性规划松弛，即从πij∈{0,1}到πij∈[0,1]的变化将使问题的解保持不变。定理3（Heller和Tompkins[1956])如果任意列中出现的非零项不超过两个，且它的行可以划分成两个集，则aij∈0,±1}的整数矩阵A是完全单模的。如果一列有两个相同符号的条目，则它们的行在独立的集合中；2。如果一列有两个双正负号项，则它们的行在同一集合中。推论4（33）的线性规划松弛有一个积分解。我们所需要证明的是，在(33b)中，每个项πijonly在coe cient1中正好出现两次。由于Bsis是一个包含{1,....,l}的分区，它解释了一个事件，而赋值约束则解释了另一个事件。现在定理3适用。注意，我们可以通过要求topicspijπijwis≤1上的加权组合进一步扩展它，这里的权值wisis可能是非积分的，并且wisis非零的域可能重叠。在这种情况下，优化问题显然不能再放松了。然而，当与整数编程代码结合使用时，它仍然会提供有用的结果，如Bonmin[Bonami et al.，2005]。最后，请注意，在测试阶段，很容易考虑约束条件(33b)：简单地从每个集合中挑选排名最高的文档，然后使用后者获得整体排名。5.2排名矩阵分解我们的框架的一个明显应用是用于协作配置的矩阵分解。Srebro和Shraibman[2005]，Rennie和Srebro[2005]，Srebro等人的工作。[2005b]建议正则化矩阵分解是一个很好的工具，用于建模协同设计应用程序。更重要的是，Srebro和他的同事假设他们得到了一个稀疏的matrixX，这个matrixX是由协作筛选产生的，他们希望对其进行分解。更具体地说，条目xij表示用户i对document/movie/object j的评分。假定Thematrix X∈RM×NIS是稀疏的，其中零个条目对应于尚未排序的（用户、对象）对。目标是对一对矩阵U，V进行筛选，使得UV>对于所有非零项都接近于X。或者更具体地，这样条目[uv>]ijcan可以用来推荐额外的对象。然而，这可能不是一个理想的方法，因为它是完全不相关的，例如，只要我们能够准确地捕捉用户对理想对象（大Xij）的偏好，我们对不理想对象（小Xij）的评级就完全不相关。换句话说，我们希望对用户的喜欢进行建模，而不是对他的不喜欢进行建模。