Matrix Factorization

분야

Recommendation System

리뷰 날짜

2021/04/01

본 포스트는 제가 휴먼스케이프 기술 블로그에 먼저 작성하고 옮긴 포스트입니다.

본 포스트에서는 Netfilx 에서도 활용하고 있는, 딥러닝을 활용한 추천 시스템인 Matrix Factorization 을 소개한 논문에 대해서 리뷰하려고 합니다. 리뷰하려는 논문의 제목은 다음과 같습니다.

“Matrix Factorization Techniques For Recommender Systems”

논문에 대한 내용을 직접 보시고 싶으신 분은 이곳을 참고하시면 좋습니다.

Objective

논문의 배경은 Netflix Prize Competition 에서부터 시작됩니다.

Netflix Prize Competition 은 Netflix 가 2006년부터 개최하고 있는 대회입니다. Netflix 는 이 대회를 위해 50만명의 사용자가 17000 개의 영상에 대해서 매긴 1억 개의 평가들(별점)에 대한 데이터를 제공했습니다.

Netflix 가 그들의 수많은 데이터를 제공하면서까지 원했던 것은 그들이 가지고 있는 Recommender System 보다 RMSE 측면에서 좋은 성능을 보이는 방법론입니다. 심지어 RMSE 가10% 이상 개선된 방법론에 대해서 100만 달러를 지급하기로 했고, 그런 방법론이 존재하지 않았다면 가장 큰 개선을 이룬 팀에게 5만 달러를 지급하기로 했습니다.

지금부터 소개할 논문은 2007년에 8.43% 의 개선으로 1위를 차지하고 2008년 9.46% 의 개선으로 1위를 차지한 팀의 방법론에 대한 내용을 담고 있습니다.

Background

기존의 recommender system 은 크게 두 가지, Content Filtering 과 Collaborative Filtering 으로 나누어집니다.

Content Filtering

먼저, Content Filtering 은 가장 기본적인 recommender system 으로 소개된 친구입니다. Content Filtering 의 핵심은 product 의 profile 을 만드는 것입니다.

이렇게 설명하면 엥 이게 무슨 소리지…??? 하실 분들을 위해 부연 설명을 드리자면, user 와 product 의 특징을 만들고, user 가 좋아할만한 특징을 가진 product 를 찾아낸다고 보시면 됩니다.

위 글귀가 혹시라도 이해되지 않는 분들을 위해 예시를 들어보려고 합니다. 이해가 되셨다면 넘어가셔도 좋습니다 :)product 를 영화로 생각해봅시다.product 의 profile 은 영화의 장르, 영화에 참여한 배우 목록, 박스 오피스 순위와 같은 영화의 정보라고 보시면 됩니다.

이런 profile 들을 사용해서 user 가 과거에 선호했던 product 의 profile 을 바탕으로 비슷한 profile 을 가지는 product 를 연관지어 추천을 하게 되는 것입니다.

그런데, Content Filtering 은 한 가지 큰 문제점이 있습니다. Product 의 명시적인 profile 을 작성하는 것이 상당히 귀찮고 어려운 일이라는 점입니다. 더불어 어떤 profile 을 작성해야 높은 만족도의 추천을 할 수 있는지에 대해서도 모호합니다.

Collaborative Filtering

위에서 설명드린 Content Filtering 의 문제점에 대한 대안책으로 등장한 것이 Collaborative Filtering 입니다. Collaborative Filtering 은 product 의 명시적인 profile 을 작성할 필요가 없습니다. 대신, user 간의 관계와 user-product 간의 상호 의존성을 분석하여 새로운 user-product 간의 관계를 밝혀냅니다.

또 이렇게 설명하면 엥 이게 무슨 소리지…??? 하실 분들을 위해 부연 설명을 드리자면, user 간의 유사도를 측정하고, 유사한 user 가 기존 user 입장에서 새로이 맞이하는 product 에 대해서 평가한 내용을 바탕으로 추천의 척도를 결정한다는 것입니다. 유사한 user 가 product 에 대해서 좋은 평가를 했다면, user 간 관계가 유사하기 때문에 기존 user 도 좋은 평가를 할 가능성이 높다고 보고 추천을 한다는 것입니다.

