Machine Learning(六) 交叉验证与支持向量机

交叉验证

---

评估泛化能力

机器学习的算法模型大多依赖于训练集数据，而前几篇日志中我们讨论了模型过拟合的问题。模型在未见过的数据上的表现通常被定性为模型的泛化能力，而交叉验证(Cross Validation)便是评估一个模型泛化能力的方法。

交叉验证是一种通过反复划分数据集来评估模型泛化能力的验证方法，其有多种形式。我们先介绍最简单的留出法，即把原训练集数据随机划分为70%数据量的训练集和30%数据量的测试集(Test Set)，并凭借模型对测试集数据的表现进行评估。

混淆矩阵(Confusion Matrix)是评估分类模型表现的重要指标。以二分类问题为例，假设对于测试集样本 $(x,y),y\in\{0,1\}$，模型的预测结果为 $Y\in\{0,1\}$，有以下几种情况。

	$Y=1$	$Y=0$
$y=1$	真正例 $TP$	假反例 $FN$
$y=0$	假正例 $FP$	真反例 $TN$

• $TP$：被正确预测的正例个数
• $TN$：被正确预测的反例个数
• $FP$：被错误预测的正例个数
• $FN$：被错误预测的反例个数

下面定义四个统计量，他们从不同角度评估了一个模型表现的优劣

1. 精确率(Precision)：模型预测为正例的样本中，真正为正例的比例

$$\text{P}=\frac{TP}{TP+FP}$$

2. 准确率(Accuracy)：模型预测正确的样本占总样本的比例

$$\text{Acc}=\frac{TP+TN}{TP+FP+TN+FN}$$

3. 召回率(Recall)：实际为正例的样本中，被模型正确预测为正例的比例

$$\text{R}=\frac{TP}{TP+FN}$$

4. F1值：精确率和召回率的调和平均数，综合反映模型性能

$$F=2\cdot\frac{\text{PR}}{\text{P+R}}$$

精确率关注预测结果，准确率关注整体预测，召回率关注实际样本，F1值平衡两者。四个指标从不同角度反映了一个模型的表现情况。

选择超参数

超参数(Hyperparameter)是用于控制模型的行为和性能的一种参数类型。例如，学习率 $\alpha$、迭代次数、正则化参数 $\lambda$、隐藏层的神经元数量 $s_l$ 等都是常见的超参数。选择合适的超参数可以借助交叉验证方法实现。

我们可以把原训练集随机划分为三个部分

• 60%的数据作为训练集，代价函数记为 $J_{train}(\boldsymbol{\theta})$
• 20%的数据作为交叉验证集(Cross Vadilation Set)，代价函数记为 $J_{cv}(\boldsymbol{\theta})$
• 20%的数据作为测试集，代价函数记为 $J_{test}(\boldsymbol{\theta})$

我们以多项式回归为例，多项式次数 $d=1,2,\cdots,n,\cdots$ 便是一个超参数。我们可以通过以下步骤确定一个较为合适的 $d$ 值。

1. 划分数据集
2. 对于次数为 $d$ 的多项式回归模型，进行训练使得 $\min J_{train}(\boldsymbol{\theta})$，得到参数 $\boldsymbol{\theta}^{(d)}$
3. 计算该参数对交叉验证集数据的代价 $J_{cv}(\boldsymbol{\theta}^{(d)})$
4. 确定一个范围 $1\leqslant d\leqslant p$，重复2,3步并选取使得 $J_{cv}(\boldsymbol{\theta}^{(d)})$ 最小的 ${\boldsymbol{\theta}}^{(d_0)}$
5. 确定超参数 $d=d_0$，并通过测试集计算准确率 $\text{Acc}$，评估模型

区别	训练集	交叉验证集	测试集
比例	60%	20%	20%
是否参与模型训练	是	否	否
训练对象	普通参数	超参数	-
评估对象	-	超参数	模型表现

我们可以更直观的画出下图

[{"url":"/img/mlearning/m6f1.png","alt":"偏差和方差","title":""}]

• 当 $d$ 过小时，模型欠拟合
  • $J_{train}$ 和 $J_{cv}$ 都较大
  • 模型偏差较大
• 当 $d$ 过大时，模型过拟合
  • $J_{train}$ 很小，$J_{cv}$ 较大
  • 模型方差较大
• 当 $d$ 适中时，模型表现良好

类似的，我们也可以凭借此方法确定合适的正则化参数 $\lambda$。

[{"url":"/img/mlearning/m6f2.png","alt":"正则化参数的选取","title":""}]

