毕业设计（论文）文献翻译：通过点击链接型数据优化搜索引擎

1-文献翻译二级学院计算机科学与工程学院班级学生姓名学号通过点击链接型数据优化搜索引擎和ThorstenJoachims康奈尔大学计算机科学系伊萨卡，NY14853USAtj@摘要本文介绍的方法使用的点击，自动优化搜索引擎的检索质量数据。直观地说，一个良好的信息检索系统应高的排名目前相关文件，以较少的相关文件如下所示。虽然以前的方法示例学习检索功能存在，它们通常需要从关联生成训练数据判断通过专家评审。这使得它们困难和昂贵的应用。本文的目标是开发一个方法，它使用的点击数据进行训练，即在与连接在查询日志中的搜索引擎链接日志的用户在呈现的排名点击。这样的点击数据是可用的丰富性和可应以非常低的成本。以支持向量机（SVM）方法，本文提出的方法学习的检索功能。从理论的角度来看，这种方法证明是有理有据的风险最小化的框架。此外，它被证明是可行即使是大集的查询和功能。理论结果都在受控制的实验验证。这表明该方法能有效地适应的检索功能一个元搜索引擎一个定的用户群，后超越谷歌的检索质量方面的一几百训练实例。引言其中WWW网页（s）不用户实际想要检索的时候，他种了一些关键字在搜索引擎？通常有成千上万的包含这些页面话，但用户的爱好有一个更小的子集。人们可以简单地要求反馈给用户。如果我们知道了置的实际上相关的用户的查询页中，我们可以

