On the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution
Lecture notes in computer sciencePublished 1 January 2002
Jürgen Forster, Hans Ulrich Simon
Citations6
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The embeddability of a given concept class into a class of Euclidean half spaces of low dimension, or of arbitrarily large dimension but realizing a large margin, is studied.
Abstract
This paper discusses theoretical limitations of classification systems that are based on feature maps and use a separating hyper-plane in the feature space. In particular, we study the embeddability of a given concept class into a class of Euclidean half spaces of low dimension, or of arbitrarily large dimension but realizing a large margin. New bounds on the smallest possible dimension or on the largest possible margin are presented. In addition, we present new results on the rigidity of matrices and briefly mention applications in complexity and learning theory.
Keywords
Computer Science
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Matrix Analysis
22,234 Citations1985Roger A. Horn, Charles R. Johnson
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
Cambridge University Press eBooksMatrix Analysis
10,056 Citations1985Roger A. Horn, Charles R. Johnson
Cambridge University Press eBooksTopics in Matrix Analysis
9,501 Citations1991Roger A. Horn, Charles R. Johnson
ePrints Soton (University of Southampton)An Introduction to Support Vector Machines
4,120 Citations2000Nello Cristianini, John Shawe‐Taylor
Machine LearningAn algorithmic theory of learning: Robust concepts and random projection
334 Citations2006Rosa I. Arriaga, Santosh Vempala
This work provides a novel algorithmic analysis via a model of robust concept learning (closely related to “margin classifiers”), and shows that a relatively small number of examples are sufficient to learn rich concept classes.
Journal of Computer and System SciencesA linear lower bound on the unbounded error probabilistic communication complexity
186 Citations2002Jürgen Forster
An algorithmic theory of learning: robust concepts and random projection
88 Citations2003Rosa I. Arriaga, S. Vempala
Lecture notes in computer scienceLimitations of Learning via Embeddings in Euclidean Half-Spaces
88 Citations2001Shai Ben-David, Nadav Eiron +1 more
The 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.
Lecture notes in computer scienceRelations Between Communication Complexity, Linear Arrangements, and Computational Complexity
84 Citations2001Jürgen Forster, Matthias Krause +4 more
This paper presents a concrete family of distributed Boolean functions where the generalized bound leads to a linear lower bound on the probabilistic communication complexity (and thus to an exponential lower Bound on the number of Euclidean dimensions needed for a successful half space representation), whereas the old bound fails.
Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity
38 Citations2002Satyanarayana V. Lokam
It is shown that the lower bound on a variant of rigidity implies lower bounds on size-depth tradeoffs for arithmetic circuits with bounded coefficients computing linear transformations, and this results complement and strengthen a result of Razborov.
Mathematical NotesImproved lower bounds on the rigidity of Hadamard matrices
38 Citations1998Борис Сергеевич Кашин, Alexander Razborov
It is shown that at least Ω(n2/r) entries must be changed in an arbitrary (generalized) Hadamard matrix in order to reduce its rank belowr.
Lecture notes in computer scienceEstimating the Optimal Margins of Embeddings in Euclidean Half Spaces
18 Citations2001Jürgen Forster, Niels Schmitt +1 more
A linear lower bound on the unbounded error probabilistic communication complexity
13 Citations2002Jüurgen Forster
This work proves a general lower bound on the complexity of unbounded error probabilistic communication protocols for the functions defined by Hadamard matrices and gives an upperbound on the margin of any embedding of a concept class in half spaces.