em演算法介紹

A. em演算法怎麼做聚類

1.一般概念介紹

最大期望演算法（Expectation-maximization algorithm，又譯期望最大化演算法）在統計中被用於尋找，依賴於不可觀察的隱性變數的概率模型中，參數的最大似然估計。

在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計或者最大後驗估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。

B. 如何自學人工智慧

數學知識
我想在大多數學校里，數學都是理工科學生的必修課，微積分、線性代數、概率論與數理統計，這些都比較基礎實用，我覺得這個數學基礎對入門人工智慧足夠了，人工智慧應用數學最多的也就是求導、矩陣的運算和分解、概率的統計與分析。
編程能力
工欲善其事、必先利其器，人工智慧方向編程語言使用最多的應該就是Python了，在很多學校理工科學生應該都會必修一門編程課，有的是C，有的是C++，就算這些都沒用過，也應該對Matlab了解一些，我覺得有一些編程基礎入門Python算是比較簡單的，網上資源很多，社區支持也很強大。
機器學習
我這里所說的機器學習是廣義上的機器學習，涵蓋深度學習。無論是做傳統的機器學習回歸和分類，還是做深度學習，無論是做計算機視覺，還是做自然語言處理，都離不開機器學習，後面我會介紹一些我認為比較好的學習資源，對於機器學習，我劃分為兩個方面：(1) 框架層面；(2) 理論層面。

C. 淚求與EM演算法類似的SAGE演算法的簡介！感激不盡！~

縱馬飛迎。程遠

D. em演算法的介紹

最大期望演算法（Expectation Maximization Algorithm，又譯期望最大化演算法），是一種迭代演算法，用於含有隱變數（latent variable）的概率參數模型的最大似然估計或極大後驗概率估計。

E. 利用lda.collapsed.gibbs.sampler怎樣去預測新的樣本文檔

一.主題模型

傳統判斷兩個文檔相似性的方法是通過查看兩個文檔共同出現的單詞的多少，如TF-IDF等，這種方法沒有考慮到文字背後的語義關聯，可能在兩個文檔共同出現的單詞很少甚至沒有，但兩個文檔是相似的。
舉個例子，有兩個句子分別如下：
「喬布斯離我們而去了。」
「蘋果價格會不會降？」
可以看到上面這兩個句子沒有共同出現的單詞，但這兩個句子是相似的，如果按傳統的方法判斷這兩個句子肯定不相似，所以在判斷文檔相關性的時候需要考慮到文檔的語義，而語義挖掘的利器是主題模型，LDA就是其中一種比較有效的模型。
在主題模型中，主題表示一個概念、一個方面，表現為一系列相關的單詞，是這些單詞的條件概率。形象來說，主題就是一個桶，裡面裝了出現概率較高的單詞，這些單詞與這個主題有很強的相關性。
怎樣才能生成主題？對文章的主題應該怎麼分析？這是主題模型要解決的問題。
首先，可以用生成模型來看文檔和主題這兩件事。所謂生成模型，就是說，我們認為一篇文章的每個詞都是通過「以一定概率選擇了某個主題，並從這個主題中以一定概率選擇某個詞語」這樣一個過程得到的。那麼，如果我們要生成一篇文檔，它裡面的每個詞語出現的概率為：

這個概率公式可以用矩陣表示：

其中」文檔-詞語」矩陣表示每個文檔中每個單詞的詞頻，即出現的概率；」主題-詞語」矩陣表示每個主題中每個單詞的出現概率；」文檔-主題」矩陣表示每個文檔中每個主題出現的概率。
給定一系列文檔，通過對文檔進行分詞，計算各個文檔中每個單詞的詞頻就可以得到左邊這邊」文檔-詞語」矩陣。主題模型就是通過左邊這個矩陣進行訓練，學習出右邊兩個矩陣。
主題模型有早起使用SVD的LSA(隱形語義分析)，然後引入基於概率的pLSA（ProbabilisticLatent Semantic Analysis），其參數學習採用EM演算法和後來改進PLSA，引入hyperparameter的LDA（Latent Dirichlet Allocation），其參數學習主要採用EM和Gibbs sampling，下面主要介紹LDA。
二.LDA

