Additive Nearest Neighbor Feature Maps

In this paper, we present a concise framework to approximately construct feature maps for nonlinear additive kernels such as the Intersection, Hellinger´s, and X² kernels. The core idea is to construct for each individual feature a set of anchor points and assign to every query the feature map of its nearest neighbor or the weighted combination of those of its k-nearest neighbors in the anchors. The resultant feature maps can be compactly stored by a group of nearest neighbor (binary) indication vectors along with the anchor feature maps. The approximation error of such an anchored feature mapping approach is analyzed. We evaluate the performance of our approach on large-scale nonlinear support vector machines~(SVMs) learning tasks in the context of visual object classification. Experimental results on several benchmark data sets show the superiority of our method over existing feature mapping methods in achieving reasonable trade-off between training time and testing accuracy.