© Springer Nature Singapore Pte Ltd. 2020

X.-D. ZhangA Matrix Algebra Approach to Artificial Intelligencehttps://doi.org/10.1007/978-981-15-2770-8_8

8. Support Vector Machines

Xian-Da Zhang¹  

(1)

Department of Automation, Tsinghua University, Beijing, Beijing, China

 

 Deceased

Supervised regression/classification methods learn a model of relation between the target vectors and the corresponding input vectors consisting of N training samples and utilize this model to predict/classify target values for the previously unseen inputs.

In real-world data, the presence of noise (in regression) and class overlap (in classification) implies that the principal modeling challenge is to avoid “overfitting” of the training set, which is an important concern with this modeling.

Unlike traditional neural network approaches which suffer difficulties with generalization, producing models that may overfit the data, SVMs [43] are a popular machine learning approach for classification, regression, and other learning tasks, based on statistical learning theory (Vapnik–Chervonenkis or VC-theory).

In regression and classification applications, SVMs draw on two main practical observations [5, pp. 12–13]:

• At a sufficiently high dimension, patterns are orthogonal to each other, and thus it is easier to find a separating hyperplane for data in a high dimension space.

• Not all patterns are necessary for finding a separating hyperplane. In fact, it is sufficient to use only those points that are near the boundary between groups to construct the boundary.

As a kind of generalization intelligence, this chapter presents SVMs together with applications in target regression and classification.

8.1 Support Vector Machines: Basic Theory

Support vector machines comprise a new class of learning algorithms, originally developed for pattern recognition [3, 46], and motivated by results of statistical learning theory [43].

The problem of empirical data modeling is germane to many engineering applications. In empirical data modeling a process of induction is used to build up a model of the system under study, and it is hoped to deduce responses of the system that have yet to be observed.

The SVMs aim at minimizing an upper bound of the generalization error by maximizing the margin between the separating hyperplane¹ and the data. What makes SVMs attractive is the property of condensing information in the training data and providing a sparse representation by using a very small number of data points (support vectors, SVs) [17].

8.1.1 Statistical Learning Theory

This subsection is a very brief introduction to statistical learning theory [42, 44].

Statistical learning theory based modeling aims at choosing a model from the hypothesis space, which is closest (with respect to some error measure) to the underlying function in the target space.

Errors in SVM modeling arise from two cases [19]:

• Approximation Error is a consequence of a poor choice of the hypothesis space smaller than the target space, which will result in a large approximation error, and is referred to as model mismatch.

• Estimation Error is the error due to the learning procedure which results in a technique selecting the non-optimal model from the hypothesis space.

In order to choose the best available approximation to the supervisor’s response, it is important to measure the loss or discrepancy L(y, f(w, x)) between the response y of the supervisor to a given input x and the response f(w, x) provided by the learning machine.

Given a training set of N independent observations . We would like to find the function f such that the expected value of the loss, called the risk function, is minimized:

(8.1.1)

where P(x, y) is the joint probability distribution. The goal of SVM is to minimize the risk function R(w) over the class of functions f(w, x), w ∈ W.

The problem is: the joint probability distribution P(x, y) = P(y|x)P(x) is unknown, and the only available information is contained in the training set .

In order to solve this problem, the incalculable risk function R(w) should be approximated by the empirical risk function

(8.1.2)

which can be constructed by using the training set . In the above equation, the Boolean function f(w, x _i) on the input feature x _i and a set of Boolean functions on the input features {f(w, x _i), w ∈ W, x _i ∈ X} are known as hypothesis and hypothesis space, respectively.

Empirical risk minimization (ERM) principle is to minimize R _emp(w) over the set w ∈ W, results in a risk which is close to its minimum.

The evaluation of the soundness of the ERM principle requires answers to the following two questions [42]:

1. 1.
   Does the empirical risk R _emp(w) converge uniformly to the actual risk R(w) over the full set f(w, x), w ∈ W, namely

   

   (8.1.3)
    
2. 2.

   What is the rate of convergence?

    

The theory of uniform convergence of empirical risk to actual risk includes necessary and sufficient conditions as well as bounds for the rate of convergence. These bounds independent of the distribution function P(x, y) are based on the Vapnik–Chervonekis (VC) dimension of the set of functions f(w, x) implemented by the learning machine.

For a set of functions {f(w)}, w is a generic set of parameters: a choice of w specifies a particular function and can be defined for various classes of function f.

Let us consider only the functions corresponding to the two-class pattern recognition case, so that f(w, x) ∈{−1, 1}, ∀w, x.

If a given set of N data points can be labeled in all possible 2^N ways, and for each labeling, a member of the set {f(w)} with correctly assigned labels can be found, then the set of points is said to be shattered by the set of functions.

Suppose that the space in which the data live is , and the set {f(w)} consists of oriented straight lines, so that for a given line, all points on one side are assigned to the class 1, and all points on the other side, the class − 1, as shown in Fig. 8.1.

Fig. 8.1

Three points in , shattered by oriented lines. The arrow points to the side with the points labeled black

One can find at least one set of 3 points in 2D all of whose 2³ = 8 possible labeling can be separated by some hyperplane. The orientation is shown by an arrow, specifying on which side of the line points is to be assigned the label 1. Any set of 4 points, all of whose 2⁴ = 16 possible labeling, are not separable by hyperplanes.

Suppose we have a data set containing N points. These N points can be labeled in 2N ways as positive “+” and negative “−.” Therefore, 2N different learning problems can be defined by N data points. If for any of these problems, we can find a hypothesis that separates the positive examples from the negative, then we say shatters N points. That is, any learning problem definable by N examples can be learned without error by a hypothesis drawn from .

Definition 8.1 (Indicator Function [12])

Let be a 2n full factorial design with levels − 1 and + 1, and a fractional factorial design be a subset of . The indicator function F of its fraction is a function defined on as follows:

(8.1.4)

Definition 8.2 (VC-Dimension [42])

The VC-dimension of a set of indicator functions f(w, x), w ∈ W is the maximal number h of vectors which can be shattered in all possible 2h ways by f(w, x), w ∈ W.

For example, h = n + 1 for linear decision rules in n-dimensional space, since they can shatter at most n + 1 points.

It is well-known [45] that the finiteness of the VC-dimension of the set of indicator functions implemented by the learning machine forms the necessary and sufficient condition for consistency of the ERM method independent of probability measure. Finiteness of VC-dimension also implies fast convergence.

Theorem 8.1 ([6])

Consider some set of m points in . Choose any one of the points as origin. Then the m points can be shattered by oriented hyperplanes if and only if the position vectors of the remaining points are linearly independent.

Corollary 8.1 ([6])

The VC-dimension of the set of oriented hyperplanes in is n + 1, since we can always choose n + 1 points, and then choose one of the points as origin, such that the position vectors of the remaining n points are linearly independent, but can never choose n + 2 such points (since no n + 1 vectors in can be linearly independent).

8.1.2 Linear Support Vector Machines

We discuss linear SVMs in two cases: the separable case and the nonseparable case.

The Separable Case

Consider first the simplest case: linear machines trained on separable data. We are given the labeled training data with . Suppose we have a “separating hyperplane” which separates the positive from the negative data samples. The points x on the hyperplane satisfy w ^Tx + b = 0, where w is normal to the hyperplane, is the perpendicular distance from the hyperplane to the origin, and is the Euclidean norm of w.

Lemma 8.1 ([6])

Two sets of points in may be separated by a hyperplane if and only if the intersection of their convex hulls is empty.

Let and be the shortest distances from the separating hyperplane to the closest positive and negative data samples, respectively. Then, the “margin” of a separating hyperplane can be defined to be .

For the linearly separable case, the support vector algorithm aims at the separating hyperplane with the largest margin . For this end, all the training data need to satisfy the following constrains:

(8.1.5)

(8.1.6)

The above two constrains can be combined into one set of inequality constrains:

(8.1.7)

Clearly, the points satisfying the equality in (8.1.5) lie on the hyperplane with normal w and perpendicular distance from the origin . Similarly, the points satisfying the equality in Eq. (8.1.6) lie on the hyperplane with normal again w and perpendicular distance from the origin . Then and hence the margin is simply 2∕∥w∥₂.

Due to having the same normal, and are parallel, and no training points fall between them. Thus the pair of hyperplanes (H ₁, H ₂) which gives the maximum margin can be found by minimizing subject to constraints (8.1.7), namely we have the constrained optimization problem:

(8.1.8)

(8.1.9)

For the above equality constraints, the Lagrange multiplier method gives the following unconstrained primal optimization problem:

(8.1.10)

with nonnegative Lagrange multipliers .

From the first-order optimality conditions we have

(8.1.11)

(8.1.12)

Substituting (8.1.11) and (8.1.12) into (8.1.10) can eliminate b, and thus yield the dual objective function

(8.1.13)

Combining (8.1.13) with (8.1.12), we get the Wolfe dual optimization problem corresponding to (8.1.10) as follows:

(8.1.14)

(8.1.15)

for the separable case.

The Nonseparable Case

When applied to nonseparable data, the above separable optimization algorithm will result into no feasible solution. Hence, the inequality constraints (8.1.5) and (8.1.6) must be relaxed by introducing positive slack variables :

(8.1.16)

and

(8.1.17)

(8.1.18)

For an error to occur, the corresponding must exceed unity, so is an upper bound on the number of training errors. Hence, a natural way to assign an extra cost for errors is to change the objective function to be minimized from to , where C is a parameter to be chosen by the user, a larger C corresponding to assigning a higher penalty to errors.

Consider the primal minimization problem

(8.1.19)

(8.1.20)

By the first-order optimality conditions it follows that

(8.1.21)

(8.1.22)

(8.1.23)

By substituting (8.1.21) and (8.1.22) into (8.1.19), and using the constraints (8.1.20) and (8.1.23), we can eliminate and C in the loss to get

