내 마음을 훔치는 스포티파이 음악 추천 시스템 - 1

Recommendation System With LMF(Logistic Matrix Factorization)

최근 몇년동안 추천 시스템, 개인 맞춤화 시스템에 대한 수요가 급증하고 이에 따른 기술적 발전이 급격하게 이루어 지고 있죠.

수많은 알고리즘과 접근방법들에 대한 연구가 이루어지고 있는 가운데 글로벌 최대 음악 스트리밍 서비스사인 스포티파이의 음악 추천 시스템에 대해서 글을 써보고자 합니다 :D

참조 문서 를 바탕으로 작성한 글입니다.

최대한 초심자들을 대상으로 쉽게 쉽게 풀어 쓰는것이 최종 목표인 문서 입니다 ^^

Implicit or Explicit ?

추천 시스템은 우선 데이터를 필요로 합니다. 유저 정보에 대한 데이터, 특히 유저의 행동(Interaction) 데이터를 기반으로 학습을 시키고 유저 취향에 맞는 아이템이 추천되도록 유도합니다.

시스템에서 수집할 수 있는 Interaction 데이터는 2가지의 특성으로 나뉩니다.첫번째로 유저의 호불호가 확실하게 반영되는 데이터를 Explicit Feedback Data라 하는데,예를 들면 유저들의 구매내역, 아이템에 대한 평가 내역 등이 있을 수 있습니다.

Explicit Feedback Data은 아이템에 대한 User의 선호 시그널을 강력히 반영해 주므로 추천 시스템에 있어서 매우 귀중한 데이터 입니다. 하지만 그만큼 얻기 힘든 귀한 데이터이기도 합니다.

Explicit Feedback Data로 추천 모델을 만들지 않은 이유는 아마도 모든 유저들이 많은 아이템을 구매하거나, 댓글을 작성하는 슈퍼 유저들이 아니기도 하고, 가입한지 얼마 안된 유저들에게도 알맞은 추천을 해주어야 하기 때문이기 아닐까 생각합니다.

두번 째로 암시적인 유저들의 Interaction Data가 있는데 이를 Implicit Feedback Data 라 합니다.예를 들면 유저들의 아이템 조회 정보나, 아이템 시청 정보 등이 있습니다. 이를 Implicit 이라 하는 이유는 시청정보 만으로는 유저가 그 아이템을 좋아하는지 아닌지를 판별할 수 없기 때문입니다.

Spotify 에서는 이러한 특성을 가진 Implicit Feedback Data를 이용한 대용량 트래픽이 발생하는 서비스내에서의 추천 시스템을 완벽하게 구현해내었습니다.

Notation

$$\mathcal{U(i)} :\; A\;Group\;Of\;User\\ \mathcal{I(i)} :\; A\;Group\;Of\;Item\\ \mathcal{R(u,i)} :\; A\;Number\;Of\;Atrraction\;Of\;User\;i\; To\; Item\;i$$

대부분의 머신 러닝 모델들은 잡다한 수학식으로 이루어진 짬뽕요리인건 모두들 아실거라 생각합니다 ^^;

여기서 U는 유저 i에 대한 Factor Vector가 로우로 이루어진 행렬이고, I는 아이템 i에 대한 행렬입니다.

Factor Vector란 각 Feature들에대한 가중치를 가지고 있는 벡터인데, Factor 개수는 설정하기 나름입니다. 일반적으로 Factor 개수가 많으면 많을 수록 손실함수의 평가값은 낮아지는 경향이 있습니다. 물론 무작정 늘린다고 성능이 좋아 지지 않고, 계산 복잡도가 급격히 높아지므로 모델에 맞는 적정선의 Feature 개수를 설정하는 것도 모델을 구축하는 일중 매우 큰 비중을 차지 합니다.

R은 유저 i가 아이템 i에 대해 Interaction이 발생한 횟수를 가진 행렬 입니다. 만약 유저 A가 아이템 B을 2번 청취하였으면, 이에 대한 값은 2가 됩니다.

간단히 말해 Spotify의 Recommendation System은 아래 수식을 만족 시키는 U와 I행렬을 찾는 문제로 볼 수 있습니다.

