[Paper] Neural Factorization Machines for Sparse Predictive Analytics

Neural Factorization Machines for Sparse Predictive Analytics

Abstract

• web applications의 predictive tasks는 categorical variables을 modeling하는게 필요하다.
• categorical data
  • user IDs
  • demographics
  • genders
  • occupations

• standard machine learning에서는 binary features의 set으로 변환을 했다 (one-hot encoding). 결과적으로 feature vector는 highly sparse한 결과물이 생긴다. 이러한 sparse data를 효과적으로 학습하기 위해서는 features 사이에 interactions를 설명하는게 중요하다.

• Factorization Machines(FMs)는 second-order feature interations을 효율적으로 사용하는 유명한 솔루션이다. 그러나 FM은 feature interactions을 linear way로만 학습을 할 수 있고, real-world data의 non-linear와 complex inherent structure를 capturing하기 충분하지 못하다.

• deep neural networks는 최근 non-linear feature interactions를 학습하는데 적합하다.
  • Wide & Deep (google)
  • DeepCross (Microsoft)

• deep structure는 그동안 train하는게 어렵다.

• Neural Factorization Machine (NFM)을 제안 sparse settings에서.

• NFM은 seamlessly combine
  • linearity of FM in modeling second-order feature ineteractions
  • non-linearity of neural network in modeling higher-order feature interactions
• 기존 알고리즘과 비교했을때 shallower structure, better performance, much easier to train and tune in practice

Introduction

• Predictive analytis는 most important techniques information retrieval(IR), data mining(DM), ranking from recommendation systems, targeted advertising to search ranking, visual anlaysis, and event detection
• predictive는 estimating a function으로서 formulated하는 task를 말한다. 예를 들면 real value는 regression, classification은 categorical target. continuous predictor variables는 images, audio

• web applications에서는 대부분 discrete and categorical 데이터

  • online advertising
  • predict how likely (target) a user (first predictor variable) of a particular occupation (second predictor variable) will click on an ad (third predictor variable)

  • predictive models을 build 하기 위해서는 공통적으로 categorical variable을 a set of binary features으로 변경을 해야 한다.(a.k.a feature vector) - one hot encoding

  • 그 이후에 standard machine learning에 적용을 한다.

• possible value of categorical predictor variables에 따라 generated feature vector는 sparse하지만, 매우 높은 dimension을 가질 수 있다.
• sparse data로 효율적으로 ML models을 build 하기 위해서는 features 사이의 interactions을 설명하는게 가장 중요하다.
• crafting combinatorical features
  • cross features: constructing new features by combining multiple predictor variables
  • occupation = {banker, docker}, gender = {M, F} ---> occupationgender = {bankerM, bankerF, dockerM, docker_F}

• crafting combinatorical features는 high cost로 heavy engineering efforts, useful domain knowledge to design effective features가 요구 된다. 이 말은 즉 solutions은 새로운 문제 또는 도메인에서 generalize하는게 어렵다

• argumenting(늘리다) feature vectors 대신에 다른 솔루션으로 ML model을 디자인 하기 위한것으로 raw데이터 에서 feature interfactions을 자동으로 배운다. factorization machines (FMs)는 embededs features를 latent space와 embedding vectors의 inner product를 통해서 features 사이의 interactions을 모델링 한다.

• FM의 성능은 linearity에서 한계가 있다. (modeling of pairwise feature interactions only)

• real-world data는 complex, non-linear underlying structure를 갖고 있다. 결과적으로 FM은 충분히 real-word의 데이터를 표현하기에는 부족함이 있을 것이다. higher-order FMs가 제안되긴 했지만, 그것은 여전히 linear models에 속할 것이고, estimate하는데 어려움이 있을 것이다. higher-order FMs은 FM보다 더 좋은 성능을 보여주고 있다고 주장을 하지만, linear way의 higher-order interactions을 lineary way로 modeling했기 때문이라고 주장하고 있다.

• sparse data prediction인 Neural Factorization Machiens (NFMs)을 제안한다.

  • modeling higher-order and non-linear feature ineteractions
• Bilinear Interaction (Bi-Interaction) pooling 의 새로운 operation을 devising했다.
• FM을 neural network framework에서 첫번째로 위치 시켰다.
• Bi-Interaction layer위에 non-linear lyaers를 stacking을 shallow linear FM을 deepen 할 수 있었다.
• higher-order and non-linear feature interactions은 FM의 표현을 증가시킬 수 있었다.

