SVM(支持向量机)

1.预备知识

1.1 KKT 条件

无约束优化

对于变量 x ∈ ℝⁿ 的函数 f(x) ,无约束优化问题如下:

min_xf(x)

直接找到使目标函数导数为 0 的点即可，即 f^′(x) = 0 ,如果没有解析解可以使用梯度下降或牛顿法等通过迭代使 x 沿负梯度方向逐渐逼近最小值点。

等式约束

如下等式约束问题：

约束条件会将解的范围限定在一个可行区域，此时不一定能找到 f^′(x) 为 0 的点，只需找到可行区域内使得 f(x) 最小的点即可，一般使用拉格朗日乘子法来进行求解，引入拉格朗日乘子 α ∈ ℝ^m ,构建拉格朗日函数：

并分别对 α 和 x 求偏导：

求得 x 、 α 的值，将 x 代入 f(x) 即为在约束条件 h_i(x) 下的可行解。下面用一个示例来进行说明，对于二维的目标函数 f(x, y) ,在平面中画出 f(x, y) 的等高线，如下图虚线，并给出一个约束等式 h(x, y) = 0 ,如下图绿线，目标函数 f(x, y) 与约束 h(x, y) 只可能相交，相切或没交集，只有相交或相切时才有可能是解，而且只有相切才可能得到可行解，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小。

因此,拉格朗日乘子法取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即

f^′(x) − αh^′(x) = 0

所以只要满足上述等式，且满足约束 h_i(x) = 0, i = 1, 2, …, m 即可得到解，联立起来，正好得到就是拉格朗日乘子法。以上为拉格朗日乘子法的几何推导。

不等式约束

给定如下不等式约束问题：

对应的拉格朗日函数：

L(x, λ) = f(x) + λg(x)

这时的可行解必须落在约束区域 g(x) 之内，下图给出了目标函数的等高线与约束：

由图可知可行解 x 只能在 g(x) ≤ 0的区域里:

(1)当可行解 x 落在 g(x) < 0 的区域内，此时直接极小化 f(x) 即可；

(2)当可行解 x 落在 g(x) = 0 即边界上，此时等价于等式约束问题。

当约束区域包含目标函数原有的可行解时，此时加上约束可行解仍然落在约束区域内部，对应 g(x) < 0 的情况，这时约束条件不起作用；当约束区域不包含目标函数原有的可行解时，此时加上约束后可行解落在边界 g(x) = 0 上。下图分别描述了两种情况，右图表示加上约束可行解会落在约束区域的边界上。

以上两种情况，要么可行解落在约束边界上即得 g(x) = 0 ，要么可行解落在约束区域内部，此时约束不起作用，令 λ = 0 消去约束即可，所以无论哪种情况都会得到：

λg(x) = 0

在等式约束优化中，约束函数与目标函数的梯度只要满足平行即可，而在不等式约束中则不然，若 λ ≠ 0，则可行解 x 是落在约束区域的边界上，这时可行解应尽量靠近无约束时的解，所以在约束边界上，目标函数的负梯度方向应该远离约束区域朝向无约束时的解，此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同：

−∇_xf(x) = λ∇_xg(x)

上式需要满足 λ > 0 ，这个问题可以举一个形象的例子，假设你去爬山，目标是山顶，但有一个障碍挡住了通向山顶的路，所以只能沿着障碍爬到尽可能靠近山顶的位置，然后望着山顶叹叹气，这里山顶便是目标函数的可行解，障碍便是约束函数的边界，此时的梯度方向一定是指向山顶的，与障碍的梯度同向，下图描述了这种情况:

对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是 KKT 条件。

对于以下约束问题:

对应拉格朗日函数：

则不等式约束后的可行解 x 需要满足的 KKT 条件为：

满足 KKT 条件后极小化拉格朗日函数即可得到在不等式约束条件下的可行解。 KKT 条件:

(1)拉格朗日取得可行解的必要条件；

(2)这就是以上分析的一个比较有意思的约束，称作松弛互补条件；

(3)(4)初始的约束条件；

(5)不等式约束的 Lagrange Multiplier 需满足的条件。

主要的 KKT 条件便是 (3) 和 (5) ，只要满足这俩个条件便可直接用拉格朗日乘子法， SVM 中的支持向量便是来自于此，需要注意的是 KKT 条件与对偶问题也有很大的联系。

1.2 对偶问题

对于任意一个带约束的优化都可以写成如下形式：

如果 g_j(x) 全是凸函数，并且 h_i(x) 全是仿射函数（ Ax + b 的形式），上述优化就是一个凸优化问题，凸优化极值唯一。

定义如下 Lagrangian ：

它通过一些系数把约束条件和目标函数结合起来，将带约束的优化问题转化为无约束问题。

现在我们针对参数 α, β 对 L(x, α, β) 取最大值，令:

Z(x) = max_{αi, βj ≥ 0}L(x, α, β)

满足约束条件的 x 使得 h_i(x) = 0 ,并且 g_j(x) ≤ 0, β_j ≥ 0 ,则有 β_jg_j(x) ≤ 0 .因此对于满足约束条件的 x 有 f(x) = Z(x) .而对于那些不满足约束条件的 x 有 Z(x) = ∞ ,这样将导致问题无解，因此必须满足约束条件。这样一来，原始带约束的优化问题等价于如下无约束优化问题：

