Ruhr-Universität Bochum zum Inhalt Startseite der RUB pix
Startseite UniStartseite
Überblick UniÜberblick
A-Z UniA-Z
Suche UniSuche
Kontakt UniKontakt

Das Siegel
Naturwissenschaften Ingenieurwissenschaften Geisteswissenschaften Medizinische Einrichtungen Zentrale Einrichtungen
pix Lehrstuhl Mathematik & Informatik
Dimension and Margin Bounds ...
Unser Angebot: Mitarbeiter | Forschung | Lehre   
Startseite » Mitarbeiter » Thorsten Doliwa » Dimension and Margin Bounds ...

pix pix Dimension and Margin Bounds ...
Abstract.  A kernel over the Boolean domain is said to be reflection-invariant, if its value does not change when we flip the same bit in both arguments. (Many popular kernels have this property.) We study the geometric margins that can be achieved when we represent a specific Boolean function $f$ by a classifier that employs a reflection-invariant kernel. It turns out $\|\hat{f}\|_\infty$ is an upper bound on the average margin. Furthermore, $\|\hat{f}\|_\infty^{-1}$ is a lower bound on the smallest dimension of a feature space associated with a reflection-invariant kernel that allows for a correct representation of $f$. This is, to the best of our knowledge, the first paper that exhibits margin and dimension bounds for {\em specific functions} (as opposed to {\em function families}). Several generalizations are considered as well. The main mathematical results are presented in a setting with arbitrary finite domains and a quite general notion of invariance.

Zum Seitenanfang  Seitenanfang | Diese Seite drucken
Letzte Änderung: 15.10.2008 | Ansprechpartner: Webmaster