On the smallest possible dimension ...

On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes

Authors: Jürgen Forster and Hans Ulrich Simon
Source: Theoretical Computer Science Vol. 350, Issue 1, January 2006, pp. 40-48
(Special Issue Algorithmic Learning Theory (ALT 2002)).
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: Linear arrangements; Dimension bounds; Margin bounds; Matrix rigidity