1.绪论

归纳偏置：

学习算法在面对多个都能解释训练数据的假设时，倾向于选择某一类假设的偏好。

模型	归纳偏置
线性模型	输入与输出近似线性相关
决策树	可以通过一系列特征划分完成判断
KNN	相近样本有相似标签
朴素贝叶斯	特征之间条件独立
SVM	最大间隔的分类边界更好
CNN	图像具有局部性和平移不变性
RNN	序列数据存在时间依赖
Transformer	token 之间存在可通过注意力建模的关系

归纳偏置和泛化的关系

情况	结果
偏置太弱	模型太自由，容易过拟合
偏置太强	模型太死板，容易欠拟合
偏置合适	泛化能力较好

奥卡姆剃刀

奥卡姆剃刀可以概括为：

若有多个假设都能解释现象，应优先选择最简单的那个。

在机器学习中，它通常表现为：

如果多个模型在训练集上表现相近，优先选择更简单的模型。

考试中可以这样写

归纳偏置是学习算法在学习过程中对假设空间的偏好。由于训练样本有限，通常存在多个假设都能与训练数据一致，学习算法必须借助某种先验假设来选择其中一个假设，从而实现对未见样本的泛化。常见归纳偏置包括线性假设、平滑性假设、最大间隔假设、特征条件独立假设等。

奥卡姆剃刀是一种典型的归纳偏置，其思想是：若多个假设都能较好解释训练数据，则应优先选择较简单的假设。在机器学习中，这通常表现为偏好低复杂度模型、较小参数范数、较浅决策树或较短描述长度，以降低过拟合风险并提高泛化能力。但奥卡姆剃刀并不保证总是正确，当真实规律本身复杂时，过度追求简单可能导致欠拟合。

生成式和判别式模型

任务	生成式模型	判别式模型
文本分类	朴素贝叶斯	逻辑回归、SVM、BERT 分类器
序列标注	HMM	CRF、BiLSTM-CRF
图像分类	高斯判别分析、生成式分类器	CNN、ResNet、ViT
聚类/密度建模	GMM、VAE、Diffusion	通常不是判别式任务
语音识别	HMM-GMM	DNN-HMM、CTC、Transformer 判别模型

2.模型评估与选择

统计学习方法三要素

统计学习方法 = 模型 + 策略 + 算法。

模型：要学习的映射函数、决策函数或条件概率分布。
假设空间：所有候选模型组成的集合，如 $\mathcal{F}={f\mid Y=f(X)}$。
策略：从假设空间中选择最优模型的准则，通常以风险最小化为目标。
算法：求解最优化问题的具体方法，如梯度下降、牛顿法等。

损失与风险

损失函数 $L(y,f(x))$：衡量模型对单个样本的预测误差。
- 0-1 损失：预测错误为 1，正确为 0。
- 平方损失：$L(y,f(x))=(y-f(x))^2$。
期望风险（泛化风险）：模型在真实数据分布上的平均损失，无法直接计算。 $$R_{exp}(f)=\mathbb{E}[L(Y,f(X))]$$
经验风险：模型在训练集上的平均损失，是期望风险的近似。 $$R_{emp}(f)=\frac{1}{N}\sum_{i=1}^{N}L(y_i,f(x_i))$$
经验风险最小化（ERM）：选择训练误差最小的模型；数据少或模型复杂时容易过拟合。
结构风险最小化（SRM）：在经验风险上加入模型复杂度惩罚，以提高泛化能力。 $$\min_{f\in\mathcal{F}}R_{emp}(f)+\lambda J(f)$$ 其中 $J(f)$ 表示模型复杂度，$\lambda$ 控制拟合能力与模型复杂度之间的权衡。

基本概念

经验误差（训练误差）：模型在训练集上的误差。
泛化误差：模型在未见样本上的误差，是模型评估真正关心的指标。
欠拟合：模型过于简单，训练误差和测试误差都较高。
过拟合：模型过度适应训练数据，训练误差低，但测试误差高。
模型选择的三个问题：如何获得可靠测试结果、如何度量性能、如何判断差异是否显著。

评估方法

测试集必须与训练集互斥，并尽量保持数据分布一致。

方法	核心做法	特点
留出法	将数据一次划分为训练集和测试集	简单；应分层采样并多次随机划分，测试集常占 $1/5\sim1/3$
$K$ 折交叉验证	分成 $K$ 份，轮流用一份测试、其余训练，结果取平均	较稳定，但需训练 $K$ 次
自助法	有放回抽取与原数据集等量的样本作为训练集	约 $36.8%$ 的样本未被抽中，可作为包外测试集；会改变数据分布

训练集、验证集与测试集

训练集：学习模型参数。
验证集：选择模型和调整超参数。
测试集：只用于最终评估泛化性能，不能参与调参。
超参数确定后，应使用“训练集 + 验证集”重新训练最终模型，再在测试集上评估。

性能度量

回归任务

均方误差（MSE）：预测值与真实值之差的平方的平均值，越小越好。 $$MSE=\frac{1}{m}\sum_{i=1}^{m}(f(x_i)-y_i)^2$$

分类任务

错误率：分类错误的样本比例。
准确率（Accuracy）：分类正确的样本比例，$Accuracy=1-Error$。
查准率（Precision）：预测为正的样本中，真正为正的比例。 $$P=\frac{TP}{TP+FP}$$
查全率（Recall）：所有真实正例中，被正确找出的比例。 $$R=\frac{TP}{TP+FN}$$
F1：Precision 与 Recall 的调和平均，用于兼顾二者。 $$F1=\frac{2PR}{P+R}$$
$F_\beta$：$\beta>1$ 更重视 Recall，$\beta<1$ 更重视 Precision。

P-R、ROC 与 AUC

P-R 曲线：以 Recall 为横轴、Precision 为纵轴；曲线越靠近右上方越好，适合类别不平衡问题。
BEP（平衡点）：Precision 等于 Recall 时的取值，越大越好。
ROC 曲线：以假阳性率 FPR 为横轴、真正例率 TPR 为纵轴。
AUC：ROC 曲线下的面积，表示随机取一对正负样本时，模型将正例排在负例之前的概率；越大越好。

宏平均与微平均

Macro：先分别计算各类别指标，再取平均；各类别权重相同，更关注小类别。
Micro：先汇总各类别的 TP、FP、FN，再计算指标；样本多的类别影响更大。

代价敏感评估

当不同错误造成的损失不同时，应使用代价敏感指标：为不同类型的误分类设置不同代价，而不是只统计错误次数。

比较检验

测试结果受到数据划分和算法随机性的影响，数值更高不一定代表模型具有实质优势，需要进行统计显著性检验。

两个学习器：交叉验证 $t$ 检验、McNemar 检验。
多个学习器：先用 Friedman 检验判断整体是否存在差异，再用 Nemenyi 检验进行两两比较。
统计显著性：观察到的性能差异不太可能仅由随机因素造成。

偏差-方差分解

对于回归任务，泛化误差可分解为：

$$泛化误差=偏差^2+方差+噪声$$

偏差（Bias）：模型平均预测与真实规律之间的差距，反映模型的拟合能力；偏差高通常意味着欠拟合。
方差（Variance）：训练集变化引起模型预测结果变化的程度，反映模型的稳定性；方差高通常意味着过拟合。
噪声：数据本身不可避免的随机误差，决定了任何学习算法能达到的误差下界。

偏差-方差权衡

模型过于简单：高偏差、低方差，容易欠拟合。
模型过于复杂：低偏差、高方差，容易过拟合。
目标是在模型复杂度、数据量和正则化强度之间取得平衡，使泛化误差最小。

问题	常用改进方法
高偏差	增加有效特征、提高模型复杂度、训练更充分、减小正则化
高方差	增加训练数据、减少特征、简化模型、增大正则化、进行超参数调优

大模型评估的特点

与经典机器学习相比，大模型通常预训练一次、训练成本高；评估需要多个 benchmark 和多维指标，还要关注数据污染、Prompt 对结果的影响，并结合自动指标与人工评价。

速记

划分数据 → 选择指标 → 调整模型 → 显著性检验 → 分析偏差与方差。

3. 线性模型

线性可分性

设 $X_1$ 和 $X_2$ 是 $n$ 维欧氏空间中的两个点集。若存在 $n+1$ 个实数 $w_1,w_2,\dots,w_n,k$，使得：

对任意 $x\in X_1$，有 $\sum_{i=1}^{n}w_i x_i>k$。
对任意 $x\in X_2$，有 $\sum_{i=1}^{n}w_i x_i<k$。

则称 $X_1$ 和 $X_2$ 是线性可分的。

直观理解：可以用一条直线、一个平面或更高维的超平面把两类样本完全分开。

感知机

**感知机（Perceptron）**是 Frank Rosenblatt 于 1957 年提出的二分类线性分类模型，是神经网络和支持向量机的重要基础。

类型：判别模型。
任务：二分类。
决策边界：线性超平面。

感知机的划分超平面为：

$$ \mathbf{w}^T\mathbf{x}+b=0 $$

其中：

$\mathbf{w}$ 是法向量，决定超平面的方向。
$b$ 是位移项，决定超平面与原点之间的距离。

分类函数为：

$$ f(\mathbf{x})=\mathrm{sign}(\mathbf{w}^T\mathbf{x}+b) $$

$$ \mathrm{sign}(z)= \begin{cases} +1, & z\ge 0\ -1, & z<0 \end{cases} $$

线性模型的一般形式

线性模型试图通过属性的线性组合进行预测：

$$ f(\mathbf{x})=w_1x_1+w_2x_2+\cdots+w_dx_d+b $$

向量形式：

$$ f(\mathbf{x})=\mathbf{w}^T\mathbf{x}+b $$

特点：

形式简单，是很多复杂模型的基础。
可解释性强，权重 $w_i$ 可以反映对应属性的重要程度。
可用于回归，也可通过联系函数用于分类。

线性回归

线性回归希望预测值尽可能接近真实值：

$$ f(x_i)=wx_i+b\approx y_i $$

常用均方误差作为优化目标：

$$ (w^,b^)=\arg\min_{w,b}\sum_{i=1}^{m}(y_i-wx_i-b)^2 $$

这就是最小二乘法。

一元线性回归闭式解

对误差函数分别对 $w$ 和 $b$ 求导并令其为 0，可得：

$$ w=\frac{\sum_{i=1}^{m}y_i(x_i-\bar{x})}{\sum_{i=1}^{m}x_i^2-\frac{1}{m}(\sum_{i=1}^{m}x_i)^2} $$

$$ b=\frac{1}{m}\sum_{i=1}^{m}(y_i-wx_i) $$

其中：

$$ \bar{x}=\frac{1}{m}\sum_{i=1}^{m}x_i $$

多元线性回归

多元线性回归中，参数 $\mathbf{w}$ 和输入 $\mathbf{x}$ 都是 $d$ 维向量：

$$ f(\mathbf{x}_i)=\mathbf{w}^T\mathbf{x}_i+b\approx y_i $$

将 $b$ 吸收入参数向量，令：

$$ \hat{\mathbf{w}}=(\mathbf{w};b),\quad \hat{\mathbf{x}}=(\mathbf{x};1) $$

则模型可写为：

$$ f(\mathbf{x})=\hat{\mathbf{w}}^T\hat{\mathbf{x}} $$

采用矩阵形式，最小二乘解为：

$$ \hat{\mathbf{w}}^*=(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} $$

成立条件：

若 $\mathbf{X}^T\mathbf{X}$ 满秩或正定，则闭式解唯一。
若 $\mathbf{X}^T\mathbf{X}$ 不满秩或非正定，可能存在多个解。
多解时需要依赖归纳偏好，或引入正则化。

线性模型的变化

如果希望线性模型直接逼近真实标记：

$$ y=\mathbf{w}^T\mathbf{x}+b $$

得到普通线性回归。

如果希望线性模型逼近真实标记的某种变换，例如：

$$ \ln y=\mathbf{w}^T\mathbf{x}+b $$

则得到对数线性回归。此时实际是在用：

$$ e^{\mathbf{w}^T\mathbf{x}+b} $$

逼近 $y$，从而实现非线性映射。

广义线性模型

广义线性模型的核心思想：在线性预测值和真实标记之间引入联系函数（link function）。

一般形式：

$$ y=g^{-1}(\mathbf{w}^T\mathbf{x}+b) $$

或等价写成：

$$ g(y)=\mathbf{w}^T\mathbf{x}+b $$

其中 $g(\cdot)$ 是单调可微函数。

例子：

$g(y)=y$：普通线性回归。
$g(y)=\ln y$：对数线性回归。
$g(y)=\ln\frac{y}{1-y}$：对数几率回归。

对数几率回归

二分类任务中，期望输出 $y\in{0,1}$，而线性模型输出的是实值：

$$ z=\mathbf{w}^T\mathbf{x}+b $$

需要一个函数把实值 $z$ 映射到 $[0,1]$，作为正类概率。

Logistic 函数

单位阶跃函数不连续，性质不好，因此使用对数几率函数：

$$ y=\frac{1}{1+e^{-z}} $$

它是 Sigmoid 函数的一种，具有单调、连续、可微等性质。

注意：Logistic 和“逻辑”没有关系，不要把 logistic regression 翻译成“逻辑回归”，更准确的译法是对数几率回归或对率回归。

对数几率

若将 $y$ 看作正类概率：

$$ y=P(y=1\mid \mathbf{x}) $$

则：

$$ \frac{y}{1-y} $$

称为几率（odds），表示样本作为正例的相对可能性。

其对数：

$$ \ln\frac{y}{1-y} $$

称为对数几率（log odds / logit）。

对数几率回归建立如下关系：

$$ \ln\frac{P(y=1\mid\mathbf{x})}{P(y=0\mid\mathbf{x})} =\mathbf{w}^T\mathbf{x}+b $$

因此：

$$ P(y=1\mid\mathbf{x})= \frac{e^{\mathbf{w}^T\mathbf{x}+b}}{1+e^{\mathbf{w}^T\mathbf{x}+b}} $$

$$ P(y=0\mid\mathbf{x})= \frac{1}{1+e^{\mathbf{w}^T\mathbf{x}+b}} $$

求解方法

对数几率回归通常使用极大似然法估计参数。

给定数据集 ${(\mathbf{x}i,y_i)}{i=1}^{m}$，最大化对数似然函数等价于最小化负对数似然。该目标函数是高阶可导、连续的凸函数，常用方法包括：

梯度下降法。
牛顿法。
拟牛顿法。

多分类学习

多分类任务常通过拆解法转化为多个二分类任务。

方法	分类器数量	特点
OvO（一对一）	$N(N-1)/2$	每个分类器只使用两个类的样本，训练时间较短；分类器数量多，存储和测试开销大
OvR（一对其余）	$N$	分类器数量少，存储和测试开销小；每个分类器使用全部训练样本，训练时间较长

多数情况下，OvO 和 OvR 的预测性能取决于具体数据分布，整体表现通常差不多。

纠错输出码

纠错输出码（Error Correcting Output Code, ECOC）是一种多分类拆解方法。

核心过程：

编码：对 $N$ 个类别做 $M$ 次划分，每次将一部分类别作为正类，另一部分类别作为反类，从而得到 $M$ 个二分类任务。
训练：训练 $M$ 个二分类器。
预测：测试样本经过 $M$ 个分类器，得到长度为 $M$ 的预测编码。
解码：将预测编码与各类别编码比较，选择距离最小的类别作为最终结果。

重点结论：

ECOC 对分类器错误有一定容忍和修正能力。
编码越长，通常纠错能力越强。
在编码长度相同的情况下，任意两个类别之间的编码距离越远，纠错能力越强。

类别不平衡

类别不平衡（class-imbalance）指不同类别样本比例差异很大，且小类往往更重要。

如果直接按：

$$ \frac{P(y=1\mid\mathbf{x})}{P(y=0\mid\mathbf{x})}>1 $$

判断为正类，可能会偏向多数类。

一种基本思想是进行再缩放（rescaling），根据类别先验比例调整判断阈值。但精确估计类别先验通常较困难。

常用处理方法：

过采样（oversampling）：增加少数类样本，例如 SMOTE。
欠采样（undersampling）：减少多数类样本，例如 EasyEnsemble。
阈值移动（threshold-moving）：调整分类阈值，使模型更关注少数类。

公式推导与细节

1. 线性可分公式为什么是超平面

原定义写成：

$$ \sum_{i=1}^{n}w_i x_i>k $$

把右边移到左边：

$$ \sum_{i=1}^{n}w_i x_i-k>0 $$

令：

$$ \mathbf{w}=(w_1,w_2,\dots,w_n)^T,\quad b=-k $$

则有：

$$ \mathbf{w}^T\mathbf{x}+b>0 $$

同理，另一类样本满足：

$$ \mathbf{w}^T\mathbf{x}+b<0 $$

分界面就是等号成立的位置：

$$ \mathbf{w}^T\mathbf{x}+b=0 $$

这在二维空间是直线，在三维空间是平面，在更高维空间称为超平面。

细节问题：

$k$ 和 $b$ 本质上都是截距项，只是符号不同。
$\mathbf{w}$ 不能是零向量，否则 $\mathbf{w}^T\mathbf{x}+b$ 与 $\mathbf{x}$ 无关，不能形成有效分界面。
同一个超平面可以乘以任意非零常数表示，例如 $\mathbf{w}^T\mathbf{x}+b=0$ 和 $2\mathbf{w}^T\mathbf{x}+2b=0$ 表示同一个超平面。

2. 感知机分类公式的推导

感知机先计算样本到分界超平面一侧的代数值：

$$ z=\mathbf{w}^T\mathbf{x}+b $$

若 $z>0$，样本位于超平面正侧，预测为正类；若 $z<0$，样本位于负侧，预测为负类。因此可以写成：

$$ f(\mathbf{x})=\mathrm{sign}(z) $$

代入 $z$：

$$ f(\mathbf{x})=\mathrm{sign}(\mathbf{w}^T\mathbf{x}+b) $$

细节问题：

$z=0$ 表示样本刚好落在决策边界上，课件中通常把它归为 $+1$，也有教材把它单独处理。
$\mathbf{w}$ 是超平面的法向量，因为超平面上任意两点 $\mathbf{x}_1,\mathbf{x}_2$ 都满足：

$$ \mathbf{w}^T\mathbf{x}_1+b=0,\quad \mathbf{w}^T\mathbf{x}_2+b=0 $$

两式相减：

$$ \mathbf{w}^T(\mathbf{x}_1-\mathbf{x}_2)=0 $$

这说明 $\mathbf{w}$ 与超平面内任意方向向量 $\mathbf{x}_1-\mathbf{x}_2$ 垂直。

3. 线性模型向量形式的推导

属性线性组合为：

$$ f(\mathbf{x})=w_1x_1+w_2x_2+\cdots+w_dx_d+b $$

根据向量内积定义：

$$ \mathbf{w}^T\mathbf{x}= \begin{bmatrix} w_1&w_2&\cdots&w_d \end{bmatrix} \begin{bmatrix} x_1\x_2\\vdots\x_d \end{bmatrix} =\sum_{j=1}^{d}w_jx_j $$

所以：

$$ f(\mathbf{x})=\mathbf{w}^T\mathbf{x}+b $$

如果想把 $b$ 也并入向量，可令：

$$ \hat{\mathbf{x}}=(x_1,x_2,\dots,x_d,1)^T,\quad \hat{\mathbf{w}}=(w_1,w_2,\dots,w_d,b)^T $$

则：

$$ f(\mathbf{x})=\hat{\mathbf{w}}^T\hat{\mathbf{x}} $$

细节问题：

多出的常数特征必须是 $1$，否则 $b$ 无法作为独立截距项。
写成 $\mathbf{w}^T\mathbf{x}$ 时，要注意 $\mathbf{w}$ 和 $\mathbf{x}$ 都默认是列向量。

4. 一元线性回归最小二乘推导

目标是最小化平方误差：

$$ E(w,b)=\sum_{i=1}^{m}(y_i-wx_i-b)^2 $$

令残差为：

$$ e_i=y_i-wx_i-b $$

则：

$$ E(w,b)=\sum_{i=1}^{m}e_i^2 $$

先对 $w$ 求偏导：

$$ \frac{\partial E}{\partial w} =\sum_{i=1}^{m}2e_i\frac{\partial e_i}{\partial w} $$

由于：

$$ \frac{\partial e_i}{\partial w}=-x_i $$

所以：

$$ \frac{\partial E}{\partial w} =-2\sum_{i=1}^{m}x_i(y_i-wx_i-b) $$

展开：

$$ \frac{\partial E}{\partial w} =-2\sum_{i=1}^{m}x_iy_i +2w\sum_{i=1}^{m}x_i^2 +2b\sum_{i=1}^{m}x_i $$

再对 $b$ 求偏导：

$$ \frac{\partial E}{\partial b} =\sum_{i=1}^{m}2e_i\frac{\partial e_i}{\partial b} $$

由于：

$$ \frac{\partial e_i}{\partial b}=-1 $$

所以：

$$ \frac{\partial E}{\partial b} =-2\sum_{i=1}^{m}(y_i-wx_i-b) $$

展开：

$$ \frac{\partial E}{\partial b} =-2\sum_{i=1}^{m}y_i +2w\sum_{i=1}^{m}x_i +2mb $$

令两个偏导都为 0。先看 $b$ 的方程：

$$ -2\sum_{i=1}^{m}y_i+2w\sum_{i=1}^{m}x_i+2mb=0 $$

两边除以 2：

$$ -\sum_{i=1}^{m}y_i+w\sum_{i=1}^{m}x_i+mb=0 $$

移项：

$$ mb=\sum_{i=1}^{m}y_i-w\sum_{i=1}^{m}x_i $$

所以：

$$ b=\frac{1}{m}\sum_{i=1}^{m}y_i-w\frac{1}{m}\sum_{i=1}^{m}x_i $$

记：

$$ \bar{x}=\frac{1}{m}\sum_{i=1}^{m}x_i,\quad \bar{y}=\frac{1}{m}\sum_{i=1}^{m}y_i $$

得到：

$$ b=\bar{y}-w\bar{x} $$

再把 $b=\bar{y}-w\bar{x}$ 代入 $\frac{\partial E}{\partial w}=0$：

$$ -\sum_{i=1}^{m}x_iy_i +w\sum_{i=1}^{m}x_i^2 +b\sum_{i=1}^{m}x_i=0 $$

代入 $b$：

$$ -\sum_{i=1}^{m}x_iy_i +w\sum_{i=1}^{m}x_i^2 +(\bar{y}-w\bar{x})\sum_{i=1}^{m}x_i=0 $$

整理：

$$ w\left(\sum_{i=1}^{m}x_i^2-\bar{x}\sum_{i=1}^{m}x_i\right) =\sum_{i=1}^{m}x_iy_i-\bar{y}\sum_{i=1}^{m}x_i $$

由于：

$$ \bar{x}\sum_{i=1}^{m}x_i =\frac{1}{m}\left(\sum_{i=1}^{m}x_i\right)^2 $$

且：

$$ \bar{y}\sum_{i=1}^{m}x_i =\bar{x}\sum_{i=1}^{m}y_i $$

所以：

$$ w= \frac{\sum_{i=1}^{m}x_iy_i-\bar{x}\sum_{i=1}^{m}y_i} {\sum_{i=1}^{m}x_i^2-\frac{1}{m}\left(\sum_{i=1}^{m}x_i\right)^2} $$

分子也可写为：

$$ \sum_{i=1}^{m}y_i(x_i-\bar{x}) $$

因此：

$$ w= \frac{\sum_{i=1}^{m}y_i(x_i-\bar{x})} {\sum_{i=1}^{m}x_i^2-\frac{1}{m}\left(\sum_{i=1}^{m}x_i\right)^2} $$

最后：

$$ b=\bar{y}-w\bar{x} =\frac{1}{m}\sum_{i=1}^{m}(y_i-wx_i) $$

细节问题：

