[논문 리뷰] Collaborative Filtering for Implicit Feedback Datasets

 Introduction 

 

e-commerce가 점차 발전함에 따라 시장에 등장하는 상품의 종류도 매우 많아졌다. 이에 따라서 사용자들은 올바른 상품을 찾을 수 있도록 해주는 추천 시스템이 필요했는데 일반적으로 사용자나 상품에 대한 프로필을 만들어 서로 연관 짓는 것을 기반으로 하고 있었다. 이런 추천 시스템은 크게 보자면 2종류로 나눌 수 있었는데 하나는 content based approach이고, 다른 하나는 Collaborative Filtering 기반이다.

 

 

 

 

출처: 영화 [신비한 동물사전]

 

 

 

 

 

콘텐츠 기반 추천 시스템은 상품이 가진 특성들을 사용하여 추천을 진행하는 것인데, 유저 프로파일과 아이템(상품) 프로파일을 참고한다. 예를 들어, 어떤 유저가 <해리포터🧙🏻> 영화를 즐겨서 본다면 이와 유사한 분위기의 영화를 가진 <신비한 동물 사전🦨> 영화를 유저에게 추천해주는 것이다. 하지만 콘텐츠 기반 추천은 수집하기 어려운 추가적인 정보를 요구하게 되면 추천하기가 힘들다는 단점이 존재한다.

 

 

 

 

이번 논문에서 주로 다룰 Collaborative Filtering(CF)은 오로지 유저들의 과거 행적들을 사용하여 추천을 진행한다. 예를 들어, 전자기기를 좋아해서 많이 구매했던 유저가 있고, 비슷하게  전자기기들을 주로 소비했던 유저가 있다면 서로 유저의 구매 기록을 참고하여 추천을 진행하는 것이다. 협업 필터링의 주된 장점은 필요한 정보가 사용자들의 과거 이력 정보뿐이라는 것이다. 따라서 도메인의 지식이 따로 존재하지 않아도 여러 분야에서 적용시킬 수가 있다. 하지만, 맨 처음에 유저의 기록이 없을 때 추천하기 어렵다는 Cold Start Problem이 있다.

 

 

 

 

출처: Adobe Stock

 

 

추천 시스템은 다양한 데이터를 입력으로 받는다. 그중에서 가장 편리한 것은 explicit feedback 데이터로 사용자가 직접 특정 상품의 평점이나 평가를 내린 데이터를 의미한다. 예로 Netflix의 별점 남기기, TiVo의 좋아요/싫어요 정보가 이에 해당한다. 하지만, explicit feedback 데이터는 유저가 기록을 남겨야만 사용할 수 있다. 이런 행위조차 실제로 귀찮아하는 유저가 훨씬 많기 때문에 이보다는 단순히 접속 기록, 시청 기록, 검색 패턴 등의 간접적 정보를 사용하는 implicit feedback 데이터가 풍부하며 잘 다룰 필요성이 있다.

 

 

 

 

논문에서는 유저들의 TV 프로그램 시청 기록들을 바탕으로 좋아할 만한 TV 프로그램을 추천하는 실험을 진행하였다. 유저의 시청기록 데이터를 바탕으로 저자들이 말하는 Implicit Feedback 데이터의 특징에는 4가지가 있다.

 

 

 

1. 부정적인 피드백이 없다.
   
   유저의 과거 이력들을 바탕으로 어떤 것들을 좋아하고 소비를 하는지 알 수 있지만, 어떤 상품들을 싫어하는지 알아내기가 어렵다. 예를 들어 TV 프로그램을 시청하지 않은 이유가 진짜 싫어해서 보지 않았을 수도 있고, 그런 프로그램이 존재하는지 몰라서 안 봤을 수도 있으며 시간이 맞지 않아 못 봤을 수도 있다.
   
   
   
   
   
2. Implicit feedback 데이터 자체에 노이즈가 많이 추가되어 있다.
   
   유저가 특정 상품을 구매했다고 해서 그 상품을 진짜로 좋아해서 샀다는 보장이 없다. 유저가 좋아하지 않는데, 선물용으로 구매했을 수도 있고, 구매하고 나서 실망을 했을 수 있다. 유저가 어떤 TV 프로그램을 시청했다는 기록이 있더라도 TV를 켜두고 잠들었을 수도 있다.
   
   
   
   
   
