Figure 7.13 displays two groups of data points, given in Table 7.8. The convex hulls have also been plotted. It is possible to separate the two classes of points via a straight line.

In fact, many such lines are possible. SVM gives the best separation, in the sense that the gap (margin) between the points is maximal.

(a) Identify from the figure the three support vectors.

(b) For a separating boundary (line) given by \(\beta_{0}+\boldsymbol{\beta}^{\top} \boldsymbol{x}=0\), show that the margin width is \(2 / \|\) \(\boldsymbol{\beta} \|\).

(c) Show that the parameters \(\beta_{0}\) and \(\boldsymbol{\beta}\) that solve the convex optimization problem (7.24) provide the maximal width between the margins.

(d) Solve (7.24) using a penalty approach; see Section B.4. In particular, minimize the penalty function 415 \[ S\left(\boldsymbol{\beta}, \beta_{0}\right)=\|\boldsymbol{\beta}\|^{2}-C \sum_{i=1}^{n} \min \left\{\left(\beta_{0}+\boldsymbol{\beta}^{\top} \boldsymbol{x}_{i}\right) y_{i}-1,0\right\} \]
for some positive penalty constant \(C\).

(e) Find the solution the dual optimization problem (7.21) by using sklearn's sCV method. Note that, as the two point sets are separable, the constraint \(\lambda \leqslant 1\) may be removed, and the value of \(\gamma\) can be set to 1 .

Transcribed Image Text:

-1 1 0 5 4 3 2 6 -3 -2 -1 0 1 2 3 4 Figure 7.13: Separate the points by a straight line so that the separation between the two groups is maximal.