D047

Singular Value Decomposition

M(mxn) 행렬이 있고, M의 랭크를 r로 둡시다.
그러면 U, V, $\Sigma$ 를 다음과 같이 찾을 수 있습니다.

1. U 는 $m\times r$ 의 column-orthonomal matrix 입니다.
   이것의 칼럼들은 각각 유닛벡터입니다. (각 칼럼끼리의 dot 이 0)
2. V 는 $n\times r$ 의 column-orthonormal matrix 입니다.
   여기서 V 는 transpose 형태로 사용합니다.
   그래서 $V^T$ 의 행은 orthonormal 입니다.
3. $\Sigma$ 는 diagonal matrix 입니다.
   대각 성분 외의 모든 요소는 0 입니다.
   이 행렬의 성분들은 M의 singular value 라고 합니다.

다음 그림은 movie-user 레이팅에 관한 2랭크 행렬을 보여줍니다.

여기서 영화에 2개의 conncept 이 숨겨져 있습니다.
매트릭스, 에일리언, 스타워즈는 SF 영화이고
카사블랑카와 타이타닉은 로맨스 영화입니다.
이 정보는 명시적으로 파악할 수 없습니다.

모든 남자들(Joe, Jim, John, Jack)은 SF 에 평가를 했고,
여자(Jill, Jenny, Jane)들은 로맨스에만 평가를 했습니다.
이 행렬에서는 2개의 rank 를 갖습니다.

이 행렬 M의 decomposition 은 그림 11.7 과 같습니다.
(SVD decomposition 은 추후 선형대수 포스팅에서 다룰 예정입니다.)

SVD 을 사용하는 목적은 기존 행렬에 숨겨진 표상(represent)된 concept들을 찾는 것 입니다.
위의 예시에서, 숨겨진 컨셉으로 SF와 로맨스가 있었습니다.

M의 행들을 사람, 칼럼을 영화로 봅시다.
그러면 행렬 U 는 ‘사람-concept’ 을 연결합니다.
예를들어,
M의 1 행은 Joe 이고 SF concept만 좋아합니다.
그래서 U 의 1행(Joe) 1열(SF)에 만 0.14 로 점수가 있고,
Joe 가 SF 영화들을 다른 사람에 비해 낮은 점수를 주었기 때문에
점수가 있는 다른 행들(사람들)에 비해 낮습니다.

V는 ‘영화-concept’ 과 관련있습니다.
$V^T$ 의 첫번째 부터 세번째 칼럼의 첫 행의 값 0.58 은
3개의 영화 매트릭스, 에일리언, 스타워즈를 가리킵니다.
이 영화들은 SF 장르이므로 값이 있고,
나머지 두 칼럼에서 성분이 0 인 것은 이 영화들이 로맨스 개념에 대한 성질이 없다는 것을 의미합니다.

$\Sigma$ 행렬은 각 concept들의 강도(strength)를 나타냅니다.
위 에서, SF 컨셉의 강도는 12.4 이고 로맨스의 강도는 9.5 입니다.
기존 행렬 M 에서 직관적으로 보면, SF 컨셉이 더 강합니다.
로맨스 영화보다 SF의 영화를 좋아하는 사람들에 대한 정보를 더 많이 제공하고 있는 것을 볼 수 있습니다.

실제 상황에서는, 이 concept들을 명확히 파악하기는 어렵습니다.
아래 예시와 같이 다른 상황이 발생할 것이고,
그 행렬의 SVD 분해에서
concept 들을 SF, 로맨스와 같이 단순히 찾기는 어렵습니다.

Jill 과 Jane 이 Alien에 추가로 점수를 매겨.
이전에는 행렬의 랭크가 2 였지만 3 이 되었습니다.
$\Sigma$ 에서 첫번째는 SF, 두번째는 로맨스이고
3번째의 컨셉은 정의하기 어렵지만 weight, 강도가 작습니다.
때문에 중요하지 않은 컨셉이라고 볼 수 있습니다.

Dimensionality Reduction Using SVD 

엄청 큰 행렬 M 을 $U\Sigma V^T$ 로 표현하는 작업을 가정해 봅시다.
행렬이 너무커서 쉽게 저장할 수 없는 상황입니다.
M 을 SVD 분해한 세개의 행렬의 차원을 줄이는
적합한 방법은 $\Sigma$ 의 가장 작은 Sigular value 를 0으로 바꾸는 것입니다.
작은 Sigular value 들 s 개를 0으로 바꾸면
이와 같이 계산되는 따르는 U, V의 칼럼들을 s개 제거할 수 있습니다.

그림 11.9 예시에서는 3개의 특이값을 갖었습니다.
여기서 2개의 차원으로 줄이고자 하면,
$\Sigma$ 의 세번째에 있는 가장 작은 특이값 1.3 을 0 으로 바꿉니다.
U의 3번째 칼럼과 $V^T$ 의 3번째 행은 연산시 0 만 곱해지므로, 이 행과 칼럼도 제거할 수 있습니다.
이렇게 만들어진 행렬은 기존의 행렬에 근사한 값을 갖는 것을 확인할 수 있습니다.