min_xf(x) = min_xZ(x) = min_xmax_{αi, βj ≥ 0}L(x, α, β)

这个问题称作原问题(primal problem),与之相对应的为对偶问题(dual problem),其形式非常类似，只是把 min , max  交换了一下：

max_{αi, βj ≥ 0}min_xL(x, α, β)

原问题是在最大值中取最下的那个，对偶问题是在最小值取最大的那个。令：

D(α, β) = min_xL(x, α, β)

如果原问题的最小值记为 p^* ,那么对于所有 α_i, β_j ≥ 0 有：

D(α, β) ≤ p^*

由于对于极值点(包括所有满足约束条件的点) x^* , 并且 β_j ≥ 0 ,总有 :

因此

于是

D(α, β) = min_xL(x, α, β) ≤ L(x^*, α, β) ≤ f(x^*) = p^*

因此

max_{αi, βj ≥ 0}D(α, β)

实际上就是原问题的最大下界，最大下界离我们要逼近的值最近。记对偶问题的最优值为 d^* ，则有：

d^* ≤ p^*

这个性质叫做弱对偶性（weak duality），对于所有优化问题都成立，即使原始问题非凸。这里还有两个概念： f(x)–D(α, β) 叫做对偶间隔（duality gap），p^*–d^*叫做最优对偶间隔（optimal duality gap）。无论原始问题是什么形式，对偶问题总是一个凸优化的问题，这样对于那些难以求解的原始问题 （甚至是 NP 问题），均可以通过转化为偶问题，通过优化这个对偶问题来得到原始问题的一个下界， 与弱对偶性相对应的有一个强对偶性（strong duality） ，强对偶即满足：

d^* = p^*

强对偶是一个非常好的性质，因为在强对偶成立的情况下，可以通过求解对偶问题来得到原始问题的解，在 SVM 中就是这样做的。当然并不是所有的对偶问题都满足强对偶性 ，在 SVM 中是直接假定了强对偶性的成立，其实只要满足一些条件，强对偶性是成立的，比如说 Slater 条件与 KKT 条件。

Slater 条件

若原始问题为凸优化问题，且存在严格满足约束条件的点 x ，这里的“严格”是指 g_j(x) ≤ 0 中的“ ≤ ”严格取到“ < ”，即存在 x 满足 g_j(x) < 0, i = 1, 2, …, n ，则存在x^*, α^*, β^*使得 x^* 是原始问题的解，α^*, β^*是对偶问题的解，且满足：

p^* = d^* = L(x^*, α^*, β^*)

也就是说如果原始问题是凸优化问题并且满足 Slater 条件的话，那么强对偶性成立。需要注意的是，这里只是指出了强对偶成立的一种情况，并不是唯一的情况。例如，对于某些非凸优化的问题，强对偶也成立。SVM 中的原始问题 是一个凸优化问题（二次规划也属于凸优化问题），Slater 条件在 SVM 中指的是存在一个超平面可将数据分隔开，即数据是线性可分的。当数据不可分时，强对偶是不成立的，这个时候寻找分隔平面这个问题本身也就是没有意义了，所以对于不可分的情况预先加个 kernel 就可以了。

KKT 条件

假设x^*与α^*, β^*分别是原始问题（并不一定是凸的）和对偶问题的最优解，且满足强对偶性，则相应的极值的关系满足：

由于两头是相等的，所以这一系列的式子里的不等号全部都可以换成等号。根据第一个不等号我们可以得到x^*是L(x, α^*, β^*)的一个极值点，因此L(x, α^*, β^*)在x^*处的梯度为0，即:

∇_x^*L(x, α^*, β^*) = 0

由第二个不等式，并且β_j^*g_j(x^*)都是非正的，因此有：

β_j^*g_j(x^*) = 0, j = 1, ⋯, m

显然，如果β_j^* > 0,那么必定有g_j(x^*) = 0,如果g_j(x^*) < 0,那么可以得到β_j^* = 0。再将其他一些显而易见的条件写到一起，就是传说中的 KKT (Karush-Kuhn-Tucker) 条件：

总结来说就是说任何满足强对偶性的优化问题，只要其目标函数与约束函数可微，任一对原始问题与对偶问题的解都是满足 KKT 条件的。即满足强对偶性的优化问题中，若x^*为原始问题的最优解，α^*, β^*为对偶问题的最优解，则可得x^*, α^*, β^*满足 KKT 条件。

上面只是说明了必要性，当满足原始问题为凸优化问题时，必要性也是满足的，也就是说当原始问题是凸优化问题,且存在x^*, α^*, β^*满足 KKT 条件，那么它们分别是原始问题和对偶问题的极值点并且强对偶性成立.

证明

首先原始问题是凸优化问题，固定α^*, β^*之后对偶问题D(α^*, β^*)也是一个凸优化问题，x^* 是L(x, α^*, β^*)的极值点：

最后一个式子是根据 KKT 条件中的 h_i(x) = 0 与 β_jg_j(x) = 0 得到的。这样一来，就证明了对偶间隔为零，也就是说，强对偶成立。

