支持向量机|从0开始，搞懂SVM支持向量机！人工智能|机器学习

SVM支持向量机：支持向量机(Support Vecor. Machine, SVM)本身是一个二元分类算法，是对感知器算法模型的一种扩展，现在的SVM算法支持线性分类和非线性分类的分类应用，并且也能够直接将SVM应用于回归应用中，同时通过OvR,或者OvO的方式我们也可以将SVM应用在多元分类领域中。在不考虑集成学习算法，不考虑特定的数据集的时候，在分类算法中SVM可以说是特别优秀的。
感知机（SVM支持向量机基础）：
在任意空间中，感知机模型寻找的就是一个超平面，能够把所有的二元类别分割开。感知机模型的前提是：数据是线性可分的。

文章图片

对应m个样本，每个样本n维特征以及一个二元类别输出y,如下：
[ ( x 1 ( 1 ) , x 2 ( 1 ) , . . . , x n ( 1 ) ) , ( x 1 ( 2 ) , x 2 ( 2 ) , . . . , x n ( 2 ) ) , . . . , ( x 1 ( m ) , x 2 ( m ) , . . . , x n ( m ) ) ] \large [(x_1^{(1)},x_2^{(1)},...,x_n^{(1)}),(x_1^{(2)},x_2^{(2)},...,x_n^{(2)}),...,(x_1^{(m)},x_2^{(m)},...,x_n^{(m)})] [(x1(1)?,x2(1)?,...,xn(1)?),(x1(2)?,x2(2)?,...,xn(2)?),...,(x1(m)?,x2(m)?,...,xn(m)?)]
目的是找到一个超平面
w 0 + w 1 x 1 + . . . + w n x n = 0 → w X = 0 \large w_0 + w_1x_1 + ...+w_nx_n = 0 \rightarrow w X = 0 w0?+w1?x1?+...+wn?xn?=0→wX=0
让一个类别的样本满足： w x > 0 \large w x >0 wx>0 ；另外一个类别的满足： w x < 0 \large w x <0 wx<0 (这里就是带一个样本数据进入平面中，根据得到的值进行分类)
因此，感知机模型为**(把正1作为正例，负1作为负例)**：
y = s i g n ( w x ) = { 1ifw x > 0 ? 1ifw x < 0 \LARGE y = sign(w x) = \begin{cases} 1 & \text{ if } w x>0 \\ -1 & \text{ if } w x<0 \end{cases} y=sign(wx)=? ? ??1?1? if wx>0 if wx<0?
感知机分类的损失函数：
期望使分类错误的所有样本到超平面的距离之和最小。

逻辑回归的几何意义，又何尝不是向量空间找到一个超平面，超平面一侧的点计算分数结果为负，另一侧结果分数为正，只不过最后不直接看sign符合，而是根据sigmoid,函数将分数映射到0-1之间通过最大似然来赋予概率意义。

补充一下点到空间的距离公式**(空间距离公式，( x 0 , y 0 x_0,y_0 x0?,y0?) )：
d ( w x 0 ) = ∣ w T x 0 + b ∣ ∣ ∣ w ∣ ∣ 其中， ∣ ∣ w ∣ ∣ = w T w \large d(w x_0) = \frac{|w^Tx_0+b|}{||w||}\\ \large 其中，||w|| = \sqrt{w^Tw} d(wx0?)=∣∣w∣∣∣wTx0?+b∣?其中，∣∣w∣∣=wTw ?
在感知机模型中，对于那些正确分类的点**， y 0 \large y_0 y0? 必然与∣ w T x 0 + b ∣ \large |w^Tx_0+b| ∣wTx0?+b∣ 同号，所以我们可以定义一个距离：几何距离
γ = y 0 ( w T x 0 + b ) ∣ ∣ w ∣ ∣ \LARGE \gamma = \frac{y_0(w^Tx_0+b)}{||w||} γ=∣∣w∣∣y0?(wTx0?+b)?
那么当一个空间固定时， ∣ ∣ w ∣ ∣ \large ||w|| ∣∣w∣∣就已经固定了，我们用一个相对距离来表示点到空间的距离：函数距离
γ ′ = y 0 ( w T x 0 + b ) \LARGE \gamma^{'} = {y_0(w^Tx_0+b)} γ′=y0?(wTx0?+b)
回到上文：期望使分类错误的所有样本到超平面的距离之和最小
那么,我们利用SGD来求解损失函数的过程为：
M S E : L = ? ∑ i = 1 m y ( i ) w T x ( i ) δ L ( w ) δ w = ? ∑ i = 1 m y ( i ) x ( i ) w k + 1 = w k + α y ( i ) x ( i ) \large MSE:L = -\sum_{i=1}^{m}y^{(i)}w^Tx^{(i)}\\ \large \frac{\delta L(w)}{\delta w} = -\sum_{i=1}^{m}y^{(i)}x^{(i)}\\ \large w^{k+1} = w^{k} + \alpha y^{(i)}x^{(i)} MSE:L=?i=1∑m?y(i)wTx(i)δwδL(w)?=?i=1∑m?y(i)x(i)wk+1=wk+αy(i)x(i)
SVM算法思想：
与感知机相同的地方：
SVM也是通过寻找超平面，用于解决二分类问题的分类算法。超平面一侧的点计算分数结果为负是负例，另一侧结果分数为正是正例。与感知机相同，通过sign给出预测标签，正例为+1，负例为-1，模型判别式同样：
y = s i g n ( w x ) = { 1ifw x > 0 ? 1ifw x < 0 \LARGE y = sign(w x) = \begin{cases} 1 & \text{ if } w x>0 \\ -1 & \text{ if } w x<0 \end{cases} y=sign(wx)=? ? ??1?1? if wx>0 if wx<0?
不同的地方：
损失函数与感知机和逻辑回归都不同。
感知机是通过判错点找超平面，逻辑回归是通过最大似然寻找超平面，SVM是通过支持向量寻找超平面。
高级的地方：

文章图片

明显是中间这条分界更好，如何找到这条分界线，这便是SVM要解决的问题。

文章图片

在感知器模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都离超平面尽可能的远，但是实际上离超平面足够远的点基本上都是被正确分类的，所以这个是没有意义的; 反而比较关心那些离超平面很近的点，这些点比较容易分错。

文章图片

文章图片

所以SVM企图找到一个边界（超平面）。在支持向量机中，距离超平面最近的且满足一定条件的几个训练样本点被称为支持向量。SVM最终目的就是这些离超平面的点越远越好。
SVM支持向量机分类：

间隔：数据点到分割超平面的距离称为间隔。
支持向量：离分割超平面最近的那些点叫做支持向量

1.线性可分支持向量机：损失函数：线性可分：在数据集中，如果可以找出一个超平面，将两组数据分开，那么这个数据集叫做线性可分数据。
硬间隔最大化：
需要找到一个超平面

1.能够完美分类正负例
2.距离最近的点越远越好

超平面怎么确定

1. y ^ = s i g n ( w T x + b ) \large \hat{y} = sign(w^Tx+b) y^?=sign(wTx+b)
2. w T x + b = 0 \large w^T x+b = 0 wTx+b=0表示的就是分割超平面
3.只要确认了 w \large w w和 b \large b b，就确定了我们的分割超平面

目标：
能正确分类的平面中，距离越近的点越远越好，即：找到一组最好的w和b固定一个超平面，使这个超平面在能完美区分正负例的基础上，距离最近的点间隔最大
转换为有约束的函数最优化问题就是:
m a x w , b ? γ m i n = y m i n ( w x m i n + b ) ∣ ∣ w ∣ ∣ s . t y i ( w T x i + b ) = γ ( i ) ? γ m i n \LARGE max_{w,b}\: \gamma_{min} = \frac{y_{min}(w x_{min+b})}{||w ||}\\ \LARGE s.t \quad y_i(w^Tx_i + b) = \gamma^{(i)} \geqslant \gamma^{min} maxw,b?γmin?=∣∣w∣∣ymin?(wxmin+b?)?s.tyi?(wTxi?+b)=γ(i)?γmin
简化目标：
我们设定一个阈值：令 γ m i n = 1 \large \gamma^{min} =1 γmin=1,那么最优化问题就简述成：
m a x 1 ?? ∣ ∣ w ∣ ∣ 2 s . t y i ( w T x i + b ) = γ ( i ) ? 1 \LARGE max \frac{1}{\:\:||w||_{2}}\\ \LARGE s.t \quad y_i(w^Tx_i + b) = \gamma^{(i)} \geqslant 1 max∣∣w∣∣2?1?s.tyi?(wTxi?+b)=γ(i)?1

文章图片

等价于：
m a x ? 1 2 ∣ ∣ w ∣ ∣ 2 s . t y i ( w T x i + b ) = γ ( i ) ? 1 \LARGE max \:\frac{1}{2}{||w||_{2}}\\ \LARGE s.t \quad y_i(w^Tx_i + b) = \gamma^{(i)} \geqslant 1 max21?∣∣w∣∣2?s.tyi?(wTxi?+b)=γ(i)?1
可以简化的原因：一组 w , b w,b w,b只能固定一个超平面，一个超平面对应无数个 w , b w,b w,b。那么我们只需要找到一个 w w w，就可以找到这个超平面，因此我们选择最好求的， γ ′ = 1 \gamma^{'}=1 γ′=1
因此损失函数为：
m i n ? 1 2 ∣ ∣ w ∣ ∣ 2 ? s . t y i ( w T x i + b ) = 1 \LARGE min \:\frac{1}{2}||w||_{2}\\ \: \\ \LARGE s.t \quad y_i(w^Tx_i + b) = 1 min21?∣∣w∣∣2?s.tyi?(wTxi?+b)=1
SVM训练原理： SVM的训练原理其实就是对损失函数进行最优化求解（最值求解）的过程。
我们的求解目标就是求得一个分割超平面，也就是求解一组 w , b w,b w,b
下面先讲述一下最优化的数学基础：
带约束条件的最优化问题泛化表示方法：
m i n x ∈ R f ( x ) s . t . c i ≤ 0 , i = 1 , 2 , . . . , k h j ( x ) = 0 , j = 1 , 2 , . . . , l \underset{x\in R}{min}f(x)\\ s.t.\quad c_i\leq0,i = 1,2,...,k\\ h_j(x) =0,j=1,2,...,l x∈Rmin?f(x)s.t.ci?≤0,i=1,2,...,khj?(x)=0,j=1,2,...,l
可以将约束条件表述成k个不等式约束条件，和L个等式约束条件，我们将其命名为原始最优化问题。
拉格朗日函数：
定义某原始最优化问题的拉格朗日函数为：
L ( x , α , β ) = f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ i = 1 l β j h j ( x ) L(x,\alpha,\beta) = f(x)+\sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{i=1}^{l}\beta_jh_j(x) L(x,α,β)=f(x)+i=1∑k?αi?ci?(x)+i=1∑l?βj?hj?(x)
其中 c i c_i ci?是第i个不等式约束函数， b j b_j bj?是第j个等式约束函数。
α i \alpha_i αi?和 β i \beta_i βi?是拉格朗日乘子
拉格朗日函数的特性：
令 θ P ( x ) \theta_P(x) θP?(x)
= m a x α , β ; α i ≥ 0 L ( x , α , β ) =\underset{\alpha,\beta; \alpha_i \geq0}{max}L(x,\alpha,\beta) =α,β; αi?≥0max?L(x,α,β)
若x不满足在原始最优化问题中的条件：
θ P ( x ) = m a x α , β ; α i ≥ 0 [ f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ j = 1 l β j h j ( x ) ] = + ∞ \theta_P(x) =\underset{\alpha,\beta; \alpha_i \geq0}{max}[f(x)+\sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)] = +\infty θP?(x)=α,β; αi?≥0max?[f(x)+i=1∑k?αi?ci?(x)+j=1∑l?βj?hj?(x)]=+∞
若x满足在原始最优化问题中的条件：
θ P ( x ) = f ( x ) \theta_P(x) =f(x) θP?(x)=f(x)
其实也是可以理解的，如果满足约束条件，那么 h j ( x ) = 0 h_j(x)=0 hj?(x)=0。又因为 c i ≤ 0 , α i ≥ 0 c_i\leq0,\alpha_i\geq0 ci?≤0,αi?≥0,所以 ∑ i = 1 k α i c i ( x ) \sum_{i=1}^{k}\alpha_ic_i(x) ∑i=1k?αi?ci?(x)肯定为负。
因此 m a x α , β ; α i ≥ 0 L ( x , α , β ) \underset{\alpha,\beta; \alpha_i \geq0}{max}L(x,\alpha,\beta) α,β; αi?≥0max?L(x,α,β)时， ∑ i = 1 k α i c i ( x ) = 0 \sum_{i=1}^{k}\alpha_ic_i(x)=0 ∑i=1k?αi?ci?(x)=0,所以 θ P ( x ) = f ( x ) \theta_P(x) =f(x) θP?(x)=f(x)
那么回到我们的最优化问题中来：
m i n x ∈ R f ( x ) s . t . c i ≤ 0 , i = 1 , 2 , . . . , k h j ( x ) = 0 , j = 1 , 2 , . . . , l \underset{x\in R}{min}f(x)\\ s.t.\quad c_i\leq0,i = 1,2,...,k\\ h_j(x) =0,j=1,2,...,l x∈Rmin?f(x)s.t.ci?≤0,i=1,2,...,khj?(x)=0,j=1,2,...,l
在x满足条件的情况下
m i n f ( x ) = m i n ? θ P ( x ) = m i n x ? m a x α , β ; α i ≥ 0 L ( x , α , β ) minf(x) = min \:\theta_P(x) = \underset{x}{min} \:\underset{\alpha,\beta; \alpha_i \geq0}{max}L(x,\alpha,\beta) minf(x)=minθP?(x)=xmin?α,β; αi?≥0max?L(x,α,β)
以上三个拥有同样的解！因此我们定义原始问题的最优解为 p ? = m i n x ? θ P ( x ) p^{*} =\underset{x}{min} \:\theta_P(x) p?=xmin?θP?(x)
对偶问题：
当 f ( x ) f(x) f(x)和 c i c_i ci?函数均为凸函数， h j h_j hj?函数为仿射函数时，有可以使用拉格朗日的对偶形式：
m i n x ? m a x α , β ; α i ≥ 0 L ( x , α , β ) = m a x α , β ; α i ≥ 0 m i n x ? L ( x , α , β ) \underset{x}{min} \:\underset{\alpha,\beta; \alpha_i \geq0}{max}L(x,\alpha,\beta) = \underset{\alpha,\beta; \alpha_i \geq0}{max}\underset{x}{min} \:L(x,\alpha,\beta) xmin?α,β; αi?≥0max?L(x,α,β)=α,β; αi?≥0max?xmin?L(x,α,β)
设m a x α , β ; α i ≥ 0 m i n x L ( x , α , β ) \underset{\alpha,\beta; \alpha_i \geq 0 }{max} \underset{x}{min} L(x,\alpha,\beta) α,β; αi?≥0max?xmin?L(x,α,β) 的解为x ? , α ? , β ? x^{*},\alpha^{*},\beta^{*} x?,α?,β?则：
p ? = ( x ? , α ? , β ? ) p^{*} = (x^{*},\alpha^{*},\beta^{*}) p?=(x?,α?,β?)
KKT条件：
a i ? c i ? = 0 , i = 1 , 2 , . . . , k c i ( x ? ) ≤ 0 , i = 1 , 2 , . . . , k α i ? ≥ 0 , i = 1 , 2 , . . . , k h j ( x ? ) = 0 , j = 1 , 2 , . . . , l a^{*}_ic_i^{*} = 0,\quad i = 1,2,...,k\\ c_i(x^{*})\leq0,\quad i = 1,2,...,k\\ \alpha_i^{*} \geq0,\quad i = 1,2,...,k\\ h_j(x^{*}) = 0, \quad j = 1,2,...,l ai??ci??=0,i=1,2,...,kci?(x?)≤0,i=1,2,...,kαi??≥0,i=1,2,...,khj?(x?)=0,j=1,2,...,l
? a 对 a 求梯度 ( 偏导 ) ? x L ( x ? , α ? , β ? ) = 0 ? α L ( x ? , α ? , β ? ) = 0 ? β L ( x ? , α ? , β ? ) = 0 \nabla_a 对a求梯度(偏导) \\\nabla_xL(x^{*},\alpha^{*},\beta^{*}) = 0 \\ \nabla_\alpha L(x^{*},\alpha^{*},\beta^{*}) = 0 \\ \nabla_\beta L(x^{*},\alpha^{*},\beta^{*}) = 0 ?a?对a求梯度(偏导)?x?L(x?,α?,β?)=0?α?L(x?,α?,β?)=0?β?L(x?,α?,β?)=0
先做一个小总结，我们上面讲述了

1.拉格朗日函数
2.对偶问题
3.KKT条件

这三个部分都是我们对SVM的损失函数进行最优化的基础
对于我们的SVM中的原始问题：有约束的最优化问题
m i n ? 1 2 ∣ ∣ w ∣ ∣ 2 s . t y i ( w T x i + b ) = 1 \LARGE min \:\frac{1}{2}||w||_{2}\\ \LARGE s.t \quad y_i(w^Tx_i + b) = 1 min21?∣∣w∣∣2?s.tyi?(wTxi?+b)=1
构建拉格朗日函数**(我们假设一共有m条样本，每个样本有n个特征)**：
L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 2 ? ∑ i = 1 m α i [ y i ( w T x i + b ) ? 1 ] , α i ≥ 0 我们假设 L ( w , b , α ) 的解为 ( w ? , b ? , α ? ) L(w,b,\alpha) = \frac{1}{2}||w||_2^2-\sum_{i=1}^m\alpha_i[y_i(w^Tx_i + b)-1],\alpha_i\geq0\\ 我们假设L(w,b,\alpha)的解为(w^*,b^*,\alpha^*) L(w,b,α)=21?∣∣w∣∣22??i=1∑m?αi?[yi?(wTxi?+b)?1],αi?≥0我们假设L(w,b,α)的解为(w?,b?,α?)
可将原始的有约束的最优化问题，转换成对拉格朗日函数进行无约束的最优化问题（也叫二次规划问题）
首先我们必须明白我们要求解的分割超平面为什么：
W ? T x + b ? = 0 W^{*T}x+b^{*} = 0 W?Tx+b?=0
那么拉格朗日函数到底能求解出什么： w ? , b ? , α ? w^{*},b^{*},\alpha^{*} w?,b?,α?
【支持向量机|从0开始，搞懂SVM支持向量机！】那么这三者之间有没有什么关系呢？
w ? w^{*} w?和 α ? \alpha^{*} α?:
对 L ( w ? , b ? , α ? ) L(w^{*},b^{*},\alpha^{*}) L(w?,b?,α?)求 w ? w^{*} w?偏导,得
w ? = ∑ i = 1 m a i ? y i x i w^{*} = \sum_{i=1}^m a_i^{*}y_ix_i w?=i=1∑m?ai??yi?xi?
b ? b^{*} b?和 α ? \alpha^{*} α?:
对于任意支持向量 ( x s , y s ) (x_s,y_s) (xs?,ys?)，有：
y s ( w T x s + b ) = y s ( ∑ i = 1 m a i y i x i T x s + b ) = 1 y_s(w^Tx_s+b) = y_s(\sum_{i=1}^m a_iy_ix_i^Tx_s+b) = 1 ys?(wTxs?+b)=ys?(i=1∑m?ai?yi?xiT?xs?+b)=1
如何找到支持向量？根据KKT条件 a i ? c i ? = 0 a^{*}_ic_i^{*} = 0 ai??ci??=0有：
a i ? ( y i ( w T x i + b ) ? 1 ) = 0 , a i ? ≥ 0 a_i^{*}(y_i(w^Tx_i+b)-1) = 0,a_i^{*} \geq0 ai??(yi?(wTxi?+b)?1)=0,ai??≥0
那么当 α ? > 0 \alpha^{*} >0 α?>0时，后面一项需要 = 0 =0 =0，也就是
y i ( w T x i + b ) = 1 y_i(w^Tx_i+b) = 1 yi?(wTxi?+b)=1
上面的式子意味着第i条样本 x i x_i xi?恰好在分割超平面的边上，因此 x i x_i xi?就是支持向量。
因此，我们只需要寻找 α i ? > 0 \alpha_i^{*} >0 αi??>0对应的样本即可，这些样本就是支持向量。
求b的过程：求出 α ? \alpha^{*} α?,通过 α ? \alpha^{*} α?找到所有个支持向量带进去求出所有的 b b b,然后求平均，得到 b ? b^{*} b?
因此，我们仅需要求出 α ? \alpha^{*} α?即可！
对于原始函数：
x = ( w , b ) x = (w,b) x=(w,b), α \alpha α存在， β \beta β不存在，因此 L ( x , α , β ) L(x,\alpha,\beta) L(x,α,β) 就写为 L ( w , α , β ) L(w,\alpha,\beta) L(w,α,β)
m i n ? 1 2 ∣ ∣ w ∣ ∣ 2 = m i n ? θ P ( x ) = m i n w , b ? m a x α ; α i ≥ 0 L ( w , α , β ) min\:\frac{1}{2}||w||_{2} = min \:\theta_P(x) = \underset{w,b}{min} \:\underset{\alpha; \alpha_i \geq0}{max}L(w,\alpha,\beta) min21?∣∣w∣∣2?=minθP?(x)=w,bmin?α; αi?≥0max?L(w,α,β)
那么对偶函数为：
m a x α ≥ 0 ? m i n w , b L ( w , b , α ) \underset{\alpha \geq 0}{max} \:\underset{w,b}{min} L(w,b,\alpha) α≥0max?w,bmin?L(w,b,α)
因此我们先对 L L L求极小，在求极大。
求极小：
L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 2 ? ∑ i = 1 m α i [ y i ( w T x i + b ) ? 1 ] , α i ≥ 0 ? L ? w = 0 → w = ∑ i = 1 m a i y i x i ? L ? b = 0 → ∑ i = 1 m a i y i = 0 L(w,b,\alpha) = \frac{1}{2}||w||_2^2-\sum_{i=1}^m\alpha_i[y_i(w^Tx_i + b)-1],\alpha_i\geq0\\ \frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^m a_iy_ix_i \qquad \frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^m a_iy_i=0 L(w,b,α)=21?∣∣w∣∣22??i=1∑m?αi?[yi?(wTxi?+b)?1],αi?≥0?w?L?=0→w=i=1∑m?ai?yi?xi??b?L?=0→i=1∑m?ai?yi?=0
可以看出：我们已经求出了 w w w和 α \alpha α的关系，下一步将 w w w反代回原来的拉格朗日函数中就可以进行第二步求关于 α \alpha α的极大了。
= 1 2 ∣ ∣ w ∣ ∣ 2 2 ? ∑ i = 1 m α i [ y i ( w T x i + b ) ? 1 ] = 1 2 w T w ? ∑ i = 1 m α i y i w T x i ? ∑ i = 1 m α i y i b + ∑ i = 1 m α i = 1 2 w T ∑ i = 1 m α i y i x i ? ∑ i = 1 m α i y i w T x i ? ∑ i = 1 m α i y i b + ∑ i = 1 m α i = ? 1 2 w T ∑ i = 1 m α i y i x i ? ∑ i = 1 m α i y i b + ∑ i = 1 m α i = ? 1 2 w T ∑ i = 1 m α i y i x i ? b ∑ i = 1 m α i y i + ∑ i = 1 m α i = ? 1 2 ( ∑ i = 1 m α i y i x i ) T ∑ i = 1 m α i y i x i ? b ∑ i = 1 m α i y i + ∑ i = 1 m α i 因为 α i , y i 是一个数，并且 α i y i = 0 , 所以 = ? 1 2 ∑ i = 1 m α i y i x i T ∑ i = 1 m α i y i x i + ∑ i = 1 m α i = ? 1 2 ∑ i = 1 m ∑ j = 1 m α i y i x i T α j y j x j + ∑ i = 1 m α i = \frac{1}{2}||w||_2^2-\sum_{i=1}^m\alpha_i[y_i(w^Tx_i + b)-1]\\ \qquad \qquad= \frac{1}{2}w^Tw - \sum_{i=1}^m\alpha_iy_iw^Tx_i -\sum_{i=1}^m\alpha_iy_ib + \sum_{i=1}^m\alpha_i\\ \qquad \qquad \qquad =\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i - \sum_{i=1}^m\alpha_iy_iw^Tx_i -\sum_{i=1}^m\alpha_iy_ib + \sum_{i=1}^m\alpha_i\\ \qquad =-\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i -\sum_{i=1}^m\alpha_iy_ib + \sum_{i=1}^m\alpha_i\\ \qquad =-\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i -b\sum_{i=1}^m\alpha_iy_i + \sum_{i=1}^m\alpha_i\\ \qquad \qquad \qquad =-\frac{1}{2}(\sum_{i=1}^m\alpha_iy_ix_i)^T\sum_{i=1}^m\alpha_iy_ix_i -b\sum_{i=1}^m\alpha_iy_i + \sum_{i=1}^m\alpha_i\\ 因为\alpha_i,y_i是一个数，并且\alpha_iy_i =0,所以\\ = -\frac{1}{2}\sum_{i=1}^m\alpha_iy_ix_i^T\sum_{i=1}^m\alpha_iy_ix_i +\sum_{i=1}^m\alpha_i\\ = -\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j +\sum_{i=1}^m\alpha_i\\ =21?∣∣w∣∣22??i=1∑m?αi?[yi?(wTxi?+b)?1]=21?wTw?i=1∑m?αi?yi?wTxi??i=1∑m?αi?yi?b+i=1∑m?αi?=21?wTi=1∑m?αi?yi?xi??i=1∑m?αi?yi?wTxi??i=1∑m?αi?yi?b+i=1∑m?αi?=?21?wTi=1∑m?αi?yi?xi??i=1∑m?αi?yi?b+i=1∑m?αi?=?21?wTi=1∑m?αi?yi?xi??bi=1∑m?αi?yi?+i=1∑m?αi?=?21?(i=1∑m?αi?yi?xi?)Ti=1∑m?αi?yi?xi??bi=1∑m?αi?yi?+i=1∑m?αi?因为αi?,yi?是一个数，并且αi?yi?=0,所以=?21?i=1∑m?αi?yi?xiT?i=1∑m?αi?yi?xi?+i=1∑m?αi?=?21?i=1∑m?j=1∑m?αi?yi?xiT?αj?yj?xj?+i=1∑m?αi?
通过数学求解，最后得到的求极大形式为：
m a x a ? 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( x i ? x j ) + ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 a i ≥ 0 i = 1 , 2 , . . . , m \underset{a}{max}-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)+\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ a_i \geq 0 \quad i =1,2,...,m amax??21?i=1∑m?j=1∑m?αi?αj?yi?yj?(xi??xj?)+i=1∑m?αi?s.t.i=1∑m?ai?yi?=0ai?≥0i=1,2,...,m
将求极大形式“去掉负号“转换成求极小问题：
m a x a 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( x i ? x j ) ? ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 a i ≥ 0 i = 1 , 2 , . . . , m \underset{a}{max}\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ a_i \geq 0 \quad i =1,2,...,m amax?21?i=1∑m?j=1∑m?αi?αj?yi?yj?(xi??xj?)?i=1∑m?αi?s.t.i=1∑m?ai?yi?=0ai?≥0i=1,2,...,m
只要解决了上述这个问题，SVM的训练问题就完成了！ x i , x j , y i , y j x_i,x_j,y_i,y_j xi?,xj?,yi?,yj?均为已知。我们通常使用SMO算法进行求解，可以求得一组 α ? \alpha^{*} α?使得函数最优化。
训练流程总结： 1.原始目标：求一组 w , b w,b w,b使得分隔最大
2.转换目标：利用拉格朗日函数构建目标函数，并分析得到 α ? 和 b ? 和 w ? \alpha^{*}和b^{*}和w^{*} α?和b?和w?之间的关系。
m a x a 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( x i ? x j ) ? ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 a i ≥ 0 i = 1 , 2 , . . . , m \underset{a}{max}\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ a_i \geq 0 \quad i =1,2,...,m amax?21?i=1∑m?j=1∑m?αi?αj?yi?yj?(xi??xj?)?i=1∑m?αi?s.t.i=1∑m?ai?yi?=0ai?≥0i=1,2,...,m
3.利用SMO算法求得m个 a ? a^{*} a?
4.利用求得的 a ? a^{*} a?得到 w ? w^* w?和 b ? b^{*} b?
w ? = ∑ i = 1 m a i ? y i x i b s ? = y s ? ∑ i = 1 m a i ? y i x i T x s b ? = 1 S ∑ i = 1 S b s ? w^{*} = \sum_{i=1}^m a_i^{*}y_ix_i\\ b_s^* = y_s - \sum_{i=1}^ma_i^{*}y_ix_i^Tx_s\\ b^* = \frac{1}{S}\sum_{i=1}^S b_s^* w?=i=1∑m?ai??yi?xi?bs??=ys??i=1∑m?ai??yi?xiT?xs?b?=S1?i=1∑S?bs??
2.线性支持向量机： **线性不可分：**在数据集中，没法找出一个超平面，能够将两组数据分开，那么这个数据集就叫做线性不可分数据。分割超平面:将数据集分割开来的直线/平面叫做分割超平面。
对于上面的”线性不可分”的情况，往往是由噪声点造成的。
软间隔最大化：
对于之前讲述的“线性可分SVM”，可通过构造超平面令硬间隔最大化，从而求得最好的分隔超平面。
但当存在噪声点，硬间隔不可分的情况，就不能够使用上面的“线性可分SVM”
因此我们提出一个松弛变量 ε i > 0 \varepsilon_i >0 εi?>0(每个数据点自己有一个 ε i \varepsilon_i εi?)
我们将约束条件放松为：
y i ( w ? x i + b ) ≥ 1 ? ε i y_i(w\cdot x_i+b) \geq 1-\varepsilon_i yi?(w?xi?+b)≥1?εi?
这样就至少肯定有足够的 w , b w,b w,b满足条件，但是这也相当于我们没有了约束条件，只要 ε \varepsilon ε无穷大，那么所有的 w , b w,b w,b都满足条件。
ε \varepsilon ε表示异常点嵌入间隔面的深度。因此，我们需要在能选出符合约束条件的最好的 w , b w,b w,b的同时，让嵌入间隔面的总深度越少越好。
损失函数以及最值优化（流程和硬间隔类似）：损失函数：
m i n 1 2 ∣ ∣ w ∣ ∣ 2 2 + C ∑ i = 1 m ε i s . t . y i ( w T x i + b ) ≥ 1 ? ε i ( i = 1 , 2 , . . . , m ) ε i ≥ 0 ( i = 1 , 2 , . . . , m ) C 为自定义超参数 min\quad \frac{1}{2}||w||_2^2 + C\sum_{i=1}^m \varepsilon_i\\ s.t. \quad y_i(w^Tx_i+b)\geq1-\varepsilon_i \quad (i = 1,2,...,m)\\ \varepsilon_i \geq 0 \quad(i = 1,2,...,m)\\ C为自定义超参数 min21?∣∣w∣∣22?+Ci=1∑m?εi?s.t.yi?(wTxi?+b)≥1?εi?(i=1,2,...,m)εi?≥0(i=1,2,...,m)C为自定义超参数
通过拉格朗日函数构造目标函数：
L ( w , b , ε , α , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 2 + C ∑ i = 1 m ε i ? ∑ i = 1 m a i [ y i ( w T x i + b ) ? 1 + ε i ] ? ∑ i = 1 m μ i ε i L(w,b,\varepsilon,\alpha,\mu) =\frac{1}{2}||w||_2^2 + C\sum_{i=1}^m \varepsilon_i - \sum_{i=1}^ma_i[y_i(w^Tx_i+b)-1+\varepsilon_i] - \sum_{i=1}^m\mu_i \varepsilon_i L(w,b,ε,α,μ)=21?∣∣w∣∣22?+Ci=1∑m?εi??i=1∑m?ai?[yi?(wTxi?+b)?1+εi?]?i=1∑m?μi?εi?
其中 α i ≥ 0 ; μ i ≥ 0 \alpha_i \geq0; \mu_i \geq0 αi?≥0; μi?≥0
优化原始问题
m i n w , b , ε ? m a x α i ≥ 0 ; μ i ≥ 0 L ( w , b , ε , α , μ ) \underset{w,b,\varepsilon}{min} \: \underset{\alpha_i \geq0; \mu_i \geq0}{max} L(w,b,\varepsilon,\alpha,\mu) w,b,εmin?αi?≥0; μi?≥0max?L(w,b,ε,α,μ)
对偶问题
m a x α i ≥ 0 ; μ i ≥ 0 ? m i n w , b , ε L ( w , b , ε , α , μ ) \underset{\alpha_i \geq0; \mu_i \geq0}{max} \: \underset{w,b,\varepsilon}{min} L(w,b,\varepsilon,\alpha,\mu) αi?≥0; μi?≥0max?w,b,εmin?L(w,b,ε,α,μ)
依旧是先求极小，再求极大。
? L ? w = 0 → w = ∑ i = 1 m a i x i y i ? L ? b = 0 → ∑ i = 1 m a i y i = 0 ? L ? ε = 0 → C ? α i ? μ i = 0 → C = α i + μ i \frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^ma_ix_iy_i\\ \frac{\partial L}{\partial b} = 0\rightarrow \sum_{i=1}^{m}a_iy_i = 0\\ \frac{\partial L}{\partial \varepsilon}=0 \rightarrow C-\alpha_i - \mu_i = 0 \rightarrow C = \alpha_i+\mu_i ?w?L?=0→w=i=1∑m?ai?xi?yi??b?L?=0→i=1∑m?ai?yi?=0?ε?L?=0→C?αi??μi?=0→C=αi?+μi?
带回拉格朗日函数
= 1 2 ∣ ∣ w ∣ ∣ 2 2 + C ∑ i = 1 m ε i ? ∑ i = 1 m α i [ y i ( w T x i + b ) ? 1 + ε i ] ? ∑ i = 1 m μ i ε i = 1 2 ∣ ∣ w ∣ ∣ 2 2 ? ∑ i = 1 m α i [ y i ( w T x i + b ) ? 1 + ε i ] + ∑ i = 1 m α i ε i = 1 2 ∣ ∣ w ∣ ∣ 2 2 ? ∑ i = 1 m α i [ y i ( w T x i + b ) ? 1 ] 和硬间隔的形式一致 ! = ? 1 2 ∑ i = 1 m ∑ j = 1 m α i y i x i T α j y j x j + ∑ i = 1 m α i =\frac{1}{2}||w||_2^2 + C\sum_{i=1}^m\varepsilon_i - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b)-1+\varepsilon_i]-\sum_{i=1}^m \mu_i\varepsilon_i\\ =\frac{1}{2}||w||_2^2 - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b)-1+\varepsilon_i]+\sum_{i=1}^m \alpha_i\varepsilon_i\\ =\frac{1}{2}||w||_2^2 - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b)-1]\\ \\ 和硬间隔的形式一致!\\ \\ = -\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j +\sum_{i=1}^m\alpha_i\\ =21?∣∣w∣∣22?+Ci=1∑m?εi??i=1∑m?αi?[yi?(wTxi?+b)?1+εi?]?i=1∑m?μi?εi?=21?∣∣w∣∣22??i=1∑m?αi?[yi?(wTxi?+b)?1+εi?]+i=1∑m?αi?εi?=21?∣∣w∣∣22??i=1∑m?αi?[yi?(wTxi?+b)?1]和硬间隔的形式一致!=?21?i=1∑m?j=1∑m?αi?yi?xiT?αj?yj?xj?+i=1∑m?αi?
通过数学求解，最后得到的求极大形式为：
m a x a ? 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( x i ? x j ) + ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 a i ≥ 0 ; μ i ≥ 0 i = 1 , 2 , . . . , m C = α i + μ i \underset{a}{max}-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)+\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ a_i \geq 0; \mu_i \geq 0 \quad i =1,2,...,m\\ C = \alpha_i + \mu_i amax??21?i=1∑m?j=1∑m?αi?αj?yi?yj?(xi??xj?)+i=1∑m?αi?s.t.i=1∑m?ai?yi?=0ai?≥0; μi?≥0i=1,2,...,mC=αi?+μi?
虽然形式一样吗，但是限制条件是不同的！
我们对限制条件再进行优化得到
m i n a 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( x i ? x j ) ? ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 0 ≤ a i ≤ C ; \underset{a}{min} \quad\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ 0\leq a_i \leq C; amin?21?i=1∑m?j=1∑m?αi?αj?yi?yj?(xi??xj?)?i=1∑m?αi?s.t.i=1∑m?ai?yi?=00≤ai?≤C;
与之前相比，只是多了一个约束条件，仍然可以使用SMO进行求解。
结论：
α i = 0 → 该点为分类正确的点 0 < α i < C → 该点为软边界上的点 α i = C → 该点嵌入了软边界内 : 如果此时 ε < 1 , 该点被分类正确 ??? 如果此时 ε = 1 , 该点刚好落在超平面上如果此时 ε > 1 , 该点被分类错误 \alpha_i = 0 \rightarrow 该点为分类正确的点\\ 0 <\alpha_i 1,该点被分类错误\\ αi?=0→该点为分类正确的点0<αi?1,该点被分类错误
训练流程总结： 1.原始目标：求一组 w , b w,b w,b使得分隔最大
2.转换目标：利用拉格朗日函数构建目标函数，并分析得到 α ? 和 b ? 和 w ? \alpha^{*}和b^{*}和w^{*} α?和b?和w?之间的关系。
m i n a 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( x i ? x j ) ? ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 0 ≤ a i ≤ C ; \underset{a}{min} \quad\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ 0\leq a_i \leq C; amin?21?i=1∑m?j=1∑m?αi?αj?yi?yj?(xi??xj?)?i=1∑m?αi?s.t.i=1∑m?ai?yi?=00≤ai?≤C;
3.利用SMO算法求得m个 a ? a^{*} a?
4.利用求得的 a ? a^{*} a?得到 w ? w^* w?和 b ? b^{*} b?
w ? = ∑ i = 1 m a i ? y i x i b s ? = y s ? ∑ i = 1 m a i ? y i x i T x s b ? = 1 S ∑ i = 1 S b s ? w^{*} = \sum_{i=1}^m a_i^{*}y_ix_i\\ b_s^* = y_s - \sum_{i=1}^ma_i^{*}y_ix_i^Tx_s\\ b^* = \frac{1}{S}\sum_{i=1}^S b_s^* w?=i=1∑m?ai??yi?xi?bs??=ys??i=1∑m?ai??yi?xiT?xs?b?=S1?i=1∑S?bs??
3.非线性支持向量机：判别函数的另一种表现形式对于线性SVM来说，判别函数为 y = ( w ? T x + b ? ) y = (w^{*T}x + b^*) y=(w?Tx+b?)
由于 w ? = ∑ i = 1 m a i ? y i x i w^* = \sum_{i=1}^m a_i^{*}y_ix_i w?=∑i=1m?ai??yi?xi?,所有也有下面这种判别函数的形式：
y = ( ∑ i = 1 m a i ? y i ( x i ? x ) ) + b ? y = (\sum_{i=1}^m a_i^{*}y_i(x_i \cdot x)) + b^* y=(i=1∑m?ai??yi?(xi??x))+b?
如何处理线性不可分问题升维是一种处理线性不可分问题的方式，我们通过把原始的X映射到高维空间 φ ( x ) \varphi (x) φ(x)上，比如多项式回归：
可以将2元特征（x1,x2）映射为5元特征 x 1 , x 2 , x 1 ? x 2 , x 1 2 , x 2 2 x_1,x_2,x_1*x_2,x_1^2,x_2^2 x1?,x2?,x1??x2?,x12?,x22?这样在五元空间中有些二元空间里线性不可分的问题就变得线性可分了
将这个思想引入SVM，可以处理线性不可分的问题
但是看似这样的升维方式已经完美解决了线性不可分问题，但是带来了一个新问题，假设就使用多项式回归的方式进行升维：对于二维 x 1 , x 2 x_1,x_2 x1?,x2?升维后的结果是： x 1 , x 2 , x 1 ? x 2 , x 1 2 , x 2 2 x_1,x_2,x_1*x_2,x_1^2,x_2^2 x1?,x2?,x1??x2?,x12?,x22?
假如是三维数据，思维数据等更高维呢? x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1?,x2?,...,xn?
这样会产生维度爆炸的问题。
因此在SVM中引入核函数解决这一问题
升维（核函数）：
在SVM学习过程中
m i n a 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( ? ( x i ) ? ? ( x j ) ) ? ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 0 ≤ a i ≤ C ; \underset{a}{min} \quad\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(\phi(x_i) \cdot \phi(x_j))-\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ 0\leq a_i \leq C; amin?21?i=1∑m?j=1∑m?αi?αj?yi?yj?(?(xi?)??(xj?))?i=1∑m?αi?s.t.i=1∑m?ai?yi?=00≤ai?≤C;
我们只需要求得 ? ( x i ) ? ? ( x j ) \phi(x_i)\cdot\phi(x_j) ?(xi?)??(xj?)的结果，并不需要知道具体的 ? ( x ) \phi(x) ?(x)是什么。于是决定跳过 ? ( x ) \phi(x) ?(x)直接定义 ? ( x i ) ? ? ( x j ) \phi(x_i)\cdot\phi(x_j) ?(xi?)??(xj?)的结果，这样既可以达到升维ied效果，又可以避免维度爆炸的问题。
因此定义核函数：
K ( x , z ) = ? ( x ) ? ? ( z ) K(x,z) = \phi(x)\cdot\phi(z) K(x,z)=?(x)??(z)
此时，目标函数就变为：
m i n a 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j K ( x i , x j ) ? ∑ i = 1 m α i s . t . ∑ i = 1 m a i y i = 0 0 ≤ a i ≤ C ; \underset{a}{min} \quad\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^m \alpha_i\\ s.t. \sum_{i=1}^m a_iy_i = 0\\ 0\leq a_i \leq C; amin?21?i=1∑m?j=1∑m?αi?αj?yi?yj?K(xi?,xj?)?i=1∑m?αi?s.t.i=1∑m?ai?yi?=00≤ai?≤C;
判别函数就为：
y = ( ∑ i = 1 m a i ? y i K ( x i , x ) ) + b ? y = (\sum_{i=1}^m a_i^{*}y_iK(x_i,x)) + b^* y=(i=1∑m?ai??yi?K(xi?,x))+b?
常用的核函数： 1.线性核函数
K ( x , z ) = x ? z K(x,z) = x\cdot z K(x,z)=x?z
2.多项式核函数
K ( x , z ) = ( γ x ? z + r ) d K(x,z) = (\gamma x \cdot z +r)^d K(x,z)=(γx?z+r)d
3.高斯核函数
K ( x , z ) = e x p ( ? γ ∣ ∣ x ? z ∣ ∣ 2 ) K(x,z) = exp(-\gamma ||x-z||^2) K(x,z)=exp(?γ∣∣x?z∣∣2)
4.Sigmoid核函数
K ( x , z ) = t a n h ( γ x ? z + r ) K(x,z) = tanh(\gamma x \cdot z +r) K(x,z)=tanh(γx?z+r)
SVM算法流程总结
1.选择某个核函数以及其对应的超参数
2.选择惩罚系数C
3.利用拉格朗日函数构造最优化问题
4.利用SMO算法求解出一组 α ? \alpha^* α?
5.根据 α ? \alpha^* α?计算 w ? w^* w?
6.根据 α ? \alpha^* α?找出全部支持向量，计算每个支持向量对应的 b s ? b_s^* bs??
7.对 b s ? b_s^* bs??求均值得到最后的 b ? b^* b?
8.学习得到超平面为：
∑ i = 1 m a i ? y i K ( x i , x ) + b ? = 0 \sum_{i=1}^m a_i^{*}y_iK(x_i,x) + b^* = 0 i=1∑m?ai??yi?K(xi?,x)+b?=0
9.最终的判别函数为：
f ( x ) = s i g n ( ∑ i = 1 m a i ? y i K ( x i , x ) + b ? ) f(x) = sign(\sum_{i=1}^m a_i^{*}y_iK(x_i,x) + b^*) f(x)=sign(i=1∑m?ai??yi?K(xi?,x)+b?)
Sklearn中使用SVM
最基本用法：

from sklearn import svm #训练 clf = svm.SVC() clf.fit(X, y) #预测 clf.predict([[2., 2.]]) #获得支持向量 clf.support_vectors_ #支持向量的索引 clf.support_ #获取每个类中支持向量的个数 clf.n_support_

其他用法使用时查就可以了
1.4 支持向量机-scikit-learn中文社区