二、信息檢索模型研究 - 謝謝您的光臨哦

1、第二講　信息檢索模型研究,陸銘66134922richard.lu@shu.edu.cnmingler.ccshu.org,2,內(nèi)容提要,檢索模型的基本概念與分類 布爾模型 向量模型 概率模型 其他模型 結(jié)構(gòu)模型 瀏覽模型 統(tǒng)計語言建模 國內(nèi)外檢索模型理論研究現(xiàn)狀,3,檢索模型的基本概念——1.信息檢索模型,信息檢索模型是指如何對查詢和文檔進(jìn)行表示，然后對它們進(jìn)行相似度計算的框架和方法 本質(zhì)上是對相關(guān)度建模 信

2、息檢索模型是IR中的核心內(nèi)容之一,4,檢索模型的基本概念——2.相關(guān)概念,標(biāo)引項(Index Term) 文檔表示成多個Term的集合 通常用詞來表示，但是也可以用其他語言單位來表示 關(guān)鍵詞(key words) 可以看成Term的一種 標(biāo)引項的權(quán)重(Weight) 不同標(biāo)引項作用是不同的 通過權(quán)重加以區(qū)分,5,模型F,檢索模型的基本概念——3.檢索模型的定義,信息檢索模型是描述信息檢索中的文檔、查詢和它們之間的關(guān)系(匹配函

3、數(shù))的數(shù)學(xué)模型。,文檔D,查詢Q,匹配函數(shù)R(qi,dj),6,檢索模型的基本概念——4.模型要素,F是一個框架,用以構(gòu)建文檔,查詢以及它們之間關(guān)系的模型 D是一個文檔集合，通常由文檔邏輯視圖來表示。可以是一組索引詞或關(guān)鍵詞。既可以自動提取，也可以是由人主觀指定。 Q是一個查詢集合，是用戶任務(wù)的表達(dá)，由查詢需求的邏輯視圖來表示。 R(qi,dj) 是一個排序函數(shù)，它給查詢qi和文檔 dj 之間的相關(guān)度賦予一個排序值 即:

4、IR模型由上述三個要素組成 R(qi,dj) = F( D, Q ),7,檢索模型的基本概念——5.文檔邏輯視圖,文檔邏輯視圖D：,8,檢索模型的基本概念——6.檢索模型的分類,三種主要類型 基于內(nèi)容的信息檢索模型 結(jié)構(gòu)化模型 瀏覽型數(shù)學(xué)模型 基于內(nèi)容的信息檢索模型有 集合論模型 布爾模型、模糊集合模型、擴(kuò)展布爾模型 代數(shù)模型 向量空間模型、廣義向量空間模型、潛在語義標(biāo)引模型、神經(jīng)網(wǎng)絡(luò)模型

5、概率模型 經(jīng)典概率論模型、推理網(wǎng)絡(luò)模型、置信（信念）網(wǎng)絡(luò)模型,9,檢索模型的基本概念——7.檢索模型分類,結(jié)構(gòu)化模型 非重疊鏈表模型 臨近節(jié)點模型 瀏覽型數(shù)學(xué)模型 平面文本 (Hypertext),10,檢索模型的基本概念——檢索模型分類,11,檢索模型的基本概念——8.理論研究歷史,描述查詢的結(jié)構(gòu)化階段 布爾檢索模型 描述相關(guān)性的量化階段 向量空間模型 概率模型,12,檢索模型的基本概念——理論研究歷史,定性評價與定

6、量計算相結(jié)合的階段 邏輯模型,基于集合論的IR模型(Set Theoretic models),布爾模型擴(kuò)展布爾模型,14,布爾模型——1.定義,一種簡單的檢索模型，它建立在經(jīng)典的集合論和布爾代數(shù)的基礎(chǔ)上 基本原理 系統(tǒng)索引詞集合中的每一個索引詞在一篇文檔中只有兩個狀態(tài) 出現(xiàn) 不出現(xiàn) 檢索提問式q由三種布爾運算符 “and”、“or”、“not”連接索引詞來構(gòu)成,15,布爾模型——2.集合的直觀描述,具有某種屬性的對象總體

7、(通常用大寫字母表示，如A,B等)，這些對象稱為其元素(通常用小寫字母表示，如x,y等) x是A的元素記為：x∈A (讀作x屬于A) x不是A的元素記為：x?A (讀作x不屬于A) 集合的基本特性是，對于給定的集合A，任何對象x, x∈A與x?A中有且只有一個成立.,16,布爾模型——3.集合論,集合的幾種表示 具有某種屬性的事物的全體就構(gòu)成一個集合，以 A,B,C,…表示構(gòu)成集合的事物，以 a,b,c,…表示該集合的元 某個

8、圖書館現(xiàn)存的所有圖書——有限集 以 S1＝ {a,b,c,d}表示 所有的正整數(shù)——無限集 以 S2＝ {1,2,3,4,…}表示 P(x)表示與元x有關(guān)的一個屬性 S3＝ {x|x是正偶數(shù)} S4＝ {x|1<x<10 } 為空集,17,布爾模型——4.集合的表示,集合間的關(guān)系

9、 x是A中的一個元，記作x ∈ A x不是A中的一個元，記作x ? A 集合的圖形表示,18,布爾模型——5.集合的運算,并運算 設(shè)A，B是兩個集合，集合A與B的并運算是由A的一切元素和B的一切元素所組成的集合，記做 A∪B，數(shù)學(xué)表示為： 設(shè) A={a,b,c,d,e}，B={c,d,x,y,z} 則 A∪B={a,b,c,d,e,x,y,z} 即 A∪B={x|x∈A∨x∈B },19,布爾模型——6.集合的運算,

10、交運算 設(shè)A，B是兩個集合，包含A和B的所有公共元素的集合叫做A與B的交集，記做 A∩B，數(shù)學(xué)表示為： 設(shè) A={a,b,c,d,e}，B={c,d,x,y,z} 則 A∩B={c,d} 即 A∩B={x|x∈A∧x∈B },20,布爾模型——7.集合的運算,差運算 設(shè)A，B是兩個集合，A-B是由一切屬于A但不屬于B的元素所組成的集合，稱為B在A中的余集，或者A與B的差，即 設(shè) A={a,b,c,d,e}， B

11、={c,d,x,y,z} 則 A-B={a,b,e}， B-A={x,y,z} 數(shù)學(xué)表示為 A-B={x|x∈A﹁x∈B },21,布爾模型——8.布爾代數(shù),布爾變量 1849年英國數(shù)學(xué)家喬治.布爾(George Boole)首先提出，用來描述客觀事物邏輯關(guān)系的數(shù)學(xué)方法——稱為布爾代數(shù) 后來被廣泛用于開關(guān)電路和數(shù)字邏輯電路的分析與設(shè)計，所以也稱為開關(guān)代數(shù)或邏輯代數(shù) 邏輯代數(shù)中用字母表示變量——邏輯變量 每個

12、邏輯變量的取值只有兩種可能——0和1 它們也是邏輯代數(shù)中僅有的兩個常數(shù) 0和1只表示兩種不同的邏輯狀態(tài)，不表示數(shù)量大小,22,布爾模型——布爾代數(shù),與運算,決定事件的全部條件都滿足時，事件才發(fā)生——這就是與邏輯關(guān)系。,在函數(shù)式中，用?表示與運算，記做 Y=A?B 或Y=AB,只有輸入全為1時，輸出才為1,真值表,23,布爾模型——布爾代數(shù),或運算,決定事件的全部條件至少有一個滿足時，事件就發(fā)生——這就是或邏輯關(guān)系。,輸入全部為0時，

13、輸出為0,在函數(shù)式中，用＋ 表示或運算，記做 Y=A＋B,真值表,24,布爾模型——布爾代數(shù),非運算,該圖代表的邏輯關(guān)系是：決定事件的條件滿足時，事件不發(fā)生——這就是非邏輯關(guān)系。,真值表,在函數(shù)式中，用_ 表示非運算，記做 Y=A,25,布爾模型—— Bag of Terms Example,Document 1,Document 2,the,is,for,to,of,,Stopword List,The quick brow

14、n fox jumped over the lazy dog’s back.,Now is the time for all good men to come to the aid of their party.,26,布爾模型—— Boolean Free Text Example,dog AND fox Doc 3, Doc 5 dog NOT fox Empty fox NOT dog Doc 7

15、 dog OR fox Doc 3, Doc 5, Doc 7 good AND party Doc 6, Doc 8 good AND party NOT over Doc 6,27,布爾模型——布爾代數(shù),布爾運算的性質(zhì)和定理 交換律 A?B=B?A 　　 A+B=B+A 結(jié)合律 A+(B+C)=(A+B)+C A?(B?C)=(A?B)?C 分配律 A?(B+

16、C)=A?B+A?C A+(B?C)=(A+B)?(A+C),28,布爾模型——布爾代數(shù),布爾變量 只有“真”、“假”取值的變量 計算機(jī)中常常用1表示“真”true，0表示“假”false 布爾操作(關(guān)系) 與(AND)：(A AND B) = true iffA=true and B=true 或(OR) ：(A OR B) = true iffA=true OR B=true 非(NOT) ：(NOT A) = t

17、rue iffA=false 布爾表達(dá)式 多個布爾變量之間通過布爾操作組成的表達(dá)式 如：A AND (B OR C) AND NOT D 蘊(yùn)含：兩個布爾表達(dá)式P、Q，如果A為true，那么Q為true，則稱P蘊(yùn)含Q，記為P?Q,29,布爾模型,布爾模型 查詢和文檔均表示為Term(“是否存在”)的布爾表達(dá)式，其中文檔表示成所有Term(存在)的“與”關(guān)系布爾表達(dá)式。 例子(因不會產(chǎn)生歧義，以下例子直接用Term進(jìn)行布爾操作)

18、： 查詢：2010 AND 世界杯AND NOT 小組賽 文檔1：2010年世界杯在南非舉行 文檔2：2006年世界杯小組賽已經(jīng)結(jié)束 相似度計算 查詢布爾表達(dá)式和所有文檔的布爾表達(dá)式進(jìn)行匹配，匹配成功的文檔的得分為1，否則為0 類似于傳統(tǒng)數(shù)據(jù)庫檢索，是精確匹配,30,布爾模型,遵循兩條基本規(guī)則 每個索引詞在一篇文檔中只有兩種狀態(tài)：出現(xiàn)或不出現(xiàn)，對應(yīng)邏輯值為 0 或 1 查詢是由三種布爾邏輯運算符 and, or, no

