Google搜索与Inter网的信息检索

Google搜索与

Inter网的信息检索

马志明

May16,2008Email:mazm@/member/mazhiming/index.html约有626,000项符合中国科学院数学与系统科学研究院的查询结果，以下是第1-100项。

(搜索用时0.45

秒）Howcangooglemakearankingof626,000pagesin0.45seconds?Amaintaskof

Internet(Web)

InformationRetrieval

=DesignandAnalysisof

SearchEngine(SE)Algorithm

involvingplentyofMathematicsHITS

PageRank1998JonKleinbergCornellUniversity

SergeyBrinandLarryPageStanfordUniversityNevanlinnaPrize（2006)

JonKleinberg

OneofKleinberg‘smostimportantresearchachievementsfocusesontheinternetworkstructureoftheWorldWideWeb.Priorto

Kleinberg‘swork,searchenginesfocusedonlyonthecontentofwebpages，notonthelinkstructure.Kleinbergintroducedtheideaof“authorities”and“hubs”:Anauthorityisawebpagethatcontains

informationonaparticulartopic,andahubisapagethatcontainslinksto

manyauthorities.Zhuzihuthesis.pdfPage

Rank,therankingsystem

usedbytheGooglesearch

engine.

Queryindependentcontentindependent.usingonlythewebgraphstructurePage

Rank,therankingsystemusedbytheGooglesearchengine.

PageRankasaFunctionoftheDampingFactorPaoloBoldiMassimoSantiniSebastianoVignaDSI,UniversitàdegliStudidiMilanoWWW2005paper3.1Choosingthedampingfactor3GeneralBehaviour3.2Gettingcloseto1

canwesomehowcharacterisethepropertiesof?whatmakes

differentfromtheother(infinitelymany,ifPisreducible)limitdistributionsofP?

isthelimitdistributionofPwhenthestartingdistributionisuniform,thatis,Conjecture1

:

Website

provideplentyofinformation:

pagesinthesamewebsitemaysharethesameIP,runonthesamewebserveranddatabaseserver,andbeauthored/maintainedbythesamepersonororganization.

theremightbehighcorrelationsbetweenpagesinthesamewebsite,intermsofcontent,pagelayoutandhyperlinks.

websitescontainhigherdensityofhyperlinksinsidethem(about75%)andlowerdensityofedgesinbetween.HostGraphlosesmuchtransitioninformation

