第一次听说svm这个东西的时候，我还只有大一，在夏天的午后听张老师不厌其烦至少讲了三遍svm的推导，然后我还是不会……转眼要毕业了，最近看了台大林老师的视频课程，终于基本弄明白了整个推导过程，仅此记录一下。文章比较跳跃，省去了基本的背景信息，只有一些核心的推导思路，供自己以后再次忘记了的时候回来看看，这也是人生第一篇技术类的博客，哈哈。

线性svm

问题描述

假设已有训练样本为$(X, \vec y)$, 线性svm的目标即为寻找超平面$y = w^T + b$，使得所有样本到超平面的最小距离(margin)最大，即
$$ \max \min_{i=1,2,…,n} d_i $$

首先我们来计算任意一点 x 至超平面$y = w^T + b$的距离，作x至超平面的垂线，记垂足为$x_0$， 则 $d \frac{w}{||w||}= \vec x - \vec x_0$。 对此式两边乘上 $w^T$，可得：
$$
w^Tx - w^Tx_0 = d \frac{ww^T}{||w||}
$$

又点$x_0$在超平面上，有$w^Tx_0 + b =0 $，代入上式，即解得距离d的长度为：
$$
d = \frac{||w^Tx + b||}{||w||}
$$

考虑到绝对值符号不利于最值问题的求解，我们对该优化问题做一些变形。注意到所有的样本中的$y_n = 1$, 并且当超平面划分正确时，必有 $y_n(w^T + b) > 0 $.故我们可以以此代替上式中的绝对值部分。于是我们的优化问题可以等价为：

$$\begin{multline*} \max_{b,w} margin(b,w) \\\ s.t. y_n(w^Tx_n + b) > 0, margin(b,w) = \min_{i} \frac{y_n(w^Tx_n + b)}{||w||} \end{multline*}$$

问题简化

以上这个优化问题依旧是不好解决的，主要原因在于我们的边界，margin是不确定的。考虑到我们对于所有的样本，只关心他们相对于超平面的实际距离，而并不关心其相对的函数距离，我们不妨假设最小的函数距离永远为1，后面我们将说明即使最小的距离不为1，并不会影响最优解情况下w与b的值。即若$\min y_n(w^Tx+b) = 1$，优化问题变为：

$$\begin{multline*} \max_{b,w} \frac{1}{||w||} \qquad s.t. y_n(w^Tx_n + b) \ge 1, \quad \min_{i} \frac{y_n(w^Tx_n + b)}{||w||} = \frac{1}{||w||} \end{multline*}$$

若$\min y_n(w^Tx+b) = d$，其中d不为1，则$margin(b,w) = \frac{d}{||w||}$，优化问题变为

$$\begin{multline*} \max_{b,w} \frac{d}{||w||} \qquad s.t. y_n(w^Tx_n + b) \ge d, \quad \min_{i} \frac{y_n(w^Tx_n + b)}{||w||} = \frac{d}{||w||} \end{multline*}$$

只要令 $w = dw, b = db$，代入上式就可以得到和最小距离为1时完全相同的目标问题，从而不影响后续的求解工作。从几何上看，相当于我们对所有问题都进行了缩放，直至其距离超平面的距离变为一个恰当距离为止。

求解

为了方便求解，我们对该问题做一个等价的变换，

$$\begin{equation} \min_{b,w} \frac{1}{2} w^Tw \qquad s.t. y_n(w^Tx_n + b) \ge 1 \end{equation}$$

注意到我们一共修改了两处，第一将求最大值变为求最小值，并恰好讲w从分母移至分子位置，从而方便后续的求导求最值工作。第二，我们将$\min y_n(w^Tx_n + b) = 1$ 改为了 $y_n(w^Tx_n + b) \ge 1$, 这样的修改看起来弱化了约束条件，有可能使得得到的最优解不符合原始的约束条件。但正如上一节中讨论最小函数距离不为1的情况一样，对于解得的参数，若不符合等号条件只需进行简单的放缩，即可保证其正确性。

观察可以发现，上式是一个线性的二次规划问题，共有d维特征，d+1个变量（w有d维，b一维），当我们解得最优解w，b后，只需将新的样本代入决策函数 $g_{svm} = w^Tx + b$即可判断其类别。

利用二次规划求解，只需方程组符合形式

$$ min_n \dfrac{1}{2}u^TQu + P^Tu \qquad s.t. \quad a_m^Tu \ge c_m $$

此处 $u = [w,b]$， Q,P分别为u的二次项系数与一次项系数，至此随意采用一个现成的二次规划求解函数，即可得到线性svm问题的最优解。

