說明：文章內(nèi)容來源于課程視頻和課程ppt。我只學(xué)習(xí)了課程沒有做習(xí)題。文章不是翻譯，是我對課程的理解。

---

上文提到文檔排序函數(shù)是TR的核心。文檔排序函數(shù)的實現(xiàn)有幾種思路，其中一種是基于相似度的模型。這種模型具體是用空間向量模型(Vector Space Model)實現(xiàn)。這篇文章就介紹VSM。

VSM概念

什么是VSM

　VSM定義了兩點。
　第一，用詞向量(term vector)來表示查詢語句、表示文檔。英文中的term vector，我們翻譯為詞向量。但是這里的“詞”并不是指漢語中的一個詞，具體含義是：基本概念，可以是一個字、一個詞、一個短語。每個詞表示一個維度，N個詞就可以定義N維空間。如上圖所示，programming,libarary,presidential，分別定義了三個維度。查詢語句的向量表示：$q=(x_1,x_2,...x_N)$，文檔的向量表示：$d=(y_1,y_2,...y_N)$。
　第二，查詢語句和文檔的相關(guān)度正比于查詢語句和文檔的相似度：$relevance(q,d)\propto similarity(q,d)=f(q,d)$

VSM沒有定義的

1 怎么定義或者說怎么選擇term。只說term是文檔集中的基本概念，并未指明什么可以作為term。
　2 向量的表示。用什么值來計算查詢向量和文檔向量。
　3 相似度怎么計算。
　基于以上幾點說VSM其實是一個框架frame。在實踐中有好多版本的實現(xiàn)。繼續(xù)往下看。

VSM實現(xiàn)

來源于ppt的例子。
　query=“news about presidential campaign”
　d1:"… news about …"
　d2:"… news about organic food campaign…"
　d3:"… news of presidential campaign …"
　d4:"… news of presidential campaign … … presidential candidate …"
　d5:"… news of organic food campaign… campaign…campaign…campaign…"

在這個例子中很理想的排序大概應(yīng)該是：d4,d3。d1,d2,d5其實是不相關(guān)文檔。

簡單實現(xiàn)

BOW+bit-vector+dotproduct 這是一個最簡單的實現(xiàn)。
　1 用文檔中的每一個詞定義一個維度。稱為詞袋模型(Bag of Word=BOW)。
　2 用Bit-Vector 表示向量。如果詞出現(xiàn)則記為1，否則為0。$x_i,y_i\in \{0,1\}$。
　3 相似度通過點積(dot product)計算。
　最終表示
　$q=(x_1,x_2....y_n),x_i\in \{0,1\}$
　$d=(y_1,y_2...y_n),y_i\in \{0,1\}$
　$sim(q,d)=x_1{y}_1+x_2{y}_2+....+x_N{y}_N={\sum }_{i=1}^N{x}_i{y}_i$
　
　計算一下例子。
　V= {news, about, presidential, campaign, food …. }
　q= (1, 1, 1, 1, 0, …)
　d1= (1, 1, 0, 0, 0, …)
　d2= (1, 1, 0, 1, 0, …)
　d3= (1, 0, 1, 1, 0, …)
　…
　f(q,d1)=11+11+0…=2
　f(q,d2)=11+11+0+1*1+…=3
　…
　本算法中sim(q,d)函數(shù)的實質(zhì)就是表示有多少個不同的查詢詞出現(xiàn)在文檔中。
　在d2,d3,d4文檔中各出現(xiàn)了3次，值為3,；在d1,d5文檔中各出現(xiàn)了2次，值為2。

進(jìn)階實現(xiàn)

BOW+term frequency+dotproduct
　問題：d4中 “presidential ”的次數(shù)要比d2多，應(yīng)該排在前面才對。
　解決策略就是使用詞頻這個信息。
　最終表示
　$q=(x_1,x_2…y_n),x_i $是詞$w_i$在查詢語句中出現(xiàn)次數(shù)$d=(y_1,y_2…y_n),y_i $是詞$w_i$在文檔中出現(xiàn)次數(shù)$sim(q,d)=x_1y_1+x_2y_2+…+x_Ny_N=\sum_{i=1}^{N}x_iy_i$
　
　計算一下例子。
　f(q,d4)=11+10+12+11+0+…=4
　f(q,d2)=…
　…

TF-IDF

