An Input-aware Factorization Machine for Sparse Prediction

1 Introduction

Prediction now plays a crucial role in many personalized systems, such as online advertising [McMahan et al., 2013; Juan et al., 2016] and recommendation [Koren et al., 2009; Cheng et al., 2014]. Typically, the recommendation task is formulated as estimating a function that maps categorical predictor variables (a.k.a. features) to a target. For example, we need to predict the click probability (target) that a user (first predictor variables) of a particular occupation will click on an item (second predictor variables). The first and second predictor variables are usually combined in the form of an instance, e.g., {young, female, student, pink, skirt}.

To build predictive models with these categorical predictor variables, it is indispensable to accurately represent them in machine identifiable forms. A common solution is to convert them to a set of binary features (a.k.a. feature vector) via one-hot encoding [Cheng et al., 2016]. Depending on the number of possible values of categorical predictor variables, the generated feature vector can be very high dimensional and sparse. To build an effective model with such sparse data, factorization machines (FMs) were proposed [Rendle, 2010], which learn a one-dimensional weight and a k-dimensional embedding vector as the representation of each feature from sparse data. Owing to its efficient linear training time and high prediction accuracy, FMs have been successfully applied to various applications, from recommendation systems [Rendle et al., 2011] to natural language processing [Petroni et al., 2015]. Despite great promise, FMs produce a single representation for each feature and the same representation of a given feature is shared in different instances to compute its predictive power, which may lead to inferior performance. In this paper, we argue that the impact of each individual input should be given full consideration when creating the representation for each feature.

*Corresponding author

Many existing studies attempt to improve the prediction accuracy of FMs by focusing on feature interactions. For example, DeepFM [Guo et al., 2017] models high-order feature interactions through a neural network, while AFM [Xiao et al., 2017] enhances FMs by learning the importance of each feature interaction from data via a neural attention network. Nevertheless, these improvements are limited as the uniqueness of each instance is not exploited.

In our work, we propose to improve FMs from a new perspective that tries to refine the representation of features according to different instances. In real-world applications, a feature usually has dissimilar levels of predictive power in different situations. For example, the feature female is apparently crucial for click probability in an instance: {young, female, student, pink, skirt}. However, in another instance: {young, female, student, blue, notebook}, the feature female is relatively less crucial. As such, the same feature on different instances should be assigned different levels of predictive power to better reflect its specific contribution.

In this paper, we present a novel model for prediction tasks under sparsity named Input-aware Factorization Machine (IFM), which enhances FMs by explicitly considering the impact of each individual input on the representation of features. It refines the weight and embedding vector of each feature with regard to different instances and adds nonlinearity to the model simultaneously. Specifically, we adopt the idea of end to end memory network [Sukhbaatar et al., 2015]

to enable each feature to contribute dissimilarly in different instances. In this way, the representation of each feature is not only related to itself, but also to the instances containing it. In contrast to other deep learning based methods that mainly focus on feature interactions, our use of neural networks for more informative representations of features greatly enhances the expressiveness and interpretability of FMs. Comprehensive experiments show that our IFM features two major advantages: i). it produces better prediction results compared to existing techniques; ii). it provides deeper insights into the role that each feature plays in the prediction task.

2 Preliminaries

Factorization machines are proposed to learn feature interactions for sparse data, which combine the advantages of Support Vector Machines (SVMs) with factorization models. FMs enhance linear regression (LR) using the second-order factorized interactions between features. Given a real valued feature vector x ∈ Rn where n denotes the number of features and most of the elements xi in a vector x are zero, the FMmodel estimates the target by modelling the interactions via factorized interaction parameters:

where x is the feature vector of the instance and xi denotes the i-th dimension of the feature vector while ˆ y represents the value predicted by the FM model (e.g., the estimated probability of click). w0 is the global bias and wi models the weight of the i-th variable. vi is a k-dimensional embedding vector of the i-th variable and ⟨vi, vj⟩ is the dot product of two vectors of size k, which models the interaction between the i-th and j-th variables. Here, k is the dimension of embedding vectors, which controls the complexity of FMs. Note that the feature interactions can be reformulated [Rendle, 2010] as:

where vj,f denotes the f -th element in vj . The time complexity of Equation 1 is O(kn2 ), but with reformulating it drops to linear time complexity O(kn).

It is worth noticing that FMs produce a fixed representation for each feature: the same weight wi and embedding vector vi are shared across all different instances that involve the i-th feature. However, it is not unusual that a certain feature is not equally predictive and useful across different instances. Consequently, due to the lack of flexibility in feature representation, FMs may suffer from the insufficient ability for modelling complex data, which may adversely affect their performance in general.

3 Input-aware FactorizationMachine

In this section, we present the details of the proposed IFM model to show how to boost the performance of FMs via the input-aware strategy.

3.1 The IFMModel

Similar to factorization machines, given a sparse feature vector x ∈ Rn as input, where a feature value xi = 0 means that the i-th feature does not exist in the instance, IFM predicts the target as:

where the first and second terms model the global bias of data and weights of features respectively, and the third term captures the feature interaction. Note that, in our method, the second and third terms model each feature's effect on the label in a nonlinear way, as the weight wx,i and embedding vector vx,i of each feature not only correlate with the i-th feature but also are related to the input vector x. Figure 1 illustrates the network architecture of our proposed IFM model, where the extra components in addition to traditional FMs are marked by dark background.

Embedding Layer

As in FMs, a weight and an embedding vector are randomly initialized for each feature as its representation. Formally, let vi ∈ Rk be the embedding vector of the i-th feature, where k is the embedding size. Due to the sparsity of x, we only need to include the embedding vectors of non-zero features, i.e., Vx = {vi} where xi ̸= 0. Finally, we stack all vectors in Vx into a single k × h dimensional vector: Vx = [vT 1 , vT 2 ...., vT h ], where h denotes the number 1 of nonzero elements per instance.

Factor Estimating Network

The input-aware strategy is inspired by memory networks [Weston et al., 2014], which are a class of deep learning based models mainly used in question answering (QA) tasks. One of their key ideas is to allow different memory records to con-

1 In this paper, we assume that h is a fixed value for each dataset.

2

4

7

Figure 2: The neural network architecture of Factor Estimating Network

tribute differently to each question. Motivated by this inherent flexibility of memory networks, the input-aware strategy is proposed to extend the functionality of FMs by introducing an input-aware factor mx,i into the feature weight wi and embedding vector vi, which allows each feature to contribute dissimilarly in different inputs.

To estimate the input-aware factor mx,i, we first feed the stacked vector Vx into the Factor Estimating Network (FEN) to learn a unique vector Ux for the given input x. Figure 2 shows the architecture of FEN. The network begins with a stack of fully connected layers that are capable of learning unique information from x. Formally, the definition of the fully connected layers is as follows:

where Wl, bl, σl and al are the weight matrix, bias vector, activation function and the output of the l-th layer, respectively. Next, Ux, which is the output vector of the last hidden layer aL, is used to learn an input-aware factor mx,i for each feature in the input x:

where P denotes the weight matrix that transforms Ux to a hdimensional vector m′ x, and t denotes the number of neurons in the last hidden layer. Finally, the elements m′ x,d, d ∈ [1, h] in m′ x are normalized through a softmax function, so that the sum of all elements is equal to h, representing the input-aware factor mx,i of each non-zero feature in x.

Reweighting Layer

Once the outputs from FEN are obtained, they are used to refine the feature weight wi and embedding vector vi with regard to the current input. The inputs of this layer are the wi and vi of the given input x and the input-aware factor mx,i from the previous layer. Formally, the definition of the reweighting layer is as follows:

where wx,i, vx,i are the refined representations of features for the specific input x.

FM Prediction Layer