3. explicit feedback 데이터는 선호도를 의미하지만, implicit feedback 데이터는 신뢰도를 의미한다.
   
   explicit feedback 데이터는 평점과 같은 정보이기 때문에 유저가 아이템을 얼마나 선호하는지 직접적으로 보여진다. 하지만, implict feedback 데이터는 얼마나 상호작용 했는지, 몇 번 시청했고 얼마나 그 페이지를 방문했는지의 정보들만 주어지기 때문에 직접적인 선호도로 해석할 수는 없다. 하지만 자주 상호작용 했다는 의미는 어느 정도의 선호도가 있다고 볼 수 있다.
   
   
   
   
   
4. Implicit feedback 데이터를 사용하는 추천시스템은 적절한 평가 측정치가 필요하다.
   
   기존에는 MSE를 통해 예측이 얼마나 잘 이루어졌는지 평가할 수 있었지만, Implicit feedback 데이터를 사용할 때는 고려해야 할 사항이 있다. 예로, 여러 번 시청했던 프로그램이나 동시간대에 방영하는 두 TV 프로그램 사이에서 어떻게 적절하게 평가할지 생각해보아야 한다.

 

 

 

 

 

 

 Preliminaries 

 

논문에서 사용하는 용어에 대해서 먼저 정의하고 시작한다. 앞으로 사용되는 다음 기호에 대해서는 아래와 같은 의미를 갖게 된다.

 

 

 

• $u, v$ : 유저
• $i, j$ : 아이템
• $r_{ui}$ : $u$가 $i$에 남긴 평점(Explicit) 또는 $u$가 $i$와 상호작용한 횟수(Implicit). 논문에서는 유저가 해당 프로그램의 전체 시간 중 얼마나 시청했는지의 비율을 의미한다. ex. $r_{ui} = 0.7$ 은 전체의 70%를 시청했음을 의미한다.

 

 

 

모든 유저와 모든 아이템의 상호작용 행렬을 만들었을 때, 비어있는 $r_{ui}$ 값은 0으로 모두 채우고 진행한다. 

 

 

 

 

 

 

 

Previous Work

 

 Neighborhood models 

 

Collaborative Filtering들은 이웃기반의 모델인데, 크게 2종류로 나뉠 수 있다. 하나는 유저를 기반으로 협업 필터링을 하는 것이고 다른 하나는 아이템을 기반으로 협업 필터링을 하는 것이다. 유저를 기준으로 하여 계산하는 것이 먼저 등장하였고 이후에 아이템 기반으로 한 협업 필터링이 등장하였다. 아이템 기반 협업 필터링이 전체적으로 정확도가 더 좋게 나왔으며 추천된 이유를 설명할 수 있어 많이 사용되었다. 아이템 기준이 성능 측면에서 더 좋았던 것은 유저가 이전에 선호했던 아이템들을 잘 알지만, 나와 비슷한 성향을 가진 사람은 많이 모르기 때문이다.

 

 

 

 

아이템 기반 협업필터링은 아이템 간의 유사도를 측정하며, $s_{ij}$로 나타낸다. 유사도를 구할 때는 주로 피어슨 상관계수를 사용한다. 저자들이 이번 논문을 통해 예측하고자 하는 것은 관측되지 않은 값 $r_{ui}$를 예측하는 것이며, 초반에는 가중 평균을 사용하여 그 값을 계산하였다.

 

 

 

$$ \hat{r}_{ui} = \frac{\sum_{j \in S^k(i ; u)} s_{ij}r_{uj}}{\sum_{j \in S^k(i ; u)} s_{ij}} $$

 

• $\hat{r}_{ui}$ : 예측한 $r_{ui}$ 값
• $S^k(i ; u)$ : $u$가 소비한 아이템들 중 $i$와 아이템 $k$개의 집합
• $s_{ij}$ : $i$와 $j$의 유사도
• $r_{uj}$ : $u$가 $j$에 남긴 평점 또는 $u$와 $j$의 상호작용 횟수

 

 

 

 

