Title | ||
---|---|---|
On the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution |
Abstract | ||
---|---|---|
This paper discusses theoretical limitations of classification systems that are based on feature maps and use a separating hyperplane 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. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/3-540-36169-3_12 | ALT |
Keywords | Field | DocType |
concept class,smallest possible dimension,uniform distribution,low dimension,largest possible margin,concept classes,large margin,new bound,feature space,possible dimension,new result,large dimension,feature map,classification system,learning theory | Discrete mathematics,Effective dimension,Feature vector,Combinatorics,Inductive dimension,Minkowski–Bouligand dimension,Concept class,Euclidean space,Hyperplane,Mathematics,Arbitrarily large | Conference |
Volume | ISSN | ISBN |
2533 | 0302-9743 | 3-540-00170-0 |
Citations | PageRank | References |
3 | 1.64 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jürgen Forster | 1 | 197 | 24.09 |
Hans-Ulrich Simon | 2 | 567 | 104.52 |