다시 또 예시를 들려고 합니다. 이 예시는 위 글귀를 이해하셨어도 봐주세요!!product 를 영화로 생각해봅시다.user1 이랑 user2 는 영화 취향이 잘 맞는 절친입니다. 세부적으로, user1 이 스릴러 영화 1을 좋아할 때 user2 도 스릴러 영화 1을 좋아했고, user1 이 스릴러 영화 2를 좋아할 때 user2 도 스릴러 영화 2를 좋아했습니다. 이렇게 같이 좋아한 스릴러 영화가 100개도 넘습니다.user1이 근데 갑자기 로맨스 영화 1을 좋아한다고 평가했습니다. 이 때 추천 시스템은 user1 과 user2 를 유사한 취향의 사람으로 보고 로맨스 영화 1을 아직 보지 않은 user2 에게 추천해 주는 것입니다.

위 예시에서 드러나기도 한 Collaborative Filtering 의 장점은 domain-free 하다는 점입니다. Domain-free 함은 product 의 세부적인 특징(앞서 설명한 profile 로도 표현할 수 있겠네요)에 대해서 알 필요가 없다는 점입니다. 그 만큼 profiling 하기 어려운 데이터 양상도 추천 시스템이 캐치하고 올바른 추천을 해 줄 수 있다는 것입니다.

예시에서 뜬금없이 로맨스 영화를 등장시켰었는데요,그 이유가 Collaborative Filtering 을 이용한 추천이 profiling 하기 어려운 데이터도 다룰 수 있음을 알려드리기 위함이었습니다.product 의 profile 내에 "장르" 가 들어갈 것이지만, "장르" 로는 추천을 하지 못했던 user 의 세부 선호 특성을 Collaborative Filtering 이 추천을 해줄 수 있었던 것입니다.극단적으로는, Collaborative Filtering 이 캐치한 product 의 profile 이 "영화의 후반부에 여주인공이 안타깝게 생을 마감한 이후 각성한 남주인공이 악당이 되어버리는 스토리" 일 수도 있는데 이런 표현하기도 어려운 특징들을 다룰 수 있다는 것입니다.

지금까지 Collaborative Filtering 이 무엇이고, Content Filtering 에 비해서 가지는 장점이 무엇인가에 대해서 알아보았습니다. 지금부터는 논문에서 제시하는 방법론과 조금 더 가까워지기 위해 Collaborative Filtering 의 세부적인 방법에 대해서 설명드리려고 합니다.

Collaborative Filtering — Neighborhoods Method

Collaborative Filtering 의 첫 번째 방법, Neighborhoods Method는 앞서 설명한 Collaborative Filtering 의 설명과 크게 다르지 않습니다.

다만 앞에서는 user 의 유사도에 대해서 초점을 맞추고 유사한 user 의 선호도에 따른 추천을 진행하는 User-Oriented Neighborhood Method 를 소개했었는데, 반대로 user 의 선호도가 유사한 product 를 찾아서 그 product 에 대한 본인의 선호도로 추천을 진행하는 Product-Oriented Neighborhood Method 도 있다는 점만 추가로 언급드리면 될 것 같습니다.

User-Oriented Neighborhood Method

위 그림은 User-Oriented Neighborhood Method 를 나타낸 그림입니다. 그림의 가장 좌측에 있는 Joe 가 좋아하는 세 개의 영화를 좋아하는 다른 user 세 명을 찾아서 그들이 또 좋아하는 다른 영화들을 Joe 에게 추천을 하는 형태입니다.

Collaborative Filtering — Latent Factor Models

Collaborative Filtering 의 두번째 방법, Latent Factor Models 는 앞서 유사도라고 표현했던 요소를 user 와 product 모두에서 직접적인 Latent Factor (잠재요인)으로 뽑아내어 특정 유저가 특정 product 와 가까운 정도를 측정하는 방법입니다.

