非負矩陣分解未能收斂

Question

我試圖使用Kullback-Liebler分歧作爲相似性度量來實現非負矩陣分解。該算法描述如下：http://hebb.mit.edu/people/seung/papers/nmfconverge.pdf。下面是我的python/numpy實現，用一個示例矩陣來運行它。簡而言之，該算法應該學習矩陣W（n by r）和H（r by m），使得V（n乘m）近似爲WH。從W和H中的隨機值開始，按照Seung和Lee論文中描述的更新規則，您應該更接近W和H的近似值。

該算法已被證明單調地減少分歧度量，但這不是我的實現中發生的情況。相反，它會解決兩個分歧值之間的交替。如果你看W和H，你可以看到由此產生的因子不是特別好。

我想知道在計算W的更新時是否使用更新的或舊的H。我試過這兩種方法，並且它不會改變實現的行爲。

我已經檢查了我的實施對紙張一堆，我看不到我做錯了什麼。任何人都可以解釋一下這個問題嗎？

import numpy as np 

def update(V, W, H, r, n, m): 
    n,m = V.shape 
    WH = W.dot(H) 

    # equation (5) 
    H_coeff = np.zeros(H.shape) 
    for a in range(r): 
     for mu in range(m): 
      for i in range(n): 
       H_coeff[a, mu] += W[i, a] * V[i, mu]/WH[i, mu] 
      H_coeff[a, mu] /= sum(W)[a] 
    H = H * H_coeff 

    W_coeff = np.zeros(W.shape) 
    for i in range(n): 
     for a in range(r): 
      for mu in range(m): 
       W_coeff[i, a] += H[a, mu] * V[i, mu]/WH[i, mu] 
      W_coeff[i, a] /= sum(H.T)[a] 
    W = W * W_coeff 

    return W, H 


def factor(V, r, iterations=100): 
    n, m = V.shape 
    avg_V = sum(sum(V))/n/m 
    W = np.random.random(n*r).reshape(n,r)*avg_V 
    H = np.random.random(r*m).reshape(r,m)*avg_V 

    for i in range(iterations): 
     WH = W.dot(H) 
     divergence = sum(sum(V * np.log(V/WH) - V + WH)) # equation (3) 
     print "At iteration " + str(i) + ", the Kullback-Liebler divergence is", divergence 
     W,H = update(V, W, H, r, n, m) 

    return W, H 


V = np.arange(0.01,1.01,0.01).reshape(10,10) 

W, H = factor(V, 6) 

Answer 1

如何消除交替影響：

的定理2讀證明的最後一行，

通過逆轉的H和W，更新規則中的作用對於W可以類似地 顯示爲不增加。

因此，我們可以推測，更新H可以獨立更新W。更新後H這意味着：

H = H * H_coeff 

我們也應該更新W之前更新的中間值WH：

WH = W.dot(H) 
W = W * W_coeff 

兩個更新減少分歧。

嘗試一下：在計算W_coeff之前只需粘貼WH = W.dot(H)，交替效應就消失了。

---

簡化的代碼：

當與NumPy的陣列處理，使用他們的mean和sum方法，以及避免使用Python sum功能：

avg_V = sum(sum(V))/n/m 

可以寫成

avg_V = V.mean() 

和

divergence = sum(sum(V * np.log(V/WH) - V + WH)) # equation (3) 

可以寫成

divergence = ((V * np.log(V_over_WH)) - V + WH).sum() 

避免了Python內建sum函數，因爲

• 它比NumPy的sum方法慢，並且
• 它不是與NumPy sum方法一樣多才多藝。 （這 不允許你指定要總結軸。我們設法消除兩個調用Python的sum有一個呼叫與NumPy的sum或mean方法。）

---

消除三聯供-loop：

但在速度和可讀性較大的改進可以通過更換

H_coeff = np.zeros(H.shape) 
for a in range(r): 
    for mu in range(m): 
     for i in range(n): 
      H_coeff[a, mu] += W[i, a] * V[i, mu]/WH[i, mu] 
     H_coeff[a, mu] /= sum(W)[a] 
H = H * H_coeff 

可以了

與

V_over_WH = V/WH 
H *= (np.dot(V_over_WH.T, W)/W.sum(axis=0)).T 

---

說明：

如果你看一下H方程式5更新規則，首先注意指數是V和(W H)是相同的。所以，你可以用

V_over_WH = V/WH 

下一頁取代V/(W H)，請注意，在分子，我們正在總結在索引i，這是兩個W和V_over_WH第一指標。我們可以表達爲矩陣乘法：

np.dot(V_over_WH.T, W).T 

，分母是簡單的：

W.sum(axis=0).T 

如果我們把分子和分母

(np.dot(V_over_WH.T, W)/W.sum(axis=0)).T 

我們得到由兩個索引的矩陣剩餘的指數，阿爾法和畝，按順序。這與H的指數相同。所以我們希望按這個比例乘以H。完善。 NumPy默認情況下將數組按元素化。

因此，我們可以表示爲

H *= (np.dot(V_over_WH.T, W)/W.sum(axis=0)).T 

---

所以，H整個更新規則把他們放在一起：

import numpy as np 
np.random.seed(1) 


def update(V, W, H, WH, V_over_WH): 
    # equation (5) 
    H *= (np.dot(V_over_WH.T, W)/W.sum(axis=0)).T 

    WH = W.dot(H) 
    V_over_WH = V/WH 
    W *= np.dot(V_over_WH, H.T)/H.sum(axis=1) 

    WH = W.dot(H) 
    V_over_WH = V/WH 
    return W, H, WH, V_over_WH 


def factor(V, r, iterations=100): 
    n, m = V.shape 
    avg_V = V.mean() 
    W = np.random.random(n * r).reshape(n, r) * avg_V 
    H = np.random.random(r * m).reshape(r, m) * avg_V 
    WH = W.dot(H) 
    V_over_WH = V/WH 

    for i in range(iterations): 
     W, H, WH, V_over_WH = update(V, W, H, WH, V_over_WH) 
     # equation (3) 
     divergence = ((V * np.log(V_over_WH)) - V + WH).sum() 
     print("At iteration {i}, the Kullback-Liebler divergence is {d}".format(
      i=i, d=divergence)) 
    return W, H 

V = np.arange(0.01, 1.01, 0.01).reshape(10, 10) 
# V = np.arange(1,101).reshape(10,10).astype('float') 
W, H = factor(V, 6)