对于一个约束优化问题，找到其对偶问题，当弱对偶成立时，可以得到原始问题的一个下界。而如果强对偶成立，则可以直接求解对偶问题来解决原始问题。 SVM 就是这样的。对偶问题由于性质良好一般比原始问题更容易求解，在 SVM 中通过引入对偶问题可以将问题表示成数据的内积形式从而使得 kernel trick 的应用更加自然。此外，还有一些情况会同时求解对偶问题与原始问题 ，比如在迭代求解的过程中，通过判断对偶间隔的大小，可以得出一个有效的迭代停止条件。

2.支持向量机

2.1 线性可分支持向量机与硬间隔最大化

2.1.1 线性可分支持向量机

SVM 一直被认为是效果最好的现成可用的分类算法之一，SVM 内容比较多，学习 SVM 首先要从线性分类器开始。考虑一个二分类问题，给定训练数据集

T = {(x₁, y₁), (x₂, y₂), ⋯, (x_n, y_n)},  x_i ∈ 𝒳 = Rⁿ,  y_i ∈ 𝒴 = {+1, −1},  i = 1, 2, ⋯, n

其中 x_i 为第 i 个特征向量， y_i 为 x_i 的类标记（有些地方会选 0 和 1 ，当然其实分类问题选什么都无所谓，只要是两个不同的数字即可，不过这里选择 +1 和 -1 是为了方便 SVM 的推导），学习的目标是在特征空间中找到一个分离超平面(线性分类器),其方程可表示为：

w^Tx + b = 0

其中 w = (w₁; w₂; ⋯; w_d) 为法向量，决定了超平面的方向； b 为位移项，决定了超平面与原点之间的距离。在二维空间中的例子就是一条直线。通过这个超平面可以把两类数据分隔开来，一部分是正类，一部分是负类，法向量指向的一侧为正类，另一侧为负类。这里我们首先来说明线性可分的情况，对于线性不可分的情况后边会进行分析。

2.1.2 函数间隔与几何间隔

如图所示，两种标记的点分别代表两个类别，直线表示一个可行的超平面。将数据点 x 代入 f(x) 中，如果得到的结果小于 0 ，则赋予其类别 -1 ，如果大于 0 则赋予类别 1 。对于 f(x) 的绝对值很小(包括)的情况，是很难处理的，因为细微的变动（比如超平面稍微转一个小角度）就有可能导致结果类别的改变，也就是越接近超平面的点越“难”分隔。

在超平面 w^Tx + b = 0 确定的情况下| w^Tx + b |能够相对的表示点 x 与超平面的距离。 w^Tx + b 的符号与类标记 y 的符号是否一致可判断分类是否正确,因此 y(w^Tx + b) 可以用来表示分类的正确性及确信度。

隔函数间隔（functional margin）：

γ̂_i = y_i(w^Tx_i + b) = y_if(x_i)

而超平面关于 T 中所有样本点 (x_i, y_i) 的函数间隔最小值（ i 表示第 i 个样本），便为超平面关于训练数据集 T 的函数间隔：

γ̂ = min_{i = 1, 2, ⋯, n}γ̂_i

这样定义的函数间隔有问题，如果成比例的改变 w 和 b（如将它们改成 2w 和 2b ），则函数间隔的值 f(x) 却变成了原来的2倍（虽然此时超平面没有改变）。但可以通过对超平面的法向量 w 加一些约束，如规范化∥w∥ = 1,使间隔确定。这时的函数间隔即为几何间隔(geometrical margin)。

如图所示，对于一个点 x ，令其垂直投影到超平面上的对应的为 x₀ ，由于 w 是垂直于超平面的一个向量， γ 为样本 x 到超平面的距离,则有：

其中∥w∥为 w 的二阶范数（范数是一个类似于模的表示长度的概念），是单位向量（一个向量除以它的模称之为单位向量）。又由于 x₀ 是超平面上的点，满足 f(x0) = 0 ，代入超平面的方程 w^Tx + b = 0 ，可得 w^Tx₀ = −b。

两边同时乘以 w^T , 再有w^Tw = ∥w∥²,可得：

为了得到 γ 的绝对值，令 γ 乘上对应的类别 y ,并取最小值，即可得出几何间隔（用 γ̃ 表示）的定义：

几何间隔就是函数间隔除以∥w∥，而且函数间隔 y(w^Tx + b) = yf(x) 实际上就是| f(x) |，只是人为定义的一个间隔度量，而几何间隔

才是直观上的点到超平面的距离。

2.1.3 硬间隔最大化

对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。通过由前面的分析可知：函数间隔不适合用来最大化间隔值，因为在超平面固定以后，可以等比例地缩放 w 的长度和 b 的值,可以使函数间隔的值任意大；而几何间隔的大小不会随着 w 和 b 的缩放而改变。因此，最大间隔分类超平面中的“间隔”指的是几何间隔。

于是最大间隔分类器（maximum margin classifier）的目标函数可以定义为：

max_w, bγ̃

同时需满足一些条件，根据间隔的定义，有

于是这个问题可以改写为：

函数间隔 γ̂ 的取值是点到超平面的最小间隔，并不影响最优化问题的解， 我们固定 γ̂ 的值也只会将 w, b 成比例缩放并不会改变超平面，因此我们可以令 γ̂ = 1 ，并且最大化等价于最小化,于是线性可分支持向量机学习的最优化问题可以写为：

(1)分离超平面的存在性

由于训练数据集线性可分，上述优化问题一定存在可行解。又由于目标函数有下界，并且数据集中既有正类又有负类，因而最优解(w^*, b^*)必满足w^* ≠ 0.由此得知分离超平面的存在性。

(2)超平面的唯一性

假设上述优化问题有两个最优解(w₁^*, b₁^*)和(w₂^*, b₂^*).显然∥w₁^*∥ = ∥w₂^*∥ = c,其中 c 是一个常数。令,易知 (w, b) 也为原问题的可行解(非最优解)，从而有

从而有w₁^* = λw₂^*,易知 λ = 1 或 λ = −1 ,但 λ = −1 时 w = 0 不是原问题的可行解，则有w₁^* = w₂^*.

可以将两个最优解分别写为(w^*, b₁^*), (w^*, b₂^*),然后证b₁^* = b₂^*.设 x₁^′, x₂^′ 是 y_i = +1 集合中分别对应(w^*, b₁^*), (w^*, b₂^*)使得问题的不等式等号成立的点， x₁^″, x₂^″ 是 y_i = −1 集合中分别对应(w^*, b₁^*), (w^*, b₂^*)使得问题的不等式等号成立的点，则有:

使得

又因为

(w^*)^Tx₂^′ + b₁^* ≥ 1 = (w^*)^Tx₁^′ + b₁^*

(w^*)^Tx₁^′ + b₂^* ≥ 1 = (w^*)^Tx₂^′ + b₂^*

所以，(w^*)^T(x₁^′ − x₂^′) = 0,同理有(w^*)^T(x₁^″ − x₂^″) = 0,因此

b₁^* − b₂^* = 0

得两个最优解是相同的，即最优解唯一。

支持向量和间隔边界

如上图所示，中间的实线便是寻找到的最优超平面（Optimal Hyper Plane），其到两条虚线边界的距离相等，这个距离便是几何间隔 γ̃ ,两条虚线间隔边界之间的距离等于 2γ̃ ,而虚线间隔边界上的点则是支持向量。由于这些支持向量刚好在虚线间隔边界上，所以它们满足 y(w^Tx + b) = 1 ,而对于所有不是支持向量的点，则显然有 y(w^Tx + b) > 1 。

2.1.4 对偶

线性可分支持向量机最优化问题的原问题的拉格朗日函数为:

其中， α_i ≥ 0 .

则线性可分支持向量机最优化原问题等价于如下无约束问题:

min_w, bmax_αL(w, b, α)

其对偶问题为:

max_αmin_w, bL(w, b, α)

首先求 L(w, b, α) 对 w, b 的极小，由

得

将上述结果代入拉格朗日函数得：

再对 求 α 的极大,即得对偶问题:

上式可转化为:

可以通过求解上述对偶问题的解，进而确定分离超平面。即，设α^* = (α₁^*, α₂^*, ⋯, α_N^*)^T为上述对偶问题的一个解，若存在一个α_j^*使得0 < α_j^*，则原始问题的解w^*, b^*为:

将 w^* 代入分离超平面函数可得:

其中 ⟨⋅, ⋅⟩ 代表向量内积，这里的形式的有趣之处在于，对于新点 x 的预测，只需要计算它与训练数据点的内积即可.

由拉格朗日函数和 KKT 互补条件可得：

α_i(y_i(w^*)^Tx_i) − 1) = 0, i = 1, 2, ⋯, N

而当 α_i > 0 时，有

y_i(w^*)^Tx_i) − 1 = 0

即这些 x_i 一定在间隔边界上， 而对于那些不在间隔边界上的实例 x_i 所对应的 α_i = 0 .

2.2 线性不可分支持向量机与软间隔最大化

2.2.1 线性支持向量机

线性可分问题的支持向量机的学习方法，对线性不可分训练数据不适用。通常情况是，训练集中有一些特异点，将这些特异点除去后，剩下大部分样本点组成的集合是线性可分的。

线性不可分意味着某些样本点 (x_i, y_i) 不能满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点 (x_i, y_i) 引入一个松弛变量 ξ_i ≥ 0 ,使函数间隔加上松弛变量大于等于1，即：

y_i(w^Tx_i + b) ≥ 1 − ξ_i

而对于每个松弛变量 ξ_i ,需要做一些惩罚，则目标函数可写为:

这里， C > 0 称为惩罚参数， C 值大时对误分类的惩罚增大， C 值小时对误分类的惩罚减小。最小化上述目标函数，即要使间隔最大化，同时使误分类的个数尽量小， C 是调和二者的系数。相对于硬间隔最大化，这个称为软间隔最大化。

线性不可分的线性支持向量机的学习问题可描述成如下凸二次优化问题:

上述问题是一个凸二次规划问题，因而关于 (w, b, ξ) 的解是存在的。并且 w 唯一， b 不唯一， b 的解存在于一个区间。

对于线性不可分时的线性支持向量机简称为线性支持向量机。显然，线性支持向量机包含线性可分支持向量机。而由于现实中训练数据往往是不可分的，因此信息支持向量机具有更广的实用性。

2.2.2 对偶

线性不可分支持向量机最优化问题的原问题的拉格朗日函数为:

其中， α_i ≥ 0, μ_i ≥ 0 ,在线性可分支持向量机可以认为 ξ_i = 0.

