Optimizing Locally Linear Classifiers with Supervised Anchor Point Learning

1 Introduction

Kernel Support Vector Machine (SVM) [Sch¨olkopf and Smola, 2002] is a widely used classification technique. Although effective in dealing with nonlinear data, kernel SVM is computationally expensive especially for large datasets. To address this issue, locally linear classifiers [Ladicky and Torr, 2011; Yu et al., 2009] have been proposed to approximate nonlinear decision boundaries with locally linear classifiers using a local coding scheme. 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 linear coefficients are local coordinate values that can be used for subsequent classifier training.

Although effective, the classification performance of locally linear classifiers depends heavily on the quality of the local coding, which further depends on the anchor points being used. Current locally linear classification methods learn the anchor points and classifiers in two separate steps. In the first step, anchor points are learned and used to encode the training data with a local coding scheme. After that, supervised classifier training is performed based on the results of encoding. One major issue with this decoupled approach is that the purposes of each step are different. While local coding techniques mainly focus on minimizing the data reconstruction error and exploit unsupervised learning algorithms such as clustering [van Gemert et al., 2008; Zhou et al., 2009] for anchor point learning, the main purpose of classifier learning is to minimize classification error. Since the anchor points are obtained in an unsupervised fashion without making use of class label information, discriminative information might be lost in the encoding step and the local coding produced by these anchor points may not be optimal for the classification task. Therefore, an optimized classification model should exploit supervised information for anchor point learning and update both the anchor points and classifier simultaneously for further performance improvement.

In this paper, we propose an efficient nonlinear classification algorithm based on the Locally Linear Classifiers with Supervised Anchor Point Learning (LLC-SAPL). We take a fully supervised approach for learning both anchor points and classifiers jointly in a discriminative framework. Firstly, we use a localized soft-assignment coding scheme [Liu et al., 2011] for encoding the training data. The use of softassignment coding enables us to express the local coordinates in analytic form. With these local coordinates, any nonlinear but smooth function defining the classifier can be approximated using multiple linear functions. We can then formulate a single optimization problem over both anchor point and classifier variables that can be efficiently solved using stochastic gradient descent. Instead of choosing anchor points independently from the classifiers, our LLC-SAPL model is capable of refining the initial anchor points while simultaneously updating the classifier to minimize the regularized classification risk. Moreover, the stochastic gradient descent is simple and fast so that it can be applied to large datasets in an online fashion. Experimental results on benchmark datasets show that LLC-SAPL outperforms stateof-the-art methods with unsupervised anchor point learning and achieves accuracy rates on par with the kernel SVM.

However, LLC-SAPL achieves much higher efficiency than kernel SVM in prediction.

2 RelatedWork

Local coding methods provide a useful tool for approximating data on the nonlinear manifold. Different encoding schemes have been proposed in the literature, including local soft-assignment coding [van Gemert et al., 2008; Liu et al., 2011], Local Coordinate Coding (LCC) [Yu et al., 2009]. 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. The anchor points are learned in unsupervised fashion either by using a clustering algorithm or solving a locality or sparsity constrained least squares optimization problem for direct minimization of the reconstruction error.

A number of locally linear classifiers have been proposed based on local coding methods, most notably LCC+SVM [Yu et al., 2009] and LLSVM [Ladicky and Torr, 2011]. LCC+SVM applies a linear SVM directly to the local coordinates obtained by the LCC [Yu et al., 2009] scheme by treating them as feature values. Alternatively, LLSVM treats the local coordinates as weight values for assigning training data into different local regions. Separate linear classifiers are then trained for the weighted data points in each local region and combined to form a locally linear classifier.

Apart from local coding based methods, there exist other locally linear classifiers, such as SVM-KNN [Zhang et al., 2006], CSVM [Gu and Han, 2013] and LDKL [Jose et al., 2013]. SVM-KNN employs a lazy learning strategy by training a linear SVM in the subregion of a testing example and using the trained SVM classifier for prediction. CSVM adopts K-means to partition the data into clusters and then trains a linear SVM for each cluster. Meanwhile, CSVM requires the weight vector of each linear SVM to align with a global weight vector, which can be treated as a type of regularization. LDKL learns a tree-based primal feature embedding that encodes non-linearities, and then combines this feature embedding with the SVM classifier. Same as the proposed LLC-SAPL, LDKL is a fully supervised technique where the trees are built by utilizing the label information.

