Journal of Machine Learning Research 2 (2001) 67-93 Submitted 08/01; Published 12/01

On the Influence of the Kernel on the Consistency of Support Vector Machines

Ingo Steinwart steinwart@minet.uni-jena.de Mathematisches Institut Friedrich-Schiller-Universität Ernst-Abbe-Platz 1-4 07743 Jena, Germany

Editor: Bernhard Schölkopf (for HTTP://WWW.KERNEL-MACHINES.ORG)

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. Keywords: Computational learning theory, pattern recognition, PAC model, support vector machines, kernel methods

1. 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 (cf. Shawe-Taylor et al., 1998; Bartlett & Shawe-Taylor, 1999; Cristianini & Shawe-Taylor, 2000, chap. 2). The latter usually needs large margins on the

\begin{matrix}c \\ ◯ \end{matrix}2001 Steinwart.

Steinwart

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 (cf. Vapnik, 1998; Cristianini & Shawe-Taylor, 2000). Let (X, d) be a compact metric space^{1}, Y := {−1, 1} and P be a probability measure on X×Y, where X is equipped with the Borel σ-algebra. By disintegration (cf. Dudley, 1989, Lem. 1.2.1.) there exists a map x ↦ 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 supervisor. A classifier is an algorithm that constructs to every training set T = ((x_{1}, y_{1}), …, (x_{n}, y_{n})) ∈ (X × Y)^{n} a decision function f_{T} : X → 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 → 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) ≠ y. To make this precise, for a measurable function f : X → {−1, 1} we define the risk of f by

R_{P} (f) := ∫_{X×Y} 1_{{f(x)≠y}} P (dx, dy) = P ({(x, y) : f(x) ≠ y}) .

When considering noisy supervisors we cannot expect that we obtain zero risk. Indeed, for

B_{1}(P) := {x ∈ X : P (y = 1|x) > P (y = −1|x) }
B_{−1}(P) := {x ∈ X : P (y = 1|x) < P (y = −1|x) }
B_{0}(P) := {x ∈ X : P (y = 1|x) = P (y = −1|x) }

and a function f_{0} : X → {−1, 1} with f_{0}(x) = 1 if x ∈ B_{1}(P) and f_{0}(x) = −1 if x ∈ B_{−1}(P) we have (cf. Devroye et al., 1997, Thm. 2.1.)

R_{P} (f_{0}) = inf{R_{P} (f) : f:X → {−1, 1} measurable} = ∫_{X} p(x) P_{X}(dx) ,  (1)

where the noise level p : X → ℝ is defined by p(x) := P (y = −1|x) for x ∈ B_{1}(P), p(x) := P (y = 1|x) for x ∈ B_{−1}(P) and p(x) = 1/2 otherwise. Equation (1) 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 R_{P} := R_{P} (f_{0}). Now, a classifier C should guarantee with high probability that R_{P} (f_{T}) is close to R_{P} provided that T is large enough. Here, f_{T} denotes the decision function constructed by C on the basis of T. Asymptotically, this means that

R_{P} (f_{T}) → R_{P}

On the Consistency of Support Vector Machines

should hold in probability if |T | → ∞. In this case the algorithm C is called consistent for P (cf. Devroye et al., 1997, Def. 6.1). If a classifier is consistent for all distributions on X × Y it is said to be universally consistent. Although several algorithms such as the knearest neighbour classifier for k → ∞ and k/|T | → 0 (cf. Devroye et al., 1997, Thm. 6.4) are universally consistent it is an open question whether support vector machines are universally consistent for a particular choice of the free parameters.

1. For mathematical notions see Section 2.

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 ≡ p^{∗}, p^{∗} ∈ [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 {⟨w, Φ(.)⟩ : w ∈ H} (or {⟨w, Φ(.)⟩ + b : w ∈ H, b ∈ ℝ}), where Φ : X → H is a feature map of the used kernel. If this function class is dense in C(X) we shall call the corresponding kernel universal (cf. Def. 4). 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ß we show that kernels that can be expanded in certain types of Taylor or Fourier series are universal (cf. Cor. 10 and Cor. 11). In particular it turns out that the Gaussian RBF kernel is universal (cf. Ex. 1). 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. 6 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 ⊂ ℝ^{d} the regularization sequence c_{n} = n^{β−1}, 0 < β < 1/d, yields consistency for all problems with constant noise level (cf. Cor. 17 and Cor. 23). 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 independent of the training set size (cf. Thm. 18, Thm. 19 and Thm. 24). For this class of problems we also prove consistency for the maximal margin classifier (cf. Thm. 25). Finally, it turns out that even for these simple, noise free classification problems SVM’s with polynomial kernels can behave arbitrarily badly (cf. Prop. 20).

This work is organized as follows: we introduce some mathematical notions in Section 2. 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.

2. Preliminaries

For a set X, a metric d on X is a function d : X ×X → [0, ∞) such that for all x, y, z ∈ X we have d(x, y) = d(y, x) and d(x, y) ≤ 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 ε and centre x by B_{d}(x, ε) := {y ∈ X : d(x, y) ≤ ε}.

The covering numbers of X are defined by

N ((X, d), ε) := min{n ∈ ℕ ∪ {∞} : ∃x_{1}, …, x_{n} with X ⊂ ⋃_{i=1}^{n} B_{d}(x_{i}, ε)}

for all ε > 0. The space (X, d) is precompact if and only if N ((X, d), ε) is finite for all ε > 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 ⊂ X we denote the distance of A and B by

d(A, B) := inf_{\begin{matrix}x∈A \\ y∈B \end{matrix}} 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 σ-algebra on a set X is a set of subsets of X that contains ∅ and is closed under elementary, countable set operations such as complements and countable intersections. For a metric space (X, d) the Borel σ-algebra is the smallest σ-algebra that contains all open sets. Let A be a σ-algebra on X. A subset A of X is called measurable if A ∈ A. We say that a function f : X → ℝ is measurable if the pre-image of every Borel measurable B ⊂ ℝ is in A. Basic examples are the functions 1_{A}, where A ∈ A and 1_{A}(x) = 1 if x ∈ A and 1_{A}(x) = 0 otherwise. A probability measure P : A → ℝ^{+} is a σ-additive function with P (∅) = 0 and P (X) = 1. If A is a Borel σ-algebra we call P a Borel probability measure. In this case P is said to be regular, if for all Borel measurable B ⊂ X we have

P (B) = sup{P (K) : K ⊂ B, K compact} .

If (X, d) is compact, then every Borel probability measure on X is regular (cf. Dudley, 1989, p. 176).

In this paper H always denotes a Hilbert space, i.e. a complete, normed vector space endowed with a dot product ⟨., .⟩ giving rise to its norm via ∥x∥ = \sqrt{⟨x, x⟩}. Let B_{H} := {x ∈ H : ∥x∥ ≤ 1} be the closed unit ball of H and S_{H} := {x ∈ H : ∥x∥ = 1} be its sphere. Recall, that every separable Hilbert space is isometrically isomorphic to the space of all 2-summable sequences ℓ_{2}.

A commutative algebra A is a vector space equipped with an additional associative and commutative multiplication · : A × A → A such that

x·(y + z) = x·y + x·z
λ(x·y) = (λx)·y

holds for all x, y, z ∈ A and λ ∈ ℝ. A classical example of an algebra is the space C(X) of all continuous functions f : X → ℝ on the compact metric space (X, d) endowed with the usual supremum norm

∥f∥_{∞} := sup_{x∈X} |f(x)| .

The following well-known approximation theorem of Stone-Weierstraß (cf. Pedersen, 1988, Cor. 4.3.5.) 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:

Theorem 1 Let (X, d) be a compact metric space and A ⊂ C(X) be an algebra. Then A is dense in C(X) if both A does not vanish, i.e. for all x ∈ X there exists an f ∈ A with f(x) ≠ 0, and A separates points, i.e. for all x, y ∈ X with x ≠ y there exists an f ∈ A with f(x) ≠ f(y).

3. Kernels

In the following let (X, d) be a metric space. A function k : X × X → ℝ is called a kernel on X if there exists a Hilbert space H and a map Φ : X → H with

k(x, y) = ⟨Φ(x), Φ(y)⟩

for all x, y ∈ X. We call Φ a feature map and H a feature space of k. Note, that both H and Φ 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) (cf. Cristianini & Shawe-Taylor, 2000, Ch. 3). 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 Φ : X → H be a feature map of k. A function f : X → ℝ is induced by k if there exists an element w ∈ H such that f = ⟨w, Φ(.)⟩. The next lemma shows that this definition is independent of Φ and H:

Lemma 2 Let k : X × X → ℝ be a kernel and Φ_{1} : X → H_{1}, Φ_{2} : X → H_{2} be two feature maps of k. Then for all w_{1} ∈ H_{1} there exist w_{2} ∈ H_{2} with ∥w_{2}∥ ≤ ∥w_{1}∥ and

⟨w_{1}, Φ_{1}(x)⟩ = ⟨w_{2}, Φ_{2}(x)⟩  for all x ∈ X.

Proof Let H_{1}^{∗} := \overline{span Φ_{1}(X)} and H̃_{1} its orthogonal complement in H_{1}. Then w_{1} ∈ H_{1} can be written as w_{1} = w_{1}^{∗} + w̃_{1} with w_{1}^{∗} ∈ H_{1}^{∗} and w̃_{1} ∈ H̃_{1}. Given an x ∈ X we have ⟨w̃_{1}, Φ_{1}(x)⟩ = 0 and therefore we obtain ⟨w_{1}^{∗}, Φ_{1}(x)⟩ = ⟨w_{1}, Φ_{1}(x)⟩ for all x ∈ X. Now by the definition of H_{1}^{∗} there exists a sequence (w_{n}^{(1)}) ⊂ span Φ_{1}(X) with w_{n}^{(1)} = ∑_{m=1}^{m_{n}} λ_{m}^{(n)}Φ_{1}(x_{m}^{(n)}) and w_{1}^{∗} = ∑_{n=1}^{∞} w_{n}^{(1)}. Then for w_{n}^{(2)} := ∑_{m=1}^{m_{n}} λ_{m}^{(n)}Φ_{2}(x_{m}^{(n)}) and l_{2} ≥ l_{1} ≥ 1 we obtain

∥∑_{n=l_{1}}^{l_{2}} w_{n}^{(1)}∥^{2} = ∑_{n=l_{1}}^{l_{2}} ∑_{m=1}^{m_{n}} ∑_{i=l_{1}}^{l_{2}} ∑_{j=1}^{m_{i}} λ_{m}^{(n)}λ_{j}^{(i)}⟨Φ_{1}(x_{m}^{(n)}), Φ_{1}(x_{j}^{(i)})⟩

= ∑_{n=l_{1}}^{l_{2}} ∑_{m=1}^{m_{n}} ∑_{i=l_{1}}^{l_{2}} ∑_{j=1}^{m_{i}} λ_{m}^{(n)}λ_{j}^{(i)}⟨Φ_{2}(x_{m}^{(n)}), Φ_{2}(x_{j}^{(i)})⟩

= ∥∑_{n=l_{1}}^{l_{2}} w_{n}^{(2)}∥^{2} .

Therefore, (∑_{n=1}^{m} w_{n}^{(2)})_{m≥1} is a Cauchy sequence and hence converges to w_{2} := ∑_{n=1}^{∞} w_{n}^{(2)} ∈ H_{2}. Clearly, we then have ∥w_{2}∥ = ∥w_{1}^{∗}∥ ≤ ∥w_{1}∥. Moreover, an easy calculation similar to the consideration above shows ⟨w_{1}, Φ_{1}(x)⟩ = ⟨w_{2}, Φ_{2}(x)⟩ for all x ∈ X.

In the following we only consider continuous kernels. The following lemma provides some useful properties of this class:

Lemma 3 Let k be a kernel on the metric space (X, d) and Φ : X → H be a feature map of k. Then k is continuous if and only if Φ is continuous. In this case

d_{k}(x, y) := ∥Φ(x) − Φ(y)∥

defines a semi-metric on X such that the identity map id : (X, d) → (X, d_{k}) is continuous. If Φ is injective d_{k} is even a metric.

Proof Let us first suppose that k is continuous. Since

d_{k}(x, y) = \sqrt{k(x, x) − 2k(x, y) + k(y, y)}

we observe that d_{k}(x, .) : (X, d) → ℝ is continuous for every x ∈ X. In particular, {y ∈ X : d_{k}(x, y) < ε} is open with respect to d and therefore id : (X, d) → (X, d_{k}) is continuous. Furthermore, Φ : (X, d_{k}) → H is continuous and hence Φ : (X, d) → H is also continuous. Conversely, assume that Φ is continuous. Since for all x, x′, y, y′ ∈ X we have

|k(x, y) − k(x′, y′)| ≤ |⟨Φ(x), Φ(y) − Φ(y′)⟩| + |⟨Φ(x) − Φ(x′), Φ(y′)⟩|
≤ ∥Φ(x)∥·∥Φ(y)−Φ(y′)∥ + ∥Φ(y′)∥·∥Φ(x)−Φ(x′)∥

it is easily verified that k is also continuous.

The metric d_{k} enjoys the property that every induced function ⟨w, Φ(.)⟩ is Lipschitz continuous with respect to d_{k} and the Lipschitz constant is bounded from above by ∥w∥. This fact turns out to be very important in the proof of Theorem 12 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:

Definition 4 A continuous kernel k on a compact metric space (X, d) is called universal if the space of all functions induced by k is dense in C(X), i.e. for every function f ∈ C(X) and every ε > 0 there exists a function g induced by k with

∥f − g∥_{∞} ≤ ε .

We also need a weaker concept. Let Φ : X → H be a feature map of k and A, B be disjoint subsets of X. We say that k separates A and B with margin γ ≥ 0 if Φ(A) and Φ(B) can be separated by a hyperplane with margin γ, i.e. if there exists a pair (w, b) ∈ S_{H} × ℝ such that

⟨w, Φ(x)⟩ + b > γ  for all x ∈ A and
⟨w, Φ(y)⟩ + b < −γ  for all y ∈ B .

If γ = 0 we simply say that k separates A and B. In this case the restriction w ∈ S_{H} is superfluous. By Lemma 2 both definitions are independent of the feature map Φ. 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 compact sets A and B then it automatically separates them with a suitable margin γ > 0. Moreover, it was shown in Steinwart (2001a, Ex. 3.13) 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 ι : X′ → X be a continuous and injective map. Then one easily checks that k(ι(.), ι(.)) is a universal kernel on X′. Moreover, we have k(x, x) > 0 for all x ∈ 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:

Proposition 5 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}, …, K_{n} ⊂ X, all α_{1}, …, α_{n} ∈ ℝ and all ε > 0 there exists a function g induced by k with ∥g∥_{∞} ≤ max_{i} |α_{i}| + ε such that

∥g_{|K} − ∑_{i=1}^{n} α_{i}1_{K_{i}} ∥_{∞} ≤ ε ,

where K := ⋃_{i=1}^{n} K_{i} and g_{|K} denotes the restriction of g to K.

Proof Since d(K_{i}, K_{j}) > 0 for all i ≠ j we obtain ∑_{i=1}^{n} α_{i}1_{K_{i}} ∈ C(K). Since this function can be extended to a continuous function f on X with ∥f∥_{∞} ≤ max_{i} |α_{i}| (by the Lemma of Urysohn or by a direct construction with the help of d) the assertion follows.

Corollary 6 Every universal kernel separates all compact subsets.

Proof Let (X, d) be a compact metric space and k be a universal kernel on X with feature map Φ : X → H. Given two compact and disjoint subsets K_{1} and K_{−1} of X there exists an induced function g = ⟨w, Φ(.)⟩ with ∥g_{|K_{−1}∪K_{1}} − (1_{K_{1}} − 1_{K_{−1}})∥_{∞} < 1/2. This implies that (∥w∥^{−1}w, 0) separates K_{1} and K_{−1} with margin \frac{1}{2∥w∥}.

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}, …, x_{n}} of X. Then the above corollary ensures that for every sequence of signs y_{1}, …, 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}, …, 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:

Corollary 7 Every feature map of a universal kernel is injective.

Proof Finite subsets are compact and thus the assertion follows by the previous corollary.

Proposition 8 Let (X, d) be a compact metric space and k be a universal kernel on X. Then

k^{∗}(x, y) := \frac{k(x, y)}{\sqrt{k(x, x)k(y, y)}}

defines a universal kernel on X.

Proof Let Φ : X → H be a feature map of k and α(x) := k(x, x)^{−1/2}. Clearly, αΦ : X → H is a feature map of k and thus k is a kernel. To show that k^{∗} is universal we fix a function f ∈ C(X) and ε > 0. For a := ∥α∥_{∞} we then get an induced function g = ⟨w, Φ(.)⟩ with ∥α^{−1}f − g∥_{∞} ≤ \frac{ε}{a}. This yields

∥f − ⟨w, αΦ(.)⟩∥_{∞} ≤ ∥α∥_{∞} ∥α^{−1}f − g∥_{∞} ≤ ε

and thus the assertion is proved.

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:

Theorem 9 Let (X, d) be a compact metric space and k be a continuous kernel on X with k(x, x) > 0 for all x ∈ X. Suppose that we have an injective feature map Φ : X → ℓ_{2} of k with Φ(x) = (Φ_{n}(x))_{n∈ℕ}. If A := span {Φ_{n} : n ∈ ℕ} is an algebra then k is universal .

Proof Because of k(x, x) > 0 for all x ∈ X the algebra A does not vanish. Since k is continuous every Φ_{n} : X → ℝ is continuous by Lemma 3 and hence A ⊂ C(X). Moreover, A is even dense in C(X) since the injectivity of Φ implies that A separates points and thus Theorem 1 can be applied. Now we fix f ∈ C(X) and ε > 0. Then there exists a function

g = ∑_{j=1}^{n} λ_{j} · (Φ_{n_{j}}) ∈ A

such that ∥f − g∥_{∞} ≤ ε. However, if we define w_{n} := λ_{j} for n = n_{j} and w_{n} := 0 otherwise, we have w := (w_{n}) ∈ ℓ_{2} and ⟨w, Φ(.)⟩ = g.

The following corollaries give various examples of universal kernels. We begin with kernels that can be expressed by a Taylor series:

Corollary 10 Let 0 < r ≤ ∞ and f : (−r, r) → ℝ be a C^{∞}-function that can be expanded into its Taylor series in 0, i.e.

f(x) = ∑_{n=0}^{∞} a_{n}x^{n}  for all x ∈ (−r, r) .

Let X := \{x ∈ ℝ^{d} : ∥x∥_{2} < \sqrt{r}\}. If we have a_{n} > 0 for all n ≥ 0 then k(x, y) := f(⟨x, y⟩) defines a universal kernel on every compact subset of X.

Proof Since |⟨x, y⟩| ≤ ∥x∥_{2}∥y∥_{2} < r for all x, y ∈ X we see that k is well-defined. We also have

k(x, y) = ∑_{n=0}^{∞} a_{n} (∑_{k=1}^{d} x_{k}y_{k})^{n}

= ∑_{n=0}^{∞} a_{n} ∑_{\begin{matrix}k_{1}+···+k_{d}=n \\ k_{1},...,k_{d}≥0 \end{matrix}} c_{k_{1},...,k_{d}} ∏_{i=1}^{d}(x_{i}y_{i})^{k_{i}}

= ∑_{k_{1},...,k_{d}≥0} a_{k_{1}+···+k_{d}}c_{k_{1},...,k_{d}} ∏_{i=1}^{d} x_{i}^{k_{i}} ∏_{i=1}^{d} y_{i}^{k_{i}} ,

where c_{k_{1},...,k_{d}} := (∏_{i=1}^{d} k_{i}!)^{−1}(∑_{i=1}^{d} k_{i})! (cf. also Poggio, 1975, Lem. 2.1). Note, that the series can be rearranged since it is absolutely summable. In particular, for x = y we obtain that Φ : X → ℓ_{2}(ℕ_{0}^{d}) is well defined by

Φ(x) := (\sqrt{a_{k_{1}+···+k_{d}}c_{k_{1},...,k_{d}}} ∏_{i=1}^{d} x_{i}^{k_{i}})_{k_{1},...,k_{d}≥0} .

The above equation also shows that k(x, y) = ⟨Φ(x), Φ(y)⟩ holds for all x, y ∈ X and hence k is indeed a kernel. Moreover, a_{0} > 0 implies k(x, x) > 0 for all x ∈ X and trivially, Φ is injective. Since A := span {Φ_{k_{1},...,k_{d}} : k_{1}, …, k_{d} ≥ 0} is an algebra we thus obtain by Theorem 9 that k is universal.

Instead of Taylor series one can also consider Fourier expansions. The result reads as follows:

Corollary 11 Let f : [0, 2π] → ℝ be a continuous function that can be expanded in a pointwise absolutely convergent Fourier series of the form

f(t) = ∑_{n=0}^{∞} a_{n} cos(nt) .  (2)

If a_{n} > 0 holds for all n ≥ 0 then k(x, y) := ∏_{i=1}^{d} f(|x_{i} − y_{i}|) defines a universal kernel on every compact subset of [0, 2π)^{d}.

Recall, that every function f : [0, 2π] → ℝ that can be extended to a continuous, symmetric, periodic and piecewise continuously differentiable function on ℝ has a Fourier series of the form (2).

Proof By induction and the Cauchy product of series we may restrict ourselves to d = 1. Then

k(x, y) = a_{0} +∑_{n=1}^{∞} a_{n} sin(nx) sin(ny) +∑_{n=1}^{∞} a_{n} cos(nx) cos(ny)

holds for all x, y ∈ [0, 2π) and hence Φ = (Φ_{n})_{n≥0} defined by Φ_{0}(x) := a_{0} and Φ_{2n−1}(x) := \sqrt{a_{n}} sin(nx), Φ_{2n}(x) := \sqrt{a_{n}} cos(nx) for n ≥ 1 is an injective feature map of k with image in ℓ_{2}. Moreover, A := span(\{\sqrt{a_{n}} sin(n · .) : n ≥ 1\} ∪ \{\sqrt{a_{0}} cos(n · .) : n ≥ 0\}) is an algebra and since a_{0} > 0 implies k(x, x) > 0 for all x ∈ X we obtain that k is universal.

The following examples show that various well-known kernels are universal:

Example 1 The kernels exp(−σ^{2}∥. − .∥_{2}^{2}) and exp(⟨., .⟩) are universal on every compact subset of ℝ^{d}.

Proof The universality of exp(⟨., .⟩) is due to Corollary 10. Therefore, by Proposition 8 and exp(−σ^{2}∥x − y∥_{2}^{2}) = exp(−∥σx∥_{2}^{2}) exp(−∥σy∥_{2}^{2}) exp(⟨\sqrt{2}σx, \sqrt{2}σy⟩) the assertion follows for the RBF kernel.

Example 2 Let X := {x ∈ ℝ^{d} : ∥x∥_{2} < 1} and α > 0. Then V. Vovk’s (cf. Saunders et al., 1998, p. 15) infinite polynomial kernel k(x, y) := (1 − ⟨x, y⟩)^{−α}, x, y ∈ X, is universal on every compact subset of X.

Proof To check the assertion we use that (1 − t)^{−α} = ∑_{n=0}^{∞} \binom{−α}{n}(−1)^{n}t^{n} holds for |t| < 1. Since \binom{−α}{n}(−1)^{n} > 0 for all n ≥ 0, the assertion then follows by Corollary 10.

Example 3 Let 0 < q < 1 and f(t) := (1 − q^{2})/(2 − 4q cos t + 2q^{2}), t ∈ ℝ. Then the stronger regularized Fourier kernel k(x, y) := ∏_{i=1}^{d} f(x_{i} − y_{i}) considered by Vapnik (1998, p. 470) and Saunders et al. (1998, p. 15) is universal on every compact subset of [0, 2π)^{d}.

Proof The assertion can be seen using Corollary 11 and f(t) = 1/2 + ∑_{n=1}^{∞} q^{n} cos(nt) (cf. Gradstein & Ryshik, 1981, p. 68).

Example 4 Let 0 < q < ∞ and f(t) := π cosh((π − |t|)/q)/(2q sinh(π/q)) for all t with −2π ≤ t ≤ 2π. Then the weaker regularized Fourier kernel k(x, y) := ∏_{i=1}^{d} f(x_{i} − y_{i}) considered by Vapnik (1998, p. 470/1) and Saunders et al. (1998, p. 15) is universal on every compact subset of [0, 2π)^{d}.

Proof To obtain the assertion we use f(t) = 1/2 + ∑_{n=1}^{∞} cos(nt)/(1 + q^{2}n^{2}) (cf. Gradstein & Ryshik, 1981, p. 68).

4. The 2-norm soft margin classifier

Let k be a kernel on X and Φ : X → H be a feature map of k. For a training set T = ((x_{1}, y_{1}), …, (x_{n}, y_{n})) ∈ (X × Y)^{n} and c_{n} > 0 we denote the unique solution of the optimization problem

minimize  W(w, b, ξ) := ⟨w, w⟩ + c_{n} ∑_{i=1}^{n} ξ_{i}^{2}  over w, b, ξ
subject to  y_{i}(⟨w, Φ(x_{i})⟩ + b) ≥ 1 − ξ_{i},  i = 1, …, n

(3)

by (w_{T}^{2,k,c_{n}}, b_{T}^{2,k,c_{n}}) ∈ H × ℝ. An algorithm C_{k}^{2,(c_{n})} that provides the decision function

f_{T}^{2,k,c_{n}}(x) := sign(⟨w_{T}^{2,k,c_{n}}, Φ(x)⟩ + b_{T}^{2,k,c_{n}}) , x ∈ 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 ≥ 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} = cn^{β−1} where β > 0 is a parameter a-priori determined by the kernel and c is a new free parameter (cf. Cor. 17). Of course, for fixed training set sizes both parameterizations are equivalent, i.e. they can be transformed into each other.

By Lemma 2 the decision function is independent of the choice of the feature map Φ. Moreover, f_{T}^{2,k,c_{n}} can be expressed by

f_{T}^{2,k,c_{n}}(x) = ∑_{i=1}^{n} y_{i}α_{i}k(x_{i}, x) + b_{T}^{2,k,c_{n}},

where α_{i} ≥ 0 are suitable constants depending on T and b_{T}^{2,k,c_{n}} can also be computed with the help of the kernel (cf. Cristianini & Shawe-Taylor, 2000; Vapnik, 1998; Schölkopf et al., 2001). 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 Vapnik (1998, Ch. 4), Cristianini & Shawe-Taylor (2000, Ch. 4) and van der Vaart & Wellner (1996, Ch. 2.6).

Given a Borel probability measure P on X × Y with noise level p we denote the nondeterministic part of the supervisor by X^{+} := {x ∈ X : p(x) > 0}. If P_{X}(X^{+}) > 0 we write q^{∗} := inf_{x∈X} p(x) and p^{∗} := sup_{x∈X} p(x). Due to technical reasons we define q^{∗} := p^{∗} := 1/4 otherwise. We begin with a preliminary result:

Theorem 12 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 ×Y with q^{∗}, p^{∗} ∈ (0, 1/2) and all ε > 0 there exist c^{∗} > 0 and δ^{∗} > 0 such that for all c ≥ c^{∗}, 0 < δ ≤ δ^{∗} and all n ≥ 1 we have

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P} (f_{T}^{2,k,c/n}) ≤ R_{P} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε\}) ≥ 1 − 3Me^{−2(\frac{δ}{M})^{2}n} ,

where M := N ((X, d_{k}), \frac{δ}{\sqrt{c}}) is the covering number of X with respect to the metric d_{k} which is induced by the kernel k. Moreover, Pr^{∗} denotes the outer probability measure of P^{n}.

Note, that in order to avoid the (probably very difficult) question whether the sets

{T ∈ (X × Y)^{n} : R_{P} (f_{T}^{2,k,c/n}) ≤ α}

are measurable we consider the outer probability measure, only.

Since the proof of Theorem 12 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 ∈ [0, 1/2). Moreover, we assume that we have an induced function ⟨w^{∗}, Φ(.)⟩ 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 (4)) that

⟨w_{T}^{k,c/n}, w_{T}^{k,c/n}⟩ + \frac{c}{n} ∑_{l=1}^{n} ξ_{l}^{2} ≲ ⟨w^{∗}, w^{∗}⟩ + 4cp(1 − p)

holds. Here ≲ means that the relation ≤ 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 (6)). 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 (7)). Combining these considerations we obtain

c(1 − 2p)^{2}P_{X}(E) + 4cp(1 − p) = c(P_{X}(E) + 4p(1 − p)P_{X}(X \ E))
≲ ⟨w_{T}^{k,c/n}, w_{T}^{k,c/n}⟩ + \frac{c}{n} ∑_{l=1}^{n} ξ_{l}^{2}
≲ ⟨w^{∗}, w^{∗}⟩ + 4cp(1 − p) ,

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”.

Proof of Theorem 12 Without loss of generality we may assume ε ∈ (0, 1]. Let X^{0} := X \ X^{+} be the deterministic part of the supervisor and X_{−1}^{0} := X^{0} ∩B_{−1}(P), X_{1}^{0} := X^{0} ∩B_{1}(P) be the parts of the classes B_{−1}(P), B_{1}(P) in X^{0}. Furthermore, let X_{−1}^{+} := X^{+} ∩ B_{−1}(P) and X_{1}^{+} := X^{+} ∩ B_{1}(P) be the parts of the classes B_{−1}(P) and B_{1}(P) in X^{+}. We define δ^{∗} := min\{2p^{∗}, \frac{ε}{74}q^{∗}(1 − 2q^{∗})\} and fix δ ≤ δ^{∗}. Since P_{X} is regular (cf. Dudley, 1989, p. 176) there exist compact subsets K_{i}^{j} of X_{i}^{j} with P_{X}(X_{i}^{j} \ K_{i}^{j}) ≤ δ/4 for i ∈ {−1, 1} and j ∈ {0, +}. Moreover, for a fixed feature map Φ : X → H of k Proposition 5 ensures the existence of an element w^{∗} ∈ H with

⟨w^{∗}, Φ(x)⟩ ∈ \begin{cases}[1, 1 + δ] & if x ∈ K_{1}^{0} \\ [−(1 + δ), −1] & if x ∈ K_{−1}^{0} \\ [1 − 2p^{∗} − δ, 1 − 2p^{∗}] & if x ∈ K_{1}^{+} \\ [−(1 − 2p^{∗}), −(1 − 2p^{∗} − δ)] & if x ∈ K_{−1}^{+} \\ [−(1 + δ), 1 + δ] & otherwise. \end{cases}

We define c^{∗} := \frac{2}{ε(1−2q^{∗})}∥w^{∗}∥_{2}^{2} and for fixed c ≥ c^{∗} let σ := \frac{δ}{\sqrt{c}}. By Lemma 13 we then

obtain partitions P̃_{i}^{j} of K_{i}^{j} with diam_{d_{k}}(A) ≤ σ for all A ∈ P̃_{i}^{j} and

| ⋃_{\begin{matrix}i∈\{−1,1\} \\ j∈\{0,+\} \end{matrix}} P̃_{i}^{j}| ≤ N ((X, d_{k}), σ) = M .

Let P_{i}^{j} := \{A ∈ P̃_{i}^{j} : P_{X}(A) ≥ \frac{δ}{q^{∗}M} \} for i ∈ \{−1, 1\} and j ∈ \{0, +\}. To construct “representative” training sets we define

F_{n,A} := \{((x_{1}, y_{1}), …, (x_{n}, y_{n})) : |\{l : x_{l} ∈ A\}| ≥ (P_{X}(A) − \frac{δ}{M} ) n\}

for all A ∈ P_{i}^{j}, i ∈ {−1, 1} and j ∈ {0, +}. Moreover, for A ∈ P_{i}^{+}, i ∈ {−1, 1} let

F_{n,A}^{+} := \{((x_{1}, y_{1}), …, (x_{n}, y_{n})) : |\{l : x_{l} ∈ A and y_{l} = i\}| ≥ ((1 − p^{∗})P_{X}(A) − \frac{δ}{M} ) n\}
F_{n,A}^{−} := \{((x_{1}, y_{1}), …, (x_{n}, y_{n})) : |\{l : x_{l} ∈ A and y_{l} ≠ i\}| ≥ (q^{∗}P_{X}(A) − \frac{δ}{M} ) n\}
F_{n} := ⋂_{A∈P_{−1}^{0}∪P_{1}^{0}} F_{n,A} ∩ ⋂_{A∈P_{−1}^{+}∪P_{1}^{+}}(F_{n,A} ∩ F_{n,A}^{+} ∩ F_{n,A}^{−}) .

Lemma 14 yields P^{n}(F_{n}) ≥ 1 − 3Me^{−2(\frac{δ}{M})^{2}n} and thus it suffices to show that

R_{P} (f_{T}^{2,k,c/n}) ≤ R_{P} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε

holds for all T ∈ F_{n}. Therefore, let us fix a training set T = ((x_{1}, y_{1}), …, (x_{n}, y_{n})) ∈ F_{n}. For c_{n} := c/n we denote the solution of (3) by (w_{T} , b_{T} , ξ_{T}). Our first step is to estimate W(w_{T} , b_{T} , ξ_{T}) from above by comparing it with W(w^{∗}, 0, ξ^{∗}), where ξ^{∗} is an admissible slack vector of (w^{∗}, 0). Hence we have to construct ξ^{∗}. For this let us first assume that we have a sample (x_{l}, y_{l}) ∈ K_{1}^{0}. Then we observe that

y_{l}⟨w^{∗}, Φ(x_{l})⟩ = ⟨w^{∗}, Φ(x_{l})⟩ ≥ 1

and thus we may define ξ_{l}^{∗} := 0. Analogous considerations yield

ξ_{l}^{∗} := \begin{cases}0 & if x_{l} ∈ K_{i}^{0} \\ 2p^{∗} + δ & if x_{l} ∈ K_{i}^{+}, y_{l} = i \\ 2 − 2p^{∗} & if x_{l} ∈ K_{i}^{+}, y_{l} ≠ i \\ 2 + δ & otherwise. \end{cases}

Moreover, our construction of F_{n} guarantees that there are at most

n − n ∑_{\begin{matrix}i∈\{−1,1\} \\ j∈\{0,+\} \end{matrix}} ∑_{A∈P_{i}^{j}}(P_{X}(A) − \frac{δ}{M} ) ≤ n(1 − ∑_{\begin{matrix}i∈\{−1,1\} \\ j∈\{0,+\} \end{matrix}} P_{X}(X_{i}^{j}) + (2 + \frac{1}{q^{∗}} )δ) = \frac{2}{q^{∗}} δn

samples which are not elements of a suitable K_{i}^{j}. Furthermore, since there are at most

n − n ∑_{i∈\{−1,1\}} ∑_{A∈P_{i}^{0}}(P_{X}(A) − \frac{δ}{M} ) ≤ n(P_{X}(X^{+}) + \frac{2}{q^{∗}} δ)

samples in K^{+} := K_{1}^{+} ∪ K_{−1}^{+} we also obtain that there are at most

n(P_{X}(X^{+}) + \frac{2}{q^{∗}} δ) − n ∑_{i∈\{−1,1\}} ∑_{A∈P_{i}^{+}}((1 − p^{∗})P_{X}(A) − \frac{δ}{M} ) ≤ n(p^{∗}P_{X}(X^{+}) + \frac{4}{q^{∗}} δ)

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

W(w_{T} , b_{T} , ξ_{T})
≤ W(w^{∗}, 0, ξ^{∗})
≤ ⟨w^{∗}, w^{∗}⟩ + \frac{c}{n} ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}x_{l}∈K_{i}^{+} \\ y_{l}=i \end{matrix}}(ξ_{l}^{∗})^{2} + \frac{c}{n} ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}x_{l}∈K_{i}^{+} \\ y_{l}≠i \end{matrix}}(ξ_{l}^{∗})^{2} + 2δc(2 + δ)^{2}

≤ ⟨w^{∗}, w^{∗}⟩ + c(1 − p^{∗})P_{X}(X^{+})(2p^{∗} + δ)^{2} + c(p^{∗}(P_{X}(X^{+}) + \frac{4}{q^{∗}} δ)(2 − 2p^{∗})^{2} + 2δc(2 + δ)^{2}
≤ ⟨w^{∗}, w^{∗}⟩ + c(4p^{∗}(1 − p^{∗})P_{X}(X^{+}) + \frac{27}{q^{∗}}δ) .  (4)

For later purposes we note that we also have W(w_{T} , b_{T} , ξ_{T}) ≤ W(0, 0, (1, …, 1)) ≤ c and thus ∥w_{T} ∥_{2} ≤ \sqrt{c}. In the second step of the proof we estimate W(w_{T} , b_{T} , ξ_{T}) from below. For this let us denote the set of misclassified points in X_{i}^{j} by

E_{i}^{j} := {x ∈ X_{i}^{j} : f_{T} (x) ≠ i} .

For brevity’s sake we also write E^{j} := E_{1}^{j} ∪ E_{−1}^{j} and E := E^{0} ∪ E^{+}. Let us first consider an A ∈ P_{i}^{0} with A ∩ E ≠ ∅. Without loss of generality we may assume that i = 1. Then for x_{l} ∈ A and z ∈ A ∩ E we obtain

1 − ξ_{T} (l) ≤ y_{l}(⟨w_{T} , Φ(x_{l})⟩ + b_{T} )
= ⟨w_{T} , Φ(x_{l}) − Φ(z)⟩ + ⟨w_{T} , Φ(z)⟩ + b_{T}
≤ ∥w_{T} ∥ d_{k}(x_{l}, z)
≤ δ,

i.e. ξ_{T}^{2} (l) ≥ (1 − δ)^{2} ≥ 1 − 2δ. Since the same estimate holds in the case i = −1 our construction of F_{n} implies

\frac{1}{n} ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{0} \\ A∩E≠∅ \end{matrix}} ∑_{x_{l}∈A} ξ_{T}^{2} (l) ≥ ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{0} \\ A∩E≠∅ \end{matrix}}(1−2δ)(P_{X}(A)− \frac{δ}{M} ) ≥ P_{X}(E^{0})− \frac{3}{q^{∗}} δ . (5)

Now let us consider an A ∈ P_{i}^{+} with A ∩ E ≠ ∅. Without loss of generality we may assume that i = 1 again. Then for fixed z ∈ A ∩ E and a := −(⟨w_{T} , Φ(z)⟩ + b_{T} ) ≥ 0 we obtain

ξ_{T} (l) ≥ \begin{cases}1 − δ + a & for x_{l} ∈ A with y_{l} = 1 \\ max\{0, 1 − δ − a\} & for x_{l} ∈ A with y_{l} = −1 \end{cases}

analogously to the above considerations. We first treat the case 1 − δ − a ≥ 0. Since there are at least (P_{X}(A) − δ/M)n samples in A and at least ((1 − p^{∗})P_{X}(A) − δ/M)n correctly labeled samples in A we get

\frac{1}{n} ∑_{x_{l}∈A} ξ_{T}^{2} (l) ≥ (1 − δ + a)^{2}((1 − p^{∗})P_{X}(A) − \frac{δ}{M} ) + (1 − δ − a)^{2}p^{∗}P_{X}(A)

≥ P_{X}(A)((1 − δ + a)^{2}(1 − p^{∗}) + (1 − δ − a)^{2}p^{∗}) − \frac{4δ}{M} .

Now an easy minimization with respect to a ∈ [0, 1 − δ] yields

\frac{1}{n} ∑_{x_{l}∈A} ξ_{T}^{2} (l) ≥ P_{X}(A)((1 − δ)^{2}(1 − p^{∗}) + (1 − δ)^{2}p^{∗}) − \frac{4δ}{M} ≥ (1 − 2δ)P_{X}(A) − \frac{4δ}{M} .

On the other hand, if 1 − δ − a < 0 we have 1 − δ + a > 2 − 2δ and thus the same inequality follows:

\frac{1}{n} ∑_{x_{l}∈A} ξ_{T}^{2} (l) ≥ (1 − δ + a)^{2}((1 − p^{∗})P_{X}(A) − \frac{δ}{M} ) ≥ (1 − 2δ)P_{X}(A) − \frac{4δ}{M} .

Therefore, we obtain

\frac{1}{n} ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E≠∅ \end{matrix}} ∑_{x_{l}∈A} ξ_{T}^{2} (l) ≥ ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E≠∅ \end{matrix}}((1 − 2δ)P_{X}(A) − \frac{4δ}{M} ) .  (6)

Finally, an analogous consideration yields

\frac{1}{n} ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E=∅ \end{matrix}} ∑_{x_{l}∈A} ξ_{T}^{2} (l) ≥ ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E=∅ \end{matrix}}((1 − 2δ)4q^{∗}(1 − q^{∗})P_{X}(A) − \frac{4δ}{M} ) . (7)

Steinwart

Now, the estimates (6) and (7) imply

\frac{1}{n} ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E≠∅ \end{matrix}} ∑_{x_{l}∈A} ξ_{T}^{2} (l) + \frac{1}{n} ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E=∅ \end{matrix}} ∑_{x_{l}∈A} ξ_{T}^{2} (l)

≥ ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E≠∅ \end{matrix}}((1 − 2δ)P_{X}(A) − \frac{4δ}{M} ) + ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E=∅ \end{matrix}}((1 − 2δ)4q^{∗}(1 − q^{∗})P_{X}(A) − \frac{4δ}{M} )
≥ ∑_{i∈\{−1,1\}} ∑_{\begin{matrix}A∈P_{i}^{+} \\ A∩E≠∅ \end{matrix}}(1 − 2δ)(1 − 2q^{∗})^{2}P_{X}(A) + ∑_{\begin{matrix}i∈\{−1,1\} \\ A∈P_{i}^{+} \end{matrix}}(1 − 2δ)4q^{∗}(1 − q^{∗})P_{X}(A) − 4δ
≥ (1 − 2δ)(1 − 2q^{∗})^{2}P_{X}(E^{+}) + (1 − 2δ)4q^{∗}(1 − q^{∗})P_{X}(X^{+}) − 6δ − \frac{2}{q^{∗}} δ
≥ (1 − 2q^{∗})^{2}P_{X}(E^{+}) + 4q^{∗}(1 − q^{∗})P_{X}(X^{+}) − \frac{7}{q^{∗}} δ .

The latter inequality together with (5) yields

\frac{1}{n} ∑_{l=1}^{n} ξ_{T}^{2} (l) ≥ P_{X}(E^{0}) + (1 − 2q^{∗})^{2}P_{X}(E^{+}) + 4q^{∗}(1 − q^{∗})P_{X}(X^{+}) − \frac{10}{q^{∗}}δ .

Combining this estimate with (4) we now obtain

⟨w^{∗}, w^{∗}⟩

≥ c (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^{∗}}δ)
≥ c^{∗}(P_{X}(E^{0}) + (1 − 2q^{∗})^{2}P_{X}(E^{+}) − 4(p^{∗} − q^{∗})P_{X}(X^{+}) − \frac{37}{q^{∗}}δ) .  (8)

Moreover, a simple calculation shows

R_{P} (f_{T}^{2,k,c/n}) = R_{P} + ∫_{E} (1 − 2p) dP_{X} ≤ R_{P} + \frac{1}{1 − 2q^{∗}} (P_{X}(E^{0}) + (1 − 2q^{∗})^{2}P_{X}(E^{+}))

and thus P_{X}(E^{0}) + (1 − 2q^{∗})^{2}P_{X}(E^{+}) ≥ (1 − 2q^{∗})(R_{P} (f_{T}^{2,k,c/n}) − R_{P}). With this and (8) we find

⟨w^{∗}, w^{∗}⟩ ≥ \frac{2 ⟨w^{∗}, w^{∗}⟩}{ε(1 − 2q^{∗})}((1 − 2q^{∗})(R_{P} (f_{T}^{2,k,c/n}) − R_{P} ) − 4(p^{∗} − q^{∗})P_{X}(X^{+}) − \frac{37}{q^{∗}}δ) .

The latter inequality finally implies

R_{P} (f_{T}^{2,k,c/n}) − R_{P} ≤ \frac{ε}{2} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + \frac{37}{(1 − 2q^{∗})q^{∗}} \frac{ε(1 − 2q^{∗})q^{∗}}{74}
= 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε .

Thus the assertion follows.

We have to prove the remaining lemmas now. We begin with the lemma that constructs the partitions P_{i}^{j} of the above proof:

Lemma 13 Using the notations of the proof of Theorem 12 there exist partitions P_{i}^{j} of K_{i}^{j}, i ∈ {−1, 1}, j ∈ {0, +}, such that diam_{d_{k}}(A) ≤ σ for all A ∈ P_{i}^{j}, i ∈ {−1, 1}, j ∈ {0, +}, and

| ⋃_{\begin{matrix}i∈\{−1,1\} \\ j∈\{0,+\} \end{matrix}} P_{i}^{j}| ≤ N ((X, d_{k}), σ) .  (9)

Proof By the definition of the covering numbers there exists a partition P of X with diam_{d_{k}}(A) ≤ σ for all A ∈ P and |P| ≤ N ((X, d_{k}), σ). Let us define P̃_{i}^{j} := {A ∈ P : A ∩ K_{i}^{j} ≠ ∅} and P_{i}^{j} := {A ∩ K_{i}^{j} : A ∈ P̃_{i}^{j}}. Therefore, to prove (9) we have to show that the P̃_{i}^{j}’s are mutually disjoint. Assume the converse, i.e. there exists A ∈ P̃_{i}^{j} ∩ P̃_{i′}^{j′} with i ≠ i′ or j ≠ j′. By the definition of the partitions there exist z_{1}, z_{2} ∈ A with z_{1} ∈ K_{i}^{j} and z_{2} ∈ K_{i′}^{j′}. Now on the one hand, we obtain

|⟨w^{∗}, Φ(z_{1}) − Φ(z_{2})⟩| ≤ ∥w^{∗}∥ d_{k}(z_{1}, z_{2}) ≤ ∥w^{∗}∥ σ ≤ ∥w^{∗}∥ \frac{δ}{\sqrt{c^{∗}}} < δ

but on the other hand we also have

|⟨w^{∗}, Φ(z_{1}) − Φ(z_{2})⟩| = |⟨w^{∗}, Φ(z_{1})⟩ − ⟨w^{∗}, Φ(z_{2})⟩| ≥ 1 − (1 − 2p^{∗}) ≥ δ^{∗} ≥ δ .

Therefore the assertion follows.

Lemma 14 Using the notations of the proof of Theorem 12 we have

P^{n}(F_{n}) ≥ 1 − 3Me^{−2(\frac{δ}{M})^{2}n} .

Proof Let us recall Hoeffding’s inequality (cf. Devroye et al., 1997, Thm. 8.1) which in particular states that for all i.i.d. random variables z_{i} : (Ω, A, Q) → {0, 1} and all ε > 0, n ≥ 1 we have

Q^{n}(∑_{i=1}^{n} z_{i} ≤ n(q − ε)) ≤ e^{−2ε^{2}n} ,

where q := Q(z_{i} = 1). Thus for A ∈ P_{i}^{+} we get

P^{n}(F_{n,A}^{+})
≥ P^{n}(\{((x_{1}, y_{1}), …, (x_{n}, y_{n})) : |\{l : x_{l} ∈ A, y_{l} = i\}| ≥ (∫_{A}(1 − p) dP_{X} − \frac{δ}{M} ) n\})
≥ 1 − P^{n}(\{((x_{1}, y_{1}), …, (x_{n}, y_{n})) : |\{l : x_{l} ∈ A, y_{l} = i\}| ≤ (∫_{A}(1 − p) dP_{X} − \frac{δ}{M} ) n\})
≥ 1 − e^{−2(\frac{δ}{M})^{2}n} ,

i.e. P^{n}(Z^{n} \F_{n,A}^{+}) ≤ e^{−2(\frac{δ}{M})^{2}n}, where Z := X ×Y. Analogously, we obtain P^{n}(Z^{n} \F_{n,A}^{−}) ≤

e^{−2(\frac{δ}{M})^{2}n} for all A ∈ P_{i}^{+} and P^{n}(Z^{n} \ F_{n,A}) ≤ e^{−2(\frac{δ}{M})^{2}n} for all A ∈ P_{i}^{j}. These estimates yield

P^{n}(F^{n})
= P^{n}( ⋂_{A∈P_{−1}^{0}∪P_{1}^{0}} F_{n,A} ∩ ⋂_{A∈P_{−1}^{+}∪P_{1}^{+}}(F_{n,A} ∩ F_{n,A}^{+} ∩ F_{n,A}^{−}))

= 1 − P^{n}( ⋃_{A∈P_{−1}^{0}∪ P_{1}^{0}}(Z^{n} \ F_{n,A}) ∪ ⋃_{A∈P_{−1}^{+}∪P_{1}^{+}}((Z^{n} \ F_{n,A})∪(Z^{n} \ F_{n,A}^{+})∪(Z^{n} \ F_{n,A}^{−})))

≥ 1 − ∑_{\begin{matrix}A∈P_{−1}^{j}∪P_{1}^{j} \\ j∈\{0,+\} \end{matrix}} P^{n}(Z^{n} \ F_{n,A})− ∑_{A∈P_{−1}^{+}∪P_{1}^{+}} P^{n}(Z^{n} \ F_{n,A}^{+})− ∑_{A∈P_{−1}^{+}∪P_{1}^{+}} P^{n}(Z^{n} \ F_{n,A}^{−})

≥ 1 − 3Me^{−2(\frac{δ}{M})^{2}n} .

With the help of Theorem 12 we can now investigate how to choose the parameter sequence (c_{n}) for a given universal kernel:

Theorem 15 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 N ((X, d_{k}), ε) ∈ O(ε^{−α}) for some α > 0. Suppose that we have a positive sequence (c_{n}) with (c_{n}) ∈ O(n^{β−1}) for some 0 < β < \frac{1}{α} and nc_{n} → ∞. Then for all Borel probability measures P on X × Y with q^{∗}, p^{∗} ∈ (0, 1/2) and all ε > 0 we have

lim_{n→∞} Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P} (f_{T}^{2,k,c_{n}}) ≤ R_{P} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε\}) = 1 .

Proof Let γ := \frac{1−αβ}{4(1+α)} > 0 and δ_{n} := n^{−γ}. By Theorem 12 there exist c^{∗} > 0 and δ^{∗} > 0 such that for all c ≥ c^{∗}, 0 < δ ≤ δ^{∗} and all n ≥ 1 we have

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P} (f_{T}^{2,k,c/n}) ≤ R_{P} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε\}) ≥ 1 − 3Me^{−2(\frac{δ}{M})^{2}n} ,

where M := N ((X, d_{k}), \frac{δ}{\sqrt{c}}). Since δ_{n} → 0 and nc_{n} → ∞ we may fix an n_{0} ≥ 1 such that for all n ≥ n_{0} we have both δ_{n} ≤ δ^{∗} and nc_{n} ≥ c^{∗}. This yields

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P} (f_{T}^{2,k,c_{n}}) ≤ R_{P} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε\}) ≥ 1 − 3M_{n}e^{−2( \frac{δn}{Mn} )^{2}n} ,

where M_{n} := N ((X, d_{k}), \frac{δ_{n}}{\sqrt{nc_{n}}} ). This implies M_{n} ∈ O(n^{α(γ+β/2)}) and hence we easily check

that M_{n}e^{−( \frac{δn}{Mn} )^{2}n} ∈ O(e^{−n^{2(1+α)γ}}) holds. Thus the assertion follows.

Corollary 16 Under the assumptions of Theorem 15 the 2-SMC with sequence (c_{n}) is consistent for all Borel probability measures P on X × Y with q^{∗} = p^{∗} < 1/2. In particular this holds for all Borel probability measures with constant noise level.

Corollary 17 Let X ⊂ ℝ^{d} be compact and k be a Gaussian RBF kernel on X. Let 0 < β < \frac{1}{d} and (c_{n}) be a positive sequence with (c_{n}) ∈ O(n^{β−1}) and nc_{n} → ∞. Then the 2-SMC with kernel k and sequence (c_{n}) is consistent for all Borel probability measures P on X × Y with q^{∗} = p^{∗} < 1/2.

Proof Let σ > 0 and k(x, y) := exp(−σ^{2}∥x − y∥_{2}^{2}). Since 1 − e^{−t} ≤ t for all t ≥ 0 we observe

d_{k}(x, y) = \sqrt{2 − 2 exp(−σ^{2}∥x − y∥_{2}^{2})} ≤ \sqrt{2}σ∥x − y∥_{2} .

This yields N ((X, d_{k}), ε) ≤ N ((X, ∥.∥_{2}), \frac{ε}{\sqrt{2}σ} ) and thus N ((X, d_{k}), ε) ∈ O(ε^{−d}) (cf. Carl & Stephani, 1990, p. 9).

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:

Theorem 18 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×Y with a deterministic supervisor and with classes B_{−1}(P), B_{1}(P) which have strictly positive distance, i.e. d(B_{−1}(P), B_{1}(P)) > 0. Then k separates B_{−1}(P) and B_{1}(P) with margin γ > 0 and for all c > 0, ε > 0 and n ≥ mM we have

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P,S}(f_{T}^{2,k,c}) ≤ ε\}) ≥ 1 − M e^{− \frac{εn}{2M} +m} .

Here, M := N ((X, d_{k}), γ/2) is the covering number of (X, d_{k}) and m := ⌊\frac{4}{cγ^{2}} ⌋ + 1.

Proof Since (X, d_{k}) is precompact and d(B_{−1}(P), B_{1}(P)) > 0 both B_{i}(P) are compact, too. Thus they can be separated with margin γ > 0 by Corollary 6. In analogue to Lemma 13 we now construct partitions P̃_{i} of B_{i}(P), i ∈ {−1, 1} such that diam_{d_{k}}(A) ≤ γ/2 for all A ∈ P̃_{i} and |P̃_{−1} ∪ P̃_{1}| ≤ M. We define P_{i} := \{A ∈ P̃_{i} : P_{X}(A) > \frac{ε}{M} \} for i ∈ \{−1, 1\}. Moreover, for n ≥ mM and A ∈ P_{−1} ∪ P_{1} let

F_{n,A} := {((x_{1}, y_{1}), …, (x_{n}, y_{n})) ∈ (X × Y)^{n} : |{l : x_{l} ∈ A}| ≥ m}
F_{n} := ⋂_{A∈P_{−1}∪P_{1}} F_{n,A} .

For n ≥ mM the Chernoff-Okamoto inequality (see e.g. Dudley, 1978) then yields

P^{n}((X × Y)^{n} \ F_{n,A}) ≤ exp(−\frac{(n\frac{ε}{M} − (m − 1))^{2}}{2n\frac{ε}{M} (1 − \frac{ε}{M} )} )

≤ exp(−\frac{n^{2}(\frac{ε}{M} )^{2} − 2n\frac{ε}{M} (m − 1) + (m − 1)^{2}}{2n\frac{ε}{M}} )
≤ exp(−\frac{εn}{2M} + m)

and thus P^{n}(F_{n}) ≥ 1 − M e^{− \frac{εn}{2M} +m} for all n ≥ mM. Hence it suffices to show that for all T = ((x_{1}, y_{1}), …, (x_{n}, y_{n})) ∈ F_{n} the decision function f_{T}^{2,k,c} classifies ⋃_{A∈P_{1}} A and ⋃_{A∈P_{−1}} A correctly. To see this we fix a feature map Φ : X → H of k. For brevity’s sake the unique solution of problem (3) is denoted by (w_{T} , b_{T} , ξ_{T}). Furthermore, (w^{∗}, b^{∗}) ∈ S_{H} × ℝ is a hyperplane that separates Φ(B_{1}(P)) and Φ(B_{−1}(P)) with margin γ > 0. Then we have y_{l}(⟨w^{∗}, Φ(x_{l})⟩ + b^{∗}) ≥ γ for all l = 1, …, n and therefore we obtain

⟨w_{T} , w_{T} ⟩ + c ∑_{l=1}^{n} ξ_{l}^{2} ≤ ⟨\frac{w^{∗}}{γ} , \frac{w^{∗}}{γ} ⟩ = \frac{1}{γ^{2}} .

In particular this implies ∥w_{T} ∥ ≤ 1/γ. Now, let us suppose that there exists a misclassified point z. Without loss of generality we may assume that z ∈ ⋃_{A∈P_{1}} A. Hence there is an A ∈ P_{1} with z ∈ A and for this there exist mutually different indexes l_{1}, …, l_{m} such that x_{l_{j}} ∈ A. In particular this yields d_{k}(x_{l_{j}}, z) ≤ γ/2 for all j = 1, …, m. Since ⟨w_{T} , Φ(z)⟩ + b_{T} ≤ 0 we thus obtain

1−ξ_{l_{j}} ≤ ⟨w_{T} , Φ(x_{l_{j}})⟩+b_{T} = ⟨w_{T} , Φ(x_{l_{j}})−Φ(z)⟩+⟨w_{T} , Φ(z)⟩+b_{T} ≤ ∥w_{T} ∥ d_{k}(x_{l_{j}}, z) ≤ \frac{1}{2}.

Hence we have ξ_{l_{j}} ≥ 1/2 and this leads to the contradiction

\frac{1}{γ^{2}} ≥ ⟨w_{T} , w_{T} ⟩ + c ∑_{l=1}^{n} ξ_{l}^{2} ≥ c ∑_{j=1}^{m} ξ_{l_{j}}^{2} ≥ \frac{cm}{4} = \frac{c}{4}(⌊\frac{4}{cγ^{2}} ⌋ + 1) > \frac{1}{γ^{2}} .

Therefore the assertion follows.

Theorem 18 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 (3) 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 P_{i} whose probability was larger than or equal to \frac{ε}{M}. If we extend our considerations to all elements with strictly positive probability we obtain the following theorem:

Theorem 19 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×Y with a deterministic supervisor and with classes B_{−1}(P), B_{1}(P) which have strictly positive distance, i.e. d(B_{−1}(P), B_{1}(P)) > 0. Then k separates B_{−1}(P) and B_{1}(P) with margin γ > 0 and for all c > 0 there exists a constant ρ > 0 such that for all n ≥ (⌊\frac{4}{cγ^{2}} ⌋ + 1)N ((X, d_{k}), γ/2) we have

Pr^{∗}({T ∈ (X × Y)^{n} : R_{P,S}(f_{T}^{2,k,c}) = 0}) ≥ 1 − e^{−ρn} ,

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 (⟨., .⟩ + c)^{m}, c ≥ 0, m ∈ ℕ, on a subset X of ℝ^{n}. 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 18 and 19:

Proposition 20 Let P_{n}^{d} be the set of all polynomials on X := [0, 1]^{d} whose degree is less than n + 1. Then for all ε > 0 there exists a Borel probability measure P on X × Y with d(B_{1}(P), B_{−1}(P)) > 0, R_{P} = 0 and

inf\{R_{P} (sign f) : f ∈ P_{n}^{d}\} ≥ \frac{1}{2} − ε .

Proof We first treat the case d = 1. We fix an integer m ≥ (3n + 2)/ε and let I_{i} := [(i + ε)/m, (i + 1 − ε)/m], i = 0, …, m − 1. Denoting the Lebesgue measure on I_{i} by λ_{I_{i}} let P_{X} := (1 − 2ε)^{−1} ∑_{i=0}^{m−1} λ_{I_{i}}. Moreover, we define a deterministic supervisor P (.|.) by P (y = 1|x) := 1 for x ∈ I_{2i}, i = 0, …, ⌊(m + 1)/2⌋, and P (y = −1|x) := 1 otherwise. For a fixed polynomial f ∈ P_{n}^{d} we denote its mutually different and ordered zeroes in (0, 1) by x_{1} < … < x_{k}, k ≤ n. For brevity’s sake let x_{0} := 0 and x_{k+1} := 1. Finally, we define a_{j} := |{i : I_{i} ⊂ [x_{j}, x_{j+1}]}| for j = 0, …, k. Then by an easy observation we get ∑_{j=0}^{k} a_{j} ≥ m − k ≥ m − n. Moreover, at most ⌊(a_{j} + 1)/2⌋ intervals I_{i} are correctly classified on [x_{j}, x_{j+1}] by the function sign f. Hence at least

∑_{j=0}^{k}⌊\frac{a_{j}}{2} ⌋ ≥ ∑_{j=0}^{k}(\frac{a_{j}}{2} − 1) ≥ \frac{m − n}{2} − (k + 1) ≥ \frac{m − 3n − 2}{2}

intervals I_{i} are not correctly classified on [0, 1] by sign f. Since P_{X}(I_{i}) = 1/m we thus obtain

R_{P} (sign f) ≥ \frac{1}{m} ∑_{j=0}^{k}⌊\frac{a_{j}}{2} ⌋ ≥ \frac{1}{2} − \frac{3n + 2}{m} ≥ \frac{1}{2} − ε .

To treat the case d > 1 we have to embed [0, 1] into [0, 1]^{d} via t ↦ (t, 0, …, 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.

5. The 1-norm soft margin classifier

We now consider the 1-norm soft margin classifier. Again we fix a kernel k on X with feature map Φ : X → H. For a training set T = ((x_{1}, y_{1}), …, (x_{n}, y_{n})) ∈ (X × Y)^{n} and c_{n} > 0 we denote a solution of the optimization problem

minimize  ⟨w, w⟩ + c_{n} ∑_{i=1}^{n} ξ_{i}  over w, b, ξ
subject to  y_{i}(⟨w, Φ(x_{i})⟩ + b) ≥ 1 − ξ_{i},  i = 1, …, n
ξ_{i} ≥ 0,  i = 1, …, n

(10)

by (w_{T}^{1,k,c_{n}}, b_{T}^{1,k,c_{n}}) ∈ H × ℝ. An algorithm C_{k}^{1,(c_{n})} that provides the decision function

f_{T}^{1,k,c}(x) := sign(⟨w_{T}^{1,k,c_{n}}, Φ(x)⟩ + b_{T}^{1,k,c_{n}}) , x ∈ 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 Cristianini & Shawe-Taylor (2000, Ch. 6 and 7) and Vapnik (1998, Ch. 10)

Burges & Crisp (2000) proved that in general the optimization problem (10) has no unique solution. Although the 1-SMC only has to construct an arbitrary 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 12:

Theorem 21 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 ×Y with q^{∗}, p^{∗} ∈ (0, 1/2) and all ε > 0 there exist c^{∗} > 0 and δ^{∗} > 0 such that for all c ≥ c^{∗}, 0 < δ ≤ δ^{∗} and all n ≥ 1 we have

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P} (f_{T}^{1,k,c/n}) ≤ R_{P} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε\}) ≥ 1 − 3Me^{−2(\frac{δ}{M})^{2}n} ,

where M := 4N ((X, d_{k}), \frac{δ}{\sqrt{c}}) is essentially the covering number of X with respect to the metric d_{k} which is induced by the kernel k.

Sketch of the proof Since the proof is very similar to that of Theorem 12 we only point out the main differences besides adjusting the constants: Firstly the vector w^{∗} ∈ H has to be chosen in a different manner, namely it has to fulfill

⟨w^{∗}, Φ(x)⟩ ∈ \begin{cases}i [1, 1 + δ] & if x ∈ K_{i}^{j} \\ [−(1 + δ), 1 + δ] & otherwise. \end{cases}

This condition also enforces the second modification since Lemma 13 does not hold anymore in this setting. Indeed, we cannot guarantee that the definition of the P̃_{i}^{j}’s in Lemma 13 implies that they are mutually disjoint. Instead, we only obtain |P̃_{i}^{j}| ≤ N((X, d_{k}), \frac{δ}{\sqrt{c}}) and thus

| ⋃_{\begin{matrix}i∈\{−1,1\} \\ j∈\{0,+\} \end{matrix}} P_{i}^{j}| ≤ 4N ((X, d_{k}), σ) .

The latter explains the definition of M, which is different to that of Theorem 12.

Following the proof of Theorem 15 we obtain an analogous result for the 1-SMC:

Theorem 22 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 N ((X, d_{k}), ε) ∈ O(ε^{−α}) for some α > 0. Suppose that we have a positive sequence (c_{n}) with (c_{n}) ∈ O(n^{β−1}) for some 0 < β < \frac{1}{α} and nc_{n} → ∞. Then for all Borel probability measures P on X × Y with q^{∗}, p^{∗} ∈ (0, 1/2) and all ε > 0 we have

lim_{n→∞} Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P} (f_{T}^{1,k,c_{n}}) ≤ R_{P} + 4\frac{p^{∗} − q^{∗}}{1 − 2q^{∗}} P_{X}(X^{+}) + ε\}) = 1

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:

Corollary 23 Let X ⊂ ℝ^{d} be compact and k be a Gaussian RBF kernel on X. Let 0 < β < \frac{1}{d} and (c_{n}) be a positive sequence with (c_{n}) ∈ O(n^{β−1}) and nc_{n} → ∞. Then the 1-SMC with kernel k and sequence (c_{n}) is consistent for all Borel probability measures P on X × Y with q^{∗} = p^{∗} < 1/2.

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 18. However, a result that is analogous to Theorem 19 also holds.

