lda演算法實現

㈠ LDA的公式推導

根據符號說明可得類i的樣本均值為：
同理我們也可以得到總體樣本均值：

根據類間離散度矩陣和類內離散度矩陣定義，可以得到如下式子：


當然還有另一中類間的離散度矩陣表達方式：

其中是指i類樣本的先驗概率，即樣本中屬於i類的概率，把P(i)代入第二組式子中，我們可以發現第一組式子只是比第二組式子都少乘了1/m，我們將在稍後進行討論，其實對於乘不乘該1/m，對於演算法本身並沒有影響，我們分析一下演算法的思想，
我們可以知道矩陣的實際意義是一個協方差矩陣，這個矩陣所刻畫的是該類與樣本總體之間的關系，其中該矩陣對角線上的函數所代表的是該類相對樣本總體的方差（即分散度），而非對角線上的元素所代表是該類樣本總體均值的協方差（即該類和總體樣本的相關聯度或稱冗餘度），所以根據公式（3）可知（3）式即把所有樣本中各個樣本根據自己所屬的類計算出樣本與總體的協方差矩陣的總和，這從宏觀上描述了所有類和總體之間的離散冗餘程度。同理可以的得出（4）式中為分類內各個樣本和所屬類之間的協方差矩陣之和，它所刻畫的是從總體來看類內各個樣本與類之間（這里所刻畫的類特性是由是類內各個樣本的平均值矩陣構成）離散度，其實從中可以看出不管是類內的樣本期望矩陣還是總體樣本期望矩陣，它們都只是充當一個媒介作用，不管是類內還是類間離散度矩陣都是從宏觀上刻畫出類與類之間的樣本的離散度和類內樣本和樣本之間的離散度。
LDA做為一個分類的演算法，我們當然希望它所分的類之間耦合度低，類內的聚合度高，即類內離散度矩陣的中的數值要小，而類間離散度矩陣中的數值要大，這樣的分類的效果才好。
這里我們引入Fisher鑒別准則表達式：

㈡ NLP系列（三）LDA主題模型

LDA模型是NLP中很基礎也是大家廣為熟知的模型，在面試過程也經常遇到。本文簡單講述下其大致流程。

首先，我們來感受下LDA是什麼，

看來，不同人在不同場景下對LDA的認識，那我們看下網路的解釋：

看到這里我們只需要先記住： LDA的目的就是要識別主題，即把文檔—詞彙矩陣變成文檔—主題矩陣（分布）和主題—詞彙矩陣（分布）

對於語料庫中的每篇文檔，LDA定義了如下生成過程（generativeprocess）：
1.對每一篇文檔，從主題分布中抽取一個主題；
2.從上述被抽到的主題所對應的單詞分布中抽取一個單詞；
3.重復上述過程直至遍歷文檔中的每一個單詞。

語料庫中的每一篇文檔與T（通過反復試驗等方法事先給定）個主題的一個多項分布 （multinomialdistribution）相對應，將該多項分布記為θ。每個主題又與詞彙表（vocabulary）中的V個單詞的一個多項分布相對應，將這個多項分布記為φ。

LDA的核心公式如下：
p(w|d)=p(w|t)*p(t|d)
直觀的看這個公式，就是以Topic作為中間層，可以通過當前的θd和φt給出了文檔d中出現單詞w的概率。其中p(t|d)利用θd計算得到，p(w|t)利用φt計算得到。
實際上，利用當前的θd和φt，我們可以為一個文檔中的一個單詞計算它對應任意一個Topic時的p(w|d)，然後根據這些結果來更新這個詞應該對應的topic。然後，如果這個更新改變了這個單詞所對應的Topic，就會反過來影響θd和φt。

LDA演算法開始時，先隨機地給θd和φt賦值（對所有的d和t）。然後上述過程不斷重復，最終收斂到的結果就是LDA的輸出。再詳細說一下這個迭代的學習過程：
1.針對一個特定的文檔ds中的第i單詞wi，如果令該單詞對應的topic為tj，可以把上述公式改寫為：
pj(wi|ds)=p(wi|tj)*p(tj|ds)
2.現在我們可以枚舉T中的topic，得到所有的pj(wi|ds)，其中j取值1~k。然後可以根據這些概率值結果為ds中的第i個單詞wi選擇一個topic。最簡單的想法是取令pj(wi|ds)最大的tj（注意，這個式子里只有j是變數），即argmax[j]pj(wi|ds)
3.然後，如果ds中的第i個單詞wi在這里選擇了一個與原先不同的topic，就會對θd和φt有影響了（根據前面提到過的這兩個向量的計算公式可以很容易知道）。它們的影響又會反過來影響對上面提到的p(w|d)的計算。對D中所有的d中的所有w進行一次p(w|d)的計算並重新選擇topic看作一次迭代。這樣進行n次循環迭代之後，就會收斂到LDA所需要的結果了。

