Matrix Factorization

Matrix Factorization techniques for recommendation systems

https://datajobs.com/data-science-repo/Recommender-Systems-[Netflix].pdf

 

Intro

오늘은 2009년에 나온, 추천 논문을 하나 분석하고자 한다.

최근에 추천 모델 공부를 주로 하였는데, 모델 뿐 아니라 데이터를 다루는 공부를 더 하고자 하여 kaggle을 하나 파고 있다. 그래서 그 과정에서 이전에 공부했던 여러 테크닉들을 정리하고자 하는데, 가장 대표적인 collaborative filtering 방식인 matrix factorization에 대해 복기하고 기록하고자 대표적인 이 논문을 읽어보고자 한다.

요즘 어딜가든 나오는 말이 있다. 개인화. 특정 개인에게 맞춘 맞춤 서비스를 제공하고자 하는 여러 기업들이 늘고, 그러한 서비스에 대한 수요가 늘면서 항상 나오는 말이다. 누구나 자신은 특별한 대우를 받고 싶을 것이고, 이러한 생각에서 점점 수요가 늘고, 정말 다양한 개인화 서비스가 나오고 있다. 개인 성향에 따른 여행 계획을 짜준다거나, 개인에 맞는 샐러드 배달 서비스 같이 말이다.(실제로 있는 서비스들이다.)

이러한 개인화에는 공통적으로 개인이 가진 특성을 보고 비슷한, 잘 맞는 서비스를 찾아주는 추천/매칭 시스템이 필수적이기에, 해당 분야 연구가 굉장히 활발하게 이루어지고 있다. 이 논문은 2009년에 나왔는데, 지금은 더 활황이지 않은가.

 

Classic Recommendation System

고전 추천 시스템으로는 두 가지 전략이 있었는데, 하나는 Content Filtering으로 각 개인의 프로필을 만들어, 프로필 정보들을 바탕으로 맞는 아이템 특성을 매칭시켜준다. 이는 유저가 직접 기록한 정보,자신의 특성들을 기초하여 매칭하기에 비교적 쉬우나 "직접"기록한 정보가 필요하므로 많은 데이터를 모으기 어렵다는 단점이 있다.

그래서 많은 데이터들을 다루기 위해선 다른 방법을 써야 하는데, 이것이 Collaborative Filtering 방법이다. 이 방법은 실제 프로필 대신, 유저의 사용 기록이나 댓글, 평점과 같이 비교적 모으기 쉬운 implicit 정보들을 통해 아이템을 추천한다. 이 방법은 유저가 귀찮게 자신의 특징/선호를 기록할 필요가 없이 추천이 가능하나, 오로지 사용 기록 등을 통해 추천하기에 신규유저/기록이 없는 유저들에게는 추천을 하기 어려운 문제가 생긴다. (흔히들 Cold-start 문제라고 한다.)

Collaborative filtering은 또 두 가지로 나뉘는데, 하나가 위 그림에서 나오는 Neighborhood method이다. 간단히 item 간 혹은 user 간 관계 하나에 집중하여, 한 유저가 두 영화에 비슷한 rating을 주었다면 이웃 item으로 보고, 다른 유저가 한 영화를 보았을 때 이웃 영화를 추천해주는, 간단한 방식이다.

하지만 이 방법은 하나의 관계에서만 이웃을 찾기에, item/user간 복잡한 관계를 분석하기 어렵다. 예로 한사람은 장르때문에 영화를 봤는데 또다른사람은 배우때문에 보았다면, 단순히 많이 본 영화가 겹쳐서 추천을 하는 방법은 좋은 효과를 나타내기 어려울 것이다.

그래서 나온 것이 Latent vector method이다. 번역하면 숨겨진 벡터인데, 즉 item/user 내의 숨겨진 특성들을 벡터로 표현하여, 비슷한 벡터를 기반으로 추천을 하는 방법이다.

앞의 예시에선 단순히 본 영화가 겹쳐 추천을 했다면, 이젠 장르 벡터가 비슷한, 혹은 좋아하는 배우 벡터가 비슷한 유저의 영화를 추천한다는 것이다. 아래 그림을 보면 이해가 더 잘 될 것이다.

위 그림과 같이 각각 user, item(movie)에 대한 matrix가 있다면, 두 matrix의 dot product를 통해 서로 간의 연관성을 계산한다. 각 축 마다 어떤 특성을 선호/가지는지를 나타낸 것을 숨겨진 벡터로 이해하면 된다.

 

Matrix Factorization

이러한 방법을 사용할 때 가장 좋은 방법으로 쓰이는 것이 Matrix factorization이다. 이 방법의 장점은 특징 표현/기록이 없는 추가 정보에 대해서도 점수를 얻을 수 있고 정확도도 높다는 것이다.

단순히 설명하면 item 정보와 user 정보를 모두 하나의 특징 공간에 각각 매핑하여, 두 정보 행렬간의 dot product로써 user-item 관계를 얻고자하는 방법이다.

이렇게 얻은 dot product(r_hat)와 실제 item-user간 관계를 나타낸(rating과 같이) item-user 행렬(r)간의 오차를 줄이는, optimization 문제로써 추천 문제를 해결하는 방법이 matrix factorization이다.

이때 계산하는 u,i 집합은 기록된 rating들만 계산하여 최적화한다. (기록 안된 관계를 예측해야하므로)기록된 rating의 경우 보통 많지 않으니, (explicit rating 방법의 경우 훨씬 희소하다.) 행렬이 굉장히 sparse하기 때문에 regularization term을 추가한다.

 