• traditional deep learning methods 방식인 low level에서 concatenate, average embedding vectors와 반대로 이 논문에서는 Bi-Interaction pooling informative feature interactions을 encodes 했다. Bi-Interaction은 따라오는 deep layers에서 meaningful information을 배우기 수월하게 해준다.

• Contributions

  • Bi-Interaction pooling operation
  • FM아래 neural network framework를 deep하게 해서 higher-order, non-linear interactions을 학습시킨것
  • extensive experiments

Modeling Feature Interactions

• large space of combinatorical features의 이유로 feature enginerring을 하거나, feature selection techniques(boosted decision tree to select imprortant feature interactions)을 사용했다.
  • 위 솔루션은 tarining data에서 갖고 있지 않은 combinatorical features을 generalize 할 수 없다.
  • 데이터가 많으면 문제 해결이 아닌가?
• 최근 embedding-based methods가 popular한데, raw data로 부터 feature interactions을 학습한다.
• high-dimensional sparse features를 low-demensional latent space로 embedding을 하면 model은 unseen feature combinations을 generalize를 할 수 있다.
• domain과 상관없이 factorization machine-based linear models, neural network based non-linear models에 적용이 가능하다.

Factorization Machines

• factorization machines은 collaborative recommendation을 위해서 제안된 방법
• FM은 모든 feature의 interactions에 대해서 학습을 한다.
• matrix factorization (MF)와 반대로 FM은 오직 두개의 entities의 관계를 모델링
• FM은 linear/logistic regression (LR)과 함께 second-order factorized interactions between features.
• FM은 sparse data prediction을 위한 effective embedding methods

Expressiveness Limitation of FM

• FM의 성능은 좋지만, FM은 linear models이다. 다른말로 target은 linear 모델로 설명이 가능하다.
• FM을 pre-training해서 사용하면 성능이 더 좋음

Deep Neural Networks

• speech recognition, computer vision, natural language processing에 deep learning이 사용이 되고 있는데, IR과 DM에서는 많이 사용을 안하고 있는데, 그 이유는 대부분의 데이터가 sparse하기 때문이다.
• DNNs이 dense data로 부터 patterns을 학습하는데 강력한 능력을 갖고 있지만, sparse data에서는 less scrutiny(정밀한 조사)이고, sparse settings에서 feature interactions을 효율적으로 learning하기 위해 어떻게 employ해야하는지 모른다.
• 최근들어서 DNNs을 sparse predictive analytics에서 사용하기 시작했다.
  • neural collaborative filtering framework는 users와 items의 관계를 interactions을 학습한다. 이후에 model attribute interactions을 위해서 CF가 등장. 그러나 이 방법들은 두개의 entities의 관계만을 학습하고, general settings of supervised learnings을 직접적으로 지원하지 않는다.
  • FM-supported Neural Network(FNN), FM으로 feature embeddings을 사용해서 DNNs을 초기화
  • Wide & Deep, Multi-layer perceptron, concatentation of feature embeddings vectors to learn feature interactions
  • DeepCross
  • Wide & Deep 과 유사하고, MLP를 residual network로 변경

Optimization Difficulties of DNN

• neural network-based approaches의 공통된 structure
  • stacking multiple layers above the concatenation of embedding vectors to learn feature interactions
• implicit way의 combinatorical features of arbitary orders 을 배울수 있는 multiple layers
• 단순하게 concatenating feature embedding vectors는 too little information about feature ineteractions in the low level
  • item, user를 단순하게 concatenating을 하면 embedding vectors는 collaboriative filtering에서 very poor results를 가져다 준다.
• 위 문제를 해결하기 위해서, deep layers을 사용해 meaningful interaction function을 학습하는 방법이 있다. multiple non-linear layers는 feature inteactions을 잘 학습할 수 있다.

• deep architecture는 vanishing/exploding gradients, overfitting, degradation, among otehrs의 notorious(유명한) problems으로 optimize하는게 어렵다.

• DNNs의 optimzation의 어려움을 설명하기 위해서, training, test error를 each epoch에 plot을 했다.

• 실제 실험에 사용한 parameters와 architectures를 사용했다.
  • Wide&Deep 3 layers, DeepCross 10-layer residual network
