支撑向量机（SVM）算法在分类问题中有着重要地位，其主要思想是最大化两类之间的间隔。按照数据集的特点：

  1. 线性可分问题，如之前的感知机算法处理的问题
  2. 线性可分，只有一点点错误点，如感知机算法发展出来的 Pocket 算法处理的问题
  3. 非线性问题，完全不可分，如在感知机问题发展出来的多层感知机和深度学习

这三种情况对于 SVM 分别有下面三种处理手段：

  1. hard-margin SVM
  2. soft-margin SVM
  3. kernel Method

SVM 的求解中，大量用到了 Lagrange 乘子法，首先对这种方法进行介绍。

约束优化问题

一般地，约束优化问题（原问题）可以写成：

4.支持向量机 - 图1%5C%5C%0A%26s.t.%5C%20mi(x)%5Cle0%2Ci%3D1%2C2%2C%5Ccdots%2CM%5C%5C%0A%26%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20n_j(x)%3D0%2Cj%3D1%2C2%2C%5Ccdots%2CN%0A%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0A%0A%26%5Cmin%7Bx%5Cin%5Cmathbb%7BR%5Ep%7D%7Df%28x%29%5C%5C%0A%26s.t.%5C%20m_i%28x%29%5Cle0%2Ci%3D1%2C2%2C%5Ccdots%2CM%5C%5C%0A%26%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20%5C%20n_j%28x%29%3D0%2Cj%3D1%2C2%2C%5Ccdots%2CN%0A%0A%5Cend%7Balign%7D%0A&height=67&width=202#crop=0&crop=0&crop=1&crop=1&id=pPoT0&originHeight=95&originWidth=283&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

定义 Lagrange 函数：

4.支持向量机 - 图2%3Df(x)%2B%5Csum%5Climits%7Bi%3D1%7D%5EM%5Clambda_im_i(x)%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Cetain_i(x)%0A#card=math&code=L%28x%2C%5Clambda%2C%5Ceta%29%3Df%28x%29%2B%5Csum%5Climits%7Bi%3D1%7D%5EM%5Clambdaim_i%28x%29%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Ceta_in_i%28x%29%0A&height=47&width=292#crop=0&crop=0&crop=1&crop=1&id=C1vND&originHeight=66&originWidth=409&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

那么原问题可以等价于无约束形式：

4.支持向量机 - 图3%5C%20s.t.%5C%20%5Clambdai%5Cge0%0A#card=math&code=%5Cmin%7Bx%5Cin%5Cmathbb%7BR%7D%5Ep%7D%5Cmax_%7B%5Clambda%2C%5Ceta%7DL%28x%2C%5Clambda%2C%5Ceta%29%5C%20s.t.%5C%20%5Clambda_i%5Cge0%0A&height=28&width=193#crop=0&crop=0&crop=1&crop=1&id=cmQKu&originHeight=39&originWidth=270&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这是由于，当满足原问题的不等式约束的时候，4.支持向量机 - 图4 才能取得最大值，直接等价于原问题，如果不满足原问题的不等式约束，那么最大值就为 ，由于需要取最小值，于是不会取到这个情况。

这个问题的对偶形式：

4.支持向量机 - 图5%5C%20s.t.%5C%20%5Clambdai%5Cge0%0A#card=math&code=%5Cmax%7B%5Clambda%2C%5Ceta%7D%5Cmin_%7Bx%5Cin%5Cmathbb%7BR%7D%5Ep%7DL%28x%2C%5Clambda%2C%5Ceta%29%5C%20s.t.%5C%20%5Clambda_i%5Cge0%0A&height=28&width=193#crop=0&crop=0&crop=1&crop=1&id=otumj&originHeight=39&originWidth=270&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

对偶问题是关于 4.支持向量机 - 图6 的最大化问题。

由于：

4.支持向量机 - 图7%5Cle%5Cmin%7Bx%7D%5Cmax%7B%5Clambdai%2C%5Ceta_j%7DL(x%2C%5Clambda_i%2C%5Ceta_j)%0A#card=math&code=%5Cmax%7B%5Clambdai%2C%5Ceta_j%7D%5Cmin%7Bx%7DL%28x%2C%5Clambdai%2C%5Ceta_j%29%5Cle%5Cmin%7Bx%7D%5Cmax_%7B%5Clambda_i%2C%5Ceta_j%7DL%28x%2C%5Clambda_i%2C%5Ceta_j%29%0A&height=29&width=277#crop=0&crop=0&crop=1&crop=1&id=Ty66d&originHeight=42&originWidth=388&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

