第二章信息檢索模型

1、信息檢索模型,,內(nèi)容提要,信息檢索系統(tǒng)的形式化表示布爾邏輯模型向量空間模型概率模型其他檢索模型,什么是模型？,模型是采用數(shù)學(xué)工具，對(duì)現(xiàn)實(shí)世界某種事物或某種運(yùn)動(dòng)的抽象描述面對(duì)相同的輸入，模型的輸出應(yīng)能夠無(wú)限地逼近現(xiàn)實(shí)世界的輸出舉例：天氣的預(yù)測(cè)模型信息檢索模型給出了文檔的表示方法，查詢的表示方式以及查詢與文檔的匹配過(guò)程,信息檢索模型,信息檢索模型是指如何對(duì)查詢和文檔進(jìn)行表示，然后對(duì)它們進(jìn)行相似度計(jì)算的框架和方法。本質(zhì)上是對(duì)相

2、關(guān)度建模。信息檢索模型是IR中的核心內(nèi)容之一。,信息檢索模型,一個(gè)信息檢索模型是由文檔表示、查詢、關(guān)系、模型框架構(gòu)成的四元組。四元組：System=(D,Q,F,R(dj,qi))D 文檔集的表示Q 用戶需求的表示F 文檔表示、查詢表示和他們之間關(guān)系的模型框架（Frame）R(dj ，qi) 給出Query qi和Document dj 的評(píng)分,文檔邏輯視圖,D是一個(gè)文檔集合，通常由文檔邏輯視圖來(lái)表示?？梢允且唤M索

3、引詞或關(guān)鍵詞。既可以自動(dòng)提取，也可以是由人主觀指定。,匹配處理框架（F）,在信息集合（D）與需求集合（F）之間建立模型化處理的框架與規(guī)則。不同檢索模型的匹配處理的數(shù)學(xué)機(jī)制是不同的。布爾模型：集合論的基本運(yùn)算向量空間模型：多維向量空間理論和向量線性代數(shù)概率模型：集合論、概率運(yùn)算和Bayes法則,匹配計(jì)算函數(shù)R,匹配函數(shù)R（dj，q）用于計(jì)算任一信息dj（dj∈D）與任一提問(wèn)q（q∈Q）形成的信息——提問(wèn)對(duì)（dj，q）之間的相似度大

4、小。一般地，R（dj，q）的函數(shù)值為一實(shí)數(shù)，其取值區(qū)間為[0，1] 匹配函數(shù)的特點(diǎn)：計(jì)算方法簡(jiǎn)單，計(jì)算量?。缓瘮?shù)值在取值區(qū)間均勻分布；針對(duì)某一提問(wèn)所獲取的相關(guān)文檔集合，能夠?qū)崿F(xiàn)合理的排序輸出。,信息檢索模型決定于：從什么樣的視角去看待查詢式和文檔？基于什么樣的理論去看待查詢式和文檔的關(guān)系？如何計(jì)算查詢式和文檔之間的相似度？,模型的分類,從所使用的數(shù)學(xué)方法上分：基于集合論的IR模型(Set Theoretic models

5、)布爾模型基于模糊集的模型擴(kuò)展布爾模型基于代數(shù)論的IR模型(Algebraic models)向量空間模型潛性語(yǔ)義索引模型基于概率統(tǒng)計(jì)的IR模型(Probabilistic models)回歸模型二元獨(dú)立概率模型語(yǔ)言模型建模IR模型,1 布爾模型(Boolean Model),布爾模型是建立經(jīng)典集合論和布爾邏輯代數(shù)的基礎(chǔ)上。 優(yōu)勢(shì)：“集合”概念直觀容易被理解和接受,布爾模型描述,文檔表示一個(gè)文檔被表示為

6、關(guān)鍵詞的集合查詢式表示查詢式(Queries)被表示為關(guān)鍵詞的布爾組合，用“與、或、非”連接起來(lái)，并用括弧指示優(yōu)先次序匹配一個(gè)文檔當(dāng)且僅當(dāng)它能夠滿足布爾查詢式時(shí)，才將其檢索出來(lái)檢索策略基于二值判定標(biāo)準(zhǔn),布爾模型的基本原理布爾模型在解釋信息檢索處理過(guò)程時(shí)，主要遵守的兩條原則：系統(tǒng)索引詞集合中的每一個(gè)索引詞在一篇文檔中只有兩種狀態(tài)：出現(xiàn)或不出現(xiàn)。每個(gè)索引詞的權(quán)值wij∈{0,1}檢索提問(wèn)式q由三種布爾邏輯運(yùn)算符“and”、

