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

信息檢索與Web搜索

第10講

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

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

包含“plane”,但是不包含

“aircraft”顯然對(duì)于查詢q，一個(gè)簡(jiǎn)單的IR系統(tǒng)不會(huì)返回文檔d，即使d是和q最相關(guān)的文檔兩種方法：相關(guān)反饋和查詢擴(kuò)展23相關(guān)反饋的基本思想和流程基本思想：根據(jù)用戶對(duì)查詢結(jié)果的標(biāo)注，生成更有效的查詢，以提高召回率及準(zhǔn)確率流程：用戶提交一個(gè)(簡(jiǎn)短的)查詢搜索引擎返回一系列文檔用戶將部分返回文檔標(biāo)記為相關(guān)的，將部分文檔標(biāo)記為不相關(guān)的搜索引擎根據(jù)標(biāo)記結(jié)果更新查詢表示搜索引擎對(duì)新查詢進(jìn)行處理，返回新結(jié)果3相關(guān)反饋分類顯式相關(guān)反饋(UserFeedbackorExplicitFeedback)：用戶交互地進(jìn)行查詢結(jié)果標(biāo)注隱式相關(guān)反饋(ImplicitFeedback)：系統(tǒng)跟蹤用戶的行為來推測(cè)返回文檔的相關(guān)性，從而進(jìn)行反饋偽相關(guān)反饋或盲相關(guān)反饋(PseudoFeedbackorBlindFeedback)：沒有用戶參與，系統(tǒng)直接假設(shè)返回文檔的前k篇是相關(guān)的，然后進(jìn)行反饋445相關(guān)反饋舉例-156初始查詢的結(jié)果67用戶反饋:選擇相關(guān)結(jié)果78相關(guān)反饋后再次檢索的結(jié)果8相關(guān)反饋舉例-29初始查詢:[newspacesatelliteapplications]初始查詢的檢索結(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用戶將一些文檔標(biāo)記為相關(guān)“+”.910基于相關(guān)反饋進(jìn)行擴(kuò)展后的查詢查詢:[newspacesatelliteapplications]102.074new15.106space30.816satellite5.660application5.991nasa5.196eos4.196launch3.972aster3.516instrument3.446arianespace3.004bundespost2.806ss2.790rocket2.053scientist2.003broadcast1.172earth0.836oil0.646measure基于擴(kuò)展查詢的檢索結(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)查詢定義

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

15舉例

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

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

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

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

21Rocchio算法原理圖示22

得到22Rocchio算法原理圖示23

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

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

qm:修改后的查詢;q0:原始查詢;Dr

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

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

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

2526正反饋

vs.

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

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

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

的檢索結(jié)果精度會(huì)顯著高于q0!上述評(píng)價(jià)過程是否公平？2829相關(guān)反饋的評(píng)價(jià)公平的評(píng)價(jià)過程一定要基于存留文檔集(residualcollection):用戶沒有判斷的文檔集研究表明，采用這種方式進(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)反饋的一種替代方法:用戶修改并重新提交新的查詢用戶更傾向于修改和重新提交查詢而不是判斷文檔的相關(guān)性并沒有清晰的證據(jù)表明，相關(guān)反饋是用戶需要時(shí)間最少的方法3031課堂思考Web搜索引擎是否使用相關(guān)反饋？為什么？3132相關(guān)反饋存在的問題相關(guān)反饋開銷很大相關(guān)反饋生成的新查詢往往很長(zhǎng)長(zhǎng)查詢的處理開銷很大用戶不愿意提供顯式的相關(guān)反饋應(yīng)用相關(guān)反饋之后返回的某些文檔的原因不易理解32隱式相關(guān)反饋基本思想：通過觀察用戶對(duì)當(dāng)前檢索結(jié)果采取的行為來給出對(duì)檢索結(jié)果的相關(guān)性判定判定不一定很準(zhǔn)確，但是省卻了用戶的顯式參與過程對(duì)用戶非當(dāng)前檢索行為或非檢索相關(guān)行為的分析也可以用于提高檢索的效果，這些主要是個(gè)性化信息檢索(PersonalizedIR)的內(nèi)容3333用戶行為種類鼠標(biāo)鍵盤動(dòng)作：點(diǎn)擊鏈接、加入收藏夾、拷貝粘貼、停留、翻頁等等用戶眼球動(dòng)作：Eyetracking可以跟蹤用戶的眼球動(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)作(通過鼠標(biāo)軌跡模擬)3636關(guān)于Eyetracking3737隱式相關(guān)反饋分析優(yōu)點(diǎn)：不需要用戶顯式參與，減輕用戶負(fù)擔(dān)用戶行為某種程度上反映用戶的興趣，具有可行性缺點(diǎn)：對(duì)行為分析有較高要求準(zhǔn)確度不一定能保證某些情況下需要增加額外設(shè)備383839偽相關(guān)反饋(Pseudo-relevancefeedback)基本思想：將相關(guān)反饋的人工操作部分進(jìn)行自動(dòng)化偽相關(guān)反饋算法對(duì)于用戶查詢返回有序的檢索結(jié)果假定前k篇文檔是相關(guān)的進(jìn)行相關(guān)反饋(如采用Rocchio算法)平均來講效果不錯(cuò)但是對(duì)于某些查詢而言可能結(jié)果很差幾次循環(huán)之后可能會(huì)導(dǎo)致查詢漂移(querydrift)3940TREC4上的偽相關(guān)反饋實(shí)驗(yàn)實(shí)驗(yàn)中的偽相關(guān)反饋方法對(duì)查詢只增加了20個(gè)詞項(xiàng)(使用Rocchio算法將增加更多的詞項(xiàng))上述結(jié)果表明，偽相關(guān)反饋在平均意義上說是有效的方法40檢索方法相關(guān)文檔數(shù)目lnc.ltc3210lnc.ltc-PsRF3634Lnu.ltu3709Lnu.ltu-PsRF4350使用Cornell大學(xué)的SMART系統(tǒng)50個(gè)查詢，每個(gè)查詢基于前100個(gè)結(jié)果進(jìn)行反饋

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