学习曲线

学习曲线(Learning Curve)是评估模型准确率的一种图示，一般可以表示为训练集和验证集在不同训练样本数量 $m_{train}$ 或特征数量 $n$ 下表现的变化趋势。下图分别展现了高偏差，高方差和良好模型的学习曲线。

[{"url":"/img/mlearning/m6f3.png","alt":"不同情况下的学习曲线","title":""}]

高偏差模型	高方差模型	良好模型
误差收敛	误差之间有大的差距	误差收敛
误差很高	误差较小	误差较小

支持向量机

---

接下来，我们来介绍支持向量机(Support Vector Machine, SVM)。正式介绍其定义之前，我们需要先介绍一些基本内容。

Hinge Loss

先回顾一下 Logistic 回归模型，我们曾经定义了单样本代价函数

$$\text{Cost}=-y\log h(\boldsymbol{x})-(1-y)\log(1-h(\boldsymbol{x}))$$

上述代价(损失)函数称为交叉熵损失函数(Cross-Entropy Loss Function)，其中 $h(\boldsymbol{x})=g(\boldsymbol{\theta}^T\boldsymbol{x})=\dfrac{1}{1+e^{-\boldsymbol{\theta}^T\boldsymbol{x}}}$ 是 Sigmoid 函数形式。令 $z=\boldsymbol{\theta}^T\boldsymbol{x}$，代入原代价函数有

$$\text{Cost}=-y\log \frac{1}{1+e^{-z}}-(1-y)\log\left(1-\frac{1}{1+e^{-z}}\right)$$

之前的日志中，我们曾经讨论过 $z$ 的取值和真实类别 $y$ 之间的关系

• 当 $y=1$ 时，$z$ 应该尽可能的大($z\gg 0$)，此时有

$$\text{Cost}=-\log \frac{1}{1+e^{-z}}\to 0$$

• 当 $y=0$ 时，$z$ 应该尽可能的小($z\ll 0$)，此时有

$$\text{Cost}=-\log \left(1-\frac{1}{1+e^{-z}}\right)\to 0$$

事实上，我们可以用下图的两条紫色折线近似代替此代价函数。

[{"url":"/img/mlearning/m6f4.png","alt":"Hinge Loss函数的大致图像","title":""}]

把两种情况的紫色折线函数称作Hinge损失函数，定义为

$$L(\boldsymbol{\theta}^T\boldsymbol{x})=L(z)=\begin{cases}\max(0,1-z)=L_1(z),&y=1\\\max(0,1+z)=L_0(z),&y=0\end{cases}$$

为此，我们可以写出一个全新的代价函数 $J$，形式如下

$$\begin{aligned}J(\boldsymbol{\theta})&=C\sum_{i=1}^m\Big[y^{(i)}L_1(\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})+(1-y^{(i)})L_0(\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})\Big]+\frac{1}{2}\sum_{j=1}^n \theta^2_j\\&=C\sum_{i=1}^mL(\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})+\frac{1}{2}\sum_{j=1}^n \theta_j^2,\quad\text{$C$ is a hyperparameter}\end{aligned}$$

尽管上述代价函数形式和之前介绍的有所区别，但优化目标是等价的。

本日志讨论的 SVM 便使用了上述形式的代价函数。

反过来思考

前面提到了Hinge损失函数的形式，仔细观察会发现

• 当 $y=1$ 时，只有 $z=\boldsymbol{\theta}^T\boldsymbol{x}\geqslant 1$ 时代价为0
• 当 $y=0$ 时，只有 $z=\boldsymbol{\theta}^T\boldsymbol{x}\leqslant -1$ 时代价为0

令 SVM 算法的假设函数形式为

$$h(\boldsymbol{x})=\begin{cases}1,&\boldsymbol{\theta}^T\boldsymbol{x}\geqslant 0\\0,&\boldsymbol{\theta}^T\boldsymbol{x}<0 \end{cases}$$

可以发现，只要 $\boldsymbol{\theta}^T\boldsymbol{x}\geqslant 0$ 时，模型就预测其类型为正，但此时其代价可能不为0；类似的，当 $\boldsymbol{\theta}^T\boldsymbol{x}<0$ 时，模型就预测其类型为负，但此时其代价也可能不为0。这就是 SVM 的一个有趣性质。

由于我们的优化目标是 $\min J(\boldsymbol{\theta})$，因此每一个样本的代价都应该尽可能的小。考虑代价函数中 $C$ 取一个很大的数字，比如 $114514$。

