Locally Linear Factorization Machines

1 Introduction

Interactions between features play an important role in many classification and regression tasks. One of the widely used approach to leverage such interactions is the polynomial kernel[Friedman et al., 2001] which implicitly maps the data via the kernel trick. However, the cost of storing and evaluating the model is expensive especially for large datasets. This is sometimes called the curse of kernelization [Wang et al., 2010]. To address this issue, Factorization machines (FMs)[Rendle, 2010; 2012] have been proposed to model the high order nested interactions with factorized interaction parameters. The model estimation can be computed in linear time and they only depend on a linear number of parameters. This allows direct optimization and storage of model parameters without the need of storing any training data.

Despite their great success, FMs only consider the high order information of the input features which limits their capacities in non-linear problems and fails to capture the underlying structures of more complex data. Specifically, taking classification task into consideration, not all problems are approximately linearly separable after quadratic mapping. In most cases, real data naturally groups into clusters and lies on nearly disjoint lower dimensional manifolds and thus the original FMs are inapplicable. One solution to address this limitation is the locally linear classifiers [Ladicky and Torr, 2011; Yu et al., 2009; Mao et al., 2015] which leverage the manifold geometric structure to learn a nonlinear function which can be effectively approximated by a linear function with an coding under appropriate localization conditions. Since a nonlinear manifold behaves linearly in the local neighborhood, data on the manifold can be encoded locally in a local coordinate system established by a set of anchor points. Each data point can then be approximated with a linear combination of surrounding anchor points, and the weights are local coding coordinates which can be used for subsequent model training.

Although local coding methods provide a powerful tool for approximating data on the nonlinear manifold, the model performance of locally linear classifiers depends heavily on the quality of the local coding coordinates and the anchor points. The existing locally linear classifiers learn the local coding coordinates, the anchor points and classifiers in two separate steps. They first compute the anchor points with some unsupervised learning method that does not take class label information into account and encode the training data with a predefined local coding scheme, and then feed the results of encoding to the downstream supervised classifier training process. One major issue with this decoupled approach is that it only leverages the anchor points and local coding coordinates to improve classifier training task, but not reverse. This two-step procedure is rather suboptimal as the class label information is not used in discovering the anchor points and local coding coordinates, which is clearly not an optimal encoding for classification task as the two methods are not tightly coupled to fully exploit their potential.

In this paper, we present a novel Locally Linear Factorization Machines (LLFM) which is capable of learning complex non-linear data by exploring local coding technique. Unlike existing local coding classifiers that involve a two-step procedure, a joint optimization is formulated over the anchor points, local coding coordinates and FMs variables to minimize classification or regression risk simultaneously. Specifically, our learning method is capable of refining local coding scheme which adaptively choose the number of nearest anchor points and the corresponding approximation weight according to the current data point x and the anchor points. With these local coding coordinates, we adopt stochastic gradient descent to efficiently learn both the anchor points and the FMs model simultaneously. Experimental results on benchmark datasets show that our proposed LLFM approach with joint optimization (LLFM-JO) outperforms state-of-the-art methods with predefined fixed local coding scheme (LLFMDO) or unsupervised anchor point learning(LLFM-APL).

The rest of this paper is organized as follows. We first review related work about FMs and local coding method, followed by introducing the proposed Locally Linear Factorization Machines model. Then we present our joint optimization method with respect to the local coding coordinates, anchor points and FMs parameters. Finally, we discuss empirical results and conclude this work.

2 RelatedWork

2.1 FactorizationMachines

A standard 2-order FMs model takes the form:

where p is the dimensionality of feature vector x ∈ Rp , k ≪ p is a hyper-parameter that denotes the dimensionality of latent factors, and wj, vj,f are the model parameters to be estimated, i.e., Θ = {w1, . . . ,wp, v1,1, . . . , vp,k} = {w ∈ Rp ,V ∈ Rp×k }. It is equivalent to the following simple equation:

The gradient can be derived

