此文是学习林轩田老师的机器学习技法第三课——Kernel Support Vector Machine——的课堂笔记。
给定上节课的公式：
$$
\min_{\alphan} (\frac{1}{2}\sum{m=1}^{N} \sum_{n=1}^{N} y_m y_n \mathbf{z_m^T} \mathbf{z_n} \alpha_m \alphan - \sum{n=1}^{N}\alpha_n) \\
s.t.\ all\ \alphan \ge 0,\ \sum{n=1}^N \alpha_n y_n = 0
$$
这里 $\mathbf{z}$ 是由 $\mathbf{x}$ 变换得到。在 $\mathbf{x}$ 向量所处的空间里，如果所有超平面都不能对数据进行分类，可以将 $\mathbf{x}$ 映射到高维空间，也就是 $\mathbf{x}$ 变换成 $\mathbf{z}$。这次课的目标包括：了解这种变换带来的求解问题，引入核函数、多项式核函数、高斯核函数，及了解如何选择核 SVM 或线性 SVM。
参考
求解复杂度
考虑将 $\mathbf{x}$ 从一次变换到二次：
$$\mathbf{x} = (x_1, x_2, …, x_d) \ \ \rightarrow \\
\mathbf{z} = (1, x_1, x_2, …, x_d, x_1 x_1, x_1 x_2, …, x_1 x_d, x_2 x_1, x_2 x_2, …, x_2 x_d, …, x_d x_d)$$
向量长度增加了 $d^2 + 1$，由于在求解公式中需要计算任意2个 $\mathbf{x}$ 的内积（$\mathbf{z_m^T z_n}$），计算复杂度从 $o(d^2)$ 增加到 $o(d^4)$，陡增了不少困难。而这仅是变换到二次的情况。
核函数
就 求解复杂度 一节所举一次变二次，有以下推导：
$$\mathbf{z^T z’} = 1 + \sum_{i=1}^d x_i x’i + \sum{i=1}^d \sum_{j=1}^d x_i x_j x’_i x’j \\
=1 + \sum{i=1}^d x_i x’i + (\sum{i=1}^d x_i x’i) (\sum{j=1}^d x_j x’_j) \\
=1 + \mathbf{x^T x’} + (\mathbf{x^T x’})(\mathbf{x^T x’})$$
可见任意2个 $\mathbf{w}$ 的内积（$\mathbf{z^T z’}$）可以用 $\mathbf{x}$ 的内积表示。这可以推广到更高次变换。
这种处理有何好处？复杂度大幅降低，从原来的 $o(d^4)$ 回降到 $o(d^2)$。
核函数
简单来说，核函数（核）应该是：
$$\mathbf{z^T z’} = K(\mathbf{x}, \mathbf{x’})$$
在一次变二次例子中 $K(\mathbf{x}, \mathbf{x’}) =1 + \mathbf{x^T x’} + (\mathbf{x^T x’})(\mathbf{x^T x’})$。
原求解公式变换为：
$$
\min_{\alphan} (\frac{1}{2}\sum{m=1}^{N} \sum_{n=1}^{N} y_m y_n K(\mathbf{x}_m, \mathbf{x}_n) \alpha_m \alphan - \sum{n=1}^{N}\alpha_n) \\
s.t.\ all\ \alphan \ge 0,\ \sum{n=1}^N \alpha_n y_n = 0
$$
设 $(\mathbf{x}_s, y_s)$ 为支持向量（$\alpha_s = 0$）解出 $b$:
$$
b = y_s - \mathbf{w^T \mathbf{z_s}} \\
= ys - (\sum{n=1}^{N} \alpha_n y_n \mathbf{z_n})^\mathbf{T} \mathbf{z}_s \\
= ys - \sum{n=1}^{N} \alpha_n y_n K(\mathbf{x}_n, \mathbf{x}s)
$$
求解 $\mathbf{w}$ 似乎有点复杂，但不影响最终分类。分类公式变换为
$$g{svm}(\mathbf{x}) = sign(\mathbf{w^T z} + b)
=sign(\sum_{n=1}^{N} \alpha_n y_n K(\mathbf{x}_n, \mathbf{x}) + b)$$
多项式核函数
$$K(\mathbf{x}, \mathbf{x’}) = (\zeta + \gamma \mathbf{x^T x’})^q,\ with\ \zeta \ge 0,\ \gamma \gt 0$$
例如，当 $q = 2$ 时，
$$\mathbf{z^T z’} = K(\mathbf{x}, \mathbf{x’}) =1 + 2\zeta\gamma\mathbf{x^T x’} + \gamma^2(\mathbf{x^T x’})^2 \\
\Rightarrow \mathbf{z} = (1, \sqrt{2\zeta\gamma}x_1, \sqrt{2\zeta\gamma}x_2, …, \sqrt{2\zeta\gamma}x_n, \gamma x_1 x_1, \gamma x_1 x_2, …, \gamma x_n x_n)$$
感觉这个核不能满足所有从 $\mathbf{x}$ 到 $\mathbf{z}$ 的多项式变换，比如 $\mathbf{z}$ 中至少所有一次项系数都相等（在上例中为 $\sqrt{2\zeta\gamma}$）。
高斯核函数
$$K(\mathbf{x}, \mathbf{x’}) = exp(-\gamma |\mathbf{x - x’}|^2),\ with\ \gamma \gt 0$$
高斯（Gaussian）核函数可以将 $\mathbf{x}$ 扩展到无限维。
课上只给了 $\gamma = 1,\ \mathbf{x} = (x)$（$\mathbf{x}$ 只有一个维度）时的推导：
$$K(\mathbf{x}, \mathbf{x’}) = exp(-(\mathbf{x - x’})^2) \\
=exp(-x^2)exp(-x’^2)exp(2xx’)\\
=exp(-(x)^2)exp(-(x’)^2) \sum{i=0}^\infty \frac{(2xx’)^i}{i!},\ \ taylor\ expansion \\
=\sum{i=0}^\infty(exp(-x^2)exp(-x’^2) \sqrt{\frac{2^i}{i!}} \sqrt{\frac{2^i}{i!}} x^i x’^i) \\
=\mathbf{z^T z’} \\
with\ \mathbf{z}=exp(-x^2)(1, \sqrt{\frac{2}{1!}} x, \sqrt{\frac{2^2}{2!}}x^2, …)
$$
如果 $\gamma$ 取值过大（方差过大），高斯核会过拟合。
核函数并非万能
线性 SVM 指原始的，$\mathbf{x}$ 未经变换的 SVM，求解相对多项式核 SVM 简单（系数矩阵为对角矩阵），而且，参数选择较少。而高斯核的模型难以解释，且容易过拟合。
对于高次的多项式 kernel，可以考虑用原始的方法，将 $\mathbf{x}$ 转化成 $\mathbf{z}$ 之后代入线性 SVM 求解，如果维度不高，求解速度会更快。
其他核函数
课上指出，能成为核函数的充要条件是，核函数导出的矩阵 $\mathbf{K}$，$k_{i,j}=K(\mathbf{x_i, x_j})$，是对称且半正定的。这2个条件被称为 Mercer’s condition。