Ivor W. Tsang
ABSTRACT
Maximum margin discriminant analysis (MMDA) was proposed that uses the margin idea for feature extraction. It often outperforms traditional methods like kernel principal component analysis (KPCA) and kernel Fisher discriminant analysis (KFD). However, as in other kernel methods, its time complexity is cubic in the number of training points m, and is thus computationally inefficient on massive data sets. In this paper, we propose an (1+ε)2-approximation algorithm for obtaining the MMDA features by extending the core vector machines. The resultant time complexity is only linear in m, while its space complexity is independent of m. Extensive comparisons with the original MMDA, KPCA, and KFD on a number of large data sets show that the proposed feature extractor can improve classification accuracy, and is also faster than these kernel-based methods by more than an order of magnitude.
- M. Bǎdoiu and K. L. Clarkson. Optimal core-sets for balls. In DIMACS Workshop on Computational Geometry, 2002.]]Google Scholar
- T. Friess, N. Cristianini, and C. Campbell. The kernel-adatron: a fast and simple learning procedure for support vector machines. In Proceeding of the Fifteenth International Conference on Machine Learning, pages 188--196, 1998.]] Google ScholarDigital Library
- W. Kienzle and B. Schölkopf. Training support vector machines with multiple equality constraints. In Proceedings of the European Conference on Machine Learning, 2005.]] Google ScholarDigital Library
- H.-C. Kim, S. Pang, H.-M. Je, D. Kim, and S. Bang. Constructing support vector machine ensemble. Pattern Recognition, 36(12):2757--2767, 2003.]]Google ScholarCross Ref
- A. Kocsor, K. Kovács, and C. Szepesvári. Margin maximizing discriminant analysis. In Proceedings of the 15th European Conference on Machine Learning, pages 227--238, Pisa, Italy, Sept. 2004.]]Google ScholarDigital Library
- O. Mangasarian and E. Wild. Multisurface proximal support vector machine classification via generalized eigenvalues. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(1):69--74, 2006.]] Google ScholarDigital Library
- S. Mika, G. Rätsch, J. Weston, B. Schölkopf, and K.-R. Müller. Fisher discriminant analysis with kernels. In Y.-H. Hu, J. Larsen, E. Wilson, and S. Douglas, editors, Neural Networks for Signal Processing IX, pages 41--48, 1999.]]Google Scholar
- J. Platt. Fast training of support vector machines using sequential minimal optimization. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning, pages 185--208. MIT Press, Cambridge, MA, 1999.]] Google ScholarDigital Library
- B. Schölkopf and A. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.]]Google Scholar
- I. W. Tsang, J. T. Kwok, and P.-M. Cheung. Core vector machines: Fast SVM training on very large data sets. Journal of Machine Learning Research, 6:363--392, 2005.]] Google ScholarDigital Library
- I. W. Tsang, J. T. Kwok, and K. T. Lai. Core vector regression for very large regression problems. In Proceedings of the Twentieth-Second International Conference on Machine Learning, pages 913--920, Bonn, Germany, Aug. 2005.]] Google ScholarDigital Library
Index Terms
- Efficient kernel feature extraction for massive data sets
Recommendations
A novel local sensitive frontier analysis for feature extraction
ICIC'09: Proceedings of the Intelligent computing 5th international conference on Emerging intelligent computing technology and applicationsIn this paper, an efficient feature extraction method, named local sensitive frontier analysis (LSFA), is proposed. LSFA tries to find instances near the crossing of the multi-manifold, which are sensitive to classification, to form the frontier ...
Constrained discriminant neighborhood embedding for high dimensional data feature extraction
When handling pattern classification problem such as face recognition and digital handwriting identification, image data is always represented to high dimensional vectors, from which discriminant features are extracted using dimensionality reduction ...
Efficient and robust feature extraction by maximum margin criterion
In pattern recognition, feature extraction techniques are widely employed to reduce the dimensionality of data and to enhance the discriminatory information. Principal component analysis (PCA) and linear discriminant analysis (LDA) are the two most ...
Comments