非线性svm

问题起因

在上文中我们解决了线性可分情况下的svm问题，在这一节里我将描述一下求解线性不可分情况下的做法。直观而言，我们的思路是将原始的数据点映射至高维空间中(甚至无限维)，直至在高维空间中找到可以线性分割样本点的超平面，并对新的数据进行分类。数学描述即：

对于映射 $\phi: \quad d \to \tilde{d}\quad$ 有 $z_n = \phi(x_n)$， 这里的映射$\phi$也可以成为核函数，即kernel，我们的svm优化问题将转化为：

$$\begin{equation} \min_{b,w} \frac{1}{2} w^Tw \qquad s.t. y_n(w^Tz_n + b) \ge 1 \end{equation}$$

随后我们仍可如法炮制，使用二次规划问题求解的方法替我们找到最优的w与b，对于新样本x，首先计算其在高维空间中的映射$\phi(x)$，随后利用决策函数即可判断其类别，看起来我们至此已经解决了非线性svm的问题。

然而，这样的求解有一个巨大的隐患，观察可以发现，上述二次规划问题的参数数量取决于$z_n$的维度即$\tilde{d}$的大小。当我们使用的训练集较多或特征数量较多是时，我们必须将原始数据集映射到更高维度的空间中，这样将导致$\tilde{d}$变得相当大，这对最优解的求解是相当不利的，所以我们希望再次寻找一个和原问题等价的优化问题，使优化求解时变量的数目不依赖于高维空间的维度，而只依赖于训练样本特征的维度，这就是非线性svm问题中需要解决的问题。这里我们用到的方法是构造拉格朗日对偶问题。

Lagrange Dual

构造对偶问题我们采用拉格朗日乘数法，即构造拉格朗日方程

$$
L(b,w,\alpha) = \frac{1}{2}w^Tw + \sum_n\alpha_n(1-y_n(w^Tz_n + b)), \alpha_n > 0
$$

注意到这里，我们将原问题的约束条件作为一部分，放入了待求解的式子中，并用一组非负参数$\alpha_n$(一般Lagrange问题中会采用$\lambda$)来控制其变化，则SVM问题可以被转化为等价问题：

$$ SVM = \min_{b,w} \max_n L(w,b,\alpha_n)$$

等价性由lagrange乘数法得以保证(我们也可以简单的验证其正确性，待补充)

求解

上面的问题中，内层的最大化问题依旧不好求解，因为我们无法确定所有参数$\alpha$的值，然而先求外层的最小值我们则有较好的方案，所以我们考虑以下事实：

$$\begin{equation} SVM = \min_{b,w} \max_n L(w,b,\alpha_n) \ge \max_n \min_{b,w} L(w,b,\alpha_{n}) \end{equation}$$

注意到右边的问题是左边问题的弱化，而事实上两者的最优解将是相同的，在此处略去证明，因为我没看懂。。我们下面直接求解右侧问题的最优解，代入得到：

$$\begin{equation} \max_{\alpha_n \ge 0} \min_{b,w}(\frac{1}{2}w^Tw + \sum_n \alpha_n(1-y_n(w^Tz_n + b))) \end{equation}$$

里层的最小化问题就是一个标准的拉格朗日乘数法可以解决的问题，当其取到最优解时，必有其在各个参数上的偏导数为0，即：$\dfrac{\partial L}{\partial w_n} = 0 \quad \dfrac{\partial L}{\partial b} = 0$ 求解这两个等式后代入原来的不等式中，有：

$$ \dfrac{\partial L}{\partial b} = -\sum_n \alpha_n y_n = 0$$

代入原式，有：

$$\begin{equation} \max_{\sum_n \alpha_n y_n = 0, \alpha_n \ge 0} \min_{b,w}(\frac{1}{2}w^Tw + \sum_n \alpha_n(1-y_nw^Tz_n )) \end{equation}$$

进一步考虑在w方向上的偏导数，

$$\begin{align*} \dfrac{\partial L}{\partial w_i} = w_i - \sum_n \alpha_n y_n z_{n,i}= 0\\\ 即 \quad w = \sum_n \alpha_ny_nz_n \end{align*}$$

再次代入原式后，不等式退化为：

$$\begin{align} \max_{\sum_n \alpha_n y_n = 0, \alpha_n \ge 0， w = \sum_n \alpha_ny_nz_n} (-\frac{1}{2}w^Tw + \sum_n \alpha_n) = \\\ \max_{\sum_n \alpha_n y_n = 0, \alpha_n \ge 0， w = \sum_n \alpha_ny_nz_n} (-\frac{1}{2}||\sum_n \alpha_n y_n z_n||^2 + \sum_n \alpha_n) \end{align}$$