7、“or”、“not”連接索引詞來(lái)構(gòu)成。 根據(jù)布爾邏輯的運(yùn)算規(guī)定，提問(wèn)式q可以被表示成由合取子項(xiàng)（conjunctive components）組成的析取范式（disjunctive normal form,簡(jiǎn)稱dnf）形式。,如：提問(wèn)式 q = k1 and （k2 or not k3）可寫(xiě)成等價(jià)的析取范式形式： q dnf = (k1 and k2 and k3) or (k1 and k2 and not k3

8、) or (k1 and not k2 and not k3 ) 這里q dnf是提問(wèn)式q的主析取范式?？蛇M(jìn)一步簡(jiǎn)化表示 為： q dnf =(1,1,1) or (1,1,0) or (1,0,0) 其中： (1,1,1) or (1,1,0) or (1,0,0)是q dnf的三個(gè)合取子項(xiàng)qcc，他們是一組向量，由對(duì)應(yīng)的三元組(k1 , k2 , k3)的每一個(gè)分量取0或1得到。

9、 基于以上規(guī)則和假定，布爾模型對(duì)于任一篇文獻(xiàn)dj∈D，定義與用戶提問(wèn)q的匹配函數(shù)為：,1 如果存在qcc|(qcc∈qdnf)且對(duì)于任意ki, 有 gi(dj) = gi(qcc) Sim(dj,q)= 0 其他 例如: 文檔集合D存在兩篇文檔d1和d2,其中,d1含有關(guān)鍵詞k1和k2,d2含有關(guān)鍵詞k1

10、和k3,則它們的文檔向量分別為: d1 =(1,1,0) , d2 =(1,0,1) 根據(jù)匹配函數(shù)的定義,顯然,d1與提問(wèn)式q = k1 and （k2 or not k3）的匹配函數(shù)值是1,即d1與提問(wèn)q是相關(guān)的; d2與提問(wèn)式q的匹配函數(shù)值是0, 表明d2與提問(wèn)q是不相關(guān)的。,,,,,,,例子：q = 病毒 AND （計(jì)算機(jī) OR 電腦）AND NOT醫(yī) d1: …據(jù)報(bào)道，計(jì)算機(jī)病

11、毒近日猖獗…d2: …小王雖然是學(xué)醫(yī)的，但對(duì)研究電腦病毒也很感興趣，最近發(fā)明了一種…d3: …計(jì)算機(jī)程序發(fā)現(xiàn)了愛(ài)滋病病毒的傳播途徑… 哪些文檔會(huì)被檢索出來(lái)？,布爾模型的優(yōu)點(diǎn),到目前為止，布爾模型是最常用的檢索模型，因?yàn)椋河捎诓樵兒?jiǎn)單，因此容易理解通過(guò)使用復(fù)雜的布爾表達(dá)式，可以很方便地控制查詢結(jié)果相當(dāng)有效的實(shí)現(xiàn)方法相當(dāng)于識(shí)別包含了一個(gè)某個(gè)特定term的文檔經(jīng)過(guò)某種訓(xùn)練的用戶可以容易地寫(xiě)出布爾查詢式布

12、爾模型可以通過(guò)擴(kuò)展來(lái)包含排序的功能，即“擴(kuò)展的布爾模型”,布爾模型存在的問(wèn)題,布爾模型被認(rèn)為是功能最弱的方式，其主要問(wèn)題在于不支持部分匹配，而完全匹配會(huì)導(dǎo)致太多或者太少的結(jié)果文檔被返回非常剛性: “與”意味著全部; “或”意味著任何一個(gè)很難控制被檢索的文檔數(shù)量原則上講，所有被匹配的文檔都將被返回很難對(duì)輸出進(jìn)行排序不考慮索引詞的權(quán)重，所有文檔都以相同的方式和查詢相匹配很難進(jìn)行自動(dòng)的相關(guān)反饋如果一篇文檔被用戶確認(rèn)為相關(guān)或者不相

13、關(guān)，怎樣相應(yīng)地修改查詢式呢？,課堂練習(xí)題（1）,課堂思考題：想查關(guān)于今年超女5進(jìn)4比賽的新聞，用布爾模型怎么構(gòu)造查詢？,參考答案,􀂄(2006 OR 今年) AND (超級(jí)女聲OR 超女OR 超級(jí)女生) AND (6進(jìn)5 OR 六進(jìn)五OR 六AND 進(jìn)AND 五)􀂄表達(dá)式相當(dāng)復(fù)雜，構(gòu)造困難！􀂄不嚴(yán)格的話結(jié)果過(guò)多，而且很多不相關(guān)；非常嚴(yán)格的話結(jié)果會(huì)很少，漏掉很多結(jié)果。,課堂習(xí)題（

14、2）,2 向量空間模型,向量空間模型(Vector Space Model)是康奈爾大學(xué)Salton1970年代提出并倡導(dǎo)成功應(yīng)用于SMART（ System for the Manipulation and Retrieval of Text）文本檢索系統(tǒng)這一系統(tǒng)理論框架到現(xiàn)在仍然是信息檢索技術(shù)研究的基礎(chǔ),向量空間模型的基本原理,,,,,,,,,,文檔,提問(wèn),關(guān)鍵字的權(quán)重矢量,,關(guān)鍵字的權(quán)重矢量,匹配,檢索到文獻(xiàn),模型的描述,文檔

15、D(Document)：泛指文檔或文檔中的一個(gè)片段（如文檔中的標(biāo)題、摘要、正文等）。索引項(xiàng)t（Term）：指出現(xiàn)在文檔中能夠代表文檔性質(zhì)的基本語(yǔ)言單位（如字、詞等），也就是通常所指的檢索詞，這樣一個(gè)文檔D就可以表示為D(t1,t2,…,tn)，其中n就代表了檢索字的數(shù)量。 特征項(xiàng)權(quán)重Wk（Term Weight）：指特征項(xiàng)tn能夠代表文檔D能力的大小，體現(xiàn)了特征項(xiàng)在文檔中的重要程度。 相似度S（Similarity）：指兩個(gè)文檔內(nèi)

16、容相關(guān)程度的大小,模型的特點(diǎn),基于關(guān)鍵詞(一個(gè)文本由一個(gè)關(guān)鍵詞列表組成)根據(jù)關(guān)鍵詞的出現(xiàn)頻率計(jì)算相似度例如：文檔的統(tǒng)計(jì)特性用戶規(guī)定一個(gè)詞項(xiàng)(term)集合，可以給每個(gè)詞項(xiàng)附加權(quán)重未加權(quán)的詞項(xiàng): Q = ? database; text; information ?加權(quán)的詞項(xiàng): Q = ? database 0.5; text 0.8; information 0.2 ?查詢式中沒(méi)有布爾條件根據(jù)相似度對(duì)輸出結(jié)果進(jìn)行排序

17、支持自動(dòng)的相關(guān)反饋有用的詞項(xiàng)被添加到原始的查詢式中例如：Q ? ? database; text; information; document ?,模型中的問(wèn)題,怎樣確定文檔中哪些詞是重要的詞？（索引項(xiàng)）怎樣確定一個(gè)詞在某個(gè)文檔中或在整個(gè)文檔集中的重要程度？（權(quán)重）怎樣確定一個(gè)文檔和一個(gè)查詢式之間的相似度？,索引項(xiàng)的選擇,若干獨(dú)立的詞項(xiàng)被選作索引項(xiàng)(index terms) or 詞表vocabulary索引項(xiàng)代表了一個(gè)應(yīng)用

18、中的重要詞項(xiàng)計(jì)算機(jī)科學(xué)圖書(shū)館中的索引項(xiàng)應(yīng)該是哪些呢?,索引項(xiàng)的選擇,這些索引項(xiàng)是不相關(guān)的 (或者說(shuō)是正交的) ，形成一個(gè)向量空間vector space實(shí)際上，這些詞項(xiàng)是相互關(guān)聯(lián)的當(dāng)你在一個(gè)文檔中看到 “計(jì)算機(jī)”, 非常有可能同時(shí)看到“科學(xué)”當(dāng)你在一個(gè)文檔中看到 “計(jì)算機(jī)”, 有中等的可能性同時(shí)看到 “商務(wù)”當(dāng)你在一個(gè)文檔中看到“商務(wù)”，只有很少的機(jī)會(huì)同時(shí)看到“科學(xué)”,文檔向量的構(gòu)造 對(duì)于任一文檔dj∈D，都可

19、將它表示為t維向量形式： dj= (w1j, w2j, …,wij) 其中，向量分量wij代表第i個(gè)索引詞ki在文檔dj中所具有的權(quán)重，t為系統(tǒng)中索引詞的個(gè)數(shù)。 在Boolean模型中， wij ={0，1} 在VSM中，wij =[0，1] 一篇文檔有多個(gè)索引詞，如何計(jì)算每個(gè)索引詞的權(quán)值？,索引詞的權(quán)重,根據(jù)詞項(xiàng)在文檔(tf)和文檔集(idf)中的頻率(frequency)計(jì)算詞