$$\min \Big[114514\sum_{i=1}^mL(\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})+\frac{1}{2}\sum_{j=1}^n \theta_j^2\Big]\Rightarrow \sum_{i=1}^mL(\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})\to 0$$

这一步是显然的：要想让整体最小，由于前一项的因子很大，所以在合适的训练后其值应当几乎为0。换言之，对于训练好的参数 $\boldsymbol{\theta}$，下述条件几乎成立。

• $h(\boldsymbol{x})=1$ 时：$\boldsymbol{\theta}^T\boldsymbol{x}\geqslant 1$
• $h(\boldsymbol{x})=0$ 时：$\boldsymbol{\theta}^T\boldsymbol{x}\leqslant -1$

我们不妨就把代价函数的前一项看做0，此时优化目标等价于

$$\min \frac{1}{2}\sum_{j=1}^n \theta_j^2,\quad \text{s.t. $\forall \boldsymbol{x}^{(i)}$ with $\boldsymbol{\theta}$, }\begin{cases}\boldsymbol{\theta}^T\boldsymbol{x}^{(i)}\geqslant 1,&y^{(i)}=1\\\boldsymbol{\theta}^T\boldsymbol{x}^{(i)}\leqslant -1,&y^{(i)}=0\end{cases}$$

原代价函数的前一项为0时，后一部分的约束条件(s.t.)必须对于所有的样本都成立。这种思想是一种反推思想，初次接触可能较难理解。

大间隔分类器

假设现在有一个线性可分(Linearly Separable)的训练集，即决策边界可以是一条直线、一个平面，或者更高维度的超平面。以下图为例，通过上述我们讨论的内容，SVM 可以找到一条黑色直线，其相比于其他的直线似乎更能区分开两个类别的样本数据。更一般的表述为

• 可以找到两条平行于黑色直线的蓝色直线，保证两条蓝色线中间没有任何数据点，且黑色直线被包含其中
• 这两条蓝色线可以充当边界，他们区分了两种类别的数据
• 黑色线到两条蓝色线的距离等距，这个距离称作间隔(Margin)
• SVM 模型总是试图寻找具有大间隔的决策边界

因此，SVM也被称作大间隔分类器。

[{"url":"/img/mlearning/m6f5.png","alt":"大间隔的直观理解","title":""}]

当然，上述内容都建立在 $C$ 很大的假设上。我们前面提到过，SVM 的代价函数形式和一般的代价函数是有区别的。他们之中的超参数分别是 $C$ 和 $\lambda$，而且不难发现 $C\Leftrightarrow \dfrac{1}{\lambda}$，因此 $C$ 很大就意味着 $\lambda$ 很小，此时模型很容易过拟合。

因此，超参数 $C$ 不应该设置的过大，下图直观地展现了这一观点。

[{"url":"/img/mlearning/m6f6.png","alt":"超参数C的选取","title":""}]

直观理解

接下来先讨论一个线性可分，特征数 $n=2$ 且 $\theta_0=0$ 的二分类问题。

给定两个平面向量 $\boldsymbol{u}=(u_1,u_2)^T,\boldsymbol{v}=(v_1,v_2)^T$，定义内积

$$\langle\boldsymbol{u},\boldsymbol{v}\rangle=\boldsymbol{u}^T\boldsymbol{v}=\boldsymbol{u}\cdot\boldsymbol{v}=u_1v_1+u_2v_2\in \mathbb{R}$$

根据中学知识，两个向量的内积可以看做其在同一个方向上投影的乘积。设 $p$ 是 $\boldsymbol{v}$ 在 $\boldsymbol{u}$ 上的有向投影，那么内积的定义式等价于

$$\langle\boldsymbol{u},\boldsymbol{v}\rangle=p\cdot\|\boldsymbol{u}\|\in \mathbb{R}$$

其中 $\|\boldsymbol{u}\|$ 表示 $\boldsymbol{u}$ 的模长或范数，即 $\|\boldsymbol{u}\|=\sqrt{u^2_1+u^2_2}\in \mathbb{R}$

给定线性可分的训练集，目前的优化目标为

$$\min \frac{1}{2}(\theta_1^2+\theta_2^2),\quad \text{s.t. $\forall \boldsymbol{x}^{(i)}$ with $\boldsymbol{\theta}$, }\begin{cases}\boldsymbol{\theta}^T\boldsymbol{x}^{(i)}\geqslant 1,&y^{(i)}=1\\\boldsymbol{\theta}^T\boldsymbol{x}^{(i)}\leqslant -1,&y^{(i)}=0\end{cases}$$