N個文檔組成的語料庫（𝐷 1，𝐷 2，"……" ，𝐷 𝑛），由V個片語成的詞彙表。矩陣中的值表示了詞𝑊𝑗 〖在文檔𝐷〗 𝑖 中出現的頻率，主題用Z表示，下面對語料庫中的每一個word隨機指派一個主題編號𝑍 𝑖，統計每個𝑍_𝑖下出現的word次數，可得一個主題—詞彙矩陣。

統計每個詞代表的主題在每一個文檔中出現的次數，可得出以下矩陣文檔—主題矩陣

以上講了大致LDA的感性認識，如果進行嚴格的數學推導請看這篇文章( https://www.jianshu.com/p/74ec7d5f6821 )，本人認為是看到的不錯的文章。

LDA對自己一直是一個謎，看了網上的很多資料，然後整理了幾篇不錯的，我在這里貼出來。本篇文章主要大致了解了下LDA的大致流程，如果真正搞懂其背後數學原理，還得反復看一下下面的文章：

LDA（LDA文檔主題生成模型）_網路

㈢ 無監督第五節：LDA (Latent Dirichlet Allocation演算法細節)（主題模型）

LDA是生成式概率模型。基本的觀點是一個文檔由多個隱主題生成，每個主題是由單詞的分布式表達。

LDA假設在語料庫D中每個文檔的生成過程如下：

1.主題數量k已知

2.單詞的概率由參數 控制

參數 是一個k 維的向量，並且每個元素大於0， 服從Gamma 分布

已知參數 ， 聯合分布主題混合的參數 , 表示主題的參數 z,表示文檔的參數w:

對 積分，並對z求和得到關於文檔的邊緣分布：

所有文檔的邊緣分布相乘，得到整個語料庫的概率：

參數 和參數 是語料庫級別的參數，在生成語料庫的過程中使用。

變數 是文檔級別的參數，每個文檔采樣一次。

變數 和 是單詞級別的參數，每個文檔中每個單詞都采樣一次.

一組隨機變數如果聯合分布和變數的排列順序無關，則稱這組變數是可交換的。

在LDA中，我們假設單詞是由主題生成的，並且這些主題在文檔中是無限可交換的，

其中 是關於主題多項式分布的隨機變數。

通過對隱主題變數z積分。可以得到單詞分布：

這是一個隨機量，因為他依賴於

我們定義接下來的生成過程， 對於一個文檔 w

1.選擇θ∼Dir(α)

2.對於每個N的單詞 :

(a)從 中選擇一個單詞

這個過程定義一篇文檔的邊緣分布看成一個連續的混合分布

inference的關心的問題使用LDA來計算隱變數z的後驗分布：

這個分布通常很難計算。通過normaliza 分布，並且計算邊緣分布。

這個後驗分布很難計算，但是通過一些變分推斷的方法還是可以得到。

基本的觀點是使用jensen's 不等式來獲得一個調整的下界，變分參數通過優化過程來試圖找到最接近的可能的下界。

一個簡單的方式是通過鮮花原始的計算圖，將一些邊和節點移去。在LDA中，原始的圖是左圖，通過把 移去，生成右邊含有自由變分參數的圖。
新的計算圖使用如下變分分布：

是狄利克雷參數，多項式參數(φ1 , . . . , φ N ) 是自由變數參數。

得到簡化的概率分布後，下一步是開始的優化問題是決定變分參數 的值。

優化這個變分參數是通過最小化KL散度來實現，並且吧他們設為0，得到以下的更新參數。

在文本的語言中，優化參數 是文檔制定的。特別的，我們認為狄利克雷參數 是一個文檔的主題表達。

經驗貝葉斯方法來估計LDA中的參數。給定一個語料D，我們希望找到參數 來最大化邊緣似然概率：

計算 比較困難，可以通過變分EM演算法來估計。

1.E step,對於每個文檔，找到最優的變分參數 。

2.M step, 最大化結果的下界。

重復上述幾步直到下界收斂。

㈣ 降維演算法二：LDA（Linear Discriminant Analysis）

學習分類演算法，線性分類器最簡單的就是LDA，它可以看做是簡化版的SVM，如果想理解SVM這種分類器，那理解LDA就是很有必要的了。

談到LDA，就不得不談談PCA，PCA是一個和LDA非常相關的演算法，從推導、求解、到演算法最終的結果，都有著相當的相似。

本次的內容主要是以推導數學公式為主，都是從演算法的物理意義出發，然後一步一步最終推導到最終的式子，LDA和PCA最終的表現都是解一個矩陣特徵值的問題，但是理解了如何推導，才能更深刻的理解其中的含義。本次內容要求讀者有一些基本的線性代數基礎，比如說特徵值、特徵向量的概念，空間投影，點乘等的一些基本知識等。除此之外的其他公式、我都盡量講得更簡單清楚。

LDA的全稱是Linear Discriminant Analysis（線性判別分析），是一種 supervised learning 。有些資料上也稱為是Fisher』s Linear Discriminant，因為它被Ronald Fisher發明自1936年，Discriminant這次詞我個人的理解是，一個模型，不需要去通過概率的方法來訓練、預測數據，比如說各種貝葉斯方法，就需要獲取數據的先驗、後驗概率等等。LDA是在 目前機器學習、數據挖掘領域經典且熱門的一個演算法 ，據我所知，網路的商務搜索部裡面就用了不少這方面的演算法。

LDA的原理是，將帶上標簽的數據（點），通過投影的方法，投影到維度更低的空間中，使得投影後的點，會形成按類別區分，一簇一簇的情況，相同類別的點，將會在投影後的空間中更接近。要說明白LDA，首先得弄明白線性分類器( Linear Classifier )：因為LDA是一種線性分類器。對於K-分類的一個分類問題，會有K個線性函數：

上式實際上就是一種投影，是將一個高維的點投影到一條高維的直線上，LDA最求的目標是，給出一個標注了類別的數據集，投影到了一條直線之後，能夠使得點盡量的按類別區分開，當k=2即二分類問題的時候，如下圖所示：

紅色的方形的點為0類的原始點、藍色的方形點為1類的原始點，經過原點的那條線就是投影的直線，從圖上可以清楚的看到，紅色的點和藍色的點被原點明顯的分開了，這個數據只是隨便畫的，如果在高維的情況下，看起來會更好一點。下面我來推導一下二分類LDA問題的公式：
假設用來區分二分類的直線（投影函數)為：

