第七章：支持向量机

线性支持向量机

线性可分或硬间隔支持向量机

前提：训练数据集$\color{red}{线性可分}$线性可分；

学习目标：特征空间的分离超平面：$w\cdot{x}+b=0，w\neq{0}$w⋅x+b=0，w​=0；这个超平面是$\color{red}{唯一的}$唯一的；

学习策略：最大间隔法，等价于下列的最优化问题：

$\color{red}{\displaystyle\min_{w,b}\frac{1}{2}||w||^2}$w,bmin​21​∣∣w∣∣2
$\color{red}{st. {y_i(w\cdot{x_i}+b)-1}\geq{0},i=1,2,...N}$st.yi​(w⋅xi​+b)−1≥0,i=1,2,...N

由于是条件约束的最优化问题，所以自然想到采用$\color{red}{拉格朗日乘数法}$拉格朗日乘数法来求解问题，一般转化为求解$\color{red}{对偶问题}$对偶问题,引入拉格朗日乘子后，原始问题成为下式：

$\color{red}{L(w,b,\alpha)=\frac{1}{2}||w||^2-\displaystyle\sum_{i=1}^{N}{\alpha}_iy_i(w\cdot{x}+b)+\displaystyle\sum_{i=1}^N{\alpha}_i;}$L(w,b,α)=21​∣∣w∣∣2−i=1∑N​αi​yi​(w⋅x+b)+i=1∑N​αi​;,每一个$\alpha$α对应一个样本；

原始问题的对偶问题是极大极小问题：

$\color{red}{\displaystyle\max_{\alpha}\min_{w,b}L(w,b,\alpha);}$αmax​w,bmin​L(w,b,α);

1. 先求解极小化问题：求导、等于0解得：
   $\color{red}{w=\displaystyle\sum_{i=1}^{N}{\alpha}_iy_ix_i}；$w=i=1∑N​αi​yi​xi​；
   $\color{red}{\displaystyle\sum_{i=1}^N{\alpha}_iy_i};$i=1∑N​αi​yi​;

2. 然后使用最优化方法来求解$\alpha$α
   $\color{red}{\displaystyle\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}$αmin​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​
   $\color{red}{s.t. \displaystyle\sum_{i=1}^N{\alpha}_iy_i=0} ;{{\alpha}_i}\geq{0},i=1,2,...N;$s.t.i=1∑N​αi​yi​=0;αi​≥0,i=1,2,...N;

3. 代入1中所求得的表达式，得到 w、b的值，得到分离超平面和决策函数；
   求得的$\alpha$α中，对于那些$\color{red}{{\alpha}_j>0}$αj​>0（这些点被称为$\color{red}{支持向量：即落在间隔边界（y_j(w\cdot{x_j}+b)-1=0）上的那些点，只有这些点才对分离平面的确定起作用，是距离分离超平面最近的实例点}$支持向量：即落在间隔边界（yj​(w⋅xj​+b)−1=0）上的那些点，只有这些点才对分离平面的确定起作用，是距离分离超平面最近的实例点）;可借此求得b的值：
   $\color{red}{b=y_j-\displaystyle\sum_{i=1}^N{\alpha}_iyi(x_i\cdot{x_j})}；$b=yj​−i=1∑N​αi​yi(xi​⋅xj​)；

超平面对于某个训练集的各个间隔定义如下：

• 函数间隔：$\color{red}{\hat\gamma=\displaystyle\min_{i=1,...N}{y_i}(w\cdot{x_i}+b)}$γ^​=i=1,...Nmin​yi​(w⋅xi​+b)，（所有实例点中最小的函数间隔即为该分离超平面对于训练集的函数间隔）函数间隔可以表示$\color{red}{分类预测的正确性及确信度}$分类预测的正确性及确信度，但由于其量级随着w、b的比例变化而变化，所以引入几何间隔的概念；
• 几何间隔：$\color{red}{\gamma=\frac{\hat\gamma}{||w||}}$γ=∣∣w∣∣γ^​​，这时，w、b比例变化时，几何间隔是$\color{red}{不变的}$不变的；

线性不可分或软件隔支持向量机