이와 같이 작은 singular value 값을 버려서 얻는 M’ 는
M과의 RMSE(Root Mean Square Error) 가 최소화됩니다.(다른 것을 줄이는 것에 비해)
행렬에 대한 Frobenius norm 을 사용하여(||M||) RMSE 가 왜 최소화되는지 확인해보겠습니다.

M 이 3개의 행렬의 곱(product)이라고 가정해 봅시다.
$M = PQR$, $m_{ij},p_{ij},q_{ij},r_{ij}$ 는 각 행렬의 성분입니다.
그러면 행렬 곱의 정의에 따라 다음이 나옵니다.

M의 Frobenius norm의 제곱은 다음과 같이 표현할 수 있습니다.

이 제곱식을 풀면 다음과 같이 표현됩니다.

이제 위의 $PQR$을 $U\Sigma V^T$ 라고 합시다.
R은 row-orthonomal 이고, 그 행들은 유닛벡터입니다.
이 성질에 따라 행의 dot product 는 0 이 됩니다.

Q가 대각행렬이기 때문에 k=l, n=m 일때 빼고는 $q_{kl} ,q_{nm}$ 은 0이 됩니다.
그래서 l 과 m 에 대한 시그마를 없앨 수 있습니다.
그래서 다음과 같이 식을 줄일 수 있습니다.

다음 i 가 내부에 있도록 시그마의 순서를 바꿉니다.
위 식에서 $p_{ik} p_{in}$ 만 i 와 관련이 있습니다. 모든 다른 항들은 상수로 보고 i 에 관한 시그마만 신경씁니다.
P 가 column-orthonormal 이기 때문에, k 가 n 일때 $\Sigma_ip_{ik}p_{in} = 1$ 이고 그외에는 0 입니다.
그러므로 k=n 으로 설정하고(1인 경우) $p_{ik} p_{in}$ 항을 버릴 수 있습니다. 다음과 같이 줄일 수 있습니다.

R은 row-orthonormal 이므로 $\Sigma_jr_{kj}r_{kj} = 1$ 입니다. 그래서 $r_{kj}$ 항과 j 에 대한 합을 제거할 수 있습니다.
그래서 다음과 같이 단순한 식을 만들 수 있습니다.

M - M’ = $U(S - S’)V^T$ 이므로
$||M - M’||^2$ 를 S-S’ 의 대각 요소의 제곱합과 동일하게 볼 수 있습니다.
이를 최소화 하기 위해서는 특이값에서 가장 작은 요소를 선택해야합니다.

How Many Singular Values Should We Retain?

경험적으로 $\Sigma $ 의 energy 는 90% 정도는 갖도록 하는 것이 좋습니다..
이 의미는 M’ 의 singular value의 제곱합이 적어도 M 제곱합의 90%는 되어야 한다는 의미입니다.
위 행렬에서는 $12.4^2 + 9.5^2 + 1.3^2 = 245.70$ 이 전체 energy이고, 유지한 energy 는 $12.4^2 + 9.5^2 = 244.01$ 으로 99% 입니다.

Querying Using Concepts

이렇게 SVD decomposition 을 사용하여 다뤄야할 차원을 축소할 수 있습니다.
실제로 SVD를 어떻게 사용하는지 확인해보겠습니다.

예시 상황에서 A라는 사람이 매트릭스를 보고 4점을 메겼다고 합시다.
그러면 이 사람의 벡터는 a=[4,0,0,0,0] 입니다.

A 를 M 을 분해한 행렬 V 에 곱하여 concept space 에 매핑할 수 있습니다.
aV = [2.32, 0] 의 결과가 나오고
이것은 A 가 SF 에 관심이 있다는 것을 나타냅니다.

이제 컨셉 공간에서 A를 표현했지만 원래의 movie space에서 파생 된 표현과는 다릅니다.
우리가 그의 표상을 영화 공간에 매핑하는

사용자 A 의 컨셉에 대한 정보를 얻었고
이를 ‘concept-영화’ 의 연결을 위해 $V^T$ 를 곱합니다.
위 행렬에서 $[2.32,0] \cdot V^T =    [1.35,1.35,1.35,0,0] $ 으로 나오고,
이 결과를 가지고 A 에게 에일리언, 스타워즈 영화를 제시할 수 있습니다.

위의 사용자의 concept 정보를 사용하여,
유사한 사용자를 더 간단하게 찾을 수 있습니다.
예를들어, Joe 는 [1.74,0] 으로 Jill 은 [0, 5.68] 으로 ‘concept’ 정보를 갖습니다. ($r_i\cdot V$)
이 concept 공간의 사용자 정보에 코사인 거리를 사용하여 사용자 간 유사도를 측정할 수 있습니다.
위의 경우 A 가 Joe 와 유사합니다.(0) Jill 과는 코사인 거리가 1 이됩니다.

SVD 에서 작은 Sigular value 를 제거하여
더 작은 차원으로 연산을 수행할 수 있습니다.
축소하는 경우 기존값과 정확하게 같지는 않지만
RMSE 가 최소가 되도록 축소할 수 있습니다.