[RecSys] Matrix Factorization

오늘은 추천 시스템의 Matrix Factorization(MF)을 리뷰해보고자 한다.

 

리뷰에 앞서 협업 필터링의 두 가지 방식에 대해 짚고 넘어가자.

 

협업 필터링의 두 가지 방식

 

Memory-based Approach

 

Memory-based Approach는 추천할 때마다 Raw 데이터를 활용하고 계산해서 이를 추천에 사용하는 방식이다. 기본적인 협업필터링 알고리즘은 모두 메모리 기반 알고리즘이라고 보면 되고, 이는 계산량이 많기 때문에 현실에서 빅데이터를 사용한 모델에는 적합한 방법은 아니다.

 

Model-based Approach

 

우리가 오늘 살펴보고자 하는 Model-based Approach는 Raw 데이터로 미리 학습한 모델을 만들어두고, 추천 시에 학습한 모델을 사용하여 예측하는 방식이다.

 

Model-based Approach의 경우, 주기적으로 업데이트할 필요가 있으며, Weak Signal도 파악할 수 있기에 여러 사용자들 사이에서 나타나는 약한 패턴도 파악할 수 있다는 장점이 존재한다. 이는 여러 개의 데이터를 동시에 고려하여 공통된 Feature를 추출할 수 있기에 메모리 기반 모델보다 Robust하다는 특징이 있다.

 

Model-based Approach는 모델 학습에 많은 컴퓨팅 자원이 필요하지만, 예측을 진행할 때에는 만들어진 모델만 사용하기에 적은 자원이 들어가기에 많이 선호되는 방식이다. 오늘 우리가 살펴볼 Matrix Factorization도 이 방법에 포함된다고 생각하면 된다.

 

Latent Factor Model

 

MF는 모델기반 협업필터링의 한 종류로, 유저와 아이템간의 관계를 학습하는 모델이다. 유저와 아이템이 가지는 잠재적인 특징을 모델링하고 이를 Latent Factor Model이라고 하는데, MF는 Latent Factor Model의 한 종류라고 이해할 수 있다.

 

Latent Factor Model은 잠재 요인 모델로 해석할 수 있다. 이는 유저와 아이템의 Feature를 벡터로 간략화하는 모델링 기법이다. 일반적으로 유저와 아이템은 서로 다른 Feature를 가지고 있고, 이들이 어떤 관계를 가지는 지 학습하게 된다. 이 때, 유저와 아이템을 나타낸 벡터의 길이는 같기 때문에, 같은 벡터 공간 안에 표현할 수 있게 된다.

 

아래는 패션플랫폼에서의 유저와 아이템의 Feature를 파악하기 위해 Latent Factor를 분석했다고 가정한 것이다. 이는 Latent Factor가 2차원으로 표현된 예시로, x축과 y축 방향으로 각 유저와 아이템의 벡터 위치가 표현되어 있다. 유저와 아이템이 차원이 같은 벡터로 표현되었기에 같은 공간에 표현이 가능하고 서로의 유사도를 파악할 수 있게 된다.

 

실제로 Latent Factor Model은 위의 예시처럼 2차원이 아니라, 차원의 수가 정해지지 않은 차원에 표현될 수도 있고, 차원의 수가 여러 개일 수도 있다. 더불어, 위의 예시처럼 벡터로 명확한 특징을 파악할 수 있는 것은 아니다. 말 그대로 잠재적 특성을 파악하는 것이기에 아이템(또는 유저)을 표현한 Factor는 사람이 명시적으로 이해할 수 없다.

 

다시 사진의 예시로 돌아와보자. x축의 $+$로 갈수록 Maximal 패션이고 y축의 $+$로 갈수록 Boyish한 패션이라는 것은 Factor의 공간맵핑을 통해 얻어진 휴리스틱한 판단을 표현한 것일뿐, 각 차원이 실제로 명시하는 특징은 아니다.

 

Latent Factor Model을 한줄로 정리하면, 성향을 파악하기 위해 각 유저와 아이템을 잠재 Factor로 표현하고, 이를 같은 공간에 맵핑이 가능하기에 서로의 거리나 각도 등을 통해 유사도를 파악하여 잠재적인 취향을 파악할 수 있게 되는 것이다.

 

SVD

 

Latent Factor Model의 한 종류라고 했던 MF 모델을 알아보기 이전에 알아야 할 선형대수 개념이 바로 SVD(특이값 분해)다.