위의 수식을 개선하여 유저와 아이템 사이에 발생할 수 있는 bias를 잡도록 했었는데 이는 explicit feedback에 대해서만 해당하고, implicit feedback 데이터에는 직접적으로 적용하기 어려웠다. 서로 다른 유저들은 평균적으로 어떤 TV 프로그램에 머무는 시간도 다르기 때문에 그 편차가 존재할 것이다. 따라서 직접적으로 implicit feedback 데이터를 사용하는 데에 어려움이 있다.

 

 

 

 

 

 Latent factor models 

 

잠재요인(latent factor)을 사용한 모델들은 latent feature를 사용하여 유저와 아이템 사이의 관계를 파악한다. 저자들은 그러한 모델들 중 SVD(Singular Value Decomposition)을 사용한 모델을 사용했다. SVD를 사용한 모델은 당시에 높은 성능을 보여주며 인기를 끌고 있던 모델이었다.

 

 

 

 

일반적으로 이 모델은 유저에 대한 잠재 벡터 $x_u \in \mathbb{R}^f$와 아이템에 대한 잠재 벡터 $y_i \in \mathbb{R}^f$를 연관 짓는다. 이 두 가지 잠재 벡터를 사용하여 예측을 진행하며 계산은 두 벡터의 내적으로 계산한다.

 

 

 

$$ \hat{r}_{ui} = x_u^Ty_i $$

 

 

 

당시에 위의 예측모델에 대해서 많은 연구가 이루어졌는데, 적절한 규제(Regularization)를 통해 과적합이 이루어지지 않도록 만든 목적함수가 존재한다. 실제 레이팅 값과 예측된 레이팅 값과의 차이를 최소화하도록 만드는 수식으로 다음과 같다.

 

 

 

$$ \underset{x_*, y_*}{\min} \sum_{r_{ui} \text{ is known}} (r_{ui} - x_u^Ty_i)^2 + \lambda(\| x_u \|^2 + \| y_i \|^2)$$

 

 

 

여기서 $\lambda$는 모델의 규제를 위해서 사용되었으며 파라미터를 학습할 때는 경사하강법을 사용하였다. 이 모델을 Netflix 데이터셋으로 훈련시킨 결과, 이웃 기반 모델보다 뛰어난 성능을 보여주었다. 이에 저자들은 모델을 implicit feedback 데이터에도 적용시키려고 노력했으며, 추가적인 모델의 개선과 최적화 방법을 고안하려고 했다.

 

 

 

 

 

 Our model 

 

이번에는 implicit feedback 데이터를 사용한 모델에 대해서 소개한다. 먼저 $r_{ui}$값에서 신뢰도의 개념을 재정의 해야한다. 저자들은 $r_{ui}$ 값에 따라 이진 값으로 구분하였으며 이진 값을 $p_{ui}$로 정의하였다.

 

 

 

