[Paper Review] (2009, IEEE) Matrix Factorization Techniques for Recommender Systems

7

Recommender_System

목록 보기
7/22
post-thumbnail

작성자: 류채은

MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS

Yehuda Koren, Yahoo Research Robert Bell and Chris Volinsky, AT&T Labs—Research(2009)

1. Recommender System Strategies

content filtering:
사용자나 제품에 대한 profile 먼저 생성한다.
ex.) 관객 - (인구통계적 사실, 설문 결과) 영화 - (장르, 인기도)

collaborative filtering approach:
profile이 없는 상태에서 아이템이나 유저에 대한 필터링하는 방법(과거 구매 이력, 제품평가점수, browsing history 등 implicit data 활용)

하지만, 기존 평가 자료 존재하지 않거나 신규 유저가 나타남으로 인해 cold start 문제가 존재한다.

Neighborhood method:
아이템끼리의 관계, 사용자들끼리의 관계 계산. 거리가 가까운 것을 추천한다

  • item oriented(아이템끼리의 관계 산출):
    전제:특정 아이템들의 점수가 비슷하다면 그 아이템끼리는 가까운 위치에 있을 것이다.

  • user oriented(유저들끼리의 관계 산출):
    전제: 비슷한 영화를 동일한 점수를 매긴 사용자들끼리 선호 경향이 비슷할 것이다. (like minded user)

Latent factor method:
전제: 아이템에게 주는 rating 점수에는 패턴이 있을 것이다.
패턴을 찾아내서 하나의 factor로 추출내고 factor score을 중심으로 근거리 추정하여 추천하는 방법이다.

2.Matrix Factorization method

Latent model은 Model Factorization을 이용한다.

보통 추천시스템은 위 형태의 인풋 데이터 세트를 사용하지만 이 explicit feedback데이터는 sparsity issue 존재한다.

Matrix Factorization은 implicit feedback을 추론하므로 이 sparsity issue 극복 가능하다.(이 논문에서는 implicit data로 Purchase history, browsing history, search pattern, mouse movement 등을 활용했다.)

3. Basic Factorization model

SVD(Singular Value Decomposition) 이용 시 문제점:

  • Missing value가 많으면 SVD 이용이 곤란하다. Matrix에 대한 정보가 충분하지 않으면 정의하기 곤란하거나 Overfitting 위험하기 때문이다.
    기존의 해결방식은 missing value imputation을 해서 문제를 해결하는데 데이터가 많아지면 매우 힘든(비효율적) 방법이 될 수 있고
    부정확한 imputation은 데이터를 왜곡시킬 위험이 있다

-> 최근에는 Regularized modeling을 통해 해결한다.

  • Factor vector을 학습시키기 위해 regularized squared error를 최소화
    cf. k는 set of the (u,i) pairs R은 rating(training set)

  • 학습한 파라미터를 regularizing하므로 관찰된 데이터에 overfitting 되는 것을 극복한다.

  • 상수 ʎ는 regularization의 정도를 조절하는 상수다.

4.Learning Algorithms


Stochastic gradient descent

  • r_ui를 예측하고 예측 에러를 계산한다.
  • Gradient의 반대 방향에서 r에 비례하는 양만큼 파라미터를 수정한다.

Alternating least squares

  • q_j와 p_u는 unknown parameter이기 때문에 앞의 에러 최소화 식은 convex 형태가 아니다.
  • Unknown parameter 중 하나를 fix하면 이 최적화문제는 2차식(quadratic)이 된다.
  • ALS 테크닉이란 q_i와 p_u를 교대로 fixing하는 방식을 의미한다.
    - p_u를 fix하면 least-square 문제를 해결하는 방식으로 q_i를 재계산한다.
    - 보통은 SGD가 ALS보다 빠르고 용이하나 다음 두 경우에는 ALS가 우월하다.

5. Adding Biases

Collaborative filtering 대비 MF의 장점
: 다양한 데이터와 기타 application specific 요구사항을 반영해내는 유연성이 있다.