分母 $\sum x_i^2-\frac{1}{m}(\sum x_i)^2$ 等价于 $\sum (x_i-\bar{x})^2$，表示 $x$ 的离散程度。
若所有 $x_i$ 都相同，则分母为 0，斜率 $w$ 不可唯一确定。
求导时最容易漏掉链式法则中的负号：$e_i=y_i-wx_i-b$，所以对 $w$ 求导是 $-x_i$，对 $b$ 求导是 $-1$。
最小二乘不是最小化误差绝对值，而是最小化误差平方和。

5. 多元线性回归闭式解推导

将所有样本写成矩阵形式。令：

$$ \mathbf{X}= \begin{bmatrix} \hat{\mathbf{x}}_1^T\ \hat{\mathbf{x}}_2^T\ \vdots\ \hat{\mathbf{x}}_m^T \end{bmatrix}, \quad \hat{\mathbf{w}}= \begin{bmatrix} w_1\w_2\\vdots\w_d\b \end{bmatrix}, \quad \mathbf{y}= \begin{bmatrix} y_1\y_2\\vdots\y_m \end{bmatrix} $$

其中 $\mathbf{X}$ 的最后一列全为 1，用来吸收截距 $b$。

预测向量为：

$$ \hat{\mathbf{y}}=\mathbf{X}\hat{\mathbf{w}} $$

残差向量为：

$$ \mathbf{e}=\mathbf{y}-\mathbf{X}\hat{\mathbf{w}} $$

平方误差为：

$$ E(\hat{\mathbf{w}}) =|\mathbf{y}-\mathbf{X}\hat{\mathbf{w}}|_2^2 $$

写成矩阵乘法：

$$ E(\hat{\mathbf{w}}) =(\mathbf{y}-\mathbf{X}\hat{\mathbf{w}})^T (\mathbf{y}-\mathbf{X}\hat{\mathbf{w}}) $$

展开：

$$ E(\hat{\mathbf{w}}) =\mathbf{y}^T\mathbf{y} -2\hat{\mathbf{w}}^T\mathbf{X}^T\mathbf{y} +\hat{\mathbf{w}}^T\mathbf{X}^T\mathbf{X}\hat{\mathbf{w}} $$

对 $\hat{\mathbf{w}}$ 求导：

$$ \frac{\partial E}{\partial \hat{\mathbf{w}}} =-2\mathbf{X}^T\mathbf{y} +2\mathbf{X}^T\mathbf{X}\hat{\mathbf{w}} $$

令导数为 0：

$$ -2\mathbf{X}^T\mathbf{y} +2\mathbf{X}^T\mathbf{X}\hat{\mathbf{w}}=0 $$

两边除以 2 并移项：

$$ \mathbf{X}^T\mathbf{X}\hat{\mathbf{w}} =\mathbf{X}^T\mathbf{y} $$

这称为正规方程（normal equation）。

如果 $\mathbf{X}^T\mathbf{X}$ 可逆，则两边左乘 $(\mathbf{X}^T\mathbf{X})^{-1}$：

$$ \hat{\mathbf{w}}^* =(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} $$

细节问题：

$\mathbf{X}$ 的维度是 $m\times(d+1)$，$\hat{\mathbf{w}}$ 的维度是 $(d+1)\times1$，所以 $\mathbf{X}\hat{\mathbf{w}}$ 才是 $m\times1$。
$\mathbf{X}^T\mathbf{X}$ 可逆通常要求 $\mathbf{X}$ 列满秩，即特征之间没有完全线性相关，且样本量足够。
若 $\mathbf{X}^T\mathbf{X}$ 不可逆，不能直接写闭式逆矩阵。可使用伪逆、加入正则化，或借助归纳偏好选择一个解。
实际计算中一般不显式求逆，而是解线性方程组；显式求逆数值稳定性较差。

6. 对数线性回归与广义线性模型推导

普通线性回归假设：

$$ y=\mathbf{w}^T\mathbf{x}+b $$

但如果 $y$ 与输入之间不是线性关系，而是 $\ln y$ 与输入更接近线性，则令：

$$ \ln y=\mathbf{w}^T\mathbf{x}+b $$

两边取指数：

$$ y=e^{\mathbf{w}^T\mathbf{x}+b} $$

因此模型虽然对参数是线性的，但对原始输出 $y$ 是非线性的。

推广这个想法，令：

$$ g(y)=\mathbf{w}^T\mathbf{x}+b $$

如果 $g$ 可逆，则：

$$ y=g^{-1}(\mathbf{w}^T\mathbf{x}+b) $$

细节问题：

对数线性回归要求 $y>0$，否则 $\ln y$ 没有实数意义。
联系函数 $g$ 通常要求单调可微，这样预测值和线性输出之间的关系稳定、可优化。
广义线性模型的“线性”指的是 $\mathbf{w}^T\mathbf{x}+b$ 这部分对参数线性，不代表最终 $y$ 一定是输入的线性函数。

7. Logistic 函数由对数几率推导

令：

$$ p=P(y=1\mid\mathbf{x}) $$

则：

$$ P(y=0\mid\mathbf{x})=1-p $$

几率定义为：

$$ \frac{p}{1-p} $$

对数几率回归假设对数几率与输入线性相关：

$$ \ln\frac{p}{1-p}=\mathbf{w}^T\mathbf{x}+b $$

令：

$$ \eta=\mathbf{w}^T\mathbf{x}+b $$

则：

$$ \ln\frac{p}{1-p}=\eta $$

两边取指数：

$$ \frac{p}{1-p}=e^\eta $$

两边同乘 $1-p$：

$$ p=e^\eta(1-p) $$

展开：

$$ p=e^\eta-e^\eta p $$

把含 $p$ 的项移到左边：

$$ p+e^\eta p=e^\eta $$

提取 $p$：

$$ p(1+e^\eta)=e^\eta $$

所以：

$$ p=\frac{e^\eta}{1+e^\eta} $$

分子分母同除以 $e^\eta$：

$$ p=\frac{1}{1+e^{-\eta}} $$

代回 $\eta=\mathbf{w}^T\mathbf{x}+b$：

$$ P(y=1\mid\mathbf{x}) =\frac{1}{1+e^{-(\mathbf{w}^T\mathbf{x}+b)}} $$

同时：

$$ P(y=0\mid\mathbf{x}) =1-p =\frac{1}{1+e^{\mathbf{w}^T\mathbf{x}+b}} $$

细节问题：

Logistic 函数输出范围是 $(0,1)$，适合作为概率近似。
当 $\eta=0$ 时，$p=0.5$，所以默认阈值 0.5 等价于判断 $\mathbf{w}^T\mathbf{x}+b$ 是否大于 0。
Logistic 函数导数常用结论为：

$$ \frac{dp}{d\eta}=p(1-p) $$

推导如下：

$$ p=(1+e^{-\eta})^{-1} $$

$$ \frac{dp}{d\eta} =-(1+e^{-\eta})^{-2}(-e^{-\eta}) =\frac{e^{-\eta}}{(1+e^{-\eta})^2} $$

又因为：

$$ p=\frac{1}{1+e^{-\eta}},\quad 1-p=\frac{e^{-\eta}}{1+e^{-\eta}} $$

所以：

$$ \frac{dp}{d\eta}=p(1-p) $$

8. 对数几率回归的极大似然推导

对每个样本，令：

$$ p_i=P(y_i=1\mid\mathbf{x}_i) $$

因为 $y_i\in{0,1}$，可用伯努利分布统一表示：

$$ P(y_i\mid\mathbf{x}_i) =p_i^{y_i}(1-p_i)^{1-y_i} $$

验证：

若 $y_i=1$，则 $P(y_i\mid\mathbf{x}_i)=p_i$。
若 $y_i=0$，则 $P(y_i\mid\mathbf{x}_i)=1-p_i$。

假设样本独立同分布，则整体似然函数为：

$$ L(\mathbf{w},b) =\prod_{i=1}^{m}p_i^{y_i}(1-p_i)^{1-y_i} $$

取对数得到对数似然：

$$ \ell(\mathbf{w},b) =\sum_{i=1}^{m} \left[ y_i\ln p_i+(1-y_i)\ln(1-p_i) \right] $$

令：

$$ \eta_i=\mathbf{w}^T\mathbf{x}_i+b $$

由 Logistic 函数：

$$ p_i=\frac{e^{\eta_i}}{1+e^{\eta_i}}, \quad 1-p_i=\frac{1}{1+e^{\eta_i}} $$

所以：

$$ \ln p_i =\ln\frac{e^{\eta_i}}{1+e^{\eta_i}} =\eta_i-\ln(1+e^{\eta_i}) $$

以及：

$$ \ln(1-p_i) =\ln\frac{1}{1+e^{\eta_i}} =-\ln(1+e^{\eta_i}) $$

代回对数似然：

$$ \ell(\mathbf{w},b) =\sum_{i=1}^{m} \left[ y_i\eta_i-\ln(1+e^{\eta_i}) \right] $$

极大似然是最大化 $\ell$，等价于最小化负对数似然：

$$ J(\mathbf{w},b) =-\ell(\mathbf{w},b) =\sum_{i=1}^{m} \left[ \ln(1+e^{\eta_i})-y_i\eta_i \right] $$

若把 $b$ 吸收到参数中，令：

$$ \boldsymbol{\beta}=(\mathbf{w};b),\quad \hat{\mathbf{x}}_i=(\mathbf{x}_i;1) $$

则：

$$ \eta_i=\boldsymbol{\beta}^T\hat{\mathbf{x}}_i $$

对 $\boldsymbol{\beta}$ 求梯度：

$$ \frac{\partial J}{\partial \boldsymbol{\beta}} =\sum_{i=1}^{m} \left[ \frac{e^{\eta_i}}{1+e^{\eta_i}}-y_i \right]\hat{\mathbf{x}}_i $$

由于：

$$ \frac{e^{\eta_i}}{1+e^{\eta_i}}=p_i $$

所以：

$$ \frac{\partial J}{\partial \boldsymbol{\beta}} =\sum_{i=1}^{m}(p_i-y_i)\hat{\mathbf{x}}_i $$

矩阵形式为：

$$ \nabla J(\boldsymbol{\beta})=\mathbf{X}^T(\mathbf{p}-\mathbf{y}) $$

其 Hessian 矩阵为：

$$ \nabla^2J(\boldsymbol{\beta}) =\mathbf{X}^T\mathbf{R}\mathbf{X} $$

其中：

$$ \mathbf{R}=\mathrm{diag}(p_1(1-p_1),p_2(1-p_2),\dots,p_m(1-p_m)) $$

因为 $p_i(1-p_i)\ge 0$，所以 Hessian 半正定，目标函数是凸函数。

细节问题：

对数几率回归一般没有像线性回归那样的闭式解，需要梯度下降、牛顿法或拟牛顿法。
若数据完全线性可分，极大似然解可能趋向无穷大，参数不收敛，此时常加入正则化。
计算 $\ln(1+e^\eta)$ 时，如果 $\eta$ 很大，直接算 $e^\eta$ 可能溢出，实际实现常用数值稳定写法。
负对数似然也称为交叉熵损失，二分类交叉熵正是从伯努利极大似然推导而来。

9. 类别不平衡阈值调整推导

默认情况下，模型按后验概率大小分类：

$$ P(y=1\mid\mathbf{x})>P(y=0\mid\mathbf{x}) $$

等价于：

$$ \frac{P(y=1\mid\mathbf{x})}{P(y=0\mid\mathbf{x})}>1 $$

如果正负类先验比例差异很大，直接使用阈值 0.5 往往偏向多数类。设训练集中的正负类比例为：

$$ \frac{m^+}{m^-} $$

真实任务中希望采用的正负类先验比例为：

$$ \frac{\pi^+}{\pi^-} $$

则可以对模型输出的 odds 做再缩放：

$$ \frac{P(y=1\mid\mathbf{x})}{P(y=0\mid\mathbf{x})} \cdot \frac{\pi^+/\pi^-}{m^+/m^-}

1 $$

等价于：

$$ \frac{P(y=1\mid\mathbf{x})}{P(y=0\mid\mathbf{x})}

\frac{m^+/m^-}{\pi^+/\pi^-} $$

如果用阈值 $t$ 表示正类概率判断：

$$ P(y=1\mid\mathbf{x})>t $$

则阈值移动本质上是在改变 $t$，而不是改变模型参数本身。

细节问题：

若更关注少数正类，通常会降低正类判定阈值，使更多样本被判为正类。
阈值降低通常会提高 Recall，但可能降低 Precision。
再缩放需要估计真实先验比例 $\pi^+/\pi^-$，而这个量在实际任务中经常不准确。
类别不平衡不应只看 Accuracy，通常要结合 Precision、Recall、F1、P-R 曲线等指标。

考试中可以这样写

线性模型是通过输入属性的线性组合进行预测的模型，基本形式为 $f(\mathbf{x})=\mathbf{w}^T\mathbf{x}+b$。它既可以用于回归，也可以通过联系函数扩展到分类任务。线性模型形式简单、可解释性强，是许多复杂模型的基础。

线性回归以均方误差最小化为目标，通常使用最小二乘法求解。当 $\mathbf{X}^T\mathbf{X}$ 满秩时，多元线性回归具有闭式解 $(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$；若不满秩，则可能存在多个解，需要引入归纳偏好或正则化。

对数几率回归用于二分类任务，通过 Logistic 函数将线性模型输出映射为 $[0,1]$ 内的概率，并建立对数几率与线性预测值之间的关系。它不需要事先假设数据分布，可输出类别的近似概率，通常用极大似然法和数值优化方法求解。

速记

线性组合 → 最小二乘 → 联系函数 → 对率回归 → 多分类拆解 → 类别不平衡处理。

4. 决策树

本章是重点。核心是掌握决策树如何构造、如何预测、何时停止，以及 ID3、C4.5、CART 三类算法的划分指标。

决策树模型

决策树基于树结构进行决策：

内部结点：对应某个属性上的测试。
分支：对应测试的一种可能结果。
叶结点：对应最终预测结果。

学习过程：

根据训练样本递归选择划分属性，构造从根结点到叶结点的判定测试序列。

预测过程：

测试样本从根结点开始，根据各内部结点的属性测试沿分支向下走，直到到达叶结点，叶结点的类别就是预测结果。

决策树如何构造

决策树采用**分而治之（divide-and-conquer）策略，自根向叶递归构造。

基本过程：

当前结点拿到一个样本集合 $D$ 和一个候选属性集合 $A$。
判断是否满足停止条件。
若不停止，则从 $A$ 中选择最优划分属性 $a^*$。
按 $a^*$ 的不同取值把 $D$ 划分为若干子集。
对每个子集递归生成子树。

伪代码理解：

TreeGenerate(D, A):
    生成结点 node
    若 D 中样本全属于同一类别:
        node 标记为该类别，返回
    若 A 为空，或 D 中样本在 A 上取值都相同:
        node 标记为 D 中样本最多的类别，返回
    从 A 中选择最优划分属性 a*
    对 a* 的每个取值 v:
        令 Dv = D 中在 a* 上取值为 v 的样本子集
        若 Dv 为空:
            分支结点标记为 D 中样本最多的类别
        否则:
            递归生成 TreeGenerate(Dv, A - {a*})

细节问题：

若当前结点样本已经纯净，就不需要继续划分。
若属性用完，或所有样本在剩余属性上取值相同，就无法继续有效划分。
若某个分支没有训练样本，应使用父结点中的多数类作为该分支的预测类别。
每次选择划分属性，本质是在让子结点尽可能“纯”。

决策树如何用于判断

对于一个新样本 $\mathbf{x}$：

从根结点开始。
查看当前内部结点对应的属性。
根据 $\mathbf{x}$ 在该属性上的取值选择对应分支。
重复该过程，直到到达叶结点。
输出叶结点类别。

例子：

纹理 = 清晰 -> 根蒂 = 蜷缩 -> 判断为好瓜
纹理 = 模糊 -> 判断为坏瓜

停止条件

课件中的三类停止条件：

当前结点包含的样本全属于同一类别，无需划分。
当前属性集为空，或所有样本在所有属性上取值相同，无法划分。
当前结点包含的样本集合为空，不能划分。

对应处理：

情况	处理方式
样本全属于同一类	标记为该类
属性集为空或属性取值相同	标记为当前结点样本最多的类别
样本集合为空	标记为父结点样本最多的类别

三类算法核心指标

算法	核心指标	选择原则
ID3	信息增益	选择信息增益最大的属性
C4.5	增益率	先筛选信息增益高于平均的属性，再选增益率最高的属性
CART	基尼指数	选择划分后基尼指数最小的属性

ID3：信息增益

1. 信息熵

信息熵用于度量样本集合的不确定性，也可以理解为“不纯度”。

设样本集合 $D$ 中共有 $|\mathcal{Y}|$ 个类别，第 $k$ 类样本所占比例为 $p_k$，则：

$$ Ent(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2 p_k $$

约定：

$$ 0\log_2 0=0 $$

因为当 $p\to 0^+$ 时：

$$ \lim_{p\to 0^+}p\log_2 p=0 $$

所以这个约定是合理的。

信息熵性质：

$Ent(D)$ 越小，样本集合越纯。
若所有样本属于同一类，则 $Ent(D)=0$。
若各类别比例越均匀，不确定性越大，信息熵越大。
最大值为 $\log_2|\mathcal{Y}|$。

二分类时，若正例比例为 $p$，反例比例为 $1-p$，则：

$$ Ent(D)=-p\log_2p-(1-p)\log_2(1-p) $$

细节问题：

课件例子默认使用 $\log_2$，所以熵的单位是 bit。
计算时不要漏掉前面的负号。
$p_k$ 是比例，不是样本数；要先用该类样本数除以总样本数。

2. 信息增益公式推导

划分前，样本集合 $D$ 的不确定性为：

$$ Ent(D) $$

若用离散属性 $a$ 划分，属性 $a$ 有 $V$ 个可能取值：

$$ {a^1,a^2,\dots,a^V} $$

对应产生 $V$ 个子集：

$$ D^1,D^2,\dots,D^V $$

其中 $D^v$ 表示在属性 $a$ 上取值为 $a^v$ 的样本集合。

划分后，第 $v$ 个分支的重要性由样本占比决定：

$$ \frac{|D^v|}{|D|} $$

所以划分后的加权平均信息熵为：

$$ \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$

信息增益定义为“划分前的不确定性”减去“划分后的不确定性”：

$$ Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$

推导理解：

信息增益 = 原来的混乱程度 - 划分后的平均混乱程度

若某个属性划分后使各子集更纯，则划分后的加权熵更小，信息增益更大。

ID3 的选择策略：

$$ a^*=\arg\max_{a\in A}Gain(D,a) $$

细节问题：

子集熵要乘权重 $\frac{|D^v|}{|D|}$，不能直接求平均。
信息增益越大越好。
信息增益偏好取值数目多的属性。例如“编号”这种属性几乎能把每个样本单独分开，信息增益很大，但泛化能力很差。

3. 信息增益手算步骤

给定数据集 $D$ 和属性 $a$：

统计 $D$ 中各类别比例，计算 $Ent(D)$。
按属性 $a$ 的每个取值划分出 $D^1,\dots,D^V$。
分别统计每个 $D^v$ 中各类别比例，计算 $Ent(D^v)$。
计算划分后加权熵：

$$ \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$

用划分前熵减去划分后加权熵，得到 $Gain(D,a)$。

西瓜数据集课件例子：

根结点共有 17 个样本，正例 8 个，反例 9 个：

$$ Ent(D)=-\frac{8}{17}\log_2\frac{8}{17} -\frac{9}{17}\log_2\frac{9}{17} =0.998 $$

以“色泽”为例，有三个取值：青绿、乌黑、浅白。

若：

$$ Ent(D^{青绿})=1.000,\quad Ent(D^{乌黑})=0.918,\quad Ent(D^{浅白})=0.722 $$

且三个子集大小分别为 6、6、5，则：

$$ Gain(D,色泽) =0.998-\left( \frac{6}{17}\times1.000 +\frac{6}{17}\times0.918 +\frac{5}{17}\times0.722 \right) =0.109 $$

课件中类似计算所有属性后，“纹理”的信息增益最大，因此根结点选择“纹理”。

C4.5：增益率

1. 为什么需要增益率

信息增益的缺点：

对取值数目较多的属性有偏好。

极端例子是“编号”属性。每个样本编号都不同，用编号划分后每个子集可能只有一个样本，子集纯度很高，信息增益很大，但这个划分没有泛化意义。

C4.5 使用**增益率（gain ratio）来缓解这个问题。

2. 固有值 IV

属性 $a$ 的固有值定义为：

$$ IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|} \log_2\frac{|D^v|}{|D|} $$

它度量属性 $a$ 的取值本身带来的划分复杂度。

属性取值越多，通常 $IV(a)$ 越大。

3. 增益率公式推导

信息增益为：

$$ Gain(D,a) $$

属性本身的划分复杂度为：

$$ IV(a) $$

为了惩罚取值数目过多的属性，用信息增益除以固有值：

$$ Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} $$

推导理解：

增益率 = 单位划分复杂度带来的信息增益

C4.5 的启发式策略：

先找出信息增益高于平均水平的候选属性。
再从这些属性中选择增益率最高的属性。

细节问题：

不能只看增益率，否则会偏好取值数目很少的属性。
$IV(a)$ 可能很小，直接用增益率会放大某些不稳定属性，所以 C4.5 先用信息增益做过滤。
增益率越大越好。

CART：基尼指数

1. 基尼值的含义

基尼值用于度量样本集合的不纯度。它反映：

从样本集合 $D$ 中随机抽取两个样本，它们类别标记不一致的概率。

设第 $k$ 类样本比例为 $p_k$。

随机抽到一个样本属于第 $k$ 类的概率是 $p_k$，另一个样本不属于第 $k$ 类的概率是 $1-p_k$，所以类别不一致的概率可写为：

$$ Gini(D)=\sum_{k=1}^{|\mathcal{Y}|}p_k(1-p_k) $$

展开：

$$ Gini(D)=\sum_{k=1}^{|\mathcal{Y}|}(p_k-p_k^2) $$

因为：

$$ \sum_{k=1}^{|\mathcal{Y}|}p_k=1 $$

所以：

$$ Gini(D)=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 $$

这就是基尼值公式：

$$ Gini(D)=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 $$

二分类时，若正例比例为 $p$，反例比例为 $1-p$：

$$ Gini(D)=1-p^2-(1-p)^2 $$

展开：

$$ Gini(D)=2p(1-p) $$

性质：

$Gini(D)$ 越小，数据集越纯。
若所有样本属于同一类，$Gini(D)=0$。
二分类最不纯时 $p=0.5$，此时 $Gini(D)=0.5$。

细节问题：

熵和基尼都衡量不纯度，但基尼不需要计算对数，计算更简单。
基尼指数越小越好，和信息增益“越大越好”方向相反。

2. 属性划分下的基尼指数

若属性 $a$ 有 $V$ 个取值，划分后得到：

$$ D^1,D^2,\dots,D^V $$

则属性 $a$ 划分后的基尼指数为：

$$ Gini_index(D,a) =\sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v) $$

CART 选择使划分后基尼指数最小的属性：

$$ a^*=\arg\min_{a\in A}Gini_index(D,a) $$

推导理解：

基尼指数 = 划分后各分支不纯度的加权平均

如果某个属性能让各个子集更纯，则各子集 $Gini(D^v)$ 更小，加权平均也更小。

3. CART 的特点

CART 全称是 Classification And Regression Tree。

特点：

既可用于分类，也可用于回归。
通常生成二叉树。
分类树使用基尼指数。
回归树常使用平方误差最小化。

分类树中，如果是离散属性，CART 往往也会把划分转化为二分问题；如果是连续属性，则选择最优切分点。

三个指标对比

指标	衡量什么	优化方向	典型算法	易错点
信息增益	划分前后熵减少多少	越大越好	ID3	偏好取值多的属性
增益率	单位固有值带来的信息增益	越大越好	C4.5	不能只看增益率，需先过滤低增益属性
基尼指数	划分后的不纯度	越小越好	CART	方向和信息增益相反

奥卡姆剃刀与决策树

奥卡姆剃刀思想：

若多个假设都能解释训练数据，应优先选择较简单的假设。

在决策树中体现为：

优先选择较短的树。
优先选择更靠近根结点就能有效划分数据的属性。
避免生成过多只适应训练集细节的分支。