根据范数的定义，目标优化函数可以改写成 $\dfrac{1}{2}\|\boldsymbol{\theta}\|^2$。对于训练样本 $(\boldsymbol{x}^{(i)},y^{(i)})$，由于 $\boldsymbol{\theta},\boldsymbol{x}^{(i)}$ 在此例子中都视作一个二维向量($\theta_0=0$)，因此有

$$\boldsymbol{\theta}^T\boldsymbol{x}^{(i)}=\theta_1x_1+\theta_2x_2=p^{(i)}\|\boldsymbol{\theta}\|,\quad p^{(i)} \text{ is the projection of $\boldsymbol{x}^{(i)}$ on $\boldsymbol{\theta}$}$$

因此可以改写目标优化的限制条件为

$$\text{$\forall \boldsymbol{x}^{(i)}$ with $\boldsymbol{\theta}$, }\begin{cases}p^{(i)}\|\boldsymbol{\theta}\|\geqslant 1,&y^{(i)}=1\\p^{(i)}\|\boldsymbol{\theta}\|\leqslant -1,&y^{(i)}=0\end{cases}$$

设有一过原点直线 $L$ ，其法向量为 $\boldsymbol{\theta}$，也就是说 $\boldsymbol{\theta}$ 与直线 $L$ 垂直。由于我们要优化 $\|\boldsymbol{\theta}\|$ 最小，介于限制条件，此时我们需要让每个样本点对参数向量的投影 $p^{(i)}$ 都尽可能大，而投影 $p^{(i)}$ 等价于该点到直线 $L$ 的有向距离，比如规定沿 $\boldsymbol{\theta}$ 方向为正。

下图给出了两个不同的 $L$，可以发现右图是 SVM 选择的间隔更大的决策边界。也就是寻找使得不同类别样本点到自身距离都尽可能大的直线。这样就找到了具有最大间隔的决策边界，因为计算点到直线的距离是很简单的。

[{"url":"/img/mlearning/m6f7.png","alt":"SVM选取最大间隔","title":""}]

更一般的推导，我会以后单独开一篇日志。

核函数

---

非线性可分集

前面提到的几个 SVM 的例子都是线性可分的，即可以找到直线、平面等线性函数作为具有最大间隔的决策边界。通常情况下，决策边界无法表示成线性函数的形式，也就是说训练集数据是个非线性可分集。此时，我们可以考虑构造新的特征量，使得原始特征被映射到一个更高维的特征空间中，并且数据在这个更高维度空间中是线性可分的。这便是核函数(Kernel Function)的基本思想。

举例来说，假设有特征量 $x_1,x_2$，我们想要把这些特征量映射为三个全新的特征量 $f_1,f_2,f_3$。如果 $f_1,f_2,f_3$ 组成的新特征集合是一个线性可分集，那我们就可以使用大间隔分类器。

高斯核

不妨假设在 $x_1,x_2$ 的特征空间 $\mathbb{R}^2$ 中选取了三个标记点(Landmarks) $\boldsymbol{l}^{(1)},\boldsymbol{l}^{(2)},\boldsymbol{l}^{(3)}\in \mathbb{R}^2$。定义高斯核函数(Gaussian Kernel Function)为

$$f_i=K(\boldsymbol{x},\boldsymbol{l}^{(i)})=\exp\left(-\frac{\|\boldsymbol{x}-\boldsymbol{l}^{(i)}\|}{2\sigma^2}\right),\quad \sigma^2\text{ is a hyperparameter}$$

上述核函数源于高斯分布，又称正态分布。高斯核函数的作用是衡量 $\boldsymbol{x}$ 和 $\boldsymbol{l}^{(i)}$ 之间的相似度，其值域在 $[0,1]$ 之间

• 当 $\boldsymbol{x}\approx \boldsymbol{l}^{(i)}$ 时，$K(\boldsymbol{x},\boldsymbol{l}^{(i)})\approx 1$
• 当 $\|\boldsymbol{x}-\boldsymbol{l}^{(i)}\|$ 较大时时，$K(\boldsymbol{x},\boldsymbol{l}^{(i)})\approx 0$
• $\sigma^2$ 控制核函数的宽度，即影响的范围

下图给出了不同 $\sigma^2$ 的高斯核函数图像。

[{"url":"/img/mlearning/m6f8.png","alt":"高斯核函数图像","title":""}]

