Ref. Open: SVD

레이블이 SVD인 게시물을 표시합니다. 모든 게시물 표시

2014년 8월 29일 금요일

협업 필터링과 추천 시스템으로 내일 뭐 먹을지 결정해보기

Collaborative Filtering and Recommendation System

한글로 적어 놓고 나니 왠지 어색합니다. 협업 필터링(Collaborative Filtering)과 추천 시스템(Recommendation System)은 밀접한 관련이 있고, 우리가 모르는 사이에 매일 이것을 이용하고 있습니다. 실제로 Amazon에서 구매하는 물건의 약 35%가 추천으로부터 발생하고, Netflix의 영화 대여도 2/3 정도가 추천에 의해서 발생한다고 알려져 있습니다. 한국에서도 ‘와챠’라는 모바일 앱이 개인화된 추천 서비스를 제공함으로써 기존의 영화 리뷰 시장을 뒤흔들었습니다. 이 글에서는 추천 시스템 중에서 협업 필터링의 개념을 이용해서 ‘내일 뭐 먹을까?’를 결정해보는 간단한 예시를 통해 접근하고자 합니다.

여기에서도 SVD를 적용합니다. SVD는 singular value가 큰 순서로 정렬되는 형태이므로, 중요한 정보를 압축할 수 있는 특성을 가진다는 것을 알고 있다면, Low-rank approximation으로 분류를 하는데 활용할 수 있다는 것도 생각해 볼 수 있습니다. 다시 말하면 eigenvalue가 큰 것들은 어떤 자료에서 중요한 의미를 지니는데, 그에 해당되는 eigenvector들은 모두 orthogonal합니다. orthogonal하다는 말은 직교한다는 말하고 비슷한데, 그릴 수 없는 3차원을 넘어가는 다차원에 대해서도 일반화된 개념입니다. 내적이 ‘0’이므로 서로 겹치는 부분이 없습니다. 어떤 자료를 SVD한다는 말은 결국 중요한 의미를 지니는 eigenvector공간으로 재 투영한 값들로 재구성한다는 의미로 해석하면 될 것 같습니다.

예를 들자면, 어느 학교의 학생에 대한 정보가 몸무게, 손가락 길이, 키로 각각 주어진다고 가정해보겠습니다. 그러면 3차원 공간에 데이터를 그려볼 수 있습니다. (1,0,0)(0,1,0)(0,0,1)-x, y, z-몸무게, 손가락 길이, 키를 기저 벡터로 하는 공간에 그리는 겁니다. 그런데, 만약에 키가 모두 비슷한 학생들만 다니는 학교라고 하면 z축은 별로 의미가 없어 집니다. x-y평면에 투영해서 봐도 3차원 공간의 데이터와 별로 손실이 없을 수 있다는 의미입니다.

추천 시스템에 활용하는 간단한 예시를 들어보겠습니다.

어떤 모임에 4명의 사람이 있었는데, 새로운 사람이 들어온 경우에 그 사람이 어떤 성향을 가지는 사람인지 판단하고 메뉴를 추천해주는 것을 생각해 볼 수 있습니다. 아래 표와 같은 정보가 주어진다고 가정해보겠습니다.

	Korean Cuisine	Pizza	Hamburger	Chinese Cuisine
A	9	2	1	8
B	8	5	6	10
C	7	9	8	9
D	2	3	4	8

데이터를 직관적으로 관찰해보면 중국 요리는 대부분의 사람이 좋아하고 피자를 좋아하는 사람은 대체로 햄버거도 좋아한다는 특성을 관찰할 수 있습니다.

새로운 멤버 E와 식사를 하러 가야 하는데, 그날 마침 한국음식과 햄버거 중에 결정해야 하는 상황이라면 E는 어떤 음식을 더 좋아할까요?

	Korean Cuisine	Pizza	Hamburger	Chinese Cuisine
A	9	2	1	8
B	8	5	6	10
C	7	9	8	9
D	2	3	4	8
E	?	9	?	7

SVD를 이용한 Low-rank approximation으로 추정해볼 수 있습니다. Rank 3으로 줄이면 아마도 한국음식, 피자, 햄버거와 비슷한 방향을 가지는 기저 벡터 공간에 재 투영될 것을 예측할 수 있습니다. 다음 예시를 참고하여 주시기 바랍니다.

협업 필터링 예제

E가 평가를 하지 않은 빈 곳에 대해서 평균으로 채우고 Low-rank approximation을 수행해보면 이 사람은 아마도 햄버거를 더 좋아하는 사람인 것 같습니다.

실제 시스템에서는 고려해야 할 사항이 훨씬 더 많을 것입니다. 왜냐하면 SVD의 연산 복잡도는 선형으로 증가하지 않기 때문에 100만명의 회원이 있을 경우에 간단한 방법으로 해결할 수 없을 것입니다. 의도적으로 데이터에 손상을 가하려는 사람들(평점을 일부로 높게 주거나 낮게 주는 사람들)이 있을 수도 있고 개인적인 성향에 따라 평점이 후한 사람도 있고 그렇지 않은 사람도 있을 것입니다.

협업 필터링(Collaborative Filtering) 예제

Matfact_newcomer

% Collaborative Filtering
% 2014. 8. 29
% refopen.blogspot.com

A = [9 2 1 8;
    8 5 6 10;
    7 9 8 9;
    2 3 4 8;
    5 9 5 7];

rank = 2;

m = mean(A, 2);
s = std(A, 1, 2);
matm = repmat(m, 1, 4);
mats = repmat(s, 1, 4);

% normalization
normA = (A - matm) ./ mats;

[u d v] = svd(normA)

