《搜索引擎-信息檢索實踐》筆記

05-08

倒排索引

簡單地來說倒排索引以單詞作為index，認為包含該單詞的文本是index後面的一行。每行倒排索引的列表中的元素被稱為posting。具體地來說，倒排索引可以僅包括文本的id，但是這種情況不能很好地表示同一篇文本里多次出現某一個單詞，所以。我們可以對倒排索引進行改進。

改進一：除了有文本的id以外，加入該單詞在文本里出現的次數。這樣我們就可以選出來對某個具體的單詞排名最靠前的文本了。

改進二：我們將可以加入該單詞在文本里的位置，這種情況所增大倒排索引列的長度。

改進三：考慮到單詞出現在文本的標題和正文里對於文本在一條索引里的重要性是不同的。我們可以在倒排索引里引入域和範圍的概念。第一種方法是按照不同的域建立不同的索引表，可以為正文建立一個，為標題建立一個，為小標題建立一個。第二種方法是在每個posting後面增加一個bit位用來表示該單詞在該文本里究竟是不是處在標題。當域的種類增加的情況下，以上兩種方法會帶來巨大的開銷。第三種方法是範圍表，範圍表可以表示文本內標題出現在起始位置和終止位置，這樣我們就可以判斷出現在某一文檔里的單詞是不是出現在範圍域內。

布爾檢索

通過關鍵詞在文檔中出現返回為True，沒出現返回未False，其中可以加入基本的邏輯運算。

向量空間模型

將查詢信息和文檔都表示成向量，通過計算向量的餘弦相似性，給文檔給出相關性得分。

文檔的向量可以用tf-idf向量來表示。

二元獨立模型

給定一篇文檔D判斷它是不是相關文檔，這是一個二元分類的問題。其中相關可以表示為R，不相關表示未NR。如果我們要判定一篇文檔屬於相關文檔，則必須得到

$egin{align} frac{P(R|D)}{P(NR|D)} &>1\ P(R|D)&>P(NR|d)\ frac{P(D|R)P(R)}{P(D)}&>frac{P(D|NR)P(NR)}{P(D)}\ frac{P(D|R)}{P(D|NR)}&>frac{P(NR)}{P(R)} end{align}$ （式1）

等式左邊是在相關文檔里出現這篇文檔的概率比上在不相關文檔里出現這篇文檔的概率，等式右邊是不相關文檔和相關文檔的之比，是先驗概率可以通過計算得到。

現在來看一下P(D|R)等於什麼，文檔D可以表示為一個m唯的向量，其中每一個分量為0或1，m表示詞典的大小。根據條件獨立的假設：

$P(D|R)=P([d1...dm]|R) = prod _{iin D}P(d_i|R)$ （式2）

我們不妨設P(di=1|R)=pi,P(di=0|R)=1-pi，同理設P(di=1|NR)=si,P(di=0|NR)=1-si。所以（式1）就可以寫成

$egin{align} frac{P(D|R)}{P(D|NR)}&=prod_{i:di=1}frac{p_i}{s_i} prod_{i:di=0}frac{1-pi}{1-si}\ &=prod_{i:di=1}frac{p_i}{s_i}(prod_{i:d_i=1}frac{1-s_i}{1-p_i}prod_{i:d_i=1}frac{1-p_i}{1-s_i}) prod_{i:di=0}frac{1-pi}{1-si}\ &=prod_{i:di=1}frac{p_i(1-s_i)}{s_i(1-pi)}prod_ifrac{1-pi}{1-si} end{align}$ （式3）

如果我們利用上式是為了給不同的文檔排序，上面的D具體可能是D1,D2,..,.Dn。對於這些不同的D來說上式的最後一項是相同的，這一些之和相關文檔與不相同文檔有關，而與我們要判別的文檔無關，所以可以將其省略。但是要是為了和P(NR)/P(R)進行比較，從而判斷是否為相關文檔，此時不可以省略。

具體對pi和si的估計，我們借用書上的一張表。

顯然pi =ri/R,si=(ni-ri)/(N-R)，這裡為了防止出現pi和si為零的情況。我們設pi = (ri+0.5)/(R+1),

si = (ni-ri+0.5)/(N-R+0.5). 帶入（式3）得到

$prod_{i:di=1}log(frac{p_i(1-s_i)}{s_i(1-pi)})=prod_{i:di=1}log(frac{(r_i+0.5)(R-r_i+0.5)}{(n_i-r_i+0.5)(N-n_i-R+r_i+0.5)})$ ( 式4)

BM25模型

BM25是在二元獨立模型上發展而來的。

具體地BM25的得分函數如下所示：

$prod_{i:di=1}logfrac{(r_i+0.5)(R-r_i+0.5)}{(n_i-r_i+0.5)(N-n_i-R+r_i+0.5)} frac{(k_1+1)f_i}{(K+f_i)}frac{(k_2+1)qf_i}{k_2+qfi}$