则线性不可分支持向量机最优化原问题等价于如下无约束问题:

min_w, b, ξmax_α, μL(w, b, ξ, α, μ)

其对偶问题为:

max_α, μmin_w, b, ξL(w, b, ξ, α, μ)

首先求 L(w, b, ξ, α, μ) 对 w, b, ξ 的极小，由

得

C − α_i − μ_i = 0

将上述结果代入拉格朗日函数得：

再对 求 α 的极大(上式中已不包含 μ ),即得对偶问题:

上式可转化为:

可以通过求解上述对偶问题的解，进而确定分离超平面。即，设α^* = (α₁^*, α₂^*, ⋯, α_N^*)^T为上述对偶问题的一个解，若存在一个α_j^*使得0 < α_j^* < C，则原始问题的解w^*, b^*为:

2.2.3 支持向量

在线性不可分情况，对偶问题的解α^* = (α₁^*, α₂^*, ⋯, α_N^*)^T中对应于α_i^* > 0的样本点 (x_i, y_i) 的实例 x_i 称为软间隔的支持向量。如下图所示，图中分离超平面由实线表示，间隔边界由虚线表示，正离由圈表示，负例由叉表示。 x_i 到间隔边界的距离.

软间隔的支持向量 x_i 或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分的一侧。若α_i^* < C, 则 ξ_i = 0,支持向量 x_i 恰好落在间隔边界上；若α_i^* = C, 0 < ξ_i < 1,则 x_i 间隔边界与分离超平面之间；若α_i^* = C, ξ_i = 1,则 x_i 在分离超平面上；若α_i^* = C, ξ_i > 1,则 x_i 在分离超平面误分一侧。

2.2.4 合页损失函数

线性支持向量机原始最优化问题:

等价于最优化问题:

函数

L(y(w^Tx + b)) = [1 − y(w^Tx + b)]

称为合页损失函数(hinge loss function). 下标“+”表示以下取正直的函数:

以上说明，当样本点 (x_i, y_i) 被正确分类且函数间隔(确信度) y_i(w^Tx_i + b) 大于1时，损失是0，否则损失是 1 − y_i(w^Tx_i + b) .目标函数第二项是系数为 λ 的 w 的 L₂ 范数，是正则化项。

令:

[1 − y_i(w^Tx_i + b)]₊ = ξ_i ⇒ ξ_i ≥ 0

1 − y_i(w^Tx_i + b) > 0 ⇒ y_i(w^Tx_i + b) = 1 − ξ_i

1 − y_i(w^Tx_i + b) ≤ 0 ⇒ xi_i = 0, y_i(w^Tx_i + b) ≥ 1 − ξ_i

所以等价优化问题可写为:

若取 ,则

合页损失函数的图形如下图，横轴是函数间隔，纵轴是损失。由于函数形状像一个合页，故名合页函数。

图中还花出0-1损失函数，可以认为它是二分类问题的真正的损失函数，而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的，直接优化其构成的目标函数比较困难，可以认为线性2支持向量机是优化由0-1损失函数的上界(合页损失函数)构成的目标函数。这时的上界损失函数又成为代理损失函数(surrogate loss function)。

图中虚线显示的是感知机的损失函数 [−y_i(w^Tx_i + b)]₊ .这时，当样本点 (x_i, y_i) 被正确分类时，损失是0，否则损失是 −y_i(w^Tx_i + b) .相比之下，合页损失函数不仅要分类正确，而且确信度足够高时损失才是0.也就是合页损失函数对学习有更高要求。

2.3 非线性支持向量机与核函数

对于线性分类问题，线性分类支持向量机是一种十分有效的方法。但，有时分类问题是非线性的，这时就得使用非线性支持向量机，其主要特点是利用核技巧(kernel trick).

2.3.1 核技巧

如上图可见，对于非线性分类问题无法用直线将正负例正确分离，但可以用一条椭圆曲线将它们正确分开。同样也可以通过将数据映射到高维空间，使正负样例变的线性可分。具体来说，在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。

设原空间为 $,x=(x^{(1)},x{(2)}) ,z=(z^{(1)},z{(2)}) $ ，定义从原空间到新空间的变换(映射)：

z = ϕ(x) = ((x⁽¹⁾)², (x⁽²⁾)²)^T

经过变换 z = ϕ(x) ,原空间 ,变换为新空间 ,原空间中的点相应地变换为新空间中的点，原空间中的椭圆

w₁(x⁽¹⁾)² + w₂(x⁽²⁾)² + b = 0

变换为新空间中的直线

w₁z⁽¹⁾ + w₂z⁽²⁾ + b = 0

这样，原空间的非线性可分问题就变成了新空间的线性可分问题。

可知，用线性分类方法求解非线性分类问题可以分为两步（核技巧）：

1.用一个变换将原空间的数据映射到新空间；

2.在新空间里用线性分类学习方法从训练数据中学习分类模型。

核技巧应用到支持向量机，就是通过一个非线性变换将输入空间（欧氏空间 Rⁿ 或离散集合）对应于一个特征空间（希伯特空间 ℋ ）,使得在输入空间中的超取面模型对应于特征空间中的超平面模型。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。

核函数

通过映射函数可以将对偶问题的目标函数转化为：