The main advantage of FMs compared to the polynomial kernel in SVM [Vapnik, 2013] is the pairwise feature interaction weight matrix Z = VV⊤ ∈ Sp×p , where the number of parameters to estimate is reduced from p2 to kp by utilizing the factorized form. In addition, this factorization form helps to drop the prediction cost to linear runtime especially under sparsity condition. Given a training set [x1, . . . , xn]⊤ ∈ Rn×p and corresponding targets p[y1, . . . , yn]⊤ ∈ Rn , model parameters Θ can be learned by using the principle of empirical risk minimization and solving the following non-convex problem

where R(Θ) is the regularization term and ℓ is a convex loss function incurred. Although the objective is a non-convex problem, this optimization problem can be efficiently solved by many off-the-shelf approaches [Rendle, 2012].

In recent years, some developments in FMs have been proposed to efficiently optimize FMs model. [Blondel et al., 2015] gives a convex formulation of FMs based on the nuclear norm and proposed a two-block coordinate descent algorithm. [CHIN et al., ] proposes an alternating minimization algorithm based on Newton method. [Lin and Ye, 2016] designs a construction of an estimation sequence endowed with a CI-RIP condition and proposesp an efficient single-pass alternating updating framework for generalized FMs. [Blondel et al., 2016b] discusses the relationship between high order FMs and ANOVA kernel. [Blondel et al., 2016a] proposes linear time dynamic programming algorithms for evaluating the ANOVA kernel and the algorithm for training arbitraryorder FMs.

2.2 Locally Linear Coding

Local coding methods offer a powerful tool for approximating data on the nolinear manifold. All these methods employ a set of anchor points to encode data as a linear combination of surrounding anchor points, so as to minimize the approximation error. Specifically, let Z = {zi}mi=1 denote the set of m anchor points, any point x is then approximated as x ≈ ∑mi=1 γx,zi zi, where γx,zi is the local coding coordinates, depicting the degree of membership of x to the ith anchor point zi, constrained by ∑mi=1 γx,zi = 1. Different encoding schemes have been proposed in literature, [Liu et al., 2011; Van Gemert et al., 2008] proposes local soft-assignment coding, which is defined as:

where d(·, ·) is the distance function, and Nk(x) denotes the set of indices of k-nearest anchor points to x. Notice here only the k-nearest anchor points are considered for encoding data point x with k nonzero weights, and the remaining weights for anchor points are all set to zero. Other local coding methods include local coordinate coding [Yu et al., 2009], inverse Euclidian distance based weighting [Van Gemert et al., 2008; Ladicky and Torr, 2011], etc.

A number of locally linear classifiers have been proposed based on local coding methods. [Ladicky and Torr, 2011] calculates the local coordinates with fixed and predefined local coding scheme, and them treats the local coordinates as weights for assigning training data into different local regions. Separate model are trained for each local region and combined to form a local linear classifier. [Gu and Han, 2013] adopts K-means to partition the data into clusters and then trains a linear SVM for each cluster. Meanwhile, it requires each cluster's model to align with a global model, which can be treated as a type of regularization. Unlike these two-step methods, a joint optimization is formulated over the anchor points, local coding coordinates and FMs variables in our work.

3 Locally Linear FactorizationMachines

FMs haven been found successful in many prediction tasks, including classification, regression and ranking. However, they only consider the second order information of the input features which limits their capacity in non-linear problems and fails to capture the underlying structures of complex data.

One intuitive idea for addressing this limitation is to leverage the manifold geometric structure to learn a nonlinear function which can be effectively approximated by a linear function with an coding under appropriate localization conditions. In another word, we assume that in a sufficiently small region the decision boundary is approximately linear and each data point x can then be approximated with a linear combination of surrounding anchor points, which are usually called local codings scheme. To encode this local linearity with FMs, the model parameters Θ should vary according to the location of the point x in the feature space as:

According to [Yu et al., 2009; Ladicky and Torr, 2011], smoothness and constrained curvature of the decision boundary implies that the function w(x) and V(x) are Lipschitz in the feature space x. Thus, for a local coding scheme defined by anchor points, we can approximate the weight function w(x),V(x) of FMs using local coding as:

Substituting these equations into the prediction function f LLFM (x), we obtain:

where ΘLLFM = {Θzi }mi=1 = {wzi ,Vzi }mi=1 are the model parameters corresponding to the anchor point zi. This transformation can be seen as a finite kernel transforming a p-dimensional problem into a mp-dimensional one. It can also be interpreted as defining a locally linear Factorization Machines as the weighted average of m separate FMs with respect to each anchor point, where the weights are determined by the local coding coordinates. Let γx,z = [γx,z1 , · · · , γx,zm ]⊤ and f FM Z = [f FM z1 (x), · · · , f FM zm (x)]⊤ be m dimensional vectors by stacking the m FMs models. The prediction function in Equation (5) can be written as f LLFM γx,z,Z,ΘLLFM (x) = γ⊤ x,z f FM Z .

4 Joint OptimizationMethod for Locally Linear Factorization Machines

To evaluate f LLFM γx,z,Z,ΘLLFM (x) for each data point x, we need to calculate the corresponding local coding coordinates γx,z, that is further depend on the anchor points z being used and the local coding scheme, which means the prediction function f LLFM γx,z,Z,ΘLLFM (x) depends on the model parameters ΘLLFM, the anchor point variable z and local coding coordinates γx,z. This leads to a natural two-step approach taken by existing methods [Ladicky and Torr, 2011; Yu et al., 2009; Gu and Han, 2013], which first estimate the anchor points for each data point by adopting K-means clustering and evaluate the local coding coordinates with a predefined scheme by utilizing exponential decay scheme or inversely-proportional decay scheme, and then feeds the anchor points and the local coding coordinates to the downstream supervised model training. This two-step learning procedure is inconsistent with the objective function and rather suboptimal as the prediction information is not used in discovering the anchor points and the local coding scheme. This motivates a joint optimization method for LLFMs. Using a similar formulation to Equation (2), we define the LLFM optimization problem as follows:

Note that here the local coding coordinates γx,z and anchor points z are treated as the variables to be optimized. Previous approaches [Mao et al., 2015] select local coding coordinates without supervised information, which is not guaranteed to retain the discriminative information for prediction. Consequently, the selected anchor points and the local coding coordinates may not be optimal for the model being trained. On the contrary, the use of embedded optimization for the local coding scheme, the anchor points and the model parameters in Equation (6) is crucial to the success of our approach. The objective function in Equation (6) is a non-convex optimization problem when considering variables γx,z, Z, ΘLLFM together. Therefore, we iteratively optimize γx,z, Z, ΘLLFM until convergence to obtain a local minimum.

4.1 Local Coding Coordinates Optimization Method

To start off, we first present our optimization method for the local coding coordinates γx,z. Take the weight function w(x) into consideration, recall we seek to find the best local approximation in a sense of minimizing the distance between this approximation and the ground truth. Assume that for any data point x, the ground truth holds that wx = w(x) + ϵx, where w(·) is a Lipschitz continuous function that for any x1, x2 ∈ Rp it holds that |w(x1) -w(x2)| ≤ L · d(x1, x2) for some predefined distance function d(·, ·) and ϵx is a noise term that E[ϵx|x] = 0 and |ϵx| ≤ b for some given b > 0. Our task is to estimate w(x), where we restrict the estimator ˆw(x) to be of the form ˆw(x) = ∑mi=1 γx,zi wzi . That is, the estimator is a weighted average of the anchor points. Formally, the objective is to minimize the absolute distance between our approximation and the ground truth w(x), we need to solve

Decomposing the above objective into a sum of bias and variance terms, we can transforms it into

By Hoeffding's inequality it follows that | ∑mi=1 γx,zi ϵzi | ≤ C‖γx,z‖2 for C = b√2 log( 2δ ), w.p. at least 1 - δ. Inequality (7) yield a upper bound guarantee for solving the original objective with high probability, we can formulate the new problem as the following optimization:

where u = {Ld(z1, x), · · · , Ld(zm, x)}. Its Lagrangian is:

where λ ∈ R and θ1, · · · , θm ≥ 0 are the Lagrange multipliers. This optimization problem has a convex objective function and feasible affine constraints. Thus, satisfying the KKT conditions is a necessary and sufficient condition for finding the problem's optimum. Setting the partial derivative of L(γx,z, θ, λ) with respect to γx,z to zero gives:

Let γ ⋆x,z be the optimal solution. According to the KKT conditions, if γ ⋆x,zi > 0 it follows that θi = 0. Otherwise, γ ⋆x,zi = 0 and λ ≤ ui. Substituting it into the equality constraint ∑i γ ⋆x,zi = 1, for any γ ⋆x,zi > 0, we have

It demonstrates that the optimal weight γ ⋆x,zi is proportional to -d(zi, x), whose weight decay is quite slow compared to the popular exponential decay scheme or inverselyproportional decay scheme that used in [Mao et al., 2015; Gu and Han, 2013; Ladicky and Torr, 2011]. It also shows that parameter λ has a cutoff effect that only nearest anchor points that λ - Ld(zi, x) > 0 are considered for encoding data point x, the weights for the remaining anchor points are all set to zero. This is consistent with the previous predefined local coding scheme. Note that the objective (8) is a convex optimization problem, which can be efficiently solved using off-the-shelf toolbox. Here we follow the method in [Anava and Levy, 2016]. The key idea is to greedily add neighbors according to their distance from x until a stopping condition is achieved. Our algorithm is presented in Algorithm 1.

Denote by k the number of nonzero weights which correspond to the k smallest value of u. Squaring and summing Equation (9) over all the nonzero elements of γ ⋆x,z , we have

Algorithm 1 Local Coding Coordinates (LLC) Optimization Algorithm

Input: data point x and anchor points Z = {z1, · · · , zm} Initialization: λ0 = u1 +1, k = 0 and compute the vector of ascending ordered distance u ∈ Rm

end while

Output: The number of nearest anchor points k, compute the local coding coordinates γx,z based on (10)

which is equivalent to kλ2 -2λ ∑ki=1 ui +(∑ki=1 u2i -1) = 0. Solving this quadratic equation with respect to λ and ignoring the solution that violate γ ⋆x,zi ≥ 0, we get

4.2 Anchor Points and FMs OptimizationMethod

For the anchor points and FMs optimization, we apply the SGD method to the objective in (6). Specifically, at each iteration, we randomly sample a data point x and its corresponding target y, then we update the anchor points Z and FMs parameters ΘLLFM. Since the data point x is approximate as a linear combination of its k-nearest anchor points, only the k-nearest anchor points need to be optimized. For updating anchor points z, we take the partial derivative of the objective (6) with respect to z while fixing ΘLLFM. The derivative ∂γ⊤ x,z ∂zi is a (p+p2 ) ×mmatrix, among which only k columns are non zero. The ith column is computed as:

where s = ∂d(zi,x) ∂zi . The other nonzero columns except the ith column are computed as

-

where zj also belongs to the k-nearest neighbors of x and it is not equal to zi. Then the ith anchor point zi is updated as:

where ρz is the learning rate, t denotes the current iteration number and t0 is a positive constant [Bordes et al., 2009]. The optimal learning rate is denoted as ρ t+t0 [Shalev-Shwartz et al., 2007]. Note that our method works well with different loss function and can be applied to classification task or regression task, which only needs to minorly modify the last term about the derivative of the loss function in update rule (15). The FMs variables ΘLLFM can also be updated by utilizing SGD method (more details can be found in [Rendle, 2012; 2010]). Specifically, the update rules for FMs parameter θzi with respect to anchor point zi is:

where ∂f FM zi ∂θzi can be found in Equation (1). Algorithm 2 summarizes the proposed Locally linear Factorization Mahicnes with pJoint Optimization (LLFM-JO) method.

Algorithm 2 Locally Linear Factorization Mahicnes Joint Optimization Algorithm (LLFM-JO)