(8.1.24)

(8.1.25)

(8.1.26)

which is called the Wolfe dual optimization problem for finding α.

8.2 Kernel Regression Methods

Following the development of support vector machines, positive definite kernels have recently attracted considerable attention in the machine learning community.

8.2.1 Reproducing Kernel and Mercer Kernel

Consider how a linear SVM is generalized to the case where the decision function f(x), whose sign represents the class assigned to data point x, is not a linear function of the data x?

Definition 8.3 (Reproducing Kernel Hilbert Space [47])

A reproducing kernel Hilbert space (RKHS) is a Hilbert space of real-valued function on a compact domain X with the reproducing property that for , and each x ∈ X, there exists M _x, not depending on f such that

(8.2.1)

where is called the evaluation functional of f. That is to say, is a bounded linear functional.

The reproducing property above states that the inner product of a function f and a kernel function K _x, 〈f(⋅), K _x(⋅)〉, is f(x) in the RKHS. Because K _x must ensure reproducing the function f, the function K _x(⋅) is called the reproducing kernel of f for the RKHS H.

A natural question to ask is: how to choose a function K _x which is a reproducing kernel? To answer this question, we define K _x as a two-variable function

(8.2.2)

Definition 8.4 (Gram Matrix [35])

Given a kernel K(x, y) and patterns ∈ X, where X is a closed subset of . The N × N matrix K with entries

(8.2.3)

is called the Gram matrix of the kernel K with respect to .

Definition 8.5 (Positive Definite Kernel [47])

Let X be a closed subset of , and a symmetric function satisfying: for any finite set of points in X and real numbers ,

(8.2.4)

Then K is said to be a positive definite kernel on X.

Denote kernels , then positive definition (pd) kernels have the following general properties:

1. 1.

   If K ₁, …, K _n are p.d. kernels and λ ₁, …, λ _n ≥ 0, then the sum is p.d.

    
2. 2.

   If K ₁, …, K _n are p.d. kernels and α ₁, …, α _n ∈{1, …, N}, then their product is p.d.

    
3. 3.

   For a sequence of p.d. kernels, the limit K =lim_n→∞K _n is p.d., if the limit exists.

    
4. 4.

   If X ₀ ⊆ X, then is also a p.d. kernel.

    
5. 5.
   If is a sequence of p.d. kernels, then

   • is p.d. kernel on X ₁ ×⋯ × X _n.

   • is p.d. kernel on X ₁ ×⋯ × X _n.

    

Definition 8.6 (Reproducing Kernel [1])

Let F be a class of functions f(x) defined in a set E, forming a Hilbert space (complex or real). The function K(x, y) of x and y in E is called a reproducing kernel of F if

1. 1.

   For every y, K(x, y) as function of x belongs to F.

    
2. 2.
   The reproducing property: for every y ∈ E and every f ∈ F,

   

   (8.2.5)

   Here the subscript x ^∗ by the scalar product indicates that the scalar product applies to functions of x.

    

Theorem 8.2 (Moore–Aronszajn Theorem [1])

Let x, y ∈ X and be positive defined. Then, there must be a unique RKHS whose reproducing kernel is K(x, y). Moreover, if the space has the inner product

(8.2.6)

where and , then is an effective RKHS.

Moore–Aronszajn theorem states that there is one-to-one correspondence between positive definite kernel function K(x, y) and RKHS . This is why the kernel function is limited to the reproducing kernel Hilbert space .

The reproducing kernel has the following basic properties [1]:

• Uniqueness. If a reproducing kernel K(x, y) exists, then it is unique.

• Existence. For the existence of a reproducing kernel K(x, y) it is necessary and sufficient that for every y of the set E, f(y) be a continuous functional of f running through the Hilbert space F.

• Positiveness. is a positive matrix in the sense of E.

• One-to-one correspondence. To every positive matrix , there corresponds one and only one class of functions with a uniquely determined quadratic form in it, forming a Hilbert space and admitting K(x, y) as a reproducing kernel.

• Convergence. If the class F possesses a reproducing kernel K(x, y), every sequence of functions {f _n} which converges strongly to a function f in the Hilbert space F, converges also at every point in the ordinary sense, .

The following Mercer’s theorem provides a construction method of the nonlinear reproducing kernel function.

Theorem 8.3 (Mercer’s Theorem)

Each positive definite kernel K(x, y) defined on a compact domain X × X can be written in the form

(8.2.7)

The kernel satisfying Mercer’s theorem is called the Mercer kernel. According to Mercer’s theorem, the nonlinear kernel function is usually constructed by

(8.2.8)

where is a nonlinear function.

The widely used Mercer kernel is the Gaussian radial basis function (GRBF) kernel:

(8.2.9)

or the exponential radial basis function kernel

(8.2.10)

For a radial basis function (RBF) kernel one has the following approximation [16]:

(8.2.11)

where is an N × 1 summation vector with all entries equal to 1.

If the N × N kernel matrix K has the eigenvalue decomposition K = U ΛU ^T, then

(8.2.12)

This result has two important applications.

1. 1.

   Kernel PCA: For given data vectors and an RBF kernel, K dominant eigenvalues and their corresponding eigenvectors of the kernel matrix K give the kernel PCA after the principal components in standard PCA are replaced by the principal components of the kernel matrix K. The kernel PCA was originally proposed by Schölkopf et al. [33].

    
2. 2.

   Kernel K-means clustering: If there are K distinct clustered regions within the N data samples, then there will be K dominant terms that provide a means of estimating the possible number of clusters within the data sample in kernel based K-means clustering [16].

    

Kernel PCA is a nonlinear generalization of PCA in the sense that it is performing PCA in feature spaces of arbitrarily large (possibly infinite) dimensionality. If the kernels are used, then the kernel PCA reduces to standard PCA. Compared to the standard PCA, kernel PCA has the main advantage that no nonlinear optimization is involved; it is essentially linear algebra, as simple as standard PCA.

8.2.2 Representer Theorem and Kernel Regression

We now focus on applications of nonlinear kernel functions in SVMs. The following are widely used types of kernel functions in SVMs [19, 36]:

1. 1.
   Linear SVM uses the linear kernel function

   

   (8.2.13)
    
2. 2.
   Polynomial SVM uses the polynomial kernel of degree d

   

   (8.2.14)
    
3. 3.
   Radial basis function (RBF) SVM consists of the Gaussian radial basis function

   

   (8.2.15)

   or exponential radial basis function

   

   (8.2.16)
    
4. 4.
   Multilayer SVM uses the multilayer perceptron kernel function

   

   (8.2.17)

   for certain values of the scale ρ and offset 𝜗 parameters. Here the support vector (SV) corresponds to the first layer and the Lagrange multipliers to the weights.

    
5. 5.
   B-splines SVM consists of B-splines kernel function of order 2M + 1:

   

   (8.2.18)

   with

   

   (8.2.19)
    
6. 6.
   Summing SVM uses additive kernel function

   

   (8.2.20)

   which is obtained by forming summing kernels, since the sum of two positive definite functions is positive definite.

    

To address the poor generalization properties of SVMs, regularization networks, Gaussian processes, and spline methods, a popular technique is to solve regularized optimization problem in a reproducing kernel Hilbert space :

(8.2.21)

where f is regressor or classifier.

The solution to the problem (8.2.21) was given by Kimeldorf and Wahba in 1971 [24], known as the representer theorem.

Theorem 8.4 (Representer Theorem for Supervised Learning [24, 47])

Given a set of l labeled examples . Any solution to the optimization problem (8.2.21) for SVMs has a representation of the form

(8.2.22)

where .

Denoting then we have

(8.2.23)

Letting , substituting (8.2.22) into (8.2.21), and using (8.2.23), we get the loss expressed by α:

(8.2.24)

From it follows that , which yields the optimal solution

(8.2.25)

This is just the Tikhonov regularization least squares solution.

8.2.3 Semi-Supervised and Graph Regression

Representer theorem for supervised learning (Theorem 8.4) can be extended to semi-supervised learning and/or graph signals.

Theorem 8.5 (Representer Theorem for Semi-Supervised Learning [2])

Given a set of l labeled examples , a set of u unlabeled examples , and the graph LaplacianL. The minimizer of semi-supervised/graph optimization problem

(8.2.26)

admits an expansion

(8.2.27)

in terms of the labeled and unlabeled examples.

Note that the above representer theorem [2] is different from the generalized representer theorem in [35]. When the graph Laplacian L = I, Theorem 8.5 reduces to the representer theorem for semi-supervised learning. If letting further u = 0, then Theorem 8.5 reduces to the representer theorem 8.4 for supervised learning.

Theorem 8.5 shows that the optimization problem (8.2.26) is equivalent to finding the optimal solution α ^∗.

Letting the loss and using (8.2.23), then the loss in (8.2.26) can be represented as [2]:

(8.2.28)

where K is the (l + u) × (l + u) Gram matrix K _ij = K(x _i, x _j), is the (l + u)-dimensional label vector, and J = Diag(1, …, 1, 0, …, 0) is an (l + u) × (l + u) diagonal matrix with the first l diagonal entries 1 and the rest 0.

From , one has the first-order optimization condition

(8.2.29)

Due to K ^TJ ^T = KJ, JJ = J, and Jy −JJKα = Jy −JKα, the optimization condition (8.2.29) gives the optimal solution

(8.2.30)

This solution is known as Laplacian regularized least squares (LapRLS) solution [2].

Interestingly, LapRLS is also available for graph supervised regression and classification. In this setting, the number u of unlabeled samples is equal to zero, resulting to the l × l matrix J = I, and thus (8.2.30) becomes

(8.2.31)

This is just LapRLS solution for supervised regression and classification.