In this layer, the input-aware weight wx,i and embedding vector vx,i are fed into factorization machines to predict the target as Equation 3. It is worth mentioning that, similar to Equation 2, we can reformulate Equation 3 to reduce the runtime of this layer to linear time complexity O(kn):

In summary, in IFM, the model parameters are Θ = {w0, wi, vi,Wl, bl, P}. Compared to the FMmodel, the additional model parameters of IFM are {Wl, bl, P}, which are mainly used for capturing the input-aware factors.

3.2 Relationship with FMand AFM

It is easy to see that, in the IFMmodel, by fixing all mx,i to 1, wx,i and vx,i only depend on the i-th feature, and IFM reduces to the original FMmodel. On the other hand, if we neglect the second term of Equation 1, AFM [Xiao et al., 2017] can be seen as a similar case to IFM.

To show this, we compare the formulation of feature interaction in AFM with ours:

As can be seen from Equation 8, by replacing mx,imx,j with ai,j and fixing pT to a constant vector of [1, ..., 1], we can roughly cover the AFMmodel.

3.3 Learning

As IFM directly enhances FMs from the perspective of data modelling, it can also be applied to a variety of prediction tasks, including regression, classification and ranking. Different objective functions should be used to customize the IFM model for different tasks. For binary classifications, the loss function is log loss. For regression, a commonly adopted loss function is the squared loss:

where χ denotes the training data, and y (x), ˆ yIFM (x) denote the label and target of the input x, respectively. In this work, we mainly focus on the regression task and optimize the squared loss of Equation 3. The optimization for ranking and classification tasks can be done in the same way. To optimize the loss function, we employ adaptive gradient descent (AdaGrad), a universal solver for neural network models. The key to implementing the AdaGrad algorithm is to obtain the derivative of the squared loss Lreg w.r.t. each parameter with an adaptive learning rate. In our model, not only can we train all parameters directly through backpropagation, but also we can pretrain the feature weight wi and embedding vector vi through a FM.

Overfitting is a perpetual issue in model training and we employ dropout [Srivastava et al., 2014] and L2 regularization to control the overfitting of FEN. In doing so, the actual objective function to be optimized is:

where λ controls the regularization strength and Φ denotes the weight matrix {W, P} in FEN.

4 RelatedWork

As extensions of FMs, GBFM [Cheng et al., 2014] selects good features using gradient boosting and models only the interactions between good features. Field-aware FM (FFM) [Juan et al., 2016] enables each variable to have multiple embedding vectors for feature interactions, but its large number of parameters may result in undesirable computational cost. In our work, we aim to boost the performance of FMs by explicitly considering the impact of each individual input on the representation of features, which refines the weight and embedding vector of each feature with regard to different instances.

Meanwhile, an increasing number of researchers are interested in employing deep learning for prediction. Specifically, some models use DNN to explore high-order feature interactions: Wide&Deep [Cheng et al., 2016], employs a Multilayer Perceptron(MLP) on the concatenation of feature embedding vectors to learn feature interactions; DeepCross [Shan et al., 2016] applies a deep residual MLP to learn cross features; PNN [Qu et al., 2016] introduces a product layer between the embedding layer and DNN layers to learn feature interaction; DeepFM [Guo et al., 2017] uses the FM component and the deep component to get 2-order and highorder interaction information; NFM [He and Chua, 2017] extends FMs by using DNN to explore high-order nonlinear feature interactions; xDeepFM [Lian et al., 2018] learns certain bounded-degree feature interactions explicitly and arbitrary low/high-order feature interactions implicitly. Some other models extend FMs by discriminating the importance of feature interactions. For example, AFM [Xiao et al., 2017] uses attention mechanism to weight different feature interactions, and FwFM [Pan et al., 2018] uses mutual information to distinguish the strength of feature interactions.

In all the above models, each feature holds a fixed representation for different instances, instead of an adaptive representation according to each unique instance. Consequently, the performance of these methods may be limited, as the impact of each instance on the representation of features is ignored. By extending FMs with a more accurate and flexible representation of features, IFM is expected to produce superior performance compared to existing methods.