$$\mathbf{U}\bullet\;\; \mathbf{I}^T =\;\mathbf{R}$$

따라서, 손실 함수는 대략적으로 아래와 같이 정의 될 수 있고, 이를 최소화 시키는 문제로 치환 됩니다.

$$L\;=\;\mathbf{U}\bullet\;\; \mathbf{I}^T -\;\mathbf{R}\;\\ Loss \;= \; \sum_{}\mathbf{L}(u,i)$$

물론 Loss 계산시 저 수식 그대로 계산하지는 않습니다. Loss가 양수일수도, 음수일수도 있어 단순히 합산하는 방법으로는 제대로 Loss를 구할수 없고, 많은 학습 편향들을 보정해주지 못하므로 Spotify는 MPR함수를 통해 Loss를 평가합니다.

또한 학습 성능을 이끌어 내기 위해 데이터 셋의 정규화를 진행하는 등 많은 수학적 기술들이 사용되고 있으나, 이번장에서는 간단히 컨셉을 설명하고자 최대한 단순화 하여 작성하였습니다.

예를 들어 유저 A,B,C가 있고, Feature로는 아이템에 대한 장르,발매지역,가수에 대한 가중치를 가지는 벡터로 설정한다면 U행렬은 아래와 같을수 있습니다.

$$\begin{Bmatrix} 0.9 & -0.8 & 0.7 \\ 0.3 & 0.3 & 0.4 \\ 0.6 & 0.1 & 0.3 \\ \end{Bmatrix}$$

위 행렬은 학습이 모두 완료된 상태라 가정한다면 A와 [ B,C ]는 2번째 Feature 에 대한 취향이 정반대라고 추론할 수 있습니다.

아이템 행렬 I는 아래와 같을 수 있습니다.

$$\begin{Bmatrix} 2 & -5 & 3 \\ 6 & 4 & 1 \\ 8 & 2 & 1 \\ \end{Bmatrix}$$

아이템 A,B,C 에대한 행렬입니다. B,C는 국내, A는 국외 음반이라 가정 합니다. 여기서는 발매지역을 국내/국외로 한정하기로 합니다. 학습된 결과, 유저행렬 U의 Row 벡터의 2번째 피쳐(발매지역)가 음수이면 국외 컨텐츠에 대한 Attraction 강도가 크다고 해석할 수 있습니다(음수*음수는 양수이므로).

R 은 아래와 같다고 한다면,

$$\begin{Bmatrix} 8 & 3 & 6 \\ 0 & 3 & 3 \\ 1 & 4 & 5 \\ \end{Bmatrix}$$

유저 A가 아이템 A,B,C에 대해 Attraction이 발생한 횟수는 8번,4번,6번 입니다. 모델의 적합도는 R과 $\mathbf{U}\bullet\;\; \mathbf{I}^T$ 의 차이가 적을 수록 높다고 볼 수 있습니다. 실제로 계산을 해보면,

$$\begin{Bmatrix} 0.9 & -0.8 & 0.7 \\ 0.3 & 0.3 & 0.4 \\ 0.6 & 0.1 & 0.3 \\ \end{Bmatrix} \bullet \begin{Bmatrix} 2 & -5 & 3 \\ 6 & 4 & 1 \\ 8 & 2 & 1 \\ \end{Bmatrix}^T \;= \; R'$$

이는,

$$\begin{Bmatrix} 0.9 & -0.8 & 0.7 \\ 0.3 & 0.3 & 0.4 \\ 0.6 & 0.1 & 0.3 \\ \end{Bmatrix} \bullet \begin{Bmatrix} 2 & 6 & 8 \\ -5 & 4 & 2 \\ 3 & 1 & 1 \\ \end{Bmatrix} \;= \; \begin{Bmatrix} 7.9 & 2.9 & 6.3 \\ 0.3 & 3.4 & 3.4 \\ 1.7 & 4.3 & 5.3 \\ \end{Bmatrix}$$

이고 R’과 R을 비교해 보았을때 거의 비슷하게 나오는 것을 확인할 수 있습니다. 학습이 매우 잘되었네요!

