本文将介绍SVM(Support Vector Machine)学习算法。SVM是现有的最强大的监督学习算法。我们首先讨论什么是间隔以及使用最大间隔来分类数据的思想。接着讨论最优间隔分类器，这里面会涉及拉格朗日对偶问题。我们也会讨论关于核方法以及如何有效地应用核方法到高维特征空间。最后我们会讨论SMO算法，它是SVM的一种实现方法。
间隔的直观理解
要理解支持向量机，首先必须先了解间隔以及关于预测置信度的概念。考虑一下逻辑回归，模型是\(h_\theta(x)=g(\theta^Tx)\),当且仅当\(h_\theta(x) \geq 0.5\),也即\(\theta^Tx \geq 0\)时，我们预测结果为1。考虑一个正例样本，显然\(\theta^Tx\)的值越大，\(h_\theta(x)=p(y=1|x;w;b)\)的值也越大，则预测样本label为1的置信程度也越高。更正式的，当\(\theta^Tx \gg 0\)时，可以认为我们的预测样本label为1的置信程度很高，同样，当\(\theta^Tx \ll 0\)时,可以认为我们的预测样本label为0的置信程度很高。给定一个训练集，如果我们能够在标签为1的样本中，找到合适的\(\theta\)，使得\(\theta^Tx^{(i)} \gg 0\)，那么这样拟合的效果就很好。同样，在标签为0的样本中，找到合适的\(\theta\)，使得\(\theta^Tx^{(i)} \ll 0\)。这样的拟合效果能够体现出分类器对于样本分类的置信程度很高。后面我们会使用函数间隔来形式化该思想。
我们可以换一种方式来理解。考虑下图，X代表正例，O代表反例，判定边界或称作分离超平面(separating hyperplane)将正反例分开，边界上，我们有\(\theta^T X = 0\)。考虑三个点A,B,C。
如上图所示，A点离判定边界很远。如果要预测A点的y值,显然可以很自信的预测y=1. 相反，C点离判定边界很近，尽管目前看我们可以判定C点y=1，但是如果我们对判定稍微移动一点，就很容易导致C点跑到另一侧y=0。因此可以说对A点预测的置信程度是高于C点的。B点介于两种情况之间。更通用的，对于离分离超平面远的点，我们可以对我们的预测结果很自信。因此，对于给定的训练集，我们希望找到一个判定边界，能够使得对于所有的样本都分类正确并且置信程度高，这也就意味着样本点要离判定边界远一点。后面我们会使用几何间隔来形式化该思想。
符号变化
为了使SVMs的讨论更加容易，我们需要对以前习惯的符号进行略微修正。我们首先考虑二分类线性分类器。对于标签y，我们现在不使用\(y \in \{0,1\}\),而使用\(y \in \{-1,1\}\)。对于线性分类器的参数，我们不使用向量\(\theta\),而使用参数\(w,b\)来表示：
$$h_{w,b}(x)=g(w^T x + b)$$
上述g函数就是分类的决策函数，当\(z \geq 0\)时，g(z)=1, 分类为正样本；当\(z<0\)时，g(z)=-1，分类为负样本。新的标志可以使得我们将截距项b和其他参数分开讨论。我们不再使用之前的\(x_0=1\), b相当于之前的\(\theta_0\),\(w\)相当于之前的\([\theta_1,\theta_2,…,\theta_n]^T\)
根据上文g的定义，我们的分类器会直接预测样本为1或者-1，而不是像逻辑回归那样先预测样本类别如果为1的概率，再根据概率大小确定样本类别。
函数间隔和几何间隔
函数间隔
对于一个给定的训练样本\((x^{(i)},y^{(i)})\), 我们定义该样本到w,b确定的分离超平面的函数间隔为：
$$\hat{\gamma}^{(i)}=y^{(i)}(w^T x + b)$$
注意为了使得预测更准确并且置信度更高，函数间隔越大越好。当\(y^{(i)}=1\)时,即\(w^T x + b\)在正方向越大越好。当当\(y^{(i)}=-1\)时,即\(w^T x + b\)在负方向越大越好。归纳起来，当\(y^{(i)}(w^T x + b)>0\)时，我们对该样本的预测结果就是正确的。而最大函数间隔可以代表我们的预测结果是正确并且置信度高。
对于一个线性分类器, 在我们选择的g函数的基础上(取值为-1和1)，函数间隔的问题在于，只要成倍增大\(w,b\)，\(g(w^Tx+b)=g(2w^Tx+2b)\)，这不会改变\(h_{w,b}\)的值，因为\(h_{w,b}\)的值只取决于其符号，即正负性，而不取决于\(w^T x + b\)的数量级。但是我们发现函数间隔却变大了2倍。这意味着，放大\(w,b\),会使得函数间隔任意大，但是却对模型的改进没有任何帮助。我们可以引入正则化条件，例如规定\(||w||_2=1\)，即二阶范式的值。然后将\((w,b)\)替换成，\((\frac{w}{||w||_2},\frac{b}{||w||_2})\).
对于给定的训练集\(S=\{(x^{(i)},y^{(i)});i=1,…,m\}\),我们定义训练集S相对于\((w,b)\)决定的分离超平面的函数间隔为，每个样本相对于分离超平面函数间隔中的最小的那个值。即：
$$\hat{\gamma}=\min_\limits{i=1,…,m} \hat{\gamma}^{(i)}$$
几何间隔
如上图，\((w,b)\)决定了分离超平面。可以证明\(w\)就是分离超平面的法向量。证明如下，考虑在分离超平面上取两点，\(x^{\\’}和x^{\\’’}\)
，则\(w^Tx^{\\’}+b=0\),\(w^Tx^{\\’’}+b=0\),两式相减有：
$$w^T(x^{\\’}-x^{\\’’})=0$$
因为\(x^{\\’}-x^{\\’’}\)是超平面上的向量，则根据垂直向量乘积为0，可以得到\(w\)就是分离超平面的法向量。
考虑点Ａ，Ａ代表了某个输入样本\(x^{(i)}\)且标签\(y^{(i)}=1\),设它到分离超平面的距离为\(\gamma^{(i)}\),就是图中AB代表的线段。
如何求\(\gamma^{(i)}\)的值呢？因为\(\frac{w}{||w||}\)代表和法向量同方向的单位向量，A点为\(x^{(i)}\),设B点位\(x^{(j)}\),BA和法向量同方向。则:
$$x^{(i)}-x^{(j)}=\gamma^{(i)}\frac{w}{||w||}$$
得出B点为：
$$x^{(j)}=x^{(i)}-\gamma^{(i)}\frac{w}{||w||}$$
因为B点位于分离超平面上，则：
$$w^T\left(x^{(i)}-\gamma^{(i)}\frac{w}{||w||}\right)+b=0$$
解的：
$$\gamma^{(i)}=\frac{w^Tx^{(i)}+b}{||w||}=\left(\frac{w}{||w||}\right)^T x^{(i)}+\frac{b}{||w||}$$
上面的结果是针对正样本，对于负样本，结果是一样的。
更通用的，我们定义某个训练样本\(x^{(i)},y^{(i)})\)相对于由\((w,b)\)决定的分离超平面的几何间隔为：
$$\gamma^{(i)}=y^{(i)}\left(\left(\frac{w}{||w||}\right)^T x^{(i)}+\frac{b}{||w||}\right)$$
注意到，如果\(||w||=1\),函数间隔等于几何间隔。这也是两种间隔之间的联系。根据上述几何间隔公式，几何间隔不受参数量级的影响，如果同时成倍放大\(w和b\)，几何间隔不会改变。这也可以从另一个方面来理解，注意到我们的分类超平面为\(g(x)=w^T x + b=0\), 成倍放大\(w和b\), 分类超平面根本就没有改变，所以几何间隔更不会改变。正因为如此，在使用训练集拟合w和b的时候，我们可以施加任意的放大缩小约束条件，例如，可以限制\(||w||=1\)或者\(||w_1||=5\),或者\(||w_1+b||+|w_2|=2\),所有的这些可以通过重新调整w和b来恢复。
对于给定的训练集\(S=\{(x^{(i)},y^{(i)});i=1,…,m\}\),我们定义训练集S相对于\((w,b)\)决定的分离超平面的几何间隔为，每个样本相对于分离超平面几何间隔中的最小的那个值。即：
$$\gamma=\min_\limits{i=1,…,m} \gamma^{(i)}$$
最优间隔分类器
对于给定的训练集，根据前面的讨论，我们很自然的希望能够找到一个分离超平面使得几何间隔最大化，只有这样，对于预测结果我们的置信度才足够高，样本拟合的结果才足够好。
开始前，我们要强调下，本文所讨论的内容仍然是假设数据集是线性可分的。我们可以写出如下的优化问题：
$$\max_{\gamma,w,b} \gamma \\\\
使得，y^{(i)}(w^T x^{(i)} + b) \geq \gamma, i=1,2,…,m \\\\
||w||=1
$$
我们要最大化\(\gamma\)，使得每一个训练样本的函数间隔都至少为\(\gamma\)。\(||w||=1\)约束保证了函数间隔等于几何间隔。也即，我们保证了每一个训练样本的几何间隔都至少为\(\gamma\)。因此，解决该优化问题的方法就是不断调整\((w,b)\)，来最大化几何间隔。
但是||w||=1的约束条件是非凸性约束，最优解容易陷入局部最优，因此我们无法使用现成的标准优化方法来解该优化问题。我们尝试修改该优化问题，考虑如下：
$$\max_{\gamma,w,b} \frac{\hat{\gamma}}{||w||} \\\\
使得，y^{(i)}(w^T x^{(i)} + b) \geq \hat{\gamma}, i=1,…,m
$$
我们尝试最大化几何间隔\(\frac{\hat{\gamma}}{||w||}\),使得每个样本的函数间隔都至少为\(\hat{\gamma}\)。几何间隔和函数间隔通过\(\gamma=\frac{\hat{\gamma}}{||w||}\)来联系。我们去掉了非凸约束||w||。我们通过将非凸约束转移到目标函数上，从而使得问题变成了非凸性问题。该问题目前仍然无法用标准通用方法解决。
对于上式，我们还可以再做一次变换。我们知道，等比例对\(w,b\)进行缩放，不会改变分离超平面的位置，假设已经得到了\(w,b\)，那么就能求得\(\hat{\gamma}\)的值，那么我们可以通过缩放w,b(同时除以\(\hat{\gamma}\)),使得\(\hat{\gamma}\)变为1.这样得到的分离超平面位置没有变化，完全可以从最开始就将\(\hat{\gamma}\)设为1。因此优化问题可以改写成：
$$\max_{\gamma,w,b} \frac{1}{||w||}$$
也即：（加上1/2系数是为了使结果更漂亮）
$$\min_{\gamma,w,b} \frac{1}{2}{||w||}^2 \\\\
使得, y^{(i)}(w^T x^{(i)} + b) \geq 1, i=1,…,m
$$
上述问题已经转换成凸性问题了，约束条件只有线性约束。该优化问题的结果就是最优间隔分类器。为了更好解决该问题，需要使用它的对偶问题，下面首先介绍拉格朗日对偶性。
拉格朗日对偶性
下面回顾一下线性约束优化问题。如下形式：
$$\min_w f(w) \\\\
使得， h_i(w)=0, i=1,…,l
$$
我们使用拉格朗日乘子(Lagrange multipliers)，拉格朗日方程如下：
$$L(w,\beta)=f(w)+\sum_{i=1}^l \beta_i h_i(w)$$
这里，\(\beta_i\)称作拉格朗日乘子，我们对其求偏导数并设为0.求得的值就是原问题的解了。
$$\frac{\partial L}{\partial w_i}=0; \frac{\partial L}{\partial \beta_i}=0$$
至于为什么引入拉格朗日算子可以求出极值，原因是f(w)的方向导数dw受等式的约束，dw的变化方向与f(w)的梯度度垂直时才能获得极值，而且在极值处，f(w)的梯度与其他等式梯度的线性组合平行，因此他们之间存在线性关系。
上述问题对应的是等式约束条件，我们需要将其扩展为不等式约束条件。考虑如下原始优化问题(primal optimization problem):
$$\min_w f(w) \\\\
使得， g_i(w) \leq 0, i=1,…,k \\\\
h_i(w)=0, i=1,…,l
$$
我们定义通用的拉格朗日方程(generalized Lagrangian)：
$$L(w,\alpha,\beta)=f(w)+\sum_{i=1}^k \alpha_i g_i(w) + \sum_{i=1}^l \beta_i h_i(w)$$
\(\alpha_i和\beta_i\)是拉格朗日乘子。考虑如下等式:
$$\theta_p(w)=\max_{\alpha,\beta:\alpha_i \geq 0} L(w,\alpha,\beta)$$
这里的下标p代表原始Primal。对于某些给定的\(w\)，如果w不符合约束条件，例如当某个\(g_i(w)>0\)时，我们可以使得和该\(g_i(w)>0\)相乘的乘子\(\alpha_i\)趋向于正无穷，则\(\theta_p(w)\)也趋向于正无穷；同样，当\(h_i(w) \neq 0\)时，根据\(h_i(w)\)的正负性，选择相应的\(\beta_i\)趋向于正无穷或负无穷，则\(\theta_p(w)\)也趋向于正无穷。因此对于不满足约束条件时，上述问题结果是：
$$\theta_p(w)=\max_{\alpha,\beta:\alpha_i \geq 0} L(w,\alpha,\beta) \\\\
=f(w)+\sum_{i=1}^k \alpha_i g_i(w) + \sum_{i=1}^l \beta_i h_i(w) \\\\
=\infty$$
相反，如果约束条件满足的话，对于给定的\(w\)，我们有,\(\theta_p(w)=f(w)\),这里的关键是我们的\(\alpha_i \geq 0且g_i(w) \leq 0\), 则\(\sum_{i=1}^k \alpha_i g_i(w) \leq 0\)，那么为了最大化\(\theta_p(w)\),有\(\sum_{i=1}^k \alpha_i g_i(w)=0\)。
因此，我们有：
$$
\begin{eqnarray} \theta_p(w)=\begin{cases} f(w), if \ w \ satisfies \ primal \ constraints \cr \infty, otherwise. \end{cases} \end{eqnarray}
$$
因而，我们可以认为\(\theta_p(w)\)即使将约束条件与目标函数融合在一起的表达方法，考虑最小化问题，我们得到了如下公式：
$$\min_w \theta_p(w) = \min_w \max_{\alpha,\beta:\alpha_i \geq 0} L(w,\alpha,\beta) (1)$$
因为,\(\theta_p(w)\)在满足约束条件下等价于\(f(w)\)问题，则\(\min_w \theta_p(w)\)问题等价于我们最初的原始优化问题(primal problem) \(\min_w f(w)\)。
我们定义\(p^{*}\)为原始问题取得最优解时的函数值，也即:
$$p^{*} = \min_w \theta_p(w)$$
接着定义：
$$\theta_D(\alpha,\beta)=\min_w L(w,\alpha,\beta)$$
上式中的下标D代表对偶(dual)。注意，\(\theta_p(w)\)优化的参数是\(\alpha,\beta\)，而这里\(\theta_D\)优化的参数是w.
我们可以得到对偶问题：
$$\max_{\alpha,\beta:\alpha_i \geq 0} \theta_D(\alpha,\beta)=\max_{\alpha,\beta:\alpha_i \geq 0} \min_w L(w,\alpha,\beta) (2)$$
该式就是我们原始问题的对偶形式，我们对比(1)和(2)发现：两个式子很相似，只是max和min位置调换了。
我们定义对偶问题的最优解为:
$$d^{*}=\max_{\alpha,\beta:\alpha_i \geq 0} \theta_D(w)$$
对偶问题和原始问题的关联如下：
$$d^{*}=\max_{\alpha,\beta:\alpha_i \geq 0} \min_w L(w,\alpha,\beta) \leq \min_w \max_{\alpha,\beta:\alpha_i \geq 0} L(w,\alpha,\beta) = p^{*}$$
可以证明,对于任意函数,max min的结果总是小于等于min max。在特定条件下, 我们有：
$$d^{*}=p^{*}$$
这些特定的条件包括，约束不等式\(g_i\)都是凸函数(线性函数都属于凸函数);约束\(h_i\)都是仿射函数(其实就是在线性函数基础上加上截距b);不等式\(g_i(w)\)约束条件严格可行,即对于任意的i,存在w,使得\(g_i(w)<0\)
在这些假设下，肯定存在\(w^{*},\alpha^{*},\beta^{*}\),使得\(w^{*}\)是原始问题的解，\(\alpha^{*},\beta^{*}\)是对偶问题的解,且\(p^{*}=d^{*}=L(w^{*},\alpha^{*},\beta^{*})\),这样的\(w^{*},\alpha^{*},\beta^{*}\)需要满足KKT(Karush-Kuhn-Tucker)条件，KKT条件如下：
$$\frac{\partial}{\partial w_i}L(w^{*},\alpha^{*},\beta^{*})=0, i=1,…,n \\\\
\frac{\partial}{\partial \beta_i}L(w^{*},\alpha^{*},\beta^{*})=0, i=1,…,l \\\\
\alpha_i^{*}g_i(w^{*})=0, i=1,…,k \\\\
g_i(w^{*}) \leq 0, i=1,…,k \\\\
\alpha^{*} \geq 0, i=1,…,k
$$
注意第3个式子，特别的:
$$当\alpha_i^{*}大于0时,g_i(w^{*})=0$$
我们称之为KKT互补条件。也就是说，\(g_i(w^{*})=0\)时，w处于可行域的边界上，这时才是起作用的约束，其他位于可行域内内部(\(g_i(w^{*})小于0\)的点都是不起作用的约束,其\(\alpha_i^{*}=0\))。KKT的总体思想是将极值会在可行域边界上取得，也就是不等式为0或等式约束里取得，而最优下降方向一般是这些等式的线性组合，其中每个元素要么是不等式为0的约束，要么是等式约束。对于在可行域边界内的点，对最优解不起作用，因此前面的系数为0。这个条件比较重要，在后文中，它将展示SVM只有一些支持向量点会起作用，在SMO算法中会给出收敛测试。
最优间隔分类器求解
上面讲述的原始／对偶优化问题(primal/dual optimal problem)，其目的在于对原始问题上不易求解的问题进行转换，使之更易求解。下面介绍通过对最优间隔分类器的对偶问题进行求解，得到的简化后的问题的过程。之前我们的优化问题是：
$$\min_{\gamma,w,b} \frac{1}{2}{||w||}^2 \\\ 使得, y^{(i)}(w^T x^{(i)} + b) \geq 1, i=1,…,m$$
我们将约束条件改写成:
$$g_i(w)=-y^{(i)}(w^T x^{(i)} + b)+1 \leq 0$$
该约束条件对每个样本都成立，根据KKT对偶互补条件，对于函数间隔为1(即满足约束\(g_i(w)=0\))的样本点，我们有\(\alpha_i > 0\)
考虑下图，最大间隔分离超平面是图中的实线。
最小间隔的点是那些靠近分离超平面的点，这里有3个这样的点，位于图中虚线处，1个负样本，2个正样本，因此只有该3个点对应的\(\alpha_i\)非零。这3个点叫做该问题的支持向量，意味着在求解问题时，使用到的支持向量数比样本大小少的多。
上述问题对应的拉格朗日方程是：
$$L(w,b,\alpha)=\frac{1}{2}{||w||}^2-\sum_{i=1}^m \alpha_i[y^{(i)}(w^T x^{(i)}+b)-1]$$
我们的问题只有不等式约束，没有等式约束，故拉格朗日乘子只有\(\alpha\)。并且该问题符合\(d^{*}=p^{*}\)的假设，肯定存在\(w^{*},\alpha^{*},\beta^{*}\)使得原始问题和对偶问题共用最优解。
求解对偶问题时，首先要固定\(\alpha\),以w,b为变量，最小化L；最小化L时，求解L对w和b的偏导，并将导数设为0，可以得到：
$$\nabla_w L(w,b,\alpha)=w-\sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}=0$$
得到:
$$w=\sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}$$
对b求偏导，得到：
$$\frac{\partial}{\partial b}(w,b,\alpha)=\sum_{i=1}^m \alpha_i y^{(i)}=0$$
我们将上式代入拉格朗日方程得到：
$$L(w,b,\alpha)=\frac{1}{2}{||w||}^2-\sum_{i=1}^m \alpha_i[y^{(i)}(w^T x^{(i)}+b)-1] \\\\
= \frac{1}{2}w^T w-\sum_{i=1}^m \alpha_i y^{(i)} w^T x^{(i)}-\sum_{i=1}^m \alpha_i y^{(i)} b + \sum_{i=1}^m \alpha_i \\\\
= \frac{1}{2}w^T \sum_{i=1}^m \alpha_i y^{(i)}x^{(i)} - \sum_{i=1}^m \alpha_i y^{(i)} w^T x^{(i)} + \sum_{i=1}^m \alpha_i \\\\
= \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \alpha_i y^{(i)} w^T x^{(i)} \\\\
= \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \alpha_i y^{(i)} \left(\sum_{j=1}^m \alpha_j y^{(j)} (x^{(j)})^T \right)x^{(i)} \\\\
= \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)} (x^{(j)})^T x^{(i)} \\\\
=\sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i,j=1}^m y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(j)})^T x^{(i)}
$$
得到如下对偶优化问题：
$$
\max_{\alpha} W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i,j=1}^m y^{(i)} y^{(j)} \alpha_i \alpha_j ＜x^{(i)},x^{(j)}＞ \\\\
使得， \alpha_i \geq 0, i=1,…,m \\\\
\sum_{i=1}^m \alpha_i y^{(i)} = 0
$$
\(＜x^{(i)},x^{(j)}＞\)代表向量的内积,该式子可以当作一个整体，在后续核技巧中发挥重要作用。
上式第一步为原问题，第二部将累加和展开，第三步代入w和b求导并设置为0后的结果，第四步合并系数，第五步代入w求导结果。
再强调一次，该问题符合\(d^{*}=p^{*}\)的假设和KKT条件。因此我们可以求解对偶优化问题，从而求得原始优化问题。上述对偶优化问题求解的参数只有\(\alpha_i\)。如果我们能够求解使得对偶问题最大化的\(\alpha\), 我们就可以通过\(w=\sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}\)推出原始优化问题的\(w\).如果找到了\(w^{*}\),可以得到截距b的值：
$$b^{*}=-\frac{\max_{i:y^{(i)}=-1} {w^{*}}^T x^{(i)} + \min_{i:y^{(i)}=1} {w^{*}}^T x^{(i)}}{2}$$
上式是在确定\(w^{*}\)后，正例和负例的支持向量所对应的截距的平均值，为了更直观的理解，考虑下图：
上式即是两条虚线与纵轴的截距的平均值。也可以理解为离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔，可以将分母2乘到b，再整理式子：
$$(\max_{i:y^{(i)}=-1} {w^{*}}^T x^{(i)}+b^{*}) + (\min_{i:y^{(i)}=1} {w^{*}}^T x^{(i)}+b^{*})=0$$
可以理解为二者函数间隔互为相反数，抵消了。
我们进一步考察一下式子\(w=\sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}\)，假设我们已经找到了优化问题的最优解，现在需要对新样本ｘ作出预测,我们可以通过计算\(w^T x+b\)来判断，大于等于0则预测y=1,否则y=0.但是使用上述式子，我们有：
$$w^T x+b=\left(\sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}\right)^T x + b \\\\
=\sum_{i=1}^m \alpha_i y^{(i)}＜x^{(i)},x＞+b$$
根据上式，如果我们求得了\(\alpha_i\)，为了对新样本做出预测，我们可以只计算x和每一个训练样本的内积。更进一步，前面我们讨论过，只有在支持向量处，\(\alpha_i\)才非零，因此我们只需要计算新样本和每一个支持向量之间的内积，这样计算数据量就少了很多。相当于只有这些支持向量为目标函数的计算做出贡献。
下文将引入核技巧到目标函数中，从而得到完全的支持向量机算法，然后介绍SMO序列最小化算法，该算法是优化问题的一种较快的解决方法。
核Kernels
上文中，我们的对偶最优问题中都会出现内积的形式，本部分将介绍可以使用核来替代内积，一定程度上可以解决非线性可分的问题。
核函数的理解
核函数！＝内积！＝映射！＝相似度，核函数是一种表征映射、实现内积逻辑关系且降低计算复杂度的一类特殊函数。(满足Mercer’s condition)。简单来说，核函数只是用来计算映射到高维空间滞后的内积的一种简便方法。
一般英文文献中对Kernel有两种提法，意识Kernel Function,二是Kernel Trick。从Trick一词可以看出，这只是一种运算技巧，不涉及高深莫测的东西。具体巧在哪里，我们如果想进行原本线性不可分的数据集的分割，那么一种方法是引入Soft Margin来容忍一些错误；另一种方法是对输入空间(Input Space)做特征扩展(Feature Expansion)，把数据集映射到高维中去，形成了特征空间(Feature Space)。我们几乎可以认为原本在低维中线性不可分的数据集在足够高的维度中存在线性可分的超平面。
对于第二种方法，我们所做的就是在特征空间中，使用原本在线性可分的情况下的优化方法，来找到最优分离超平面，唯一不同的是代入数据不同，我们需要代入得是\(\phi_(x_i)\),而不是\(x_i\)，\(\phi_(x_i)\)才是真正的从低维空间到高维空间的映射。考虑我们前面的优化式子，存在着一步内积计算。也即必须求出\(\phi_(x_i)^T \phi_(x_j)\),我们定义核函数为\(K(x_i,x_j)=\phi_(x_i)^T \phi_(x_j)\),使得我们不需要显示的计算每一个\(\phi_(x_i)\),甚至不需要知道\(\phi(\dot)\)长什么样，就可以直接求出\(\phi_(x_i)^T \phi_(x_j)\)的值，同时也能够大幅度提高计算速度和效率。
另外需要强调的一点是，kernel是一个独立的概念，kernel在SVM中的应用只是冰山一角，kernel的应用非常广泛，甚至出现的比SVM还早。
核函数
首先让我们回顾一下线性回归中房价预测的例子，我们曾尝试对变量居住面积Ｘ进行处理以获得三次型函数。即使用特征\(x,x^2,x^3\)。为了区别这两种形式的变量，我们称原始输入为输入属性(attributes)，映射之后的输入称为输入特征(features)。我们记\(\phi\)为特征映射(feature mappping)，即从属性到特征的映射。在上面例子中，我们有:
$$\phi(x)=\begin{bmatrix}x \\\ x^2 \\\ x^3 \end{bmatrix}$$
我们现在不使用原始的属性ｘ,而使用映射后的特征\(\phi(x)\).我们将之前的对偶优化问题使用\(\phi(x)\)来替换\(x\)。因为我们的对偶优化问题有内积的形式存在，意味着我们可以使用\(＜\phi(x),\phi(z)＞\)来替换\(＜x,z＞\)。对于给定的映射\(\phi\),我们定义相应的核为：
$$K(x,z)=\phi(x)^T \phi(Z)$$
这样，对于出现\(＜x,z＞\)的地方，我们可以使用\(K(x,z)\)来替换，这样我们的算法就是使用特征\(\phi\)得到的,而不是原始的属性。这样的处理可以使数据线性可分的概率变大，即不能保证在高维上一定是线性可分的，但一般情况下高维空间比低维空间上更倾向于线性可分。
但通常通过\(\phi\)映射后的向量维度过高，导致映射后向量内积的计算复杂度过高，核函数的引入就是为了解决这个问题，它既可以使得我们不需要显示定义出映射函数就能计算两个向量在高维空间的内积了，又使得时间复杂度降低。
下面介绍一个核函数的例子，假设\(x,z \in {\mathbb{R}}^n\)，考虑如下核函数：
$$K(x,z)=(x^T z)^2$$
重写为：
$$K(x,z)=\left(\sum_{i=1}^n x_i z_i \right) \left(\sum_{j=1}^n x_i z_i \right) \\\
= \sum_{i=1}^n \sum_{j=1}^n x_i x_j z_i z_j \\\\
= \sum_{i,j=1}^n (x_i x_j) (z_i z_j)
$$
因为\(K(x,z)=\phi(x)^T \phi(Z)\), 则相应的映射为：
$$\phi(x)=\begin{bmatrix} x_1 x_1 \\\ x_1 x_2 \\\ … \\\ x_n x_n\end{bmatrix}
$$
因此计算\(\phi(x)\)需要\(O(n^2)\)时间复杂度(内外两层循环计算乘积)。而计算\(K(x,z)\)只需要\(O(n)\)时间复杂度(一层循环计算\(\sum_{i=1}^n x_i z_i\),再对结果平方即可)。
一个相似的核函数如下：
$$K(x,z)=(x^T z+c)^2 \\\\
=\sum_{i,j=1}^n (x_i x_j)(z_i z_j) + \sum_{i=1}^n (\sqrt{2c}x_i)(\sqrt{2c}z_i) + c^2$$
对应的映射如下：
$$\phi(x)=\begin{bmatrix} x_1 x_1 \\\ x_1 x_2 \\\ … \\\ x_n x_n \\\ \sqrt{2c}x_1 \\\ … \\\ \sqrt{2c}x_n \\\ c \end{bmatrix}$$
一个更一般化的核函数如下：
$$K(x,z)=(x^T z+c)^d$$
该核函数对应的映射函数结果是一个\(\binom{n+d}{n}\)(组合符号)大小的向量，向量中每个向量都是最高为d阶的变量的组合。
对于上面的这些核函数，虽然它们对应的映射函数的维度可能是\(n^2,n^4\)等，意味着直接计算映射结果的内积的复杂度为\(O(n^2),O(n^4)\)。但是如果直接计算核函数的值，其复杂度均为\(O(n)\).
直观上来看，如果\(\phi(x)和\phi(z)\)在其对应的维度空间中位置接近，那么内积值K会很大(可认为同方向比较大)，如果很远则内积很小。这意味着核函数K是一个向量x和向量z接近程度的度量函数，从而引出SVM中使用较广泛的高斯核：
$$K(x,z)=exp\left(-\frac{ ||x-z||^2 }{2 \sigma^2}\right)$$
高斯核函数是一种度量x和z相似度的方法，如果x和y位置很接近，则K值接近1;如果很远，则k值接近0。高斯核函数对应的映射函数\(\phi\)是可以映射到无限维的。
Mercer定理
那么，什么样的核函数才是正确有效的核函数的？即如何判断一个函数是不是能拆分成映射函数乘积的形式？这两种表述是等价的，核函数是由映射函数乘积得到的，因而如果核函数合法，那么必然能写成两个映射函数的乘积。
我们首先定义核矩阵，对一个数据集\(\{x^{(1)},x^{(2)},…,x^{(m)}\}\),定义一个m*m的矩阵K，K中每个元素定义如下：
$$K_{ij}=K(x^{(i)},x^{(j)})$$
注意K既代表核函数又代表核矩阵。对于核矩阵，有几个性质，首先很显然\(K_{ij}=K_{ji}\),因此核矩阵是一个对称矩阵(symmetric matrix)。其次，对于任意的m维向量z，记\(\phi_k(x)\)为向量\(\phi(x)\)的第k个分量，我们有:
$$z^T K z = \sum_i \sum_j z_i K_{ij} z_j = \sum_i \sum_j z_i \phi(x^{(i)})^T \phi(x^{(j)}) z_j \\\\
=\sum_i \sum_j z_i \left(\sum_k \phi_k(x^{(i)}) \phi_k(x^{(j)}) \right)z_j \\\\
=\sum_k \sum_i \sum_j z_i \phi_k(x^{(i)}) \phi_k(x^{(j)}) z_j \\\\
= \sum_k \left(\sum_i z_i \phi_k(x^{(i)})\right)^2 \geq 0
$$
因为z是任意向量，可以得出K是半正定矩阵，加上对称性，K是对称半正定矩阵。如果K是有效的核，可以推出K是对称半正定矩阵，同样如果K是对称半正定矩阵，可以得出K是有效核。因此我们可以归纳出一个充要条件，该定理称作Mercer定理：
给定一个K：\({\mathbb{R}}^n \times {\mathbb{R}}^n -> \mathbb{R}\),那么K是有效核的充分必要条件是，对于任意一个有限数据集，对应的核矩阵式对称半正定矩阵。
对于核来说，不仅仅只存在SVM内，对于任意的算法，只要计算时出现了内积，都可以用核函数替代，从而提高在高维数据上的性能，例如感知机算法，代入后发展为核感知机算法，这也是核函数被称作核技巧的原因。
软间隔分类器
上文提到的最优间隔分类器时，一直强调数据是线性可分的。但是，当数据线性不可分时，或者映射到高维空间后仍然线性不可分，再或者即便是线性可分的但实际应用中不可避免出现噪声时，该如何处理呢？下文使用软间隔的方式进行解决。
首先观察上图，左边图代表最优间隔分类器，右边图在左上角添加一个负样本，为了实现最优间隔分类器，这导致分离超平面发生了一个急剧的旋转变换，这也导致得到的新的分类器在整体上只拥有一个比原来更小的间隔。
为了使算法能够适用于非线性分类器，对一些额外的点不那么敏感，我们重新修改优化问题，加入L1正则化项：
$$\min_{\gamma,w,b} \frac{1}{2}{||w||}^2+C \sum_{i=1}^m \zeta_i \\\\
使得, y^{(i)}(w^T x^{(i)} + b) \geq 1-\zeta_i, i=1,…,m \\\\
\zeta_i \geq 0, i=1,…,m
$$
注意上述的正则化是指第二项\(C \sum_{i=1}^m \zeta_i\)，称作hinge loss。如果是L2正则化则为，\(C\sum_{i=1}^m \zeta_i^2\),称作squared-hinge-loss。可参考A study on L2-Loss(Squared Hinge-Loss Multi-Class SVM)。另外对于第一项\(\frac{1}{2}{||w||}^2\)有的时候也叫做正则化，我们上述公式的第一项就是L2正则化。为了区别，对于上式，称第一项为L2-regularized，第二项为L1-loss。可参考Liblinear does not support L1-regularized L1-loss ( hinge loss ) support vector classification. Why?。在sklearn的LinearSVC中，L2-regularized对应参数penalty=’l2’,L1-loss对应参数loss=’hinge’。如果使用L2-loss，则loss=’squared_hinge’。
因此现在样本允许函数间隔小于1,如果一个样本的函数间隔为\(1-\zeta_i\),我们在目标函数上增加一个代价项\(C\zeta_i\). 参数C在\(||w||^2\)变大(我们之前希望其越小越好)和保证大多数样本函数间隔至少为1之间进行权衡。相当于现在放宽了约束条件，但是我们也对目标函数进行惩罚，使之更加严格。松弛因子\(\zeta\)使SVM能够容忍异常离群点的存在。惩罚因子\(C\)决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量(\(\zeta\))的和一定时，你定的C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点，最极端的情况是你把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，马上让问题变成无解，这就退化成了硬间隔问题，即C越大，你越希望在训练数据上少犯错误，而实际上这是不可能/没有意义的，于是就造成过拟合。
根据上述软间隔优化问题得到新的拉格朗日方程：
$$L(w,b,\zeta,\alpha,r)=\frac{1}{2}w^T w+C \sum_{i=1}^m \zeta_i - \sum_{i=1}^m \alpha_i[y^{(i)}(w^T x^{(i)}+b)-1+\zeta_i]- \sum_{i=1}^m r_i \zeta_i$$
\(\alpha_i,r_i\)是拉格朗日乘子，并且都\(\geq 0\).我们将上述改写成对偶问题的形式，具体过程不进行推导，和前文类似,得到如下对偶问题：
$$ \max_\alpha W(\alpha)= \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)} y^{(j)} \alpha_i \alpha_j ＜x^{(i)},x^{(j)}＞ \\\\
使得, 0 \leq \alpha_i \leq C, i=1,…,m \\\\
\sum_{i=1}^m \alpha_i y^{(i)} = 0 (对b求导得到的)
$$
我们惊奇的发现，该式子和之前最优间隔分类器优化问题唯一的区别是对\(\alpha_i\)做了进一步约束。求解得到\(\alpha\)后，\(w\)仍然可以按照公式\(w=\sum_{i=1}^m \alpha_i y^{(i)} x^{(i)}\)给出，但是截距b得到方式需要变化。KKT中的互补条件也要有略微变化,因为根据KKT条件有：
$$\alpha_i (y_i f(x_i)-1+\zeta_i)=0 \\\\
r_i \zeta_i = 0 \\\\
\alpha_i + r_i = C \Longrightarrow 0 \leq \alpha_i \leq C \\\
(约束：\zeta_i \geq 0，故根据拉格朗日方程以及KKT稳定性条件，对\zeta_i求导并等于0）
$$
则有：
$$\alpha_i=0 \Longrightarrow y^{(i)}(w^T x^{(i)} + b) \geq 1 \\\\
\alpha_i=C \Longrightarrow y^{(i)}(w^T x^{(i)} + b) \leq 1 \\\\
0 < \alpha_i < C \Longrightarrow y^{(i)}(w^T x^{(i)} + b) = 1
$$
则对b的计算，需要根据第三种情况，即\(0 < \alpha_i < C\)对应的样本在超平面上，将所有在超平面上的样本计算出来的\(b\)求平均。
这些条件将在下一节中用于判断SMO算法是否收敛。至此，终于已经得到一个可以应用于实际的具体问题了，下面一节将对对偶问题求解进行讨论。
SMO算法
SMO全称序列最小优化(sequential minimal optimization)，给出了一种解决对偶问题的有效方法。
坐标上升法
在介绍SMO算法前，先介绍一个简化的但与SMO使用同一思想的算法，坐标上升法(Coordinate Ascent)。
考虑如下无约束优化问题:
$$\max_\alpha W(\alpha_1,\alpha_2,…,\alpha_m)$$
我们认为W是关于\(\alpha_i\)参数的函数。暂且先不考虑SVM。我们已经学习过梯度上升和牛顿法，现在介绍一种新方法：
Loop Until Convergence: {
For i=1,2,…,m {
$$\alpha_i := \mathop{argmax}\limits_{\hat{\alpha_i}}W(\alpha_1,…,\alpha_{i-1}, \hat{\alpha_i},…,\alpha_n)
$$
}
}
最内层循环,当更新\(\alpha_i\)时，保持其它参数不变。在上述方法中，我们内层循环按照下标顺序遍历，在其他情况下，我们也可能根据一些规则，例如使得\(W(\alpha)\)增幅最大来选择相应的\(\alpha_i\)。如果argmax方法能够有效的执行，那么坐标上升法会是一个效率不错的算法。下图是只有二次型函数的坐标上升法：
上图的椭圆代表二次型函数的等高线。坐标上升法初始\(\alpha\)为(2,-2)。图中线条代表了从起始点到全局最大值经过的路径，每一步坐标上升法的收敛方法都与一个坐标轴平行，因为我们一次优化只更新一个变量，固定其余的变量。这张图只有2个参数，所以才能在二维图中展示出来。
SMO算法
我们的优化问题是：
$$ \max_\alpha W(\alpha)= \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)} y^{(j)} \alpha_i \alpha_j ＜x^{(i)},x^{(j)}＞ \\\\
使得, 0 \leq \alpha_i \leq C, i=1,…,m
\sum_{i=1}^m \alpha_i y^{(i)} = 0
$$
SMO算法与坐标上升法的不同地方在于，我们的对偶优化问题存在着约束\(\sum_{i=1}^m \alpha_i y^{(i)} = 0\),使得当固定其他参数而只改变一个参数的时候，发现该参数实际上是固定不变的，这样就无法进行更新。例如第一次更新\(\alpha_1\),则：
$$\alpha_1 y^{(1)} = - \sum_{i=2}^m \alpha_i y^{(i)}$$
两边同乘\(y^{(1)}\),即：
$$\alpha_1 = -y^{(1)} \sum_{i=2}^m \alpha_i y^{(i)}$$
因此，\(\alpha_1\)由其他参数唯一决定，我们就无法在不违反约束的情况下更新\(\alpha_1\).
因而SMO算法每次选择两个参数进行优化。选择参数时，使用一些启发式规则选择使全局目标函数增长最大的参数，具体：
假设我们在一次优化中选择\(\alpha_1,\alpha_2\)，根据约束条件，有:
$$\alpha_1 y^{(1)} + \alpha_2 y^{(2)} = - \sum_{i=3}^m \alpha_i y^{(i)}$$
右边式子是固定已知的(因为我们固定了其余的参数,注意这些参数一开始都有初始化的,因此上一次迭代完的参数值是已知的)。我们设右边式子为\(\zeta\):
$$\alpha_1 y^{(1)} + \alpha_2 y^{(2)} = \zeta$$
如上图，画出了该次迭代的约束直线，我们知道\(\alpha_1,\alpha_2\)一定位于\([0,C] \times [0,C]\)决定的边界以内。我们进一步得出,\(L \leq \alpha_2 \leq H\),否则\((\alpha_1,\alpha_2)\)无法同时满足在边界内核约束直线上。在这个例子中，L=0。实际上，两个参数中可以将一个当作变量，另外一个当作该变量的函数。我们重写为:
$$\alpha_1 = (\zeta-\alpha_2 y^{(2)})y^{(1)}$$
因此，目标函数W可以重写为：
$$W(\alpha_1,\alpha_2,…,\alpha_m)=W((\zeta-\alpha_2 y^{(2)})y^{(1)}, \alpha_2,…,\alpha_m)$$
将\(\alpha_3,…,\alpha_m\)当作常量，我们不难证明W是关于\(\alpha_2\)的二次函数，可以表达为\(a\alpha_2^2+b\alpha_2+c\)。加上[L,H]的约束条件，我们不难求出该二次函数最大时的\(\alpha_2\)取值。记二次函数无约束时的最优解为,\(\alpha_2^{new,unclipped}\),则有:
得到\(\alpha_2^{new}\)后，再使用\(\alpha_1,\alpha_2\)的关系求得\(\alpha_1^{new}\),最后在循环中进行更新。
关于选择更新参数的规则以及截距b如何求解，可以参考SMO作者Platt的论文。
SVM的应用
SVM作为一种分类器，在分类问题上表现惊人。比如文本分类、图像分类等。下面列举几个SVM的实际应用。
第一个例子是关于手写数字识别的问题。给定一张16*16的图片，上面写着0-9的10个数字，使用SVM判断。这本来是NN(Neural Network)比较擅长的问题，但初次用在SVM上时效果就好的惊人，因为SVM没有图片识别的先验知识，它只依据像素就能达到很好的效果。SVM上使用高斯核和多项式核都能在该问题上达到和NN相当的效果。
再比如通过氨基酸序列对蛋白质种类进行判别，假设有20种氨基酸，它们按照不同的序列组成不同的蛋白质，但是这些氨基酸序列的长度差异很大，那么该如何表示特征呢？有一种方式是使用连续4个氨基酸序列出现次数作为向量。首先求出氨基酸序列所有的排列组合\(20^4\)种，每个排列组合作为特征向量的一个特征，值是出现的次数，例如对于AABAABACDEF，可以得到AABA：2，ABAA：1，…，CDEF：1。因为特征向量的长度为\(20^4\)种,难以载入内存，但有一种高效的动态规划算法可以解决该问题。最后，再使用SVM进行建模。
参考
斯坦福大学机器学习视频教程
知乎: 核函数理解
Mercer’s Condition
Platt, John (1998), Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines
