Database Reference
In-Depth Information
EXAMPLE 12.8 Let us consider the four points of Fig. 11.1 , supposing that they alternate as
positive and negative examples. That is, the training set consists of
([1, 2], +1) ([2, 1], −1)
([3, 4], +1) ([4, 3], −1)
Let w = [ u , v ]. Our goal is to minimize subject to the constraints we derive from
the four training examples. For the first, where x 1 = [1, 2] and y 1 = +1, the constraint is
(+1)( u +2 v + b ) = u +2 v + b ≥ 1. For the second, where x 2 = [2, 1] and y 2 = −1, the constraint
is (−1)(2 u + v + b ) ≥ 1, or 2 u + v + b ≤ −1. The last two points are analogously handled, and the
four constraints we derive are:
u + 2 v + b ≥ 1 2 u + v + b ≤ −1
3 u + 4 v + b ≥ 1 4 u + 3 v + b ≤ −1
We shall cover in detail the subject of how one optimizes with constraints; the subject is
broad and many packages are available for you to use. Section 12.3.4 discusses one method
- gradient descent - in connection with a more general application of SVM, where there is
no separating hyperplane. An illustration of how this method works will appear in Example
12.9 .
In this simple example, the solution is easy to see: b = 0 and w = [ u , v ] = [−1, +1]. It hap-
pens that all four constraints are satisfied exactly; i.e., each of the four points is a support
vector. That case is unusual, since when the data is two-dimensional, we expect only three
support vectors. However, the fact that the positive and negative examples lie on parallel
lines allows all four constraints to be satisfied exactly.
12.3.3
Finding Optimal Approximate Separators
We shall now consider finding an optimal hyperplane in the more general case, where no
matter which hyperplane we chose, there will be some points on the wrong side, and per-
haps some points that are on the correct side, but too close to the separating hyperplane
itself, so the margin requirement is not met. A typical situation is shown in Fig. 12.16 . We
see two points that are misclassified; they are on the wrong side of the separating hyper-
plane w . x + b = 0. We also see two points that, while they are classified correctly, are too
close to the separating hyperplane. We shall call all these points bad points.
Search WWH ::




Custom Search