信息檢索與web搜索課件 10學(xué)習(xí)資料

信息檢索與Web搜索

第10講

相關(guān)反饋及查詢(xún)擴(kuò)展RelevanceFeedback&QueryExpansion授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開(kāi)課件（/~wangbin）*改編自“現(xiàn)代信息檢索”網(wǎng)上公開(kāi)課件（/~wangbin）2關(guān)于提高召回率提高召回率，特別是在前幾頁(yè)給用戶(hù)返回更多的相關(guān)文檔，十分重要現(xiàn)有方法的召回率存在問(wèn)題，例如：考慮查詢(xún)q:[aircraft]...某篇文檔d

包含“plane”,但是不包含

“aircraft”顯然對(duì)于查詢(xún)q，一個(gè)簡(jiǎn)單的IR系統(tǒng)不會(huì)返回文檔d，即使d是和q最相關(guān)的文檔兩種方法：相關(guān)反饋和查詢(xún)擴(kuò)展23相關(guān)反饋的基本思想和流程基本思想：根據(jù)用戶(hù)對(duì)查詢(xún)結(jié)果的標(biāo)注，生成更有效的查詢(xún)，以提高召回率及準(zhǔn)確率流程：用戶(hù)提交一個(gè)(簡(jiǎn)短的)查詢(xún)搜索引擎返回一系列文檔用戶(hù)將部分返回文檔標(biāo)記為相關(guān)的，將部分文檔標(biāo)記為不相關(guān)的搜索引擎根據(jù)標(biāo)記結(jié)果更新查詢(xún)表示搜索引擎對(duì)新查詢(xún)進(jìn)行處理，返回新結(jié)果3相關(guān)反饋分類(lèi)顯式相關(guān)反饋(UserFeedbackorExplicitFeedback)：用戶(hù)交互地進(jìn)行查詢(xún)結(jié)果標(biāo)注隱式相關(guān)反饋(ImplicitFeedback)：系統(tǒng)跟蹤用戶(hù)的行為來(lái)推測(cè)返回文檔的相關(guān)性，從而進(jìn)行反饋偽相關(guān)反饋或盲相關(guān)反饋(PseudoFeedbackorBlindFeedback)：沒(méi)有用戶(hù)參與，系統(tǒng)直接假設(shè)返回文檔的前k篇是相關(guān)的，然后進(jìn)行反饋445相關(guān)反饋舉例-156初始查詢(xún)的結(jié)果67用戶(hù)反饋:選擇相關(guān)結(jié)果78相關(guān)反饋后再次檢索的結(jié)果8相關(guān)反饋舉例-29初始查詢(xún):[newspacesatelliteapplications]初始查詢(xún)的檢索結(jié)果:

r + 1 0.539 NASAHasn’tScrappedImagingSpectrometer + 2 0.533 NASAScratchesEnvironmentGearFromSatellitePlan 3 0.528 SciencePanelBacksNASASatellitePlan,ButUrgesLaunches SmallerProbes 4 0.526 ANASASatelliteProjectAccomplishesIncredibleFeat:Staying WithinBudget 5 0.525 ScientistWhoExposedGlobalWarmingProposesSatellitesfor ClimateResearch 6 0.524 ReportProvidesSupportfortheCriticsOfUsingBigSatellites toStudyClimate 7 0.516 ArianespaceReceivesSatelliteLaunchPactFromTelesat Canada + 8 0.509 TelecommunicationsTaleofTwoCompanies用戶(hù)將一些文檔標(biāo)記為相關(guān)“+”.910基于相關(guān)反饋進(jìn)行擴(kuò)展后的查詢(xún)查詢(xún):[newspacesatelliteapplications]102.074new15.106space30.816satellite5.660application5.991nasa5.196eos4.196launch3.972aster3.516instrument3.446arianespace3.004bundespost2.806ss2.790rocket2.053scientist2.003broadcast1.172earth0.836oil0.646measure基于擴(kuò)展查詢(xún)的檢索結(jié)果11

r

