Collaborative Metric Learning

$Matrix = \begin{bmatrix} 0 & 2 \\ 2 & 0 \\ 2 & 2 \end{bmatrix}$ $LatentUser = \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ 1 & 1 \end{bmatrix}$ $LatentItem = \begin{bmatrix} 0 & 2 \\ 2 & 0 \end{bmatrix}$

$N \times M = (N \times K) \cdot (K \times M)$

$3 \times 2$ User-Item Matrix를 K = 2인 $3 \times 2$ User Latent Matrix와 $2 \times 2$ Item Latent Matrix로 분해한 뒤 둘을 다시 곱하면 원래의 행렬을 복원되는데 $U_3$의 경우 $v_1$,$v_2$ 를 모두 선호함에도 $v_1$, $v_2$ 간의 관계는 유사한 관계처럼 표현되지 않는다.

CML을 통해 학습하게 된다면 User-Item 관계 뿐 아니라 User-User, Item-Item 관계를 Metric을 통해 학습하여 $U_3$이 선호하는 $v_1$,$v_2$를 유사한 관계로 표현이 가능해진다.

Triangle Inequality

CML에서는 한 User가 Positive Item을 자기쪽으로 당기려고 학습을 진행할 때 두 Item이 User에 가까워질수록 Item들끼리의 거리도 가까워지게 된다. 이를 Triangle Inequality를 만족한다고 하는데 MF의 경우 User와 유사한 Item을 찾을 순 있지만 Item-Item 관계를 학습하는데에는 한계가 존재한다.

Training

Total Loss

$\underset{\theta,u_*,v_*} {min}\mathcal{L_m}+\lambda_f \mathcal{L_f} +\lambda_c \mathcal{L_c}$

다음과 같이 3개의 식을 minimize하도록 진행된다.

$\mathcal{L_m}$ : Embedding Loss

$\mathcal{L_f}$ : Feature Loss

$\mathcal{L_c}$ : Covariance Loss

Embedding Loss

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

User i

Positive Item j

Negative Item k

$[z]_+ = max(0,z)$

$\mathcal{L_m}$은 크게 두 개의 식으로 분리할 수 있다

1. $[m + d(i,j)^2 - d(i,k)^2]_+$

2. $w_{ij}$

1. $[m + d(i,j)^2 - d(i,k)^2]_+$

Metric Learning에서의 Loss

1. Contrastive Loss
2. Triplet Loss
3. Quadruplet Loss

Triplet Loss

Triplet Loss는 Anchor, Positive, Negative 3쌍을 필요로 한다. Anchor는 거리 기반이기 때문에 거리를 측정하기 위해 기준으로 삼은 Input, Positive는 Anchor와 같은 클래스의 Input, Negative는 Anchor와 다른 클래스의 Input이다. Anchor를 기준으로 Positive와의 거리와 Negative와의 거리를 측정한 뒤 Anchor와 Positive와의 거리를 가깝게, Negative와의 거리를 멀어지도록 학습하는 것이 Triplet Loss의 방식이다.

Collaborative Metric Learning에서는 이 Triplet Loss를 적용할 때 기준이 되는 Anchor를 User, Positive와 Negative를 각각 User가 선호하는 Item과 선호하지 않는 Item으로 설정했다.

Negative 위치에 따른 Loss

Anchor와 Positive가 존재할 때 Negative가 어디에 위치하느냐에 따라 3가지 상황이 존재한다.

1. Easy Triplets
2. Hard Triplets
3. Semi-Hard Triplets

Easy Triplets

$d(i,k)^2 > m + d(i,j)^2$ → $\mathcal{L_m} = 0$

Negative Item이 margin 바깥 영역에 위치하는 경우 충분히 멀리 떨어져 있다 판단이 되어 Loss에 반영하지 않으며, 이처럼 Negative가 Positive보다 Margin만큼 더 멀리 있도록 위치시키기 위해서 Hinge Loss를 사용한다.

Hard Triplets & Semi-Hard Triplets

$d(i,k)^2 < m + d(i,j)^2$

Hard Triplets은 Positive보다 안 쪽에 Negative가 위치하는 경우, Semi-Hard Triplets는 Positive보다는 바깥에 존재하지만 Margin 영역에 위치하는 경우를 말하는 것으로 둘 다 $\mathcal{L_m} > 0$ 이기 때문에 $\mathcal{L_m}$을 줄이는 방향으로 학습해야 한다.

Negative Sample Mining(=Negatives Selection=Triplet Mining)

학습을 할 때 User, Positive, Negative 3쌍씩 뽑고 계산을 하는데 Negative의 경우 효과적인 학습을 위해서 $\mathcal{L_m} = 0$ 인 Easy Triplets을 제외한 나머지 Negative를 샘플링하여 사용해야 한다.

위 논문에서는 Hardest Negative를 사용하면 Local Minimum에 빠진다고 하여 Semi-Hard Negative를 샘플링하지만 CML 논문에서는 이 둘을 따로 구분짓지 않고 하나로 사용하고 있다.