An alternative approach for large-scale kernel classification is the Nystr¨om method [Li et al., 2010; Williams and Seeger, 2001; Yang et al., 2012], that provides a low rank approximation to the kernel matrix by sampling a subset of columns. As a generic technique for matrix factorization, the Nystr¨om method is not specifically designed for the classification task and does not take into account label information in the factorization process. Hence discriminative information may be lost with the Nystr¨om approximation, which leads to sub-optimal solution for the classifier model.

3 LLC-SAPLModel

3.1 Localized Soft-assignment Coding

We first introduce the local coding scheme employed by the LLC-SAPL model. Let {vj}mj=1 denote the set of m anchor points generated by K-means clustering. Each data point x is then approximated by a linear combination of surrounding anchor points:

The coefficient γvj (x) specifies the degree of membership of x to the jth anchor point vj and is defined by:

where d(x, vj) is the squared Euclidean distance between x and vj, 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 each data point x with k nonzero coefficients, and the coefficients for the remaining anchor points are all set to zero. In contrast, a global coding scheme expands a data point to all the anchor points and ignores the underlying local manifold structure, which leads to unreliable estimation of the membership to distant anchor points. By assigning a data point only to its surrounding anchor points, the above "localized" soft-assignment coding scheme alleviates this problem and achieves computational efficiency at the same time due to the sparse representation.

3.2 AUnified Framework for Learning Anchor Points and Locally Linear Classifier

We next integrate the above local coding scheme into locally linear classifier, leading to a unified framework for learning both the anchor points and the locally linear classifier. In this paper, we focus on the linear SVM classifier, but the technique discussed below can be applied to other linear classifiers by modifying the loss function. Given the labeled binary dataset {(xn, yn)}Nn=1 with xn ∈ RD and yn ∈ {-1, 1}, one can solve the optimization problem below for linear SVM training:

where the first term in Equation (3) is the regularization term on the classifier weight vector w and the second term is the average hinge loss incurred. f(x) is the decision function for linear SVM.

Although linear SVM is extremely efficient, it cannot handle nonlinear decision boundaries with acceptable accuracy due to the use of linear prediction function f(x). In a sufficiently small region, a nonlinear decision boundary is approximately linear and data is locally linearly separable. To encode this local linearity, the weight vector w and bias b of the SVM classifier should vary according to the location of the point x in the feature space as:

The dimensionality of feature vector x is D.

To deal with nonlinear data, a smooth decision boundary with constrained curvature is desired, since an unconstrained decision boundary is likely to overfit [Ladicky and Torr, 2011]. Smoothness and constrained curvature imply that the functions w(x) and b(x) are Lipschitz smooth in the feature space x. Thus according to [Yu et al., 2009], for a local coding scheme defined by anchor points v, any Lipschitz smooth function h(x) defined on a lower dimensional manifold can be approximated by a linear combination of function values h(v) over the set of anchor points as:

Thus we can approximate the weight functions wd(x) and bias function b(x) in Equation (6) using the localized softassignment coding as:

Substituting the above equations into Equation (6), we obtain:

This transformation can be seen as a finite kernel transforming a D-dimensional problem into a mD-dimensional one. It can also be interpreted as defining a locally linear classifier as the weighted sum of m separate linear classifiers for each anchor point, where the weights are determined by the local coordinates γv(x). To evaluate f(x) for each data point x, one needs to calculate the corresponding local coordinates γv(x), which further depend on the anchor points v being used for local coding. This leads to a natural twostep approach taken by existing methods [Yu et al., 2009; Ladicky and Torr, 2011], which involves learning the anchor points first and evaluating the local codes for each data point, followed by the subsequent step of supervised classifier training. The anchor points are learned separately from the classifier, and are directly obtained using unsupervised learning techniques. This may lead to sub-optimal solutions for the discriminative classification task.

Let W = [w(v1), . . . ,w(vm)]T be a m × D matrix composed by stacking the m classifier weight vectors in rows. Let b = [b(v1), . . . , b(vm)]T and γv(x) = [γv1 (x), . . . , γvm (x)]T be m-dimensional vectors of bias terms and local coordinates respectively. The decision function of the locally linear classifier in Equation (10) can then be written as:

Note that the decision function fW,b,v(x) in Equation (11) depends on both the classifier variables W, b and the anchor point variable v, which determines the local coordinates γv(x). This motivates an optimization-based approach for jointly learning both the classifier and the anchor points. Using a similar formulation to Equation (3), we define the LLCSAPL optimization problem as follows:

where ‖W‖2F = ∑mj=1 ∑Dd=1 W 2 j,d . Note that here the anchor point variable v is treated as one of the target variables to be optimized in the objective function Q. This is made possible by the use of localized soft-assignment coding scheme in our approach, where the local coordinates γv(x) are subdifferentiable to the anchor point variable v. In contrast, when using the standard sparse coding schemes, there is no closed-form solution to local coordinate values. Hence, it is infeasible to incorporate them into the optimization problem formulated above.

The use of embedded optimization for both feature and classifier variables in Equation (12) is crucial to the success of our approach. A na¨ıve approach for selecting anchor points with supervised information is not guaranteed to retain the discriminative information for classification. Consequently, the selected anchor points may not be optimal for the linear classifier being used. On the contrary, our approach provides a principled solution to joint anchor point optimization and classifier training instead of treating them separately.

The LLC-SAPL formulation in Equation (12) defines a generic framework that includes LLSVM [Ladicky and Torr, 2011] and LCC+SVM [Yu et al., 2009] as special cases. Specifically, it reduces to LLSVM if the anchor points v are fixed and only the classifier variables W and b are optimized. LLSVM further reduces to the degenerate case LCC+SVM if W = 0 and only b is optimized. In this case, the decision function reduces to a linear classifier where the local coordinate values γv(x) are used as input features and the bias vector b becomes the weight vector for the linear classifier. We can improve either LLSVM or LCC+SVM with the proposed LLC-SAPL framework by minimizing the objective function Q in Equation (12) with respect to both the anchor points and classifier variables. In the following discussion, we focus on the more generic scenario of LLC-SAPL, which can be treated as the fully supervised counterpart of LLSVM. However, the techniques presented below can be easily adapted to obtain optimized anchor points for the degenerate case LCC+SVM, which we refer to as LLC-SAPLlcc in subsequent text.

3.3 The Stochastic Gradient Descent Algorithm for LLC-SAPL

The Stochastic Gradient Descent (SGD) algorithm is simple and efficient, and can be applied to large datasets in an online fashion. Empirical results have shown that SGD significantly outperforms other complex optimization methods for training linear SVMs [Bordes et al., 2009; Shalev-Shwartz et al., 2007]. We now apply the SGD algorithm to the LLC-SAPL formulation in Equation (12). Each iteration of SGD involves drawing a random data point x and its corresponding label y and updating the current anchor points v and classifier variablesW, b if the hinge loss is positive. For updating anchor points v, we take the partial derivative of Q in Equation (12) with respect to v while fixingW, b. Since the data point x is approximated as a linear combination of its k-nearest anchor points, only the k-nearest anchor points need to be optimized in each iteration. Assume that the jth anchor point vj belongs to the k-nearest neighbors of x. Firstly, we take the partial derivative of γv(x)T with respect to vj. The obtained derivative ∂γv(x)T ∂vj is a D × m matrix, among which only k columns are nonzero. The jth column is computed as:

where

The other nonzero columns except the jth column are computed as:

where vh also belongs to the k-nearest neighbors of x and it is not equal to vj.

Then the jth anchor point vj is updated as:

where t denotes the current iteration number. The optimal learning rate is denoted as 1 λ(t+t0) [Shalev-Shwartz et al., 2007], where t0 is a positive constant [Bordes et al., 2009], that avoids producing too large steps in the first few iterations. The classifier variables W and b are updated as:

To speed up the training process, we adopt a similar strategy to [Bordes et al., 2009] and perform a regularization update to the weight matrix W every skip iterations by:

Our LLC-SAPL algorithm is presented in Algorithm 1. Kmeans is utilized to initialize the set of anchor points v, which are then used to encode the training data with the localized

Algorithm 1 LLC-SAPL