19、t 連接索引詞組成的布爾表達(dá)式,31,布爾模型——9. 形式化表示,任意查詢都可轉(zhuǎn)化為一個主析取范式DNF 例如：查詢?yōu)閝=ka∧(kb∨¬kc)可表示為 q=ka∧(kb∨¬kc)=kakbkc∨kakb¬kc∨ka¬kb ¬kc qbnf=(1,1,1)∨(1,1,0)∨(1,0,0) 即：每一個分量都是三元組的二值向量 任一文本可以寫成所有Term的交，如do

20、c=a∧b∧c∧d∧e因為doc?(蘊(yùn)含)q，所以相似度為1,,,,,?,32,布爾模型,定義 用qdnf表示查詢q的析取范式，qcc表示qdnf的任意合取分項，文獻(xiàn)dj 與查詢q的相似度為 如果 ，則表示文獻(xiàn)dj與q相關(guān)，否則為不相關(guān)。 sim(dj, q) 為該模型的匹配函數(shù)(相似度),,,33,布爾模型,簡單實例 q = 病毒 AND（計算機(jī) OR 電腦）AND NOT醫(yī) d1:

21、 …據(jù)報道，計算機(jī)病毒近日猖獗… d2: …小王雖然是學(xué)醫(yī)的，但對研究電腦病毒也很感興趣，最近發(fā)明了一種… d3: …計算機(jī)程序發(fā)現(xiàn)了愛滋病病毒的傳播途徑… 寫出DNF，哪些文獻(xiàn)會被檢索出來？,q=A(B+C)~D =(AB+AC) ~D =AB~D+AC~D =AB(C+~C) ~D+A(B+~B)C~D=ABC~D+AB~C~D+ABC~D+A~BC~D,34,布爾模型——10. 優(yōu)缺點,布爾模型的優(yōu)點

22、 簡單而整齊，為現(xiàn)代許多商業(yè)系統(tǒng)所用 自我保護(hù)功能，降低用戶對搜索系統(tǒng)的期望，使自己不在責(zé)任方，檢索結(jié)果不好的原因在于用戶構(gòu)造查詢不好 簡單、易理解、簡潔的形式化布爾模型的缺點 它的檢索策略是基于二值決策準(zhǔn)則，即一個文檔只被判斷成相關(guān)的或不相關(guān)的，無任何等級變化 當(dāng)用布爾表達(dá)式表示精確語義的時候，很難將信息表達(dá)為一個布爾表達(dá)式 準(zhǔn)確匹配，信息需求的能力表達(dá)不足 布爾模型目前仍然是商業(yè)文檔數(shù)據(jù)庫的主流模型，并為一些新的領(lǐng)域

23、提供了一個好的起點,35,布爾模型——布爾模型的改進(jìn),布爾模型的典型問題 k1 and k2 and k3 and ……and k8 含有7個k和0個k的文獻(xiàn)一樣被排除 k1 or k2 or k3 or ……or k8 含有8個k和含有1個k的文獻(xiàn)沒有區(qū)別 擴(kuò)展布爾模型兩個索引詞,36,布爾模型——擴(kuò)展布爾模型,如果權(quán)值是布爾型的，則文獻(xiàn)總是處于4個角上（0,1）（0,1）（1,0）（1,1）,基于代數(shù)論的IR模型(Alg

24、ebraic models),向量空間模型,38,向量模型——1. n維向量,考慮從空間坐標(biāo)系原點出發(fā)（其他向量可以平移到原點出發(fā)）的向量 ，其終點坐標(biāo)為，我們稱之為一個n維向量 向量的運算 加、減、倍數(shù)、內(nèi)積,39,向量模型——2. 空間概念,文獻(xiàn)空間 如果把每個標(biāo)引詞看作是一個向量，代表了空間的一個維，則由這些標(biāo)引詞集合定義了一個空間 文獻(xiàn)集合中的任一文獻(xiàn)都可以表示為這個多維空間中的一個向量，這個空間就成為“文獻(xiàn)空間”

25、 標(biāo)引詞空間 文獻(xiàn)集合中的一篇文獻(xiàn)可看成是標(biāo)引詞空間的一個維，空間中的一點代表一個標(biāo)引詞點 從原點到該點的向量就是一個標(biāo)引詞向量 它在各個軸上的分量就是該標(biāo)引詞在各個軸所代表的相應(yīng)文獻(xiàn)中的權(quán)重,40,向量模型——3. 文檔-標(biāo)引項矩陣(Doc-Term Matrix),文獻(xiàn)-標(biāo)引項矩陣 n篇文檔Tn，m個標(biāo)引項Dm構(gòu)成的矩陣Am*n 每列可以看成每篇文檔的向量表示 每行也可以可以看成標(biāo)引項的向量表示

26、 T1 T2 T3 D1 d11 d12 d13 A33 = D2 d21 d22 d23 D3 d31 d32 d33,41,向量：,既有大小又有方向的量,向量表示：,,模長為1的向量,,,零向量：,模長為0的向量,向量的模：,向量的大小,單位向量：,向量模型——4. 向量的概念,或,或,或,42,

