em演算法收斂
㈠ kmeans 質心為什麼會收斂
直接證明Kmeans收斂其實是無本之木
嚴格說，kmeans過程收斂是因為 他的數據劃分判斷依據 歐式距離 與 均值算質心 這兩步搭配
恰好是EM演算法的特例，EM演算法的收斂性非常復雜，解釋不清楚。
㈡ 對於EM快速保養的敘述是什麼
EM演算法是一種迭代優化策略，由於它的計算方法中每一次迭代都分兩步，其中一個為期望步（E步），另一個為極大步（M步），所以演算法被稱為EM演算法（Expectation-Maximization Algorithm）。EM演算法受到缺失思想影響，最初是為了解決數據缺失情況下的參數估計問題，其演算法基礎和收斂有效性等問題在Dempster、Laird和Rubin三人於1977年所做的文章《Maximum likelihood from incomplete data via the EM algorithm》中給出了詳細的闡述。其基本思想是：首先根據己經給出的觀測數據，估計出模型參數的值；然後再依據上一步估計出的參數值估計缺失數據的值，再根據估計出的缺失數據加上之前己經觀測到的數據重新再對參數值進行估計，然後反復迭代，直至最後收斂，迭代結束。
㈢ em演算法是什麼
最大期望演算法（Expectation-Maximization algorithm, EM），或Dempster-Laird-Rubin演算法，是一類通過迭代進行極大似然估計（Maximum Likelihood Estimation, MLE）的優化演算法 ，通常作為牛頓迭代法（Newton-Raphson method）的替代用於對包含隱變數（latent variable）或缺失數據（incomplete-data）的概率模型進行參數估計。
EM演算法的標准計算框架由E步（Expectation-step）和M步（Maximization step）交替組成，演算法的收斂性可以確保迭代至少逼近局部極大值 。EM演算法是MM演算法（Minorize-Maximization algorithm）的特例之一，有多個改進版本，包括使用了貝葉斯推斷的EM演算法、EM梯度演算法、廣義EM演算法等 。
由於迭代規則容易實現並可以靈活考慮隱變數，EM演算法被廣泛應用於處理數據的缺測值 ，以及很多機器學習（machine learning）演算法，包括高斯混合模型（Gaussian Mixture Model, GMM） 和隱馬爾可夫模型（Hidden Markov Model, HMM） 的參數估計。
㈣ em演算法的EM演算法簡述
迭代使用EM步驟，直至收斂。
可以有一些比較形象的比喻說法把這個演算法講清楚。比如說食堂的大師傅炒了一份菜，要等分成兩份給兩個人吃，顯然沒有必要拿來天平一點一點的精確的去稱分量，最簡單的辦法是先隨意的把菜分到兩個碗中，然後觀察是否一樣多，把比較多的那一份取出一點放到另一個碗中，這個過程一直迭代地執行下去，直到大家看不出兩個碗所容納的菜有什麼分量上的不同為止。EM演算法就是這樣，假設我們估計知道A和B兩個參數，在開始狀態下二者都是未知的，並且知道了A的信息就可以得到B的信息，反過來知道了B也就得到了A。可以考慮首先賦予A某種初值，以此得到B的估計值，然後從B的當前值出發，重新估計A的取值，這個過程一直持續到收斂為止。
EM 演算法是 Dempster，Laind，Rubin 於 1977 年提出的求參數極大似然估計的一種方法，它可以從非完整數據集中對參數進行 MLE 估計，是一種非常簡單實用的學習演算法。這種方法可以廣泛地應用於處理缺損數據，截尾數據，帶有雜訊等所謂的不完全數據(incomplete data)。
假定集合Z = (X,Y)由觀測數據 X 和未觀測數據Y 組成，X 和Z = (X,Y)分別稱為不完整數據和完整數據。假設Z的聯合概率密度被參數化地定義為P(X,Y|Θ)，其中Θ表示要被估計的參數。Θ的最大似然估計是求不完整數據的對數似然函數L(X;Θ)的最大值而得到的：
L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ；
EM演算法包括兩個步驟：由E步和M步組成，它是通過迭代地最大化完整數據的對數似然函數Lc(X;Θ)的期望來最大化不完整數據的對數似然函數，其中：
Lc(X;Θ) =log p(X,Y |Θ) ；
假設在演算法第t次迭代後Θ獲得的估計記為Θ(t) ，則在(t+1)次迭代時，
E-步：計算完整數據的對數似然函數的期望，記為：
Q(Θ|Θ (t)) = E{Lc(Θ;Z)|X;Θ(t)}；
M-步：通過最大化Q(Θ|Θ(t) ) 來獲得新的Θ 。
通過交替使用這兩個步驟，EM演算法逐步改進模型的參數，使參數和訓練樣本的似然概率逐漸增大，最後終止於一個極大點。直觀地理解EM演算法，它也可被看作為一個逐次逼近演算法：事先並不知道模型的參數，可以隨機的選擇一套參數或者事先粗略地給定某個初始參數λ0 ，確定出對應於這組參數的最可能的狀態，計算每個訓練樣本的可能結果的概率，在當前的狀態下再由樣本對參數修正，重新估計參數λ，並在新的參數下重新確定模型的狀態，這樣，通過多次的迭代，循環直至某個收斂條件滿足為止，就可以使得模型的參數逐漸逼近真實參數。
EM演算法的主要目的是提供一個簡單的迭代演算法計算後驗密度函數，它的最大優點是簡單和穩定，但容易陷入局部最優。
㈤ em演算法的EM演算法
在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計或者最大後驗估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。
最大期望演算法經過兩個步驟交替進行計算：
第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；
第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。
M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
總體來說，EM的演算法流程如下：
1.初始化分布參數
2.重復直到收斂：
E步驟：估計未知參數的期望值，給出當前的參數估計。
M步驟：重新估計分布參數，以使得數據的似然性最大，給出未知變數的期望估計。
㈥ em演算法原理
我最近也在看EM演算法，主要是它在無監督學習中的應用，例子倒是沒有，原理差不多弄明白了一些，其實是出於一種很自然的想法，似然度均值的最大化，但是中間有些問題就是在迭代的過程中似然度是單調增加的，這個證明過程比較繁瑣，具體你在模式識別中的應用可以參考這個WiKi頁：http://en.wikipedia.org/wiki/Expectation-maximization_algorithm
㈦ 怎麼通俗易懂地解釋EM演算法並且舉個例子
在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計或者最大後驗估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。
最大期望演算法經過兩個步驟交替進行計算：
第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；
第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。
M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
總體來說，EM的演算法流程如下：
初始化分布參數
2.重復直到收斂：
E步驟：估計未知參數的期望值，給出當前的參數估計。
M步驟：重新估計分布參數，以使得數據的似然性最大，給出未知變數的期望估計。
㈧ 統計機器翻譯的模型
雜訊信道模型假定，源語言中的句子f（信宿）是由目標語言中的句子e（信源）經過含有雜訊的信道編碼後得到的。那麼，如果已知了信宿f和信道的性質，我們可以得到信源產生信宿的概率，即p(e | f)。而尋找最佳的翻譯結果也就等同於尋找：
利用貝耶斯公式，並考慮對給定f，p(f)為常量，上式即等同於
由此，我們得到了兩部分概率：
p(f | e)，指給定信源，觀察到信號的概率。在此稱為翻譯模型。 p(e)，信源發生的概率。在此稱為語言模型 可以這樣理解翻譯模型與語言模型，翻譯模型是一種語言到另一種語言的詞彙間的對應關系，而語言模型則體現了某種語言本身的性質。翻譯模型保證翻譯的意義，而語言模型保證翻譯的流暢。從中國對翻譯的傳統要求「信達雅」三點上看，翻譯模型體現了信與達，而雅則在語言模型中得到反映。
原則上任何語言模型均可以應用到上述公式中，因此以下討論集中於翻譯模型。在IBM提出的模型中，翻譯概率被定義為：
p(f | e) = p(f,a | e)其中的a被定義為隱含變數——詞對齊（Word Alignment），所謂詞對齊，簡而言之就是知道源語言句子中某個詞是由目標語言中哪個詞翻譯而來的。例如右圖中，一個詞可以被翻譯為一個或多個詞，甚至不被翻譯。於是，獲取翻譯概率的問題轉化為詞對齊問題。IBM系列模型及HMM, Model 6都是詞對齊的參數化模型。它們之間的區別在於模型參數的數量，類型各不相同。例如IBM Model 1，唯一的參數是詞翻譯概率，與詞在句子中的位置無關。也就是說：
其中(i,j)是詞對齊中的一條連接，表示源語言中的第i個詞翻譯到目標語言中的第j個詞。注意這里的翻譯概率是詞之間而非位置之間的。IBM Model 2的參數中增加了詞在句子中的位置，公式為：
其中I,J分別為源、目標語言的句子長度。
HMM模型將IBM Model 2中的絕對位置更改為相對位置，即相對上一個詞連接的位置，而IBM Model 3,4,5及Model 6引入了「Fertility Model」，代表一個詞翻譯為若干詞的概率。
在參數估計方面，一般採用最大似然准則進行無監督訓練，對於大量的「平行語料」，亦即一些互為翻譯的句子(fs,es)
由於並沒有直接的符號化最優解，實踐中採用EM演算法。首先，通過現有模型，對每對句子估計(fs,es)全部可能的（或部分最可能的）詞對齊的概率，統計所有參數值發生的加權頻次，最後進行歸一化。對於IBM Model 1,2，由於不需要Fertility Model，有簡化公式可獲得全部可能詞對齊的統計量，而對於其他模型，遍歷所有詞對齊是NP難的。因此，只能採取折衷的辦法。首先，定義Viterbi對齊為當前模型參數θ下，概率最大的詞對齊：
在獲取了Viterbi對齊後，可以只統計該對齊結果的相關統計量，亦可以根據該對齊，做少許修改後（即尋找「臨近」的對齊）後再計算統計量。IBM 3,4,5及Model 6都是採用這種方法。
目前直接採用雜訊信道模型進行完整機器翻譯的系統並不多見，然而其副產品——詞對齊卻成為了各種統計機器翻譯系統的基石。時至今日，大部分系統仍然首先使用GIZA++對大量的平行語料進行詞對齊。由於所面對的平行語料越來越多，對速度的關注使得MGIZA++，PGIZA++等並行化實現得到應用。雜訊信道模型和詞對齊仍然是研究的熱點，雖然對於印歐語系諸語言，GIZA++的對齊錯誤率已經很低，在阿拉伯語，中文等語言與印歐語系語言的對齊中錯誤率仍然很高。特別是中文，錯誤率常常達到30%以上。所謂九層之台，起於累土，缺乏精確的詞對齊是中文機器翻譯遠遠落後於其他語言的原因。雖然目前出現了一些區分性詞對齊技術，無監督對齊仍然是其中的重要組成部分。 在這個框架下，M個特徵函數
通過參數化公式
其中是每個特徵函數的權重，也是模型所要估計的參數集，記為Λ。基於這個模型，獲取給定源語言句子f，最佳翻譯的決策准則為：
簡而言之，就是找到使得特徵函數最大的解。
原則上，任何特徵函數都可以被置於此框架下，雜訊信道模型中的翻譯模型、語言模型都可以作為特徵函數。並且，在產生式模型中無法使用的「反向翻譯模型」，即p(f,e)也可以很容易的被引入這個框架中。目前基於短語的翻譯系統中，最常用的特徵函數包括：
1.短語翻譯概率 2.詞翻譯概率（短語中每個詞的翻譯概率） 3.反向短語翻譯概率 4.反向詞翻譯概率 5.語言模型 而一些基於句法的特徵也在被加入。 優化准則指的是給定訓練語料，如何估計模型參數Λ。一般來說，訓練模型參數需要一系列已翻譯的文本，每個源語言句子fs擁有Rs個參考翻譯。
早期，區分性訓練被置於最大熵准則下，即：
這一準則簡單快速且由於優化目標是凸的，收斂速度快。然而，一個極大的問題是，「信息熵」本身和翻譯質量並無聯系，優化信息熵以期獲得較好的翻譯結果在邏輯上較難說明。藉助客觀評價准則如BLEU，希望直接針對這些客觀准則進行優化能夠提升翻譯性能。由此而產生最小化錯誤率訓練演算法。通過優化系統參數，使得翻譯系統在客觀評價准則上的得分越來越高，同時，不斷改進客觀評價准則，使得客觀評價准則與主觀評價准則越來越接近是目前統計機器翻譯的兩條主線。
使用這些客觀評價准則作為優化目標，即：
的一個主要問題是，無法保證收斂性。並且由於無法得到誤差函數（即客觀評價准則）的導數，限制了可使用的優化方法。目前常用的方法多為改進的Powell法，一般來說訓練時間頗長且無法針對大量數據進行訓練。 語料預處理階段，需要搜集或下載平行語料，所謂平行語料，指的是語料中每一行的兩個句子互為翻譯。目前網路上有大量可供下載的平行語料。搜尋適合目標領域（如醫療、新聞等）的語料是提高特定領域統計機器翻譯系統性能的重要方法。
在獲取語料後，需要進行一定得文本規范化處理，例如對英語進行詞素切分，例如將's獨立為一個詞，將與詞相連的符號隔離開等。而對中文則需要進行分詞。同是，盡可能過濾一些包含錯誤編碼的句子，過長的句子或長度不匹配（相差過大）的句子。
獲取的語料可分為三部分，第一部分用於詞對齊及短語抽取，第二部分用於最小錯誤率訓練，第三部分則用於系統評價。第二第三部分的數據中，每個源語言句子最好能有多條參考翻譯。 首先，使用GIZA++對平行語料進行對齊。由於GIZA++是「單向」的詞對齊，故而對齊應當進行兩次，一次從源到目標，第二次從目標到源。一般來說，GIZA++需要依次進行IBM Model 1, HMM及IBM Model 3,4的對齊，因IBM Model 2對齊效果不佳，而IBM Model 5耗時過長且對性能沒有較大貢獻。根據平行語料的大小不同及所設置的迭代次數多少，訓練時間可能很長。一個參考數據為，1千萬句中文-英文平行語料（約3億詞）在Inter Xeon 2.4GHz伺服器上運行時間約為6天。如果耗時過長可考慮使用MGIZA++和PGIZA++進行並行對齊（PGIZA++支持分布式對齊）。
其後，對兩個方向的GIZA++對齊結果進行合並，供短語抽取之用。 最小化錯誤率訓練通過在所准備的第二部分數據——優化集（Tuning Set）上優化特徵權重Λ，使得給定的優化准則最優化。一般常見的優化准則包括信息熵，BLEU，TER等。這一階段需要使用解碼器對優化集進行多次解碼，每次解碼產生N個得分最高的結果，並調整特徵權重。當權重被調整時，N個結果的排序也會發生變化，而得分最高者，即解碼結果，將被用於計算BLEU得分或TER。當得到一組新的權重，使得整個優化集的得分得到改進後，將重新進行下一輪解碼。如此往復直至不能觀察到新的改進。
根據選取的N值的不同，優化集的大小，模型大小及解碼器速度，訓練時間可能需要數小時或數日。 使用經最小化錯誤率訓練得到的權重，即可進行解碼。一般此時即可在測試集上進行系統性能評價。在客觀評價基礎上，有一些有條件的機構還常常進行主觀評價。