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 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.
Cite
Text
Forster and Simon. "On the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution." International Conference on Algorithmic Learning Theory, 2002. doi:10.1007/3-540-36169-3_12Markdown
[Forster and Simon. "On the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution." International Conference on Algorithmic Learning Theory, 2002.](https://mlanthology.org/alt/2002/forster2002alt-smallest/) doi:10.1007/3-540-36169-3_12BibTeX
@inproceedings{forster2002alt-smallest,
title = {{On the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution}},
author = {Forster, Jürgen and Simon, Hans Ulrich},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2002},
pages = {128-138},
doi = {10.1007/3-540-36169-3_12},
url = {https://mlanthology.org/alt/2002/forster2002alt-smallest/}
}