MARK: a boosting algorithm for heterogeneous kernel models

ABSTRACT

Support Vector Machines and other kernel methods have proven to be very effective for nonlinear inference. Practical issues are how to select the type of kernel including any parameters and how to deal with the computational issues caused by the fact that the kernel matrix grows quadratically with the data. Inspired by ensemble and boosting methods like MART, we propose the Multiple Additive Regression Kernels (MARK) algorithm to address these issues. MARK considers a large (potentially infinite) library of kernel matrices formed by different kernel functions and parameters. Using gradient boosting/column generation, MARK constructs columns of the heterogeneous kernel matrix (the base hypotheses) on the fly and then adds them into the kernel ensemble. Regularization methods such as used in SVM, kernel ridge regression, and MART, are used to prevent overfitting. We investigate how MARK is applied to heterogeneous kernel ridge regression. The resulting algorithm is simple to implement and efficient. Kernel parameter selection is handled within MARK. Sampling and "weak" kernels are used to further enhance the computational efficiency of the resulting additive algorithm. The user can incorporate and potentially extract domain knowledge by restricting the kernel library to interpretable kernels. MARK compares very favorably with SVM and kernel ridge regression on several benchmark datasets.

REFERENCES

• 1: C. L. Blake and C. J. Merz. UCI repository of machine learning databases, 1998. http://www.ics.uei.edu/~mlearn/MLRepository.html.
• 2: Olivier Chapelle , Vladimir Vapnik , Olivier Bousquet , Sayan Mukherjee, Choosing Multiple Parameters for Support Vector Machines, Machine Learning, v.46 n.1-3, p.131-159, 2002 [doi>10.1023/A:1012450327387]
• 3: R. Collobert and S. Bengio. Support vector machines for large-scale regression problems. IDIAP-RR-00-17, 2000.
• 4: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 5: Nigel Duffy , David P. Helmbold, Leveraging for Regression, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.208-219, June 28-July 01, 2000
• 6: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 7: J. Friedman. Greedy function approximation. Technical report, Department of Statistics, Stanford University, February 1999.
• 8: Glenn Fung , Olvi L. Mangasarian, Proximal support vector machine classifiers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.77-86, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502527]
• 9: T. Hastie, R. Tibshairani, and J. Friedman. The elements of statistical Learning. Springer, 2001.
• 10: T. Hastie and R. Tibshirani. Generalized additive models. Statistical Science, 1:297--318, 1986.
• 11: C. F. Ipsen and C. D. Meyer. The idea behind krylov methods. Amer. Math. Monthly, 105(10):889--99, 1998.
• 12: L. Mason, P. Bartlett, J. Baxter, and M. Frean. Functional gradient techniques for combining hypotheses. In B. Schölkopf, A. Smola, P. Bartlett, and D. S. ans, editors, Advances in Large Margin Classifiers. MIT Press, 2000.
• 13: Martin Fodslette Møller, A scaled conjugate gradient algorithm for fast supervised learning, Neural Networks, v.6 n.4, p.525-533, 1993 [doi>10.1016/S0893-6080(05)80056-5]
• 14: M. Momma and K. P. Bennett. A pattern search method for model selection of support vector regression. In Proceedings of the Second SIAM International Conference on Data Mining. SIAM, 2002. to appear.
• 15: G. Rätsch. Robust Boosting via Convex Optimization: Theory and Applications. PhD thesis, University of Potsdam, Department of Computer Science, 2002.
• 16: Gunnar Rätsch , Ayhan Demiriz , Kristin P. Bennett, Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces, Machine Learning, v.48 n.1-3, p.189-218, 2002 [doi>10.1023/A:1013907905629]
• 17: Craig Saunders , Alexander Gammerman , Volodya Vovk, Ridge Regression Learning Algorithm in Dual Variables, Proceedings of the Fifteenth International Conference on Machine Learning, p.515-521, July 24-27, 1998
• 18: Alexander J. Smola , Peter J. Bartlett, Advances in Large Margin Classifiers, MIT Press, Cambridge, MA, 2000
• 19: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 20: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Measurement, Performance