vt = v';
temp = u(:, 1:rank)*d(1:rank, 1:rank)*vt(1:rank, :)

% denormalization
Ahat = matm + (temp .* mats)

u =

   -0.5699   -0.1579   -0.5892   -0.5351   -0.1297
   -0.5471   -0.3829   -0.0037    0.7322   -0.1339
    0.3887   -0.5537    0.0504   -0.1310   -0.7230
   -0.1319   -0.6232    0.4847   -0.3305    0.5001
    0.4554   -0.3654   -0.6445    0.2261    0.4388


d =

    3.0336         0         0         0
         0    2.9144         0         0
         0         0    1.5179         0
         0         0         0    0.0000
         0         0         0         0


v =

   -0.5690    0.4985   -0.4216    0.5000
    0.7368   -0.0436   -0.4530    0.5000
    0.1603    0.3410    0.7798    0.5000
   -0.3281   -0.7958    0.0948    0.5000


temp =

    0.7543   -1.2537   -0.4339    0.9334
    0.3882   -1.1743   -0.6465    1.4326
   -1.4753    0.9392   -0.3612    0.8973
   -0.6777   -0.2156   -0.6834    1.5767
   -1.3170    1.0644   -0.1417    0.3943


Ahat =

    7.6667    0.5676    3.4658    8.2999
    7.9954    4.9950    6.0085   10.0010
    7.0268    9.0288    7.9505    8.9940
    2.7065    3.7590    2.6934    7.8411
    4.3160    8.2652    6.2650    7.1538

2014년 8월 28일 목요일

동차 선형 방정식을 SVD로 풀 수 있는 이유

Solving homogeneous linear equation using SVD

최소 자승법을 이야기 하면서 의사 역행렬을 이용해 over-constrained eq.을 푸는 방법을 소개 했는데 정작 왜 그것이 정답이 되는지는 얼버무리고 넘어간 것 같아서 이 글을 게시합니다.

SVD(Singular Value Decomposition)은 선형 대수학에서 매우 중요한 의미를 가집니다. eigenvalue, eigenvector가 중요한 것처럼 singular value들은 eigenvalue와 관계가 있기 때문입니다. 컴퓨터 비전이나 기계 학습에서 선형 대수학이 빠질 수 없는 이유는 바로 선형 변환에 불변하는 특성을 가지는 eigenspace 해석을 통해서 중요한 성질을 구할 수 있기 때문입니다. PCA(Principal Component Analysis)도 결국 SVD를 이용해서 주요 성분을 얻어내는 것이고, 기계 학습에서 sparse coding으로 중요한 정보 만을 이용해서 영상을 분류하는 방법에도 적용될 수 있습니다.

행렬 \(\mathbf{A}\)의 singular value를 \(\sigma\)라고 하면, \(\mathbf{A^*A}\)와 \(\mathbf{AA^*}\)의 0이 아닌 eigenvalue, \(\lambda\)와 \(\sigma\) = \(\sqrt{\lambda}\)의 관계를 가집니다. 여기서 \(\mathbf{A^*}\)는 \(\mathbf{A}\)의 켤레전치행렬(conjugate transpose) 입니다. 간단하게 상수라고 생각하면 제곱 한 것을 분해한 것과 그냥 분해한 것의 차이 정도로 대략 감을 잡으시면 될 것 같습니다.

그럼 SVD로 어떻게 동차 방정식의 해를 구할 수 있는지 보겠습니다.

\(\mathbf{Ax} = 0\)

와 같은 동차 방정식이 주어지는 경우, 자명하지 않은 해(non trivial solution)을 구한는 것이 목적입니다. (\(\mathbf{x}=0\)이면 항상 참이 되니 자명한 해이므로 관심이 없습니다.)

그래서 자명한 해가 아닌 해를 구하기 위해서 제약 조건을 줍니다. 보통은 \(||\mathbf{x}||=1\) 과 같이 벡터의 크기를 정해줍니다. 우변이 0이기 때문에 벡터의 크기는 아무래도 관계 없기 때문입니다.

이제 행렬 \(\mathbf{A=UDV^T}\)로 분해하면,

\(\mathbf{||UDV^Tx||=||DV^Tx||}\) - ①
\(\mathbf{||x||=||V^Tx||}\) - ②

로 둘 수 있습니다. 왜냐하면, SVD로 구한 \(\mathbf{U, V^T}\)행렬은 각 열이 모두 orthogonal 하기 때문입니다. 이 특성은 회전 행렬과 같습니다. 벡터 공간에서 임의의 벡터를 아무리 회전 시켜도 그 크기가 변하지 않는다는 것을 생각해보면 식 ①, ②가 성립하는 것을 알 수 있습니다.

\(\mathbf{y=V^Tx}\) - ③

을 도입해 보면, 최초의 문제는 결국 '\(\mathbf{||Dy||}\)를 최소화하되 \(\mathbf{||y||}=1\)을 만족 시켜라.'는 문제로 바뀌게 됩니다.

여기서 SVD의 특성을 다시 한 번 생각해보면, 분해된 행렬 \(\mathbf{UDV^T}\)에서 \(\mathbf{D}\)는 대각 행렬이고 원소들은 singular value가 큰 순서대로 정렬되기 때문에 \(\mathbf{||Dy||}\)를 가장 작게 만들면서 \(\mathbf{||y||}=1\)을 만족 시킬 수 있는 방법은 \(\mathbf{y}=(0, 0, ..., 0, 1)^T\)로 두는 것입니다.

그러므로, \(\mathbf{x=V^Ty}\)는 결국 \(\mathbf{V^T}\)의 마지막 열이 됩니다.