大名鼎鼎的SVM（支持向量机）算法，拥有较为坚实的数学基础，在很长一段时间内都是最佳分类器的代名词。本文以《统计学习方法》中支持向量机为主要学习资料，同时参考了vapnik发表的《support-vector networks》论文，力图较为清晰的描述SVM的优化目标（引出、推导）及优化方法。

本文的内容包括：

1. 最大间隔分类器的提出

2. SVM的优化目标

   1. 线性可分情况下的优化目标

   2. 线性不可分下优化目标

   3. 从合页损失的角度看优化目标

   4. 确认最终优化目标

3. 引入核方法

4. 优化方法（SMO）

   1. SMO思想

   2. 具体推导

   3. SMO总结

开始编辑时间2015-12-31 ， 预期编辑完成时间 2016-1-18 (有大量考试)

###最大间隔分类器的提出

读Support-Vector Networks的Introduction部分，真的是一种享受。本学期刚刚学过了模式识别，对机器学习曾经的一些方法及发展有些许了解。而这个部分对于过去机器学习或者说模式识别方法的回顾，与自己从课程中学习到的知识产生了呼应。这种感觉实在美妙，以致于一口气读完简介兴致大涨，想着明天再接再厉抛弃中文资料直接读论文。当然看到第二节的推导时就懵了…

SVM包含两大核心，一个是最优线性分类器（或者说最大间隔分类器），另一个是核函数（核技巧） 。

这里首先要讲的就是最优线性分类器。而最优线性分类器，本身也有一段历史可循。根据论文描述，1936年时R.A.Fisher提出了最早的模式识别方法，即假定两个类别分别服从参数不同的高斯分布，然后对这两个分布，建立贝叶斯决策平面。所谓贝叶斯决策平面，通俗地来说，就是给定实例情况下，比较两个分布的后验概率大小：

\(P_{x \sim w_1}(w_1 | x) > P_{x \sim w_2 }( w_2 | x )\) 其中$w_1$ , $w_2$ 是两个类别。

一般把上面的式子取对数，然后移项过来，对于（多元）高斯分布 $P = \frac{1}{(2\Pi)^{N/2}|\Sigma|^{1/2}}\exp{\big (-\frac{1}{2}(x-\mu)^T \Sigma^{-1} (x - \mu) \big )}$ ，就是下面的式子：

其中$\mu_1$,$\Sigma_1$,$\mu_2$ , $\Sigma_2$分别是两个高斯分布的均值和协方差。

上述（应该）是一个关于$X$二次型函数。特别的，如果两个高斯分布的协方差矩阵都是对角阵、或者两个高斯分布协方差矩阵相同，那么上式就可以化为关于输入实例$X$的线性形式（忘了怎么推了）。而且，在论文中还提到，对于其他协方差任意的情况，可以近似用$\Sigma_1$,$\Sigma_2$的线性插值来表示一个$\Sigma$，然后转换为相同协方差的情况，也可以近似用线性来表示。而这种线性表示，就是我们后来直接使用的线性分类分类器，即$y = w x + b$，并由此引出了线性分类面、线性超平面的概念。

上述”关于$X$的二次型函数“，”关于$X$的线性函数“值得商榷，因为如果是参数估计，那么$X$是已知的，而通常将均值$\mu$作为参数。当然，$x$与$\mu$的幂次数始终是相同的（写在一个括号里的，作为一个整体）。

以上，通过非数学证明的方式，说明了线性分类器的产生。一个常用的基础线性分类器就是感知器。根据模式识别课程上的内容，感知器主要是说这种线性分类器的损失定义为所有错分点到分离面的距离和。感知器的学习算法通常使用基于错误驱动的Online更新算法，以我的观点来看，就是SGD方法。

感知器在线性可分时，学习到的分类面大部分情况下不是最优的。因为只要一旦得到可以区分所有点的分类面，感知器更新就彻底停止了。

