Margin support vectors

Xi < C i = 0) This situation corresponds to correctly classified patterns situated on the hyperplanes that border the SVMC OSH, i.e., patterns +1 are situated on the hyperplane wxi + b = +1), whereas patterns -1 are situated on the hyperplane (wxi + b = —1). The distance between these patterns and the separating hyperplane is l/ w. Such a pattern is called a margin support vector. 

Fig. 8. Representation of a support vector machine. There are three different compounds in this simplified SVM representation. The plus (+) symbols represent active, the minus (-) symbols represent nonactive, and the question mark ( ) symbol represents undetermined compounds. The solid line in the hyperplane and the dotted lines represent the maximum margin as defined by the support vectors.

Figure 1.9. SVM-based hyperplane. Two classes of molecules are separated in descriptor space by a hyperplane (H(x) = 0) with margins (H(x) = 1). Support vectors are shown as filled objects and used to construct the hyperplane and define its margins...

SVM s are an outgrowth of kernel methods. In such methods, the data is transformed with a kernel equation (such as a radial basis function) and it is in this mathematical space that the model is built. Care is taken in the constmction of the kernel that it has a sufficiently high dimensionality that the data become linearly separable within it. A critical subset of transformed data points, the support vectors , are then used to specify a hyperplane called a large-margin discriminator that effectively serves as a hnear model within this non-hnear space. An introductory exploration of SVM s is provided by Cristianini and Shawe-Taylor and a thorough examination of their mathematical basis is presented by Scholkopf and Smola. ... 

Figure 15-9 A support vector machine (SVM).The patients in the training data are represented by encircled plus and minus signs, while example patients that we have not seen before are represented by encircled question marks.The SVM classifier in this example is the set of the two parallel lines that go through patients Pj, P2, and P3, respectively.These two lines specify the classification margin. Patients P, P2, and P3 are the support vectors. Unseen cases are classified according to whether they are closer to the line defined by the disease-positive support vectors P, P3. or to the line parallel to the previous line and the disease-negative support vector P3.

As illustrated in Figure 5, SVMs work by constructing a hyper-plane in a higher-dimensional feature space of the input data,91 and use the hyper-plane (represented as Hi and H2) to enforce a linear separation of input samples, which belong to different classes (represented as Class O and Class X). The samples that lie on boundaries of different classes are referred to as support vectors. The underlying principle behind SVM-based classification is to maximize the margin between the support vectors using kernel functions. In the case of... 

FIGURE 13.15. Example of two linearly separable classes that can be separated with (a) several hyperplanes, but for which SVM defines (b) a unique separating hyperplane. The margin (M) is the distance between the dashed lines through the support vectors. 

Only those training vectors will have nonzero Lagrange multipliers which are at the class boundaries or are margin errors. These prototypes, which determine the construction of the decision function, are termed support vectors. 

A Support Vector Machine (SVM) is a class of supervised machine learning techniques. It is based on the principle of structural risk minimization. The ideal of SVM is to search for an optimal hyperplane to separate the data with maximal margin. Let <5 -dimensional input x belong to two classwhich was labeled... 

Hence only the points x, which satisfy, change equation will have non-zero Lagrange multipliers. These points are termed Support Vectors (SV). All the SVs will lie on the margin and hence the number of SVs can be very small. Consequently the hyperplane is determined by a small subset of the training set. Hence the solution to the optimal classified problem is given by. 

In effect, the maximum margin, i.e. optimal typerplane, is the one that gives the greatest separation between the classes. The data points that are closest to the optimal hyperplane are called support vectors (SV) . In each class, there exists at least one SV very often there are multiple SVs. The optimal hyperplane is uniquely defined by a set of SVs. As a result, all other training data points can be ignored. 

Figure 6.10 An example of linearly separable classes where different frontiers (hyperplanes or borders) are possible (a) concept of optimum separated hyperplane, margin and support vectors (b) concept of slack variables (c).

The positive point here is that to calculate the optimum hyperplane, only a very reduced set of samples will be required. They will be those that locate exactly over the margins around the hyperplane and, therefore, they are called support vectors (SV Figure 6.10b). Recall that the hyperplane is defined in the feature space and therefore in general it cannot be visualised as in the example. 

Based on the concept of classical statistical mathematics, people are apt to think that the number of free parameters (or the dimension of feature space) is the controlling factor deciding the reliability of mathematical model for prediction. But Vapnik and his coworkers have proved that the controlling factor for the reliability in classification problems is VC dimension. And VC dimension exhibits no one-to-one correspondence to the number of free parameters. One of the most important achievements of Vapnik and his coworkers is the large margin concept. It is found that the VC dimension can be greatly depressed if the sample points of different classes can be mapped into another feature space to make a wide margin between the points of two classes. It is just this achievement that makes the success of support vector machine. 

In this chapter, we will give a comprehensive introduction to support vector machine (SVM) in an accessible and self-contained way. The organization of this chapter is as follows We start from the central concepts about margin, from which the support vector methods are developed Second, the SVM for classification problems are introduced and the derivation in both linear and nonlinear cases will be described in detail Third, we discuss the support vector regression, i.e. the SVM in regression problems. At last, a variant of SVM, v-SVM is briefly introduced. 

Section 2.1 has attempted to determine the maximal margin hyperplane in an intuitive way. Support Vector Machine, the successful implementation of statistical learning theory (SLT), are built on the basis of the maximal margin hyperplane described above. It is important to reveal the relationship between the formula (2.16) and SLT. 

In practice, the soft margin versions of the standard SVM (also known as C-SVM) described in the previous sections often suffer from the following problems. Firstly, there is a problem of how to determine the error penalty parameter C. Although the cross-validation technique can be used to determine this parameter, it is still hard to explain. Secondly, the time taken for a support vector classifier to compute the class of a new sample is proportional to the number of support vectors, so if that number is large, the computation is time-consuming. 

It can be shown that v gives an upper bound on the fraction of the training set that are margin errors and provides a lower bound on the total number of support vectors. Accordingly, when the sample size goes to infinity, both fractions tend almost surely to v under rather general assumptions on the learning problem and the used kernel. 

---