ResSys - Factorization Machines (2)

RecSys - Factorization Machines (1)

---

Comparison to SVM

Factorization Machines, degree=2

SVM의 결과 $\hat{y} (x)$는 kernel $K$와 Equation 1으로 연관된, feature 공간 $R^n$ 에서 고차원 공간 $F$로 향하는 매핑함수 $\phi$와 모델 파라미터 $w$와의 내적 $<\phi (x), w>$로 표현할 수 있습니다. 따라서 $K$를 어떻게 설정하느냐에 따라 입력 $x\in R^n$을 어떤 공간으로 매핑해서 hyperplane을 구할지 정해지게 되는데요,

Equation 1

Linear kernel

먼저 가장 간단한 선형 커널 $K_l (x, z) := 1 + <x,z>$ 를 생각해볼 수 있습니다. 이는 $\phi (x) := (1, x_1, ..., x_n)$ 와 같고 $\hat{y} (x)=<\phi (x), w>$를 이용하여 Equation 2와 같이 표현할 수 있습니다. 이는 차원 2의 factorization machines가 feature 상호관계없이 차원 1로 축소된 것과 같습니다.

Equation 2

따라서 유저 $u$, 아이템 $i$ feature에 대해서 $j=u, i$ 일때만 $x_j=1$ 이므로 Equation 3과 같이 표현되고 해당되는 유저와 아이템을 기반으로 예측합니다. 모델이 매우 간단하여 sparse 상황에서도 파라미터를 잘 추정할 수 있으나 feature 상호관계에 관련된 항이 없어 Figure 1과 같이 성능이 매우 낮습니다.

Equation 3

Figure 1

Polynomial kernel

Polynomial kernel은 $K(x,z) := (<x,z>+1)^d$와 같이 표현되고 $d=2$라면 $\phi (x)$는 Equation 4와 같습니다.

Equation 4

따라서 이를 $\hat{y} (x)=<\phi (x), w>$에 대입해 풀어쓰면 Equation 5와 같고 $w_0 \in R, w\in R^n, W^{(2)}\in R^{n\times n}$ 입니다. Equation 5를 보면 feature 간의 2차 상호관계까지 모델링된 것을 볼 수 있고 FM과 다른 점은 Equation 4의 모든 상호관계 파라미터 $w_{i,j}$는 서로 독립적이라는 것입니다. 지난 포스트에서도 살펴봤듯이 FM은 factorization 기법을 사용하여 각 feature의 잠재변수를 학습하여 $<v_i, v_j>, <v_i, v_l>$이 공유된 $v_i$ 벡터를 기반으로 독립적이지 않습니다.

Equation 5

이 경우에도 유저 $u$, 아이템 $i$에 대해서만 non-zero 값을 가진다고 가정합니다. 즉, $m(x)$를 $x$의 non-zero 요소 개수라 하면 $m(x)=2$ 가 되는거죠. 따라서 Equation 6과 같이 쓸 수 있고 $w_u, w_{u,u}^{(2)}$는 모두 유저를 포함하므로 하나를 제거합니다. ($w_i$ 도 마찬가지) 따라서 Equation 6은 Equation 3의 선형 수식에서 상호관계 $w_{u,i}^{(2)}$가 추가된 것과 같습니다.

Equation 5

이같은 경우는 훈련 데이터셋에 $(u,i)$에 대한 관측치가 존재해야 $w_{u,i}^{(2)}$ 학습될 수 있고 존재하지 않는 feature 조합에 대해서는 상호관계가 없는 0으로 학습됩니다. 따라서 훈련 데이터셋에 존재하지 않는 feature 조합으로 이루어진 데이터에 대해서는 상호관계가 아닌 Equation 3과 같이 유저와 아이템의 개별적인 feature 로만 예측되어 선형 kernel 과 다르지 않게 됩니다. 즉, $w_{u,i}^{(2)}를 잘 추정하기 위해서는 $x_i, x_j$가 모두 0이 아닌 데이터가 충분히 많아야 되고 이로 인해 매우 sparse한 데이터에 대해서는 SVM의 추정이 제대로 동작하지 않습니다. 또한, FM이 본래 수식 그대로 SGD 방법으로 쉽게 최적화할 수 있는데에 비해 SVM은 복잡한 dual form 으로 변환하여 풀어야 하고 최종적으로 구한 support vector 자체가 훈련 데이터에 의존하는 문제가 있습니다.

 

---

RecSys - Factorization Machines (3), Pytorch 구현