网络搜索-填补信息断层课件

WebSearch:

FillingtheInformationGapYanyanLan(兰艳艳)WebDataScienceandEngineeringResearchCenter,InstituteofComputingTechnology,CASAboutOurTeamWebDataScienceandEngineeringResearchCenter,ICTLabHeadResearcher:XueqiCheng(程学旗)ResearchDepartment(XiaolongJin(靳小龙),JiafengGuo(郭嘉丰)):WebSearchandDataMining(WSDM)YanyanLan(兰艳艳)NetworkAnalysisandSocialComputing(NASC)HuaweiShen(沈华伟)ResearchPlatform(Soscholar天玑学术网)LeiCao(曹雷)GroupofWSDMGroupofResearchPlatformBigdataresearchplatformVerticalCollaborativeSystemAnalysisEngineSocialEngineSearchEngineRecommendationEngineLearningtorankQueryrefinementNamedisambiguationLearningtorecommendCollaborativefilteringHeterogeneousnetworkmining……WebSearch:FillingtheInformationGapWebSearchmachinelearningToday’sTopicsPartI:QueryUnderstandingandRepresentationPartII:RankingAlgorithmsandTheories查询UserSearchEngine=“BlackBox”QueryUnderstandingandRepresentationDifferentlevelsofUnderstandingTaskRepresentationStructure[MichaelJordan:PersonName][Berkeley:Location]MJordanBerkeleMichaelJordanBerkeleyInterestsUtilityPerceivedUtility+PosteriorUtilitySearchInterests+ExplortaryInterestsUnderstandthegoalofthequery(Sequence)Understandthesemanticsofthequery(Single)MichaelJordan~MichaelJordanBerkeleyMichaelJordan~NBAMichaelJordanMichaelJordanBerkeley~NBAMichaelJordanIntent:NBAstarIntent:academicresearcherUnderstandthesimilaritybetweenqueries(Pair)Q:MJordanBerkele×SIGIR’08，SIGIR’09CIKM’11CIKM’10，CIKM’12UnderstandingtheRelation:

Intent-AwareQuerySimilarity（CIKM’11）

BestPaperAwardMotivationApplesearchintent:lookingforapplefruitssearchintent:findproductsoftheapplecompanyAppletreeApplestoreSimilaritybetweenqueriesdefineduponsearchintentIntent-awarequerysimilarityExistingMethodsIntent-Not-AwareIntent-AwarePare-wiseMeasuresGraph-basedMeasuresIndependentmeasuredoneachpairPropagatesimilarityoverqueryrelationgraphJaccardcoefficient[Beefermanetal.2000]cosinesimilarity[Baeza-Yatesetal.2004;Wenetal.2002]Hybridmethods[Zhangetal.2006;Jonesetal.2006]Jaccard&cosine[Dengetal.2009]Kernelmethod[Sahamietal.2006]Randomwalk[Craswelletal.2007]hittingtime[Meietal.2008]SimRank[Antonellisetal.2008]MatrixFactorization[Maetal.2008]GraphProjection[Bordinoetal.2010]Problem:MixedrepresentationBiasedbypopularintentIgnoreunpopularonesProblem:PropagateacrosstheboundaryWronglyconnectqueriesfromdifferentsearchintentsAppleAppletreeApplestoreAppletreeApplestore~~Apple~/OverviewA.

