信息检索第一讲_第1页
信息检索第一讲_第2页
信息检索第一讲_第3页
信息检索第一讲_第4页
信息检索第一讲_第5页
已阅读5页,还剩67页未读, 继续免费阅读

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

InformationRetrieval&WebDongShoubin董守斌)IRRetrieval

TypicalIRAcorpusoftextualnatural-languagedocuments.Auserqueryintheformof

..ArankedsetofdocumentsthatareDefinitionsofInformationRetrieval(IR)Salton(1989):“Information-retrievalsystemsprocessfilesofrecordsandrequestsforinformation,andidentifyandretrievefromthefilescertainrecordsinresponsetotheinformationrequests.Theretrievalofparticularrecordsdependsonthesimilaritybetweentherecordsandthequeries,whichinturnismeasuredbycomparingthevaluesofcertainattributestorecordsandinformationrequests.”Kowalski(1997):“AnInformationRetrievalSystemisasystemthatiscapableofstorage,retrieval,andmaintenanceofinformation.Informationinthiscontextcanbecomposedoftext(includingnumericanddatedata),images,audio,video,andothermulti-mediaobjects).”WhatisInformationInformationRetrieval(IR)isthestudyofusuallytext,butalsoaudioandDataisconsideredunstructuredthestructureisunknown,thesemanticsofeachcomponentareunknown.e.g.,“bank”,“nut”,“sun”,“whitehouse”IRsystemsexploitstatisticalregularitiesinthewithouttryingto“understand”whattheyContrastingNLP(NaturalLanguageprocessing:自然语言处理)systemstrytofindthemeaning(semantics)inunstructuredtextInformationvs.DataDataRetrieveallobjectswhichsatisfyclearlydefinedconditionsinregularexpressionorrelationalalgebraexpressionDatahasawelldefinedstructureandSolutiontotheuserofadatabasesystemInformationneed=>Retrieveallthedocumentswhicharerelevanttoauserquery,whileretrievingasfewnon-relevantdocumentsaspossibleSimpleflowofretrievalKeystoInformationRepresentationofinformationRepresentationofObjectretrievalaccordingtorelevancebasedontherepresentationsEvaluationRelevanceisasubjectivejudgmentandmayBeingontheproperBeingtimely(recentSatisfyinginformationneed:thegoalsoftheuserandhis/herintendeduseoftheinformation.ThenotionofSimplestnotion:thequerystring(keyword)appearsverbatiminthedocumentSlightlylessstrictnotion:thekeywordappearfrequentlyinthedocument,inanyorder(bagofwords).IRRetrievalKeyidea:Everything(documents,queries,terms)isavectoroftermsinahigh-dimensionalspacedj=(w1j,w2j,…,Eachtermki,inadocumentorqueryj,isgivenanon-binaryweight,wij.ThesetermweightsareusedtocomputeadegreeofbetweenaqueryandeachRankedsetofdocumentsprovidesforbettermatchingandpartial Dimension=t=|vocabulary|VectorSpaceModel(VSM)wasdevelopedintheSMARTsystem(Salton,c.1970)andstandardlyusedbyTRECparticipantsandwebsearchengine.Graphic5D1=2T1+3T2+Q=0T1+0T2+ D2=3T1+7T2+ •IsD1orD2moresimilartoHowtomeasurethedegree similarity?Distance? DocumentCollectionAcollectionofndocumentscanberepresentedinthevectorspacemodelbyaterm-documentmatrix.Anentryinthematrixcorrespondstothe“weight”ofaterminthedocument;zeromeansthetermhasnosignificanceinthedocumentoritsimplydoesn’texistinthedocument. w21 … HowtocalculateTermfrequencyTheNumberofTermOccurs,…0740220060052019012600300200…0008AnyCountingTermstellusaboutIf“rabbit”appearsalot,itmaybeaboutDocumentstellusabout“the”isineverydocument--notDocumentsaremostlikelydescribedwellraretermsthatoccurinthemHigher“termfrequency”isstrongerLow“collectionfrequency”makesitstrongerTermWeightingtffactortermfrequency,词频 therawfrequencyofatermkiinsideadocumentdjidffactorinversedocumentfrequency逆theinverseofthefrequencyofatermkiamongthedocumentsinthecollectionTF-IDFTermAtypicalweightingistf-idf

idfi=tf

dfjAtermoccurringfrequentlyinthedocumentbutrarelyintherestofthecollectionisgivenhighweight.Hightermfrequencyisevidenceofmeaning.AndhighIDFisevidenceoftermimportance.VerygoodweightingItwasalsotheoreticallyprovedtoworkwell(Papineni,“Whyinversedocumentfrequency?”NAACL2001)Documentsas…000000000000…000SowehaveavectortermsaredocsliveinthisVeryhighdimensions:thoughstemming,mayhave20,000+QueryQueryvectoristypicallytreatedasa(veryshort)documentandalsotf-idfweighted.Alternativeisfortheusertosupplyweightsforthegivenqueryterms.Querytermweight(SaltonandBuckley) =(0.5+0.5freqi,q )·logNi,q maxl freqi,q freqi,q:therawfrequencyofthetermkiinSimilarityWenowhavevectorsforalldocumentsinthecollection,avectorforthequery,howtocomputeAsimilaritymeasureisafunctionthatcomputesthedegreeofsimilarity(相似度)betweentwoUsingasimilaritymeasurebetweenthequeryandeachdocument:Itispossibletoranktheretrieveddocumentsintheorderofpresumedrelevance.Itispossibletoenforceacertainthresholdsothatthesizeoftheretrievedsetcanbecontrolled.CosineDistancebetweenvectorsd1andd2capturedbythecosineoftheanglexbetweenthem.sim(dj,dk)= ttttThecosinemeasureisknownasthenormalizedinnerproduct.i,Lengthd tCosineNormalizationtfi,

123 123412345241354363321372614RetrievalQuery:contaminated1111231111234SimilarityDocDocDocDocRankedList:2,3,1,4(innerproduct)VectorSpaceModel:Simple,mathematicallybasedMapeverything(documents,queries,sentences,terms)toaAbilitytoincorporatetermAnytypeoftermweightscanbeTFIDFweighting:considersbothlocal(tf)andglobal(idf)wordoccurrencefrequencies.ProvidespartialmatchingandrankedTendstoworkquitewellinpracticedespiteobviousThevectorspacemodelisthemostThevectorspacemodelisthemostpopularretrievalmodelVectorSpaceModel:Missingsemanticinformation(e.g.wordMissingsyntacticinformation(e.g.phrasestructure,wordorder,proximityinformation).Assumptionoftermindependence(e.g.ignoresLacksthecontrolofaBooleanmodelrequiringatermtoappearinaGivenatwo-termquery“AB”,maypreferadocumentcontainingAfrequentlybutnotB,overadocumentthatcontainsbothAandB,butbothlessfrequently.IRRetrievalHowtoOnlinetextNaïve:ScanthetextHowlongwillittaketofindaIsthereanyworkwecandoinIfso,howlongwillthatIndexedBuilddatastructuresoverthetexttospeeduptheSemi-staticcollections:updatedatreasonablyregularOriginalDocument101110110000011RetrievalwithanInvertedTokensthatarenotinboththequeryandthedocumentdonoteffectcosinesimilarity.Productoftokenweightsiszeroanddoesnotcontributetothedotproduct.Usuallythequeryisfairlyshort,andthereforeitsvectorisextremelysparse.UseinvertedindextofindthelimitedsetofdocumentsthatcontainatleastoneofthequeryInverted100010110101101InvertedWord-orientedmechanismforindexingtestcollectionstospeedupsearchingInvertedEachdocumentisassignedalistofkeywordsorEachkeyword(attribute)isassociatedwithoperationalrelevanceweights.Aninvertedfileisthesortedlistofkeywords(attributes),witheachkeywordhavinglinkstothedocumentscontainingthatkeyword.IndexDIndexDj,D1,D5,D7,D2,Indexfile PostingsFriends,Romans,beFriends,Romans,beLinguistic化12国24国2412345678Producing123456780001000101010100101000101010101001010101001010000010101001010101001000001010101001010001010001011010101100000101101000001000101001010100

4,2,4,2,4,1,3,1,3,2,4,6,3,3,5,2,4,6,31,3,5,2,4,2,6,1,3,5,7,6,1,1,5,2,4,WhatGoesinaPostingsD4,D2,D4,D4,D2,D4,JustthedocumentD4:2,D4:2,D2:1,D4:3,D1:1,D3:1,Documentnumberandtermweight(TF*IDF,...)D4(17,36),D4(17,36),D2(44),D4(10,20),D1(18),D3(6),WordoffsetsforeachoccurrenceofthetermBooleanKeywordscombinedwithBooleanOR:(e1ORAND:(e1ANDBUT:(e1BUTe2)Satisfye1butnotNegationonlyallowedusingBUTtoallowefficientuseofinvertedindexbyfilteringanotherefficientlyretrievableset.NaïveusershavetroublewithBooleanBooleanRetrievalwithInvertedIndexPrimitivekeyword:Retrievecontainingdocumentsusingtheinvertedindex.OR:Recursivelyretrievee1ande2andtakeunionofresults.AND:Recursivelyretrievee1ande2andtakeintersectionofresults.BUT:Recursivelyretrievee1ande2andtakesetdifferenceofresults.BooleanQueryprocessing248248281232812385Ifthelistlengthsarexandy,themergetakesO(x+y)operations.(Crucial:postingssortedbydocID)PhrasalRetrievedocumentswithaspecificphrase(orderedlistofcontiguouswords)“informationMayallowinterveningstopwordsand/or“buycamera”matches:“buyacamera”“buyingthecameras” PhrasalRetrievalwithInvertedIndicesMusthaveaninvertedindexthatalsopositionsofeachkeywordinaRetrievedocumentsandpositionsforeachindividualword,intersectdocuments,andthenfinallycheckfororderedcontiguityofkeywordBesttostartcontiguitycheckwiththeleastcommonwordinthephrase.PhrasalFindsetofdocumentsDinwhichallkeywords(k1…km)inphraseoccur(usingANDqueryprocessing).Intitializeemptyset,R,ofretrieveddocuments.Foreachdocument,d,inD:Getarray,Pi,ofpositionsofoccurrencesforeachkiinFindshortestarrayPsoftheForeachpositionpofkeywordksinForeachkeywordkiexceptUsebinarysearchtofindaposition(p–s+i)inthearrayIfcorrectpositionforeverykeywordfound,adddtoIndexingandWalktheinvertedfile,splittingifInsertintothepostingsfileinsortedHoursordaysforlargeQueryWalktheinvertedReadthepostingsManipulatepostingsbasedonSeconds,evenforenormousIRRetrievalWhySystemTherearemanyretrievalmodels/algorithms/systems,whichoneisthebest?WhatisthebestcomponentRankingfunction(dot-product,cosine,Termselection(stopwordremoval,Termweighting(TF,TF-Howfardowntherankedlistwillauserneedtolooktofindsome/allrelevantdocuments?DifficultiesinEvaluatingIREffectivenessisrelatedtotherelevancyofretrieveditems.RelevancyisnottypicallybinarybutEvenifrelevancyisbinary,itcanbeadifficultjudgmenttomake.Relevancy,fromahumanstandpoint,Subjective:Dependsuponaspecificuser’sSituational:Relatestouser’scurrentCognitive:DependsonhumanperceptionandDynamic:ChangesoverAutomaticEvaluation RankedRelevanceMeasureofSet-BasedEffectiveness

Relevant EntiredocumentPrecision&NotRelevant RelevantIrrelevant IrrelevantNotPrecisionRecall

PrecisionandHowmuchofwhatwasfoundisTheabilitytoretrievetop-rankeddocumentsthataremostlyrelevant.HowmuchofwhatisrelevantwasTheabilityofthesearchtofindalloftherelevantitemsinthecorpus.TotalnumberofrelevantitemsissometimesnotTrade-offbetweenRecalland1Returnsrelevantdocumentsbutmissesmanyusefulonestoo110

TheReturnsmostrelevantdocumentsbutincludeslotsofjunkComputingRecall/PrecisionForagivenquery,producetherankedlistofAdjustingathresholdonthisrankedlistproducesdifferentsetsofretrieveddocuments,andthereforedifferentrecall/precisionmeasures.Markeachdocumentintherankedlistthatisrelevantaccordingtothegoldstandard.Computearecall/precisionpairforeachpositionintherankedlistthatcontainsarelevantndoc1ndoc1x2x34x56x789x

LetLettotal#ofrelevantdocsCheckeachnewrecallR=1/6=0.167;R=2/6=0.333; MissingoneR=5/6=0.833;R=5/6=0.833;InterpolatingaRecall/PrecisionInterpolate插值at11standardrecalllevels(11-rj˛{0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,r0=0.0,r1=0.1,…,Theinterpolatedprecisionatthej-thstandardrecalllevelisthemaximumknownprecisionatanyrecalllevelgreaterthatthej-thlevel:P(rj)=rj

P(r)Example:Interpolatingat11-RecallLevelsndocndoc1x2x34x56x789x11112131415678900Example:InterpolatingaRecall/PrecisionCurve 1.0CompareTwoorMore1PrecisionPrecision0 Thecurve(RPCurve)closesttotheupperright-handcornerofthegraphindicatesthebestperformanceMeanAveragePrecisionHowtocomparetwosystembyP/RcurvesNeedtoaverageovermanyTwomaintypesofMicro-average(微平均averageoverallqueries(eachrelevantdocumentisapointintheaverage)Macro-average(宏平均)-averageofwithin-queryprecision/recall(eachqueryisapointintheaverage)MeanAveragePrecision(MAP):meanofaverageprecisionformanyqueriesInterpolated:Avgprecisionatrecall=0.0,0.1,…,Uninterpolated:AvgprecisionateachrelevantOnemeasureofperformancethattakesintoaccountbothrecallandprecision.Harmonicmean调和平均/倒数平均ofrecallandprecision:=2PRF=P+=

Comparedtoarithmeticmean(算术平均),bothneedtobehighforharmonicmeantobeEMeasure(ParameterizedFMeasure)AvariantofFmeasurethatallowsweightingemphasisonprecisionoverrecall: 2E=b2P+ 2b+ Valueofbcontrolstrade-b=1:Equallyweightprecisionandrecallb>1:Weightrecallb<1:WeightprecisionFocusingonTopUserstendtolookatonlythetoppartoftherankedresultlisttofindrelevantdocumentsSomesearchtaskshaveonlyonerelevante.g.,navigationalsearch,questionRecallnotinsteadneedtomeasurehowwellthesearchenginedoesatretrievingrelevantdocumentsatveryhighPrecision@N,R-Precision,MeanReciprocalRank(MRR)R-R-PrecisionR-查准率PrecisionattheR-thpositionintherankingofresultsforaquerythathasRrelevantdocuments.ndoc1x2x34xndoc1x2x34x56x789789xSingle-ValuedMeanprecisionatafixednumberofPrecision@10,Precision@20areoftenusedforWebMRR(MeanReciprocalMeanofthereciprocalranks排序倒数:正确答案序号的倒数)overallthetopicsverysensitivetorankDiscountedCumulativeGainPopularmeasureforevaluatingwebsearchandrelatedtasksTwoHighlyrelevantdocumentsaremoreusefulthanmarginallyrelevantdocumentthelowertherankedpositionofarelevantdocument,thelessusefulitisfortheuser,sinceitislesslikelytobeexaminedUsesgradedrelevanceasameasureof

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论