nips nips2011 nips2011-143 nips2011-143-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ziming Zhang, Lubor Ladicky, Philip Torr, Amir Saffari
Abstract: Local Coordinate Coding (LCC) [18] is a method for modeling functions of data lying on non-linear manifolds. It provides a set of anchor points which form a local coordinate system, such that each data point on the manifold can be approximated by a linear combination of its anchor points, and the linear weights become the local coordinate coding. In this paper we propose encoding data using orthogonal anchor planes, rather than anchor points. Our method needs only a few orthogonal anchor planes for coding, and it can linearize any (α, β, p)-Lipschitz smooth nonlinear function with a fixed expected value of the upper-bound approximation error on any high dimensional data. In practice, the orthogonal coordinate system can be easily learned by minimizing this upper bound using singular value decomposition (SVD). We apply our method to model the coordinates locally in linear SVMs for classification tasks, and our experiment on MNIST shows that using only 50 anchor planes our method achieves 1.72% error rate, while LCC achieves 1.90% error rate using 4096 anchor points. 1
[1] Bordes, A., Bottou, L. & Gallinari, P. (2009) Sgd-qn: Careful quasi-newton stochastic gradient descent. Journal of Machine Learning Research (JMLR).
[2] Bordes, A., Bottou, L., Gallinari, P., & Weston, J. (2007) Solving multiclass support vector machines with larank. In Proceeding of International Conference on Machine Learning (ICML).
[3] Bordes, A., Ertekin, S., Weston, J., & Bottou, L. (2005) Fast kernel classifiers with online and active learning. Journal of Machine Learning Research (JMLR).
[4] Chang, C. & Lin, C. (2011) LIBSVM: A Library for Support Vector Machines. ACM Transactions on Intelligent Systems and Technology, vol. 2, issue 3, pp. 27:1-27:27.
[5] Crammer, K. & Singer, Y. (2002) On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research (JMLR).
[6] Cristianini, N., Shawe-Taylor, J. & Lodhi, H. (2002) Latent Semantic Kernels. Journal of Intelligent Information Systems, Vol. 18, No. 2-3, 127-152.
[7] Everingham, M., Van Gool, L., Williams, C.K.I., Winn, J. & Zisserman, A. The PASCAL Visual Object Classes Challenge 2009 (VOC2009). http://www.pascal-network.org/ challenges/VOC/voc2009/workshop/index.html
[8] Fan, R., Chang, K., Hsieh, C., Wang, X. & Lin, C. (2008) LIBLINEAR: A Library for Large Linear Classification. Journal of Machine Learning Research (JMLR), vol. 9, pp. 1871-1874.
[9] Gönen, M. & Alpaydin, E. (2008) Localized Multiple Kernel Learning. In Proceeding of International Conference on Machine Learning (ICML).
[10] Kecman, V. & Brooks, J.P. (2010) Locally Linear Support Vector Machines and Other Local Models. In Proceeding of IEEE World Congress on Computational Intelligence (WCCI), pp. 26152620.
[11] Ladicky, L. & Torr, P.H.S. (2011) Locally Linear Support Vector Machines. In Proceeding of International Conference on Machine Learning (ICML).
[12] Lee, H., Battle, A., Raina, R., & Ng, A.Y. (2007) Efficient Sparse Coding Algorithms. In Advances in Neural Information Processing Systems (NIPS).
[13] Mairal, J., Bach, F., Ponce, J. & Sapiro, G. (2009) Online Dictionary Learning for Sparse Coding. In Proceeding of International Conference on Machine Learning (ICML).
[14] Shalev-Shwartz, S., Singer, Y., & Srebro, N. (2007) Pegasos: Primal Estimated sub-GrAdient SOlver for SVM. In Proceeding of International Conference on Machine Learning (ICML).
[15] Tsochantaridis, I., Joachims, T., Hofmann, T., & Altun, Y. (2005) Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research (JMLR).
[16] Wang, J., Yang, J., Yu, K., Lv, F., Huang, T., & Gong, Y. (2010) Locality-constrained Linear Coding for Image Classification. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
[17] Yu, K. & Ng, A. (2010) ECCV-2010 Tutorial: Feature Learning for Image Classification. http://ufldl.stanford.edu/eccv10-tutorial/.
[18] Yu, K., Zhang, T., & Gong, Y. (2009) Nonlinear Learning using Local Coordinate Coding. In Advances in Neural Information Processing Systems (NIPS).
[19] Yu, K. & Zhang, T. (2010) Improved Local Coordinate Coding using Local Tangents. In Proceeding of International Conference on Machine Learning (ICML).
[20] Zhang, H., Berg, A., Maure, M. & Malik, J. (2006) SVM-KNN: Discriminative nearest neighbor classification for visual category recognition. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2126-2136. 9