• Wide&Deep에서 training error는 상대적으로 높았다. 이 문제를 degradation problem 때문
  • pre-training 해서 degradation problem을 해결
• DeepCross에서는 낮은 training error를 보여주었지만, high test error를 보여줬다. overfitting
  • pre-training을 해도, overfitting 을 해결할 수 없었음
• FNN으로 pre-train을 하고, DNNs을 initialize했다. (11%의 성능향상)
• concatenating feature embedding vectors, Bi-Interaction operation을 적용
  • informative representation이 더 높음
  • higher-order interactions을 학습하기 위해 subsequent non-linear layers를 도와준다.

Neural Factoriaztion Machines

• NFM은 sparse data modeling을 하기 위해서 FMs와 neural networks를 합쳤다
• 거기에 플러스로 dropout, batch normalization을 사용

The NFM Model

• factorization machines과 유사하게 NFM은 general machine learner
• sparse Vector가 input으로 들어올때, xi=0은 i-th feature의 값은 존재하지 않는다를 의미

• f(x)는 NFM의 core component로서 feature interactions을 modlieng하기 위한 것. (multi-layered feed forward neural network)

• Embedding Layer

  • 임베딩 레이어. 임베디드 레이어는 각 기능을 밀집된 벡터 표현으로 투사하는 완전히 연결된 레이어입니다. 공식적으로, vi ∈ Rk를 i 번째 피쳐에 대한 임베딩 벡터 라하자. 우리는 임베딩 벡터 Vx = {x1v1, ..., xnvn}의 집합을 얻어서 입력 특징 벡터 x를 표현한다. x의 드문 드문 한 표현 때문에 비 - 제로 피처, 즉 Vx = {xi vi}에 대해 임베딩 벡터를 포함하기 만하면됩니다. 여기서 xi는 0입니다. 단순히 입력 특성 값으로 매립 벡터를 재조정했습니다 실제 가치있는 기능을 설명하기 위해 임베딩 테이블 조회
  • embedding layer는 fully connected layer로 각 feature를 dense vector representation으로 project
  • vi는 i-th feature에 embedding vector
  • embedding 이후에 input feature vector x를 나타내기 위해 embedding vectors의 set을 얻게 된다. Vx = {x1v1, ... ,xnvn}
  • x의 sparse representation 때문에, non-zero features를 위한 embedding vectors를 포함해야 한다.
• Bi-Interaction Layer
  • embedding set Vx를 Bi-Interaction layer에 feed
  • pooling operation (set of embedding vectors을 one vector로 converts)
  • embedding space에서 features사이에 second-order interactions를 encodes -> k-dimension vector로 Bi-interaction pooling
  • Bi-Interaction pooling은 extra model parameter가 필요하지 않고, linear time에 효율적으로 계산이 가능하다.
  • 이 property는 average/max pooling, concatenation과 같다.
  • pairwise feature interactions modeling을 하는데 추가적인 코스트가 필요 없다.
• Hidden Layers
  • 위에서 Bi-Interaction pooling layer는 stack of fully connected layer로, features 사이에 higher order interactions을 학습할 수 있다.

• Prediction Layer

  • last hidden layer Zl은 final prediction score로 변환되는 ouput vector

• NFM Generalize FM

  • FM은 shallow, linear model, hidden layer가 없는 NFM의 special case에서 볼 수 있다.
  • L에 zero를 세팅하고 Bi-Interaction pooling to prediction score (L은 hidden layer의 개수)
  • neural network framework의 아래에서 FM의 표현력을 확인할 수 있다.
  • FM에서 learning, generalization ability를 향상시키기 위해서 다양한 neural network techniques를 사용했다.
  • dropout을 써서 overfitting을 prevent
  • Bi-Interaction layer는 regularize FM을 하기 위한 방법으로 사용, conventional L2 regularization보다 더 효과적인 것을 찾아 냈음.