LDA要乾的事情簡單來說就是為一堆文檔進行聚類（所以是非監督學習），一種topic就是一類，要聚成的topic數目是事先指定的。聚類的結果是一個概率，而不是布爾型的100%屬於某個類。國外有個博客上有一個清晰的例子，直接引用：
Suppose you have the following set of sentences:
I like to eat broccoli and bananas.
I ate a banana and spinach smoothie for breakfast.
Chinchillas and kittens are cute.
My sister adopted a kitten yesterday.
Look at this cute hamster munching on a piece of broccoli.
What is latent Dirichlet allocation? It』s a way of automatically discovering topics that these sentences contain. For example, given these sentences and asked for 2 topics, LDA might proce something like
Sentences 1 and 2: 100% Topic A
Sentences 3 and 4: 100% Topic B
Sentence 5: 60% Topic A, 40% Topic B
Topic A: 30% broccoli, 15% bananas, 10% breakfast, 10% munching, … (at which point, you could interpret topic A to be about food)
Topic B: 20% chinchillas, 20% kittens, 20% cute, 15% hamster, … (at which point, you could interpret topic B to be about cute animals)
上面關於sentence 5的結果，可以看出來是一個明顯的概率類型的聚類結果（sentence 1和2正好都是100%的確定性結果）。
再看例子里的結果，除了為每句話得出了一個概率的聚類結果，而且對每個Topic，都有代表性的詞以及一個比例。以Topic A為例，就是說所有對應到Topic A的詞裡面，有30%的詞是broccoli。在LDA演算法中，會把每一個文檔中的每一個詞對應到一個Topic，所以能算出上面這個比例。這些詞為描述這個Topic起了一個很好的指導意義，我想這就是LDA區別於傳統文本聚類的優勢吧。
LDA整體流程
先定義一些字母的含義：
文檔集合D，topic集合T
D中每個文檔d看作一個單詞序列< w1,w2,...,wn >，wi表示第i個單詞，設d有n個單詞。（LDA裡面稱之為word bag，實際上每個單詞的出現位置對LDA演算法無影響）
D中涉及的所有不同單片語成一個大集合VOCABULARY（簡稱VOC）
LDA以文檔集合D作為輸入（會有切詞，去停用詞，取詞乾等常見的預處理，略去不表），希望訓練出的兩個結果向量（設聚成k個Topic，VOC中共包含m個詞）：
對每個D中的文檔d，對應到不同topic的概率θd < pt1,..., ptk >，其中，pti表示d對應T中第i個topic的概率。計算方法是直觀的，pti=nti/n，其中nti表示d中對應第i個topic的詞的數目，n是d中所有詞的總數。
對每個T中的topic t，生成不同單詞的概率φt < pw1,..., pwm >，其中，pwi表示t生成VOC中第i個單詞的概率。計算方法同樣很直觀，pwi=Nwi/N，其中Nwi表示對應到topic t的VOC中第i個單詞的數目，N表示所有對應到topic t的單詞總數。
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的輸出。用數學語言描述就是如下過程

轉化成概率圖模型表示就是

圖中K為主題個數，M為文檔總數，是第m個文檔的單詞總數。 是每個Topic下詞的多項分布的Dirichlet先驗參數， 是每個文檔下Topic的多項分布的Dirichlet先驗參數。是第m個文檔中第n個詞的主題，是m個文檔中的第n個詞。剩下來的兩個隱含變數和分別表示第m個文檔下的Topic分布和第k個Topic下詞的分布，前者是k維(k為Topic總數)向量，後者是v維向量（v為詞典中term總數）。

三.用Gibbs Sampling學習LDA

Gibbs Sampling的流程：LDA中的變數，和都是未知的隱含變數，也是我們需要根據觀察到的文檔集合中的詞來學習估計的，那麼如何來學習估計呢？這就是概率圖模型的Inference問題。主要的演算法分為exact inference和approximate inference兩類。盡管LDA是最簡單的Topic Model， 但是其用exact inference還是很困難的，一般我們採用approximate inference演算法來學習LDA中的隱含變數。比如LDA原始論文Blei02中使用的mean-field variational expectation maximisation 演算法和Griffiths02中使用的Gibbs Sampling，其中Gibbs Sampling 更為簡單易懂。
Gibbs Sampling 是Markov-Chain Monte Carlo演算法的一個特例。這個演算法的運行方式是每次選取概率向量的一個維度，給定其他維度的變數值Sample當前維度的值。不斷迭代，直到收斂輸出待估計的參數。可以圖示如下