Another interesting fact is that LapRLS contains the regularized least squares (RLS) as a special example. The regularized least squares algorithm for non-graph signals is a fully supervised method where the optimal problem is to find the solution

(8.2.32)

By the classical representer theorem, this solution is given by

(8.2.33)

Substituting (8.2.33) into (8.2.32) then

(8.2.34)

From the first-order optimization condition , it is easy to get

(8.2.35)

which is just the Tikhonov regularization least squares (RLS) solution. Clearly, the Tikhonov RLS solution is a special example of LapRLS solution (8.2.31) for supervised machine learning when the graph Laplacian L is a null matrix.

8.2.4 Kernel Partial Least Squares Regression

Given two data blocks X and Y, consider kernel methods for partial least squares (PLS) regression. This type of methods is known as the kernel partial least squares regression.

Kernel PLS regression is a natural extension of PLS regression discussed in Sect. 6.​9.​2.

The key steps of PLS regression are given by

1. 1.

   w = X ^Tu∕(u ^Tu).

    
2. 2.

   t = Xw.

    
3. 3.

   c = Y ^Tt∕(t ^Tt).

    
4. 4.

   u = Y ^Tc∕(c ^Tc).

    
5. 5.

   p = X ^Tt∕(t ^Tt).

    
6. 6.

   q = Y ^Tu∕(u ^Tu).

    
7. 7.

   X = X −tp ^T.

    
8. 8.

   Y = Y −tc ^T.

    

Then, we have

(8.2.36)

(8.2.37)

(8.2.38)

(8.2.39)

(8.2.40)

Using Φ =  Φ(X) instead of X, then Eqs. (8.2.36) and (8.2.39) become

(8.2.41)

Therefore, the key steps of kernel nonlinear iterative partial least squares (NIPALS) regression are as follows [28, 32]:

Given Φ ₀ =  Φ and the data block Y ₀ = Y.

1. 1.

   Randomly initialize u.

    
2. 2.

   t =  Φ Φ ^Tu, t ←t∕(t ^Tt).

    
3. 3.

   c = Y ^Tt.

    
4. 4.

   u = Y ^Tu, u ←u∕(u ^Tu).

    
5. 5.

   Repeat Steps 2–4 until convergence of t.

    
6. 6.

   Deflate the matrix: Φ Φ ^T = (I −tt ^T) Φ Φ ^T(I −tt ^T)^T.

    
7. 7.

   Deflate the matrix: Y = Y −tc ^T.

    

The kernel NIPALS regression is an iterative process: after extraction of the first component t ₁ the algorithm starts again using the deflated matrices Φ Φ ^T and Y computed in Step 6 and Step 7, and repeat Steps 2–7 until the deflated matrix Φ Φ ^T or Y becomes a null matrix.

Once two matrices T = [t ₁, …, t _p] and U = [u ₁, …, u _p] are found by using the NIPALS regression algorithm, then the matrix regression coefficients B can be computed in the form similar to (6.​9.​26):

(8.2.42)

Then for a given new data block X _new and Φ _new =  Φ(X _new), then unknown -values can be predicted as

(8.2.43)

MATLIB code for Kernel RLS algorithm can be found in [28, Appendix III].

8.2.5 Laplacian Support Vector Machines

Consider support vector machines for graph signals. Given a set of l labeled graph examples and a set of u unlabeled graph examples . Let f be a semi-supervised SVM for graph training samples. The graph or Laplacian support vector machines are extended by solving the following optimization problem [2]:

(8.2.44)

By the extended representer theorem (Theorem 8.5), the solution to the problem (8.2.44) is given by

(8.2.45)

Substituting (8.2.45) into (8.2.44) and adding an unregularized bias term b in f ^∗, then the primal problem for optimizing α can be written as

(8.2.46)

(8.2.47)

(8.2.48)

By using the augmented Lagrange multiplier method, the Lagrange function for dual unconstrained optimization is then given by

(8.2.49)

From the first-order optimization conditions

By using above identities, the Lagrange function in (8.2.49) can be reduced to

(8.2.50)

where J = [1, …, 1, 0, …, 0] is an 1 × (l + u) matrix with the first l entries as 1 and the rest as 0, and .

From the first-order optimization condition

(8.2.51)

it follows that

(8.2.52)

8.3 Support Vector Machine Regression

The support vector machine regression is a binary regressor algorithm that looks for an optimal hyperplane as a decision function in a high-dimensional space.

8.3.1 Support Vector Machine Regressor

Suppose we are given a training set of N data points , where is the kth input pattern and is the kth associated “truth”.

Let be a mapping from the input space to the feature space F. Here, ϕ(x _i) is the extracted feature of the input x _i.

The SVM learning algorithm aims at finding a hyperplane (w, b) through the constrained optimization

(8.3.1)

(8.3.2)

where the quality (〈w, ϕ(x)〉− b) corresponds to the distance between the point x _i and the decision boundary, and the quality

(8.3.3)

is called the margin.

The constrained optimization problem (8.3.1) can be rewritten as an unconstrained optimization in Lagrangian form:

(8.3.4)

where the Lagrangian multiplies are nonnegative.

From the optimization conditions, we have

(8.3.5)

(8.3.6)

Substituting these two results into (8.3.1) to give the following constrained optimization with respect to α:

(8.3.7)

or

(8.3.8)

subject to

(8.3.9)

where .

The support vector machine regression aims at designing the following machine learning algorithms:

• solve the maximization problem (8.3.8) and (8.3.9) for the Lagrangian multiplies α _i, i = 1, …, N;

• update the bias via ;

• use (8.3.5) to calculate the support vector regressor w.

8.3.2 𝜖-Support Vector Regression

The basic idea of 𝜖-support vector (SV) regression is to find a function f(x) = w ^Tϕ(x) + b that has at most 𝜖 deviation from the actually obtained targets for all the training data , namely for i = 1, …, N, and at the same time w is as flat as possible. In other words, we do not count errors as long as they are less than 𝜖, but will not accept any deviation larger than this [36].

One way to ensure the flatness of w is to minimize its norm . Hence, the basic form of 𝜖-support vector regression can be written as a convex optimization problem [36, 43]:

(8.3.10)

(8.3.11)

where 𝜖 > 0 is a regression error.

In order to avoid a violation of constrained conditions in (8.3.11), one can introduce slackness parameters , for given parameters C > 0 and 𝜖 > 0. Hence we have the standard form of support vector regression given by Vapnik [44]

(8.3.12)

(8.3.13)

(8.3.14)

(8.3.15)

Here C > 0 is the regularization parameter that denotes SVM misclassification tolerance and is a pre-specified value. ξ _k represents the upper training error, and is the lower training error subject to 𝜖-insensitive tube .

To solve the above constrained optimization problem, one can define the Lagrange function (or Lagrangian) as follows [36]:

(8.3.16)

where are Lagrange multipliers which have to satisfy the positivity constraints:

(8.3.17)

where and .

From the first-order optimality conditions it follows that

(8.3.18)

(8.3.19)

(8.3.20)

(8.3.21)

Equation (8.3.18) is the so-called support vector expansion, i.e., w can be completely described as a linear combination of the training patterns x _i.

Substituting (8.3.18) and (8.3.19) into (8.3.16) can eliminate the dual variables and gives the dual function

(8.3.22)

On the other side, from (8.3.17), (8.3.20), and (8.3.21) it is known that

(8.3.23)

Equations (8.3.22) together with constraints (8.3.19) and (8.3.23) constitute the Wolfe dual 𝜖-support vector machine regression problem:

(8.3.24)

(8.3.25)

(8.3.26)

where is an N × N positive semi-definite matrix with being the kernel function of SVM.

Then the regression function is given by

(8.3.27)

where w is described by the support vector expansion Eq. (8.3.18).

The KKT conditions for the dual constrained optimization problem (8.3.24) are given by [36]

(8.3.28)

(8.3.29)

(8.3.30)

(8.3.31)

From the above conditions it follows that

(8.3.32)

(8.3.33)

(8.3.34)

(8.3.35)

Then the computation of b is given by Smola and Schölkopf [36]:

(8.3.36)

If some α _i or , then the inequalities become equalities.

8.3.3 ν-Support Vector Machine Regression

In the standard support vector machine regression described above, an error of 𝜖 is allowed at each point x _i. By introducing a constant ν ≥ 0, the size of 𝜖 can be traded off against model complexity and slack variables. This is the basic idea of the following ν-support vector machine regression developed by Schölkopf et al. [34]:

(8.3.37)

(8.3.38)

(8.3.39)

(8.3.40)

By introducing the Lagrange multipliers , one has the Lagrange function [34]:

(8.3.41)

The first-order optimality conditions give the results

(8.3.42)

(8.3.43)

(8.3.44)

(8.3.45)

for minimizing over the primal variables , while maximizing over the dual variables yields

and

Hence, the regression result is given by

(8.3.46)

Substituting the four constraints in (8.3.42)–(8.3.45) into the Lagrange function defined in (8.3.41) leads to the optimization problem called the Wolfe dual. The Wolfe dual ν-support vector machine regression problem can be written as [34]

(8.3.47)

(8.3.48)

After solving the Wolfe dual problem, the regression value of the new instance x is given by

(8.3.49)

Proposition 8.1 ([34])

Suppose ν-SVR is applied to some data set, and the resulting 𝜖 is nonzero. The following statements hold:

• ν is an upper bound on the fraction of errors.

• ν is a lower bound on the fraction of SVs.

The following function is a popular choice to illustrate SVR for regression in the literature:

(8.3.50)

8.4 Support Vector Machine Binary Classification

A basic task in data analysis and pattern recognition is classification that requires the construction of a classifier, namely a function that assigns a class label to instances described by a set of attributes.

In this section we discuss SVM binary classification problems with two classes.

8.4.1 Support Vector Machine Binary Classifier

