




免费预览已结束,剩余76页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
InformationRetrievalModels PengBoOct30 2010 上次课回顾 BasicIndexTechniquesInvertedindexDictionary PostingsScoringandRankingTermweightingtf idfVectorSpaceModelCosineSimilarityIRevaluationPrecision Recall FInterpolationMAP interpolatedAP 本次课大纲 InformationRetrievalModelsVectorSpaceModel VSM LatentSemanticModel LSI LanguageModel LM RelevanceFeedbackQueryExpansion VectorSpaceModel Documentsasvectors 每一个文档j能够被看作一个向量 每个term是一个维度 取值为log scaledtf idfSowehaveavectorspacetermsareaxesdocsliveinthisspace高维空间 即使作stemming mayhave20 000 dimensions Intuition Postulate 在vectorspace中 closetogether 的文档会talkaboutthesamethings 用例 Query by example FreeTextqueryasvector Cosinesimilarity 向量d1和d2的 closeness 可以用它们之间的夹角大小来度量具体的 可用cosineoftheanglex来计算向量相似度 向量按长度归一化Normalization 1 COSSimilarity 计算查询 digitalcameras 与文档 digitalcamerasandvideocameras 之间的相似度 假定N 10 000 000 query和document都采用logarithmictermweighting wfcolumns query采用idfweighting document采用cosinenormalization and 作为stopword 2 Evaluation 定义precision recallgraph如下 对一个查询结果列表 每一个返回结果文档处计算precision recall点 由这些点构成的图 在这个图上定义breakevenpoint为precision和recall值相等的点 问 存在多于一个breakevenpoint的图吗 如果有 给出例子 没有的话 请证明之 LatentSemanticModel VectorSpaceModel Pros AutomaticselectionofindextermsPartialmatchingofqueriesanddocuments dealingwiththecasewherenodocumentcontainsallsearchterms Rankingaccordingtosimilarityscore dealingwithlargeresultsets Termweightingschemes improvesretrievalperformance VariousextensionsDocumentclusteringRelevancefeedback modifyingqueryvector Geometricfoundation ProblemswithLexicalSemantics Polysemy 词通常有multitudeofmeanings和不同用法 VectorSpaceModel不能区分同一个词的不同含义 即ambiguity Synonymy 不同的terms可能具有identicalorasimilarmeaning VectorSpaceModel里不能表达词之间的associations IssuesintheVSM terms之间的独立性假设有些terms更可能在一起出现同义词 相关词汇 拼写错误 etc 根据上下文 terms可能有不同的含义term document矩阵维度很高 对每篇文档 每个词 真的有那么多重要的特征 SingularValueDecomposition 对term document矩阵作奇异值分解SingularValueDecompositionr 矩阵的rank singularvalues的对角阵 按降序排列 D T 具有正交的单位长度列向量 TT I DD I WWT的特征值 WTW和WWT的特征向量 SingularValues givesanorderingtothedimensions值下降非常快尾部的singularvaluesat代表 noise 在low valuedimensions截止可以减少noise 提高性能 Low rankApproximation t d t r wtd T r r DT r d t d t k w td k k k d T DT LatentSemanticIndexing LSI Performalow rankapproximationofterm documentmatrix typicalrank100 300 GeneralideaMapdocuments andterms toalow dimensionalrepresentation Designamappingsuchthatthelow dimensionalspacereflectssemanticassociations latentsemanticspace Computedocumentsimilaritybasedontheinnerproductinthislatentsemanticspace Whatitis 从原始的term document矩阵Ar 我们计算得到它的近似Ak 在Ak中 每行对应一个term 每列对应一个document区别是 文档在新的空间 它的维度k rdimensions怎样比较两个term 怎样比较两个document 怎样比较一个term和一个文档 AKTAk D TTTT DT DT T DT Ak I j AkAKT T DTD TTT T T T LSITermmatrixT Tmatrix每个term在LSIspace的向量原始matrix terms向量是d dimensional T中要小很多Dimensions是在相同文档中倾向于与这个词 同现 的一组termssynonyms contextually relatedwords variantendings T 用来计算term相似度 DocumentmatrixD Dmatrix在LSIspace中文档的表示和Tvectors有相同的dimensionality DT 用来计算document相似度可用于计算查询和一个文档的similarity RetrievalwithLSI LSI检索过程 查询映射 投影到LSI的DT空间 称为 foldedin W T DT 若q投影到DT中后为q 则有q T q T既有q 1T 1q T qT 1Foldedin既为document queryvector乘上T 1文档集的文档向量为 DT两者通过dot product计算相似度 ImprovedRetrievalwithLSI 性能提升来自 去除了noise不需要stemterms variantswillco occur 不需要stoplist没有速度和空间上的改进 though C Tr r DrT 2 2D2T Example Mapinto2 dimenstionspace LatentSemanticAnalysis Latentsemanticspace illustratingexample courtesyofSusanDumais Empiricalevidence ExperimentsonTREC1 2 3 DumaisPrecisionatorabovemedianTRECprecisionTopscoreronalmost20 ofTRECtopicsSlightlybetteronaveragethanstraightvectorspacesEffectofdimensionality LSIhasmanyotherapplications 在很多场合 我们都有feature objectmatrix 矩阵是高维 有大量冗余 从而能使用low rankapproximation 比如文本检索 theterms是features thedocs是objects LatentSemanticIndex比如opinions和users 数据不全 e g users opinions 可以在低维空间里恢复 Powerfulgeneralanalyticaltechnique LanguageModels IRbasedonLanguageModel LM query Informationneed documentcollection 通常的search方法 猜测作者写相关文档时使用的词 形成queryTheLMapproachdirectlyexploitsthatidea FormalLanguage Model 传统的生成模型generativemodel 产生stringsFinitestatemachinesorregulargrammars etc Example Iwish IwishIwish IwishIwishIwish IwishIwishIwishIwish Iwish StochasticLanguageModels Modelsprobabilityofgeneratingstringsinthelanguage commonlyallstringsoveralphabet 0 2the0 1a0 01man0 01woman0 03said0 02likes the man likes the woman 0 2 0 01 0 02 0 2 0 01 ModelM P s M 0 00000008 StochasticLanguageModels Modelprobabilityofgeneratinganystring 0 2the0 01class0 0001sayst0 0001pleaseth0 0001yon0 0005maiden0 01woman ModelM1 ModelM2 P s M2 P s M1 0 2the0 0001class0 03sayst0 02pleaseth0 1yon0 01maiden0 0001woman StochasticLanguageModels 用来生成文本的统计模型Probabilitydistributionoverstringsinagivenlanguage M Unigramandhigher ordermodels UnigramLanguageModelsBigram generally n gram LanguageModelsOtherLanguageModelsGrammar basedmodels PCFGs etc ProbablynotthefirstthingtotryinIR Easy Effective ThefundamentalproblemofLMs 模型M是不知道的只有代表这个模型的样例文本从样例文本中来估计Model然后计算观察到的文本概率 M UsingLanguageModelsinIR 每篇文档对应一个model按P d q 对文档排序P d q P q d xP d P q P q isthesameforalldocuments soignoreP d theprior isoftentreatedasthesameforalldButwecouldusecriterialikeauthority length genreP q d istheprobabilityofqgivend smodelVerygeneralformalapproach LanguageModelsforIR LanguageModelingApproaches为querygenerationprocess建模文档排序 按一个query作为由文档模型产生的随机样本而被观察到的概率theprobabilitythataquerywouldbeobservedasarandomsamplefromtherespectivedocumentmodelMultinomialapproach RetrievalbasedonprobabilisticLM 把query的产生当作一个随机过程方法为每个文档Inferalanguagemodel Estimatetheprobability 估计每个文档模型产生这个query的概率Rank 按这个概率对文档排序 通常使用Unigrammodel Querygenerationprobability 1 排序公式用最大似然估计 Unigramassumption Givenaparticularlanguagemodel thequerytermsoccurindependently languagemodelofdocumentd rawtfoftermtindocumentd totalnumberoftokensindocumentd Insufficientdata Zeroprobability一个文档里没有query中的某个term时 Generalapproach没有出现文档中的term按它出现在collection中的概率来代替 If rawcountoftermtinthecollection rawcollectionsize totalnumberoftokensinthecollection Insufficientdata Zeroprobabilitiesspelldisaster使用平滑 smoothprobabilitiesDiscountnonzeroprobabilitiesGivesomeprobabilitymasstounseenthings有很多方法 如adding1 or tocounts Dirichletpriors discounting andinterpolation SeeFSNLPch 6ifyouwantmore 使用混合模型 useamixturebetweenthedocumentmultinomialandthecollectionmultinomialdistribution Mixturemodel P w d Pmle w Md 1 Pmle w Mc 参数 很重要 值高 使得查询成为 conjunctive like 适合短查询 值低更适合长查询调整 来优化性能比如使得它与文档长度相关 cf DirichletpriororWitten Bellsmoothing Basicmixturemodelsummary GeneralformulationoftheLMforIR generallanguagemodel individual documentmodel Example Documentcollection 2documents d1 Xeroxreportsaprofitbutrevenueisdownd2 LucentnarrowsquarterlossbutrevenuedecreasesfurtherModel MLEunigramfromdocuments Query revenuedownP Q d1 1 8 2 16 2 x 1 8 1 16 2 1 8x3 32 3 256P Q d2 1 8 2 16 2 x 0 1 16 2 1 8x1 32 1 256Ranking d1 d2 AlternativeModelsofTextGeneration QueryModel Query DocModel Doc Searcher Writer Isthisthesamemodel RetrievalUsingLanguageModels QueryModel Query DocModel Doc 1 2 3 Querylikelihood 1 Documentlikelihood 2 Modelcomparison 3 QueryLikelihood P Q Dm 主要问题是估计文档modeli e smoothingtechniquesinsteadoftf idfweights检索效果不错e g UMass BBN Twente CMU问题 处理relevancefeedback queryexpansion structuredqueries困难 DocumentLikelihood 按P D R P D NR 排序P w R isestimatedbyP w Qm QmisthequeryorrelevancemodelP w NR isestimatedbycollectionprobabilitiesP w 问题是估计relevancemodelTreatqueryasgeneratedbymixtureoftopicandbackgroundEstimaterelevancemodelfromrelateddocuments queryexpansion RelevancefeedbackiseasilyincorporatedGoodretrievalresultse g UMassatSIGIR01inconsistentwithheterogeneousdocumentcollections ModelComparison 估计query和document模型 进行模型比较KLdivergenceD Qm Dm 取得了较前两方法更好的效果 Languagemodels pro con NovelwayoflookingattheproblemoftextretrievalbasedonprobabilisticlanguagemodelingConceptuallysimpleandexplanatoryFormalmathematicalmodelNaturaluseofcollectionstatistics notheuristics almost LMsprovideeffectiveretrievalandcanbeimprovedtotheextentthatthefollowingconditionscanbemetOurlanguagemodelsareaccuraterepresentationsofthedata Usershavesomesenseoftermdistribution ComparisonWithVectorSpace 和传统的tf idfmodels有一定联系 unscaled termfrequencyisdirectlyinmodeltheprobabilitiesdolengthnormalizationoftermfrequenciestheeffectofdoingamixturewithoverallcollectionfrequenciesisalittlelikeidf termsrareinthegeneralcollectionbutcommoninsomedocumentswillhaveagreaterinfluenceontheranking ComparisonWithVectorSpace 相似点TermweightsbasedonfrequencyTermsoftenusedasiftheywereindependentInversedocument collectionfrequencyusedSomeformoflengthnormalizationused不同点BasedonprobabilityratherthansimilarityIntuitionsareprobabilisticratherthangeometricDetailsofuseofdocumentlengthandterm document andcollectionfrequencydiffer 本次课小结 LatentSemanticIndexingsingularvaluedecompositionMatrixLow rankApproximationLanguageModelGenerativemodelsmoothprobabilitiesMixturemodel Resources TheTemplateNumericalToolkit TNT http math nist gov tnt documentation htmlTheLemurToolkitforLanguageModelingandInformationRetrieval http www 2 cs cmu edu lemur CMU UmassLMandIRsysteminC currentlyactivelydeveloped ThankYou Q A 阅读材料 1 IIRCh12 Ch18 2 M Alistair Z Justin andH David RecommendedreadingforIRresearchstudents SIGIRForum vol 39 pp 3 14 2005 2Evaluation Questiona不能有两个或两个以上的breakevenpoint证明 一次检索I 相关文档集为R 设当前为breakevenpoint 检出文档集为A 检出的相关文档集为Ra 则precision Ra A recall Ra R 根据breakevenpoint的定义 precision recall 推出 R A 假设再检出k k 0 个文档后 又出现一个breakevenpoint 则此时的precision R a A recall R a R 推出 A R 由于 A A k k 0 且 A R 推出矛盾 所以不能有两个或两个以上的breakevenpoint 注意 当没有检出相关文档时 查全率和查准率都是零 这时是breakevenpoint吗 考虑到这种情况 则可以有两个或两个以上的breakevenpoint MatrixLow rankApproximationforLSI Eigenvalues Eigenvectors Eigenvectors forasquarem mmatrixS Howmanyeigenvaluesarethereatmost eigenvalue right eigenvector Matrix vectormultiplication haseigenvalues3 2 0withcorrespondingeigenvectors Anyvector sayx canbeviewedasacombinationoftheeigenvectors x 2v1 4v2 6v3 Matrixvectormultiplication Thusamatrix vectormultiplicationsuchasSx S xasinthepreviousslide canberewrittenintermsoftheeigenvalues vectors Eventhoughxisanarbitraryvector theactionofSonxisdeterminedbytheeigenvalues vectors Suggestion theeffectof small eigenvaluesissmall Eigenvalues Eigenvectors Forsymmetricmatrices eigenvectorsfordistincteigenvaluesareorthogonal Alleigenvaluesofarealsymmetricmatrixarereal Example LetThenTheeigenvaluesare1and3 nonnegative real Theeigenvectorsareorthogonal andreal Real symmetric Pluginthesevaluesandsolveforeigenvectors LetbeasquarematrixwithmlinearlyindependenteigenvectorsTheorem ExistsaneigendecompositionColumnsofUareeigenvectorsofSDiagonalelementsofareeigenvaluesof Eigen diagonalDecomposition Diagonaldecomposition why how LetUhavetheeigenvectorsascolumns Then SUcanbewritten AndS U U 1 ThusSU U orU 1SU Diagonaldecomposition example Recall Theeigenvectorsandform Inverting wehave Then S U U 1 RecallUU 1 1 Examplecontinued Let sdivideU andmultiplyU 1 by Then S Q Q 1 QT Why Staytuned Ifisasymmetricmatrix Theorem Existsa unique eigendecompositionwhereQisorthogonal Q 1 QTColumnsofQarenormalizedeigenvectorsColumnsareorthogonal everythingisreal SymmetricEigenDecomposition Timeout Whatdothesematriceshavetodowithtext Recallm nterm documentmatrices Buteverythingsofarneedssquarematrices so SingularValueDecomposition Foranm nma
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 ISO/TS 21310:2025 EN Traditional Chinese medicine - Microscopic examination of medicinal herbs
- 【正版授权】 ISO/TS 14812:2025 EN Intelligent transport systems - Vocabulary
- 【九江】2025年上半年江西九江市事业单位“才汇九江”招聘高层次人才373人笔试历年典型考题及考点剖析附带答案详解
- 2025年公共营养师之三级营养师能力检测试卷A卷附答案
- 【张家界】2025年湖南张家界市市直事业单位公开招聘急需紧缺人员41人笔试历年典型考题及考点剖析附带答案详解
- 中国高考评价体系解读课件
- 第四章氧化还原反应第三节氧化还原反应的方向和限度无机化学电
- 完璧归赵教学课件
- Brand KPIs for milk:Lac Del in Mexico-英文培训课件2025
- 2025年小学科学课程标准考试测试题及答案
- 压力容器事故应急预案
- 招聘工作人员笔试考务手册
- 2024年广东茂名信宜市事业单位招聘工作人员144人笔试【重点基础提升】模拟试题(共500题)附带答案详解
- 2024年秋新版人教版三年级英语上册电子课本
- 2024-2034年中国油桐种植行业市场调查研究及投资战略咨询报告
- 六君子汤的现代中药制剂研究
- 管理思维培训
- 中国古代安全文化发展及其启示
- 教师信息技术能力提升培训课件
- 2022年宜宾机场集团有限公司招聘考试真题
- 金属与石材幕墙工程技术规范-JGJ133-2013含条文说
评论
0/150
提交评论