CS229 笔记 08
Kernel
回顾之前的优化问题
原始问题为：
$$ \min_{w,b} \frac{1}{2}||w||^2\\[1.5em] {\text{s.t.}}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq1 $$原始问题的对偶问题为：
$$ \max_{\alpha}\left\{ \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j}^m y{(i)} y^{(j)}\alpha_i \alpha_j \left\langle x^{(i)}, x^{(j)} \right\rangle \right\}\\[2em] \begin{eqnarray*} {\text{s.t.}}\alpha_i&\geq&0\\[1em] \sum_{i=0}^my^{(i)}\alpha_i&=&0 \end{eqnarray*} $$求解出对偶问题得到 $\alpha_i$ 后，代入以下等式可求出 $w$ ：
$$ w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} $$模型训练完成之后的预测函数 $h_{w,b}(x)$ 为：
$$ \begin{eqnarray*} h_{w,b}(x)&=&g(w^{\rm T}x+b)\\[1em] &=&g\left(\sum_{i=1}^m\alpha_iy^{(i)}\left\langle x^{(i)},x\right\rangle+b\right) \end{eqnarray*} $$Kernel（核函数）
之前讨论的分类问题都是假设训练样本数据是线性可分的，而若样本线性不可分，则需要将样本（向量）从低维空间映射到高维空间，因为在低维空间线性不可分的样本，很有可能在高维空间线性可分。
假设从低维空间到高维空间的映射为 $\phi: {\Bbb R}^a \to {\Bbb R}^b$ ，其中 $b>a$ ，那么在之前讨论中所有出现 $\left\langle x^{(i)},x^{(j)} \right\rangle$ 内积的地方都可以替换成 $\left\langle \phi\left(x^{(i)}\right),\phi\left(x^{(j)}\right) \right\rangle$ 。
这样替换会有两个问题，第一是如何找到这样的将向量从低维空间转化到高维空间的映射，第二是映射之后的向量的维数很大，甚至是无限维的，这样计算内积的效率很低。
如果可以不把高维的向量算出来，也能知道两个向量在高维空间中的内积（或者等同于内积的量），就方便很多了。而 Kernel（核函数）在很多情况下就能达到这样的效果。
这种思想的目标是，找到这样的函数 $K$ ，使得：
$$ K(x^{(i)},x^{(j)})=\left\langle \phi\left(x^{(i)}\right),\phi\left(x^{(j)}\right) \right\rangle $$一些常见的核函数
多项式核函数，映射之后的向量维数为组合数 $C(n+d,d)$ ：
$$ K(x,z)=\left(x^{\rm T}z+c\right)^d $$高斯核函数（径向基函数核，Radial basis function kernel，RBF 核），映射后的向量维数是无穷大：
$$ K(x,z)=\exp\left(-\frac{||x-z||^2}{2\sigma^2}\right) $$构造核函数的原则
对于内积的一个直观但不一定准确的理解是：若两个向量相似度高，即它们指向的方向大致相同，那么它们的内积将会很大；反之若两个向量相似度很小，那么内积会很小。
对于一个新的问题，在其中的两个向量内积的表示，可以用多项式核函数，可以用高斯核函数，也可以另外构造一个函数，至于如何选择，则需要考察一下核函数的合法性。判断一个核函数 $K$ 是否合法，也就是判断是否存在一个映射 $\phi$ ，使得 $K(x,z)=\left\langle\phi(x),\phi(z)\right\rangle$ 。
下面给出一个函数 $K$ 是一个合法的核函数的充要条件，在此之前需要定义一些记号：
设原始向量为：
$$ x^{(1)},x^{(2)},\cdots,x^{(m)} $$存在一个函数 $K$ ，令一个矩阵 $K \in {\Bbb R}^{m\times m}$（这里两个概念用了相同的字母表示）：
$$ K_{ij}=K(x^{(i)},x^{(j)}) $$那么函数 $K$ 是一个合法的核函数的充要条件是：矩阵 $K$ 是一个半正定矩阵。
必要性证明：
已知函数 $K$ 是一个合法的核函数，那么存在映射 $\phi$ ，使得 $K(x,z)=\left\langle\phi(x),\phi(z)\right\rangle$ 。
对于任意的 $z\in {\Bbb R}^{m}$ ：
$$ \begin{eqnarray*} z^{\rm T}Kz&=&\sum_{i=1}^m\sum_{j=1}^mz_iK_{ij}z_j\\[1em] &=&\sum_{i=1}^m\sum_{j=1}^mz_iK(x^{(i)},x^{(j)})z_j\\[1em] &=&\sum_{i=1}^m\sum_{j=1}^mz_i \left\langle\phi(x^{(i)}),\phi(x^{(j)})\right\rangle z_j\\[1em] &=&\sum_{i=1}^m\sum_{j=1}^mz_i \left(\phi(x^{(i)})\right)^{\rm T}\phi(x^{(j)}) z_j\\[1em] &=&\sum_{i=1}^m\sum_{j=1}^mz_i \left(\sum_{k=1}^{n}\phi(x^{(i)})_k\phi(x^{(j)})_k\right) z_j\\[1em] &=&\sum_{k=1}^{n}\sum_{i=1}^m\sum_{j=1}^m z_i \phi(x^{(i)})_k\phi(x^{(j)})_k z_j\\[1em] &=&\sum_{k=1}^{n}\left(\sum_{i=1}^mz_i \phi(x^{(i)})_k\right)\left(\sum_{j=1}^m z_j\phi(x^{(j)})_k\right)\\[1em] &=&\sum_{k=1}^{n}\left(\sum_{i=1}^mz_i \phi(x^{(i)})_k\right)^2\\[1em] &\geq&0 \end{eqnarray*} $$将核函数应用到 SVM 问题中
要将核函数应用到 SVM 问题中，只需要将对偶问题中出现的内积变成核函数值，这样就达到了将原始向量从低维空间映射到高维空间的目的。
Soft Margin
Soft Margin SVM（软间隔 SVM）
在很多情况下，训练样本并不一定是线性可分的，即使映射到无限维空间中也是这样。其中的原因可能是因为噪声，也可能是数据本身的性质就是如此。同时，即使数据能够线性可分，我们在大多数情况下也不希望其中的少量噪声影响我们超平面最终的选择，所以有必要提出一种 Soft Margin SVM（软间隔 SVM）。
再回忆一下 SVM 的原始问题：
$$ \min_{w,b} \frac{1}{2}||w||^2\\[1.5em] {\text{s.t.}}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq1 $$现在将原始问题进行改造：
$$ \min_{w,b,\xi} \frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i\\[1.5em] {\text{s.t.}}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq1-\xi_i\\[1.5em] \xi_i\geq0 $$有之前的讨论可知，当 $y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq0$ 时，表示分类结果正确。
现在不等式右边变成了 $1-\xi_i$ ，表示某些 $\xi_i$ 的取值可以让不等式的右面小于 0，即可以容忍某一些样本的分类结果是错误的。
但是这样的容忍并不值得鼓励，所以需要在目标优化函数上面加上相应的惩罚项 $C\sum_{i=1}^{m}\xi_i$ 。
所以原始的最优化问题就转化成了一个新的最优化问题，这也是一个凸优化问题，这个问题也可以推导出它的对偶问题。
拉格朗日算子为：
$$ \begin{eqnarray*} &&{\mathcal L}(w,b,\xi,\alpha,r)\\[1em] &=&\frac{1}{2}\left\|w\right\|^2+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1+\xi_i\right]-\sum_{i=1}^mr_i\xi_i \end{eqnarray*} $$对偶问题为：
$$ \max_{w,b,\xi} {\mathcal L}(w,b,\xi,\alpha,r) $$对 $w$ 求导：
$$ \begin{eqnarray*} &&\frac{\partial}{\partial w}{\mathcal L}(w,b,\xi,\alpha,r)\\[1em] &=&\frac{\partial}{\partial w}\left\{\frac{1}{2}\left\|w\right\|^2+C\sum_{i=1}^{m}\xi_i \right. \\[1em] &&\left. -\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1+\xi_i\right]-\sum_{i=1}^mr_i\xi_i\right\}\\[1em] &=&w-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\xlongequal{set}0\\[1em] \therefore\,w&=&\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} \end{eqnarray*} $$对 $b$ 求导：
$$ \begin{eqnarray*} &&\frac{\partial}{\partial b}{\mathcal L}(w,b,\xi,\alpha,r)\\[1em] &=&\frac{\partial}{\partial b}\left\{\frac{1}{2}\left\|w\right\|^2+C\sum_{i=1}^{m}\xi_i \right. \\[1em] && \left. -\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1+\xi_i\right]-\sum_{i=1}^mr_i\xi_i\right\}\\[1em] &=&-\sum_{i=1}^m\alpha_iy^{(i)}\xlongequal{set}0\\[1em] \therefore\,\sum_{i=1}^m\alpha_iy^{(i)}&=&0 \end{eqnarray*} $$对 $\xi_i$ 求导：
$$ \begin{eqnarray*} &&\frac{\partial}{\partial \xi_i}{\mathcal L}(w,b,\xi,\alpha,r)\\[1em] &=&\frac{\partial}{\partial \xi_i}\left\{\frac{1}{2}\left\|w\right\|^2+C\sum_{i=1}^{m}\xi_i \right. \\[1em] && \left. -\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1+\xi_i\right]-\sum_{i=1}^mr_i\xi_i\right\}\\[1em] &=&C-\alpha_i-r_i\xlongequal{set}0\\[1em] \therefore\,\alpha_i&=&C-r_i\\[1em] \because\, r_i &\geq& 0\\[1em] \therefore\, \alpha_i&\leq&C \end{eqnarray*} $$最终得到的对偶问题为：
$$ \begin{eqnarray*} &&\max_{w,b}{\mathcal L}(w,b,\alpha)\\[1em] &=&\max_{w,b}\left\{\sum_{i=1}^m\alpha_i-\frac{1}{2}\left(\sum_{i,j}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle\right)\right\}\\[1em] &=&\max_{w,b}W(\alpha)\\[1em] {\text{s.t.}}&&0\leq\alpha_i\leq C\\[1em] &&\sum_{i=1}^m\alpha_iy^{(i)}=0\\[1em] \end{eqnarray*} $$
SMO Algorithm
Coordinate Ascent Algorithm（坐标上升法）
对于一个优化问题：
$$ \max W(\alpha_1,\alpha_2,\cdots,\alpha_m) $$选择其中一个参数，固定其它的参数，改变这个参数使得函数取得最优值，即：
$$ \begin{eqnarray*} &&{\text{Repeat \{}} \\ &&\,\,\,\,\,\,\,\,{\text{For i=0 to m}}\\ &&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\alpha_i:=\arg\max_{\hat\alpha_i} W(\alpha_1,\alpha_2,\cdots,\alpha_{i-1},\hat\alpha_{i},\alpha_{i+1},\cdots,\alpha_m)\\ &&{\text{\}}} \end{eqnarray*} $$这就是坐标上升法。
Sequential Minimal Optimization (SMO) Algorithm
考虑直接使用坐标上升法来解决 SVM 的对偶问题，由于约束 $\sum_{i=1}^m\alpha_iy^{(i)}=0$ 的存在，若每次只改变一个参数 $\alpha_i$ 且固定其它参数，那么这个参数也无法改变，因为要满足限制条件。
序列最小优化（SMO）算法可以用来求解以上的对偶最优化问题，它的主要思想是一次性改变数量尽可能少的参数。在这个问题中，可以是一次改变两个参数。
所以使用 SMO 算法来解决 SVM 的对偶问题的大致步骤为：利用一些启发式的方法，选择两个参数 $\alpha_i$ 和 $\alpha_j$ ，固定其它的参数，改变 $\alpha_i$ 和 $\alpha_j$ 使得 $W$ 最优化，同时要满足其它的约束。重复这个步骤，直到满足收敛条件。
现在的问题就是如何在满足其它约束的前提下，改变 $\alpha_i$ 和 $\alpha_j$ 使得 $W$ 最优化。
我们现在要优化的目标函数是：
$$ \begin{eqnarray*} &&W(\alpha_1,\alpha_2,\cdots,\alpha_m)\\[1em] &=&\sum_{i=1}^m\alpha_i-\frac{1}{2}\left(\sum_{i,j}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle\right) \end{eqnarray*} $$由于其中一个约束条件是： $\sum_{i=1}^m\alpha_iy^{(i)}=0$ ，对于任选的两个参数 $\alpha_i$ 和 $\alpha_j$ ，在其它参数固定的情况下，可以用 $\alpha_j$ 来表示 $\alpha_i$ ：
$$ \alpha_i=-\frac{1}{y^{(i)}}\left(y^{(j)}\alpha_j+\sum_{k\neq i,k\neq j}^my^{(k)}\alpha_k\right) $$如此一来函数 $W$ 就变成了 $\alpha_j$ 的二次函数（因为其它参数固定了，且 $\alpha_i$ 被 $\alpha_j$ 表示了），二次函数一定可以写成 $W=W(\alpha_j)=A\alpha_j^2+B\alpha_j+C$ 的形式。
总结起来，只需要在以下条件中找到最优值即可：
$$ \alpha_i=-\frac{1}{y^{(i)}}\left(y^{(j)}\alpha_j+\sum_{k\neq i,k\neq j}^my^{(k)}\alpha_k\right)\\[2em] W=W(\alpha_j)=A\alpha_j^2+B\alpha_j+C \\[1.5em] 0\leq\alpha_i\leq C\\[1.5em] 0\leq\alpha_i\leq C\\[1.5em] $$在这组约束中可以求出最优的 $\alpha_j$ ，进而可以求出 $\alpha_i$ ，更新 $\alpha_i$ 和 $\alpha_j$ ，继续按照一定策略寻找下一组可变参数，重复这个步骤，直到满足某个收敛条件。