Functional Margin

• Relative distance. For a hyperplane, $wx+b=0$, the relative distance (not geometric distance) from a point $x_i$ to this hyperplane is $|w{x}_i+b|$.

  • When $w\cdot x_i+b>0$, the instance $x_i$ is above the hyperplane, and $x_i$ is classified by positive. If $y_i=+1$, then the classification is correct. See blue points.

  • When $w\cdot x_i+b<0$, the instance $x_i$ is below the hyperplane, and $x_i$ is classified by negative If $y_i=-1$, then the classification is correct. See green points.

  • Consistency of the sign of $w{x}_i+b$ with the sign of its class label $y_i$ can tell the correctness of the classification.

  • Functional Margin. The functional margin of a sample point $(x_i,y_i)$ and a hyperplane $(wx,b)$ is defined as ${\hat{\gamma }}_i(w,b)=y_i(wx+b),i=1,2,\dots ,n$. The functional margin of the training dataset $T$ and a hyperplane $(wx,b)$ is defined as $\hat{\gamma }(w,b)={min}_i{\hat{\gamma }}_i(w,b)$.

• Reliability. For a linearly separable SVM, the distance from an instance to the hyperplane indicates the reliability of the classification prediction: the farther an instance to the hyperplane is, the more reliable the classification is, and vice versa.

• Shortcoming of the functional margin. When $(w,b)$ changes proportionally, for example $(10w,10b)$, the hyperplane $10w+10b=0$ keeps the same. Thus, we introduce geometric margin that makes a unique maximum margin hyperplane (solid line in Fig. 1).

Geometric Margin

The geometric distance between $x_i$ and the hyperplane $wx+b=0$ is given by

$${\gamma }_i=\frac{|w{x}_i+b|}{\parallel w\parallel }.$$ Similarly, we will choose $(w,b)$ to make $wx+b<0$ for negative instances, and $>0$ for positive instances. Therefore, when a sample point $(x_i,y_i)$ is correctly classified, the geometric distance from the hyperplane is ${\gamma }_i=\frac{y_i(w{x}_i+b)}{\parallel w\parallel }.$ Thus, geometric margin between $(x_i,y_i)$ and a hyperplane $(w,b)$ is defined as $${\gamma }_i(w,b)=\frac{y_i(w{x}_i+b)}{\parallel w\parallel },i=1,2,\dots ,n$$ and geometric margin between a training dataset $T$ and a hyperplane $(w,b)$ is defined as

$$\gamma (w,b)=\underset{x_i\in T}{min}{\gamma }_i(w,b).$$ Note that the geometric margin is scale invariant and it is a function of $(w,b)$.

Linearly Separable SVM as An Optimization Problem

The target of SVM is to find a hyperplane with maximum geometric margin to correctly separate training dataset. The maximum geometric margin is also called maximum hard margin. This goal falls into the description of constraint optimization problems:

$$\begin{array}{ccc}& & \underset{w,b}{max}\gamma \\ & & s.t.\frac{y_i(w{x}_i+b)}{\parallel w\parallel }\ge \gamma ,i=1,2,\dots ,n& \text{(2)}\end{array}$$ The inequality in Eq. (2) holds because $\frac{y_i(w{x}_i+b)}{\parallel w\parallel }={\gamma }_i(w,b)\ge {min}_{x_i\in T}{\gamma }_i(w,b)=\gamma$.

According to connection between functional margin and geometric margin, the above proglem can be converted to: $$\begin{array}{ccc}& & \underset{w,b}{max}\frac{\hat{\gamma }}{\parallel w\parallel }\\ & & s.t.y_i(w{x}_i+b)\ge \gamma \parallel w\parallel ,i=1,2,\dots ,n.\end{array}$$ Note that for all $i$, $$y_i(w{x}_i+b)\ge \gamma \parallel w\parallel ⟺y_i(\frac{w}{\gamma \parallel w\parallel }{x}_i+\frac{b}{\gamma \parallel w\parallel })\ge 1.$$ Reparameterizing, $$\frac{w}{\gamma \parallel w\parallel }\triangleq \tilde{w},\frac{b}{\gamma \parallel w\parallel }\triangleq \tilde{b}.$$ Therefore, the new hyperplane is $(\tilde{w},\tilde{b})$. Suppose a point $(x_0,y_0)$ is in the line: $\tilde{w}x+\tilde{b}=\pm 1$, then the geometric margin is $\gamma =\frac{|\tilde{w}{x}_0+\tilde{b}|}{\parallel \tilde{w}\parallel }=\frac{1}{\parallel \tilde{w}\parallel }$, and functional margin is $\hat{\gamma }=1$.

Therefore, Eq. (2) is equivalent to $$\begin{array}{ccc}& & \underset{w,b}{max}\frac{1}{\parallel w\parallel }\\ & & s.t.y_i(w{x}_i+b)\ge 1,i=1,2,\dots ,n.\end{array}$$ Note that $max\frac{1}{\parallel w\parallel }⟺min\frac{1}{2}\parallel w{\parallel }^2$. Therefore, the SVM for a linearly separable data set is the solution of the following restricted convex optimization problem: $$\begin{array}{ccc}& & \underset{w,b}{min}\frac{1}{2}\parallel w{\parallel }^2\\ & & s.t.y_i(w{x}_i+b)-1\ge ,i=1,2,\dots ,n,\end{array}$$ which is a quadratic convex optimization problem.

The complete SVM alogrithm can be described as follows:

• Input: Linearly separable training dataset $T=\left\{\right(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n\left)\right\}$, where $x_i=(x_i^{\left(1\right)},x_i^{\left(2\right)},\dots ,x_i^{\left(d\right)}{)}^{\top }\in R^d,y_i\in Y=\{+1,-1\},i=1,2,\dots ,n$.

• Output: The separating hyperplane $wx+b=0$ and the classification decision function.

1. Find the solution $(w^{\ast },b^{\ast })$ of the following restricted optimization question:

$$\begin{array}{c}\{\begin{array}{c}{min}_{w,b}\frac{1}{2}\parallel w{\parallel }^2\\ s.t.y_i(w{x}_i+b)-1\ge 0,i=1,2,\dots ,n.\end{array}\end{array}$$

2. The separating hyperplane is $$w^{\ast }x+b^{\ast }=0,$$ and the classification decision function is $$f\left(x\right)=\text{sign}(w^{\ast }x+b^{\ast }).$$

Existence and Uniqueness of SVM Hyperplane

Proof of Existence: Note that the linearly separability of $T$ implies there exists a feasible point $(\tilde{w},\tilde{b})$, such that the optimization question is equivalent to

$$\begin{array}{c}\{\begin{array}{c}{min}_{w,b}\frac{1}{2}\parallel w{\parallel }^2\\ s.t.y_i(w{x}_i+b)-1\ge 0,i=1,2,\dots ,n,\\ \parallel w\parallel \le \parallel \tilde{w}\parallel .\end{array}\end{array}$$ Therefore, the feasible region of this optimization question is nonempty and bounded closed set. Note that any continuous function achieves minimum in a nonempty and bounded closed set, os the solution to the optimization question exists. Also, because both positive and negative instances present in $T$, so for any $(w,b)$ with $(w,b)=(0,b)$ will not be a feasible point, which implies the solution must satisfy $w^{\ast }\ne 0.\square$

Proof of Uniqueness:

1. Before showing the uniqueness, we prove the following two statements first:

• There exists $j\in \{i:y_i=1\}$, such that $w^{\ast }{x}_j+b^{\ast }=1$;

• There exists $j\in \{i:y_i=-1\}$, such that $w^{\ast }{x}_j+b^{\ast }=-1$;

Use contradiction. Suppose the first statement is not true, then

$$w^{\ast }{x}_j+b^{\ast }>1,\text{for}\forall j\in \{i:y_i=1\}.$$ Since $w^{\ast },b^{\ast }$ satisfy the contrains, so $$w^{\ast }{x}_j+b^{\ast }\le -1,\text{for}\forall j\in \{i:y_i=-1\}.$$ For any $\alpha \in (0,1)$, let $\tilde{w}=\alpha w^{\ast },\tilde{b}=(b^{\ast }+1)\alpha -1$. Then for any $j\in \{i:y_i=-1\}$, $$\tilde{w}{x}_j+\tilde{b}=\alpha w^{\ast }{x}_j+(b^{\ast }+1)\alpha -1=\alpha (w^{\ast }{x}_j+b^{\ast })+\alpha -1\le -\alpha +\alpha -1=-1.$$ For any $j\in \{i:y_i=1\}$, $$\underset{\alpha \to 1^{-}}{lim}(\tilde{w}{x}_j+\tilde{b})=\underset{\alpha \to 1^{-}}{lim}\left[\alpha \right(w^{\ast }{x}_j+b^{\ast })+\alpha -1]=w^{\ast }{x}_j+b^{\ast }\ge 1.$$ So, we can choose a suitable $\alpha \in (0,1)$ such that $$\tilde{w}{x}_j+\tilde{b}>1\text{for}\forall j\in \{i:y_i=1\}.$$ This implies that $(\tilde{w},\tilde{b})$ is a feasible point. However $\parallel \tilde{w}{\parallel }^2={\alpha }^2\parallel w^{\ast }{\parallel }^2\le \parallel w^{\ast }{\parallel }^2$, which implies $(w^{\ast },b^{\ast })$ is not a solution.$\square$

2. Now let’s show the uniqueness of SVM hyperplane.

Suppose we have optimal solutions $(w_1^{\ast },b_1^{\ast })$ and $(w_2^{\ast },b_2^{\ast })$.

First we show that $w_1^{\ast }=w_2^{\ast }$. It is easy to verify that $(w,b)$ is a feasible point. Note that we must have $\parallel w_1^{\ast }\parallel =\parallel w_2^{\ast }{\parallel }^2=c\ge 0.$ Let $w=(w_1^{\ast }+w_2^{\ast })/2$, and $b=(b_1^{\ast }+b_2^{\ast })/2$. Then $$c\le \parallel w\parallel =\frac{1}{2}\parallel w_1^{\ast }+w_2^{\ast }\parallel \le \frac{1}{2}(\parallel w_1^{\ast }\parallel +\parallel w_2^{\ast }\parallel )=c.$$ So equality holds. Hence, $c=\parallel w\parallel =\frac{1}{2}\sqrt{\parallel w_1^{\ast }{\parallel }^2+\parallel w_2^{\ast }{\parallel }^2+2\parallel w_1^{\ast }\parallel \parallel w_2^{\ast }\parallel \cos \theta }=\frac{1}{2}\sqrt{2c^2(\cos \theta +1)}$, where $\theta$ is the angle between $w_1^{\ast }$ and $w_2^{\ast }$. Thus we have $\theta =0$ or $\pi$. If $\theta =\pi$, $w=0$, which is impossible because $(w,b)$ is a feasible point. Then we mush have $\theta =0$, which implies $w_1^{\ast }=w_2^{\ast }$.

Finally, we show that $b_1^{\ast }=b_2^{\ast }$. From aforementioned, there exists $i,j$ such that $y_i=1$ and $y_j=-1$. Thus we have

$$w^{\ast }{x}_i+b_1^{\ast }=1,w^{\ast }{x}_j+b_1^{\ast }\le -1$$ and $$w^{\ast }{x}_j+b_2^{\ast }=1,w^{\ast }{x}_i+b_2^{\ast }\ge 1.$$ This implies $b_1^{\ast }=b_2^{\ast }.■$

Support Vectors

When the training data set $T$ is linearly separable, the points $x_i$ which satisfy

$$w{x}_i+b\pm 1=0$$ are called suport vectors.

Dual Problem

We regard the solution to optimization problem of the linearly separable SVM as the primary optimization problem. $$\begin{array}{ccc}& & \underset{w,b}{min}\frac{1}{2}\parallel w{\parallel }^2\\ & & s.t.y_i(w{x}_i+b)-1\ge 0,i=1,2,\dots ,n,\end{array}$$

We construct the Lagrange function

$$L(w,b,\alpha )=\frac{1}{2}\parallel w{\parallel }^2-\sum {\alpha }_i\left[y_i\right(w{x}_i+b)-1],$$ where ${\alpha }_i\ge 0,\alpha =({\alpha }_1,\dots ,{\alpha }_n)$ is the Lagrange multiplier vector.