Code Sprint 2015 Round 2 – SVD로 VOD추천하기

안녕하세요 Code Sprint 2015 Round 2 – VOD 추천에서 2위에 입상한 김대환입니다. 이 글을 통해 제가 VOD 추천문제에 어떻게 접근하였는지를 설명하려고 합니다. 추천 서비스에 대해서는 문외한이라 대회 기간 공부를 하면서 답을 찾아 나갔기 때문에, 최종 제출한 방식이 방법론 측면에서 꼭 맞는 것이 아닐 수도 있고, 제가 선택하고 진행한 방식에 오류가 있을 수 있음을 미리 밝힙니다. 문제의 풀이보다는 후기의 측면에서 보아 주셨으면 좋겠습니다.

 Round 2 문제가 공개되고

기계 학습에 관심이 있어서 이번 Round 2 문제가 공개되고 상당히 가슴이 뛰었습니다. 하지만 하고 싶은 마음과는 달리, Round 2 기간에 겹쳐 있던 여러 가지 빡빡한 일정과 24CPU를 장착했다는 테스트 머신과 비교하기에는 좀 초라했던 제 노트북에서 코드를 테스트해야 하는 상황 때문에, 가장 간단한 알고리즘으로 짧은 시간에 짤 수 있는 코드를 만드는 것을 기본 방향으로 했습니다.

공부하기 / 전략 짜기

기계학습에 관심이 있다는 말이 무색하게도, 추천 서비스의 작동방식에 대해서는 아는 바가 없었습니다. 검색을 통해 알아낸 것은 크게 협업 필터링(Collaborative Filtering, 줄여서 CF)과 특이값 분해(Singular Value Decomposition, 줄여서 SVD)가 있다는 것을 알 수 있었습니다. 주말 동안 찾은 내용을 요약하자면,

1. Collaborative Filtering

1.1. 사용자 유사성 기반 – 사용자 간 유사성을 구한 다음 주어진 사용자와 가장 비슷한 사용자 N명을 구하고, 그 사용자들이 본 VOD 중에서 주어진 사용자가 보지 않은 VOD를 추천하는 방식

1.2. VOD 유사성 기반 – VOD 간의 유사성을 구한 다음, 주어진 사용자가 본 VOD와 비슷한 VOD를 추천하는 방식

2. Singular Value Decomposition

어떻게 적용하는지는 모르지만 (주말까지는 몰랐습니다. 수식으로만 주로 설명되어 있어서요) Netflix 대회에서 좋은 결과를 얻은 방식 중의 하나

등이 있는 것 같더군요. 이 중에 무언가 하나를 골라서 어느 정도 성능이 나오고 나면

3. 미성년자 관람불가물만 주로 보던 사람을 골라내서 해당 VOD를 주로 추천

4. 유아용 VOD를 아이들에게 보여주는 사용자를 골라내서 해당 VOD를 주로 추천

이렇게 두 가지 정도를 추가해서 조금 더 점수를 높이려고 했습니다.

고민을 조금 하다가 메인 알고리즘으로는 SVD를 선택했고, 결국 3, 4안은 시간이 없어서 시작하지도 못했습니다. VOD 추천에서 대표적인 알고리즘이라고 하는 CF대신 SVD를 선택했던 이유는, 유사성을 구하기 위해서는 사용자나 VOD가 가지고 있는 특징(feature) 중에 어느 것이 유사성을 구하는 데 중요하게 작용하는지 판단하기 위해서 반복적인 테스트를 해야 할 것으로 예상이 되지만, SVD는 아주 유명한 행렬 분해 알고리즘이기 때문에 적용만 된다면 공개된 라이브러리를 이용해서 간단하게 알고리즘을 짤 수 있어 보였기 때문입니다.

SVD를 이용한 VOD 추천

SVD는 m x n 행렬 A를 다음과 같은 3개 행렬을 곱으로 나타내는 방법입니다.

A = B S C

B: m x k 행렬

S: k x k 대각행렬

C: k x n 행렬

대각 행렬 S의 각 원소에 제곱근을 취한 행렬을 s라고 하면

A = B s s C = U V (단, U = B s, V = s C)

와 같이 나타낼 수도 있겠지요. 이렇게 하면, m x n 행렬 A를 m x k 행렬 U와 k x n 행렬 V의 곱으로 나타낼 수 있게 됩니다.

이것을 어디에 쓸 수 있을까요? 2차원 행렬 A가 이미지를 나타낸다고 하면, 그냥 저장하면 mn개의 값을 저장해야 하지만, 위와 같은 두 행렬의 곱으로 나타내면 (m + n)k개의 값만 있으면 되기 때문에, k가 mn / (m + k)보다 작은 값이기만 하면 정보를 압축하는 효과를 가집니다. 물론 일반적으로 행렬 곱을 통해서 복원한 이미지와 원본 이미지 사이에는 차이가 있어서 손실 압축이 되겠지요.

