✅ 넷플릭스 프라이즈 대회에서 입증된 바와 같이, 행렬 분해(matrix factorization) 모델은 암시적 피드백, 시간적 요소, 신뢰 수준과 같은 추가 정보를 통합할 수 있어 상품 추천을 생성하는 데 있어 기존의 최인접 기법(nearest-neighbor techniques)보다 우수하다.

0. Introduction

현대 소비자들은 선택의 폭이 넓다.

• 전자제품 리테일러와 콘텐츠 제공업체는 다양한 특별한 요구와 취향을 충족시킬 수 있는 전례 없는 기회와 함께 방대한 제품을 제공
• 소비자에게 가장 적합한 제품을 매칭하는 것이 사용자 만족도와 충성도를 높이는 핵심
• 따라서 사용자의 상품에 대한 관심 패턴을 분석하여 사용자의 취향에 맞는 개인화된 추천을 제공하는 추천 시스템에 관심을 갖는 리테일러가 많아지고 있음

1. Recommender system strategies

일반적으로 추천 시스템은 두 가지 전략 중 하나를 기반으로 한다.

1) 콘텐츠 필터링 방식

정의

콘텐츠 필터링 방식은 각 사용자 또는 제품에 대한 프로필을 생성하여 그 특성을 특성화하는 방식이다.

예시

예) 영화의 경우 장르, 참여 배우, 흥행 인기도 등의 속성이 포함될 수 있다. 프로그램은 프로필을 통해 사용자와 제품을 매칭시킬 수 있다. 물론 콘텐츠 기반 전략은 수집하기 쉽지 않을 수 있는 외부 정보를 수집해야 한다.
예) 판도라닷컴에 사용되는 Music Genome Project가 있다. 여기에서는 전문적인 음악 분석가가 수백 가지의 음악적 특성을 기반으로 뮤직 게놈 프로젝트의 각 곡에 점수를 매긴다. 이러한 특성들은 노래의 음악적 특성뿐만 아니라 청취자의 음악적 선호도를 파악할 수 있는 지표가 된다.

2) 협업 필터링

정의

콘텐츠 필터링의 대안은 명시적인 프로필을 만들지 않고도 과거 사용자 행동(예: 이전 거래 또는 제품 평점)에만 의존하는 방식이다. 이 접근 방식을 협업 필터링이라고 하며, 최초의 추천 시스템인 태피스트리 개발자가 만든 용어이다. 협업 필터링은 사용자 간의 관계와 제품 간의 상호 의존성을 분석하여 새로운 사용자-아이템 연관성을 식별한다.

장점

• 도메인에 구애받지 않으면서도 콘텐츠 필터링으로는 프로파일링하기 어려운 데이터 측면을 다룰 수 있다.
• 일반적으로 콘텐츠 기반 기술보다 정확도가 높다.

단점

• 콜드 스타트 문제: 시스템의 새로운 제품과 사용자를 처리할 수 없기 때문

주요 방법론

1) 이웃 방법(neighborhood methods)

항목 간 또는 사용자 간의 관계를 계산하는 데 중점을 둔다.

• 항목 중심 접근 방식(item oriented approach): 동일한 사용자가 '인접한' 항목의 평점을 기반으로 항목에 대한 사용자의 선호도를 평가하고, 해당 유저가 과거 평점을 매겼던 이웃 아이템을 대상으로 예측한다.
  • 예) 영화 라이언 일병 구하기를 생각해보면 이 영화의 이웃 영화에는 전쟁 영화, 스필버그 영화, 톰 행크스 영화 등이 포함될 수 있다. 라이언 일병 구하기에 대한 특정 사용자의 평점을 예측하려면 이 사용자가 실제로 평점을 매긴 영화의 가장 가까운 이웃 영화를 찾아야 한다.
• 사용자 중심 접근 방식(user-oriented approach): 평점을 예측할 때 이웃 유저(비슷한 유저)를 이용해서 예측한다.
  • 그림 1에서 볼 수 있듯이, 사용자 중심 접근 방식은 서로의 평점을 보완할 수 있는 비슷한 생각을 가진 사용자를 식별한다.

그림1. 사용자 중심의 이웃 방법
조는 왼쪽에 있는 세 편의 영화를 좋아함 → 조를 예측하기 위해 해당 영화를 좋아하는 비슷한 사용자를 찾은 다음 이들이 좋아하는 다른 영화가 무엇인지 확인 → 세 사람 모두 라이언 일병 구하기를 좋아했기 때문에 첫 번째 추천 영화가 됨 → 두 명은 듄을 좋아했으므로 듄이 다음 추천 영화가 됨

2) 잠재 요인 모델(latent factor models)

평점 패턴에서 추론된 20~100개의 요인으로 항목과 사용자 모두를 특성화하여 평점을 설명하려는 대안적인 접근 방식

예) 영화의 경우, 코미디 vs 드라마, 액션의 정도, 어린이에 대한 방침 결정 등과 같은 명백한 관점 혹은 지수 뿐만 아니라, 캐릭터 발달의 깊이 또는 완전히 설명하기 어려운 관점 등과 같은 잘 정의되지 않은 부분들까지도 측정할 수 있다.

그림2. 잠재 요인 접근 방식의 단순화된 그림으로, 남성 vs 여성, 지향적인 사람 vs 현실 도피적인 사람 두 축을 사용하여 사용자와 영화를 모두 특징 짓는다.

2차원 상의 단순화된 예

• 여성(females)과 남성(males) , 지향적인 사람(serious)과 현실 도피적인 사람(escapist)으로 나누고, 잘 알려진 영화와 몇몇 가상 사용자들이 차원에서 어디에 해당하는 지를 보여준다.
• 이 모델의 경우 영화의 평균 평점과 비교하여 영화에 대한 사용자의 예측 평점은 그래프에서 영화 및 사용자 위치의 점 곱(내적)과 같다.

예) 우리는 Gus가 Dumb and Dumber를 좋아하고 The Color Purple은 싫어하며, Braveheart는 중간정도 되리라고 예상해 볼 수 있다.

2. Matrix factorization methods

잠재 요인 모델(latent factor models)의 가장 성공적인 것은 matrix factorization이다.

matrix factorization

아이템의 평점 패턴으로부터 항목과 사용자 모두를 특징 짓고, 항목과 사용자간의 높은 일치는 추천으로 이어진다.

• 최근 몇 년 동안 우수한 확장성과 예측 정확도를 보여주며 인기를 얻고 있다.
• 다양한 실제 상황을 모델링하는 데 많은 유연성을 제공한다.

추천 시스템은 사용자를 나타내는 하나의 차원과 관심 있는 항목을 나타내는 다른 차원으로 행렬에 배치되는 다양한 유형의 입력 데이터에 의존한다.

가장 편리한 데이터

• 등급과 같이 명시적으로 피드백된 데이터 예) 넷플릭스는 영화의 스타 등급을 수집하고, TiVo 사용자는 엄지손가락을 세우고 엄지손가락을 아래로 내리는 버튼을 눌러 TV 프로그램에 대한 선호도를 표시한다.
  
• 일반적으로 사용자는 몇 가지 항목에만 등급을 매겼을 것이기 때문에 명시적 피드백은 희소 행렬이다.

장점

• 추가 정보를 통합할 수 있다.
• 명시적으로 피드백을 사용할 수 없을 때 추천자 시스템은 구매 이력, 브라우징 이력, 검색 패턴 또는 심지어 마우스 움직임을 포함하는 사용자 행동을 관찰하여 간접적으로 의견을 반영하는 암묵적 피드백을 사용하여 사용자 선호를 추론할 수 있다.
• 암시적 피드백은 일반적으로 이벤트의 유무를 나타내므로 일반적으로 촘촘하게 채워진 행렬로 표시됩니다.

3. A basic matrix factorization model

Matrix factorization 모델은 사용자와 아이템을 모두 차원 f의 합동 latent factor 공간에 매핑하고 user-item의 상호작용을 이 공간에 내적하여 모델링 되도록 한다.

