A Close Look to Margin Complexity and Related Parameters

Michael Kallweit, Hans Ulrich Simon
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:437-456, 2011.

Abstract

Concept classes can canonically be represented by sign-matrices, i.e., by matrices with entries $1$ and $-1$. The question whether a sign-matrix (concept class) $A$ can be learned by a machine that performs large margin classification is closely related to the “margin complexity” associated with $A$. We consider several variants of margin complexity, reveal how they are related to each other, and we reveal how they are related to other notions of learning-theoretic relevance like SQ-dimension, CSQ-dimension, and the Forster bound.

Cite this Paper

BibTeX
@InProceedings{pmlr-v19-kallweit11a, title = {A Close Look to Margin Complexity and Related Parameters}, author = {Kallweit, Michael and Simon, Hans Ulrich}, booktitle = {Proceedings of the 24th Annual Conference on Learning Theory}, pages = {437--456}, year = {2011}, editor = {Kakade, Sham M. and von Luxburg, Ulrike}, volume = {19}, series = {Proceedings of Machine Learning Research}, address = {Budapest, Hungary}, month = {09--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v19/kallweit11a/kallweit11a.pdf}, url = {https://proceedings.mlr.press/v19/kallweit11a.html}, abstract = {Concept classes can canonically be represented by sign-matrices, i.e., by matrices with entries $1$ and $-1$. The question whether a sign-matrix (concept class) $A$ can be learned by a machine that performs large margin classification is closely related to the “margin complexity” associated with $A$. We consider several variants of margin complexity, reveal how they are related to each other, and we reveal how they are related to other notions of learning-theoretic relevance like SQ-dimension, CSQ-dimension, and the Forster bound.} }
Endnote
%0 Conference Paper %T A Close Look to Margin Complexity and Related Parameters %A Michael Kallweit %A Hans Ulrich Simon %B Proceedings of the 24th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2011 %E Sham M. Kakade %E Ulrike von Luxburg %F pmlr-v19-kallweit11a %I PMLR %P 437--456 %U https://proceedings.mlr.press/v19/kallweit11a.html %V 19 %X Concept classes can canonically be represented by sign-matrices, i.e., by matrices with entries $1$ and $-1$. The question whether a sign-matrix (concept class) $A$ can be learned by a machine that performs large margin classification is closely related to the “margin complexity” associated with $A$. We consider several variants of margin complexity, reveal how they are related to each other, and we reveal how they are related to other notions of learning-theoretic relevance like SQ-dimension, CSQ-dimension, and the Forster bound.
RIS
TY - CPAPER TI - A Close Look to Margin Complexity and Related Parameters AU - Michael Kallweit AU - Hans Ulrich Simon BT - Proceedings of the 24th Annual Conference on Learning Theory DA - 2011/12/21 ED - Sham M. Kakade ED - Ulrike von Luxburg ID - pmlr-v19-kallweit11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 19 SP - 437 EP - 456 L1 - http://proceedings.mlr.press/v19/kallweit11a/kallweit11a.pdf UR - https://proceedings.mlr.press/v19/kallweit11a.html AB - Concept classes can canonically be represented by sign-matrices, i.e., by matrices with entries $1$ and $-1$. The question whether a sign-matrix (concept class) $A$ can be learned by a machine that performs large margin classification is closely related to the “margin complexity” associated with $A$. We consider several variants of margin complexity, reveal how they are related to each other, and we reveal how they are related to other notions of learning-theoretic relevance like SQ-dimension, CSQ-dimension, and the Forster bound. ER -
APA
Kallweit, M. & Simon, H.U.. (2011). A Close Look to Margin Complexity and Related Parameters. Proceedings of the 24th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 19:437-456 Available from https://proceedings.mlr.press/v19/kallweit11a.html.

Related Material