SVM 超平面计算例题

SVM Summary

Example

Suppose the dataset contains two positive samples $x^{(1)}=[1,1{]}^T$ and$x^{(2)}=[2,2{]}^T$, and two negative samples $x^{(3)}=[0,0{]}^T$ and $x^{(4)}=[-1,0{]}^T$. Please calculate the SVM decision hyperplane.

Calculate

$$\underset{\lambda }{\min }\mathcal{J}(\lambda )=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}^{(i)}{y}^{(j)}(x^{(i)}{)}^T{x}^{(j)}-\sum _{i=1}^N{\lambda }_i$$
$$s.t.{\lambda }_i⩾0,\sum _{i=1}^N{\lambda }_i{y}^{(i)}=0$$
由 D a t a s e t   D : { x : { [ 1 , 1 ] , [ 2 , 2 ] , [ 0 , 0 ] , [ − 1 , 0 ] } , y : { 1 , 1 , − 1 , − 1 } } Dataset\ D:\{x:\{[1,1],[2,2],[0,0],[-1,0]\},y:\{1,1,-1,-1\}\} Dataset D:{x:{[1,1],[2,2],[0,0],[−1,0]},y:{1,1,−1,−1}}可得下式：
$$\begin{gathered} \underset{\lambda }{\min }\mathcal{J}(\lambda )=\frac{1}{2}(2{\lambda }_1^2+8{\lambda }_2^2+{\lambda }_4^2+8{\lambda }_1{\lambda }_2+2{\lambda }_1{\lambda }_4+4{\lambda }_2{\lambda }_4) \\ -{\lambda }_1-{\lambda }_2-{\lambda }_3-{\lambda }_4 \\ s.t{\lambda }_1⩾0,{\lambda }_2⩾0,{\lambda }_3⩾0,{\lambda }_4⩾0 \\ {\lambda }_1+{\lambda }_2-{\lambda }_3-{\lambda }_4=0 \end{gathered}$$
since ${\lambda }_1+{\lambda }_2={\lambda }_3+{\lambda }_4\to {\lambda }_3={\lambda }_1+{\lambda }_2-{\lambda }_4$:
min ⁡ λ   J ( λ ) = λ 1 2 + 4 λ 2 2 + 1 2 λ 4 2 + 4 λ 1 λ 2 + λ 1 λ 4 + 2 λ 2 λ 4 − 2 λ 1 − 2 λ 2 s . t         λ 1 ⩾ 0 , λ 2 ⩾ 0 ⟹ 求 偏 导 { ∂ J ∂ λ 1 = 2 λ 1 + 4 λ 2 + λ 4 − 2 = 0 ∂ J ∂ λ 2 = 4 λ 1 + 8 λ 2 + 2 λ 4 − 2 = 0 ∂ J ∂ λ 4 = λ 1 + 2 λ 2 + λ 4 = 0 \min_\lambda\ {\mathcal{J}(\lambda)} = \lambda_1^2+4\lambda_2^2+\frac{1}{2}\lambda_4^2+4\lambda_1\lambda_2+\lambda_1\lambda_4+2\lambda_2\lambda_4 - 2\lambda_1-2\lambda_2\\ s.t \ \ \ \ \ \ \ \lambda_1 \geqslant 0,\lambda_2\geqslant 0 \\ \\ \Longrightarrow ^{求偏导}\\ \left\{

\right. λmin​ J(λ)=λ12​+4λ22​+21​λ42​+4λ1​λ2​+λ1​λ4​+2λ2​λ4​−2λ1​−2λ2​s.t       λ1​⩾0,λ2​⩾0⟹求偏导⎩⎨⎧​∂λ1​∂J​=2λ1​+4λ2​+λ4​−2=0∂λ2​∂J​=4λ1​+8λ2​+2λ4​−2=0∂λ4​∂J​=λ1​+2λ2​+λ4​=0​
Lagrange无解，所以极小值在边界上：

• 令${\lambda }_1=0，{\lambda }_3={\lambda }_1+{\lambda }_2-{\lambda }_4$带入$\mathcal{J}(\lambda )$中，得：
  J ( λ ) = 4 λ 2 2 + 1 2 λ 4 2 + + 2 λ 2 λ 4 − 2 λ 2 ⟹ 求 偏 导 { ∂ J ∂ λ 2 = 8 λ 2 + 2 λ 4 − 2 = 0 ∂ J ∂ λ 4 = 2 λ 2 + λ 4 = 0 ⟹ { λ 2 = 1 2 λ 4 = − 1 ( ≤ 0      不 满 足 s . t . ) 再 令 ： λ 2 = 0 , 则 λ 4 = 0 ， J ( λ ) = 0 ； 或 λ 4 = 0 , 则 λ 2 = 1 4 ， J ( λ ) = − 1 4 ； \mathcal{J}(\lambda) = 4\lambda_2^2+\frac{1}{2}\lambda_4^2++2\lambda_2\lambda_4 -2\lambda_2 \\ \\ \Longrightarrow ^{求偏导}\\ \left\{
  ∂J∂λ2=8λ2+2λ4−2=0∂J∂λ4=2λ2+λ4=0" role="presentation">∂J∂λ2=8λ2+2λ4−2=0∂J∂λ4=2λ2+λ4=0$$\begin{array}{c}\frac{\mathrm{\partial }\mathcal{J}}{\mathrm{\partial }{\lambda }_2}=8{\lambda }_2+2{\lambda }_4-2=0\\ \frac{\mathrm{\partial }\mathcal{J}}{\mathrm{\partial }{\lambda }_4}=2{\lambda }_2+{\lambda }_4=0\end{array}$$
  \right. \Longrightarrow \left\{
  λ2=12λ4=−1(≤0    不满足s.t.)" role="presentation">λ2=12λ4=−1(≤0    不满足s.t.)$$\begin{array}{c}{\lambda }_2=\frac{1}{2}\\ {\lambda }_4=-1(\le 0不满足s.t.)\end{array}$$
  \right.\\ 再令：\\ \lambda_2 = 0,则\lambda_4=0， \mathcal{J}(\lambda) = 0；\\ 或\lambda_4 = 0,则\lambda_2=\frac{1}{4}， \mathcal{J}(\lambda) = -\frac{1}{4}； J(λ)=4λ22​+21​λ42​++2λ2​λ4​−2λ2​⟹求偏导{∂λ2​∂J​=8λ2​+2λ4​−2=0∂λ4​∂J​=2λ2​+λ4​=0​⟹{λ2​=21​λ4​=−1(≤0    不满足s.t.)​再令：λ2​=0,则λ4​=0，J(λ)=0；或λ4​=0,则λ2​=41​，J(λ)=−41​；

同理可得：

• ${\lambda }_2=0$
  $$\begin{gathered} {\lambda }_1=0,则{\lambda }_4=0，\mathcal{J}(\lambda )=0； \\ 或{\lambda }_4=0,则{\lambda }_1=1，\mathcal{J}(\lambda )=-1； \end{gathered}$$
• ${\lambda }_3=0$
  $$\begin{gathered} {\lambda }_1=0,则{\lambda }_2=\frac{2}{13}，\mathcal{J}(\lambda )=-\frac{2}{13}； \\ 或{\lambda }_2=0,则{\lambda }_1=\frac{2}{5}，\mathcal{J}(\lambda )=-\frac{2}{5}； \end{gathered}$$
• ${\lambda }_4=0$
  $$\begin{gathered} {\lambda }_1=0,则{\lambda }_2=\frac{1}{4}，\mathcal{J}(\lambda )=-\frac{1}{4}； \\ 或{\lambda }_2=0,则{\lambda }_1=1，\mathcal{J}(\lambda )=-1； \end{gathered}$$
  综上： λ 1 , 2 , 3 , 4 = { 1 , 0 , 1 , 0 } \lambda_{1,2,3,4} =\{1,0,1,0\} λ1,2,3,4​={1,0,1,0}
  { W = ∑ i = 1 N λ i y ( i ) x ( i ) b = y ( j ) − ∑ i = 1 N λ i y ( i ) ( x ( i ) ) T x ( j ) ⟹ { W = [ 1 , 1 ] T b = − 1 ⟹ x ( 1 ) + x ( 2 ) − 1 = 0 \left\{
  W=∑i=1Nλiy(i)x(i)b=y(j)−∑i=1Nλiy(i)(x(i))Tx(j)" role="presentation">W=∑Ni=1λiy(i)x(i)b=y(j)−∑Ni=1λiy(i)(x(i))Tx(j)$$\begin{array}{c}W=\sum _{i=1}^N{\lambda }_i{y}^{(i)}{\mathit{x}}^{(i)}\\ b=y^{(j)}-\sum _{i=1}^N{\lambda }_i{y}^{(i)}{\left(x^{(i)}\right)}^T{x}^{(j)}\end{array}$$
  \right. \Longrightarrow \left\{
  W=[1,1]Tb=−1" role="presentation" style="position: relative;">W=[1,1]Tb=−1$$\begin{array}{c}W=[1,1{]}^T\\ b=-1\end{array}$$
  \right. \\\Longrightarrow x^{(1)}+x^{(2)} -1 =0 {W=∑i=1N​λi​y(i)x(i)b=y(j)−∑i=1N​λi​y(i)(x(i))Tx(j)​⟹{W=[1,1]Tb=−1​⟹x(1)+x(2)−1=0