第10講XML檢索XMLRetrieval12012/10/25提綱2上一講回顧

簡介基本的XML概念XMLIR中的挑戰(zhàn)基于向量空間模型的XMLIRXMLIR評價提綱3上一講回顧

簡介基本的XML概念XMLIR中的挑戰(zhàn)基于向量空間模型的XMLIRXMLIR評價4上一講內(nèi)容交互式相關(guān)反饋(Interactiverelevancefeedback):在初始檢索結(jié)果的基礎(chǔ)上，通過用戶交互指定哪些文檔相關(guān)或不相關(guān)，然后改進(jìn)檢索的結(jié)果最著名的相關(guān)反饋方法：Rocchio相關(guān)反饋查詢擴(kuò)展(Queryexpansion):通過在查詢中加入同義或者相關(guān)的詞項(xiàng)來提高檢索結(jié)果相關(guān)詞項(xiàng)的來源:人工編輯的同義詞詞典、自動構(gòu)造的同義詞詞典、查詢?nèi)罩镜鹊取?5相關(guān)反饋的基本思想用戶提交一個(簡短的)查詢搜索引擎返回一系列文檔用戶將部分返回文檔標(biāo)記為相關(guān)的，將部分文檔標(biāo)記為不相關(guān)的搜索引擎根據(jù)標(biāo)記結(jié)果計算得到信息需求的一個新查詢表示。當(dāng)然我們希望該表示好于初始的查詢表示搜索引擎對新查詢進(jìn)行處理，返回新結(jié)果新結(jié)果可望（理想上說）有更高的召回率56Rocchio1971算法(SMART系統(tǒng)使用)

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

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

α,β,γ:權(quán)重新查詢向相關(guān)文檔靠攏而遠(yuǎn)離非相關(guān)文檔αvs.β/γ設(shè)置中的折中:如果判定的文檔數(shù)目很多，那么

β/γ可以考慮設(shè)置得大一些一旦計算后出現(xiàn)負(fù)權(quán)重，那么將負(fù)權(quán)重都設(shè)為0在向量空間模型中，權(quán)重為負(fù)是沒有意義的。6實(shí)際中使用的公式:7偽相關(guān)反饋(Pseudo-relevancefeedback)偽相關(guān)反饋對于真實(shí)相關(guān)反饋的人工部分進(jìn)行自動化偽相關(guān)反饋算法對于用戶查詢返回有序的檢索結(jié)果假定前

k

篇文檔是相關(guān)的進(jìn)行相關(guān)反饋(如Rocchio)平均上效果不錯但是對于某些查詢而言可能結(jié)果很差幾次循環(huán)之后可能會導(dǎo)致查詢漂移(querydrift)78查詢擴(kuò)展(Queryexpansion)查詢擴(kuò)展是另一種提高召回率的方法我們使用“全局查詢擴(kuò)展”來指那些“查詢重構(gòu)(queryreformulation)的全局方法”在全局查詢擴(kuò)展中，查詢基于一些全局的資源進(jìn)行修改，這些資源是與查詢無關(guān)的主要使用的信息:同義詞或近義詞同義詞或近義詞詞典(thesaurus)兩種同(近)義詞詞典構(gòu)建方法：人工構(gòu)建和自動構(gòu)建89查詢擴(kuò)展的類型人工構(gòu)建的同(近)義詞詞典(人工編輯人員維護(hù)的詞典，如PubMed)自動導(dǎo)出的同(近)義詞詞典(比如，基于詞語的共現(xiàn)統(tǒng)計信息)基于查詢?nèi)罩就诰虺龅牟樵兊葍r類(Web上很普遍，比如上面的“palm”例子)9本講內(nèi)容XMLIR中的基本概念XMLIR中的挑戰(zhàn)XMLIR中的向量空間模型XMLIR評價10提綱11上一講回顧

簡介基本的XML概念XMLIR中的挑戰(zhàn)基于向量空間模型的XMLIRXMLIR評價12IRvs.關(guān)系數(shù)據(jù)庫

IR系統(tǒng)常常與關(guān)系數(shù)據(jù)庫進(jìn)行對比(RDB)傳統(tǒng)上說，IR系統(tǒng)從無結(jié)構(gòu)文本(unstructuredtext,指沒有標(biāo)記的“生”文本--“raw”textwithoutmarkup)中返回信息

RDB系統(tǒng)主要用于查詢關(guān)系型數(shù)據(jù)(relationaldata)，即一系列記錄集合，這些記錄中包含預(yù)先定義的屬性及屬性值，如員工號、職位和工資

一些包含文本的結(jié)構(gòu)化數(shù)據(jù)最好建模成結(jié)構(gòu)化文檔而不是關(guān)系型數(shù)據(jù)，結(jié)構(gòu)化文檔的檢索稱為結(jié)構(gòu)化檢索

（structuredretrieval）1213結(jié)構(gòu)化檢索(Structuredretrieval)

基本配置：

結(jié)構(gòu)化或非結(jié)構(gòu)化查詢+結(jié)構(gòu)化文檔結(jié)構(gòu)化檢索的應(yīng)用場景數(shù)字圖書館、專利數(shù)據(jù)庫、博客、包含已標(biāo)注命名實(shí)體（如人名、地名）的文本例子數(shù)字圖書館:

givemeafull-lengtharticleonfastfouriertransforms專利:givemepatenswhoseclaimsmentionRSApublickeyencryptionandthatciteUSpatent4,405,829實(shí)體標(biāo)記文本:givemearticlesaboutsightseeingtoursoftheVaticanandtheColiseum13RDB并不適合上述場景14采用RDB會存在下列三個主要問題無序的DB系統(tǒng)可能返回大量文章，這些文章提到Vatican、theColiseum和sightseeingtours，但是并沒有按照它們和查詢的相關(guān)度排序大部分用戶都很難精確描述結(jié)構(gòu)化的限制條件。比如，用戶可能并不知道搜索系統(tǒng)支持對哪些結(jié)構(gòu)化元素的查詢

toursAND(COUNTRY:VaticanOR LANDMARK:Coliseum)?

toursAND(STATE:VaticanORBUILDING:Coliseum)?用戶可能對結(jié)構(gòu)化搜索和高級搜索很不熟悉，或者他們壓根就不想用這些搜索功能。

解決辦法：將排序檢索模型用于結(jié)構(gòu)化文檔搜索來解決上述問題15結(jié)構(gòu)化檢索

一個對結(jié)構(gòu)化文檔進(jìn)行編碼的標(biāo)準(zhǔn)：ExtensibleMarkupLanguage(XML)結(jié)構(gòu)化IRXMLIR同樣適用于其他標(biāo)記語言(HTML,SGML,…)15提綱16上一講回顧

簡介基本的XML概念XMLIR中的挑戰(zhàn)基于向量空間模型的XMLIRXMLIR評價17XML文檔有序帶標(biāo)記樹樹上的每個節(jié)點(diǎn)都是一個XML元素（XMLelement），它由起始標(biāo)簽（tag）和結(jié)束標(biāo)簽來界定(如<title…>,</title…>)一個XML元素可以有一個或多個XML屬性（XMLattribute）。(如

number)屬性可以有屬性值(如vii)屬性可以有子元素(如

title,verse)

<play> <author>Shakespeare</author>

<title>Macbeth</title>

<act

number=“I”>

<scene

number=“”vii”>

<title>Macbeth’scastle</title>

<verse>WillIwithwine …</verse> </scene> </act> </play>1718XML文檔1819XML文檔葉節(jié)點(diǎn)由文本構(gòu)成19XML文檔內(nèi)部節(jié)點(diǎn)對文檔結(jié)構(gòu)或元數(shù)據(jù)（author）進(jìn)行編碼21XML基礎(chǔ)知識

XML文檔對象模型(XMLDocumentsObjectModel,XMLDOM):訪問和處理XML文檔的標(biāo)準(zhǔn)DOM將元素、屬性及元素內(nèi)部的文本表示成樹中的節(jié)點(diǎn)使用DOMAPI，我們可以從根元素出發(fā)，依據(jù)元素間的父子關(guān)系，自上而下對整個XML文檔進(jìn)行處理XPath:XML文檔集中的路徑表達(dá)式描述標(biāo)準(zhǔn)路徑表達(dá)式也稱為XML上下文(context)或直接稱上下文Schema:給出了XML文檔所允許的結(jié)構(gòu)限制條件。比如，莎士比亞劇本的schema規(guī)定，場（scene）只能以幕（act）的子節(jié)點(diǎn)方式出現(xiàn)。XML文檔的兩個schema標(biāo)準(zhǔn)分別是XMLDTD（documenttypedefinition，文檔類型定義）和XMLschema

21提綱22上一講回顧

簡介基本的XML概念XMLIR中的挑戰(zhàn)基于向量空間模型的XMLIRXMLIR評價23挑戰(zhàn)1:返回文檔的一部分