以 ID3 为例：

搜索策略会产生归纳偏置。
信息增益高的属性更容易靠近根结点。
这相当于偏好某些结构更简单、划分更有效的树。

细节问题：

奥卡姆剃刀不是无条件选择最简单模型。
正确理解是：在能较好解释数据的候选假设中，优先选择更简单的。
如果真实规律本身复杂，过度追求简单会导致欠拟合。

为什么要剪枝

决策树如果为了尽可能正确分类训练样本而不断划分，可能产生过多分支。

结果：

训练集表现很好。
测试集表现变差。
模型学习到了训练数据中的噪声和偶然性。

这就是过拟合。

剪枝的目的：

主动去掉一些分支，降低模型复杂度，从而提升泛化能力。

课件强调：

划分选择准则对树大小影响较大，但对泛化性能影响有限。
剪枝方法和剪枝程度对泛化性能影响更显著。
在有噪声的数据中，剪枝可能明显提升泛化性能。

剪枝有什么作用

剪枝的主要作用：

降低过拟合风险。
减少树的规模。
提高模型泛化能力。
提高预测速度。
增强可解释性。

但也有风险：

剪枝过强会导致欠拟合。
剪掉有用分支会降低模型表达能力。

剪枝的基本方式

1. 预剪枝

预剪枝是在决策树生成过程中提前停止某些分支的生长。

基本做法：

对当前结点，先评估“不划分”的验证集性能。
再评估“划分后”的验证集性能。
若划分不能提升验证集性能，则禁止划分，把当前结点作为叶结点。

形式化理解：

$$ Acc_{after}\le Acc_{before} \quad\Rightarrow\quad 停止划分 $$

若：

$$ Acc_{after}>Acc_{before} $$

则允许划分。

优点：

训练时间减少。
测试时间减少。
树较小。
过拟合风险降低。

缺点：

贪心地提前停止，可能剪掉后续有用结构。
欠拟合风险增加。

2. 后剪枝

后剪枝是先生成一棵完整决策树，再自底向上考察是否剪枝。

基本做法：

先训练出完整树。
从非叶结点开始，尝试把该子树替换为叶结点。
叶结点类别设为该子树覆盖训练样本中的多数类。
比较剪枝前后在验证集上的性能。
若剪枝后验证集性能不下降或提升，则可以剪枝。

常见判断：

$$ Acc_{pruned}\ge Acc_{original} \quad\Rightarrow\quad 剪枝 $$

若：

$$ Acc_{pruned}<Acc_{original} $$

则保留原子树。

优点：

通常泛化性能优于预剪枝。
欠拟合风险相对较小。

缺点：

需要先生成完整树，训练时间更长。
需要额外验证集或其他评估方法。

3. 预剪枝与后剪枝对比

角度	预剪枝	后剪枝
发生时机	建树过程中	完整建树之后
训练开销	较小	较大
测试开销	较小	较小
过拟合风险	降低	降低
欠拟合风险	增加	基本不变或较小
泛化性能	不一定最优	通常更好

连续值处理（了解）

决策树可以通过离散化处理连续属性。

常见方法：二分法（bi-partition）。

设连续属性 $a$ 在样本中的取值排序为：

$$ a^1\le a^2\le \cdots\le a^n $$

候选切分点通常取相邻取值的中点：

$$ t_i=\frac{a^i+a^{i+1}}{2},\quad i=1,2,\dots,n-1 $$

每个切分点 $t$ 把数据划为两部分：

$$ D^-={\mathbf{x}\in D\mid a(\mathbf{x})\le t} $$

$$ D^+={\mathbf{x}\in D\mid a(\mathbf{x})>t} $$

然后对每个候选切分点计算信息增益、增益率或基尼指数，选择最优切分点。

细节问题：

$n$ 个不同取值最多产生 $n-1$ 个候选切分点。
连续属性在决策树中通常可以被多次使用。
离散属性在某些算法中使用一次后会从候选属性集中移除。

缺失值处理（了解）

现实数据中可能有属性值缺失。

如果简单丢弃含缺失值样本，会造成数据浪费。

需要解决两个问题：

如何在属性有缺失时选择划分属性？
选定划分属性后，若样本在该属性上的值缺失，样本该进入哪个分支？

基本思想：

样本赋权，权重划分。

1. 划分属性选择

对属性 $a$，先只使用在 $a$ 上无缺失的样本来估计该属性的划分效果。

设无缺失样本集合为 $\tilde{D}$，其在全部样本中的权重比例为：

$$ \rho=\frac{\sum_{\mathbf{x}\in \tilde{D}}w_{\mathbf{x}}} {\sum_{\mathbf{x}\in D}w_{\mathbf{x}}} $$

则可将属性 $a$ 在无缺失样本上的信息增益乘以 $\rho$，作为带缺失情况下的有效信息增益。

直观理解：

无缺失样本越多，属性评估越可信。
无缺失样本越少，该属性的有效增益应被打折。

2. 缺失样本如何进入分支

若样本 $\mathbf{x}$ 在划分属性 $a$ 上缺失，不把它硬分到某一个分支，而是按各分支样本比例同时进入多个分支。

若第 $v$ 个分支的无缺失样本权重比例为：

$$ r_v=\frac{\sum_{\mathbf{x}\in D^v}w_{\mathbf{x}}} {\sum_{\mathbf{x}\in \tilde{D}}w_{\mathbf{x}}} $$

则缺失样本以权重 $r_v w_{\mathbf{x}}$ 进入第 $v$ 个分支。

细节问题：

缺失样本不是复制成多个完整样本，而是按权重拆分。
各分支权重之和应保持为原样本权重。
学习开始时，通常所有样本权重为 1。

树到规则的转换（了解）

一棵决策树可以转化为规则集。

转换方式：

每条从根结点到叶结点的路径对应一条规则。
路径上的属性测试组成规则前件。
叶结点类别作为规则后件。

例子：

IF 纹理 = 清晰 AND 密度 <= 0.381
THEN 坏瓜

IF 纹理 = 稍糊 AND 触感 = 软粘
THEN 好瓜

好处：

提高可理解性。
可进一步做规则合并、规则简化和规则泛化。
有时规则集的泛化能力优于原决策树。

延伸内容（基本不考）

了解即可：

单变量决策树产生轴平行分类边界。
多变量决策树可以在结点处使用多个属性组合，例如斜决策树。
随机森林、XGBoost 等是基于决策树的重要集成方法。
决策树在表格数据上仍然非常强。
神经支持决策树、LLM 辅助构树等属于延伸方向。

公式推导与细节

1. 信息熵为什么能表示不纯度

信息量常定义为：

$$ I(x)=-\log_2 P(x) $$

事件概率越小，发生后带来的信息量越大。

对于样本集合 $D$，类别 $k$ 出现概率为 $p_k$，则类别标记的平均信息量为：

$$ \sum_{k=1}^{|\mathcal{Y}|}p_kI(k) $$

代入 $I(k)=-\log_2p_k$：

$$ Ent(D)=\sum_{k=1}^{|\mathcal{Y}|}p_k(-\log_2p_k) $$

即：

$$ Ent(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k $$

如果样本全属于一类，例如 $p_1=1$，其他类别概率为 0：

$$ Ent(D)=-1\log_2 1=0 $$

说明没有不确定性。

如果二分类中 $p_1=p_2=0.5$：

$$ Ent(D)=-0.5\log_2 0.5-0.5\log_2 0.5=1 $$

说明不确定性最大。

2. 信息增益为什么是熵的减少量

划分前，不知道样本类别时的不确定性是：

$$ Ent(D) $$

用属性 $a$ 划分后，样本会落入某个分支 $D^v$。落入第 $v$ 个分支的概率为：

$$ P(D^v)=\frac{|D^v|}{|D|} $$

在该分支内部，类别不确定性为：

$$ Ent(D^v) $$

所以划分后的条件熵为：

$$ Ent(D\mid a) =\sum_{v=1}^{V}P(D^v)Ent(D^v) $$

代入 $P(D^v)$：

$$ Ent(D\mid a) =\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$

信息增益就是：

$$ Gain(D,a)=Ent(D)-Ent(D\mid a) $$

所以：

$$ Gain(D,a) =Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$

细节问题：

$Ent(D\mid a)$ 是划分后的条件熵，不是某一个子集的熵。
若划分没有带来任何纯度提升，则 $Ent(D\mid a)\approx Ent(D)$，信息增益接近 0。
若划分后每个子集都纯净，则 $Ent(D^v)=0$，信息增益达到最大。

3. 增益率为什么能惩罚多取值属性

如果属性 $a$ 的取值很多，划分后产生很多分支，信息增益可能虚高。

属性 $a$ 本身的划分复杂度为：

$$ IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|} \log_2\frac{|D^v|}{|D|} $$

这和熵形式相同，只不过它度量的是“样本被分到哪个分支”的不确定性。

当属性取值很多且分支较均匀时，$IV(a)$ 较大。

因此：

$$ Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} $$

会降低多取值属性的得分。

细节问题：

若某属性只有一个取值，则 $IV(a)=0$，它本身也无法有效划分。
若某属性取值极多，$Gain(D,a)$ 可能大，但 $IV(a)$ 也大。
C4.5 不直接全局最大化增益率，而是先排除信息增益偏低的属性。

4. 基尼公式的概率推导

随机抽取两个样本，类别不一致的概率可以写为：

$$ \sum_{k=1}^{|\mathcal{Y}|}P(\text{第一个样本属于 }k) P(\text{第二个样本不属于 }k) $$

第一个样本属于第 $k$ 类的概率为：

$$ p_k $$

第二个样本不属于第 $k$ 类的概率为：

$$ 1-p_k $$

因此：

$$ Gini(D)=\sum_{k=1}^{|\mathcal{Y}|}p_k(1-p_k) $$

展开：

$$ Gini(D)=\sum_{k=1}^{|\mathcal{Y}|}p_k-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 $$

由于所有类别概率之和为 1：

$$ \sum_{k=1}^{|\mathcal{Y}|}p_k=1 $$

所以：

$$ Gini(D)=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 $$

属性 $a$ 划分后的基尼指数是各分支基尼值的加权平均：

$$ Gini_index(D,a)= \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v) $$

选择：

$$ a^*=\arg\min_{a\in A}Gini_index(D,a) $$

细节问题：

基尼值越小越纯。
计算 CART 时不要误选最大值。
若某个分支样本很多，它对最终 $Gini_index$ 的影响更大。

考试中可以这样写

决策树是一种基于树结构的监督学习模型。内部结点表示属性测试，分支表示测试结果，叶结点表示预测类别。学习时从根结点开始递归选择最优划分属性，预测时样本沿属性测试路径下行直到叶结点。

ID3 使用信息增益选择划分属性。信息熵度量样本集合不纯度，信息增益等于划分前熵减去划分后加权熵，选择信息增益最大的属性。但信息增益偏好取值数目多的属性。

C4.5 使用增益率缓解 ID3 的多取值偏好。增益率等于信息增益除以属性固有值。实际选择时通常先筛选信息增益高于平均水平的属性，再从中选择增益率最高的属性。

CART 使用基尼指数进行划分。基尼值 $Gini(D)=1-\sum_kp_k^2$ 表示随机抽取两个样本类别不一致的概率，基尼指数是划分后各子集基尼值的加权平均。CART 选择基尼指数最小的划分。

剪枝是决策树防止过拟合的主要手段。预剪枝在建树过程中提前停止划分，训练和测试开销较小，但欠拟合风险较高；后剪枝先生成完整树，再根据验证集性能自底向上剪去无用子树，通常泛化性能更好。

速记

建树递归选属性 → ID3 看信息增益最大 → C4.5 看增益率最高 → CART 看基尼指数最小 → 过拟合靠剪枝。

5. 支持向量机 SVM

本章是重点。老师强调：距离公式和最大间隔思想是 SVM 推导的基础。

从感知机到支持向量机

感知机和 SVM 都是线性分类模型，基本分类边界都是超平面：

$$ f(\mathbf{x})=\mathbf{w}^T\mathbf{x}+b $$

预测规则：

$$ \hat{y}=\mathrm{sign}(\mathbf{w}^T\mathbf{x}+b) $$

其中 $y\in{+1,-1}$。

感知机只要求把训练样本分对：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)>0 $$

如果数据线性可分，满足条件的超平面通常有无穷多个。

SVM 进一步追问：

在所有能正确分类训练样本的超平面中，哪一个最好？

SVM 的答案是：

选择距离两类样本都尽可能远的那个超平面，即最大化最小间隔。

逻辑链条：

感知机：只要分对
SVM：不仅要分对，还要离分类边界尽可能远
最大间隔：让最靠近超平面的样本也尽量远
支持向量：决定最小间隔的那些样本

SVM 的核心思想

一个样本到分类超平面的垂直距离称为该样本的间隔（margin）。

SVM 要最大化所有训练样本中最小的间隔：

$$ \max_{\mathbf{w},b}\min_i \frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|} $$

其中：

$\mathbf{w}^T\mathbf{x}+b=0$ 是分类超平面。
$|\mathbf{w}|$ 是法向量长度。
$y_i(\mathbf{w}^T\mathbf{x}_i+b)>0$ 表示分类正确。
具有最小间隔的样本称为支持向量（support vectors）。

直观理解：

感知机只看分类是否正确。
SVM 还看分类的确信度。
离超平面越远，分类越稳定。
最大间隔通常意味着更好的鲁棒性和泛化能力。

点到分类超平面的距离

设分类超平面为：

$$ \mathbf{w}^T\mathbf{x}+b=0 $$

点 $\mathbf{x}$ 到该超平面的距离为：

$$ \frac{|\mathbf{w}^T\mathbf{x}+b|}{|\mathbf{w}|} $$

若样本标签 $y_i\in{+1,-1}$，并且分类正确，则：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)>0 $$

于是带标签的几何间隔可写为：

$$ \gamma_i= \frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|} $$

距离公式详细推导

设点 $\mathbf{x}$ 在超平面上的投影点为 $\mathbf{x}_{\perp}$。

因为 $\mathbf{w}$ 是超平面的法向量，所以从 $\mathbf{x}_{\perp}$ 到 $\mathbf{x}$ 的距离向量方向与 $\mathbf{w}$ 平行。

单位法向量为：

$$ \frac{\mathbf{w}}{|\mathbf{w}|} $$

因此可以写成：

$$ \mathbf{x} =\mathbf{x}_{\perp}+r\frac{\mathbf{w}}{|\mathbf{w}|} $$

其中 $r$ 是带符号距离：可能为正、负或 0。

两边左乘 $\mathbf{w}^T$ 并加上 $b$：

$$ \mathbf{w}^T\mathbf{x}+b =\mathbf{w}^T\mathbf{x}_{\perp}+b +r\mathbf{w}^T\frac{\mathbf{w}}{|\mathbf{w}|} $$

因为 $\mathbf{x}_{\perp}$ 在超平面上，所以：

$$ \mathbf{w}^T\mathbf{x}_{\perp}+b=0 $$

又因为：

$$ \mathbf{w}^T\frac{\mathbf{w}}{|\mathbf{w}|} =\frac{\mathbf{w}^T\mathbf{w}}{|\mathbf{w}|} =\frac{|\mathbf{w}|^2}{|\mathbf{w}|} =|\mathbf{w}| $$

所以：

$$ \mathbf{w}^T\mathbf{x}+b=r|\mathbf{w}| $$

得到带符号距离：

$$ r=\frac{\mathbf{w}^T\mathbf{x}+b}{|\mathbf{w}|} $$

真正的几何距离取绝对值：

$$ distance(\mathbf{x},H) =|r| =\frac{|\mathbf{w}^T\mathbf{x}+b|}{|\mathbf{w}|} $$

对于带标签样本，若分类正确，则 $y_i(\mathbf{w}^T\mathbf{x}_i+b)>0$，所以可以去掉绝对值：

$$ \gamma_i= \frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|} $$

细节问题：

$\mathbf{w}$ 是法向量，不是超平面上的方向向量。
距离公式分母一定是 $|\mathbf{w}|$，不能漏。
$\mathbf{w}^T\mathbf{x}+b$ 本身不是距离，它会随 $\mathbf{w},b$ 等比例缩放。
几何距离不随 $(\mathbf{w},b)$ 同比例缩放而改变。

函数间隔与几何间隔

定义函数间隔：

$$ \hat{\gamma}_i=y_i(\mathbf{w}^T\mathbf{x}_i+b) $$

定义几何间隔：

$$ \gamma_i=\frac{\hat{\gamma}_i}{|\mathbf{w}|} =\frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|} $$

如果把参数同时放大 $c>0$：

$$ (\mathbf{w},b)\to(c\mathbf{w},cb) $$

预测结果不变：

$$ \mathrm{sign}(c\mathbf{w}^T\mathbf{x}+cb) =\mathrm{sign}(c(\mathbf{w}^T\mathbf{x}+b)) =\mathrm{sign}(\mathbf{w}^T\mathbf{x}+b) $$

函数间隔会变成原来的 $c$ 倍：

$$ y_i(c\mathbf{w}^T\mathbf{x}_i+cb) =c y_i(\mathbf{w}^T\mathbf{x}_i+b) $$

几何间隔不变：

$$ \frac{c y_i(\mathbf{w}^T\mathbf{x}_i+b)} {|c\mathbf{w}|} =\frac{c y_i(\mathbf{w}^T\mathbf{x}_i+b)} {c|\mathbf{w}|} =\frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)} {|\mathbf{w}|} $$

细节问题：

函数间隔依赖参数尺度，不适合直接作为最终优化目标。
几何间隔不受参数缩放影响，才是真正的距离。
SVM 推导中会人为固定最小函数间隔为 1，从而消除尺度不确定性。

由距离公式构造 SVM 目标函数

SVM 原始目标是最大化最小几何间隔：

$$ \max_{\mathbf{w},b}\min_i \frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|} $$

由于 $(\mathbf{w},b)$ 可以任意等比例缩放，而几何间隔不变，因此可以规定最小函数间隔为 1：

$$ \min_i y_i(\mathbf{w}^T\mathbf{x}_i+b)=1 $$

这等价于约束所有样本满足：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1 $$

在这个约束下，最小几何间隔为：

$$ \gamma=\frac{1}{|\mathbf{w}|} $$

最大化间隔：

$$ \max_{\mathbf{w},b}\frac{1}{|\mathbf{w}|} $$

等价于最小化 $|\mathbf{w}|$：

$$ \min_{\mathbf{w},b}|\mathbf{w}| $$

为了便于求导和优化，通常写成最小化：

$$ \min_{\mathbf{w},b}\frac{1}{2}|\mathbf{w}|^2 $$

因此线性可分 SVM 的标准优化问题为：

$$ \min_{\mathbf{w},b}\frac{1}{2}|\mathbf{w}|^2 $$

约束为：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1,\quad i=1,2,\dots,m $$

细节问题：

最大化 $\frac{1}{|\mathbf{w}|}$ 等价于最小化 $|\mathbf{w}|$。
最小化 $|\mathbf{w}|$ 和最小化 $\frac{1}{2}|\mathbf{w}|^2$ 的最优解相同。
$\frac{1}{2}$ 是为了求导后抵消平方带来的 2。
约束中的 1 不是随便来的，而是通过缩放参数固定最小函数间隔得到的。

线性可分 SVM / 硬间隔 SVM

当训练数据可以被某个线性超平面完全分开时，使用线性可分 SVM，也称硬间隔 SVM（Hard Margin SVM）。

优化问题：

$$ \min_{\mathbf{w},b}\frac{1}{2}|\mathbf{w}|^2 $$

约束：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1,\quad i=1,2,\dots,m $$

分类决策函数：

$$ f(\mathbf{x})=\mathrm{sign}(\mathbf{w}^T\mathbf{x}+b) $$

支持向量满足：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)=1 $$

它们恰好落在两条间隔边界上：

$$ \mathbf{w}^T\mathbf{x}+b=1 $$

或：

$$ \mathbf{w}^T\mathbf{x}+b=-1 $$

两条间隔边界之间的距离为：

$$ \frac{2}{|\mathbf{w}|} $$

推导：

正类支持向量到分类超平面的距离为：

$$ \frac{|1|}{|\mathbf{w}|}=\frac{1}{|\mathbf{w}|} $$

负类支持向量到分类超平面的距离也为：

$$ \frac{|-1|}{|\mathbf{w}|}=\frac{1}{|\mathbf{w}|} $$

所以两侧总间隔宽度为：

$$ \frac{1}{|\mathbf{w}|}+\frac{1}{|\mathbf{w}|} =\frac{2}{|\mathbf{w}|} $$

细节问题：

硬间隔要求所有样本都满足约束，不允许违反。
对噪声和异常点非常敏感。
只适合线性可分且数据较干净的情况。

拉格朗日乘子法（不要求很深）

硬间隔 SVM 是带约束优化问题：

$$ \min_{\mathbf{w},b}\frac{1}{2}|\mathbf{w}|^2 $$

约束：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)-1\ge 0 $$

构造拉格朗日函数：

$$ L(\mathbf{w},b,\boldsymbol{\alpha}) =\frac{1}{2}|\mathbf{w}|^2 -\sum_{i=1}^{m}\alpha_i \left[y_i(\mathbf{w}^T\mathbf{x}_i+b)-1\right] $$

其中：

$$ \alpha_i\ge 0 $$

对 $\mathbf{w}$ 求偏导并令为 0：

$$ \frac{\partial L}{\partial \mathbf{w}} =\mathbf{w}-\sum_{i=1}^{m}\alpha_i y_i\mathbf{x}_i=0 $$

得到：

$$ \mathbf{w}=\sum_{i=1}^{m}\alpha_i y_i\mathbf{x}_i $$

对 $b$ 求偏导并令为 0：

$$ \frac{\partial L}{\partial b} =-\sum_{i=1}^{m}\alpha_i y_i=0 $$

得到：

$$ \sum_{i=1}^{m}\alpha_i y_i=0 $$

KKT 互补松弛条件：

$$ \alpha_i\left[y_i(\mathbf{w}^T\mathbf{x}_i+b)-1\right]=0 $$

含义：

若 $\alpha_i=0$，该样本通常不是支持向量，对最终超平面没有直接贡献。
若 $\alpha_i>0$，则必须有 $y_i(\mathbf{w}^T\mathbf{x}_i+b)=1$，该样本是支持向量。

细节问题：

SVM 的对偶问题中样本以内积 $\mathbf{x}_i^T\mathbf{x}_j$ 的形式出现。
这为后面的核技巧提供了入口。
本课程对拉格朗日乘子法不要求很深，重点理解 $\alpha_i>0$ 的样本才是支持向量。

最优 $b$ 与支持向量

由：

$$ \mathbf{w}^=\sum_{i=1}^{m}\alpha_i^ y_i\mathbf{x}_i $$

对任意支持向量 $\mathbf{x}_s$，有：

$$ y_s((\mathbf{w}^)^T\mathbf{x}_s+b^)=1 $$

由于 $y_s\in{+1,-1}$，所以 $y_s^{-1}=y_s$。

两边乘以 $y_s$：

$$ (\mathbf{w}^)^T\mathbf{x}_s+b^=y_s $$

因此：

$$ b^=y_s-(\mathbf{w}^)^T\mathbf{x}_s $$

代入 $\mathbf{w}^*$：

$$ b^* =y_s-\sum_{i=1}^{m}\alpha_i^*y_i\mathbf{x}_i^T\mathbf{x}_s $$

实际中常对所有支持向量求平均：

$$ b^*=\frac{1}{|S|} \sum_{s\in S} \left[ y_s-\sum_{i=1}^{m}\alpha_i^*y_i\mathbf{x}_i^T\mathbf{x}_s \right] $$

细节问题：

只有 $\alpha_s>0$ 的样本才适合用来计算 $b$。
取平均可以减小数值误差。

软间隔 SVM

现实数据往往不是完全线性可分的，或者存在噪声和异常点。

硬间隔约束：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1 $$

可能无法满足，或者会被异常点严重影响。

软间隔 SVM 允许少量样本违反间隔约束，引入松弛变量 $\xi_i$：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1-\xi_i $$