Theorem 24 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×Y with a deterministic supervisor and with classes B_{−1}(P), B_{1}(P) which have strictly positive distance, i.e. d(B_{−1}(P), B_{1}(P)) > 0. Then k separates B_{−1}(P) and B_{1}(P) with margin γ > 0 and for all c > 0, ε > 0 and n ≥ mM we have

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P,S}(f_{T}^{1,k,c}) ≤ ε\}) ≥ 1 − M e^{− \frac{εn}{2M} +m} ,

where M := N ((X, d_{k}), γ/2) is the covering number of (X, d_{k}) and m := ⌊\frac{2}{cγ^{2}} ⌋ + 1.

Sketch of the proof The proof is completely analogous to that of Theorem 18. However, since the slack variables are not squared we obtain

c ∑_{j=1}^{m} ξ_{l_{j}} ≥ \frac{cm}{2}

in the last estimate of the proof of Theorem 18 and this yields the slightly better value of m.

Finally we mention that using polynomial kernels Proposition 20 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).

6. The maximal margin hyperplane classifier

We finally consider the maximal margin classifier. Again we fix a kernel k on X with feature map Φ : X → H. For a training set T = ((x_{1}, y_{1}), …, (x_{n}, y_{n})) ∈ (X × Y)^{n} we denote the unique solution of the optimization problem

minimize  ⟨w, w⟩  over w, b
subject to  y_{i}(⟨w, Φ(x_{i})⟩ + b) ≥ 1,  i = 1, …, n

(11)

by (w_{T}^{k} , b_{T}^{k}) ∈ H × ℝ. An algorithm C_{k} that provides the decision function

f_{T}^{k}(x) := sign(⟨w_{T}^{k} , Φ(x)⟩ + b_{T}^{k}) , x ∈ 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 Cristianini & Shawe-Taylor (2000, Ch. 6 and 7) and Vapnik (1998, Ch. 10).

The MMC is assumed to work poorly in the absence of large margins (cf. Tong Zhang, 2001). Thus we only consider the setting of Theorem 18. We begin with a result similar to Theorem 18 and Theorem 24:

Theorem 25 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×Y with a deterministic supervisor and with classes B_{−1}(P), B_{1}(P) which have strictly positive distance, i.e. d(B_{−1}(P), B_{1}(P)) > 0. Then k separates B_{−1}(P) and B_{1}(P) with margin γ > 0 and for all ε > 0 and n ≥ M := N ((X, d_{k}), γ/2) we have

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P,S}(f_{T}^{k}) ≤ ε\}) ≥ 1 − M e^{n ln(1− \frac{ε}{2M})} .

Sketch of the proof We repeat the construction of the proof of Theorem 18 with m := 1. An easy calculation then shows

P^{n}(F_{n}) ≥ 1 − M e^{n ln(1− \frac{ε}{2M})} .

Now suppose that for T ∈ F_{n} we have an element z ∈ ⋃_{A∈P_{1}} A misclassified by f_{T}^{k}. Hence there exist an A ∈ P_{1} with z ∈ A and a sample (x_{l}, y_{l}) of T with x_{l} ∈ A. Then the following estimate yields a contradiction:

0 ≥ ⟨w_{T}^{k} , Φ(z)⟩+b_{T}^{k} = ⟨w_{T}^{k} , Φ(z)−Φ(x_{l_{j}})⟩+⟨w_{T}^{k} , Φ(x_{l_{j}})⟩+b_{T}^{k} ≥ ∥w_{T}^{k} ∥ d_{k}(x_{l_{j}}, z)+1 ≥ \frac{1}{2} .

Therefore the assertion follows.

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 25 can be obtained using data-dependent margin-based bounds of Shawe-Taylor et al. (1998). To compare both we first state a corollary:

Corollary 26 Let k_{σ} be the Gaussian RBF kernel with parameter σ on the unit ball X := B_{ℓ_{2}^{d}} of the d-dimensional Euclidean space. Let P be a Borel probability measure on X × Y

which can be separated by k_{σ} with margin γ > 0. Then for all δ ∈ (0, 1) and all n ≥ 2(\frac{16σ}{γ} )^{d} we have

Pr^{∗}(\{T ∈ (X × Y)^{n} : R_{P,S}(f_{T}^{k}) ≤ \frac{4d}{n}(\frac{16σ}{γ} )^{d}(d ln \frac{16σ}{γ} + ln \frac{2}{δ})\}) ≥ 1 − δ .

Proof As already shown in the proof of Corollary 17 we have

N ((X, d_{k}), ε) ≤ N ((X, ∥.∥_{2}), \frac{ε}{\sqrt{2}σ} ) ≤ 2 · 5^{d}(\frac{ε}{\sqrt{2}σ} )^{−d} ≤ 2(8σ)^{d}ε^{−d}

and thus M := N ((X, d_{k}), γ/2) ≤ 2(16σ)^{d}γ^{−d}. Now let ε := 2M(1 − (\frac{δ}{M} )^{1/n}) for n ≥ 2(16σ)^{d}γ^{−d}, i.e. δ = M(1 − \frac{ε}{2M} )^{n}. Since ε < \frac{2M}{n} ln \frac{M}{δ} Theorem 25 yields the assertion.

Corollary 26 shows that the learning curve of the MMC is of order O(n^{−1}) provided that P guarantees a large margin. These conditions also allow the application of margin-based bounds on generalization proved by Shawe-Taylor et al. (1998) (cf. also Bartlett & Shawe-Taylor, 1999; Cristianini & Shawe-Taylor, 2000). We then obtain that the learning curve is of order 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 γ is essentially of order O(γ^{−2}) in the estimates of Shawe-Taylor et al. (1998) while the Corollary 26 shows that our estimates are essentially influenced by order O(γ^{−d}), where d is the dimension of the input space X. We thus suppose that only for small input dimensions d our estimates are more suitable to treat realistic sample sizes.

7. 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 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 Tong Zhang (2001, p. 442) 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 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^{∗} ∈ (0, 1/2). Moreover, we suppose that the universality of kernels is also very important for related algorithms such as ν-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.

Remark Using the techniques of this work the author was recently able to prove universal consistency for the 1-SMC (cf. Steinwart, 2001b).

Acknowledgments

We would like to acknowledge support for this project from the Deutsche Forschungsgemeinschaft (DFG grant Ca 179/4-1).

References

P. Bartlett and J. Shawe-Taylor. Generalization performance of support vector machines and other pattern classifiers. In B. Schölkopf, C.J.C. Burges, and A.J. Smola, editors, Advances in Kernel Methods - Support Vector Learning, pages 43-54, Cambridge, MA, 1999. MIT Press.

C.J.C. Burges and D.J. Crisp. Uniqueness of the SVM solution. In M.I. Jordan, T.K. Leen, and K.-R. Müller, editors, Advances in Neural Information Processing 12, pages 223-229, Cambridge, MA, 2000. MIT Press.

N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press, Cambridge, 2000.

B. Carl and I. Stephani. Entropy, compactness and the approximation of operators. Cambridge University Press, Cambridge, 1990.

L. Devroye, L. Györfi and G. Lugosi. A probabilistic theory of pattern recognition. Springer, New York, 1997.

R.M. Dudley. Central limit theorems for empirical measures, Ann. Probab., 6(6):899-929, 1978.

R.M. Dudley. Real Analysis and Probability. Chapman & Hall, New York, 1989.

S. Gradstein and I.M. Ryshik. Summen- Produkt- und Integraltafeln * Tables of series, products and integrals. Verlag Harri Deutsch, Frankfurt am Main, 1981.

G.K. Pedersen. Analysis Now. Springer, Berlin, 1988.

T. Poggio. On optimal nonlinear associative recall. Biological Cybernetics, 19(4):201-209, 1975.

C. Saunders, M.O. Stitson, J. Weston, L. Bottou, B. Schölkopf, 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. Avail-

able electronically at http://www.dcs.rhbnc.ac.uk/research/compint/areas/comp_
learn/sv/pub/report98-03.ps, 1998.

B. Schölkopf, R. Herbrich, A.J. Smola, and R.C. Williamson. A generalized representer theorem. In Proceedings of the 14th Annual Conference on Computational Learning Theory, Lecture Notes in Artificial Intelligence 2111, pages 416-426, 2001.

J. Shawe-Taylor, P.L. Bartlett, R.C. Williamson and M. Anthony. Structural risk minimization over data-dependent hierarchies. IEEE Trans. Inf. Theory 44(5):1926-1940, 1998.

I. Steinwart. On the influence of the kernel on the generalization ability of support vector machines. Technical Report 01-01, Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Jena, Germany, available electronically at http://www.

minet.uni-jena.de/Math-Net/reports/sources/2001/01-01report.ps, 2001a.

I. Steinwart. On the generalization ability of support vector machines. Submitted to J. Complexity, 2001b.

Tong Zhang. A leave-one-out cross validation bound for kernel methods with applications in learning. In Proceedings of the 14th Annual Conference on Computational Learning Theory, Lecture Notes in Artificial Intelligence 2111, pages 427-443, 2001.

A.W. van der Vaart and J.A. Wellner. Weak Convergence and Empirical Processes. Springer, New York, 1996.

V.N. Vapnik. Statistical Learning Theory. Wiley, New York, 1998.