D048

CUR Decomposition

일반적으로 실제 상황에선 행렬 M 은 매우 크고 sparse 하게 구성됩니다.
예를 들어 문서들과 그 안에 있는 단어를 표현한 행렬는 sparse 합니다.
대부분의 단어들은 문서들에서 나타나는 것은 아니기 때문입니다.
유사하게, 고객과 제품의 행렬도 많은 사람들이 대부분의 제품을 사는게 아니기 때문에 sparse 합니다.

큰 행렬의 경우 sparse 한 경우는 0이 많아서 계산을 할 수 있지만
dense 하게 되면 이 행렬은 다루지 못합니다.
이전 포스팅의 SVD 에서는 M 이 sparse 하더라도
decomposition 한 결과인 U와 V 가 dense 하게 나옵니다.
$\Sigma$ 는 sparse 하지만, 일반적으로 U와 V 보다 크기가 더 작고,
실제 연산을 줄이는데 큰 도움이 되지 않습니다.

그래서 CUR-decomposition 이라는 다른 분해 방식을 사용합니다..
이 방식은 M 이 sparse 하고,
분해했을 때의 C, R 두개의 행렬 또한 sparse 할 때 유용합니다.

행렬 M 에 대해 정확한 분해를 하는 SVD 와 달리,
CUR-decomposition 은 concept의 수 r 에 따라
M에 가까워지는 근사한(approximation) 분해를 수행합니다.

Definition of CUR

M을 m행과 n 칼럼의 행렬이라고 둡시다.
concept의 수 r 을 정합니다.(분해에 사용될)
M 의 CUR 분해는 M의 r 개의 칼럼의 무작위로 선택된 집합, C 행렬($m \times r$) 과
M 의 r 개의 행이 무작위로 선택된 집합, R($r \times n$) 행렬 입니다.
$r\times r$ 의 행렬 U 는 C와 R으로 부터 구성됩니다.

1. W 를 $r\times r$ 행렬, C 행렬과 R 행렬에서 교차되는 집합이라고 봅시다.
   W의 i 행과 j 칼럼은 C의 j 칼럼과 R 의 i 행입니다.
2. W 에 대한 SVD 를 계산합니다. $W = X\Sigma Y^T$
3. $\Sigma^+$ 를 계산합니다. 이는 $\Sigma$ 의 Moore-Penrose pseudoinverse 입니다.
   만약 i 번째 요소 $\sigma$ 가 0 이 아니라면, $1/\sigma$ 로 바꾸고,
   0 이라면 그대로 남겨둡니다.
4. U = $Y(\Sigma^+)^2 X^T$ 라 합니다.

예시를 통해 확인해보겠습니다.

아래의 행렬에서 2개의 행과 열을 다음과 같이 선택했다고 봅시다.

W의 첫번째 행은 R의 첫번째 행을 따르고, 이는 M의 Jenny 에 대한 행입니다.
첫번째 행의 첫번째 칼럼이 0 이고 두번째 칼럼이 5이므로 Jenny 입니다.
두번째 행은 Jack 입니다. 앞에는 5이고 뒤에는 0 입니다.
그리고 칼럼은 에일리언과 카사블랑카 입니다.

행렬 U 는 W 에서 pseudo inverse 를 사용해 만들어진 행렬입니다.

$W = X \Sigma Y^T$ 일때, $\Sigma $ 의 pseudo inverse 를 $\Sigma^+$ 라 하고(nonzero 를 역수로 취하는 것)
$U = Y(\Sigma^+)^2 X^T $ 를 수행하면 됩니다.

W 를 SVD 분해를 하면 다음과 같습니다.

여기서 pseudo inverse $\Sigma^+$ 는 다음과 같습니다.

그러므로 행렬 U 는 다음과 같습니다.

위 과정에서 행과 칼럼을 무작위로 선택했습니다.
그러나 더 중요한 행과 열은 선택되도록 bias 를 주는 것이 좋습니다.
여기서 사용하는 중요도의 측도는 Frobenius norm 의 제곱입니다. (행, 열의 요소의 제곱 합)
많은 데이터를 갖고 있을수록 더 중요하다고 가정 하여 행렬의 크기를 나타내는 Frobenius를 사용합니다.

Frobenius norm f를 $f= \Sigma_{i,j}m_{ij}^2$ 라 합시다.
그러면 한 행을 선택할 때 행 i 를 선택하는 확률 $p_i$ 는 $\Sigma_jm_{ij}^2 / f$ 이고
한 열을 선택할 때 열 j 를 선택하는 확률 $q_j$ 는 $\Sigma_im_{ij}^2 / f$ 입니다.

