Collaborative Metric Learning

안녕하세요. 이번 시간엔 Collaborative Metric Learning 논문에 대해 리뷰하겠습니다.

참고자료는 다음과 같습니다.

 

Hsieh, Cheng-Kang, et al. "Collaborative metric learning." Proceedings of the 26th international conference on world wide web. 2017.

vision.cornell.edu/se3/wp-content/uploads/2017/03/WWW-fp0554-hsiehA.pdf

 

Intro to WARP Loss, automatic differentiation and PyTorch

medium.com/@gabrieltseng/intro-to-warp-loss-automatic-differentiation-and-pytorch-b6aa5083187a

 

Intro to WARP Loss, automatic differentiation and PyTorch

 

2017년에 발간된 이 논문은 20201년 4월 14일 기준, SOTA의 추천시스템에서 MovieLens 20M dataset 기준, 9위의 RANK를 가지고 있습니다. 저자가 tensorflow로 이 모델을 만들어서 아래 사이트에서 구현할 수도 있습니다.

 

Collaborative Metric Learning 코드

github.com/changun/CollMetric

changun/CollMetric

 

이 방법을 설명하기 앞서 아래와 같은 사전지식을 먼저 설명하겠습니다.(제가 필요한 것을 기준으로 적은 거라 논문에서 언급한 내용이 없을 수 있습니다.

Metric learning

$X = {x_1, ..., x_n}$에서 각 $x_i \in \mathcal{R}^{m} $일 때,  아래와 같은 dataset을 정의합니다.

- n : 데이터 개수 (row)

- m : feature 개수

- $ S = {(x_i, x_j)} $ : $x_i$와 $x_j$는 서로 유사합니다.

- $ D = {(x_i, x_j)} $ : $x_i$와 $x_j$는 서로 유사하지 않습니다.

 

여기서 저자는 보통 Mahalanobis distance metric를 학습시킬 때 아래와 같은 식을 사용한다고 합니다.

$d_A(x_i, x_j) = \sqrt{(x_i - x_j)^{T} A (x_i, - x_j)}$

- $A$ : m x m 크기의 positive semi-definite matrix입니다.

    - positive semi-definite matrix (양의 준정부호 행렬) : matrix $M$의 모든 고윳값이 음수가 아닌 경우 (즉, 0이 아닌 모든 벡터 $x $에 대해 $x^{*}Mx\geq 0인 경우)$ matrix $M$을 positive semi-definite matrix라고 함

(출처 : [wikipedia(정부호 행렬)] (ko.wikipedia.org/wiki/%EC%A0%95%EB%B6%80%ED%98%B8_%ED%96%89%EB%A0%AC) )

 

이 식을 최적화 하기 위해 아래와 같은 방식을 활용합니다.

$min_A \sum_{(x_i, x_j) \in S } d_A ( x_i, x_j)^2 $

$s.t. \sum_{(x_i, x_j) \in D} d_A ( x_i, x_j)^2 \ge 1 \, and \, A \, \succeq 0$

즉, 식을 요약하면 Mahalanobis distance metric의 거리 값을 최소화 할 수 있는 matrix A를 찾는 것인데 조건으로 유사하지 않다고 표현한 데이터 간에는 거리값이 1이상으로, A는 양의 준정부호 행렬을 가정하고 있습니다.

LMNN

이 부분은 제가 전에 정리한 내용이 있어 아래 페이지를 참고하시기 바랍니다.

 

hwa-a-nui.tistory.com/34

LMNN(Large Margin Nearest Neighbors)

 

여기까지가 사전지식이었으며 다음은 모델에서 쓰이는 부분입니다.

모델 정의

Collaborative Metric Learning(CML)은 다음과 같은 목적을 가지고 만들었습니다.

- 유저의 점수가 아닌 상대적인 선호도를 예측

- implicit data를 사용하여 모델 형성

- 모델 학습 방향 : 유사한 user-item pair는 서로 인접하게, 상대적으로 다른 user-item pair는 서로 멀리 떨어지도록 하는 metric (matrix $M$)을 만듦

    - 결과 : 다음과 같은 경우 최근접 이웃으로 형성됨

        - 특정 user i가 좋아하는 item 집합

        - 특정 user i와 유사한 취향을 가진 user들이 좋아하는 item 집합

loss

loss 식은 다음과 같습니다.

 

$ \mathcal{L}_m(d) = \sum_{(i,j) \in S} \sum_{(i, k) \notin S} w_{ij} [ m +D(i,j)^{2} - d(i,k)^{2}]_{+}$

- (i,j) : user i가 선호하는 item j입니다. (j를 Positive item 또는 target이라고 정의합니다)

- (i,k) : user i가 선호하지 않는 item k입니다. (k를 imposter라고 정의합니다)

-  $d(i,j) = || \textbf{u}_i - textbf{v}_j || $ : 각 item j에 대한 user i의 선호도를 나타냅니다. 만약 선호한다면 해당 거리값은 작아지게 됩니다. (이는 같은 차원의 embedding vector이기 때문에 가능하다고 생각됩니다.)

    - $u_i \in \mathcal{R}^{r}$ : embedding 된 user vector입니다.

    - $v_j \in \mathcal{R}^{r}$ : embedding 된 item vector입니다.

- $[z]_{+} = max(0, z)$ : hinge loss로 z값이 0보다 작으면 0으로 반환하는 함수입니다.

- m : margin 값으로 $m > 0$입니다. (hyperparameter로 생각하시면 되겠습니다)

- $w_{ij}$ : ranking loss weight로 뒤에서 설명됩니다.

 

식을 설명하면 다음과 같습니다. user i와 Positive item j와의 거리 값과 Margin을 더한 값보다 user i와 Imposter k와의 거리보다 더 가깝다면 loss 값이 커지게 되고 아닌 경우 0으로 처리가 됩니다. 즉, loss를 통해 Positive item j와 Imposter k를 조정하게 되는 것입니다. 즉, Imposter가 존재할 때만 Positve item j를 당기고, Imposter k를 밀어내게 됩니다.

 

위의 사진을 보면 CMF 모델을 학습하면 User를 기준으로 Imposter item은 Margin 밖으로 나가고 Positive item은 Margin 안으로 들어오게 됩니다. 

Warp loss(Weighted Approximate-Rank Pairwise)

위에서 보았던 $w_{ij}$ 변수에 대한 설명입니다. metric d가 주어졌을 때 user i에 대한 item j의 rank weight는 다음과 같이 만듭니다.

$w_{ij} = log(rank_{d}(i,j) + 1) $ 

- $rank_{d}(i,j)$ : user i가 item j를 선호하는 순위 (1위면 1, 2위면 2, ...)

 

이는 Positve item j에 대해 penalty를 주는 것으로, 낮은 rank를 받을수록 값이 커지므로 loss값도 커지게 됩니다. 즉, user i에 대해 다른 item과 비교했을 때 j의 순위를 구하는 것입니다. 하지만 이 과정은 item 각각, user 각각에 대해 해야하므로 시간이 굉장히 오래 걸려 일부 데이터만 비교하는 방식을 사용하는데 이는 Positive item j와 negative sample과 비교하는 방식으로 구하는 것입니다. negative 개수는 하이퍼 파라미터로 저자는 20개를 사용했습니다.

* negative는 user i가 고르지 않았던 item을 의미합니다. 

 

그랬을 때 $rank_{d}(i,j)$는 대략적으로 $\frac{J \, x \, M}{N}$ 값을 가질 것이라고 합니다. 여기서 J는 item 개수, M은 Negative sample에서 Imposter 개수, N은 negative sample 개수입니다.

Integrating Item Features

사실 위의 Metric learning에서 본 식을 다르게 생각하면 input을 transformation 한 것으로 볼 수 있습니다. 이를 활용하여 raw input $x_j \in \mathcal{R}^{m}$을 joint user-item space로 transformation 시키는 함수 $f$를 학습시킵니다.

$\mathcal{L}_f (\theta, \textbf{v}_{*}) = \sum_{j} || \mathcal{f}( \textbf{x}_{j}, \theta) - \textbf{v}_{j}||^{2}$

- $x_{j}$ : raw item j의 vector 값입니다.

- $v_{j}$ : embedding한 item j입니다.

Regularization

크게 2가지 Regularization을 사용합니다.

 

첫 번째는 Normalize입니다. KNN의 경우 feature의 값이 큰 것이 있으면 해당 feature에 편향되어 클래스를 결정할 수 있기 때문에 이를 방지하기 위해 embedding 된 item, user vector에 대해 다음과 같은 제약을 합니다.

$ || \textbf{u}_{*}||^2 \le$ and $ || \textbf{v}_{*}||^2 \le$

 

두 번째는 covariance regularization입니다. 학습된 metric에서의 상관관계를 줄이기 위해 해당 방식을 사용합니다. covariance matrix 식은 다음과 같습니다.

$ C_{ij} = \frac{1}{N} \sum_{n}(y_{i}^{n} - \mu_{i}) ( y_{j}^{n} - \mu_{j} )$

- $C_{ij}$ : item 또는 user의 covariance matrix입니다.

- $ y_{i}^{n}$ : i번째 row, n번째 feature의 item 또는 user vector 입니다.

- $ \mu_{i} = \sum_{n} y_{i}^{n}$

 

loss 식은 다음과 같습니다.

$\mathcal{L}_c = \frac{1}{N}( ||C||_{\mathcal{f}} - ||diag(C)||_{2}^{2})$

- || z || : Frobenius norm입니다.

Training Procedure

위의 것들을 정리했을 때 최종 loss는 다음과 같습니다.

$min_{\theta, \textbf{u}_{*}, \textbf{v}_{*}} \, \mathcal{L}_{m} + \lambda_{f} \mathcal{L}_{f} + \lambda_{f} \mathcal{c}_{c} $

$ s.t. ||\textbf{u}_{*}||^{2} \le 1$ and $||\textbf{v}_{*}||^{2} \le 1$

- $\lambda_{f}, \lambda_{c}$ : hypterparameter입니다.

 

학습 과정은 다음과 같습니다.

- Set S로부터 positive sample N개를 뽑습니다.

- 위에서 뽑은 각 sample인 (user, item) pair에 대해 Negative Sample U를 뽑습니다.

- 각 pair에 대해 위의 hinge loss를 극대화 할 수 있는 negative item k개를 유지하고 mini-batch size N을 만듭니다.

- AdaGrad를 사용하여 gradient를 계싼하고 parameter를 업데이트 합니다.

- $y^{\prime} = \frac{y}{max(||y||,1)}$로 $\textbf{u}_{*}$와 $\textbf{u}_{*}$ 값을 조정함

- 수렴할 때까지 위의 절차 반복

 

여기까지가 Collaborative Metric Learning에 대한 설명이었습니다. 아마 설명이 잘 이해되지 않는 곳이 일부 있을텐데 이 부분은 코드 돌리고 정리하면서 고치도록 하겠습니다.

 

잘못된 부분이나 궁금한 부분있으면 말씀해주세요!