证明：显然有 4.支持向量机 - 图8，于是显然有 4.支持向量机 - 图9，且 4.支持向量机 - 图10。

对偶问题的解小于原问题，有两种情况：

  1. 强对偶：可以取等于号
  2. 弱对偶：不可以取等于号

其实这一点也可以通过一张图来说明：

originVSdual.jpg

对于一个凸优化问题，有如下定理：

如果凸优化问题满足某些条件如 Slater 条件，那么它和其对偶问题满足强对偶关系。记问题的定义域为：4.支持向量机 - 图12%5Ccap%20dom%20m_i(x)%5Ccap%20domn_j(x)#card=math&code=%5Cmathcal%7BD%7D%3Ddomf%28x%29%5Ccap%20dom%20m_i%28x%29%5Ccap%20domn_j%28x%29&height=19&width=251#crop=0&crop=0&crop=1&crop=1&id=PBIg0&originHeight=27&originWidth=351&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。于是 Slater 条件为：
4.支持向量机 - 图13
其中 Relint 表示相对内部（不包含边界的内部）。

  1. 对于大多数凸优化问题，Slater 条件成立。
  2. 松弛 Slater 条件，如果 M 个不等式约束中，有 K 个函数为仿射函数，那么只要其余的函数满足 Slater 条件即可。

上面介绍了原问题和对偶问题的对偶关系，但是实际还需要对参数进行求解，求解方法使用 KKT 条件进行：

KKT 条件和强对偶关系是等价关系。KKT 条件对最优解的条件为：

  1. 可行域：4.支持向量机 - 图14%5Cle0%5C%5C%0An_j(x%5E)%3D0%5C%5C%0A%5Clambda%5E%5Cge0%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0Am_i%28x%5E%2A%29%5Cle0%5C%5C%0An_j%28x%5E%2A%29%3D0%5C%5C%0A%5Clambda%5E%2A%5Cge0%0A%5Cend%7Balign%7D%0A&height=58&width=77#crop=0&crop=0&crop=1&crop=1&id=y5tJs&originHeight=83&originWidth=108&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

  2. 互补松弛 4.支持向量机 - 图15%3D0%2C%5Cforall%20mi#card=math&code=%5Clambda%5E%2Am_i%28x%5E%2A%29%3D0%2C%5Cforall%20m_i&height=18&width=121#crop=0&crop=0&crop=1&crop=1&id=Smucx&originHeight=26&originWidth=170&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，对偶问题的最佳值为 4.支持向量机 - 图16，原问题为 4.支持向量机 - 图17![](https://g.yuque.com/gr/latex?%5Cbegin%7Balign%7D%0Ad%5E*%26%3D%5Cmax%7B%5Clambda%2C%5Ceta%7Dg(%5Clambda%2C%5Ceta)%3Dg(%5Clambda%5E%2C%5Ceta%5E)%5Cnonumber%5C%5C%0A%26%3D%5Cmin%7Bx%7DL(x%2C%5Clambda%5E%2C%5Ceta%5E)%5Cnonumber%5C%5C%0A%26%5Cle%20L(x%5E%2C%5Clambda%5E%2C%5Ceta%5E)%5Cnonumber%5C%5C%0A%26%3Df(x%5E)%2B%5Csum%5Climits%7Bi%3D1%7D%5EM%5Clambda%5Em_i(x%5E)%5Cnonumber%5C%5C%0A%26%5Cle%20f(x%5E)%3Dp%5E%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0Ad%5E%2A%26%3D%5Cmax%7B%5Clambda%2C%5Ceta%7Dg%28%5Clambda%2C%5Ceta%29%3Dg%28%5Clambda%5E%2A%2C%5Ceta%5E%2A%29%5Cnonumber%5C%5C%0A%26%3D%5Cmin%7Bx%7DL%28x%2C%5Clambda%5E%2A%2C%5Ceta%5E%2A%29%5Cnonumber%5C%5C%0A%26%5Cle%20L%28x%5E%2A%2C%5Clambda%5E%2A%2C%5Ceta%5E%2A%29%5Cnonumber%5C%5C%0A%26%3Df%28x%5E%2A%29%2B%5Csum%5Climits_%7Bi%3D1%7D%5EM%5Clambda%5E%2Am_i%28x%5E%2A%29%5Cnonumber%5C%5C%0A%26%5Cle%20f%28x%5E%2A%29%3Dp%5E%2A%0A%5Cend%7Balign%7D%0A&height=144&width=186#crop=0&crop=0&crop=1&crop=1&id=RMXLG&originHeight=203&originWidth=261&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
    为了满足相等，两个不等式必须成立，于是，对于第一个不等于号，需要有梯度为0条件，对于第二个不等于号需要满足互补松弛条件。

  1. 梯度为0：4.支持向量机 - 图18%7D%7B%5Cpartial%20x%7D%7C%7Bx%3Dx%5E*%7D%3D0#card=math&code=%5Cfrac%7B%5Cpartial%20L%28x%2C%5Clambda%5E%2A%2C%5Ceta%5E%2A%29%7D%7B%5Cpartial%20x%7D%7C%7Bx%3Dx%5E%2A%7D%3D0&height=37&width=146#crop=0&crop=0&crop=1&crop=1&id=pYkL6&originHeight=53&originWidth=204&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