VOD 추천 문제에 적용하면, i번째 사용자가 매기는 j번째 VOD에 대한 점수를 r이라고 할 때 (i, j) = r 의 형태로 행렬의 모든 값을 채워나가면 모든 사용자가 모든 VOD에 매기는 점수를 하나의 행렬 A로 나타낼 수 있습니다. 이것을 분해해서 U, V 두 행렬을 곱으로 나타내면, m x k의 크기를 가지는 행렬 U는 m명의 사용자를 그보다 작은 k 차원의 값으로 표현하는 변환 행렬이 되고, k x n 의 크기를 가지는 행렬 V는, k 차원으로 표현된 사용자 데이터를 기준으로 VOD의 점수를 계산하는 행렬이 됩니다. m, n보다 작은 k 차원으로의 변환이 이루어지기 때문에, 이 과정은 주성분 분석(principal component analysis)이나 데이터 추상화를 도입한 것과 비슷한 효과가 있습니다.

그렇다면, 이것이 VOD 추천에는 어떻게 쓰일 수 있을까요? 실제로 사용자는 모든 VOD는커녕 아주 일부분의 VOD에 대해서만 점수를 매기기 때문에, 행렬 A의 일부분에만 사용자가 정한 점수가 부여되고, 대부분의 값은 정해지지 않은(그래서 추정해야 하는) 상태가 됩니다. 이때 행렬 A에 대해서 SVD를 수행하면서 사용자가 점수를 부여해서 이미 알고 있는 값(Training Data)만 맞아 들어가도록 행렬 U, V를 찾아낸 다음, 그 두 행렬의 곱으로 행렬 A를 복원하면, 사용자가 점수를 매기지 않았던 곳(그래서 추정해야 하는 Test Data)의 VOD 점수 또한 U, V의 곱에 의하여 값을 가지게 되고, 그 값은 Training Data와 비슷한 경향을 가지게 됩니다.

E = || A – U V || 라고 하면, U, V를 곱해서 정확히 A가 나오면 E는 0이 되겠지요. 이제 E 값이 0에 가까워지도록 U, V를 찾아내면 됩니다. (단 이때 행렬 A의 값 중에서 Training Data에 있는 점수에 대해서만 U V 곱과의 차이 값을 구하고, 그 외의 값에 대해서는 정해진 바가 없으니 차이 값을 구하지 않고 무시합니다)

E의 그레디언트(gradient)를 구해서 E가 작아지는 방향을 찾은 후 그 방향으로 U, V값을 변경해서 E의 값을 줄여갈 수 있습니다. 경사 하강법(Gradient Descent)이라고 알려진 유명한 방식입니다.

그런데 추정해야 하는 U, V의 변수 가짓수보다 의미 있는 데이터의 수가 크지 않으면, U, V가 전혀 예상하지 못한 값으로 수렴할 수 있는데 (과적합 overfitting) 이를 막기 위해서 U, V 행렬에 대한 조건을 추가합니다.

E = || A – U V|| + lambda1  || U || + lambda2 || V ||

이렇게 하면 U와 V를 구성하는 변수의 절댓값이 커질수록 E의 값이 커지기 때문에, E 값을 줄이는 것을 통해서, 곱해서 A가 되는 U, V를 추정함과 동시에 변수의 절댓값이 작아지도록 만들 수 있습니다. 베이지안 추정에서는 추정하고자 하는 변수에 대한 사전 지식을 반영할 때, 각 변수가 평균이 0인 정규 분포를 가지고 있다고 종종 가정하는데, 그 부분을 그대로 에너지 함수로 나타내면 위와 같은 모양의 식이 나오게 됩니다.

다만 위와 같이 하게 되면 lambda1와 lambda2 에 따라서 U, V의 값이 달라지고, 반복적인 테스트를 통해서 최적 lambda를 찾아내야 해서 많은 시간이 걸리게 되겠지요. 적당한 값, 예를 들어 lambda1 = lambda2 = 1/2 정도의 수준에서 어느 정도 근접한 값이 추정되기를 기대하면서 시작할 수밖에 없었습니다.

그런데 이 방법을 적용해 보다가, Netflix 대회문제와 같이 주로 VOD 평가에 기초하여 VOD 추천 하는 방식과 이번 대회문제 사이에 한 가지 큰 차이점이 있다는 것을 발견했습니다.