위 식은 $A$라는 행렬을 $U$,  $\sum$, $V$라는 행렬로 분해하는 것을 확인할 수 있다.

• $U$: 고유값 분해로 얻은 m x m 직교행렬
• $V$: 고유값 분해로 얻은 n x n 직교행렬
• $\sum$: m x n 대각행렬

 

여기서 핵심은 $\sum$ 시그마 행렬이며, 이 시그마 행렬을 이용하여 $A$를 다시 복원하는 데 사용할 것이다. (뒤에서 추가 설명) 이 $\sum$ 행렬은 $A$의 특징이 담겨져 있는 행렬로, 이 행렬에 대해 양쪽의 U와 V 행렬이 분해되는 것이라고 이해하면 된다.

 

이렇게 SVD는 행렬을 분해하여 좀 더 작은 차원의 행렬로 표현하는 기법이기에 차원축소기법 중 하나이다. (SVD는 다양한 종류로 나뉨)

 

이해를 위해 Truncated SVD를 추가로 살펴보자.

 

위의 Full SVD는 앞서 설명한 SVD의 기본 형태로, $A$(m x n) 행렬을 $U$(m x m) * $\sum$(m x n) * $V^T$(n x n)으로 분해하고 있다. Truncated SVD는 $\sum$을 k x k 크기 만큼만 사용하고 있다. 이에 따라 양 옆의 $U$와 $V$ 행렬의 모양도 변형됨을 확인할 수 있다. $\sum$는 대각행렬로 앞에서부터 중요한 정보를 담고 있는 원소가 정렬이되어 있다. 이 중 K개의 대각 원소만 사용하더라도 A의 행렬의 특징을 잘 담는 행렬이라고 보는 것이다. k x k의 크기만 사용하면 당연히 원래 A 행렬을 완전히 표현하지는 못하지만, 이렇게 표현된 A'은 중요한 특징만으로 거의 근사하게 복원된 행렬로써 좀 더 적은 계산과 좀 더 작은 크기로 표현할 수 있다는 특징을 가지고 있다.

 

우리는 이러한 SVD를 사용하여 MF를 구현한다. 

 

Matrix Factorization

 

MF는 Latent Factor Model인데, 핵심은 유저와 아이템의 잠재 요인을 벡터화한다는 것이다. MF의 기본 형태는 아래와 같다.

 

추천시스템의 구현을 위해 유저가 아이템에 매긴 평가 (Explicit Feedback) 또는 행동데이터 (Implicit Feedback) 등이 Sparse Matrix로 표현이 되어있을 것이다. 이 행렬을 $R$이라고 하자. 이 행렬을 두개의 행렬로 쪼개면 하나는 User에 대한 Latent Factor가 담긴 행렬, 하나는 Item에 대한 Latent Factor가 담긴 행렬이 된다. 위의 그림 속 노랜색 행렬에는 각 유저들에 대한 잠재 벡터가 행(row)방향으로 구성되어 있고, 연두색 행렬 속에는 각 아이템에 대한 잠재 벡터가 열(col) 방향으로 구성되어 있는 형태다.

 

이 때, 각 유저와 각 아이템은 정해진 길이 만큼의 벡터로 정의되고 이 벡터의 길이 K는 직접 정해야한다. 행렬의 크기로 MF의 형태를 다시 정리하면, m명의 유저와 n명의 아이템 사이의 평점 데이터를 분해하게 된다. 이 때 유저와 아이템의 잠재 벡터를 담은 두개의 행렬로 쪼개게되고 하나는 m명의 유저에 대한 길이가 K인 벡터가 담긴 m x n 행렬, 하나는 n개의 아이템에 대한 길이 k 벡터가 담긴 k x n 행렬이다.

 

MF는 SVD를 통해 구현될 수 있고 이를 앞에서 잠깐 언급한 Truncated SVD를 통해 자세히 뜯어보자.

 

위 그림을 살펴보면, Truncated SVD를 통해 유저와 아이템 간의 Sparse Matrix를 세개의 행렬(m x k, k x k, k x n)로 쪼개어 근사하게 표현할 수 있다. 그런데, MF는 총 두 개의 행렬로 쪼개어 구성되어야 하고 이는 Truncated SVD를 통해 구현할 수 있다.

 