Input: Training data {(xn, yn)}Nn=1 ⊂ RD × {-1, 1}, the number of anchor points m and parameters λ, t0, T , skip Output: Classifier variables W, b and anchor points v Initialize anchor points v by K-means. Convert each x to z via Equation (20) and initialize classifier variables W, b by training a linear SVM on the transformed dataset {(zn, yn)}Nn=1 . t = 0

while t ≤ T do

Sample a data point x randomly.

Compute the local coordinates γv(x) via Equation (2).

Compute hinge loss L=1-y(γv(x)T Wx+γv(x)T b).

if L > 0 then

for j = 1 → k do

Update the jth nearest anchor point of x via

Equation (16).

end for

Update W via Equation (17).

Update b via Equation (18).

end if

if t mod skip == 0 then

Update W via Equation (19).

end if

t = t +1

end while

soft-assignment coding scheme and obtain the local coordinates γv(x). To initialize the classifier weights W and biases b, the following transformation is applied to each data point in the training set

where the operator ⊗ is the Kronecker product. This is equivalent to appending 1 to the column vector x and multiplying each element of γv(x) with the augmented feature vector. Then we apply LibLinear [Fan et al., 2008] to the new data {(zn, yn)}Nn=1 for obtaining the initial W and b.

The SGD iterations start after the initialization steps. In each iteration, a subset of anchors corresponding to the knearest neighbors of the selected data point are updated along with the classifier variables if a positive hinge loss is incurred. In this way, all the anchor points are updated after one epoch (a full pass through the whole training set).

For the degenerate version LLC-SAPLlcc, we need to make some minor modifications to the LLC-SAPL algorithm. Most importantly, we need to set all occurrences of W to 0 in the relevant algorithm steps and equations for LLC-SAPLlcc and ignore those steps that involve updating W in Algorithm 1. To obtain initial b, we only need to train a linear SVM on the local coordinates γv(x). Moreover, as the bias vector b serves as the weight vector of the globally linear SVM, we should also apply regularization updates via Equation (19) by substituting Wwith b in the equation, in addition to the regular updates of b in Equation (18).

For prediction, the test data are encoded using the learned anchor points and then classified by the locally linear classifier. The prediction complexity is linear in the number of anchor points while the prediction complexity of kernel SVM scales with the number of support vectors. For large datasets, the number of support vectors is usually orders of magnitude larger than that of anchor points. Hence the proposed algorithm is much more efficient than kernel SVM in prediction, which is critical for large-scale or online applications.

3.4 Extension toMulti-class Classification

For multi-class classification problems, we can combine multiple binary classifiers discussed above following standard one-vs-all strategy. However, in this case, the multi-class algorithm learns class-specific anchor points, with different anchor points obtained for different binary classification problems. This leads to significant computational overhead for multi-class problems with many classes, as the number of anchor points produced scales by mI, where I denotes the number of classes. Hence it is desirable to share the same anchor points among different classes, which leads to the following formulation for multi-class classification problem:

The variables WI i=1 and bIi=1 represent the weight matrices and bias vectors of the locally linear classifiers for I classes. The label yn,i equals 1 if the nth example belongs to the ith class and -1 otherwise. Compared with the LLC-SAPL formulation for binary classification in Equation (12), the multiclass formulation in (21) learns different weight matrices and bias vectors for different classes while sharing the same anchor points among classes. This is much cheaper than inducing different anchor points for different classes with the na¨ıve one-vs-all approach, and scales our algorithm up to large multi-class datasets nicely. This multi-class classification problem can be solved by the same SGD algorithm presented in Algorithm 1 subject to slight modifications.

4 Experiments

4.1 Synthetic Dataset