Latent Factor Models

이 Latent Factor (잠재요인)라는 친구를 설명하기 위해 위 그림을 살짝 이용해보려고 합니다.

위 그림의 x 축은 남성을 타겟으로 한 영화인지, 여성을 타겟으로 한 영화인지에 따른 분류 기준선이며, y 축은 현실적인지, 비현실적인지에 따른 분류 기준선으로 볼 수 있습니다. 영화의 경우에는 좌표평면에서 해당 분류에 따라 배치 되어 있고, 사람의 경우에는 좌표평면에서 분류에 따른 영화를 얼마나 좋아하는지에 따라 배치 되어 있습니다.

당연하게도, 영화와 사람의 거리가 가까울 수록 사람이 좋아하는 영화라서 좋은 평가를 내겠죠??

놀라운 점은 이 좋은 평가의 정도를 영화와 사람의 좌표의 dot product 로 수치화하여 표현할 수 있다는 점입니다. Gus 의 경우에는 Dumb and Dumber 와의 dot product 는 큰 것에 비해 The Color Purple 과의 dot product 는 작은 것을 확인할 수 있죠.

다만, 여기서 한 가지 의문을 품으실 수 있습니다.

“아니 영화는 저런 분류로 구분할 수 있다 쳐도, 사람을 어떻게 저런 기준선에 배치해???”

이런 생각이 드셨다면 상당히 잘 이해하고 계신 것입니다. 이런 의문점을 해결해주는 것이 논문에서 제시하는 방법론 Matrix Factorization 입니다.

Matrix Factorization

Matrix Factorization 은 Latent Factor Models 의 가장 성공적인 구현이라고도 불립니다.

하지만, 위의 수식어가 붙은 것 치고는 상당히 간단한 개념입니다.

한 마디로 설명하자면, Latent Factor Models 에서 Latent Factor (잠재요인)으로 불렸던 친구들을 딥러닝을 사용해 학습을 시키는 방법입니다.

바로 의문이 풀리셨죠??

사람을 기준선에 배치하는 것은 저희가 할 일이 아니라 딥러닝 모델이 사람이 명시적/비명시적으로 표출한 선호도를 바탕으로 저희가 알 수 없는 잠재요인을 찾아서 “알아서" 배치해줌으로써 해결한 것입니다.

즉, recommendation 도 Latent Factor Models 에서 진행했던 것과 다르지 않습니다. User 의 Latent Factor 와 product 의 Latent Factor 간의 dot product 로 계산합니다. 이를 수식으로 나타내면 다음과 같습니다.

\hat{r}_{ui}=q_i^Tp_u

r_ui hat 은 inferred recommendation 이고, q_i 는 item(지금까지는 product 로 설명해왔던 그 것입니다.)의 Latent Factor 이고, p_u 는 user 의 Latent Factor 입니다.

여기서 선형대수학을 공부해보신 분이라면 ground truth 인 recommendation 으로부터 반대로 q_i 와 p_u 를 구해내면 되지 않을까? 하는 생각에 EVD, SVD 등의 방법 등을 생각해볼 수 있습니다.하지만 item 은 많은데 user 의 rating 은 적기 때문에 recommendation matrix 가 sparse 하고, 이 때문에 decomposition 을 통해 역으로 Latent Factor 를 구하는 것은 무리가 있습니다

Inferred recommendation 이 위와 같은 형태이면, 저희는 SSE with regularization term 을 아래와 같이 쓸 수 있다는 것을 너무나도 잘 알고 있습니다. 그리고 이를 최소화 하는 것이 학습의 목표가 될 것이라는 것도 아시겠죠..!

\min_{q^*,p^*}\sum_{(u,i)\in K}(r_{ui}-q_i^Tp_u)^2+\lambda(\left|| q_i|\right|^2+\left|| p_u|\right|^2)

