Adaptive Kernel Principal Analysis for Online Feature Extraction
The batch nature limits the standard kernel principal component analysis (KPCA) methods in numerous applications, especially for dynamic or large-scale data. In this paper, an efficient adaptive approach is presented for online extraction of the kernel principal components (KPC). The contribution of this paper may be divided into two parts. First, kernel covariance matrix is correctly updated to adapt to the changing characteristics of data. Second, KPC are recursively formulated to overcome the batch nature of standard KPCA.This formulation is derived from the recursive eigen-decomposition of kernel covariance matrix and indicates the KPC variation caused by the new data. The proposed method not only alleviates sub-optimality of the KPCA method for non-stationary data, but also maintains constant update speed and memory usage as the data-size increases. Experiments for simulation data and real applications demonstrate that our approach yields improvements in terms of both computational speed and approximation accuracy.
[1] B. Scholkopf, A. Smola, and K. R. Muller, "Nonlinear component
analysis as a kernel eigenvalue problem," Neural Computation, vol. 10,
no. 5, pp. 1299-1319, 1998.
[2] K. R. Muller, S. Mika, G. Ratsch et al., "An introduction to kernel-based
learning algorithms," IEEE Trans. Neural Networks, vol. 12, no. 2, pp.
181-201, 2001.
[3] J. Yang, Z. Jin, J. Y. Yang, D. Zhang, and A. F. Frangi , "Essence of
kernel Fisher discriminant: KPCA plus LDA," Pattern Recognition, vol.
37, no. 10, pp. 2097-2100, 2004.
[4] H. Sahbi, "Kernel PCA for similarity invariant shape recognition,"
Neurocomputing, vol. 70, pp. 3034-3045, 2007.
[5] K. I. Kim, K. Jung, and H. J. Kim, "Face recognition using kernel
principal component analysis," IEEE Signal Processing Letters, vol. 9,
no. 2, pp. 40-42, 2002.
[6] X. L. Yu, X. G. Wang, and B. Y. Liu, "Supervised kernel neighborhood
preserving projections for radar target recognition," Signal Processing,
vol. 88, no. 9, pp. 2335-2339, 2008.
[7] G. Blanchard, O. Bousquet, and L. Zwald, "Statistical properties of kernel
principal component analysis," Machine Learning, vol. 66, no. 2-3, pp.
259-294, 2007.
[8] X. Liu, U. Kruger, T. Littler, L. Xie, S.-Q. Wang, "Moving window kernel
PCA for adaptive monitoring of nonlinear processes," Chemometrics and
Intelligent Laboratory Systems, vol. 96, no. 2, pp. 132-143, 2009.
[9] W.-J. Ma, H. Chen, and H.-Y. Tian, "Image registration based on
piecewise linear group parameters," Journal of Computer Applications,
pp. 976-8, 2007.
[10] K. I. Kim, M. O. Franz, and B. Scholkopf, "Iterative kernel principal
component analysis for image modeling," IEEE Trans.Pattern Analysis
and Machine Intelligence, vol. 27, no. 9, pp. 1351-1366, 2005.
[11] M. Girolami, "Mercer kernel-based clustering in feature space," IEEE
Tran. Neural Networks, vol. 13, no. 3, pp. 780-784, 2002.
[12] S. Gunter, N. N. Schraudolph, and S. V. N. Vishwanathan, "Fast iterative
kernel principal component analysis," Journal of Machine Learning
Research, vol. 8, pp. 1893-1918, 2007.
[13] T.-J. Chin, and D. Suter, "Incremental kernel principal component
analysis," IEEE Trans. Image Processing, vol. 16, no. 6, pp. 1662-74,
2007.
[14] C. Tat-jun, and D. Suter, "Incremental Kernel PCA for Efficient
Non-linear Feature Extraction," British Machine Vision Conference,
Edinburgh, 4-7 September 2006, (III:939).
[15] V. Franc, and V. Hlavac, "Greedy algorithm for a training set reduction in
the kernel methods," Computer Analysis of Images and Patterns,
Proceedings, vol. 2756, pp. 426-433, 2003.
[16] V. Franc, "Optimization Algorithms for Kernel Methods," Department of
Cybernetics, Faculty of Electrical Engineering, Czech Technical
University, Prague, 2005.
[17] K. B. Yu, "Recuresive updating the eigenvalue deccomposition of a
covariance-matrix," IEEE Trans. Signal Processing, vol. 39, no. 5, pp.
1136-1145, 1991.
[18] N. Critianini, and J. Shawe-Taylor, Kernel Method for pattern Analysis,
New York: Cambridge Univ. Press, 2004.
[19] D. A. Ross, J. Lim, R. S. Lin, and M-H, Yang , "Incremental learning for
robust visual tracking," International Journal of Computer Vision, vol.
77, no. 1-3, pp. 125-141, 2008.
[20] M. Pavlou, and N. M. Allinson, "An unsupervised multiresolution
face-kernel recognition model," The Irish Machine Vision and Image
Processing Conference, Aug, 2005.
[1] B. Scholkopf, A. Smola, and K. R. Muller, "Nonlinear component
analysis as a kernel eigenvalue problem," Neural Computation, vol. 10,
no. 5, pp. 1299-1319, 1998.
[2] K. R. Muller, S. Mika, G. Ratsch et al., "An introduction to kernel-based
learning algorithms," IEEE Trans. Neural Networks, vol. 12, no. 2, pp.
181-201, 2001.
[3] J. Yang, Z. Jin, J. Y. Yang, D. Zhang, and A. F. Frangi , "Essence of
kernel Fisher discriminant: KPCA plus LDA," Pattern Recognition, vol.
37, no. 10, pp. 2097-2100, 2004.
[4] H. Sahbi, "Kernel PCA for similarity invariant shape recognition,"
Neurocomputing, vol. 70, pp. 3034-3045, 2007.
[5] K. I. Kim, K. Jung, and H. J. Kim, "Face recognition using kernel
principal component analysis," IEEE Signal Processing Letters, vol. 9,
no. 2, pp. 40-42, 2002.
[6] X. L. Yu, X. G. Wang, and B. Y. Liu, "Supervised kernel neighborhood
preserving projections for radar target recognition," Signal Processing,
vol. 88, no. 9, pp. 2335-2339, 2008.
[7] G. Blanchard, O. Bousquet, and L. Zwald, "Statistical properties of kernel
principal component analysis," Machine Learning, vol. 66, no. 2-3, pp.
259-294, 2007.
[8] X. Liu, U. Kruger, T. Littler, L. Xie, S.-Q. Wang, "Moving window kernel
PCA for adaptive monitoring of nonlinear processes," Chemometrics and
Intelligent Laboratory Systems, vol. 96, no. 2, pp. 132-143, 2009.
[9] W.-J. Ma, H. Chen, and H.-Y. Tian, "Image registration based on
piecewise linear group parameters," Journal of Computer Applications,
pp. 976-8, 2007.
[10] K. I. Kim, M. O. Franz, and B. Scholkopf, "Iterative kernel principal
component analysis for image modeling," IEEE Trans.Pattern Analysis
and Machine Intelligence, vol. 27, no. 9, pp. 1351-1366, 2005.
[11] M. Girolami, "Mercer kernel-based clustering in feature space," IEEE
Tran. Neural Networks, vol. 13, no. 3, pp. 780-784, 2002.
[12] S. Gunter, N. N. Schraudolph, and S. V. N. Vishwanathan, "Fast iterative
kernel principal component analysis," Journal of Machine Learning
Research, vol. 8, pp. 1893-1918, 2007.
[13] T.-J. Chin, and D. Suter, "Incremental kernel principal component
analysis," IEEE Trans. Image Processing, vol. 16, no. 6, pp. 1662-74,
2007.
[14] C. Tat-jun, and D. Suter, "Incremental Kernel PCA for Efficient
Non-linear Feature Extraction," British Machine Vision Conference,
Edinburgh, 4-7 September 2006, (III:939).
[15] V. Franc, and V. Hlavac, "Greedy algorithm for a training set reduction in
the kernel methods," Computer Analysis of Images and Patterns,
Proceedings, vol. 2756, pp. 426-433, 2003.
[16] V. Franc, "Optimization Algorithms for Kernel Methods," Department of
Cybernetics, Faculty of Electrical Engineering, Czech Technical
University, Prague, 2005.
[17] K. B. Yu, "Recuresive updating the eigenvalue deccomposition of a
covariance-matrix," IEEE Trans. Signal Processing, vol. 39, no. 5, pp.
1136-1145, 1991.
[18] N. Critianini, and J. Shawe-Taylor, Kernel Method for pattern Analysis,
New York: Cambridge Univ. Press, 2004.
[19] D. A. Ross, J. Lim, R. S. Lin, and M-H, Yang , "Incremental learning for
robust visual tracking," International Journal of Computer Vision, vol.
77, no. 1-3, pp. 125-141, 2008.
[20] M. Pavlou, and N. M. Allinson, "An unsupervised multiresolution
face-kernel recognition model," The Irish Machine Vision and Image
Processing Conference, Aug, 2005.
@article{"International Journal of Information, Control and Computer Sciences:54251", author = "Mingtao Ding and Zheng Tian and Haixia Xu", title = "Adaptive Kernel Principal Analysis for Online Feature Extraction", abstract = "The batch nature limits the standard kernel principal component analysis (KPCA) methods in numerous applications, especially for dynamic or large-scale data. In this paper, an efficient adaptive approach is presented for online extraction of the kernel principal components (KPC). The contribution of this paper may be divided into two parts. First, kernel covariance matrix is correctly updated to adapt to the changing characteristics of data. Second, KPC are recursively formulated to overcome the batch nature of standard KPCA.This formulation is derived from the recursive eigen-decomposition of kernel covariance matrix and indicates the KPC variation caused by the new data. The proposed method not only alleviates sub-optimality of the KPCA method for non-stationary data, but also maintains constant update speed and memory usage as the data-size increases. Experiments for simulation data and real applications demonstrate that our approach yields improvements in terms of both computational speed and approximation accuracy.
", keywords = "adaptive method, kernel principal component analysis, online extraction, recursive algorithm", volume = "3", number = "11", pages = "2588-6", }