• Relation to Wide&Deep and DeepCross

  • NFM은 여러 유사한 deep learning 솔루션과 유사하게 multi-layered neural architecture를 갖고 있다.
  • key difference는 Bi-Interaction pooling component는 NFM에서 만 사용하고 있다.
  • Bi-Interaction pooling을 concatenation과 변경하고 MLP(residual units)에 적용하면 Wide&Deep (DeepCross)
  • concatentation operation의 분명한 한계는 features 사이의 어떤 interactions은 해결을 할 수 없다. 그 처럼 이 deep learning approaches는 deep layers에서 meaningful feature ineteractions을 배워야 하는데, 실제 train하는게 매우 어렵다.
  • low level에서 Bi-Interaction pooling captures second-order feature ineteractions은 concatenation operation보다 더 informative하다.
  • NFM의 subsequent hidden-layers가 수월하게 useful higher-order feature ineteractions을 더 쉽게 가능

• Time Complexity Analysis

  • Bi-interaction pooling은 O(kNx)time에 효율적으로 계산이 가능하다. (=FM)
  • hidden layers에서 추가적인 비용이 발생한다.
  • hidden layer l은 O(dl-1 dl) > 다 필요없고 그냥 좋다. Wide&Deep, DeepCross와 같다.

Learning

• NFM은 다양한 prediction tasks에 적용이 가능하다. (regression, classification, ranking)
  • regression - squared loss object function을 사용
  • classification - hinge loss, logloss를 사용
  • ranking task - pairwise personalized ranking loss, contrastive max-margin loss
• 본 논문에서는 regression에 초점을 맞췄지만, ranking/classifiation도 같은 방법으로 진행하면 된다.

• Stochastic gradient descent (SGD)은 neural network models을 최적화 하기 위한 universal solver

• Dropout

  • dropout는 estimating할때 사용하는 전체 네트워크에서는 disable 되어야만 한다.
• Batch Normalization
  • multilayered neural network의 어려움중 하나는 fact of covariance shift의 원인
  • 각 layers의 inputs의 distribution이 training하는 중에 이전 layers의 변화의 파라미터로서 변화된다.
  • 그 결과 later layer은 이 변화(noisy)들에 대해서 자신들의 parameters의 업데이트할때 adapt할 필요가 필요하다.
  • 반대로 training 이 slow down
  • 위 문제를 해결하가기 위해 batch normalization (BN)이 등장!,
  • layer inputs을 normalizae한다 zero-mean unit-variance Gaussian distribution 각 mini-batch training에서
  • faster covergence, better performance의 결과를 준다.

Experiments

• Bi-Interaction pooling이 효율적으로 second order feature ineteractions을 찾을 수 있는지?
• 어떻게 dropout과 batchnormalization으로 Bi-Interaction pooling에 적용하는지
• FM보다 features사이에 higher order interactions을 찾을 수 있는지?
• Wide&Deep, DeepCross와 비교했을때 더 좋은지?

Experimental Settings

datasets

• frappe
• movielens
• Dataset, Instance #, Feature #, User #, Item #
• 70% training, 20% validation, 10% testA

Evaluation Protocols

• RMSE를 evaluate performance하는데 사용하고, explicit ratings와 함께 recommendations, click-through rate prediction 과같은 regression task에서 많이 사용된다.

Baseline

• sparse data prediction에 design된 embedding-based models과 비교
• LibFM
• HOFM
• Wide&Deep
• DeepCross

Parameter Settings

• learning rate 모든 method에 대해서 [0.005, 0.01, 0.02, 0.05]
• regularization (prevent overfitting)
  • LibFM, HOFM에는 overfitting을 피하기 위해서 regularization
  • Wide&Deep, DeepCross, NFM에서는 drop out [0, 0.1, 0.2, ... ,0.9]
  • DeepCross에서는 regluarize가 잘 되지 않았음 (residual units)
• batch size
  • batch size가 클수록 training time이 줄어들고 convergence rate가 줄어든다.
• embedding size는 64로

Study of Bi-Interaction Pooling (RQ1)

• Bi-Interaction pooling operation의 성능을 비교하기 위해서 hidden layer가 없이 prediction socre를 계산! (NFM-0)
• NFM-0은 다른 모델의 expressiveness에 영향을 받지 않아 FM과 동일하다고 생각하면 된다.
• drop out을 L2 regularization, batch normalization impact를 비교!

Dropout Improves Generalization

• LR, reg, drouput을 각각 비교했을때, dropout을 한 결과가 더 좋았음.
• L2 reg보다 dropout의 generalization이 좋은 이유
  • L2 regularization은 values of parameters를 only suppresses 하기 때문에, 반면 dropout은 ensembling multiple sub-models