왼쪽 아래를 보면, 주황색으로 표현되어있던 U'행렬과 파란색으로 표현된 $\sum$' 행렬을 곱하여 m x k 행렬을 만들었다. 또한 오른쪽 아래를 보면, 파란색으로 표현된 $\sum$'과 초록색의 $V'^T$ 행렬을 곱하여 k x n 행렬을 만들어주었다. 둘 중 어떤 방법을 사용해도 괜찮으며, 우리는 MF의 기본 형태인 유저의 잠재벡터모음 행렬 m x k, 아이템의 잠재벡터모음 행렬 k x n을 만들어주면 된다.

 

이 쪼갠 행렬들은 (m x n) * (k x n) 곱을 통해 다시 m x n의 행렬로 복원할 수 있고 이 복원한 행렬이 예측행렬이 되는 것이다.

 

그러나, 유저와 아이템 간의 평점 행렬은 Sparse Matrix하다. 이 행렬을 분해하기 위해선 행렬에 빈공간이 없는 형태여야하며, 빈공간은 보통 0 또는 평균값으로 대체하게 된다.

 

MF의 형태를 이해하기 위해 SVD를 살펴봤다. 그러나, 실제로 MF는 SGD등의 Optimization을 통해 학습이 가능하다.

 

MF 학습과정

 

Objective Function

 

MF는 모델 기반 협업필터링이고 유저와 아이템의 잠재 벡터를 학습해야한다. 때문에 목적함수가 정의되어 있고 이를 기반으로 Optimization 과정을 거치게 된다. 우리가 가지고 있는 유저와 아이템 간의 상호작용을 나타낸 행렬은 Sparse 하기에 행렬의 빈공간을 채워나가는 matrix completion 문제로 정의할 수도 있다. 학습을 위해선 Sparse Matrix 안에서 관측된 값들을 가지고 비교해나가며 학습을 하게 된다.

 

위 수식은 MF의 Objective Function다. 이 때 실제로 관측된 값(평점)에 대해 학습을 진행하기 위해서 그 위치에서 계산되는 예측평점과 실제평점을 반영해준다. 따라서 위 수식에서 시그마 아래에 있는 T는 관측된 유저와 아이템들의 집합이라고 볼 수 있다. 

 

 

위 Object Function은 크게 두가지로 구분하여 볼 수 있다. 첫번째 빨간색으로 표시한 부분이 실제 평점과 예측평점간의 오차를 나타낸다. 그리고 이 오차를 제곱하여 더해준다. 두번째 파란색으로 표시한 부분은 정규화 텀이다. 이는 L2 정규화를 의미하며, 각각의 유저와 아이템 행렬이 너무 커지지 않도록 정규화해주고 있다. 이 두가지의 식을 모두 더하여 최소화(MIN) 하는 것이 최종 목표다.

 

정리하자면 (1) 행렬의 크기를 제한해주면서 (2) 실제평점과 예측평점간의 오차를 줄여나가는 방향으로 학습해나가게 된다.

 

Optimization

 

목적함수를 알아보았으니, 학습 단계에서의 Optimization 과정을 살펴보자. MF에서는 주로 SGD 방법을 사용하며, 추가로 ALS 방식에 대해서도 설명한다.

 

SGD(Stochastic Gradient Descent)

 

 

SGD의 과정을 위해선 먼저 Gradient를 구해주어야 한다. 위에서 본 목적함수를 유저벡터와 아이템벡터를 기준으로 각각 편미분 해주게 된다.

 

유저의 Latent Vector를 업데이트 해주기 위해서 현재 Latent Vector에서 $x_u$로 편미분한 결과를 빼주어 업데이트 하게된다. 위의 사진에서 초록색으로 밑줄을 그은 식이 그 $x_u$의 편미분한 Gradient에 해당하고 이를 오른쪽의 업데이트 식에서 Learning Rate를 곱해주었기 때문에 부호가 반대로 변함을 확인할 수 있다.

 

아이템의 Latent Vector를 업데이트 해주는 방법도 동일한 방법으로 진행이 된다. 현재 Latent Vector에서 $y_i$를 편미분하여 해당 Gradient를 Learning Rate와 곱하여 현재 아이템의 Latent Vector에서 뺀 다음 새로운 $y_i$로 업데이트 하게 된다.

 

SGD 예시

 

위의 과정을 실제 예시로 살펴보자.

 

 

영화를 예시로 들어보자. 4명의 유저가 3개의 영화에 대해 직접 매긴 평점데이터가 있다고 생각하자. 유저들이 모든 영화를 보는 것은 아니기 때문에, 평가가 내려지지 않은 부분에 대해선 ?(NaN)로 표시해둔다.

 

