Introduction

소비자와 가장 적절한 제품을 매칭하는 것은 사용자의 만족도와 충성도를 높이는 데 중요한 역할을 한다.

좋은 개인화 추천시스템은 사용자 경험에 또 다른 차원을 추가할 수 있기 때문에,
Amazon.com과 넷플릭스 같은 e-commerce 리더들은 추천시스템을 웹사이트의 중요한 부분으로 만들었다.

이러한 시스템은 영화, 음악, 및 TV쇼와 같은 엔터테인먼트 제품에 특히 유용하다.

고객이 특정 영화에 대한 만족도를 나타낼 수 있다는 것이 증명되었기 때문에, 어떤 영화가 어떤 고객에게 어필할 수 있는지에 대한 방대한 양의 데이터를 사용할 수 있다. 회사는 이 데이터를 분석하여 특정 고객에게 영화를 추천할 수 있다.

---

Recommender System Strategies

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

• 콘텐츠 필터링 접근법(Content Filtering Approach)
• 협업 필터링 접근법(Collaborative Filtering)
  • 이웃기반 접근법(Neighborhood based CF methods)
  • 잠재변수모델(Latent Factor Models)

콘텐츠 필터링 접근법(Content Filtering Approach)

콘텐츠 필터링 접근법은 사용자 또는 제품에 대한 profile을 생성하여 그 성질을 특징화하여 추천한다.

예를 들어, 영화 프로필은 장르, 참여하는 배우들, 박스 오피스 인기도 등에 관한 속성들을 포함할 수 있다.

사용자 프로파일에는 적합한 질문지에 제공된 인구 통계 정보 또는 답변이 포함될 수 있습니다.

프로파일을 사용하여 프로그램이 사용자를 일치하는 제품과 연관시킬 수 있습니다.

물론, 컨텐츠 기반 전략은 수집하기가 쉽지 않거나 쉽지 않을 수도 있는 외부 정보를 수집해야 합니다.

장점

user의 이전 데이터를 기반으로 내용 중심의 추천을 하기 때문에

• Cold-Start Problem ( 새로운 아이템 추가시 평가한 사람이 없어 추천이 어려운 문제 )
• Sparsity Problem ( 모든 유저가 모든 아이템을 평가하지 못하기 때문에 발생하는 문제 )

에 대하여 자유롭다.

단점

No first-rater problem : 처음 유입된 user의 경우 어떤 것을 좋아하는지 판단할 데이터가 없기 때문에 추천하기 어렵다.

Content Filtering 대표 예시- Music Genome Project

콘텐츠 필터링의 성공적인 실현은 인터넷 라디오 서비스 (Pandora.com) 를 위해 사용되는 음악 게놈 프로젝트 (Music Genome Project) 이다. 이러한 속성들 또는 유전자들은 노래의 음악적 아이덴티티 뿐만 아니라, 청취자들의 음악적 선호도들을 이해하는 것과 관련된 많은 중요한 특징들을 잡아낸다.

**Music Genome Project**
유전자 마커에는 노래가 음향 또는 전자인지 여부와 같은 기본 속성부터 
리드 가수의 목소리의 자질과 배열의 모든 측면에 이르기까지 모든 것이 포함됩니다. 
불협화음의 하모니, 기타 이펙트, 드럼 및 심벌즈의 특정 사용, 
오케스트라 음악 및 미묘한 영향도 노래의 DNA 맵의 일부가됩니다.

https://www.netinbag.com/ko/internet/what-is-the-music-genome-project.html

---

협업 필터링 접근법(Collaborative Filtering)

협업 필터링 은 (예: 이전 트랜잭션 or 제품 평점) 에만 의존

협업 필터링 은 새로운 user-item 연관성(association)을 찾기위해 users 간 관계(relationship) products간 상호의존성(interdependencies)을 분석한다.

장점