对于有些线性不可分的数据集来说，也可以采用类似线性可分的方法来求得分离超平面；方法是为每个样本点引进一个松弛变量 $\color{red}{\epsilon}_i\geq0$ϵi​≥0；

约束条件变为：$\color{red}{y_i(w\cdot{x}+b)\geq{1-\epsilon_i}}$yi​(w⋅x+b)≥1−ϵi​;

原始问题变为：

$\color{red}{\displaystyle\min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^N\epsilon_i}$w,bmin​21​∣∣w∣∣2+Ci=1∑N​ϵi​
$\color{red}{st. {y_i(w\cdot{x_i}+b)}\geq{1-\epsilon_i},i=1,2,...N}$st.yi​(w⋅xi​+b)≥1−ϵi​,i=1,2,...N
$\color{red}{\epsilon_i\geq0,i=1,2,...,,N}$ϵi​≥0,i=1,2,...,,N

线性不可分的线性支持向量机知识多了一个$\color{red}{惩罚系数:C}$惩罚系数:C,目标函数有两层含义：使间隔尽量大，同时使误分类点个数尽可能少

对偶问题为：

$\color{red}{\displaystyle\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}$αmin​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​
$\color{red}{s.t. \displaystyle\sum_{i=1}^N{\alpha}_iy_i=0} ;{0\leq{\alpha}_i}\leq{C},i=1,2,...N;$s.t.i=1∑N​αi​yi​=0;0≤αi​≤C,i=1,2,...N;

求得了对应的$\alpha$α之后，对于那些$0<{\alpha}_j<{C}$0<αj​<C的那些实例点，根据KTT条件，与线性可分SVM一致，可求得w、b值：

$\color{red}{w=\displaystyle\sum_{i=1}^{N}{\alpha}_iy_ix_i}；$w=i=1∑N​αi​yi​xi​；

$\color{red}{b=y_j-\displaystyle\sum_{i=1}^N{\alpha}_iyi(x_i\cdot{x_j})}；$b=yj​−i=1∑N​αi​yi(xi​⋅xj​)；

线性SVM的$\color{red}{分类决策函数}$分类决策函数都是：

$\color{red}{f(x)=sign(w\cdot{x}+b)}$f(x)=sign(w⋅x+b)

根据最后学习到的w、b、$\alpha$α,可以求得松弛变量的值，分一下几种情况：

• 0<$\alpha_i$αi​<C；这一类实例点全部落在间隔边界上，即=0；$
• $\alpha=C$α=C；
  1. 若0<$\epsilon_i$ϵi​<1；分类正确，点落在分割面和分割边界之间；
  2. 若$\epsilon_i$ϵi​=1,点落在分离超平面上；
  3. $\epsilon_i$ϵi​>1,误分类点；

合页损失函数

线性支持向量机还有另一种解释，就是最小化以下损失函数：

$\color{red}{\displaystyle\min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot{x_i}+b)]_++\lambda||w||^2}，\lambda=\frac{1}{2C};$w,bmin​i=1∑N​[1−yi​(w⋅xi​+b)]+​+λ∣∣w∣∣2，λ=2C1​;

