人工智能原理-北京大学-10--PartVLearningChapter10TasksinMac-(

ArtificialIntelligence6810.1.Classification10.2.Regression10.3.Clustering10.4.Ranking10.5.DimensionalityReductionContents:10.TasksinMachineLearningSchoolofElectronicandComputerEngineeringPekingUniversityWangWenminRankingArtificialIntelligence::Learning::Tasks70Alongerdescription较长描述Arankingisarelationshipbetweenasetofitemssuchthat,foranytwoitems,thefirstiseither‘rankedhigherthan’,‘rankedlowerthan’or‘rankedequalto’thesecond.排名是一组项之间的关系，即对于任意两个项，满足第一个“排名高于”、“排名低于”或“排名等于”第二个。Ashorterdescription较短描述Thedatatransformationinwhichnumericalorordinalvaluesarereplacedbytheirrank.排名是一种数据转换，其中数值或者顺序值由其排名来代替。Averyshortdescription极简描述Toorderitemsaccordingtosomecriterion.依据某种准则整理数据项。WhatisRanking什么是排名10.4.RankingArtificialIntelligence7110.4.1.HowRankingWorks10.4.2.MajorApproachesofRanking10.4.3.ApplicationsandAlgorithmsContents:10.4.RankingArtificialIntelligence::Learning::Tasks72LetXdenoteinputspace,DanunknowndistributionoverX×X.设X表示输入空间，D是X×X上的未知分布。Targetrankingfunction:目标排名函数：AFormalDescriptionofRanking一种排名的形式化描述10.4.1.HowRankingWorksf∶X×X→Y={−1,0,+1}S={(x(i),x’(i),y(j))|y(j)=f(x(i),x’(i))∈Y,i∈[1,m],j∈[1,3]}Trainingdata:训练数据wheref(x,x’)=+1,ifxisrankedhigherthanx’,f(x,x’)=−1,ifxisrankedlowerthanx’,f(x,x’)=0,ifbothxandx’hassameranking.其中若x排名高于x’，若x排名低于x’，若x与x’二者排名相同。ArtificialIntelligence::Learning::Tasks73Rankingproblem:排名问题GivenahypothesissetHoffunctionsmappingX×XtoY={−1,0,+1},toselectahypothesish∈Hwiththetargetfunctionf:给定一个将X×X映射到Y={−1,0,+1}的假设函数集H，选择一个具有目标函数f的假设h∈H：smallexpectedgeneralizationerror:最小预期泛化错误：AFormalDescriptionofRanking一种排名的形式化描述10.4.1.HowRankingWorks෠𝑅(h)=1𝑚෍𝑖=1𝑚1((𝑦(𝑖)≠0)∧(𝑦(𝑖)(h(𝑥′(𝑖))−h(𝑥(𝑖)))≤0)))R(h)=Pr(x,x’)[f(x,x’)≠0∧(f(x,x’)(h(x’)−h(x))≤0)]empiricalpairwisemisrankingerror:经验性成对误排名错误：ArtificialIntelligence7410.4.1.HowRankingWorks10.4.2.MajorApproachesofRanking10.4.3.ApplicationsandAlgorithmsContents:10.4.RankingArtificialIntelligence::Learning::Tasks751)Score-basedapproach基于分值方法Thepredictorisareal-valuedfunction,calledscoringfunction.该预测器是一个实数函数，称为分值函数。Thescoresassignedtoinputpointsbythisfunctiondeterminetheirranking.由该函数分派给输入数据点的分值决定其排名。Thisapproachisthemostwidelyexploredone.这种方法是研究得最多的一种。2)Preference-basedapproach基于偏好方法Thepredictorisapreferencefunction.该预测器是一个偏好函数。TypicalApproachesofRanking典型的排名方法10.4.2.MajorApproachesofRankingArtificialIntelligence7610.4.1.HowRankingWorks10.4.2.MajorApproachesofRanking10.4.3.ApplicationsandAlgorithmsContents:10.4.RankingArtificialIntelligence::Learning::Tasks77IninformationretrievalSearchengineDocumentretrievalCollaborativefilteringSentimentanalysisComputationaladvertisingInotherareasMachinetranslationRecommendersystemsComputationalbiologyProteomicsTypicalApplicationsofRanking排名的典型应用10.4.3.ApplicationsandAlgorithms信息检索领域搜索引擎文档检索协同式过滤情感分析计算广告学其它领域机器翻译推荐系统计算生物学蛋白质组学ArtificialIntelligence::Learning::Tasks78AnalgorithmusedbyGoogletorankwebsitesintheirsearchengine,namedafterLarryPage,oneofGooglefounders.谷歌用于在其搜索引擎中对网站进行排名的一种算法，以谷歌创始人之一拉里·佩奇的名字命名。CaseStudy:PageRank10.4.3.ApplicationsandAlgorithmsPageRankworksbycountingthenumberandqualityoflinkstoapagetodeterminehowimportantthewebsiteis.PageRank通过计算网页的链接数量和质量来决定该网站的重要性。Theunderlyingassumptionisthatmoreimportantwebsitesarelikelytoreceivemorelinksfromotherwebsites.其基本假设是：越重要的网站，就会被越多其它网站所链接。