Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The notion of embedding a class of dichotomies in a class of linear half spaces is central to the support vector machines paradigm. We examine the question of determining the minimal Euclidean dimension and the maximal margin that can be obtained when the embedded class has a finite VC dimension. We show that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in low-dimensional half spaces. (In fact, we show that the Euclidean dimension must be almost as high as the size of the instance space.) We strengthen this result even further by showing that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in half spaces (of arbitrarily high Euclidean dimension) with a large margin. (In fact, the margin cannot be substantially larger than the margin achieved by the trivial embedding.) Furthermore, these bounds are robust in the sense that allowing each image half space to err on a small fraction of the instances does not imply a significant weakening of these dimension and margin bounds. Our results indicate that any universal learning machine, which transforms data into the Euclidean space and then applies linear (or large margin) classification, cannot enjoy any meaningful generalization guarantees that are based on either VC dimension or margins considerations. This failure of generalization bounds applies even to classes for which "straight forward" empirical risk minimization does enjoy meaningful generalization guarantees.

REFERENCES

• 1: N. Alon, P. Frankl, and V. Rödl. Geometrical realization of set systems and probabilistic communication complexity. In Proceedings of the 26th Symposium on Foundations of Computer Science, pages 277-280. 1985.
• 2: Rosa I. Arriaga , Santosh Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.616, October 17-18, 1999
• 3: Shai Ben-David. A priori generalization bounds for kernel based learning: Can sparsity save the day? Technical Report, Cornell University, 2001.
• 4: Béla Bollobás. Extremal Graph Theory. Academic Press, 1978.
• 5: Jurgen Forster, A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity, Proceedings of the 16th Annual Conference on Computational Complexity, p.100, June 18-21, 2001
• 6: Jürgen Forster , Niels Schmitt , Hans-Ulrich Simon, Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.402-415, July 16-19, 2001
• 7: 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]
• 8: Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
• 9: Llew Mason , Peter L. Bartlett , Jonathan Baxter, Improved Generalization Through Explicit Optimization of Margins, Machine Learning, v.38 n.3, p.243-255, March 2000 [doi>10.1023/A:1007697429651]
• 10: Marvin L. Minsky and Seymour A. Papert. Perceptrons. The MIT Press, Cambrigde MA, third edition, 1988.
• 11: A. B. J. Novikoff. On convergence proofs for perceptrons. In Proceedings of the Symposium of Mathematical Theory of Automata, pages 615-622, 1962.
• 12: Ramamohan Paturi , Janos Simon, Probabilistic communication complexity, Journal of Computer and System Sciences, v.33 n.1, p.106-123, Aug. 1986 [doi>10.1016/0022-0000(86)90046-2]
• 13: F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psych. Rev., 65:386-407, 1958.
• 14: F. Rosenblatt. Principles and Neurodynamics: Perceptrons and the Theory of Brain Mechanisms . Spartan Books, Washington, D.C., 1962.
• 15: Vladimir Vapnik. Statistical Learning Theory. Wiley Series on Adaptive and Learning Systems for Signal Processing, Communications, and Control. John Wiley & Sons, 1998.
• 16: K. Zarankiewicz. Problem P 101. Colloq. Math., 2:301, 1951.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Geometric
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Measurement, Theory

Keywords:
concept learning, embeddings in half spaces, large margin classification