Hard-margin SVM

支撑向量机也是一种硬分类模型，在之前的感知机模型中，我们在线性模型的基础上叠加了符号函数，在几何直观上，可以看到，如果两类分的很开的话，那么其实会存在无穷多条线可以将两类分开。在 SVM 中，我们引入最大化间隔这个概念，间隔指的是数据和直线的距离的最小值，因此最大化这个值反映了我们的模型倾向。

分割的超平面可以写为：

4.支持向量机 - 图19

那么最大化间隔（约束为分类任务的要求）：

4.支持向量机 - 图20%3E0%5C%5C%0A%5CLongrightarrow%5Cmathop%7Bargmax%7D%7Bw%2Cb%7D%5B%5Cmin_i%5Cfrac%7By_i(w%5ETx_i%2Bb)%7D%7B%7C%7Cw%7C%7C%7D%5D%5C%20s.t.%5C%20y_i(w%5ETx_i%2Bb)%3E0%0A#card=math&code=%5Cmathop%7Bargmax%7D%7Bw%2Cb%7D%5B%5Cmini%5Cfrac%7B%7Cw%5ETx_i%2Bb%7C%7D%7B%7C%7Cw%7C%7C%7D%5D%5C%20s.t.%5C%20y_i%28w%5ETx_i%2Bb%29%3E0%5C%5C%0A%5CLongrightarrow%5Cmathop%7Bargmax%7D%7Bw%2Cb%7D%5B%5Cmin_i%5Cfrac%7By_i%28w%5ETx_i%2Bb%29%7D%7B%7C%7Cw%7C%7C%7D%5D%5C%20s.t.%5C%20y_i%28w%5ETx_i%2Bb%29%3E0%0A&height=90&width=643#crop=0&crop=0&crop=1&crop=1&id=IAgal&originHeight=128&originWidth=900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

对于这个约束 4.支持向量机 - 图21%3E0#card=math&code=y_i%28w%5ETx_i%2Bb%29%3E0&height=20&width=109#crop=0&crop=0&crop=1&crop=1&id=OmdDd&originHeight=29&originWidth=153&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，不妨固定 4.支持向量机 - 图22%3D1%3E0#card=math&code=%5Cmin%20y_i%28w%5ETx_i%2Bb%29%3D1%3E0&height=20&width=164#crop=0&crop=0&crop=1&crop=1&id=uOCnR&originHeight=29&originWidth=230&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，这是由于分开两类的超平面的系数经过比例放缩不会改变这个平面，这也相当于给超平面的系数作出了约束。化简后的式子可以表示为：

4.支持向量机 - 图23%3D1%5C%5C%0A%5CRightarrow%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%5C%20s.t.%5C%20y_i(w%5ETx_i%2Bb)%5Cge1%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A#card=math&code=%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%5C%20s.t.%5C%20%5Cminiy_i%28w%5ETx_i%2Bb%29%3D1%5C%5C%0A%5CRightarrow%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%5C%20s.t.%5C%20y_i%28w%5ETx_i%2Bb%29%5Cge1%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A&height=82&width=643#crop=0&crop=0&crop=1&crop=1&id=VFGXA&originHeight=116&originWidth=900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这就是一个包含 4.支持向量机 - 图24 个约束的凸优化问题，有很多求解这种问题的软件。

但是，如果样本数量或维度非常高，直接求解困难甚至不可解，于是需要对这个问题进一步处理。引入 Lagrange 函数：

4.支持向量机 - 图25%3D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambda_i(1-y_i(w%5ETx_i%2Bb))%0A#card=math&code=L%28w%2Cb%2C%5Clambda%29%3D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambda_i%281-y_i%28w%5ETx_i%2Bb%29%29%0A&height=47&width=300#crop=0&crop=0&crop=1&crop=1&id=bnBsO&originHeight=66&originWidth=419&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

我们有原问题就等价于：

4.支持向量机 - 图26%5C%20s.t.%5C%20%5Clambdai%5Cge0%0A#card=math&code=%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cmax_%7B%5Clambda%7DL%28w%2Cb%2C%5Clambda_i%29%5C%20s.t.%5C%20%5Clambda_i%5Cge0%0A&height=31&width=222#crop=0&crop=0&crop=1&crop=1&id=wT4HQ&originHeight=44&originWidth=311&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

我们交换最小和最大值的符号得到对偶问题：

4.支持向量机 - 图27%5C%20s.t.%5C%20%5Clambdai%5Cge0%0A#card=math&code=%5Cmax%7B%5Clambdai%7D%5Cmin%7Bw%2Cb%7DL%28w%2Cb%2C%5Clambda_i%29%5C%20s.t.%5C%20%5Clambda_i%5Cge0%0A&height=28&width=198#crop=0&crop=0&crop=1&crop=1&id=HztRE&originHeight=39&originWidth=277&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

由于不等式约束是仿射函数，对偶问题和原问题等价：

  • 4.支持向量机 - 图28：4.支持向量机 - 图29
  • 4.支持向量机 - 图30：首先将 4.支持向量机 - 图31 代入：4.支持向量机 - 图32%3D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambda_i(1-y_iw%5ETx_i-y_ib)%3D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambdai-%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambdaiy_iw%5ETx_i%0A#card=math&code=L%28w%2Cb%2C%5Clambda_i%29%3D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambdai%281-y_iw%5ETx_i-y_ib%29%3D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambdai-%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambda_iy_iw%5ETx_i%0A&height=47&width=527#crop=0&crop=0&crop=1&crop=1&id=sHVg0&originHeight=66&originWidth=738&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)


所以：4.支持向量机 - 图33

  • 将上面两个参数代入：4.支持向量机 - 图34%3D-%5Cfrac%7B1%7D%7B2%7D%5Csum%5Climits%7Bi%3D1%7D%5EN%5Csum%5Climits%7Bj%3D1%7D%5EN%5Clambdai%5Clambda_jy_iy_jx_i%5ETx_j%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambdai%0A#card=math&code=L%28w%2Cb%2C%5Clambda_i%29%3D-%5Cfrac%7B1%7D%7B2%7D%5Csum%5Climits%7Bi%3D1%7D%5EN%5Csum%5Climits%7Bj%3D1%7D%5EN%5Clambda_i%5Clambda_jy_iy_jx_i%5ETx_j%2B%5Csum%5Climits%7Bi%3D1%7D%5EN%5Clambda_i%0A&height=49&width=303#crop=0&crop=0&crop=1&crop=1&id=R5Wvb&originHeight=69&originWidth=424&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

因此，对偶问题就是：4.支持向量机 - 图35

从 KKT 条件得到超平面的参数：

原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT 条件：
4.支持向量机 - 图36)%3D0(slackness%5C%20complementary)%5C%5C%0A%26%5Clambda_i%5Cge0%5C%5C%0A%261-y_i(w%5ETx_i%2Bb)%5Cle0%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0A%26%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w%7D%3D0%2C%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20b%7D%3D0%0A%5C%5C%26%5Clambda_k%281-y_k%28w%5ETx_k%2Bb%29%29%3D0%28slackness%5C%20complementary%29%5C%5C%0A%26%5Clambda_i%5Cge0%5C%5C%0A%261-y_i%28w%5ETx_i%2Bb%29%5Cle0%0A%5Cend%7Balign%7D%0A&height=97&width=352#crop=0&crop=0&crop=1&crop=1&id=uXKAR&originHeight=137&originWidth=493&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

