0. 개요
Matrix Factorization은 행렬을 주요 요인으로 분해한다는 개념으로, 천문학,화학,자연어 처리, 사운드 분석, 추천 시스템 등에서 다양하게 응용되는 개념이라고 한다.
앞서 포스팅한 PCA나 군집분석과는 다르게, 이번에는 좀 더 일반화된 개념부터 접근해서 행렬 분해의 전반을 공부 해보려고 한다.
현재까지 예정되어 있는 학습 내용은 다음과 같다.
Part 1. Bregmann Divergence
Part 2.Generalized Non Negative Matrix Factorizaion with Bregamnn Divergence
Part 3. Independent Component Analysis
Part 4. Incremental PCA, Kernel PCA, Sparse PCA
Part 5. Factorization Model
1. NMF 란?
Non Negative Matrix Factorization(; 이하 NMF)는 차원 축소의 한 방법으로 pca에 비해서는 비교적 최근에 연구된 개념이다. $\def\b#1{\textbf{#1}}$
다음과 같은 행렬을 가정하자
$A \triangleq [\b{a}_1,\b{a}_2,…,\b{a}_N]$
where $\b a_1 ,\b a_2 ,… , \b a_n$ is Non-Negative
이에 대해 NMF는 다음을 만족하는 벡터들 $\b b_1 , \b b _2 , … , \b b_k$를 찾는 것을 목표로 한다.
$\b a_n \approx \overset{K}{\underset{k=1}{\sum}}c_{kn}\b b_k, \quad 1 \leq n \leq N $
$\b b_k$ is Non-Negative , $c_{nk}$ is restricted to be non-negative
즉 $A \approx BC$ 이다.
이때 벡터 $\b b_k$와 $c_{nk}$가 Non-Negative라는 조건이 없다면 Truncated Singular Value Decomposition (TSVD) 문제로 변형이 되고, $\b b_k$만 조건이 없을시에는 hard-clustering이라는 문제로 변형이 된다고 한다.
원소들이 모두 Non-Negative하다는 제약을 두는 이유는 다음과 같다.
- 다양한 실제 사례에서 행렬의 원소들이 오직 양수로만 나타남 (ex)이미지 표현, 빈도 자료 등)
- 결과물이 양수로만 구성 된다면 해석이 매우 용이해짐
- 위와 같은 제약을 둔다면 결과물이 sparse 해진다고 한다.
그러나 제약을 두는 만큼 실제 근이 아니라 근사 근을 구하게 되고, 또 행렬분해의 특징 상 그 근 마저도 유일하지는 않다고 한다. 이와 같은 특징 때문에 내가 참고한 논문에서는 NNMF(;NNM Factorization)이 아니라 NNMA(;NNM Approximation)이라는 용어를 사용했다.
2. NMF의 목적함수
NMF는 $A \approx BC$ 를 만족하는 A보다 낮은 랭크를 가지는 행렬 B를 찾는 것을 목표로 한다. 따라서 Bregman Divergence $D\phi_(A,BC)$를 최소화 하는 것이 목적이라고 일반화 할 수 있다. (Bregman Divergence란? -링크 참고)
행렬에서 정의되는 Bregman Divergence의 경우, 여기서는 분리가능한(;separable) 경우만 생각해준다. 이때 $D_\phi (X,Y) = \sum_{ij}D_\phi(x_{ij},y_{ij})$로 간략화 된다.
Bregman Divergence는 convex function을 대상으로 정의되기 떄문에 목적함수로 사용하기에 적합하지만 Asymmetric한 특징이 있기 때문에 $D_\phi(A,BC)$와 $D_\phi(BC,A)$를 모두 고려해줘야 한다. 거기에 패널티 함수 까지 넣어 주면 아래와 같은 목적함수를 정의 할 수 있다.
$\underset{B,C \geq 0 }{min} D_\phi(A,BC) +\alpha(B)+\beta(C)$
$\underset{B,C \geq 0 }{min} D_\phi(BC,A) +\alpha(B)+\beta(C)$
$\alpha:\Omega \rightarrow R ,\beta:\Omega \rightarrow R $
Penalty Function과 Convex Function을 적절히 정해줌으로써 새로운 알고리즘을 만들어 낼 수 있다. 논문에서 언급하고 있는 예시는 다음과 같다.
| Remarks | Convex Function $\phi(x)$ | Penalty $\alpha$ | Penalty $\beta$ | Divergence $D_\phi$ |
|---|---|---|---|---|
| Lee and Seung | $\frac{1}{2}x^2$ | 0 | 0 | $\mid \mid A-BC \mid \mid _F^2$ |
| Hoyer | $\frac{1}{2}x^2$ | 0 | $\lambda 1^T C 1$ | $\mid \mid A-BC \mid \mid _F^2$ |
| Paatero and Tapper | $\frac{1}{2}x^2$ | 0 | 0 | $\mid \mid W \odot (A-BC) \mid \mid _F^2$ |
| Lee and Seung | $x \ log \ x$ | 0 | 0 | KL(A,BC) |
| Guillamet et al. | $x \ log \ x$ | 0 | 0 | KL(A,WBC) |
| Feng et al. | $x \ log \ x$ | $c \mid \mid B \times 1\mid \mid^2 $ | $-c’ \mid \mid C \mid \mid_F^2$ | KL(A,BC) |
- $\mid \mid X \mid \mid _F$는 Frobenius Norm으로 Euclid Norm의 복소수 확장판이라고 한다.
- KL(A,B)는 Kullback-Leibler Divergence이다.
3. 최적화 하기
우리가 여기서 최소화를 시킬 목적함수는 다음과 같다.
$F(\b c) = D_{\phi}(B \b c , \b a)$ {$\b a$는 $\b c$와 연계되는 $A$의 열 중 하나}
최적화 문제를 편하게 만들기 위해 다음과 같은 Auxiliary Function을 정의해주자
$G(\b c , \b c’)$ 는 다음을 만족할때 $F(C)$의 Auxiliary Function이다.
- $G(\b c ,\b c) = F( \b c)$
- $G(\b c , \b c’) \geq F( \b c) \ \ \forall c’$
$G(\b c , \b c’)$를 위와 같이 정의했을 때 아래의 lemma를 얻을 수 있다
If $G(\b c , \b c’)$ is an auxiliary function for $F(\b c)$, then F is non-increasing under the update
$\begin{aligned} c^{t+1} = \underset{c}{argmin} G(\b c \b ,c^t)\end{aligned}$
pf) $F(C^{t+1}) \leq G(\b c^{t+1},\b c^t) \leq G(\b c^t ,\b c^t) = F(\b c^t)$
즉 $F(C)$를 직접 Maximizing하는 것이 아니라 $G(\b c, \b c’)$를 이용해서 간접적으로 최적화를 해줄 수 있다.
이를 그대로 만족하는 auxiliary fucntion을 다음과 같이 정의를 해주자
$G(\b c , \b c’) = \underset{ij}{\sum}\lambda_{ij}\phi(\frac{b_{ij}c_j}{\lambda_{ij}})-(\underset{i}{\sum}\phi(a_i)+\psi(a_i)((B \b c)_i -a_i))$
where $\lambda_{ij} = (b_{ij}c_j’)/(\sum_lb_{il}c_l’)$ , $\psi \equiv \nabla \phi$
이때 설정한 $G(\b c , \b c’)$는 위에서 설정한 조건을 만족한다.
편의를 위해 아래부터는 모두 $\psi \equiv \nabla \phi$의 notation을 사용하겠다.
pf)
$F(\b c) = D_{\phi}(B\b c,\b a) = \sum_i \phi((B \b c)_i)-\phi(\b a_i)-\psi(\b a_i)((B \b c)_i - \b a _i)$에 대해
-
$G(\b c , \b c) = \sum_i \phi(\sum_l b_{il}c_l)-\phi(\b a_i)-\psi(\b a_i)((B \b c)_i-\b a_i) = F(\b c)$
-
$\phi(\sum_l b_{il}c_l) \leq \sum_{j} \lambda_{ij}\phi(\frac{b_{ij}c_j}{\lambda_{ij}})$ {$\sum_j \lambda_{ij}=1$이므로 Jensen’s inequality를 활용하여 }
이를 이용하면 $G(\b c, \b c) \leq G(\b c, \b c’)$가 성립함을 알 수 있다.
이제 새로이 만들어진 목적함수를 최적화 시켜보자 $c^{t+1} = \underset{c}{argmax} \ G(\b c ,\b c^{t})$를 찾는 것이 목적이므로 $ G (\b c, \b c’)$를 c에 대해서 미분해보자
$\frac{\delta G}{\delta c_p} = \sum_i \lambda_{ip} \psi(\frac{b_{ip}c_{p}}{\lambda_{ip}})\frac{b_{ip}}{\lambda_{ip}}-\sum_i b_{ip} \psi(a_i)$
$= \sum_i b_{ip} \psi(\frac{c_p}{c_p’}(B \b c ‘)_i)-(B^T \psi(\b a))_p$
이 식을 0으로 뒀을 때 analytic하게 풀린다는 보장은 없다. 그러나 $\psi(xy)=\psi(x)\psi(y)$라는 가정하에서 다음과 같은 iterative form을 얻어 낼 수 있다.
$b_p \leftarrow b_p \cdot \psi^{-1}(\frac{[\psi(\b a^T)C^T]_p}{[\psi(\b b^T C)C^T]_p})$
$c_p \leftarrow c_p \cdot \psi^{-1}(\frac{[B^T\psi(\b a)]_p}{[B^T\psi(B^T \b c)]_p})$
여기서 $\phi $가 legendre type convex function 이라면 $\psi^{-1}$ 는 $\phi$의 conjugate function의 미분 폼으로 쉽게 구해질 수 있다고 한다.
4. 예시
거리의 측도를 KullBack - Leibler Divergence로 둘 때의 최적화 문제를 풀어보자 .
이 경우 일반화된 KL Divergence를 사용할 것이므로 다음과 같은 식을 사용한다.
$KL(B \b c , \b a) = \underset{i}{\sum}(B \b c )_i log \frac{(B \b c)_i}{a_i} - (B \b c)_i +a_i$
KL의 $\phi (x)$는 Entropy 이지만 문제를 한 단계 더 쉽게 만들기 위해 $\phi (x) = x \ log \ x - x$로 두자.
이 경우 $\psi(x) = log \ x$ 이므로 앞서 설정한 Auxiliary Function의 미분값은 다음과 같이 변형된다.
$\frac{\delta G}{\delta c_p} = \sum_i b_{ip}log(c_p (B \b c’)i/\b c_p’) - \sum_ib{ip}log \ a_i = 0$
\
$\Rightarrow (B^T 1)_p log \frac{\b c_p}{\b c_p’} = [B^T log \ \b a - B^T log \ (B \b c ‘)]_p$
$\Rightarrow c_p = c_p’ \cdot exp(\frac{[B^T log (\b a / (B \b c;))]_p}{[B^T1]_p})$
5. Futher Discussion
a. Link function 도입
$h(\cdot)$을 link function이라고 했을 때 $A \approx h(BC)$를 통해서 비선형적인 관계성도 잡아줄 수 있다고 한다. 이 경우 목적 함수는 $D_{\phi}(h(BC),A)$가 될 것이다.
Bregman Divergence를 이용한 일반화된 풀이는 $\phi(x)$가 Convex Function임에 강하게 의존하고 있으므로 합성함수 $(\phi \circ h)$가 Convex Function이고 $\nabla (\phi \circ h)$가 factorizable 하다면 위에서 서술한 방법론을 조금만 응용해서 적용할 수 있다.
b. 가장 적절한 $D_{\phi}(a,b)$ 찾기
$A = BC + N$을 구성한 다음 N을 Noise Matrix라고 가정하자.
만약 N이 exponential family라고 가정한다면 관련된 noise를 최소화 시키는 Bregman Divergence가 가장 적절할 것이다.
6. Scikit - Learn
Scikit-Learn에서는 NMF에 대한 패키지를 제공하고 있다. 아래는 그 함수에 대한 설명이다.
Parameters
- n_componenets : 목표로 하는 component 개수
- init : 알고리즘을 시작할때의 Initial Matirx - random, svd 등
- solver : 수치해석 알고리즘
- beta_loss : 거리 기준 - frobenius, kullback-leibler,itakura-saito
- l1_ratio : 패널티 파라미터, 0 이며 L2 에 가깝고, 1이면 L1에 가까움, 중간은 둘의 combination
Attributies
- Components_ : 결과물 축들 (행렬)
- n_components_ : 결과물 축 개수
- reconstruction_err_ : A와 BC의 Frobenius Divergence
여기까지 Non-Negative Matrix Factorization에 대해서 살펴보았다. NMF는 행렬 분해에서 널리 쓰이는 방법 중 하나이며 앞으로 더 공부할 행렬분해를 이해하는 것에 있어서 기본이 될 것이라고 보인다.
공식의 유도에 대해서는 얼추 이해한 듯 싶으나, 역시 실제로 구현을 해봐야 완전히 체화가 될 것 같다. 언젠가 시간이 된다면 KL Divergence를 기반으로 하여서 직접 Matrix Factorization을 하는 알고리즘을 구현해보겠다.
다음으로 포스팅할 내용은 ICA(;Independent Components Analysis)이다. PCA가 Linearly Independent한 Factor들로 분해를 하는 기술이라면 ICA는 Statistically Independent한 Factor들로 분해를 하는 방법이라고 한다.
참고 문헌
- Inderjit S. Dhillon, Suvrit Sra (2005). [Generalized Nonnegative Matrix Approximations with Bregman Divergences]
- http://en.wikipedia.org/wiki