第3讲机器学习（二）

支持向量机

最大间隔线性分类

支持向量机 SVM 是 Vapnik 在小样本统计学习理论基础上提出的方法。其三要素是：

策略上引入最大分类间隔；
模型上用核函数实现非线性建模；
算法上用带不等式约束的拉格朗日乘子法，可用 SMO 求解对偶问题，也可用神经网络架构和 Hinge Loss 优化。

SVM 直接拟合 \(P(Y\mid X)\) 对应的分类界面，是鉴别式模型；生成式模型则估计 \(P(X,Y)\)。

给定训练样本 \((x_i,y_i)\)，\(y_i\in\{+1,-1\}\)，线性分类面为

\[ w^Tx+b=0. \]

同一分类面可由成比例的 \(w,b\) 表示，因此可调整尺度，使两类离分类面最近的样本满足

\[ y_i(w^Tx_i+b)\ge1. \]

落在两侧边界上的样本 \(x^+,x^-\) 是支持向量：

\[ w^Tx^++b=1,\qquad w^Tx^-+b=-1. \]

两条边界之间的间隔为

\[ M=(x^+-x^-)^T\frac{w}{\|w\|} =\frac{2}{\|w\|}. \]

最大化间隔等价于硬间隔二次规划

\[ \min_{w,b}\frac12\|w\|^2 \quad \text{s.t.}\quad y_i(w^Tx_i+b)-1\ge0,\ i=1,\ldots,n. \]

\(y(w^Tx+b)-1\) 描述样本相对间隔边界的位置：等于0的点位于边界，大于0的点在正确一侧并留有安全距离，小于0则侵入间隔或被误分。与感知机只惩罚 \(y(w^Tx+b)<0\) 的误分类点不同，SVM 的 Hinge Loss 为

\[ L_{\mathrm{hinge}}=\max\bigl(0,1-y(w^Tx+b)\bigr), \]

既惩罚误分类点，也惩罚已分对但落入间隔内的点。用神经网络形式训练 SVM 时，目标函数可取权重的 \(L_2\) 范数与带正则化系数的 Hinge Loss 之和。

拉格朗日对偶与 SMO

硬间隔问题的拉格朗日函数为

\[ \mathcal L(w,b,\alpha) =\frac12w^Tw +\sum_{i=1}^{n}\alpha_i\left[1-y_i(w^Tx_i+b)\right], \qquad \alpha_i\ge0. \]

KKT 条件包括：

\[ y_i(w^Tx_i+b)\ge1,\qquad \alpha_i\ge0, \]

\[ \alpha_i\left[y_i(w^Tx_i+b)-1\right]=0, \]

以及驻点条件

\[ \frac{\partial\mathcal L}{\partial w} =w-\sum_i\alpha_iy_ix_i=0, \qquad \frac{\partial\mathcal L}{\partial b} =-\sum_i\alpha_iy_i=0. \]

因此

\[ w=\sum_{i=1}^{n}\alpha_iy_ix_i, \qquad \sum_{i=1}^{n}\alpha_iy_i=0. \]

这里第二式来自 \(\partial\mathcal L/\partial b=0\)。课件第 12 页红框把它排成了 \(b=\sum_i\alpha_i y_i\)，应按上面的 KKT 等式理解。

把它们代回拉格朗日函数，得到对偶问题

\[ \max_{\alpha} \left[ \sum_{i=1}^{n}\alpha_i -\frac12\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_jy_iy_jx_i^Tx_j \right], \quad \alpha_i\ge0,\quad \sum_i\alpha_iy_i=0. \]

Platt 于1998年提出序列最小优化 SMO，每次选择两个拉格朗日乘子迭代优化。只有 \(\alpha_i>0\) 的样本进入最终权重，它们构成支持向量集合 \(SV\)：

\[ w=\sum_{j\in SV}\alpha_jy_jx_j. \]

任选一个支持向量代入 \(y_i(w^Tx_i+b)=1\) 可求 \(b\)。未知样本的判别函数为

\[ f(x)=\sum_{j\in SV}\alpha_jy_jx_j^Tx+b. \]

带不等式约束的凸优化可这样理解：若无约束极小值位于可行域内，答案与无约束问题相同；若它落在可行域外，最优点会落到约束边界上，此时可把活跃不等式看成等式约束。

软间隔

噪声和异常值会使数据只能近似线性可分。为每个样本引入松弛变量 \(\xi_i\ge0\)：

\[ y_i(w^Tx_i+b)\ge1-\xi_i. \]

软间隔问题为

\[ \min_{w,b,\xi} \frac12\|w\|^2+C\sum_{i=1}^{n}\xi_i, \]

\[ \text{s.t.}\quad 1-\xi_i-y_i(w^Tx_i+b)\le0,\qquad -\xi_i\le0. \]

其拉格朗日函数为

\[ \mathcal L =\frac12w^Tw +\sum_i\alpha_i[1-\xi_i-y_i(w^Tx_i+b)] -\sum_i\gamma_i\xi_i, \]

