EM算法的計算複雜度是多少？

Question

一般來說，更具體的伯努利混合模型（又稱潛類分析）。

Answer 1

由於EM算法本質上是迭代的，所以您必須決定終止標準。如果您修復了步數的上限，運行時分析顯然很容易。對於其他終止標準（如收斂到恆定差異），必須對情況進行具體分析。長話短說，「EM」的描述不包括終止標準，所以這個問題不能這樣回答。

Answer 2

EM與K-means的勞埃德變體幾乎相同。所以每次迭代需要O(n*k)距離計算。它們是更復雜的距離計算，但最終它們是馬哈拉諾比斯距離的一些變體。

但是，k-means具有相當不錯的終止行爲。只有k^n個可能的羣集分配。現在，如果在每一步中，您選擇一個更好的，它將不得不嘗試所有k^n後終止最新。但實際上，它通常會在最多幾十步後終止。

對於EM，這並不容易。對象沒有被分配到一個單一的聚類，但如在模糊C均值相對於所有聚類分配。那就是當你失去這個終止保證。

因此，如果沒有任何停止閾值，EM將無限優化集羣分配，達到無限精度（假設您將以無限精度實現它）。

因此，EM的理論運行時間爲：無限。

任何閾值（如果它只是硬件浮點精度）將使它更早完成。但是這裏很難獲得理論上的極限，這裏的值不同於O(n*k*i)，其中i是迭代次數（可能是無限的，但如果您不想進行單次迭代，也可以將其設置爲0）。

Answer 3

這就是我的想法： 如果我們假設的EM algorithm使用linear algebra，這確實如此，那麼它的複雜性應該是O（MN^3），其中m是 迭代次數，n是參數數量。

迭代次數將受到起始值質量的影響。良好的起始值意味着小米。

由於收斂到本地解決方案，不太好的起始值意味着更大的m甚至失敗。局部解決方案可以存在，因爲EM用於可能性函數nonlinear。

良好的起始值意味着您從圍繞全局最優解的軌跡的凸起吸引區開始。