IdentifythepotentialsearchintentofqueriesI.Extractintent-awarerepresentationsII.ApplydifferenttypesofsimilaritymeasuresB.Intent-awaresimilaritymeasureA.IdentifySearchIntents(Algorithm)RegularizedTopicModeltopsearchresultsnippetsvirtualdocumentswordsinsnippetswordspotentialsearchintentstopicsPLSImodellog-likelihoodTopicModelRegularizationtwoqueriessharemanysameclickedURLsconveysimilarsearchintentco-clickmatrixSearchresultsnippetsClickthroughpowerfulconstraint:B.Intent-AwareSimilarityMeasure(Pair-wise)Similarityindependentlymeasuredbypair-wisemetricsI.Extractintent-awarerepresentationswordvectorrepresentationoriginal:intent-aware:expectedsearchintentdistributionforeachwordoccurrencewlgivenqueryqiwordvectorrepresentationunderk-thsearchintentII.ApplyPair-wisesimilaritymeasuressimilarityunderk-thsearchintentResultExpectedinter-intraratioPartII:RankingAggregatione.g.DiversityOutputaperfectrankingfrommultiplerankinginputConsideringtherelationbetweenitemsRankingaccordingtothedegreeofrelevanceDifferentlevelsofRankingSIGIR’12，CIKM’12,NIPS’12ICDM’11，TKDE’11UAI’12RelevanceRanking(Algorithm):

Top-kLearningtoRank:Labeling,RankingandEvaluation(SIGIR’12)

BestStudentPaperAwardACentralProbleminLTRHowtoobtainreliabletrainingdata?Motivation：userstudyDowereallyneedtogetatotalorderingforeachqueryorlearningwiththat?Usersmainlycareaboutthetopresultsinrealwebsearchapplication!NO!Takemoreefforttofigureoutthetopresultsandjudgethepreferenceordersamongthem.Morefocusedontheorderingsofthetopresults.Top-KGround-truth

TotalorderingoftopKresultsPreferencesbetweentopKDocumentsandtheotherN-KdocumentsWefindthattop-kissufficientforranking!Motivation:empiricalstudyCIKM’13:Istop-kSufficientforRanking?Wefindthattop-kissufficientforranking!Lossfunctionintop-ksettingisaupperboundofevaluationmeasurebasederrorLossfunctionintop-ksettingisalowerboundoflossfunctioninfull-ordersettingMotivation:theoreticalstudyCIKM’13:Istop-kSufficientforRanking?Top-kLearningtoRankFrameworkThreeTasks:Howtodesignanefficientlabelingstrategytogettop-kground-truth?Howtodevelopmorepowerfulrankingalgorithmsinthenewscenario?Howtodefinenewevaluationmeasuresforthenewscenario?Top-kLearningtoRank:LabelingPairwisePreferenceJudgment

PreferenceOrder

HeapSortTop-kLearningtoRank：LabelingExample:k=3,n=5

Top-3Ground-truthStep1Step2Step3O(nlogk)O(k)O((n-k)logk)O(klogk)Top-kLearningtoRank:RankingNewcharacteristicsoftop-kground-truth

TotalorderingoftopkitemsPreferencesbetweentopkItemsandtheothern-kitemsListiwiserankingalgorithmsPairwiserankingalgorithmsFocusedRankStruct-SVMAdaRankListNetRankSVMRankBoostRankNetFocusedSVMFocusedBoostFocusedNetTop-kEvaluationMeasure

ExperimentIEffectivenessandefficiencyoftop-klabelingstrategyDataSets:allthe50queriesfromTopicDistillationtaskofTREC2003,foreachquery,sample50documents.LabelingTools:top-10labelingtoolT1andfive-gradedrelevancejudgmenttoolT2.Assessors:Fivegraduatestudentswhoarefamiliarwithwebsearch.Assignment:DividedintofivefoldsQ1,…Q5,UijudgesQiwithT1andQi+1withT2,fori=1,2,3,4,andU5judgesQ5withT1andQ1withT2.ResultsITimeEfficiencyAgreementTop10Labeling5GradedLabelingExperimentsIIPerformanceofFocusedRankBaselines:PairwiseAlgorithms:RankSVM,RankBoost,RankNet,ListwiseAlgorithms:SVMMAP,AdaRank,ListNet,Top-kAlgorithms:Top-kListMLEDataSets:MQ2007(FromLETOR):GradedMQ2007andTop-kMQ2007TD2003(Previousconstructeddata):GradedTD2003andTop-kTD2003Top-10MQ2007Top-10TD2003κNDCG@10κERRPerforma