• Domain Free : user나 item들의 profile을 작성하지 않고 이전의 사용자 동작에 의존하기 때문에 해당 도메인에 대한 지식이 크게 필요하지 않다.
• 일반적으로 콘텐츠 필터링 보다 정확하다고 알려져 있다.
  콘텐츠 필터링보다 정확하지만 새 제품이나 사용자를 처리할 수 없기때문에 coldstart 단점 -> 이런 면에서는 콘텐츠 필터링이 더 낫다.

단점

• ColdStart Problem : 새로운 아이템 추가시 평가한 사람이 없어 추천이 어려운 문제
  
• Sparsity Problem : 모든 유저가 모든 아이템을 평가하지 못하기 때문에 발생하는 문제

이웃기반 접근법(Neighborhood based CF methods)

1. User-based collaborative filtering

   User A와 유사한 User가 제공한 등급을 가지고 추천 리스트를 만드는데 사용됨
   
   A의 예상 등급은 각 “피어 그룹” 등급의 가중 평균값으로 계산

2. Item-based collaborative filtering

   대상 Item B에 대한 추천 리스트를 만들기 위해 첫번째 단계는 Item B와 가장 유사한 Item의 집합 S를 결정하는 것
   
   User A의 등급을 예측하기 위해 Item B에서 A가 평가한 집합 S의 등급을 가지고 결정
   
   등급의 가중 평균은 Item B에 대한 User A의 예상 등급을 계산하는 데 사용됨

잠재변수모델(Latent Factor Models)

잠재변수모델(Latent Factor Models) 은 rating patterns 으로부터 20~100개의 잠재적인 차원(Latent Factor)을 추론하는 것을 목적으로 한다.

• 영화의 경우
  코미디 vs 드라마, 액션의 양, 같은 차원을 측정
• 사용자의 경우
  각 Factor는 사용자가 해당 영화 요소에서 높은 점수를 받는 영화를 좋아하는 정도를 측정

이 그림은 영화와 가상의 사용자가 두 차원(여성향 vs 남성향 과 심각함 vs 현실도피)에 속할 수 있는 위치를 보여 준다.

이 모델의 경우, 영화의 평균 평점과 비교하여, 영화에 대한 사용자의 예측된 평점은 그래프 상의 영화와 사용자의 위치들의 내적(dot product) 과 동일할 것이다.

예를 들어, 우리는 Gus가 Dumb and Dumber를 좋아하고, The Color Purple을 싫어하고, Braveheart를 평균적으로 평가하기를 기대할 것이다.

Matrix Factorization Methods

성공적인 잠재변수모델(Latent Factor Models) 는 Matrix Factorization 을 기반으로 한다.

Matrix Factorization 는 아이템 평점 패턴들로부터 추론된 Factor들의 벡터들에 의해 item과 user 모두를 특징화한다. 이때 item과 user 사이에 강한 correspondence를 통해 추천을 하게 된다.

이 방법들은 양호한 확장성(Scalability), 예측 정확도(Accuracy), 실제 상황에 대한 높은 유연성(Flexibility)으로 최근에 인기를 얻었다.

추천 시스템은 다양한 유형의 입력 데이터에 의존한다.

명시적 피드백(Explicit-Feedback)

• 추천 시스템의 가장 편리한 데이터
• 제품에 대한 관심과 관련하여 사용자가 명시적으로 입력하는 것
  • 따봉과 비따봉 / 평점 등
• 희소 매트릭스(Sparse Matrix)를 포함 -> Sparsity Problem 야기

암시적 피드백(Implicit-Feedback)

• 명시적 피드백을 활용할 수 없는 경우 이용 (명시적인 선호도에 대한 데이터가 없거나 미미한 경우)
• 구매 이력, 브라우징 이력, 검색 패턴, 또는 마우스 이동을 포함하는 사용자 행동을 의미
• 일반적으로 이벤트의 존재 또는 부재를 표시 -> 밀도가 높은 매트릭스(Densely Filled Matrix)로 표시 <-> 희소 행렬(Sparse Matrix)

---

A Basic Matrix Factorization Model

Matrix Factorization Model은 user와 item의 결합 잠재요인 공간 $f$ 로 맵핑하는데
user와 item 의 상호작용(interaction)은 공간 $f$ 에서 내적(inner product)로 모델링 된다.