这样拿到非线性数据，就找一个映射 ϕ(⋅) ，然后把原来的数据映射到新空间中，再做线性 SVM 即可.但是，假设我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这样 ϕ(⋅) 的计算就非常困难。下面讨论如何解决这种问题。

设两个向量 x₁ = (η₁, η₂)^T, x₂(ξ₁, ξ₂)^T , 则通过映射后的内积为:

⟨ϕ(x₁), ϕ(x₂)⟩ = ⟨(η₁, η₁², η₂, η₂², η₁η₂)^T, (ξ₁, ξ₁², ξ₂, ξ₂², ξ₁ξ₂)^T, ⟩ = η₁ξ₁ + η₁²ξ₁² + η₂ξ₂ + η₂²ξ₂² + η₁η₂ξ₁ξ₂

另外:

(⟨x₁, x₂⟩ + 1)² = 2η₁ξ₁ + η₁²ξ₁² + η₂ξ₂ + η₂²ξ₂² + 2η₁η₂ξ₁ξ₂ + 1

我们可以通过把映射函数的某几个维度线性缩放，然后加上一个常数维度， 使得 ⟨ϕ(x₁), ϕ(x₂)⟩ 的结果和 (⟨x₁, x₂⟩ + 1)² 相同，该映射为:

这样一来我们就可以将映射到高维空间中，然后计算内积，改为直接在原来的地位空间中进行计算，而不需要显示地写出映射后的结果。

这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (Kernel Function)，记为 k(x, z).

刚才的例子中，核函数为:

k(x₁, x₂) = (⟨x₁, x₂⟩ + 1)²

继而将对偶问题的目标函数转化为：

这样就避开了直接在高维空间中进行计算内积，简化了计算。在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。

2.3.2 正定核

在已知映射函数 ϕ ，可以通过 ϕ(x) 和 ϕ(z) 的内积求得核函数 K(x, z) .在不用构造映射 ϕ(x) 能否判断一个给定的函数是不是 K(x, z) 是不是核函数？接下来就来说明这个问题。

给定 m 个训练样本

{x⁽¹⁾, x⁽²⁾, ⋯, x^(m)}

每个 x⁽ⁱ⁾ 对应一个特征向量，并且假设 K(x, z) 为一个有效的核函数，我们可以计算 K_ij = K(x⁽ⁱ⁾, x^(j)), i, j = 1, 2, ⋯, m ,这样我们可以计算出 m * m 的核函数矩阵 K (Kernel Matrix).

由以上可知，矩阵 K 为对称矩阵。即

K_ij = K(x⁽ⁱ⁾, x^(j)) = ⟨ϕ(x⁽ⁱ⁾), ϕ(x^(j))⟩ = ⟨ϕ(x^(j)), ϕ(x⁽ⁱ⁾)⟩ = k_ji

首先使用 ϕ_k(x) 表示映射函数 ϕ(x) 的第 k 维属性值。那么对任意向量 z, 有

上述推导说明，核函数矩阵 K 是半正定的 ( K ≥ 0 ).即， K(x, z) 是有效核函数，可推出核函数矩阵 K 是对称半正定的。

正定核充要条件:

设 K : 𝒳 × 𝒳 → ℝ 是对称函数.则 K(x, z) 为正定核的充要条件是，对任意 x_i ∈ 𝒳, i = 1, 2, ⋯, m ，K(x, z) 对应的核函数矩阵 K 是对称半正定的. ( 𝒳 为欧式空间 Rⁿ 的子集或离散集合)

必要性已经证过，下面来说明充分性。

充分性:

1.定义映射，构成向量空间 S

定义映射为: ϕ : x → K(⋅, x)

根据映射，对任意 x_i ∈ 𝒳, α_i ∈ R, i = 1, 2, ⋯, m ,定义线性组合

由线性组合为元素的集合 S 对加法和数乘运算是封闭的，所以 S 构成一个向量空间。

2.在 S 上定义内积，使其成为内积空间

在 S 上定义一个运算 * : 对任意 f, g ∈ S

定义运算 *

证明运算 * 是空间 S 的内积，需要证:

(1)(cf) * g = c(f * g), c ∈ R

(2)(f + g) * h = f * h + g * h, h ∈ S

(3)f * g = g * f

(4)f * f ≥ 0, f * f = 0 ⇔ f = 0

其中1-3有上述假设和 K(x, z) 的对称性容易得到，现在只需证4

由核矩阵 K 的半正定性可知上式非负，即 f * f ≥ 0 .

接着证 f * f = 0 ⇔ f = 0

充分性：当 f = 0 时，显然有 f * f = 0 .

必要性：首先证

|f * g|² ≤ (f * f)(g * g)

设 f, g ∈ S , λ ∈ R ,则 f + λg ∈ S ,则有

(f + λg) * (f + λg) ≥ 0

f * f + 2λ(f * g) + λ²(g * g) ≥ 0

上式为 λ 的二次三项式，非负，则其判别式小于等于0，即

(f * g)² − (f * f)(g * g) ≤ 0

设

则有

于是

|f(x)|² = |K(⋅, x) * f|²

根据上述证明的不等式可得

|K(⋅, x) * f|² ≤ (K(⋅, x) * K(⋅, x))(f * f) = K(x, x)(f * f)

上式表明，当 f * f = 0 时，对任意 x 都有

|f(x)| = 0

