一些概念

  支持向量机（Support Vector Machine，简称SVM）是一种广受欢迎的监督学习算法，主要用于分类和回归分析。在分类问题中，SVM的主要目标是在训练数据中找到一个超平面。这个超平面不仅能够准确地区分不同类别的样本，而且还能最大化不同类别样本到该超平面的最小距离，这个距离被称为“间隔”（margin）。

  超平面是一个重要的数学概念。在n维空间中，超平面是一个维度为n-1的子空间，它将空间划分成两个半空间。
  超平面可以被看作是平面概念的推广，就像在二维空间中，直线是一维的超平面；在三维空间中，平面是二维的超平面。
  在数学上，n维空间中的超平面可以通过一个线性方程来定义，即：

$w_1{x}_1+w_2{x}_2+...+w_n{x}_n+b=0$
用向量写作 ${\vec{w}}^T\vec{x}+b=0$

  超平面的法向量是指与超平面垂直的向量，能够指示超平面的方向。

  点到超平面或超平面到超平面的间隔即它们间的距离。公式为：

$\overrightarrow{x_0}=(x_{01},x_{02},...x_{0n})$ (点）
$||\vec{w}||=\sqrt{{\sum }_{i=1}^n{w}_i^2}$ （模）

$d=\frac{|{\vec{w}}^T\overrightarrow{x_0}+b|}{||\vec{w}||}$ （间隔）

  正超平面是离决策边界最近的一个超平面，位于决策边界的正类别一侧。数学定义为：

${\vec{w}}^T\vec{x}+b=1$

  负超平面是离决策边界最近的一个超平面，位于决策边界的负类别一侧。数学定义为：

${\vec{w}}^T\vec{x}+b=-1$

支持向量机SVM

  对于一个训练集，有时能找到很多有效的决策边界来实现分类任务，但不同的决策边界在新的测试集中的表现各不相同。而SVM采用最大化间隔的标准来挑选出一种较优的决策边界，可以有效减少过拟合。

  对于一个决策边界，我们可以将它视作这个数据集维度下的超平面$({\vec{w}}^T,b)={\vec{w}}^T\vec{x}+b=0$。假设该超平面已经能正确将训练样本分类，即满足两类样本$-1,+1$已经分到了正负超平面的两侧：

若$y_i=+1$，那么 ${\vec{w}}^T\vec{x}+b\ge +1$
若$y_i=-1$，那么 ${\vec{w}}^T\vec{x}+b\le -1$

  如右图，距离超平面最近的几个训练样本点使等号成立，它们被称为“支持向量”（support vector）。显然，正负超平面的间隔等于两个异类支持向量到超平面$({\vec{w}}^T,b)$的间隔之和，记作$\gamma$，有：

$\gamma =\frac{2}{||\vec{w}||}$

  显然，正负超平面离地越远，不同类别的数据的差异就体现地越明显，于是，我们希望找到具有“最大间隔”的划分超平面，即找到这样的参数$\vec{w}$和$b$，使得：

${\min }_{\vec{w},b}||\vec{w}||$
 
s.t. $y_i({\vec{w}}^T\overrightarrow{x_i}+b)\ge 1,i=1,2,...,m$
 
PS: s.t. 意思是 subject to， 即受限于…， 满足…
PS: m 表示数据组数

  这就是SVM要解决的问题。

凸二次规划求解

一些定义

 

  简单理解：海森矩阵是将函数在某一点处的所有二阶偏导数组织成一个矩阵的形式，这个矩阵可以提供函数在该点局部行为的详细信息。海森矩阵也记作$H={▽}^{2}f(x)$
 

 
  我们有这样的定理：若函数在任一点的海森矩阵是半正定的，那么这个函数是凸函数。

凸二次规划问题

  

转化原问题为凸二次规划问题

  这里我们用拉格朗日乘子法。

  （1） 构建拉格朗日函数：令$\vec{\alpha }=({\alpha }_1,{\alpha }_2,...{\alpha }_m)$是与不等式约束向对应的拉格朗日乘子向量。则拉格朗日函数$L(\vec{w},b,\vec{\alpha })$定义为：

$L(\vec{w},b,\vec{\alpha })=\frac{1}{2}||\vec{w}|{|}^2-{\sum }_{i=1}^m{\alpha }_i[y_i({\vec{w}}^T{\vec{x}}^i+b)-1]$

  （2）定义KKT条件。举个例子，一个二次函数的最小值满足$△=0$。对于这个复杂的命题，也可以有类似的想法。当函数的某个点满足KKT条件，则这个点就是全局最优解（凸函数的局部最优解即全局最优点）。KKT条件包括：
 
    （i）驻点条件（Stationarity）：表示在最优解处，对于变量 $\vec{w}$和$b$拉格朗日函数的梯度必须为零，即：

${▽}_{\vec{w}}L(\vec{w},b,\vec{\alpha })=\vec{w}-{\sum }_{i=1}^m{\alpha }_i{y}_i{\vec{x}}_i=0$
${▽}_{b}L(\vec{w},b,\vec{\alpha })=-{\sum }_{i=1}^m{\alpha }_i{y}_i=0$

    （ii）原问题可行性（Primal Feasibility）：约束条件必须满足。即：

$y_i({\vec{w}}^T\overrightarrow{x_i}+b)\ge 1$   $(i=1,2,...,m)$

    （iii）对偶可行性（Dual Feasibility）：拉格朗日乘子必须非负。即：

${\alpha }_i\ge 0$,   $(i=1,...,m)$

     （iv）互补松弛性（Complementary Slackness）：先定义一个约束条件是活动的（active），当在某个点处该约束刚好达到其允许的最大或最小值（即取等）。而在拉格朗日乘子法中，这些活动的约束条件对应的拉格朗日乘子通常为非零，体现这个约束的重要性；对应的，非活动的（inactive）约束条件对应的拉格朗日乘子通常为零，表明它们在当前解中是冗余的或非限制性的。
     所以，互补松弛性表述为：

${\alpha }_i[y_i({\vec{w}}^T{\vec{x}}^i+b)-1]=0$,   $(i=1,...,m)$
 
${\alpha }_i$ 和 $y_i({\vec{w}}^T{\vec{x}}^i+b)-1$至少有一个为0

 
    以上四个条件描述了最优解应该满足的性质，其中从驻点条件中，我们可以解出$\vec{w}$和$b$关于$\vec{\alpha }$的关系式：

$\vec{w}={\sum }_{i=1}^m{\alpha }_i{y}_i{\vec{x}}_i$

    代入$L$后得到新的函数$g(\vec{\alpha })$：

$g(\vec{\alpha })={\sum }_{i=1}^m{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^m{\sum }_{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{\vec{x}}_i^T\overrightarrow{x_j}$

    当最小化$||w|{|}^2$和最大化$g(\vec{\alpha })$这两个命题同时满足了KKT条件，它们解的数值相等。称前者为原命题，后者为对偶命题。于是目标变成求解以下问题：

    ${\max }_{\vec{\alpha }}g(\vec{\alpha })$
 
$s.t.$  ${\alpha }_i\ge 0$,   $(i=1,...,m)$
 
   ${\sum }_{i=1}^m{\alpha }_i{y}_i=0$

    对比式子可以发现这正是一个二次规划问题。解出$\alpha$后即可由$\vec{w}={\sum }_{i=1}^m{\alpha }_i{y}_i{\vec{x}}_i$求出最初想要的$\vec{w}$
 
    注意，条件$y_i({\vec{w}}^T\overrightarrow{x_i}+b)\ge 1$   $(i=1,2,...,m)$会在后续求解中自动满足。

解决

  我们可以用通用的方法解决二次规划问题，但是该问题的规模正比于训练样本数，会造成很大的开销。所以，针对这个特定的问题的特性，人们提出了一些高效的算法。在《机器学习》中提到的是SMO算法。

步骤

  （1）初始化。
     $\cdot$ 选择一个初始的$\alpha$值，通常可以随机选取或置为0。
 
  （2）选择两个变量。
     $\cdot$ 选择第一个变量${\alpha }_1$。通常，从违反KKT条件最严重的$\alpha$开始，也可以随机选择。
     $\cdot$ 选择第二个优化变量${\alpha }_2$。这个选择不是随机的，而是基于启发式规则，以加速收敛。常见的策略是选择能够使目标函数最大下降的${\alpha }_2$，也可以说选取的两个变量对应的样本之间的间隔最大。
      SMO算法每次选择两个变量，固定其他变量，这样有利于减少运算的时间和空间（主要体现为避免了大矩阵之间的运算）。
 
  （3）计算边界
     $\cdot$ 确定${\alpha }_1$和${\alpha }_2$的上下界$L$和$H$。记${\alpha }_1$和${\alpha }_2$对应的样本点为$({\vec{x}}_1,y_1)$和$({\vec{x}}_2,y_2)$。
       $\cdot$ 当 $y_1\ne y_2$，${\alpha }_1$和${\alpha }_2$将朝着相反的方向移动，此时上下界$L$和$H$应该这样计算：

 $L=\max (0,{\alpha }_2-{\alpha }_1)$
 $H=\min (C,C+{\alpha }_2-{\alpha }_1)$
 
 $C$是SVM中的惩罚参数，控制了错误分类的惩罚强度。在SVM的优化问题中，${\alpha }_i$的值必须在$0$和$C$之间，这反映了KKT条件中的不等式约束。
 这样定义的原因是确保${\alpha }_2$的更新值不会小到负数，同时也不会超过$C$

       $\cdot$ 当 $y_1=y_2$，${\alpha }_1$和${\alpha }_2$将朝着相反的方向移动，此时上下界$L$和$H$应该这样计算：

 $L=\max (0,{\alpha }_1+{\alpha }_2-C)$
 $H=\min (C,{\alpha }_1+{\alpha }_2)$
 
 这里，下界确保了${\alpha }_2$的值不会低于0（考虑到${\alpha }_1$和${\alpha }_2$的增加或减少是同步的），而上界则限制了${\alpha }_2$的值不会超过$C$。

  （4）更新${\alpha }_2$。 在合法区间内找到最优的更新值，若不使用核函数，会用以下式子：

它们的实际类别标签与当前模型预测的结果之间的差距
$E_1=g({\vec{x}}_1)-y_1$
$E_2=g({\vec{x}}_2)-y_2$
 
${\alpha }_2^{{}^{\prime }}={\alpha }_2+\frac{y_2(E_1-E_2)}{k_{11}+k_{22}-2k_{12}}$
其中 $k_{ij}={\vec{x}}_i\cdot {\vec{x}}_j$

    然后调整，如果新的${\alpha }_2$超出了$L$或$H$，则裁剪成$L$或$H$。

  （5）更新${\alpha }_1$。保持${\sum }_{i=1}^m{\alpha }_i{y}_i=0$即可。

  （6）更新$b$。懒得敲公式了

  以上是GPT给出的方法，不知道对不对，感觉说的很有道理。《机器学习》中则利用支持向量的性质给出更新式：

注意到对于所有支持向量$({\vec{x}}_s,y_s)$，满足：
$y_i({\vec{w}}^T\overrightarrow{x_i}+b)=1$，  即：
$y_i({\sum }_{i=1}^m{\alpha }_i{y}_i{\vec{x}}_i^T\overrightarrow{x_s}+b)=1$
 
为了模型更好的性能，采用所有的支持向量并取均值，得：
$b=\frac{1}{|S|}{\sum }_{s\in S}^{}(\frac{1}{y_s}-{\sum }_{i=1}^m{\alpha }_i{y}_i{\vec{x}}_i^T\overrightarrow{x_s})$

  （7）迭代，如果所有$\alpha$的更新都小于给定的阈值，或者达到最大迭代次数，算法终止。否则，返回步骤2。

后话

  这是支持向量机的基础部分，后续还有核函数、正则化、软间隔、回归等变化。这一块内容真是目前学到的最难的了，到处查资料，以后可能会先出一些简单的内容再来攻克SVM的后续。