Latent Semantic Analysis

Probabilistic latent semantic indexing

Summary:
在PLSA之前，有人提出了用的SVD方法來作latent semantic indexing的動作，而本篇作者用一個較有統計基礎的機率模型(aspect model)來模擬，這個模型是以likelihood來產生一個對training data的generative model。

其實aspect model也就是一個建立在兩個假設上的一種statistical mixture model。第一個假設為，觀察到的document和word是獨立的。第二個假設則為，latent z和word w的關係，和document d是沒有相關的。如此一來就可以將N個document的檔案，降維到一個含有K個latent的關係上，而K個latent(z)就可以拿來在給定條件d的情況下預測w。

而作者利用likelihood principle，希望能求出L = ∑d ∑w [n(d,w)logP(d,w)]的最大值，其中n(d,w)是term frequency，P(d,w)= ∑z P(z)P(w|z)P(d|z)。在這裡使用的方法是EM algorithm:
Step E: Hidden parameters (posterior)將被估計，也就是計算出P(z|d,w)。
Step M: 建立在已經觀測到的部分，進行parameter estimation。
如此EM的過程將持續進行，直到上方的L值收斂為止，就可建出這個模型。
而在PLSA中，作者為了避免over-fitting的問題，還加入了一個beta控制項來修改EM，這個方式稱為Tempered EM。Beta在一開始被指定為1，之後漸漸減少，利用held-out data來測試目前beta的效果，如果沒有辦法透過減少beta繼續改善的話就停止這個遞迴的過程，定為收斂。

Critiques:
雖然在本篇paper中後面對text作了一些測試效果很好，但是在其一開始的假設上，提出document和word是independent的概念，在實際運用上是否真的成立仍是一個問題。另外，在LDA那篇paper中也提到了，PLSA雖然不像unigram的方法在perplexity上會有很大的問題，但相對LDA的方法而言，其perplexity還是增加的較快。


------------------------------------------------------------



Latent dirichlet allocation

Summary:
在之前所提到的PLSI(PLSA)中把每個文件表示成一個數字的list(semantic topics的組合)，但是沒有一個用機率來表示的模型，會衍生出兩個問題:
(1) 參數的數量會因為corpus的量增加而線性增加，造成一個overfitting的問題。
(2) 無法去對不在traing data中出現過的document去assign機率。
因此，作者提出了LDA這個方法，希望能找出一個機率模型，不只能assign機給在已經看過的member of corpus，也能對其他類似的document給定一個機率。

其和PLSA不同之處在於，LDA利用了一個k維的Dirichlet random variable來取代原來在PLSA中的d(document)，而這個Dirichlet random variable還擁有finite dimensional sufficient statistics的特性，且conjugate to multinomial distribution，這對於作者後來在推導和參數估計的地方有很大的幫助。
而LDA也做到了一個降低參數維度的動作，原來的PLSA要在對k個semantic topic，V個word，N個document設定共k*V+k*M個參數；而LDA只要設定k(alpha的參數)+k*V(beta的參數)就好了。

LDA的架構是一個包含了三個level的hierarchical model，在corpus level有alpha和beta參數，只需要在產生corpus的時候sample一次。而theta則是document-level variable，需要在每個document中sample一次。最後一層則是word level，這裡面的變數則需要在每個document的每個word中都要sample一次。

而在paper後半部的實驗中也展現出了LDA在對於沒有看過的document中還是可以有很好的效果。此外，其在perplexity的表現上，由於PLSI在每個document給定對於每個z給定一個值，但當有些z沒有出現在此document中，導致到某些特定字在估計時機率很小，就會讓perplexity上升很快。但在LDA中就不會有這個問題。


Conclusion:
本周這兩篇paper大概是從開學以來aMMAI指定閱讀裡面讀起來最難的了，就算多看了一遍，其中還是有許多數學的部分不太理解，可能是之前對於機率模型的部分理解的不夠透徹。目前也只有在概念上稍為理解作者們的想法，希望在明天上完課後能夠更通透一些。

補充:
在網路上搜尋一些相關資料的時候，發現了一個有關PLSA的公式推導的網站，寫的還滿詳細的，有興趣的朋友們可以參考一下:
http://www.hongliangjie.com/2010/01/04/notes-on-probabilistic-latent-semantic-analysis-plsa/