• 각 item $i$ 는 $q_i \in R^f$ 라는 벡터로 표현되고
  • 해당 factor에 대한 item $i$ 의 긍정/부정

• 각 user $u$ 는 $p_u \in R^f$ 라는 벡터로 표현된다.
  • 해당 factor에 대한 user $u$ 의 interest, 긍정/부정

결론적으로 $q_i$ 와 $p_u$ 의 벡터의 내적(dot product)를 통해 user $u$ 와 item $i$ 의상호작용 (유저의 아이템의 특성에 대한 전체적인 관심) $\hat{r_{ui}}$를 얻게 된다.

$\hat{r_{ui}}=q_i^Tp_u$ ------ (1)

이때 $\hat{r_{ui}}$ 은 item $i$ 에 대한 user $u$ 의 평가($rating$)을 추정한 것을 뜻한다.

주요 과제는 item과 user를 $q_i$ 와 $p_u$로 맵핑하는 것으로 맵핑 후에 임의의 user가 item에 대한 평점의 추정값을 (1)에 의해 구할 수 있게된다.

---

이 모델은 SVD(singular value decomposition) 와 밀접하게 관련되어 있다.

하지만 협업필터링 에 SVD를 적용하는 것은 어렵다.

• user-item rating 행렬을 고려해야 하는데 Sparsity Problem 으로 인해 적용하기 어려운 점이 존재한다.(결측값이 너무 많아서)
• 높은 결측치 비율로 인해 맵핑 과정에서 과적합이 일어날 수 있다.
• 정확하지 않은 결측값 대체로 인해 데이터의 왜곡 가능성이 있다.

따라서 관측된 평점만을 직접적으로 모델링하는 방법(2) 제시

$min_{q^*,p^*}\sum_{(u,i)∈\kappa}(r_{ui}−q_i^Tp_u)^2+λ(∥q_i∥^2+∥p_u∥^2)$ ----(2)

• $λ(∥q_i∥^2+∥p_u∥^2)$ : 과적합을 피하기 위한 규제 항 (L2-Norm 규제항)
  • $λ$ :상수(constant)로 규제의 정도를 나타냄 / 주로 cross-validation에 의해 결정
• $\kappa$ : $r_{ui}$ 가 측정된(known) 값일 때의 $(u, i)$ 세트

이 식은 요인벡터 $q_i, p_u$ 를 학습하기 위해 측정된 $r_{ui}$와 예측한 $\hat{r_{ui}}$의 오차를 최소화 하도록 하는 것이다.

---

Learning Algorithms

식(2)-목적식 를 최소화하기 위한 방법 2가지 제시

SGD (Stochastic Gradient Descent)

알고리즘은 트레이닝 세트 내의 모든 평점들을 순환시킨다.
각각의 주어진 트레이닝 케이스에 대해, $r_{ui}$를 예측하고 연관된 예측 에러$e_{ui}$ 를 계산한다.
$e_{ui} = r_{ui} - q_i^Tp_u$

구해진 에러 $e_{ui}$ 를 이용하여 $q_i$ 와 $p_u$를 업데이트 한다.

• $q_i \overset{}{\leftarrow} q_i + γ(e_{ui}-λq_i)$
• $p_u \overset{}{\leftarrow} p_u + γ(e_{ui}-λp_u)$

SGD는 비교적 구현이 쉽고 빠르다는 장점이 있다.
그러나 일부 경우에는 ALS 최적화를 사용하는 것이 유리하다.

ALS (Alternating Least Squares)

ALS 를 설명한 블로그

ALS 는 사용자와 아이템의 Latent Factor를 한번씩 번갈아가며 학습시킵니다.

두 행렬을 한꺼번에 최적화시키는 것은 어렵기 때문에 둘 중 하나를 고정시킵니다.

아이템의 행렬을 상수로 놓고 사용자의 행렬을 학습시키고,

사용자 행렬을 상수로 놓고 아이템 행렬을 학습시키는 방식입니다.

이 과정을 계속 반복하면서 최적의 사용자와 아이템 Latent Factor를 학습시킵니다

https://yeomko.tistory.com/4

in paper

$q_i$와 $p_u$ 모두는 알 수 없기 때문에, 식(2)-목적식 은 convex 하지 않다.

그러나, 만약 우리가 미지의 것들 중 하나를 고정하면 , 최적화 문제는 이차식(quadratic)이 되어 해결할 수 있다.

따라서 ALS 는 $q_i$와 $p_u$를 번갈아 고정한다.
만약 $p_u$를 고정했다면, 최소제곱법으로 $q_i$를 다시 계산한다. (반대도 마찬가지)
이 방식을 통해 식(2)-목적식을 점점 줄이는 것을 보장하게 된다.

앞선 SGD는 일반적으로 ALS 보다 쉽고 빠르지만 2가지 경우에서 ALS가 유리하다.

• 시스템이 병렬화 가능한 경우
• 시스템이 implicit data에 집중된 경우
  - implicit data의 경우 sparse 문제가 발생하는데, 이는 SGD로 계산하기엔 현실적이지 못하다.

---

Adding Biases

예측한 평점 식(1) [$\hat{r_{ui}}=q_i^Tp_u$]에서 사실 많은 경우에 user나 item 자체의 특성(user의 평가 경향성 / item자체의 평점)은 평점 예측에 영향을 미친다.

따라서 이러한 특성을 고려하기 위해 bias 를 추가한다.
이때 $b_{ui}$ 는 bias 로 $r_{ui}$ 에 포함되는 값이다.

$b_{ui} = µ + b_i + b_u$ ----- (3)

• µ : overall average rating (전체 평균 등급)
• $b_i$ : observed deviation(편차) of user u
• $b_u$ : observed deviation(편차) of item i

식(1)에 bias 식(3) 를 추가

$\hat{r_{ui}}=b_{ui} + q_i^Tp_u$
$\hat{r_{ui}}=µ + b_i + b_u + q_i^Tp_u$ ----- (4)

$\hat{r_{ui}}$ 는 4가지 요소 글로벌 평균 $µ$, item-bias $b_i$, user-bias $b_u$ 및 user-item interaction $q_i^Tp_u$으로 구분된다.

식(2)-목적식 에 식(4) 적용한 최종 목적식 식(5)
$min_{q^*,p^*}\sum_{(u,i)∈\kappa}(r_{ui}−q_i^Tp_u)^2+λ(∥q_i∥^2+∥p_u∥^2)$ ----(2)
$\hat{r_{ui}}=µ + b_i + b_u + q_i^Tp_u$ ----- (4)

$min_{q^*,p^*,b^*}\sum_{(u,i)∈\kappa}(µ + b_i + b_u + q_i^Tp_u)^2+λ(∥q_i∥^2+∥p_u∥^2 + b_u^2 + b_i^2)$ -------(5)

bias는 모델의 정확도를 높여주는데 중요한 역할을 한다.

---

Additional Input Sources

Cold Start 문제 해결을 위해 추가적인 정보 Boolean implicit-feedback 과 user attributes 를 사용할 수 있다.

Boolean implicit-feedback

$\sum_{i∈N(u)}^{}x_i$

• $N(u)$ : user $u$ 가 암시적으로 선호를 표현한 item의 집합
• $x_i$ : item $i$와 연관된 벡터 $x_i \in R^f$
  • user와 item의 결합 잠재요인 공간 $f$

이를 Normalize 하면 다음과 같다. (일반적으로 정규화 시 더 좋은 결과)

Boolean implicit-feedback Normalization

$|N(u)|^{-0.5}\sum_{i∈N(u)}^{}x_i$

또다른 중요한 정보는 사용자 속성(user attributes) 이다.
여기서 사용자 속성은 인구 통계(성별, 연령 등)을 예로 들 수 있다.

user attributes

$\sum_{a∈A(u)}^{}y_a$

