基础数学工具
定义
随机变量 $X$ 的 期望 $E[X]$ 定义为
$$ E[X] = \sum_{x} x \cdot P(X=x) $$随机变量 $X$ 的 方差 $\text{Var}(X)$ 定义为
$$ \text{Var}(X) = E[(X - E[X])^2] $$标准差 $\sigma(X)$ 定义为
$$ \sigma(X) = \sqrt{\text{Var}(X)} $$定理Markov 不等式
设 $X$ 是一个非负随机变量, 期望存在, 那么对于任意 $t > 0$ 有
$$ P(X \geq t) \leq \frac{E[X]}{t} $$定理Chebyshev 不等式
设 $X$ 是一个随机变量, 期望和方差都存在, 那么对于任意 $t > 0$ 有
$$ P(|X - E[X]| \geq t) \leq \frac{\text{Var}(X)}{t^2} $$定义
随机变量 $X$ 和 $Y$ 的 协方差 $\text{Cov}(X, Y)$ 定义为
$$ \text{Cov}(X, Y) = E[(X - E[X])(Y - E[Y])] $$如果 $\text{Cov}(X, Y) = 0$, 则称 $X$ 和 $Y$ 不相关.
协方差具有对称性, 双线性.
定义
随机向量 $X=(X_1, X_2, \ldots, X_n)$ 的 协方差矩阵 $C(X)$ 定义为
$$ C(X) = E[(X - E[X])(X - E[X])^T] = (\text{Cov}(X_i, X_j))_{ij} $$定义
Gauss 分布 (正态分布) 的概率密度函数为
$$ f(x) = \frac{1}{\sqrt{2\pi}\sigma} \exp(-\frac{(x-\mu)^2}{2\sigma^2}) $$Laplace 分布 的概率密度函数为
$$ f(x) = \frac{1}{2b} \exp(-\frac{|x-\mu|}{b}) $$最优化问题
$$ \begin{aligned} & \min f(x) \\ \text{s.t. } & c_i(x) \leq 0, i = 1, 2, \dots, k \\ & h_j(x) = 0, j = 1, 2, \dots, l \end{aligned} $$构造 Lagrange 函数
$$ L(x, \alpha, \beta) = f(x) + \sum_{i=1}^{k} \alpha_i c_i(x) + \sum_{j=1}^{l} \beta_j h_j(x) $$引入 Karush-Kuhn-Tucker (KKT) 条件
$$ \begin{aligned} & \nabla_x L(x, \alpha, \beta) = 0 \\ & c_i(x) \leq 0, i = 1, 2, \dots, k \\ & h_j(x) = 0, j = 1, 2, \dots, l \\ & \alpha_i c_i(x) = 0, i = 1, 2, \dots, k \\ & \alpha_i \geq 0, i = 1, 2, \dots, k \end{aligned} $$基本概念和术语
定义
监督学习: 基于标记数据 $T=\{ (x_i,y_i) \}_{i=1}^N$, 学习一个从输入空间到输出空间的映射 $f: \mathcal{X} \mapsto \mathcal{Y}$. 利用此对未见数据进行预测. 通常分为 回归 和 分类 两类.
无监督学习: 基于未标记数据 $T=\{ x_i \}_{i=1}^N$, 发现其中隐含的知识模式. 聚类 是典型的无监督学习任务.
半监督学习: 既有标记数据又有未标记数据 (通常占比较大).
强化学习: 通过观察环境的反馈, 学习如何选择动作以获得最大的奖励.
模型评估与选择
损失函数
模型基于算法按照一定策略给出假设 $h \in \mathcal{H}$, 通过 损失函数 $L(h(x), y)$ 衡量假设的好坏.
- 0-1 损失函数:
- 平方损失函数:
平均损失 $R(h) = E_{x \sim D} [L(h(x), y)]$ 称为 泛化误差.
容易验证, 对于 0-1 损失函数, 准确率 $a = 1-R(h)$.
二分类
对于二分类问题, 样本预测结果有四种情况:
- 真正例 (True Positive, TP): 预测为正例, 实际为正例.
- 假正例 (False Positive, FP): 预测为正例, 实际为负例.
- 真负例 (True Negative, TN): 预测为负例, 实际为负例.
- 假负例 (False Negative, FN): 预测为负例, 实际为正例.
由此引入
- 准确率(查准率): $P = \frac{TP}{TP+FP}$.
- 召回率(查全率): $R = \frac{TP}{TP+FN}$.
- $F_1$ 度量: 考虑到二者抵触, 引入调和均值 $F_1 = \frac{2PR}{P+R}$.
过拟合和正则化
为了防止由于模型过于复杂而导致的过拟合, 可以通过 正则化 方法来限制模型的复杂度.
$$ \min \sum_{i=1}^{N} L(h(x_i), y_i) + \lambda J(h) $$其中 $J(h)$ 是随着模型复杂度增加而增加的函数. $\lambda$ 是正则化参数.
怎么选取合适的 $\lambda$ ? 一般是先给出若干候选, 在验证集上进行评估, 选取泛化误差最小的.
数据集划分
一般将数据集划分为 训练集 $T$ 和 测试(验证)集 $T^\prime$.
- 留出法 (hold-out): 分层无放回地随机采样. 也叫简单交叉验证.
- $k$ 折交叉验证 ($k$-fold cross validation): 将数据集分为 $k$ 个大小相等的子集, 每次取其中一个作为验证集, 其余作为训练集, 最后以这 $k$ 次的平均误差作为泛化误差的估计. 当 $k=|D|$ 时称为留一 (leave-one-out) 验证法.
- 自助法 (bootstrapping): 从数据集中有放回地采样 $|D|$ 个数据作为训练集, 没抽中的作为验证集. 因而训练集 $T$ 和原始数据集 $D$ 的分布未必一致, 对数据分布敏感的模型不适用.
偏差-方差分解
为什么泛化误差会随着模型复杂度的增加而先减小后增大?
定义
偏差 (bias): 模型预测值的期望与真实值之间的差异. 体现了模型的拟合能力.
$$\text{Bias}(x) = E_T[h_T(x)-c(x)] = \bar{h}(x) - c(x)$$方差 (variance): 模型预测值的方差. 体现了模型的对数据扰动的稳定性.
$$\text{Var}(x) = E[(h(x) - \bar{h}(x))^2]$$现在对泛化误差进行分解:
$$ \begin{aligned} R(h) &= E_T[(h_T(x) - c(x))^2] \\ &= E_T[h_T^2(x) - 2h_T(x)c(x) + c^2(x)] \\ &= E_T[h_T^2(x)] - 2c(x)E_T[h_T(x)] + c^2(x) \\ &= E_T[h_T^2(x)] - \bar{h}^2(x) + \bar{h}^2(x) - 2\bar{h}(x)c(x) + c^2(x) \\ &= E_T[(h_T(x) - \bar{h}(x))^2] + (\bar{h}(x) - c(x))^2 \\ &= \text{Var}(x) + \text{Bias}^2(x) \end{aligned} $$当然, 由于噪声存在, $y$ 未必一定等于 $c(x)$, 不妨设 $y=c(x)+\varepsilon$, 其中 $\varepsilon \sim \Epsilon$ 期望为 $0$. 可以证明
定理偏差-方差分解
$$ E_{T \sim D^{|T|}, \varepsilon \sim \Epsilon} [(h_T(x)-y)^2] = \text{Bias}^2(x) + \text{Var}(x) + E[\varepsilon^2] $$即泛化误差可以分解为偏差、方差和噪声三部分.
起初, 模型较为简单, 偏差在泛化误差起主导作用. 随着模型复杂度的增加, 拟合能力增强, 偏差减小, 但带来过拟合风险, 算法对数据扰动敏感, 方差增大. 方差占比逐渐增大, 最终导致泛化误差增大.