Lehrstuhl Mathematik & InformatikDimension and Margin Bounds for Reflection-invariant Kernels
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.