线性不可分时，实际的做法是记录错误达到最小时的权值，然后发现错误增大或超过最大迭代次数时退出学习，将有最小错误的权值作为最终的参数。理论上，则是说其不能处理这种情况，可以使用LMSE方法，即以均方差最小为目标，保证任意数据集下都能收敛。不过这个似乎并不怎么常见。

基于直觉，如果我们在样本中找到最优的分类面，即这个分类面保证在两类别的中间、使得间隔最大，那么这样的分类面将优于一个任意的、仅能区分当前数据集的分类面。其泛化能力将更高。

由此便提出了最优线性分类面，即最大间隔分类面。

###SVM的优化目标

1. 线性可分情况下的优化目标

   最大间隔优化目标

   设超平面为$w x + b = 0$，SVM将建立两个分隔超平面，分别为

   \[wx + b = 1 \\ wx + b = -1\]

   此时原始的$wx + b = 0$可以称为判决(超平)面。

   分隔超平面 似乎并不是标准统一的称呼。因为一般的线性分类器，只有判决超平面，即$wx + b = 0$ ，有时就也被称为分隔超平面。在本文中，由于判决超平面仅在判断（预测）时有用，在模型建立、参数学习时都是以$wx + b = \pm 1$ 为分离面的，所以本文中均用分隔超平面来指代$wx + b = \pm 1$ ， 用判决超平面来指代wx + b = 0 。

   分类器通过改变$w$和$b$的大小，改变这三条线的方向以及间隔距离。当达到理想情况时，在数据集线性可分的情况下，两类别相互靠近的一侧的数据点恰好分别落在两个分隔超平面上，此时两类别中的点到判决超平面的距离和最大。此刻即是线性可分情况下的最优解。

   以上是思想说明，下面形式化的定义这个过程。

   一些定理：

   1. 平面$wx + b = 0$的法向量是$w$

   2. 任意点$x_0$到平面$wx + b = 0$的距离为$\frac{w x_0 + b}{|w|}$

   证明，可查看点到平面的距离公式

   定义1

   训练集中，正例点（$y=1$）满足： $wx + b \ge 1$

   负例点($y=-1$)满足: $wx + b \le -1$

   这是最大间隔分类器的定义，不必纠结。

   定义2

   正例中距离超平面的最小距离为 $d_{pos_min} = \frac{wx_i + b}{|w|} $ , 其中 $y_i=+1 , wx_i + b \ge 1$

   负例中距离超平面的最小距离为 $d_{neg_min} = \frac{wx_j + b}{|w|} $ , 其中 $y_j=+1 , wx_j + b \le -1$

   则两点集到超平面的最小距离和满足：

   \[\begin{split} d &= d_{pos\_min} + d_{neg\_min} \\ &= \frac{wx_i + b}{|w|} - \frac{wx_j + b}{|w|} \\ &\ge \frac{2}{|w|} \end{split}\]

   由此我们最大化$\frac{2}{|w|}$即可。

   此时需要满足的条件

   $ wx_i + b \ge 1 , y_i = + 1 $

   $ wx_j + b \le -1 , y_j= -1 $

   可以合并到一起，有$y_i (w x_i + b) \ge 1$

   又最大化间隔$\frac{2}{|w|}$，等价最小化$\frac{1}{2} |w|^2$

   为什么是平方？ 因为$w$是向量,其二范数是根号形式，取平方当然比根式更简单；

   为什么系数为$\frac{1}{2}$ ? 因为平方求导有系数2，恰与$\frac{1}{2}$消去！

   综合以上结论，有最大间隔分类器在线性可分数据集下的优化目标：

   \[\begin{split} &min_{w,b} ~~~&\frac{1}{2} |w|^2 \\ &s.t. & y_i(wx_i + b) \ge 1 , i=1,2,\cdots , N \end{split}\]

   记住这个形式，这是在线性可分数据集下由最大间隔直接推出的优化目标形式。

   其是不可计算的，接下来我们就将对其做变换，使其变为可计算的优化目标。

   ”不可计算“并不能确定。

   变化1-约束优化变为无约束优化问题

   首先针对约束最优化问题，引入拉格朗日乘子，变为无约束问题。

   先将约束化为标准形式(小于等于、右端项为0)：

   \[\begin{split} &min_{w,b} ~~~&\frac{1}{2} |w|^2 \\ &s.t. & -( y_i(wx_i + b) -1) \le 0 , i=1,2,\cdots , N \end{split}\]

   引入Lagrange multiplier :

   \[L(w,b,\alpha) = \frac{1}{2}|w|^2 - \sum_{i=1}^{N}\alpha_i y_i(wx_i + b) + \sum_{i=1}^N \alpha_i\]

   定义等价的无约束问题：

   \[\begin{split} &{转为无约束优化}{\Longrightarrow}\\ &min_{w,b} ~max_{\alpha} ~ L(w,b,\alpha) ~,\\ &其中~L(w,b,\alpha) = \frac{1}{2}|w|^2 - \sum_{i=1}^{N}\alpha_i y_i(wx_i + b) + \sum_{i=1}^N \alpha_i \end{split}\]

   注意极小极大，这是有约束优化与无约束优化等价的必备条件。

   变化2-拉格朗日原始问题变为对偶问题

   定理：

   对凸规划问题，原始问题的最优解与对偶问题的最优解相同。

   目标函数($\frac{1}{2} |w|^2$)是凸函数，将原始问题转为对偶问题。

   为何要转为对偶？ 1. 计算更简单（书上所言，不知道为何） 2. 看原始问题，需要先求内层的$max_{\alpha} ~ L(w,b,\alpha)$ , 变量是$\alpha$，一般对其求导并令其为0，这样只能得到一个等式：$-y_i (wx_i + b) + 1 = 0 , i = 1,2,\cdots,N$，没办法再继续求外层的$min_{w,b}$了 ？

   转为对偶问题：

   \[\begin{split} min_{w,b} ~max_{\alpha} ~ L(w,b,\alpha) \Longrightarrow max_{\alpha}~min_{w,b} ~ L(w,b,\alpha) \end{split}\]

   以下就变为对该对偶问题求解！

   求解对偶问题内层$min_{w,b} ~ L(w,b,\alpha)$

   不用多想，直接对$L(w,b,\alpha)$求关于变量$w,b$的导数，再令其为0 。结果为：

   \[\begin{split} &w = \sum_{i=1}^N {\alpha_i y_i x_i} \\ &\sum_{i=1}^N \alpha_i y_i = 0 \longrightarrow 对b求导产生新的约束！ \end{split}\]

   这里就出现了导致SVM复杂的问题：求解内层问题后，又出现了一个约束！前面讲到的最大熵，求完内层问题后就可以直接利用无约束方法（如BFGS）求解了。

   对最大熵求解的论述不敢保证，因为没有实现过。

   将内层的结果带入

   将上面内层求解的结果($w , b$)带入到拉格朗日函数$L(w,b,\alpha)$中，可以消去$w,b$，得到仅关于$\alpha$的拉格朗日函数：

   \[L(\alpha) = - \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j~(x_ix_j) + \sum_{i=1}^N\]

   接下来就是求解外层，即$max_{\alpha} L(\alpha)$。由于又是带有约束的优化问题，所以按照优化问题的标准格式，将$\max$变为$\min$问题。

   很简单，取负即可： $min_{\alpha} - L(\alpha)$

   求解外层的表示

   完整地表示外层问题：

   \[\begin{split} &min_{\alpha} ~~&\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j~(x_ix_j) - \sum_{i=1}^N\alpha_i \\ &s.t. &\sum_{i=1}^N \alpha_i y_i = 0 \\ & &\alpha_i \ge 0 ~~, ~~i=1,2,\cdots,N \end{split}\]

   这就是在线性可分数据集下最终可化简的优化目标。在解析数学上，应该不能再继续了。应该只能通过迭代方法去求解。

   不确定该观点

   以上就是在线性可分数据集下的优化目标及最终的优化问题。如果是浅层次说，那么第一个最大间隔推出的优化目标就够了，如果是需要求解该问题，那么就需要记住经过各步骤后最终得到的优化目标。

