zbMATH — the first resource for mathematics

An efficient kernel matrix evaluation measure. (English) Zbl 1154.68469
Summary: We study the problem of evaluating the goodness of a kernel matrix for a classification task. As kernel matrix evaluation is usually used in other expensive procedures like feature and model selections, the goodness measure must be calculated efficiently. Most previous approaches are not efficient except for Kernel Target Alignment (KTA) that can be calculated in \(O(n^{2})\) time complexity. Although KTA is widely used, we show that it has some serious drawbacks. We propose an efficient surrogate measure to evaluate the goodness of a kernel matrix based on the data distributions of classes in the feature space. The measure not only overcomes the limitations of KTA but also possesses other properties like invariance, efficiency and an error bound guarantee. Comparative experiments show that the measure is a good indication of the goodness of a kernel matrix.

68T05 Learning and adaptive systems in artificial intelligence
68T10 Pattern recognition, speech recognition
Full Text: DOI
[1] Schölkopf, B.; Smola, A.J., Learning with kernels, (2002), MIT Press Cambridge, MA
[2] Shawe-Taylor, J.; Cristianini, N., Kernel methods for pattern analysis, (2004), Cambridge University Press New York, NY, USA
[3] Vapnik, N.V., The nature of statistical learning theory, (2000), Springer New York, NY · Zbl 0934.62009
[4] Schölkopf, B.; Smola, A.J.; Müller, K.-R., Kernel principal component analysis, (), 327-352
[5] Wahba, G., Spline models for observational data, () · Zbl 0813.62001
[6] Fine, S.; Scheinberg, K., Efficient SVM training using low-rank kernel representations, J. Mach. learn. res., 2, 243-264, (2002) · Zbl 1037.68112
[7] Ong, C.S.; Smola, A.J.; Williamson, R.C., Learning the kernel with hyperkernels, J. Mach. learn. res., 6, 1043-1071, (2005) · Zbl 1222.68277
[8] Cristianini, N.; Shawe-Taylor, J.; Elisseeff, A.; Kandola, J., On kernel-target alignment, ()
[9] Lanckriet, G.R.G.; Cristianini, N.; Bartlett, P.; Ghaoui, L.E.; Jordan, M.I., Learning the kernel matrix with semidefinite programming, J. Mach. learn. res., 5, 27-72, (2004) · Zbl 1222.68241
[10] Neumann, J.; Schnorr, C.; Steidl, G., Combined SVM-based feature selection and classification, Mach. learn., 61, 1-3, 129-150, (2005) · Zbl 1137.90643
[11] Wu, M.; Farquhar, J., A subspace kernel for nonlinear feature extraction, (), 1125-1130
[12] Kwok, J.T.; Tsang, I.W., Learning with idealized kernels, (), 400-407
[13] Crammer, K.; Keshet, J.; Singer, Y., Kernel design using boosting, (), 537-544
[14] Kandola, J.; Cristianini, N.; Shawe-Taylor, J., Learning semantic similarity, ()
[15] Kandola, J.; Shawe-Taylor, J., Refining kernels for regression and uneven classification problems, ()
[16] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge University Press New York, NY, USA · Zbl 1058.90049
[17] Meila, M., Data centering in feature space, ()
[18] Gradshteyn, I.S.; Ryzhik, I.M., Table of integrals, series, and products, (2000), Academic Press San Diego, CA · Zbl 0981.65001
[19] Gartner, T.; Lloyd, J.W.; Flach, P.A., Kernels and distances for structured data, Mach. learn. J., 57, 3, 205-232, (2004) · Zbl 1079.68086
[20] Jebara, T.; Kondor, R.; Howard, A., Probability product kernels, J. Mach. learn. res., 5, 819-844, (2004) · Zbl 1222.68226
[21] Feller, W., An introduction to probability theory and its applications, vol. 2, (1971), Wiley New York · Zbl 0219.60003
[22] Japkowicz, N.; Stephen, S., The class imbalance problem: a systematic study, Intell. data anal., 6, 5, 429-449, (2002) · Zbl 1085.68628
[23] Lanckriet, G.R.G.; Ghaoui, L.E.; Bhattacharyya, C.; Jordan, M.I., A robust minimax approach to classification, J. Mach. learn. res., 3, 555-582, (2002)
[24] L. Wang, K.L. Chan, Learning kernel parameters by using class separability measure, in: Advances in Neural Information Processing Systems, Sixth workshop on Kernel Machines, Canada, 2002.
[25] Fukunaga, K., Introduction to statistical pattern recognition, (1990), Academic Press New York · Zbl 0711.62052
[26] Globerson, A.; Roweis, S., Metric learning by collapsing classes, (), 451-458
[27] Mika, S.; Rätsch, G.; Weston, J.; Schölkopf, B.; Müller, K.-R., Fisher discriminant analysis with kernels, (), 41-48
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.