XML檢索中，用戶希望返回文檔的一部分（即XML元素），而不像非結(jié)構(gòu)化檢索那樣往往返回整個文檔上述情況下，用戶可能在查找

場(scene)但是，另一個沒有具體指定返回節(jié)點(diǎn)的查詢Macbeth，應(yīng)該返回劇本的名稱而不是某個子單位

解決辦法:結(jié)構(gòu)化文檔檢索原理(structureddocumentretrievalprinciple)例子如果在《莎士比亞全集》中查找Macbeth’scastle，那么到底應(yīng)該返回場（scene）、幕（act）還是整個劇本呢？2324結(jié)構(gòu)化文檔檢索原理

上述原理會引發(fā)這樣一種檢索策略，即返回包含信息需求的最小單位但是，要在算法上實(shí)現(xiàn)這種原理是非常困難的。比如查詢：title:Macbeth，整個劇本的標(biāo)題Maccbeth以及第一幕第六場的標(biāo)題Macbeth’scastle都是包含匹配詞項(xiàng)Macbeth的較好的命中結(jié)果。然而在這個例子中，劇本的標(biāo)題這個位于更高層的節(jié)點(diǎn)作為答案卻更合適確定查詢應(yīng)答的正確層次是非常困難的。結(jié)構(gòu)化文檔檢索原理選擇最合適的文檔部分:系統(tǒng)應(yīng)該總是檢索出回答查詢的最明確最具體的文檔部分24挑戰(zhàn)2:如何確定文檔的索引單位25IR索引和排名中的核心概念：文檔單位或索引單位在非結(jié)構(gòu)化檢索中，合適的文檔單位往往比較明顯，如PC上的文檔、郵件、Web上的網(wǎng)頁等等而在結(jié)構(gòu)化檢索中，卻有定義索引單位的一系列不同的方法將節(jié)點(diǎn)分組，形成多個互不重疊的偽文檔（pseudodocument)索引最大元素，然后自頂向下(topdown)后處理索引葉節(jié)點(diǎn)，然后自底向上(bottomup)進(jìn)行后處理擴(kuò)展對所有元素建立索引XML索引單位:方法1-不重疊偽文檔法26將節(jié)點(diǎn)分組，形成多個互不重疊的偽文檔索引單位:book、chapter、section但是這些單位之間沒有重疊缺點(diǎn):由于這些偽文檔的內(nèi)容不連貫，所以它們對用戶而言可能沒有意義XML索引單位：方法2-自頂向下法27自頂向下(分兩步走):可以使用最大的一個元素作為索引單位，比如，在一個書的集合中以元素book為索引單位然后通過對結(jié)果進(jìn)行后處理，從而在每本書中找到更適合作為答案的子元素上述”分兩步走”的做法往往并不能返回最佳匹配子元素，這是因?yàn)檎緯c查詢的相關(guān)性并不能代表其子元素與查詢的相關(guān)性XML索引單位：方法3-自底向上法28自底向上:與上述先返回大單位然后識別子元素（自頂向下）的方法不同的是，可以直接對所有葉節(jié)點(diǎn)進(jìn)行搜索并返回最相關(guān)的一些節(jié)點(diǎn)，然后通過后處理將它們擴(kuò)展成更大的單位和自頂向下存在類似的問題：個葉節(jié)點(diǎn)的相關(guān)性往往不能代表包含該葉節(jié)點(diǎn)的上層元素的相關(guān)性29XML索引單位:方法4—索引所有元素

索引所有元素是限制最少的方法，也存在下列問題：很多XML元素并不是有意義的搜索結(jié)果，比如，排版相關(guān)的元素（如<b>definitely</b>）或者不能脫離上下文進(jìn)行單獨(dú)解釋的ISBN書號等對所有元素建立索引也意味著搜索結(jié)果將會有高度的冗余性。 Wecallelementsthatarecontainedwithineachothernestedelements.元素之間互相包含的關(guān)系稱為嵌套（nested）。對用戶而言，在返回結(jié)果中包含冗余的嵌套元素則顯得不太友好例子查詢Macbeth’scastle，我們會返回從根節(jié)點(diǎn)到Macbeth’scastle路徑上的所有play、act、scene和title元素。此時，葉節(jié)點(diǎn)在結(jié)果集合中會出現(xiàn)4次，其中1次是作為索引對象直接出現(xiàn)的，而其他3次是作為其他元素的一部分出現(xiàn)的29挑戰(zhàn)3：元素嵌套針對元素嵌套所造成的冗余性，普遍的做法是對返回元素進(jìn)行限制。這些限制策略包括：這些限制策略包括：忽略所有的小元素忽略用戶不會瀏覽的所有元素類型（這需要記錄當(dāng)前XML檢索系統(tǒng)的運(yùn)行日志信息忽略通常被評估者判定為不相關(guān)性的元素類型（如果有相關(guān)性判定的話）只保留系統(tǒng)設(shè)計人員或圖書館員認(rèn)定為有用的檢索結(jié)果所對應(yīng)的元素類型在大部分上述方法中，結(jié)果集中仍然包含嵌套元素。30挑戰(zhàn)3：元素嵌套進(jìn)一步的處理策略:可以通過一個后處理過程來去掉某些元素，從而降低索引結(jié)果的冗余性在結(jié)果列表中將多個嵌套元素折疊起來，并通過對查詢詞項(xiàng)進(jìn)行高亮顯示（highlighting）來吸引用戶關(guān)注相關(guān)段落