먼저 User Latent Vector와 Item Latent Vector를 랜덤으로 초기화한 후 시작해보자. 그림에서 X가 유저행렬, Y가 아이템행렬이고 각 유저별로 길이가 2인 잠재벡터들이 4개씩, 각 아이템별로 길이가 2인 잠재벡터 3개가 정의되어 있음을 확인할 수 있다. 우리는 해당 행렬 2개를 곱하여 예측행렬을 도출할 수 있다. 가장 오른쪽에 보이는 4 x 3 행렬처럼, X와 Y를 곱하여 예측평점이 계산된 행렬이 등장함을 볼 수 있다.

 

우리가 다음에 할 것은 도출해낸 4 x 3 행렬과 실제 평점행렬의 오차를 비교하여 학습하는 것이다.

 

위 그림은 전 학습과정을 모두 담은 그림으로 차근차근 하나씩 살펴보자. MF 학습과정에서는 관측된 데이터를 가지고만 학습이 가능하다고 했는데, 가장 첫번째 순서인 Error를 구하는 과정을 살펴보자.

 

• 가장 첫번째 순서인 에러를 구하는 과정을 살펴보자. 1번 유저가 2번영화에 대해 매겼던 4점이라는 실제평점과, 예측행렬로부터 나온 예측평점 간의 오차를 구해주는 과정이라고 이해하면 된다. 관측되지 않은 1번 영화는 건너뛰고, 관측된 영화에 대한 비교를 진행하는 모습이다.

 

• 두번째로, Gradient를 구해야 한다. 앞에서 User Latent Vector와 Item Latent Vector 각각을 기준으로 Object Function을 편미분해주었으며, 편미분 계산식을 따라 값을 그대로 계산해주는 과정이다. (람다는 정규화율로, 임의로 0.01로 설정)
  • 현재 우리는 1번 유저에 대한 2번 영화를 보고 있다. 그렇다면, 업데이트를 해주어야 하는 벡터의 기준도 1번 유저의 Latent Vector, 2번 영화의 Latent Vector를 반영해주어야 하며, Gradient 계산시에 넣어주는 벡터도 $y_i$는 2번 영화의 Latent Vector, $x_u$는 1번 유저에 대한 잠재벡터임을 확인할 수 있다.

 

• 세번째로 Gradient를 계산했다면, 이를 그대로 학습율(Learning Rate)에 곱하여 업데이트 해주고자 하는 벡터에서 빼주면 된다. (학습율은 0.1로 설정)
  • 3번의 계산과정에서 확인할 수 있듯이 2번 과정에서 구해준 Gradient와 0.1을 곱하여 현재 업데이트 하고자 하는 벡터에서 그 값을 빼주고 있다. 이렇게 나온 벡터가 업데이트 된 새로운 Latent Vector이며, 이전 벡터 대신 교체해주면 된다.

 

 

위 그림처럼 1번 유저의 Latent Vector 대신에 새로 업데이트 된 잠재벡터로 교체해주고, 2번 영화 위치의 잠재벡터 대신에, 새로 업데이트 된 잠재벡터로 교체해주면 된다. (이 과정을 모든 관측 평점에 대해 반복해주면 된다!!)

 

ALS(Alternating Least Squares)

 

MF에서는 SGD 말고도 ALS로 불리는 최적화기법도 적용해볼 수 있다. 이는 $x_u$와 $y_i$ 둘 중 하나를 고정하고 식을 2차식 문제로 풀 수 있는 기법이다. 이름과 같이 Least Square 문제를 풀게되고 하나를 고정하고 독립적으로 계산하기에 병렬처리에 사용할 수 있다는 장점이 존재한다.

 

(ALS 예시는 생략한다.)

---

Reference

https://uoahvu.tistory.com/entry/Matrix-Factorization-%EA%B0%9C%EC%9A%94%EC%99%80-%EC%9B%90%EB%A6%AC%EB%B6%80%ED%84%B0-%EC%B5%9C%EC%A0%81%ED%99%94SGD-ALS%EA%B9%8C%EC%A7%80-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

Matrix Factorization : 개요와 원리부터, 최적화(SGD, ALS)까지 이해하기

https://yeong-jin-data-blog.tistory.com/entry/%EC%B6%94%EC%B2%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Matrix-Factorization

추천 알고리즘 - Matrix Factorization