On a theory of learning with similarity functions

ABSTRACT

Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly very high dimensional space, and describes a kernel function as being good for a given learning problem if data is separable by a large margin in that implicit space. However, while quite elegant, this theory does not directly correspond to one's intuition of a good kernel as a good similarity function. Furthermore, it may be difficult for a domain expert to use the theory to help design an appropriate kernel for the learning task at hand since the implicit mapping may not be easy to calculate. Finally, the requirement of positive semi-definiteness may rule out the most natural pairwise similarity functions for the given problem domain.In this work we develop an alternative, more general theory of learning with similarity functions (i.e., sufficient conditions for a similarity function to allow one to learn well) that does not require reference to implicit spaces, and does not require the function to be positive semi-definite (or even symmetric). Our results also generalize the standard theory in the sense that any good kernel function under the usual definition can be shown to also be a good similarity function under our definition (though with some loss in the parameters). In this way, we provide the first steps towards a theory of kernels that describes the effectiveness of a given kernel function in terms of natural similarity-based properties.

REFERENCES

• 1: Martin M. Anthony , Peter Bartlett, Learning in Neural Networks: Theoretical Foundations, Cambridge University Press, New York, NY, 1999
• 2: Balcan, M.-F., Blum, A., & Vempala, S. (2004). On kernels, margins and low-dimensional mappings. International Conference on Algorithmic Learning Theory.
• 3: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 4: Cristianini, N., Shawe-Taylor, J., Elisseeff, A., & Kandola, J. (2001). On kernel target alignment. Advances in Neural Information Processing Systems.
• 5: Yoav Freund , Robert E. Schapire, Large Margin Classification Using the Perceptron Algorithm, Machine Learning, v.37 n.3, p.277-296, Dec. 1999 [doi>10.1023/A:1007662407062]
• 6: Herbrich, R. (2002). Learning kernel classifiers. MIT Press.
• 7: Thorsten Joachims, Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 8: Adam Tauman Kalai , Adam R. Klivans , Yishay Mansour , Rocco A. Servedio, Agnostically Learning Halfspaces, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.11-20, October 23-25, 2005 [doi>10.1109/SFCS.2005.13]
• 9: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 10: Nick Littlestone, From on-line to batch learning, Proceedings of the second annual workshop on Computational learning theory, p.269-284, December 1989, Santa Cruz, California, United States
• 11: Perceptrons: An Introduction to Computational Geometry, The MIT Press, 1969
• 12: Muller, K. R., Mika, S., Ratsch, G., Tsuda, K., & Scholkopf, B. (2001). An introduction to kernel-based learning algorithms. IEEE Transactions on Neural Networks, 12, 181--201.
• 13: Novikoff, A. B. J. (1962). On convergence proofs on perceptrons. Proc. Symposium on the Mathematical Theory of Automata.
• 14: Scholkopf, B., Tsuda, K., & Vert, J.-P. (2004). Kernel methods in computational biology. MIT Press.
• 15: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 16: Shawe-Taylor, J., Bartlett, P. L., Williamson, R. C., & Anthony, M. (1998). Structural risk minimization over data-dependent hierarchies. IEEE Trans. Information Theory, 44, 1926--1940.
• 17: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 18: Alexander J. Smola , Peter J. Bartlett, Advances in Large Margin Classifiers, MIT Press, Cambridge, MA, 2000
• 19: Vapnik, V. N. (1998). Statistical learning theory. Wiley & Sons.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Neural nets

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms