[Day37] Context-aware Recommendation 8-2 : FM & FFM

Factorization Machines

SVM과 MF의 장점을 결합

 

커널 공간을 사용한 non-linear dataset에 대해서 SVM이 ML 모델중에 가장 사용되는 모델이었다. 그럼에도 CF환경(유저와 아이템에 대한 평점예측)에서는 MF계열의 모델이 더 좋은 성능을 내왔다. 하지만 MF는 또 그런 CF환경에서만 적용이 가능했다. CF환경은 sparse해서 SVM이 좋은 성능을 내지 못했다. 

 

$$\hat{y}(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left<v_i, v_j \right> x_ix_j, \quad w_0\in\mathbb{R}, w_i\in\mathbb{R}, v_i\in\mathbb{R}^k$$

 

앞의 term은 logistic regression과 같고 뒤에 factorization term이 추가된 형태이다. 또한 polynomial model과도 비교해 보았을 때 polynomial model은 각 feature의 상호작용을 하나의 파라미터로 표현했다면, FM은 각 feature에 대해 k차원의 factorization vector로 표현해서 좀 더 일반화 시켰다.

• $w_0$
  global bias
• $x_i$
  입력변수. $x_1 ~ x_n$으로 총 n개
• $w_i$
  1차 파라미터
• $v_i, v_j$
  학습하는 파라미터
  각각이 스칼라값이 아니라 k차원의 벡터
   $x_i$와 $x_j$가 상호작용 할 때 $x_i$에 해당되는 $v_i$가, $x_j$에 해당되는 $v_j$가 각각 곱해져서 
  $\left<v_i, v_j \right> := \sum_{f=1}^{k}v_{i,f}v_{j,f}$와 같이 두 벡터의 스칼라곱(dot product)를 통해서 두 feature간의 상호작용을 모델링한다.
• $\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left<v_i, v_j \right> x_ix_j$
  factorization term

유저의 영화에 대한 평점 데이터는 high sparsity한 데이터이다.

{(유저1, 영화2, rating),(유저1, 영화3, rating) ...}이렇게 있던 평점 데이터를 general predictor가 소화할 수 있는 x,y로 바꾸어보자

 

유저 1 을 유저 전체 수 U=3일 때, one-hot encoding으로  [1,0,0] 

영화 2 가 영화 전체 수 M = 4일 때, one-hot encoding으로 [0,1,0,0]

평점은 5.0으로 표현할 수 있다면

(유저1, 영화2, rating)=(1, 0, 0, 0, 1, 0, 0, 5.0)

로 바꿀 수 있다. 그래서 입력값의 차원이 전체 유저와 아이템수만큼 증가하게 된다.

 

Factorization Machines

위 데이터에서  유저 A의 영화 ST에 대한 평점을 예측하기 위해서는 A에 대한 factorization parameter $v_A$와  ST에 대한 factorization parameter $v_{ST}$가 학습되어 그 상호작용이 반영되기 때문에 구할 수 있다.

 

$v_ST$는 유저B,C가 동시에 SW라는 영화도 보았기 때문에 이에 기반해서 학습 될 것이다. 그래서 직접적인 interaction data는 없지만 다른 데이터를 통해 각각의 factorization parameter가 잘 학습될 것이고, 최종적으로 유저 A의 영화 ST에 대한 평점을 구할 수 있게 된다.

 

또다른 장점은 뒤에 다양한 context정보를 붙혀서 더 많은 interaction을 만들 수 있게 된다.

 

	FM	SVM	Matrix Factorization
sparse data	예측 성능이 높다	예측 성능이 낮다
복잡도	선형 복잡도(O(kn))이므로 학습량이 많아도 빠르게 학습된다.	학습데이터가 많아질수록 FM보다 느려진다.
data	CF형태가 아닌 general predictor에도 활용 가능		CF환경 데이터만 소화 가능
meta data	추가적인 context data 사용가능		추가적인 context data 사용불가

Field-aware Factorization Machines

FM을 변형시켜서 더 높은 성능을 보이게 했다.

 

PITF라는 모델에서 아이디어를 얻어서 발전시켰는데, PIFT또한 MF을 발전시킨 모델이다. PITF는 MF를 3차원으로 확장시킨다. 예시로 (user, item, tag)라면 user와 item이외에 tag의 임베딩까지 총 3개의 field의 embedding을 학습한다. 총 3개의 interaction (user,item), (user,tag) (item,tag) 각각의 interaction을 서로 다른 latent factor로 정의해서 구했다. 하나의 임베딩만으로는 다른 field와의 interaction을 표현하기는 부족했기 때문이다.

 

이 아이디어를 일반화해서 여러 개의 field에 대해 latent vector를 정의했다. 그래서 FFM에서는 사용자가 정의하는 만큼 field를 늘려서 embedding에 interaction 시킬 수 있다.

 

FM은 하나의 변수에 대해서 k개로 factorize했지만, FFM는 입력 변수를 field로 나누어 field별로 서로 다른 latent factor를 가지도록 factorize한다. 그래서 f개의 필드에 대해 각각 k개로 factorize한다.

 

field는 사용자가 정의하는 것이며 어떤 변수를 같은 필드로 묶을지 정의한다. 유저에 대해 성별과 디바이스라는 context가 있다면 두 개 이상의 다른 feature공간으로 표현하게 되고, 두 개 이상의 변수가 하나의 field가 될 수 있다. 

 

예를 들어, 디바이스가 0-삼성, 1-애플, 2-샤오미 이렇게 3가지 종류가 있다면 디바이스라는 필드가 있고 3개의 변수로 표현된다. 그러니까 3개의 변수가 하나의 필드에 포함되는 것이다.

 

CTR예측에 사용되는 feature는 훨씬 많은데, 보통 feature의 갯수만큼 필드를 정의한다.

---

$$\hat{y}(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left<v_{i, f_j}, v_{j, f_i} \right> x_ix_j, \quad w_0\in\mathbb{R}, w_i\in\mathbb{R}, v_{i,f}\in\mathbb{R}^k$$

 

앞의 term은 logistic regression 과 같고 factorization term이 FM에 비해 달라졌다. FM은 두 개의 변수가 interaction할 때 각각에 해당하는 k차원의 벡터로된 파라미터가 내적으로 표현했었다. 

 

FFM은 하나의 변수가 총 f개의 field를 갖고, 각 field별로 factorization 파라미터가 정의된다.

• $v_{i,f_j}$
  $x_i$가 곱해지는 반대편인 $x_j$의 field에 해당하는 factorization 파라미터
  각 field별로 factorization 파라미터가 정해진다.
• $x_i$
  입력 변수
  하나의 변수는 f개의 field를 갖는다

 

Publisher(P)	Advertiser(A)	Gender(G)	Clicked
ESPN	Nike	Male	Yes

FM

• field가 존재하지 않기 때문에 하나의 변수(ESPN, NIike, Male)에 대해서 하나의 factorization 파라미터가 존재한다.
• $\hat{y} = w_0 +w_{ESPN} + w_{Nike} + w_{Male} + v_{ESPN}\dot v_{Nike} + v_{ESPN}\dot v_{Male} + v_{Nike}\dot v_{Male}$
• 각각의 변수에 해당하는 factorization parameter를 내적한다.

FFM

 

• $\hat{y} = w_0 +w_{ESPN} + w_{Nike} + w_{Male} + v_{ESPN,A}\dot v_{Nike,P} + v_{ESPN,G}\dot v_{Male,P} + v_{Nike,G}\dot v_{Male,A}$
• Publisher feature를 P라는 필드로 정의하듯이 각각의 feature를 필드로 사용자가 정의했다.
• $v_{ESPN, A}$ : ESPN변수면서 Advertiser field와 곱해진다는 의미
• interaction이 일어나는 반대편 field를 고려해서 factorization을 수행한다.

 

Field 구성

 

 

FM은 필드가 필요없지만, FFM은 각각의 변수가 속한 feature group을 field로 정의한다. FFM은 모든 변수가 어떤 field에 속해야한다. 하지만 numerical feature은 필드를 할당하기 부족하다. one-hot encoding으로 표현되는 것이 아니라 하나의 실수값이기 때문이다. 

 

그래서 아래의 두 가지 방법을 사용한다.

• dummy field
  하나의 변수에 하나의 field만 할당한다. 그리고 다른 변수는 그 field를 사용하지 않는다. 그래서 field가 큰 의미를 갖지 않게 된다.
  기온이 34.2도 라면 T : T-34.2 : 34.2
• discretize
  numerical feature를 n개의 구간으로 나누고 n 차원의 one-hot encoding으로 표현된다. 그래서 n차원의 one-hot encoding은 총 n개의 입력변수가 된다.
  기온이 34.2도이고 10도씩 구간을 나누었다면 T:10:2

두 방법은 정답이 있지 않고 피쳐의 특징을 고려해서 수행하면 된다.

 

FM/FFM 성능 비교

LM : logistic regression

 

FM과 FFM이 LM과 Poly보다는 성능이 좋다. 하지만 field별로 factorization parameter를 나누는 것이 오히려 좋지 않는 경우는 FM이 성능이 더 좋은 경우도 있다.