[추천시스템] (잠재요인) 모델 기반 협업 필터링(1) - 경사하강법(SGD)

저번에는 추천시스템의 이웃 기반 협업필터링에 관하여 다루었습니다.

[추천시스템] 이웃 기반 협업필터링 (1) - 사용자 기반

 

[추천시스템] 이웃 기반 협업 필터링(2) - 아이템 기반

오늘은 모델 기반 협업 필터링 중 경사하강법(SGD)에 대하여 알아보겠습니다.

참고한 링크는 다음과 같습니다.

• https://yamalab.tistory.com/89
• https://yamalab.tistory.com/92
• https://lsjsj92.tistory.com/564
• https://www.kaggle.com/code/chocozzz/00-sgd-1
• 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

모델 기반 협업 필터링에는 여러 다른 방법들이 존재합니다.

• 규칙 기반 협업필터링
• 나이브 베이즈 협업필터링 
• 등등

여기서는 잠재요인 협업필터링에 관하여 다루겠습니다.

잠재 요인 협업필터링은 잘 알려진 차원 축소 방법을 활용하여 NULL(사용자가 평가 하지 않은 아이템)을 채우게됩니다.

차원 축소는 기본 차원의 데이터를 적은 차원으로 표현하는데 대부분의 차원 축소는 아래와 같은 행렬분해(Matrix Factorization)으로 표현이 가능합니다.

$$R = UV^{T}$$

이때 $R$은 $m \times n$이고 $U$는 $m \times k$, $V$는 $n \times k$로 $V^{T}$는 $k \times n$으로 행렬분해됩니다.

여기서 $U$, $V$의 각 행과 열은 사용자, 아이템 잠재벡터(잠재행렬) 혹은 잠재 요인이라고 부릅니다.

$$\hat{R} \approx{}  UV^{T}$$

분해된 $U$, $V^{T}$를 $UV^{T}$를 계산하면 $R$과 유사하며 동일한 크기의 행렬이 생성이 됩니다. 이때 행렬이 재 생성되면 빈공간이 채워지게 되는데 협업필터링에서 NULL값을 채우는 것을 이용하는 것입니다.

 

여기서 $U$, $V$의 요소들을 이용해서 예측값$\hat{r_{ij}}$을 구하게 됩니다.

$$\hat{r_{ij}} = \sum_{s=1}^{k} u_{is} \cdot v_{js}$$

 

관측값($r_{ij}$)과 예측값($\hat{r_{ij}}$)의 차이를 줄여서 우리가 예측한 값($\hat{r_{ij}}$)이 최대한 관측값과 가까워지는 것이 목적입니다.

 

아래는 목적함수($cost==loss$)를 정의한 것입니다.

 

$$MinJ(Loss) = \frac{1}{2} \sum_{(i, j) \in{S}}^{} e_{ij}^{2}$$

 

여기서 $e_{ij}$는 관측값과 예측값의 차이로 아래와 같습니다.

$$e_{ij} = (r_{ij} - \hat{r_{ij}})$$

$$ = r_{ij} - \sum_{s=1}^{k} u_{is} \cdot v_{js}$$

 

목적함수를 다시 표현하면 다음과 같습니다.

$$MinJ(Loss) = \frac{1}{2} \sum_{(i,j)\in{S}}^{}(r_{ij}-\sum_{s=1}^{k} u_{is} \cdot v_{ks})^{2}$$

 

그리고 모델이 과적합이 되는 것을 방지하기 위하여 위의 목적함수에 아래의 정규화 과정을 추가합니다.

$$\frac{\lambda{}}{2}(||U||^{2}+||V||^{2})$$

 

결과적으로 구해야하는 목적함수는 아래와 같습니다.

$$MinJ(Loss) = \frac{1}{2} \sum_{(i,j)\in{S}}^{}(r_{ij}-\sum_{s=1}^{k} u_{is} \cdot v_{ks})^{2} + \frac{\lambda{}}{2}(||U||^{2} + ||V||^{2})$$

 

---

SGD(Stochastic Gradient Descent) - 확률적 경사하강법

위에서 언급했듯이 예측값이 관측값과 가까워지도록 하는 것이 목적입니다.

$u_{is}$, $v_{js}$를 목적함수가 최소화되도록 학습하여 구할 수 있습니다.

목적함수가 최소화가 되었다는 의미는 기울기가 0에 가장 가깝다는 의미이며 편미분을 사용하여 기울기를 구하여 계산할 수 있습니다.

$u_{is}$, $v_{js}$에 대한 $J$의 편미분을 계산하면 식은 다음과 같습니다.

 

$$\frac{\partial J}{\partial u_{ij}} = \sum_{j:(i,j)\in{S}}(r_{ij}-\sum_{s=1}^{k} u_{is} \cdot v_{js})(-v_{jq})+\lambda u_{iq}$$

$$= \sum_{j:(i,j)\in{S}}^{} (e_{ij}) (-v_{iq}) + \lambda u_{iq}$$

 

$$\frac{\partial J}{\partial v_{ij}} = \sum_{j:(i,j)\in{S}}(r_{ij}-\sum_{s=1}^{k} u_{is} \cdot v_{js})(-u_{iq})+\lambda v_{jq}$$

$$= \sum_{j:(i,j)\in{S}}^{} (e_{ij}) (-u_{iq}) + \lambda v_{jq}$$

 

기울기를 구했으면 기울기가 0에 가까워지도록 기울기를 이용하여 값을 갱신할 수 있습니다.

이때 $\alpha$가 등장하는데 learning rate(학습률)이라고 하며 경사하강법에서 기울기를 통하여 값이 최적화가 될 때 얼만큼의 보폭으로 내려갈지 결정해주는 step size에 해당합니다.

 

값을 갱신하는 식은 아래와 같습니다.

$$u_{iq} \Leftarrow u_{iq} - \alpha \cdot [\frac{\partial J}{\partial u_{iq}}]$$

$$v_{jq} \Leftarrow v_{jq} - \alpha \cdot [\frac{\partial J}{\partial v_{jq}}]$$

 

효율을 높이기 위하여 사용자 $i$ 및 아이템 $j$에 대하여 $k$의 잠재벡터에 대해 벡터화된 형태로 수식을 다시 작성하면 다음과 같습니다.

 

$$\overline{u_{i}} \Leftarrow \overline{u_{i}} + \alpha{}(e_{ij}\overline{v_{j}}-\lambda \overline{u_{i}})$$

$$\overline{v_{j}} \Leftarrow \overline{v_{j}} + \alpha{}(e_{ij}\overline{u_{i}}-\lambda \overline{v_{j}})$$

 

사용자 기반 협업 필터링에서 볼 수 있듯이 사용자의 평가 경향을 고려할 수 있습니다.

사용자의 평가 경향을 고려하여 계산하는 것이 더 정확합니다.

 

$$\hat{r_{ij}} = b + o_{i} + p_{j} + \sum_{s=1}^{k} u_{is} \cdot v_{js}$$

 

• $o_{i}$ : 사용자의 bias
• $p_{j}$ : 아이템의 bias
• $b$ : 전체 평균(고정된 값)
• $\sum$(시그마 부분) : 경사하강법으로 계산한 값

 

사용자, 아이템 bias는 다음과 업데이트하여 구할 수 있습니다.

 

$$o_{i} \Leftarrow o_{i} + \alpha \times (e_{ij} - \beta{} o_{i})$$

$$p_{j} \Leftarrow p_{j} + \alpha \times (e_{ij} - \beta{} p_{j})$$

 

$e_{ij}$는 다음과 같이 구해집니다

 

$$e_{ij} = r_{ij} - \hat{r_{ij}} = r_{ij} - (o_{i} + p_{j} + \sum_{s=1}^{k}u_{is} \cdot v_{js})$$

 

위에서 구한 $\hat{r_ij}$는 최종 예측값이 됩니다. 사용자가 아직 평가하지 않은 아이템에 대해서만 예측값을 바탕으로 정렬하여 아이템을 추천하면 추천알고리즘이 완성이됩니다.

 

코드 관련한 부분은 다음 포스팅에서 이어가겠습니다.