根据这个条件就得到了对应的最佳参数：

4.支持向量机 - 图37

于是这个超平面的参数 4.支持向量机 - 图38 就是数据点的线性组合，最终的参数值就是部分满足 4.支持向量机 - 图39%3D1#card=math&code=y_i%28w%5ETx_i%2Bb%29%3D1&height=20&width=109#crop=0&crop=0&crop=1&crop=1&id=KnZQf&originHeight=29&originWidth=153&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)向量的线性组合（互补松弛条件给出），这些向量也叫支撑向量。

Soft-margin SVM

Hard-margin 的 SVM 只对可分数据可解，如果不可分的情况，我们的基本想法是在损失函数中加入错误分类的可能性。错误分类的个数可以写成：

4.支持向量机 - 图40%5Clt1%5C%7D%0A#card=math&code=error%3D%5Csum%5Climits_%7Bi%3D1%7D%5EN%5Cmathbb%7BI%7D%5C%7By_i%28w%5ETx_i%2Bb%29%5Clt1%5C%7D%0A&height=47&width=209#crop=0&crop=0&crop=1&crop=1&id=HS1v0&originHeight=66&originWidth=292&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这个函数不连续，可以将其改写为：

4.支持向量机 - 图41%5C%7D%0A#card=math&code=error%3D%5Csum%5Climits_%7Bi%3D1%7D%5EN%5Cmax%5C%7B0%2C1-y_i%28w%5ETx_i%2Bb%29%5C%7D%0A&height=47&width=243#crop=0&crop=0&crop=1&crop=1&id=S6Cdi&originHeight=66&originWidth=340&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

求和符号中的式子又叫做 Hinge Function。

将这个错误加入 Hard-margin SVM 中，于是：

4.支持向量机 - 图42%5C%7D%5C%20s.t.%5C%20yi(w%5ETx_i%2Bb)%5Cge1-%5Cxi_i%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A#card=math&code=%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2BC%5Csum%5Climits_%7Bi%3D1%7D%5EN%5Cmax%5C%7B0%2C1-y_i%28w%5ETx_i%2Bb%29%5C%7D%5C%20s.t.%5C%20y_i%28w%5ETx_i%2Bb%29%5Cge1-%5Cxi_i%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A&height=47&width=588#crop=0&crop=0&crop=1&crop=1&id=TgFAm&originHeight=66&originWidth=823&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

这个式子中，常数 4.支持向量机 - 图43 可以看作允许的错误水平，同时上式为了进一步消除 4.支持向量机 - 图44 符号，对数据集中的每一个观测，我们可以认为其大部分满足约束，但是其中部分违反约束，因此这部分约束变成 4.支持向量机 - 图45%5Cge1-%5Cxi_i#card=math&code=y_i%28w%5ETx%2Bb%29%5Cge1-%5Cxi_i&height=20&width=134#crop=0&crop=0&crop=1&crop=1&id=KlFpO&originHeight=29&originWidth=188&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，其中 4.支持向量机 - 图46#card=math&code=%5Cxi_i%3D1-y_i%28w%5ETx_i%2Bb%29&height=20&width=140#crop=0&crop=0&crop=1&crop=1&id=fpCWj&originHeight=29&originWidth=195&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，进一步的化简：

4.支持向量机 - 图47%5Cge1-%5Cxii%2C%5Cxi_i%5Cge0%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A#card=math&code=%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2BC%5Csum%5Climits_%7Bi%3D1%7D%5EN%5Cxi_i%5C%20s.t.%5C%20y_i%28w%5ETx_i%2Bb%29%5Cge1-%5Cxi_i%2C%5Cxi_i%5Cge0%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A&height=47&width=481#crop=0&crop=0&crop=1&crop=1&id=VxObs&originHeight=66&originWidth=673&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

Kernel Method

核方法可以应用在很多问题上，在分类问题中，对于严格不可分问题，我们引入一个特征转换函数将原来的不可分的数据集变为可分的数据集，然后再来应用已有的模型。往往将低维空间的数据集变为高维空间的数据集后，数据会变得可分（数据变得更为稀疏）：