2. 线性不可分下优化目标

   现实世界中的数据通常包含噪点，或者本身就只是近似线性可分的。如果在线性不可分的情况下使用上述优化问题求解，因为约束条件始终得不到满足，在这种情况下会出现解的震荡，迭代无法停止。如果仍想要求出最大间隔的分类面，那么就需要一些处理。

   上述用解决线性可分问题的方法解决线性不可分问题带来的“震荡”和“无法停止”，只是主观猜测，无数据支持和理论证明。

   引入松弛变量

   松弛变量(slack variable) , 就我在《最优化方法》中学习到的知识，其是在解决线性规划时，引入一个非负变量，将原来的不等式约束化为等式约束，这个引入的变量就称为松弛变量。

   不过这里引入的松弛变量，主要是为了：

   为那些的确是线性不可分的点：

   1. 在约束中引入松弛变量，使得其满足约束

   2. 在目标函数中，为加入的松弛变量引入惩罚

   经过以上处理，我们看到线性不可分问题得到了一个不错的解决：因为我们优化的目标包含了惩罚项，所以肯定优先要减少惩罚项的引入，即是减少松弛变量的引入。也就是让能够线性可分的点线性可分，这样就减少了目标函数的值，符合优化目标；对于那些确实不可分的点，通过引入松弛变量，抹去了“震荡”的问题。

   即我们引入松弛变量$\theta$，下面形式化表示上述思想：

   \[\begin{split} &min_{w,b} ~~~&\frac{1}{2} |w|^2 + C\sum_{i=1}^N\theta_i\\ &s.t. & y_i(wx_i + b) \ge 1 - \theta_i \\ &&\theta_i \ge 0 ~~,~~i=1,2,\cdots , N \end{split}\]

   其中的$C$是惩罚因子，为一常数。该常数值大小对最终结果的影响，暂时还没有细致的总结过。公式一一对应了上面的思想以及限制，不赘述。

   变为无约束问题

   先将上面的式子写为数学上优化问题的标准形式：

   \[\begin{split} &min_{w,b} ~~~&\frac{1}{2} |w|^2 + C\sum_{i=1}^N\theta_i\\ &s.t. & 1 - \theta_i - y_i(wx_i + b) \le 0 \\ && -\theta_i \le 0 ~~,~~i=1,2,\cdots , N \end{split}\]

   与前面“线性可分情况下”的处理类似，同样引入拉格朗日乘子$\alpha , \mu$ , 有如下式子：

   \[\begin{split} &{转为无约束优化}{\Longrightarrow}\\ &min_{w,b,\theta} ~max_{\alpha} ~ L(w,b,\theta,\alpha) ~,\\ &其中~L(w,b,\theta,\alpha) = \frac{1}{2}|w|^2 + C\sum_{i=1}^N\theta_i - \sum_{i=1}^{N}\alpha_i ( y_i(wx_i + b) -1 + \theta_i ) - \sum_{i=1}^N {\mu_i \theta_i} \end{split}\]

   转为对偶问题

   \[\begin{split} min_{w,b,\theta} ~max_{\alpha} ~ L(w,b,\theta,\alpha) \Longrightarrow max_{\alpha}~min_{w,b,\theta} ~ L(w,b,\theta,\alpha) \end{split}\]

   求解对偶问题内层

   同样，对$L(w,b,\theta,\alpha)$求关于$w,b,\theta$的导数，并令其为0，得到结果为：

   \[\begin{split} &w = \sum_{i=1}^N {\alpha_i y_i x_i} \\ &\sum_{i=1}^N \alpha_i y_i = 0 \\ &C = \alpha_i + \mu_i , i = 1,2,\cdots , N \longrightarrow \mu与\alpha相关，后续可以消去！ \end{split}\]

   注意到对$\mu$求导得到了关于$\alpha,\mu,C$的表达式，而$C$是常数，故$\alpha$与$\mu$是相关的，可以用$\alpha$去表示$\mu$

   带入内层结果

   计算过程不表，按照约束化简即可。得到如下关于$\alpha$的函数：

   \[L(\alpha) = - \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j~(x_ix_j) + \sum_{i=1}^N\]

   不过很神奇，结果与线性可分时结果一致。不过约束是不一致的。

   外层表示

   \[\begin{split} &min_{\alpha} ~~&\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j~(x_ix_j) - \sum_{i=1}^N\alpha_i \\ &s.t. &\sum_{i=1}^N \alpha_i y_i = 0 \\ & &0 \le \alpha_i \le C~~, ~~i=1,2,\cdots,N \longrightarrow(唯一的区别) \end{split}\]

   仅仅对$\alpha_i$多了一个小于等于$C$的约束。

   意义

   因为$\alpha_i , i = 1,2,\cdots , N$ 有了更多的限制，我们需要探究这种限制代表的意义。

   1. $\alpha_i = 0$ ，对应点满足约束，且不是支持向量

      由最优化理论中的K-T条件可知，如果约束项$1 - \theta_i - y_i(wx_i + b) \le 0$ 中不能取等号，即$1 - \theta_i - y_i(wx_i + b) \lt 0$ ， 那么该约束对最终优化问题的结果无影响，不属于起作用约束集（紧约束集）。相应的约束项乘子$\alpha_i = 0 $ 。

      上面的理论称为互补松弛条件。通俗而不严谨地说，即是如果约束项为0，那么对应的乘子就不为0 ，该约束项对目标起作用；如果约束项小于0，那么乘子为0，表示该约束项对目标不起作用。

   2. $0 \lt \alpha_i \lt C $ ， 对应的$x_i$是支持向量。

      由上，此时$x_i$属于起约束集，对最终优化结果有影响。在SVM中，就是该点在分隔界面上，也就是该点是支持向量。

   3. $\alpha_i = C$

      此时有了惩罚项，根据约束$\alpha_i + \mu_i = C$ ， 知此时$\mu_i = 0$ ， 由互补松弛条件，相应的就是说$- \theta_i < 0 $， 即松弛变量$\theta_i > 0$ .

      此时，该点满足约束：$wx_i + b = 1 - \theta_i$ , 可以认为其在平面（或直线）$wx_i+b = 1 - \theta_i$上。我们考虑该平面与判决面$wx_i + b = 0$的距离：

      $d = |\frac{1 - \theta_i}{|w|}| $

      如果$0 \lt \theta_i \lt 1$ , 则其仍然在正确类别的一边，位于$wx_i + b = 1$与$wx_i+b=0$间。

      如果$\theta_i = 1$ ， 则其在判决界面$wx + b = 0$上。

      如果$\theta_i \gt 1 $，则其在正确类别的另一面，属于被错分的点（导致线性不可分的点）。