以上可说明 * 运算就是向量空间 S 的内积运算，仍然可用 • 表示。赋予内积的向量空间为内积空间。

3.将内积空间 S 完备化为希尔伯特空间

由内积的定义可以得到范数

这样， S 就是一个赋范向量空间。根据泛函分析理论，对于不完备的赋范向量空间 S ,一定可以使之完备化，得到完备的赋范向量空间 ℋ ,同时又是内积空间，这就是希尔伯特空间。

这一希尔伯特空间 ℋ 称为再生核希伯特空间(Reproducing Kernel Hilbert Space, RKHS).这是由于核 K 具有再生性，即满足

K(⋅, x) ⋅ f = f(x)

及

K(⋅, x) ⋅ K(⋅, z) = K(x, z)

称为再生核。

通过上述过程可得

K(x, z) = ϕ(x) ⋅ ϕ(z)

表明 K(x, z) 为 𝒳 × 𝒳 上的核函数。

2.3.3 常用核函数

通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数），常用核函数有以下几种：

1.多项式核函数(Polynomial Kernel Function)

K(x, z) = (⟨x, z⟩ + R)^d

显然刚才我们上述举的例子是这里多项式核的一个特例( R = 1，d = 2 )。虽然比较麻烦，而且没有必要，不过这个核所对应的映射实际上是可以写出来的，该空间的维度是 ,其中 m 是原始空间的维度。

2.高斯核函数(Gaussian Kernel Function)

这个核会将原始空间映射为无穷维空间。不过，如果 σ 选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果 σ 选得很小，则可以将任意的数据映射为线性可分——当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数 σ ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间：

3.线性核核函数(Linear Kernel Function)

K(x, z) = ⟨x, z⟩

这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了。

2.3.4 非线性支持向量分类机

1. 选取适当的核函数 K(x, z) 和适当参数 C ,构造并求解最优化问题

求最优解α^* = (α₁^*, α₂^*, ⋯, α_N^*)^T.

2. 选择 α^* 的一个正分量 0 < α_i < C ,计算

(3)构造决策函数

2.4 序列最小最优化算法

支持向量机的学习问题可以形式化为求解凸二次规划问题，这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当数据量非常大使，这些算法往往非常低效。序列最小最优化(Sequential Minimal Optimization, SMO)算法就是一种比较高效的解决支持向量机的算法。

SMO算法要解如下凸二次规划的对偶问题：

其中变量是拉格朗日乘子，一个变量 α_i 对应于一个样本点 (x_i, y_i) ;变量总数等于训练样本容量 N .

SMO算法是一种启发式算法，其基本思路是:如果所有变量的解都满足此最优化问题的 KKT 条件，那么 这个最优化问题就解决了。否则，选择两个变量固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题，因为这会使得原始二次规划问题的目标函数值变的更新，并且这个子问题可以通过解析方法求解从而大大提高整个算法的计算速度，子问题的两个变量，一个是违反 KKT 条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并将子问题求解，进而达到求解原问题的目的。

子问题中只有一个是自由变量，假设 α₁, α₂ 为两个变量， α₃, α₄, ⋯, α_N 固定，那么有等式约束可得

如果 α₂ 确定，那么 α₁ 也随之确定。所以子问题中同时更新两个变量。

整个SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。

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

假设 α₁, α₂ 为两个变量， α₃, α₄, ⋯, α_N 固定，则SMO的最优化问题的子问题可以写成

其中， K_ij = K(x_i, x_j), i, j = 1, 2, ⋯, N , 𝜍 是常数，目标函数省略了不含 α₁, α₂ 的常数项。

不等式约束 0 ≤ α_i ≤ C 使得( α₁, α₂ )在 [0, C] × [0, C] 内；等式约束 α₁y₁ + α₂y₂ = 𝜍 其中 y₁, y₂ 取值为1或-1，因此有，

y₁ ≠ y₂ ⇒ α₁ − α₂ = k

y₁ = y₂ ⇒ α₁ + α₂ = k

因此要求的目标函数其实是在一条平行于对角线段上的最优值，如下图。这使得两个变量的最优化问题成为实质上的单变量的最优化问题，不妨考虑为变量 α₂ 的最优化问题。

设 α₁^old, α₂^old 为初始可行解，最优解为 α₁^new, α₂^new ，并假设在沿着约束方向未经剪辑是 α₂ 的最优解为 α₂^new, unc .

α₂^new 必须满足约束条件，则 α₂^new 的取值范围为

L ≤ α₂^new ≤ H

其中， L 与 H 是 α₂^new 所在对角线端点的界，由上图可得：

令

当 i = 1, 2 时， E_i 为函数 g(x) 对输入 x_i 的预测值与真实输出 y_i 之差。

定理

最优化问研着约束方向未经剪辑时(不考虑不等式约束)的解是

其中，

η = K₁₁ + K₂₂ − 2K₁₂ = ∥Φ(x₁) − Φ(x₂)∥²

Φ(x) 是输入空间到特征空间的映射。

经剪辑后 α₂ 的解是

由 α₂^new 求得 α₁^new

α₁^new = α₁^old + y₁y₂(α₂^old − α₂^new)

证明

引进记号

目标函数可写成

由 α₁y₁ = 𝜍 − α₂y₂ ,及 y_i² = 1 ,可得