初始時隨機給文本中的每個單詞分配主題,然後統計每個主題z下出現term t的數量以及每個文檔m下出現主題z中的詞的數量，每一輪計算，即排除當前詞的主題分配，根據其他所有詞的主題分配估計當前詞分配各個主題的概率。當得到當前詞屬於所有主題z的概率分布後，根據這個概率分布為該詞sample一個新的主題。然後用同樣的方法不斷更新下一個詞的主題，直到發現每個文檔下Topic分布和每個Topic下詞的分布收斂，演算法停止，輸出待估計的參數和，最終每個單詞的主題也同時得出。

用Gibbs Sampling 學習LDA參數的演算法偽代碼如下

四.LDA開源工具GibbsLDA++
GibbsLDA++說明文檔寫的很清晰易懂，這里只說下輸出模型。
<model_name>.others：LDA模型的一些參數。α、βLDA的先驗參數、ntopics主題數、liter采樣迭代次數
<model_name>.phi：This file contains the word-topic distributions, i.e., p(wordw|topict). Each line is a topic, each column is a word in the vocabulary
<model_name>.theta：This file contains the topic-document distributions, i.e., p(topict|documentm). Each line is a document and each column is a topic.
<model_name>.tassign：This file contains the topic assignments for words in training data. Each line is a document that consists of a list of <wordij>:<topic of wordij>
<model_name>.twords：This file contains twords most likely words of each topic.

case study示例：
學習：src/lda -est -alpha 0.5 -beta 0.1 -ntopics 100 -niters 1000 -savestep 100 -twords 20 -dfile models/casestudy/ trndocs.dat
預測：src/lda -inf -dir models/casestudy/ -model model-01800 -niters 30 -twords 20 -dfile newdocs.dat

F. 自然語言處理的相關技術

數據稀疏與平滑技術
大規模數據統計方法與有限的訓練語料之間必然產生數據稀疏問題，導致零概率問題，符合經典的zip'f定律。如IBM, Brown：366M英語語料訓練trigram，在測試語料中，有14.7%的trigram和2.2%的bigram在訓練語料中未出現。
數據稀疏問題定義：「The problem of data sparseness, alsoknown as the zero-frequency problem ariseswhen analyses contain configurations thatnever occurred in the training corpus. Then it isnot possible to estimate probabilities from observedfrequencies, and some other estimation schemethat can generalize (that configurations) from thetraining data has to be used. —— Dagan」。
人們為理論模型實用化而進行了眾多嘗試與努力，誕生了一系列經典的平滑技術，它們的基本思想是「降低已出現n-gram條件概率分布，以使未出現的n-gram條件概率分布非零」，且經數據平滑後一定保證概率和為1，詳細如下： Add-one（Laplace） Smoothing 加一平滑法，又稱拉普拉斯定律，其保證每個n-gram在訓練語料中至少出現1次，以bigram為例，公式如圖：

其中，V是所有bigram的個數。 Good-Turing Smoothing 其基本思想是利用頻率的類別信息對頻率進行平滑。調整出現頻率為c的n-gram頻率為c*：

直接的改進策略就是「對出現次數超過某個閾值的gram，不進行平滑，閾值一般取8~10」，其他方法請參見「Simple Good-Turing」。 InterpolationSmoothing 不管是Add-one，還是Good Turing平滑技術，對於未出現的n-gram都一視同仁，難免存在不合理（事件發生概率存在差別），所以這里再介紹一種線性插值平滑技術，其基本思想是將高階模型和低階模型作線性組合，利用低元n-gram模型對高元n-gram模型進行線性插值。因為在沒有足夠的數據對高元n-gram模型進行概率估計時，低元n-gram模型通常可以提供有用的信息。公式如下如右圖1：

擴展方式（上下文相關）為如右圖2：
λs可以通過EM演算法來估計，具體步驟如下： 首先，確定三種數據：Training data、Held-out data和Test data； 然後，根據Training data構造初始的語言模型，並確定初始的λs（如均為1）； 最後，基於EM演算法迭代地優化λs，使得Held-out data概率（如下式）最大化。

G. 機器學習需要什麼數學基礎

• 數學基礎

  歡迎補充。

  文中提供的PDF下載鏈接，均來自於網路，如有問題，請站內告知。

• 《矩陣分析》 PDFRoger Horn。矩陣分析領域無爭議的經典