혹시나 SSE 가 무엇인지 모르실 분들을 위해...Sum Squared Error 로, 오차의 제곱의 합이라고 보시면 됩니다.더불어 regularization 이 무엇인지 모르실 분들을 위해...Overfitting 을 막는 방법 중 하나로, 학습될 weight를 loss 에 추가로 포함시킴으로써 training data 에만 정확히 맞아떨어지는 형태로 학습되는 것을 방지하고 일반적인 양상에 맞아떨어지는 형태로 학습되게 하는 친구입니다. Lambda 는 그 정도를 조절하는 요소로 보시면 됩니다.

여기까지 하면 Matrix Factorization 의 개괄적인 내용에 대해서는 전부 다루었습니다. 논문에서는 Matrix Factorization 의 5가지 개선 방법에 대해서도 설명을 하고 있습니다. 지금부터는 그 내용에 대해서 소개드리려고 합니다.

Improvement — Learning Algorithms

Deep Learning 의 optimization algorithm 중에 SGD(Stochastic Gradient Descent) 라는 친구가 있습니다.

SGD 에 대해서 자세히 알아보고 싶으신 분은 제가 이전에 작성했던 포스트를 참고하시면 좋을 것 같습니다. 여기서는 SGD 가 하나의 training dataset 에 대해서 한 번의 update 를 진행한다는 점만 짚고 넘어가려고 합니다.

SGD 를 사용하여 q_i 와 p_u 를 update 하는 과정은 다음과 같습니다.

e_{ui} \overset{\underset{\mathrm{def}}{}}{=}r_{ui}-q_i^Tp_u

위 식은 error 를 나타낸 것이고,

q_i\gets q_i+\gamma\cdot(e_{ui}\cdot p_u-\gamma\cdot q_i)\\ p_u\gets p_u+\gamma\cdot(e_{ui}\cdot q_i-\lambda\cdot p_u)

위 식은 Loss function 을 각각 q_i, p_u 에 대해서 편미분한 값이 괄호 안에 들어 있는 친구의 2배인 값이기 때문에, 2 를 포함해서 상수배만큼을 gamma 로 치환해서 작성한 update 식입니다.

그런데, 여기서 기가막힌 개선 방안이 하나 있습니다.

p_i, q_u 중 하나를 고정하면 gradient descent 를 사용하지 않더라도 loss function 이 quadratic 이 되어 최소로 만드는 값을 계산하여 구해낼 수 있지 않을까?

위 생각을 실현 한 것이 논문에서 제시한 ALS (Alternating Least Squares)입니다.

위 생각대로 하나를 고정하고 하나를 update 하는 과정을 번갈아가면서 수렴이라고 판단되는 지점까지 반복하는 것이 ALS 의 핵심입니다. 다만, 제가 설명하는 도중에 느끼셨겠지만 동시에 update 되는 SGD 에 비해서는 속도가 느립니다.

그럼에도 ALS 가 선호되는 상황이 크게 두 가지 경우가 있다고 합니다.

Parallelization 이 가능할 때 ALS 는 다른 item 의 q_i 를, 다른 user 의 p_u 를 병렬적으로 계산해낼 수 있기 때문에 빠른 연산이 가능합니다.

Recommendation System 이 implicit data 에 중점적인 판단을 해야할 경우, ground truth data 가 sparse 하지 않기 때문에 SGD 사용 시 연산량이 많아지는 단점이 있다고 합니다.

ALS 사용을 적절하게 고려해보는 것이, 논문에서 제시한 첫 번째 개선 방법입니다.

Improvement — Adding Biases

앞서 Matrix Factorization 세션에서 설명드렸던 loss function 의 경우에는 수식 설계가 user-item 간의 interaction 에 초점을 맞추어 학습을 하려고 했다는 것을 알 수 있습니다.

즉, user 자체, item 자체가 rating value 에 미치는 variation 에 대한 고려가 이루어지지 않은 loss function 설계라고 볼 수 있습니다.

user1 이 다른 유저들에 비해서 원래 평가를 후하게 하는 스타일인 경우, item1 이 다른 item에 비해서 기본적으로 평가가 좋은 item 인 경우에 대한 고려가 이루어지지 않았다는 점을 개선하려고 하는 것입니다.

이를 개선하기 위해 개별 user, 개별 item 이 가지는 bias term 을 추가하는 개선사항을 제시합니다.

b_{ui}=\mu+b_i+b_u

총 bias 는 위와 같이 item 의 bias b_i 와 user 의 bias b_u 에 모든 user 의 모든 item 에 대한 평균적인 평가 mu 를 더한 값으로 설정했습니다.

\hat{r}_{ui}=\mu+b_i+b_u+q_i^Tp_u

그리고, 논문에서는 이를 inferred recommendation 에 반영하는 형태로 개선을 진행할 수 있다고 제시했고, 이 것이 두 번째 개선 방법입니다.

Improvement — Additional Input Sources

앞서 이야기했던 user 의 rating 은 explicit 한 rating 에 한정되었습니다. 하지만, user 가 implicit 하게 system 에 주는 feedback 도 있고, 논문에서는 이를 활용하여 개선을 진행했습니다.

|N(u)|^{-0.5}\sum_{i\in N(u)}x_i

N(u) 를 user u 가 implicit feedback 을 표현한 item 의 집합이라고 하고, x_i 가 그 item 에 준 feedback 이라고 했을 때 이를 학습에 반영하는 것을 제시합니다. 이 때, 논문에서는 편향된 feedback 이 들어가는 것을 방지하기 위해 normalize 된 위와 같은 형태로 loss function 에 반영하는 것을 설계했습니다.

\sum_{a\in A(u)} y_a

A(u) 를 user 의 gender, age group, zip code, income level 과 같은 요소의 집합이라고 하고, y_a 가 그 요소가 준 feedback 이라고 했을 때 이 또한 학습에 반영하는 것을 제시합니다.

\hat{r}_{ui}=\mu+b_i+b_u+q_i^T[p_u+|N(u)|^{-0.5}\sum_{i\in N(u)}x_i+\sum_{a\in A(u)} y_a]

그렇게 최종적으로 inferred recommendation 를 위와 같은 형태로 바꾸는 것이 논문에서 제시한 세 번째 개선 방법입니다.

Improvement — Temporal Dynamics

지금까지 이야기 했던 System 은 정적이었습니다. 다른 말로 표현하면 시간과는 무관한 요소들로 설계를 진행했었습니다.

하지만, 실제 user 의 성향은 시간이 지남에 따라 지속적으로 변화하고, item 의 유행이나 인식, 선호도 또한 시간에 따라서 동적으로 변화합니다.

이 때문에 논문에서는 recommender system 이 dynamic, time-drifting effect 에 대해서 다룰 필요성이 있다고 판단했고 해당 사항에 대한 개선책을 제시합니다.

이에 따라 시간에 대한 함수로 변화해야 할 값들로 b_i, b_u, p_u 를 제시합니다.

각각에 대한 예시를 들자면,b_i 는 다른 영화에 등장한 배우에 따라서 실시간으로 item 의 bias 선호도가 달라지는 현상 등이 있을 수 있고,b_u 는 user 가 나이를 들면서 평균적으로 관대하거나 엄격해지는 현상 등이 있을 수 있고,p_u 는 user 가 스릴러 영화를 좋아하다가 선호도가 로맨스 영화로 달라지는 현상 등이 있을 수 있습니다.

\hat{r}_{ui}(t)=\mu+b_i(t)+b_u(t)+q_i^Tp_u(t)

그렇게 최종적으로 inferred recommendation 를 위와 같은 형태로 바꾸는 것이 논문에서 제시한 네번째 개선 방법입니다.

Improvement —Varying Confidence Levels

마지막으로 논문에서 제시한 개선점은 관측된 user 의 rating 에 대한 신뢰도가 모두 일정하게 비슷하거나 같은 수준이라고 보장할 수 없다는 것입니다.