α₁ = (𝜍 − α₂y₂)y₁

代入目标函数得

对 α₂ 求导

令其为0，得到

将 α₁y₁ + α₂y₂ = 𝜍 代入，得到

将 η = K₁₁ + K₂₂ − 2K₁₂ 代入，得

要使其满足不等式约束必须将其限制在区间 [L, H] ,从而得到 α₂^new 的表达式，继而得到 α₁^new .

2.4.2 变量的选择方法

SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反 KKT 条件的。

1. 第一个变量的选择

SMO称第一个变量的选择过程为外层循环，外层循环在训练样本中选取违背 KKT 条件的样本点，并将其对应的变量作为第一个变量。检验训练样本点 (x_i, y_i) 是否满足 KKT 条件，即

α_i = 0 ⇔ y_ig(x_i) ≥ 1

0 < α_i < C ⇔ y_ig(x_i) = 1

α_i = C ⇔ y_ig(x_i) ≤ 1

其中， .

该检验是在 ε 范围内进行的。在检验过程中外层循环先遍历所有满足条件 0 < α_i < C 的样本点，即在间隔边界上的支持向量点，检验它们是否满足 KKT 条件。如果这些样本点都满足 KKT 条件，那么遍历整个训练集，检验它们是否满足 KKT 条件。

2. 第二个变量的选择

SMO称第二个变量的选择过程为内层循环。假设在外层循环中已经找到第一个变量 α₁ ，现在要在内层循环找第二个变量 α₂ .第二个变量的选择标准是希望能使 α₂ 有足够大变化。

α₂^new 是依赖于| E₁ − E₂ |的，为了加快计算速度，一种简单的做法是选择 α₂ ，使其对应的| E₁ − E₂ |最大。因为 α₁ 已定， E₁ 也确定了，如果 E₁ 是正的，那么选择最小的 E_i 作为 E₂ ;如果 E₁ 是负的，那么选择最大的 E_i 作为 E₂ 。为了节省计算时间，将所有 E_i 值保存在一个列表中。

在特殊情况下，如果内层循环通过以上方法选择的 α₂ 不能使目标函数有足够的下降，那么采用以下启发式规则继续选择 α₂ .遍历在将边界上的支持向量点，依次将其对应的变量最为 α₂ 试用，知道目标函数有足够的下降。若找不到合适的 α₂ ，那么遍历训练数据集；若仍找不到合适的 α₂ ,则放弃第一个 α₁ ,再通过外层循环寻求另外的 α₁ .

2. 计算阈值 b 和差值 E_i

在每次完成两个变量优化后，都要重新计算阈值 b 。当 0 < α₁^new < C 时，由 KKT 条件可知:

于是，

由 E₁ 定义式，有

于是 b₁^new 的前两项可写成

可得

b₁^new = −E₁ − y₁K₁₁(α₁^new − α₁^old) − y₂K₂₁(α₂^new − α₂^old) + b^old

同样，如果 0 < α₂^new < C ,那么，

b₂^new = −E₂ − y₁K₁₂(α₁^new − α₁^old) − y₂K₂₂(α₂^new − α₂^old) + b^old

如果 α₁^new , α₂^new 同时满足条件 0 < α_i^new < C, i = 1, 2 ,那么 b₁^new = b₂^new .如果 α₁^new , α₂^new 是0 或 C .那么 b₁^new, b₂^new 以及它们之间的数都是符合 KKT 条件的阈值，这是选择它们的中间点作为 b^new .

在每次完成两个变量的优化之后，还必须更新对应的 E_i 值，并将它们保存在列表中。 E_i 值得更新要用到 b^new 值，以及所有支持向量对应的 α_j :

E_i^new = ∑_Sy_jα_jK(x_i, x_j) + b^new − y_i

其中， S 是所有支持向量 x_j 的集合。

2.4.2 SMO算法流程

输入：训练数据集

T = {(x₁, y₁), (x₁, y₁), ⋯, (x_N, y_N)}

其中 ,精度 ε ;

输出：近似解 α̂ .

(1)取初值 α⁽⁰⁾ = 0, k = 0 ;

(2)选取优化变量 α₁^(k), α₂^(k) ,解析求解两个变量的最优化问题，求得最优解 α₁^(k + 1), α₂^(k + 1) ,更新 α = α^(k + 1) ;

(3)若在精度 ε 范围内满足停机条件

0 ≤ α_i ≤ C,    i = 1, 2, ⋯, N

其中, .则转(4);否则令 k = k + 1 ,转(2);

(4)取 α̂ = α^(k + 1)

参考

1. 周志华 《机器学习》
2. 支持向量机：Duality
3. 拉格朗日对偶
4. 约束优化方法之拉格朗日乘子法与KKT条件
5. 话说泛函——Hilbert空间
6. 向量空间 内积空间 线性空间 欧氏空间 希尔伯特空间
7. 支持向量机通俗导论（理解SVM的三层境界）
8. SVM学习——核函数
9. SVM（三），支持向量机，线性不可分和核函数
10. 支持向量机系列
11. 再生核希尔伯特空间（RKHS）和核函数
12. A Story of Basis and Kernel - Part II: Reproducing Kernel Hilbert Space
13. 支持向量机（三）核函数
14. 【机器学习详解】SMO算法剖析