在这一系列变换中，所有的参数必须符合一系列约束条件，这一系列约束条件就被称为KKT条件，具体如下：

1. $y_n(w^Tx_n + b) \ge 1$
2. $\alpha_n \ge 0$
3. $\sum_n \alpha_ny_n = 0, w = \sum_n \alpha_ny_nz_n$
4. $\alpha_n(1-y_n(w^Tz_n+b))$

当一组训练集以及我们寻找的超平面符合以上一组KKT条件时，我们就可以将原来的svm问题转化为如上的拉格朗日对偶问题，随后我们就可以利用同样利用二次规划方法进行求解。

solve.

$$\begin{align} \min_{\alpha_n}(\frac{1}{2}||\sum_n \alpha_n y_n z_n||^2 - \sum_n \alpha_n) \\\ s.t. \sum y_n\alpha_n = 0, \alpha_n \ge 0 \\\ 这里就可以运用二次规划问题，对于二次系数和一次项系数 Q,P \\\ q_{n,m} = y_n y_m z_n z_m, p_n = -1 \end{align}$$

此时我们可以发现，矩阵Q,P都是N维矩阵(N为训练样本的特征维度)，即我们的二次规划问题共有N个变量以及N+1个约束条件，已经与高维空间的维数$\tilde{d}$无关了，至此我们就已经解决了非线性的SVM问题。

Kernel

我们再来回头观察一下svm中的核函数的概念，当我们利用核函数将样本映射至高维划分时，大致经过了一下三个步骤：

1. 计算$z_n = \phi(x_n)$
2. 对$z_n$进行求解，找到最优情况下的参数w,b
3. $\phi(x{new}) = z{new}, g{svm}(z{new})$

在这当我们在优化时计算二次系数矩阵Q时，需要在$\tilde{d}$中进行N次内积运算，这个过程将会很大的影响我们求解最优解的过程，而事实上，我们可以通过巧妙的选取$\phi$函数，来避免在高维空间中的内积运算。

多项式内核

我们先随意的选取一个二次多项式核函数，

$$\phi_2(x) = (1,x_1,x_2,…,x_n,x_1^2,x_1,x_2,…,x_n^2)$$

当我们在在映射后的空间中计算内积时：

$$\begin{align} Kernel = \phi_2(x)\phi_2(x') = 1 + \sum_{i=1}^n x_i x_i' + \sum_{i=1}^n \sum_{j=1}^n x_ix_jx_i'x_j' = 1 + x^Tx' + (x^Tx')^2 \end{align}$$

即：
$$K_{\phi_2}(x,x’) = \phi(x)^T \phi(x’)$$

故当我们利用二次规划程序寻找最优解时，只要取$q{n,m} = y_n y_m k{\phi}(x_n, x_m)$即可

当对新样本进行分类时

$$\begin{align} g_{svm}(w^T\phi(x)+b) = g_{svm}(\sum_n \alpha_n y_n \phi(x_n) \phi(x) +b) = sign(\sum_n \alpha_n y_n k_{\phi}(x_n,x) + b) \end{align}$$

至此，通过合理的选择核函数，我们的求解过程中不再需要在$\tilde{d}$维空间中进行内积运算，算法复杂度为$o(N^2)$

高斯核

高斯核又称为rbf核（一般机器学习库中会使用这个名字作为参数），它比多项式核更进一步，将原始数据映射至无限维空间中进行分割，其形式为：

$$k(x,x’) = exp(-\gamma ||x-x’||^2), \quad \gamma \ge 0$$

下面我们取$\gamma = 1$来说明一下其合理性：

$$\begin{align} k(x,x') = exp(-\gamma ||x-x'||^2) = exp(-x^2) exp(-x'^2) exp(2xx')\\\ = exp(-x^2) exp(-x'^2) (1 + \frac{2xx'}{2!} + \frac{(2xx')^2}{2!} +...+\frac{(2xx')^i}{i!} + ...) \\\ = \sum_i ((exp(-x^2) \sqrt{\frac{2!}{i!}x}) (exp(-x'^2) \sqrt{\frac{2!}{i!}x'})\\\ = \phi(x)^T \phi(x') \end{align}$$

这就是高斯核的基本形式，实际计算时，我们不必考虑其真正的高维空间维度，这使得我们可以很好的分割输入的数据点。