NMF의 기본 이론과 이해

NMF (Non-netgative Matrix Factorization)

: 음수를 포함하지 않는 행렬 $X$를 음수를 포함하지 않는 행렬 $W$와 $H$의 곱으로 분해하는 알고리즘이다.

$$X = WH$$

 

$$X\in \mathbb{R}^{m \times n} \\ where \ m: Num \ of \ data samples, \ n: Dimension \ of \ data \ samples$$

만약 $p$개의 feature를 가지고 원래의 $data \ set \ X$를 분해한다면

$$W\in \mathbb{R}^{m \times p}, \ H \in \mathbb{R}^{p \times n}$$

NMF는 다른 분해법과는 달리 분해 후 non-netgativity 특성을 보존할 수 있고, PCA 및 SVD에 비해 각 feature들의 독립성을 잘 습득 할 수 있다. (PCA, SVD는 직교성이 보장되는 대신 feature vector들이 서로 직교하게 된다면 dataset의 실제 구조를 잘 반영하기 힘들다.)

 

사전 지식

(1) trace (대각합 연산)

$$A = \begin{pmatrix} a_{11} \ a_{12} \ a_{13}\\ a_{21} \ a_{22} \ a_{23}\\ a_{31} \ a_{32} \ a_{33} \end{pmatrix} \Rightarrow tr(A) = a_{11}+a_{22}+a_{33}$$

 

$$tr(A+B) = tr(A) + tr(B) \\ tr(ABC) = tr(CAB) = tr(BCA) = \cdots = tr(CBA)$$

 

$$\triangledown x\ tr(AX)  = A^T \\ \triangledown x\ tr(X^{T}A) = A \\  \triangledown x\ tr(X^{T}AX) = (A+A^{T})X \\ \triangledown x\ tr(XAX^{T})= X(A^{T}+A)$$

 

(2) Frobenius norm

$$A = \begin{pmatrix} a \ b \\ c \  d \end{pmatrix}  \rightarrow \| A\|_{F}= \sqrt{a^2 + b^2+c^2+d^2}$$

$$A^TA =\begin{pmatrix} a \ c \\ b \  d \end{pmatrix}  \begin{pmatrix} a \ b \\ c \  d \end{pmatrix}  = \begin{pmatrix} a^2+c^2 \ ab+cd \\ ab+cd \  b^2+d^2 \end{pmatrix}$$

$$\rightarrow \|A\|_{F} = \sqrt{tr(A^TA)}$$

$$\therefore \|A\|_{F} = \sqrt{\sum^m_{i=1} \sum^n_{j=1}\|a_{ij}\|^2} = \sqrt{tr(A^TA)}$$

 

(3) Element-wise product

$$A = \begin{pmatrix} 1 \ 2 \\ 3 \ 4 \\ \end{pmatrix}, B = \begin{pmatrix} a \ b \\ c \ d \\ \end{pmatrix} \\ \\ A \circ B =  \begin{pmatrix} 1a \ 2b \\ 3c \ 4d \\ \end{pmatrix}$$

 

NMF의 update 규칙

$$H:= H\circ \frac{W^TX}{W^TWH} \\ W:= W\circ \frac{XH^T}{WHH^T}$$

 

유도과정

: X를 분해해서 얻은 W, H는 최대한 X에 가까워야 한다.

 

$\|X-WH\|^2_{F} = tr((X-WH)^T(X-WH)) \cdots Frobenius \ norm$

 

$\rightarrow H := H - \eta H\circ \triangledown_{H}\|X-WH\|^2_{F} \\  \ \ \ \ \ W := W - \eta W\circ \triangledown_{W}\|X-WH\|^2_{F} \ \cdots gradient \ descent \ \ \ (a)$

 

interative한 방식으로 분해를 진행한다.

 

Frobenius norm으로 표현한 수식을 아래와 같이 전개한다.

$\|X-WH\|^2_{F} = tr((X-WH)^T(X-WH)) \\ = tr((X^T - H^TW^T)(X - WH)) \\ = tr(X^TX - X^TWH-H^TW^TX+H^TW^TWH)$

 

이를 통해  $\triangledown_{H}\|X-WH\|^2_{F}, \  \triangledown_{W}\|X-WH\|^2_{F}$ 를 아래와 같이 전개한다.

$\triangledown_{H}\|X-WH\|^2_{F} = \triangledown H\{ tr(X^TX) \ -tr(X^TWH) \ -tr(H^TW^TX) + tr(H^TW^TWH) \} \\ = 0 \ -(X^TW)^T -W^TX + (W^TW+(W^TW)^T)H \\ = -2W^TX+2W^TWH \cdots (b)$

 

$\triangledown_{W}\|X-WH\|^2_{F} = \cdots \\ = -2XH^T +2WHH^T \cdots (c)$

 

$(a)$에 $(b), \ (c)$를 대입한다. (상수곱은 무시)

$H := H + \eta H\circ (W^TX - W^TWH) \\ W := W + \eta W\circ (XH^T - WHH^T)$

 

이 과정에서 뒤 term에 음수가 포함되므로 특별한 방식의 gradient descent를 수행한다.

$\rightarrow$ learning rate인 $\eta$를 data-driven하게 정의한다.

$$\eta_{H} =\frac{H}{W^TWH}, \ \eta_{W} = \frac{W}{WHH^T} \\ \rightarrow H := H + \frac{H}{W^TWH} \circ (W^TX - W^TWH) \\ = H + H \circ \frac{W^TX}{W^TWH} - H \circ \frac{W^TWH}{W^TWH}$$

$\frac{W^TWH}{W^TWH} = I , \ H \circ \frac{W^TWH}{W^TWH}=H$이므로

$$\rightarrow H+ H \circ\frac{W^TX}{W^TWH}- H = H \circ \frac{W^TX}{W^TWH} \\ \therefore H := H \circ \frac{W^TH}{W^TWH} \\ \therefore W := W \circ \frac{XH^T}{WHH^T}$$

Reference

https://angeloyeo.github.io/2020/10/15/NMF.html

https://nbviewer.org/github/fastai/numerical-linear-algebra/blob/master/nbs/2.%20Topic%20Modeling%20with%20NMF%20and%20SVD.ipynb#Non-negative-Matrix-Factorization-(NMF)