27、自由向量：,不考慮起點位置的向量,相等向量：,大小相等且方向相同的向量,負(fù)向量：,大小相等但方向相反的向量,向徑：,,,,,向量模型——向量的概念,43,向量模型—— 5. 向量的模、距離和夾角,向量的模向量的(歐氏)距離向量的夾角,44,（1）交換律：,（2）結(jié)合律：,（3）,減法運算,,,,,,,,向量模型——6. 向量加法的運算規(guī)律,45,向量模型——7. 模型含義,向量空間模型(Vector Space Model,

28、 VSM) 由康奈爾大學(xué)Salton等人在上世紀(jì)70年代末提出并倡導(dǎo)的，原型系統(tǒng)為SMART* 該模型采用了“部分匹配”的檢索策略，即：出現(xiàn)部分索引詞也可以出現(xiàn)在檢索結(jié)果中，以克服布爾模型的缺點 通過給查詢或文檔中的索引詞分配非二值權(quán)值來實現(xiàn) 查詢和文檔都可轉(zhuǎn)化成Term及其權(quán)重組成的向量表示，并可以看成空間中的點。向量之間通過距離計算得到查詢和每個文檔的相似度 * 可從ftp://ftp.cs.corne

29、ll.edu/pub/smart/下載全部源碼和相關(guān)語料,46,向量模型——模型含義,向量模型通過分派非二值權(quán)重給查詢和文檔中的索引項來實現(xiàn)檢索目標(biāo) 這些權(quán)重用于計算系統(tǒng)中的每個文檔與用戶的查詢請求的相似程度，向量模型通過對文檔按照相似程度降序排列的方式，來實現(xiàn)文檔與查詢項的部分匹配 結(jié)果中的文檔排列順序比通過布爾模型得到的結(jié)果要合理得多,47,向量模型——模型含義,在該模型中，與（ki，dj）相關(guān)聯(lián)的權(quán)重wi,j是一個非二值數(shù)

30、查詢中的索引項也是有權(quán)重的，設(shè)wi,q是與（ki，q）相關(guān)聯(lián)的權(quán)重，且wi,q≥0，則查詢向量Q被定義成 Q=（w1,q，w2,q，w3,q…………wt,q）其中，t是系統(tǒng)中所有索引項的數(shù)目， 文檔dj的向量可以表示為 wj=（w1,j，w2,j，w3,j………wt,j）， 向量模型通過wj和Q的相關(guān)度來評價文檔dj和查詢q的相關(guān)度。這種關(guān)系可以用定量表示，一般使用兩個向量之間的夾角余弦值來計算,4

31、8,向量模型——模型含義,變量wi稱為權(quán)值，非負(fù) 表示對應(yīng)詞項ki對于判斷d和查詢q相關(guān)性的重要程度（注意，這里的q是一般的，而d是具體的） q= 變量vi的含義類似于wi 兩個基本問題： 如何定義wi和vi 如何計算R(d, q),49,向量模型——模型含義,設(shè)wi和vi為對應(yīng)的詞分別在d和q中出現(xiàn)的次數(shù)，于是我們有了兩個m維向量，用夾角的cos表示“接近度”，即,50,向量模型——8. 例子,查詢q：(,) 文檔d1

32、：(,,,) 文檔d2：(,,,,),20052010世博會中國1970日本舉行,51,向量模型——例子,查詢和文檔進(jìn)行向量的相似度計算： 采用內(nèi)積： 文檔d1與q的內(nèi)積：1*1+3*2=7 文檔d2與q的內(nèi)積：2*2=4 夾角余弦： 文檔d1與q的夾角余弦： 文檔d2與q的夾角余弦：,52,,,向量模型—— 9. 權(quán)重規(guī)范化,不進(jìn)行權(quán)重規(guī)范化，檢索結(jié)果因文獻(xiàn)篇幅的長短而存在不合理現(xiàn)象 長文獻(xiàn)詞量大，同一

33、詞詞頻更大，命中的概率更大 長文獻(xiàn)中不同的詞量大，增加了查詢和文獻(xiàn)的相似度 Normalization seeks to remove these effects Related somehow to maximum term frequency But also sensitive to the number of terms,53,,向量模型—— Cosine‘s Normalization,Compute the leng

34、th of each document vector Multiply each weight by itself Add all the resulting values Take the square root of that sum Divide each weight by that length,54,向量模型—— 10. 項向量的規(guī)范方法,布爾權(quán)重 term i在文檔j中的權(quán)重aij=0or 1(出現(xiàn)則取1，否則取

35、0) TF權(quán)重：TF(Term Frequency)是term在文檔中出現(xiàn)的次數(shù)。權(quán)重aij=TFij或者歸一化后的TF值 TF的歸一化(Normalization) ：將一篇文檔中所有Term的TF值歸一化到[0,1]之間。通?？梢圆捎靡韵氯N方式之一 Maximum Normalization[1,2,1,0,4]?[0.25,0.5,0.25,0,1] Augmented Maximum Normalization[1

36、,2,1,0,4] ?[0.625,0.75,0.625,0.5,1] Cosine Normalization[1,2,1,0,4] ?[0.213,0.426,0.213,0,0.852],55,向量模型——11. 確定權(quán)重的方法,How to Weighting? N文獻(xiàn)數(shù) ni文獻(xiàn)集合中包含標(biāo)引詞 ki的詞頻 freqi,j 某篇文獻(xiàn)dj中包含標(biāo)引詞ki的詞頻(描述能力)fi,j詞頻的規(guī)范化值（局部權(quán)值,描述能

37、力）idfi 標(biāo)引詞ki的逆詞頻值 （全局權(quán)值,區(qū)分能力 ）,56,向量模型——確定權(quán)重的方法,文檔向量權(quán)值 tf/idf查詢向量的構(gòu)造：索引詞權(quán)值: WI,q 索引詞權(quán)值wij= tf*idf,57,向量模型——12. TF*IDF Example,58,,59,,,向量模型—— Weighted Matching Schemes,未予加權(quán)的查詢權(quán)重 計算全部匹配詞的權(quán)重和 用戶指定查詢詞的權(quán)重 計算每一

38、詞的查詢權(quán)重和文獻(xiàn)權(quán)重的積 計算這些詞權(quán)重積的和 自動計算查詢權(quán)重 多數(shù)查詢的詞頻TF無用, 但 IDF有價值 實踐中使用用戶指定的查詢詞權(quán)重,60,向量模型,向量模型的優(yōu)點 索引項的加權(quán)改善了檢索的性能，其部分匹配的策略允許所檢索的文檔與查詢條件相近似，其余弦排序公式按照文檔與查詢的相似程度對文檔進(jìn)行排序 向量模型的缺點 索引項被假設(shè)為彼此之間相互獨立的，然而在實際中，考慮索引項之間的相關(guān)性也許是個缺陷 由于許多索引項

39、之間的相關(guān)性具有局限性，不加區(qū)別地將其應(yīng)用到所有文檔中，會影響檢索系統(tǒng)的整體性能,61,向量模型——13. 對模型的評價,重要的學(xué)術(shù)貢獻(xiàn)，已用了幾十年 G. Salton and M. E. Lesk, “Computer evaluation of indexing and text processing,” Journal of the ACM, 15(1):8-38, January 1968. G. Salton, The

40、SMART Retrieval System – Experiments in Automatic Document Processing. Prentice Hall Inc., 1971. 實踐證明，盡管VSM在許多方面依然和“現(xiàn)實”都不符，但實際效果不錯 為什么比布爾模型好很多？,62,向量模型——14. 向量模型的改進(jìn),標(biāo)引詞位置加權(quán) 結(jié)構(gòu)位置 標(biāo)題、摘要、關(guān)鍵詞、正文、結(jié)論和超連接 重點句位置 綜上所述、結(jié)束語、主

41、要在于 輔助主題詞表 將帶修飾和限制作用的詞——形容詞和副詞做成輔助主題詞表，用以擴(kuò)展用戶查詢 將檢索關(guān)鍵詞和字典庫中的同義詞和修飾詞結(jié)合起來，形成新的查詢，提高了檢索的效率 個性化協(xié)同檢索設(shè)計 將每次的檢索結(jié)果、用戶興趣等建立個性化信息庫，并進(jìn)行信息反饋，定期刷新，不斷充實,63,課后練習(xí),利用夾角余弦方式(向量的分量采用TF表示) 進(jìn)行計算(s=0.2，文檔長度以字節(jié)數(shù)表示，1個漢字以2個字節(jié)計算，不含標(biāo)點和空格)，寫出計

42、算過程，并判斷哪篇文檔和查詢q更相關(guān)(不去除停用詞)。 查詢q：2010 亞運會 舉辦地 文檔d1：第十六屆亞運會2010年11月在廣州開幕 文檔d2：第11屆亞運會在中國北京舉行，參賽國家37個 如何判斷兩個文檔之間是否存在抄襲？,基于概率統(tǒng)計的IR模型(Probabilistic models),概率模型,65,概率模型,隨機(jī)現(xiàn)象與隨機(jī)事件 事件有多種不同的結(jié)果，在同樣的條件下進(jìn)行一系列重復(fù)試驗，每次出現(xiàn)的結(jié)果都不能預(yù)先確

43、定的事件稱為隨機(jī)事件 隨機(jī)現(xiàn)象在每次試驗中的結(jié)果雖然是不確定的，但在大量重復(fù)試驗下，各種不同結(jié)果出現(xiàn)的可能性的大小是具有規(guī)律性的 例如，統(tǒng)計大量的新生兒的性別，男女約各占50％，多次拋一枚均勻的硬幣，正反面出現(xiàn)的次數(shù)約各占50％ 為研究隨機(jī)現(xiàn)象的統(tǒng)計規(guī)律性而進(jìn)行的試驗稱為隨機(jī)試驗。用字母Ｅ來表示。,66,概率模型,隨機(jī)試驗具有下面三個特點 1. 在相同條件下可以重復(fù)進(jìn)行 2. 試驗前不能確定出現(xiàn)哪種結(jié)果 3. 能夠知道可能出

44、現(xiàn)的所有結(jié)果 在隨機(jī)試驗中出現(xiàn)的每一個結(jié)果，稱為隨機(jī)試驗的基本事件。全體基本事件組成的集合稱為樣本空間Ｕ。例如，上面舉過的例子中， 和 樣本空間Ｕ的子集稱為隨機(jī)事件。因此，隨機(jī)事件是指隨機(jī)試驗出現(xiàn)的一種結(jié)果或幾種結(jié)果的總和。用A、B、C等表示。 樣本空間Ｕ表示必然事件，空集 表示不可能事件,67,概率模型——1. 事件的關(guān)系和運算,事件的包含和相等 如果事件A

