\NeedsTeXFormat{LaTeX2e} \documentclass[twoside,11pt]{article} \usepackage{jmlr2e} \usepackage{natbib} \usepackage{amsmath} \usepackage{amssymb} \usepackage{theorem} \usepackage{url} \sloppy \DeclareSymbolFontAlphabet{\Bbb}{AMSb} \parskip0em \newtheorem{example}{Example} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{axiom}[theorem]{Axiom} \newcommand{\eins}{\boldsymbol{1}} \newcommand{\T}{\Bbb{T}} % Sonderzeichen fr \newcommand{\C}{\Bbb{C}} % Sonderzeichen fr \newcommand{\N}{\Bbb{N}} % Sonderzeichen fr \newcommand{\R}{\Bbb{R}} % Sonderzeichen fr \newcommand{\Rp}{\Bbb{R}^+} % Sonderzeichen fr \newcommand{\Rn}{\Bbb{R}^n} % Sonderzeichen fr \newcommand{\K}{\Bbb{K}} % Sonderzeichen fr \newcommand{\Z}{\Bbb{Z}} % Sonderzeichen fr \newcommand{\Q}{\Bbb{Q}} % Sonderzeichen fr \newcommand{\E}{\Bbb{E}} % Sonderzeichen fr \newcommand{\opa}{\mbox{\rm Pr}^*} \newcommand{\So}[1]{{\sf SO(\mbox{$#1$})}} \newcommand{\On}[1]{{\sf ON(\mbox{$#1$})}} \newcommand{\Gl}[1]{{\sf GL(\mbox{$#1$})}} \newcommand{\ca}[1]{\mbox{${\mathcal #1}$}} \newcommand{\rem}[1]{} \newcommand{\iso}{=\hspace{-0.8em}^{^1}\hspace{0.4em}} \newcommand{\isoin}{\hookrightarrow\hspace{-1em}^{^1}\hspace{0.6em}} \newenvironment{abstrakt}{\small}{} \newenvironment{beispiel}{\small\it}{} \def \B {{\cal B}} % Borelsche s-Algebra \def \Om { \Omega } \def \om { \omega } \def \lb { \lambda } \def \a { \alpha } \def \b { \beta } \def \g { \gamma } \def \e { \varepsilon } \def \r { \rho } \def \s { \sigma } \def \vs { \varsigma } \def \t { \tau } \def \et { \tilde{\eta}} \def \d { \delta } \def \D { \Delta } \def \p { \varphi } \def \x { \xi } \def \P { \Phi } \newcommand{\ld}{\log_2} \newcommand{\loq}{\log_m} \newcommand{\ed}{\exp_2} \newcommand{\edot}{\!\cdot\!} \newcommand{\dsp}{S\edot P} \newcommand{\jin}{j\in\{0,+\}} \newcommand{\iin}{i\in\{-1,1\}} \newcommand{\Sim}{\ \sim \ } \newcommand{\Preceq}{\ \preceq \ } \newcommand{\Succeq}{\ \succeq \ } \newcommand{\Leq}{\ \leq \ } \newcommand{\Geq}{\ \geq \ } \newcommand{\Eq}{\ = \ } \newcommand{\Defi}{\ := \ } \newcommand{\Lfloor}{\left\lfloor} \newcommand{\Rfloor}{\right\rfloor} \newcommand{\Bew}{\noindent{\bf Proof\ }} \newcommand{\Bewo}[1]{\noindent{\bf Proof #1\ }} \newcommand{\eBew}{$\hfill\BlackBox$\\[2mm]} \newcommand{\sn}{\s_{n-1}} \newcommand{\Int}{\int\limits} \newcommand{\Sum}{\sum\limits} \DeclareMathOperator{\co}{co} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\diam}{diam} \newcommand{\modc}[2]{\mbox{$\omega (#1,#2)$}} \newcommand{\im}[1]{\mbox{${\rm {im}} \ #1$}} \newcommand{\Ker}[1]{\mbox{${\mathfrak {Ker}} \ #1$}} \newcommand{\rank}[1]{{\rm rank} \ #1} %\newcommand{\rank}[1]{\mbox{\rm rank $#1$}} \newcommand{\codim}[1]{\mbox{\rm codim $#1$}} \newcommand{\vol}{\mbox{\rm vol}} \DeclareMathOperator{\spann}{span} \newcommand{\card}{\mbox{\rm card }} \newcommand{\dn}[2]{\mbox{$d_{\| .\|}(#1,#2)$}} \newcommand{\ol}[1]{\overline{#1}} \DeclareMathOperator{\vcdim}{VC-dim} \DeclareMathOperator{\pot}{pot} \newcommand{\id}{\mbox{${\rm {id}}$}} \newcommand{\posku}[2]{\mbox{$\ca W_{#1}(#2)$}} \newcommand{\einku}[2]{\mbox{$\ca W_{#1}^1(#2)$}} \newcommand{\btens}{\bigotimes} \newcommand{\tens}{\otimes} \newcommand{\xtens}[1]{\otimes_{_{\triangle_{#1}}}} \newcommand{\afalt}{\circledast} %Normen und Rume \newcommand{\lt}[1]{\mbox{${\ell}_2 (#1)$}} \newcommand{\lto}{\mbox{${\ell}_2$}} %Der Raum Lo \newcommand{\Lo}{\mbox{${L}_o (\mu)$}} \newcommand{\Lom}[1]{\mbox{${L}_o (#1)$}} \newcommand{\Lox}[1]{\mbox{${L}_o (\mu,#1)$}} \newcommand{\Loxinf}[1]{{\sf L\mbox{$_o (\mu,#1)$}}} \newcommand{\Lof}{\mbox{${L}_o (\mu,F)$}} \newcommand{\onorm}[1]{\mbox{$\left\Vert #1 \right\Vert_{_0}$}} %Der Raum Lps \newcommand{\Lps}{\mbox{${L}_{p,\infty} (\mu)$}} \newcommand{\Lqs}{\mbox{${L}_{q,\infty} (\mu)$}} \newcommand{\Lpsm}[1]{\mbox{${L}_{p,\infty} (#1)$}} \newcommand{\Lxsm}[2]{\mbox{${L}_{#1,\infty} (#2)$}} \newcommand{\psno}[1]{\mbox{$\left\Vert #1 \right\Vert_{p,\infty}$}} \newcommand{\qsno}[1]{\mbox{$\left\Vert #1 \right\Vert_{q,\infty}$}} % Der Raum Lp \newcommand{\Lp}{\mbox{${L}_{p} (\mu)$}} \newcommand{\Lpm}[1]{\mbox{${L}_{p} (#1)$}} \newcommand{\Lx}[1]{\mbox{${L}_{#1} (\mu)$}} \newcommand{\Lxn}[1]{\mbox{${L}_{#1} (\nu)$}} \newcommand{\Lpx}[3]{\mbox{${L}_{#1} (#2,#3)$}} \newcommand{\Le}{\mbox{${L}_{1} (\mu)$}} \newcommand{\Li}{\mbox{${L}_{\infty} (\mu)$}} \newcommand{\Lpmx}[2]{\mbox{${L}_{#1} (#2)$}} \newcommand{\Lpmxge}[2]{\mbox{${L}_{#1}^{^{\geq 0}} (#2)$}} \newcommand{\Lpmxpo}[2]{\mbox{${L}_{#1}^{^{> 0}} (#2)$}} \newcommand{\wLpx}[3]{\mbox{$w^*$-$L_{#1} (#2,#3')$}} \newcommand{\wsLpx}[3]{\mbox{$w^*$-$\ca L_{#1} (#2,#3')$}} \newcommand{\wN}[3]{\mbox{$w^*$-$\ca N_{#1} (#2,#3')$}} \newcommand{\pnorm}[1]{\mbox{$\left\Vert #1 \right\Vert_{p}$}} \newcommand{\norm}[1] {\Bigl\Vert #1 \Bigr\Vert} \newcommand{\Norm}[1] {\left\Vert #1 \right\Vert} \newcommand{\snorm}[1] {\Vert #1 \Vert} \newcommand{\enorm}[1]{\mbox{$\left\Vert #1 \right\Vert_{E}$}} \newcommand{\fnorm}[1]{\mbox{$\left\Vert #1 \right\Vert_{F}$}} \newcommand{\xnorm}[3]{\mbox{$\left\Vert #1 \right\Vert_{{#2}}^{#3}$}} \newcommand{\ynorm}[2]{\mbox{$\left\Vert #1 \right\Vert_{{#2}}$}} \newcommand{\betr}[1]{\mbox{$\left\vert #1 \right\vert$}} \newcommand{\M}[4]{\mbox{$\ca M (\Lpx #1 G #3,\Lpx #2 G #4)$}} \newcommand{\einorm}[1]{\mbox{$\left\Vert #1 \right\Vert_{1}$}} \newcommand{\inorm}[1]{\mbox{$\left\Vert #1 \right\Vert_{\infty}$}} \newcommand{\isnorm}[1]{\mbox{$\bigl\Vert #1 \bigr\Vert_{\infty}$}} \newcommand{\Coo}[1]{\mbox{${C}_{oo} (#1)$ }} \newcommand{\supp}[1]{\mbox{{\rm supp} $#1$}} \newcommand{\sL}[2]{\mbox{${\cal L}(#1,#2)$ }} \newcommand{\sLp}[1]{\mbox{${\cal L}_p(\mu)$ }} \newcommand{\vwu}[1]{\norm {#1} _r} \newcommand{\vwurs}[1]{\norm {#1} _{r'}} \newcommand{\mzr}[1]{{\sf m}_r(#1)} \newcommand{\mzx}[2]{{\sf m}_{#2}(#1)} \begin{document} \jmlrheading{2}{2001}{67-93}{08/01}{12/01}{Steinwart} \ShortHeadings{On the Consistency of Support Vector Machines}{Steinwart} \firstpageno{67} \title{On the Influence of the Kernel on the Consistency of Support Vector Machines} \author{\name Ingo Steinwart \email steinwart@minet.uni-jena.de\\ \addr Mathematisches Institut\\ Friedrich-Schiller-Universit\"at\\ Ernst-Abbe-Platz 1-4\\ 07743 Jena, Germany} \editor{Bernhard Sch\"olkopf (for \url{HTTP://WWW.KERNEL-MACHINES.ORG})} \maketitle \begin{abstract}% In this article we study the generalization abilities of several classifiers of support vector machine (SVM) type using a certain class of kernels that we call universal. It is shown that the soft margin algorithms with universal kernels are consistent for a large class of classification problems including some kind of noisy tasks provided that the regularization parameter is chosen well. In particular we derive a simple sufficient condition for this parameter in the case of Gaussian RBF kernels. On the one hand our considerations are based on an investigation of an approximation property---the so-called universality---of the used kernels that ensures that all continuous functions can be approximated by certain kernel expressions. This approximation property also gives a new insight into the role of kernels in these and other algorithms. On the other hand the results are achieved by a precise study of the underlying optimization problems of the classifiers. Furthermore, we show consistency for the maximal margin classifier as well as for the soft margin SVM's in the presence of large margins. In this case it turns out that also constant regularization parameters ensure consistency for the soft margin SVM's. Finally we prove that even for simple, noise free classification problems SVM's with polynomial kernels can behave arbitrarily badly. \end{abstract} \begin{keywords} Computational learning theory, pattern recognition, PAC model, support vector machines, kernel methods \end{keywords} \section{Introduction} Support vector machines comprise a class of learning algorithms originally introduced for pattern recognition problems. Although their development was motivated by results of statistical learning theory the known bounds on their generalization performance are not fully satisfactory. In particular, the influence of the chosen kernel is far from being completely understood. The aim of this paper is to give a new insight into the role of the kernels. Our considerations are mainly based on a certain approximation property of various standard kernels that generate function classes with infinite VC-dimension. Since in this case classical Vapnik-Chervonenkis theory fails to be applicable for support vector machines, other concepts such as data dependent structural risk minimization, e.g.\ in terms of the observed margin, were introduced \citep*[cf.][chap.~2]{SBWA,BST,CST}. The latter usually needs large margins on the training sets to provide good bounds. It is, however, open which distributions and kernels guarantee this assumption. A systematical study of this question is the starting point of this paper. The resulting techniques allow us to show new bounds for the generalization performance of several standard support vector classifiers. We begin with a description of the problem of pattern recognition \citep*[cf.][]{Vap,CST}. Let $(X,d)$ be a compact metric space\footnote{For mathematical notions see Section 2.}, $Y:= \{-1,1\}$ and $P$ be a probability measure on $X\times Y$, where $X$ is equipped with the Borel $\s$-algebra. By disintegration \citep[cf.][Lem.~1.2.1.]{Dud} there exists a map $x\mapsto P(\,.\,|x)$ from $X$ into the set of all probability measures on $Y$ such that $P$ is the joint distribution of $(P(\,.\,|x))_x$ and of the marginal distribution $P_X$ of $P$ on $X$. We call $P(\,.\,|.)$, which is in fact a regular conditional probability, the {\em supervisor}. A classifier is an algorithm that constructs to every {\em training set} $T=((x_1,y_1),\dots,(x_n,y_n))\in (X\times Y)^n$ a {\em decision function} $f_T:X \to Y$. In our context it is always assumed that $T$ is i.i.d.\ according to $P$, which itself is unknown. Then the decision function $f_T:X\to Y$ constructed by the classifier should guarantee a small probability for the misclassification of an example $(x,y)$ randomly generated according to $P$. Here, misclassification means $f(x) \neq y$. To make this precise, for a measurable function $f:X\to \{-1,1\}$ we define the risk of $f$ by $$ \ca R_{P}(f) \Defi \Int_{X\times Y} \eins_{\{f(x) \neq y\}}\ P(dx,dy) \Eq P\bigl(\{(x,y): f(x)\neq y\}\bigr)\ . $$ When considering noisy supervisors we cannot expect that we obtain zero risk. Indeed, for \begin{eqnarray*} B_1(P) & := & \bigl\{x\in X\ : \ P(y=1|x) > P(y=-1|x)\, \bigr\}\\ B_{-1}(P) & := & \bigl\{x\in X\ : \ P(y=1|x) < P(y=-1|x)\, \bigr\}\\ B_0(P) & := & \bigl\{x\in X\ : \ P(y=1|x) = P(y=-1|x)\, \bigr\} \end{eqnarray*} and a function $f_0:X\to \{-1,1\}$ with $f_0(x)=1$ if $x\in B_1(P)$ and $f_0(x)=-1$ if $x\in B_{-1}(P)$ we have \citep[cf.][Thm.~2.1.]{DGL} \begin{equation}\label{Bayesrisk} \ca R_{P}(f_0) \Eq \inf\bigl\{\ca R_{P}(f) \ :\ f\!:\!X\to \{-1,1\} \mbox{ measurable}\bigr\} \Eq \Int_X p(x)\, P_X(dx)\ , \end{equation} where the {\em noise level} $p:X\to \R$ is defined by $p(x):= P(y=-1|x)$ for $x\in B_1(P)$, $p(x):= P(y=1|x)$ for $x\in B_{-1}(P)$ and $p(x)=1/2$ otherwise. Equation (\ref{Bayesrisk}) shows that no function can yield less risk than $f_0$. The function $f_0$ is called an optimal Bayes decision rule and we write $\ca R_{P} := \ca R_{P}(f_0)$. Now, a classifier $\ca C$ should guarantee with high probability that $\ca R_{P}(f_T)$ is close to $\ca R_{P}$ provided that $T$ is large enough. Here, $f_T$ denotes the decision function constructed by $\ca C$ on the basis of $T$. Asymptotically, this means that \begin{equation*} \ca R_{P}(f_T) \to \ca R_{P} \end{equation*} should hold in probability if $|T|\to\infty$. In this case the algorithm $\ca C$ is called {\em consistent} for $P$ \citep[cf.][Def.~6.1]{DGL}. If a classifier is consistent for all distributions on $X\times Y$ it is said to be universally consistent. Although several algorithms such as the $k$-nearest neighbour classifier for $k\to \infty$ and $k/|T| \to 0$ \citep[cf.][Thm.~6.4]{DGL} are universally consistent it is an open question whether support vector machines are universally consistent for a particular choice of the free parameters. In this article we show that at least for a restricted class of distributions SVM's are consistent provided that the parameters are chosen in a specific manner. In particular our results cover both the noise free case and the case of constant noise level, i.e $p \equiv p^*$, $p^*\in [0,1/2)$. Our results are based on an investigation of a certain approximation property of kernels. Recall that the ansatz of SVM's is to solve specific optimization problems over the class of functions $\{\langle w,\P(.)\rangle : w\in H\}$ (or $\{\langle w,\P(.)\rangle + b : w\in H, b\in \R\}$), where $\P:X\to H$ is a feature map of the used kernel. If this function class is dense in $C(X)$ we shall call the corresponding kernel {\em universal} (cf.\ Def.\ \ref{Defuniv}). Roughly speaking this notion enables us to approximate the Bayes decision rule in probability, a fact that is frequently used in our proofs of consistency. Using the approximation theorem of Stone-Weierstra\ss\ we show that kernels that can be expanded in certain types of Taylor or Fourier series are universal (cf.\ Cor.\ \ref{taylorexp} and Cor.\ \ref{fourierexp}). In particular it turns out that the Gaussian RBF kernel is universal (cf.\ Ex. \ref{gaussexp}). Besides the importance of the notion of universality in the context of consistency it also turns out that this concept has strong implications for the geometric interpretation of the shape of the feature map (cf.\ Cor.\ \ref{sepcpct} and the following remark). Since the class of functions implemented by an SVM with universal kernel is very rich the problem of overfitting can always occur in the presence of noise. Thus it is very important to know how to chose the regularization parameter. The second part of this work is devoted to this question. Here, we show in particular that for a soft margin SVM with Gaussian RBF kernel on $X\subset \R^d$ the regularization sequence $c_n=n^{\b-1}$, $0<\b<1/d$, yields consistency for all problems with constant noise level (cf.\ Cor.\ \ref{Cor1} and Cor.\ \ref{Cor3}). These results are of special interest since they show at the first time that SVM's are able to learn noisy problems arbitrarily well. Moreover, we prove that for problems that ensure a large margin it suffices to use universal kernels and a regularization parameter that is {\em independent} of the training set size (cf.\ Thm.\ \ref{HS3}, Thm.\ \ref{HS4} and Thm.\ \ref{HS7}). For this class of problems we also prove consistency for the maximal margin classifier (cf.\ Thm.\ \ref{HS8}). Finally, it turns out that even for these simple, noise free classification problems SVM's with polynomial kernels can behave arbitrarily badly (cf.\ Prop.\ \ref{Pro1}). This work is organized as follows: we introduce some mathematical notions in Section \ref{prelim}. In the third section we study the concept of universal kernels. The following sections are devoted to applications of these kernels to support vector machines. We begin with the 2-soft margin classifier in Section 4. Here, consistency results for both noisy distributions and problems ensuring a large margin are proved. In the fifth section we show that these results also hold for the 1-soft margin algorithm. In the last section we discuss the maximal margin classifier in the presence of large margins. \section{Preliminaries}\label{prelim} For a set $X$, a metric $d$ on $X$ is a function $d:X\times X\to [0,\infty)$ such that for all $x,y,z\in X$ we have $d(x,y)=d(y,x)$ and $d(x,y) \leq d(x,z)+d(z,y)$ as well as $d(x,y) =0$ if and only if $x=y$. We denote the closed ball with radius $\e$ and centre $x$ by $B_d(x,\e):=\{y\in X:d(x,y)\leq \e\}$. The covering numbers of $X$ are defined by $$ \ca N((X,d),\e) \Defi \min\Bigl\{n\in \N\cup \{\infty\}\ : \ \exists x_1,\dots,x_n \mbox{ with } X\subset \bigcup_{i=1}^n B_d(x_i,\e)\Bigr\} $$ for all $\e>0$. The space $(X,d)$ is precompact if and only if $\ca N((X,d),\e)$ is finite for all $\e>0$. Moreover, $X$ is called compact if every open covering of $X$ has a finite subcovering. If the space $(X,d)$ is complete, i.e.\ every Cauchy sequence converges in $X$, then $X$ is compact if and only if $X$ is precompact. For given $A,B\subset X$ we denote the distance of $A$ and $B$ by $$ d(A,B) \ :=\ \inf_{\substack{x\in A\\ y\in B}} d(x,y). $$ We often use that if $A$ is closed, $B$ is compact and both sets are disjoint then $d(A,B)>0$ holds. A $\s$-algebra on a set $X$ is a set of subsets of $X$ that contains $\emptyset$ and is closed under elementary, countable set operations such as complements and countable intersections. For a metric space $(X,d)$ the Borel $\s$-algebra is the smallest $\s$-algebra that contains all open sets. Let $\ca A$ be a $\s$-algebra on $X$. A subset $A$ of $X$ is called measurable if $A\in \ca A$. We say that a function $f:X\to \R$ is measurable if the pre-image of every Borel measurable $B\subset \R$ is in $\ca A$. Basic examples are the functions $\eins_A$, where $A\in \ca A$ and $\eins_A(x)=1$ if $x\in A$ and $\eins_A(x)=0$ otherwise. A probability measure $P :\ca A\to \Rp$ is a $\s$-additive function with $P(\emptyset)=0$ and $P(X)=1$. If $\ca A$ is a Borel $\s$-algebra we call $P$ a Borel probability measure. In this case $P$ is said to be regular, if for all Borel measurable $B\subset X$ we have $$ P(B) \Eq \sup \{P(K): K\subset B \mbox{, $K$ compact}\}\ . $$ If $(X,d)$ is compact, then every Borel probability measure on $X$ is regular \citep[cf.][p.~176]{Dud}. In this paper $H$ always denotes a Hilbert space, i.e.\ a complete, normed vector space endowed with a dot product $\langle.,.\rangle$ giving rise to its norm via $\snorm x = \sqrt{\langle x,x\rangle}$. Let $B_H:=\{x\in H: \snorm x \leq 1\}$ be the closed unit ball of $H$ and $S_H:=\{x\in H: \snorm x = 1\}$ be its sphere. Recall, that every separable Hilbert space is isometrically isomorphic to the space of all 2-summable sequences $\lto$. A commutative algebra $A$ is a vector space equipped with an additional associative and commutative multiplication $\cdot:A\times A\to A$ such that \begin{eqnarray*} x\edot (y+z) & = & x\edot y+x\edot z\\ \lb (x\edot y) & = & (\lb x)\edot y \end{eqnarray*} holds for all $x,y,z\in A$ and $\lb\in \R$. A classical example of an algebra is the space $C(X)$ of all continuous functions $f:X\to \R$ on the compact metric space $(X,d)$ endowed with the usual supremum norm $$ \inorm f \Defi \sup_{x\in X} |f(x)|\ . $$ The following well-known approximation theorem of Stone-Weierstra\ss \ \citep[cf.][Cor.~4.3.5.]{Ped} states that certain subalgebras of $C(X)$ generate the whole space. This result will be the key tool when considering approximation properties of kernels in the next section: \begin{theorem}\label{StoneWeier} Let $(X,d)$ be a compact metric space and $A\subset C(X)$ be an algebra. Then $A$ is dense in $C(X)$ if both $A$ does not vanish, i.e.\ for all $x\in X$ there exists an $f\in A$ with $f(x)\neq 0$, and $A$ separates points, i.e.\ for all $x,y\in X$ with $x\neq y$ there exists an $f\in A$ with $f(x)\neq f(y)$. \end{theorem} \section{Kernels}\label{kernels} In the following let $(X,d)$ be a metric space. A function $k:X\times X\to \R$ is called a kernel on $X$ if there exists a Hilbert space $H$ and a map $\P:X\to H$ with $$ k(x,y) \ =\ \langle\P(x),\P(y)\rangle $$ for all $x,y\in X$. We call $\P$ a {\em feature map} and $H$ a {\em feature space} of $k$. Note, that both $H$ and $\P$ are far from being unique. However, for a given kernel there exists a canonical feature space (with associated feature map), which is the so-called reproducing kernel Hilbert space (RKHS) \citep*[cf.][Ch.~3]{CST}. Since our ansatz is mainly based on specific series expansions of certain kernels we do not need to consider these spaces. Let $k$ be a kernel on $X$ and $\P:X\to H$ be a feature map of $k$. A function $f:X\to \R$ is {\em induced} by $k$ if there exists an element $w\in H$ such that $f=\langle w,\P(.)\rangle$. The next lemma shows that this definition is independent of $\P$ and $H$: \begin{lemma}\label{sameHyper} Let $k:X\times X\to \R$ be a kernel and $\P_1:X\to H_1$, $\P_2:X\to H_2$ be two feature maps of $k$. Then for all $w_1\in H_1$ there exist $w_2\in H_2$ with $\snorm {w_2} \leq \snorm{w_1}$ and \begin{displaymath} \langle w_1,\P_1(x)\rangle \ = \ \langle w_2,\P_2(x)\rangle\eqno{\mbox{for all }x\in X.} \end{displaymath}\\[-8mm] \end{lemma} \begin{proof} Let $H_1^*:= \overline{\spann {\P_1(X)}}$ and $\tilde H_1$ its orthogonal complement in $H_1$. Then $w_1\in H_1$ can be written as $w_1=w_1^*+\tilde w_1$ with $w_1^*\in H_1^*$ and $\tilde w_1\in \tilde H_1$. Given an $x\in X$ we have $\langle \tilde w_1,\P_1(x)\rangle =0$ and therefore we obtain $\langle w_1^*,\P_1(x)\rangle = \langle w_1,\P_1(x)\rangle$ for all $x\in X$. Now by the definition of $H_1^*$ there exists a sequence $(w_n^{(1)})\subset \spann {\P_1(X)}$ with $w_n^{(1)}= \sum_{m=1}^{m_n} \lb_m^{(n)} \P_1(x_m^{(n)})$ and $w_1^*= \sum_{n=1}^\infty w_n^{(1)}$. Then for $w_n^{(2)}:= \sum_{m=1}^{m_n} \lb_m^{(n)} \P_2(x_m^{(n)})$ and $l_2\geq l_1\geq 1$ we obtain \begin{eqnarray*} \norm{\sum_{n=l_1}^{l_2}w_n^{(1)}}^2 & =& \sum_{n=l_1}^{l_2}\sum_{m=1}^{m_n} \sum_{i=l_1}^{l_2}\sum_{j=1}^{m_i} \ \lb_m^{(n)} \lb_j^{(i)}\langle \P_1(x_m^{(n)}),\P_1(x_j^{(i)})\rangle\\ & =& \sum_{n=l_1}^{l_2}\sum_{m=1}^{m_n} \sum_{i=l_1}^{l_2}\sum_{j=1}^{m_i} \ \lb_m^{(n)} \lb_j^{(i)}\langle \P_2(x_m^{(n)}),\P_2(x_j^{(i)})\rangle\\ & = & \norm{\sum_{n=l_1}^{l_2}w_n^{(2)}}^2 \ . \end{eqnarray*} Therefore, $(\sum_{n=1}^m w_n^{(2)})_{m\geq 1}$ is a Cauchy sequence and hence converges to $w_2:= \sum_{n=1}^\infty w_n^{(2)} \in H_2$. Clearly, we then have $\snorm{w_2}=\snorm{w_1^*}\leq\snorm{w_1}$. Moreover, an easy calculation similar to the consideration above shows $\langle w_1,\P_1(x)\rangle = \langle w_2,\P_2(x)\rangle$ for all $x\in X$. \end{proof} \noindent In the following we only consider continuous kernels. The following lemma provides some useful properties of this class: \begin{lemma}\label{contkernel} Let $k$ be a kernel on the metric space $(X,d)$ and $\P:X\to H$ be a feature map of $k$. Then $k$ is continuous if and only if $\P$ is continuous. In this case $$ d_k (x,y)\Defi\Norm{\P(x)-\P(y)} $$ defines a semi-metric on $X$ such that the identity map $\id:(X,d)\to (X,d_k)$ is continuous. If $\P$ is injective $d_k$ is even a metric. \end{lemma} \begin{proof} Let us first suppose that $k$ is continuous. Since $$ d_k(x,y)\Eq\sqrt{k(x,x)-2k(x,y)+k(y,y)} $$ we observe that $d_k(x,.):(X,d)\to \R$ is continuous for every $x\in X$. In particular, $\{y\in X : d_k(x,y)<\e\}$ is open with respect to $d$ and therefore $\id:(X,d)\to (X,d_k)$ is continuous. Furthermore, $\P:(X,d_k)\to H$ is continuous and hence $\P:(X,d)\to H$ is also continuous.\\ Conversely, assume that $\P$ is continuous. Since for all $x,x',y,y'\in X$ we have \begin{eqnarray*} |k(x,y)-k(x',y')| & \leq & |\langle \P(x),\P(y)-\P(y')\rangle| + |\langle \P(x)-\P(x'),\P(y')\rangle|\\ & \leq & \Norm{\P(x)}\edot \Norm{\P(y)\!-\!\P(y')} + \Norm{\P(y')}\edot \Norm{\P(x)\!-\!\P(x')} \end{eqnarray*} it is easily verified that $k$ is also continuous.\end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % separierende und universelle Kerne %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent The metric $d_k$ enjoys the property that every induced function $\langle w,\P(.)\rangle$ is Lipschitz continuous with respect to $d_k$ and the Lipschitz constant is bounded from above by $\snorm w$. This fact turns out to be very important in the proof of Theorem \ref{HS1} since it allows us to control the behaviour of solutions of SVM's on subsets of small diameters. From the last lemma we know in particular that for a continuous kernel every induced function is continuous. The following definition plays a central role throughout this paper: \begin{definition}\label{Defuniv} A continuous kernel $k$ on a compact metric space $(X,d)$ is called {\em universal} if the space of all functions induced by $k$ is dense in $C(X)$, i.e. for every function $f\in C(X)$ and every $\e>0$ there exists a function $g$ induced by $k$ with $$ \inorm{f-g} \Leq \e\ . $$ \end{definition} \noindent We also need a weaker concept. Let $\P:X\to H$ be a feature map of $k$ and $A$, $B$ be disjoint subsets of $X$. We say that $k$ {\em separates $A$ and $B$ with margin $\g\geq 0$} if $\P(A)$ and $\P(B)$ can be separated by a hyperplane with margin $\g$, i.e.\ if there exists a pair $(w,b)\in S_H\times \R$ such that $$ \begin{array}{rcll} \langle w,\P(x)\rangle + b & > &\g & \qquad \qquad \mbox{for all } x\in A \mbox{ and}\\ \langle w,\P(y)\rangle + b & < &-\g & \qquad \qquad \mbox{for all } y\in B\ . \end{array} $$ If $\g=0$ we simply say that $k$ separates $A$ and $B$. In this case the restriction $w\in S_H$ is superfluous. By Lemma \ref{sameHyper} both definitions are independent of the feature map $\P$. We say that the kernel $k$ separates all finite, resp.\ compact subsets if it separates all finite, resp.\ compact disjoint subsets of $X$. Note, that if $k$ separates {\em compact} sets $A$ and $B$ then it automatically separates them with a suitable margin $\g>0$. Moreover, it was shown in \citet[][Ex.~3.13]{Ste} that there exists a continuous kernel that separates all finite subsets but fails to separate all compact subsets. Before we investigate which kernels are universal we collect some useful properties of these kernels. Firstly, let $(X,d)$ and $(X',d')$ be compact metric spaces, $k$ be a universal kernel on $X$ and $\iota:X'\to X$ be a continuous and injective map. Then one easily checks that $k(\iota(.),\iota(.))$ is a universal kernel on $X'$. Moreover, we have $k(x,x)>0$ for all $x\in X$ since $k(y,y) = 0$ implies $g(y)=0$ for all induced functions $g$. Since all feature maps of $k$ are continuous and $X$ is compact we may also restrict ourselves to separable feature spaces of $k$. The next proposition is fundamental for our considerations of support vector machines: \begin{proposition}\label{approxstep} Let $(X,d)$ be a compact metric space and $k$ be a universal kernel on $X$. Then for all compact and mutually disjoint subsets $K_1,\dots,K_n \subset X$, all $\a_1,\dots,\a_n \in \R$ and all $\e>0$ there exists a function $g$ induced by $k$ with $\inorm g \leq \max_i |\a_i| + \e$ such that $$ \norm{g_{|K} - \Sum_{i=1}^n \a_i \eins_{K_i}}_\infty \leq \e\ , $$ where $K:= \bigcup_{i=1}^n K_i$ and $g_{|K}$ denotes the restriction of $g$ to $K$. \end{proposition} \begin{proof} Since $d(K_i,K_j) > 0$ for all $i\neq j$ we obtain $\sum_{i=1}^n \a_i \eins_{K_i} \in C(K)$. Since this function can be extended to a continuous function $f$ on $X$ with $\inorm f \leq \max_i |\a_i|$ (by the Lemma of Urysohn or by a direct construction with the help of $d$) the assertion follows. \end{proof} \begin{corollary}\label{sepcpct} Every universal kernel separates all compact subsets. \end{corollary} \begin{proof} Let $(X,d)$ be a compact metric space and $k$ be a universal kernel on $X$ with feature map $\P:X\to H$. Given two compact and disjoint subsets $K_1$ and $K_{-1}$ of $X$ there exists an induced function $g=\langle w,\P(.)\rangle$ with $\inorm{g_{|K_{-1}\cup K_1}- (\eins_{K_1}-\eins_{K_{-1}})} < 1/2$. This implies that $({\Norm w}^{-1} w,0)$ separates $K_1$ and $K_{-1}$ with margin $\frac 1{2\Norm w}$. \end{proof} \noindent Although the previous corollary is an almost trivial consequence of the notion of universality it has surprising implications for the geometric interpretation of the shape of the feature map: let us suppose that we have a finite subset $\{x_1,\dots,x_n\}$ of $X$. Then the above corollary ensures that for every sequence of signs $y_1,\dots,y_n$ the corresponding training set can be correctly separated by a hyperplane in the feature space. Moreover, this can even be done by a hyperplane that has almost the same distance to every point of $\{x_1,\dots,x_n\}$. Therefore, any finite dimensional interpretation of the geometric situation in a feature space of a universal kernel must fail. In particular this holds for 2- or 3-dimensional drawings. (Actually, the shape of the feature map is even more complicated since not only all finite subsets but every pair of compact disjoint subsets can be separated.) The following corollary ensures in particular that the semi-metric $d_k$ induced by a universal kernel $k$ is in fact a metric: \begin{corollary} Every feature map of a universal kernel is injective. \end{corollary} \begin{proof} Finite subsets are compact and thus the assertion follows by the previous corollary. \end{proof} \begin{proposition}\label{normkern} Let $(X,d)$ be a compact metric space and $k$ be a universal kernel on $X$. Then $$ k^*(x,y)\Defi \frac{k(x,y)}{\sqrt{k(x,x)k(y,y)}} $$ defines a universal kernel on $X$. \end{proposition} \begin{proof} Let $\P:X\to H$ be a feature map of $k$ and $\a(x):= k(x,x)^{-1/2}$. Clearly, $\a\P:X\to H$ is a feature map of $k$ and thus $k$ is a kernel. To show that $k^*$ is universal we fix a function $f\in C(X)$ and $\e>0$. For $a:=\inorm{\a}$ we then get an induced function $g=\langle w,\P(.)\rangle$ with $\isnorm{ \a^{-1} f -g} \leq \frac \e a$. This yields $$ \inorm{f-\langle w ,\a\P(.)\rangle} \Leq \inorm{\a}\ \isnorm{\a^{-1} f -g} \Leq \e $$ and thus the assertion is proved. \end{proof} \noindent Up to now we do not know whether there exist universal kernels. To attack this question we begin with a simple criterion that makes it possible to check whether a given kernel is universal: \begin{theorem}\label{kernuniv} Let $(X,d)$ be a compact metric space and $k$ be a continuous kernel on $X$ with $k(x,x)>0$ for all $x\in X$. Suppose that we have an injective feature map $\P:X\to \lto$ of $k$ with $\P(x)=(\P_n(x))_{n\in \N}$. If $A:=\spann{\{\P_n : n\in \N\}}$ is an algebra then $k$ is universal . \end{theorem} \begin{proof} Because of $k(x,x)>0$ for all $x\in X$ the algebra $A$ does not vanish. Since $k$ is continuous every $\P_n:X\to \R$ is continuous by Lemma \ref{contkernel} and hence $A\subset C(X)$. Moreover, $A$ is even dense in $C(X)$ since the injectivity of $\P$ implies that $A$ separates points and thus Theorem \ref{StoneWeier} can be applied. Now we fix $f\in C(X)$ and $\e>0$. Then there exists a function \begin{displaymath} g=\sum_{j=1}^n\lb_j\cdot(\P_{n_j}) \ \in \ A \end{displaymath} such that $\inorm{f-g} \leq \e$. However, if we define $w_n:= \lb_j$ for $n=n_j$ and $w_n:= 0$ otherwise, we have $w:=(w_n) \in \lto$ and $\langle w,\P(.)\rangle =g$. \end{proof} \noindent The following corollaries give various examples of universal kernels. We begin with kernels that can be expressed by a Taylor series: \begin{corollary}\label{taylorexp} Let $0 0$ for all $n\geq 0$ then $k(x,y):=f(\langle x,y\rangle)$ defines a universal kernel on every compact subset of $X$. \end{corollary} \begin{proof} Since $|\langle x, y\rangle| \leq \ynorm x 2 \ynorm y 2 < r$ for all $x,y\in X$ we see that $k$ is well-defined. We also have \begin{eqnarray*} k(x,y) & = & \sum_{n=0}^\infty a_n\ \Bigl(\sum_{k=1}^d x_k y_k\Bigr)^n\\ & = & \sum_{n=0}^\infty a_n\ \sum_{\substack{k_1+\dots+k_d=n\\k_1,\dots,k_d\geq 0}} c_{k_1,\dots,k_d} \prod_{i=1}^d (x_iy_i)^{k_i}\\ & = & \sum_{k_1,\dots,k_d\geq 0} a_{k_1+\dots+k_d} c_{k_1,\dots,k_d} \prod_{i=1}^d x_i^{k_i} \prod_{i=1}^d y_i^{k_i} \ , \end{eqnarray*} where $c_{k_1,\dots,k_d}:= (\prod_{i=1}^d k_i!)^{-1}{(\sum_{i=1}^d k_i)!}$ \citep[cf.\ also][Lem.~2.1]{Pog}. Note, that the series can be rearranged since it is absolutely summable. In particular, for $x=y$ we obtain that $\P:X \to \lt{\N_0^d}$ is well defined by $$ \P(x) \Defi \Bigl(\sqrt{a_{k_1+\dots+k_d} c_{k_1,\dots,k_d}} \prod_{i=1}^d x_i^{k_i}\Bigr)_{k_1,\dots,k_d\geq 0}\ . $$ The above equation also shows that $k(x,y)= \langle \P(x),\P(y) \rangle$ holds for all $x,y\in X$ and hence $k$ is indeed a kernel. Moreover, $a_0>0$ implies $k(x,x)>0$ for all $x\in X$ and trivially, $\P$ is injective. Since $A:=\spann{\{\P_{k_1,\dots,k_d} : k_1,\dots,k_d\geq 0\}}$ is an algebra we thus obtain by Theorem \ref{kernuniv} that $k$ is universal. \end{proof} \noindent Instead of Taylor series one can also consider Fourier expansions. The result reads as follows: \begin{corollary}\label{fourierexp} Let $f:[0,2\pi] \to \R$ be a continuous function that can be expanded in a pointwise absolutely convergent Fourier series of the form \begin{equation}\label{fourierh1} f(t) \Eq \sum_{n=0}^\infty a_n \cos(n t)\ . \end{equation} If $a_n>0$ holds for all $n\geq 0$ then $k(x,y):=\prod_{i=1}^d f(|x_i-y_i|)$ defines a universal kernel on every compact subset of $[0,2\pi)^d$. \end{corollary} \noindent Recall, that every function $f:[0,2\pi] \to \R$ that can be extended to a continuous, symmetric, periodic and piecewise continuously differentiable function on $\R$ has a Fourier series of the form (\ref{fourierh1}).\\ \begin{proof} By induction and the Cauchy product of series we may restrict ourselves to $d=1$. Then \begin{displaymath} k(x,y) = a_0 + \! \sum_{n=1}^\infty a_n \sin(n x)\sin(n y) +\! \sum_{n=1}^\infty a_n \cos(n x)\cos(n y) \end{displaymath} holds for all $x,y\in [0,2\pi)$ and hence $\P=(\P_n)_{n\geq 0}$ defined by $\P_0(x):= a_0$ and $\P_{2n-1}(x):= \sqrt{a_n} \sin (nx)$, $\P_{2n}(x):= \sqrt{a_n} \cos (nx)$ for $n\geq 1$ is an injective feature map of $k$ with image in $\lto$. Moreover, $ A:=\spann \bigl(\{\sqrt{a_n} \sin(n\cdot . ) : n\geq 1\} \cup \{\sqrt{a_0} \cos(n \cdot .) : n\geq 0\}\bigr) $ is an algebra and since $a_0>0$ implies $k(x,x)>0$ for all $x\in X$ we obtain that $k$ is universal. \end{proof} \noindent The following examples show that various well-known kernels are universal: \begin{example}\label{gaussexp} {\em The kernels $\exp(-\s^2 \xnorm{.-.} 2 2)$ and $\exp(\langle .,.\rangle)$ are universal on every compact subset of $\R^d$.} \end{example} \begin{proof} The universality of $\exp(\langle .,.\rangle)$ is due to Corollary \ref{taylorexp}. Therefore, by Proposition \ref{normkern} and $\exp(-\s^2 \xnorm{x-y} 2 2) \Eq \exp(- \xnorm{\s x} 2 2) \exp(- \xnorm{\s y} 2 2) \exp(\langle \sqrt 2 \s x,\sqrt 2 \s y\rangle)$ the assertion follows for the RBF kernel. \end{proof} \begin{example} {\em Let $X:=\{x\in \R^d : \ynorm x 2 < \mbox{$1$}\}$ and $\a>0$. Then V. Vovk's \citep[cf.][p.~15]{SSW} infinite polynomial kernel $k(x,y):= (1-\langle x,y \rangle )^{-\a}$, $x,y\in X$, is universal on every compact subset of $X$.} \end{example} \begin{proof} To check the assertion we use that $(1-t)^{-\a} = \sum_{n=0}^\infty \binom {-\a} n (-1)^n t^n$ holds for $|t|<1$. Since $\binom {-\a} n (-1)^n > 0$ for all $n\geq 0$, the assertion then follows by Corollary \ref{taylorexp}. \end{proof} \begin{example} {\em Let $00$ we denote the unique solution of the optimization problem \begin{equation}\label{prim2sno} \begin{array}{rll} \!\!\!\!\!\!\mbox{minimize} & \qquad \ca W(w,b,\xi) := \langle w,w\rangle + c_n\Sum_{i=1}^n\x_i^2 \qquad &\mbox{over } w,b,\x\\ \!\!\!\!\!\!\mbox{subject to} & \qquad y_i(\langle w,\P(x_i)\rangle +b) \geq 1-\x_i, & i=1,\dots,n \end{array} \end{equation} by $(w_{T}^{2,k,c_n},b_T^{2,k,c_n})\in H\times \R$. An algorithm $\ca C_k^{2,(c_n)}$ that provides the decision function $$ f_T^{2,k,c_n}(x):= \sign(\langle w_T^{2,k,c_n},\P(x)\rangle +b_T^{2,k,c_n})\ , \qquad \qquad x\in X $$ for every training set $T$ is called a 2-norm soft margin classifier (2-SMC) with kernel $k$ and parameter sequence $(c_n)$. Note, that in order to have a small set of free parameters one usually fixes $c_n := c$ for all $n\geq 1$. In this section it turns out that this is not suitable for problems that do no guarantee a large margin. Instead one should use sequences $c_n = c n^{\b-1}$ where $\b>0$ is a parameter a-priori determined by the kernel and $c$ is a new free parameter (cf.\ Cor.\ \ref{Cor1}). Of course, for fixed training set sizes both parameterizations are equivalent, i.e.\ they can be transformed into each other. By Lemma \ref{sameHyper} the decision function is independent of the choice of the feature map $\P$. Moreover, $f_T^{2,k,c_n}$ can be expressed by \begin{displaymath} f_T^{2,k,c_n}(x) \Eq \sum_{i=1}^n y_i \a_i k(x_i,x) +b_T^{2,k,c_n}, \end{displaymath} where $\a_i\geq 0$ are suitable constants depending on $T$ and $b_T^{2,k,c_n}$ can also be computed with the help of the kernel \citep*[cf.][]{CST,Vap,SHSW}. Note, that if $k$ is a kernel on $X$ which separates all finite sets and $X$ has infinitely many elements then the function class represented by the 2-SMC has infinite VC-dimension. For more information on this we refer to \citet*[][Ch.~4]{Vap}, \citet*[][Ch.~4]{CST} and \citet*[][Ch.~2.6]{V-W}. Given a Borel probability measure $P$ on $X\times Y$ with noise level $p$ we denote the nondeterministic part of the supervisor by $X^+:=\{x\in X : p(x)>0\}$. If $P_X(X^+)>0$ we write $q^*:= \inf_{x\in X} p(x)$ and $p^* := \sup_{x\in X}p(x)$. Due to technical reasons we define $q^*:= p^* := 1/4$ otherwise. We begin with a preliminary result: \begin{theorem}\label{HS1} Let $(X,d)$ be a compact metric space and $k$ be a universal kernel on $X$. Then for all Borel probability measures $P$ on $X\times Y$ with $q^*,p^* \in (0, 1/2)$ and all $\e>0$ there exist $c^*>0$ and $\d^*>0$ such that for all $c\geq c^*$, $0<\d\leq\d^*$ and all $n\geq 1$ we have \begin{displaymath} \opa \Bigl(\Bigl\{T\in (X\times Y)^n : \ca R_P (f^{2,k,c/n}_{T})\leq \ca R_P + 4 \frac{p^*-q^*}{1-2q^*}P_X(X^+) + \e\Bigr\}\Bigr) \Geq 1 - 3M e^{-2 \left(\frac \d M\right)^2 n}\ , \end{displaymath} where $M := \ca N\bigl((X,d_k),\frac \d {\sqrt c}\bigr)$ is the covering number of $X$ with respect to the metric $d_k$ which is induced by the kernel $k$. Moreover, $\opa$ denotes the outer probability measure of $P^n$. \end{theorem} \noindent Note, that in order to avoid the (probably very difficult) question whether the sets $$ \bigl\{T\in (X\times Y)^n : \ca R_P (f^{2,k,c/n}_{T})\leq \a\bigr\} $$ are measurable we consider the outer probability measure, only. Since the proof of Theorem \ref{HS1} is very technical we like to explain the basic idea of the proof firstly. Let us suppose that the supervisor has a constant level of noise $p\in [0,1/2)$. Moreover, we assume that we have an induced function $\langle w^*,\P(.)\rangle$ which has the constant values $1-2p$, resp. $-(1-2p)$ on $B_1(P)$, resp. $B_{-1}(P)$. Now let us take a ``representative'' training set $T$ of length $n$. Then one easily checks (cf.\ estimate (\ref{above})) that $$ \langle w_T^{k,c/n},w_T^{k,c/n}\rangle + \frac c n\sum_{l=1}^n \x_l^2 \ \ \lesssim \ \ \langle w^*,w^*\rangle + 4cp(1-p) $$ holds. Here $\lesssim$ means that the relation $\leq$ only holds ``approximately''. On the other hand, by the continuity of the decision function $w_T^{k,c/n}$ a misclassified (compared with the optimal Bayes decision rule) element $z$ forces the sum of those slack variables, which belong to samples in the ``neighbourhood'' of $z$, to be ``approximately'' greater than their cardinality (cf.\ inequality (\ref{below2})). Conversely, for a correctly classified element the corresponding sum of the slack variables is ``approximately'' larger than $4p(1-p)$ times their cardinality (cf.\ inequality (\ref{below3})). Combining these considerations we obtain \begin{eqnarray*} c(1-2p)^2P_X(E)+4cp(1-p) & = & c\bigl(P_X(E) + 4p(1-p)P_X(X\setminus E)\bigr)\\ & \lesssim & \langle w_T^{k,c/n},w_T^{k,c/n}\rangle + \frac c n\sum_{l=1}^n \x_l^2 \\ & \lesssim & \langle w^*,w^*\rangle + 4cp(1-p) \ , \end{eqnarray*} where $E$ denotes the set of misclassified (compared with the optimal Bayes decision rule) elements. Thus $P_X(E)$ must be ``small'' if we have chosen $c$ ``large enough''. The difficulty of the proof below is firstly, to transfer the idea to the general case and secondly, to give exact formulations of ``representative'', ``neighbourhood'' and ``approximately''.\\ \begin{proofo}{of Theorem \ref{HS1}} Without loss of generality we may assume $\e\in(0,1]$. Let $X^0:= X\setminus X^+$ be the deterministic part of the supervisor and $X_{-1}^0 := X^0 \cap B_{-1}(P)$, $X_{1}^0 := X^0 \cap B_{1}(P)$ be the parts of the classes $B_{-1}(P)$, $B_1(P)$ in $X^0$. Furthermore, let $X_{-1}^+ := X^+ \cap B_{-1}(P)$ and $X_{1}^+ := X^+ \cap B_{1}(P)$ be the parts of the classes $B_{-1}(P)$ and $B_1(P)$ in $X^+$. We define $\d^* := \min\{2p^*,\frac \e {74}q^* (1-2q^*)\}$ and fix $\d\leq \d^*$. Since $P_X$ is regular \citep[cf.][p.~176]{Dud} there exist compact subsets $K_i^j$ of $X_i^j$ with $P_X(X_i^j \setminus K_i^j) \leq \d /4$ for $\iin$ and $\jin$. Moreover, for a fixed feature map $\P:X\to H$ of $k$ Proposition \ref {approxstep} ensures the existence of an element $w^*\in H$ with \begin{equation*} \langle w^*,\P(x) \rangle \quad\in\quad \begin{cases} [1,1+\d] & \mbox{ if } x\in K_1^0 \\ [-(1+\d),-1] & \mbox{ if } x\in K_{-1}^0 \\ [1-2p^*-\d, 1-2p^*] & \mbox{ if } x\in K_1^+ \\ [-(1-2p^*),-(1-2p^*-\d)] & \mbox{ if } x\in K_{-1}^+ \\ [-(1+\d),1+\d] & \mbox{ otherwise. } \end{cases} \end{equation*} We define $c^* := \frac 2 {\e(1-2q^*)} \xnorm{w^*} 2 2$ and for fixed $c\geq c^*$ let $\s := \frac \d{\sqrt c}$. By Lemma \ref{part} we then obtain partitions $\tilde {\ca P}_i^j$ of $K_i^j$ with $\diam_{d_k}(A) \leq \s$ for all $A\in \tilde {\ca P}_i^j$ and $$ \Bigl|\bigcup_{\substack{\iin\\ \jin}} \tilde {\ca P}_i^j\Bigr| \Leq \ca N\bigl((X,d_k),\s\bigr)\ = \ M\ . $$ Let $\ca P_i^j := \{ A \in \tilde {\ca P}_i^j : P_X(A) \geq \frac \d {q^*M}\}$ for $\iin$ and $\jin$. To construct ``representative'' training sets we define \begin{align*} F_{n,A} & := \Bigl\{\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr) \ : \ \bigl|\{l:x_l\in A\}\bigr| \geq \Bigl(P_X(A)-\frac \d M\Bigr)\, n\Bigr\} \intertext{for all $A\in \ca P_i^j$, $\iin$ and $\jin$. Moreover, for $A\in \ca P_i^+$, $\iin$ let} F^+_{n,A} & := \Bigl\{\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr) \ : \ \bigl|\{l:x_l\in A \mbox{ and } y_l=i\}\bigr| \geq \Bigl((1-p^*)P_X(A)-\frac \d M\Bigr)\, n\Bigr\}\\ F^-_{n,A} & := \Bigl\{\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr) \ : \ \bigl|\{l:x_l\in A \mbox{ and } y_l\neq i\}\bigr| \geq \Bigl(q^*P_X(A)-\frac \d M\Bigr)\, n\Bigr\}\\ F_n & := \bigcap_{A\in {\cal P}^0_{-1}\cup {\cal P}^0_1} F_{n,A} \quad \cap \bigcap_{A\in {\cal P}^+_{-1}\cup {\cal P}^+_1} \bigl(F_{n,A} \cap F_{n,A}^+ \cap F_{n,A}^-\bigr)\ . \end{align*} Lemma \ref{prob} yields $P^n(F_n) \geq 1- 3M e^{-2 \left(\frac \d M\right)^2 n}$ and thus it suffices to show that $$ \ca R_P (f^{2,k,c/n}_{T})\leq \ca R_P + 4 \frac{p^*-q^*}{1-2q^*}P_X(X^+) + \e $$ holds for all $T\in F_n$. Therefore, let us fix a training set $T=\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr)\in F_n$. For $c_n:= c/n$ we denote the solution of (\ref{prim2sno}) by $(w_T,b_T,\xi_T)$. Our first step is to estimate $\ca W(w_T,b_T,\xi_T)$ from above by comparing it with $\ca W(w^*,0,\xi^*)$, where $\xi^*$ is an admissible slack vector of $(w^*,0)$. Hence we have to construct $\xi^*$. For this let us first assume that we have a sample $(x_l,y_l) \in K_1^0$. Then we observe that $$ y_l\langle w^*,\P(x_l)\rangle \Eq \langle w^*, \P(x_l)\rangle \Geq 1 $$ and thus we may define $\xi_l^*:= 0$. Analogous considerations yield \begin{equation*} \xi_l^* \quad\Defi\quad \begin{cases} 0 & \mbox{ if } x_l\in K_i^0 \\ 2p^*+\d & \mbox{ if } x_l\in K_i^+, y_l=i \\ 2-2p^* & \mbox{ if } x_l\in K_i^+, y_l\neq i \\ 2+\d & \mbox{ otherwise. } \end{cases} \end{equation*} Moreover, our construction of $F_n$ guarantees that there are at most $$ n - n\sum_{\substack{\iin \\ \jin}} \sum_{A\in {\cal P}_i^j} \Bigl(P_X(A)-\frac \d M\Bigr) \Leq n \Bigl( 1-\sum_{\substack{\iin \\ \jin}} P_X(X_i^j) +\Bigl(2+ \frac 1 {q^*}\Bigr)\d\Bigr) \Eq \frac 2 {q^*}\d n $$ samples which are not elements of a suitable $K_i^j$. Furthermore, since there are at most $$ n-n\sum_{\iin} \sum_{A\in {\cal P}_i^0} \Bigl(P_X(A)-\frac \d M\Bigr) \Leq n\Bigl(P_X(X^+) +\frac 2 {q^*}\d\Bigr) $$ samples in $K^+:= K_1^+\cup K_{-1}^+$ we also obtain that there are at most $$ n\Bigl(P_X(X^+) +\frac 2 {q^*}\d\Bigr) - n\sum_{\iin} \sum_{A\in {\cal P}_i^+} \Bigl((1-p^*)P_X(A)-\frac \d M\Bigr) \Leq n \Bigl(p^* P_X(X^+) + \frac 4 {q^*}\d\Bigr) $$ samples in $K^+$ which have incorrect labels. Since these have larger slack variables with respect to $(w^*,0)$ than the correctly labeled samples in $K^+$ we obtain \begin{eqnarray}\nonumber \label{above} \!\!\!\!&&\!\! \ca W(w_T,b_T,\xi_T)\\ \nonumber \!\!\!\!& \leq &\!\! \ca W(w^*,0,\xi^*) \\ \nonumber \!\!\!\!&\leq & \!\!\langle w^*,w^*\rangle + \frac c n \sum_{\iin} \sum_{\substack{x_l\in K_i^+\\y_l=i}} (\xi_l^*)^2 + \frac c n \sum_{\iin} \sum_{\substack{x_l\in K_i^+\\y_l\neq i}} (\xi_l^*)^2 + 2\d c(2+\d)^2 \\ \nonumber \!\!\!\!&\leq &\!\! \langle w^*,w^*\rangle + c (1-p^*)P_X(X^+) (2p^*+\d)^2 + c\Bigl(p^* (P_X(X^+) + \frac 4 {q^*}\d\Bigr) (2-2p^*)^2 + 2 \d c(2+\d)^2 \\ \!\!\!\!&\leq &\!\! \langle w^*,w^*\rangle + c \Bigl( 4p^*(1-p^*)P_X(X^+) + \frac {27} {q^*}\d\Bigr)\ . \end{eqnarray} For later purposes we note that we also have $\ca W(w_T,b_T,\xi_T) \leq \ca W\bigl(0,0,(1,\dots,1)\bigr) \leq c$ and thus $\Norm{w_T}_2 \leq \sqrt c$. In the second step of the proof we estimate $\ca W(w_T,b_T,\xi_T)$ from below. For this let us denote the set of misclassified points in $X_i^j$ by $$ E_i^j \Defi \{x\in X_i^j : f_T(x) \neq i\} \ . $$ For brevity's sake we also write $E^j := E^j_1\cup E_{-1}^j$ and $E:= E^0 \cup E^+$. Let us first consider an $A\in \ca P_i^0$ with $A\cap E\neq \emptyset$. Without loss of generality we may assume that $i=1$. Then for $x_l\in A$ and $z\in A\cap E$ we obtain \begin{eqnarray*} 1-\x_T(l) &\leq& y_l\bigl(\langle w_T, \P(x_l)\rangle + b_T\bigr)\\ &= & \langle w_T,\P(x_l)-\P(z)\rangle + \langle w_T,\P(z)\rangle + b_T\\ &\leq & \snorm{ w_T}\ d_k(x_l,z)\\ &\leq& \d , \end{eqnarray*} i.e. $\xi_T^2(l) \geq (1-\d)^2 \geq 1-2\d$. Since the same estimate holds in the case $i=-1$ our construction of $F_n$ implies \begin{equation}\label{below1} \frac 1 n \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^0 \\ A\cap E\neq \emptyset}} \sum_{x_l\in A} \xi_T^2(l) \Geq \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^0 \\ A\cap E\neq \emptyset}} (1-2\d)\Bigl(P_X(A)-\frac \d M\Bigr) \Geq P_X(E^0) - \frac 3 {q^*}\d\ . \end{equation} Now let us consider an $A\in \ca P_i^+$ with $A\cap E\neq \emptyset$. Without loss of generality we may assume that $i=1$ again. Then for fixed $z\in A\cap E$ and $a:= -\bigl(\langle w_T,\P(z)\rangle + b_T\bigr)\geq 0$ we obtain \begin{equation*} \xi_T(l) \quad\Geq\quad \begin{cases} 1-\d+a & \mbox{ for } x_l\in A \mbox{ with } y_l=1\\ \max\{0,1-\d-a\} & \mbox{ for } x_l\in A \mbox{ with } y_l=-1\\ \end{cases} \end{equation*} analogously to the above considerations. We first treat the case $1-\d-a\geq 0$. Since there are at least $\bigl(P_X(A) - \d/M\bigr)n$ samples in $A$ and at least $\bigl((1-p^*)P_X(A) - \d/M\bigr)n$ correctly labeled samples in $A$ we get \begin{eqnarray*} \frac 1 n \sum_{x_l\in A} \xi_T^2(l) & \geq& (1-\d+a)^2 \Bigl((1-p^*)P_X(A)-\frac \d M\Bigr) + (1-\d-a)^2 p^* P_X(A) \\ & \geq & P_X(A) \bigl((1-\d+a)^2(1-p^*) + (1-\d-a)^2p^*\bigr) - \frac {4\d}M\ . \end{eqnarray*} Now an easy minimization with respect to $a\in [0,1-\d]$ yields $$ \frac 1 n \sum_{x_l\in A} \xi_T^2(l) \Geq P_X(A) \bigl((1-\d)^2(1-p^*) + (1-\d)^2p^*\bigr) - \frac {4\d}M \Geq (1-2\d)P_X(A) -\frac {4\d}M \ . $$ On the other hand, if $1-\d-a < 0$ we have $1-\d+a > 2-2\d$ and thus the same inequality follows: $$ \frac 1 n \sum_{x_l\in A} \xi_T^2(l) \Geq (1-\d+a)^2 \Bigl((1-p^*)P_X(A)-\frac \d M\Bigr) \Geq (1-2\d)P_X(A) -\frac {4\d}M\ . $$ Therefore, we obtain \begin{equation}\label{below2} \frac 1 n \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E\neq \emptyset}} \sum_{x_l\in A} \xi_T^2(l) \Geq \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E\neq \emptyset}} \Bigl((1-2\d)P_X(A)-\frac {4\d} M\Bigr) \ . \end{equation} Finally, an analogous consideration yields \begin{equation}\label{below3} \frac 1 n \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E= \emptyset}} \sum_{x_l\in A} \xi_T^2(l) \Geq \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E=\emptyset}} \Bigl((1-2\d)4q^*(1-q^*)P_X(A)-\frac {4\d} M\Bigr) \ . \end{equation} Now, the estimates (\ref{below2}) and (\ref{below3}) imply \begin{eqnarray*} \!\!\!\!&& \!\!\frac 1 n \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E\neq \emptyset}} \sum_{x_l\in A} \xi_T^2(l) + \frac 1 n \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E= \emptyset}} \sum_{x_l\in A} \xi_T^2(l) \\ \!\!\!\!& \geq &\!\! \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E\neq \emptyset}} \Bigl((1-2\d)P_X(A)-\frac {4\d} M\Bigr) +\!\! \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E=\emptyset}} \Bigl((1-2\d)4q^*(1-q^*)P_X(A)-\frac {4\d} M\Bigr)\\ \!\!\!\!& \geq &\!\! \sum_{\iin}\sum_{\substack{A\in {\cal P}_i^+ \\ A\cap E\neq \emptyset}} (1-2\d)(1-2q^*)^2 P_X(A) + \sum_{\substack{\iin \\ A\in {\cal P}_i^+ }} (1-2\d)4q^*(1-q^*)P_X(A) - 4\d\\ \!\!\!\!& \geq &\!\! (1-2\d)(1-2q^*)^2 P_X(E^+) + (1-2\d)4q^*(1-q^*) P_X(X^+) - 6\d - \frac 2 {q^*}\d\\ \!\!\!\!& \geq &\!\! (1-2q^*)^2 P_X(E^+) + 4q^*(1-q^*) P_X(X^+) - \frac 7 {q^*}\d\ . \end{eqnarray*} The latter inequality together with (\ref{below1}) yields $$ \frac 1 n \sum_{l=1}^n \xi_T^2(l) \geq P_X(E^0) + (1-2q^*)^2 P_X(E^+) + 4q^*(1-q^*) P_X(X^+) - \frac {10} {q^*}\d\ . $$ Combining this estimate with (\ref{above}) we now obtain \begin{eqnarray}\nonumber\label{togeth1} &&\langle w^*,w^*\rangle\\ & \geq & c\, \Bigl(P_X(E^0) + (1-2q^*)^2 P_X(E^+) + 4q^*(1-q^*) P_X(X^+) - 4p^*(1-p^*)P_X(X^+) - \frac {37} {q^*}\d\Bigr)\nonumber\\ & \geq & c^* \Bigl(P_X(E^0) + (1-2q^*)^2 P_X(E^+) - 4(p^*-q^*)P_X(X^+) - \frac {37} {q^*}\d\Bigr) \ . \end{eqnarray} Moreover, a simple calculation shows $$ \ca R_P(f_T^{2,k,c/n}) \Eq \ca R_P + \Int_E (1-2p)\, dP_X \Leq \ca R_P + \frac 1 {1-2q^*} \Bigl( P_X(E^0) + (1-2q^*)^2P_X(E^+)\Bigr) $$ and thus $P_X(E^0) + (1-2q^*)^2P_X(E^+) \geq (1-2q^*) (\ca R_P(f_T^{2,k,c/n}) -\ca R_P)$. With this and (\ref{togeth1}) we find $$ \langle w^*,w^*\rangle \Geq \frac {2\, \langle w^*,w^*\rangle}{\e(1-2q^*)} \Bigl( (1-2q^*) \bigl(\ca R_P(f_T^{2,k,c/n})-\ca R_P\bigr) - 4(p^*-q^*)P_X(X^+) - \frac {37} {q^*}\d\Bigr)\ . $$ The latter inequality finally implies \begin{eqnarray*} \ca R_P(f_T^{2,k,c/n}) - \ca R_P &\leq& \frac \e 2 + 4 \frac {p^*-q^*}{1-2q^*} P_X(X^+) + \frac {37}{(1-2q^*)q^*} \, \frac {\e(1-2q^*)q^*}{74} \\ & = & 4 \frac {p^*-q^*}{1-2q^*} P_X(X^+) + \e\ . \end{eqnarray*} Thus the assertion follows. \end{proofo} \newpage \noindent We have to prove the remaining lemmas now. We begin with the lemma that constructs the partitions $\ca P_i^j$ of the above proof: \begin{lemma}\label{part} Using the notations of the proof of Theorem \ref{HS1} there exist partitions $\ca P_i^j$ of $K_i^j$, $\iin$, $\jin$, such that $\diam_{d_k}(A) \leq \s$ for all $A\in \ca P_i^j$, $\iin$, $\jin$, and \begin{equation}\label{cardpart} \Bigl|\bigcup_{\substack{\iin\\ \jin}} \ca P_i^j\Bigr| \Leq \ca N\bigl((X,d_k),\s\bigr)\ . \end{equation} \end{lemma} \begin{proof} By the definition of the covering numbers there exists a partition $\ca P$ of $X$ with $\diam_{d_k}(A) \leq \s$ for all $A\in \ca P$ and $|\ca P| \leq \ca N \bigl((X,d_k),\s\bigr)$. Let us define $\tilde{\cal P}_i^j := \{ A\in \ca P: A\cap K_i^j \neq \emptyset\}$ and $\ca P_i^j := \{ A\cap K_i^j : A \in \tilde{\cal P}_i^j\}$. Therefore, to prove (\ref{cardpart}) we have to show that the $\tilde {\cal P}_i^j$'s are mutually disjoint. Assume the converse, i.e. there exists $A\in \tilde {\cal P}_i^j \cap \tilde {\cal P}_{i'}^{j'}$ with $i\neq i'$ or $j \neq j'$. By the definition of the partitions there exist $z_1,z_2\in A$ with $z_1\in K_i^j$ and $z_2\in K_{i'}^{j'}$. Now on the one hand, we obtain $$ |\langle w^*,\P(z_1)-\P(z_2)\rangle| \Leq \Norm{w^*} d_k(z_1,z_2) \Leq \Norm{w^*} \s \Leq \Norm{w^*} \frac \d{\sqrt{c^*}}\ <\ \d $$ but on the other hand we also have $$ |\langle w^*,\P(z_1)-\P(z_2)\rangle| \Eq |\langle w^*,\P(z_1)\rangle - \langle w^*,\P(z_2)\rangle| \Geq 1-(1-2p^*) \Geq \d^* \Geq \d\ . $$ Therefore the assertion follows. \end{proof} \begin{lemma}\label{prob} Using the notations of the proof of Theorem \ref{HS1} we have $$ P^n(F_n) \geq 1- 3M e^{-2 \left(\frac \d M\right)^2 n}\ . $$ \end{lemma} \begin{proof} Let us recall Hoeffding's inequality \citep[cf.][Thm.~8.1]{DGL} which in particular states that for all i.i.d.\ random variables $z_i:(\Om,\ca A,Q) \to \{0,1\}$ and all $\e>0$, $n\geq 1$ we have $$ Q^n \Bigl( \sum_{i=1}^n z_i \leq n(q-\e)\Bigr) \Leq e^{-2\e^2n}\ , $$ where $q:= Q(z_i=1)$. Thus for $A\in \ca P_i^+$ we get \begin{eqnarray*} &&P^n(F_{n,A}^+)\\ & \geq & P^n\Bigl(\!\Bigl\{\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr) : \bigl|\{l:x_l\in A, y_l=i\}\bigr| \geq \Bigl(\int_A(1-p)\, dP_X-\frac \d M\Bigr)\, n\Bigr\}\!\Bigl)\\ & \geq & 1- P^n\Bigl(\!\Bigl\{\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr) : \bigl|\{l:x_l\in A, y_l=i\}\bigr| \leq \Bigl(\int_A(1-p)\, dP_X-\frac \d M\Bigr)\, n\Bigr\}\!\Bigl)\\ & \geq & 1- e^{-2\left(\frac \d M\right)^2n}\ , \end{eqnarray*} i.e. $P^n(Z^n\setminus F_{n,A}^+) \leq e^{-2\left(\frac \d M\right)^2n}$, where $Z := X\times Y$. Analogously, we obtain $P^n(Z^n\setminus F_{n,A}^-) \leq e^{-2\left(\frac \d M\right)^2n}$ for all $A\in \ca P_i^+$ and $P^n(Z^n\setminus F_{n,A}) \leq e^{-2\left(\frac \d M\right)^2n}$ for all $A\in \ca P_i^j$. These estimates yield \begin{eqnarray*} &&P^n(F^n)\\ & = & P^n\Bigl( \bigcap_{A\in {\cal P}^0_{-1}\cup {\cal P}^0_1} F_{n,A} \quad \cap \bigcap_{A\in {\cal P}^+_{-1}\cup {\cal P}^+_1} \bigl(F_{n,A} \cap F_{n,A}^+ \cap F_{n,A}^-\bigr) \Bigr)\\ & = & 1- P^n\Bigl( \bigcup_{A\in {\cal P}^0_{-1}\!\cup\!\!\!\!\!\! {\cal P}^0_1} \bigl(Z^n\setminus F_{n,A}\bigl) \quad \cup\! \bigcup_{A\in {\cal P}^+_{-1}\cup {\cal P}^+_1}\! \bigl(\bigl(Z^n\setminus F_{n,A}\bigl) \cup \bigl(Z^n\setminus F_{n,A}^+\bigl) \cup \bigl(Z^n\setminus F_{n,A}^-\bigl)\bigr)\!\Bigr)\\ & \geq & 1- \sum_{\substack{A\in {\cal P}^j_{-1}\cup {\cal P}^j_1\\ \jin }} P^n\bigl(Z^n\setminus F_{n,A}\bigl) - \sum_{\substack{A\in {\cal P}^+_{-1}\cup {\cal P}^+_1}} P^n\bigl(Z^n\setminus F_{n,A}^+\bigl) - \sum_{\substack{A\in {\cal P}^+_{-1}\cup {\cal P}^+_1}} P^n\bigl(Z^n\setminus F_{n,A}^-\bigl)\\ & \geq & 1 - 3M e^{-2 \left(\frac \d M\right)^2 n}\ . \end{eqnarray*} \end{proof} \noindent With the help of Theorem \ref{HS1} we can now investigate how to choose the parameter sequence $(c_n)$ for a given universal kernel: \begin{theorem}\label{HS2} Let $(X,d)$ be a compact metric space and $k$ be a universal kernel on $X$ such that the covering numbers of $(X,d_k)$ fulfill $\ca N\bigl((X,d_k),\e\bigr)\in \ca O(\e^{-\a})$ for some $\a>0$. Suppose that we have a positive sequence $(c_n)$ with $(c_n)\in \ca O(n^{\b-1})$ for some $0<\b<\frac 1 \a$ and $n c_n \to \infty$. Then for all Borel probability measures $P$ on $X\times Y$ with $q^*,p^*\in (0,1/2)$ and all $\e>0$ we have \begin{displaymath} \lim_{n\to \infty}\opa \Bigl(\Bigl\{T\in (X\times Y)^n : \ca R_P (f^{2,k,c_n}_{T})\leq \ca R_P + 4 \frac{p^*-q^*}{1-2q^*}P_X(X^+) + \e\Bigr\}\Bigr) \Eq 1\ . \end{displaymath} \end{theorem} \begin{proof} Let $\g := \frac{1-\a\b}{4(1+\a)} > 0$ and $\d_n:= n^{-\g}$. By Theorem \ref{HS1} there exist $c^*>0$ and $\d^*>0$ such that for all $c\geq c^*$, $0<\d\leq \d^*$ and all $n\geq 1$ we have \begin{displaymath} \opa \Bigl(\Bigl\{T\in (X\times Y)^n : \ca R_P (f^{2,k,c/n}_{T})\leq \ca R_P + 4 \frac{p^*-q^*}{1-2q^*}P_X(X^+) + \e\Bigr\}\Bigr) \Geq 1 - 3M e^{-2 \left(\frac \d M\right)^2 n}\ , \end{displaymath} where $M := \ca N\bigl((X,d_k),\frac \d {\sqrt c}\bigr)$. Since $\d_n\to 0$ and $nc_n\to \infty$ we may fix an $n_0\geq 1$ such that for all $n\geq n_0$ we have both $\d_n\leq \d^*$ and $nc_n \geq c^*$. This yields \begin{displaymath} \opa \Bigl(\Bigl\{T\in (X\times Y)^n : \ca R_P (f^{2,k,c_n}_{T})\leq \ca R_P + 4 \frac{p^*-q^*}{1-2q^*}P_X(X^+) + \e\Bigr\}\Bigr) \Geq 1 - 3M_n e^{-2 \left(\frac {\d_n} {M_n}\right)^2 n}\ , \end{displaymath} where $M_n := \ca N\bigl((X,d_k),\frac {\d_n} {\sqrt {nc_n}}\bigr)$. This implies $M_n\in \ca O(n^{\a(\g+\b/2)})$ and hence we easily check that $M_n e^{- \left(\frac {\d_n} {M_n}\right)^2 n}\in \ca O(e^{-n^{2(1+\a)\g}})$ holds. Thus the assertion follows. \end{proof} \begin{corollary} Under the assumptions of Theorem \ref{HS2} the 2-SMC with sequence $(c_n)$ is consistent for all Borel probability measures $P$ on $X\times Y$ with $q^*=p^*< 1/2$. In particular this holds for all Borel probability measures with constant noise level. \end{corollary} \begin{corollary}\label{Cor1} Let $X\subset \R^d$ be compact and $k$ be a Gaussian RBF kernel on $X$. Let $0<\b<\frac 1 d$ and $(c_n)$ be a positive sequence with $(c_n)\in \ca O(n^{\b-1})$ and $n c_n \to \infty$. Then the 2-SMC with kernel $k$ and sequence $(c_n)$ is consistent for all Borel probability measures $P$ on $X\times Y$ with $q^*=p^*< 1/2$. \end{corollary} \begin{proof} Let $\s>0$ and $k(x,y) := \exp(-\s^2\xnorm{x-y} 2 2)$. Since $1-e^{-t} \leq t$ for all $t\geq 0$ we observe $$ d_k(x,y) \Eq \sqrt{2-2\exp(-\s^2\xnorm{x-y} 2 2)} \Leq \sqrt 2 \s \ynorm{x-y} 2 \ . $$ This yields $\ca N\bigl((X,d_k),\e\bigr) \leq \ca N\bigl((X,\ynorm . 2),\frac \e{\sqrt 2 \s}\bigr)$ and thus $\ca N\bigl((X,d_k),\e\bigr)\in \ca O(\e^{-d})$ \citep*[cf.][p.~9]{C-S}.\end{proof} \noindent For the classification problems we have considered up to now we usually may not expect that we obtain a large margin for sample sizes growing to infinity. In the following we restrict ourselves to distributions that guarantee a fixed and strictly positive margin for all training sets. Of course, these classification problems must have a deterministic supervisor, i.e.\ a noise level that vanishes (almost) everywhere. In general, additional assumptions are required. Using universal kernel these reduce to a simple geometric condition: \begin{theorem}\label{HS3} Let $(X,d)$ be a compact metric space and $k$ be a universal kernel on $X$. Suppose that we have a Borel probability measure $P$ on $X\times Y$ with a deterministic supervisor and with classes $B_{-1}(P),B_1(P)$ which have strictly positive distance, i.e. $d\bigl(B_{-1}(P),B_1(P)\bigr)>0$. Then $k$ separates $B_{-1}(P)$ and $B_1(P)$ with margin $\g>0$ and for all $c>0$, $\e>0$ and $n\geq mM$ we have \begin{displaymath} \opa\bigl(\{T\in (X\times Y)^n : \ca R_{P,S} (f^{2,k,c}_{T}) \leq \e \}\bigr) \Geq 1-M\ e^{-\frac {\e n}{2 M}+m}\ . \end{displaymath} Here, $M:= \ca N\bigr((X,d_k),\g/2\bigl)$ is the covering number of $(X,d_k)$ and $m:=\bigl\lfloor \frac 4 {c\g^2} \bigr\rfloor + 1$. \end{theorem} \begin{proof} Since $(X,d_k)$ is precompact and $d\bigl(B_{-1}(P),B_1(P)\bigr)>0$ both $B_i(P)$ are compact, too. Thus they can be separated with margin $\g>0$ by Corollary \ref{sepcpct}. In analogue to Lemma \ref{part} we now construct partitions $\tilde{\ca P}_i$ of $B_i(P)$, $\iin$ such that $\diam_{d_k}(A) \leq \g/2$ for all $A\in \tilde{\ca P}_i$ and $\bigl|\tilde{\ca P}_{-1} \cup \tilde{\ca P}_1\bigr| \leq M$. We define ${\cal P}_i := \{A\in \tilde{{\cal P}}_i: P_X(A) >\frac \e M\}$ for $\iin$. Moreover, for $n\geq mM$ and $A\in {\cal P}_{-1}\cup {\cal P}_1$ let \begin{eqnarray*} F_{n,A} & := & \Bigl\{\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr)\in (X\times Y)^n \ : \ \bigl|\{l:x_l\in A\}\bigr| \geq m\Bigr\}\\ F_n & := & \bigcap_{A\in {\cal P}_{-1}\cup {\cal P}_1} F_{n,A}\ . \end{eqnarray*} For $n\geq mM$ the Chernoff-Okamoto inequality \citep[see e.g.][]{Dud2} then yields \begin{eqnarray*} P^n\bigl((X\times Y)^n\setminus F_{n,A}\bigr) &\leq & \exp\Bigl(- \frac{\bigl(n \frac \e M - (m-1)\bigr)^2}{2n\frac \e M\bigl(1-\frac \e M\bigr)}\Bigr)\\ & \leq & \exp\Bigl(- \frac{n^2\bigl(\frac \e M\bigr)^2 - 2 n \frac \e M (m-1) + (m-1)^2}{2n\frac \e M}\Bigr)\\\ & \leq & \exp\bigl(- \frac {\e n}{2 M}+ m\bigr) \end{eqnarray*} and thus $P^n(F_n) \geq 1-M\ e^{-\frac {\e n}{2 M}+m}$ for all $n\geq mM$. Hence it suffices to show that for all $T=\bigl((x_1,y_1),\dots,(x_n,y_n)\bigr) \in F_n$ the decision function $f^{2,k,c}_T$ classifies $\bigcup_{A \in {\cal P}_1} A$ and $\bigcup_{A\in {\cal P}_{-1}} A$ correctly. To see this we fix a feature map $\P:X\to H$ of $k$. For brevity's sake the unique solution of problem (\ref{prim2sno}) is denoted by $(w_T,b_T,\xi_T)$. Furthermore, $(w^*,b^*)\in S_H\times \R$ is a hyperplane that separates $\P\bigl(B_1(P)\bigr)$ and $\P\bigl(B_{-1}(P)\bigr)$ with margin $\g>0$. Then we have $y_l\bigl(\langle{w^*},\P(x_l)\rangle +{b^*}\bigr)\geq \g$ for all $l=1,\dots,n$ and therefore we obtain \begin{displaymath} \langle w_T,w_T\rangle + c\sum_{l=1}^n\x_l^2 \Leq \Bigl\langle \frac {w^*}\g,\frac {w^*}\g\Bigr\rangle \Eq \frac 1 {\g^2}\ . \end{displaymath} In particular this implies $\snorm{w_T}\leq 1/ \g$. Now, let us suppose that there exists a misclassified point $z$. Without loss of generality we may assume that $z\in \bigcup_{A \in {\cal P}_1} A$. Hence there is an $A\in {\cal P}_1$ with $z\in A$ and for this there exist mutually different indexes $l_1,\dots,l_m$ such that $x_{l_j}\in A$. In particular this yields $d_k(x_{l_j},z)\leq \g/ 2$ for all $j=1,\dots,m$. Since $\langle w_T,\P(z)\rangle +b_T \leq 0$ we thus obtain $$ 1-\x_{l_j} \Leq \langle w_T,\P(x_{l_j})\rangle +b_T \Eq \langle w_T,\P(x_{l_j})-\P(z)\rangle + \langle w_T,\P(z)\rangle +b_T \Leq \snorm{w_T}\ d_k(x_{l_j},z) \Leq \frac 1 2 . $$ Hence we have $\x_{l_j}\geq 1/2$ and this leads to the contradiction $$ \frac 1 {\g^2} \Geq \langle w_T,w_T\rangle + c\sum_{l=1}^n\x_l^2 \Geq c \sum_{j=1}^m \x_{l_j}^2 \Geq \frac{cm} 4 \Eq \frac c 4 \Bigl(\Bigl \lfloor \frac 4 {c\g^2} \Bigr\rfloor + 1 \Bigr) \ > \ \frac 1 {\g^2} \ . $$ Therefore the assertion follows. \end{proof} \noindent Theorem \ref{HS3} shows that the 2-SMC works well with fixed weight factor $c$ whenever it treats a classification problem that ensures a large margin. We believe that these distributions are also the only ones for which a fixed $c$ is suitable. Our conjecture is based on the observation that the constant $c$ controls the Lipschitz constant of the solution of (\ref{prim2sno}) with respect to the metric $d_k$: if we have a classification problem that does not guarantee a large margin the Lipschitz constant may grow like $n$. The proofs of this section indicate that this may be too fast since for large sample sizes the solution need not be ``almost'' constant on each element of the partitions, i.e. overfitting may occur. In the proof of the above theorem we only used elements of the partitions $\ca P_i$ whose probability was larger than or equal to $\frac \e M$. If we extend our considerations to all elements with strictly positive probability we obtain the following theorem: \begin{theorem}\label{HS4} Let $(X,d)$ be a compact metric space and $k$ a universal kernel on $X$. Suppose that we have a Borel probability measure $P$ on $X\times Y$ with a deterministic supervisor and with classes $B_{-1}(P),B_1(P)$ which have strictly positive distance, i.e. $d\bigl(B_{-1}(P),B_1(P)\bigr)>0$. Then $k$ separates $B_{-1}(P)$ and $B_1(P)$ with margin $\g>0$ and for all $c>0$ there exists a constant $\rho > 0$ such that for all $n\geq \bigl(\bigl\lfloor \frac 4 {c\g^2} \bigr\rfloor + 1\bigr)\ca N\bigr((X,d_k),\g/2\bigl) $ we have \begin{displaymath} \opa\bigl(\{T\in (X\times Y)^n : \ca R_{P,S} (f^{2,k,c}_{T}) = 0 \}\bigr) \Geq 1- e^{-\rho n}\ , \end{displaymath} \end{theorem} \noindent Up to now we have only treated universal kernels. One may ask whether other classes of kernels are also suitable to treat with the classification problems considered in this work. One type often used are polynomial kernels of the form $(\langle .,.\rangle +c)^m$, $c\geq 0$, $m\in \N$, on a subset $X$ of $\Rn$. For these kernels the functions generated by the 2-SMC are polynomials on $X$ of degree up to $m$. Thus the next proposition shows that these kernels are not even capable to solve the problems of Theorems \ref{HS3} and \ref{HS4}: \begin{proposition}\label{Pro1} Let ${\cal P}_n^d$ be the set of all polynomials on $X:=[0,1]^d$ whose degree is less than $n+1$. Then for all $\e>0$ there exists a Borel probability measure $P$ on $X\times Y$ with $d\bigl(B_1(P),B_{-1}(P)\bigr)>0$, $\ca R_{P}=0$ and $$ \inf\{\ca R_{P}(\sign f) \ : \ f\in {\cal P}_n^d\} \Geq \frac 1 2 -\e\ . $$ \end{proposition} \begin{proof} We first treat the case $d=1$. We fix an integer $m\geq (3n+2)/\e$ and let $I_i:= [(i+\e)/ m,(i+1-\e)/m]$, $i=0,\dots,m-1$. Denoting the Lebesgue measure on $I_i$ by $\lb_{I_i}$ let $P_X:= ({1-2\e})^{-1}\sum_{i=0}^{m-1}\lb_{I_i}$. Moreover, we define a deterministic supervisor $P(.|.)$ by $P(y=1|x) := 1$ for $x\in I_{2i}$, $i=0,\dots,\lfloor ( {m+1})/ 2\rfloor$, and $P(y=-1|x) := 1$ otherwise. For a fixed polynomial $f\in {\cal P}_n^d$ we denote its mutually different and ordered zeroes in $(0,1)$ by $x_1< \ldots 1$ we have to embed $[0,1]$ into $[0,1]^d$ via $t\mapsto (t,0,\dots,0)$. Considering the above distribution $P$ embedded into $[0,1]^d$ we then get the assertion since polynomials in $d$ variables on $[0,1]$ embedded into $[0,1]^d$ as above are essentially polynomials in one variable. \end{proof} \section{The 1-norm soft margin classifier}\label{1smc} We now consider the 1-norm soft margin classifier. Again we fix a kernel $k$ on $X$ with feature map $\P:X\to H$. For a training set $T = ((x_1,y_1),\dots,(x_n,y_n)) \in (X\times Y)^n$ and $c_n>0$ we denote a solution of the optimization problem \begin{equation}\label{prim1sno} \begin{array}{rll} \!\!\!\!\!\!\mbox{minimize} & \qquad \langle w,w\rangle + c_n\Sum_{i=1}^n\x_i & \qquad \mbox{over } w,b,\x\\ \!\!\!\!\!\!\mbox{subject to} & \qquad y_i(\langle w,\P(x_i)\rangle +b) \geq 1-\x_i, & \qquad i=1,\dots,n\\ & \qquad \x_i \geq 0, & \qquad i=1,\dots,n \end{array} \end{equation} by $(w_{T}^{1,k,c_n},b_T^{1,k,c_n})\in H\times \R$. An algorithm $\ca C_k^{1,(c_n)}$ that provides the decision function $$ f_T^{1,k,c}(x):= \sign(\langle w_T^{1,k,c_n},\P(x)\rangle +b_T^{1,k,c_n})\ , \qquad \qquad x\in X $$ for every training set $T$ is called a 1-norm soft margin classifier (1-SMC) with kernel $k$ and parameter sequence $(c_n)$. For an introduction to the 1-SMC as well as for implementation techniques we refer to \citet*[][Ch.~6 and 7]{CST} and \citet[][Ch.~10]{Vap} \citet*{BC} proved that in general the optimization problem (\ref{prim1sno}) has no unique solution. Although the 1-SMC only has to construct an arbitrary {\em solution} we show in this section that it enjoys all the properties of the 2-SMC proven in this work. We begin with a statement which is analogous to Theorem \ref{HS1}: \begin{theorem}\label{HS5} Let $(X,d)$ be a compact metric space and $k$ be a universal kernel on $X$. Then for all Borel probability measures $P$ on $X\times Y$ with $q^*,p^*\in (0,1/2)$ and all $\e>0$ there exist $c^*>0$ and $\d^*>0$ such that for all $c\geq c^*$, $0<\d\leq\d^*$ and all $n\geq 1$ we have \begin{displaymath} \opa \Bigl(\Bigl\{T\in (X\times Y)^n : \ca R_P (f^{1,k,c/n}_{T})\leq \ca R_P + 4 \frac{p^*-q^*}{1-2q^*}P_X(X^+) + \e\Bigr\}\Bigr) \Geq 1 - 3M e^{-2 \left(\frac \d M\right)^2 n}\ , \end{displaymath} where $M := 4 \ca N\bigl((X,d_k),\frac \d {\sqrt c}\bigr)$ is essentially the covering number of $X$ with respect to the metric $d_k$ which is induced by the kernel $k$. \end{theorem} \begin{proofs} Since the proof is very similar to that of Theorem \ref{HS1} we only point out the main differences besides adjusting the constants: Firstly the vector $w^* \in H$ has to be chosen in a different manner, namely it has to fulfill \begin{equation*} \langle w^*,\P(x) \rangle \quad\in\quad \begin{cases} i\,[1,1+\d] & \mbox{ if } x\in K_i^j \\ [-(1+\d),1+\d] & \mbox{ otherwise. } \end{cases} \end{equation*} This condition also enforces the second modification since Lemma \ref{part} does not hold anymore in this setting. Indeed, we cannot guarantee that the definition of the $\tilde {\ca P}_i^j$'s in Lemma \ref{part} implies that they are mutually disjoint. Instead, we only obtain $|\tilde {\ca P}_i^j| \leq N\bigl((X,d_k),\frac \d {\sqrt c}\bigr)$ and thus \begin{equation*} \Bigl|\bigcup_{\substack{\iin\\ \jin}} \ca P_i^j\Bigr| \Leq 4\ca N\bigl((X,d_k),\s\bigr)\ . \end{equation*} The latter explains the definition of $M$, which is different to that of Theorem \ref{HS1}. \end{proofs} \noindent Following the proof of Theorem \ref{HS2} we obtain an analogous result for the 1-SMC: \begin{theorem}\label{HS6} Let $(X,d_k)$ be a compact metric space and $k$ be a universal kernel on $X$ such that the covering numbers of $(X,d_k)$ fulfill $\ca N\bigl((X,d_k),\e\bigr)\in \ca O(\e^{-\a})$ for some $\a>0$. Suppose that we have a positive sequence $(c_n)$ with $(c_n)\in \ca O(n^{\b-1})$ for some $0<\b<\frac 1 \a$ and $n c_n \to \infty$. Then for all Borel probability measures $P$ on $X\times Y$ with $q^*,p^*\in (0,1/2)$ and all $\e>0$ we have \begin{displaymath} \lim_{n\to \infty}\opa \Bigl(\Bigl\{T\in (X\times Y)^n : \ca R_P (f^{1,k,c_n}_{T})\leq \ca R_P + 4 \frac{p^*-q^*}{1-2q^*}P_X(X^+) + \e\Bigr\}\Bigr) \Eq 1 \end{displaymath} \end{theorem} \noindent To complete our considerations of noisy problems we mention that for the 1-SMC with Gaussian RBF kernel we obtain the following consistency result which has already been proved for the 2-SMC: \begin{corollary}\label{Cor3} Let $X\subset \R^d$ be compact and $k$ be a Gaussian RBF kernel on $X$. Let $0<\b<\frac 1 d$ and $(c_n)$ be a positive sequence with $(c_n)\in \ca O(n^{\b-1})$ and $n c_n \to \infty$. Then the 1-SMC with kernel $k$ and sequence $(c_n)$ is consistent for all Borel probability measures $P$ on $X\times Y$ with $q^*=p^*< 1/2$. \end{corollary} \noindent In the presence of large margins it turns out that we may fix the weight factor analogously to the 2-SMC. For brevity's sake we only state a result that is similar to Theorem \ref{HS3}. However, a result that is analogous to Theorem \ref{HS4} also holds. \begin{theorem}\label{HS7} Let $(X,d)$ be a compact metric space and $k$ a universal kernel on $X$. Suppose that we have a Borel probability measure $P$ on $X\times Y$ with a deterministic supervisor and with classes $B_{-1}(P),B_1(P)$ which have strictly positive distance, i.e. $d\bigl(B_{-1}(P),B_1(P)\bigr)>0$. Then $k$ separates $B_{-1}(P)$ and $B_1(P)$ with margin $\g>0$ and for all $c>0$, $\e>0$ and $n\geq mM$ we have \begin{displaymath} \opa\bigl(\{T\in (X\times Y)^n : \ca R_{P,S} (f^{1,k,c}_{T}) \leq \e \}\bigr) \Geq 1-M\ e^{-\frac {\e n}{2 M}+m}\ , \end{displaymath} where $M:= \ca N\bigr((X,d_k),\g/2\bigl)$ is the covering number of $(X,d_k)$ and $m:=\bigl\lfloor \frac 2 {c\g^2} \bigr\rfloor + 1$. \end{theorem} \begin{proofs} The proof is completely analogous to that of Theorem \ref{HS3}. However, since the slack variables are not squared we obtain $$ c \sum_{j=1}^m \xi_{l_j} \Geq \frac {cm}2 $$ in the last estimate of the proof of Theorem \ref{HS3} and this yields the slightly better value of $m$. \end{proofs} \noindent Finally we mention that using polynomial kernels Proposition \ref{Pro1} can also be applied. Thus problems that cannot be treated well with a fixed polynomial kernel and the 2-SMC cannot be treated well with the 1-SMC and the same kernel, either (and vice versa). \section{The maximal margin hyperplane classifier}\label{mmh} We finally consider the maximal margin classifier. Again we fix a kernel $k$ on $X$ with feature map $\P:X\to H$. For a training set $T = ((x_1,y_1),\dots,(x_n,y_n)) \in (X\times Y)^n$ we denote the unique solution of the optimization problem \begin{equation} \begin{array}{rll} \!\!\!\!\!\!\mbox{minimize} & \qquad \langle w,w\rangle \qquad &\mbox{over } w,b\\ \!\!\!\!\!\!\mbox{subject to} & \qquad y_i(\langle w,\P(x_i)\rangle +b) \geq 1, \qquad & i=1,\dots,n \end{array} \end{equation} by $(w_{T}^k,b_T^k)\in H\times \R$. An algorithm $\ca C_k$ that provides the decision function $$ f_T^k(x):= \sign(\langle w_T^k,\P(x)\rangle +b_T^k)\ , \qquad \qquad x\in X $$ for every training set $T$ is called a maximal margin classifier (MMC) with kernel $k$. For an introduction to the MMC as well as for implementation techniques and a geometric motivation we again refer to \citet*[][Ch.~6 and 7]{CST} and \citet*[][Ch.~10]{Vap}. The MMC is assumed to work poorly in the absence of large margins \citep*[cf.][]{TZ}. Thus we only consider the setting of Theorem \ref{HS3}. We begin with a result similar to Theorem \ref{HS3} and Theorem \ref{HS7}: \begin{theorem}\label{HS8} Let $(X,d)$ be a compact metric space and $k$ a universal kernel on $X$. Suppose that we have a Borel probability measure $P$ on $X\times Y$ with a deterministic supervisor and with classes $B_{-1}(P),B_1(P)$ which have strictly positive distance, i.e. $d\bigl(B_{-1}(P),B_1(P)\bigr)>0$. Then $k$ separates $B_{-1}(P)$ and $B_1(P)$ with margin $\g>0$ and for all $\e>0$ and $n\geq M:= \ca N\bigr((X,d_k),\g/2\bigl)$ we have \begin{displaymath} \opa\bigl(\{T\in (X\times Y)^n : \ca R_{P,S} (f_{T}^k) \leq \e \}\bigr) \Geq 1-M\ e^{n \ln\left(1-\frac \e {2M}\right) }\ . \end{displaymath} \end{theorem} \begin{proofs} We repeat the construction of the proof of Theorem \ref{HS3} with $m:= 1$. An easy calculation then shows $$ P^n(F_n) \Geq 1 - M\ e^{n \ln\left(1-\frac \e {2M}\right) }\ . $$ Now suppose that for $T\in F_n$ we have an element $z\in \bigcup_{A \in {\cal P}_1} A$ misclassified by $f_T^k$. Hence there exist an $A\in {\cal P}_1$ with $z\in A$ and a sample $(x_l,y_l)$ of $T$ with $x_l \in A$. Then the following estimate yields a contradiction: $$ 0 \Geq \langle w_T^k,\P(z)\rangle +b_T^k \Eq \langle w_T^k,\P(z)-\P(x_{l_j})\rangle + \langle w_T^k,\P(x_{l_j})\rangle +b_T^k \Geq \snorm{w_T^k}\ d_k(x_{l_j},z) + 1 \Geq \frac 1 2\ . $$ Therefore the assertion follows. \end{proofs} \noindent The above result and its proof indicate that in the presence of large margins it may be more suitable to use the MMC instead of a soft margin algorithm. We mention that an estimate which is very similar to Theorem \ref{HS8} can be obtained using data-dependent margin-based bounds of \citet{SBWA}. To compare both we first state a corollary: \begin{corollary}\label{Cor4} Let $k_\s$ be the Gaussian RBF kernel with parameter $\s$ on the unit ball $X:= B_{\ell_2^d}$ of the $d$-dimensional Euclidean space. Let $P$ be a Borel probability measure on $X\times Y$ which can be separated by $k_\s$ with margin $\g>0$. Then for all $\d\in (0,1)$ and all $n\geq 2 \bigl(\frac{16\s}\g\bigr)^d$ we have $$ \opa \Bigl(\Bigl\{T\in (X\times Y)^n : \ca R_{P,S} (f_{T}^k) \leq \frac {4d} n \Bigl(\frac {16\s} \g \Bigr)^d \Bigl(d \ln \frac{16\s}\g + \ln \frac 2 \d\Bigr) \Bigr\}\Bigr) \Geq 1-\d\ . $$ \end{corollary} \begin{proof} As already shown in the proof of Corollary \ref{Cor1} we have $$ \ca N\bigl((X,d_k),\e\bigr) \Leq \ca N\Bigl((X,\ynorm . 2),\frac \e{\sqrt 2 \s}\Bigr) \Leq 2 \cdot 5^d \Bigl(\frac \e {\sqrt 2 \s}\Bigr)^{-d} \Leq 2 (8\s)^d \e^{-d} $$ and thus $M:= \ca N\bigr((X,d_k),\g/2\bigl)\ \leq\ 2 (16\s)^d \g^{-d}$. Now let $\e:= 2M (1-\bigl(\frac \d M\bigr)^{1/n})$ for $n\geq 2 (16\s)^d \g^{-d}$, i.e. $\d=M\bigl( 1-\frac \e {2M}\bigr)^n$. Since $\e<\frac {2M} n \ln \frac M \d$ Theorem \ref{HS8} yields the assertion. \end{proof} \noindent Corollary \ref{Cor4} shows that the learning curve of the MMC is of order $\ca O(n^{-1})$ provided that $P$ guarantees a large margin. These conditions also allow the application of margin-based bounds on generalization proved by \citet{SBWA} \citep*[cf.\ also][]{BST,CST}. We then obtain that the learning curve is of order $\ca O(n^{-1} (\log n)^2)$. However, to compare both results one also has to consider the constants that arise since the sample size $n$ only varies in a typical range. Here we observe that the influence of the margin $\g$ is essentially of order $\ca O(\g^{-2})$ in the estimates of \citet{SBWA} while the Corollary \ref{Cor4} shows that our estimates are essentially influenced by order $\ca O(\g^{-d})$, where $d$ is the dimension of the {\em input} space $X$. We thus suppose that only for small input dimensions $d$ our estimates are more suitable to treat realistic sample sizes. \section{Conclusions} The aim of this paper has been to investigate which kind of distributions could be classified well by support vector machines (SVM's). It has turned out that the ability of the kernel to approximate arbitrary continuous functions plays a fundamental role for this question. Since the resulting function classes represented by the classifier are very large there always exists the risk of {\em overfitting}. However, using soft margin support vector machines with specific sequences of regularization parameters this risk can be controlled at least for simple noise models, e.g. models with constant noise level. In particular, the restriction to large margin problems in \citet*[][p.~442]{TZ} has been significantly weakened. Since the ansatz of this paper is new many questions remain open, and are worth for further investigations. Firstly it is interesting whether the soft margin algorithms yield arbitrarily good generalization for {\em all distributions.} Up to now our results only provide consistency if the noise level is constant. However, approximating an arbitrary noise level by step functions it seems possible that the soft margin algorithms with certain parameter sequences are universally consistent. Of course, the universality of kernels, which roughly speaking enables us to do ``almost everything'' with induced functions on compact subsets would play a crucial role for this ansatz, too. However, a solution is certainly also based on a deeper investigation of the underlying optimization problems in order to remove the restriction $q^*,p^* \in (0,1/2)$. Moreover, we suppose that the universality of kernels is also very important for related algorithms such as $\nu$-SVM's, linear programming SVM's and leave-one-out SVM's as well as all kind of SVM's used for regression, distribution estimation, etc.. However, since each treatment of one of these algorithms needs its own investigation of the corresponding optimization problem many open questions remain.\\[2mm] % \noindent{\bf Remark } {\em Using the techniques of this work the author was recently able to prove universal consistency for the 1-SMC \citep[cf.][]{Ste2}.} \acks{We would like to acknowledge support for this project from the Deutsche Forschungsgemeinschaft (DFG grant Ca 179/4-1). } \begin{thebibliography}{99} \bibitem[Bartlett et al.(1999)Bartlett \& Shawe-Taylor]{BST} { P. Bartlett and J. Shawe-Taylor}. Generalization performance of support vector machines and other pattern classifiers. In B. Sch\"olkopf, C.J.C. Burges, and A.J. Smola, editors, {\em Advances in Kernel Methods - Support Vector Learning}, pages 43-54, Cambridge, MA, 1999. MIT Press. \bibitem[Burges et al.(2000)Burges \& Crisp]{BC} { C.J.C. Burges and D.J. Crisp}. Uniqueness of the SVM solution. In M.I. Jordan, T.K. Leen, and K.-R. M\"uller, editors, {\em Advances in Neural Information Processing 12}, pages 223-229, Cambridge, MA, 2000. MIT Press. \bibitem[Cristianini et al.(2000)Cristianini \& Shawe-Taylor]{CST} { N. Cristianini and J. Shawe-Taylor}. {\em An Introduction to Support Vector Machines and other kernel-based learning methods}. Cambridge University Press, Cambridge, 2000. \bibitem[Carl et al.(1990)Carl \& Stephani]{C-S} { B. Carl and I. Stephani}. {\em Entropy, compactness and the approximation of operators}. Cambridge University Press, Cambridge, 1990. \bibitem[Devroye et al.(1997)]{DGL} { L. Devroye, L. Gy\"orfi and G. Lugosi}. {\em A probabilistic theory of pattern recognition}. Springer, New York, 1997. \bibitem[Dudley(1978)]{Dud2} { R.M. Dudley}. Central limit theorems for empirical measures, {\it Ann. Probab.}, { 6}(6):899-929, 1978. \bibitem[Dudley(1989)]{Dud} { R.M. Dudley}. {\em Real Analysis and Probability}. Chapman \& Hall, New York, 1989. \bibitem[Gradstein et al.(1981)Gradstein \& Ryshik]{G-R} { S. Gradstein and I.M. Ryshik}. {\em Summen- Produkt- und Integraltafeln * Tables of series, products and integrals}. Verlag Harri Deutsch, Frankfurt am Main, 1981. \bibitem[Pedersen(1988)]{Ped} { G.K. Pedersen}. {\em Analysis Now}. Springer, Berlin, 1988. \bibitem[Poggio(1975)]{Pog} { T. Poggio}. On optimal nonlinear associative recall. {\it Biological Cybernetics,} { 19}(4):201-209, 1975. \bibitem[Saunders et al.(1998)]{SSW} { C. Saunders, M.O. Stitson, J. Weston, L. Bottou, B. Sch\"olkopf, and A. Smola}. Support vector machine --- reference manual. {Technical Report} {CSD-TR-98-03}, Department of Computer Science, Royal Holloway, University of London, Egham, UK. Available electronically at \url{http://www.dcs.rhbnc.ac.uk/research/compint/areas/comp_learn/sv/pub/report98-03.ps}, 1998. \bibitem[Sch\"olkopf et al.(2001)]{SHSW} { B. Sch\"olkopf, R. Herbrich, A.J. Smola, and R.C. Williamson}. A generalized representer theorem. In {\it Proceedings of the 14th Annual Conference on Computational Learning Theory, Lecture Notes in Artificial Intelligence 2111}, pages 416-426, 2001. \bibitem[Shawe-Taylor et al.(1998)]{SBWA} { J. Shawe-Taylor, P.L. Bartlett, R.C. Williamson and M. Anthony}. Structural risk minimization over data-dependent hierarchies. {\it IEEE Trans. Inf. Theory} {44}(5):1926-1940, 1998. \bibitem[Steinwart(2001a)]{Ste} { I. Steinwart}. On the influence of the kernel on the generalization ability of support vector machines. {Technical Report} {01-01}, Fakult\"at f\"ur Mathematik und Informatik, Friedrich-Schiller-Universit\"at, Jena, Germany, available electronically at \url{http://www.minet.uni-jena.de/Math-Net/reports/sources/2001/01-01report.ps}, 2001a. \bibitem[Steinwart(2001b)]{Ste2} { I. Steinwart}. On the generalization ability of support vector machines. Submitted to {\em J. Complexity}, 2001b. \bibitem[Tong Zhang(2001)]{TZ} { Tong Zhang}. A leave-one-out cross validation bound for kernel methods with applications in learning. In {\it Proceedings of the 14th Annual Conference on Computational Learning Theory, Lecture Notes in Artificial Intelligence 2111}, pages 427-443, 2001. \bibitem[van der Vaart et al.(1996)van der Vaart \& Wellner]{V-W} { A.W. van der Vaart and J.A. Wellner}. {\em Weak Convergence and Empirical Processes}. Springer, New York, 1996. \bibitem[Vapnik(1998)]{Vap} { V.N. Vapnik}. {\em Statistical Learning Theory}. Wiley, New York, 1998. \end{thebibliography} \end{document}