Separation hyperplane

A polynomial function is applied to return the inner products of descriptor vectors and the separating hyperplane is defined as... 

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. 

Separation of overlapping classes is not feasible with methods such as discriminant analysis because they are based on optimal separating hyperplanes. SVMs provide an efficient solution to separating nonhnear boundaries by constructing a linear boundary in a large, transformed version of the feature space. 

Support vector machine (SVM) is originally a binary supervised classification algorithm, introduced by Vapnik and his co-workers [13, 32], based on statistical learning theory. Instead of traditional empirical risk minimization (ERM), as performed by artificial neural network, SVM algorithm is based on the structural risk minimization (SRM) principle. In its simplest form, linear SVM for a two class problem finds an optimal hyperplane that maximizes the separation between the two classes. The optimal separating hyperplane can be obtained by solving the following quadratic optimization problem ... 

Support vector machine (SVM) is a widely used machine learning algorithm for binary data classification based on the principle of structural risk minimization (SRM) [21, 22] unlike the traditional empirical risk minimization (ERM) of artificial neural network. For a two class problem SVM finds a separating hyperplane that maximizes the width of separation of between the convex hulls of the two classes. To find the expression of the hyperplane SVM minimizes a quadratic optimization problem as follows ... 

Fig. 13.2 The ideal steric moleeular field corresponding to the vector perpendicular to separating hyperplane in the 1-SVM model built for thrombin inhibitors (2-amidinophenylalanines). Its isosurface can be viewed as a negative image of the binding site in biological taiget...

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

Therefore, the analyst has to set C. This is not always trivial because it determines the toleranee of the model, with larger values reflected in lower tolerance of miselassifieation and more complex separating hyperplanes (these models are likely to be prone to over-fitting). To identify the trade-off may be trieky and time eonsuming and some care is needed. 

According to Theorem 2.2, given some selection of learning machines whose empirical risk is zero, one wants to choose that learning machine whose associated set of functions has minimal VC dimension. At present, for the y-margin separating hyperplane, we quote an important theorem without proof as follows. For more details, see [132]. 

Theorem 2.3 Let vectors x e belong to a sphere of radius R. Then the set of -margin separating hyperplanes has the VC dimension h bounded by the inequality... 

Finally, the optimal separating hyperplane decision function can thus be written as... 

Note that both the separation hyperplane in (2.33) and the objective function of our optimization problem (2.26) do not depend explicitly on the dimensionality of the vector x but depend only on the inner product of two vectors. This fact will allow us later to construct separating hyperplanes in high-dimensional spaces. 

In a natural way, therefore, the generalized optimal separating hyperplane is determined by solving the following functional ... 

The use of nonlinear kernels provides the SVM with the ability to model complicated separation hyperplanes in this example. However, because there is no theoretical tool to predict which kernel will give the best results for a given dataset, experimenting with different kernels is the only way to identify the best function. An alternative solution to discriminate the patterns from Table 1 is offered by a degree 3 polynomial kernel (Figure 5a) that has seven support vectors, namely three from class +1 and four from class —1. The separation hyperplane becomes even more convoluted when a degree 10 polynomial kernel is used (Figure 5b). It is clear that this SVM model, with 10 support vectors (4 from class +1 and 6 from class —1), is not an optimal model for the dataset from Table 1. 

In general, for each linearly separable training set, one can find an infinite number of hyperplanes that discriminate the two classes of patterns. Although all these linear classifiers can perfectly separate the learning patterns, they are not all identical. Indeed, their prediction capabilities are different. A hyperplane situated in the proximity of the border +1 patterns will predict as —1 all new -hi patterns that are situated close to the separation hyperplane but in the —1 region (w x- -fi<0). Conversely, a hyperplane situated in the proximity of the border —1 patterns will predict as -hi all new —1 patterns situated close to the separation hyperplane but in the - -1 region (w x -F > 0). It is clear that such classifiers have little prediction success, which led to the idea... 

The optimum separation hyperplane (OSFI) is the hyperplane with the maximum margin for a given finite set of learning patterns. The OSH computation with a linear support vector machine is presented in this section. 

Based on the notations from Figure 21, we will now establish the conditions necessary to determine the maximum separation hyperplane. Consider a... 

The problem of finding the optimum separation hyperplane is represented by the identification of the linear classifier (w, b), which satisfies... 

In the previous section, we presented the SVM algorithm for training a linear classifier. The result of this training is an optimum separation hyperplane defined by (w, b) (Eqs. [29] and [31]). After training, the classifier is ready to predict the class membership for new patterns, different from those used in training. The class of a pattern is determined with... 

We now present several SVM classification experiments for a dataset that is linearly separable (Table 3). This exercise is meant to compare the linear kernel with nonlinear kernels and to compare different topologies for the separating hyperplanes. All models used an infinite value for the capacity parameter C (no tolerance for misclassified patterns see Eq. [39]). 

---