• 아이템 i는 벡터 $q_i$ ∈ $\mathbb{R}^f$연관되고, 각 사용자 u는 벡터 $p_u$ ∈ $\mathbb{R}^f$와 연관된다.
• 아이템 i의 경우, 벡터 $q_i$의 원소들은 아이템이 긍정 또는 부정 요소를 얼마나 가지는지 측정
• 사용자 u의 경우, 벡터 $p_u$의 원소들은 긍정 또는 부정 정도가 높은 아이템에 대해 얼마나 선호 하는지 측정
• 내적은 사용자 u와 아이템 i 사이의 상호작용, 즉 아이템의 특성에 대한 사용자의 전반적인 관심도를 나타냄

가장 큰 과제는 각 항목과 사용자를 요인 벡터 $q_i$, $p_u$ ∈ $\mathbb{R}^f$에 매핑을 계산하는 것이다. 추천 시스템이 이 매핑을 완료하면 위 방정식을 사용하여 사용자가 항목에 부여할 평점을 쉽게 예측할 수 있다.

이러한 모델은 특이값 분해(SVD)와 밀접한 관련이 있다.

• 협업 필터링에 SVD를 적용하려면 사용자-항목 평가 행렬을 인수 분해해야 한다.
• 이 과정에서 사용자-항목 평가 행렬의 희소성으로 인한 결측치 비율이 높기 때문에 종종 어려움이 발생한다.
• 기존의 SVD는 행렬에 대한 지식이 불완전할 경우 정의되지 않는다. 또한 상대적으로 적은 수의 알려진 항목만 부주의하게 처리하면 과적합이 발생할 가능성이 높다.

이전 시스템에서는 누락된 평점을 채우고 평점 매트릭스를 밀도있게 만들기 위해 결측값 대체를 많이 했다.

• 그러나 결측값 대체는 데이터 양이 크게 증가하기 때문에 비용이 매우 많이 들 수 있고, 부정확한 대체는 데이터를 상당히 왜곡할 수 있다.
• 따라서 최근 연구에서는 정규화된 모델을 통해 과적합을 피하면서 관찰된 평점만을 직접 모델링할 것을 제안한다.

요인 벡터($p_u$ 및 $q_i$)를 학습하기 위해 시스템은 다음 집합에서 정규화된 제곱 오차를 최소화한다.

시스템은 이전에 관찰된 평점을 맞춰 모델을 학습한다. 그러나 목표는 미래의 알지못하는 등급을 예측하는 방식으로 이전 등급을 일반화하는 것이다. 따라서 시스템은 규모에 패널티를 주는 학습된 매개변수를 정규화하여 관찰된 데이터에 과적합 되지 않도록 해야 한다. 상수 λ는 정규화의 정도를 제어, 일반적으로 교차 검증을 통해 결정된다.

4. Learning algorithms

방정식 2를 최소화하는 두 가지 접근 방식은 stochastic gradient descent과 alternating least squares (ALS)이다.

Stochastic gradient descent(SGD)

Simon Funk는 알고리즘이 훈련 세트의 모든 등급을 반복하는 방정식 2의 확률적 경사 하강 최적화를 대중화했다. 주어진 각 훈련 사례에 대해 시스템은 $r_{ui}$를 예측하고 관련 예측 오류를 계산한다.

그런 다음 gradient의 반대 방향으로 g에 비례하는 크기로 매개변수를 수정하여 결과를 산출한다:

널리 사용되는 이 방식은 구현이 용이하며 비교적 빠르게 실행된다. 그러나 경우에 따라 ALS 최적화를 사용하는 것이 유리할 수도 있다.

Alternating least squares(ALS)

ALS 기법은 q를 고정하는 것과 p를 고정하는 것 사이를 번갈아 가며 사용한다. 모든 p가 고정되면 시스템은 최소제곱 문제를 해결하여 q를 다시 계산하고, 그 반대의 경우도 마찬가지다. 이렇게 하면 각 단계가 수렴할 때까지 방정식 2를 감소시킨다.

일반적으로 확률적 경사 하강이 ALS보다 쉽고 빠르지만, 적어도 두 가지 경우에는 ALS가 더 유리하다.

• 시스템이 병렬화를 사용할 수 있는 경우 ALS에서는 시스템이 다른 항목 요소와 독립적으로 각 q를 계산하고 다른 사용자 요소와 독립적으로 각 p를 계산한다. 이로 인해 알고리즘의 잠재적인 대규모 병렬화가 발생한다.
  
• 암시적 데이터를 중심으로 할 경우 훈련 세트가 희소하다고 볼 수 없기 때문에 경사 하강처럼 각 단일 훈련 사례에 대해 반복하는 것은 실용적이지 않다.
  

ALS는 이러한 경우를 효율적으로 처리할 수 있다.

5. Adding biases

협업 필터링에 대한 matrix factorization의 장점

• 여러 데이터 측면을 다룰 수 있는 flexibility

평점을 전반적으로 높게 주는 사용자가 있고, 그로 인해 일부 항목이 다른 항목보다 높은 평점을 받는다. → 일부 제품은 다른 제품보다 더 나은(또는 더 나쁜) 것으로 인식된다.

• 그러기 위해 $\hat{r}_{ui} = q^T_i p_u$ 수식에 조정이 필요하다.

시스템은 이러한 값 중 개별 사용자 또는 항목 편향으로 설명할 수 있는 부분을 식별하여 데이터의 실제 상호 작용 부분만 요인 모델링에 적용하려고 시도한다.

평점 $r_{ui}$와 관련된 편향에 대한 1차 근사치는 다음과 같다:

$b_{ui}$: $r_{ui}$ 평점과 관련된 편향, $μ$: 전체 평균 평점(global average), $b_i$ : 평균으로부터의 아이템 편차(item bias), $b_u$ : 평균으로부터의 사용자 편차(user bias), $q^T_i p_u$ : user-item interaction

영화 타이타닉에 대한 사용자 Joe의 등급에 대한 1차 추정치를 원한다고 가정:

• 모든 영화의 평균 평점인 µ가 3.7점이라고 가정
• 타이타닉은 평균 영화보다 더 좋아서, 평균보다 0.5점 높은 점수를 받는 경향이 있음
• 반면에, Joe는 평균보다 0.3개 낮은 별을 평가하는 경향이 있는 비판적인 사용자
• 따라서, Joe가 타이타닉을 평가하는 추정치는 3.9개의 별(3.7 + 0.5 - 0.3)이 될 것이다.

regularization term 까지:

bias는 관측된 신호의 많은 부분을 포착하는 경향이 있기 때문에 정확한 모델링이 중요하다.

6. Additional input sources

콜드 스타트 문제

해결 방법:

• 사용자에 대한 추가 정보 소스를 획득한다.
• 추천자 시스템은 암시적 피드백을 사용하여 사용자 선호도에 대한 통찰력을 얻을 수 있다.

실제로 사용자의 명시적 등급 제공 의지와 상관없이 행동 정보를 수집할 수 있다.

예) 소매업체는 고객이 제공할 수 있는 등급 외에도 고객의 구매 또는 검색 내역을 사용하여 고객의 성향을 파악할 수 있다.

단순성을 위해 Boolean으로 암묵적 피드백이 있는 경우를 고려한다.

• $N(u)$는 사용자 $u$가 암묵적 선호도를 표현한 항목 집합을 나타낸다.
• 이러한 방식으로 시스템은 사용자가 암시적으로 선호하는 항목을 통해 사용자를 프로파일링한다.

여기서 항목 i가 $x_i$ ∈ $\mathbb{R}^f$ 와 연결된 새로운 항목 요인 집합이 필요하다. 따라서, $N(u)$의 항목에 대한 선호도를 보인 사용자가 벡터에 의해 특징지어진다.

예를 들어, 합을 정규화하는 것은 도움이 된다.

다른 정보 소스는 알려진 사용자 속성(예: 인구 통계)이다. 사용자 $u$가 성별, 연령 그룹, 우편 번호, 소득 수준 등을 설명할 수 있는 속성 집합 $A(u)$에 해당하는 Boolean 속성을 고려하면 고유한 요인 벡터 $y_a$ ∈ $\mathbb{R}^f$는 사용자 관련 속성 집합을 통해 사용자를 설명하는 각 속성에 해당한다.

matrix factorization 모델은 사용자 표현이 향상된 모든 신호 소스를 통합해야 한다.

7. Temporal dynamics

새로운 선택들이 등장하면서 제품에 대한 인식과 인기는 지속적으로 변화하고 있다. 마찬가지로, 고객의 성향도 바뀌기 때문에 고객의 취향을 재정의 하도록 유도한다. 따라서, 시스템은 사용자-항목 상호 작용의 동적이고 시간이 흐르는 특성을 반영하는 시간적 효과를 설명해야 한다. matrix factorization 접근법은 시간적 효과를 모델링하면 정확도를 크게 향상시킬 수 있다.

1) 아이템의 인기가 시간이 지남에 따라 변할 수 있다는 사실

예) 영화는 배우의 등장과 같은 외부 사건에 의해 인기가 오르내릴 수 있다.

2) 시간이 지남에 따라 사용자가 기준 평점을 변경할 수 있다.

예) 영화에 평균적으로 4점을 부여하는 경향이 있던 사용자는 시간이 흐른 뒤에는 평균적으로 3점을 부여하도록 변할 수 있다.

3) 사용자는 시간이 지남에 따라 선호도가 바뀌므로 Temporal dynamics는 사용자 선호도에 영향을 미치고, 사용자와 항목 간의 상호 작용에도 영향을 미친다.

예) 심리 스릴러 장르의 팬은 1년 후 범죄 드라마의 팬이 될 수도 있다. 마찬가지로 인간은 특정 배우와 감독에 대한 인식이 바뀐다.

$b_i$ : item bias(trend) ⇒ $b_i(t)$
$b_u$ : user bias(taste) ⇒ $b_u(t)$
$p_u$ : user preference(taste) ⇒ $p_u(t)$

8. Inputs with varying confidence levels

모든 평점들이 동일한 신뢰도를 갖는 것이 아니다.

• 대규모 광고 ⇒ 장기적 특성을 적절히 반영x 특정 아이템에 치중
• 별점 테러 등 고의적으로 평점을 낮추려는 적대적인 사용자
• implicit 피드백을 중심으로 구축된 시스템 ⇒ 사용자의 정확한 선호 수준은 정량화하기 어렵다.

따라서 이 시스템은 "아마도 제품을 좋아할 것" 또는 "아마도 제품에 관심이 없을 것"이라고 명시하는 cruder binary 표현법을 사용한다. 이러한 경우 추정된 선호도와 함께 신뢰 스코어를 첨부하는 것이 가치 있다.

예) 신뢰 스코어는 사용자가 특정 쇼를 얼마나 시청했는지 또는 사용자가 특정 품목을 얼마나 자주 구입했는지와 같은 행동 빈도를 설명하는 사용 가능한 수치에서 비롯될 수 있다.

• $r_{ui}$ 관측에 대한 신뢰: $c_{ui}$

  덜 의미있는 관측에 더 적은 가중치를 부여, 반복적인 event에 가중치를 크게 부여

• 최종 $\hat{r}_{ui}$

  

9. Netflix prize competitions

대회 설명

2006년, 온라인 DVD 대여 회사인 넷플릭스는 추천인 시스템의 상태를 개선하기 위한 대회를 발표했다.

• 회사는 약 50만 명의 익명 고객과 고객이 평가한 17,000편 이상의 영화를 포함한 1억 건 이상의train 세트를 제공
• 영화는 별 1개에서 5개의 등급으로 평가됨
• 참가 팀은 약 300만 테스트 세트에 대해 예측된 평점을 제출하고 넷플릭스는 제곱근 오차(RMSE)를 계산

평가 기준

넷플릭스 알고리즘의 RMSE 성능을 10% 또는 그 이상 향상시킬 수 있는 첫 번째 팀은 100만 달러 상금을 받는다. 만약 어떤 팀도 10% 목표에 도달하지 못한다면, 넷플릭스는 매년 대회 후에 1등으로 그 팀에게 50,000 달러의 진행 상금을 준다.

화제의 대회

지금까지 협업 필터링 연구를 위해 공개적으로 사용할 수 있는 유일한 데이터는 규모가 작았으므로 이 대회는 협력 필터링 분야에서 화제였다.

• 대회 웹사이트(www.netflixprize.com)에 따르면, 182개국에서 온 48,000개 이상의 팀이 이 자료를 다운로드 했다.

Matrix factorization

넷플릭스 사용자-영화 행렬을 인수분해(factorization)하면 영화 선호도를 예측하기 위한 가장 설명력이 좋은 차원을 발견할 수 있다. 우리는 행렬 분해에서 처음 몇 개의 가장 중요한 차원을 식별하고 이 새로운 공간에서 영화의 위치를 탐색할 수 있다.

그림 3은 넷플릭스 데이터 행렬 인수분해의 처음 두 요인을 보여주며, 영화는 요소 벡터에 따라 배치된다. 영화를 잘 아는 사람은 잠재 요소에서 명확한 의미를 볼 수 있다.

사진 3. 넷플릭스 상금 데이터의 행렬 분해에서 처음 두 벡터. 선택된 영화는 2차원의 요인 벡터를 기반으로 적절한 위치에 배치된다. 줄거리는 강력한 여성 주연의 영화 무리, 사교성 유머, 기발한 독립 영화를 포함하여 뚜렷한 장르를 보여준다.

x축

첫 번째 요소 벡터(x축)는 한쪽에는 남성 또는 청소년 관객(Half Baked, Freddy vs Jason)을 겨냥한 저급 코미디 및 공포 영화가 있고, 다른 한쪽에는 serious undertones과 여성 주연(Sophie's Choice, Moonstruck)이 이끄는 드라마 또는 코미디가 있다.

y축

두 번째 요인화 축(y축)에는 독립적이고 비평가들의 호평을 받은 기발한 영화들(Punch-Drunk Love, I Heart Huckabees)이 상단에, 그리고 하단에는 주류 공식 영화들(Armageddon, Runaway Bride)이 있다.

이 경계들 사이에는 흥미로운 점들이 있다. 왼쪽 상단에는 indie와 lowbrow가 만나는 '킬 빌(Kill Bill)'과 '내추럴 본 킬러(Natural Born Killers)'가 있는데, 둘 다 폭력적인 주제를 연기하는 예술 영화이다. 오른쪽 하단에는 여성 주도의 진지한 영화들인 사운드 오브 뮤직(The Sound of Music)이 있다. 그리고 중간에 있는 것은 모든 종류의 사람들에게 매력적인 "오즈의 마법사"이다.

서로 이웃한 일부 영화는 일반적으로 같이 놓이지 않는다. 예를 들어 Annie Hall과 and Citizen Kane이 옆에 있는데 스타일적으로는 매우 다르지만 유명 감독들이 높이 평가하는 고전 영화라는 공통점이 많다. 실제로 인수분해(factorization)의 세 번째 차원은 이 두 가지를 분리한다.

인수분해를 위해 여러 가지 다양한 구현과 매개변수화를 시도했다. 그림 4는 factorization의 성능뿐만 아니라 다양한 모델과 매개변수 수가 RMSE에 어떤 영향을 미치는지 보여준다.

그림 4. Matrix factorization 모델의 정확도. 파라미터의 차원이 증가할수록 정확도가 좋아지고, 설명이 더 명확한 매개 변수 세트를 포함할수록 정확하다.

즉, 파라미터의 차원이 증가할수록 정확도가 좋아지고, 설명이 더 명확한 매개 변수 세트를 포함할수록 정확하다.

10. Conclusion

Matrix factorization 기술은 협업 필터링 기법 내에서 유명한 방법론이 되었다.

• 넷플릭스 상금 데이터와 같은 데이터 세트에서 이전의 nearest-neighbor 기술보다 우수한 정확도를 제공한다는 것을 보여주었다.
• 시스템이 상대적으로 쉽게 학습할 수 있도록 메모리를 많이 차지하지 않는 효율적인 모델이다.
• 모델이 여러 형태의 피드백들, 시간 역학 및 신뢰 수준과 같은 데이터의 많은 중요한 측면을 자연스럽게 통합할 수 있어 더욱 편리하다.