LDA分類的一個目標是使得不同類別之間的距離越遠越好，同一類別之中的距離越近越好，所以我們需要定義幾個關鍵的值。
類別i的原始中心點為：（Di表示屬於類別i的點)

類別i投影後的中心點為：

衡量類別i投影後，類別點之間的分散程度（方差）為：

最終我們可以得到一個下面的公式，表示LDA投影到w後的損失函數：

分類的目標是， 使得類別內的點距離越近越好（集中），類別間的點越遠越好。 分母表示每一個類別內的方差之和，方差越大表示一個類別內的點越分散，分子為兩個類別各自的中心點的距離的平方，我們最大化J(w)就可以求出最優的w了。想要求出最優的w，可以使用拉格朗日乘子法，但是現在我們得到的J(w)裡面，w是不能被單獨提出來的，我們就得想辦法將w單獨提出來。
我們定義一個投影前的各類別分散程度的矩陣，這個矩陣看起來有一點麻煩，其實意思是，如果某一個分類的輸入點集Di裡面的點距離這個分類的中心店mi越近，則Si裡面元素的值就越小，如果分類的點都緊緊地圍繞著mi，則Si裡面的元素值越更接近0.

同樣的將J(w)分子化為：

我們希望 分母越小越好，分子越大越好 ：
分母小，則每個類內部數據點比較聚集；
分子大，則兩個類別的距離較遠。
所以需要找出一個 W 使 J(W) 的值最大。

這樣就可以用最喜歡的拉格朗日乘子法了，但是還有一個問題，如果分子、分母是都可以取任意值的，那就會使得有無窮解，我們將分母限制為長度為1（這是用拉格朗日乘子法一個很重要的技巧，在下面將說的PCA裡面也會用到，如果忘記了，請復習一下高數），並作為拉格朗日乘子法的限制條件，帶入得到：

這樣的式子就是一個求特徵值的問題了。
對於N(N>2)分類的問題，我就直接寫出下面的結論了：

二者都有降維的作用。