추천시스템 18 - 경사하강법

추천시스템

본 포스팅은 Minnesota대학교의 Intro to Recommender Systems코세라 강좌를 정리한 내용입니다.

https://www.coursera.org/learn/collaborative-filtering?specialization=recommender-systems

 

SVD의 문제점

SVD는 좋은 테크닉이지만 아래와 같은 문제가 있다:

1. SVD를 계산하는것은 매우 느리다.
2. SVD는 채워지지 않은 데이터에 대해 어떠한 조치를 취해주어야 한다.

따라서 이러한 문제들을 해결하기 위해 경사하강법을 적용해보고자 한다.

 

접근법

경사하강법을 적용하고자 하는 인사이트는, SVD를 사용해 추천을 계산할때의 에러를 직시하는것이다. 선형대수적으로는 SVD를 구한 다음, k만큼의 값을 자르는것이, rank-k를 예측하는 최적의 방법이다. 하지만, 이것을 다른 우회방법으로 더 빠르게 구할 수 있다면 어떨까? 에러를 최소화할 수 있는 방법으로 k-rank 행렬을 구한다면, 기존에 무시할 수 없었던 값들을 무시하고, 경사하강법을 적용해 k-rank 행렬을 구할 수 있을것이라는 가정에서 시작한다. 그리고 가장 중요하게, 빠르게 값들을 구할 수 있다는 장점이 있다.

 

경사하강법

** 머신러닝에 대한 경사하강법은 이 포스팅에서 이야기 하지 않겠습니다.

아래 머신러닝 포스팅에 가면 경사하강법을 설명하고 있습니다:

https://jyoondev.tistory.com/10

 

에러 함수 간소화

경사하강법은 에러(오차)를 최소화 하는 기법이기 때문에, 에러가 명확하게 정의되어 있어야 한다.

 

먼저 문제를 정의합니다: 우리는 행렬R을 분해하기 원한다. $R = P \sum Q^{T}$

경사하강법을 적용할 때 RMSE라는 에러 함수를 사용한다.

(RMSE = Root Mean Squared Error, 오차값을 모두 더해 제곱하고 전체의 수로 나눈 뒤 루트를 씌우는 에러 계산법)

우리는 이 에러의 값 자체에 관심 있는것이 아니라, 값이 최소화 되는 상황에 행렬에 관심이 있다.

그리고 RMSE는 루트를 없앤 MSE와 효과가 비슷하고, N의 개수를 알면 평균도 필요가 없어지기 때문에, SSE (Sum of Squared Error)로 에러함수를 교체합니다. 이 SSE를 minimize 하는것이 RMSE를 minimize하는것과 같은 효과를 내는것을 기대하는 것이다.

 

알고리즘 정의

1. 먼저 행렬의 값들을 0이 아닌 랜덤한 값으로 초기화 한다.
2. 그리고 각 값들을 사용해 기존 데이터셋에 있는 평점들을 예측한다.
3. 예측한 평점과 실제 평점들을 이용해 에러(오차)를 구하고 매번 행렬의 값들을 갱신한다.
4. 위의 작업을 값들이 수렴할때까지 반복한다.
1. 일정한 반복 횟수를 정해놓고 반복할 수도 있고,
2. 에러의 변화값이 일정 수준을 미치지 못할 때 멈추는 방법도 있다.

 

SVD 간소화

기존 수식은 다음과 같다. (B는 Baseline을 의미한다.)

$R = P \sum Q^{T} + B$

먼저 위의 수식에서 $\sum$을 없앤다. 대각행렬은 어차피 rank-k의 결과값에 없을 것이기 때문에, 빼놓고 계산을 진행한다.

$R = B + P Q^{T}$

이에 따라 예측법 또한 간소화가 된다.

가운데 하나의 스칼라값이 사라진 내적곱 하나만 남게 된다. (사용자 예측값과 아이템 예측값)

 

FunkSVD

• Funk라는 사람이 발명한 SVD를 학습하는 기법
• Feature를 한번에 하나씩만 학습시킨다.
• 없는 데이터는 무시한다
• 베이스라인을 사용한다 (사용자의 평균값에서 값들을 학습한다)
• 다음과 같은 수식을 통해 학습한다.

• 예측값 $\epsilon$과 예측수식의 결과값을 사용해 에러를 계산한다.
• 그 에러를 통해 사용자 예측값고 아이템 예측값을 경사하강법으로 학습률 $\lambda$를 사용해 갱신한다.
• $\gamma$값은 정규화 값이다. 일종의 Bias값인데 아주 큰(극적인) 값을 억제하는 효과가 있다.
• 아이템 값을 갱신할 때는 에러에 사용자 값을 곱한 값에서 정규화값인 $\gamma$값을 아이템값에 곱한 값을 빼준다.
• 사용자 값을 갱실할 때는 반대로 에러에 아이템 값을 곱한 값에서 $\gamma$값을 사용자 값에 곱한 값을 빼준다.
• 이 작업을 값들이 일정수준에 도달할때까지 예측하고 갱신하고를 반복한다.
• 스토캐스틱 경사하강법이기 때문에 모든 데이터를 다 예측하고 갱신하는것이 아니라, 정해진 미니배치값으로 갱신한다.

 

SVD와의 차이점

• FunkSVD로 구해진 값들은 사실상 SVD가 아니게 된다. 그 이유는 P와 Q가 직교행렬이 아니게 되기 때문이다.
• 따라서 앞서 이야기한 새로운 데이터에 대한 Folding-in기법은 이 방식에서는 사용할 수 없게 된다.

FunkSVD는 하나의 방식일 뿐이다. FunkSVD처럼 한번에 하나의 특성을 수렴시키는 것이 아니라, 한번에 모든 특성을 수렴시키는 경사하강법도 있고, 경사하강법 뿐만 아니라 최적화 기법이 사용된 어떤 방식이든 예측하는데 사용할 수 있다.

 

SVD와 경사하강법

경사하강법을 갱신할 때는 에러를 계산하고 에러함수를 미분하게 된다.

우선 예측함수는 다음과 같다:

이 함수를 기반으로 예측과 실제 평점을 비교해 에러를 계산하고,

그리고 이 에러를 p와 q에 대해 미분을 한다.

$\frac{d}{dp_{uf}}E^{2}_{ui}, \frac{d}{dq_{uf}}E^{2}_{ui}$

 

FunkSVD에서는 이 작업을 한번에 하나의 특성씩 적용하게 된다.

그리고 스토캐스틱 경사하강법을 사용하게 되는데,

학습 데이터를 한꺼번에 경사하강법에 적용하는것이 아니라,

한번에 한개의 데이터씩 에러를 계산해 적용하게 된다.