아래부터 설명할 Spotify의 Recommendation System의 알고리즘은 유저들의 Interaction Data들을 활용해 R행렬을 만들고, 이에 적합한 U행렬과 I행렬을 찾아가는 과정으로 축약 할수 있습니다. 실제로 위와 같이 적합한 수치들을 가진 U와 I행렬을 만드는 과정을 하나하나 짚어가보도록 하겠습니다.

대략적인 설명은 위와 같고, 아래 내용부터는 논문 그대로 수식을 옮겨 설명해 보도록 합니다 ㅎㅎ

Matrix Factorization ?

만약 각 유저에 대한 아이템 Interaction을 행렬로 표현한다면, 그 행렬은 거의 모든값이 0으로 채워져 있고 아주 드물게 값이 나타는 거대한 행렬이 될 것입니다. 전세계에 발매된 음원 수는 엄청나지만 한 개인이 듣는 음원 집합들은 아주 제한된 수를 갖기 때문이죠.

만약 그렇게 표현한다면 유저 3개에 대한 Interaction 행렬은 $N(item count)*3$ 의 크기를 갖게 될 것입니다. 표현되는 값들은 몇개 안되는 대부분이 0으로 채워져 가지고 있는 정보량에 비해 너무 많은 공간을 차지하게 될것입니다.

$$\begin{Bmatrix} 0&0&2&0& 0 &0 & ... & 0 & 0&1 & 0 \\ 0 & 3 & 0 &0 &0&0 & ... &1&0&0&0\\ 0&0&0&0&0&0&...&0 & 0 & 5&0 \\ \end{Bmatrix}$$

위와 같은 행렬을 Sparse Matrix라 하는데, 값들이 아주 드문드문 있다는 뜻입니다.

유저 1은 Item 3 을 2번, 유저2는 Item 2를 3번 듣고 그외의 아이템에 대해서는 거의 Interaction이 발생하지 않았습니다. 아무리 서비스를 활발히 이용하는 슈퍼 유저라도 모든 아이템들을 한번씩이라도 들어 보기는 물리적으로도 가능하지 않습니다. 평생을 노래만 들어도 전세계 모든 노래를 들어볼 수는 없으니까요.

이러한 문제를 해결하기 앞에서 설명했던 것과 같이, 위해 각 Feature에 대한 Factor값을 가진 User 행렬, Item행렬 2개로 분해해 표현함으로써 Sparse Matrix를 변환 시킬수 있습니다.

이러한 기법을 이용해, 메모리 공간도 절약하고, 학습 모델을 구현하기도 용이하게 되는 이점을 누릴 수 있는 것입니다.

Logistic Matrix Factorization

Spotify에서는 R행렬을 유저들의 행동을 관측해 0과 1을 가진 행렬로 만듭니다.

0값을 가지는 R(u,i) 값은 유저 u는 Item i를 좋아하지 않는다는 것을 표현하는 것이고 1은 그반대의 정보를 표현하는 것입니다.

그런데, 0과 1만으로 학습을 진행하게 되면, 유실되는 정보량이 매우 많기 때문에 Spotify는 확률적 접근방법을 사용합니다. 앞서 설명예제에서는 이해하기 쉽도록 Interaction이 발생한 수를 취했는데, 실제 Spotify 추천 시스템에서는 그대신 유저가 아이템을 좋아할 확률값을 취하는 것이죠.

확률값으로 환산하는 식은 아래와 같습니다.

$$p\ (l_{(u,i)} | x_u,y_i,\beta_u,\beta_i) = \frac{exp(x_uy_i^T+\beta_u+\beta_i)}{1+exp(x_uy_i^T+\beta_u+\beta_i)}$$

( 네… 어마무시합니다…. )

하나씩 살펴 보면, $x_u$ 는 유저 Factor 벡터이고, $y_i$는 아이템 Factor 벡터입니다. $\beta_u,\beta_i$는 각각 유저,아이템에 대한 편향값 입니다.