并要求：

$$ \xi_i\ge 0 $$

软间隔优化目标：

$$ \min_{\mathbf{w},b,\boldsymbol{\xi}} \frac{1}{2}|\mathbf{w}|^2+C\sum_{i=1}^{m}\xi_i $$

约束：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1-\xi_i,\quad \xi_i\ge 0 $$

其中 $C>0$ 是正则化参数。

含义：

$\frac{1}{2}|\mathbf{w}|^2$：希望间隔尽可能大。
$\sum_i\xi_i$：惩罚违反间隔的样本。
$C$：控制“间隔大小”和“训练错误惩罚”之间的权衡。

松弛变量的含义

对单个样本：

$$ y_i f(\mathbf{x}_i)=y_i(\mathbf{w}^T\mathbf{x}_i+b) $$

不同 $\xi_i$ 的含义：

情况	含义
$\xi_i=0$	样本在间隔外侧或刚好在间隔边界上，满足硬间隔要求
$0<\xi_i<1$	样本分类正确，但落在间隔内部
$\xi_i=1$	样本落在分类超平面上
$\xi_i>1$	样本被错分

从约束看：

$$ y_i f(\mathbf{x}_i)\ge 1-\xi_i $$

如果 $\xi_i>1$，则右侧小于 0，说明允许 $y_i f(\mathbf{x}_i)<0$，即允许错分。

细节问题：

松弛变量不是让模型随便犯错，因为目标函数会惩罚 $\sum_i\xi_i$。
$C$ 越大，对错误惩罚越重，模型越倾向于少犯训练错误，但可能过拟合。
$C$ 越小，对错误容忍度越高，间隔可能更大，但可能欠拟合。

软间隔与合页损失

软间隔 SVM 也可理解为最小化正则化的合页损失。

对单个样本，合页损失为：

$$ \ell_i=\max(0,1-y_i f(\mathbf{x}_i)) $$

当：

$$ y_i f(\mathbf{x}_i)\ge 1 $$

损失为 0。

当：

$$ y_i f(\mathbf{x}_i)<1 $$

损失为：

$$ 1-y_i f(\mathbf{x}_i) $$

因此软间隔目标可以写成：

$$ \min_{\mathbf{w},b} \frac{1}{2}|\mathbf{w}|^2 +C\sum_{i=1}^{m}\max(0,1-y_i(\mathbf{w}^T\mathbf{x}_i+b)) $$

细节问题：

合页损失不仅惩罚错分样本，也惩罚虽然分对但距离边界太近的样本。
这体现了 SVM 的大间隔思想。

核函数思想

如果数据在原始空间中线性不可分，可以把样本映射到更高维特征空间：

$$ \phi:\mathcal{X}\to\mathcal{H} $$

在特征空间中使用线性 SVM：

$$ f(\mathbf{x})=\mathbf{w}^T\phi(\mathbf{x})+b $$

核心思想：

原始空间非线性可分，映射到高维特征空间后可能线性可分。

例如二维数据可能无法用直线分开，但映射到三维或更高维后可以用平面分开。

核技巧如何解决非线性分类

SVM 的对偶形式和预测函数只依赖样本之间的内积。

线性情况下：

$$ \mathbf{x}_i^T\mathbf{x}_j $$

如果映射到高维空间，本来需要计算：

$$ \phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j) $$

核函数直接定义为：

$$ K(\mathbf{x}_i,\mathbf{x}_j) =\phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j) $$

这样不需要显式计算 $\phi(\mathbf{x})$，只需要计算核函数 $K$。

核 SVM 的分类函数为：

$$ f(\mathbf{x}) =\mathrm{sign}\left( \sum_{i=1}^{m}\alpha_i y_i K(\mathbf{x}_i,\mathbf{x})+b \right) $$

因为只有支持向量的 $\alpha_i>0$，实际预测时可写为：

$$ f(\mathbf{x}) =\mathrm{sign}\left( \sum_{i\in S}\alpha_i y_i K(\mathbf{x}_i,\mathbf{x})+b \right) $$

核技巧解决非线性分类的逻辑：

原空间线性不可分
-> 通过 phi 映射到高维特征空间
-> 在高维空间用线性超平面分类
-> 通过核函数计算高维内积
-> 不显式构造高维特征

细节问题：

核函数表示的是高维特征空间中的内积。
不是任意相似度函数都能作为核函数。
合法核函数需要对应某个特征映射，常用判断条件是核矩阵半正定。
核技巧的关键是“只替换内积”，不是重新发明一个分类器。

Mercer 条件（了解）

函数 $K(\mathbf{x},\mathbf{z})$ 若能作为核函数，需要存在特征映射 $\phi$，使得：

$$ K(\mathbf{x},\mathbf{z})=\phi(\mathbf{x})^T\phi(\mathbf{z}) $$

等价理解：

对任意样本集合，核矩阵 $K$ 总是半正定。

核矩阵定义为：

$$ K_{ij}=K(\mathbf{x}_i,\mathbf{x}_j) $$

半正定表示对任意向量 $\mathbf{c}$：

$$ \mathbf{c}^T K \mathbf{c}\ge 0 $$

本课程只需了解：合法核函数必须满足一定条件，不能随便定义。

常见核函数（了解）

核函数	公式	特点
线性核	$K(\mathbf{x},\mathbf{z})=\mathbf{x}^T\mathbf{z}$	不做非线性映射，适合线性可分或近似线性问题
多项式核	$K(\mathbf{x},\mathbf{z})=(\gamma\mathbf{x}^T\mathbf{z}+c)^d$	可表达多项式特征组合
RBF / 高斯核	$K(\mathbf{x},\mathbf{z})=\exp(-\gamma\|\mathbf{x}-\mathbf{z}\|^2)$	常用，能产生非线性边界

超参数：

$C$：软间隔惩罚强度。
$\gamma$：RBF 核或多项式核中的尺度参数。
$d$：多项式核次数。
$c$：多项式核常数项。

这些参数通常不能由 SVM 自动学习，需要用验证集或交叉验证选择。

SMO 算法（了解）

SMO 全称是 Sequential Minimal Optimization，序列最小最优化算法。

作用：

高效求解 SVM 对偶问题。

基本思想：

SVM 对偶问题是凸二次规划问题。
SMO 每次选择两个变量 $\alpha_i,\alpha_j$。
固定其他变量，只优化这两个变量。
该二变量子问题可以解析求解。
不断选择最违反 KKT 条件的变量对并更新，直到基本满足 KKT 条件。

了解即可：

SMO 是工程上常用的 SVM 求解方法。
不要求手推完整算法。
重点知道它利用 KKT 条件和二变量子问题来高效优化。

多分类 SVM

SVM 原始形式主要用于二分类，多分类通常转化为多个二分类问题。

1. One-vs-One

若有 $C$ 个类别，训练：

$$ \frac{C(C-1)}{2} $$

个二分类器。

每个分类器只区分两个类别。

预测时：

每个分类器投票。
最终选择得票最多的类别。

特点：

分类器数量多。
每个分类器训练数据较少。
常用于多分类 SVM。

2. One-vs-Rest

若有 $C$ 个类别，训练 $C$ 个二分类器。

第 $i$ 个分类器：

类 $i$ 作为正类。
其他所有类别合并为负类。

预测时：

$$ \hat{y}=\arg\max_i f_i(\mathbf{x}) $$

即选择实值输出信心最高的类别。

特点：

分类器数量少。
每个分类器要使用全部训练数据。
类别不平衡问题可能更明显。

必须掌握的推导主线

1. 从距离到最大间隔

点到超平面距离：

$$ d_i=\frac{| \mathbf{w}^T\mathbf{x}_i+b |}{|\mathbf{w}|} $$

带标签后：

$$ \gamma_i=\frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|} $$

SVM 最大化最小间隔：

$$ \max_{\mathbf{w},b}\min_i \gamma_i $$

代入几何间隔：

$$ \max_{\mathbf{w},b} \min_i \frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|} $$

通过缩放固定：

$$ \min_i y_i(\mathbf{w}^T\mathbf{x}_i+b)=1 $$

于是：

$$ \max_{\mathbf{w},b}\frac{1}{|\mathbf{w}|} $$

等价于：

$$ \min_{\mathbf{w},b}\frac{1}{2}|\mathbf{w}|^2 $$

约束：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1 $$

这就是硬间隔 SVM。

2. 从硬间隔到软间隔

硬间隔约束：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1 $$

若数据有噪声或不可线性分，则放宽为：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1-\xi_i $$

其中：

$$ \xi_i\ge 0 $$

为了防止无限放宽，加入惩罚：

$$ C\sum_{i=1}^{m}\xi_i $$

得到软间隔目标：

$$ \min_{\mathbf{w},b,\boldsymbol{\xi}} \frac{1}{2}|\mathbf{w}|^2+C\sum_{i=1}^{m}\xi_i $$

约束：

$$ y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1-\xi_i,\quad \xi_i\ge 0 $$

3. 从线性到核 SVM

线性 SVM 的对偶和预测只依赖内积：

$$ \mathbf{x}_i^T\mathbf{x}_j $$

非线性映射后应使用：

$$ \phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j) $$

用核函数替代：

$$ K(\mathbf{x}_i,\mathbf{x}_j) =\phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j) $$

预测函数变为：

$$ f(\mathbf{x}) =\mathrm{sign}\left( \sum_{i\in S}\alpha_i y_iK(\mathbf{x}_i,\mathbf{x})+b \right) $$

这就是核技巧。

易错点

感知机和 SVM 都是线性分类器起步，但感知机只追求分对，SVM 追求最大间隔。
$\mathbf{w}^T\mathbf{x}+b$ 不是距离，距离要除以 $|\mathbf{w}|$。
函数间隔会随参数缩放变化，几何间隔不会。
硬间隔不允许任何样本违反间隔约束。
软间隔允许违反，但通过松弛变量和 $C$ 惩罚。
$C$ 越大，不代表一定越好；它会降低训练错误容忍度，可能过拟合。
核函数不是直接把样本“画到高维”，而是隐式计算高维内积。
核 SVM 的非线性边界来自高维空间中的线性超平面映射回原空间。
SMO 了解思想即可，不需要完整手推。

考试中可以这样写

支持向量机是在感知机基础上发展出的最大间隔分类模型。感知机只要求找到一个能正确分类训练样本的超平面，而 SVM 在所有可分超平面中选择使最小几何间隔最大的超平面，因此具有更强的鲁棒性和泛化能力。

点到超平面 $\mathbf{w}^T\mathbf{x}+b=0$ 的距离为 $\frac{|\mathbf{w}^T\mathbf{x}+b|}{|\mathbf{w}|}$。对带标签样本，几何间隔为 $\frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{|\mathbf{w}|}$。通过固定最小函数间隔为 1，最大化几何间隔等价于最小化 $\frac{1}{2}|\mathbf{w}|^2$，并满足约束 $y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1$，这就是硬间隔 SVM。

软间隔 SVM 引入松弛变量 $\xi_i$，将约束放宽为 $y_i(\mathbf{w}^T\mathbf{x}_i+b)\ge 1-\xi_i$，并在目标函数中加入惩罚项 $C\sum_i\xi_i$，从而在最大间隔和允许少量错误之间折中。

核技巧通过核函数 $K(\mathbf{x},\mathbf{z})=\phi(\mathbf{x})^T\phi(\mathbf{z})$ 隐式计算高维特征空间中的内积，使 SVM 能在高维空间中构造线性超平面，从而解决原空间中的非线性分类问题。

速记

感知机只求分对 → SVM 求最大最小间隔 → 距离除以 $|\mathbf{w}|$ → 固定函数间隔为 1 → 最小化 $\frac{1}{2}|\mathbf{w}|^2$ → 软间隔加 $\xi$ 和 $C$ → 核函数替换内积。

6. 贝叶斯分类器

范围：贝叶斯公式、贝叶斯分类思想、朴素贝叶斯、条件独立性、分类计算公式、拉普拉斯修正；半朴素贝叶斯和贝叶斯网络了解即可。

一、必须掌握

1. 贝叶斯公式

贝叶斯公式用于在看到新证据后更新原来的判断：

$$ P(A|B)=\frac{P(B|A)P(A)}{P(B)} $$

含义：

$P(A)$：先验概率。看到证据前，事件 $A$ 本来发生的概率。
$P(B|A)$：似然。在 $A$ 成立时，看到证据 $B$ 的概率。
$P(B)$：证据因子。证据 $B$ 本身出现的概率。
$P(A|B)$：后验概率。看到证据 $B$ 后，事件 $A$ 成立的概率。

直观理解：

$$ 后验概率 = \frac{似然 \times 先验概率}{证据概率} $$

考试要点：贝叶斯公式不是“证据出现就直接确定结论”，而是根据证据对原判断进行概率更新。

2. 贝叶斯分类的基本思想

贝叶斯分类器的目标：对样本 $\mathbf{x}$，计算它属于每个类别 $c$ 的后验概率 $P(c|\mathbf{x})$，然后选择后验概率最大的类别。

根据贝叶斯公式：

$$ P(c|\mathbf{x})=\frac{P(c)P(\mathbf{x}|c)}{P(\mathbf{x})} $$

其中：

$P(c)$：类别 $c$ 的先验概率，通常用训练集中该类样本的比例估计。
$P(\mathbf{x}|c)$：类条件概率，也叫似然，表示类别为 $c$ 时出现样本 $\mathbf{x}$ 的概率。
$P(\mathbf{x})$：证据因子，对所有类别相同，分类比较时可以忽略。

因此分类时只需要比较：

$$ h(\mathbf{x})=\arg\max_{c\in \mathcal{Y}} P(c)P(\mathbf{x}|c) $$

贝叶斯分类器属于生成式模型：先对联合概率分布 $P(\mathbf{x},c)$ 或 $P(c)P(\mathbf{x}|c)$ 建模，再得到后验概率。

3. 朴素贝叶斯分类器

直接估计 $P(\mathbf{x}|c)$ 很困难，因为样本 $\mathbf{x}$ 可能包含多个属性：

$$ \mathbf{x}=(x_1,x_2,\dots,x_d) $$

所有属性的联合概率 $P(x_1,x_2,\dots,x_d|c)$ 很难从有限训练样本中准确估计，会出现组合爆炸和样本稀疏问题。

朴素贝叶斯的做法：引入条件独立性假设，把联合概率拆成多个单属性概率的乘积。

4. 条件独立性假设

朴素贝叶斯假设：在给定类别 $c$ 的条件下，各个属性相互独立。

即：

$$ P(\mathbf{x}|c)=P(x_1,x_2,\dots,x_d|c)=\prod_{i=1}^{d}P(x_i|c) $$

所以：

$$ P(c|\mathbf{x}) \propto P(c)\prod_{i=1}^{d}P(x_i|c) $$

注意：这个假设在现实中往往不完全成立，所以叫“朴素”。但它大大降低了估计难度，实际效果经常不错。

5. 朴素贝叶斯分类计算公式

最终分类公式：

$$ h_{nb}(\mathbf{x})=\arg\max_{c\in \mathcal{Y}} P(c)\prod_{i=1}^{d}P(x_i|c) $$

离散属性估计：

$$ P(c)=\frac{|D_c|}{|D|} $$

$$ P(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|} $$

其中：

$D$：训练集。
$D_c$：训练集中类别为 $c$ 的样本集合。
$D_{c,x_i}$：类别为 $c$ 且第 $i$ 个属性取值为 $x_i$ 的样本集合。

连续属性估计：通常假设属性服从某种分布，例如正态分布：

$$ P(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}} \exp\left(-\frac{(x_i-\mu_{c,i})^2}{2\sigma_{c,i}^2}\right) $$

其中 $\mu_{c,i}$ 和 $\sigma_{c,i}^2$ 可由类别 $c$ 中第 $i$ 个属性的样本均值和方差估计。

6. 拉普拉斯修正

问题：如果某个属性值在训练集中没有与某个类别同时出现，则：

$$ P(x_i|c)=0 $$

朴素贝叶斯要做概率连乘，只要有一个概率为 0，整个类别的得分就会变成 0，导致其他属性提供的信息被完全“抹去”。

例子：如果训练集中没有出现过“敲声=清脆”的好瓜，那么测试样本只要有“敲声=清脆”，未修正的模型就会令：

$$ P(\text{敲声=清脆}|\text{好瓜})=0 $$

从而把“好瓜”类别的整体概率乘成 0。

拉普拉斯修正的做法：给每种情况都加 1，避免零概率。

类别先验修正：

$$ \hat{P}(c)=\frac{|D_c|+1}{|D|+N} $$

属性条件概率修正：

$$ \hat{P}(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i} $$

其中：

$N$：训练集中可能的类别数。
$N_i$：第 $i$ 个属性可能的取值数。

本质：拉普拉斯修正相当于假设每个类别、每个属性取值都至少出现过一次。它可以避免零概率，但也额外引入了“均匀分布”的偏置。

考试重点：老师明确说拉普拉斯修正需要掌握，因为它用于避免某些类别或属性取值没出现时导致概率为 0 的问题。

二、了解即可

1. 半朴素贝叶斯

朴素贝叶斯假设属性之间条件独立，但现实中属性之间往往有关联。

半朴素贝叶斯的基本思想：适当考虑部分属性之间的依赖关系，而不是完全假设独立。

常见方法：

ODE：独依赖估计，假设每个属性除了类别之外，最多依赖一个其他属性。
SPODE：所有属性依赖同一个“超父”属性，通过模型选择确定超父属性。
TAN：用属性之间的条件互信息作为边权，构建最大带权生成树，只保留较强的属性依赖关系。
AODE：把多个 SPODE 集成起来，平均多个独依赖模型的结果。

理解重点：半朴素贝叶斯是在“完全独立”和“完全联合建模”之间折中。

2. 贝叶斯网络

贝叶斯网络是概率图模型的一种，用有向无环图 DAG 表示变量之间的依赖关系。

贝叶斯网络由两部分组成：

结构 $G$：有向无环图，表示变量之间的依赖关系。
参数 $\theta$：条件概率表 CPT，表示每个节点在父节点给定时的条件概率。

联合概率可以分解为：

$$ P(x_1,x_2,\dots,x_d)=\prod_{i=1}^{d}P(x_i|\pi_i) $$

其中 $\pi_i$ 是 $x_i$ 的父节点集合。

理解重点：贝叶斯网络不是简单假设所有属性独立，而是用图结构表达哪些变量之间存在依赖。

三、PDF 中出现的问题/例题及解答

问题 1：99% 准确的癌症检测，阳性就几乎确定患癌吗？

PDF 条件：

患病率：1%。
真正患癌的人，99% 检测阳性。
没患癌的人，99% 检测阴性，即 1% 会假阳性。
张三检测结果为阳性。

用 10000 人来算：

真正患癌：100 人，其中阳性 99 人。
没有患癌：9900 人，其中假阳性 99 人。
所有阳性：99 + 99 = 198 人。

所以：

$$ P(\text{患癌}|\text{阳性})=\frac{99}{198}=50% $$

如果患病率只有 0.1%，则 10000 人中约 10 人患病：

真阳性约 $10 \times 0.99 = 9.9$ 人。
假阳性约 $9990 \times 0.01 = 99.9$ 人。

所以：

$$ P(\text{患癌}|\text{阳性}) =\frac{9.9}{9.9+99.9} \approx 9% $$

结论：检测准确率高，不代表阳性后的患病概率一定高。还要看先验概率，也就是患病率。

问题 2：侦探故事中，门禁异常后 A 是嫌疑人的概率是多少？

PDF 条件：

先验：$P(A)=50%$，$P(\neg A)=50%$。
如果 A 是小偷，门禁异常概率为 80%。
如果 A 不是小偷，门禁异常概率为 20%。

计算：

$$ P(A|\text{异常}) =\frac{P(\text{异常}|A)P(A)} {P(\text{异常}|A)P(A)+P(\text{异常}|\neg A)P(\neg A)} $$

$$ =\frac{0.8\times0.5}{0.8\times0.5+0.2\times0.5} =\frac{0.4}{0.5} =0.8 $$

答案：A 是嫌疑人的后验概率为 80%。

问题 3：西瓜样本“青绿、稍蜷、浊响、清晰”是好瓜还是坏瓜？

PDF 给定训练集共有 17 个样本：

好瓜 8 个。
坏瓜 9 个。

目标样本：

$$ \mathbf{x}=(青绿, 稍蜷, 浊响, 清晰) $$

未使用拉普拉斯修正时：

好瓜得分：

$$ P(好瓜)\cdot P(青绿|好瓜)\cdot P(稍蜷|好瓜)\cdot P(浊响|好瓜)\cdot P(清晰|好瓜) $$

$$ =\frac{8}{17}\times\frac{3}{8}\times\frac{3}{8}\times\frac{6}{8}\times\frac{7}{8} $$

坏瓜得分：

$$ P(坏瓜)\cdot P(青绿|坏瓜)\cdot P(稍蜷|坏瓜)\cdot P(浊响|坏瓜)\cdot P(清晰|坏瓜) $$

$$ =\frac{9}{17}\times\frac{3}{9}\times\frac{4}{9}\times\frac{4}{9}\times\frac{2}{9} $$

比较可知好瓜得分更大，因此分类结果为：好瓜。

问题 4：为什么需要拉普拉斯修正？

问题：如果训练集中没有某个“属性值-类别”的组合，例如没有“敲声=清脆”的好瓜，那么：

$$ P(\text{清脆}|\text{好瓜})=0 $$

在朴素贝叶斯中：

$$ P(c)\prod_i P(x_i|c) $$

只要有一个因子为 0，整个类别得分就是 0。这样会导致其他属性即使很支持“好瓜”，也完全不起作用。

解决：使用拉普拉斯修正。

若“敲声”这个属性有 3 种可能取值，且好瓜样本有 8 个，那么即使训练集中没有“清脆”的好瓜：

$$ \hat{P}(\text{清脆}|\text{好瓜}) =\frac{0+1}{8+3} =\frac{1}{11} $$

这样概率不再为 0，分类器仍然可以综合其他属性进行判断。

问题 5：水果糖案例中，水果糖来自 1 号碗的概率是多少？

PDF 图中条件：

随机选择一个碗，所以 $P(#1)=P(#2)=1/2$。
1 号碗：10 颗水果糖，30 颗非水果糖，所以 $P(水果糖|#1)=10/(10+30)=1/4$。
2 号碗：20 颗水果糖，20 颗非水果糖，所以 $P(水果糖|#2)=20/(20+20)=1/2$。
已知摸到的是水果糖，求来自 1 号碗的概率。

计算：

$$ P(#1|水果糖) =\frac{P(水果糖|#1)P(#1)} {P(水果糖|#1)P(#1)+P(水果糖|#2)P(#2)} $$

$$ =\frac{\frac14\times\frac12} {\frac14\times\frac12+\frac12\times\frac12} =\frac{\frac18}{\frac18+\frac14} =\frac{\frac18}{\frac38} =\frac13 $$

答案：这颗水果糖来自 1 号碗的概率是 $\frac{1}{3}$。

四、速记版

贝叶斯公式：$P(A|B)=P(B|A)P(A)/P(B)$。
贝叶斯分类：比较每个类别的后验概率，选最大的类别。
朴素贝叶斯：假设给定类别后，各属性条件独立。
分类公式：$h(\mathbf{x})=\arg\max_c P(c)\prod_iP(x_i|c)$。
离散属性：$P(x_i|c)=|D_{c,x_i}|/|D_c|$。
拉普拉斯修正：把分子加 1，分母加可能取值数，避免概率为 0。
半朴素贝叶斯：适当考虑属性依赖。
贝叶斯网络：用有向无环图和条件概率表表示变量依赖。

7. 维度约简 PCA

来源：纬度约减.pdf
范围：维度约简动机、PCA、LDA、Kernel PCA。重点掌握 PCA。

一、必须掌握：PCA

1. 维度约简的动机

高维数据会带来“维度灾难”：

数据样本在高维空间中变得稀疏。
距离计算变得困难，很多依赖距离的算法效果下降。
特征维度高会增加计算和存储开销。

降维的核心思想：通过某种数学变换，把原始高维属性空间变成低维子空间。

为什么可以降维：虽然样本看起来处在高维空间中，但与学习任务真正相关的信息可能只分布在某个低维嵌入上。也就是说，高维数据可能本质上由少数几个主要方向决定。

2. PCA 的核心思想

PCA，全称 Principal Component Analysis，主成分分析。

PCA 是一种无监督线性降维方法。它通过线性变换，把原始数据变换到一组新的坐标轴上，使得前几个坐标轴尽可能保留数据中的主要信息。

一句话概括：

PCA 找到数据方差最大的方向，把这些方向作为新的坐标轴，然后保留最重要的前几个方向。

主成分的含义：

第一个主成分：数据方差最大的方向。
第二个主成分：在与第一个主成分正交的条件下，方差第二大的方向。
依次类推。

3. 为什么可以用投影实现降维

线性降维把原始样本 $\mathbf{x}\in \mathbb{R}^d$ 投影到低维空间：

$$ \mathbf{z}=W^T\mathbf{x} $$

其中：

$W$ 是投影矩阵。
$W=(\mathbf{w}_1,\mathbf{w}2,\dots,\mathbf{w}{d'})$。
$d'<d$，所以 $\mathbf{z}\in \mathbb{R}^{d'}$。

投影的意义：用少数几个方向上的坐标来表示原始样本。
如果这些方向保留了数据中最主要的变化，那么即使维度降低，重要信息仍然能被保留下来。

例如人脸图像原本可能是 $100\times100=10000$ 维像素向量，但人脸并不是随机像素排列，而是有共同结构。PCA 可以提取“特征脸”，用少量权重系数近似表示一张人脸。

4. 最大可分性思想

最大可分性要求：样本投影到低维空间后，投影点尽可能分散。

也就是让投影后的方差尽可能大。

对一维投影方向 $\mathbf{w}$，中心化后样本投影为：

$$ \mathbf{w}^T\mathbf{x}_i $$

投影后的方差与下面的量成正比：

$$ \sum_i \mathbf{w}^T\mathbf{x}_i\mathbf{x}_i^T\mathbf{w}

\mathbf{w}^TXX^T\mathbf{w} $$

为了防止 $\mathbf{w}$ 无限放大，需要约束：

$$ \mathbf{w}^T\mathbf{w}=1 $$

所以一维 PCA 可以写成：

$$ \max_{\mathbf{w}} \mathbf{w}^TXX^T\mathbf{w} \quad s.t.\quad \mathbf{w}^T\mathbf{w}=1 $$

多维投影时：

$$ \max_W tr(W^TXX^TW) \quad s.t.\quad W^TW=I $$

解释：PCA 选择使投影后样本方差最大的方向。方差越大，说明样本在该方向上越能被区分，也越能保留信息。

5. 最近重构性思想

最近重构性要求：样本投影到低维空间后，再从低维表示重构回原空间时，重构误差尽可能小。

投影：

$$ \mathbf{z}_i=W^T\mathbf{x}_i $$

重构：

$$ \hat{\mathbf{x}}_i=W\mathbf{z}_i $$

PCA 希望最小化：

$$ \sum_i |\mathbf{x}_i-\hat{\mathbf{x}}_i|^2 $$

推导后可得到与最大可分性等价的优化目标：

$$ \min_W -tr(W^TXX^TW) \quad s.t.\quad W^TW=I $$

结论：最大化投影方差和最小化重构误差是 PCA 的两种等价理解。

6. 数据中心化

PCA 之前必须对数据中心化。

对每个样本：

$$ \mathbf{x}_i \leftarrow \mathbf{x}i-\frac{1}{m}\sum{i=1}^{m}\mathbf{x}_i $$

中心化后：

$$ \sum_{i=1}^{m}\mathbf{x}_i=0 $$

为什么要中心化：

PCA 关心的是数据围绕均值的变化方向。
不中心化时，均值偏移会影响协方差矩阵和主成分方向。
中心化后，协方差矩阵能正确描述各特征之间的共同变化。

注意：如果做标准化或归一化，不能统计测试集信息。应保存训练集上的均值、方差、最大值、最小值等参数，再用这些参数处理测试集。

7. 协方差矩阵

协方差衡量两个变量共同变化的程度。

对随机变量 $X,Y$：

$$ Cov(X,Y)=E[(X-\mu)(Y-\nu)] $$

如果数据已经中心化，则：

$$ Cov(X,Y)=E[XY] $$

协方差矩阵：

$$ \Sigma_{ij}=Cov(X_i,X_j) $$

性质：

协方差矩阵是对称矩阵。
对角线元素是每个特征自身的方差。
非对角线元素表示不同特征之间的协方差。

PCA 中常用 $XX^T$ 或 $\frac{1}{m}XX^T$ 表示协方差矩阵。常数 $\frac{1}{m}$ 不影响特征向量方向，所以推导里常直接写 $XX^T$。

8. 求特征值和特征向量

PCA 的关键求解问题：

$$ XX^T\mathbf{w}_i=\lambda_i\mathbf{w}_i $$

也就是对协方差矩阵 $XX^T$ 做特征值分解。

含义：

$\lambda_i$：第 $i$ 个方向上的方差大小。
$\mathbf{w}_i$：对应的投影方向。

特征值越大，说明数据在对应特征向量方向上的方差越大，该方向保留的信息越多。

9. 选择最大特征值对应的特征向量作为投影方向

把特征值从大到小排序：

$$ \lambda_1\ge \lambda_2\ge \cdots \ge \lambda_d $$

选择前 $d'$ 个最大特征值对应的特征向量：

$$ W^*=(\mathbf{w}_1,\mathbf{w}2,\dots,\mathbf{w}{d'}) $$

然后用：

$$ \mathbf{z}=W^{*T}\mathbf{x} $$

得到低维表示。

PCA 算法步骤：

输入样本集 $D={\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m}$ 和目标维度 $d'$。
对所有样本进行中心化。
计算协方差矩阵 $XX^T$。
对 $XX^T$ 做特征值分解。
取最大的 $d'$ 个特征值对应的特征向量。
输出投影矩阵 $W=(\mathbf{w}_1,\mathbf{w}2,\dots,\mathbf{w}{d'})$。

10. 子空间维度如何选择

常见方法：

用户直接指定 $d'$。
在低维空间中用简单学习器交叉验证，选择效果较好的 $d'$。
通过重构误差或保留能量比例选择。

保留能量比例：

$$ \frac{\lambda_1+\lambda_2+\cdots+\lambda_T} {\lambda_1+\lambda_2+\cdots+\lambda_d}>0.9 $$

通常选择第一个满足该不等式的 $T$，表示保留 90% 以上的信息量。

11. PCA 的优点和注意事项

优点：

降低维度，减少计算和存储开销。
提高样本密度，缓解维度灾难。
小特征值方向常与噪声有关，丢弃这些方向可以起到去噪作用。
新样本只需保存均值向量和投影矩阵，就能快速投影到低维空间。

注意事项：

PCA 对特征尺度敏感，因为协方差矩阵会受量纲影响。
不同特征量纲差异大时，应先做标准化或归一化。
PCA 是无监督方法，不使用类别标签，所以方差最大的方向不一定最适合分类。

二、了解即可

1. LDA 的基本思想

LDA，全称 Linear Discriminant Analysis，线性判别分析。

LDA 是有监督降维方法，会利用类别标签。

核心思想：

同类样本投影后尽可能接近。
异类样本投影后尽可能远离。

二分类 LDA 中：

类内散度矩阵：

$$ S_w=\Sigma_0+\Sigma_1

\sum_{\mathbf{x}\in X_0}(\mathbf{x}-\mu_0)(\mathbf{x}-\mu_0)^T + \sum_{\mathbf{x}\in X_1}(\mathbf{x}-\mu_1)(\mathbf{x}-\mu_1)^T $$

类间散度矩阵：

$$ S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T $$

LDA 目标是最大化广义瑞利商：

$$ J=\frac{\mathbf{w}^TS_b\mathbf{w}} {\mathbf{w}^TS_w\mathbf{w}} $$

直观理解：分子大表示类间距离大，分母小表示类内距离小。

二分类 LDA 的投影方向：

$$ \mathbf{w}=S_w^{-1}(\mu_0-\mu_1) $$

PCA 与 LDA 区别：

PCA 是无监督，LDA 是有监督。
PCA 目标是投影后方差最大，LDA 目标是类内小、类间大。
PCA 基于协方差矩阵，LDA 基于类内散度和类间散度。
PCA 的投影方向正交，LDA 不要求投影方向正交。
LDA 的降维维度通常受类别数限制，多分类最多可降到 $N-1$ 维。

2. Kernel PCA 的基本想法

普通 PCA 是线性降维，如果数据存在非线性结构，线性投影可能不够。

Kernel PCA 的想法：

假设存在非线性映射 $\phi$，把原始数据映射到高维特征空间。
在高维特征空间中做 PCA。
不显式计算 $\phi(\mathbf{x})$，而是用核函数计算内积。

高维空间中的协方差矩阵：

$$ C=\frac{1}{m}\sum_{i=1}^{m}\phi(\mathbf{x}_i)\phi(\mathbf{x}_i)^T $$

如果直接做 PCA，需要解：

$$ C\mathbf{w}=\lambda \mathbf{w} $$

但高维空间可能维度很高甚至无限维，无法显式计算 $C$。

Kernel PCA 使用核矩阵：

$$ G_{ij}=\langle \phi(\mathbf{x}_i),\phi(\mathbf{x}_j)\rangle =K(\mathbf{x}_i,\mathbf{x}_j) $$

于是问题转化为对核矩阵 $G$ 做特征值分解。

新样本 $\mathbf{x}$ 在第 $j$ 个主成分上的投影坐标：

$$ \langle \phi(\mathbf{x}),\mathbf{w}_j\rangle

\sum_{i=1}^{m}a_i^j K(\mathbf{x},\mathbf{x}_i) $$

注意：Kernel PCA 对新样本投影时需要对所有训练样本求和，因此计算开销较大。

三、PDF 中出现的问题/思考点及解答

问题 1：为什么高维数据可以降维？

答案：因为数据虽然表示在高维空间中，但真正与任务相关的变化可能集中在低维嵌入上。例如人脸图像像素维度很高，但人脸结构不是随机的，眼睛、鼻子、嘴巴等结构具有规律性，所以可以用少量主成分近似表达。

问题 2：PCA 为什么选择方差最大的方向？

答案：方差表示数据在某个方向上的分散程度。投影后方差越大，说明样本在该方向上越能被区分，保留的信息越多。因此 PCA 从最大可分性角度选择投影方差最大的方向。

问题 3：PCA 的“最大可分性”和“最近重构性”为什么等价？

答案：在正交投影和数据中心化条件下，样本总能量可以分解为“投影后保留的能量”和“重构损失”。最大化投影后的方差，等价于保留尽可能多的信息；保留的信息越多，被丢弃的信息越少，重构误差就越小。因此两种推导得到相同的优化目标：

$$ \max_W tr(W^TXX^TW) \quad s.t.\quad W^TW=I $$

或等价地：

$$ \min_W -tr(W^TXX^TW) \quad s.t.\quad W^TW=I $$

问题 4：PCA 为什么要先中心化？

答案：PCA 要找的是数据围绕均值变化最大的方向。若不中心化，数据整体均值偏移会影响协方差矩阵，使主成分方向受到原点位置影响。中心化后，协方差矩阵才能正确表示特征之间的共同变化。

问题 5：PCA 的投影矩阵怎么求？

答案：

中心化数据。
计算协方差矩阵 $XX^T$。
求解特征值问题：

$$ XX^T\mathbf{w}_i=\lambda_i\mathbf{w}_i $$

将特征值从大到小排序。
选择最大的 $d'$ 个特征值对应的特征向量组成：

$$ W=(\mathbf{w}_1,\mathbf{w}2,\dots,\mathbf{w}{d'}) $$

问题 6：为什么取最大特征值对应的特征向量？

答案：协方差矩阵的特征值表示数据在对应特征向量方向上的方差。特征值越大，该方向的数据变化越明显，保留的信息越多。因此 PCA 选择最大特征值对应的特征向量作为主成分方向。

问题 7：PCA 降到几维比较合适？

答案：常用保留能量比例判断。若希望保留 90% 的信息量，就选择最小的 $T$，使得：

$$ \frac{\lambda_1+\lambda_2+\cdots+\lambda_T} {\lambda_1+\lambda_2+\cdots+\lambda_d}>0.9 $$

也可以由用户指定，或通过交叉验证选择。

问题 8：为什么 PCA 前常要标准化？

答案：PCA 基于协方差矩阵，协方差会受到特征尺度影响。如果某个特征数值范围特别大，它可能主导主成分方向。标准化后，各特征处在相同尺度上，PCA 结果更合理。

注意：标准化参数只能从训练集统计，不能用测试集信息。

问题 9：PCA 为什么不一定适合分类？

答案：PCA 不使用类别标签，只寻找整体方差最大的方向。但分类任务需要的是最能区分类别的方向，方差最大的方向不一定能把类别分开。因此 PDF 中引出 LDA：有标签时，可以用 LDA 找更有利于分类的低维空间。

问题 10：Kernel PCA 为什么不显式计算高维协方差矩阵？

答案：Kernel PCA 假设通过 $\phi(\mathbf{x})$ 把数据映射到高维空间，但这个高维空间可能维度很高甚至无限维，显式计算：

$$ C=\frac{1}{m}\sum_i\phi(\mathbf{x}_i)\phi(\mathbf{x}_i)^T $$

通常不可行。所以 Kernel PCA 使用核函数：

$$ K(\mathbf{x}_i,\mathbf{x}_j)=\langle \phi(\mathbf{x}_i),\phi(\mathbf{x}_j)\rangle $$

通过核矩阵完成特征分解，避免显式计算 $\phi$ 和 $C$。

四、速记版

降维原因：高维数据稀疏，距离计算困难，但有效信息可能在低维嵌入上。
PCA 核心：找方差最大的方向，保留最大特征值对应的特征向量。
中心化：$\mathbf{x}_i\leftarrow \mathbf{x}_i-\bar{\mathbf{x}}$。
协方差矩阵：中心化后用 $XX^T$ 或 $\frac{1}{m}XX^T$。
求解：$XX^T\mathbf{w}=\lambda\mathbf{w}$。
投影矩阵：取最大的 $d'$ 个特征值对应的特征向量组成 $W$。
最大可分性：投影后方差最大。
最近重构性：重构误差最小。
LDA：有监督降维，类内小、类间大。
Kernel PCA：先用核函数隐式映射到高维空间，再做 PCA。

8. K 近邻 KNN

范围：k 近邻分类器、最近邻分类器、k 近邻回归、近邻计算优化、扩展内容。

一、必须掌握

1. KNN 的核心思想

KNN，全称 k-Nearest Neighbor，k 近邻。

核心思想：

一个样本的类别或预测值，可以由它在特征空间中最接近的 k 个训练样本决定。

KNN 属于基于实例的学习方法。它不显式学习一个参数模型，而是保存训练样本，预测时再进行距离计算。

2. k 近邻分类器

算法流程：

给定测试样本 $\hat{\mathbf{x}}$。
计算 $\hat{\mathbf{x}}$ 与训练集中所有样本 $\mathbf{x}_i$ 的距离 $d(\hat{\mathbf{x}},\mathbf{x}_i)$。
按距离从小到大排序。
选择距离最近的 k 个训练样本。
对这 k 个近邻的类别做投票。
将票数最多的类别作为测试样本的类别。

分类规则可以写成：

h(\hat{\mathbf{x}})=\arg\max_c

\sum_{\mathbf{x}_i\in N_k(\hat{\mathbf{x}})} I(y_i=c)

其中：

$N_k(\hat{\mathbf{x}})$ 表示 $\hat{\mathbf{x}}$ 的 k 个最近邻。
$I(y_i=c)$ 表示样本 $\mathbf{x}_i$ 的类别是否为 $c$。

3. k 的取值影响

k 的取值会直接影响分类结果。

k 一般取奇数，避免投票平局。
k 取不同值，分类结果可能不同。
k 较小时，模型更复杂，对噪声敏感，容易过拟合。
k 较大时，模型更平滑，对噪声不敏感，但容易欠拟合。

PDF 图中例子：

当 $k=3$ 时，测试点的 3 个最近邻中 Class 2 占多数，所以分为 Class 2。
当 $k=5$ 时，测试点的 5 个最近邻中 Class 1 占多数，所以分为 Class 1。

结论：KNN 的分类结果依赖 k 的选择，k 是重要超参数。

4. 距离度量

KNN 依赖“近邻”，所以距离度量非常关键。

常用欧式距离：

d(\mathbf{x}_i,\mathbf{x}_j)

\sqrt{\sum_{r=1}^{d}(x_{ir}-x_{jr})^2}

若只比较大小，也常用平方欧式距离，省去开根号：

d^2(\mathbf{x}_i,\mathbf{x}_j)

\sum_{r=1}^{d}(x_{ir}-x_{jr})^2

注意：不同特征尺度会影响距离计算，因此使用 KNN 前通常需要标准化或归一化。

5. 最近邻分类器 1-NN

1-NN 是 KNN 的特殊情况，即 $k=1$。

算法流程：

计算测试样本 $\hat{\mathbf{x}}$ 与所有训练样本的距离。
找到距离最近的训练样本：

i^*=\arg\min_i d(\hat{\mathbf{x}},\mathbf{x}_i)

将最近邻 $\mathbf{x}_{i^*}$ 的类别赋给 $\hat{\mathbf{x}}$。

1-NN 很简单，但对噪声非常敏感。只要最近的训练样本是噪声点，就可能分类错误。

PDF 中给出的重要结论：

最近邻分类器虽然简单，但它的泛化错误率不超过贝叶斯分类器错误率的两倍。

也就是说，1-NN 是一个非常简单但有理论保证的基线方法。

6. k 近邻回归

KNN 不只可以做分类，也可以做回归。

k 近邻回归流程：

计算测试样本与所有训练样本的距离。
选择 k 个最近邻。
将这 k 个近邻的标签值平均或加权平均，作为预测值。

简单平均：

$$ \hat{y}

\frac{1}{k}\sum_{\mathbf{x}_i\in N_k(\mathbf{x})}y_i $$

加权平均：

$$ \hat{y}

\frac{\sum_i K_\lambda(\mathbf{x},\mathbf{x}i)y_i} {\sum_i K\lambda(\mathbf{x},\mathbf{x}_i)} $$

其中 $K_\lambda$ 是核函数或权重函数。距离越近，权重通常越大。

7. 懒惰学习与急切学习

KNN 是典型的懒惰学习。

懒惰学习：

训练阶段几乎不建模，只保存训练样本。
预测阶段才计算距离并做决策。
训练快，预测慢。

急切学习：

训练阶段就构造模型。
预测时直接使用学到的模型。
例如 SVM、神经网络、CNN。

8. KNN 的优缺点

优点：

思想简单，容易理解。
不需要对数据分布作强假设。
对复杂决策边界有一定适应能力。
在数据充分且距离度量合适时，效果可以很好。

缺点：

预测阶段计算复杂度高。
需要存储全部训练样本，空间复杂度高。
对特征尺度敏感。
高维数据中距离度量容易失效。
k 和距离度量选择会明显影响结果。

9. 时间复杂度和空间复杂度

假设训练样本数为 $n$，特征维度为 $d$。

计算一个测试样本到一个训练样本的欧式距离，复杂度为：

$$ O(d) $$

对所有训练样本计算距离：

$$ O(nd) $$

如果维护 k 个最近距离，可以得到测试阶段复杂度：

$$ O(nd+n\log k) $$

训练阶段：

$$ O(0) $$

因为 KNN 训练时基本只保存样本。

空间复杂度：

$$ O(nd) $$

因为需要保存全部训练数据。

10. 重新补充：KNN 常考知识点

距离度量的选择

KNN 的核心是“近”，所以距离度量会直接决定近邻是谁。

常见距离：

欧式距离：适合连续数值特征，是最常见选择。
曼哈顿距离：各维绝对差求和，对异常值相对没那么敏感。
闵可夫斯基距离：欧式距离和曼哈顿距离的统一形式。
余弦相似度：更关注方向，常用于文本向量、高维稀疏向量。

曼哈顿距离：

$$ d(\mathbf{x},\mathbf{z})

\sum_{j=1}^{d}|x_j-z_j| $$

闵可夫斯基距离：

$$ d(\mathbf{x},\mathbf{z})

\left(\sum_{j=1}^{d}|x_j-z_j|^p\right)^{1/p} $$

当 $p=1$ 时是曼哈顿距离；当 $p=2$ 时是欧式距离。

特征标准化非常重要

KNN 使用距离做判断，如果不同特征量纲差异很大，数值范围大的特征会主导距离。

例如：

年龄范围可能是 0-100。
收入范围可能是 0-100000。

如果不标准化，收入几乎会完全决定距离，年龄的作用被压小。

常用标准化：

$$ x'=\frac{x-\mu}{\sigma} $$

归一化到 $[0,1]$：

$$ x'=\frac{x-x_{\min}}{x_{\max}-x_{\min}} $$

注意：均值、方差、最大值、最小值只能从训练集统计，再用于验证集和测试集，不能用测试集信息。

加权 KNN

普通 KNN 中，k 个近邻投票权重相同。但有时更近的邻居应当更重要。

加权投票思想：

$$ h(\mathbf{x})

\arg\max_c \sum_{\mathbf{x}_i\in N_k(\mathbf{x})} w_i I(y_i=c) $$

常见权重：

$$ w_i=\frac{1}{d(\mathbf{x},\mathbf{x}_i)+\epsilon} $$

其中 $\epsilon$ 用来避免距离为 0 时分母为 0。

优点：距离更近的样本影响更大，可以减少较远邻居的干扰。

k 的选择方法

k 是超参数，不能只凭感觉选。

常见选择方法：

用验证集选择。
用交叉验证选择。
二分类时常取奇数，减少平票。
样本少、噪声少时可取较小 k。
样本多、噪声较大时可取稍大 k。

经验理解：

$k=1$：决策边界最复杂，方差高，容易过拟合。
$k$ 很大：决策边界很平滑，偏差高，容易欠拟合。

KNN 的决策边界

KNN 的决策边界不是显式学出来的，而是由训练样本分布、距离度量和 k 共同决定。

k 小：边界曲折，容易贴合训练集。
k 大：边界平滑，更像整体趋势。

因此 KNN 也体现了偏差-方差权衡：

k 小：低偏差、高方差。
k 大：高偏差、低方差。

平票处理

当多个类别票数相同，可以：

选择距离总和更小的类别。
使用距离加权投票。
固定类别优先级。
增大或减小 k，避免平票。

考试中通常写：k 常取奇数，二分类中可减少平票。

类别不平衡问题

如果某个类别样本数量很多，KNN 投票时容易偏向多数类。

可用方法：

对距离投票加权。
对类别投票加权，降低多数类优势。
重采样，使类别分布更平衡。
使用更合适的评价指标，例如 F1、AUC，而不是只看准确率。

高维空间中的问题

KNN 在高维数据中常会变差，原因是维度灾难。

表现：

样本变稀疏。
距离差异变小，最近和最远不再明显。
距离计算成本升高。

解决思路：

先做特征选择。
先做 PCA 等降维。
使用合适距离度量，例如文本任务用余弦相似度。
使用近似最近邻方法。

KNN 与参数模型的区别

KNN 是非参数模型。这里的“非参数”不是没有参数，而是不假设固定形式的参数化函数。

它的模型复杂度会随着训练数据增加而变化，因为预测时依赖整个训练集。

与线性模型、SVM、神经网络相比：

KNN 几乎没有显式训练过程。
KNN 的主要计算发生在预测阶段。
KNN 对数据存储和检索要求高。

二、了解即可

1. 降低近邻计算的方法

KNN 的主要瓶颈在预测阶段，需要和所有训练样本计算距离。

PDF 中给出的降低近邻计算方法：

低维数据 2-5 维：维诺图 Voronoi diagrams。
中等维度 6-30 维：KD 树。
高维数据：降维方法，例如 PCA；近似最近邻 ANN；哈希 Hashing。

2. 维诺图

维诺图根据一组给定点，把平面划分成多个区域。每个区域中的点都更靠近对应的基点。

适用：

主要用于低维数据。
适合 1-NN。
2 维中可较高效查询。

理解即可：维诺图本质是预先把空间按最近点划分好，查询时判断测试点落在哪个区域。

3. KD 树

KD 树是一种用于 K 维空间点快速检索的数据结构。

核心思想：

用垂直于坐标轴的超平面不断切分空间。
每个结点对应一个空间区域。
查询时先沿树向下找到候选近邻，再回溯判断是否可能存在更近点。

KD 树构造流程：

选择 split 域：计算各维特征方差，选方差最大的维度作为切分维度。
选择 Node-data：按该维度排序，取中位数点作为当前结点。
用该点对应的坐标值切分空间。
对左右子空间递归构建。
直到区域中只剩少量点或一个点。

KD 树搜索流程：

从根结点开始，按切分维度进行二叉搜索。
到达叶结点后，得到一个当前最优近邻。
回溯检查其他分支是否可能存在更近点。
若查询点到切分平面的距离小于当前最优距离，则另一侧可能有更优点，需要继续搜索。
若不可能存在更优点，则剪枝。

理解重点：KD 树通过空间划分减少不必要的距离计算。

4. 近似最近邻 ANN

ANN，全称 Approximate Nearest Neighbors。

核心思想：不要求一定返回真正最近的 k 个点，只要求返回足够接近的近邻，用少量精度损失换取大幅速度提升。

PDF 中条件：

若第 k 个真实最近邻距离为 $d_k$，ANN 可接受返回距离满足：

$$ \hat{d}\le (1+\epsilon)d_k $$

意义：允许近似结果，从而将 KNN 搜索速度提高几个数量级。

5. 哈希 Hashing

哈希方法用哈希函数把高维数据映射为更短的编码。

核心思想：

设计多个哈希函数。
每个样本被表示为若干 bit。
$m\ll d$，计算和存储成本降低。
相似样本应尽量落到相同或相近哈希桶中。

了解即可：哈希是高维近邻搜索中的常见加速方法。

6. Probabilistic k-NN

PDF 中提到 KNN 的一个缺点：它通常不是建立在概率框架上。

因此：

难以直接得到类别后验概率。
难以概率化地推断 k 的个数或距离度量参数。

Probabilistic k-NN 的想法：通过定义似然函数，把 KNN 放入概率框架。

7. ModernNCA

PDF 扩展内容提到 ModernNCA。

核心思想：

从经典 NCA 出发，把“同类样本在投影空间更近”的思想现代化。
用 SGD 替代传统 L-BFGS。
用 Soft-NN Loss 替代原始留一法准确率。
用 Soft-NN 替代传统 Hard KNN。
用 MLP 等非线性表征增强能力。

理解即可：KNN 虽然经典，但近邻关系仍然是现代机器学习中的重要思想。

三、PDF 中出现的问题/例题及解答

问题 1：k 的取值会影响分类结果吗？

会。

PDF 图中同一个绿色测试点：

当 $k=3$ 时，最近的 3 个邻居中 Class 2 占多数，因此分类为 Class 2。
当 $k=5$ 时，最近的 5 个邻居中 Class 1 占多数，因此分类为 Class 1。

结论：k 是 KNN 的关键超参数。k 太小容易受噪声影响，k 太大可能把远处甚至其他类别的样本也纳入投票，导致欠拟合。

问题 2：为什么 k 一般取奇数？

答案：为了尽量避免二分类投票时出现平局。

例如二分类任务中：

$k=4$ 时可能出现 2 票对 2 票。
$k=5$ 时通常不会出现完全平局。

注意：多分类时即使 k 是奇数，也仍可能出现平局，因此实际实现中还可能需要按距离加权或设置平局规则。

问题 3：从 n 个距离中选择 k 个最小的，时间复杂度是多少？

常见做法：

如果直接排序所有距离，复杂度为 $O(n\log n)$。
如果维护一个大小为 k 的堆，遍历 n 个距离，复杂度为 $O(n\log k)$。
如果使用选择算法，可在平均 $O(n)$ 时间内找到第 k 小元素，再取出前 k 个。

PDF 中给出的测试阶段复杂度：

$$ O(nd+n\log k) $$

其中 $O(nd)$ 是计算所有距离，$O(n\log k)$ 是选择 k 个最近邻。

问题 4：KNN 的空间复杂度是多少？

答案：

$$ O(nd) $$

原因：KNN 训练阶段基本不学习模型参数，而是保存全部训练数据。若有 $n$ 个样本、每个样本 $d$ 维，就需要存储 $nd$ 个特征值。

问题 5：1-NN 的泛化错误率有什么理论结论？

PDF 给出结论：

最近邻分类器虽然简单，但它的泛化错误率不超过贝叶斯分类器错误率的两倍。

直观理解：当样本足够多时，测试样本的最近邻通常离它很近，因此最近邻标签能提供较可靠的信息。但 1-NN 仍然容易受噪声影响。

问题 6：KD 树示例中，第一步为什么选择 x 方向切分？

PDF 示例数据点：

$$ (2,3),(5,4),(4,7),(7,2),(9,6),(8,1) $$

KD 树构造时先计算 x、y 两个方向上的方差。PDF 中说明 x 方向方差更大，因此选择 x 方向作为 split 域。

将 x、y 方向分别编码为 0 和 1，则：

$$ split=0 $$

问题 7：KD 树示例中，为什么根结点选为 $(7,2)$？

答案：选定 x 方向后，把各点的 x 值取出：

$$ 2,5,4,7,9,8 $$

按大小排序：

$$ 2,4,5,7,8,9 $$

PDF 中取中位数 7，因此选定 Node-data 为：

$$ (7,2) $$

然后用直线：

$$ x=7 $$

把空间切分为左右两个子空间。

问题 8：KD 树搜索示例中，查询点 $(2.1,3.1)$ 的最近邻是谁？

PDF 中查询点为：

$$ (2.1,3.1) $$

二叉搜索先找到叶结点：

$$ (2,3) $$

距离为：

$$ \sqrt{(2.1-2)^2+(3.1-3)^2}

\sqrt{0.01+0.01} \approx 0.1414 $$

回溯检查其他可能分支后，没有发现更近点。

答案：最近邻为：

$$ (2,3) $$

问题 9：高维数据中如何降低 KNN 的近邻计算开销？

答案：

可以先用 PCA 等降维方法降低维度。
可以用 ANN 近似最近邻，用可接受的精度损失换速度。
可以用哈希方法把高维向量变成短编码。
中低维场景可考虑 KD 树或维诺图。

四、易错点

KNN 没有显式训练参数，但不等于没有超参数；k、距离度量、加权方式都很重要。
KNN 对特征尺度敏感，通常必须标准化。
k 越小不一定越好，小 k 容易过拟合。
k 越大也不一定越好，大 k 容易欠拟合。
1-NN 对噪声最敏感。
KNN 训练快不代表整体快，因为预测时要计算大量距离。
高维数据中“最近邻”可能不再可靠，需要降维或换距离度量。
KD 树适合中低维，高维时效果会明显下降。

五、考试中可以这样写

KNN 是一种基于实例的懒惰学习方法。它在训练阶段主要保存训练样本，在预测阶段计算测试样本与训练样本之间的距离，并根据最近的 k 个样本进行决策。分类任务中通常采用多数投票，回归任务中通常采用平均或加权平均。

KNN 的关键超参数是 k 和距离度量。k 较小时模型复杂、方差较大，容易受噪声影响；k 较大时模型更平滑、偏差较大，可能欠拟合。由于 KNN 依赖距离计算，因此特征标准化非常重要。KNN 的主要缺点是预测阶段计算和存储开销较大，在高维数据中还会受到维度灾难影响，可通过 KD 树、近似最近邻、哈希或降维等方法加速。

六、速记版

KNN 核心：看测试样本最近的 k 个训练样本。
分类：k 个近邻投票，票数最多的类别胜出。
回归：k 个近邻标签平均或加权平均。
k 小：复杂、低偏差、高方差、易过拟合。
k 大：平滑、高偏差、低方差、易欠拟合。
1-NN：取最近的一个样本类别，简单但对噪声敏感。
距离度量：欧式、曼哈顿、闵可夫斯基、余弦相似度。
标准化：KNN 必须重点注意特征尺度。
加权 KNN：距离越近权重越大。
KNN 是懒惰学习：训练快，预测慢。
测试复杂度：常见写法 $O(nd+n\log k)$。
空间复杂度：$O(nd)$。
加速方法：维诺图、KD 树、PCA 降维、ANN、哈希。

9. 集成学习 Ensemble Learning

一、整体思想

集成学习的核心思想：把多个学习器组合起来，用群体决策提高整体泛化性能。

它本身不是某一种具体分类器，而是一类“模型结合方法”：

先训练多个基学习器。
再用平均、投票、加权投票或元学习器进行组合。
目标是让整体模型比单个模型更稳定、更准确。

直观理解：

单个模型可能只学到数据规律的一部分。
多个模型如果都比随机猜测好，并且错误不完全相同，就可以通过组合抵消一部分错误。
集成学习强调两个条件：准确性和多样性。

为什么单个模型性能有限？

单个模型通常受以下因素限制：

假设空间有限：模型结构决定了它能表达什么，表达能力不足会导致欠拟合。
训练数据有限：样本少或噪声多时，模型容易学到偶然规律。
优化结果不稳定：不同初始化、不同训练集划分可能得到不同模型。
偏差和方差难以同时很低：简单模型偏差大，复杂模型方差大。
归纳偏置单一：一个模型只带有一种主要偏好，可能不适合所有局部规律。

因此，单个模型即使训练得很好，也可能在泛化时受限。

集成学习如何提升泛化性能？

集成学习主要通过两条路径提升泛化：

降低方差：多个模型平均或投票后，个别模型的不稳定预测被抵消，结果更稳定。Bagging 主要属于这一类。
降低偏差：后续模型不断修正前面模型的错误，使整体模型逐步逼近真实规律。Boosting 主要属于这一类。

从 bias-variance 角度看，以均方误差为例：

$$ Err(x)=Bias^2+Variance+Random\ Error $$

Bias：学习结果的期望与真实规律之间的差距。
Variance：学习结果自身的不稳定性。
Random Error：数据中的不可约噪声，集成学习也无法消除。

二、结合策略

常见结合策略：

任务	常用结合方式	含义
回归	简单平均	多个模型预测值直接取平均
回归	加权平均	表现更好的模型权重更大
分类	绝对多数投票	超过半数的类别胜出
分类	相对多数投票	得票最多的类别胜出
分类	加权投票	表现更好的分类器投票权重更大
通用	Stacking	用一个元学习器学习如何融合多个模型输出

多样性的来源：

数据层面：自助采样、序列采样。
属性层面：随机选择部分特征。
输出层面：改变输出标记或把分类问题转成回归问题。
参数层面：扰动模型参数或训练过程。

三、重点方法对比

方法	训练方式	主要目标	基学习器关系	结合方式	代表方法
Bagging	并行训练	主要降低方差	相互独立或弱相关	投票/平均	Random Forest
Boosting	串行训练	主要降低偏差	前后依赖，逐步改错	加权投票/加法模型	AdaBoost、Boosting Tree、GBDT
Stacking	分层训练	同时利用多模型优势	可异构	元学习器融合	Stacked Generalization

记忆：

Bagging：并行、采样、投票、降方差。
Boosting：串行、加权、改错、降偏差。
Stacking：先让多个模型预测，再训练一个模型学习怎么融合。

四、Bagging

Bagging 是 Bootstrap Aggregating 的缩写，即自助采样 + 聚合。

核心思想：

从原训练集 $S$ 中进行有放回采样，得到多个自助采样集。
每个采样集训练一个基学习器。
多个基学习器可以并行训练。
分类时投票，回归时平均。

算法流程：

给定训练集 $S$、基学习算法 $I$、训练轮数 $T$。
对 $t=1,\dots,T$：
- 从 $S$ 中有放回采样得到 $S_t$。
- 用 $S_t$ 训练基学习器 $C_t$。
对分类任务，用多数投票得到最终分类器：

$$ C^*(x)=\arg\max_y \sum_{t=1}^{T} I(C_t(x)=y) $$

重点理解：

Bagging 不会特别关注某些难样本，每个样本被抽到的概率相同。
由于基学习器可并行训练，所以效率较高。
它主要降低模型方差，使结果更稳定。
如果基学习器本身偏差很高，Bagging 后偏差仍可能很高。

优点：

并行式集成，训练效率较好。
能降低分类器方差，改善泛化。
对不稳定模型特别有效，例如决策树。

缺点：

对高偏差模型帮助有限。
集成后可解释性下降。
训练多个模型会增加计算和存储开销。

五、Random Forest

随机森林是 Bagging 的代表方法。

它可以理解为：Bagging + 决策树 + 特征随机选择。

训练过程：

从 $N$ 个训练样本中有放回采样 $N$ 次，得到一棵树的训练集。
每棵树使用不同的自助采样数据。
在每个结点分裂时，不从全部 $d$ 个特征中选最优特征，而是先随机选 $k$ 个特征，再从这 $k$ 个特征中选最优分裂特征。
通常 $k\ll d$。
每棵树通常充分生长，不剪枝。
多棵树投票或平均得到最终结果。

随机森林的特点：

差异性：每棵树的数据和特征都可能不同。
稳定性：通过投票或平均降低单棵树的不稳定性。
可并行化：树之间训练相对独立。
缓解维度灾难：每次只考虑部分特征。
可用袋外样本估计误差：每棵树约有一部分样本没有被抽到，可作为 out-of-bag 样本评估误差。

考试重点：

Random Forest 是 Bagging 的典型代表。它通过样本随机和特征随机增强树之间的差异性，再通过投票或平均降低方差、提高泛化能力。

六、Boosting

Boosting 的核心思想：把多个弱学习器串行组合成强学习器。

弱学习器：性能只比随机猜测略好。
强学习器：性能较高、泛化能力较好的学习器。

Boosting 的理论背景来自 PAC 学习理论：

强可学习和弱可学习在一定条件下等价。
可以通过 Boosting 把弱学习器提升为强学习器。

Boosting 的训练特点：

基学习器按顺序训练，不能简单并行。
后一个学习器依赖前面学习器的结果。
重点关注前面模型预测错误的样本。
最终模型通常是多个基学习器的加权组合。

从 bias-variance 角度看：

Boosting 通过不断修正错误，主要降低偏差。
但如果迭代过多或弱学习器过强，也可能过拟合。

七、AdaBoost

AdaBoost 是 Boosting 的代表方法，全称 Adaptive Boost。

核心思想：

初始化时，每个样本权重相同。
每一轮训练一个弱分类器。
被上一轮分错的样本权重变大。
被上一轮分对的样本权重变小。
错误率低的弱分类器在最终投票中权重大。
错误率高的弱分类器在最终投票中权重小。

二分类任务中，训练集为：

$$ T={(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)},\quad y_i\in{-1,1} $$

第 $k$ 个弱分类器 $G_k(x)$ 的加权错误率：

$$ e_k=\sum_{i=1}^{m} w_{k,i} I(G_k(x_i)\ne y_i) $$

弱分类器权重：

$$ \alpha_k=\frac{1}{2}\log \frac{1-e_k}{e_k} $$

含义：

$e_k$ 越小，$\alpha_k$ 越大。
分类越准的弱分类器，在最终模型中话语权越大。

样本权重更新：

$$ w_{k+1,i}=\frac{w_{k,i}}{Z_k}\exp(-\alpha_k y_iG_k(x_i)) $$

其中 $Z_k$ 是规范化因子，使新权重仍构成概率分布。

最终分类器：

$$ f(x)=sign\left(\sum_{k=1}^{K}\alpha_kG_k(x)\right) $$

考试重点：

AdaBoost 通过调整样本权重让后续弱分类器更关注前面分错的样本，并通过加权投票组合弱分类器。分类误差越小的弱分类器权重越大。

八、Boosting Tree 与 GBDT

Boosting Tree 是 Boosting 思想与决策树的结合。

核心思想：

Boosting 通常采用加法模型。
如果基函数是决策树，就得到提升树。

加法模型形式：

$$ f_M(x)=\sum_{m=1}^{M} h_m(x) $$

其中 $h_m(x)$ 表示第 $m$ 棵树。

回归提升树

回归问题中，提升树的基本流程：

初始化模型 $f_0(x)=0$ 或初始化为常数预测。
第 $m$ 轮计算当前模型的残差：

$$ r_{m,i}=y_i-f_{m-1}(x_i) $$

用残差训练一棵新的回归树 $h_m(x)$。
更新模型：

$$ f_m(x)=f_{m-1}(x)+h_m(x) $$

多轮之后得到最终模型：

$$ f_M(x)=\sum_{m=1}^{M}h_m(x) $$

直观理解：

第一棵树先做一个粗略预测。
第二棵树学习第一棵树没预测好的残差。
后面的树继续补前面模型的错误。

GBDT

GBDT 是 Gradient Boosting Decision Tree，即梯度提升决策树。

它把“拟合残差”的思想推广到一般损失函数：

平方损失下，负梯度就是残差。
一般损失下，用损失函数对当前模型的负梯度作为“伪残差”。
每一轮训练一棵 CART 树去拟合负梯度。

基本流程：

初始化弱学习器。
对每个样本计算当前损失的负梯度。
用负梯度构造新的训练目标。
训练一棵 CART 树。
计算叶子区域的最佳拟合值。
更新强学习器。
重复多轮，得到最终模型。

考试重点：

Boosting Tree 的基本思想是逐步加树，每一棵新树都学习当前模型没有拟合好的部分。平方损失下，新树拟合残差；一般损失下，新树拟合负梯度。

九、Stacking

Stacking 又称 Stacked Generalization，是一种学习法融合策略。

核心思想：

第一层训练多个初级学习器。
用这些初级学习器的预测结果构造新的特征。
第二层训练一个次级学习器，也叫元学习器。
元学习器学习如何融合第一层模型的输出。

流程：

将训练集划分为 $k$ 份。
对每个初级模型：
- 用其中 $k-1$ 份训练。
- 用剩下 1 份预测。
- 重复直到每份都被预测一次。
得到每个训练样本的 out-of-fold 预测结果。
把多个初级模型的预测结果拼成新的特征。
用新特征和原标签训练元学习器。
测试时，先让初级模型预测，再把预测结果输入元学习器。

为什么要用交叉验证构造次级训练集？

如果直接用训练好的初级模型预测原训练集，容易把训练集拟合得太好。
元学习器会学到过于乐观的预测结果，导致过拟合。
用 out-of-fold 预测可以更接近测试时的真实预测表现。

Stacking 的特点：

是异源集成的典型代表，可以融合不同类型模型。
目标是同时降低 bias 和 variance。
元学习器常用 Logistic Regression、CART、Random Forest、XGBoost 等。
重点掌握思想即可：把多个模型的输出当作新特征，再训练一个模型做融合。

十、前向分步算法

前向分步算法了解即可。

它用于优化加法模型：

$$ f(x)=\sum_{m=1}^{M}\beta_m b(x;\gamma_m) $$

直接同时优化所有基函数和系数通常很复杂，因此采用分步思想：

初始化 $f_0(x)=0$。
每一轮只学习一个新的基函数及其系数。
把新学到的基函数加到已有模型中。
逐步逼近整体目标函数。

与 AdaBoost 的关系：

AdaBoost 可以看作前向分步加法算法的一个特例。
AdaBoost 的基函数是基分类器。
AdaBoost 的损失函数是指数损失：

$$ L(y,f(x))=\exp[-yf(x)] $$

考试要求：

前向分步算法只需知道“每次只加一个基学习器，逐步优化加法模型”，不需要深入推导。

十一、Bagging 和 Boosting 的 bias-variance 区别

角度	Bagging	Boosting
训练方式	并行	串行
数据处理	自助采样，样本概率基本相同	根据错误调整样本权重
基学习器关系	相互独立或弱相关	后一个依赖前一个
主要作用	降低方差	降低偏差
适合模型	不稳定、高方差模型，如决策树	弱学习器，如浅层树、树桩
代表方法	Random Forest	AdaBoost、Boosting Tree、GBDT
过拟合风险	相对较低	迭代过多时可能过拟合

重点理解：

Bagging 通过“多个不稳定模型取平均/投票”来稳定结果，所以主要降低方差。
Boosting 通过“后续模型修正前面模型错误”来增强拟合能力，所以主要降低偏差。
Stacking 通过元学习器学习融合方式，目标可以同时降低偏差和方差。

十二、易错点

集成学习不等于一定有效；基学习器既要有一定准确率，也要有差异性。
Bagging 的关键不是串行改错，而是并行采样和聚合。
Boosting 的关键不是简单投票，而是逐步关注错误样本。
Random Forest 是 Bagging 的代表方法，不是 Boosting。
AdaBoost 是 Boosting 的代表方法，核心是样本权重和分类器权重。
Boosting Tree 是用决策树作为基学习器的 Boosting 方法。
GBDT 中平方损失下拟合残差，一般损失下拟合负梯度。
Stacking 的重点是元学习器，不是简单平均。
Stacking 训练元学习器时通常要用交叉验证生成 out-of-fold 预测，避免过拟合。
Bagging 主要降方差，Boosting 主要降偏差，不要反过来。

十三、考试中可以这样写

集成学习是一类通过组合多个基学习器来提升泛化性能的方法。单个模型由于假设空间、训练数据、优化稳定性和 bias-variance 权衡等限制，性能往往有限。集成学习通过提高模型多样性并进行投票、平均或学习式融合，使多个模型的错误相互抵消，从而提升整体预测效果。

Bagging 是并行式集成方法，通过自助采样训练多个基学习器，再用投票或平均得到最终结果，主要作用是降低方差，代表方法是随机森林。随机森林在 Bagging 的基础上进一步引入特征随机选择，使树之间差异更大，从而提升稳定性和泛化能力。

Boosting 是串行式集成方法，后一个基学习器依赖前一个基学习器的结果，重点关注前面预测错误的样本，逐步把弱学习器提升为强学习器，主要作用是降低偏差。AdaBoost 通过调整样本权重和弱分类器权重进行加权投票；Boosting Tree 则用决策树作为基学习器，每一棵新树学习当前模型尚未拟合好的部分。

Stacking 是一种多模型融合思想，它把多个初级学习器的预测结果作为新的特征，再训练一个元学习器进行融合。它可以融合异构模型，目标是同时利用不同模型的优势，降低泛化误差。

十四、速记版

集成学习：多个模型一起决策，提高泛化。
单个模型有限：表达能力、数据、噪声、优化和偏差-方差限制。
好集成需要：基学习器准确，并且错误有差异。
Bagging：有放回采样，并行训练，投票/平均，主要降方差。
Random Forest：Bagging + 决策树 + 特征随机选择。
Boosting：串行训练，后面模型改前面错误，主要降偏差。
AdaBoost：错样本权重变大，好分类器权重变大。
Boosting Tree：用树做 Boosting，每棵树补前面模型的残差或负梯度。
GBDT：一般损失下拟合负梯度，平方损失下拟合残差。
Stacking：多个模型输出变新特征，再训练元学习器融合。
前向分步算法：每次只加一个基函数，逐步优化加法模型，了解即可。

10. 聚类 Clustering

一、整体思想

聚类是典型的无监督学习任务。它没有事先给定类别标签，而是根据样本之间的相似性或距离，把数据划分成若干簇。

核心目标：

同一簇内部样本尽量相似。
不同簇之间样本尽量不相似。

一个好的聚类结果通常满足：

簇内相似度高：intra-cluster similarity 高。
簇间相似度低：inter-cluster similarity 低。

注意：聚类没有绝对标准。聚类结果好不好，往往依赖用户关注的特征和实际应用场景。

例如同一批图形：

按颜色可以得到一种聚类。
按形状可以得到另一种聚类。
按大小或顶点数又可以得到其他聚类。

所以聚类的关键是：

特征选取是否合适。
距离度量是否合适。
聚类准则是否符合任务目标。

二、基本概念

给定样本集合：

$$ D={x_1,x_2,\dots,x_m},\quad x_i\in \mathbb{R}^d $$

希望把它划分为 $k$ 个簇：

$$ C_1,C_2,\dots,C_k $$

通常要求：

$$ C_i\cap C_j=\varnothing,\quad i\ne j $$

$$ D=\bigcup_{i=1}^{k} C_i $$

聚类分析的依据：

把每个样本看成特征空间中的一个点。
点与点之间的距离表示差异。
距离越近，越可能属于同一簇。
距离越远，越可能属于不同簇。

三、距离度量

聚类必须先定义“相似”或“不相似”。

常见距离或相似度：

度量	形式	适用理解
欧氏距离	$\|x_i-x_j\|_2$	最常用，适合连续数值特征
曼哈顿距离	$\|x_i-x_j\|_1$	按各维绝对差累加
切比雪夫距离	$\|x_i-x_j\|_\infty$	取各维差异最大值
闵可夫斯基距离	$\left(\sum_{l=1}^{d}\left\|x_{il}-x_{jl}\right\|^p\right)^{\frac{1}{p}}$	欧氏和曼哈顿的推广
余弦相似度	$\frac{x_i^Tx_j}{\|x_i\|\|x_j\|}$	关注方向相似，常用于文本/高维向量
马氏距离	$\sqrt{(x_i-x_j)^TM^{-1}(x_i-x_j)}$	考虑特征相关性和尺度

易错点：

距离度量不同，聚类结果可能完全不同。
使用欧氏距离时通常要做标准化，否则量纲大的特征会主导结果。
聚类效果很依赖特征设计；特征不好，算法再复杂也可能聚不好。

四、聚类准则

聚类准则用来判断一个聚类结果是否好。

常见思想：

类内距离小。
类间距离大。
或者簇内相似度高、簇间相似度低。

K-means 使用的典型准则是最小化簇内平方误差和：

$$ J=\sum_{j=1}^{k}\sum_{x\in C_j}|x-\mu_j|^2 $$

其中：

$C_j$ 表示第 $j$ 个簇。
$\mu_j$ 表示第 $j$ 个簇的中心。
$J$ 越小，说明样本越靠近自己的簇中心。

五、聚类方法分类

课件中聚类方法主要包括：

方法类型	核心思想	代表方法	掌握程度
原型聚类	用一组原型刻画聚类结构	K-means、ISODATA、GMM	重点
密度聚类	根据样本分布紧密程度扩展簇	DBSCAN、OPTICS、DENCLUE	了解
层次聚类	逐步合并或拆分类	AGNES	了解
基于图的方法	把样本看成图节点，根据边权划分图	谱聚类等	了解

老师强调：K-means、ISODATA、高斯混合聚类在实际中出现频率较高，需要重点掌握。

六、K-means

K-means 是最经典的原型聚类算法。

核心思想：

每个簇用一个中心点表示。
样本归到最近的中心。
中心更新为簇内样本均值。
不断重复“分配样本”和“更新中心”，直到收敛。

算法流程：

选择聚类数量 $k$。
初始化 $k$ 个聚类中心：

$$ \mu_1,\mu_2,\dots,\mu_k $$

对每个样本 $x_i$，计算它到每个中心的距离，把它分到最近的中心所属簇：

$$ c_i=\arg\min_j |x_i-\mu_j|^2 $$

对每个簇重新计算中心：

$$ \mu_j=\frac{1}{|C_j|}\sum_{x_i\in C_j}x_i $$

如果样本所属簇不再变化，或目标函数变化很小，则停止；否则回到第 3 步。

K-means 优化目标：

$$ \min_{C_1,\dots,C_k}\sum_{j=1}^{k}\sum_{x_i\in C_j}|x_i-\mu_j|^2 $$

重点理解：

K-means 是迭代优化算法。
分配样本时固定中心。
更新中心时固定样本归属。
每一步都会使目标函数不增大，但只能保证收敛到局部最优。

适用场景：

聚类数 $k$ 大致已知。
簇接近球形或凸形。
簇之间分离较明显。
特征为连续数值型，并且距离度量有意义。

缺点：

需要预先指定 $k$。
对初始中心敏感。
对离群点敏感。
不适合非凸形状的簇。
不适合大小、密度差异很大的簇。

七、K-means++

K-means++ 是 K-means 的初始化改进方法。

基本思想：

初始聚类中心之间应该尽量分散。

如果初始中心太近，K-means 容易陷入较差的局部最优；K-means++ 用概率方式让后续中心更倾向于选在远离已有中心的位置。

算法流程：

从数据集中随机选择一个样本作为第一个初始中心 $c_1$。
对每个样本 $x$，计算它到当前已有中心的最近距离：

$$ D(x)=\min_{c\in C}|x-c| $$

按如下概率选择下一个中心：

$$ P(x)=\frac{D(x)^2}{\sum_{x'\in D}D(x')^2} $$

重复第 2-3 步，直到选出 $k$ 个初始中心。
后续过程与普通 K-means 相同。

重点掌握：

K-means++ 不是新的聚类目标函数。
它主要改进 K-means 的初始中心选择。
距离已有中心越远的样本，被选为新中心的概率越大。
它通常能让 K-means 更稳定、收敛更好。

八、ISODATA

ISODATA 全称 Iterative Self-organizing Data Analysis Techniques，即迭代自组织数据分析算法。

它可以理解为：在 K-means 的基础上加入簇的分裂与合并机制。

K-means 通常要求类别数 $k$ 已知，而 ISODATA 更灵活：

如果某些簇太小，可以丢弃。
如果两个簇中心太近，可以合并。
如果某个簇内部太分散，可以分裂。

基本流程：

选择初始参数和初始聚类中心。
将每个样本分配到最近的聚类中心。
检查每个簇的样本数；如果某簇样本数小于阈值 $N_{min}$，可丢弃该簇，并重新分配样本。
重新计算每个簇中心。
根据当前簇数和簇内分散程度，决定是否分裂。
根据簇中心之间距离，决定是否合并。
重复迭代，直到收敛或达到最大迭代次数。

合并操作

当两个簇中心距离小于给定阈值 $d_{min}$ 时，可以合并。

设两个簇样本数分别为 $n_i,n_j$，中心分别为 $m_i,m_j$，合并后的新中心为：

$$ m_{new}=\frac{n_i m_i+n_j m_j}{n_i+n_j} $$

直观理解：

两个簇太近，说明它们可能本来就是同一类。
合并后中心是按样本数加权的均值。

分裂操作

当某个簇内部方差太大，并且样本数足够多时，可以分裂。

基本做法：

计算该簇在各个属性维度上的方差。
找到最大方差方向。
如果最大方差超过阈值 $\sigma$，且样本数满足要求，则沿该方向把中心正负偏移，生成两个新中心。

直观理解：

一个簇太散，说明它可能包含多个真实簇。
沿最分散的方向拆开，得到更合理的聚类结构。

ISODATA 与 K-means 的区别：

角度	K-means	ISODATA
聚类数	通常固定为 $k$	可通过分裂/合并动态调整
核心操作	分配样本、更新均值	分配、更新、丢弃、分裂、合并
灵活性	较低	较高
参数数量	较少	较多
实用问题	初始中心和 $k$ 敏感	参数较多，不易设定

考试重点：

ISODATA 与 K-means 类似，都通过样本均值迭代更新聚类中心；不同点是 ISODATA 增加了分裂和合并操作，可以根据类别实际情况调整聚类中心数。

九、高斯混合聚类 GMM

高斯混合聚类使用概率模型表达聚类原型。

K-means 是“硬聚类”：

每个样本只属于一个簇。
样本归属是 0 或 1。

GMM 是“软聚类”：

每个样本可以以不同概率属于多个高斯成分。
输出的是后验概率，也叫责任度。

高斯混合分布：

$$ p(x)=\sum_{i=1}^{k}\alpha_i p(x|\mu_i,\Sigma_i) $$

其中：

$k$ 是高斯成分个数。
$\alpha_i$ 是第 $i$ 个高斯成分的混合系数。
$\alpha_i\ge 0$。
$\sum_{i=1}^{k}\alpha_i=1$。
$\mu_i$ 是第 $i$ 个高斯分布的均值。
$\Sigma_i$ 是第 $i$ 个高斯分布的协方差矩阵。

样本 $x_j$ 由第 $i$ 个高斯成分生成的后验概率：

$$ \gamma_{ji} =P(z_j=i|x_j) =\frac{\alpha_i p(x_j|\mu_i,\Sigma_i)} {\sum_{l=1}^{k}\alpha_l p(x_j|\mu_l,\Sigma_l)} $$

理解：

$\gamma_{ji}$ 表示第 $i$ 个高斯成分对样本 $x_j$ 的责任度。
责任度越大，说明该样本越可能来自这个高斯成分。
聚类时可以把样本分到责任度最大的成分，也可以保留软分配概率。

GMM 参数通常用 EM 算法估计：

E 步：根据当前参数计算每个样本属于每个高斯成分的后验概率。
M 步：根据后验概率更新 $\alpha_i,\mu_i,\Sigma_i$。

GMM 与 K-means 对比：

角度	K-means	GMM
模型思想	距离中心最近	概率生成模型
聚类方式	硬聚类	软聚类
簇形状	倾向球形	可通过协方差刻画椭圆形
输出	类别编号	属于各成分的概率
参数	中心 $\mu$	混合系数、均值、协方差
优点	简单、快	表达能力更强
缺点	对形状假设强	参数估计更复杂

考试重点：

高斯混合聚类假设数据由多个高斯分布混合生成，每个高斯成分对应一个潜在簇。对样本进行聚类时，计算它属于每个高斯成分的后验概率，并根据概率进行软分配。

十、聚类性能评价指标

聚类评价没有统一绝对标准，通常分为外部指标和内部指标。

1. 外部指标

外部指标需要有参考标签或参考模型。

常见外部指标：

Cluster Accuracy，CA，聚类准确率。
Rand Index，RI，兰德指数。
Adjusted Rand Index，ARI，调整兰德指数。
Mutual Information，MI，互信息。
Normalized Mutual Information，NMI，归一化互信息。
Jaccard 系数。
FM 指数。

适用场景：

已经知道真实类别标签。
想比较聚类结果和真实标签是否一致。

理解：

RI/ARI 关注样本对关系是否一致。
MI/NMI 关注聚类结果和真实标签共享了多少信息。
ARI 相比 RI 做了随机校正，更适合比较不同聚类结果。
NMI 对互信息做归一化，便于比较。

2. 内部指标

内部指标不需要真实标签，直接根据聚类结果自身评价。

核心思想：

类内越紧凑越好。
类间越分散越好。

常见内部指标：

指标	含义	趋势
Compactness，CP	紧密度，衡量簇内距离	越小越好
Separation，SP	间隔度，衡量簇间距离	越大越好
Davies-Bouldin Index，DBI	同时考虑类内紧密和类间分离	越小越好
Dunn Validity Index，DVI	最小类间距离 / 最大类内距离	越大越好

CP 紧密度：

衡量簇内样本到簇中心的距离。
CP 越小，说明类内越紧凑。
缺点：只考虑类内，没有考虑类间分离。

SP 间隔度：

衡量不同簇中心之间的距离。
SP 越大，说明类间越分散。
缺点：只考虑类间，没有考虑类内紧密。

DBI：

同时考虑簇内紧密度和簇间距离。
DBI 越小，说明类内越紧凑、类间越分散。
缺点：通常依赖欧氏距离，对环状等非凸分布评价可能不好。

DVI：

用最小类间距离除以最大类内距离。
DVI 越大越好。
缺点：对离散点敏感，对环状分布评价也可能不理想。

考试重点：

聚类评价的基本思想是簇内相似度高、簇间相似度低。外部指标需要参考标签，如 RI、ARI、MI、NMI；内部指标不需要参考标签，如 CP、SP、DBI、DVI。

十一、了解即可：DBSCAN

DBSCAN 是基于密度的聚类方法。

核心思想：

聚类结构由样本分布的紧密程度决定。
从高密度区域开始扩展簇。
能发现任意形状的簇。
能识别噪声点。

关键概念：

$\epsilon$-邻域：距离某样本不超过 $\epsilon$ 的样本集合。
MinPts：邻域内至少需要多少样本。
核心对象：$\epsilon$-邻域内样本数不少于 MinPts 的点。
密度直达：一个点在核心对象的 $\epsilon$-邻域内。
密度可达：通过一串密度直达关系可以到达。
密度相连：两个点都可由某个共同点密度可达。

优点：

不需要预先指定簇数。
可以发现非球形簇。
可以处理噪声。

缺点：

对 $\epsilon$ 和 MinPts 敏感。
不适合密度差异很大的数据。
高维数据中距离和密度判断可能不可靠。

十二、了解即可：层次聚类

层次聚类通过逐步合并或拆分形成树状聚类结构。

课件重点是凝聚式层次聚类 AGNES。

AGNES 流程：

初始时，每个样本自成一簇。
计算簇与簇之间的距离。
合并最近的两个簇。
更新距离矩阵。
重复直到达到目标簇数，或所有样本合成一个簇。

簇间距离常见定义：

最短距离法：两个簇中任意样本对的最小距离。
最长距离法：两个簇中任意样本对的最大距离。
类平均距离法：两个簇所有样本对距离的平均值。

理解即可：

层次聚类能形成树形结构。
不同距离准则会得到不同结果。
计算量通常较大，不适合特别大规模数据。

十三、了解即可：基于密度或基于图的方法

基于密度的方法：

典型代表：DBSCAN、OPTICS、DENCLUE。
通过样本局部密度和可连接关系扩展簇。
适合发现非凸形状簇。

基于图的方法：

把样本看成图中的节点。
节点之间的边权表示相似度。
聚类问题转化为图划分问题。
谱聚类是典型代表。

了解重点：

基于图的方法强调样本之间的连接结构。
它不只看中心点距离，而是看整体相似图结构。
通常用于非线性结构较明显的数据。

十四、易错点

聚类是无监督学习，类别标签不是事先给定的。
聚类结果没有唯一绝对标准，取决于特征、距离和任务需求。
K-means 需要预先指定 $k$。
K-means 对初始中心敏感，K-means++ 是为了解决初始化问题。
K-means++ 不是“拼命史佳佳”，也不是另一种完全不同的聚类模型。
ISODATA 的关键是分裂和合并，可以动态调整类别数。
GMM 是软聚类，K-means 是硬聚类。
GMM 中每个高斯成分不一定严格等同于真实类别，但常被用作潜在簇。
外部评价指标需要真实标签，内部评价指标不需要真实标签。
CP 越小越好，SP 越大越好，DBI 越小越好，DVI 越大越好。

十五、考试中可以这样写

聚类是一类无监督学习方法，它根据样本之间的相似性或距离，将数据划分为若干簇。一个好的聚类结果通常要求簇内相似度高、簇间相似度低。聚类效果强烈依赖特征选择、距离度量和聚类准则，因此不存在适用于所有任务的绝对标准。

K-means 是典型原型聚类方法。它先指定聚类数 $k$ 并初始化聚类中心，然后反复执行两个步骤：将样本分配给最近的聚类中心，并把每个簇的中心更新为簇内样本均值。K-means 简单高效，但对初始中心、离群点和 $k$ 的选择敏感。K-means++ 通过让初始中心尽量分散来改进初始化。

ISODATA 与 K-means 类似，也通过样本均值更新聚类中心，但它增加了簇的分裂和合并机制，因此可以根据聚类结果动态调整类别数。高斯混合聚类使用多个高斯分布成分来刻画数据分布，每个样本以一定后验概率属于不同成分，是一种软聚类方法，参数通常通过 EM 算法估计。

聚类评价指标分为外部指标和内部指标。外部指标需要参考标签，如 RI、ARI、MI、NMI；内部指标直接根据聚类结果评价，如 CP、SP、DBI、DVI。评价的共同思想是类内尽量紧凑、类间尽量分离。

十六、速记版

聚类：无标签分组，簇内相似、簇间不同。
聚类关键：特征、距离、准则。
K-means：选 $k$，初始化中心，分配样本，更新均值，直到收敛。
K-means++：让初始中心尽量分散，改善 K-means 初始化。
ISODATA：K-means + 分裂 + 合并，类别数更灵活。
GMM 聚类：多个高斯成分生成数据，样本按后验概率软分配。
DBSCAN：按密度扩展簇，可发现噪声和非球形簇，了解即可。
层次聚类：从每点一簇开始逐步合并，形成树形结构，了解即可。
外部指标：CA、RI、ARI、MI、NMI，需要真实标签。
内部指标：CP、SP、DBI、DVI，不需要真实标签。

11. 高斯混合模型 GMM 与 EM

一、为什么单一分布不足以刻画复杂数据？

单一高斯分布通常只能描述一个比较简单的“单峰”数据分布。

单个高斯分布由均值和协方差决定：

均值 $\mu$ 决定分布中心位置。
协方差 $\Sigma$ 决定分布的尺度、方向和形状。

但实际数据往往更复杂：

可能有多个中心。
可能有多个子群体。
可能不是单峰分布。
不同区域的方差、方向、密度可能不同。

例如所有人的身高可能近似一个高斯分布，但如果把不同性别、不同年龄段、不同群体混在一起，整体分布就可能不再适合用一个高斯分布描述。

因此，单一高斯分布的表达能力有限。

二、GMM 如何刻画复杂分布？

GMM 的核心思想：

用多个高斯分布的加权和来刻画复杂数据分布。

高斯混合模型：

$$ p(x)=\sum_{i=1}^{K}\alpha_i \mathcal{N}(x|\mu_i,\Sigma_i) $$

其中：

$K$ 是高斯成分个数。
$\alpha_i$ 是第 $i$ 个高斯成分的权重。
$\alpha_i\ge 0$。
$\sum_{i=1}^{K}\alpha_i=1$。
$\mathcal{N}(x|\mu_i,\Sigma_i)$ 是第 $i$ 个高斯分布。

直观理解：

每个高斯分布负责刻画数据中的一个局部模式。
多个高斯分布叠加后，可以形成更复杂的整体分布。
权重 $\alpha_i$ 表示第 $i$ 个成分在整体分布中的占比。

GMM 的生成过程：

先从离散分布中选择一个隐藏成分 $z$：

$$ P(z=i)=\alpha_i $$

再从对应的高斯分布中生成样本：

$$ x\sim \mathcal{N}(\mu_i,\Sigma_i) $$

这里：

$x$ 是可观测变量。
$z$ 是隐藏变量，表示样本来自哪个高斯成分。

三、GMM 的参数

GMM 需要估计三类参数：

参数	含义
$\alpha_i$	第 $i$ 个高斯成分的混合权重
$\mu_i$	第 $i$ 个高斯成分的均值
$\Sigma_i$	第 $i$ 个高斯成分的协方差矩阵

如果知道每个样本来自哪个高斯成分，参数估计会很简单：

$\alpha_i$：来自第 $i$ 个成分的样本比例。
$\mu_i$：这些样本的均值。
$\Sigma_i$：这些样本的协方差。

但现实中通常不知道样本来自哪个成分，也就是隐藏变量 $z$ 未知，所以需要 EM 算法。

四、最大似然估计 MLE

最大似然估计的思想：

选择一组参数，使观测数据在该模型下出现的概率最大。

给定样本 $X={x_1,x_2,\dots,x_m}$，GMM 的似然函数为：

$$ L(\theta)=\prod_{j=1}^{m}p(x_j|\theta) $$

通常使用对数似然：

$$ \log L(\theta)=\sum_{j=1}^{m}\log p(x_j|\theta) $$

对 GMM：

$$ \log L(\theta)=\sum_{j=1}^{m} \log \left(\sum_{i=1}^{K}\alpha_i\mathcal{N}(x_j|\mu_i,\Sigma_i)\right) $$

难点：

对数里面有求和。
样本来自哪个高斯成分未知。
无法像单高斯分布那样直接求闭式解。

这就是 EM 算法要解决的问题。

五、EM 算法的基本思想

EM 是 Expectation-Maximization，即期望最大化算法。

适用场景：

模型中有无法直接观测的隐藏变量。
直接最大化似然函数比较困难。
如果隐藏变量已知，参数估计会变简单。

核心思想：

在不知道隐藏变量的情况下，先用当前参数估计隐藏变量的分布，再用估计出的隐藏变量分布更新参数，如此反复迭代。

EM 包含两步：

E-Step

E-Step：Expectation Step，期望步。

作用：

固定当前模型参数。
根据当前参数计算隐藏变量的后验概率。
在 GMM 中，就是计算每个样本属于每个高斯成分的概率。

对样本 $x_j$，它属于第 $i$ 个高斯成分的后验概率为：

$$ \gamma_{ji} =P(z_j=i|x_j) =\frac{\alpha_i\mathcal{N}(x_j|\mu_i,\Sigma_i)} {\sum_{l=1}^{K}\alpha_l\mathcal{N}(x_j|\mu_l,\Sigma_l)} $$

这里 $\gamma_{ji}$ 也叫责任度。

M-Step

M-Step：Maximization Step，最大化步。

作用：

固定 E 步得到的责任度。
用这些软分配结果重新估计模型参数。

令：

$$ N_i=\sum_{j=1}^{m}\gamma_{ji} $$

则参数更新为：

$$ \alpha_i=\frac{N_i}{m} $$

$$ \mu_i=\frac{1}{N_i}\sum_{j=1}^{m}\gamma_{ji}x_j $$

$$ \Sigma_i=\frac{1}{N_i}\sum_{j=1}^{m}\gamma_{ji}(x_j-\mu_i)(x_j-\mu_i)^T $$

直观理解：

$\gamma_{ji}$ 越大，样本 $x_j$ 对第 $i$ 个高斯成分参数更新的影响越大。
均值和协方差不是用硬分类样本计算，而是用责任度加权计算。

六、EM 算法流程

初始化参数：

$$ \theta^{(0)}={\alpha_i,\mu_i,\Sigma_i}_{i=1}^{K} $$

E 步：用当前参数计算每个样本属于每个高斯成分的后验概率 $\gamma_{ji}$。
M 步：用 $\gamma_{ji}$ 更新 $\alpha_i,\mu_i,\Sigma_i$。
重复 E 步和 M 步。
当对数似然变化很小或达到最大迭代次数时停止。

重要性质：

每轮 EM 通常不会降低似然函数。
EM 可能收敛到局部最优。
EM 对初始化敏感。
GMM 中高斯成分个数 $K$ 需要人为指定或通过模型选择确定。

七、K-means 与 EM 的关系

K-means 可以看作一种带有 EM 思想的算法。

对应关系：

K-means	EM/GMM 视角
样本 $x$	可观测变量
簇标签	隐藏变量
聚类中心 $\mu$	模型参数
分配样本到最近中心	E 步
更新簇中心为均值	M 步

区别：

K-means 是硬分配，每个样本只属于一个簇。
GMM/EM 是软分配，每个样本对多个成分都有责任度。
K-means 常对应协方差相同、形状较简单的特殊情况。
GMM 表达能力更强，可以刻画不同形状和方差的簇。

八、易错点

GMM 不是一个高斯分布，而是多个高斯分布的加权和。
混合系数 $\alpha_i$ 必须非负，并且总和为 1。
GMM 中的 $z$ 是隐藏变量，表示样本来自哪个高斯成分。
EM 不是只用于 GMM，而是用于含隐藏变量的参数估计问题。
E 步估计隐藏变量后验概率，M 步更新模型参数。
GMM 聚类是软聚类，K-means 是硬聚类。
EM 只能保证逐步改进似然，不能保证找到全局最优。
本章重点掌握思想，不需要花太多时间推复杂理论证明。

九、考试中可以这样写

单一高斯分布只能刻画较简单的单峰分布，而实际数据往往包含多个子群体或多个局部模式，因此单一分布表达能力不足。高斯混合模型用多个高斯分布的加权和来表示复杂分布，每个高斯成分刻画一个局部结构，混合权重表示该成分在整体数据中的占比。

GMM 可以看成一个含隐藏变量的生成模型。生成样本时，先根据混合系数选择一个高斯成分，再从该高斯分布中采样得到观测样本。由于实际训练数据中不知道每个样本来自哪个高斯成分，因此需要用 EM 算法估计参数。

EM 算法是一种处理隐藏变量模型的迭代方法。E 步在当前参数下计算隐藏变量的后验概率，在 GMM 中就是计算每个样本属于各个高斯成分的概率；M 步固定这些后验概率，重新估计混合权重、均值和协方差。反复执行 E 步和 M 步，直到模型收敛。

十、速记版

单高斯：只能描述简单单峰分布。
GMM：多个高斯分布加权相加，刻画复杂分布。
$\alpha_i$：第 $i$ 个成分的权重。
$\mu_i$：第 $i$ 个成分的中心。
$\Sigma_i$：第 $i$ 个成分的形状和方向。
隐变量 $z$：样本来自哪个高斯成分。
E 步：算每个样本属于各成分的概率。
M 步：用这些概率加权更新参数。
EM：E/M 两步反复迭代，直到收敛。
GMM vs K-means：GMM 软分配，K-means 硬分配。

12. 神经网络 Neural Networks

一、整体思想

神经网络可以看成由大量可学习的函数模块组合而成的模型。

核心思想：

单个神经元完成一次“加权求和 + 非线性变换”。
多个神经元组成一层。
多层堆叠形成复杂函数。
训练时通过损失函数衡量预测误差，再用反向传播计算梯度并更新参数。

神经网络学习的是一个复合函数：

$$ f(x)=f_L(f_{L-1}(\cdots f_1(x))) $$

每一层都有参数，训练目标是找到一组参数，使损失函数尽可能小。

本章重点抓住四件事：

神经元和网络结构。
前向传播如何算输出。
反向传播如何算梯度。
CNN 为什么适合图像，以及参数量怎么算。

二、MP 神经元基本结构

MP 神经元是最早的人工神经元数学模型。

一个神经元包含：

输入：$x_1,x_2,\dots,x_d$。
权重：$w_1,w_2,\dots,w_d$。
偏置：$b$。
加权求和：$z=\sum_i w_i x_i+b$。
激活函数：$a=f(z)$。
输出：$a$。

也可以把偏置写成一个固定输入：

$$ x_0=1,\quad w_0=b $$

则：

$$ z=\sum_{i=0}^{d}w_i x_i $$

$$ a=f(z) $$

MP 神经元的直观对应：

输入相当于树突接收信号。
权重相当于突触连接强度。
加权求和相当于细胞体整合信号。
激活函数决定是否“放电”。

早期 MP 模型常用阈值函数：

$$ g(z)= \begin{cases} 1, & z>0\ 0, & z\le 0 \end{cases} $$

例如逻辑与、逻辑或都可以用合适权重和偏置表示。

MP 神经元的局限：

输入只是线性求和，表达能力有限。
输出形式简单。
单个神经元只能表达简单决策边界。
对 XOR 这类非线性可分问题无能为力。

三、多层神经网络

单层感知机只能解决线性可分问题。多层神经网络通过隐藏层引入非线性表示，可以解决更复杂的问题。

多层感知机 MLP 通常包含：

输入层：接收原始特征。
隐藏层：学习中间特征表示。
输出层：给出最终预测。

多层前馈神经网络的特点：

包含一个或多个隐藏层。
信息从输入层逐层传到输出层。
同层神经元之间通常没有连接。
不存在从后层到前层的反馈连接。

隐藏层的作用：

隐藏层神经元可以看作特征检测器。
它们把原始输入变换到新的特征空间。
多层组合可以表达复杂的非线性函数。

重要结论：

只要隐藏层神经元足够多，多层前馈神经网络可以以任意精度逼近连续函数。

但实际中：

隐藏层数怎么选没有固定答案。
每层神经元数怎么选也没有固定答案。
常用验证集和试错法调整结构。

四、激活函数

激活函数的作用：引入非线性。

如果没有激活函数，多层线性变换叠加仍然等价于一个线性变换，网络再深也无法表达复杂非线性关系。

常见激活函数：

激活函数	公式	特点
阶跃函数	$I(x\ge 0)$	早期感知机使用，不连续、不可微
Sigmoid	$\frac{1}{1+e^{-x}}$	输出在 $(0,1)$，可微，但易梯度消失
tanh	$\tanh(x)$	输出在 $(-1,1)$，零中心，也可能饱和
ReLU	$\max(0,x)$	简单高效，缓解梯度消失
Leaky ReLU/PReLU	$x$ 或 $ax$	负半轴保留小梯度
ELU	$x$ 或 $a(e^x-1)$	负半轴更平滑
Maxout	$\max(w_1x+b_1,w_2x+b_2)$	表达能力强，参数更多

Sigmoid：

$$ \sigma(x)=\frac{1}{1+e^{-x}} $$

导数必须会：

$$ \sigma'(x)=\sigma(x)(1-\sigma(x)) $$

ReLU：

$$ ReLU(x)=\max(0,x) $$

导数：

$$ ReLU'(x)= \begin{cases} 1, & x>0\ 0, & x<0 \end{cases} $$

重点理解：

Sigmoid/tanh 是饱和激活函数，输入很大或很小时导数接近 0，容易梯度消失。
ReLU 是非饱和激活函数，计算简单，训练深层网络更常用。
激活函数必须可用于梯度计算，否则反向传播无法顺利进行。

五、如何构造神经网络

构造神经网络一般按任务从后往前确定。

基本步骤：

确定输入形式：
- 表格数据：输入维度为特征数 $d$。
- 图像：输入形状为 $H\times W\times C$。
- 文本/序列：输入为 token 序列或向量序列。
确定输出形式：
- 二分类：1 个输出或 2 个输出。
- 多分类：类别数 $K$ 个输出，通常接 Softmax。
- 回归：输出维度等于预测目标维度。
选择网络层：
- 表格数据常用全连接层。
- 图像数据常用卷积层、池化层、全连接层。
- 序列数据可用 RNN、Transformer 等。
选择激活函数：
- 隐藏层常用 ReLU 系列。
- 输出层根据任务选 Sigmoid、Softmax 或线性输出。
选择损失函数：
- 回归：均方误差 MSE。
- 二分类：二元交叉熵。
- 多分类：交叉熵。
用前向传播计算输出。
用反向传播计算梯度。
用优化器更新参数。

常见输出层选择：

任务	输出层	损失函数
回归	线性输出	MSE
二分类	Sigmoid	Binary Cross Entropy
多分类	Softmax	Cross Entropy

六、全连接网络参数量计算

全连接层中，每个输出神经元都连接到上一层所有输入。

若上一层有 $n_{in}$ 个单元，当前层有 $n_{out}$ 个单元，则：

权重参数：$n_{in}\times n_{out}$。
偏置参数：$n_{out}$。
总参数：

$$ (n_{in}+1)n_{out} $$

多层全连接网络总参数量：

$$ \sum_{l=1}^{L}(n_{l-1}+1)n_l $$

其中 $n_{l-1}$ 是上一层宽度，$n_l$ 是当前层宽度。

例 1：

输入 100 维，隐藏层 50 个神经元，输出 10 类。

第一层参数：

$$ (100+1)\times 50=5050 $$

第二层参数：

$$ (50+1)\times 10=510 $$

总参数：

$$ 5050+510=5560 $$

例 2：图像全连接很容易爆炸。

一张 $1000\times1000$ 灰度图像有：

$$ 1000\times1000=10^6 $$

个输入。如果连接到 $10^6$ 个隐藏单元，全连接权重数量约为：

$$ 10^6\times 10^6=10^{12} $$

参数量极大，训练和存储都非常困难。

七、CNN 为什么比全连接网络更适合图像

图像具有两个重要结构：

局部性：相邻像素关系最强，局部区域能形成边缘、纹理、角点等特征。
平移不变性：同一个局部模式出现在图像不同位置，含义通常相近。

全连接网络的问题：

每个像素都连接到每个隐藏单元，参数量巨大。
没有利用图像的局部空间结构。
同一个图案出现在不同位置，需要重复学习。
容易过拟合，计算开销大。

CNN 的关键设计：

局部连接：每个卷积核只看局部区域。
参数共享：同一个卷积核在整张图像上滑动，共用一组参数。
多过滤器：不同卷积核学习不同特征。
层次化特征：浅层学边缘纹理，深层学部件和语义。
池化/下采样：降低空间尺寸，扩大感受野，缓解过拟合。

课件中的参数量对比：

$1000\times1000$ 图像连接到 $10^6$ 个隐藏单元，全连接约 $10^{12}$ 个参数。
若只做 $10\times10$ 局部连接，约 $10^8$ 个连接参数。
若使用 $10\times10$ 卷积核并共享参数，100 个 filters 只有：

$$ 10\times10\times100=10000 $$

个卷积核参数，不含偏置。

结论：

CNN 通过局部连接和参数共享大幅减少参数量，同时更符合图像的局部结构和平移不变性，因此比全连接网络更适合图像任务。

八、CNN 参数量计算

卷积层参数量只和卷积核大小、输入通道数、输出通道数有关，和输入图像的高宽无关。

设：

卷积核大小为 $K_h\times K_w$。
输入通道数为 $C_{in}$。
输出通道数为 $C_{out}$，也就是 filter 个数。
每个输出通道有一个 bias。

卷积层参数量：

$$ (K_hK_wC_{in}+1)C_{out} $$

不计 bias 时：

$$ K_hK_wC_{in}C_{out} $$

例 1：

输入为 RGB 图像，$C_{in}=3$，卷积核 $3\times3$，输出通道 $96$。

不计 bias：

$$ 3\times3\times3\times96=2592 $$

计 bias：

$$ (3\times3\times3+1)\times96=2688 $$

例 2：

输入通道 $64$，卷积核 $3\times3$，输出通道 $128$。

计 bias：

$$ (3\times3\times64+1)\times128=73856 $$

卷积输出尺寸也常考：

输入大小 $H\times W$，卷积核大小 $K$，padding 为 $P$，stride 为 $S$，则输出高宽：

$$ H_{out}=\left\lfloor\frac{H+2P-K}{S}\right\rfloor+1 $$

$$ W_{out}=\left\lfloor\frac{W+2P-K}{S}\right\rfloor+1 $$

输出通道数等于卷积核个数 $C_{out}$。

池化层：

通常没有可学习参数。
主要改变特征图尺寸。
Max pooling 取局部最大值，Average pooling 取局部平均值。

九、前向传播

前向传播就是从输入开始，逐层计算每一层的线性变换和激活输出。

单层：

$$ z^{(l)}=W^{(l)}a^{(l-1)}+b^{(l)} $$

$$ a^{(l)}=f(z^{(l)}) $$

其中：

$a^{(0)}=x$。
$W^{(l)}$ 是第 $l$ 层权重。
$b^{(l)}$ 是第 $l$ 层偏置。
$z^{(l)}$ 是激活前输入。
$a^{(l)}$ 是激活后输出。

完整流程：

输入样本 $x$。
第一层计算 $z^{(1)},a^{(1)}$。
第二层计算 $z^{(2)},a^{(2)}$。
继续直到输出层。
得到预测值 $\hat{y}$。
用损失函数计算 $L(\hat{y},y)$。

前向传播负责算预测和损失，反向传播负责算梯度。

十、反向传播 BackPropagation

反向传播是神经网络训练的核心。

它解决的问题：

如何高效计算损失函数对每个参数的梯度。

核心工具：链式法则。

如果：

$$ L=L(a),\quad a=f(z),\quad z=wx+b $$

则：

$$ \frac{\partial L}{\partial w} =\frac{\partial L}{\partial a} \frac{\partial a}{\partial z} \frac{\partial z}{\partial w} $$

这就是“误差从后往前传”的本质。

1. 输出层误差项

定义误差项：

$$ \delta^{(l)}=\frac{\partial L}{\partial z^{(l)}} $$

若输出层使用均方误差：

$$ L=\frac{1}{2}(\hat{y}-y)^2 $$

且：

$$ \hat{y}=a^{(L)}=f(z^{(L)}) $$

则输出层误差项：

$$ \delta^{(L)} =\frac{\partial L}{\partial z^{(L)}} =(a^{(L)}-y)f'(z^{(L)}) $$

如果输出层是 Sigmoid：

$$ f'(z)=a(1-a) $$

所以：

$$ \delta^{(L)}=(a^{(L)}-y)a^{(L)}(1-a^{(L)}) $$

2. 隐藏层误差项

隐藏层的误差来自后一层。

$$ \delta^{(l)} =((W^{(l+1)})^T\delta^{(l+1)})\odot f'(z^{(l)}) $$

其中 $\odot$ 表示逐元素相乘。

理解：

后一层误差通过权重传回当前层。
再乘以当前层激活函数的导数。

3. 参数梯度

有了误差项后，梯度很简单。

权重梯度：

$$ \frac{\partial L}{\partial W^{(l)}}=\delta^{(l)}(a^{(l-1)})^T $$

偏置梯度：

$$ \frac{\partial L}{\partial b^{(l)}}=\delta^{(l)} $$

单个权重：

$$ \frac{\partial L}{\partial w_{ij}^{(l)}}=\delta_i^{(l)}a_j^{(l-1)} $$

意思是：

某条边的梯度 = 终点神经元误差项 × 起点神经元输出。

4. 参数更新

梯度下降更新：

$$ W^{(l)}\leftarrow W^{(l)}-\eta \frac{\partial L}{\partial W^{(l)}} $$

$$ b^{(l)}\leftarrow b^{(l)}-\eta \frac{\partial L}{\partial b^{(l)}} $$

其中 $\eta$ 是学习率。

学习率：

太大：可能震荡或发散。
太小：收敛很慢。

十一、梯度计算例题模板

例 1：简单链式法则

设：

$$ f(x,y,z)=(x+y)z $$

令：

$$ q=x+y $$

则：

$$ f=qz $$

反向传播：

$$ \frac{\partial f}{\partial q}=z,\quad \frac{\partial f}{\partial z}=q $$

$$ \frac{\partial q}{\partial x}=1,\quad \frac{\partial q}{\partial y}=1 $$

所以：

$$ \frac{\partial f}{\partial x} =\frac{\partial f}{\partial q}\frac{\partial q}{\partial x} =z $$

$$ \frac{\partial f}{\partial y} =\frac{\partial f}{\partial q}\frac{\partial q}{\partial y} =z $$

$$ \frac{\partial f}{\partial z}=q=x+y $$

若 $x=-2,y=5,z=-4$，则：

$$ q=3,\quad f=-12 $$

$$ \frac{\partial f}{\partial x}=-4,\quad \frac{\partial f}{\partial y}=-4,\quad \frac{\partial f}{\partial z}=3 $$

例 2：单个 Sigmoid 神经元

设：

$$ z=wx+b,\quad a=\sigma(z),\quad L=\frac{1}{2}(a-y)^2 $$

要求 $\frac{\partial L}{\partial w}$。

按链式法则：

$$ \frac{\partial L}{\partial w} =\frac{\partial L}{\partial a} \frac{\partial a}{\partial z} \frac{\partial z}{\partial w} $$

三项分别为：

$$ \frac{\partial L}{\partial a}=a-y $$

$$ \frac{\partial a}{\partial z}=a(1-a) $$

$$ \frac{\partial z}{\partial w}=x $$

所以：

$$ \frac{\partial L}{\partial w}=(a-y)a(1-a)x $$

同理：

$$ \frac{\partial L}{\partial b}=(a-y)a(1-a) $$

必须会写出这类链式法则。

例 3：两层网络反向传播

两层网络：

$$ z^{(1)}=W^{(1)}x+b^{(1)},\quad a^{(1)}=f(z^{(1)}) $$

$$ z^{(2)}=W^{(2)}a^{(1)}+b^{(2)},\quad a^{(2)}=\hat{y} $$

输出层：

$$ \delta^{(2)}=(a^{(2)}-y)\odot f'(z^{(2)}) $$

隐藏层：

$$ \delta^{(1)}=((W^{(2)})^T\delta^{(2)})\odot f'(z^{(1)}) $$

梯度：

$$ \frac{\partial L}{\partial W^{(2)}}=\delta^{(2)}(a^{(1)})^T $$

$$ \frac{\partial L}{\partial W^{(1)}}=\delta^{(1)}x^T $$

这就是 BP 计算题的核心模板。

十二、优化器了解即可

优化器负责根据梯度更新参数。

最基本的梯度下降：

$$ \theta\leftarrow \theta-\eta\nabla_\theta L $$

常见类型：

优化器	核心思想	掌握程度
Batch GD	用全体样本梯度更新	了解
SGD	每次用单个样本或小批量近似梯度	了解
Mini-batch SGD	用一个 batch 的平均梯度更新	常用
Momentum	引入动量，减少震荡	了解
AdaGrad	每个参数自适应学习率	了解
Adam	一阶矩 + 二阶矩估计，自适应更新	了解
Muon	对 2D 权重矩阵的动量做正交化	新技术，了解即可

Mini-batch SGD：

$$ \theta\leftarrow \theta-\eta\frac{1}{b}\sum_{i=1}^{b}\nabla_\theta L_i $$

Adam 直观理解：

记录梯度的移动平均，类似动量。
记录梯度平方的移动平均，自动调节学习率。
实践中非常常用。

十三、标准化了解即可

标准化的作用：

加快模型收敛。
稳定每层输入分布。
缓解梯度消失和梯度爆炸。
让激活值落在较合理范围。

基本形式：

$$ \hat{x}=\frac{x-\mu}{\sqrt{\sigma^2+\epsilon}} $$

再进行缩放和平移：

$$ y=\gamma \hat{x}+\beta $$

其中 $\gamma,\beta$ 是可学习参数，用来恢复表达能力。

常见标准化：

方法	归一化范围	常见用途
Batch Normalization	同一 batch 内同一维度	CNN
Layer Normalization	单个样本所有特征维度	RNN、Transformer
Instance Normalization	单张图像每个通道	图像生成
RMSNorm	不减均值，只按均方根缩放	大语言模型

BN 和 LN 区别：

BN：跨 batch 统计，对同一特征维度求均值方差。
LN：对单个样本内部所有特征求均值方差。

十四、经典网络架构了解即可

架构	核心贡献
LeNet	早期 CNN，用卷积、池化、全连接，使用 BP 训练
AlexNet	ReLU、Dropout、数据增强，推动深度学习在 ImageNet 成功
VGG	使用大量 $3\times3$ 卷积，结构简单但很深
GoogLeNet/Inception	多分支结构，使用 $1\times1$ 卷积降维
ResNet	残差连接，缓解深层网络训练退化
Transformer	Self-Attention，任意位置直接建模关系
ViT	把图像切成 patch，用 Transformer 做视觉任务

ResNet 重点思想：

$$ H(x)=F(x)+x $$

其中 $x$ 是恒等映射，$F(x)$ 是残差映射。

残差连接的作用：

让信息和梯度更容易跨层传播。
缓解梯度消失。
使深层网络更容易优化。

CNN 与 Transformer 对比：

CNN：局部连接 + 参数共享 + 层次化特征。
Transformer：Self-Attention，任意位置之间直接建立联系。

十五、后续新技术了解即可

课件后面提到的一些新技术，只需知道大概思想：

技术	核心思想
特征可视化	可视化层激活、权重或最大激活样本，理解网络学到什么
Grad-CAM	用梯度定位模型关注的图像区域
Mamba	基于状态空间模型，适合长序列建模，强调线性时间复杂度
Vision Mamba	把 Mamba 思想用于视觉表示学习
KAN	激活函数在边上且可学习，来自 Kolmogorov-Arnold 表示思想
MoE	多个专家网络，token 只激活少数专家，扩大参数量但控制计算量
Hyper-Connections/mHC	多条残差流和流形约束，增强深层网络信息传播

这些内容了解即可，不需要作为计算重点。

十六、易错点

没有激活函数，多层神经网络仍等价于线性模型。
Sigmoid 导数必须会：$\sigma'(x)=\sigma(x)(1-\sigma(x))$。
全连接层参数量要加 bias：$(n_{in}+1)n_{out}$。
CNN 参数量与输入图像高宽无关，只与卷积核大小、输入通道、输出通道有关。
池化层通常没有可学习参数。
CNN 适合图像的根本原因是局部连接、参数共享和层次化特征。
前向传播算输出和损失，反向传播算梯度。
反向传播本质是链式法则。
权重梯度 = 终点误差项 × 起点输出。
学习率太大可能发散，太小收敛慢。
BP 虽然课堂可能没有细讲，但它是神经网络核心，必须会计算。

十七、考试中可以这样写

神经网络由大量神经元组成，每个神经元先对输入进行加权求和，再经过激活函数得到输出。MP 神经元是最早的神经元数学模型，包含输入、权重、偏置、加权求和和激活函数。单层感知机只能处理线性可分问题，多层神经网络通过隐藏层和非线性激活函数学习复杂特征表示，从而具备更强的表达能力。

构造神经网络时，需要根据任务确定输入、输出、网络层、激活函数和损失函数。全连接层参数量为 $(n_{in}+1)n_{out}$，多层网络参数量为各层参数量之和。CNN 更适合图像任务，因为图像具有局部性和平移不变性，CNN 通过局部连接和参数共享显著减少参数量，并能学习层次化图像特征。卷积层参数量为 $(K_hK_wC_{in}+1)C_{out}$。

神经网络训练包括前向传播和反向传播。前向传播逐层计算输出并得到损失；反向传播利用链式法则从输出层向前逐层计算损失对参数的梯度，再用梯度下降或 Adam 等优化器更新参数。反向传播的核心是误差项 $\delta$，权重梯度等于当前层误差项乘以上一层输出。

十八、速记版

神经元：加权求和 + 偏置 + 激活函数。
MP 模型：早期阈值神经元，可表示简单逻辑。
多层网络：隐藏层学习特征，解决非线性问题。
激活函数：引入非线性；Sigmoid、tanh、ReLU 要会区分。
Sigmoid 导数：$\sigma'(x)=\sigma(x)(1-\sigma(x))$。
全连接参数：$(n_{in}+1)n_{out}$。
CNN 适合图像：局部连接、参数共享、层次化特征。
CNN 参数：$(K_hK_wC_{in}+1)C_{out}$。
前向传播：逐层算输出和损失。
反向传播：链式法则逐层算梯度。
权重梯度：误差项 $\delta$ × 上一层输出。
优化器、标准化、经典架构、新技术了解即可。

机器学习导论复习

1.绪论

归纳偏置：

归纳偏置和泛化的关系

奥卡姆剃刀

考试中可以这样写

生成式和判别式模型

2.模型评估与选择

统计学习方法三要素

损失与风险

基本概念

评估方法

训练集、验证集与测试集

性能度量

回归任务

分类任务

P-R、ROC 与 AUC

宏平均与微平均

代价敏感评估

比较检验

偏差-方差分解

偏差-方差权衡

大模型评估的特点

速记

3. 线性模型

线性可分性

感知机

线性模型的一般形式

线性回归

一元线性回归闭式解

多元线性回归

线性模型的变化

广义线性模型

对数几率回归

Logistic 函数

对数几率

求解方法

多分类学习

纠错输出码

类别不平衡

公式推导与细节

1. 线性可分公式为什么是超平面

2. 感知机分类公式的推导

3. 线性模型向量形式的推导

4. 一元线性回归最小二乘推导

5. 多元线性回归闭式解推导

6. 对数线性回归与广义线性模型推导

7. Logistic 函数由对数几率推导

8. 对数几率回归的极大似然推导

9. 类别不平衡阈值调整推导

考试中可以这样写

速记

4. 决策树

决策树模型

决策树如何构造

决策树如何用于判断

停止条件

三类算法核心指标

ID3：信息增益

1. 信息熵

2. 信息增益公式推导

3. 信息增益手算步骤

C4.5：增益率

1. 为什么需要增益率

2. 固有值 IV

3. 增益率公式推导

CART：基尼指数

1. 基尼值的含义

2. 属性划分下的基尼指数

3. CART 的特点

三个指标对比

奥卡姆剃刀与决策树

为什么要剪枝

剪枝有什么作用

剪枝的基本方式

1. 预剪枝

2. 后剪枝

3. 预剪枝与后剪枝对比

连续值处理（了解）

缺失值处理（了解）