Canasurferjumpfrompage5ofsite1toapageinsite2?From:s06-pc-chairs-email@[mailto:s06-pc-chairs-Sent:2006年4月4日8:36

To:Tie-YanLiu;wangying@;fengg03@;ybao@;mazm@

Subject:[SIGIR2006]YourPaper#191

Title:AggregateRank:BringOrdertoWebSites

Congratulations!!29thAnnual

International

Conferenceon

Research&DevelopmentonInformationRetrieval(SIGIR’06,August6–11,2006,Seattle,Washington,USA).RankingWebsites,

aProbabilisticView

YingBao,GangFeng,Tie-YanLiu,Zhi-MingMa,andYingWang

InternetMathematics,

Volume3(2007),Issue3-WesuggestevaluatingtheimportanceofawebsitewiththemeanfrequencyofvisitingthewebsitefortheMarkovchainontheInternetGraphdescribingrandomsurfing.

WeshowthatthismeanfrequencyisequaltothesumofthePageRanksofallthewebpagesinthatwebsite(henceisreferredasPageRankSum)

Weproposeanovelalgorithm(AggregateRankAlgorithm)basedonthetheoryofstochasticcomplement

tocalculatetherankofawebsite.TheAggregateRankAlgorithmcanapproximatethePageRankSumaccurately,whilethecorrespondingcomputationalcomplexityismuchlowerthanPageRankSum

Byconstructingreturn-timeMarkovchainsrestrictedtoeachwebsite,wedescribealsotheprobabilisticrelationbetweenPageRankandAggregateRank.

ThecomplexityandtheerrorboundofAggregateRankAlgorithmwithexperimentsofrealdadaarediscussedattheendofthepaper.nwebsinNsites,

Thestationarydistribution,knownasthePageRankvector,isgivenbyWemayrewritethestationarydistributionaswithasarowvectoroflength

Wedefinetheone-steptransitionprobabilityfromthewebsite

tothewebsite

bywhereeisandimensionalcolumnvectorofallones

TheN×NmatrixC(α)=(cij(α))isreferredtoasthecouplingmatrix,whoseelementsrepresentthetransitionprobabilitiesbetweenwebsites.ItcanbeprovedthatC(α)isanirreduciblestochasticmatrix,sothatitpossessesauniquestationaryprobabilityvector.Weuseξ(α)todenotethisstationaryprobability,whichcanbegottenfrom

SinceOnecaneasilycheckthatistheuniquesolutionto

WeshallreferastheAggregateRankThatis,theprobabilityofvisitingawebsiteisequaltothesumofPageRanksofallthepagesinthatwebsite.Thisconclusionisconsistenttoourintuition.thetransitionprobabilityfromSitoSjactuallysummarizesallthecasesthattherandomsurferjumpsfromanypageinSitoanypageinSjwithinone-steptransition.Therefore,thetransitioninthisnewHostGraphisinaccordancewiththerealbehavioroftheWebsurfers.Inthisregard,theso-calculatedrankfromthecouplingmatrixC(α)willbemorereasonablethanthosepreviousworks.Let

denotethenumberofvisitingthewebsite

duringthentimes,thatisWehaveAssumeastartingstateinwebsiteA,i.e.Itisclearthatallthevariables

arestoppingtimesforX.WedefineandinductivelyLet

denotethetransitionmatrixofthereturn-timeMarkovchainforsiteSimilarly,wehaveSinceThereforeSupposethatAggregateRank,i.e.thestationarydistributionofisBasedontheabovediscussions,thedirectapproachofcomputingtheAggregateRankξ(α)istoaccumulatePageRankvalues(denotedbyPageRankSum).However,thisapproachisunfeasiblebecausethecomputationofPageRankisnotatrivialtaskwhenthenumberofwebpagesisaslargeasseveralbillions.Therefore,Efficientcomputationbecomesasignificantproblem.1.Dividethen×nmatrix

intoN×NblocksaccordingtotheNsites.AggregateRank

Constructthestochasticmatrixforbychangingthediagonalelementsoftomakeeachrawsumupto1.3.Determinefrom4.Formanapproximation

tothecouplingmatrix

,byevaluating5.Determinethestationarydistributionof

anddenoteit

,i.e.,Experiments

Inourexperiments,thedatacorpusisthebenchmarkdatafortheWebtrackofTREC2003and2004,domainintheyearof2002.Itcontains1,247,753dataset.Thelargestwebsitecontains137,103webpageswhilethesmallestonecontainsonly1page.PerformanceEvaluationofRankingAlgorithmsbasedonKendall'sdistanceSimilaritybetweenPageRankSumandotherthreerankingresults.From:pcchairs@

Sent:Thursday,April03,20089:48AM

DearYutingLiu,BinGao,Tie-YanLiu,YingZhang,ZhimingMa,ShuyuanHe,HangLi

Wearepleasedtoinformyouthatyourpaper

Title:BrowseRank:LettingWebUsersVoteforPageImportance

hasbeenacceptedfororalpresentationasafullpaperandforpublicationasaneightpaperintheproceedingsofthe31stAnnualInternationalACMSIGIR

ConferenceonResearch&DevelopmentonInformationRetrieval.

Congratulations!!BuildingmodelPropertiesofQprocess:Stationarydistribution:

Jumpingprobability:

EmbeddedMarkovchain:isaMarkovchainwiththetransitionprobabilitymatrixMainconclusion1

isthemeanofthestayingtimeonpagei.

Themoreimportantapageis,thelongerstayingtimeonitis.isthemeanofthefirstre-visittimeatpagei.Themoreimportantapageis,thesmallerthere-visittimeis,andthelargerthevisitfrequencyis.Mainconclusion2

isthestationarydistributionofThestationarydistributionofdiscretemodeliseasytocomputePowermethodforLogdataforFurtherquestionsHowaboutinhomogenousprocess?Statisticresultshow:differentperiodoftimepossessesdifferentvisitingfrequency.Poissonprocesseswithdifferentintensity.MarkedpointprocessHyperlinkisnotreliable.Users’realbehaviorshouldbeconsidered.RelevanceRankingManyfeaturesformeasuringrelevanceTermdistribution(anchor,URL,title,body,proximity,….)Recommendation&citation(PageRank,click-throughdata,…)StatisticsorknowledgeextractedfromwebdataQuestionsWhatistheoptimalrankingfunctiontocombinedifferentfeatures(orevidences)?Howtomeasurerelevance?LearningtoRankWhatistheoptimalweightingsforcombiningthevariousfeaturesUsemachinelearningmethodstolearntherankingfunctionHumanrelevancesystem(HRS)Relevanceverificationtests(RVT)Wei-YingMa,MicrosoftResearchAsiaLearningtoRankModelLearningSystemRankingSystemminLoss66Wei-YingMa,MicrosoftResearchAsiaLearningtoRank(Cont)

State-of-the-artalgorithmsforlearningtoranktakethepairwiseapproachRankingSVMRankBoostRankNet(employedatLiveSearch)67BreakdownWei-YingMa,MicrosoftResearchAsialearningtorankThegoaloflearningtorankistoconstructareal-valuedfunctionthatcangeneratearankingonthedocumentsassociatedwiththegivenquery.Thestate-of-the-artmethodstransformsthelearningproblemintothatofclassificationandthenperformsthelearningtask:Foreachquery,itisassumedthattherearetwocategoriesofdocuments:positiveandnegative(representingrelevantandirreverentwithrespecttothequery).Thendocumentpairsareconstructedbetweenpositivedocumentsandnegativedocuments.Inthetrainingprocess,thequeryinformationisactuallyignored.[5]Y.Cao,J.Xu,T.-Y.Liu,H.Li,Y.Huang,andH.-W.Hon.Adaptingrankingsvmtodocumentretrieval.InProc.ofSIGIR’06,pages186–193,2006.[11]T.Qin,T.-Y.Liu,M.-F.Tsai,X.-D.Zhang,andH.Li.Learningtosearchwebpageswithquery-levellossfunctions.TechnicalReportMSR-TR-2006-156,2006.Ascasestudies,weinvestigateRankingSVMandRankBoost.Weshowthatafterintroducing

query-levelnormalization

toitsobjectivefunction,RankingSVMwillhavequery-levelstability.ForRankBoost,thequery-levelstabilitycanbeachievedifweintroduceboth

query-levelnormalizationandregularization

toitsobjectivefunction.Were-representthelearningtorankproblembyintroducingtheconceptof‘query’and‘distributiongivenquery’intoitsmathematicalformulation.Moreprecisely,weassumethatqueriesaredrawnindependentlyfromaqueryspaceQaccordingtoan(unknown)probabilitydistributionItshouldbenotedthatif,thentheboundmakessense.Thisconditioncanbesatisfiedinmanypracticalcases.Ascasestudies,weinvestigateRankingSVMandRankBoost.Weshowthatafterintroducingquery-levelnormalizationtoitsobjectivefunction,RankingSVMwillhavequery-levelstability.ForRankBoost,thequery-levelstabilitycanbeachievedifweintroducebothquery-levelnormalizationandregularizationtoitsobjectivefunction.Theseanalysesagreelargelywithourexperimentsandtheexperimentsin[5]and[11].RankaggregationRankaggregationistocombinerankingresultsofentitiesfrommultiplerankingfunctionsinordertogenerateabetterone.Theindividualrankingfunctionsarereferredtoasbaserankers,orsimplyrankers.Score-basedaggregationRankaggregationcanbeclassifiedintotwocategories[2].Inthefirstcategory,theentitiesinindividualrankinglistsareassignedscoresandtherankaggregationfunctionisassumedtousethescores(denotedasscore-basedaggregation)[11][18][28].order-basedaggregation

Inthesecondcategory,onlytheordersoftheentitiesinindividualrankinglistsa