예시로 과대 광고를 통해서 특정 item 에 대해서 좋은 rating 을 보이는 현상이 발생했다면, 이는 일시적인 현상으로 보아야 하고, 신뢰도가 낮으며, Latent Factor 로 보기에는 무리가 있다는 것입니다.또한, recommender system 이 implicit feedback 이 주된 요소로 구성되어 있을 때 이들에 대한 신뢰도를 정량화할 필요성이 있다고 본 것입니다.

이를 개선하기 위해 논문에서는 추론한 error 에 confidence score 라는 값을 붙여서 신뢰도에 따른 loss function 에 대한 기여도를 차별화했습니다.

\min_{p^*,q^*,b^*}\sum_{(u,i)\in K}c_{ui}(r_{ui}-\mu-b_u-b_i-p_u^Tq_i)^2+\lambda(\left|| q_i|\right|^2+\left|| p_u|\right|^2+b_u^2+b_i^2)

논문에서는 위와 같은 형태로 loss function 을 변경하는 것을 마지막 개선점으로 제시했고 이를 통해 부가적으로 confidence score 가 action 에 대한 frequency 를 묘사하는 척도로도 사용될 수 있다고 제시해주었습니다.

Result

지금까지 Matrix Factorization 과 그 개선방향에 대해서 살펴보았습니다.

논문에서는 제가 이 포스트의 제일 처음에서 설명한 것처럼 Netflix Prize Competition 에 참가하여 1위를 한 이력이 있고, 그 결과에 대해서 설명을 합니다.

위 그림은 결과로 얻어낸 영화들의 Latent Factor 들 중 두 개를 뽑아 그 둘을 x, y 축으로 하여 영화들을 plotting 한 것입니다.

이를 반대로 해석해보면 상당히 재미있는 결과가 나옵니다.

x 축은 좌측으로 갈 수록 남성/청소년을 겨냥한 교양이 부족한 코미디류로, 우측으로 갈 수록 여성이 중심이 된 진지한 배경을 가진 드라마/코미디류로 볼 수 있으며,

y 축은 위쪽으로 갈 수록 독립적이며, 평론가에 호평을 받은 기발한 영화들로, 아래쪽으로 갈수록 주류 영화로 볼 수 있었습니다.

그래서인지 좌측 상단의 영화들은 인디 영화와 교양 없는 분위기의 영화가 섞인 영화들이 위치했고, 우측 하단의 영화들은 여성 중심의 진지한 주류 영화가 위치했습니다.

더불어 Annie Hall, Citizen Kane 과 같은 영화는 겉보기에 스타일이 많이 다른데 비슷한 위치에 있어 의아할 수 있는데 실제로 이들은 세 번째 Factor 로 인해서 분리가 된다고 합니다.

위 그림은 Matrix Factorization 의 개선방향을 직접 적용해 본 뒤 측정한 RMSE 에 대한 것입니다.

이를 해석하면,

학습을 위한 Parameter 증가,

Bias 항목의 고려,

Implicit feedback 항목의 고려,

Temporal Dynamics 항목의 고려

가 실제로도 RMSE 를 줄일 수 있었다는 것을 보여줍니다.

Conclusion

이것으로 논문 “Matrix Factorization Techniques For Recommender Systems” 의 내용을 간단하게 요약해보았습니다.

추천 시스템에 대해서 간단히 collaborative filtering 정도만 알고 있었는데, 이 논문이 비록 오래되었지만, 추천 시스템의 전반적인 발전에 대해서 이해하기에는 굉장히 큰 도움이 되었던 것 같습니다.

처음에는 YouTube 의 추천 시스템에 대한 논문을 읽으려고 했었는데 선행 지식이 많이 부족하다고 생각되어 그 이전의 논문을 찾아 읽어보았습니다. 생각보다 많은 지식을 알게되어 나름 만족도가 높은 논문이었던 것 같습니다. 기회가 된다면 다시 YouTube 의 추천 시스템을 정복하러 도전해보아야겠습니다. 여러분들께도 이 포스트를 충분히 숙지하신 뒤 한 번 도전해보시는 것을 추천해봅니다.