유저 u Vector가 $\left(\begin{array}{c} 0.1 \\ 0.2 \\ 0.3 \end{array} \right)$ 이고, 아이템 i Vector가 $\left(\begin{array}{c} 0.2 \\ 0.9 \\ 0.8 \end{array} \right)$, $\beta_u ,\beta_i$가 각각 0.3,0.4라고 했을때, 유저 u가 아이템 i를 좋아할 확률은 75.76% 입니다.

$x_uy_i^T = 0.44, \\ x_uy_i^T + \beta_u + \beta_i= 1.14, \\ \exp(x_uy_i^T + \beta_u + \beta_i) = 3.1268$ 이므로, p의 값은 $\frac{3.1268}{3.1268+1} = 0.7576$

R행렬의 값 $(l_{(u,i)})$ 들은 확률값이므로 모두 1보다 작은 양수값들일 것입니다. $\alpha_u ,\beta_i$ 가 의미하는 바는, 각 유저마다 음원청취 패턴이 다르므로 이러한 경향을 표현하는 변수라고 생각할 수 있습니다.

어떤 유저는 여러 장르를 폭넓게 청취하는 패턴을 가지고 있을 수 있고 어떤 유저는 그와 반대라고 했을 때, $\alpha_u , \beta_i$ 를 설정하지 않고서는 한 패턴에 대해서만 적합한 편향된 학습이 이루어지기 때문에 이러한 요인들을 보정해주는 변수를 설정하는 것입니다.

0과 1사이의 값을 취함으로써, 유저의 Negative Feedback은 음수가 아닌 0과 가까운 값으로 표현되기 때문에,

0에 가까울수록 유저가 아이템을 싫어하는 정도를 얼마나 나타낼지를 결정하는 변수를 하나더 도입하는데, 이 파라미터값을 조정하여 또한번 모델을 튜닝할 수 있습니다.

만약 음수의 값을 취한다면, 그 값만큼 부정적인 성향을 표현할 수 있지만, 이 모델에서는 c의 파라미터 값으로 조절하는 것이 특징입니다.

이 값을 컨피던스라 하는데, 이 값은 아래와 같이 정의 될 수도 있다고 합니다. $c = \alpha r_{ui} \\ c = 1 + \alpha \log (1 + r_{ui}/e)$

논문에서는 위 변수를 파워 유저의 활동 이력에 따른 편향된 학습을 방지해주는 역할을 한다고 설명하고 있습니다. 또한 위의 함수는 하나의 예로 설명한 것이고, 자유롭게 다른 함수들로 대체될 있다고 하네요.

Loss Function (손실값 계산)

이제 데이터도 준비되었고, 모델 함수도 정의 되었으니, 모델을 학습 시키기 위해선 손실 함수만 정의해 주면 되겠죠 ? Spotify의 논문에서는 또 어마 무시한 수식이 아래와 같이 튀어나옵니다….

$$L\ (R | X,Y,\beta) = \prod_{u,i} p\ (l_{(u,i)} | x_u,y_i,\beta_u,\beta_i)^{\alpha r_{ui}}(1-p\ (l_{(u,i)} | x_u,y_i,\beta_u,\beta_i))$$

네…. 익숙해지셔야 합니다…ㅎㅎ

한숨 고르고 천천히 살펴보자면, 유저 u가 아이템을 좋아할 확률값에 컨피던스를 입힌 값과 좋아하지 않을 확률을 곱해 모든 유저,아이템에 prod 연산을 수행합니다.

이러한 기법을 미지의 확률값을 관측결과만 보고 추정하는 최대 우도 정리라 합니다. 이에 대한 설명은 더 자세히 설명된 글이 너무나도 많기 때문에 따로 검색해 보시길 바랍니다.

Spotify의 추천 시스템을 전반적으로 살펴 보았습니다. 최대한 이해하기 쉽게 쓰도록 노력했는데 역시나 어렵네요…. 현재 작성중인 문서이며, 맞지 않는 부분은 언제든 피드백 주시면 감사드리겠습니다.

2편에서 부터는 대용량 데이터 학습을 어떻게 처리하였는지 아키텍쳐 적인 관점에서 살펴보도록 하겠습니다.

---