3. 从合页损失的角度看优化目标

   合页损失函数（hinge loss function）

   $f = max(c , x )$ , $c$是一个常量。

   因为函数图像形似合页（铰链）而得名。深度神经网络中常用的reLUs(Rectifier) $max(0 , x)$ 就是一个合页函数。

   从合页损失的角度看SVM优化目标

   定义如下的优化目标：

   \[min \sum_{i=1}^{N} { max( 0 , 1 - y_i(w_i x_i + b )) } + \lambda |w|^2\]

   其中$\sum_{i=1}^{N} { max( 0 , 1 - y_i(w_i x_i + b )) } $是损失函数，$|w|^2$是正则项，$\lambda$是正向项系数（因子）。

   直观的说明损失函数的意义：

   1. 如果分类正确，即$ y_i (w_i x_i + b) \ge 1$ ， 带入损失函数中，$1 - y_i(w_i x_i + b \le 0$ ，经过$\max$，故损失为0。符合定义。

   2. 如果分类不正确，则损失值是大于等于0的数，且正比于偏离分割面的距离。即分类错误程度越大，函数损失值越大。符合定义。

   形式化说明合页损失函数与最大间隔定义的等价性

   将上面的最大间隔优化目标（线性不可分）抄写如下：

   \[\begin{split} &min_{w,b} ~~~&\frac{1}{2} |w|^2 + C\sum_{i=1}^N\theta_i\\ &s.t. & y_i(wx_i + b) \ge 1 - \theta_i \\ &&\theta_i \ge 0 ~~,~~i=1,2,\cdots , N \end{split}\]

   令$\theta_i = max( 0 , 1- y_i(w_i x_i + b ))$ ， 即 ：

   \[\theta_i = \begin{cases} 0 & 1 - y_i (w_i x_i + b) \le 0 \\ 1 - y_i (w_i x_i + b) & 1 -y_i (w_i x_i + b) \ge 0 \end{cases}\]

   合页目标函数变为：

   \[min \sum_{i=1}^{N} \theta_i + \lambda |w|^2\]

   在此条件下，关于$theta_i$的约束也可以等价于:

   \[\begin{split} & \theta_i \ge 1 - y_i(w_i x_i + b) \\ & \theta_i \ge 0 \end{split}\]

   易知此时的约束与最大间隔的约束是相同的。

   再看目标函数，可以化为等价的如下形式：

   \[min \sum_{i=1}^{N} \frac{1}{C}( C \theta_i + C \lambda |w|^2 )\]

   令$\lambda = \frac{1}{2C}$ , 就化为如下形式：

   \[min \sum_{i=1}^{N} \frac{1}{C}( C \theta_i + \frac{1}{C} |w|^2 )\]

   又$C$是常数，对最小化目标没有影响。

   到此，说明合页损失函数定义的优化目标与最大间隔相同。

   用处

   定义合页损失函数的优化目标，在计算上没有什么价值。我想实际计算时需要按照此等价性转换为最大间隔的目标，然后再继续转变为实际计算的优化目标。其主要用途，我想更多的是将线性分类面推出的优化目标，再表示为损失函数的形式。这样就保持了整个机器学习算法框架的完美与统一。

   以上仅个人观点

4. 确认最终优化目标

   上面说得太长，叙述了一个推导的过程。这让我们知道了来源，却又陷入了细节与繁琐中。以下我们提取出上面的结论，给出SVM最终的优化目标。

   我们考虑两个方面，一个是原始的用于表示最大间隔思想的优化目标，我在这里称为模型优化目标；另一个是经过数学变换，化为真正用来计算求解的优化目标，这里称为计算优化目标。

   模型优化目标

   \[\begin{split} &min_{w,b} ~~~&\frac{1}{2} |w|^2 + C\sum_{i=1}^N\theta_i\\ &s.t. & y_i(wx_i + b) \ge 1 - \theta_i \\ &&\theta_i \ge 0 ~~,~~i=1,2,\cdots , N \end{split}\]

   其中$w,b$为超平面参数，$\theta_i$是为了解决线性不可分问题而引入的松弛变量，$C$是常数，是对分类错误点的惩罚。$\x_i , y_i$是输入实例的向量表示和输入实例的类别标签（取值为$\{ 1 , -1\}$）

   计算优化目标

   \[\begin{split} &min_{\alpha} ~~&\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j~(x_ix_j) - \sum_{i=1}^N\alpha_i \\ &s.t. &\sum_{i=1}^N \alpha_i y_i = 0 \\ & &0 \le \alpha_i \le C~~, ~~i=1,2,\cdots,N \end{split}\]

   其中$\alpha_i$是引入的拉格朗日乘子.

###引入核方法

TODO

###优化方法

TODO