45、發(fā)生必然導(dǎo)致事件B發(fā)生，那么稱事件A包含于事件B，或稱事件B包含事件A，記作　　 例如，擲一枚骰子， 如果 ，同時 ，則稱A＝B 事件的和 事件A發(fā)生或事件B發(fā)生，稱為事件A與事件B的和，記作A＋B。 事件A發(fā)生或事件B發(fā)生，換句話說，就是事件A和事件B至少有一件發(fā)生。,68,概率模型,例如：分析下列事件的關(guān)系 ⑴ 隨機(jī)抽查一批產(chǎn)品的質(zhì)量，記 A＝{抽到三個不合格產(chǎn)品}

46、 B＝{抽到兩個以上不合格產(chǎn)品} ⑵拋兩枚硬幣，記 C＝{不出現(xiàn)反面朝上} D＝{兩個都是正面朝上} 解： ⑴ 事件A發(fā)生則事件B一定發(fā)生了，所以 ⑵ 拋兩枚硬幣，不出現(xiàn)反面朝上，即出現(xiàn)兩個正面，顯然C＝D,69,概率模型,(3) 以直徑和長度兩項指標(biāo)衡量產(chǎn)品的質(zhì)量，設(shè) A＝{零件直徑不合格}，B＝{零件長度不合格}, E＝{零件不合格}, 試用事件A、B表示E 解 事件E發(fā)生，表示或者事件A發(fā)

47、生或者事件B發(fā)生或者事件A、B同時發(fā)生，即事件A、B至少有一件發(fā)生 故 E＝A＋B (4) 從一批產(chǎn)品中任意取出2件，A1＝{恰好有1件是次品}，A2＝{恰好有2件是次品}，試用A1、A2表示事件B＝{至少有1件是次品} 解 至少有1件是次品的意思是說，恰好有1件是次品，或者2件都是次品 因此 B＝A1＋ A2,70,概率模型,事件的積 事件A和事件B同時發(fā)生，稱為事件A與事件B的積，記作AB 例如，設(shè)C＝{零件的直徑合格

48、}, D＝{零件的長度合格}, F＝{零件合格}，試用事件C、D表示F 解 只有零件的直徑和長度都合格，零件才算合格，因此事件F發(fā)生時，事件C、D都要發(fā)生。也就是說，事件C、D同時發(fā)生，才表示事件F發(fā)生，即 F＝CD 事件的差 事件A發(fā)生而事件B不發(fā)生，稱為事件A與事件B的差，記作A－B,71,概率模型,互不相容事件 如果事件A與事件B不可能同時發(fā)生，則稱事件A與事件B互不相容或互斥。顯然：AB＝ 對立事件與完備事件組

49、 對立事件是一種特殊的互不相容事件。如果事件A與事件B不能同時發(fā)生，而事件A與事件B又必發(fā)生其一，則稱事件A和事件B是對立事件，即事件A是事件B的反面，稱為B非，記作 事件A與事件B互為對立事件是說 它們滿足AB＝ ，A＋B＝Ｕ 顯然，,72,概率模型,重新認(rèn)識事件的差 事件的差 ，而 可見，事件A－B和事件B－A是不同的。 如果有n個事件

50、 兩兩互不相容，而他們的和是必然事件，則稱事件 構(gòu)成一個完備事件組,73,概率模型——2. 事件的運算律,,,,,,,,,,,,,,,74,概率模型——3. 例題,對飛機(jī)連續(xù)射擊兩次，每次發(fā)射一枚炮彈，設(shè)A1＝{第一枚擊中飛機(jī)}，A2＝{第二枚擊中飛機(jī)}，試用A1，A2及它們的對立事件表示以下事件： B＝{兩彈都擊中飛機(jī)}，C＝{兩彈都沒有擊中飛機(jī)}，D＝{恰有一彈擊中飛機(jī)}，E＝{至少有一

51、彈擊中飛機(jī)} 解： B＝A1A2， ，D＝ ， E＝A1＋A2 其中B與C，B與D，C與D，C與E都是互不相容事件，C與E是對立事件,75,概率模型——4. 隨機(jī)事件的概率,概率的統(tǒng)計意義 隨機(jī)事件在隨機(jī)試驗中發(fā)生的可能性大小的數(shù)值稱為概率 在條件不變的情況下重復(fù)進(jìn)行n次試驗，事件A發(fā)生了m次，那么m稱為A事件發(fā)生的頻數(shù)，比值 稱為事件A發(fā)

52、生的頻率，用fn(A)表示。 如果當(dāng)n足夠大時，事件A的頻率fn(A)在一個常數(shù)p(0≤p≤1)附近擺動，則稱事件A為隨機(jī)事件，p為事件A在該條件下發(fā)生的概率，記作P(A)＝p 必然事件 P(A)＝1 不可能事件 P(A)＝0,76,概率模型——5. 概率性質(zhì),性質(zhì)1 對于任一事件A， 這是因為，任一事件A的頻數(shù)m≥0，m≤n性質(zhì)2 性質(zhì)3 對于有限個兩兩互不相容的事件 即[推論] 如果