많은 경우 관찰된 변량은 baises 또는 intercepts와 관련이 있다.
예를 들어, 어떤 user들은 더 높은 점수를 주는 경향이 있고, 어떤 item은 좀 더 좋은 점수를 받는 경향이 있는데 이것이 어떤 제품이 더 좋다는 인식을 만들어냈다.
따라서 q_iTp_u형태로만 전체 rating 값을 설명하는 것은 현명하지 않다.
(개선된 r_ui : Global average + item bias + user bias + user item interaction )

Squared error function minimizing

  • Biases는 observed signal을 잡아내기 때문에 정확한 모델링이 결정적 사항이다.

6. Additional Input Sources


Cold start problem의 해결:
User의 explicit ratings에 관계 없이 구매 이력, 브라우징 기록 등 추가 정보 이용

  • 모든 signal source를 통합해서 아래와 같이 표현한다.
  • 이때 user표현이 더 강화된 것을 알 수 있다.

7. Temporal Dynamics

변화무쌍한 현실 세계

  • 신제품이 출시되면 제품/브랜드에 대한 인식 및 인기는 지속적으로 변화한다.
  • 소비자의 선호경향도 지속적으로 변화한다.

모델링

  • Item biases b_i(t) : Item popularity의 변화를 시간의 함수로 표현
  • User biases b_u(t): Natural drift in a user’s rating을 시간의 함수로 표현
  • User preferences p_u(t): user와 item의 상호작용이므로 user preference도 시간에 따라 변화하는 함수로 표현

8. Inputs with varying confidence levels

유의수준도 변화무쌍

  • 대규모 광고 집행의 단기적 영향이 있을 수 있다.
  • 의도적으로 rating을 높거나 낮게 주는 소비자의 문제가 있을 수 있다.
  • 소비자 선호 경향을 추론하는 방식의 추천시스템의 문제(implicit feedback)가 있을 수 있다.

유의수준을 모델링에 반영

  • Confidence score을 병기하는 것이 바람직하다.

9. Netflix Prize Competition


넷플릭스 공모전(2006년 실시)

  • 50만명 이상 소비자가 17,000 영화에 평점(5점 척도)을
    준 1억 건의 데이터 셋
  • 테스트셋 3백만 건에 대한 rating 예측치를 제출하면
    넷플릭스는 RMSE 계산
  • 10% 이상 성능을 개선시키면 10억, 아무도 없으면
    1등에게 5만 달러
  • 182개 국에서 28,000팀 출전

저자가 Matrix Factorization으로 1등한 내용

  • MF로 dimension(factor vector)을 발견
  • X축: 저속 comedy & horor, 남성/청소년 타겟
    Drama & Comedy, 심각, 강한 여성
  • Y축: 독립 영화, 수상작 vs. 정형화된 주류 영화
  • 저속 & 독립영화가 가깝게 포지셔닝
  • 심각한 여성주도 영화 & 주류 영화가 가깝게 포지셔닝


모델링 성과 분석

  • 파라미터가 많아질 수록 정확도 증가
  • 모델이 복잡할수록 정확도 증가
  • Temporal component가 특히 중요

총정리

  • 기존의 nearest-neighbor보다 우월했다
  • Multiple formula of feedback, temporal dynamics,
    confidence level과 같은 다양한 측면을 반영할 수록
    성능이 좋아졌다.
profile
2021 투빅스 추천시스템 세미나입니다.

6개의 댓글

comment-user-thumbnail
2021년 5월 17일

[15기 이성범]
본 논문은 추천시스템 기술의 바이블이라고 할 수 있는 Matrix Factorization에 대하여 다룬 논문이다. Matrix Factorization은 Neighborhood Method와 Latent Factor Method로 나뉘어지는 Collaborative Filtering Approach 중에서 Latent Factor Method를 구현하는 가장 좋은 방법 중 하나이다.

