為 NMF 導出乘法更新規則
如何推導 Lee 和 Seung 給出的非負矩陣分解問題的乘法更新規則。
最小化關於和, 受約束
他們已經證明，在乘法更新規則下歐幾里得距離不會增加，但我無法弄清楚乘法更新規則是如何得出的。乘法更新規則如下：
有關該論文的更多信息，請單擊此處。請通俗地解釋，不要省略任何必要的步驟。
$$ \min_{W \in \mathbb{R}^{n \times k},H \in \mathbb{R}^{k \times m}} \left | V- WH \right |^{2}_F \text{ s.t. }W,H \geq 0 $$
$$ ;;;;;;Tr((V-WH)^T(V-WH)) ;;;;;; \scriptsize \left [ \left |X \right |^2 = Tr(X^TX) \right ] $$
$$ Tr((V^T - H^TW^T)(V-WH) ) = Tr( V^TV - V^TWH - H^TW^TV + H^TW^WWH) $$
使用 $ Tr(A+B) = Tr(A) + Tr(B) $ 我們得到，
$$ Tr( V^TV) - Tr(V^TWH) - Tr(H^TW^TV) + Tr(H^TW^TWH) ;;;;;; (1) $$
非負矩陣分解問題在 W 和 H 中是非凸的，但僅在 W 或僅 H 中是凸的。為了優化上述問題，我們使用塊坐標下降方案，我們針對以下方面進行優化 $ W $ 首先同時保持 $ H $ 固定，然後反之亦然。 $$ W \leftarrow W - \eta_W \cdot \nabla_W f(W,H) $$ $$ H \leftarrow H - \eta_H \cdot \nabla_H f(W,H) $$
因此，為了解決給定的問題，我們需要方程的導數。1關於 $ W $ 和 $ H $ . 由於方程中的項是跡形式的，因此使用一些線性代數規則更容易獲得導數。
每一項關於 W 的導數，
$ \nabla_WTr(V^TV) = 0 $
$ \nabla_WTr(V^TWH) = \nabla_WTr(HV^TW) = (HV^T)^T = VH^T ;;;;;;;;;; \scriptsize \left [ \nabla_X Tr(AX) = A^T \right ] $
$ \nabla_WTr(H^TW^TV) =\nabla_WTr(VH^TW^T) = VH^T ;;;;;;;;;;;;;;;;;;;;, \scriptsize \left [ \nabla_X Tr(X^TA) = A \right ] $
$ \nabla_W Tr(H^TW^TWH) = \nabla_W Tr(WHH^TW^T)= W((HH^T)^T + HH^T) = 2WHH^T ;;; \scriptsize \left [ \nabla_X Tr(XAX^T) = X(A+A^T) \right ] $
可以類似地計算關於 H 的導數。因此，
$$ \nabla_W f(W,H) = -2VH^T + 2WHH^T $$ $$ \nabla_H f(W,H) = -2W^TV + 2W^TWH $$
使用上述導數， $$ W \leftarrow W + \eta_W \cdot (VH^T - WHH^T) $$ $$ H \leftarrow H + \eta_H \cdot (W^TV - W^TWH) $$
常數 $ 2 $ 可以調整學習率，因此現在可以忽略。傳統上在梯度下降中，學習率是正的，但由於更新規則中的項相減會導致負元素，Lee 和 Seung 在上述論文中提出使用自適應學習率來避免減法，從而產生負元素。學習率的定義方式是在更新規則中沒有減法。因此，如果我們設置 $ \eta_W = \frac{W}{WHH^T} $ 和 $ \eta_H = \frac{H}{W^TWH} $ ，我們得出給定的更新規則。
避免減法並獲得乘法更新規則的另一種方法是使用以下形式，
$$ \theta \leftarrow \theta \cdot \frac {\nabla_{\theta}^{-} f(\theta)}{\nabla_{\theta}^{+} f(\theta)} $$
在哪裡 $ \nabla_{\theta}^{-} f(\theta) $ 和 $ \nabla_{\theta}^{+} f(\theta) $ 分別是梯度的負項和正項 $ \nabla_{\theta} f(\theta) $ .
使用上述公式和前面產生的導數，我們得到以下更新規則，
$$ W \leftarrow W \cdot \frac{(VH^T)}{(WHH^T)} $$ $$ H \leftarrow H \cdot \frac{(W^TV)}{(W^TWH)} $$
Lee 和 Seung 在上述論文中提供了這些規則的收斂證明。