Hardworking Strawberry

用slides說故事，每個人可以下comment，有聲音，也可以針對圖片的某個部份做說明

一邊說故事一邊下comment，也可以看別人怎麼描述這個圖片的，我覺得是個很有趣的idea:)

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))

另外我還可以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共同出現的機率。

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好了以後再另外丟新的字下去分類，再看看是否分得正確。