Given a training set of N data points , where x _k is the kth input pattern and is the kth output pattern. Denote the set of data

(8.4.1)

A SVM classifier is a classifier which finds the hyperplane that separates the data with the largest distance between the hyperplane and the closest data point (called margin).

A linear separating hyperplane is a decision function in the form

(8.4.2)

where x is the input pattern, w is the weight vector, and b is a bias term. Hence, we have

(8.4.3)

Similarly, for a nonlinear classifier w with the nonlinear mapping ϕ : x →ϕ(x), its testing output y = f(x) = w ^Tϕ(x) + b, where b denotes a bias term. Then, we have

(8.4.4)

Therefore the decision function of a nonlinear classifier is given by

(8.4.5)

For a SVM with the kernel function , the SVM classifier w is usually designed as

(8.4.6)

Substituting (8.4.6) into (8.4.5), we directly get the decision function of any SVM classifier as follows:

(8.4.7)

Hence, when designing any SVM classifier, its weighting vector w must have the form in (8.4.6).

The set of vectors {x ₁, …, x _N} is said to be optimally separated by the hyperplane if it is separated without error and the distance between the closest vector to the hyperplane is maximal.

For designing the classifier w, we assume that

(8.4.8)

(8.4.9)

That is to say, if the data is to be classified correctly, this hyperplane should ensure that

(8.4.10)

assuming that y ∈{−1, +1}. Here ϕ(x _k) is a nonlinear vector function mapping the input space into a higher-dimensional space, but this function is not explicitly constructed.

The distance of a point x _k from the hyperplane, denoted as d(w, b;x _k), is defined as

(8.4.11)

By the constraint condition in (8.4.10), the margin of a classifier is given by

(8.4.12)

The optimal hyperplane w _opt is given by maximizing the above margin, namely

(8.4.13)

which is equivalent to

(8.4.14)

In order to avoid the possibility to violate (8.4.10), variables ξ _k need to be introduced such that

(8.4.15)

(8.4.16)

According to the structural risk minimization principle, the risk bound is minimized by formulating the optimization problem

(8.4.17)

subject to (8.4.15), where C is a user-specified parameter for providing a trade-off between the distance of the separating margin and the training error.

Therefore the primary problem for SVM binary classifier is a constrained optimization problem:

(8.4.18)

(8.4.19)

The dual form of the above primary optimization problem is given by

(8.4.20)

(8.4.21)

where is the Lagrange multiplier corresponding to ith training sample , and vectors satisfying are termed support vectors.

In SVM learning algorithms, kernel functions K(u, v) = 〈ϕ(u), ϕ(v)〉 are usually used, and the dual optimization problem for SVM binary classifier is represented as

(8.4.22)

(8.4.23)

By Bousquet et al. [5, pp. 14–15], several important practical points should be taken into account when designing classifiers.

1. 1.

   In order to reduce the likelihood of overfitting the classifier to the training data, the ratio of the number of training examples to the number of features should be at least 10:1. For the same reason the ratio of the number of training examples to the number of unknown parameters should be at least 10:1.

    
2. 2.

   Importantly, proper error-estimation methods should be used, especially when selecting parameters for the classifier.

    
3. 3.

   Some algorithms require the input features to be scaled to similar ranges, such as some kind of a weighted average of the inputs.

    
4. 4.

   There is no single best classification algorithm!

    

8.4.2 ν-Support Vector Machine Binary Classifier

Similar to ν-SVR, by introducing a new parameter ν ∈ (0, 1] in SVM classification, Schölkopf et al. [34] presented ν-support vector classifier (ν-SVC).

The primal optimization problem of ν-SVC is described by

(8.4.24)

(8.4.25)

Let Lagrange multipliers , and consider the Lagrange function

(8.4.26)

This function needs to be minimized with respect to the primal variables w, ξ, b, ρ and maximized over the dual variables α, β, δ.

The first-order optimization conditions for minimization give the following results:

(8.4.27)

(8.4.28)

(8.4.29)

(8.4.30)

If substituting (8.4.27)–(8.4.30) into the Lagrange function , using and incorporating the kernel function K(x, x _i) instead of in dot product, then one obtains the Wolfe dual optimization problem for ν-SVC as follows:

(8.4.31)

(8.4.32)

To compute parameters b and ρ in the primal ν-SVC optimization problem, consider two sets S ₊ and S ₋, containing support vectors x _i with and .

Let

(8.4.33)

(8.4.34)

be the sizes of the sets S ₊ and S ₋, respectively.

If defining

(8.4.35)

(8.4.36)

then one has [7, 34]

(8.4.37)

8.4.3 Least Squares SVM Binary Classifier

Standard SVMs are powerful tools for data classification by assigning them to one of two disjoint halfspaces in either the original input space for linear classifiers, or in a higher-dimensional feature space for nonlinear classifiers. The least squares SVM (LS-SVMs) developed in [37] and the proximal SVMs (PSVMs) presented in [14, 15] are two much simpler classifiers, in which each class of points is assigned to the closest of two parallel planes (in input or feature space) such that they are pushed apart as far as possible.

The LS-SVMs formulate the binary classification problem as

(8.4.38)

(8.4.39)

for the binary classification .

Define the Lagrange function (Lagrangian)

(8.4.40)

where α _k are Lagrange multipliers. Different from Lagrange multipliers in SVM with inequality constraints, in LS-SVM, Lagrange multipliers α _k can be either positive or negative due to the equality constraints used.

Based on the KKT conditions, one has the optimality conditions of (8.4.40) as follows [11]:

(8.4.41)

(8.4.42)

(8.4.43)

(8.4.44)

where , 1 = [1, …, 1]^T , e = [e ₁, …, e _N]^T and α = [α ₁, …, α _N]^T.

The KKT equations (8.4.41)–(8.4.44) can be written as the following matrix  equation form [11]:

(8.4.45)

By eliminating w and e, the above KKT equations are simplified as

(8.4.46)

Mercer’s condition can be applied again to the matrix Z ^TZ to get [37]

(8.4.47)

Given a training set , constant C > 0, and the kernel function K(x _i, x _j), the LS-SVM binary classification algorithm performs the following learning step:

• Construct the N × N matrix .

• Solve the KKT matrix equation (8.4.46) for and b.

In testing step, for given testing sample , its decision is given by

(8.4.48)

8.4.4 Proximal Support Vector Machine Binary Classifier

Due to the simplicity of their implementations, least square SVM (LS-SVM) and proximal support vector machine (PSVM) have been widely used in binary classification applications.

In the standard SVM binary classifier a plane midway between two parallel bounding planes is used to bound two disjoint halfspaces each of which contains points mostly of class 1 or 2. Similar to the LS-SVM, the key idea of PSVM [14] is that the separation hyperplanes are “proximal” planes rather than bounded planes anymore. Proximal planes classify data points depending on proximity to either one of the two separation planes. We aim to push away proximal planes as far apart as possible. Different from LS-SVM, PSVM uses instead of as the objective function, making the optimization problem strongly convex and has little or no effect on the original optimization problem [22].

The primal optimization problem of linear PSVM is described by

(8.4.49)

(8.4.50)

By Fung and Mangasarian [15], the PSVM formulation (8.4.49) can be also interpreted as a regularized least squares solution [38] of the system of linear equations , that is, finding an approximate solution (w, b) to with least 2-norm .

The corresponding dual unconstrained optimization problem is given by

(8.4.51)

Using the first-order optimality conditions , and , and eliminating w and , one gets the KKT equation of linear PSVM classifier in matrix form:

(8.4.52)

and

(8.4.53)

Here

(8.4.54)

(8.4.55)

(8.4.56)

Similar to LS-SVM, the training data x can be mapped from the input space into the feature space ϕ : x →ϕ(x). Hence, the nonlinear PSVM classifier has still the KKT equation (8.4.52) with in Eq. (8.4.54).

Algorithm 8.1 shows the PSVM binary classification algorithm.

Algorithm 8.1 PSVM binary classification algorithm

The decision functions of binary SVM, LS-SVM, and PSVM classifiers have the same form

(8.4.57)

where y _i is the corresponding target class label of the training data x _i, α _i is the Lagrange multiplier to be computed by the learning machines, and K(x, x _i) is a suitable kernel function to be given by users.

The followings are the comparisons of SVM, LS-SVM, and PSVM.

• SVM, LS-SVM, and PSVM are originally proposed for binary classification.

• LS-SVM and PSVM provide fast implementations of the traditional SVM. Both LS-SVM and PSVM use equality optimization constraints instead of inequalities from the traditional SVM, which results in a direct least square solution by avoiding quadratic programming.

It should be noted [22] that the Lagrange multipliers are proportional to the training errors in LS-SVM, while in the conventional SVM, many Lagrange multipliers are typically equal to zero. As compared to the conventional SVM, sparsity is lost in LS-SVM; this is true to PSVM as well.

8.4.5 SVM-Recursive Feature Elimination

Decision functions that are simple weighted sums of the training patterns plus a bias are called linear discriminant functions [9]:

(8.4.58)

where w is the weight vector and b is a bias value.

Construct the optimal hyperplane (w, b) such that

(8.4.59)

which separates a set of training data (x ₁, y ₁), …, (x _n, y _n). Vectors x _i such that y _i(w ^Tx _i + b) = 1 is termed support vectors. Hence, the constrained optimization problem for finding the optimal weight vector w can be described as

(8.4.60)

(8.4.61)

where the inequality constraint is for ensuring x to be support vectors.

The above constrained optimization can be rewritten as the unconstrained optimization in Lagrangian form:

(8.4.62)

where α = [α ₁, …, α _n]^T is the vector of nonnegative Lagrangian multiplies α _i ≥ 0, i = 1, …, n.

The optimization conditions with respect to w and b are given by

(8.4.63)

(8.4.64)

Substituting the above two equations into (8.4.62) to yield [8]

(8.4.65)

In conclusion, when used for classification, SVMs separate a given set of binary labeled training data (x _i, y _i) with hyperplane (w, b) that is maximally distant from them. Such a hyperplane is known as “the maximal margin hyperplane.”

In nonlinear binary classification cases, Eq. (8.4.65) becomes

(8.4.66)

The goal of the SVM-recursive feature elimination (SVM-RFE) algorithm, proposed by Guyon et al. [20], is to find a subset of size r among d variables (r < d) which maximizes the performance of the predictor, based on a backward sequential selection. Starting all the features, one feature is removed at a time. The removed ith feature is the one whose removal minimizes the variation of [31]:

(8.4.67)

where is the (j, k)th entry of the Gram matrix K ⁽ⁱ⁾of the training data when variable i is removed, and is the corresponding solution of (8.4.66). For the sake of simplicity, is usually taken even if a variable has been removed in order to reduce the computational complexity of the SVM-RFE algorithm.

Algorithm 8.2 shows the SVM-RFE algorithm that is an application of RFE using the weight magnitude as ranking criterion.

Algorithm 8.2 SVM-recursive feature elimination (SVM-RFE) algorithm [20]

8.5 Support Vector Machine Multiclass Classification

A multiclass classifier is a function that maps an instance into an element y of .

8.5.1 Decomposition Methods for Multiclass Classification

A popular way to solve a k-class problem is to decompose it to a set of L binary classification problems. One-versus-one, one-versus-rest, and directed acyclic graph SVM methods are three of the most common decomposition approaches [21, 41, 48].

One-Against-All Method

The standard method for k-class SVM classification is to construct L = k binary classifiers . The ith SVM will be trained with all of the examples in the ith class with positive labels, and all other examples with negative labels. Then, the weight vector w _m for the mth model can be generated by any linear classifier. Such an SVM classification method is referred to as one-against-all (OAA) or one-versus-rest (OVR) method [4, 27].

Let be a set of N training examples, and each example be drawn from a domain and is the class of .

The mth one-against-all classifier solves the following constrained optimization problem:

(8.5.1)

(8.5.2)

where is the weight vector of the mth classifier, C is the penalty parameter, and is the training error corresponding to the mth class and the ith training data that is mapped to a higher-dimensional space by the function .

Minimizing means maximizing the margin between two groups of data. When data are not linear separable, there is a penalty term which can reduce the training errors in the mth classifier. The basic concept behind one-against-all SVM is to search for a balance between the regularization term and the training error for the m classifiers.

By “decision function” it means a function f(x) whose sign represents the class assigned to data point x.

The solution of (8.5.1) gives k decision functions . Hence, a new testing instance x is said to be in the class which has the largest value among k decision functions:

(8.5.3)

One-Against-One Method

The one-against-one (OAO) method [13, 25] is also known as one-versus-one (OVO) method. This method constructs L = k(k − 1)∕2 binary classifiers by solving k(k − 1)∕2 binary classification problems [25]. Each binary classifier constructs a model with data from one class as positive and another class as negative. Since there is k(k − 1)∕2 combinations of two classes, one needs to construct k(k − 1)∕2 weight vectors: w _1,2, …, w _1,k;w _2,3, …, w _2,k;…;w _k−1,k.

For training data from the ith and the jth classes, one solves the following binary classification problem:

(8.5.4)

(8.5.5)

(8.5.6)

(8.5.7)

where w ^ij is the binary classifier for the ith and the jth classes, b ^ij is a real parameter, and ξ _ij is the training error corresponding to the ith and the jth classes.

After all k(k − 1)∕2 binary classifiers are constructed by solving the above binary problems for i, j = 1, …, k, the following voting strategy suggested in [25] can be used: if the decision function sign((w ^ij)^Tϕ(x) + b ^ij) determines that x is in ith class, then vote for the ith class is added by one. Otherwise, the vote for jth is added by one. Finally, x is predicted to be in the class with the largest vote. This voting approach is also called the “Max Wins” strategy. In case that two classes have identical votes, thought it may not be a good strategy, we simply select the one with the smaller index [21].

DAGSVM Method

Directed acyclic graph SVM method [27] is simply called DAGSVM method whose training phase is the same as the one-against-one method by solving binary SVMs. However, in the testing phase, it uses a rooted binary directed acyclic graph which has internal nodes and leaves.

The training phase of the DAGSVM method is the same as the one-against-one method by solving k(k − 1)∕2 binary SVM classification problems, but uses one different voting strategy, called a rooted binary directed acyclic graph which has k(k − 1)∕2 internal nodes and k leaves, in the testing phase. Each node is a binary SVM classifier of ith and jth classes.

A directed acyclic graph (DAG) is a graph whose edges have an orientation and no cycles.

Definition 8.7 (Decision Directed Acyclic Graph [27])

Given a space X and a set of Boolean functions , the decision directed acyclic graphs (DDAGs) on k classes over are functions which can be implemented using a rooted binary DAG with k leaves labeled by the classes where each of the L = k(k − 1)∕2 internal nodes is labeled with an element of . The nodes are arranged in a triangle with the single root node at the top, two nodes in the second layer, and so on until the final layer of k leaves. The ith node in layer j < k is connected to the ith and (i + 1)th node in the (j + 1)st layer.

For k-class classification, a rooted binary directed acyclic graph has k layers: the top layer has a single root node, the second layer has two nodes, and so on until the kth (i.e., final) layer has k nodes, so a rooted binary DAG has k leaves and 1 + 2 + ⋯ + k = k(k − 1)∕2 internal nodes. Each node is a binary SVM of ith and jth classes.

The DDAG is equivalent to operating on a list, where each node eliminates one class from the list. The list is initialized with a list of all classes. A test point is evaluated against the decision node that corresponds to the first and last elements of the list. If the node prefers one of the two classes, the other class is eliminated from the list, and the DDAG proceeds to test the first and last elements of the new list. The DDAG terminates when only one class remains in the list. Thus, for a problem with k classes, k − 1 decision nodes will be evaluated in order to derive an answer.

Example 8.1

Given N test samples with and 3, 4}. The DDAG is equivalent to operating on a list {1, 2, 3, 4}, where each node eliminates one class from the list. The list is starting at the root node 1 versus 4 at the top layer, the binary decision function is evaluated. If the output value is not Class 1, then it is eliminated from the list to get a new list {2, 3, 4} and thus we make the binary decision of two classes 2 versus 4. If the root node prefers Class 1, then Class 4 at the root node is removed from the list to yield a new list {1, 2, 3} and the binary decision is made for two classes 1 versus 3. Then, the second layer has two nodes (2 vs 4) and (1 vs 3). Therefore, we go through a path until DDAG terminates when only one class remains in the list.

Figure 8.2 shows the decision directed acyclic graphs (DDAG) of the above four classes [27].

Fig. 8.2

The decision directed acyclic graphs (DDAG) for finding the best class out of four classes

DDAGs naturally generalize the class of Decision Trees, allowing for a more efficient representation of redundancies and repetitions that can occur in different branches of the tree, by allowing the merging of different decision paths [27].

8.5.2 Least Squares SVM Multiclass Classifier

The previous subsection discussed the support vector machine binary classifier. In this subsection we discuss multi-class classification cases.

For the multiclass case with k labels, LS-SVM uses k output nodes in order to encode multiclasses, where y _i,j denotes the output value of the jth output node for the training data x _i [41]. The k outputs can be used to encode up to 2^k different classes. For multiclass case, the primal optimization problem of LS-SVM can be represented as [41]

(8.5.8)

for i = 1, …, N.

The Lagrange function in dual LS-SVM multiclass classifier is given by

(8.5.9)

(8.5.10)

Similar to the LS-SVM solution to the binary classification, the conditions for optimality are given by

(8.5.11)

(8.5.12)

(8.5.13)

(8.5.14)

In the above equations:

(8.5.15)

(8.5.16)

(8.5.17)

(8.5.18)

(8.5.19)

Due to each classifier being binary, for given , one has

(8.5.20)

Equations (8.5.15)–(8.5.19) can be rewritten as the KKT equation in matrix form:

(8.5.21)

where with the (i, j)th entries

(8.5.22)

where (if i = j) or 0 (otherwise); and is the kernel function of the mth SVM for multiclass classification.

Algorithm 8.3 shows the LS-SVM multiclass classification algorithm.

Algorithm 8.3 LS-SVM multiclass classification algorithm [41]

8.5.3 Proximal Support Vector Machine Multiclass Classifier

The primal constrained optimization problem of PSVM multiclass classifier is described by

(8.5.23)

(8.5.24)

The corresponding dual unconstrained optimization problem is given by

(8.5.25)

From the optimality conditions we have

(8.5.26)

(8.5.27)

(8.5.28)

(8.5.29)

for m = 1, …, k.

Eliminating and in the above equations yields the KKT equations

(8.5.30)

and

(8.5.31)

where

(8.5.32)

(8.5.33)

(8.5.34)

Algorithm 8.4 shows the PSVM multiclass classification algorithm.

Algorithm 8.4 PSVM multiclass classification algorithm

8.6 Gaussian Process for Regression and Classification

In Chap. 6 we discussed traditionally parametric models based machine learning. The parametric models have a possible advantage in ease of interpretability, but for complex data sets, simple parametric models may lack expressive power, and their more complex counterparts (such as feedforward neural networks) may not be easy to work with in practice [29, 30]. The advent of kernel machines, such as Gaussian processes, sparse Bayesian learning, and relevance vector machine, has opened the possibility of flexible models which are practical to work with.

In this section we deal with Gaussian process methods for regression and classification problems.

8.6.1 Joint, Marginal, and Conditional Probabilities