5 Experiments

In this section, we conduct extensive experiments to answer the following questions:

• (Q1) How do the key hyper-parameters of IFM (e.g., the dropout ratio and the number of hidden layers) impact its performance?
• (Q2) Can the factor estimating network effectively refine the representation of features for different instances?
• (Q3) How does IFM perform compared to state-of-theart methods for sparse prediction?

5.1 Experimental Settings

Datasets. For regression tasks, we evaluate various prediction models on two public datasets: Frappe 2 [Baltrunas et al., 2015] and MovieLens [Harper and Konstan, 2016]. The Frappe dataset has been used for context-aware mobile app recommendation, which contains 96,202 records with 957 users and 4,082 apps. The MovieLens dataset has been used for personalized tag recommendation, which contains 668,953 tag applications of 17,045 users on 23,743 items with 49,657 distinct tags. We follow the data processing details of NFM [He and Chua, 2017] and randomly split instances by 8:1:1 for training, validation and test. For binary classification, we use the Avazu 3 dataset, which was published in the contest of Avazu Click-Through Rate Prediction in 2014. The public dataset is randomly split into training and test sets by 4:1. Meanwhile, we remove the features appearing less than 20 times to reduce dimensionality.

Evaluation Metrics. We use MAE (mean absolute error) and RMSE (root mean square error) for evaluating regression tasks such as recommendation and use AUC (Area Under ROC) and log loss (cross entropy) for binary classification tasks.

Baselines. We compare IFM with the following competitive methods, some of which are state-of-the-art models for sparse prediction.

• LibFM [Rendle, 2012]: This is the official implementation 4 for factorization machines that features stochastic gradient descent.
• Wide&Deep [Cheng et al., 2016]: The wide part is linear regression and the deep part is a three-layer MLPs with layer sizes 1024, 512 and 256.
• DeepFM [Guo et al., 2017]: The FM part is a factorization machine, and the deep part is a three-layer MLP with layer sizes 200, 200 and 200.
• NFM [He and Chua, 2017]: We take the implementation of NeuralFM and set the number of layers in the hidden layer to 1 with 512 neurons as the original paper.
• AFM [Xiao et al., 2017]: We use the implementation for AttentionFM, where the attention factor is set to 16 and the L2 regularization of attention net is set to 2 as recommended.

2 http://baltrunas.info/research-menu/frappe

3 http://www.kaggle.com/c/avazu-ctr-prediction

4 http://www.libfm.org/

Parameter Settings. We implement our method using Tensorflow 5 . To enable a fair comparison, all methods are learned by optimizing the squared loss (Equation 9) using the Adagrad (Learning rate: 0.01). The batch sizes for Frappe and MovieLens are set to 2048 and 4096, respectively, while the embedding size is set to 256 for all methods. The batch sizes for Avazu is set to 2048 and the embedding size is set to 40. We use a L2 regularization with λ = 0.00001 for NFM, Wide&Deep, DeepFM and IFM. The default setting for the number of neurons per layer in IFM is 256. For Wide&Deep, AFM, DeepFM and IFM, we find that pre-training their feature embeddings with FM leads to better performance than using random initialization, and so we present their performance with pre-training.

5.2 Hyper-Parameter Study (Q1)

We study the impact of hyper-parameters on IFM in this section, including the number of hidden layers, the dropout ratio and activation functions. We conduct experiments on the validation data by holding the settings for the FM prediction layer while varying the settings for FEN.

Depth of Network

Figure 3(a) and Figure 4(a) show the impact of the number of hidden layers in FEN. We can observe that the performance of IFM increases with the increasing of networks at the beginning. However, the model performance starts to degrade when the depth of networks is greater than 2(Frappe) or 3(Movielens). This is caused by overfitting evidenced by the observation that the training error still keeps decreasing.

5 Codes are available at https://github.com/gulyfish/Input-awareFactorization-Machine