* 1 0.513 NASAScratchesEnvironmentGearFromSatellitePlan * 2 0.500 NASAHasn’tScrappedImagingSpectrometer 3 0.493 WhenthePentagonLaunchesaSecretSatellite,Space SleuthsDoSomeSpyWorkofTheirOwn 4 0.493 NASAUses‘Warm’SuperconductorsForFastCircuit * 5 0.492 TelecommunicationsTaleofTwoCompanies 6 0.491 SovietsMayAdaptPartsofSS-20MissileFor CommercialUse 7 0.490 GapingGap:PentagonLagsinRaceToMatchthe SovietsInRocketLaunchers 8 0.490 RescueofSatelliteBySpaceAgencyToCost$90

Million1112

Rocchio算法核心概念:質(zhì)心

質(zhì)心的定義

其中D是一個(gè)文檔集合，是文檔d的向量表示質(zhì)心是一系列點(diǎn)的中心1213

質(zhì)心示例1314最優(yōu)查詢(xún)定義

Dr:相關(guān)文檔集;Dnr:不相關(guān)文檔集上述公式的意圖是與相關(guān)文檔相似度最大且同時(shí)與不相關(guān)文檔相似度最小基于余弦相似度，可以將上式改寫(xiě)為:14Rocchio算法原理

15舉例

圓形點(diǎn):相關(guān)文檔,叉叉點(diǎn):不相關(guān)文檔1516Rocchio算法原理圖示:相關(guān)文檔的質(zhì)心1617

不能將相關(guān)/不相關(guān)文檔分開(kāi)17Rocchio算法原理圖示18

不相關(guān)文檔的質(zhì)心18Rocchio算法原理圖示1919Rocchio算法原理圖示20

-差異向量20Rocchio算法原理圖示21加上差異向量

21Rocchio算法原理圖示22

得到22Rocchio算法原理圖示23

能夠?qū)⑾嚓P(guān)/不相關(guān)文檔完美地分開(kāi)23Rocchio算法原理圖示24能夠?qū)⑾嚓P(guān)/不相關(guān)文檔完美地分開(kāi)24Rocchio算法原理圖示25Rocchio算法

實(shí)際使用的優(yōu)化查詢(xún)確定方法

qm:修改后的查詢(xún);q0:原始查詢(xún);Dr

、Dnr:已知的相關(guān)和不相關(guān)文檔集合

α,β,γ:權(quán)重αvs.β/γ設(shè)置中的折中:如果判定的文檔數(shù)目很多，那么

β/γ可以考慮設(shè)置得大一些

2526正反饋

vs.

負(fù)反饋正（負(fù)）反饋：指用戶(hù)對(duì)相關(guān)文檔（不相關(guān)文檔）的標(biāo)記和反饋正反饋價(jià)值往往大于負(fù)反饋因此可以通過(guò)設(shè)置β=0.75,γ=0.25來(lái)給正反饋更大的權(quán)重很多系統(tǒng)甚至只允許正反饋，即γ=02627相關(guān)反饋起作用的前提條件并非什么時(shí)候相關(guān)反饋都能有效地提高召回率前提條件1：用戶(hù)所構(gòu)建的初始查詢(xún)?cè)谝欢ǔ潭壬辖咏枨笪臋n，即：用戶(hù)了解文檔集詞匯表前提條件2：相關(guān)文檔之間非常相似，相關(guān)文檔和不相關(guān)文檔之間的相似度很低即所有相關(guān)文檔都緊密聚集在某個(gè)prototype周?chē)?728相關(guān)反饋的評(píng)價(jià)選擇上一講中的某個(gè)評(píng)價(jià)指標(biāo)，比如

P@10計(jì)算原始查詢(xún)q0

檢索結(jié)果的P@10指標(biāo)計(jì)算修改后查詢(xún)q1檢索結(jié)果的P@10指標(biāo)大部分情況下q1