Let the n (discrete or continuous) random variables y ₁, …, y _n have a joint probability p(y ₁, …, y _n), or p(y) for short. Technically, one ought to distinguish between probabilities (for discrete variables) and probability densities for continuous variables. Throughout the book we commonly use the term “probability” to refer to both. Let us partition the variables in y into two groups, and , where A ∪ B = {1, …, n} and A ∩ B = ∅, so that . Each group may contain one or more variables. The marginal probability of , denoted by , is given by marginal probability

(8.6.1)

The integral is replaced by a sum if the variables are discrete valued. Notice that if the set A contains more than one variable, then the marginal probability is itself a joint probability of these variables. If the joint distribution is equal to the product of the marginals, then the variables are said to be independent, otherwise they are dependent.

The conditional probability function is defined as conditional probability

(8.6.2)

defined for , as it is not meaningful to condition on an impossible event. If and are independent, then the marginal and the conditional are equal.

Using the definitions of both and we obtain Bayes theorem

(8.6.3)

8.6.2 Gaussian Process

A random variable x with the normal distribution is called the univariate Gaussian distribution, and is denoted as x ∼ N(μ, σ ²), where μ = E{x} and σ ² = var(x) are its mean and variance, respectively.

A multivariate Gaussian (or normal) distribution has a joint probability density given by

(8.6.4)

where with μ _i = E{x _i} is the mean vector (of length N) of x and Σ is the N × N (symmetric, positive definite) covariance matrix of x. The multivariate Gaussian distribution is denoted simply as x ∼ N(μ, Σ).

If letting x and y be jointly Gaussian random vectors

(8.6.5)

then the marginal distribution of x and the conditional distribution of x given marginalizing y are

(8.6.6)

or

(8.6.7)

A Gaussian process is a natural generalization of multivariate Gaussian distribution.

Definition 8.8 (Gaussian Process [29, 30])

A Gaussian Process f(x) is a collection of random variables x, any finite number of which have (consistent) joint Gaussian distributions.

Clearly, the Gaussian distribution is over vectors, whereas the Gaussian process is over functions f(x), where x is a Gaussian vector.

A scalar Gaussian process f(x) can be represented as

(8.6.8)

where μ = E{x} is the mean of x and K(x, x′) is the covariance function of x. Equation (8.6.8) means [29]: “the function f is distributed as a GP with mean function μ and covariance function K.”

A vector-valued Gaussian process f(x) is completely specified by its mean function and covariance function

(8.6.9)

(8.6.10)

and the Gaussian process is expressed as

(8.6.11)

where the (i, j)th elements of the covariance matrix Σ are defined as Σ_ij = K(x _i, x _j).

The covariance function K(x _i, x _j) (also known as kernel, kernel function, or covariance kernel) is the driving factor in Gaussian processes for regression and/or classification. Actually, the kernel represents the particular structure present in the data being modeled. One of the main difficulties in applying Gaussian processes is to construct such a kernel.

According to Mercer’s theorem (Theorem 8.3), the nonlinear kernel function is usually constructed by

(8.6.12)

8.6.3 Gaussian Process Regression

Let {(x _n, f _n)| n = 1, …, N} be the training samples, where f _n, n = 1, …, N are the noise-free training outputs of x _n, typically continuous functions for regression or discrete function for classification.

Denote the noise-free training output vector and the test output vector given the test samples . Under the assumption of Gaussian distributions f ∼ N(0, K(X, X)) and f _∗ ∼ N(0, K(X _∗, X _∗)), the joint distribution of f and f _∗ is given by

(8.6.13)

where and are the N × N training sample matrix and the N _∗× N _∗ test sample matrix, respectively; and , , , and are the covariance function matrices, respectively.

From Eq. (8.6.6) it is known that the conditional distribution of f _∗ given f can be expressed as

(8.6.14)

This is just the posterior distribution for a specific set of test cases.

The goal of Gaussian processes regression is to find f _∗ via maximizing the posterior probability f _∗|f. However, f is unobservable. In practical applications, the noisy training output vector y = f + e is observed in the additive Gaussian white noise . In this case, y ∼ N(0, cov(y)) with

(8.6.15)

Then, the joint distribution of y and f _∗ according to the prior is given by

(8.6.16)

From Eq. (8.6.6) we get the conditional distribution of f _∗ given y below:

(8.6.17)

where

(8.6.18)

(8.6.19)

Here, is the mean vector over N _∗ test points, i.e., .

If there is only one test point x _∗, i.e., X _∗ = x _∗, then K(X, X _∗) reduce to k _∗ = k(x _∗) = k(x, x _∗) which denotes the vector of covariances between the test point x _∗ and the n training points in X. In this case, Eqs. (8.6.18) and (8.6.19) reduce to

(8.6.20)

(8.6.21)

Letting , then the mean vector centered on a test point x _∗, denoted by , is given by

(8.6.22)

When using Eqs. (8.6.20) and (8.6.21) to compute directly and var(f _∗), it needs to invert the matrix . A faster and numerically more stable computation method is to use Cholesky decomposition.

Let the Cholesky decomposition of be given by , where L is a lower triangular matrix. Then, becomes α = (L ^T)⁻¹L ⁻¹y. Denoting z = L ⁻¹y and α = (L ^T)⁻¹z, then

(8.6.23)

(8.6.24)

The above two equations suggest an efficient algorithm for finding α given K and y as follows:

1. 1.

   Make Cholesky decomposition: .

    
2. 2.

   Solve the triangular system Lz = y for z by forward substitution.

    
3. 3.

   Solve the triangular system L ^Tα = z for α by back substitution.

    

Similarly, we have , where v = L ⁻¹k _∗⇔Lv = k _∗. This implies v is the solution for the triangular system Lv = k _∗.

Once α and v are found, one can use Eqs. (8.6.20) and (8.6.21) to get and var(f _∗) = k(x _∗, x _∗) −v ^Tv, respectively.

The marginal likelihood is the integral marginal of the likelihood times the prior

(8.6.25)