Dropout Ratio

Dropout is an effective regularization technique for neural networks to prevent overfitting. Figure 3(b) and Figure 4(b) show the impact of dropout ratio on FEN. By setting the dropout ratio to a proper value, the performance of IFM on both datasets can be significantly improved. Specifically, the optimal dropout ratios for Frappe and MovieLens are 0.3 and 0.4, respectively. This verifies the usefulness of dropout on the factor estimating network, which also improves the generalization of IFM.

Activation Function

A common practice in deep learning literature is to employ non-linear activation functions on hidden neurons. We thus compare the performance of different activation functions on IFM. As shown in Figure 5, ReLU is more appropriate than others for the two datasets.

5.3 Impact of the Factor Estimating Network (Q2)

The factor estimating network in IFM plays a pivotal role in refining the representations of features for different instances. We first compare IFM with FM to demonstrate the importance of the factor estimating network. Figure 6 shows that IFM generally converges faster than FM. On Frappe and MovieLens, both the training and validation errors of IFM are much lower than those of FM, indicating that IFM can better fit the data and lead to more accurate prediction. This justifies the rationality of IFM's design of learning a unique weight for the same feature in different instances via a neural network, which is the key contribution of this work.

Mechanism Analysis

To better demonstrate the effect of FEN, we select three test instances from Frappe. Table 1 shows the difference in feature representation with respect to different instances. We can see that, in IFM, the same predictor (e.g., x3 and x9) may have significantly different degrees of importance in different instances, as evidenced by the diverse input-aware factor values. By contrast, FM assigns each feature a fixed level of predictive power in three instances, resulting in systematically larger prediction errors.

Performance Analysis of Model Components

Note that, in IFM and other baseline models, each extra model component has its own unique functionality: DNN models high-order feature interactions; attention tries to produce a weight for each feature interaction; FEN focuses on the adaptive representation of features. To provide more insights into the effect of each type of component, we first train all models without using the extra components (i.e., simulating the standard FM model). We then freeze feature embeddings, and train the extra components only. To enable a fair comparison, the hyper-parameters of each model are carefully tuned for best possible performance, and upon convergence, the relative improvements (RI) of each model on Frappe and MovieLens are listed in Table 2. It is clear that with the help of FEN, IFM achieves 35% and 22% improvement on the two datasets, respectively. Although the DNN and attention components also bring noticeable benefits to the FM model, the importance of incorporating adaptive feature representation is clearly highlighted.

5.4 Performance Comparison (Q3)

In this section, we compare IFM with several strong baselines, and the results are summarized in Table 3 and Table 4, from which we have the following key observations:

• First, IFM consistently achieves the best results (minimum prediction errors) on three datasets with large performance margins over state-of-the-art methods. This
• demonstrates overall the effectiveness of IFM and further justifies the importance of input-aware feature representation.
• Second, Wide&Deep, DeepFM and NFM are consistently better than the FM model, which is attributed to the feature extraction by DNN for modelling higherorder feature interactions. However, the superiority of IFM demonstrates that a shallow model with accurate representation of features can achieve even better performance than deep learning methods. This points to a promising direction for future research: developing more effective methods for learning accurate feature representations.

Table 4: Performance comparison for binary classification task on Avazu (embedding size: 40)

6 Conclusion

In this paper, we presented an effective predictive model named Input-aware Factorization Machine (IFM) for sparse datasets. It aims to enhance traditional FMs by purposefully learning more flexible and accurate representation of features for different instances with the help of a factor estimating network. The major advantage is that it provides a principled mechanism to better reflect the predictive power of each feature in specific situation, while keeping the linear time complexity as the original FMs. Extensive experiments on three real-world benchmark datasets show that the accurate representation of features can yield better performance than capturing high-order feature interactions. In terms of four popular performance metrics, IFM significantly outperforms the classical FM and state-of-the-art deep learning based approaches such as Wide&Deep, AFM, NFM and DeepFM on regression and classification tasks.