# 线性支持向量机（SVM）与软间隔最大化

y i ( w ⋅ x i + b ) ⩾ 1 − ξ i y_i(w\cdot x_i+b)\geqslant1-\xi_i

1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i

min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i \min_{w,b,\xi}\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i
s.t.
y i ( w ⋅ x i + b ) ⩾ 1 = ξ i , i = 1 , 2 , ⋯   , N y_i(w\cdot x_i+b)\geqslant1=\xi_i, i=1,2,\cdots,N
ξ i ⩾ 0 , i = 1 , 2 , ⋯   , N \xi_i\geqslant0,i=1,2,\cdots,N

L ( w , b , ξ , α , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i − ∑ i = 1 N α i ( y i ( w ⋅ x i + b ) − 1 + ξ i ) − ∑ i = 1 N μ i ξ i L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(w\cdot x_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i

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
C − α i − μ i = 0 C-\alpha_i-\mu_i=0

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
0 ⩽ α i ⩽ C , i = 1 , 2 , ⋯   , N 0\leqslant\alpha_i\leqslant C,i=1,2,\cdots,N

α ∗ = ( α 1 ∗ , α 2 ∗ , ⋯   , α N ∗ ) \alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*) 为对偶问题的一个解，若存在 α ∗ \alpha^* 的一个分量 α j ∗ \alpha^*_j 0 < α j ∗ < C 0<\alpha^*_j，则原始问题的解 w ∗ , b ∗ w^*,b^* 可按下式求得
w ∗ = ∑ i = 1 N α i ∗ y i x i w^*=\sum_{i=1}^N\alpha_i^*y_ix_i
b ∗ = y i − ∑ i = 1 N y i α i ∗ ( x i ⋅ x j ) b^*=y_i-\sum_{i=1}^Ny_i\alpha_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^*)

## 合页损失函数

min ⁡ w , b ∑ i = 1 N [ 1 − y i ( w ⋅ x i + b ) ] + + λ ∣ ∣ w ∣ ∣ 2 \min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2