By the term “marginal likelihood,” it refers to the marginalization over the function values f. Under the Gaussian process model, the prior is Gaussian, f|X ∼ N(0, K(X, X), or

(8.6.26)

Because of y = f + e with , the marginal likelihood

(8.6.27)

Here, the first term is a data fitting term as it is the only one involving the observed targets y. The second term is the model complexity depending only on the covariance function and the inputs. The last term is just a normalization constant.

Algorithm 8.5 shows the Gaussian process regression (GPR) in [30].

Algorithm 8.5 Gaussian process regression algorithm [30]

8.6.4 Gaussian Process Classification

Both regression and classification can be viewed as function approximation problems, but their solutions are rather different. This is because the targets in regression are continuous functions in which the likelihood function is Gaussian; a Gaussian process prior combined with a Gaussian likelihood gives rise to a posterior Gaussian process over functions, and everything remains analytically tractable [30]. But, in classification models, the targets are discrete class labels, so the Gaussian likelihood is no longer appropriate. Hence, approximate inference is only available for classification, where exact inference is not feasible.

Inference is naturally divided into two steps [30]:

1. 1.
   Computing the distribution of the latent variable corresponding to a test case:

   

   (8.6.28)

   where p(f|X, y) = p(y|f)p(f|X)∕p(y|X) is the posterior over the latent variables.

    
2. 2.
   Using this distribution over the latent f _∗ to produce a probabilistic prediction

   

   (8.6.29)
    

In classification due to discrete class labels the posterior p(f|X, y) in (8.6.28) is non-Gaussian, which makes the likelihood in (8.6.28) is non-Gaussian, which makes its integral analytically intractable. Similarly, Eq. (8.6.29) can be intractable analytically for certain sigmoid functions.

The non-Gaussian joint posterior p(f|X, y) can be approximated analytically with a Gaussian one. To this end, consider Laplace’s method that utilizes a Gaussian approximation

(8.6.30)

to the non-Gaussian posterior p(f|X, y) in the integral (8.6.28). In the above equation, , and is the Hessian matrix of the negative log posterior at that point.

By Bayes’ rule the posterior over the latent variables is given by p(f|X, y) = p(y|f)p(f|X)∕p(y|X), but as p(y|X) is independent of f, we need to consider only the unnormalized posterior when maximizing with respect to f, namely consider only p(f|X, y) = p(y|f)p(f|X). Taking its logarithm and using Eq. (8.6.26), then

(8.6.31)

whose first and second derivatives with respect to f are, respectively, given by

From ∇ Ψ(f) = 0 it follows that

(8.6.32)

The Hessian matrix can be written as

(8.6.33)

Here, W is a diagonal matrix, since the distribution for y _i depends only on f _i, not on f _{j ≠ i}.

Gaussian processes are a main mathematical tool for sparse Bayesian learning and hence the relevance vector machine that will be discussed in the next section.

8.7 Relevance Vector Machine

In real-world data, the presence of noise (in regression) and class overlap (in classification) implies that the principal modeling challenge is to avoid “overfitting” of the training set. In order to avoid the overfitting of SVMs (because of too many support vectors), Tipping [39] proposed a relevant vectors based learning machine, called the relevance vector machine (RVM). “Sparse Bayesian learning” is the basis for the RVM.

8.7.1 Sparse Bayesian Regression

We are given a set of data , where the “target” samples are conventionally considered to be realizations of a deterministic function y that is corrupted by some additive noise process . This function f is usually modeled by a linearly weighted sum of M fixed basis functions :

(8.7.1)

Our objective is to infer values of the parameters/weights such that is a “good” approximation of y(x).

The function approximation has two important benefits: accuracy and “sparsity.” By sparsity, it means that a sparse learning algorithm can set significant numbers of the parameters to zero.

The support vector machine (SVM) makes predictions based on the function:

(8.7.2)

where is a kernel function, effectively defining one basis function for each example in the training set.

There are two key features of the SVM:

• This can avoid overfitting, which leads to good generalization.

• This furthermore results in a sparse model dependent only on a subset of kernel functions.

However, there are a number of significant and practical disadvantages of the support vector learning methodology [39]:

1. 1.

   Although relatively sparse, SVMs make unnecessarily liberal use of basis functions since the number of support vectors required typically grows linearly with the size of the training set. In order to reduce computational complexity, some form of post-processing is often required.

    
2. 2.

   Predictions are not probabilistic. The SVM outputs a point estimate in regression, and a “hard” binary decision in classification. Ideally, it is desired to estimate the conditional distribution p(t|x) in order to capture uncertainty in prediction. Although posterior probability estimates can be coerced from SVMs via post-processing, these estimates are unreliable.

    
3. 3.

   Owing to satisfying Mercer’s condition, the kernel function K(x;x _i) must be the continuous symmetric kernel of a positive integral operator.

    

To avoid any of the above limitations, Tipping [39] proposed to use the “relevance vector machine” (RVM) instead of the SVM as a Bayesian learning of (8.7.2):

(8.7.3)

where the output is a linearly weighted sum of M generally nonlinear and fixed basis functions ϕ(x) = [ϕ ₁(x), …, ϕ _m(x)]^T. The regression process is to determine (or learn) the adjustable parameters (or “weights”) w = [w ₁, …, w _m]^T by using a Bayesian learning framework.

The key feature of this learning approach is that in order to offer good generalization performance, the inferred predictors are exceedingly sparse in that they contain relatively few nonzero w _i parameters. Since the majority of parameters are automatically set to zero during the learning process, this learning approach is known as the sparse Bayesian learning for regression [39].

The following are the framework of sparse Bayesian learning for regression.

Model Specification

Given a data set of input-target pairs , where . It is usually assumed that the target values are samples from the model with additive noise 𝜖 _n. Under this assumption, the standard linear regression model with additive Gaussian noise is given by

(8.7.4)

where y _n = y(x _n;w) are approximation signals of the target signal t _n, and 𝜖 _n are independent samples from some Gaussian noise N(0, σ ²) with mean-zero and variance σ ². If letting be the target vector and be the approximation vector, then under the assumption of independence of the target vector t and the Gaussian noise e = t −y, the likelihood of the complete data set can be written as

(8.7.5)

In different regression cases, the above likelihood has different forms.

• The linear neural network makes predictions based on the function

  

  (8.7.6)
  where is the weight vector, is the data matrix, and thus the likelihood (because of the independence assumption) is given by

  

  (8.7.7)
• The SVM makes predictions

  

  (8.7.8)

  where is the N × (N + 1) kernel matrix with , and . So under the independence assumption, the likelihood is given by

  

  (8.7.9)
• The RVM makes predictions

  

  (8.7.10)

  where is the N × (N + 1) “design” matrix with , and . For example, ϕ(x _n) = [1, . Therefore, the likelihood (because of the independence assumption) is given by

  

  (8.7.11)

Parameter Estimation

Inference in the Bayesian linear model is based on the posterior distribution over the weights, computed by Bayes’ rule [30]:

(8.7.12)

Hence, the posterior distribution over the weight vector w is given by Tipping [39]

(8.7.13)

where the posterior covariance and mean are, respectively, as follows [26]:

(8.7.14)

(8.7.15)

with A = Diag(α ₀, α ₁, …, α _N).

Sparse Bayesian “Learning”

The procedure which chooses a model with the maximum marginal likelihood is called the type II maximum likelihood procedure by Good [18]. By this procedure, sparse Bayesian learning is formulated as the (local) maximization with respect to α of the marginal likelihood, or equivalently, its logarithm marginal likelihood is given by Tipping [39]:

(8.7.16)

with

(8.7.17)

Here, by the term “marginal” it emphasizes a non-parametric model.

The Bayesian learning problem, in the context of the RVM, thus becomes the search for the hyperparameters α. In the RVM, these hyperparameters are estimated from minimizing . This estimation problem will be discussed in Sect. 8.7.3.

As a typical application of RVMs, consider the compressive sensing (CS) measurements g represented as [23]:

(8.7.18)

where is a K × N matrix, assuming random CS measurements are made.

A typical means of solving the CS problem is ℓ ₁ regularization:

(8.7.19)

Under the assumption that the additive noise n is mean-mean Gaussian distribution N(0, σ ²I), the Gaussian likelihood model is described as

(8.7.20)

Assuming the hyperparameters α and α ₀ are known, given the CS measurements g and the projection matrix Φ, the posterior for w can be expressed analytically as a multivariate Gaussian distribution with mean and covariance

(8.7.21)

Then, Bayesian compressive sensing problem becomes sparse Bayesian regression one.

8.7.2 Sparse Bayesian Classification

Sparse Bayesian classification follows an essentially identical framework for regression above, but using a Bernoulli likelihood and a sigmoidal link function to account for the change in the target quantities [39].

For an input vector x, an RVM classifier models the probability distribution of its class label using logistic sigmoid link function σ(y) = 1∕(1 + e ^−y) as

(8.7.22)

where f _RVM(x), called the RVM classifier function, is given by

(8.7.23)

where K(x, x _i) is a kernel function, and x _i, i = 1, …, N are the training samples.

By adopting the Bernoulli distribution for P(t|x), the likelihood can be written as

(8.7.24)

where the target t _n ∈{0, 1}.

In sparse Bayesian regression, the weights w can be integrated out analytically. Unlike the regression case, sparse Bayesian classification cannot be integrated out analytically, precluding closed form expressions for either the weight posterior p(w|t, α) or the marginal likelihood P(t|α). Thus, it utilizes the Laplace approximation procedure.

In the statistics and machine leaning literature, the Laplace approximation refers to the evaluation of the marginal likelihood or free energy using Laplace’s method. This is equivalent to a local Gaussian approximation of P(t|w) around a maximum a posteriori (MAP) estimate [40].

8.7.3 Fast Marginal Likelihood Maximization

Consider the dependence of on a single hyperparameter α _m, m ∈{1, …, M}, the matrix C in the Eq. (8.7.16) can be decomposed as

(8.7.25)

where C _−m = [C ∖c _m] is C with the mth column c _m removed. Thus, by applying the determinant identity and matrix inverse lemma, the terms of interest in can be written as

(8.7.26)

(8.7.27)

Then, can be rewritten as

(8.7.28)

where

(8.7.29)

The “sparsity factor” s _m can be seen to be a measure of the extent that basis vector ϕ _m “overlaps” those already present in the model, while the “quality factor” q _m is a measure of the alignment of ϕ _m with the error of the model with that vector excluded.

From (8.7.28) and the optimization condition we have the result

(8.7.30)

Hence, has a unique maximum with respect to α _m [10]:

(8.7.31)

for m = 1, …, M.

Equation (8.7.31) shows that:

• If ϕ _m is “in the model” (i.e., α _m < ∞) yet , then ϕ _m may be deleted (i.e., α _m set to ∞).

• If ϕ _m is excluded from the model (α _m = ∞) and , then ϕ _m may be added (i.e., α _m is set to some optimal finite value).

It is obvious that as compared with , it is easier to maintain and compute value of C ⁻¹. Let

(8.7.32)

By premultiplying , postmultiplying ϕ _m, and using (8.7.29), Eq. (8.7.27) yields

(8.7.33)

Similarly, we have

(8.7.34)

From (8.7.33) and (8.7.34) it follows that

(8.7.35)

for m = 1, …, M. Note that when α _m = ∞, s _m = S _m and q _m = Q _m.

By Duncan–Guttman inversion formula (1.​6.​5)

(8.7.36)

we have

(8.7.37)

where

(8.7.38)

Substituting (8.7.37) into (8.7.32) to yield

(8.7.39)

(8.7.40)

The following is the marginal likelihood maximization algorithm for sequential sparse Bayesian learning proposed by Tipping and Faul [40]:

1. 1.

   Initialize σ ² to some sensible value (e.g., var[t] × 0.1).

    
2. 2.
   Initialize with a single basis vector ϕ _i, setting, from (8.7.31):

   

   (8.7.41)

   All other α _m are notionally set to infinity.

    
3. 3.

   Explicitly compute Σ and μ (which are scalars initially), along with initial values of s _m and q _m for all M bases ϕ _m.

    
4. 4.

   Select a candidate basis vector ϕ _i from the set of all M.

    
5. 5.

   Compute .

    
6. 6.
   If θ _i > 0 and α _i < ∞ (i.e., ϕ _i is in the model), re-estimate α _i. Defining and Σ _j as the jth column of Σ:

   

   (8.7.42)

   

   (8.7.43)

   

   (8.7.44)

   

   (8.7.45)

   

   (8.7.46)
    
7. 7.
   If θ _i > 0 and α _i = ∞, add ϕ _i to the model with updated α _i:

   

   (8.7.47)

   

   (8.7.48)

   

   (8.7.49)

   

   (8.7.50)

   

   (8.7.51)

   where Σ _ii = (α _i + S _i)⁻¹, μ _i = Σ _iiQ _i, and e _i = ϕ _i − β Φ Σ Φ ^Tϕ _i.

    
8. 8.
   If θ _i ≤ 0 and α _i < ∞, then delete ϕ _i from the model and set α _i = ∞:

   

   (8.7.52)

   

   (8.7.53)

   

   (8.7.54)

   

   (8.7.55)

   

   (8.7.56)

   Following updates (8.7.53) and (8.7.54), the appropriate row and/or column j is removed from and .

    
9. 9.

   If it is a regression model and estimating the noise level, update .

    
10. 10.

    Recompute/update Σ, μ (using the Laplace approximation procedure in classification) and all s _m and q _m using Eqs. (8.7.35)–(8.7.40).

     
11. 11.

    If converged terminate, otherwise goto 4.

     

Brief Summary of This Chapter

• SVMs have high classification accuracy due to introducing maximum interval.

• When the sample size is small, SVMs can also classify accurately and have good generalization ability.

• The kernel function can be used to solve nonlinear problems.

• SVMs can solve the problem of classification and regression with high-dimensional features.

References

1. 1.
   Aronszajn, N.: Theory of reproducing kernels. Trans. Am. Math. Soc. 68, 337–404 (1950)MathSciNetzbMATH
2. 2.
   Belkin, M., Niyogi, P., Sindhwani, V.: Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res. 7, 2399–2434 (2006)MathSciNetzbMATH
3. 3.
   Boser, B.E., Guyon, I.M., Vapnik, V.N.: A training algorithm for optimal margin classifiers. In: Haussler D. (ed.) Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, pp. 144–152. ACM Press, Pittsburgh (1992)
4. 4.
   Bottou, L., Cortes, C., Denker, J., Drucker, H., Guyon, I., Jackel, L., LeCun, Y., Muller, U., Sackinger, E., Simard, P., Vapnik, V.: Comparison of classifier methods: a case study in handwriting digit recognition. In: Proceedings of International Conference on Pattern Recognition, pp. 77–87 (1994)
5. 5.
   Bousquet, O., von Luxburg, U., Rätsch, G. (eds.): Advanced Lectures on Machine Learning. Springer, Berlin (2004)
6. 6.
   Burges, C.J.C.: A tutorial on support vector machines for pattern recognition. Data Min. Knowl. Disc. 2, 121–167 (1998)
7. 7.
   Chang, C.-C., Lin, C.-J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(3), 27 (2011)
8. 8.
   Cortes, C., Vapnik, V.: Support vector networks. Mach. Learn. 20(3), 273–297 (1995)zbMATH
9. 9.
   Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification and Scene Analysis. Wiley, New York (1973)zbMATH
10. 10.
    Faul, A.C., Tipping, M.E.: Analysis of sparse Bayesian learning. In: Dietterich, T.G., Becker, S., Ghahramani, Z. (eds.) Advances in Neural Information Processing, vol. 14, pp. 383–389 (2002). http://​citeseer.​ist.​psu.​edu/​faul01analysis.​html
11. 11.
    Fletcher, R.: Practical Methods of Optimization. Wiley, Chichester (1987)zbMATH
12. 12.
    Fontana, R., Pistone, G., Rogantin, M.P.: Classification of two-level factorial fractions. J. Stat. Plann. Inference 87, 149–172 (2000)MathSciNetzbMATH
13. 13.
    Friedman, J.: Another approach to polychotomous classification. Department of Statistics, Stanford University, Stanford (1996). https://​www-stat.​stanford.​edu/​reports/​friedman/​poly.​ps.​Z
14. 14.
    Fung, G.M., Mangasarian, O.L.: Proximal support vector machine classifiers. In: Proceedings of International Conference on Knowledge Discovery and Data Mining, San Francisco, pp. 77–86 (2001)
15. 15.
    Fung, G.M., Mangasarian, O.L.: Multicategory proximal support vector machine classifiers. Mach. Learn. 59(1–2), 77–97 (2005)zbMATH
16. 16.
    Girolami, M.: Mercer kernel-based clustering in feature space. IEEE Trans. Neural Netw. 13(3), 780–784 (2002)
17. 17.
    Girosi, F.: An equivalence between sparse approximation and support vector machines. Neural Comput. 20, 1455–1480 (1998)
18. 18.
    Good, I.J.: The Estimation of Probabilities. MIT Press, Cambridge (1965)zbMATH
19. 19.
    Gunn, S.R.: Support vector machines for classification and regression. Technical Report, Faculty of Engineering, Science and Mathematics School of Electronics and Computer Science, University of Southampton (1998)
20. 20.
    Guyon, I., Weston, J., Barnhill, S., Vapnik, V.: Gene selection for cancer classification using support vector machines. Mach. Learn. 46, 389–422 (2002)zbMATH
21. 21.
    Hsu, C.-W., Lin C.-J.: A comparison of methods for multiclass support vector machines. IEEE Trans. Neural Netw. 13(2), 415–425 (2002)
22. 22.
    Huang, G.-B., Zhou, H., Ding, X., Zhang, R.: Extreme learning machine for regression and multiclass classification. IEEE Trans. Syst. Man Cybern. B Cybern. 42(2), 513–529 (2012)
23. 23.
    Ji, S., Xue, Y., Carin, L.: Bayesian compressive sensing. IEEE Trans. Signal Process. 56(6), 2346–2356 (2008)MathSciNetzbMATH
24. 24.
    Kimeldorf, G., Wahba, G.: Some results on Tchebycheffian spline functions. J. Math. Anal. Appl. 33, 82–95 (1971)MathSciNetzbMATH
25. 25.
    Knerr, S., Personnaz, L., Dreyfus, G.: Single-layer learning revisited: a stepwise procedure for building and training a neural network. In: Fogelman, J. (ed.) Neurocomputing: Algorithms, Architectures and Applications. Springer, New York (1990)
26. 26.
    MacKay, D.J.C.: Bayesian interpolation. Neural Comput. 4(3), 415–447 (1992)zbMATH
27. 27.
    Platt, J.C., Cristianini, N., Shawe-Taylor, J.: Large margin DAGs for multiclass classification. In: Advances in Neural Information Processing Systems, vol.12, pp. 547–553. MIT Press, Cambridge (2000)
28. 28.
    Rännar, S., Lindegren, F., Geladi, P., Wold, S.: A PLS kernel algorithm for data sets with many variables and fewer objects. Part 1: theory and algorithm. J. Chemometr. 8, 111–125 (1994)
29. 29.
    Rasmussen, C.E.: Gaussian processes in machine learning. In: Bousquet, O. et al. (ed.) Machine Learning 2003. Lecture Notes in Artificial Intelligence, vol. 3176, pp. 63–71. Springer, Berlin (2004)
30. 30.
    Rasmussen, C.E., Williams, C.K.I.: Gaussian Processes for Machine Learning. MIT Press, Cambridge (2005)zbMATH
31. 31.
    Rokotomamonjy, A.: Variable selection using SVM-based criteria. J. Mach. Learn. Res. 3, 1357–1370 (2003)MathSciNet
32. 32.
    Rosipal, R., Trejo, L.J.: Kernel partial least squares regression in reproducing kernel Hilbert space. J. Mach. Learn. Res. 2, 97–123 (2001)zbMATH
33. 33.
    Schölkopf, B., Smola, A., Müller, K.-R.: Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput. 10, 1299–1319 (1998)
34. 34.
    Schölkopf, B., Smola, A.J., Williamson, R.C., Bartlett, P.L.: New support vector algorithms. Neural Comput. 12, 1207–1245 (2000)
35. 35.
    Schölkopf, B., Herbrich, R., Smola, A.J.: A generalized representer theorem. In: Proceedings of the International Conference on Computational Learning Theory (COLT2001), pp. 416–426 (2001)
36. 36.
    Smola, A.J., Schölkopf, B.: A tutorial on support vector regression. Stat. Comput. 14, 199–222 (2004)MathSciNet
37. 37.
    Suykens, J.A.K., Vandewalle, J.: Least squares support vector machine classifiers. Neural Process. Lett. 9, 293–300 (1999)
38. 38.
    Tikhonov, A.N., Arsenin, V.Y.: Solutions of Ill-Posed Problems. Wiley, New York (1977)zbMATH
39. 39.
    Tipping, M.E.: Sparse Bayesian learning and the relevance vector machine. J. Mach. Learn. Res. 1, 211–244 (2001)MathSciNetzbMATH
40. 40.
    Tipping, M.E., Faul, A.C.: Fast marginal likelihood maximization for sparse Bayesian models. In: Bishop, C.M., Frey, B.J. (eds.) Proceedings of the 9th International Workshop Artificial Intelligence and Statistics (2003). http://​www.​miketipping.​com/​papers.​htm
41. 41.
    Van Gestel, T., Suykens, J.A.K., Lanckriet, G., Lambrechts, A., De Moor, B., Vandewalle, J.: Multiclass LS-SVMs: moderated outputs and coding-decoding schemes. Neural Process. Lett. 15(1), 48–58 (2002)zbMATH
42. 42.
    Vapnik, V.N.: Principles of risk minimization for learning theory. Adv. Neural Inf. Proces. Syst. 4, 831–838 (1992)
43. 43.
    Vapnik, V.N.: The Nature of Statistical Learning Theory. Springer, New York (1995)zbMATH
44. 44.
    Vapnik, V.N.: Statistical Learning Theory, vol. 1. Wiley, New York (1998)zbMATH
45. 45.
    Vapnik, V.N.: An overview of statistical learning theory. IEEE Trans. Neural Netw. 10(5), 988–999 (1999)
46. 46.
    Vapnik, V.N., Chervonenkis, A.: Theory of Pattern Recognition (in Russian). Moscow, Nauka (1974). (German Translation: Wapnik W., Tscherwonenkis A.: Theorie der Zeichenerkennung), Akademie-Verlag, Berlin (1979)zbMATH
47. 47.
    Wahba, G.: Support vector machines, reproducing Kernel Hilbert spaces, and randomized GACV. In: Schölkopf, B., Burges, C.J.C., Smola, A.J. (eds.) Advances in Kernel Methods – Support Vector Learning, pp. 69–88. The MIT Press, Cambridge (1999)
48. 48.
    Yuan, G.-X., Ho, C.-H., Lin C.-J.: Recent advances of large-scale linear classification. Proc. IEEE 100(9), 2584–2603 (2012)

Footnotes

1

In geometry a hyperplane is a subspace whose dimension is one less than that of its ambient space. For example, if a space is three-dimensional then its hyperplanes are the two-dimensional planes, while if the space is two-dimensional, its hyperplanes are the one-dimensional lines.