Cover TH：高维空间比低维空间更易线性可分。

应用在 SVM 中时，观察上面的 SVM 对偶问题：

4.支持向量机 - 图48

在求解的时候需要求得内积，于是不可分数据在通过特征变换后，需要求得变换后的内积。我们常常很难求得变换函数的内积。于是直接引入内积的变换函数：

4.支持向量机 - 图49

称 4.支持向量机 - 图50#card=math&code=k%28x%2Cx%27%29&height=19&width=47#crop=0&crop=0&crop=1&crop=1&id=OYDgT&originHeight=27&originWidth=67&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 为一个正定核函数，其中4.支持向量机 - 图51 是 Hilbert 空间（完备的线性内积空间），如果去掉内积这个条件我们简单地称为核函数。

4.支持向量机 - 图52%3D%5Cexp(-%5Cfrac%7B(x-x’)%5E2%7D%7B2%5Csigma%5E2%7D)#card=math&code=k%28x%2Cx%27%29%3D%5Cexp%28-%5Cfrac%7B%28x-x%27%29%5E2%7D%7B2%5Csigma%5E2%7D%29&height=39&width=177#crop=0&crop=0&crop=1&crop=1&id=pmGbs&originHeight=56&originWidth=248&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 是一个核函数。
证明：
4.支持向量机 - 图53

正定核函数有下面的等价定义：

如果核函数满足：

  1. 对称性
  2. 正定性

那么这个核函数时正定核函数。

证明：

  1. 对称性 4.支持向量机 - 图54 4.支持向量机 - 图55%3Dk(z%2Cx)#card=math&code=k%28x%2Cz%29%3Dk%28z%2Cx%29&height=18&width=102#crop=0&crop=0&crop=1&crop=1&id=k6lt3&originHeight=26&originWidth=144&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，显然满足内积的定义
  2. 正定性 4.支持向量机 - 图56 4.支持向量机 - 图57，对应的 Gram Matrix 4.支持向量机 - 图58%5D#card=math&code=K%3D%5Bk%28x_i%2Cx_j%29%5D&height=19&width=95#crop=0&crop=0&crop=1&crop=1&id=JtRvJ&originHeight=27&originWidth=134&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 是半正定的。

要证：4.支持向量机 - 图59%3D%5Cphi(x)%5ET%5Cphi(z)%5CLeftrightarrow%20K#card=math&code=k%28x%2Cz%29%3D%5Cphi%28x%29%5ET%5Cphi%28z%29%5CLeftrightarrow%20K&height=20&width=164#crop=0&crop=0&crop=1&crop=1&id=n9dDg&originHeight=29&originWidth=229&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 半正定+对称性。

  1. 4.支持向量机 - 图60：首先，对称性是显然的，对于正定性：4.支持向量机 - 图61%26%5Ccdots%26k(x_1%2Cx_N)%5C%5C%5Cvdots%26%5Cvdots%26%5Cvdots%5C%5Ck(x_N%2Cx_1)%26%5Ccdots%26k(x_N%2Cx_N)%5Cend%7Bpmatrix%7D%0A#card=math&code=K%3D%5Cbegin%7Bpmatrix%7Dk%28x_1%2Cx_2%29%26%5Ccdots%26k%28x_1%2Cx_N%29%5C%5C%5Cvdots%26%5Cvdots%26%5Cvdots%5C%5Ck%28x_N%2Cx_1%29%26%5Ccdots%26k%28x_N%2Cx_N%29%5Cend%7Bpmatrix%7D%0A&height=70&width=237#crop=0&crop=0&crop=1&crop=1&id=QIJxG&originHeight=98&originWidth=332&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)


任意取 4.支持向量机 - 图62，即需要证明 4.支持向量机 - 图63：
4.支持向量机 - 图64%5Cphi(xj)%5Calpha_j%3D%5Csum%5Climits%7Bi%7D%5Calphai%5Cphi%5ET(x_i)%5Csum%5Climits%7Bj%7D%5Calphaj%5Cphi(x_j)%0A#card=math&code=%5Calpha%5ETK%5Calpha%3D%5Csum%5Climits%7Bi%2Cj%7D%5Calphai%5Calpha_jK%7Bij%7D%3D%5Csum%5Climits%7Bi%2Cj%7D%5Calpha_i%5Cphi%5ET%28x_i%29%5Cphi%28x_j%29%5Calpha_j%3D%5Csum%5Climits%7Bi%7D%5Calphai%5Cphi%5ET%28x_i%29%5Csum%5Climits%7Bj%7D%5Calpha_j%5Cphi%28x_j%29%0A&height=37&width=469#crop=0&crop=0&crop=1&crop=1&id=MhLI1&originHeight=53&originWidth=656&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
这个式子就是内积的形式，Hilbert 空间满足线性性，于是正定性的证。

  1. 4.支持向量机 - 图65：对于 4.支持向量机 - 图66 进行分解，对于对称矩阵 4.支持向量机 - 图67，那么令 4.支持向量机 - 图68%3D%5Csqrt%7B%5Clambda_i%7DV_i#card=math&code=%5Cphi%28x_i%29%3D%5Csqrt%7B%5Clambda_i%7DV_i&height=21&width=96#crop=0&crop=0&crop=1&crop=1&id=YFZzH&originHeight=30&originWidth=136&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，其中 4.支持向量机 - 图69是特征向量，于是就构造了 4.支持向量机 - 图70%3D%5Csqrt%7B%5Clambda_i%5Clambda_j%7DV_i%5ETV_j#card=math&code=k%28x%2Cz%29%3D%5Csqrt%7B%5Clambda_i%5Clambda_j%7DV_i%5ETV_j&height=31&width=140#crop=0&crop=0&crop=1&crop=1&id=jFC5W&originHeight=44&originWidth=197&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

小结

分类问题在很长一段时间都依赖 SVM，对于严格可分的数据集，Hard-margin SVM 选定一个超平面，保证所有数据到这个超平面的距离最大，对这个平面施加约束，固定 4.支持向量机 - 图71%3D1#card=math&code=y_i%28w%5ETx_i%2Bb%29%3D1&height=20&width=109#crop=0&crop=0&crop=1&crop=1&id=BRRmD&originHeight=29&originWidth=153&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，得到了一个凸优化问题并且所有的约束条件都是仿射函数，于是满足 Slater 条件，将这个问题变换成为对偶的问题，可以得到等价的解，并求出约束参数：

4.支持向量机 - 图72

对需要的超平面参数的求解采用强对偶问题的 KKT 条件进行。

4.支持向量机 - 图73)%3D0(slackness%5C%20complementary)%5C%5C%0A%26%5Clambda_i%5Cge0%5C%5C%0A%261-y_i(w%5ETx_i%2Bb)%5Cle0%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0A%26%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20w%7D%3D0%2C%5Cfrac%7B%5Cpartial%20L%7D%7B%5Cpartial%20b%7D%3D0%0A%5C%5C%26%5Clambda_k%281-y_k%28w%5ETx_k%2Bb%29%29%3D0%28slackness%5C%20complementary%29%5C%5C%0A%26%5Clambda_i%5Cge0%5C%5C%0A%261-y_i%28w%5ETx_i%2Bb%29%5Cle0%0A%5Cend%7Balign%7D%0A&height=97&width=352#crop=0&crop=0&crop=1&crop=1&id=wKuVJ&originHeight=137&originWidth=493&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

解就是：

4.支持向量机 - 图74

当允许一点错误的时候，可以在 Hard-margin SVM 中加入错误项。用 Hinge Function 表示错误项的大小，得到：

4.支持向量机 - 图75%5Cge1-%5Cxii%2C%5Cxi_i%5Cge0%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A#card=math&code=%5Cmathop%7Bargmin%7D%7Bw%2Cb%7D%5Cfrac%7B1%7D%7B2%7Dw%5ETw%2BC%5Csum%5Climits_%7Bi%3D1%7D%5EN%5Cxi_i%5C%20s.t.%5C%20y_i%28w%5ETx_i%2Bb%29%5Cge1-%5Cxi_i%2C%5Cxi_i%5Cge0%2Ci%3D1%2C2%2C%5Ccdots%2CN%0A&height=47&width=481#crop=0&crop=0&crop=1&crop=1&id=AhlLw&originHeight=66&originWidth=673&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

对于完全不可分的问题，我们采用特征转换的方式，在 SVM 中，我们引入正定核函数来直接对内积进行变换，只要这个变换满足对称性和正定性，那么就可以用做核函数。