Non-negative Matrix Factorization (NMF), 비음수 행렬 분해

 

Non-negative Matrix Factorization (NMF) and its Applications

Basic Concepts

행렬 $V \in \mathbb{R}^{n \times m}$를 두 행렬 $W \in \mathbb{R}^{n \times r}$, $H \in \mathbb{R}^{r \times m}$의 곱으로 분해하는 방법이다. 이름에서 알 수 있듯이 $V$, $W$, $H$의 모든 원소들은 음수가 아니다.

\[ V \approx HW \]

 

Objective Function

Objective는 다음과 같다.

\[ \underset{W, H \ge 0}{\min} \| V - WH \|_F^2 \]

$\| \cdot \|_F$는 Frobenius norm이다. 예를 들어 $\| A - B \|_F^2 = \sum_{i, j}(A_{ij} - B_{ij})^2$ 이다.

두 행렬의 차이(error)를 구하는 measure 중 하나이다.

 

참고로, [1]에서는 2개의 cost function을 제시했는데 다음과 같다.

• $\| A - B \|_F^2 = \sum_{i, j}(A_{ij} - B_{ij})^2$
• $D(A || B) = \sum_{i, j}\left( A_{ij}\log \cfrac{A_{ij}}{B_{ij}} - A_{ij} + B_{ij} \right)$

이 글에서는 첫번째 cost function만을 예시로 한다.

Update Rule

update rule은 다음과 같다.

\[ H := H \circ \cfrac{W^T V}{W^T W H}, \quad W := W \circ \cfrac{VH^T}{WHH^T} \]

$\circ$은 element-wise product이다.

[1]에 의하면 위 update rule는 수렴함이 보장되어있다. (See Section 6. Proofs of convergence of [1])

 

Strengths and Weaknesses

장점

• 두 행렬의 곱으로 표현되므로, $W$와 $H$의 요소로 설명할 수 있다. (interpretability)
• Part-based Representations

단점

• 데이터가 비음수 조건이 필요하다. 데이터값이 음수가 있다면 NMF는 적용할 수 없다. 
• component 개수 $r$을 고르는 것은 정해져있지 않다.

 

Applications

제약조건이 non-negative이기 때문에, 데이터 자체가 음수를 갖지 않는 경우에 사용할 수 있다.

 

Image Processing

이미지 처리에서 NMF를 이용하여 주요 factor를 찾을 수 있다. 아래 그림은 [2]에서 보여준 NMF, VQ(Vector Quantization), PCA(Principal Components Analysis)로 찾은 사람 얼굴의 factor이다. 

VQ는 전체 얼굴의 basis prototype를 찾는다.

PCA는 "eigenface"라 부르는 전체 얼굴의 왜곡된 버전(distorted versions of whole faces)을 basis로 갖는다.

NMF는 이들과 전혀 다른 결과를 보여준다. 각 요소는 전제얼굴(whole face)가 아니라 부분(parts of face)를 나타낸다. 실제로 figure를 보면, 왼쪽 코, 오른쪽 코, 입, 눈썹, 눈 이렇게 사람의 얼굴 요소별로 factor(basis)를 갖는 것을 알 수 있다.

Image from [2]

그 외에도 다양한 분야에서 NMF를 이용할 수 있다.

• Data Imputation: 추천시스템의 rating matrix 역시 0~5의 값은 갖는다. 비어있는 값을 $W$와 $H$의 곱으로 채워서 예측할 수 있다.
• Text Mining: input matrix $X$가 document-term matrix일 때 , NMF로 분해한 행렬은 각각 term-feature, feature-document 행렬을 갖는다. 이를 이용하여 document clustering을 적용할 수도 있다.
• Speech denoising
• Bioinformatics

References

[1] Daniel Lee, H. Sebastian Seung, Algorithm for Non-negative Matrix Factorization, NeurIPS 2000

[2] Daniel D. Lee & H. Sebastian Seung(1999), Learning the parts of objects by non-negative matrix factorization, Nature

[3] https://en.wikipedia.org/wiki/Non-negative_matrix_factorization