Optimization

위와 같은 optimization 문제는 두 가지 방법을 풀게 되는데, SGD와 ALS이다.

SGD는 흔히 쓰이는 convex optimization문제 해결 방법으로, 식이 간단하고 빠르다.

ALS는 Alternating least squares의 준말로, 우리가 계산하는 item/user vector p,q는 unknown이기 때문에 사실 convex하다고 말할 수 없다. 하지만 둘 중 하나를 고정하게 되면 해당 식은 이차 방정식으로 볼 수 있어 optimal한 해를 구할 수 있게 된다.

그래서 위의 (2)식을 두번 계산하게 되는데, 따라서 parallel 계산이 가능할 때나, implicit data가 많을 경우에 SGD보다 이 방법을 선호하게 된다.

 

Additional Techniques

• Adding Bias

(2)식에서 우리가 계산하고자 한 것은 p와 q간의 관계, 즉 item과 user간의 관계를 계산하고자 했다. 하지만 어떤 user는 굉장히 긍정적으로 영화들을 평가하여, 전체적으로 높은 점수를 주었다면 어떤 user는 부정적으로 영화들을 평가하여, 평균적인 점수가 낮을 수 있다. 이러한 경우 item과 user간의 관계를 정확하게 계산하기는 (2)식만으로는 어려울 것이다.

그래서 (2)식을 다음과 같이 편향을 추가하여 계산하도록 한다. mu는 전체 rating, b_i,b_u는 item,user에 대한 편향이다.

• Adding more input sources

앞에서 말했듯이, Collaborative filtering 방법은 Cold-start라는 기록이 없는 유저에 대한 추천이 어려운 문제를 가진다. 이를 위해 implicit feedback과 같이 암시적인 기록들, 클릭, 검색기록과 같은 데이터를 활용하게 되는데, 이 정보를 정규화하여 input에 추가하여 사용하도록 하였다.

거기에 한술 더떠 암시적기록 앞에 있는, 기본적인 성별, 국적, 언어와 같은 기초 정보도 input에 추가하여 Cold-start를 해결하고자 했다. 곧 여기까지의 input은

가 된다. N(u)는 implicit feedback, A(u)는 앞에서말한 기초 정보 집합이라고 생각하면 된다.

• Handle temporal effect

앞서 보았던 최근 모델들은 모두 positional embedding을 중요시하여 여러 변형을 섞는 등, 추천에서 시간적 정보를 굉장히 중요시했다. 이러한 경향은 이때부터도 있었으며, 직관적으로도 10년전의 관심사가 오늘날까지 이어지는 경우는 거의 없고 매년 바뀜을 알 수 있을 것이다.

그래서 앞의 input i,u를 t에 관한 식으로 바꾸어 비슷한 시간대 끼리 관계를 해석하도록 바꾸었다.

• Confidence

Collaborative filtering은 Cold-start를 해결키 위해, 행렬 분해에서도 Implicit rating 방법을 쓰는 경우가 많다. 이 방법은 0과 1로 나뉘어, 보통 좋아할 것/좋아하지 않을 것으로 나눠 rating을 매기는데, 이 방법은 확실히 관심을 구분하기에 충분하지 않을 것이다.

그래서 도입된 것이 Confidence로, 신뢰도로 번역하면 이 평점이 얼마나 선호를 가지는가, 혹은 정말로 좋아할 것인가 같이 신뢰성을 나타내는 척도이다.

곧 특정 item을 자주 클릭하거나, 오래 시청하는 등의 행위로써 신뢰도를 정의하여 보다 정확한 관계 해석을 가능케 하는 것이 confidence인 것이다.

 

Conclusion

이 논문의 마지막에는 이 때 Netflix가 했던 추천 시스템에서 입상한 자신들의 모델을 소개한다. 예시로 두 가지 factor에 대한 축을 통해 item(영화)를 분류한 것을 보여주며, 장르가 비슷한 영화끼리 비슷한 point을 가짐을 보여준다. (비슷한 latent value)

오늘날에서도, 추천 시스템 설계에서 가장 중요한 것은 데이터를 이해하는 것이라 생각한다. 데이터가 얼마나 충분한 정보를 가지는가, 암시적인 정보량이 충분한가, 충분치 않다면 어떤 정보를 추가학습하여 보완할 수 있을까.(기본 정보나 또 다른 정보들.) 좀 더 나아가면 시간적 정보를 학습에 반영할 효과적인 방법, 가중치 조정 방법같은 것들이 있겠다.

이 논문은 실제 대회에서 모델을 만드셨던 분이 쓰셨는데, 그래서 어떻게 데이터를 해석하고, 어떻게 데이터의 결점을 보완하여 더 좋은 모델을 만들지 고민한 발자취를 따라갈 수 있어서 어떻게 보면 추천 시스템 설계의 첫 지침으로 좋은 것 같다.

나의 경우 몇 주전에 처음 이 논문을 접하게 되었고, 다양한 테크닉들(오늘날에도 중요하게 여기는)들이 많아 꼭 다시 정리하고 싶었다. 실제로 정리하니 정말 많은 기본 테크닉들이 있었다.

최근 convex optimization을 공부하는 터라, 이 다음으론 관련하여 심화적인 행렬 분해 방법을 공부해보려 한다. 기본 설명 및 내 생각들을 쓰느라 꽤 글이 길어졌는데, 여기서 끝!