一. 概率知識回顧
聯(lián)合概率
表示兩個事件共同發(fā)生的概率
如果兩個事件相互獨(dú)立, 則P(x, y) = P(x) · P(y) , 比如 P(第一次正面, 第二次正面) = 0.5 x 0.5 = 0.25條件概率
表示已知事件b (base)發(fā)生的情況下, 事件a (action)發(fā)生的概率P(a|b) = P(a, b) / P(b)
解釋: 已知b發(fā)生, a的發(fā)生概率 = a, b聯(lián)合發(fā)生概率 / base發(fā)生的概率
那么, 怎么如果有條件概率了, 我們怎么算聯(lián)合概率呢? 可以倒騰一下條件概率公式, 得到 P(a, b) = P(b) · P(a|b), 也就是說兩個事件ab共同發(fā)生的概率 = a發(fā)生的概率 x 已知a發(fā)生條件下b發(fā)生的概率;
于是, 我們得到了
鏈?zhǔn)揭?guī)則
P(x1, x2, ..., xn ) = P(x1) · P(x2|x1) · P(x3|x1,x2) ·... · P(xn | x1, ..., xn-1)
其中, P(x3|x1,x2) = P(x3, x1, x2) / P(x1, x2)
解釋: action x3的條件概率 = x3與base(x1, x2)的聯(lián)合發(fā)生概率與base(x1, x2)的發(fā)生概率在文本挖掘中的例子:
P(今天, 天氣, 不錯) = P(今天) · P(天氣|今天) · P(不錯|今天, 天氣)
二. 引入: 信息熵概念
信息熵 = 不確定性
note: 此處p(x)是x發(fā)生的概率.
注意觀察這個定義函數(shù), 就可以發(fā)現(xiàn), 因?yàn)閜(x)<1, 所以如果p(x)值越小且x數(shù)目越多的話, 這個H(X)將增大.
這里其實(shí)是用簡單的導(dǎo)數(shù)計(jì)算, 假設(shè)p(x) = u, 則(ulogu)' = logu + 1, 單調(diào)遞增, 再引入前面的負(fù)號, 則看出隨著u增大, H是遞減的; 換句話說, u變小, H就增大.
因此, 很容易知道, 漢語的信息熵是比英語大不少的, 因?yàn)闈h語文字?jǐn)?shù)目大于英語文字?jǐn)?shù)目, 且漢語長尾詞語非常多, 他們相對來說概率都比較小, 很容易拉高H的值.
聯(lián)合熵: H(X, Y) = - Σp(x, y) log(p(x, y)), 其實(shí)就是把p(x)替換成了p(x,y)代表聯(lián)合概率.
條件熵: 在一個隨機(jī)變量已知的時候, 另外一個變量的不確定性
H(Y|X) = - Σp(x, y) log(p(y|x))
鏈?zhǔn)揭?guī)則: H(X, Y) = H(X) + H(Y|X)
互信息: I(X; Y) = Σp(x, y) log p(x, y)/p(x)p(y)
互信息的性質(zhì): I(X; Y) = H(X) - H(X|Y)
I指標(biāo)其實(shí)就是表現(xiàn)的兩個實(shí)體之間的相關(guān)程度. 如果X和Y完全獨(dú)立, 那么I(X; Y) = H(X)- H(X) = 0
舉例子: I(計(jì)算機(jī)軟件, 軟件) > I(計(jì)算機(jī), 汽車)
三. 詞語關(guān)系的發(fā)現(xiàn)
1. what, why, how
what:
兩種關(guān)系,
聚合關(guān)系/平行關(guān)系: paradigmatic
組合關(guān)系/共同關(guān)系: syntagmatic
上下文中A能被B替換, 那這是聚合關(guān)系. //平行關(guān)系, 比如cat , dog
A和B能放在一起做搭配, 那么這是組合關(guān)系 //共同關(guān)系, 互補(bǔ) 比如cat, eat
why?
應(yīng)用: 信息檢索中的search suggestion, 主題圖譜entity map.
How?
詞語關(guān)聯(lián), 對于平行關(guān)系詞語來說,他們往往有十分相似的context.
2. 如何發(fā)現(xiàn)這兩種關(guān)系? 直覺解釋
my cat eats fish on Saturday.
my dog eats meat on Monday.
平行關(guān)系: 按照常識, 上下文context相似度高的詞是平行關(guān)系.
組合關(guān)系: 組合關(guān)系是一種詞語的搭配關(guān)系. 按照常識, 這兩個詞會一起搭配使用. 如果共同出現(xiàn)的概率高, 而獨(dú)自出現(xiàn)的概率低, 那么就是組合關(guān)系.
所以我們由此得出的初步結(jié)論:
對于平行關(guān)系的, 我們獲取每個詞語的context, 然后計(jì)算詞語間context的相似度, 相似度高的就是平行關(guān)系.
對于組合關(guān)系的, 同時出現(xiàn)在某個語段context(比如一句話或者一段話)中的概率高, 而兩個詞語獨(dú)自出現(xiàn)的概率比較低, 那么這兩者就是組合關(guān)系.
有意思的是, 如果兩個詞語是平行關(guān)系的話, 那么他們往往有著相同的組合關(guān)系詞語來搭配使用. 比如dog eats meat. cat eats meat.
那么接下去, 我們首先注意到一個問題, 如何獲取每個詞語的context?
3. context to doc
我們可以把context轉(zhuǎn)化為一個我們熟悉的概念 -- document, 這樣我們就可以利用以前學(xué)過的文檔相似度計(jì)算的很多方法了.
這里, 我們約定Context = pseudo doc = bag of words詞袋
這里詞袋的大小選擇起來有很多種方法
比如下面這個公式
Sim("cat","dog") = Sim(Left1("cat"),Left1("dog")) + Sim(Right1("cat"), Right1("dog")) + ... + Sim(Win8("cat"), Win8("dog"))
其中, Window8("cat") = {"my","his","big", "eats", "fish"}
4. doc to vector
我們將使用Vector Space Model. 非常常見, 往往用在文本分類, 情感分類上.
當(dāng)我們定好了詞袋, 也就是我們的doc以后, 我們將會把它轉(zhuǎn)化為多維度空間中的一個向量.
這個空間有n個維度, 這個維度大小取決于文本庫corpus的總體獨(dú)特單詞數(shù), 因此維度數(shù)目非常地大.
假設(shè)表示一個doc("cat") = {"eats": 5, "ate":3, "is":10 , ...}
doc("cat")可能被表示為如下:
表示成向量后, 我們的下一個問題是: 怎么計(jì)算相似度?
5. 相似度計(jì)算
求相似度往往使用余弦定理: cos(a, b) = a · b / |a||b| ,
但是, 在我們真正開始算之前, 我們得先進(jìn)行標(biāo)準(zhǔn)化(正規(guī)化), 否則各個維度上的向量長度不一, 會出現(xiàn)大數(shù)吃小數(shù)的現(xiàn)象. 要深刻理解余弦定理是為了求解向量之間夾角的大小, 或者說a向量在b向量單位化后方向上投影的長度(值是0~1)
因此,
d1 = (x1, x2, ... xn), 其中xi = c(wi, d1)/|d1|, c = count, 換句話說, xi是x在d1中出現(xiàn)的概率
Sim(d1, d2) = d1 · d2 = x1y1 + ... + xnyn = Σ(1~n) xiyi 求解向量內(nèi)積
如果Sim = cos = 1, 夾角為0°, 那么就是完全的平行關(guān)系, 即同義詞
這個模型還存在的問題:
某些頻繁出現(xiàn)的詞仍然存在壓制其他詞影響力的可能.
存在大量的廢詞, 比如and, or, the 等等...
對空間的浪費(fèi), 這個維度數(shù)過高了(n如果在這里可能>=10k, 畢竟英語還是漢語的詞語都是非常多的)
6. TF-IDF權(quán)重的引入
為了解決上述簡單模型條件下存在的問題, 我們引入TF-IDF term weighting.
1) TF值
我們首先重新定義怎么計(jì)算TermFrequency. 過去是出現(xiàn)一次我就+1, 所以在詞袋中出現(xiàn)10次, TF=10
現(xiàn)在, 我們決定壓制那些出現(xiàn)次數(shù)過多的詞, 因此考慮引入兩種樸素辦法, 0/1 bit法, 或者對數(shù)函數(shù)法.
此處, 請務(wù)必記得我們約定y: 處理后的TF變形值, x : C(wi, d1) 詞語出現(xiàn)頻次
TF transformation method:
0/1 bit hot method (not good enough)
一個詞沒出現(xiàn)標(biāo)記為0, 出現(xiàn)了就標(biāo)記成1.from y = x to y=log(1+x) (good)
這里對數(shù)函數(shù)里頭+1, 是為了保證x=0, y=0, 而不至于出現(xiàn)異常.
2) 第三種TF值計(jì)算方法: BM25 transformation
第二種對數(shù)函數(shù)的方法已經(jīng)比較好用了, 但是我們追求完美! 于是乎我們又整出了第三種更牛逼一點(diǎn)的TF計(jì)算方法, 它是BM25算法的中對于TF部分的計(jì)算方法.
y = BM25(x) = (k+1)·x / (x+k), k是認(rèn)為調(diào)整的參數(shù), k是容忍參數(shù). k越大, 對freq words越?jīng)]有任何調(diào)整. 求導(dǎo)后, 可以看到當(dāng)k->∞, y->x.
k=0, 其實(shí)就是bit hot.
所以, BM25的TF計(jì)算完美實(shí)現(xiàn)了可以自由設(shè)定對高頻詞語維度容忍參數(shù)k.
3) IDF algorithm: count adjusting weight
IDF: IDF(word) = log[(M+1)/m] ,
其中m = total number of docs containing word, 是一個變量, 可以看到, m越大, IDF會相應(yīng)變得越小.
M: total number of docs in collection, 是一個常數(shù)
造成效果是: 文檔出現(xiàn)頻率m越高的詞語word, 會相應(yīng)有一個較低的IDF weight. 當(dāng)一個詞語幾乎每篇文檔都出現(xiàn)的時候, 那么 IDFweight會很接近 log(1) = 0. 而一個詞語出現(xiàn)得非常罕見, 比如unicorn, 那么它的IDFweight會被對數(shù)函數(shù)限制增長速度, 而不至于變得過大.
7. 最后總模型
我們約定word[i] = wi, document[1] = d1, i指的是第i個元素.
那么, 現(xiàn)在我們整篇文章的對于平行關(guān)系發(fā)現(xiàn)的論述就歸于如下兩步:
第一步:
TFi= BM25(wi, d1) = (k+1)c(wi, d1) / k+c(wi, d1)
xi = BM25(wi, d1) / Σ j:1~N { BM25(wj, d1) } //把TFi轉(zhuǎn)化成xi, 即標(biāo)準(zhǔn)化
第二步:
sim(d1, d2) = Σ i:1~N { IDF(wi)·xi·yi } //模型變化體現(xiàn)在TF算法改變, 以及加上權(quán)重值IDF(wi).
再次強(qiáng)調(diào), 現(xiàn)在 xi, yi來自BM25(wi, d1) / ΣBM25(wj, d1) , 即BM25's TF of wi / BM25's TF sum of all, 是∈[0, 1]的標(biāo)準(zhǔn)化量.
相似度的計(jì)算例子
Sim(d('dog'), d('cat')) = IDF('and') x('and')y('and') + IDF('eats') x('eats')y('eats') + ...
其中x('and', d('cat')) = TF('and', d('cat')) = BM25('and') = { (k+1)·count('and', d('cat')) }/ {k+count('and', d('cat'))}
此處, d('cat') 已經(jīng)代表的是是我們約定的一個pseudo document of 'cat' --> context of 'cat' 所轉(zhuǎn)化的vector.
End.