20、項(xiàng)的權(quán)重tfij = 詞項(xiàng)j在文檔i中的頻率df j = 詞項(xiàng)j的文檔頻率= 包含詞項(xiàng)j的文檔數(shù)量idfj = 詞項(xiàng)j的反文檔頻率= log2 (N/ df j) N: 文檔集中文檔總數(shù)反文檔頻率用詞項(xiàng)區(qū)別文檔,例如：文檔總數(shù)為1000，出現(xiàn)關(guān)鍵詞k1文檔為100篇，出現(xiàn)關(guān)鍵詞k2文檔為500篇，出現(xiàn)關(guān)鍵詞k3文檔為800篇N=1000, n1=100, n2=500, n3=800根據(jù)公式： idfi = log(N/

21、ni) ，可計(jì)算出idf1= 3 - 2 = 1idf2= 3 – 2.7 = 0.3idf3 = 3 – 2.9 = 0.1Idf越大，表明區(qū)別（分）文檔的能力越強(qiáng)。,文檔的詞項(xiàng)權(quán)重(TFIDF舉例),文本：“俄羅斯頻繁發(fā)生恐怖事件，俄羅斯的安全部門(mén)加大打擊恐怖主義的力度?！?Idf 計(jì)算示例,查詢式的詞項(xiàng)權(quán)重,如果詞項(xiàng)出現(xiàn)在查詢式中，則該詞項(xiàng)在查詢式中的權(quán)重為1，否則為0也可以用用戶指定查詢式中詞項(xiàng)的權(quán)重一個(gè)自然語(yǔ)言查詢

22、式可以被看成一個(gè)文檔查詢式：“有沒(méi)有周杰倫的歌？” 會(huì)被轉(zhuǎn)換為:查詢式： “請(qǐng)幫我找關(guān)于俄羅斯和車臣之間的戰(zhàn)爭(zhēng)以及車臣恐怖主義首腦的資料” 會(huì)被轉(zhuǎn)換為: 過(guò)濾掉了：“請(qǐng)幫我找”，“和”，“之間的”，“以及”，“的資料”兩個(gè)文檔之間的相似度可以同理計(jì)算,由索引項(xiàng)構(gòu)成向量空間,2個(gè)索引項(xiàng)構(gòu)成一個(gè)二維空間，一個(gè)文檔可能包含0, 1 或2個(gè)索引項(xiàng)di = ? 0, 0 ? (一個(gè)索引項(xiàng)也不包含)dj = ? 0, 0.7 ?

23、(包含其中一個(gè)索引項(xiàng))dk = ? 1, 2 ? (包含兩個(gè)索引項(xiàng))類似的，3個(gè)索引項(xiàng)構(gòu)成一個(gè)三維空間，n個(gè)索引項(xiàng)構(gòu)成n維空間一個(gè)文檔或查詢式可以表示為n個(gè)元素的線性組合,文檔集 – 一般表示,向量空間中的N個(gè)文檔可以用一個(gè)矩陣表示矩陣中的一個(gè)元素對(duì)應(yīng)于文檔中一個(gè)詞項(xiàng)的權(quán)重?！?”意味著該詞項(xiàng)在文檔中沒(méi)有意義，或該詞項(xiàng)不在文檔中出現(xiàn)。,T1 T2 …. TtD1 d11 d12 …

24、 d1tD2 d21 d22 … d2t : : : : : : : :Dn dn1 dn2 … dnt,圖示,舉例:D1 = 2T1 + 3T2 + 5T3D2 = 3T1 + 7T2 + T3Q = 0T1 + 0T2 + 2T3,D1比D2更接近Q嗎？怎樣衡量相似程度

25、？夾角還是投影,相似度計(jì)算,相似度是一個(gè)函數(shù)，它給出兩個(gè)向量之間的相似程度，查詢式和文檔都是向量，各類相似度存在于：兩個(gè)文檔之間（文本分類，聚類）兩個(gè)查詢式之間（常問(wèn)問(wèn)題集）一個(gè)查詢式和一個(gè)文檔之間（檢索）人們?cè)岢龃罅康南嗨贫扔?jì)算方法，因?yàn)樽罴训南嗨贫扔?jì)算方法并不存在。,通過(guò)計(jì)算查詢式和文檔之間的相似度,可以根據(jù)預(yù)定的重要程度對(duì)檢索出來(lái)的文檔進(jìn)行排序可以通過(guò)強(qiáng)制設(shè)定某個(gè)閾值，控制被檢索出來(lái)的文檔的數(shù)量檢索結(jié)果可以被用于相關(guān)

26、反饋中，以便對(duì)原始的查詢式進(jìn)行修正。 (例如：將文檔向量和查詢式向量進(jìn)行結(jié)合),相似度度量 – 內(nèi)積(Inner Product),文檔D 和查詢式Q 可以通過(guò)內(nèi)積進(jìn)行計(jì)算:sim ( D , Q ) = (dik ? qk)dik 是文檔di中的詞項(xiàng)k 的權(quán)重，qk 是查詢式Q中詞項(xiàng)k的權(quán)重對(duì)于二值向量, 內(nèi)積是查詢式中的詞項(xiàng)和文檔中的詞項(xiàng)相互匹配的數(shù)量對(duì)于加權(quán)向量, 內(nèi)積是查詢式和文檔中相互匹配的詞項(xiàng)的

27、權(quán)重乘積之和,內(nèi)積 – 舉例,二值（Binary）:D = 1, 1, 1, 0, 1, 1, 0Q = 1, 0 , 1, 0, 0, 1, 1sim(D, Q) = 3,retrieval,database,architecture,computer,text,management,information,向量的大小 = 詞表的大小 = 70 意

28、味著某個(gè)詞項(xiàng)沒(méi)有在文檔中出現(xiàn)，或者沒(méi)有在查詢式中出現(xiàn),加權(quán) D1 = 2T1 + 3T2 + 5T3 D2 = 3T1 + 7T2 + T3 Q = 0T1 + 0T2 + 2T3sim(D1 , Q) = 2*0 + 3*0 + 5*2 = 10 sim(D2 , Q) = 3*0 + 7*0 + 1*2 = 2

29、,內(nèi)積的特點(diǎn),內(nèi)積值沒(méi)有界限不象概率值，要在(0,1)之間對(duì)長(zhǎng)文檔有利內(nèi)積用于衡量有多少詞項(xiàng)匹配成功，而不計(jì)算有多少詞項(xiàng)匹配失敗長(zhǎng)文檔包含大量獨(dú)立詞項(xiàng)，每個(gè)詞項(xiàng)均多次出現(xiàn)，因此一般而言，和查詢式中的詞項(xiàng)匹配成功的可能性就會(huì)比短文檔大。,余弦(Cosine)相似度度量,余弦相似度計(jì)算兩個(gè)向量的夾角余弦相似度是利用向量長(zhǎng)度對(duì)內(nèi)積進(jìn)行歸一化的結(jié)果,CosSim(Di, Q) =,D1 = 2T1 + 3T2 + 5T3 Co

30、sSim(D1 , Q) = 5 / ? 38 = 0.81D2 = 3T1 + 7T2 + T3 CosSim(D2 , Q) = 1 / ? 59 = 0.13 Q = 0T1 + 0T2 + 2T3,用余弦計(jì)算，D1 比 D2 高6倍；用內(nèi)積計(jì)算， D1 比 D2 高5倍,其它相似度度量方法,存在大量的其它相似度度量方法,Jaccard Coefficient:,D1 = 2T1 + 3T2 + 5T3

31、 Sim(D1 , Q) = 10 / (38+4-10) = 10/32 = 0.312D2 = 3T1 + 7T2 + T3 Sim(D2 , Q) = 2 / (59+4-2) = 2/61 = 0.033 Q = 0T1 + 0T2 + 2T3,D1 比 D2 高9.5倍,示例,向量空間模型優(yōu)點(diǎn),術(shù)語(yǔ)權(quán)重的算法提高了檢索的性能 部分匹配的策略使得檢索的結(jié)果文檔集更接近用戶的檢索需求可以根據(jù)結(jié)果文檔對(duì)于查詢

32、串的相關(guān)度通過(guò)Cosine Ranking等公式對(duì)結(jié)果文檔進(jìn)行排序,向量空間模型的不足,標(biāo)引詞之間被認(rèn)為是相互獨(dú)立隨著Web頁(yè)面信息量的增大、Web格式的多樣化，這種方法查詢的結(jié)果往往會(huì)與用戶真實(shí)的需求相差甚遠(yuǎn)，而且產(chǎn)生的無(wú)用信息量會(huì)非常大隱含語(yǔ)義索引模型是向量空間模型的延伸,課堂練習(xí)（3）,對(duì)于下列例子，計(jì)算(文檔長(zhǎng)度以字節(jié)數(shù)表示，不含標(biāo)點(diǎn)和空格)，寫(xiě)出計(jì)算過(guò)程，并判斷哪篇文檔和查詢q更相關(guān)。Q："gold silve

33、r truck"D1："Shipment of gold damaged in a fire"D2："Delivery of silver arrived in a silver truck"D3："Shipment of gold arrived in a truck",概率模型,,有一支沙羅曼蛇的壘球隊(duì)，根據(jù)以往的經(jīng)驗(yàn)，如果天氣晴朗的話，有75%的可能性贏得

34、比賽；如果最好的游擊手上場(chǎng)的話，有60%的可能性贏得比賽。那么，如果這支球隊(duì)在天氣晴朗且最好游擊手上場(chǎng)的情況下獲勝的概率有多少？（假設(shè)沙羅曼蛇球隊(duì)輸贏次數(shù)一樣多）,3 概率模型,概率論模型主要基于概率論原理來(lái)理解和解決信息檢索問(wèn)題。在概率論的基礎(chǔ)上，目前提出的檢索模型主要有經(jīng)典概率模型（二值獨(dú)立檢索模型, Binary Independence Retrieval, BIR)、基于Bayesian網(wǎng)絡(luò)的推理網(wǎng)絡(luò)模型(Interence

35、Network Model)和信念網(wǎng)絡(luò)模型（Belief Network Model）等。,經(jīng)典概率模型最早在1976年由英國(guó)城市大學(xué)Robertson和Sparck-Jones提出。基本思想：給定一個(gè)用戶提問(wèn)，則檢索系統(tǒng)中存在一個(gè)與該提問(wèn)相關(guān)的理論命中結(jié)果集R。如果能已知R的主要特征及其描述，則用戶的檢索要求便不難實(shí)現(xiàn)。事實(shí)上，用戶提出檢索請(qǐng)求時(shí)，并不知道R的特征，為此，需要在檢索開(kāi)始時(shí)就對(duì)R的特征進(jìn)行某種猜測(cè)。根據(jù)初始的猜測(cè)，系統(tǒng)

36、將檢索出一個(gè)初步命中的結(jié)果集合。,在此基礎(chǔ)上，用戶可以對(duì)初始的檢索結(jié)果集合中文檔相關(guān)與否進(jìn)行判斷。在根據(jù)這些反饋信息，系統(tǒng)便可以在后續(xù)的檢索處理中不斷做出優(yōu)化和改進(jìn)，經(jīng)過(guò)多次反復(fù)，至理想的結(jié)果集R。最為重要的是如何進(jìn)行初始的猜測(cè)和如何通過(guò)相關(guān)反饋與交互不斷調(diào)整、改善檢索性能。,概率模型,檢索問(wèn)題即求條件概率問(wèn)題If Prob(R|di, q) > Prob(NR|di, q) then di是檢索結(jié)果，否則不是檢索結(jié)果,檢索的

37、理想結(jié)果,理想答案集(ideal answer set)給定一個(gè)用戶的查詢串，相對(duì)于該串存在一個(gè)包含所有相關(guān)文檔的集合我們把這樣的集合看作是一個(gè)理想的結(jié)果文檔集用索引項(xiàng)刻畫(huà)理想答案集的屬性把查詢處理看作是對(duì)理想結(jié)果文檔集屬性的處理我們并不能確切地知道這些屬性，我們所知道的是用索引詞的語(yǔ)義來(lái)刻畫(huà)這些屬性,實(shí)際采取的策略,初始估計(jì)由于在查詢期間這些屬性都是不可見(jiàn)的，這就需要在初始階段來(lái)估計(jì)這些屬性。這種初始階段的估計(jì)允許我們對(duì)

38、首次檢索的文檔集合返回理想的結(jié)果集，并產(chǎn)生一個(gè)初步的概率描述。相關(guān)反饋(relevance feedback)為了提高理想結(jié)果集的描述概率，系統(tǒng)需要與用戶進(jìn)行交互式操作，具體處理過(guò)程如下：用戶大致瀏覽一下結(jié)果文檔，決定哪些是相關(guān)的，哪些是不相關(guān)的；然后系統(tǒng)利用該信息重新定義理想結(jié)果集的概率描述；重復(fù)以上操作，就會(huì)越來(lái)越接近真正的結(jié)果文檔集。,概率模型的理論,概率模型是基于以下基本假設(shè)：給定一個(gè)用戶的查詢串 q和集合中的文檔

39、dj ，概率模型估計(jì)用戶查詢串與文檔dj 相關(guān)的概率。概率模型假設(shè)這種概率只決定于查詢串和文檔。更進(jìn)一步說(shuō)，該模型假定在文檔集合中存在一個(gè)子集，即相對(duì)于查詢串q的結(jié)果文檔子集，這種理想的集合用R表示，集合中的文檔是被預(yù)料與查詢串相關(guān)的。這種假設(shè)存在著缺點(diǎn)，因?yàn)樗鼪](méi)有明確定義計(jì)算相關(guān)度的概率，下面將給出這種概率的定義。,查詢式與文檔的相關(guān)度概率定義,在概率模型中索引術(shù)語(yǔ)的權(quán)重都是二值的 wi,j?{0,1}, wi,q?{0,1

40、}, 查詢式q是索引詞項(xiàng)集合的子集設(shè)R是相關(guān)文檔集合（初始的猜測(cè)集合）， 是R的補(bǔ)集（非相關(guān)文檔的集合） 表示文檔dj和查詢式q相關(guān)的概率； 表示文檔dj和查詢式q不相關(guān)的概率；,查詢式與文檔的相關(guān)度概率定義,文檔dj對(duì)于查詢串q的相關(guān)度值定義為：根據(jù)貝葉斯原理其中： 代表從相關(guān)文檔集合R中隨機(jī)選取文檔dj的概率，P(R)表示從整個(gè)集合中隨機(jī)選取

41、一篇文檔作為相關(guān)文檔的概率，依此定義 和,推導(dǎo),P(R)和 表示從整個(gè)文檔集合中隨機(jī)選取一篇文檔是否和查詢相關(guān)先驗(yàn)概率，而對(duì)于一個(gè)確定的文檔集來(lái)說(shuō)，這兩個(gè)先驗(yàn)概率僅與查詢有關(guān)，而與具體的每篇文檔無(wú)關(guān)，進(jìn)一步簡(jiǎn)化可得假設(shè)索引術(shù)語(yǔ)是相互獨(dú)立的則：,最終的概率模型排序公式,表示集合R中隨機(jī)選取的文檔中出現(xiàn)索引術(shù)語(yǔ)ki的概率， 表示集合R中隨機(jī)選取的文檔中不出現(xiàn)索引術(shù)語(yǔ)的概率，則有：

42、類似定義 和 ，在相同查詢背景下，忽略對(duì)所有文獻(xiàn)保持不變的因子，最終得到： 這是概率模型主要的排序公式,初始化方法,由于我們?cè)陂_(kāi)始時(shí)并不知道集合R，因此必須 設(shè)計(jì)一個(gè)初始化計(jì)算 和 的算法。在查詢的開(kāi)始間段只定義了查詢串，還沒(méi)有得到結(jié)果文檔集。我們不得不作一些簡(jiǎn)單的假設(shè)，假定P(ki|R)對(duì)所有的索引術(shù)語(yǔ)來(lái)說(shuō)

43、是常數(shù)（一般等于0.5）假定索引術(shù)語(yǔ)在非相關(guān)文檔中的分布可以由索引術(shù)語(yǔ)在集合中所有文檔中的分布來(lái)近似表示。P(ki|R)=0.5=ni/Nni表示出現(xiàn)索引術(shù)語(yǔ)ki的文檔的數(shù)目，N是集合中總的文檔的數(shù)目。,改進(jìn),V表示用概率模型初步檢出的經(jīng)過(guò)排序的子集，Vi為包含ki的V的一個(gè)子集。為了改善概率排序，需要對(duì)上述初始化公式改進(jìn)：通過(guò)迄今已檢出的文獻(xiàn)中標(biāo)引詞ki的分布來(lái)估計(jì) 通過(guò)假定所有未檢出的文獻(xiàn)都是不相關(guān)的來(lái)估

44、計(jì)這一過(guò)程可以遞歸重復(fù),,概率模型小結(jié),優(yōu)點(diǎn)文檔可以按照他們相關(guān)概率遞減的順序來(lái)排序。缺點(diǎn)開(kāi)始時(shí)需要猜想把文檔分為相關(guān)和不相關(guān)的兩個(gè)集合，一般來(lái)說(shuō)很難實(shí)際上這種模型沒(méi)有考慮索引術(shù)語(yǔ)在文檔中的頻率（因?yàn)樗械臋?quán)重都是二值的）假設(shè)標(biāo)引詞獨(dú)立概率模型是否要比向量模型好還存在著爭(zhēng)論，但現(xiàn)在向量模型使用的比較廣泛。,瀏覽模型,,瀏覽模型,針對(duì)瀏覽（browsing）文獻(xiàn)的用戶具體分為三種模型扁平瀏覽(flat)模型結(jié)

45、構(gòu)導(dǎo)向(structure guided)模型超文本(hypertext)模型,扁平瀏覽模型,基本思想是假設(shè)用戶瀏覽一個(gè)扁平組織結(jié)構(gòu)的文獻(xiàn)空間。為何扁平組織結(jié)構(gòu)？日常生活中有哪些？文獻(xiàn)集合被描述為二維平面上的點(diǎn)或一維鏈表中的元素。優(yōu)點(diǎn) VS缺點(diǎn),結(jié)構(gòu)導(dǎo)向?yàn)g覽模型,基本思想是把眾多文檔或信息資源組織到一個(gè)樹(shù)狀的類目等級(jí)體系中。用戶在該結(jié)構(gòu)下，將由上到下，從寬泛到具體，逐步接近所需要的有用信息。,超文本瀏覽模型,基本思想是允許以非

46、順序的方式在計(jì)算機(jī)屏幕上瀏覽文本的高層交互式導(dǎo)航結(jié)構(gòu)。由結(jié)點(diǎn)和鏈組成，構(gòu)成一個(gè)有向圖。網(wǎng)絡(luò)空間的迷航與超文本地圖。,擴(kuò)展的布爾模型,布爾檢索示例,“飛碟”AND “小說(shuō)”：只能檢索出D4，無(wú)法顯現(xiàn)D1,D2,D3的差異“飛碟”O(jiān)R “小說(shuō)”：可以檢出D1,D2,D4，但無(wú)法顯現(xiàn)它們的差異,擴(kuò)展布爾模型,布爾模型和VSM各自有著自己的優(yōu)點(diǎn)和不足，能否將兩者結(jié)合起來(lái)，克服自身的缺點(diǎn)，發(fā)揮相互的長(zhǎng)處？1983年G.Salton及其學(xué)

47、生提出一種基于布爾邏輯框架的混合布爾、向量特性的“擴(kuò)展布爾模型”。,布爾模型和向量空間模型相結(jié)合,布爾模型可以和向量空間模型相結(jié)合，先做布爾過(guò)濾，然后進(jìn)行排序：首先進(jìn)行布爾查詢將全部滿足布爾查詢的文檔匯集成一個(gè)文檔用向量空間法對(duì)布爾檢索結(jié)果進(jìn)行排序,如果忽略布爾關(guān)系的話，向量空間查詢式和布爾查詢式是相同的,先“布爾”，后“排序”存在的問(wèn)題,如果 “與” 應(yīng)用于布爾查詢式, 結(jié)果集可能太窄,因而影響了后面的排序過(guò)程如果 “或”

48、 應(yīng)用于布爾查詢式, 就和純向量空間模型沒(méi)有區(qū)別了在第一步，如何最佳地應(yīng)用布爾模型呢？提出擴(kuò)展布爾模型,擴(kuò)展布爾模型中的“或”關(guān)系,給定一個(gè)或關(guān)系的查詢式：x ? y假設(shè)文檔di中x和y的權(quán)重被歸一化在(0,1)區(qū)間內(nèi):wx,j = （tfx,j / maxl tfl,j ）? （idfx / maxi idfi）sim(qor, dj) = [ (x2 + y2)/2 ]0.5 where x = wx,j and

49、 y = wy,j,一個(gè)文檔在(1,1)處獲得最高的權(quán)重，此時(shí)意味著文檔包含了全部?jī)蓚€(gè)查詢?cè)~，并且查詢?cè)~在文檔中的權(quán)重也是最高的函數(shù)sim()度量了從原點(diǎn)出發(fā)的文檔向量長(zhǎng)度,擴(kuò)展布爾模型中的“與”關(guān)系,給定一個(gè)聯(lián)合的查詢式 x ? ysim(qand, dj) = 1 ? { [ (1? x)2 + (1? y)2 ]/2 }0.5函數(shù)sim() 表示從(1,1) 出發(fā)到d的向量長(zhǎng)度,擴(kuò)展的布爾檢索相似度計(jì)算示例,觀察,如果權(quán)值

50、是布爾型的，x出現(xiàn)在文檔dj中，則x在文檔dj中具有權(quán)重1，否則為0當(dāng)dj 包含x和y時(shí)sim(qand, dj) = sim(qor, dj) = 1當(dāng)dj 既不包含x 也不包含y時(shí)sim(qand, dj) = sim(qor, dj) = 0當(dāng)dj 包含x 和y二者之一時(shí)sim(qand, dj) = 1 ? 1/20.5 = 0.293sim(qor, dj) = 1/20.5 = 0.707,觀察,一個(gè)詞

51、項(xiàng)的存在將對(duì)“或”關(guān)系查詢式提供0.707的增益值，但對(duì)“與”關(guān)系查詢式僅提供0.293的增益值一個(gè)詞項(xiàng)不存在，將給“與”關(guān)系的查詢式提供0.707的罰分當(dāng)x 和y 有權(quán)值0.5, sim(qand, d) = sim(qor, d) = 0.5在一個(gè)“與”關(guān)系查詢中，兩個(gè)詞項(xiàng)的權(quán)重均為0.5，則相似度為0.5。其中一個(gè)權(quán)重為1，另一個(gè)為0，相似度為0.293。在“或關(guān)系”查詢中，情況恰好相反在“與關(guān)系”查詢中，如果一個(gè)詞項(xiàng)的

52、權(quán)重低于0.5，將給相似度貢獻(xiàn)一個(gè)較大的罰分,p-norm 模型,擴(kuò)展布爾模型可以被泛化為m 個(gè)查詢項(xiàng):sim(qor, d) = [ (x12 + x22 + ... + xm2 ) / m ]0.5sim(qand, d) = 1 ? { [ (1? x1)2 + (1? x2)2 + ... + (1? xm)2 ] / m }0.5它可以被進(jìn)一步地 泛化為p-norm model:sim(qor, d) = [ (x1p

53、 + x2p + ... + xmp ) / m ] 1/psim(qand, d) = 1 ? { [ (1? x1) p + (1? x2) p + ... + (1? xm) p ] / m }1/p當(dāng)p = 1時(shí), sim(qor, d) = sim(qand, d) = (x1 + x2 + ... + xm )/ m通過(guò)語(yǔ)詞-文獻(xiàn)權(quán)值的和來(lái)求合取和析取查詢的值，和向量空間中的內(nèi)積相似當(dāng)p = ?, sim(qor,