高亮顯示好處1:允許用戶掃描中等規(guī)模的元素(如section)，因此，如果section和paragraph都出現(xiàn)在結(jié)果列表中，那么顯示section就足夠了。好處2:paragraph會和它的上下文（包含該paragraph的section）在一起展示。即使paragraph本身就可以滿足查詢的需求，這種上下文仍然對于解釋該paragraph很有幫助。31嵌套元素和詞項(xiàng)統(tǒng)計信息與嵌套相關(guān)的另一個挑戰(zhàn)：在計算用于排序的詞項(xiàng)統(tǒng)計信息(特別是idf)時，需要區(qū)別詞項(xiàng)的不同上下文解決辦法:

為每一個XML上下文-詞項(xiàng)對計算idf數(shù)據(jù)稀疏問題(許多上下文—詞項(xiàng)對出現(xiàn)過少從而導(dǎo)致對文檔頻率估計的可靠性不足)一個折中方案是在區(qū)分上下文時只考慮詞項(xiàng)的父節(jié)點(diǎn)x，而不考慮從根節(jié)點(diǎn)到x路徑上的其他部分。

例子Gates出現(xiàn)在author節(jié)點(diǎn)下與其出現(xiàn)在內(nèi)容元素中（如section中，此時代表的是gate的復(fù)數(shù)）毫無關(guān)系。于是，在這個例子中，為Gates計算一個單獨(dú)的文檔頻率df意義不大。32提綱33上一講回顧

簡介基本的XML概念XMLIR中的挑戰(zhàn)基于向量空間模型的XMLIRXMLIR評價主要思路:詞匯化子樹(lexicalizedsubtree)目標(biāo):對向量空間中的每一維都同時考慮單詞及其在XML樹中的位置信息做法:將XML文檔映射成詞匯化子樹BookTitleAuthorBillGatesMicrosoftAuthorBillGatesMicrosoftBillGatesTitleMicrosoftAuthorGatesAuthorBillBookTitleMicrosoft...Book34主要思路:詞匯化子樹考慮每個文本節(jié)點(diǎn)（葉節(jié)點(diǎn)）并將它們分裂成多個節(jié)點(diǎn)，每個節(jié)點(diǎn)對應(yīng)一個詞。例如，將

BillGates

分裂成

Bill

和Gates我們將向量空間的每一維定義為文檔的詞匯化子樹，這些子樹至少包含詞匯表中的一個詞項(xiàng)BookTitleAuthorBillGatesMicrosoftAuthorBillGatesMicrosoftBillGatesTitleMicrosoftAuthorGatesAuthorBillBookTitleMicrosoft...Book35詞匯化子樹于是就可以將查詢和文檔表示成這些詞匯化子樹空間上的向量，并根據(jù)前面的向量相似度公式進(jìn)行相似度計算非結(jié)構(gòu)化vs.結(jié)構(gòu)化IR中的向量空間相似度計算方法兩者的主要區(qū)別在于，前者中向量的每一維對應(yīng)一個詞項(xiàng)，而后者中對應(yīng)一棵詞匯化子樹36結(jié)構(gòu)化詞項(xiàng)(Structuralterm)在向量空間維度和查詢的精度之間存在著一個折中如果將每一維限制為詞匯表中的詞項(xiàng)，那么得到的是一個標(biāo)準(zhǔn)的向量空間檢索系統(tǒng)。這種系統(tǒng)下得到的很多文檔在結(jié)構(gòu)上并不與查詢匹配(例如，title中的Gates和author中的Gates)

