Elamur Research⌕
☰
home / papers / 1995 / Support-Vector Networks

Support-Vector Networks

Paper · 1995 · Corinna Cortes and Vladimir Vapnik

Summary

The paper tackles two-class pattern recognition. It presents the support-vector network, a learning machine that sends inputs through a fixed non-linear mapping into a very high-dimensional feature space and fits a linear decision surface there. Earlier work on optimal (maximum-margin) hyperplanes required training data that could be separated with no errors. This paper removes that restriction with a "soft margin" formulation that tolerates training mistakes through slack variables and still reduces to a quadratic programming problem. The resulting classifier depends only on a small subset of training points, the support vectors. Following Boser, Guyon & Vapnik (1992), the comparison between an input and the support vectors is made directly in input space through a kernel-like function, so the huge feature space never has to be built explicitly. The authors test polynomial decision surfaces up to degree 7 on 256-dimensional inputs in an optical character recognition benchmark and compare them with linear classifiers, k-nearest neighbours and neural networks. The work matters because it gives a principled, convex alternative to neural networks with strong generalization.

Key points

  • The expected test error of a separating optimal hyperplane is bounded by the expected number of support vectors divided by the training set size. The bound does not explicitly depend on feature-space dimension.
  • On real data this ratio can fall to about 0.03, and the optimal hyperplane still generalizes in a feature space of roughly a billion dimensions.
  • The soft-margin extension penalizes slack with F(u)=u^k. The reported experiments use k=2. With k=1, the dual becomes a quadratic program with box constraints 0 ≤ α ≤ C.
  • The solution weight vector is a linear combination of support vectors only, so the classifier can be viewed as a two-layer network.
  • The experiments use polynomial kernels up to degree 7 on 256-dimensional OCR inputs. The paper also references NIST Special Database 3.

Interesting ideas

  • I1. Kernel trick (swap the order of operations): compare vectors in input space first, then apply the non-linearity. This lets you get very rich feature spaces without ever computing them, and it transfers to any similarity-based model.
  • I2. Support-vector count as a generalization proxy: the fraction of training points that end up as support vectors gives a cheap, dimension-free estimate of test error. It could be useful for model selection when held-out data is scarce.
  • I3. Soft margin via slack variables: allowing controlled constraint violation with a penalty weight C turns a brittle "must separate" objective into a robust convex problem. The same pattern works for noisy labels in other tasks.
  • I4. Sparse solution representation: because the model is stored as a few support vectors with multipliers, its cost depends on how many points matter, not on the feature dimension. This is attractive for compact deployment.
  • I5. Choice of slack penalty: the authors treat the error penalty F(u) as a design knob, covering linear, squared and least-squares variants. Varying the loss shape like this is a useful lens when tuning any margin-based classifier.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢AT&TBedminster · United States40 works · 75,466 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

💡 Concepts 1Key ideas and methods explained on our concept pages.Machine learning · 51 works

Cite

Cite as Corinna Cortes and Vladimir Vapnik. 1995. Support-Vector Networks. Machine Learning.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1007/bf00994018

@inproceedings{cortes1995support,
  title = {{Support-Vector Networks}},
  author = {Corinna Cortes and Vladimir Vapnik},
  booktitle = {Machine Learning},
  year = {1995},
  doi = {10.1007/bf00994018},
  url = {https://doi.org/10.1007/bf00994018}
}

References

15 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aizerman, M., Braverman, E., & Rozonoer, L. (1964). Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821-837. find
  2. Anderson, T.W., & Bahadur, R.R. (1966). Classification into two multivariate normal distributions with different covariance matrices. Ann. Math. Stat., 33:420–431. find
  3. Boser, B.E., Guyon, I., & Vapnik, V.N. (1992). A training algorithm for optimal margin classifiers. In Proceedings of the F(fth Annual Worlaghop of Computational Learning Theory, 5, 144-152, Pittsburgh, ACM. find
  4. Bottou, L., Cortes, C., Denker, J.S., Drucker, H., Guyon, I., Jackel, L.D., LeCun, Y., Sackinger, E., Simard, P., Vapnik, V., & Miller, U.A. (1994). Comparison of classifier methods: A case study in handwritten digit recognition. Proceedings of 12th International Conference on Pattern Recognition an… find
  5. Bromley, J., & Sackinger, E. (1991). Neural-network and k-nearest-neighbor classifiers. Technical Report 11359-910819-16TM, AT&T. find
  6. Courant, R., & Hilbert, D. (1953). Methods ofMathematical Physics, Interscience, New York. find
  7. Fisher, R.A. (1936). The use of multiple measurements in taxonomic problems. Ann. Eugenics, 7:111-132. find
  8. LeCun, Y. (1985). Une procedure d'apprentissage pour reseau a seuil assymetrique. Cognitiva 85: A la Frontiere de l'Intelligence Artificielle des Sciences de la Connaissance des Neurosciences, 599-604, Paris. find
  9. LeCun, Y., Boser, B., Denker, J.S., Henderson, D., Howard, R.E., Hubbard, W., & Jackel, L.D. (1990). Handwritten digit recognition with a back-propagation network. Advances in Neural Information Processing Systems, 2, 396-404, Morgan Kaufman. find
  10. Parker, D.B. (1985). Learning logic. Technical Report TR-47, Center for Computational Research in Economics and Management Science, Massachusetts Institute of Technology, Cambridge, MA. find
  11. Rosenblatt, F. (1962). Principles ofNeurodynamics, Spartan Books, New York. ~i ä 1 [ A r D A + I A r A ] find
  12. (67) SUPPORT-VECTORNETWORKS Rumelhart, D.E., Hinton, G.E., & Williams, R.J. (1986). Learning intemal representations by backpropagating errors. Nature, 323:533-536. find
  13. Rumelhart, D.E., Hinton, G.E., & Williams, R.J. (1987). Learning intemal representations by error propagation. In James L. McClelland & David E. Rumelhart (Eds.), Parallel Distributed Processing, 1, 318-362, MIT Press. find
  14. Vapnik, V.N. (1982). Estimation ofDependences Based on Empirical Data, Addendum 1, New York: Springer-Verlag. find
  15. Received May 15, 1993 Accepted February 20, 1995 Final Manuscript March 8, 1995 find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/cortes-1995-support-vector-networks/