The synthetic dataset contains points randomly sampled from two Sine signals, as shown in Figure 1. Each signal contains 1000 points and forms one class. We then apply LLSVM, LLC-SAPL and Kernel SVM to this dataset. The number of anchor points is set to four for both LLSVM and LLCSAPL. The decision boundaries produced by the above methods are displayed by red curves in Figures 1(a), (b) and (c) respectively. These results clearly show that LLSVM produces sub-optimal decision boundary compared to the other two methods. Since LLSVM employs unsupervised anchor point learning and fixes the anchor points for subsequent classifier learning, the anchor points thus obtained may not be optimized for the learned classifier and be likely to lead to degenerate performance. On the contrary, our LLC-SAPL model utilizes a fully supervised approach for learning both the anchor points and classifier jointly. The decision boundary produced by LLC-SAPL is quite similar to that of kernel SVM. However, LLC-SAPL only uses four anchor points, while kernel SVM learns 186 support vectors. The prediction cost scales linearly with the number of anchor points for LLC-SAPL and the number of support vectors for kernel SVM. Therefore, LLC-SAPL is much more efficient than kernel SVM in the prediction phase.

4.2 Real Datasets

We use ten benchmark datasets: Banana, IJCNN, SKIN, Magic04, CIFAR, RCV1, USPS, MNIST, LETTER and MNIST8m. The Banana, USPS and MNIST datasets are used in [R¨atsch et al., 2001] [Hull, 1994] [LeCun et al., 1998]. The IJCNN, RCV1 and MNIST8m datasets are obtained from the LibSVM website [Chang and Lin, 2011]. The preprocessed binary CIFAR dataset is taken from [Jose et al., 2013]. The others are available at the UCI repository [Bache and Lichman, 2013]. The first six datasets are used for binary classification tasks, and the other four are multi-class datasets. All the datasets have been divided into training and testing sets except the Banana, SKIN, Magic04 and MNIST8m datasets. For Banana and Magic04, we randomly selected two thirds of examples for training and the rest for testing. For SKIN, we used half for training and the rest for testing. The MNIST8m dataset contains 8.1 million examples and was generated by performing careful elastic deformation of the original MNIST training set [Loosli et al., 2007]. We used the first 8 million examples as training data and tested on the 10,000 examples in the original MNIST testing set. All the datasets are normalized to have zero mean and unit variance in each dimension. Table 1 gives a brief summary of these datasets. It can be seen that the datasets used in our experiments have a wide coverage of different scenarios, including high-dimensional We compare our methods with seven previously mentioned methods: linear SVM, kernel SVM, LLSVM, LCC+SVM, SVM-KNN, CSVM and LDKL. We use LibLinear [Fan et al., 2008] and LibSVM [Chang and Lin, 2011] for training linear SVM and Gaussian kernel SVM respectively. The regularization parameter C is tuned by 5-fold cross validation on the training set for both linear and kernel SVMs. Cross validation is also used to tune the kernel width of the Gaussian kernel for kernel SVM, and the number of nearest neighbors for SVM-KNN. For the two proposed methods (LLC-SAPL and LLC-SAPLlcc), LLSVM and LCC+SVM, we adopted the same parameter values suggested in [Ladicky and Torr, 2011] by setting the number of anchor points m to 100 and number of nearest neighbours k to 8 for the local coding step. The parameters of all the other methods are set as in their original papers, with most parameters set by cross validation. For those methods involving K-means clustering or other random factors, we take the average testing results and the standard deviation over 10 random repetitions. The comparison results in terms of classification accuracy and testing time are presented in Tables 2 and 3. Note that the results for kernel SVM and SVM-KNN are left empty for the RCV1 and MNIST8m datasets, since the large size of the datasets makes the training or testing of kernel SVM and SVM-KNN infeasible.

Unsurprisingly, linear SVM does not perform well on all the datasets as it can not handle nonlinear data. Kernel SVM achieves the best performance overall. Nevertheless, kernel SVM is expensive in prediction especially for large datasets as shown in Table 3. The proposed LLC-SAPL achieves comparable performance to kernel SVM, but it is much more efficient in prediction. This is due to the fact that LLCSAPL uses much less number of anchor points compared to the large number of support vectors used by the kernel SVM model, which hinders efficiency in prediction. As a degenerate case of LLSVM, LCC+SVM does not perform as well as LLSVM. This is also true for LLC-SAPL and LLCSAPLlcc. However and most notably, LLC-SAPL outperforms LLSVM in classification accuracy on all datasets, and so does LLC-SAPLlcc and LCC+SVM. Since LLC-SAPL and LLC-SAPLlcc are supervised counterparts of LLSVM and LCC+SVM, this clearly demonstrates the effectiveness of anchor point learning for classification. Moreover, LLCSAPL is as efficient as LLSVM for prediction since both follow the same procedure for prediction and use same number of anchor points. Hence we have only included the testing time results for LLC-SAPL in Table 3. For the same reason, the testing time results for LLC-SAPLlcc are included while the results of LCC+SVM are omitted.

