# 线性支持向量机

y i ( w ∗ x i + b ) > = 1 − ξ i （ 1 ） y_i(w*x_i+b)>=1-\xi_i （1）

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 s.t. y_i(w*x_i+b)>=1-\xi_ii=1,2,...,N
ξ i > = 0 , i = 1 , 2 , . . . , N \xi_i>=0,i=1,2,...,N

## 线性支持向量机的定义

w ∗ x + b = 0 w*x+b=0

f ( x ) = s i g n ( w ∗ x + b ) f(x)=sign(w*x+b)

## 学习的对偶算法

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y ( 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(x_i*x_j)-\sum_{i=1}^{N}\alpha_i
s . t . ∑ i = 1 N a i y i = 0 s.t.\sum_{i=1}^{N}a_iy_i=0
a < = α i < = C , i = 1 , 2 , . . . , N a<=\alpha_i<=C,i=1,2,...,N

L ( w , b , ξ , α , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( y i ( w ∗ x + 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*x+b)-1+\xi_i)-\sum_{i=1}^{N}\mu_i\xi_i
α i > = 0 , μ i > = 0 \alpha_i>=0,\mu_i>=0

∇ w L = 0 , ∇ b = 0 , ∇ ξ = 0 得 到 \nabla_wL=0,\nabla_b=0,\nabla_\xi=0得到
w = ∑ i = 1 N α i y i x i , ∑ i = 1 N a i y i = 0 , C − α i − μ i = 0 w=\sum_{i=1}^{N}\alpha_iy_ix_i,\sum_{i=1}^{N}a_iy_i=0,C-\alpha_i-\mu_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,\xi}L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^{N}\alpha_i

max ⁡ α 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 \max_{\alpha}L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^{N}\alpha_i
s . t . ∑ i = 1 N α i y i = 0 s.t.\sum_{i=1}^{N}\alpha_iy_i=0
C − α i − μ i = 0 C-\alpha_i-\mu_i=0
α i > = 0 \alpha_i>=0
μ i > = 0 , i = 1 , 2 , . . . , N \mu_i>=0,i=1,2,...,N

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y ( 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(x_i*x_j)-\sum_{i=1}^{N}\alpha_i

### 线性支持向量机学习算法

（1）选择惩罚参数C>0。构造并求解凸二次规划问题
min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y ( 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(x_i*x_j)-\sum_{i=1}^{N}\alpha_i
s . t . ∑ i = 1 N a i y i = 0 s.t.\sum_{i=1}^{N}a_iy_i=0
a < = α i < = C , i = 1 , 2 , . . . , N a<=\alpha_i<=C,i=1,2,...,N

（2）计算 w ∗ w^* ，选择 α ∗ \alpha^* 的一个分量 α j ∗ \alpha_j^* 适合条件 0 < α i ∗ < C 的 α j ∗ 0<\alpha_i^*计算 b ∗ b^*
（3）求得分离超平面和决策函数