2. $w_{ij}$

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

이 가중치는 User i에 대해서 Positive Item j가 User i에 대해서 가장 가까이 있지 않을 때 패널티를 부과하여 User i에 가까워지도록 설정해 준 가중치다.

$rank_d(i,j) = 0$ 일 때 $w_{ij} = 0$ 임을 알 수 있으며, 순위가 낮아질수록 패널티는 더욱 커진다.

그러나 1번에서 3개의 쌍을 뽑고 거리를 기준으로 Loss를 계산한 것과는 달리, $w_{ij}$는 순위를 매겨야 하기 때문에 User와 Positive 각각 한 쌍, 그리고 여러 Negative samples를 필요로 하여 시간 비용이 많이 소모

1. 반복문으로 Hard Triplets & Semi-Hard Triplets에 있는 Negative를 찾는다.
2. 찾은 Negative samples의 거리를 계산한 뒤 해당 (User, Positive)에 대해 순위를 매기고 가중치를 계산한다.

각각의 쌍들마다 계속 반복문으로 찾고 곱해주는 과정을 피해 각 User, Positive에 대해서 하나의 Negative만을 찾고 가중치로 근사값을 곱해주기로 결정

→ 근사값으로 $\lfloor \frac{J}{N} \rfloor$을 사용하기로 함.

J : 전체 Item의 개수

N : 하나의 imposter를 찾을 때까지 반복한 횟수

각각의 Item들이 뽑힐 확률은 $\frac {1}{J}$로 독립이기 때문에, Geometric Distribution에 따르는 p = $\frac {N}{J}$이다.

따라서 평균에 근사시키면 $a = \frac{1}{p} = \frac {J}{N}$가 된다.

그마저도 N의 크기가 계속 커질 것을 우려

U : 10 or 20

M : U samples에서의 imposter의 개수

→ $\lfloor \frac{J \times M}{U} \rfloor$로 근사 (M : U sample에서 imposter의 개수)

batch size * num negative sample 행렬을 근사식을 통해 batch size 행렬로 만들어 빠르게 연산한다.

Feature Loss

$\mathcal{L_f(\theta,v_*)}= \sum_{j} \lVert f(x_j,\theta) - v_j \rVert^2$

$f(x)$ : MLP

$x_j$ : Item j의 feature (text description, tag, image pixel)

$v_j$ : Item j의 vector

$\mathcal {L_f}$는 Item feature를 입력으로 받은 MLP의 Embedding dim과 같은 사이즈의 output과 $\mathcal{L_m}$을 통해 학습되는 Embedding dim과 같은 사이즈의 Item vector $v_j$ 간의 거리를 minimize하도록 설계되었다.

$\mathcal{L_f}$를 통해 Item feature가 유사한 Item들끼리 서로 클러스터링되는 결과를 가지게 된다.

Covariance Loss

Matrix Factorization에서는 이미 정보가 주어진 User, Item에 대해서 과적합을 피하기 위해 User와 Item에 l2 norm을 적용한다. ($\underset{u_*,v_*} {min} \sum_{r_{ij} \in \mathcal {K}}(r_{ij} - u^T_i v_j)^2 + \lambda_u \lVert u_i \rVert^2 + \lambda_v \lVert v_i \rVert^2$)

그러나 Metric Learning에서는 distance 기반이기 때문에 비효율적이다.

$\mathcal{L_c} = \frac{1}{N} (\lVert C \rVert^2_f - \lVert diag(C) \rVert^2_2)$

$C = \begin{bmatrix} a_{1,1} & \cdots & a_{1,m} \\ \vdots & \ddots & \vdots \\ a_{m,1} & \cdots & a_{m,m} \end{bmatrix}$

$C_{ij} = \frac{1}{N} \sum_n(y_i^n-\mu_i)(y_j^n-\mu_j)$

$C_{ij}$는 batch size N일 때 embedding dim에 따른 공분산이다.

i : Embedding vector element index

n : batch index

$y^n_i$ : Embedding vector

$\lVert C \rVert^2_f = \lvert a_{11} \rvert^2 +\lvert a_{12} \rvert^2+ \cdots + \lvert a_{mm} \rvert^2$

$\lVert diag(C) \rVert^2_2 = \lvert a_{11} \rvert^2 + \lvert a_{22} \rvert^2 +\lvert a_{33} \rvert^2 + \cdots + \lvert a_{mm} \rvert^2$

대각 성분은 자기 자신의 variance이기 때문에 각 dim 간의 covariance를 minimize 하기 위해서 제외한다.

실험

Datasets:

CiteULike : tags of the papers

BookCX : Book subjects

Flickr : Photo

Medium : article tags

MovieLens : genre, plot keywords

EchoNest : X

Performance Metrics : Recall@50, Recall@100

Item feature가 없어도 성능이 좋게 나오고 feature를 넣었을 때 성능이 훨씬 좋아졌음을 알 수 있다.