VOD 평가에 기반을 두는 경우에는 사용자가 매긴 VOD의 점수가, 예를 들어 별점 1 ~ 5까지, 다양하게 존재하게 됩니다. 즉, Training Data에는 사용자가 좋아하는 것에 대한 기록도 있고 싫어하는 것에 대한 기록도 있어서, 실제 데이터는 사용자가 좋아하는 것 / 싫어하는 것 / 아직 좋아하는지 싫어하는지 모르는 것의 3종류가 있지만, VOD를 구매한 기록만 존재하는 이번 문제의 경우에는 아마도 좋아했기 때문에 산 것(가끔은 안 좋아하는 것인데 산 것일 수도 있지요) / 아직 좋아하는지 싫어하는지 모르는 것의 2 종류만 존재하게 되는 것이죠. 행렬 표현 방식으로 돌아오면, 사용자가 산 것을 1이라고 하면 Training data에는 사용자가 구매한 이력밖에 없으니 (사용자, VOD)에 할당된 숫자가 모두 1이 됩니다. 곱해서 A가 되는 행렬 U, V를 추정할 때에도, 곱했을 때 모든 값이 1이 나오도록 추정해 버리면, Training data에 대해서는 정확도 100%가 나오고 Test 데이터에 대해서는 0%에 근접한 정확도가 나오는 처참한 상황이 예상되었습니다.

그래서 방향을 조금 바꾸었습니다. 사용자가 VOD를 구매한 경우에는 1을, 구매하지 않은 경우에도 값을 정하지 않는 것이 아니라 0을 행렬 A에 할당한 다음, 곱해서 A가 나오는 U, V를 추정하기로 한 것입니다.

우선, Training Data에 해당하는 행렬 내 원소만 고려해서 E를 계산하는 것이 아니라 행렬 전체에 대해서 U, V를 추정하는 문제가 되기 때문에, 각종 수학 라이브러리에서 SVD를 하는 방식과 완전히 같게 됩니다. 그런 행렬 라이브러리는 아마도 여기저기에 있을 테고, 잘 만들어졌을 테고, 빠를 테니까 시간 내에 해답을 찾기가 훨씬 수월할 것으로 생각했습니다.

그리고 사용자가 그 많은 VOD를 다 볼 리가 없고, 극히 일부분만 볼 것이므로, 아직 구매하지 않은 VOD에 대해서 구매자가 그 이후에도 구매하지 않을 것이라는 의미인 0을 할당하는 것이 실제 상황과 큰 차이가 나지는 않을 것이라 예상했습니다.

하지만 주의할 것은 k 값의 설정이었는데요. k 값이 충분히 커서 U, V의 곱으로 A를 거의 완전히 복원하게 되면, Training Data에서 사용자가 보지 않은 VOD를 모두 앞으로도 보지 않을 VOD로 추정하게 되기 때문에, 너무 크지 않은 k값을 찾아내는 것이 중요했습니다. 반대로 k 값이 너무 작으면, U, V의 곱으로 A를 표현하기가 매우 어려워지기 때문에 여러 k 값에 대한 테스트가 필요했습니다.

결국, k = 1부터 하나씩 크게 적용을 해서 그 중에서 가장 높은 점수를 기록하는 것을 선택하기로 했습니다. 예상하기에 k 값이 증가하면서 점수 또한 계속 증가하다가 어느 순간부터 작아지는 지점이 있을 것이고 그 즈음에서 테스트를 멈추는 것으로 계획을 세웠습니다.

대회에서는 하루에 3회만 제출할 수 있었기 때문에, Training Data를 다시 둘로 나누어서 2014년 9월부터 2015년 1월까지의 데이터를 Training Data로 2015년 2월 데이터를 Validation Data로 놓고 Validation Data에서 구한 점수를 기준으로 반복적인 테스트를 했습니다.

그런데 예상과는 다르게, k = 1에서 가장 좋은 값이 나오고, 2~5로 갈수록 점수가 계속 낮아지더군요. 좀 더 큰 k 값에 대해서 테스트해보고 싶었지만, 노트북이라서 그런지 이미 k = 5에 대한 SVD를 수행하는 데에만 수 시간이 걸렸습니다. 그래서 그보다 더 큰 값에 대하여 테스트를 진행할 수는 없었습니다.

다행히 k = 1 이라는 조금은 황당 값으로 추정했는데도 어느 정도 점수가 나와준 것 같습니다.

후기

마침 문제가 공개될 즈음에 torch7을 가지고 이런저런 이미지 인식 문제를 풀고 있었기 때문에, 혹시 시간이 되면 딥 러닝으로 풀어볼 수도 있지 않을까 생각했는데, 허용 프로그래밍 언어 중에 lua가 없더군요. Python theano는 저에게는 아직 생소했고, 새로 익혀서 풀이를 완성하는 데는 시간이 오래 걸릴까 봐 문제 해결 방법에서 제외하고 쉬운 방향으로만 접근했던 것이 개인적인 아쉬움으로 남습니다. 문제에서 제공하는 VOD의 여러 가지 특징을 하나도 활용하지 못했던 것도 아쉽습니다. 혹시 테스트 데이터가 공개되면, 다양한 방법으로 풀이하고 성능을 테스트할 수 있을 것 같습니다.

마지막으로, 좋은 기회를 만들어주신 대회 운영자와 관계자 분들께 감사 드립니다. 앞으로도 많은 개발자가 도전하고 즐길 수 있는 행사가 되기를 희망합니다. 감사합니다.

김대환

카이스트에서 컴퓨터과학을 공부했습니다. 기계학습에 관심이 많습니다.

공유하기