Input: Training data{(xn, yn}Nn=1 , the number of anchor points m and parameters ρ, β, L

while no convergence do

Sample a data point x randomly

Compute the local coordinate γx,z according to Algorithm 1

Compute the loss ℓ(y, f LLFM γx,z,Z,ΘLLFM (x))

for each nearest anchor point i with respect to data point x do

Update the ith nearest anchor point of x via (15)

Update the FMs model parameters with respect to this anchor point via (16)

end for

end while

Output: Compute the local coding coordinates γx,zi based on (10)

5 Experiments

In this section, we empirically investigate whether our proposed LLFM-JO method can achieve better performance compared to other state-of-the-art methods which employ LLFM method with unsupervised anchor point learning (LLFMAPL) and predefined local coding scheme (LLFM-DO) on benchmark datasets. Furthermore we examine the efficacy and efficiency of joint optimization.

5.1 Experimental Testbeds and Setup

We conduct our experiments on six public datasets. Table 1 gives a brief summary of these datasets. All the datasets are normalized to have zero mean and unit variance in each dimension. To make fair comparison, all the algorithms are conducted over 5 experimental runs of different random permutations. We apply logistic loss [Rendle, 2012] for training and evaluate the performance of our proposed methods for classification task by measuring accuracy and logistic loss. We adopt squared Euclidean distance function in local softassignment coding and our local coding coordinates optimization method. For parameter settings, we perform grid search to choose the best parameters for each algorithm on the training set.

5.2 Performance Comparison

In our experiments, we compare the following methods:

• FM: Factorization Machines with stochastic gradient descent optimization method, which is the baseline method we introduced in Section 2.1.
• LLFM-DO: Locally Linear Factorization Machines with Decoupled Optimization method. We first compute the anchor points by K-means clustering and encode the training data with local soft-assignment coding, and then estimate the LLFM model parameters. This method is a baseline to validate the efficacy of joint optimization over the anchor points, local coding coordinates and model parameters simultaneously.
• LLFM-APL: Locally Linear Factorization Machines with Anchor Point Learning method. We jointly estimate both the anchor points and FMs model parameters as described in Section 4.2 but using the fixed local softassignment coding scheme as Equation (3). This method is a baseline to validate the efficacy of local coding coordinates optimization method in algorithm 1.
• LLFM-JO: The proposed LLFM method with Joint Optimization method in algorithm 2.

5.3 Experimental Results

The detailed comparison results are shown in Table 2 and Figure 1. We can observe that:

• All of LLFM methods that employ local linear coding techniques achieve better performance in terms of training loss, test loss and test accuracy compared with original FM method. This validates the efficacy of leveraging local coding techniques to improve the performance of FMs. Since local linear coding techniques could leverage the manifold geometric structure to learn a much more complex nonlinear model.
• It is not surprising that the performance of LLFM-JO, LLFM-APL is much better than LLFM-DO. It reveals the importance of jointly optimizing over the anchor points and the FMs model. It is even more critical on LETTER and MNIST datasets since the dimension of input features is much bigger and the LLFM-DO may be more risky and unreliable in finding the right direction for update at each iteration. Moreover, it can be clearly seen that the performance of LLFM-JO outperforms LLFM-APL especially on LETTER dataset, this clearly demonstrates the power of the local coding coordinate optimization method in algorithm 1.
• As evidenced by Table 2, LLFM-JO takes less test time compared with LLFM-DO and LLFM-APL. The reason is that test time scales linearly with the parameter

• k, LLFM model need to compute k FM model with respect to k nearest anchor points for prediction. However, LLFM-DO and LLFM-APL are restricted to choose one value of k during the locally linear coding procedure, LLFM-JO method could choose k adaptively, which is in line with our theoretical findings.
• To further examine the effectiveness of joint optimization, we record the objective function value as well as the logistic loss on the test data for epoch. Figure 1 shows the epoch-wise results of different algorithm. It can be seen clearly that the test log loss of all different algorithms are monotonically decreasing over the epochs and LLFM-JO outperforms the other algorithms significantly.

6 Conclusion and FutureWork

In this work, we present a novel Locally Linear Factorization Machines (LLFM) model that exploring local coding technique. Unlike existing previous methods that learn the anchor points and local coding scheme separately before model training process we formulate a joint optimization over anchor point, local coding coordinate and FMs variables to minimize classification or regression risk. Our encouraging results show that LLFM-JO achieves better predictive accuracy than other competitive methods which employ LLFM with unsupervised anchor point learning and predefined local coding scheme. A shortcoming of current method is the high computation cost of model training due to the search and update of the local coding coordinates, it will be interesting to develop efficient local coding coordinates optimization approach. Future work includes combining LLFM model with learning to rank technique [Cao et al., 2007] and AUC maximization[Zhao et al., 2011].

Acknowledgments

This work was supported by State Street Zhejiang University Technology Centers.