BOW+TF-IDF+dotproduct
　
　
　問題：d2與d3，雖然都命中3個詞，但是顯然命中presidential比命中about得分要高。presidential含有更重要的信息嘛。
　解決策略：使用逆文檔頻率IDF，在越多文檔中出現(xiàn)，權(quán)重越低。
　$IDF=log\frac{M+1}{k}$，M是文檔集中文檔數(shù)量，k是詞在多少個文檔中出現(xiàn)。
　
　可以看到當(dāng)k=1的時候，IDF=log(M+1)；當(dāng)k=M的時候IDF接近0。
　
　最終表示
　$q=(x_1,x_2…y_n),x_i $是詞$w_i$在查詢語句中出現(xiàn)次數(shù)$d=(y_1,y_2…y_n),y_i =c(w_i,d)*IDF(w_i)，c(w_i,d)$是$w_i$在文檔中的出現(xiàn)次數(shù)，$IDF(w_i)$是$w_i$在整個文檔集中的逆文檔頻率。$sim(q,d)=x_1y_1+x_2y_2+…+x_Ny_N=\sum_{i=1}^{N}x_iy_i$
　
　計算例子
　V= {news, about, presidential, campaign, food …. }
　IDF(W)= 1.5 1.0 2.5 3.1 1.8
　f(q,d2)=5.6 ， f(q,d3)=7.1問題解決。但是f(q,d5)=13.9。我們在最開始就分析了排在前面的文檔應(yīng)該是d4，d3。

TF變形

$sim(q,d)=f(q,d)={\sum }_{i=1}^N{x}_i{y}_i={\sum }_{w\in q\cap d}c(w,q)c(w,d)log\frac{M+1}{df(w)}$,df(w)是指詞w的文檔量。
　問題：d5的打分太高了：13.9，分值高是因為“campaign”的頻率太高。當(dāng)一個詞從無到有，有重要價值。但一個文檔中包含某個詞3-5次，與10次基本上不會有太大差異。所以要適當(dāng)降低詞頻的影響。
　解決方法1：被稱為“亞線性變換(Sublinear TF Transformation)”。使用log函數(shù)。函數(shù)1：$y=x$，函數(shù)2：$y=log(1+x)$，函數(shù)1的增長率要比函數(shù)2大多了。
　

$f(q,d)={\sum }_{w\in q\cap d}c(w,q)ln[1+c(w,d)]log\frac{M+1}{df(w)}$

解決方法2：被稱為“BM25變換”。這種變換需要為詞頻設(shè)置一個最大值。假設(shè)最大值為6，超過6的詞頻都沒有區(qū)別。函數(shù)$y=\frac{(k+1)x}{x+k}$，函數(shù)值會無線接近于k+1。實踐證明BM25變換是非常健壯和有效的(robust and effective)。
　
　

$f(q,d)={\sum }_{w\in q\cap d}c(w,q)\frac{(k+1)c(w,d)}{c(w,d)+k}log\frac{M+1}{df(w)}$

文檔長度變形

問題：當(dāng)一個文檔很長的時候，會更容易出現(xiàn)一個詞，一個詞的頻率也更可能高。所以我們需要懲罰一下長文檔。一個文檔很長可能因為兩個原因：一種是文檔內(nèi)容很詳細(xì)，做了很多必要的描述；還有一種情況是一個大的文檔中講述了很多內(nèi)容，每個內(nèi)容一個小的段落，這樣的文檔其實是一個一個的小文檔。在第二種情況中，詞的相關(guān)度計算出來是不同的：從長文檔中計算與從短文檔中計算。
　
　解決：算法稱為Pivoted Length Normalization。這里同樣也有一個參數(shù)需要選擇：平均文檔長度avdl。函數(shù)：$normalizer=1?b+b\frac{d}{avdl}$，參數(shù)b是懲罰因子，$b\in [0,1]$。
　
　normalizer會放在相似度函數(shù)$f(q,d)$的分母上。
　當(dāng)b=0，所有值都為1，沒有懲罰。
　當(dāng)b>0，當(dāng)文檔長度$<$avdl，normalizer<1，f(q,d)會增加；當(dāng)文檔產(chǎn)度>avdl，normalizer>1，f(q,d)會減小。
　
　最后的公式
　TF亞線性變換：$f(q,d)={\sum }_{w\in q\cap d}c(w,q)\frac{ln[1+c(w,d)]}{1?b+b\frac{d}{avdl}}log\frac{M+1}{df(w)}$
　BM25變換：$f(q,d)={\sum }_{w\in q\cap d}c(w,q)\frac{(k+1)c(w,d)}{c(w,d)+k(1?b+b\frac{d}{avdl})}log\frac{M+1}{df(w)}$
　
　考慮文檔長度其實是把詞頻轉(zhuǎn)為詞頻率，便于比較。

如何進(jìn)一步提高VSM的效果

從詞的維度改進(jìn)。例如可以去掉停止詞、做詞的變換(stemmed words)、使用短語、語義索引、n元模型等待。
　改進(jìn)相似度函數(shù)。例如可以用歐式距離、用余弦距離表示相似度。實踐中證明點積還是最適合的。

總結(jié)

以上是生活随笔為你收集整理的文档排序--相似度模型--VSM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。