위 행렬에서 제곱합은 243 입니다.
첫번째부터 세개의 칼럼의 Forbenius norm 은 $1^2+3^2+4^2+5^2 = 51$ 로 동일하고
그래서 각 확률은 51/243 = 0.210 입니다.
나머지 두 칼럼의 경우 $4^2 + 5^2 + 2^2 = 45$,
각 45/245 = 0.185 의 확률을 갖습니다.

이제 C 의 r 개의 칼럼을 선택해 봅시다.
각 칼럼은, M의 칼럼으로 부터 무작위로 선택하지만
칼럼마다 다른 확률을 갖습니다. j 칼럼인 경우 $q_j$ 의 확률을 갖습니다.
M의 칼럼으로부터 독립적으로 r개의 칼럼이 선택되므로,
동일한 칼럼이 한번 이상 선택될 수 있습니다. (이후 언급)

M의 선택된 칼럼을 갖고, 각 열의 요소를이 열을 선택하는 기대 횟수(r x 확률)의 제곱근으로 나누어 각 열의 크기를 조정합니다.
즉, j 번째 칼럼의 요소들을 $\sqrt{rq_j}$ 로 나눕니다. M의 조정된 칼럼은 C 의 칼럼이 됩니다.

R도 동일한 방식으로 선택합니다.
각 행은 i 행의 확률 $p_i$ 를 가지고 선택하고,
선택한 각 행을 기대 횟수로 나누어서 스케일합니다.
선택한 M의 i 번째 행인 경우 $\sqrt{rp_i}$로 나눕니다.

r = 2 로 두고, 11.12 그림의 행렬에서 에일리언(2번째), 카사블랑카(4번째) 를 무작위로 뽑았다고 가정해 봅시다.
에일리언에 대한 칼럼은 $[1,3,4,5,0,0,0]^T$ 이고 이 칼럼은 $\sqrt{rq_2}$ 로 나눠서 스케일해야합니다.
$q_2 = 0.210$ 으로, $\sqrt{rq_2} = 0.648$ 이 됩니다.

스케일된 칼럼은 $[1.54,4.63,6.17,7.72,0,0,0]^T$ 가 됩니다.
이것이 C의 첫번째 칼럼입니다.

C 의 두번째 칼럼은 $\sqrt{rp_4} = \sqrt{2\times 0.185} = 0.608$ 을 사용하여 스케일을 합니다.
그래서 C의 두번째 칼럼 $[0,0,0,0,6.58,8.22,3.29]^T$ 를 얻습니다.

행의 경우도 동일하게 스케일하여 다음과 같은 R 행렬을 얻을 수 있습니다.

이제 3개의 성분 행렬 C, U, R 을 얻었습니다.
이 세 행렬의 product 는 기존 행렬 M 에 근사하게 나옵니다.

이 근사치는 일반적으로 행과 열이 매우 많이 선택되었을 때만 가까워지는 것을 보장하지만,
행과 열을 높은 중요도의 bias를 가지고 선택하여
보다 작은 수의 행과 열을 (r) 가지고도
기존 행렬의 중요한 부분을 추출할 수 있습니다.

이전까지의 예시를 정리하면 위 그림처럼 수행됩니다.
실제 값과 근사치의 차이는 큰 편이지만(특히 SF의 숫자에서), 그 값은 기존의 것과 비례합니다.

Eliminating Duplicate Rows and Columns

위의 무작위 선택에서는 동일한 행과 열이 한번 이상 선택될 가능성이 있습니다.
사실 같은 행을 두번 사용하는 것은 크게 신경쓰지 않아도 됩니다.
그대로 사용해도 되고, R(C) 에서 동일한 k 행(열)들을 합치는 것도 가능합니다.
합치는 경우 R(C)은 더 적은 행(열)으로 남깁니다.
이와 같이 C 도 합쳐서 C 에서 더 적은 칼럼으로 만들 수 있습니다.
그러나 행들과 칼럼들에 대해 남아있는 벡터는 그것의 각 성분에 그대로 $\sqrt{k}$ 를 곱해야합니다.

위와 같이 행이나 칼럼을 합칠 때,
R의 행이 C 의 칼럼보다 더 적을 수 있고, 그 반대도 될 수 있습니다.
때문에 W 가 정방행렬이 아닌 경우도 발생합니다.
그런 경우 pseudo inverse 는 $\Sigma$ 에 전치를 시키고 nonzero 의 역수를 취하여
다음과 처럼 $\Sigma^+$ 를 구할 수 있습니다.