Hyperplane support

In light of the above facts, there exists at yf a hyperplane supporting the convex set of final states. Let... 

Given any boundary point y of the set S, there exists a non-zero vector p such that the dot product p (y — y) <0 for all y in the S. This result means that a hyperplane supports the set S at each of its boundary point. 

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.

Illustration 2.1.7 Figure 2.6 provides a few examples of supporting hyperplanes for convex and nonconvex sets. 

The dual function at (fa, fa) corresponds to determining the lowest plane with slope (-fa,—fa) which intersects the image set /. This corresponds to the supporting hyperplane h which is tangent to the image set I at the point P, as shown in Figure 4.1. 

The minimum value of this problem is the value of z3 where the supporting hyperplane h intersects the ordinate, denoted as z3 in Figure 4.1. 

Determine the value of which defines the slope of a supporting hyperplane to the... 

Remark 1 The value of (/Zi, fi2) that intersects the ordinate at the maximum possible value in Figure 4.1 is the supporting hyperplane of I that goes through the point P, which is the optimal solution to the primal problem (P). 

Remark 6 The geometrical interpretation of the primal and dual problems clarifies the weak and strong duality theorems. More specifically, in the vicinity of y — 0, the perturbation function v(y) becomes the 23-ordinate of the image set I when zi and z2 equal y. In Figure 4.1, this ordinate does not decrease infinitely steeply as y deviates from zero. The slope of the supporting hyperplane to the image set I at the point P, (-pi, -p2), corresponds to the subgradient of the perturbation function u(y) at y = 0. 

Remark 7 An instance of unstable problem (P) is shown in Figure 4.2 The image set I is tangent to the ordinate 23 at the point P. In this case, the supporting hyperplane is perpendicular, and the value of the perturbation function v(y) decreases infinitely steeply as y begins to increase above zero. Hence, there does not exist a subgradient at y = 0. In this case, the strong duality theorem does not hold, while the weak duality theorem holds. 

Remark 1 The difference in the optimal values of the primal and dual problems can be due to a lack of continuity of the perturbation function v(y) at y = 0. This lack of continuity does not allow the existence of supporting hyperplanes described in the geometrical interpretation section. 

If the support functions are linear iny, then the master problem approximates v(y) by tangent hyperplanes and we can conclude that v(y) is convex iny. Note that v(y) can be convex iny even though problem (6.2) is nonconvex in the jointx-y space Floudas and Visweswaran (1990). 

Support vector machines In addition to more traditional classification methods like clustering or partitioning, other computational approaches have recently also become popular in chemoinformatics and support vector machines (SVMs) (Warmuth el al. 2003) are discussed here as an example. Typically, SVMs are applied as classifiers for binary property predictions, for example, to distinguish active from inactive compounds. Initially, a set of descriptors is selected and training set molecules are represented as vectors based on their calculated descriptor values. Then linear combinations of training set vectors are calculated to construct a hyperplane in descriptor space that best separates active and inactive compounds, as illustrated in Figure 1.9. 

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

Figure 13.10 SVM training results in the optimal hyperplane separating classes of data. The optimal hyperplane is the one with the maximum distance from the nearest training patterns (support vectors). The three support vectors defining the hyperplane are shown as solid symbols. D(x) is the SVM decision function (classifier function).

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

Kernel methods, which include support vector machines and Gaussian processes, transform the data into a higher dimensional space, where it is possible to construct one or more hyperplanes for separation of classes or regression. These methods are more mathematically rigorous than neural networks and have in recent years been widely used in QSAR modeling. ... 

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. 

Figure 5.3 A convex set S of final states with a supporting hyperplane P. A hyperplane is a tangent line in two dimensions...

Now for a convex set, there exists a supporting hyperplane at any boundary point of the set (see Appendix 5.B, p. 149). We apply this result to our convex set of final states, in which the final optimal state... 

---