$$ p_{ui} = \left\{\begin{matrix} 1 \quad r_{ui} > 0 \\ 0 \quad r_{ui} = 0 \end{matrix}\right. $$

 

 

 

문제는 위와 같이 정의하면, 한 번이라도 상호작용 했던 아이템들은 선호함을 의미하고 한 번도 상호작용 하지 못한 아이템은 선호하지 않는다라는 의미가 된다. 문제는 선호하지 않는 아이템이 실제로 선호하는데 상호작용하지 않은 경우도 포함되는 것이다. 예를 들어, 아이템의 존재 자체를 몰랐을 수도 있고, 좋아하는데 가격이 너무 비싸서 구매하지 못한 상품일 수도 있다.

 

 

 

 

반대로, 상호작용 했다는 것이 꼭 그 아이템을 선호한다고 해석하기도 애매하다. TV 프로그램의 시청시간이 높았던 것이 단순히 이전 프로그램을 보다가 이어서 틀어놓은 것일 수도 있고, 어떤 상품을 구매하더라도 선물용으로 구매했을 수도 있는 것이다. 하지만 저자들이 주장하기를 상호작용 횟수 $r_{ui}$가 증가할수록 유저가 아이템을 선호한다는 의미로 나타난다고 하였다. 따라서 이를 반영하는 새로운 변수 $c_{ui}$를 소개한다.

 

 

 

$$ c_{ui} = 1 + \alpha r_{ui} $$

 

 

 

이렇게 값을 설정하게 되면 모든 유저와 아이템 쌍에 대해서 최소한의 신뢰도인 $p_{ui}$를 정의할 수 있으며, 더 많이 상호작용할수록 더 높은 값을 얻는 것도 가능해진다. 증가율은 상수인 $\alpha$가 결정하며 일반적으로 40으로 설정했을 때, 가장 좋은 결과를 보여준다고 한다.

 

 

 

 

신뢰도에 대한 정의가 완료되었으면 다음에는 유저 잠재벡터와 아이템 잠재 벡터를 봐야 한다. explicit feedback 모델과 마찬가지로 두 잠재 벡터의 내적으로 선호도를 예측하며 Matrix Factorization 기법과 유사성을 띄지만 다음 2가지에서 차이점을 보인다.

 

 

 

1. 사용자마다 변화하는 신뢰도를 다뤄야 한다.
2. 관측된 유저-아이템 쌍이 아닌 모든 유저-아이템 쌍에 대해서 다뤄야 한다.

 

 

 

위의 2가지를 반영한 목적함수는 아래와 같이 나타난다.

 

 

 

$$ \underset{x_*, y_*}{\min} \sum_{u, i} c_{ui}(p_{ui} - x_u^Ty_i)^2 + \lambda \left( \sum_u\| x_u \|^2 + \sum_i\| y_i \|^2 \right)$$

 

 

 

 

문제는 위의 손실함수에서 모든 쌍을 계산해야 하기 때문에 $mn$ 꼴의 수식이 등장한다는 것이다. 여기서 $m$은 유저의 수를 $n$은 아이템의 수를 나타낸다. 일반적으로 사용하는 데이터셋으로는 쉽게 $mn$의 값은 매우 커질 것이기 때문에 경사 하강법을 통한 최적화를 진행하기에는 너무 시간이 오래 걸린다는 단점이 있다. 따라서 저자들은 새로운 최적화 방법을 소개한다.

 

 

 

 

출처: PNG WING

 

 

만약 유저나 아이템 요소중 하나가 고정되어 있다면, 손실 함수는 2차원의 꼴이 될 것이기 때문에 global minimum을 쉽게 계산할 수 있게 된다. 이 방법을 사용하는 것이 Alternating Least Square(ALS) 최적화 방법이다. 손실 함수를 최적화하는 매 step마다 번갈아가면서 잠재 벡터를 상수 화하여 계산하는 것이다.

 

 

 

 

예로, 먼저 아이템 잠재벡터를 상수화시키고, 유저 잠재 벡터인 $x_u$에 대해 최적화를 진행한다고 해보자. global minimum을 찾기 위해서 손실 함수를 $x_u$에 대해 미분하여 0이 되는 값을 찾아야 한다.

 

 

 

$$ \frac{\Delta L(x_u)}{\Delta x_u} = -2\sum_i c_{ui} (p_{ui} - x_u^Ty_i) \times y_i + 2 \lambda x_u = 0 $$

 

 

$$ -\not{2}\sum_i c_{ui}p_{ui}y_i + \not{2}\sum_i c_{ui}(x_u^Ty_i)y_i + \not{2}\lambda x_u = 0$$

 

 

$$\sum_i c_{ui}(x_u^Ty_i)y_i + \lambda x_u = \sum_i c_{ui}p_{ui}y_i$$

 

 

 

두 벡터의 내적의 결과는 스칼라 값이므로, 벡터의 내적 순서를 변경하여도 동일하기 때문에 다음과 같이 표현한다.

 

 

 

$$\sum_i c_{ui}(y_i^Tx_u)y_i + \lambda x_u = \sum_i c_{ui}p_{ui}y_i$$

 

 

$$\left( \sum_i c_{ui} y_i^T y_i + \lambda I \right)x_u = \sum_i c_{ui}p_{ui}y_i $$

 

 

$$ (Y C_u Y^T + \lambda I) x_u = \sum_i c_{ui} p_{ui} y_i $$

 

 

$$ (Y C_u Y^T + \lambda I) x_u = Y^T C_u P_u $$

 

 

$$ x_u = (Y C_u Y^T + \lambda I)^{-1} Y^T C_u P_u $$

 

 

 

 

마지막으로 구한 $x_u$의 값이 결국 목적함수를 최소화시킬 수 있는 값이며 논문에서는 조금의 표현 변화를 주어서 아래와 같이 표현하였다.

 

 

 

$$ x_u = (Y^TC^uY + \lambda I)^{-1}Y^TC^up(u) $$

 

• $C^u$ : $C^u_{ii} = c_{ui}$ 인 값들로 이루어진 $n\times n$ 행렬
• $p(u)$ : $u$의 선호도 정보들을 모두 담고 있는 벡터. $p_{ui}$ 값들을 가지고 있다.

 

 

 

$Y^TC^uY$에서 계산의 복잡도가 $m$명의 유저마다 $\mathcal{O}(f^2n)$을 계산해줘야 해서 비효율적이었지만, 저자는 아래의 꼴로 수식 변형을 통해 계산 속도를 크게 증가시킬 수 있었다고 한다. $f$가 말하는 것은 잠재 벡터의 차원 크기이다.

 

 

 

$$ Y^T C^u Y = Y^T Y + Y^T (C^u - I)Y $$

 

 

 

이 변화를 통해 $Y^TY$는 유저에 관계없이 항상 같은 값을 내기 때문에 1번만 계산하면 되었다. 또한, $Y^T(C^u - I) Y$에 대해서는 $n_u$ 개의 0이 아닌 값으로 구성되어 있었다. 여기서 말하는 $n_u$는 $r_{ui} > 0$인 값의 수를 말하며 일반적으로 $n$보다 그 크기가 훨씬 작았다($n_u \ll n$). 이와 비슷하게 $C^u p(u)$도 오직 $n_u$개의 0이 아닌 값을 가지고 있으므로 최종 시간 복잡도는 $\mathcal{O}(f^2 n_u + f^3)$ 으로 계산된다.

 

 

 

 

기존의 시간 복잡도였던 $\mathcal{O}(f^2n)$에서 $n$은 아이템의 개수로 그 크기가 커질 수록 시간복잡도도 크게 증가하였지만, 새롭게 계산된 시간복잡도인 $\mathcal{O}(f^2 n_u+ f^3)$ 에서는 전체 아이템의 개수만큼 이 아닌 상호작용한 아이템의 개수만큼만 필요로 하기 때문에 계산량을 감소시킬 수 있던 것이다.  따라서 $f^3$에 비례해서 계산량이 증가하는 것을 알아냈으며 잠재 벡터의 차원을 너무 크게 잡지 않는 한 이는 큰 문제가 되지 않았다고 한다.

 

 

 

 

위의 계산이 $m$명의 유저에 대해서 실행되어야 하기 때문에 모든 유저의 계산을 포함한 시간 복잡도는 아래와 같이 다시 작성할 수 있다. 이는 특히 잠재 벡터의 차원 $f$가 20 ~ 200 일 때 입력 대비 선형적으로 시간이 걸려 효율적이었다고 한다.

 

 

 

$$ \mathcal{O}(f^2 \mathcal{N} + f^3m) $$

• $\mathcal{N}$ : $\sum_u n_u$

 

 

 

지금까지는 $x_u$에 대한 미분을 진행했고, 그 업데이트 과정에 대해서 알아보았다면 반대로 $y_i$에 대해 미분하고 업데이트하는 과정도 보아야 한다. 하지만 미분 값도 거의 동일하고 업데이트도 똑같이 이루어지기 때문에 미분 값만 살펴보고 넘어간다.

 

 

 

$$ y_i = (X^T C^i X + \lambda I)^{-1} X^T C^i p(i) $$

 

 

 

이 2가지 수식을 이용해서 번갈아가며 목적함수를 최소화해나가며, 일반적으로 10번 정도 번갈아가면서 계산하면 된다. 목적함수를 최소화해서 최종적으로 벡터의 내적을 통해 유저의 예측 선호도인 $\hat{p}_{ui}$를 계산했다면 상위 $K$개의 아이템들을 유저에게 추천한다. 이렇게 해서 ALS와 Implicit feedback 데이터를 사용해 유저에게 추천을 진행하는 큰 그림을 모두 살펴보았다.