행렬분해를 더 넓은 관점에서, 텐서로 확장한다.
- 음이 아닌 행렬 : $U \geq 0$, $V \geq 0$ 일때, $\min ||A-UV||_F^2$ 이다.
- 희소하고 음이 아닌 행렬 : $U \geq 0$, $V \geq 0 $ 일때, $\min ||A-UV||_F^2 + \lambda ||UV||_N$ 이다.
- $CP$ 텐서 분해 : $\min ||T - \sum_{i=1}^R a_i \circ b_i \circ c_i ||$
위 분해를 행렬에 적용하고, 텐서 $T$ 에도 적용한다. 행렬은 2방향 텐서이다.
음이 아닌 행렬 분해 NMF
NMF 의 목표는 음이아닌 두행렬 $U, V \geq 0$ 의 낮은 랭크 곱샘 $UV$ 로 음이 아닌 행렬 $A \geq 0 $ 을 근사하는 것이다.
낮은 랭크의 목적은 단순성에 있고, 비음수성의 ( 음이아닌 행렬 ) 목적은 유의미한 수를 만드는 것에 있다.
그러나 비음수성은 어려울 수 있다. 대칭인 양의 정부호행렬 $A \geq 0$ 에, 행렬 $B \geq 0$ 이 $B^TB = A$ 를 만족해야한다.
이러한 $B$ 는 거의 존재하지 않아서, $B \geq 0 $ 인 $B^TB$ 가 $A$ 에 근사하도록 해야한다.
희소성과 비음수성은 중요한 특징이다. 희소 벡터, 행렬의 적은 0 이아닌 수는 의미를 갖고, 수 본질적으로 음이아닌 경우가 있다.
그런데 SVD에서 특이벡터는 부호가 혼합되있는 직교벡터인데, 실제 문제에서는 $U$, $V$ 의 직교성을 포기할 필요가 있다.
위와 같은 새로운 목표에 새로운 행렬 분해법이 필요하다.
NMF : $A \approx UV$ 를 만족하는 음이 아닌 행렬 $U$, $V$ 를 찾아라.
SPCA : $A \approx BC$ 를 만족하는 희소한 낮은 랭크 행렬 $B$, $C$ 를 찾아라.
먼저 분해의 의미와 목적은 $A = BC$ 에서, $A$ 의 각 열은 $B$ 의 열의 조합으로 계수는 $C$ 의 열에 존재한다.
즉 $A$ 의 각 열 $a_j \approx c_{1j}b_1 + \cdots + c_{nj}b_n$ 이다.
여기서 $C$ 가 $A$ 보다 적은 수의 열을 가지면, 선형 차원 축소이다. 압축, 특징추출, 시각화의 기초가 된다.
얼굴 특징 추출
데이터 행렬 $A$ 의 각 열벡터가 얼굴 하나를 나타난다고 가정한다. 각 성분은 픽셀 강도이고 $A \geq 0$ 이다.
이제 $B$ 에서 기본얼굴(기본 열)을 찾아 그 조합으로 $A$ 에서 많은 얼굴을 근사하도록 해보자.
기본 얼굴의 집합을 찾는 방법으로 위의 행렬분해법 $A \approx BC$ 가 유용하게 사용된다.
텍스트 마이닝과 문서 분류
$A$ 의 각 열이 문서를 나타내고, 각 행은 한단어를 나타낸다. 즉 열벡터는 단어의 연속으로 나타난다. $A$ 의 문서를 분류하기 위해서 희소한 음이 아닌 분해를 찾는다.
문서 $a_j \approx \sum c_{ij} b_i$, 여기서 $c_{ij}$ 는 중요도를, $b_i$ 는 주제를 의미한다. 즉 한 문서는 여러개의 주제의 결합으로 이루어진다. NMF 는 주제를 식별, 해당 주제에 관한 전체 문서 집합을 분류한다. ( 최신 의미 분석 latest semantic analysis, 색인 )
NMF 는 SVD 와 달리 NP-Hard 문제이다. 정확한 해 $A= BC$ 조차 유일하지 않고, $B$ 의 열의 개수도 알 수 없다.
음이 아닌 행렬 $U$, $V$ 에 대한 최적 조건
$A \geq 0 $ 에 대해, $U \geq 0$, $V \geq 0$ 이 $||A-UV||_F^2$ 를 최소화하기 위한 최적 조건이 있다.
- 모든 $i,j$ 에 대해서 $Y_{i,j} \mathrm{or} U_{i,j} = 0$ 일때, $Y = UVV^T - AV^T \geq 0$ 이다.
- 모든 $i,j$ 에 대해서 $Z_{i,j} \mathrm{or} V_{i,j} = 0$ 일때, $Z = U^TUV - U^TA \geq 0$ 이다.
위 조건은 $U$,$V$ 가 희소 행렬로 나타날 수 있음을 시사한다. (왜?)
분해를 계산하는 기본 방법
$U$, $V$, $B$, $C$ 를 계산하는 알고리즘이 많이 제안되었고, 알고리즘의 핵심아이디어는 한 인자를 고정하고 다른 인자를 최적화하는 교대 분해법 이다.
프로베니우스 노름을 이용해, 각 단계는 최소제곱의 한 형태로 최적화한다. 일반적으로 좋은 결과를 얻을 수 있지만, 최선의 분해로 수렴하는 지는 확실하지 않다. 그래서 최적화 이론으로 더 발전된 결과를 얻길 기대한다. 교대방향승수 방법 ADMM 에서 수렴을 촉진하도록 페널티 항과 쌍대성을 사용한다.
희소한 주성분
많은 분야에서 양수와 음수를 모두 허용한다. 대신 0 이 가지는 의미는 조금 떨어진다. 0 을 기준점으로 삼고 그 기준점을 어떻게 잡느냐에 따라 달라지기 때문이다.
0 이 아닌 성분의 개수는 대체로 중요하다. SVD 의 특이벡터들 $u$, $v$ 에는 0 이아닌 수로 가득 차 있어서 이들 모두가 의사결정에 영향을 미치고, 의미를 가지기 때문에 통제하기 힘들다. 따라서 0 이아닌 변수의 개수를 통제하는 것이 중요하다.
그 방법으로 $b$ 와 $v$ 의 매우 작은 구성요소를 제거하는 것이지만, 직접 알고리즘을 통해 희소벡터를 구성하는 것도 좋은 방법이다. Sparse PCA 는 희소벡터를 만드는 알고리즘으로 $l_1$ 노름과 Nuclear 노름으로 희소성을 만든다.
$||x||_1$ 또는 $||X||_N$ 에 대한 페널티는 희소벡터 $x$ 와 희소행렬 $X$ 를 생성한다.
즉 희소벡터를 만들기위해 중요한 변수를 선택해야하고, 그 키는 $l^1$ 최적화이다. 이는 LASSO 의 핵심이다.
LASSO : $||Ax-b||^2 + \lambda \sum_1^n |x_k|$ 를 최소화한다.
이 최소값을 효율적으로 찾는 방법이 비선형 최적화이다. ADMM 과 브레이크만 알고리즘을 이후에 다룬다.
이 LASSO 에 대해서 최적 벡터 $x^*$ 의 0 이 아닌 성분의 개수는 표본의 0 이 아닌 수보다 적게 가지고 있을 것이다. 여기에 $l^2$ 페널티를 추가하면 이런 결점 없이 엘라스팃 넷 elastic net 이 생긴다. 이 $l^1$ + 리지회귀는 최소 제곱만큼 빨리 해결할 수 있다.
엘라스틱 넷 : $||Ax-b||^1 + \lambda ||x||_1 + \beta ||x||_2^2$ 을 최소화 한다.
ADMM 알고리즘은 $l^2$ 에서 $l^1$ 을 분할하는 알고리즘이다. 그리고 라그랑주 승수와 쌍대성을 이용한 페널티를 추가해 강력한 조합을 만들어 낸다.
텐서 Tensor
열벡터는 1 방향 텐서, 행렬은 2 방향 텐서이다. 3방향 텐서 $T$ 는 행 번호, 열 번호, 관(tube) 번호를 포함하는 $T_{ijk}$ 성분이 있다.
3개의 수평, 측면, 정면 슬라이스를 가질 수 있다.
$ w = Av $ 의 도함수 $\frac{\partial w}{\partial A}$
딥러닝에서 가중치행렬 $A$ 에 벡터 $v$ 를 곱해서 $w$ 를 생성하고, 이를 통해 $A$ 를 최적화한다. 여기서 $A$ 는 $m$ x $n$, $w$ 는 $n$ 의 차원을 가진다. 여기서 $w_i$ 가 변화할때, $A_{jk}$ 의 변화량은 하나의 값으로, 총 3가지의 지표인 $i$, $j$, $k$ 로 텐서가 표현된다. 크로네커 델타 $\delta_{ij}$ 는 $i=j$ 일 때 1, $i \neq j$ 일 때 0 이다.
$T_{ijk} = \frac{\partial w_i}{\partial A_{jk}} = v_k \delta_{ij}$
텐서 $T_{ijk} = v_k \delta_{ij}$ 에 대해 슬라이스 $k$ 는 단위행렬의 $v_k$ 배 이고, 신경망에서 가중치를 최적화하기 위해서 사용된다. $Av +b$ 인 선형단계의 미분은 3방향 텐서 $v_k \delta_{ij}$ 이다.
텐서의 랭크와 노름
벡터는 1방향, 행렬은 2방향 텐서이고, 일반적으로 텐서를 d 방향 배열이라고 부른다. 성분의 위치를 알기위해 d 개의 위치정보가 필요하다. d=3 텐서는 (3계수 텐서) 가장 흔하고 이해하기 쉽다. T 의 노름은 행렬의 프로베니우스 노름과 같다. $||T||^2 = \sum T_{ijk}^2$ 이다.
텐서에 벡터, 행렬, 텐서를 곱해 선형 연산자로 사용할 수 있다. 치환, 반사, 직교 행렬처럼 텐서도 이런 변환을 수행할 수 있다.
그런데 행렬과는 다르게 텐서는 좀 더 복잡하다. 곱은 수행할 수 있지만 분해는 쉽지 않다. 그래서 선형대수학의 중심 연구는 행렬 분해를 가능한 많이 포착하는 것을 목표로 하고 있다.
텐서의 랭크의 정의와 계산도 행렬 만큼 단순하거나 쉽지않다. 근데 랭크 1 인 텐서는 여전히 가장 단순하고 가장 명료하다. 이 텐서는 3개의 벡터 $a,b,c$ 에 의해서 생성된다.
3 방향 텐서 $T$ 는 랭크가 1 인 $a \circ b \circ c \circ$ 이다. $T_{ijk} = a_i b_j c_k$
텐서의 랭크는 $T$ 에 추가한 랭크 1 텐서의 최소 개수이다.
앞서 행렬에서 봤듯이, SVD 를 통해서 행렬을 랭크가 1 인 행렬들로 분해했었다. 그리고 $k$ 개의 선형 특이벡터를 이용하여 $A_k$ 가 최적의 근사임을 보았었다.
이러한 방식으로 텐서 $T$ 도 랭크 $k$ 를 갖는 텐서로 근사할 수 있다. 그런데 텐서에서는 SVD 가 적용되지 않고 다른 방식으로 낮은 랭크의 좋은 근사치를 구한다.
텐서의 CP 분해
텐서 분석과 연산에에 있어서 기본 문제는 주어진 텐선 $T$ 를 랭크 1 텐서의 합으로 근사하는 것이다. 즉 근사분해이다.
CP 분해 : $T \approx a_1 \circ b_1 \circ c_1 + \cdots + a_R \circ + b_R \circ + c_R $
CP 분해는 행렬의 SVD 확장으로 여긴다. 하지만 SVD 와의 차이점으로 벡터 $a_1,\cdots,a_R$($b$, $c$ 도 마찬가지) 이 직교하지 않는다. 즉 직교불변이 아니다. ($Q_1 A Q_2^T$ 는 같은 특이값 $A$ 를 가진다. )
그리고 에카트-영 정리는 성립하지 않고, $T$ 에 가장 가까운 랭크 $R$ 텐서를 알지 못할 수 도 있다.
크루스칼은 가장 가까운 랭크 1 텐서가 (존재한다면) 유일함을 증명했다. 만약 랭크 $R$ 을 바꾸면 가장 근사하는 벡터 $a,b,c$ 도 바뀐다.
이 근사하는 랭크 텐서를 구하는 문제의 계산가능성은 NP-Hard 문제이다.
그래서 효율적인 방법으로 벡터 $a,b,c$ 를 계산하는 알고리즘이 필요하고, 현제로서 교대 최소제곱이 효과적으로 사용된다.
$||T_1 - A(C \circ B)^T||_F^2$
1. $B,C$ 를 고정하고 $A$ 를 변화시킨다.
2. $A,C$ 를 고정하고 $B$ 를 변화시킨다.
3. $A,B$ 를 고정하고 $C$ 를 변화시킨다.
이 알고리즘은 세가지 행렬화 형태 $T_1$, $T_2$, $T_3$ 을 사용한다. ( 텐서의 각 방향 슬라이스 ) $C \circ B$ 는 카트리-라오 곱이다. 다음에 다룬다.
텐서 T 의 행렬화 형태
행렬 $A$, $B$, $C$ 은 각 열이 CP분해의 벡터 $a$, $b$, $c$ 라고 하면, 각 행렬의 열은 $R$ 개 이고 텐서 $T$ 의 차원이 $I$, $J$, $K$ 라면 세 행렬은 ($I$ x $R$), ($J$ x $R$), ($K$, $R$) 의 차원을 가진다. CP 분해를 위해 $T$ 의 행렬화가 필요하다.
$a$ 로 구성된 ($I$ x $R$) 행렬 $A$ 이 존재하고, 벡터 $b$, $c$ 로 구성된 ($R$ x $JK$) 행렬 $M_1$ 을 찾는다.
이 두행렬의 곱셈 $AM_1$ 은 3방향 텐서를 표현한다. 이 $AM_1$ 과 텐서 $T$ 를 비교하기 위해서 텐서 $T$ 를 $T_1$ 으로 펼쳐야한다.
$I$,$J$,$K$ 가 3, 4, 2 인 텐서 $T$ 를 생각해보자.
첫 번째 방식으로 슬라이스를 하면,
$T_1$ : $I$ x $JK$ = (3 x 8) 의 형태로 $ T_1 = \begin{bmatrix} 1 & 4 & 7 & 10 & 13 & 16 & 19 &22 \\ 2 & 5 & 8 & 11 & 14 & 17 & 20 & 23 \\ 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 \\ \end{bmatrix} $ 으로 펼쳐지게 된다.
두번째방식
$T_2$ : $J$ x $IK$ = (4 x 6), $ T_2 = \begin{bmatrix} 1 & 2 & 3 & 13 & 14 & 15 \\ 4 & 5 & 6 & 16 & 17 & 18 \\ 7 & 8 & 9 & 19 & 20 & 21 \\ 10 & 11 & 12 & 22 & 23 & 24 \\ \end{bmatrix} $ 으로 펼쳐진다.
세번째 방식
$T_3$ : $K$ x $IJ$ = (2 x 12), $T_3 = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\ \end{bmatrix} $ 으로 펼쳐진다.
카트리-라오 곱 $A \odot B$
카트리-라오 Khatri-Rao product : $A \odot B$ 의 $j$ 열 = ($A$ 의 $j$ 열) $\otimes$ ($B$ 의 $j$ 열)
여기서 $A \otimes B$ 는 크로네커 곱 Kronecker product 로 두벡터 $A$($J$ x 1),$B$($K$x 1) 의 크로네커곱은 성분의 곱 $a_{ij}$ x $b_{kl}$ 을 모두 포함하는 ($JK$ x 1) 형태의 큰 벡터를 의미한다. ( 행렬에도 씌임 )
즉 $C$ 와 $B$ ( $K$ x $R$ ), ($J$ x $R$) 는 $R$ 개의 긴 열이 있는 $C \odot B$ ( $JK$ x $R$ ) 을 형성한다.
우리는 $T$ 를 $\sum a_i \circ b_i \circ c_i$ 으로 근사했었고, $T$ 를 3방향으로 슬라이스한 행렬 $T_1$, $T_2$, $T_3$ 을 얻을 수 있다. 각각은 $T_1 \approx A M_1$, $T_2 \approx B M_2$, $T_3 \approx C M_3$ 인 일반행렬 곱셈으로 정의 하는 행렬 $M_1, M_2, M_3$ 를 찾는다.
이때 $A$ 는 $a_1, \cdots, a_R$ 열이 있는 $I$ x $R$ 행렬이고, $T_1$ 는 $I$ x $JK$ 행렬이기 때문에, $M_1$ 은 $R$ x $JK$ 행렬이다. 행렬 $M_1$ 은 $b_j$ 열과 $c_k$ 열이 있는 행렬 $B$, $C$ 에서 얻는다.
$M_1$ 은 카트리-라오 곱 $C \odot B$ 의 전치이다. ($JK$ x $R$)
$C \odot B$ 의 $i$ 열은 $C$, $B$ 의 $i$ 열에서 얻는다. $c_{ki}$ 와 $b_{ji}$ 의 모든 곱 즉 $JK$ x 1 의 열이 $R$ 개 존재하기 때문에 총 $JKR$ 개의 곱을 수행한다.
이로써 $T$ 의 행렬 형태 $T_1, T_2, T_3$ 은 근사 행렬 곱셈으로 나타낼 수 있다.
$T_1 \approx A(C \odot B)^T$ $T_2 \approx B(C \odot A)^T$ $T_3 \approx C(B \odot A)^T$
$T$ 의 $CP$ 분해 계산
카트리-라오 곱을 통해 표현한 $T$ 의 행렬화 형태 $T_1 \approx A (C \odot B)^T$ 에서 $B,C$ 를 고정시키고 최선의 $A$ 를 찾는 교대 최소화 를 사용하여 계산한다.
$||T_1 - A(C \odot B)^T||_F^2 = ||T_1^T - (C \odot B)A^T||_F^2 $ 에서 최선의 $A$ 를 선택한다.
여기서 $C \odot B$ 는 $JK$ x $R$ 인 계수행렬이고, $A^T$ 의 $I$ 열을 각각 곱한 것이다. 그리고 프로베니우스 노름을 사용하면, 각 행과 열의 곱의 최소제곱으로 나타낼 수 있다. 즉, $I$ 개의 일반적인 최소제곱 문제를 얻는다.
일반적인 최소제곱식은 $Ax = b$ 식이고, 여기서 $A$ 는 계수행렬로 위에서 $C \odot B$ 를 의미한다. 이 행렬은 $JK \geq R$ 이므로 길고 얇다. 다른 식에서도 $IK \geq R$, $IJ \geq R$ 이 성립한다.
최소제곱에 대한 일반적인 식 $Ax = b$ 에서, 계수행렬 $A$ 는 위에서 $C \odot B$ 를 의미한다. ($A$ 가 아님).
이 해는 유사역행렬 $ \hat{x} = A^+b 에 의해 주어진다.
행렬 $A$ 에 독립인 열이 있다면, $A^+$ 는 행렬 $A$ 의 좌역행렬이다. $C \odot B$ 의 유사역행렬은 다음과 같이 나타난다. 기호 $.*$ 는 원소별 곱을 나타낸다.
$ (C\odot B)^+ = [(C^TC).* (B^T B)]^+(C\odot B)^T$
이 행렬을 $T_1^T \approx (C \odot B)A^T $ 의 좌변에 곱하면,
$A = T_1 (C \odot B) (C^TC .* B^TB)^+$
위 식이 유도된다. 고정된 $B,C$ 가 있는 최소제곱 문제는 이 행렬로 풀 수 있다.
다음으로 $A, C$ 를 고정하여 최적의 $B$ 를 찾고, 새로운 $A, B$ 로 최적의 $C$ 를 찾으면 한주기가 끝난다.
터커 분해 Tucker decomposition
터커 분해는 $P$ 개의 열벡터 $a_p$, $Q$ 개의 열 벡터 $b_q$, $R$ 개의 열 벡터 $c_r$ 을 사용한다. 그러면 모든 랭크 1 결합 $a_p \circ b_q \circ c_r$ 이 가능해진다. $P,Q,R$ 차원의 핵심 텐서 $G$ 는 다음과 같이 계수를 결정한다.
$T$ 의 터커 분해 $T = \approx \sum_1^P \sum_1^Q \sum_1^R g_{pqr} a_p \circ b_q \circ c_r$
이 계수행렬 $G$ 로 인해서 벡터 $a,b,c$ 가 정규직교인 열을 선택할 수 있다. 터커는 $R$ 뿐만아니라 $PQR$ 개의 랭크 1 텐서의 결합이다.
터커 분해 식은 근사식으로, CP 분해와 같이 행렬화를 해야한다. $T_1, T_2, T_3, G_1, G_2, G_3$ 으로 행렬화를 하고, CP 행렬이 터커 행렬로 바뀌고, 카트리-라오 곱 대신 크로네커 곱을 사용한다.
터커 $T_1 \approx AG_1 (C \otimes B)^T T_2 \approx BG_2 (C \otimes A)^T T_3 \approx C G_3(B \otimes A)^T$
고차 SVD는 특별한 터커 분해이다.
'선형머수학' 카테고리의 다른 글
| 13. 큰 행렬의 계산 (0) | 2022.05.02 |
|---|---|
| 11. 벡터, 함수, 행렬의 노름 (0) | 2022.04.16 |
| 10. 레일리 몫과 일반화된 고유값 (0) | 2022.04.16 |
| 9. 주성분과 최적의 낮은 랭크 행렬 (0) | 2022.04.15 |
| 8. 특이값과 특이벡터 (0) | 2022.04.13 |