Recommender System
정보가 넘쳐나는 현 시대에서 추천 시스템은 전자 상거래, 온라인 뉴스 및 소셜 미디어 사이트를 포함한 많은 온라인 서비스에 널리 채택되어 기호에 맞는 상품을 제공하고 있습니다.
소비자에게 적합한 제품을 추천해주는 것은 소비자의 만족도와 충성도를 높일 수 있는 열쇠입니다.
따라서 많은 업체들은 제품에 대한 사용자의 패턴을 분석하여 개인화된 추천을 제공할 수 있는 추천시스템에 더욱 관심을 갖게 되었습니다.
strategies for Recommender System
추천시스템은 크게 두가지 갈레로 나뉩니다.
첫번째는 컨텐츠 기반 필터링(content-based)입니다.
컨텐츠 기반 추천 시스템은 각각의 유저, 아이템에 대한 Profile을 생성하여,
Profile을 통해 과거에 접한 아이템 중 유저가 선호하였던 아이템과 유사한 아이템을 추천해 주는 방법입니다.
예를 들어 영화에 관한 아이템 Profle에는 장르, 참여한 배우, 인기도, 등의 속성이 포함됩니다.
또한 유저의 프로필에는 인구통계적 정보 혹은 설문조사에 대한 답변정도 등이 포함될 수 있습니다.
간단히 설명드리면 컨텐츠 기반 필터링은 "유저 A가 아이템 1을 좋아하는데, 아이템 1과 비슷한 아이템 2도 좋아하겠지??" 라는 추측과 동일한 과정이라고 할 수 있습니다.
컨텐츠 기반 추천 시스템은 다른 유저의 데이터가 필요하지 않다는 것과 추천에 대한 근거를 어느정도 찾을 수 있다는 장점이 존재합니다.
하지만. Profile을 구성하기 위한 explicit feature를 찾기 어렵다는 점, 그리고 profile을 작성하지 못한다면 새로운 유저에 대한 추천이 어렵다는 점이 단점으로 꼽힙니다.
두번째 방법은 협업 필터링(Collaborative Filtering)입니다.
컨텐츠 기반(content-based) 방법과 더불어 추천시스템의 한가지 큰 줄기인 협업 필터링(Collaborative Filtering)은 컨텐츠 기반 필터링처럼 profile을 따로 만들 필요 없이, 평점과 방문기록 등의 과거 상호관계(interaction)에 기반하여 추천을 제공합니다.
예를들어 설명하면 협업필터링은 "유저 A와 B가 아이템 1에 대하여 비슷한 평가를 내렸다면, 유저 A가 선호하는 다른 아이템인 2에 대해서도 B가 어느정도 같은 선호도를 가지고 있지 않을까?" 라는 생각과 같습니다
쉽게 풀어 얘기하면 많은 사람의 의견을 통해 더 나은 추천을 하는 방법이라고 할 수 있습니다. 즉, 협업 필터링은 집단지성을 활용하는 방법입니다.
협업필터링은 의 장, 단점은 컨텐츠 기반 시스템과 상반됩니다.
우선, 유저에 대한 profile을 생성할 필요가 없기 때문에, Domain에 대한 지식이 상대적으로 덜 필요하다는 장점이 존재합니다.
또한, 일반적으로 컨텐츠 기반 필터링에 비해 성능이 우수합니다.
하지만 협업필터링은 상호관계에 대한 데이터가 부족할 시, 협업이 불가능하여 새로운 유저, 아이템에 대한 추천이 제대로 작동하지 않는 "Cold-start" 문제를 가지고 있습니다.
Collaborative filtering methods
협업필터링에서 가장 많이 사용되는 방법에는 neighborhood method와 Latent factor model이 있습니다.
첫번째로 neighbor method는 아이템 사이, 혹은 유저 사이의 관계를 계산하는데 초점을 맞추고 있습니다.
동일한 유저에게 비슷한 평가를 받았다면 서로 해당하는 아이템들은 이웃이 되며(item-oriented),
또한 동일한 아이템에게 비슷한 평가를 내린 유저들은 서로 이웃이 됩니다(user-oriented).
neighborhood method의 대표적인 알고리즘으로는 우리가 잘 알고 있는 KNN이 있습니다.
아래의 그림 예시는 Joe가 좋아하는 세편의 영화를 똑같이 좋아하는 이웃들의 또다른 선호 영화를 바탕으로 Joe에게 새로운 영화를 추천해주는 user-oriented neighborhood method의 예시입니다.
협업필터링에서 사용되는 또다른 방법인 Latent factor model은 user의 item 평가 패턴에서 추출된 20~100개에 해당하는 Latent factor(차원, 축)를 이용하여 유저와 아이템을 함께 특성화 하는 방법입니다.
각각의 학습된 factor 중에는 코메디 vs 드라마 와 같이 분명한 특성 대비를 보여주는 factor(축)가 존재할 수 도 있으며, 캐릭터의 깊이 혹은 기발함과 같이 분명하지 않은 특징을 표현하는 factor 또한 존재할 수 있습니다.
Latent factor model에서가장 많이 사용되는 방법은 본 논문에서 설명하고 있는 Matrix Factorization이 있습니다.
다음의 예시는 간단하게 2개의 Factor(2차원)를 이용하여 user와 item을 함께 특성화 한 경우를 보여주고 있습니다.
패턴분석을 통해 얻어낸 각각의 factor(축)은 각각 '진지함 vs 도피주의' , '여성적 vs 남성적' 의 특성을 나타내고 있음을 확인할 수 있습니다.
1.Matrix Factorization
먼저 협업필터링을 위해 사용되는 데이터에는 두가지 종류가 존재합니다.
1) Explicit feedback
Item에 대한 User의 모든 직접적인 평가를 포함하는 데이터 입니다.
바로 사용해도 좋을만큼 데이터의 품질이 좋은 경우가 많습니다.
하지만, 구하기 어렵기 때문에 sparse matrix인 경우가 많습니다.
ex) 평점, 취향, 후기, ...
2) Implicit feedback
직접적으로 Item과 User간의 선호 관계를 나타내지는 않지만, 간접적인 정보를 포함하고 있는 데이터 입니다.
다양한 방법을 통하여 구할 수 있으며, 대부분 Dense matrix입니다. 하지만 의미를 직접적으로 파악하기는 어렵습니다.
ex) 방문기록, 검색기록, 구매여부, 장바구니, ....
Matrix Factorization는 Latent factor model 중에서 가장 성능이 좋은 방법 중 하나입니다.
Matrix Factorization은 기본적으로 user-item의 평점 패턴으로 부터 아이템과 유저를 Latent factor Vector로 동시에 표현합니다.
내적을 사용하여 user-item Interaction을 모델링하기 때문에, 각 user와 item 벡터의 latent factor가 일치할수록 추천으로 이어질 가능성이 높아집니다.
Matrix Factorization의 강점 중 하나는 추가적인 정보를 함께 사용할 수 있다는 것 입니다.
만약 명백한 관계를 설명하여주는 explicit feedback을 사용할 수 없는 경우가 생긴다면, Matrix factorization 방법은 implicit feedback을 사용하여 latent factor로 유저, 아이템을 표현할 수도 있습니다.
Basic Matrix Factorization Model
Matrix factorization 모델은 유저와 아이템을 f차원의 잠재 공간(latent factor space)으로 매핑합니다.
각각의 user, item 벡터는 \(p_u \in \mathbb{R}^f\), \(q_i \in \mathbb{R}^f\)로 표현되기 때문에
user-item간의 상호관계를 내적(dot-product)을 사용하여 모델링 할 수 있습니다.
$$\hat{r_{ui}} = q^{T}_i p_u$$
따라서 내적의 결과 \(\hat{r_{ui}}\) 는 유저 u와 아이템 i 간의 상호관계(interaction)를 의미합니다.
이러한 방법은 사실 latent factor를 활용하여 정보를 복원하는 SVD(singular vector decomposition,특이값 분해)와 매우 연관되어 있습니다. SVD는 완성된 MxN matrix를 같은 f차원의 Mxf, Nxf Matrix로 분해할 수 있는 스킬 입니다.
하지만 SVD를 추천시스템에 활용하기 위해서는 문제가 발생합니다.
rating과 같은 User-Item matrix는 결측치가 매우 많은 sparse matrix인 경우가 대부분 입니다. 일반적인 SVD는 결측치가 있는 행렬에 적용할 수 없습니다. 그렇다고 해서 존재하는 일부의 데이터만을 사용하는 방법은 과적합을 불러올 것 입니다.
기존의 시스템들은 따라서 결측치를 채우는 imputation에 집중하였습니다. 하지만 Sparse한 데이터의 차원이 커질수록 Imputation의 계산 부담은 가중되며, 데이터를 왜곡할 가능성 또한 증가합니다.
따라서 근래의 Matrix Factorization 모델들은 존재하는 데이터만을 이용하고 정규화 term을 활용하여 과적합을 방지하는 방법을 택하고 있습니다. 이러한 시스템은 \(p_u\)와 \(q_i\)를 얻기 위해 다음의 regularized squared error를 최소화 하게 됩니다.
$$\min_{q, p} \sum_{(u, i) \in K} ( r_{ui} - q^T_i p_u )^2 + \lambda (\Vert{q_i}\Vert^2 + \Vert{p_u}\Vert^2)$$
이미 관측된 (u, i)의 집합 K에서 학습이 진행되지만, regularization term은 알려지지 않은 평점에 대한 모델의 일반화된 예측을 가능하게 해 줍니다.
MF는 또한 User, Item 간의 Sparse한 Interaction Matrix를 채워주는 Matrix completion이라고도 할 수 있습니다.
Training
Matrix factorization의 regularized squared error를 최소화 하기 위한 최적화 방법에는 두가지 방법이 사용됩니다.
1)SGD(Stochastic Gradient Descent)
첫번째는 확률적 경사하강법 입니다.
\(e_{ui} = r_{ui} = q^T_i p_u\)
error = 실제 평점과 예측 평점의 차이
\(q_i \leftarrow q_i + \gamma (e_{ui} p_u - \lambda q_i)\)
\(p_u \leftarrow p_u + \gamma (e_{ui} q_i - \lambda p_u)\)
gradient 반대방향으로 \(q_i,p_u\)를 update
SGD는 구현이 쉽고 빠르다는 장점이 존재합니다.
2)ALS(Alternating Least Squares)
Matrix factorization에서 유저와 아이템의 latent vector \(q_i\)와 \(p_u\)는 모두 알려지지 않은 미지의 값 입니다.
따라서 앞선 regularized squared error가 convex하다는 보장을 할 수 없습니다.
$$\min_{q, p} \sum_{(u, i) \in K} ( r_{ui} - q^T_i p_u )^2 + \lambda (\Vert{q_i}\Vert^2 + \Vert{p_u}\Vert^2)$$
하지만 두개의 벡터 중 하나를 고정하여 최적화 한다면, Convex한 2차식이 되어 최적화가 가능해집니다.
ALS(Alternating Least Squares)는 이러한 방법을 사용하여 \(q_i\)와 \(p_u\)를 번갈아가며 고정하고 최적화 하는 방식을 택합니다.
\(q_i\)를 고정하면 \(p_u\)의 least square를 계산하여 최적화 하고, 반대로 \(p_u\)를 고정하면 \(q_i\)의 least square를 계산합니다.
보통의 경우는 SGD가 더 쉽고 빠르지만 ALS가 효과적인 두가지의 상황이 존재합니다.
1) 병렬화가 가능할 경우
2) Implicit data에 집중된 시스템일 경우
Adding bias
협업필터링에 Matrix factorization을 활용하는 것은 모델이 데이터의 다양한 측면과 task-specific한 요구사항을 반영할 수 있도록 유연함을 부여해 줍니다.
\(\hat{r_{ui}} = q^{T}_i p_u\)를 계산하는 것은 유저와 아이템 사이의 상호관계를 파악하는 것입니다.
하지만, 실제로는 유저, 아이템의 다양한 bias가 rating에 variation을 가져오게 됩니다.
예를들면, 어떠한 유저는 평균보다 높은 점수를 주는 경향이 존재할 수도 있습니다.
따라서 \(q^{T}_i p_u\)를 활용하여 평점(상호작용)을 계산하는 것은 현명하지 않은 방법이 될 가능성이 존재합니다.
이러한 문제상황을 해결하기 위해 user u와 item i의 개별 특성을 표현하는 bias term을 추가할 수 있습니다.
$$\hat{r_{ui}} = \mu + b_i + b_u + q_i^Tp_u $$
\(\mu\)는 모든 item의 평점 평균,
\(b_i\)는 전체 item 평균에 대한 item i의 편차(deviation),
\(b_u\)는 전체 user 평균에 대한 user u의 편차(deviation)을 의미합니다.
이를 앞선 regularized squared error에 더하면 아래와 같은 목적함수를 얻을 수 있습니다.
$$\min_{p, q, b} \sum_{(u, i) \in K} ( r_{ui} - \mu - b_i - b_u - p_u^Tq_i )^2 + \lambda (\Vert{p_u}\Vert^2 + \Vert{q_i}\Vert^2 + b^2_u + b^2_i)$$
Additional Input Sources
협업필터링의 특성상 시스템은 종종 'cold-start' 환경에 직면하게 됩니다.
cold-start 환경은 많은 유저들이 매우 적은 평가를 내린 상황으로, 일반화된 결론에 도달하기 어렵습니다.
이러한 상황을 극복할 수 있는 한가지 방법은 유저에 대한 추가적인 Implict feedback 정보들을 통합하여 함께 활용하는 것 입니다.
추천시스템은 유저의 행동정보 등의 추가정보를 활용하여 모델링을 할 수 있습니다.
단순화하여 boolean의 implicit feedback을 고려해 보겠습니다.
\(N(u)\)는 user u가 implicit feedback을 보인 item set을 의미합니다.
이 때, 시스템은 \(N(u)\)를 활용하여 유저의 profile을 만들 수 있습니다.
\(N(u)\)에 속한 아이템에 implicit feedback을 보인 유저의 profile은 아래와 같이 표현 가능합니다.
$$\sum_{i \in N(u)} x_i$$
다음과 같이 Normalizing하여 표현할 수도 있습니다.
$$|N(u)|^{-0.5} \sum_{i \in N(u)} x_i$$
사용가능한 또다른 정보는 아이템과 관련되지 않은 속성과 성별, 나이, 우편번호 등과 같이 인구통계적인 유저의 속성(user attributes)입니다.
또 다시 간단하게 boolean 속성을 고려하여 볼 때, 유저 u의 속성 집합을 \(A(u)\)라고 하면,
같은 방법으로 user를 표현 가능합니다.
$$\sum_{a \in A(u)} y_a$$
user에 대한 추가적인 정보\(|N(u)|^{-0.5} \sum_{i \in N(u)} x_i\)와 \(\sum_{a \in A(u)} y_a\)를 통합하여 표현한 Matrix factorization의 rating 예측값은 다음과 같습니다.
$$\hat{r_{ui}} = \mu + b_i + b_u + q^T_i [p_u + |N(u)|^{-0.5} \sum_{i \in N(u)} x_i + \sum_{a \in A(u)} y_a]$$
Temporal dynamics
모든 아이템에도 유행이 존재하듯, 선호도와 성향은 시간에 따라 충분히 바뀔 수 있습니다.
누군가는 예전에 비해서 후한 점수를 주기도 하고, 어떠한 아이템은 과거의 영광속에서 인기를 잃고 잊혀져 갑니다.
Matrix Factorization은 데이터의 시간에 따른 동적인 변화 또한 반영이 가능합니다. 아래의 식에서 t는 시간을 나타냅니다.
$$\hat{r_{ui}}(t) = \mu + b_i(t) + b_u(t) + q^T_i p_u(t)$$
\(b_i(t)\)는 시간에 따른 아이템의 편향
\(b_u(t)\)는 시간에 따른 유저의 편향
\(p_u(t)\)는 시간에 따른 유저의 선호도 편향을 의미합니다.
Inputs with varying confidence levels
모든 데이터가 동일한 가중치 또는 신뢰도를 갖지 않는 상황 또한 모델링이 가능합니다.
예를 들면, 대규모 광고에 영향을 받은 아이템을 자주 선택되는 경우가 있을 수 있습니다. 또한 어떠한 유저는 악의적으로 좋지 못한 평점만을 부여할 수 있습니다.
이러한 경우, \(r_{ui}\)에 대한 신뢰도(가중치) \(c_{ui}\)를 도입하여 Matrix factorization에 해당 상황을 모델링 가능합니다.
$$\min_{p, q, b} \sum_{(u, i) \in K} c_{ui}( r_{ui} - \mu - b_i - b_u - q^T_i p_u )^2 + \lambda (\Vert{q_i}\Vert^2 + \Vert{p_u}\Vert^2 + b^2_u + b^2_i)$$
신뢰도는 행동의 빈도를 통해 나타낼 수 있으며, 예를들어 유저가 특정한 TV쇼를 얼마나 자주 보았는가, 특정한 아이템을 얼마나 자주 구매하였는가 등의 값이 채택될 수 있습니다.
2.Results
제안하는 Matrix factorization 방법의 효용성은 Netflix prize competition을 통해 충분히 입증되었습니다.
result 1.
다음의 결과는 Matrix factorization의 결과에서 처음 두개의 latent factor를 사용하여 2차원에 시각화 한 결과입니다.
영화를 좋아한다면 잘 분류되었다는 것을 한눈에 확인할 수 있다고 합니다.
x축의 좌측에는 공포영화가, 우측에는 코메디가 주로 분포 되어있습니다.
y축의 상단에는 비평가들의 찬사를 받은 독립영화들이, 하단에는 주류영화들이 위치하고 있음을 확인할 수 있습니다.
흥미로운 점은 좌측 상단에는 킬빌과 같이 작품성있는 공포영화들이 위치해 있다는 것 입니다.
result 2.
두번째 실험은 모델의 파라미터 수에 따른 RMSE 성능 비교입니다.
제안하는 여러가지 Matrix factorization의 variation들을 실험을 통해 비교하였습니다.
우선 모든 경우에서 모델 파라미터 수의 증가에 따라 일관되게 성능이 증가했음을 확인할 수 있습니다.
또한, Temporal dynamics를 고려한 모델이 특히 성능이 우수함을 알 수 있습니다. 이를 통해 추천시스템에서 시간 변수의 고려가 생각보다 중요함을 알 수 있었습니다.
3. 구현
MatrixFactorization에 대한 구현을 진행해 보았습니다. SGD를 사용하여 두개의 p_u,p_i를 동시에 업데이트 하는 방식을 사용하였습니다.
아무래도 사용한 Movielens 데이터셋의 sparsity가 매우 높기 때문에 ALS를 사용하는 것이 더 효과가 좋을것 같습니다.
\(b_u,b_i,\mu,C_{ui}\)를 추가하였으며, Confidence \(C_{ui}\)는 본 논문에 정확히 서술되어 있지 않아 'User u가 평가한 횟수 + item I가 평가된 횟수' 를 frequency로 설정하고, 정규화하여 사용하였습니다
성능에 보다는 알고리즘에 맞게 구현함에 초점을 맞추었습니다. 이 점 양해 부탁드립니다.
supkoon/MatrixFactorization
Contribute to supkoon/MatrixFactorization development by creating an account on GitHub.
github.com
마무리
추천시스템에서 정말 많이 거론되는 방법인 Matrix Factorization에 대해서 리뷰를 진행하였습니다.
기존의 Matrix Factorization을 추천 시스템에 효율적으로 적용하기 위한 다양한 제약과 활용방법을 제시하는 논문이었습니다.
최근의 알고리즘들도 정말 중요하지만, 때로는 클래식을 알고 출발하는 것이 전반적인 이해를 돕는 것 같습니다. 감사합니다.