우선 Collaborative Filtering Approach은 도메인 지식이 없어도 아이템과 유저에 대한 추천이 가능하다는 장점을 가진다. 그러나 새로운 사용자와 아이템을 다루기에 부적합해 Cold Start Problem이라는 단점을 가진다.

Matrix Factorization은 유저와 아이템의 협업으로 생성된 평점 데이터의 패턴 속에서 Latent Factor을 추론해 사용자와 아이템의 특성을 찾아내는 방식으로 구성되어 있다. 이 방식은 높은 정확도, 확장성, 유연성이라는 장점을 가진다고 본 논문의 저자는 이야기한다.

기본적으로 Matrix Factorization은 SVD 방식과 매우 유사하다. 왜냐하면 평점 데이터를 임의의 K개의 차원을 가지는 Latent Factor로 분해하기 때문이다. 그런데 SVD 방식을 직접적으로 추천시스템에 직접적으로 적용하는 것은 무리가 있다. SVD의 경우 결측치가 존재하면 안되는데 추천 시스템의 평점 데이터에는 수 많은 결측치가 존재하기 때문이고 이 결측치를 임의로 채운다면 데이터의 왜곡 가능성이 매우 높아진다. 따라서 오직 관측된 평점만을 직접적으로 모델링하는 Matrix Factorization 방법을 제시하게 되었다.

Matrix Factorization은 크게 아이템의 Latent Factor와 유저의 Latent Factor를 동시에 추론하는 SGD 방식과 하나의 Latent Factor를 먼저 추론한 후에 그 다음의 Latent Factor를 추론하는 ALS 방식으로 나뉘어 진다. SGD 방식이 간단한 방법이긴 하지만 시스템의 병렬화가 가능하고 암시적 데이터에 집중되어 있다면 ALS가 더 높은 효과를 보인다고 한다.

그런데 실제에 추천시스템 모델을 구축하기 위해서는 사용자의 행동 정보를 반영할 필요가 있으며 현실에서 제품에 대한 인식과 인기 등은 시간에 따라 변화한다. 따라서 추천 시스템은 시간에 따라 변하는 사용자와 아이템 간의 상호작용의 동적인 성질을 반영하여 Temporal Effect에 대하여 설명할 수 있어야 한다.

본 논문에서 제시한 Matrix Factorization은 추천 알고리즘 대회인 Netflix Prize에서 1등을 했으며 현재 까지도 추천 시스템에서 많이 활용되는 바이블과 같은 기술이다.

답글 달기
comment-user-thumbnail
2021년 5월 17일

[14기 이혜린]

  • Content Filtering : 사용자와 제품에 대한 profile 먼저 생성
  • Collaborative Filtering : profile이 없는 상태에서 implicit data (과거 구매이력, 제품평가점수, browsing history 등의 implicit data 사용)
    • Neighborhood Method : 아이템간, 또는 사용자간 거리 계산
    • Latent Factor Method : 아이템에게 주는 rating 점수에는 패턴이 존재할 것. 패턴을 찾아내서 하나의 factor로 추출하고 factor score를 중심으로 근거리를 추정하여 추천
  • Matrix Factorization in CF
    • SVD : missing value가 많으면 과적합 위험 → regularized modeling으로 해결
답글 달기
comment-user-thumbnail
2021년 5월 18일

[15기 권오현]
추천시스템은 크게 Content filtering approach, Collaborative filtering approach로 나뉜다. Collaborative filtering approach는 유저와 아이템 관계를 계산하여 거리가 가까운 것을 추천하는 Neighborhood method와 유저와 아이템 관계의 패턴을 찾아 Latent factor로 표현하는 Latent factor method가 존재한다. Matrix Factorization method는 Latent factor method중 한 가지 방법이다.