• $A(u)$ : 성별, 연령 그룹, 등의 boolean 속성 세트
• $y_a$ : distinct vector 로 각 속성에 해당하며 user-associated attributes 집합을 통해 user를 설명

위 두가지 signal source를 MF에 통합시키면 다음과 같은 식이 나온다.

식(6) : Enhanced 식(4) // 두 signal source 을 MF에 결합

$\hat{r_{ui}}=µ + b_i + b_u + q_i^T [p_u+|N(u)|^{-0.5}\sum_{i∈N(u)}^{}x_i +\sum_{a∈A(u)}^{}y_a]$ ------ (6)

---

Temporal Dynamics

지금까지 모델은 정적(static) 한 모델이었다. 현실에서는 제품의 인식과 인기는 끊임없이 변화한다
따라서 시스템은 user-item interaction의 동적인 시간 특성을 반영하는 temporal effects를 고려해야 한다.

모델의 temporal effects 를 적용하기 위해
식(4) 에서 3가지 항이 시간에 따라 변화 한다고 정의한다.

• $b_i(t)$ : item의 인기가 시간에 따라 변경됨

• $b_u(t)$ : user가 시간에 따라 평가의 성향이 변함

  • 작년엔 5점을 준 영화를 올해 기준으로 평가하면 4점을 줄 수 도 있다.

• $p_u(t)$ : 시간에 따라 item에 대한 user의 선호도가 변함

  • 작년엔 스릴러를 좋아했지만, 올해는 로맨스를 좋아할 수 있다.

• $q_i$는 유일하게 static한 vector인데, 이는 item 자체는 시간에 대해서 영향을 받지 않기 때문이다.

이러한 시간 변화를 식(4)에 적용하면 다음과 같다.

식(4)에 temporal effects 적용한 식

$\hat{r_{ui}}=µ + b_i(t) + b_u(t) + q_i^Tp_u(t)$ ----- (7)

---

Inputs with Varying Confidence Levels

관찰된 모든 평점이 동일한 가중치(weight) 또는 신뢰도(Confidence)를 가질 수 있는 것은 아니다.

예를 들어 시스템은 특정 item의 평정을 낮추려하는 적대적 사용자와 직면할 수 있다.

또 다른 예로는 implicit-feedback 을 중심으로 구축된 시스템이다.
implicit-feedback 은 user의 정확한 선호도를 정량화하기가 어렵다.

implicit-feedback 은 user의 정확한 선호도를 정량화하기 어려운 이유
1. No negative feedback(=알 수 없다).
2. Implicit feedback is inherently noisy
3. implicit feedback indicates confidence, not preference
4. Evaluation of implicit-feedback recommender requires appropriate measure
Collaborative Filtering for Implicit Feedback Datasets, IEEE

특히 implicit-feedback 데이터는 선호도(preference)가 아닌 신뢰도(confidence)이기 때문에 이에 대한 가중치를 적용할 필요가 있다.

신뢰도(confidence)는 사용자가 특정 쇼를 시청하는 시간 또는 사용자가 특정 항목을 얼마나 자주 구매하였는지 등의 동작의 빈도를 기술하는 수치 값(numerical values)으로부터 유래할 수 있다.

이러한 수치 값(numerical values)은 각 관측치에 대한 신뢰도(confidence)를 표시한다.

관찰하는 $r_{ui}$에 대해 신뢰도(confidence) 를 $c_{ui}$로 나타낸다면 다음과 같다.

신뢰도(confidence) 특성을 식(5)에 추가

$min_{q^*,p^*,b^*}\sum_{(u,i)∈\kappa}c_{ui}(µ + b_i + b_u + q_i^Tp_u)^2+λ(∥q_i∥^2+∥p_u∥^2 + b_u^2 + b_i^2)$ -------(8)

---

Netflex Prize Competition

논문 구현 링크

Reference

https://western-sky.tistory.com/43
https://databreak.netlify.app/2019-06-06-Neighborhood/
https://yeomko.tistory.com/4
http://yifanhu.net/PUB/cf.pdf