The training speeds of LLC-SAPL and LLC-SAPLlcc are slower than LLSVM and LCC+SVM due to the update of anchor points during training. However, training LLC-SAPL is much faster than kernel SVM for large datasets. For each epoch, classifier learning amounts to training multiple linear SVMs over small subsets of training data, which can be efficiently solved and effectively parallelized for further speedup. The extra operations for searching and updating k nearest anchor points scale linearly with training size and anchor point number in each epoch. Therefore the whole SGD algorithm simply repeats linear operations over different epochs for anchor point optimization and linear SVM training. In contrast, there are no linear-time algorithms known for kernel SVM training, which scales poorly to large-scale data.

For other locally linear classifiers, both SVM-KNN and CSVM perform well on some datasets but not all of them. Moreover, SVM-KNN is time-consuming due to the nature of lazy learning. CSVM enforces alignment between the weight vectors of individual linear SVMs and a global weight vector, which is undesirable in some cases. Additionally, the performance of CSVM is heavily influenced by the initial K-means clustering results. Hence it is likely to perform poorly with improper initialization. LDKL achieves quite good performance overall, but LLC-SAPL still gains a margin of advantage over LDKL. The reason lies in the fact that LDKL learns a tree-based primal feature embedding to partition the feature space, which may lead to non-smooth partition over the feature space and abrupt change across region boundaries.

Now we investigate how the performance of LLC-SAPL varies over different numbers of anchor points. Figure 2 shows the classification accuracies of LLC-SAPL in solid line with the number of anchor points m ranging from 2 to 180. For comparison, we also display the accuracy values of LLSVM in broken line on the same plots. It can be clearly seen that the performances of both LLC-SAPL and LLSVM improve with increasing number of anchor points m and stabilize as m exceeds a certain threshold. After that, the changes in classification accuracy become quite small. Hence, both methods are not overly sensitive to the exact choice of m, which makes it easier for model selection. Notably, LLC-SAPL outperforms LLSVM for all different numbers of anchor points on all these datasets, which demonstrates the effectiveness of supervised anchor point learning. To achieve a similar performance as LLC-SAPL with 40 anchor points, LLSVM needs to use more than 100 anchor points for local coding, leading to higher prediction cost.

To further demonstrate the effectiveness of anchor point optimization, we record the objective function value as well as the classification accuracy on the testing set for each epoch and plot the values over different epochs. Figure 3 displays the epoch-wise results for optimization and classification, where red solid lines and black broken lines show the changes of accuracy values as well as objective function values respectively against epoch number. Due to space limitation, we only show the results of LLC-SAPL for two datasets, namely the binary IJCNN dataset and the multi-class USPS dataset, in Figures 3(a) and (b). Similar observations can be made for both LLC-SAPL and LLC-SAPLlcc on other datasets. It can be seen clearly that the objective function values are monotonically decreasing over the epochs. Classification accuracies are closely correlated with objective function values, and lower objective function values usually lead to higher accuracies. The trend is especially obvious for the first 5 epochs. For the real datasets in our experiments, our algorithm generally converges within 10 epochs. Therefore, our model can be efficiently trained. These results clearly demonstrate the effectiveness of supervised anchor point learning.

5 Conclusion

In this paper, we have proposed the LLC-SAPL model, a local coding based locally linear classifier model with supervised anchor point learning for nonlinear classification problems. Unlike previous methods that learn anchor points in an unsupervised fashion separately from supervised classifier learning, LLC-SAPL is a fully supervised method and learns the anchor points and classifier together by solving a single optimization problem with both variables. Consequently, LLC- SAPL is able to refine the initial anchor points to optimize classification performance.

In the future, we will look into the model selection problem and explore potential techniques [Zhu et al., 2011; Fu et al., 2010] for automatically selecting the optimal number of anchor points for the underlying problem.

Acknowledgments

This work is partly supported by NSFC (Grant No. 61379098, 61203239, 61472421) and Baidu research fund.