Matrix Factorization은 SVD(Singular Value Decomposition)과 유사한데, SVD는 Matrix에 대한 정보가 충분하지 않으면, 즉 Missing Value가 존재하게 되면 추천시스템에 적용하기 곤란하다. 추천 시스템의 경우 Sparse한 데이터가 일반적인데 SVD는 이러한 Sparse한 부분을 inputation을 통해 문제를 해결하여 데이터를 왜곡시킬 위험이 있기 때문이다.

MF는 Stochastic gradient descent(SGD)와 Alternating least squares(ALS) 두 가지 방법이 존재하는데, SGD는 아이템과 유저의 관계에 대한 Latent factor을 학습하는 방법, ALS 방법은 user와 item의 latent factor는 unknown parameters여서 이 둘의 관계에 대한 에러는 Convex 형태가 아니기 때문에 유저와 아이템의 Latent factor를 교대로 fix하여 다른 Latent factor를 학습하는 방법이다.

하지만 소비자의 선호도와 제품/브랜드에 대한 인식은 지속적으로 변화하기 때문에 이러한 현실 세계를 반영하기 위해서는 추천 시스템 모델에 시간에 따른 유저와 아이템의 상호작용을 반영해야 하기 때문에 시간에 따른 아이템과 유저에 대한 biases term을 추가해준 모델을 최종적으로 제안하였다.

답글 달기
comment-user-thumbnail
2021년 5월 19일

[15기 강지우]
추천시스템은 고객이 형성해놓은 선호도에 기반해서 추천하는 collaborative filtering 과 컨텐츠 자체의 특성으로 추천하는 content based filtering이 존재한다. collaborative filtering은 neighborhood based model과 latent factor model로 나뉜다. 본 논문은 latent factor model의 matrix factorization을 SGD, ALS 두 가지 방향으로 진행했다. 성능 향상을 위해 시간에 따라 변화하는 선호도를 고려해서 아이템, 유저, 아이템과 유저의 상호작용 3가지에 대한 시간을 요소로하는 term을 넣어준 것이 인상적이었다.

답글 달기
comment-user-thumbnail
2021년 5월 19일

[15기 장아연]
추천시스템은 콘텐츠가 바탕인 Content filtering approach와 고객의 선호도가 바탕인 Collaborative filtering approach로 구분됨. 콘텐츠 사이, 또는 사용자간 거리를 계산하는 Neighborhood method와 콘텐츠에 평가하는 방식을 찾아내 추출하고 이를 바탕으로 거리를 추청해 추천하는 Latent factor method는
Collaborative filtering approach에 속하며 Matrix Factorization method는 바로 Latent factor method에 속하고 Stochastic gradient descent(SGD)와 Alternating least squares(ALS)로 진행함.

SGD는 아이템, 유저의 Latent factor를 동시에 추론하고 ALS는 한 개씩 차례로 Latent factor를 계산한다.

아이템에 대한 유저의 선호는 시간에 따라 빠르게 변화하기 때문에 각각의 시간을 요소를 bias term을 넣어주어 성능을 향상함.

답글 달기

Recommender System Strategies

  • Content filtering approach: 사용자나 제품에 대한 profile 활용
  • Collabrorative filtering approach: profile이 없는 상태에서 implicit data활용
    • Neighborhood method: 아이템끼리, 사용자끼리 관계를 계산해 거리가 가까운 것을 추천
    • Latent factor method: 아이템에게 주는 rating 점수의 패턴을 추출하여 추천

Matrix Factorization method

  • implicit feedback을 추론. ← sparsity issue 극복 가능

Basic Factorization model

SVD 이용 시 문제점

  • missing value가 많을 경우 matrix 정의가 곤란하거나 overfitting의 위험이 있다.

    ⇒ regularized modeling을 통해 해결

Temporal Dynamics & Inputs with varying confidence levels

제품과 브랜드에 대한 인식 및 인기와 소비자의 선호경향은 지속적으로 변화한다. 또한 광고 등의 단기적인 영향이 있을 수도 있고 의도적으로 rating을 높거나 낮게 주는 소비자도 있을 수 있기 때문에 고려할 사항이 매우 많다.

답글 달기