其中 \(\alpha_i,\gamma_i\ge0\)。驻点条件给出

\[ w=\sum_i\alpha_iy_ix_i,\qquad \sum_i\alpha_iy_i=0,\qquad C-\alpha_i-\gamma_i=0, \]

所以对偶变量满足 \(0\le\alpha_i\le C\)，对偶目标仍为

\[ \max_{\alpha} \left[ \sum_i\alpha_i -\frac12\sum_i\sum_j\alpha_i\alpha_jy_iy_jx_i^Tx_j \right]. \]

\(C\) 控制模型对误差的容忍度。\(C\) 越大，越不容许样本进入间隔，容易过拟合；\(C\) 越小，容许的误差越大，进入间隔的样本更多，容易欠拟合。

核函数与核技巧

非线性分类可以先用基函数 \(\phi(x)\) 把样本映射到高维空间，再在该空间线性分类。核函数直接计算映射后的内积：

\[ K(x_i,x_j)=\phi(x_i)^T\phi(x_j). \]

Mercer 定理给出有效核函数的充要条件：核矩阵

\[ \boldsymbol K_{ij}=K(x_i,x_j) \]

必须对称半正定，即 \(K(x_i,x_j)=K(x_j,x_i)\)，且任意非零向量 \(a\) 都满足 \(a^T\boldsymbol Ka\ge0\)。

常用核函数有：

\[ K_{\mathrm{linear}}(x_i,x_j)=x_i^Tx_j, \]

\[ K_{\mathrm{poly}}(x_i,x_j)=\left(1+x_i^Tx_j\right)^p, \]

\[ K_{\mathrm{Gaussian}}(x_i,x_j) =\exp\left(-\gamma\|x_i-x_j\|^2\right), \qquad \gamma=\frac{1}{2\sigma^2}, \]

\[ K_{\tanh}(x_i,x_j)=\tanh(\beta_0x_i^Tx_j+\beta_1). \]

引入核函数后，对偶问题成为

\[ \max_{\alpha} \left[ \sum_i\alpha_i -\frac12\sum_i\sum_j \alpha_i\alpha_jy_iy_jK(x_i,x_j) \right], \quad 0\le\alpha_i\le C, \]

判别函数为

\[ f(x)=\sum_{j\in SV}\alpha_jy_jK(x,x_j)+b. \]

这就是核技巧：只需核函数，不必显式写出可能维度很高的 \(\phi(x)\) 或 \(w\)。

非线性 SVM 求解 XOR

四个样本为

样本	\(x_i\)	\(y_i\)
\(x_1\)	\((-1,-1)^T\)	\(-1\)
\(x_2\)	\((-1,1)^T\)	\(1\)
\(x_3\)	\((1,-1)^T\)	\(1\)
\(x_4\)	\((1,1)^T\)	\(-1\)

取二次多项式核

\[ K(x_i,x_j)=\left(1+x_i^Tx_j\right)^2. \]

核矩阵为

\[ \boldsymbol K= \begin{bmatrix} 9&1&1&1\\ 1&9&1&1\\ 1&1&9&1\\ 1&1&1&9 \end{bmatrix}. \]

该核可对应到六维基函数

\[ \phi(x)= \left(1,x_1^2,\sqrt2x_1x_2,x_2^2,\sqrt2x_1,\sqrt2x_2\right)^T. \]

四个样本映射为

\[ \begin{aligned} \phi(x_1)&=(1,1,\sqrt2,1,-\sqrt2,-\sqrt2)^T,\\ \phi(x_2)&=(1,1,-\sqrt2,1,-\sqrt2,\sqrt2)^T,\\ \phi(x_3)&=(1,1,-\sqrt2,1,\sqrt2,-\sqrt2)^T,\\ \phi(x_4)&=(1,1,\sqrt2,1,\sqrt2,\sqrt2)^T. \end{aligned} \]

把样本代入对偶目标并令各偏导为0，得到

\[ \begin{aligned} 9\alpha_1-\alpha_2-\alpha_3+\alpha_4&=1,\\ -\alpha_1+9\alpha_2+\alpha_3-\alpha_4&=1,\\ -\alpha_1+\alpha_2+9\alpha_3-\alpha_4&=1,\\ \alpha_1-\alpha_2-\alpha_3+9\alpha_4&=1. \end{aligned} \]

解为

\[ \alpha_1=\alpha_2=\alpha_3=\alpha_4=\frac18, \]

所以四个样本全是支持向量。权重和偏置为

\[ w=\sum_i\alpha_iy_i\phi(x_i) =\left(0,0,-\frac{\sqrt2}{2},0,0,0\right)^T, \qquad b=0. \]

高维超平面 \(w^T\phi(x)+b=0\) 在原二维空间对应

\[ x_1x_2=0, \]

即两条坐标轴，正好把 XOR 四点分开。

高斯核的基函数也存在，但维数无穷。标量情形下，

\[ \begin{aligned} K(x_i,x_j) &=\exp\left[-\frac{(x_i-x_j)^2}{2\sigma^2}\right]\\ &=\exp\left(-\frac{x_i^2+x_j^2}{2\sigma^2}\right) \exp\left(\frac{x_ix_j}{\sigma^2}\right)\\ &=\exp\left(-\frac{x_i^2+x_j^2}{2\sigma^2}\right) \sum_{n=0}^{\infty}\frac{x_i^nx_j^n}{n!\sigma^{2n}}, \end{aligned} \]

因此可构造无穷维 \(\phi(x)\)，满足 \(K(x_i,x_j)=\phi(x_i)^T\phi(x_j)\)。

具体地，可以取

\[ \phi(x)=\exp\left(-\frac{x^2}{2\sigma^2}\right)\left[1,\frac{x}{\sigma},\frac{1}{\sqrt{2!}}\frac{x^2}{\sigma^2},\ldots,\frac{1}{\sqrt{n!}}\frac{x^n}{\sigma^n},\ldots\right]^T. \]

这也直接说明高斯核对应的基函数确实存在，而且维数无穷。

应用

SVM 可用于分类和回归。多分类可拆成多个“一对多”分类器，也可拆成两两“一对一”分类器，再用投票汇总。课件的深度图像手势识别流程为去背景、检测手部区域、识别数字1至5，150个样本中正确142个，识别率为 \(94.7\%\)。

模型选择与评估

模型容量、过拟合与欠拟合

模型容量描述其拟合能力，常与参数量、网络层数和节点数有关。容量大的模型通常需要更多训练样本，也更容易过拟合；限制过强则会欠拟合。

模型预测与真值的差异称误差。训练集上的误差叫训练误差或经验误差，测试集上的误差叫测试误差或泛化误差；训练期间还可观察验证集损失决定是否停止。理想模型从训练集学到适用于潜在样本的规律。过拟合表现为训练误差小、测试误差大；欠拟合则连训练规律也未掌握，训练误差大，测试误差通常更大。

评价指标

\(N\) 个样本中有 \(N_{\mathrm{error}}\) 个分类错误时，

\[ \mathrm{ER}=\frac{N_{\mathrm{error}}}{N}, \qquad \mathrm{AR}=1-\frac{N_{\mathrm{error}}}{N}. \]

语音和文本识别常按编辑距离计算识别率：

\[ \mathrm{AR}=1-\frac{D_e+S_e+I_e}{N}, \]

其中 \(D_e,S_e,I_e\) 分别是把识别结果改成真值所需的删除、替换、插入次数。

多分类混淆矩阵大小为 \(C\times C\)，行表示真值类别，列表示预测类别；所有元素之和是样本数，主对角线之和是正确数。石头、剪子、布分类例的矩阵为

\[ \begin{bmatrix} 99&0&1\\ 4&94&2\\ 1&1&98 \end{bmatrix}, \]

准确率为

\[ \frac{99+94+98}{300}=97\%. \]

二分类混淆矩阵含真正类 TP、假负类 FN、假正类 FP、真负类 TN。常用指标为

\[ \operatorname{Recall}=\frac{TP}{TP+FN}, \qquad \operatorname{Precision}=\frac{TP}{TP+FP}, \]

\[ F_1=\frac{2PR}{P+R}, \qquad F_\beta=\frac{(\beta^2+1)PR}{\beta^2P+R}, \]

\[ \operatorname{TPR}=\operatorname{Recall}, \qquad \operatorname{FPR}=\frac{FP}{TN+FP}. \]

若 \(TP=7,FN=3,FP=1,TN=9\)，则 Recall 为 \(70\%\)，Precision 为 \(87.5\%\)。

PR 曲线以 Recall 为横轴、Precision 为纵轴，曲线下面积 AP 越大越好。ROC 曲线以 FPR 为横轴、TPR 为纵轴，曲线下面积 AUC 越大越好。等错误率 EER 满足

\[ \operatorname{FPR}=\operatorname{FNR}=1-\operatorname{TPR}, \]

对应 ROC 与对角线 \(\operatorname{FPR}=1-\operatorname{TPR}\) 的交点，越接近 \((0,1)\) 越好。

课件还以 MNIST 比较线性分类器、SVM 和 CNN。每幅图像为 \(28\times28=784\) 像素，训练集60000张、测试集10000张，比较指标是测试集识别错误率。

交叉验证

K 折交叉验证把数据近似均分为 \(K\) 组，轮流以一组作测试集、其余 \(K-1\) 组作训练集，共训练 \(K\) 个模型，再对指标取平均；常取 \(K=10\)。样本很少时可用留一法：每次以一个样本作测试集，其他 \(N-1\) 个样本训练。

思考与探究

SVM 的约束 \(y(w^Tx+b)-1\) 有什么几何意义？它与感知机的损失有何区别与联系？
Softmax 输出可解释为后验概率并用作置信度；SVM 如何给出识别结果的置信度？
高斯核 SVM 欠拟合时，应怎样调整 \(\gamma\) 与正则化参数 \(C\)？

第3讲 机器学习（二）