• 《概率論及其應用》 PDF威廉·費勒。極牛的書，可數學味道太重，不適合做機器學習的

• 《All Of Statistics》 PDF 掃描版PDF 高清版機器學習這個方向，統計學也一樣非常重要。推薦All of statistics，這是CMU的一本很簡潔的教科書，注重概念，簡化計算，簡化與Machine Learning無關的概念和統計內容，可以說是很好的快速入門材料。

• 《Nonlinear Programming, 2nd》 PDF最優化方法，非線性規劃的參考書。

• 《Convex Optimization》 PDF配套代碼Boyd的經典書籍，被引用次數超過14000次，面向實際應用，並且有配套代碼，是一本不可多得的好書。

• 《Numerical Optimization》 PDF第二版，Nocedal著，非常適合非數值專業的學生和工程師參考，演算法流程清晰詳細，原理清楚。

• 《Introction to Mathematical Statistics》 PDF第六版，Hogg著，本書介紹了概率統計的基本概念以及各種分布，以及ML，Bayesian方法等內容。

• 《An Introction to Probabilistic Graphical Models》 PDFJordan著，本書介紹了條件獨立、分解、混合、條件混合等圖模型中的基本概念，對隱變數（潛在變數）也做了詳細介紹，相信大家在隱馬爾科夫鏈和用Gaussian混合模型來實現EM演算法時遇到過這個概念。

• 《Probabilistic Graphical Models-Principles and Techniques》 PDFKoller著，一本很厚很全面的書，理論性很強，可以作為參考書使用。

• 具體數學 PDF經典

• bind一月 4

• 線性代數 (Linear Algebra)：我想國內的大學生都會學過這門課程，但是，未必每一位老師都能貫徹它的精要。這門學科對於Learning是必備的基礎，對它的透徹掌握是必不可少的。我在科大一年級的時候就學習了這門課，後來到了香港後，又重新把線性代數讀了一遍，所讀的是

  Introction to Linear Algebra (3rd Ed.) by Gilbert Strang.

  這本書是MIT的線性代數課使用的教材，也是被很多其它大學選用的經典教材。它的難度適中，講解清晰，重要的是對許多核心的概念討論得比較透徹。我個人覺得，學習線性代數，最重要的不是去熟練矩陣運算和解方程的方法——這些在實際工作中MATLAB可以代勞，關鍵的是要深入理解幾個基礎而又重要的概念：子空間(Subspace)，正交(Orthogonality)，特徵值和特徵向量(Eigenvalues and eigenvectors)，和線性變換(Linear transform)。從我的角度看來，一本線代教科書的質量，就在於它能否給這些根本概念以足夠的重視，能否把它們的聯系講清楚。Strang的這本書在這方面是做得很好的。

  而且，這本書有個得天獨厚的優勢。書的作者長期在MIT講授線性代數課(18.06)，課程的video在MIT的Open courseware網站上有提供。有時間的朋友可以一邊看著名師授課的錄像，一邊對照課本學習或者復習。

  Linear Algebra

• 概率和統計 (Probability and Statistics):概率論和統計的入門教科書很多，我目前也沒有特別的推薦。我在這里想介紹的是一本關於多元統計的基礎教科書：

  Applied Multivariate Statistical Analysis (5th Ed.) by Richard A. Johnson and Dean W. Wichern

  這本書是我在剛接觸向量統計的時候用於學習的，我在香港時做研究的基礎就是從此打下了。實驗室的一些同學也借用這本書學習向量統計。這本書沒有特別追求數學上的深度，而是以通俗易懂的方式講述主要的基本概念，讀起來很舒服，內容也很實用。對於Linear regression, factor analysis, principal component analysis (PCA), and canonical component analysis (CCA)這些Learning中的基本方法也展開了初步的論述。

  之後就可以進一步深入學習貝葉斯統計和Graphical models。一本理想的書是

  Introction to Graphical Models (draft version). by M. Jordan and C. Bishop.

  我不知道這本書是不是已經出版了（不要和Learning in Graphical Models混淆，那是個論文集，不適合初學）。這本書從基本的貝葉斯統計模型出發一直深入到復雜的統計網路的估計和推斷，深入淺出，statistical learning的許多重要方面都在此書有清楚論述和詳細講解。MIT內部可以access，至於外面，好像也是有電子版的。