的檢索結(jié)果精度會(huì)顯著高于q0!上述評(píng)價(jià)過(guò)程是否公平？2829相關(guān)反饋的評(píng)價(jià)公平的評(píng)價(jià)過(guò)程一定要基于存留文檔集(residualcollection):用戶(hù)沒(méi)有判斷的文檔集研究表明，采用這種方式進(jìn)行評(píng)價(jià)，相關(guān)反饋是比較成功的一種方法經(jīng)驗(yàn)而言，一輪相關(guān)反饋往往非常有用，相對(duì)一輪相關(guān)反饋，兩輪相關(guān)反饋效果的提高有限。2930相關(guān)反饋的評(píng)價(jià)相關(guān)反饋有效性的正確評(píng)價(jià)，必須要和其他需要花費(fèi)同樣時(shí)間的方法進(jìn)行對(duì)比相關(guān)反饋的一種替代方法:用戶(hù)修改并重新提交新的查詢(xún)用戶(hù)更傾向于修改和重新提交查詢(xún)而不是判斷文檔的相關(guān)性并沒(méi)有清晰的證據(jù)表明，相關(guān)反饋是用戶(hù)需要時(shí)間最少的方法3031課堂思考Web搜索引擎是否使用相關(guān)反饋？為什么？3132相關(guān)反饋存在的問(wèn)題相關(guān)反饋開(kāi)銷(xiāo)很大相關(guān)反饋生成的新查詢(xún)往往很長(zhǎng)長(zhǎng)查詢(xún)的處理開(kāi)銷(xiāo)很大用戶(hù)不愿意提供顯式的相關(guān)反饋應(yīng)用相關(guān)反饋之后返回的某些文檔的原因不易理解32隱式相關(guān)反饋基本思想：通過(guò)觀察用戶(hù)對(duì)當(dāng)前檢索結(jié)果采取的行為來(lái)給出對(duì)檢索結(jié)果的相關(guān)性判定判定不一定很準(zhǔn)確，但是省卻了用戶(hù)的顯式參與過(guò)程對(duì)用戶(hù)非當(dāng)前檢索行為或非檢索相關(guān)行為的分析也可以用于提高檢索的效果，這些主要是個(gè)性化信息檢索(PersonalizedIR)的內(nèi)容3333用戶(hù)行為種類(lèi)鼠標(biāo)鍵盤(pán)動(dòng)作：點(diǎn)擊鏈接、加入收藏夾、拷貝粘貼、停留、翻頁(yè)等等用戶(hù)眼球動(dòng)作：Eyetracking可以跟蹤用戶(hù)的眼球動(dòng)作拉近、拉遠(yuǎn)、瞟、凝視、往某個(gè)方向轉(zhuǎn)3434點(diǎn)擊行為(Clickthroughbehavior)FIELDVALUEUserID1162742023015Timestamp06/Nov/2006:00:01:35Queryterms嫁給警察的理由 URL/dispbbs.asp?Star=4&boardid=46&id=346721&page=1Pagenumber1Rank7Anchortext姑娘們，你們?cè)敢?lt;FONTcolor=#cc0033>嫁給警察</FONT>嗎？[慈溪社區(qū)]3535眼球動(dòng)作(通過(guò)鼠標(biāo)軌跡模擬)3636關(guān)于Eyetracking3737隱式相關(guān)反饋分析優(yōu)點(diǎn)：不需要用戶(hù)顯式參與，減輕用戶(hù)負(fù)擔(dān)用戶(hù)行為某種程度上反映用戶(hù)的興趣，具有可行性缺點(diǎn)：對(duì)行為分析有較高要求準(zhǔn)確度不一定能保證某些情況下需要增加額外設(shè)備383839偽相關(guān)反饋(Pseudo-relevancefeedback)基本思想：將相關(guān)反饋的人工操作部分進(jìn)行自動(dòng)化偽相關(guān)反饋算法對(duì)于用戶(hù)查詢(xún)返回有序的檢索結(jié)果假定前k篇文檔是相關(guān)的進(jìn)行相關(guān)反饋(如采用Rocchio算法)平均來(lái)講效果不錯(cuò)但是對(duì)于某些查詢(xún)而言可能結(jié)果很差幾次循環(huán)之后可能會(huì)導(dǎo)致查詢(xún)漂移(querydrift)3940TREC4上的偽相關(guān)反饋實(shí)驗(yàn)實(shí)驗(yàn)中的偽相關(guān)反饋方法對(duì)查詢(xún)只增加了20個(gè)詞項(xiàng)(使用Rocchio算法將增加更多的詞項(xiàng))上述結(jié)果表明，偽相關(guān)反饋在平均意義上說(shuō)是有效的方法40檢索方法相關(guān)文檔數(shù)目lnc.ltc3210lnc.ltc-PsRF3634Lnu.ltu3709Lnu.ltu-PsRF4350使用Cornell大學(xué)的SMART系統(tǒng)50個(gè)查詢(xún)，每個(gè)查詢(xún)基于前100個(gè)結(jié)果進(jìn)行反饋

偽相關(guān)反饋分析優(yōu)點(diǎn)：不用考慮用戶(hù)的因素，處理簡(jiǎn)單很多實(shí)驗(yàn)也取得了較好效果缺點(diǎn)：沒(méi)有通過(guò)用戶(hù)判斷，所以準(zhǔn)確率難以保證不是所有的查詢(xún)都會(huì)提高效果414142查詢(xún)擴(kuò)展(Queryexpansion)基本思想：通過(guò)對(duì)查詢(xún)?cè)~或短語(yǔ)添加補(bǔ)充信息，提高檢索召回率主要途徑：基于一些全局的資源進(jìn)行查詢(xún)擴(kuò)展，這些資源與查詢(xún)無(wú)關(guān)，包括：同義詞或近義詞詞典(thesaurus、wordnet等)查詢(xún)等價(jià)類(lèi)：人工構(gòu)建自動(dòng)構(gòu)建基于查詢(xún)?nèi)罩就诰?243查詢(xún)擴(kuò)展的例子4344基于同(近)義詞詞典的查詢(xún)擴(kuò)展具體方法：對(duì)查詢(xún)中的每個(gè)詞項(xiàng)t,將詞典中與t語(yǔ)義相關(guān)的詞擴(kuò)充到查詢(xún)中例子:HOSPITAL→MEDICAL通常會(huì)提高召回率可能會(huì)顯著降低正確率，特別是對(duì)那些有歧義的詞項(xiàng)廣泛應(yīng)用于特定領(lǐng)域(如科學(xué)、工程領(lǐng)域)的搜索引擎中前提條件：有一個(gè)好的同（近）義詞詞典4445基于人工詞典的擴(kuò)展樣例:PubMed45PubMed：著名的醫(yī)學(xué)文獻(xiàn)數(shù)據(jù)庫(kù)46同(近)義詞詞典的自動(dòng)構(gòu)建基本思想：通過(guò)計(jì)算文檔集中詞語(yǔ)之間的相似度來(lái)自動(dòng)生成同(近)義詞詞典相似度度量1:如果兩個(gè)詞各自的上下文共現(xiàn)詞類(lèi)似，那么它們類(lèi)似“car”≈“motorcycle”，因?yàn)樗鼈兌寂c“road”、“gas”及“l(fā)icense”之類(lèi)的詞共現(xiàn)，因此它們類(lèi)似相似度度量2:兩個(gè)詞，如果它們同某些詞具有某種給定的語(yǔ)法關(guān)系的話，那么它們類(lèi)似apples和pears與harvest,peel,eat,prepare具有一樣的動(dòng)賓關(guān)系,因此apples和pears肯定彼此類(lèi)似共現(xiàn)關(guān)系更加魯棒，而語(yǔ)法關(guān)系更加精確46基于共現(xiàn)的同(近)義詞典構(gòu)造通過(guò)詞典-文檔矩陣A計(jì)算詞項(xiàng)-詞項(xiàng)的相似度

C=AATwi,j=(ti,dj)的(歸一化)權(quán)重對(duì)每個(gè)ti,選擇C中對(duì)應(yīng)行向量中高權(quán)重

的詞項(xiàng)進(jìn)行擴(kuò)展tiNM如果矩陣A是0/1矩陣，那么C的每一項(xiàng)是什么？djN4748基于共現(xiàn)關(guān)系的同(近)義詞詞典樣例WordSpacedemoonweb48詞語(yǔ)同(近)義詞absolutelybottomedcaptivatingdoghousemakeupmediatingkeepinglithographspathogenssensesabsurdwhatsoevertotallyexactlynothingdipcopperdropstoppedslidetrimmedshimmerstunninglysuperblypluckywittydogporchcrawlingbesidedownstairsrepel