上式第一项$\color{red}{L(y(w\cdot{x}+b)=[(1-y_(w\cdot{x}+b)]_+}$L(y(w⋅x+b)=[(1−y(​w⋅x+b)]+​即为合页损失函数；下标+的意义为【】内的数>0,则取值为本身，否则取为0；就是说$\color{red}{样本点被正确分类时，代价为0，否则损失就是1-y_i(w\cdot{x_i}),也就是\epsilon_i（到间隔边界的函数距离）}$样本点被正确分类时，代价为0，否则损失就是1−yi​(w⋅xi​),也就是ϵi​（到间隔边界的函数距离）

合页损失函数翻译了SVM$\color{red}{不仅要正确分类，而且确信度足够高（函数间隔大于等于最大间隔）}$不仅要正确分类，而且确信度足够高（函数间隔大于等于最大间隔）的时候损失才为0；

合页函数图：

图中虚线表示的是感知机的损失函数：

非线性支持向量机

非线性向量机就是采用一定的技巧$\color{red}{将输入空间映射到某一特征空间，让原本的非线性分类问题转为线性分类问题}$将输入空间映射到某一特征空间，让原本的非线性分类问题转为线性分类问题，这样，就可以直接使用线性SVM学习方法来学习分类模型，核技巧就是这样的方法；

核函数和映射函数

$K(x,z)=\phi(x)\cdot{\phi(z)},\phi(x)就是映射函数$K(x,z)=ϕ(x)⋅ϕ(z),ϕ(x)就是映射函数

这样就可以把对偶问题中的向量积$x_i\cdot{x_j}$xi​⋅xj​用核函数K(x,z)代替，

核函数

最小序列最优化方法（SMO:sequential minimal optimization）

SMO算法的思想就是：对于最终求得的$\alpha$α都会满足KTT条件，所以，当出现不满足KTT条件的点时（选取两个这样的变量，其中一个为自由变量），就可以对目标函数进行优化，从而更新$\alpha$α的值，把原本的复杂问题转变为一个$\color{red}{两个变量的优化}$两个变量的优化问题，而这种子问题又可以通过解析方法求解，大大提高了运算速度；

求解两个变量二次规划的解析方法

将除去两个变量外的其余$\alpha$α当做常数，然后将对偶问题转化为子问题对选取的两个变量进行求解，采用常规单变量求导即可得到沿约束方向的极值，根据约束条件可以求得另一个变量的更新值：

只考虑约束条件：

$a1y1+a2y2=T(常数）$a1y1+a2y2=T(常数），不考虑 $0\leq\alpha\leq{C};$0≤α≤C;求得：

$a_2^{new,unc} =a_2^{old}+\frac{y2(E_2-E_1)}{\eta}$a2new,unc​=a2old​+ηy2(E2​−E1​)​；

其中$\eta=K_{11}+K_{22}-2K_{12}$η=K11​+K22​−2K12​，E为对实例的预测值与实际函数值之差：

$E_i=\displaystyle\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b-y_i,i=1,2;$Ei​=j=1∑N​αj​yj​K(xj​,xi​)+b−yi​,i=1,2;

结合$0\leq\alpha\leq{C};$0≤α≤C;进一步求得：
$a_2^{new}= \begin{cases} H, &a_2^{new,unc} >H\\ a_2^{new,unc} ,& L\leq{a_2^{new,unc}}\leq{H} \\L,&a_2^{new,unc}\leq{L}\end{cases}$a2new​=⎩⎪⎨⎪⎧​H,a2new,unc​,L,​a2new,unc​>HL≤a2new,unc​≤Ha2new,unc​≤L​

$1.y_1\neq{y_2},L=max(0,a_2^{old}-a_1^{old}),H=min(C,C+a_2^{old}-a_1^{old});$1.y1​​=y2​,L=max(0,a2old​−a1old​),H=min(C,C+a2old​−a1old​);
$2.y_1=y_2,L=max(0,a_2^{old}+a_1^{old}-C),H=min(C,a_2^{old}+a_1^{old});$2.y1​=y2​,L=max(0,a2old​+a1old​−C),H=min(C,a2old​+a1old​);

$a_1^{new}=a_1^{old}+y1y2(a_2^{old}-a_2^{new})$a1new​=a1old​+y1y2(a2old​−a2new​);

选择变量的启发式方法（？）

选择两个变量，其中至少有一个是违背KTT条件的（不然表示优化完成）；

外层循环（选择第一个变量）：
遍历满足条件 0<$\alpha_i<C$αi​<C的样本点，这些点是在间隔边界上的支持向量；若都满足KTT，则遍历全部训练集；

内层循环（选择第二个变量）：
考虑使得$|E1-E2|$∣E1−E2∣最大的那个样本点，这样可以加快算法速度；如果不能找到使目标函数有足够下降的点，采用启发式规则选择第二个变量：遍历在间隔边界上的支持向量点，直到目标函数有足够的下降，否则，遍历整个训练集，若仍没有找到，放弃外循环选择的第一个变量，重新开始外循环、内循环。

b和E的更新
在求得了新的$\alpha$α之后，需要更新相应的b、E值；

疑问：每一个样本都计算E的话，对于那些距离分离面远的点，E岂不是很大？