如果每棵詞匯化子樹都對應(yīng)空間一維，那么空間的維數(shù)會變得太大折中方案:對所有的最終以單個詞項(xiàng)結(jié)束的路徑建立索引，換句話說，對所有的XML上下文/詞項(xiàng)對建立索引。這種XML上下文/詞項(xiàng)對被稱為結(jié)構(gòu)化詞項(xiàng)（structuralterm），記為<c,t>:其中c是XML上下文，t是詞項(xiàng)37上下文相似度(Contextresemblance)一個簡單的度量查詢中路徑cq和文檔中路徑cd相似度的指標(biāo)是上下文相似度（contextresemblance）函數(shù)CR，其定義如下：其中|cq|和|cd|分別是查詢路徑和文檔路徑中的節(jié)點(diǎn)數(shù)目，并且當(dāng)且僅當(dāng)可以通過插入額外的節(jié)點(diǎn)使cq轉(zhuǎn)換成cd時，cq和cd才能匹配。38上下文相似度計算的例子Cr(cq4,cd2)=3/4=0.75.如果q

和d

相等，那么Cr(cq,cd)=1.039上下文相似度計算的例子Cr(cq4,cd3)=3/5=0.6.40文檔相似度計算方法最終的文檔得分計算可以看成普通余弦相似度計算方法的一個變形。我們將這個計算公式稱為SimNoMerge.SimNoMerge(q,d)=

V非結(jié)構(gòu)化詞項(xiàng)的詞匯表B是所有XML上下文的集合weight（q,t,c）和weight（d,t,c）分別是詞項(xiàng)t在查詢q和文檔d的上下文c中的權(quán)重。我們可以采用第6章的某種權(quán)重機(jī)制來計算這個權(quán)重(比如，idft×wft,d。逆文檔頻率idft的值取決于dft計算時我們所利用的元素)SimNoMerge(q,d)并不是一個真正的余弦相似度計算函數(shù)，因?yàn)樗闹悼赡軙^1.041SimNoMerge算法的偽代碼

ScoreDocumentsWithSimNoMerge(q,B,V,N,normalizer)42提綱43上一講回顧

簡介基本的XML概念XMLIR中的挑戰(zhàn)基于向量空間模型的XMLIRXMLIR評價INEX(InitiativefortheEvaluationofXMLretrieval)INEX:XML檢索研究中的首要評測平臺，它通過協(xié)作產(chǎn)生參考文檔集、查詢集及相關(guān)性判斷。在每年一度的INEX會議上，研究人員展示并討論交流各自的研究結(jié)果。INEX2002文檔集包含大概12000篇來自IEEE期刊的文章。(自2006年開始，INEX使用英文Wikipedia這個更大的庫)文檔的相關(guān)性判定主要通過人工判斷來完成INEX2002文檔集統(tǒng)計信息12,107文檔數(shù)目494MB規(guī)模1995—2002文章發(fā)表年份1,532平均每篇文檔中的XML節(jié)點(diǎn)個數(shù)6.9平均每個節(jié)點(diǎn)的深度30CAS主題的數(shù)目30CO主題的數(shù)目44INEX主題兩種類型:僅基于內(nèi)容(content-only或

CO)的主題:和非結(jié)構(gòu)化信息檢索中一樣的常規(guī)關(guān)鍵詞查詢內(nèi)容結(jié)構(gòu)相結(jié)合(content-and-structure或

CAS)的主題:CAS主題在關(guān)鍵詞基礎(chǔ)上增加了結(jié)構(gòu)化限制由于CAS查詢同時包含結(jié)構(gòu)信息和內(nèi)容信息，其相關(guān)性判斷就比非結(jié)構(gòu)化中的相關(guān)性判斷要復(fù)雜得多45INEX相關(guān)性判斷INEX2002定義了部件覆蓋度(Componentcoverage)和主題相關(guān)性(topicalrelevance)作為相關(guān)性判斷的兩個方面部件覆蓋度評價的是返回元素在結(jié)構(gòu)上是否正確，也就是說，其在樹中的層次既不太高也不太低。有四種情況:精確覆蓋（E）。所需求的信息是部件的主要主題，并且該部件是一個有意義的信息單位覆蓋度太?。⊿）。所需求的信息是部件的主要主題，但是該部件不是一個有意義（自包含）的信息單位覆蓋度太大（L）。所需求的信息在部件中，但不是主要主題無覆蓋（N）。所需求的信息不是部件的主題46INEX相關(guān)性判斷主題相關(guān)性也有4個層次：強(qiáng)相關(guān)（3）、較相關(guān)（2）、弱相關(guān)（1）和不相關(guān)（0）