# 支持向量机(SVM)的原理（线性可分硬间隔）

## 线性可分支持向量机

w ∗ ⋅ x + b = 0 w^*\cdot x+b=0

f ( x ) = s i g n ( w ∗ ⋅ x + b ) f(x)=sign(w^*\cdot x+b)

γ ^ i = y i ( w ⋅ x + b ) \hat{γ}_i=y_i(w\cdot x+b)

γ ^ = min ⁡ i = 1 , . . . , N γ ^ i \hat{γ}=\min_{i=1,...,N}{\hat{γ}_i}

γ ^ i = y i ( w ∣ ∣ w ∣ ∣ ⋅ x + b ∣ ∣ w ∣ ∣ ) \hat{γ}_i=y_i(\frac{w}{||w||}\cdot x+\frac{b}{||w||})

γ ^ = min ⁡ i = 1 , . . . , N γ ^ i \hat{γ}=\min_{i=1,...,N}{\hat{γ}_i}

## 间隔最大化

max ⁡ w , b γ \max_{w,b}γ
s.t. y i ( w ∣ ∣ w ∣ ∣ ⋅ x + b ∣ ∣ w ∣ ∣ ) ⩾ γ , i = 1 , 2 , . . . , N y_i(\frac{w}{||w||}\cdot x+\frac{b}{||w||})\geqslant γ, i=1,2,...,N

max ⁡ w , b γ ^ ∣ ∣ w ∣ ∣ \max_{w,b}\frac{\hat{γ}}{||w||}
s.t. y i ( w ⋅ x + b ) ⩾ γ ^ , i = 1 , 2 , . . . , N y_i(w\cdot x+b)\geqslant \hat{γ}, i=1,2,...,N

min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 \min_{w,b}\frac{1}{2}||w||^2
s.t. y i ( w ⋅ x i + b ) − 1 ⩾ 0 , i = 1 , 2 , . . . , N y_i(w\cdot x_i+b)-1\geqslant0,i=1,2,...,N

w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*=0

f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)=sign(w^*\cdot x+b^*)

L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 N α i y i ( w ⋅ x i + b ) + ∑ i = 1 N α i L(w,b,α)=\frac{1}{2}||w||^2-\sum_{i=1}^Nα_iy_i(w\cdot x_i+b)+\sum_{i=1}^Nα_i

max ⁡ α min ⁡ w , b L ( w , b , α ) \max_{α}\min_{w,b}L(w,b,α)

w = ∑ i = 1 N α i y i x i w = \sum_{i=1}^Nα_iy_ix_i
∑ i = 1 N α i y i = 0 \sum_{i=1}^Nα_iy_i=0

min ⁡ w , b L ( w , b , α ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i \min_{w,b}L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha _i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i \min_{\alpha}\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i
s.t.
∑ i = 1 N α i y i = 0 \sum_{i=1}^N\alpha_iy_i = 0
α i ⩾ 0 , i = 1 , 2 , . . . , N \alpha_i\geqslant0,i=1,2,...,N

w ∗ = ∑ i = 1 N α i y i x i w^*=\sum_{i=1}^N\alpha_iy_ix_i
b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)

∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ = 0 \sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0

f ( x ) = s i g n ( ∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ ) f(x)=sign(\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*)