12/22/2008

Google Distance

paper: link
My presentation slides: link 

(p.s. 紅色部份是我還是非常不了解的地方)
這篇paper讓我覺得很有趣的地方是它用了資訊理論的encoding概念去計算出term 的semantic 關係。往常在semantic組討論到的大致上不外乎是based on  "ontology are us "的方法,藉由tag 跟tag 的co-occurence關係推論出tag跟tag間的relation。

在開始提什麼是google distance之前,要先複習一下一些編碼基礎,因為我沒有修過計算理論(汗顏) 所以我只能先就我了解的部份還有與這篇paper相關的部份大概說明一下。

第一個要提到的概念是entropy,在information theory 中,亂度越大,表示需要用越多byte去描述它。

而我們的目標是要想辦法找出一個編碼方式,用盡可能短的資料量來描述我們的data。在此,有一個名詞叫Kolmogorov complexity(詳細說明請見wikipedia 中文 英文),它表示了對一個字所需的資料量。我們需要注意的是為了達到盡可能少的資料量,越常出現的東西,就應該用盡量短的編碼來描述它。另外,在編碼時我們還需要計算不同term之間的distance,也就是Information Distance , E(x,y)。它被定義成: 
E(x,y) = K(x,y)-min(K(x),K(y))
p.s. 這邊我暫時查不到為什麼要算編碼,剛剛請教學姊的結果,學姊也只說印象中似乎是encoding跟decoding的過程中要用到

另外我還可以Normalized distance,使得E界於0~1之間:
Normalized Information Distance = [K(x,y)-min(K(x),K(y))] / max(K(x),K(y))
(p.s. 這邊的距離指的是編碼後兩個term距root的距離,理論上相關的字會被放在附近)

但是因為Kolmogorov complexity需要global的data,在實際情況下無法直接計算,所以我們可以用某個可以計算的Compressor, C來取代。在這裡可以想像我們是用了抽樣的方式來間接的取得K(x)的值。

抽樣的方法有很多,這篇paper提出的方式就是把整個WWW當作一個超大的database,然後利用google來做抽樣的工作。所以把C換成google之後,對一個term, x 它出現的mass probablity function , L(x)  = |x|/M,   (M = |Omega|  , Omega = Univeral. ) 
接下來我們可以去算2個term, x & y共同出現的機率。

定義Google Code(why they defined the form??)
G(x) = G(x,x) , G(x,y) = log 1/g(x,y)
g(x) = g(x,x), g(x,y) = L(x and y) M /N = |x and y|/M

就可以得到
Normalized Google Distance = [G(x,y)-min(G(x),G(y))]/max(G(x),G(y))

但是算出這個要怎麼知道(確定)這個距離跟semantic意思有關呢?在paper 裡面並沒有直接提到,不過它們將這個距離與WordNet比較,發現有87%的相似度!!!比較的方法如下:
先從wordnet裡面挑部份字跟category出來,計算它們的similarity後用SVM train model,train好了以後再另外丟新的字下去分類,再看看是否分得正確。

0 comments: