關於LDA, pLSA, SVD, Word2Vec的一些看法

本文純屬搞笑！！

Topic Model (主題模型）這個東西如果從99年Hofmann的pLSA開始算起，得火了有近20年了。這20年里出現了很多東西，這篇文章不準備對這些東西做細緻的介紹，而是談談個人對這些模型的一些看法。首先，我先闡明觀點，就是這些東西雖然看起來很不一樣，但是在某一層面的本質上看差不太多。

因為我是做推薦系統的，我就從推薦系統這個角度去說吧。2009年參加Netflix Prize的時候，當時解決的是一個評分預測的問題。也就是每個用戶給電影打了1～5分，然後讓你去預測一個用戶對一個電影會打多少分。這個時候就遇到一個矩陣，叫做user-item矩陣。這個矩陣中大量的元素都是missing的，而不missing的哪些pair都有一個1～5分的分數。整個比賽的目的就是去預測那些missing的pair如果不missing會是多少分。

在Netflix Prize之前，這個問題都是這麼解決的，首先把missing的值都填上3分（也有其他策略，但這不是本文的重點），然後把user-item矩陣做SVD分解，選取最大的K個特徵值對應的特徵向量組成的矩陣，然後再乘起來。這個時候，那些missing的pair都變成了其他的分數，這個分數就是預估值。在Netflix Prize這個方法能work的原因是當時只有一個MovieLens數據集，那個數據集只有幾百個用戶和物品，這麼做還是OK的。但到了Netflix Prize，數據集頓時到了幾十萬維的矩陣，群眾們傻眼了，因為SVD分解是個O(n^3)的複雜度。

這個時候有個哥們忽然在Blog上發了一篇文章（他的那篇博客可能是學術論文引用最多的博客文章），說你們不用管那些missing的pair。你們就直接在不missing的pair上用梯度下降法學習user和item的latent factor的表示吧。於是有了那個著名的偽SVD演算法：

r(u, i) = <p(u), q(i)>n

於是整個Netflix Prize中湧現了一大堆帶SVD的演算法，比如RSVD，NSVD，SVD++等等。我也發明了幾個SVD演算法，因為照著這個思路太容易發散了。

但是，我一直覺得Netflix Prize其實誤導了整個推薦系統的發展。當然應該說是更早的MovieLens就誤導了，只是Netflix Prize沒有糾正過來。這個誤導就是，評分預測其實不是重要的問題，反而是一個很次要的問題。因為，當人民群眾拿著Netflix Prize的演算法準備用在自己的系統里時，頓時傻眼了，因為沒有評分數據。他們有的只是觀看數據，點擊數據，購買數據等等。這些數據有一個特點，就是user-item矩陣中所有的非missing值，都是1。而不是Netflix Prize裡面的評分。而且人們意識到，評分這件事有2個步驟：

1. 看電影
2. 評分

也就是說，如果用戶連電影都不看，他是不會去評分的。於是，預測用戶會看什麼電影，並把這些電影推薦給他，顯然比知道這個用戶會看這個電影后，預測他看完會給多少分更重要。

但預測用戶會看什麼電影時，我們遇到了一個問題，就是如何對一個非missing值都是1的矩陣進行分解。這也是2012年KDD Cup的Track 2提出的問題。

這個時候，人們忽然發現，在NLP領域，做Topic Model時，遇到的doc-word矩陣，和我們遇到的這種user-item矩陣一樣，都是非missing值都是1的矩陣（有人會說doc-word矩陣的值是tfidf，但本質上其實就是1）。而那個領域已經提出了2個演算法來解決這個問題，就是著名的pLSA和LDA。這兩個演算法的訓練複雜讀都只取決於非0元素的個數，和0元素的個數都沒有關係。於是很多人開始把這兩個演算法應用於推薦系統領域（其實之前在Netflix Prize就有人用了，但後來因為那個SVD演算法太NB，大家都紛紛搞SVD去了）。

但是在2012年KDD Cup的時候。我們想，我們為什麼不在0，1上訓練SVD的模型呢？那是因為0太多了（這裡0就是missing value）。既然0太多，我們採樣吧。比如我們每遇到一個1，就隨機採樣出N個0，然後用SVD訓練。那麼我們怎麼採樣0呢？當時有兩種候選：

1. 純隨機的選擇，也就是說如果一個用戶看過K個item，我們就從所有item中隨機選擇 NK個他沒看過的item作為負樣本。
2. 按照item的熱門度去選，也就是說如果一個用戶看過K個item，我們就從所有item中按照item的熱門度隨機選擇 NK個他沒看過的item作為負樣本。

第2種更合理。這是因為，對於missing值來說，一個人沒有看過一個電影，有兩種可能：

1. 他不知道有這個電影
2. 他知道，但不喜歡

而對於熱門的電影來說，是2個概率更高（當然這裡還存在一種可能，就是他在其他平台上看過了，但這個在整體用戶的統計意義上不高）。而我們的模型學習的就是興趣，所以越可能是原因2的item，越應該作為負樣本。這個演算法就是Negative Sampling。

到這個時候為止，對於0-1矩陣的分解，我們有了2個武器，一個是貝葉斯學派的LDA，一個是頻率學派的矩陣分解。我們知道，貝葉斯學派和頻率學派有著各種各樣的區別，如果從優化的角度去看，MCMC是貝葉斯學派的模型常用的優化方法，而梯度下降是頻率學派常用的。

故事發展到這個階段時，群眾的目光忽然轉向了。Topic Model的發展忽然轉向了「我們需要更多的Topic」。之前，大家弄個幾百個topic就非常高興了，這個時候忽然有人說，我們要幾百萬個Topic。據說是因為google有個系統能學50萬topic，非常NB。另外大家希望，topic多了就能學習出更多小的topic，表達更小眾的語義。於是群眾們開始幹了。一開始大家是拿LDA開刀的。於是乎，LDA從12年開始，經歷了SparseLDA, AliasLDA, LightLDA, WarpLDA的發展道路，到了15年底，已經能非常快的學100萬topic了，而且這個快是靠直接降低理論的時間複雜度實現的，代碼寫的更好只是起了輔助作用。

1. SparseLDA利用了如果topic很多，那麼當模型快收斂時，一個word其實只會屬於很少的topic，然後利用稀疏性來加速了演算法。但這個演算法有個致命的缺陷，就是初始化時，模型並不稀疏，因此迭代的前幾輪會非常慢。當然充滿智慧的群眾發明了一堆奇技淫巧部分解決了這個問題。
2. AliasLDA是優化了Gibbs Sampling採樣的時間複雜度，利用Alias Table讓對K個topic採樣的時間複雜度從O(K)降低到O(1)
3. LightLDA修改了採用的分布，把原來基於一個word doc在topic上聯合分布的採樣過程，改成了2個交替進行的獨立採樣過程，一個只依賴word，另一個只依賴doc。
4. WarpLDA做了更多的工程級別的優化，讓LightLDA更快。

但後來，LDA一直沒有大規模的火起來。這是因為不幸的又遇到了深度學習這股風，google在2013年提出了word2vec。word2vec本身不是一個很深的模型，他其實就是一個一層的模型。但這個模型的nb之處在於，他是頻率學派的，支持梯度法優化，因此這一層可以插入到DL的網路中作為一層，和其他層一起做end-to-end的優化，LDA就沒法這麼搞。這樣，大量的有監督的問題，用上word2vec後，效果頓時就超過LDA了。

word2vec剛出來時，我發現他在優化時用了霍夫曼編碼來實現了層次化的SoftMax(HS)。當時我覺得他這麼做有2個目的：

1. 減少運算複雜度，如果是普通的SoftMax，其實就相當於在0-1矩陣的所有值上做矩陣分解，沒有能利用到矩陣的稀疏性。
2. 傾向於選擇熱門的item做負樣本，因為霍夫曼編碼是按照熱門度對item編碼的，越熱門的item離根節點越近。

所以，HS真是太巧妙了。果然不出所料，2014年的時候，有群眾提出，那我們直接用Negative Sampling吧。這樣程序寫起來簡單。大家一試，發現效果還不錯，並不比HS差，而且代碼確實很容易寫。

故事發展到這個階段時，我們總覺得少了點啥。這個word2vec忽然跳出來就搶了LDA的飯碗，那麼LDA最後搞的那些把topic提升到100萬個的工作，貌似word2vec還沒搞啊？我去google了一下，發現群眾的智慧是無限的，果不其然，有人發現這個遺留問題了。Facebook的研究人員在一個標題為Whats next, word2vec的演講中明確提出，稀疏表達是word2vec下一個要解決的問題。其實稀疏表達的前提就是topic要多。只有多了，才有可能學習出非常小的topic。

好吧，後面就讓我們拭目以待吧。

讀後思考：為什麼Netflix Prize的評分問題可以只在不missing的value上訓練，而不用管missing value？

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

歡迎關注 [ ResysChina ] 微信公眾號。

推薦閱讀：