53、 則,77,概率模型——6. 古典概型,古典概型是指等可能事件的概率模型 如果一次試驗有n種可能的結(jié)果，且這n種結(jié)果出現(xiàn)的可能性都相同，而事件A包含了這n種可能中的k種可能，則事件A發(fā)生的概率為P(A)＝k／n，這種概率稱為古典概率 例1，擲一枚骰子，求C＝{4,5,6}和D＝{4,6}的概率 解 擲一枚骰子出現(xiàn)的點數(shù)有6種可能，這6種點數(shù)的可能性是相同的，屬于古典概型 其中C占了3種可能出現(xiàn)的情況，

54、D占了2種可能出現(xiàn)的情況，故P(C)＝3／6，P(D)＝2／6,78,概率模型——7. 貝葉斯(Bayes)定理,貝葉斯定理給出了兩個條件概率p(Bi|A)和p(A|Bi)之間的關(guān)系貝葉斯定理的例子 三個抽屜分別裝有金幣和銀幣 B1: 兩個金幣 B2: 一個金幣和一個銀幣 B3: 兩個銀幣 隨機(jī)地選一個抽屜并從中取出一個錢幣，假定取出的是一個金幣，求同一抽屜中另一個錢幣是金幣的概率,79,概率模型,第一次取出金幣的事件，另一

55、個錢幣也是金幣條件要求只能選取B1,即要求的是在A發(fā)生的條件下，選擇抽屜B1的概率： p(B1|A) 在選定抽屜的情況下，取出一個金幣的概率 P(A|B1)=1, p(A|B2)=0.5, p(A|B3)=0 選擇某一抽屜的概率 p(B1)=p(B2)=p(B3)=1/3 由貝葉斯定理,80,概率模型,概率模型試圖在一個概率框架中處理信息檢索問題，其基本思想是：給定一個用戶的查詢，則有一個包含相關(guān)文檔且不包含不相關(guān)文檔的

56、集合。設(shè)想這個文檔集合是一個理想的結(jié)果集。給出這個理想結(jié)果集的描述，并用于檢索。這樣，我們可以認(rèn)為查詢的過程是說明理想結(jié)果集屬性的過程，初始的時候努力的猜測它們是什么，猜測結(jié)果我們將產(chǎn)生一個對理想結(jié)果集的概率描述，檢索出最初的結(jié)果集，然后引入用戶的交互，改善結(jié)果集。,81,概率模型,基本假設(shè) 給定一個查詢q和文檔集中一個文檔dj，概率模型試圖找出用戶對其感興趣的概率模型假設(shè)這個概率只是依賴于查詢和文檔的表示，進(jìn)而模型假設(shè)文檔集中存

57、在一個子集，它使得總體相關(guān)概率在集合中的文檔被認(rèn)為是與查詢相關(guān)的，不在集合中的則被認(rèn)為是不相關(guān)的,82,概率模型——8. 模型原型,概率論模型，亦稱為二值獨立檢索模型 1976年由Roberston和Sparck Jones提出的經(jīng)典概率模型。它企圖在概率的框架下解決IR的問題 給定一個用戶查詢，存在一個文檔集合，該集合只包括與查詢完全相關(guān)的文檔而不包括其他不相關(guān)的文檔，稱該集合為理想結(jié)果集合 如何描述這個理想

58、結(jié)果集合？ 即：該理想結(jié)果集合具有什么樣的屬性？ 基于相關(guān)反饋的原理，需要進(jìn)行一個逐步求精的過程,83,概率模型—9. PRP (Probability Ranking Principle),將信息獲取看成是一個過程 用戶提交一個查詢，系統(tǒng)提供給用戶它所認(rèn)為的相關(guān)結(jié)果列表 用戶考察這個集合后給出一些輔助信息 系統(tǒng)再進(jìn)一步根據(jù)這輔助信息(加上以前的信息)得到一個新的相關(guān)結(jié)果列表；如此繼續(xù)。 如果每次結(jié)果列表中的元素總

59、是按照和查詢相關(guān)的概率遞減排序的話，則系統(tǒng)的整體效果會最好 概率的計算基于當(dāng)時所能得到的所有信息,84,概率模型——10. 貝葉斯定理,貝葉斯定理 詞條的獨立假設(shè) P(AB)= P(A) P(B) 當(dāng)且僅當(dāng) A與B相互獨立 對一篇文檔而言，若文檔中的各個索引詞相互獨立，則有 P(dj)=P(k1)…P(kt),85,概率模型——11. 模型定義,定義 設(shè)索引詞的權(quán)重為二值的，即： R表示已知的相關(guān)文檔

60、集（或最初的猜測集），用 表示R的補(bǔ)集。 表示文檔dj與查詢q相關(guān)的概率， 表示文檔dj與查詢q不相關(guān)的概率。文檔dj與查詢q的相似度sim(dj, q)可以定義為：,86,概率模型——,根據(jù)貝葉斯定理有,,87,概率模型——,假設(shè)標(biāo)引詞獨立，則 這是概率模型中排序計算的主要表達(dá)式,,88,概率模型——,取對數(shù)，在相同背景下，忽略對所有因子保持恒定不變的因子，則有,,89,概率模型——,

61、如何計算上式中的 和 呢 ？ 簡單假設(shè)作為最初的猜測 1) 對所有的索引詞ki是恒定不變的，通常取為0.5，即 2) 不相關(guān)文檔中的索引詞ki的分布可以通過文檔集中索引詞的分布來估計，即 其中，ni表示包含索引詞ki的文檔數(shù)， N表示集合中的文檔總數(shù) 初始值確定后，根據(jù)與查詢q相關(guān)的大小進(jìn)行初步排序，取前若干個文檔作為相關(guān)查詢集合 之后通過如下方法進(jìn)行

62、改進(jìn)(即開始遞歸計算),90,概率模型——,用V表示概率模型初步檢出并經(jīng)過排序的文檔子集 Vi表示V中包含索引詞ki的文檔數(shù) 改進(jìn) 和 的過程如下： 1) 用已經(jīng)檢出的文檔中索引詞ki的分布來估計 2) 假定所有未檢出的文檔都是不相關(guān)的來估計 即 如此遞歸重復(fù)這一過程，得到理想結(jié)果集合,91,概率模型——,對較小的V和Vi上述計算會出現(xiàn)問題，

63、如V=1和Vi=0，可做一些改進(jìn)： 調(diào)整因子也可以為ni/N， 即,,92,概率模型——,概率模型的算法步驟 起始時（只有查詢需求，沒有檢索結(jié)果）假設(shè)：（1）對所有索引項概率 是常數(shù)；（2）索引項在非相關(guān)文檔集中的分布近似等于在所有文檔集中的分布，即：,93,概率模型——,令V是初始檢索結(jié)果的子集，有r個，取自檢索結(jié)果集中前r個文檔，這些檢索結(jié)果是經(jīng)過概率模型排好順序的 令Vi是V中所有包含索引項k

64、i的那些文檔，顯然Vi是V的子集；為簡單起見，直接用V和Vi表示這些集合中的元素數(shù)量 修改對概率 和 的計算方法,94,概率模型——,為保證數(shù)值計算的穩(wěn)定性，常用下列公式計算相似度：,,95,概率模型——12. 優(yōu)缺點,優(yōu)點 理論上講，文檔按照其與目標(biāo)集合的相關(guān)概率 降序排列 缺點 需要最初將文檔分為相關(guān)和不相關(guān)的集合 所有權(quán)重都是二值的，模型中仍然假設(shè)索引項之間是相互獨立的,其他模型,

65、結(jié)構(gòu)化文本檢索模型信息瀏覽模型,97,其他模型——1. 結(jié)構(gòu)化文本檢索模型→概念,有時候，用戶希望能夠?qū)ξ臋n中的某些結(jié)構(gòu)組元中包含的信息進(jìn)行檢索，例如，對出現(xiàn)在章節(jié)標(biāo)題的詞進(jìn)行檢索。那么就需要一種模型，把文檔內(nèi)容與文檔的結(jié)構(gòu)結(jié)合起來，為用戶提供信息檢索的能力。這種模型就被稱為結(jié)構(gòu)化文本檢索模型。 在檢索任務(wù)中，傳統(tǒng)的結(jié)構(gòu)化文本檢索模型沒有采用相關(guān)性的思想，它只是從各個結(jié)構(gòu)組元中匹配用戶的查詢項。從這個意義上看，過去的結(jié)構(gòu)化文檔檢索模

66、型是一個數(shù)據(jù)檢索模型，但是，檢索系統(tǒng)能夠搜索出那些部分匹配查詢條件的文檔，在這種情況下，這種匹配是近似的，并且某些排序也是使用這種近似的結(jié)構(gòu),98,其他模型——結(jié)構(gòu)化文本檢索模型→概念,結(jié)構(gòu)化文檔檢索算法可以看作是一種信息檢索算法，但排序機(jī)制并不健全 使用“匹配點”來表示文本與用戶查詢相匹配的詞串位置 使用“區(qū)域”表示文本的塊 使用“節(jié)點”表示文檔的結(jié)構(gòu)化組元 這樣，一個節(jié)點是一個區(qū)域，具有文檔的作者與用戶所共知的、預(yù)定義的邏輯

67、屬性,99,其他模型——結(jié)構(gòu)化文本檢索模型,基于非重疊鏈表的模型是把文檔中的整個文本劃分為非重疊文本區(qū)域，并用鏈表連接起來 因為有多種方法將文本分為非重疊的區(qū)域，所以，對于同一個文檔，會產(chǎn)生多個鏈表 這些鏈表清晰的記錄了文檔的數(shù)據(jù)結(jié)構(gòu) 在相同鏈表中的文本區(qū)域沒有重疊，而不同鏈表中的文本區(qū)域可能會重疊,100,其他模型——2. 結(jié)構(gòu)化文本檢索模型→非重疊鏈表模型,為允許對索引項和文本區(qū)域進(jìn)行搜索，要為每個預(yù)定義的鏈表建立一個索引

68、在索引中每個結(jié)構(gòu)組元作為索引中的一個項目 因為針對每個索引項目，其索引的文本區(qū)域是不重疊的，所以可以提交的查詢是簡單的 選擇一個包含給定詞的區(qū)域 選擇一個不包含在給定區(qū)域的區(qū)域 選擇一個不被包含于任何其他區(qū)域的區(qū)域,,101,其他模型——結(jié)構(gòu)化文本檢索模型,該模型是一種允許在相同文檔上獨立定義分層索引結(jié)構(gòu)的模型，每個索引結(jié)構(gòu)是一個嚴(yán)格的層次結(jié)構(gòu)，其中每個結(jié)構(gòu)組元稱為節(jié)點，每個節(jié)點與一個文本區(qū)域相關(guān)，兩個不同的層次結(jié)構(gòu)可能涉及到兩