以此作为训练数据优化（甚至个人化）的检索功能。不幸的是，经验表明，用户只有很少愿意给予明确的反馈。然而，本文认为有足够的信息已经隐藏在日志文件的WWW搜索引擎。由于各大搜索引擎获得每天数百万的查询，这样的数据是可用的丰盈。相比，显式反馈的数据，这是通常在引起费力用户研究，任何信息可以从日志文件中提取几乎是免费的并且基本上比较及时。本文提出了一种方法，通过分析其链接的用户点击的排名呈现学习的检索功能。这导致与学习的问题像“为查询Q，文档哒应该优先例子排在比文件高分贝“。更一般地，我会制定了一个学习排名函数的问题有限域的经验风险最小化的条件。为这一提法，我将提出一个支持向量机（SVM）算法，该算法导致的凸程序和可以扩展到非线性的排名函数。实验表明，该方法可以成功学习一种高度有效的检索功能的元搜索引擎。本文的结构如下。它开始与点击数据是什么，它如何被记录的定义，以及它如何能够被用来生成训练样本中偏好的形式。第三节然后介绍学习检索功能，导致一个总体框架一个SVM算法在学习参数化序第4节，第5节计算基于实验结果的方法。点击数据搜索发动机...在搜索引擎中的点击数据可以被认为是为三胞胎（Q，R，C）组成的查询q的，排名Ř呈现给用户，并且链接的集c中的用户点击上。图1显示了一个示例是：用户要求查询“支持向量机”，接收的排序如图1所示，然后点击的链接排1，3和7，由于每个查询对应于一个三重峰，数据是潜在可用金额几乎是无限的。显然，用户不会随意点击链接，但要一个（有点）知情选择。当点击数据通常嘈杂，点击次数并非“完美”的相关判断时，点击都有可能传达一些信息。该关键的问题是：如何将这些信息提取出来？之前导出的点击数据如何分析一个模型，让我们先考虑怎么能说是recorded.2。点击数据搜索发动机。3、记录点阅数据点击数据可被记录以小的开销并且不影响功能和usefulnessof的搜索引擎。特别是，相对于显式的用户反馈，它不添加任何开销的用户。该查询q和返回的排名r的很容易被记录每当得到的排名是显示给用户。为记录的点击，一个简单的代理系统可以保持一个日志文件。对本文中的实验，以下系统是使用。每个查询都分配了一个唯一的ID被存储在在与查询词的查询日志和呈现排名。呈现给用户的结果页面上的链接不要直接导致建议的文件，但点到代理服务器。这些链接进行编码的查询ID和建议的文档的URL。当用户点击该链接时，代理服务器会记录在点击日志URL和queryID。然后代理服务器使用HTTP位置命令给用户转发到目标URL。这过程可制成对用户透明的，并且不影响系统的性能。这表明点击数据可以很容易地被记录并以较小的代价。现在让我们来讨论如何在关键问题它可以在一个原则性的和有效的方式来分析。4、并点击链接型数据传达什么样的信息呢？有三个部分之间有很强的依赖关系（Q，R，C）。所呈现的排名Ř依赖于查询Q如通过在实施了检索功能来确定搜索引擎。此外，点击的链接的集合C取决于双方的查询q和所提出的排序河首先，用户更有可能点击一个链接，如果是相关的到q[16]。虽然这种依赖是可取的，有趣的进行分析时，点击的依赖性所呈现的排名ř模糊了水。特别是，用户是少可能点击的排名，独立的链路低它是如何相关的。在极端情况下，概率用户点击等级10.000的链接几乎为零即使是最相关的查询的文档。无用户向下滚动的排名远远不够遵守本链接。因此，为了获得可解释的和有意义的从点击数据的结果，有必要考虑和C型对q和r适当的依赖关系。在定义这样的模式，让我们首先考虑的点击数据的解释是不恰当的。一点击特定链接不能被看作是绝对的相关性判断。考虑表1中的经验数据。该数据是从[5]，并记录为搜索激光引擎覆盖的CMU学校的WWW计算机科学。该表显示的平均秩每个查询（例如，3.67的例子在图1中）的点击次数。每个表单元格中包含的平均clickrank为三大检索策略的平均值≈1400查询。平均clickrank是所有方法几乎相等。但是，根据主观的判断，这三个检索功能大致在不同的排名质量。缺乏中所观察到的平均clickrank差的可作如下解释。由于用户通常只扫描第一L（如L≈10[24]）排名的链接，点击链接不能被解释为一个绝对规模的相关性判断。也许一个文档中的排名要低得多名单是更相关，但用户永远不会看到它。它看来，用户点击（相对）最有前途在最上l链路，独立的绝对相关性。试问这些相对偏好判断被捕获并分析？再次考虑图1的例子中虽然不可能推断出链接1，3，和图7是在有关在绝对规模，这是更为合理的推断，连杆3比链节2的概率更高更相关不是随机的。假设用户扫描的排名由上到下，他必须观察到的链接2点击3，作出决定，不点击它。鉴于带有链接的摘要有足够的信息，这给一些指示用户的喜好。同样，有可能推断出连杆7是更相关比链节2，4，5，和6，这意味着点击数据不传达绝对的相关性判断，但部分相对相关性的判断，为用户浏览的链接通过。搜索引擎根据自己到q相关性排名的返回链接应该链接排名提前32，链路7提前2，4，5，和6。表示的排名通过随r的用户优选*，我们得到局部（和潜在的表格吵）信息。5、以前的结果表明，所学功能提高了检索。但到底是什么学到的功能看怎么样？它是合理和直观？由于支持向量机排行学习的线性函数，可以通过分析功能学习学到的权重。表3显示了权重的一些特征，尤其是那些具有最高绝对重量。粗略地讲，一个高的正（负）的权重表示，随着这些功能的文件应更高（更低）的排名。表3中的权重是合理的这组用户。由于许多查询是为科学材料，它似乎自然的从域“citeseer”的网址（和别名“NEC”）收到了积极的权重。最具影响力的权重进行查询之间的余弦匹配和抽象的，无论该URL是在排名前10位的谷歌，和查询，并在字与字之间的余弦匹配的URL。文档接收大量的负重量，如果是没有排名前1被任何搜索引擎，如果它没有进入前10任何搜索引擎（注意，第二蕴涵着一）如果URL是长。所有这些权重是合理的，意义直观。6，讨论及相关工作实验结果表明，该排名SVM就可以从点击数据成功学习一种改进的检索功能。没有任何明确的意见或手动参数整定，它会自动调整到一组≈20个用户的特定偏好。这种改进不仅验证了SVM的排名可以学习使用部分排名的反馈，同时也为个性化检索功能的参数。不同于传统的搜索有“适合”自己的检索功能，以大型发动机因此，用户由于成本异质群体手动调谐的，机器学习技术可以提高检索大幅剪裁的检索功能小而同质群体（甚至个人）无高昂的成本。虽然对学习检索功能以前的工作存在（例如，[10]），大多数方法需要明确的相关性判断。最密切相关的是巴特尔等的方法人。[2]。他们提出的混合物-的-专家算法线性最大化不同的等级相关标准相结合的排名专家。然而，在其安装它们依靠明确的相关性判断。类似的算法排名相结合，提出了由科恩等人。[6]。他们经验表明，理论上，他们的算法找到执行接近最佳的基本组合专家。Freund等人的boosting算法。[9]是一种方法，许多薄弱排名规则组合成一个强大的排名函数。虽然他们还（约）尽量减少反转的数目，他们并没有明确考虑分布在查询和目标排名。然而，他们的算法大概可以适应于设置考虑本文。从算法最密切相关的是Herbrich的支持向量机方法顺序回归等。[12]。但同样，他们认为不同的采样模型。在有序回归中的所有对象进行交互，他们是排在同一尺度。对于信息检索的排名问题，排名只需要内是一致的一个查询，但不查询之间。这使得排名问题较少的限制。例如，在排名问题两个文件二叔和DJ可以结束了在非常不同的居两个不同的查询qĶ和q升即使他们有完全相同的特征向量（即Φ（QĶ，二）=Φ（Q升，DJ））。一个优雅的感知类算法的顺序回归最近有人提出通过谎言和歌手[8]。一个有趣的问题是，是否这样的在线算法可以还可以用于解决连接到优化问题排名的支持向量机。一些已经尝试使用隐式反馈通过观察在检索系统中点击行为[5]和浏览助手[17][20]。然而，在语义学习过程及其结果目前还不清楚这表现在第2.2节。商业搜索引擎“直接命中”利用点击数据。确切的机制，然而，未公布。而为不同的问题，提出一种提出[3]有趣的应用点击数据。他们使用的点击数据，用以识别相关查询和URL。什么是对的点击数据训练SVM排名的计算要求？由于SVM光[15]解决了双重优化问题，它仅依赖于内特征向量Φ（Q，D）之间的产品。如果这些功能向量是稀疏如上，SVM光可以处理数以百万计功能有效。最具影响力的培训时间是约束在优化问题2的数量。然而，当使用的点击数据时，次数限制磅秤只线性地查询的数量，如果每个查询的点击次数的上界。其他应用程序，SVM光已经表明，它可以解决使用常规的问题，几百万的约束桌面计算机。然而，扩展到幅度在各大搜索引擎中找到的顺序是一个有趣的开放问题。6、结论和未来工作本文提出了一种方法来挖掘日志文件万维网搜索引擎与自动提高其检索性能的目的。关键的观点是，这样的点击数据可以提供训练数据的形式相对偏好的。基于对新配方学习信息检索问题，本文推导的算法学习排名函数。纵观支持向量机方法，由此产生的培训问题即使是大量的查询和大量要素的听话。实验结果表明，该算法表现出良好的实践，成功地适应一个元搜索引擎的喜好的检索功能一组用户的。本文将打开就使用了一系列的问题，机器学习的搜索引擎。什么是一个很好的大小一个用户组，以及如何才能确定这些群体？显然，训练数据的数量（即大组）和最大均匀性（即之间的权衡单用户）。是否有可能使用聚类算法来发现用户的同质群体？此外，可以点击数据还可以用来不能适应搜索引擎一组用户，而是一个特定的文档集合的属性？特别是，任何工厂设置现成的，现成检索系统必然是不理想的任何特定的集合。航运现成的，现成的搜索引擎与学习能力，使他们能够后自动优化（和维护）的表现被安装在一个公司内部网。然而，该算法不局限于在WWW上的元搜索引擎。有许多情况，其中学习的目的是基于一些参数的排名（如查询）。特别是，最推荐器的问题可以施放这种方式。在推荐者特别有趣设置是一个事实，即排名SVM可以训练与部分偏好数据。例如，考虑一个推荐系统，其目的是了解我的看电视的喜好。通过观察我的“频道冲浪”的行为时，系统可以推断这说明我更喜欢在其他程序在一个特定的时间。但是，这是一个相对偏好，没有偏好上的绝对规模。关于算法本身开放性问题的关注理论表征及其有效的执行。是有可能的基础上，以证明泛化界缘？或者，即使从实际的角度更有趣看，是能够分析多个进程在增量在线算法的意义学习/反馈步骤？如前论​​述，有一个依赖那些对于其呈现给用户的联系，并间系统接收反馈。这将是有趣的探索主动学习的思想，以优化这种反馈。在这种框架也可能是可能的机制探讨这使对“垃圾邮件”的算法的鲁棒性。它目前在多远的单个用户可以通过恶意反复点击影响排名的功能尚不清楚在特定的链接。关于解决算法最优化问题，这很可能是它们可以被进一步加速，由于约束条件具有一种特殊形式。在尤其是，网上的算法将是最合适的许多应用程序设置OptimizingSearchEnginesusingClickthroughDataThorstenJoachimsCornellUniversityDepartmentofComputerScienceIthaca,NY14853USAtj@ABSTRACTThispaperpresentsanapproachtoautomaticallyoptimizingtheretrievalqualityofsearchenginesusingclickthroughdata.Intuitively,agoodinformationretrievalsystemshouldpresentrelevantdocumentshighintheranking,withlessrelevantdocumentsfollowingbelow.Whilepreviousapproachestolearningretrievalfunctionsfromexamplesexist,theytypicallyrequiretrainingdatageneratedfromrelevancejudgmentsbyexperts.Thismakesthemdifficultandexpensivetoapply.Thegoalofthispaperistodevelopamethodthatutilizesclickthroughdatafortraining,namelythequery-logofthesearchengineinconnectionwiththelogoflinkstheusersclickedoninthepresentedranking.Suchclickthroughdataisavailableinabundanceandcanberecordedatverylowcost.TakingaSupportVectorMachine(SVM)approach,thispaperpresentsamethodforlearningretrievalfunctions.Fromatheoreticalperspective,thismethodisshowntobewell-foundedinariskminimizationframework.Furthermore,itisshowntobefeasibleevenforlargesetsofqueriesandfeatures.Thetheoreticalresultsareverifiedinacontrolledexperiment.Itshowsthatthemethodcaneffectivelyadapttheretrievalfunctionofameta-searchenginetoaparticulargroupofusers,outperformingGoogleintermsofretrievalqualityafteronlyacoupleofhundredtrainingexamples.1.INTRODUCTIONWhichWWWpage(s)doesauseractuallywanttoretrievewhenhetypessomekeywordsintoasearchengine?Therearetypicallythousandsofpagesthatcontainthesewords,buttheuserisinterestedinamuchsmallersubset.Onecouldsimplyasktheuserforfeedback.Ifweknewthesetofpagesactuallyrelevanttotheuser’squery,wecouldusethisastrainingdataforoptimizing(andevenpersonalizing)theretrievalfunction.Unfortunately,experienceshowsthatusersareonlyrarelywillingtogiveexplicitfeedback.However,thispaperarguesthatsufficientinformationisalreadyhiddeninthelogfilesofWWWsearchengines.SincemajorsearchenginesrePermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.SIGKDD02Edmonton,Alberta,CanadaCopyright2002ACM1-58113-567-X/02/0007...$5.00.ceivemillionsofqueriesperday,suchdataisavailableinabundance.Comparedtoexplicitfeedbackdata,whichistypicallyelicitedinlaborioususerstudies,anyinformationthatcanbeextractedfromlogfilesisvirtuallyfreeandsubstantiallymoretimely.Thispaperpresentsanapproachtolearningretrievalfunctionsbyanalyzingwhichlinkstheusersclickoninthepresentedranking.Thisleadstoaproblemoflearningwithpreferenceexampleslike”forqueryq,documentdashouldberankedhigherthandocumentdb”.Moregenerally,Iwillformulatetheproblemoflearningarankingfunctionoverafinitedomainintermsofempiricalriskminimization.Forthisformulation,IwillpresentaSupportVectorMachine(SVM)algorithmthatleadstoaconvexprogramandthatcanbeextendedtonon-linearrankingfunctions.Experimentsshowthatthemethodcansuccessfullylearnahighlyeffectiveretrievalfunctionforameta-searchengine.Thispaperisstructuredasfollows.Itstartswithadefinitionofwhatclickthroughdatais,howitcanberecorded,andhowitcanbeusedtogeneratetrainingexamplesintheformofpreferences.Section3thenintroducesageneralframeworkforlearningretrievalfunctions,leadingtoanSVMalgorithmforlearningparameterizedorderingsinSection4.Section5evaluatesthemethodbasedonexperimentalresults.2.CLICKTHROUGHDATAINSEARCHENGINESClickthroughdatainsearchenginescanbethoughtofastriplets(q,r,c)consistingofthequeryq,therankingrpresentedtotheuser,andthesetcoflinkstheuserclickedon.Figure1illustratesthiswithanexample:theuseraskedthequery“supportvectormachine”,receivedtherankingshowninFigure1,andthenclickedonthelinksranked1,3,and7.Sinceeveryquerycorrespondstoonetriplet,theamountofdatathatispotentiallyavailableisvirtuallyunlimited.Clearly,usersdonotclickonlinksatrandom,butmakea(somewhat)informedchoice.Whileclickthroughdataistypicallynoisyandclicksarenot“perfect”relevancejudgments,theclicksarelikelytoconveysomeinformation.Thekeyquestionis:howcanthisinformationbeextracted?Beforederivingamodelofhowclickthroughdatacanbeanalyzed,let’sfirstconsiderhowitcanberecorded.3、RecordingClickthroughDataClickthroughdatacanberecordedwithlittleoverheadandwithoutcompromisingthefunctionalityandusefulnessofthesearchengine.Inparticular,comparedtoexplicituserfeedback,itdoesnotaddanyoverheadfortheuser.Thequeryqandthereturnedrankingrcaneasilyberecordedwhenevertheresultingrankingisdisplayedtotheuser.Forrecordingtheclicks,asimpleproxysystemcankeepalogfile.Fortheexperimentsinthispaper,thefollowingsystemwasused.EachqueryisassignedauniqueIDwhichisstoredinthequery-logalongwiththequerywordsandthepresentedranking.Thelinksontheresultspresentedtotheuserdonotleaddirectlytothesuggesteddocument,butpointtoaproxyserver.Theselinksencodethequery-IDandtheURLofthesuggesteddocument.Whentheuserclicksonthelink,theproxy-serverrecordstheURLandthequeryIDintheclick-log.TheproxythenusestheHTTPLocationcommandtoforwardtheusertothetargetURL.Thisprocesscanbemadetransparenttotheuseranddoesnotinfluencesystemperformance.Thisshowsthatclickthroughdatacanberecordedeasilyandatlittlecost.Let’snowaddressthekeyquestionofhowitcanbeanalyzedinaprincipledandefficientway.4、WhatKindofInformationdoesClickthroughDataConvey?Therearestrongdependenciesbetweenthethreepartsof(q,r,c).Thepresentedrankingrdependsonthequeryqasdeterminedbytheretrievalfunctionimplementedinthesearchengine.Furthermore,thesetcofclicked-onlinksdependsonboththequeryqandthepresentedrankingr.First,auserismorelikelytoclickonalink,ifitisrelevanttoq[16].Whilethisdependencyisdesirableandinterestingforanalysis,thedependencyoftheclicksonthepresentedrankingrmuddiesthewater.Inparticular,auserislesslikelytoclickonalinklowintheranking,independentofhowrelevantitis.Intheextreme,theprobabilitythattheuserclicksonalinkatrank10.000isvirtuallyzeroevenifitisthedocumentmostrelevanttothequery.Nouserwillscrolldowntherankingfarenoughtoobservethislink.Therefore,inordertogetinterpretableandmeaningfulresultsfromclickthroughdata,itisnecessarytoconsiderandmodelthedependenciesofconqandrappropriately.Beforedefiningsuchamodel,let’sfirstconsideraninterpretationofclickthroughdatathatisnotappropriate.Aclickonaparticularlinkcannotbeseenasanabsoluterelevancejudgment.ConsidertheempiricaldatainTable1.Thedataistakenfrom[5]andwasrecordedforthesearchengineLASERcoveringtheWWWoftheCMUSchoolofComputerScience.Thetableshowstheaveragerankoftheclicksperquery(e.g.3.67intheexampleinFigure1).Eachtablecellcontainstheaverageclickrankforthreeretrievalstrategiesaveragedover≈1400queries.Theaverageclickrankisalmostequalforallmethods.However,accordingtosubjectivejudgments,thethreeretrievalfunctionsaresubstantiallydifferentintheirrankingquality.Thelackofdifferenceintheobservedaverageclickrankcanbeexplainedasfollows.Sinceuserstypicallyscanonlythefirstl(e.g.l≈10[24])linksoftheranking,clickingonalinkcannotbeinterpretedasarelevancejudgmentonanabsolutescale.Maybeadocumentrankedmuchlowerinthelistwasmuchmorerelevant,buttheuserneversawit.Itappearsthatusersclickonthe(relatively)mostpromisinglinksinthetopl,independentoftheirabsoluterelevance.Howcantheserelativepreferencejudgmentsbecapturedandanalyzed?ConsideragaintheexamplefromFigure1.Whileitisnotpossibletoinferthatthelinks1,3,and7arerelevantonanabsolutescale,itismuchmoreplausibletoinferthatlink3ismorerelevantthanlink2withprobabilityhigherthanrandom.Assumingthattheuserscannedtherankingfromtoptobottom,hemusthaveobservedlink2beforeclickingon3,makingadecisiontonotclickonit.Giventhattheabstractspresentedwiththelinksaresufficientlyinformative,thisgivessomeindicationoftheuser’spreferences.Similarly,itispossibletoinferthatlink7ismorerelevantthanlinks2,4,5,and6.Thismeansthatclickthroughdatadoesnotconveyabsoluterelevancejudgments,butpartialrelativerelevancejudgmentsforthelinkstheuserbrowsedthrough.Asearchenginerankingthereturnedlinksaccordingtotheirrelevancetoqshouldhaverankedlinks3aheadof2,andlink7aheadof2,4,5,and6.Denotingtherankingpreferredbytheuserwithr,wegetpartial(andpotentiallynoisy)informationoftheform5、AnalysisoftheLearnedFunctionThepreviousresultshowsthatthelearnedfunctionimprovesretrieval.Butwhatdoesthelearnedfunctionlooklike?Isitreasonableandintuitive?SincetheRankingSVMlearnsalinearfunction,onecananalyzethefunctionbystudyingthelearnedweights.Table3displaystheweightsofsomefeatures,inparticular,thosewiththehighestabsoluteweights.Roughlyspeaking,ahighpositive(negative)weightindicatesthatdocumentswiththesefeaturesshouldbehigher(lower)intheranking.TheweightsinTable3arereasonableforthisgroupofusers.Sincemanyquerieswereforscientificmaterial,itappearsnaturalthatURLsfromthedomain“citeseer”(andthealias“nec”)receivedpositiveweight.Themostinfluentialweightsareforthecosinematchbetweenqueryandabstract,whethertheURLisinthetop10fromGoogle,andforthecosinematchbetweenqueryandthewordsintheURL.Adocumentreceiveslargenegativeweights,ifitisnotrankedtop1byanysearchengine,ifitnotinthetop10ofanysearchengine(notethatthesecondimpliesthefirst),andiftheURLislong.Alltheseweightsarereasonableandmakesenseintuitively.ofmanualtuning,machinelearningtechniquescanimproveretrievalsubstantiallybytailoringtheretrievalfunctiontosmallandhomogenousgroups(orevenindividuals)withoutprohibitivecosts.Whilepreviousworkonlearningretrievalfunctionsexists(e.g.[10]),mostmethodsrequireexplicitrelevancejudgments.MostcloselyrelatedistheapproachofBartelletal.[2].Theypresentamixture-of-expertsalgorithmsforlinearlycombiningrankingexpertsbymaximizingadifferentrankcorrelationcriterion.However,intheirsetuptheyrelyonexplicitrelevancejudgments.AsimilaralgorithmforcombiningrankingswasproposedbyCohenatal.[6].Theyshowempiricallyandtheoreticallythattheiralgorithmfindsacombinationthatperformsclosetothebestofthebasicexperts.TheboostingalgorithmofFreundetal.[9]isanapproachtocombiningmanyweakrankingrulesintoastrongrankingfunctions.Whiletheyalso(approximately)minimizethenumberofinversions,theydonotexplicitlyconsideradistributionoverqueriesandtargetrankings.However,theiralgorithmcanprobablybeadaptedtothesettingconsideredinthispaper.AlgorithmicallymostcloselyrelatedistheSVMapproachtoordinalregressionbyHerbrichetal.[12].But,again,theyconsideradifferentsamplingmodel.Inordinalregressionallobjectsinteractandtheyarerankedonthesamescale.Fortherankingproblemininformationretrieval,rankingsneedtobeconsistentonlywithinaquery,butnotbetweenqueries.Thismakestherankingproblemlessconstrained.Forexample,intherankingproblemtwodocumentsdianddjcanendupatverydifferentranksfortwodifferentqueriesqkandq。Anelegantperceptron-likealgorithmforordinalregressionwasrecentlyproposedbyCrammerandSinger[8].AninterestingquestioniswhethersuchanonlinealgorithmcanalsobeusedtosolvetheoptimizationproblemconnectedtotheRankingSVM.Someattemptshavebeenmadetouseimplicitfeedbackbyobservingclickingbehaviorinretrievalsystems[5]andbrowsingassistants[17][20].However,thesemanticsofthelearningprocessanditsresultsareunclearasdemonstratedinSection2.2.Thecommercialsearchengine“DirectHit”makesuseofclickthroughdata.Theprecisemechanism,however,isunpublished.Whileforadifferentproblem,aninterestinguseofclickthroughdatawasproposedin[3].TheyuseclickthroughdataforidentifyingrelatedqueriesandURLs.WhatarethecomputationaldemandsoftrainingtheRankingSVMonclickthroughdata?SinceSVMlight[15]solvesthedualoptimizationproblem,itdependsonlyoninnerproductsbetweenfeaturevectorsΦ(q,d).Ifthesefeaturevectorsaresparseasabove,SVMlightcanhandlemillionsoffeaturesefficiently.MostinfluentialonthetrainingtimeisthenumberofconstraintsinOptimizationProblem2.However,whenusingclickthroughdata,thenumberofconstraintsscalesonlylinearlywiththenumberofqueries,ifthenumberofclicksperqueryisupperbounded.Inotherapplications,SVMlighthasalreadyshowedthatitcansolveproblemswithseveralmillionsofconstraintsusingaregulardesktopcomputer.However,scalingtotheorderofmagnitudefoundinmajorsearchenginesisaninterestingopenproblem.6.CONCLUSIONSANDFUTUREWORKThispaperpresentedanapproachtomininglogfilesofWWWsearchengineswiththegoalofimprovingtheirretrievalperformanceautomatically.Thekeyinsightisthatsuchclickthroughdatacanprovidetrainingdataintheformofrelativepreferences.Basedonanewformulationofthelearningproblemininformationretrieval,thispaperderivesanalgorithmforlearningarankingfunction.TakingaSupportVectorapproach,theresultingtrainingproblemistractableevenforlargenumbersofqueriesandlargenumbersoffeatures.Experimentalresultsshowthatthealgorithmperformswellinpractice,successfullyadaptingtheretrievalfunctionofameta-searchenginetothepreferencesofagroupofusers.Thispaperopensaseriesofquestionregardingtheusemachinelearninginsearchengines.Whatisagoodsizeofausergroupandhowcansuchgroupsbedetermined?Clearly,thereisatrade-offbetweentheamountoftrainingdata(ie.largegroup)andmaximumhomogeneity(ie.singleuser).Isitpossibletouseclusteringalgorithmstofindhomogenousgroupsofusers?Furthermore,canclickthroughdataalsobeusedtoadaptasearchenginenottoagroupofusers,buttothepropertiesofaparticulardocumentcollection?Inparticular,thefactory-settingsofanyoff-the-shelfretrievalsystemarenecessarilysuboptimalforanyparticularcollection.Shippingoff-the-shelfsearchengineswithlearningcapabilitieswouldenablethemtooptimize(andmaintain)theirperformanceautomaticallyafterbeinginstalledinacompanyintranet.However,thealgorithmisnotlimitedtometa-searchenginesontheWWW.Therearemanysituationswherethegoaloflearningisarankingbasedonsomeparameter(e.g.query).Inparticular,mostrecommenderproblemscanbecastinthisway.ParticularlyinterestingintherecommendersettingisthefactthattheRankingSVMcanbetrainedwithpartialpreferencedata.Forexample,considerarecommendersystemthataimstolearnmyTVwatchingpreferences.Byobservingmy“channelsurfing”behavior,thesystemcaninferwhichshowsIpreferoverotherprogramsataparticulartime.Butagain,thisisarelativepreference,notapreferenceonanabsolutescale.Openquestionsregardingthealgorithmitselfconcernitstheoreticalcharacterizationanditsefficientimplementation.Isitpossibletoprovegeneralizationboundsbasedonthemargin?Or,evenmoreinterestingfromapracticalpointofview,isitpossibletoanalyzetheprocessofmultiplelearning/feedbackstepsinthesenseofanincrementalonlinealgorithm?Aselaboratedbefore,thereisadependencebetweenthelinkspresentedtotheuser,andthoseforwhichthesystemreceivesfeedback.Itwouldbeinterestingtoexploreactivelearningideastooptimizethisfeedback.Inthisframeworkitmightalsobepossibletoexploremechanismsthatmakethealgorithmrobustagainst“spamming”.Itiscurrentlynotclearinhowfarasingleusercouldmaliciouslyinfluencetherankingfunctionbyrepeatedlyclickingonparticularlinks.Regardingalgorithmsforsolvingtheoptimizationproblem,itseemslikelythattheycanbefurtherspedup,sincetheconstraintshaveaspecialform.Inparticular,onlinealgorithmswouldbemostappropriateinmanyapplicationsettings译文要求1、译文内容必须与课题（或专业）内容相关，并需注明详细出处。2、外文翻译译文不少于2000字；外文参考资料阅读量至少3篇（相当于10万外文字符以上）。3、译文原文（或复印件）应附在译文后备查。译文评阅导师评语（应根据学校“译文要求”，对学生外文翻译的准确性、翻译数量以及译文的文字表述情况等作具体的评价）指导教师：年月日浅析SocketSocket是一个网络编程接口,可以适用于不同的网络协议。Windows环境下使用的Socket称为WindowsSocket,简称为Winsock。一般的网络通讯采用客户/服务器模型,在这种模型中客户应用程序向服务器程序请求服务,这种方式隐含了在建立客户机/服务器间通讯时的非对称性。使用Socket时,也使用客户机/服务器的概念,但是这些概念主要用在面向连接通讯建立网络链路时,好区别出请求连接和接受连接的两端。在建立了连接虚电路后,网络两端是对等的实体,客户机和服务器的区分也就不重要了,两端对等地进行数据通讯。TCP/IP协议分析TCP/IP协议是一个应用于Internet的非常重要的协议族,它包括IP协议、TCP协议、UDP协议、ICMP协议等。对应于ISO(InternationalStandardOrganization)组织制定的OSI(OpenSystemInterconnection)网络模型,IP协议是应用于网络层的负责将信息从一个网络设备传送到另外一个网络设备;而TCP协议是应用于传输层的,这层的作用是在会话层和网络层之间提供信息(数据)传输服务,并校验以确保信息成功到达目标设备。与TCP协议相对应的是UDP协议,这也是一个应用于传输层的协议,与TCP协议不同的是该协议是无连接的协议。尽管TCP和UDP都使用相同的网络层（IP），TCP却向应用层提供与UDP完全不同的服务，TCP提供一种面向连接的、可靠的字节流服务。面向连接意味着两个使用TCP的应用（通常是一个客户和一个服务器）在彼此交换数据之前必须先建立一个TCP连接。这一过程与打电话很相似，先拨号振铃，等待对方摘机说“喂”，然后才说明是谁。在一个TCP连接中，仅有两方进行彼此通信，广播和多播不能用于TCP。TCP通过下列方式来提供可靠性：1.应用数据被分割成TCP认为最适合发送的数据块。这和UDP完全不同，应用程序产生的数据报长度将保持不变。由TCP传递给IP的信息单位称为报文段或段（segment）TCP如何确定报文段的长度。2.当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段。3.当TCP收到发自TCP连接另一端的数据，它将发送一个确认。这个确认不是立即发送，通常将推迟几分之一秒。4.TCP将保持它首部和数据的检验和。这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错，TCP将丢弃这个报文段和不确认收到此报文段（希望发端超时并重发）。既然TCP报文段作为IP数据报来传输，而IP数据报的到达可能会失序，因此TCP报文段的到达也可能会失序。如果必要，TCP将对收到的数据进行重新排序，将收到的数据以正确的顺序交给应用层。TCP连接三层握手过程TCP是因特网中的传输层协议，使用三次握手协议建立连接。当主动方发出SYN连接请求后，等待对方回答SYN，ACK。这种建立连接的方法可以防止产生错误的连接，TCP使用的流量控制协议是可变大小的滑动窗口协议。第一次握手：建立连接时，客户端发送SYN包(SEQ=x)到服务器，并进入SYN_SEND状态，等待服务器确认。第二次握手：服务器收到SYN包，必须确认客户的SYN(ACK=x+1),同时自己也送一个SYN包(SEQ=y),即SYN+ACK包，此时服务器进入SYN_RECV状态。第三次握手：客户端收到服务器的SYN+ACK包，向服务器发送确认包ACK(ACK=y+1)，此包发送完毕，客户端和服务器时入Established状态，完成三次握手。进程标识—端口号传输层和网络层在功能上的最大区别是:前者提供进程通讯能力,后者不提供进程通讯能力。在进程间通讯的意义上,网络通讯的最终地址就不仅仅是主机地址,还包括描述通讯进程的一种标识符。为此,TCP/UDP提出了协议端口的概念,用于标识通讯的进程,端口也就是进程访问网络传输服务的入口点。Internet中全局地标识一个本地进程需要一个三元组:协议,本地地址,本地端口号。而一个完整的Internet进程通讯实例是由通讯两端的各一个进程组成,因此需要一个五元组来标识:协议,本地地址,本地端口号,远地地址,远地端口号。这里的本地地址、远地地址是用来标识计算机的,一般是指计算机的IP地址。协议族是指确定一组相关的协议族,如TCP/IP协议族。因为Socket接口可以在多个网络上通讯,除了可以使用Internet上的TCP/IP协议,还可以使用UNIX系统上的内部协议和Xerox网络服务等。Socket类型参数Socket类型参数一般是指明程序将Socket用于字节流传输还是数据报传输,也就是使用面向连接或使用无连接的网络通讯,因为在面向连接通讯中,数据按照一个没有边界的字节流(stream)传输;而在无连接网络通讯中,数据按照称为数据报的独立的自包含数据包(datagram)形式流动。因此事实上这个参数是指明使用的通讯服务类型。如何使用Socket连接？在使用面向连接的协议时,相当于在连接端点之间建立了一个虚电路。也就是说,在两个端点之间的链路看起来像直接的点到点的连接。因此在使用面向连接的程序中(如使用TCP协议),服务器段程序的Socket要先进入一种状态,而客户端程序的Socket要使用函数connect()来请求连接服务器端程序,如果服务器端的Socket接收到请求,可以同意这个请求(使用accept()函数),这样就可以在两端之间建立一个通讯虚电路了。程序配置好一个Socket后,就可以用它来进行网络通讯。网络通讯包括发送和接收两部分。Socket接口提供了函数来完成这两个功能,对于BereleySocketAPI提供了10个函数来传输数据(5个用于发送,5个用于接收),Winsock则使用4个函数来完成功能(2个用于发送,2个用于接受)。这些函数可以分为两组,其中一组是应用于面向连接的Socket,它们在函数参数中不要求提供目的Socket的地址(因为已经建立了连接,通讯双方都知道了彼此的地址);而另外一组则要求在函数参数中提供目的Socket的地址,这组函数使用于无连接的Socket。现在网络的应用越来越广泛,对程序员来讲,设计编制网络通讯程序是一个必然趋势,因此了解网络(尤其是Internet)的协议模型结构,了解网络程序设计必要的基础知识,对程序员适应社会的发展是非常有帮助的。参考文献：[1]K.L.Calvert,M.JDonhahoo.TCP/IPSocketinJava:PracticalGuideforProgrammers.MorganKaufman.2001.[2]CharlesM.Kozierok.TheTCP/IPGuide:AComprehensive,IllustratedInternetProtocolsReference.2008.[3]UsingtheSocketsAPI．/index.php/%E4%BD%BF%E7%94%A8Socket_API.

原文：AnalysisonTheSocketSocketisanetworkprogramminginterface,whichcanbeappliedtodifferentnetworkprotocol.WindowsenvironmentuseSocketcalledWindowsSocket,referredtoasWinsock.Thegeneralnetworkcommunicationwithclient/servermodel,inthismodeltheclientapplicationserverprogramtorequestservice,thiswayinestablishingimpliestheclient/servercommunicationbetweentheasymmetry.UseSocket,alsouseclient/serverconcept,butthesemajorconceptinconnectionwithtobuildupanetworkcommunicationlink,adistinctionbetweengoodconnectionandaccepttherequestatbothends