因此，我们对于每一个特征量 $\boldsymbol{x}=(x_1,x_2)^T$，经过高斯核函数映射后得到了新特征量 $\boldsymbol{f}=(f_1,f_2,f_3)^T$。可以证明，合理的高斯核函数可以把低维度的非线性可分集映射为高维度的线性可分集。因此，假设函数改写为

$$h(\boldsymbol{x})=\begin{cases}1,&(\boldsymbol{\theta'})^T\boldsymbol{f}\geqslant 0\\0,&(\boldsymbol{\theta'})^T\boldsymbol{f}<0 \end{cases}$$

记得在新参数向量和新特征向量中添加偏置项 $\theta'_0,f_0=1$。

高斯核函数是最常用的一类核函数，此外还有线性核函数、多项式核函数、Sigmoid核函数等等。他们在模型上的表现，如计算效率和准确性等各不相同。

使用技巧

当样本数量较大时($m>n$)，一种简单的选取标记点的方法便是把每一个样本的特征量 $\boldsymbol{x}^{(i)}$ 看做标记 $\boldsymbol{l}^{(i)}$。此时，我们构造了从 $\mathbb{R}^{n+1}\to\mathbb{R}^{m+1}$ 的映射，即有

$$\boldsymbol{x}^{(i)}=\begin{bmatrix}x_0^{(i)}\\x_1^{(i)}\\x_2^{(i)}\\\vdots\\x_n^{(i)}\end{bmatrix}\rightarrow \begin{bmatrix}1\\K(\boldsymbol{x}^{(i)},\boldsymbol{l}^{(1)})\\K(\boldsymbol{x}^{(i)},\boldsymbol{l}^{(2)})\\\vdots\\K(\boldsymbol{x}^{(i)},\boldsymbol{l}^{(m)})\end{bmatrix}=\begin{bmatrix}f_0^{(i)}\\f_1^{(i)}\\f_2^{(i)}\\\vdots\\f_m^{(i)}\end{bmatrix}$$

此时，令这个新特征量对应的参数为 $\boldsymbol{\theta}\in\mathbb{R}^{m+1}$，则目标优化函数为

$$\min \Big[C\sum_{i=1}^mL(\boldsymbol{\theta}^T\boldsymbol{f}^{(i)})+\frac{1}{2}\sum_{j=1}^m \theta_j^2\Big],\quad \text{under constrains}$$

其中，超参数 $C,\sigma^2$ 的取值对模型有所影响。

$C$ 过大	$C$ 过小	$\sigma^2$ 过大	$\sigma^2$ 过小
低偏差	高偏差	高偏差	低偏差
高方差	低方差	低方差	高方差

最后，我们来介绍一下目前为止几个分类模型的使用区别，这些都是前人的经验总结，对于特定情况可能不适用。选取合适的模型需要兼顾效率和准确性等。

适用情形	线性/Logistic 回归	神经网络	SVM
$m\approx n$	可使用	可使用	可使用，不采用核函数
$m>n$	不建议使用	可使用	可使用，采用核函数
$m\gg n$	可使用，添加新特征量	可使用	可使用，不采用核函数

$K$ 分类问题可以通过构造 $K$ 个 SVM，参考一对多分类。

代码实现

---

本代码基于经典的鸢尾花识别(Iris Detect)项目实现，可参考菜鸟教程。

如果 Python 未安装 sklearn 包，在终端中输入

pip install scikit-learn -i https://pypi.tuna.tsinghua.edu.cn/simple

完整代码如下

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm, datasets
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 加载鸢尾花数据集
iris = datasets.load_iris()
X = iris.data[:, :2]  # 只使用前两个特征
y = iris.target

# 将数据集划分为训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 创建SVM分类器
clf = svm.SVC(kernel='rbf')  # 使用高斯核函数

# 训练模型
clf.fit(X_train, y_train)

# 在测试集上进行预测
y_pred = clf.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"模型准确率: {accuracy:.2f}")

# 绘制决策边界
def plot_decision_boundary(X, y, model):
    h = .02  # 网格步长
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    plt.contourf(xx, yy, Z, alpha=0.8)
    plt.scatter(X[:, 0], X[:, 1], c=y, edgecolors='k', marker='o')
    plt.xlabel('Sepal length')
    plt.ylabel('Sepal width')
    plt.title('SVM Decision Boundary')
    plt.show()

plot_decision_boundary(X_train, y_train, clf)

参考网站

课程视频

吴恩达机器学习

课程讲义

吴恩达机器学习

菜鸟教程

学的不仅是技术，更是梦想！