复习总结¶

约 3583 个字预计阅读时间 12 分钟

2. Classification Metrics¶

过拟合：模型在训练集上表现很好，但在测试集上表现较差，说明模型过于复杂，捕捉到了训练数据中的噪声和偶然性，导致泛化能力下降。解决方法包括早停和添加正则项；
欠拟合：模型在训练集和测试集上都表现较差，说明模型过于简单，一般性质都没学好。解决方法包括增加模型复杂度和增加训练时间。

评估方法：

留出法/Hold-out：将数据集直接分为训练集和测试集，要求尽可能保持数据分布的一致性，使用分层采样，一般要使用若干次随机划分、重复实验取平均值；
交叉验证法/Cross Validation：将数据集划分为 $k$ 个大小近似的互斥子集，每次使用 $k-1$ 个子集作为训练集，剩下的一个子集作为测试集，重复 $k$ 次，取平均值作为最终评估结果。

性能度量：

回归任务一般使用均方误差：$E(f; d) = \frac{1}{m} \sum_{i=1}^{m} (f(x_i) - y_i)^2$；
分类任务使用分类错误率和精度来衡量，错误率为分错样本占总样本的比例，精度为分类正确样本占总样本的比例，二者互补；
混淆矩阵：真实情况（靠左竖着）和预测情况（顶上横着）的对比表格：真实正例+预测正例为真阳性/TP，真实负例+预测正例为假阳性/FP，真实正例+预测负例为假阴性/FN，真实负例+预测负例为真阴性/TN。查准率为 $P = TP / (TP + FP)$ 意思是你预测的里面有多少是真正的阳性，查全率为 $R = TP / (TP + FN)$ 意思是所有真正的阳性你预测对了多少。F1 值为查准率和查全率的调和平均数，定义为 $F1 = 2PR / (P + R)$。
ROC： Receiver Operating Characteristic 曲线，横轴为假阳性率 $FPR = FP / (FP + TN)$，纵轴为真阳性率 $TPR = TP / (TP + FN)$，曲线下面积 AUC 衡量分类器性能，AUC 越大，分类器性能越好。绘制方法为给定 $m^+$ 个正例样本和 $m^-$ 个负例样本，假设分类器对每一个样本都给出了一个评分 $s(x)$，然后将所有样本按照评分从大到小排序，逐步移动阈值，从而计算出不同阈值下的 $TPR$ 和 $FPR$，绘制 ROC 曲线。

3. Linear Models¶

目标是学习一个线性分类器 $f(x) = w \cdot x + b$，若 $f(x) \geq 0$ 则预测为正类，否则为负类，预测错误则有 $-y_i (w \cdot x_i + b) > 0$。线性分类器的学习目标是最小化经验风险，经验风险一般使用经典的均方误差，可以使用最小二乘求解。

广义线性模型一般形式为 $f(x) = g^{-1}(w \cdot x + b)$，其中 $g(\cdot)$ 是连接函数/Link Function，一般要求单调可微。比如对数线性回归：$f(x) = \exp(w \cdot x + b)$，这里连接函数为 $g(f) = \log f$；

线性判别分析也可以做二分类，想法是找一根直线，将不同类别的样本投影到这根直线上，使得投影后不同类别样本的类间距离尽可能大，类内距离尽可能小。假设两个类别的样本均值分别为 $\mu_0$ 和 $\mu_1$，类内散度矩阵为 $S_W = \sum_i \sum_{x \in D_i} (x - \mu_i)(x - \mu_i)^\top$，类间散度矩阵为 $S_B = (\mu_0 - \mu_1)(\mu_0 - \mu_1)^\top$，目标函数为最大化广义瑞丽商 $J(w) = \frac{w^\top S_B w}{w^\top S_W w}$，j结果为 $w^* = S_W^{-1} (\mu_0 - \mu_1)$。

多分类任务可以使用二分类学习器解决，常用的方法有一对多，一对其余和多对多。一对一存储开销和测试时间大，需要训练 $C_N^2$ 个分类器，但是训练时间短，只需要使用两个类的样例。一对其余需要训练 $N$ 个分类器，存储开销和测试时间适中，但是训练时间长，因为每个分类器都需要使用所有样例。多对多使用纠错输出码/ECOC。

4. Decision Trees¶

决策树学习的目的是为了产出一棵泛化能力强的决策树。关键在于如何选择最优划分属性，我们期望随着划分过程的不断进行，决策树分支节点所包含的样本尽可能属于同一类别，也就是纯度不断提升。典型的属性划分方法包括：信息增益、信息增益率和基尼指数。

信息增益：使用信息熵/Information Entropy 可以度量样本集合纯度，若每一类所占的比例为 $p_k$，则信息熵定义为 $\mathrm{Ent}(D) = - \displaystyle\sum_{k=1}^{\lvert \mathcal{Y} \rvert} p_k \log_2 p_k$，信息熵越小，纯度越高。信息增益含义为，划分前后信息熵的减少量，定义为 $\mathrm{Gain}(D, a) = \mathrm{Ent}(D) - \displaystyle\sum_{v=1}^{V} \frac{\lvert D^v \rvert}{\lvert D \rvert} \mathrm{Ent}(D^v)$，其中 $D^v$ 表示在属性 $a$ 上取值为 $a_v$ 的样本子集。信息增益越大，代表划分之后的信息熵下降越多，纯度提升越大，因此选择信息增益最大的属性进行划分，这就是 ID3 算法的划分准则。但是，信息增益偏向于取值较多的属性。
信息增益率：为了解决信息增益偏向取值较多属性的问题，引入了信息增益率/Information Gain Ratio 作为划分准则。其想法是将信息增益进行归一化处理，归一化量为信息的固有值/Intrinsic Value，定义为 $\mathrm{IV}(a) = - \displaystyle\sum_{v=1}^{V} \frac{\lvert D^v \rvert}{\lvert D \rvert} \log_2 \frac{\lvert D^v \rvert}{\lvert D \rvert}$，属性数目越多，固有值越大。信息增益率定义为 $\mathrm{Gain\_Ratio}(D, a) = \mathrm{Gain}(D, a) / \mathrm{IV}(a)$，但是，信息增益率偏向于取值较少的属性。C4.5 算法结合了信息增益和信息增益率的优点，先选出信息增益率高于平均水平的属性，再从中选择信息增益最大的属性进行划分。
基尼指数：首先需要定义基尼值/Gini Value，表示从样本集中随机抽取两个样本，它们属于不同类别的概率，定义为 $\mathrm{Gini}(D) = \displaystyle\sum_{k=1}^{\lvert \mathcal{Y} \rvert} p_k \cdot (1 - p_k) = 1 - \sum_{k=1}^{\lvert \mathcal{Y} \rvert} p_k^2$。基尼指数据此定义为 $\mathrm{Gini\_Index}(D, a) = \displaystyle\sum_{v=1}^{V} \frac{\lvert D^v \rvert}{\lvert D \rvert} \mathrm{Gini}(D^v)$，基尼指数越小，纯度越高。CART 算法使用基尼指数作为划分准则，选择基尼指数最小的属性进行划分。

决策树很容易出现过拟合现象，因此需要进行剪枝操作。剪枝分为预剪枝和后剪枝两种方式。预剪枝是在决策树生成过程中，动态地判断是否继续划分节点，若继续划分会导致泛化能力下降，则停止划分。后剪枝则是先生成完整的决策树，然后自底向上地对各个子树进行评估，若将子树替换为叶节点能够提升泛化能力，则进行替换。

这里面衡量泛化能力的指标通常是在验证集上的表现，可以使用准确率等指标。预剪枝和后剪枝各有优缺点，预剪枝计算开销较小，但可能错过一些有用的划分，有欠拟合风险（因为本质上使用贪心）；后剪枝一般欠拟合风险较小，但计算开销较大。

决策树只能处理离散属性，对于连续属性使用离散化处理：若在某个连续属性 $a$ 上出现了 $n$ 个不同的取值，将其从小到大排列，可以选择 $n-1$ 个划分点 $\{t_1, t_2, \ldots, t_{n-1}\}$，这些划分点都是相邻两个取值的中点。对于每个划分点 $t_i$，将属性 $a$ 划分为两个区间 $(-\infty, t_i]$ 和 $(t_i, +\infty)$。然后基于离散属性值方法，考察这些划分点，选取最优的划分点进行划分，就以信息增益来说：

\[ \mathrm{Gain}(D, a) = \max_{t\in \{t_1, t_2, \ldots, t_{n-1}\}} \mathrm{Gain}(D, a, t) \]

这里面 $\mathrm{Gain}(D, a, t)$ 表示基于划分点 $t$ 进行划分所得到的信息增益。

对于缺失值，我们需要考虑两个问题：第一个是如何选择划分属性，第二个是如何划分在该属性上没有取值的样本。对于第一个问题，给定数据集 $D$ 和属性 $a$，只考虑在该属性上有取值的样本子集 $\tilde{D} \subseteq D$，计算出该属性上有值的样本比例 $\rho$、无缺失值样本之中第 $k$ 类样本比例 $\tilde{p}_k$ 以及无缺失值样本中在属性 $a$ 上取值为 $a_v$ 的样本比例 $\tilde{r}_v$，然后计算信息增益可以推广为 $\mathrm{Gain}(D, a) = \rho \times \mathrm{Gain}(\tilde{D}, a)$，这里面 $\mathrm{Gain}(\tilde{D}, a) = \mathrm{Ent}(\tilde{D}) - \displaystyle\sum_{v=1}^{V} \tilde{r}_v \mathrm{Ent}(\tilde{D}^v)$，注意这里面所有比例都是考虑每一个样本带有权重的。

对于第二个问题，如果该样本在该划分属性上取值已知，那么直接划分则可，且权重不变。否则将该样本划分到所有子节点，且每一个子节点的样本权重变为原来的 $\tilde{r}_v$ 倍。

5. Neural Networks¶

就考一个反向传播，算算就行。

6. Support Vector Machine¶

image.png

7. Bayesian Classifier¶

给定 $N$ 个类别，令 $\lambda_{ij}$ 表示将类别 $j$ 误分类为类别 $i$ 所带来的损失，则基于后验概率将样本 $x$ 分类为类别 $i$ 的期望损失为

\[ R(c_i \mid x) = \displaystyle\sum_{j=1}^{N} \lambda_{ij} P(c_j \mid x) \]

贝叶斯判定准则的目标是得到最小的期望损失：$h^*(x) = \arg\min_{c_i \in \mathcal{Y}} R(c_i \mid x)$。这个称为贝叶斯最优分类器，风险为贝叶斯风险。

可以见得，我们的目标是建模后验概率 $P(c_j \mid x)$，根据生成模型和判别模型的不同，贝叶斯分类器属于判别模型，这也指出了机器学习的目标，根据有限的训练样本尽可能准确计算出后验概率。

朴素贝叶斯分类器：注意到，后验概率可以通过贝叶斯公式表示为

\[ P(c_j \mid x) = \frac{P(x \mid c_j) P(c_j)}{P(x)} \]

但是，直接计算 $P(x \mid c_j)$ 很困难，因为需要估计联合概率分布，每个类别数目组合起来会产生指数爆炸，而样本过于稀疏，联合概率估计及其不准确，因此朴素贝叶斯分类器引入了条件独立假设，假定属性之间相互独立，也就是

\[ P(c_j \mid x) = \frac{P(c_j)}{P(x)} \prod_{i=1}^{d} P(x_i \mid c_j) \]

由于 $P(x)$ 对所有类别都是相同的，因此可以忽略，最终分类决策准则为 $h_{nb}(x) = \arg\max_{c_j \in \mathcal{Y}} P(c_j) \prod_{i=1}^{d} P(x_i \mid c_j)$。对于离散属性，直接使用频率估计概率，对于连续属性，通常假设其服从高斯分布，然后估计均值和方差。如果某个属性值/类别在训练集之中没有出现过，那么估计出来的概率就为 0，因此需要拉普拉斯修正：令 $N$ 为训练集 $D$ 中可能出现的类别数目，$N_i$ 为第 $i$ 个类别可能的取值数目，因此估计：

\[ \hat{P}(c) = \frac{\lvert D_c \rvert + 1}{\lvert D \rvert + N}, \quad \hat{P}(x_i \mid c) = \frac{\lvert D_{c, x_i} \rvert + 1}{\lvert D_c \rvert + N_i} \]

EM 算法：EM 算法用于含有隐变量的概率模型参数估计问题。核心关系如下：

\[ \mathit{LL}(\theta \mid X) = \ln P(X \mid \theta) = \ln \displaystyle\sum_{Z} P(X, Z \mid \theta) \]

算法流程分两步，迭代的更新 $\theta$：

E 步：当 $\theta$ 固定时，根据训练数据推断出隐变量 $Z$ 的分布 $P(Z \mid X, \theta^{(t)})$，计算出对数似然关于隐变量的期望：

$$ Q(\theta \mid \theta^{(t)}) = \mathbb{E}{Z \mid X, \theta^{(t)}} [\ln P(X, Z \mid \theta)] = \displaystyle\sum) \ln P(X, Z \mid \theta) $$ - } P(Z \mid X, \theta^{(t)M 步：寻找参数最大化似然 $Q(\theta \mid \theta^{(t)})$，更新参数 $\theta^{(t+1)} = \arg\max_{\theta} Q(\theta \mid \theta^{(t)})$。

10. Demension Reduction¶

PCA/Principle Component Analysis：目标是对正交属性空间的样本点，使用一个超平面对所有样本进行适当的表达。需要满足的性质是：

最近重构性：样本点到超平面的距离尽可能小；
最大可分性：样本点在这个超平面上的投影尽可能分散，也就是使投影后样本点的方差最大，按这种想法看，PCA 就是在选择方差最大方向。

假设样本集为 $D = \{x_1, x_2, \ldots, x_m\}$，每一个样本点 $x_i \in \mathbb{R}^d$，低维空间维数为 $d'$，整体过程如下：

对所有样本进行中心化：$x_i \leftarrow x_i - \bar{x}$；
计算样本协方差矩阵 $S = \mathbf{X}^\top \mathbf{X} / m$，$m$ 是样本数目；
对协方差矩阵进行特征值分解，得到特征值 $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_d$ 及对应的特征向量 $w_1, w_2, \ldots, w_d$；
取最大的 $d'$ 个特征值对应的特征向量，组成投影矩阵 $\mathbf{W} = (w_1, w_2, \ldots, w_{d'})$；

最后注意到 PCA 其实是线性降维方法就可，假设从高维空间到低维空间的映射为线性的，每一个主成分的方差解释率为 $\mathrm{Var\_Ratio}(k) = \lambda_k / \sum_{i=1}^{d} \lambda_i$，前 $d'$ 个主成分的累计方差解释率为 $\mathrm{Cum\_Var\_Ratio}(d') = \sum_{k=1}^{d'} \mathrm{Var\_Ratio}(k)$，通常选择累计方差解释率达到某个阈值的 $d'$ 作为降维后的维数。