Latent Dirichlet Allocation

Latent Dirichlet Allocation

 D. Blei, A. Ng, and M. Jordan.
 Journal of Machine Learning Research, 3:993–1022, January 2003

topic model將原本從文件直接連結到字彙的機率，

轉變成兩個步驟的過程

其一是從文件到主題，而其二則是將主題對應到字彙

上個禮拜時候，我們談到了PLSA，但是PLSA有兩個致命性的缺點

















在如上圖的文本中，共有M個文件，而假設我們的topic有K個的話，
哪PLSA在將文件對應到主題的部分，一共就需要KM個參數，

這造成了一個很大的問題是參數的量，是隨著文件數量而線性成長的，
更不要說這樣做可能會導致的over-fitting了
而第二個問題是PLSA針對尚未見過過的文件無法有很有效的處理。

而為了解決這兩個問題，LDA模型就因此而誕生了!

 LDA模型描述

大致上來看，以下是LDA模型對於一個文本的生成的假設


1.利用poisson distribution決定文本的長度

2.利用dirichlet distribution (參數為alpha)來決定文件的topic distribution theta

3.對於這個文件中的每個字，由以下方式產生

    根據theta，產生一個topic
    根據topic以及beta，產生一個字
 


不過實際上因為決定文本長度的參數與其他參數是獨立的，因此我們將他視為一個輔助的參數而忽略不看

示意圖如下

在k個主題的情況下，dirichlet distribution如下    (註1)

                                                              (1)




於是我們就可以得到以下的結果

接著，把所有topic的結果加總，並且對distribution積分，我們就可以得到這樣的結果

                                          (2)







最後，將每一個文件的機率相乘，我們就可以得到整個文本的機率如下





                                           (3)




在這個model，有幾個地方值得我們注意

其一是，不同於simple dirichlet-mutinomial clustering model ，只對整個文章sample一次model，
LDA在文章內，對每一個字，不停的重新sample topic





其二則是LDA的無序性，而這個無序性可以在兩個部分展現，






在文章內，文件內的字的順序並不影響到文章的機率，
而同樣的，跨文件所組成的文本，文件的順序，也並不會影響到最後整個文本的機率
而基於無序的假設，我們可以得到以下的式子







另一方面來看，藉由揉合隱藏的主題模型，
我們可以將LDA表示成一個比較簡單的兩階段模型


我們可以將原本(2)表示成以下形式

                                                                  (4)


如此一來，我們就可以把LDA生成文件的步驟減化成如下

1.根據dirichlet distribution (參數alpha)選擇主題模型分布參數theta

2.根據theta以及式(4)產生文件的每個字

如此一來，我們就可以用以下式(5)表達新的文件機率

                                                             (5)

inference and parameter estimation

為了使用LDA模型，我們要解決的問題式計算隱藏參數(也就是theta跟topic )

                           




但是實際上，這樣的計算是很困難的，
因此實際上，我們可能會把這個問題轉換成另外一個形式

如下圖:














因此，實際上，我們就是想要藉由phi 以及gamma兩個參數來產生theta以及topic

不過，這樣所產生出來的結果當然會跟原本的有一定的落差，
因此，我們想要的phi 跟gamma就是跟原本的模型最接近的，如下式(6)


                                       (6)



接下來，我們就利用EM來進行參數的計算

smoothing

不過我們常常會遇到另外一個問題則是字典的大小，或者是說罕見字的問題，
對於罕見字，我們常常會遇到新出現的文章中出現以前從來沒有出現過的字的情況，
為了解決這個問題，所以我們通常會使用smoothing的技術，大體上來說如下圖所示

result

實際上，我們常常利用peplexity來計算我們結果，計算如下








註1

什麼是dirichlet distribution?
舉個例子來說，當我們丟一個銅板一萬次的機率是(0.4,0.6)

dirichlet distribution  P((0.5,0.5)|(0.4,0.6))的意思就是說，
在我們已經知道這一萬次的結果之後，那接下來我們丟銅板會出現(0.5,0.5)的結果的機率是多少?

Probabilistic latent semantic model

Probabilistic latent semantic model

在我搞懂怎麼在blogger上用letex之前，只能用超聯結了QQ

http://knowbee.logdown.com/posts/189751-probabilistic-latent-semantic-model

Product quantization for nearest neighbor search

Product quantization for nearest neighbor search

 Jegou, Herve, Matthijs Douze,
 Pattern Analysis and Machine Intelligence 2011

nearest neighbor search (NN earch):







在高維度的情況下，NN search很花時間，
所以我們可以使用A(aproximate)NN search，
而評估ANN search的好壞則根據效率與搜尋品質的妥協來決定，
但是實際上我們應該要考慮到空間的使用，
很多像是E2LSH這樣的演算法是很花空間的



這篇paper試著利用將高維的像量轉移到低維的像量的積，
並且引入inverted file system來達到提高效率與搜尋品質的任務，
並且同時考量的空間的使用。

 一、Background :Quantization , Product Quantization

 
   1. vector quantization :
    一個函數q將D維的向量映射到一個有限大小的向量(centroid)群(codebook)中的其中一個
     
       Voronoi cell : 所有分配到該centroid的向量!

    判斷quantizer的好壞 : mean squared error



   


quantizer :

     
     




但是當K(code book size)的大小很大的時候，使用k means 是很困難的事情
事實上，光光是要存下k 個 centroids都已經是不可能的事情了
針對這個問題，product quantizers就被提出了
     


  2. product quantizers :



 

   
   
   



   

 二、searching with quantization

  1.computing distance using quantized codes
   
  Symmetric distance computation (SDC):

     
 ASymmetric distance computation (ADC):

 2.analysis of distance error







3.estimator of the squared distance

三、non exhaustice search

1.coarse quantizer locally defined product quantizer

2.indexing structure



3.search algorithm

四、evaluation of NN search

Visualizing Brand Associations from Web Community Photos

brand association:品牌聯想，指消費者看到該品牌的聯想，使用經驗，好惡感。如下圖(一)

圖一


傳統上，使用使用者的文字資訊，在這篇paper，我們試著利用網路蒐集的大規模圖片來達成這個任務。
大體來說，有兩個主要的任務
    1. 偵測並且展示視覺的品牌聯想
    2. 偵測影像中品牌的位置


















experiment: 4種類的48個品牌從五個網站蒐集:flickr photobucket pinterest deviantART twitpic，共五百萬張照片


brand equity(品牌資產) :描述一些與品牌相關的數值或者物件



一、偵測與品牌有關的關件圖像:
1. 判斷出小部分的影像範例與群集
    2. 發現群集間的相關性
    3. 投影至低維空間
  提供了一個對於大規模且不斷增長的大規模網路影像的結構化總結
 



二、偵測影像中與品牌有關的部分
以pixal表達，但是可以藉由定義最小的外包長方形來使最後結果方便呈現
揭露了在社群中使用者與產品的互動關係
 


這兩個部分是相互加強的!




資料收集:從五個網站卻不從google的原因是因為我們要避掉源自網路購物之類的資料，我們利用品牌名稱當搜尋詞，從內建的搜尋系統，不使用任何的filter搜尋，同時，我們也蒐集相關的meta-data(時間戳記、標題、使用者名稱、內文)
























大致方法:

input:一個有興趣的品牌的影像集

第一步:建立一個KNN的graph，每個影像跟他最相近的K個影像相連

第二步:發現一小群的圖形典範，並且將其餘的照片歸類的最相近的典範，作為一個群集






















第三步:利用cosegmentation來進行照片中品牌位置的判斷，同群集間的照片有可能分享類似的品牌圖像(如:包包、衣服、標籤)

















實際上我們可以反覆進行第一步至第三步，來達成加強的效果

  approch

1. feature extraction

   兩種feature被使用:HSV color SIFT、HOG 在4跟8 pixal
   每種feature利用K-mean產生300個visual word

2.image similarity

  image segmentation -> linear assigment ->計算每對的相關性，並取平均
  相關性:histogram intersection kernel on spatial pyramids













3. construct KNN graph

Wang, Jing, et al. "Scalable k-NN graph construction for visual descriptors." Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012.
 


但在partition時加入meta-data的資訊，例如:將同拍攝者的分配到同一subset，因為同拍攝者的照片可能富含相關內容。






4.examplar detection and clustering

find examplar:
Kim, Gunhee, et al. "Distributed cosegmentation via submodular optimization on anisotropic diffusion." Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011.

find clustering :
random walk
complexity : O(LN)





5.Brand localization via cosegmentation

Kim, Gunhee, and Eric P. Xing. "On multiple foreground cosegmentation." Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012.

learn foreground model of MFC -> run region assignment

 brand association maps

radial distance :跟品牌有多相關
angular distance:同群中的影像比此有多相近
lay out :讓重疊太高的分開，利用force-directed drawing的 Fruchterman and Reingold's method

 尚待解決的問題

1.由於影像處理不當所產生的冗餘或雜訊的群
2.品牌名稱的一詞多義(EX : windows)

 實驗

1.visualization of brand association map

2.Result on clustering

3.results on brand localization

4.correlation with sales data

照片量與銷量