复习文档：机器学习（基于周志华《机器学习》）

第 2 章 模型评估与选择

2.1 经验误差与过拟合

  • 错误率（Error Rate）：分类错误的样本数占总样本数的比例
  • 精度（Accuracy）：1 - 错误率
  • 训练误差（Training Error）/ 经验误差（Empirical Error）：在训练集上的误差
  • 泛化误差（Generalization Error）：在新样本上的误差
  • 过拟合（Overfitting）：把训练样本的自身特点当作普遍规律，泛化能力下降
  • 欠拟合（Underfitting）：对训练样本的一般性质尚未学好

2.2 评估方法

2.2.1 留出法（Hold-out）

将数据集 ( D ) 划分为两个互斥集合：训练集 ( S ) 和测试集 ( T )。

  • 分层采样（Stratified Sampling）：保持训练/测试集中类别比例与原始数据集一致
  • 单次留出不够稳定，一般需多次随机划分、重复评估取平均

2.2.2 交叉验证法（Cross Validation）

将 ( D ) 划分为 ( k ) 个大小相似的互斥子集，每次用 ( k-1 ) 个子集训练、1 个子集测试，共 ( k ) 次训练/测试，取均值。

  • ( k )-折交叉验证（( k )-fold Cross Validation）
  • 留一法（Leave-One-Out, LOO）：( k = m )（样本数），最准确但计算开销最大

2.2.3 自助法（Bootstrapping）

以自助采样（Bootstrap Sampling）为基础：从 ( m ) 个样本中有放回地随机抽取 ( m ) 次，形成训练集 ( D’ )。

  • 一个样本在 ( m ) 次采样中不被抽中的概率：
    [
    \lim_{m \to \infty} \left(1 - \frac{1}{m}\right)^m = \frac{1}{e} \approx 0.368
    ]
  • 约 36.8% 的样本未出现在 ( D’ ) 中 → 用作测试集
  • 适合数据集较小、难以有效划分训练/测试集的情况

2.2.4 调参与最终模型

  • 训练集 → 训练；验证集 → 调参；测试集 → 评估泛化性能
  • 调参完成后，用全部数据重新训练得到最终模型

2.3 性能度量

2.3.1 错误率与精度

[
E(f; D) = \frac{1}{m}\sum_{i=1}^{m} \mathbb{I}(f(x_i) \neq y_i), \quad
\text{acc}(f; D) = 1 - E(f; D)
]

2.3.2 查准率、查全率与 F1

真实\预测 正 负
正 TP FN（漏报）
负 FP（误报） TN
  • 查准率（Precision）：( P = \frac{TP}{TP + FP} ) — 预测为正的样本中真正为正的比例
  • 查全率（Recall）：( R = \frac{TP}{TP + FN} ) — 真实正例中被正确找出的比例
  • F1 度量：( F1 = \frac{2 \times P \times R}{P + R} )（调和平均）

P-R 曲线：以查准率为纵轴、查全率为横轴。曲线下的面积越大性能越好；若一条曲线完全”包住”另一条，则前者性能更优。

2.3.3 ROC 与 AUC

  • ROC 曲线：纵轴 TPR（真正例率=Recall），横轴 FPR（假正例率 = FP/(TN+FP)）
  • AUC：ROC 曲线下的面积，衡量模型整体排序质量

[
\text{AUC} = \frac{1}{2} \sum_{i=1}^{m-1} (x_{i+1} - x_i)(y_i + y_{i+1})
]

2.4 课后习题精讲

习题 2.1：留出法划分方式估算

题目： 数据集包含 1000 个样本，500 正例 + 500 反例，70% 训练集 + 30% 测试集用留出法评估，估算共有多少种划分方式。

解答：

留出法应使用分层采样保持类别比例。因此：

正例 反例 合计
训练集（70%） 350 350 700
测试集（30%） 150 150 300

正例选法：从 500 个中选 350 个进入训练 → (C_{500}^{350}) 种
反例选法：从 500 个中选 350 个进入训练 → (C_{500}^{350}) 种

[
\boxed{\text{划分方式总数} = C_{500}^{350} \times C_{500}^{350} = \left(C_{500}^{350}\right)^2 = \left(C_{500}^{150}\right)^2}
]

💡 这是一个天文数字（约 (10^{282}) 量级），说明了留出法划分的多样性。这也解释了为什么需要多次随机划分评估取平均。

第 4 章 决策树

4.1 基本流程

决策树基于分而治之策略，递归地选择最优划分属性，生成一棵树。终止条件：

  1. 当前结点包含的样本全属于同一类别 → 标记为该类叶结点
  2. 当前属性集为空或所有样本在所有属性上取值相同 → 标记为叶结点，类别为样本中最多的类
  3. 当前结点样本集为空 → 标记为叶结点，类别为父结点样本中最多的类

4.2 划分选择

4.2.1 信息熵与信息增益（ID3 算法）

信息熵（Information Entropy）： 度量样本集合纯度最常用的指标。熵值越小，样本集合纯度越高。

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

  • ( p_k )：第 ( k ) 类样本在集合 ( D ) 中所占比例
  • 当 ( \text{Ent}(D) = 0 ) 时，样本完全属于同一类（最纯）
  • 当各类均匀分布时，熵最大 = ( \log_2 |\mathcal{Y}| )

🍉 直观理解：全好瓜→熵为 0，好坏各半→熵最大。

信息增益（Information Gain）： 使用属性 ( a ) 划分后，信息熵减少的程度。增益越大，纯度提升越大。

[
\text{Gain}(D, a) = \text{Ent}(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} \cdot \text{Ent}(D^v)
]

  • ( V )：属性 ( a ) 的取值个数，( D^v )：属性 ( a ) 取第 ( v ) 个值的样本子集

对应算法：ID3

  • 每次选信息增益最大的属性划分
  • ⚠️ 缺点：偏好可取值数目较多的属性（如”编号”——每个样本一个值，子集纯度为 1，信息增益极大但毫无泛化能力）

4.2.2 增益率（C4.5 算法）

增益率（Gain Ratio）： 在信息增益基础上除以属性的**固有值 (Intrinsic Value)**，惩罚取值多的属性。

[
\text{Gain_ratio}(D, a) = \frac{\text{Gain}(D, a)}{\text{IV}(a)}
]

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

  • IV(a) 本质是属性 ( a ) 的”信息熵”——取值越多，IV 越大，增益率被压低

对应算法：C4.5

  • ⚠️ 增益率会反向偏好可取值数目较少的属性
  • 启发式策略：先从候选属性中找信息增益高于平均水平的，再从中选增益率最高的

4.2.3 基尼指数（CART 算法）

基尼值（Gini）： 反映”随机抽两个样本，类别不一致”的概率。值越小，纯度越高。

[
\text{Gini}(D) = \sum_{k=1}^{|\mathcal{Y}|} \sum_{k’ \neq k} p_k p_{k’} = 1 - \sum_{k=1}^{|\mathcal{Y}|} p_k^2
]

属性 ( a ) 的基尼指数（划分后加权和）：

[
\text{Gini_index}(D, a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} \cdot \text{Gini}(D^v)
]

对应算法：CART

  • 每次选基尼指数最小的属性划分
  • CART 是二叉树（每次只二分），ID3/C4.5 是多叉树

4.2.4 划分准则对比

维度 信息增益 增益率 基尼指数
所属算法 ID3 C4.5 CART
选择标准 选最大 先 > 平均增益，再选最大增益率 选最小
偏好 偏好取值多的属性 偏好取值少的属性（启发式缓解） 无显著偏好
树结构 多叉树 多叉树 二叉树
公式基础 信息熵之差 信息增益 ÷ 固有值 二类不一致概率
一句话 不确定性减少的量 单位固有值带来的增益 随机两样本类别不同的概率

4.3 剪枝处理 — 解决过拟合

4.3.0 为什么需要剪枝？

决策树在生成过程中，为了尽可能正确分类训练样本，结点划分不断重复，导致分支过多。此时决策树把训练集自身的某些非通用特点也学了进去——这就是过拟合（Overfitting）。

🔑 剪枝（Pruning） 是决策树对付过拟合的主要手段。

两种基本策略：预剪枝（边生成边剪）和后剪枝（生成完再剪），都用验证集评估泛化性能。

4.3.1 预剪枝（Pre-pruning）

定义： 在决策树生成过程中，对每个结点在划分前先评估——若当前划分不能带来泛化性能的提升，则停止划分，将当前结点标记为叶结点。

核心思想： 贪心——“不好就停，别往下分了”。

🍉 西瓜书实例（表 4.2）

基于信息增益准则，训练集 {1,2,3,6,7,10,14,15,16,17}，验证集 {4,5,8,9,11,12,13}。类别为”好瓜”/“坏瓜”。

步骤：

步骤 操作 验证精度 决策
0 根结点不划分，全猜”好瓜” 42.9%（3/7 正确） 基线
1 用**”脐部”**划分根结点 **71.4%**（5/7） ✅ 精度↑，允许划分
2 对结点②（脐部=凹陷）用**”色泽”**划分 57.1%（4/7） ❌ 精度↓，禁止划分
3 对结点③（脐部=稍凹）用**”根蒂”**划分 71.4%（5/7） ❌ 精度不变，同样禁止
4 结点④（脐部=平坦）全坏瓜，已纯 — 不再划分

结果： 仅有一层划分的”决策树桩“（Decision Stump），验证精度 **71.4%**。

4.3.2 后剪枝（Post-pruning）

定义： 先生成一棵完整的决策树，然后自底向上对每一个非叶结点逐一考察——若将该结点替换为叶结点（剪掉其子树）能提升验证集精度，则执行剪枝。

核心思想： 全局视角——“先生成大杂烩，再慢慢剔除没用的”。

🍉 西瓜书实例（续）

先生成完整决策树（深度多层），验证精度仅 **42.9%**（严重过拟合！）。

自底向上依次考察：

步骤 考察结点 操作 验证精度变化 决策
1 结点⑥（纹理=稍糊→坏瓜，最底层） 剪为叶结点（坏瓜） 42.9% → 57.1% ✅ 剪！
2 结点⑤（纹理=清晰，色泽=？下一层） 剪为叶结点（好瓜） 57.1% 不变 剪（奥卡姆剃刀）
3 结点②（纹理=清晰） 剪为叶结点（好瓜） 57.1% → 71.4% ✅ 剪！
4 结点③（纹理=稍糊） 剪为叶结点（坏瓜） 71.4% → 57.1% ❌ 精度↓，不剪
5 结点①（根结点） 剪为叶结点（好瓜） 71.4% → 42.9% ❌ 精度↓，不剪

结果： 保留比预剪枝更多的分支，验证精度 **71.4%**。

4.3.3 预剪枝 vs 后剪枝 —— 核心区别

一句话： 预剪枝 = “边建边砍，贪心但快”；后剪枝 = “建完再修，全面但慢”。

比较维度 预剪枝 后剪枝
时机 决策树生成过程中 决策树完全生成后
方向 自顶向下 自底向上
过拟合风险 降低 ✅ 降低 ✅
欠拟合风险 增加 ⚠️ 基本不变 ✅
训练时间 减少 ✅（不生成被禁分支） 增加 ⚠️（需生成完整树再逐一考察）
泛化性能 一般（贪心短视） 通常更优 ✅（全局视角）
保留分支数 较少 较多
⚡ 为什么预剪枝有欠拟合风险？

预剪枝基于贪心本质——某个划分在当前看不能提升（甚至暂时降低）验证精度，就禁止了。但有可能该划分基础上的后续划分能带来显著提升！预剪枝一刀切，把这些”现在看似没用，未来有大用”的分支扼杀了。

类比：预剪枝像下棋只看一步，后剪枝像下棋看完全局再做判断。

4.4 连续与缺失值处理

4.4.1 连续属性处理 — 二分法离散化

核心问题： 连续属性（如密度=0.697、含糖率=0.124）的可取值数目无限，无法直接用离散属性的方式枚举每个取值进行划分。

解决方案：C4.5 的二分法（Bi-partition）

步骤：

① 排序取值： 将连续属性 ( a ) 在样本集 ( D ) 上的 ( n ) 个不同取值按升序排列：
[
{a_1, a_2, \dots, a_n}
]

② 生成候选划分点： 取每相邻两个取值的中位点作为候选，共 ( n-1 ) 个：
[
T_a = \left{\frac{a_i + a_{i+1}}{2} ;\middle|; 1 \le i \le n-1\right}
]

为什么取中位点？因为只要落在相邻两值之间，划分结果都一样，取中点最自然。

③ 逐一计算信息增益： 对每个候选划分点 ( t )，二分为 ( D_t^- (\le t) ) 和 ( D_t^+ (> t) )，计算增益，选最大者：
[
\text{Gain}(D, a) = \max_{t \in T_a} \text{Gain}(D, a, t)
]
[
\text{Gain}(D, a, t) = \text{Ent}(D) - \sum_{\lambda \in {-,+}} \frac{|D_t^\lambda|}{|D|} \cdot \text{Ent}(D_t^\lambda)
]

④ 确定最优划分点： 取使信息增益最大的 ( t ) 作为该连续属性的划分点。

🍉 西瓜书实例
属性 候选点数 最优划分点 最大信息增益
密度 16 个 0.381 0.262
含糖率 16 个 0.126 0.349
⚠️ 与离散属性的关键区别

若当前结点划分属性为连续属性，该属性仍可作为其后代结点的划分属性！

  • 父结点用 “密度 ≤ 0.381” → 左子结点仍可再用 “密度 ≤ 0.294”
  • 离散属性则不同——用过的属性不能再用于后代划分（因为取值已确定）

4.4.2 缺失值处理 — 两个核心问题

现实困境： 实际数据常有缺失值（如测糖度时仪器故障），直接丢弃 → 信息浪费。需要解决两个问题：

问题一：如何在属性值缺失的情况下选择划分属性？

引入样本权重 ( w_x )（根结点初始化为 1），定义三个参数：

参数 公式 通俗含义
( \rho ) ( \frac{\sum_{x \in \tilde{D}} w_x}{\sum_{x \in D} w_x} ) “完整样本占多大比例”
( \tilde{p}_k ) ( \frac{\sum_{x \in \tilde{D}k} w_x}{\sum{x \in \tilde{D}} w_x} ) 完整样本中第 k 类占多少
( \tilde{r}_v ) ( \frac{\sum_{x \in \tilde{D}^v} w_x}{\sum_{x \in \tilde{D}} w_x} ) 完整样本中，属性取值为 ( a^v ) 的占多少

符号说明：( D ) = 全体样本集，( \tilde{D} ) = 在属性 ( a ) 上无缺失值的样本子集

推广的信息增益公式：
[
\text{Gain}(D, a) = \rho \times \text{Gain}(\tilde{D}, a) = \rho \times \left(\text{Ent}(\tilde{D}) - \sum_{v=1}^{V} \tilde{r}_v \cdot \text{Ent}(\tilde{D}^v)\right)
]

🔑 核心思想：只用完整样本子集 ( \tilde{D} ) 算信息增益，然后乘以完整样本占比 ( \rho ) 作为”折扣”——缺失值越多，( \rho ) 越小，增益被压得越低。

🍉 西瓜数据集 2.0 缺失版本示例：

17 个样本中部分含缺失值（如样例 #8 和 #10 在”纹理”上缺失，样例 #12 在”色泽”上缺失）。

根结点各属性推广信息增益：

  • 纹理 = 0.381（最大 ✅，选为根结点划分属性）
  • 色泽 = 0.252
  • 根蒂 = 0.171
  • …
问题二：若某样本在该划分属性上值缺失，该把它分到哪个分支？

策略： 取值未知 → 同时划入所有子结点，但在各子结点中调整权重。

  • 取值已知：划入对应子结点，权重保持 ( w_x )
  • 取值未知：划入所有子结点，在每个子结点中的权重调整为：
    [
    w_{x, v} = \tilde{r}_v \cdot w_x
    ]
    即按各分支的样本比例”分配”这个缺失样本的权重。

🍉 示例： 样例 #8 的”纹理”缺失，而完整样本中纹理各取值比例为：清晰 7/15、稍糊 5/15、模糊 3/15。于是样例 #8 以权重 7/15 进入”清晰”分支，5/15 进入”稍糊”分支，3/15 进入”模糊”分支。

4.4.3 本节总结

问题 核心方法 关键技巧
连续属性 二分法离散化 n 个取值 → n-1 个中位候选点，选最大信息增益
连续属性复用 后代可继续使用 不同于离散属性的一次性使用
缺失值—选属性 推广信息增益 仅用完整子集计算 × 完整占比 ρ
缺失值—分样本 按概率同时入所有分支 权重按 ( \tilde{r}_v ) 比例分配

4.5 多变量决策树

4.5.1 单变量决策树的局限

前面讲的决策树，每个非叶结点只对一个属性进行测试（如”纹理=？”、”密度≤0.381？”），这叫单变量决策树（Univariate Decision Tree）。

它的分类边界是轴平行（Axis-Parallel）的——只能画出与坐标轴平行的横平竖直的线：

1
2
3
4
5
graph TD
    subgraph 轴平行边界
        A[单变量决策树] --> B[只能画横平竖直的线]
        B --> C[真实斜边界需要很多阶梯才能逼近]
    end
坐标系 含义
横轴 密度
纵轴 含糖率
● 好瓜
○ 坏瓜
真实边界 一条斜线 ↗
单变量逼近 用阶梯状折线勉强逼近

单变量决策树只能用阶梯状折线去逼近这条斜线，导致：

  • 分支多、树复杂
  • 逼近效率低
  • 对倾斜边界的表达能力差

4.5.2 多变量决策树的定义

多变量决策树（Multivariate Decision Tree） 的每个非叶结点不再是测试单个属性，而是测试属性的线性组合：

[
\sum_{i=1}^{d} w_i a_i \le t
]

即每个结点本身就是一个线性分类器，权重 ( w_i ) 和阈值 ( t ) 从该结点的样本集和属性集上学得。

🔑 一句话： 单变量决策树 = 每次只看一个属性（轴平行边界）；多变量决策树 = 每次看多个属性的线性组合（斜的边界）。

斜决策树（Oblique Decision Tree） 是多变量决策树的典型代表——通过在每个结点建立线性分类器，产生倾斜的划分边界。

4.5.3 🍉 西瓜数据集 3.0α 举例

以密度和含糖率两个连续属性来判断好瓜/坏瓜：

编号 密度 含糖率 好瓜
1 0.697 0.460 是
2 0.774 0.376 是
… … … …
9 0.666 0.091 否
17 0.719 0.103 否

单变量 vs 多变量 分类边界对比：

对比维度 单变量决策树 多变量决策树
边界形状 轴平行阶梯状折线 任意方向的斜线
图 4.11 场景 好瓜区被 ╔══╗ 形阶梯包围，需多段逼近 —
图 4.13/4.14 场景 — 两条斜线干净利落地分开好/坏瓜
分支数 多段阶梯 仅 2 个线性分类器
复杂度 树深、分支多 树浅、简洁

多变量决策树学到的分类器：

结点 线性分类器 含义
根结点 (-0.800 \times \text{密度} - 0.044 \times \text{含糖率} \le -0.313)？ 一条斜线划分
内部结点 (-0.365 \times \text{密度} + 0.366 \times \text{含糖率} \le -0.158)？ 另一条斜线 
1
2
3
4
5
6
7
8
graph LR
    subgraph 单变量
        A1[需多段阶梯] --> A2[树复杂]
    end
    subgraph 多变量
        B1[两条斜线] --> B2[模型简洁]
    end
    A2 -->|不如| B2

对比：单变量需要多段阶梯，多变量两条斜线就完成了——模型更简洁，表达能力更强。

4.5.4 单变量 vs 多变量 对比

维度 单变量决策树 多变量决策树
结点测试 单个属性（如”纹理=？”） 属性线性组合（(\sum w_i a_i \le t)）
分类边界 轴平行（横平竖直） 斜的（任意方向）
边界形状 阶梯状折线段 直线/超平面
树复杂度 复杂边界时需要很多分支 用更少分支逼近复杂边界
可解释性 ✅ 强（每个分支对应一个属性） ⚠️ 弱（权重不易直观理解）
训练开销 小 大（需学习权重 (w_i)）
代表性算法 ID3, C4.5, CART OC1, 感知机树

4.5.5 进一步扩展

多变量决策树还可以在结点嵌入更复杂的模型：

  • 感知机树（Perceptron Tree）：叶结点上训练感知机而非直接标记类别
  • 混合决策树：结点嵌入多层神经网络，形成神经网络与决策树的混合模型

📌 本质思想：决策树的每个结点不一定只能是”if 某个属性 ≤ 某值”，可以是任意形式的分类器。

4.6 课后习题精讲

习题 4.2：试析使用”最小训练误差”作为决策树划分选择准则的缺陷

题目来源： 周志华《机器学习》第四章课后习题 4.2

一、什么是”最小训练误差”准则？

以训练误差（即分类错误率）最小作为选择划分属性的标准——每步选那个让划分后训练集错分样本数最少的属性。

二、核心缺陷
缺陷 1：严重过拟合，泛化能力极差 ⚠️⚠️⚠️

这是最致命的缺陷。

训练误差最小 ≠ 泛化能力最强。机器学习的目标不是”背下训练集”，而是学到能适用于新样本的规律。

如果以最小训练误差为目标，决策树会：

  • 不断细分直到每个叶结点只含一个样本（训练误差=0）
  • 把所有噪声和偶然特性都学进去
  • 对新样本几乎毫无预测能力
1
2
训练误差 → 0
泛化误差 → 爆炸 💥
缺陷 2：与纯度准则的本质差异

信息增益/增益率/基尼指数基于纯度（Purity）而非直接数错误个数：

准则 衡量什么 为什么更好
信息增益 不确定性减少量 考虑了整体分布，而非逐样本计数
基尼指数 随机抽两样本类别不同的概率 统计视角，天然有平滑效果
训练误差 直接数错分个数 过于粗糙，只看表面结果

纯度准则有隐式正则化效果——即使某个划分能减少错误，如果纯度提升不大，也不会被选中。而训练误差准则没有这种约束。

缺陷 3：对样本分布的敏感性太差

考虑以下场景（二分类，共 10 个样本）：

1
2
3
4
5
6
7
8
9
10
11
划分前：6 个好瓜，4 个坏瓜 → 按多数猜"好瓜"，训练误差 = 4/10

属性A 划分后：
  左子集：4 个好瓜，2 个坏瓜 → 猜"好瓜"，错 2
  右子集：2 个好瓜，2 个坏瓜 → 瞎猜，错 2（随便猜哪个都错一半）
  训练误差 = (2+2)/10 = 4/10 → "没改善"，不选

属性B 划分后：
  左子集：5 个好瓜，3 个坏瓜 → 猜"好瓜"，错 3
  右子集：1 个好瓜，1 个坏瓜 → 随便猜，错 1
  训练误差 = (3+1)/10 = 4/10 → 也没"改善"

两个属性在训练误差上表现一样，但属性 A 明显更优（左子集纯度更高）。训练误差只看最终分类对错，完全忽略纯度的连续变化。

缺陷 4：缺乏”全局优化”的视角

决策树的划分是贪心的——每次选当前最优。信息增益至少保证了每一步的”纯度提升”，但训练误差准则在每一步的区分度都很弱（很多属性划分后错误数可能一样），导致选择随机性大，最终树的结构不稳定。

三、总结一句话

“最小训练误差”会让决策树变成”背答案的考生”——训练集上一字不差，换个新题就不会做。

维度 信息增益/增益率/基尼 最小训练误差
优化目标 纯度提升（间接） 错误数（直接）
过拟合风险 中等（还需剪枝） 极高
对噪声敏感度 较低 极高
区分能力 连续值，区分度高 粗粒度，很多属性”打平”
泛化能力 较好 差

💡 延伸思考： 为什么剪枝不直接用训练误差，而要用验证集精度？正是因为训练误差低不代表泛化能力强——验证集才能真正反映模型对新样本的表现。

习题 4.4：试将 4.4.2 节对缺失值的处理机制推广到基尼指数的计算中去

题目来源： 周志华《机器学习》第四章课后习题 4.4（注：不同版本题号可能有差异）

一、回顾：4.4.2 节对缺失值的两种处理

在 4.4.2 节中，C4.5 针对缺失值引入了一套基于样本权重的机制，解决两个问题：

问题 方法
选划分属性 推广信息增益：( \text{Gain}(D, a) = \rho \times \text{Gain}(\tilde{D}, a) )
分配缺失样本 同时划入所有子结点，权重按 ( \tilde{r}_v ) 比例调整

其中三个核心参数：

[
\rho = \frac{\sum_{x \in \tilde{D}} w_x}{\sum_{x \in D} w_x}, \quad
\tilde{p}k = \frac{\sum{x \in \tilde{D}k} w_x}{\sum{x \in \tilde{D}} w_x}, \quad
\tilde{r}v = \frac{\sum{x \in \tilde{D}^v} w_x}{\sum_{x \in \tilde{D}} w_x}
]

二、推广到基尼指数 —— 完整推导

目标： 将这套机制从”信息增益 + 信息熵”平移到”基尼指数 + 基尼值”上。

原始基尼指数（无缺失值）：

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

[
\text{Gini_index}(D, a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} \cdot \text{Gini}(D^v)
]

推广步骤：

步骤 ①：用完整子集 ( \tilde{D} ) 定义基尼值

在属性 ( a ) 上无缺失的样本子集 ( \tilde{D} ) 上，用 ( \tilde{p}_k ) 替代 ( p_k )：

[
\text{Gini}(\tilde{D}) = 1 - \sum_{k=1}^{|\mathcal{Y}|} \tilde{p}_k^{,2}
]

步骤 ②：计算每个属性值的基尼值

对属性 ( a ) 的每个取值 ( v )，在对应的完整子集 ( \tilde{D}^v ) 上计算：

[
\text{Gini}(\tilde{D}^v) = 1 - \sum_{k=1}^{|\mathcal{Y}|} (\tilde{p}_k^v)^2
]

其中 ( \tilde{p}_k^v ) 是 ( \tilde{D}^v ) 中第 ( k ) 类样本的比例（按权重加权）。

步骤 ③：加权求和得到完整子集上的基尼指数

用 ( \tilde{r}_v ) 作为权重（替代原来的 ( |D^v|/|D| )）：

[
\text{Gini_index}(\tilde{D}, a) = \sum_{v=1}^{V} \tilde{r}_v \cdot \text{Gini}(\tilde{D}^v)
]

步骤 ④：乘以完整性比例 ( \rho )

[
\boxed{\text{Gini_index}(D, a) = \rho \times \sum_{v=1}^{V} \tilde{r}_v \cdot \text{Gini}(\tilde{D}^v)}
]

这就是推广后的基尼指数！

三、验证：退化到原始公式

当无缺失值时：

  • ( \rho = 1 )（所有样本完整）
  • ( \tilde{D} = D )，( \tilde{r}_v = |D^v|/|D| )
  • ( \tilde{p}_k = p_k )

代入：

[
\begin{aligned}
\text{Gini_index}(D, a) &= 1 \times \sum_{v=1}^{V} \frac{|D^v|}{|D|} \cdot \text{Gini}(D^v) \
&= \sum_{v=1}^{V} \frac{|D^v|}{|D|} \cdot \left(1 - \sum_{k} (p_k^v)^2\right)
\end{aligned}
]

✅ 完全退化为原始基尼指数公式！

四、选择划分属性与样本分配

选择划分属性： 与信息增益时一样，选推广后基尼指数最小的属性（CART 准则）。

样本分配： 完全一致——因为样本分配机制与划分准则无关：

  • 取值已知 → 划入对应子结点，权重保持 ( w_x )
  • 取值未知 → 同时划入所有子结点，在各子结点中权重调整为：
    [
    w_{x, v} = \tilde{r}_v \cdot w_x
    ]
五、两种准则推广的对照
步骤 信息增益（4.4.2 节） 基尼指数（本题推导）
完整子集纯度 ( \text{Ent}(\tilde{D}) = -\sum \tilde{p}_k \log_2 \tilde{p}_k ) ( \text{Gini}(\tilde{D}) = 1 - \sum \tilde{p}_k^2 )
各属性值纯度 ( \text{Ent}(\tilde{D}^v) ) ( \text{Gini}(\tilde{D}^v) )
加权求和 ( \sum \tilde{r}_v \cdot \text{Ent}(\tilde{D}^v) ) ( \sum \tilde{r}_v \cdot \text{Gini}(\tilde{D}^v) )
× 完整性折扣 ( \rho \times \text{Gain}(\tilde{D}, a) ) ( \rho \times \text{Gini_index}(\tilde{D}, a) )
选择标准 选最大增益 选最小基尼指数
六、核心洞察

🔑 本质是把”信息熵 → 信息增益”的推广模板，套用到”基尼值 → 基尼指数”上。

三个参数 ( \rho )、( \tilde{p}_k )、( \tilde{r}_v ) 完全不变，唯一改变的是用基尼值公式替代熵公式。样本的权重分配机制也与划分准则无关，因此保持不变。

这个推广模式甚至可以进一步套用到任意纯度度量函数上——核心就是 **”先用完整子集算、再乘 ρ 打折”**。

第 6 章 支持向量机

6.1 间隔与支持向量

6.1.1 什么是支持向量？

定义： 距离划分超平面最近的那几个训练样本，称为支持向量（Support Vector）。

直观理解：

1
2
3
4
5
6
7
8
graph TD
    subgraph 超平面两侧
        direction LR
        POS[正例区 ●] --- HYPER[━━━ 超平面 wᵀx+b=0 ━━━]
        HYPER --- NEG[反例区 ○]
    end
    SV["⟍ 虚线上的点 = 支持向量<br/>离超平面最近，决定边界位置"]
    HYPER -.-> SV

🔑 支持向量到超平面的距离最近，它们”支撑”了整个分类边界的位置。其他离得远的样本对超平面完全没有影响——这也是 SVM 稀疏性的来源。

6.1.2 SVM 的核心思想

SVM 的目标：在样本空间中找一个划分超平面，这个超平面不仅要分对，还要让离它最近的点（支持向量）离它尽可能远。

🎯 一句话：找一条”最宽的马路”——正反例各走一边，中间的安全间隔越大越好。

为什么间隔要大？间隔越大，对未见样本的容忍度越高，泛化能力越强：

窄间隔（过拟合风险 ⚠️） 宽间隔（泛化能力强 ✅）
正反例紧贴边界 正反例远离边界
一个离群点就可能跨线 容错空间大，抗扰动
间距 = 小 间距 = 大

6.1.3 数学表达

超平面方程：
[
\boldsymbol{w}^T \boldsymbol{x} + b = 0
]

  • (\boldsymbol{w}) = 法向量（决定超平面方向）
  • (b) = 位移项（决定超平面与原点的距离）

样本到超平面的距离：
[
r = \frac{|\boldsymbol{w}^T \boldsymbol{x} + b|}{|\boldsymbol{w}|}
]

假设超平面能正确分类，令满足：
[
\begin{cases}
\boldsymbol{w}^T \boldsymbol{x}_i + b \ge +1, & y_i = +1 \
\boldsymbol{w}^T \boldsymbol{x}_i + b \le -1, & y_i = -1
\end{cases}
]

使等号成立的样本就是支持向量。两个异类支持向量到超平面的距离之和称为间隔（Margin）：
[
\gamma = \frac{2}{|\boldsymbol{w}|}
]

SVM 基本型（硬间隔）： 最大化间隔 → 等价于最小化 (|\boldsymbol{w}|^2)：
[
\boxed{\min_{\boldsymbol{w}, b} \frac{1}{2}|\boldsymbol{w}|^2 \quad \text{s.t.} \quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1, ; i=1,\dots,m}
]

📖 s.t. = subject to（约束条件），意为”在…的约束下/受限于…”。

s.t. 公式含义拆解
部分 含义
(\min_{\boldsymbol{w}, b}) 找使目标函数最小的 (w) 和 (b)
(\frac{1}{2}|\boldsymbol{w}|^2) 目标函数：要最小化的东西（值越小 → 间隔越大）
s.t. subject to，约束条件——最小化的同时必须满足
(y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1) 每个样本必须被正确分类，且离超平面距离 ≥ 1
约束 (y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1) 的物理含义

(y_i) 的巧妙之处在于它将两种情况统一为一个不等式：

标签 (y_i) 约束展开 含义
(+1)（正例） (\boldsymbol{w}^T \boldsymbol{x}_i + b \ge +1) 正例必须在超平面正侧 ≥ 1
(-1)（反例） (\boldsymbol{w}^T \boldsymbol{x}_i + b \le -1) 反例必须在超平面负侧 ≤ -1

几何示意：

  • 正例区（(y_i=+1)）：超平面正侧，所有 ● 距超平面 ≥ 1
  • 超平面：(w^T x + b = 0)
  • 反例区（(y_i=-1)）：超平面负侧，所有 ○ 距超平面 ≤ -1

🎯 (y_i) 和 ((\boldsymbol{w}^T \boldsymbol{x}_i + b)) 同号乘积为正，异号为负。约束 ≥ 1 要求不仅分对，还要留出至少为 1 的安全距离——这正是”最大间隔”的数学体现。

这是一个凸二次规划问题，有全局最优解。

6.2 对偶问题 —— 如何求解 SVM 基本型

6.2.0 求解思路概述

SVM 基本型（式 6.6，P123）是一个带有不等式约束的凸二次规划问题。直接求解较为困难，标准方法是通过拉格朗日乘子法将其转化为对偶问题再求解。

对比维度 原始问题（Primal） 对偶问题（Dual）
目标函数 (\min \frac{1}{2}|\boldsymbol{w}|^2) (\max \sum\alpha_i - \frac{1}{2}\sum\sum\alpha_i\alpha_j y_i y_j \boldsymbol{x}_i^T\boldsymbol{x}_j)
约束 (y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b) \ge 1) (\sum\alpha_i y_i = 0,\ \alpha_i \ge 0)
变量 (\boldsymbol{w}, b)（维度 d 相关） (\boldsymbol{\alpha})（样本数 m 相关）
特点 约束复杂 约束简单，可引入核函数

6.2.1 为什么要引入对偶？

原因 说明
求解更高效 对偶问题恒为凸优化，变量数从特征维度 → 样本数，高维场景下更优
自然引入核函数 对偶形式中出现 (\boldsymbol{x}_i^T \boldsymbol{x}_j)，可直接替换为 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j))
揭示稀疏性 KKT 条件直接告诉我们哪些是支持向量（(\alpha_i > 0)）

6.2.2 拉格朗日对偶推导（逐步详解）

步骤 ①：写出拉格朗日函数（引入拉格朗日乘子）

标准模板： 对于不等式约束的优化问题，数学上有固定的引入方式。

原始问题：
[
\min_{\boldsymbol{x}} f(\boldsymbol{x}) \quad \text{s.t.} \quad g_i(\boldsymbol{x}) \le 0, ; i=1,\dots,m
]

标准拉格朗日函数：
[
L(\boldsymbol{x}, \boldsymbol{\alpha}) = f(\boldsymbol{x}) + \sum_{i=1}^{m} \alpha_i \cdot g_i(\boldsymbol{x}), \quad \alpha_i \ge 0
]

📏 这是处理不等式约束优化的标准型，来自 KKT（Karush-Kuhn-Tucker）条件框架。(\alpha_i) 称为拉格朗日乘子，(\alpha_i \ge 0) 是必要条件。

套用到 SVM：

SVM 原始问题中约束为 (y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1)，需要先改成标准形式（”≤ 0”）：

[
y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1 \quad\Longrightarrow\quad 1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \le 0
]

即 (g_i(\boldsymbol{w}, b) = 1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b))，(f(\boldsymbol{w}) = \frac{1}{2}|\boldsymbol{w}|^2)。

代入标准模板：
[
\boxed{L(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}|\boldsymbol{w}|^2 + \sum_{i=1}^{m} \alpha_i \bigl(1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b)\bigr)}
]
[
\text{其中 } \alpha_i \ge 0 \quad (i = 1, 2, \dots, m)
]

为什么 (\alpha_i \ge 0)？

这是不等式约束的标准要求。直觉上：

  • 如果要最小化 (L)，当约束违反时（(g_i > 0)），只有 (\alpha_i \ge 0) 才能使惩罚项 (\alpha_i g_i) 增加 (L)，形成有效惩罚。
  • 如果 (\alpha_i < 0)，违反约束反而降低 (L)，算法会被误导去违反约束。
📖 为什么这是”标准型”？

是的，这就是带不等式约束的拉格朗日函数标准型。

标准的 KKT 条件要求拉格朗日函数写成：
[
L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) = f(\boldsymbol{x}) + \sum \alpha_i g_i(\boldsymbol{x}) + \sum \beta_j h_j(\boldsymbol{x})
]
其中 (g_i \le 0)（不等式约束，(\alpha_i \ge 0)），(h_j = 0)（等式约束，(\beta_j) 无正负限制）。

SVM 中没有等式约束、只有不等式约束，所以式子更简单：
[
L = f + \sum \alpha_i g_i, \quad \alpha_i \ge 0
]

元素 SVM 中对应
(f(\boldsymbol{x}))，目标函数 (\frac{1}{2}|\boldsymbol{w}|^2)
(g_i(\boldsymbol{x}))，不等式约束 (1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \le 0)
(\alpha_i)，拉格朗日乘子 (\alpha_i \ge 0)（每条约束一个）
等式约束 无

💡 直觉理解： 拉格朗日乘子把约束”吸收”进了目标函数。如果第 (i) 个样本刚好在间隔边界上（(y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) = 1)），则该项为 0，不产生惩罚；如果在边界内或被错分（(<1)），则 (1 - y_i(…) > 0)，该项通过 (\alpha_i) 对 (L) 加罚。最终 SVM 的优化 → 在满足约束的前提下最小化间隔的倒数。

步骤 ②：求偏导并置零

令 (L) 对 (\boldsymbol{w}) 和 (b) 的偏导为零，消去原始变量：

对 (\boldsymbol{w}) 求偏导：
[
\frac{\partial L}{\partial \boldsymbol{w}} = \boldsymbol{w} - \sum_{i=1}^{m} \alpha_i y_i \boldsymbol{x}i = 0
\quad\Rightarrow\quad
\boxed{\boldsymbol{w} = \sum{i=1}^{m} \alpha_i y_i \boldsymbol{x}_i}
]

🔑 关键含义： 最优超平面的法向量 (\boldsymbol{w}) 是所有样本的线性组合，每个样本的贡献由 (\alpha_i y_i) 加权。

对 (b) 求偏导：
[
\frac{\partial L}{\partial b} = -\sum_{i=1}^{m} \alpha_i y_i = 0
\quad\Rightarrow\quad
\boxed{\sum_{i=1}^{m} \alpha_i y_i = 0}
]

步骤 ③：代入消元得到对偶问题

将 (\boldsymbol{w} = \sum_{i=1}^{m} \alpha_i y_i \boldsymbol{x}_i) 和 (\sum \alpha_i y_i = 0) 代回 (L)：

首先展开 (L)：
[
L = \underbrace{\frac{1}{2}|\boldsymbol{w}|^2}{\text{项 1}} + \underbrace{\sum{i=1}^{m} \alpha_i}{\text{项 2}} - \underbrace{\sum{i=1}^{m} \alpha_i y_i \boldsymbol{w}^T \boldsymbol{x}i}{\text{项 3}} - \underbrace{\sum_{i=1}^{m} \alpha_i y_i b}_{\text{项 4}}
]

项 4 消去： (-b \cdot \sum_{i=1}^{m} \alpha_i y_i = -b \cdot 0 = 0)（由 (\partial L/\partial b = 0) 得）

项 1 展开 ── 这是最关键的一步：

[
\frac{1}{2}|\boldsymbol{w}|^2 = \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w}
]

将 (\boldsymbol{w} = \sum_{i=1}^{m} \alpha_i y_i \boldsymbol{x}_i) 代入：

[
\boldsymbol{w}^T \boldsymbol{w} = \left(\sum_{i=1}^{m} \alpha_i y_i \boldsymbol{x}i\right)^T \left(\sum{j=1}^{m} \alpha_j y_j \boldsymbol{x}_j\right)
]

❓ 为什么这里用了两个不同的下标 (i) 和 (j)？

因为 (\boldsymbol{w}) 出现了两次（一次转置、一次不转置），它们是两个独立的求和。就像：
[
(a_1 + a_2)(a_1 + a_2) = a_1 a_1 + a_1 a_2 + a_2 a_1 + a_2 a_2
]
两个括号各有一个下标在跑，必须用不同字母 (i, j) 区分。写成 ((\sum_i a_i)(\sum_j a_j) = \sum_i \sum_j a_i a_j)。

转置可以放入求和号内：
[
= \left(\sum_{i=1}^{m} \alpha_i y_i \boldsymbol{x}i^T\right) \left(\sum{j=1}^{m} \alpha_j y_j \boldsymbol{x}_j\right)
]

两个括号相乘 = 每一项 × 每一项，即对所有的 ((i, j)) 组合求和：

[
= \sum_{i=1}^{m} \sum_{j=1}^{m} (\alpha_i y_i \boldsymbol{x}_i^T) \cdot (\alpha_j y_j \boldsymbol{x}_j)
]

把常数 ((\alpha_i y_i \cdot \alpha_j y_j)) 提到前面：

[
= \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j ;; \boldsymbol{x}_i^T \boldsymbol{x}_j
]

所以：
[
\frac{1}{2}|\boldsymbol{w}|^2 = \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j
]

项 3 展开（同样道理）：

[
-\sum_{i=1}^{m} \alpha_i y_i \boldsymbol{w}^T \boldsymbol{x}i = -\sum{i=1}^{m} \alpha_i y_i \left(\sum_{j=1}^{m} \alpha_j y_j \boldsymbol{x}_j\right)^T \boldsymbol{x}_i
]

[
= -\sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j
]

合并：

[
\begin{aligned}
L &= \frac{1}{2}|\boldsymbol{w}|^2 + \sum \alpha_i - \sum \alpha_i y_i \boldsymbol{w}^T \boldsymbol{x}_i - 0 \[4pt]
&= \frac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}j + \sum_i \alpha_i - \sum_i \sum_j \alpha_i \alpha_j y_i y_j \boldsymbol{x}i^T \boldsymbol{x}j \[4pt]
&= \sum{i=1}^{m} \alpha_i ;-; \frac{1}{2} \sum{i=1}^{m} \sum{j=1}^{m} \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j
\end{aligned}
]

🎯 直观验证： 项 1 是 (+½) 倍的双重和，项 3 是 (-1) 倍的双重和，合并后 = (1 - ½ = -½) 倍的双重和。

📐 双重求和的直观理解

以只有 2 个样本为例，看双重求和到底在算什么：

(i) (j) 项 (\alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j)
1 1 (\alpha_1^2 y_1^2 \boldsymbol{x}_1^T \boldsymbol{x}_1) — 样本 1 与自身
1 2 (\alpha_1 \alpha_2 y_1 y_2 \boldsymbol{x}_1^T \boldsymbol{x}_2) — 样本 1 与 2
2 1 (\alpha_2 \alpha_1 y_2 y_1 \boldsymbol{x}_2^T \boldsymbol{x}_1) — 样本 2 与 1（对称）
2 2 (\alpha_2^2 y_2^2 \boldsymbol{x}_2^T \boldsymbol{x}_2) — 样本 2 与自身

🔑 (\boldsymbol{x}_i^T \boldsymbol{x}_j) 是两个样本的内积，衡量它们的相似度。这就是核函数 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j)) 的”插槽”——只需把内积替换成核函数，SVM 就获得了处理非线性的能力！

代入后得到：
[
L = \sum_{i=1}^{m} \alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j
]

得到对偶问题（式 6.11，P124）：
[
\boxed{\max_{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}j}
]
[
\text{s.t.} \quad \sum{i=1}^{m} \alpha_i y_i = 0,\quad \alpha_i \ge 0, \quad i=1,\dots,m
]

6.2.3 用 SMO 算法求解对偶问题

对偶问题仍然是一个二次规划，但变量数 = 样本数 m。当 m 很大时，通用 QP 求解器效率低下。SMO（Sequential Minimal Optimization） 是 SVM 的高效求解算法。

核心思想

每次只优化两个 (\alpha) 变量，固定其余。两个变量的子问题有闭式解，无需迭代求解器。

为什么是”两个”而不是”一个”？因为约束 (\sum \alpha_i y_i = 0) 存在——只改一个会破坏约束，所以必须成对调整。

SMO 步骤概览
步骤 操作
① 选取一对 选两个需更新的变量 (\alpha_i, \alpha_j)（通常选违反 KKT 条件最严重的）
② 计算上下界 根据 (\sum \alpha_i y_i = 0) 确定 (\alpha_j) 的取值范围 ([L, H])
③ 求闭式解 求解无约束极值点，再裁剪到 ([L, H])
④ 更新 b 利用 KKT 条件更新阈值 (b)
⑤ 循环 重复 ①-④ 直到所有 (\alpha) 满足 KKT 条件
闭式解公式

固定其他 (\alpha)，只优化 (\alpha_i, \alpha_j)，目标函数退化为关于 (\alpha_j) 的一元二次函数：

[
\alpha_j^{\text{new}} = \alpha_j^{\text{old}} + \frac{y_j(E_i - E_j)}{\eta}
]

其中 (E_k = f(\boldsymbol{x}_k) - y_k) 是预测误差，(\eta = |\boldsymbol{x}_i - \boldsymbol{x}_j|^2)。

裁剪到合法范围：
[
\alpha_j^{\text{clipped}} = \begin{cases}
H & \text{if } \alpha_j^{\text{new}} > H \
\alpha_j^{\text{new}} & \text{if } L \le \alpha_j^{\text{new}} \le H \
L & \text{if } \alpha_j^{\text{new}} < L
\end{cases}
]

然后由约束反推出 (\alpha_i^{\text{new}})。

6.2.4 KKT 条件与稀疏性

求解完成后，KKT 条件揭示了 SVM 最重要的性质：

(\alpha_i) 取值 样本状态 对模型贡献
(\alpha_i = 0) 在间隔外，正确分类 无贡献，可丢弃
(\alpha_i > 0) 是支持向量，(y_i f(\boldsymbol{x}_i) = 1) 决定 (\boldsymbol{w}) 和 (b)

🔑 稀疏性：训练完成后，只有支持向量需要保留！ 大部分 (\alpha_i=0) 的样本可以丢弃。这是 SVM 内存效率高的根本原因。

6.2.5 从 (\boldsymbol{\alpha}) 恢复 (\boldsymbol{w}) 和 (b)

求得最优 (\boldsymbol{\alpha}^*) 后：

法向量 (\boldsymbol{w})：
[
\boldsymbol{w}^* = \sum_{i=1}^{m} \alpha_i^* y_i \boldsymbol{x}i = \sum{\alpha_i^* > 0} \alpha_i^* y_i \boldsymbol{x}_i
]
（只需对支持向量求和，其余 (\alpha_i=0) 的项自动消去）

位移项 (b)： 利用任一支持向量 ((\boldsymbol{x}_s, y_s)) 满足 (y_s f(\boldsymbol{x}s) = 1)：
[
y_s\left(\sum{\alpha_i^* > 0} \alpha_i^* y_i \boldsymbol{x}_i^T \boldsymbol{x}s + b^\right) = 1
\quad\Rightarrow\quad
b^ = y_s - \sum{\alpha_i^* > 0} \alpha_i^* y_i \boldsymbol{x}_i^T \boldsymbol{x}_s
]

实际中常用所有支持向量的平均值计算 (b) 以提高数值稳定性。

最终决策函数：
[
f(\boldsymbol{x}) = \boldsymbol{w}^{T} \boldsymbol{x} + b^ = \sum_{\alpha_i^* > 0} \alpha_i^* y_i \boldsymbol{x}_i^T \boldsymbol{x} + b^*
]

6.2.6 求解过程总结

1
2
3
4
5
6
7
graph TD
    A[原始问题<br/>凸二次规划，不等式约束] -->|① 拉格朗日乘子法| B[引入 αᵢ≥0<br/>构造 L]
    B -->|② 求偏导置零| C["∂L/∂w=0 → w=Σαᵢyᵢxᵢ<br/>∂L/∂b=0 → Σαᵢyᵢ=0"]
    C -->|③ 代入消元| D[消去 w,b<br/>得仅含 α 的对偶问题]
    D -->|④ SMO 算法| E[每次选一对 α<br/>闭式解，迭代收敛]
    E -->|⑤ 恢复 w,b| F["w=Σαᵢyᵢxᵢ (仅支持向量)<br/>b=由支持向量反推"]
    F -->|⑥ 决策函数| G["f(x) = Σαᵢyᵢxᵢᵀx + b"]

6.3 软间隔与正则化

6.3.1 为什么需要软间隔？

现实数据很难完全线性可分（即使核函数映射后），强行硬间隔会过拟合。

软间隔（Soft Margin）：允许一些样本不满足约束，即允许一些点”闯入”间隔甚至被错分。

6.3.2 软间隔的数学表达

引入松弛变量 (\xi_i \ge 0)：
[
\boxed{\min_{\boldsymbol{w}, b, \xi_i} \frac{1}{2}|\boldsymbol{w}|^2 + C\sum_{i=1}^{m} \xi_i}
]
[
\text{s.t.} \quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1 - \xi_i,\quad \xi_i \ge 0
]

参数 含义
(C > 0) 惩罚因子：(C) 大 → 严格惩罚错分（趋近硬间隔）；(C) 小 → 更宽容
(\xi_i) 松弛变量，衡量第 (i) 个样本违反约束的程度

6.3.3 (\xi_i) 的三种情况

(\xi_i) 样本位置
(\xi_i = 0) 满足硬间隔（在正确一侧的间隔外）
(0 < \xi_i \le 1) 落在间隔内部但分类正确
(\xi_i > 1) 被错分

6.3.4 合页损失（Hinge Loss）

等价于在目标函数中使用 Hinge Loss：
[
\ell_{\text{hinge}}(z) = \max(0, 1-z)
]
[
\min_{\boldsymbol{w}, b} \frac{1}{2}|\boldsymbol{w}|^2 + C\sum_{i=1}^{m} \max(0, 1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b))
]

6.4 核函数

6.4.1 为什么需要核函数？

问题：线性不可分

现实中很多数据在原始空间中线性不可分（如经典的异或 XOR 问题）：

阶段 效果
原始空间（2D） XOR 问题：4 个点拧成一团，无法用一条直线分开
(\xrightarrow{\phi(\boldsymbol{x})}) 映射后（3D） 高维空间中可以用一个平面干净利落地分开
结论 维度升高 → 原本非线性可分的数据变得线性可分

📌 定理： 只要原始空间是有限维的，就一定存在一个高维特征空间使样本线性可分。

朴素做法 → 维数灾难

直接把 (\boldsymbol{x}) 映射为 (\phi(\boldsymbol{x}))，在高维空间里做内积 (\phi(\boldsymbol{x}_i)^T \phi(\boldsymbol{x}_j))：

原始维度 映射后维度（以多项式映射为例）
2 维 → 5 维
3 维 → 19 维
一般情况 → 可能无穷维

高维空间的内积计算量爆炸，甚至无法计算——这就是维数灾难。

核函数的巧妙之处

🔑 核技巧（Kernel Trick）： 不需要显式写出 (\phi(\boldsymbol{x}))，就能直接算出映射后的内积！

[
\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \phi(\boldsymbol{x}_i)^T \phi(\boldsymbol{x}_j)
]

  • 左边：在低维原始空间中计算 (\kappa)，O(d) 复杂度
  • 右边：等价于高维特征空间中的内积，但你不必真的去算 (\phi)

一句话：核函数 = 在低维计算，等价于高维内积。

🍉 例子： 设 (\boldsymbol{x} = [x_1, x_2]^T)，映射 (\phi(\boldsymbol{x}) = [x_1^2, \sqrt{2}x_1 x_2, x_2^2]^T)，则：
[
\kappa(\boldsymbol{x}i, \boldsymbol{x}j) = (\boldsymbol{x}i^T \boldsymbol{x}j)^2 = (x{i1}x{j1} + x{i2}x{j2})^2
]
左边只算了2维的点积再平方，但结果等价于在3维空间做内积。

6.4.2 对偶形式中使用核函数

对偶问题中的 (\boldsymbol{x}_i^T \boldsymbol{x}_j) 全部替换为 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j))：

优化问题：
[
\max_{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j \kappa(\boldsymbol{x}_i, \boldsymbol{x}_j)
]

决策函数（支持向量展式）：
[
f(\boldsymbol{x}) = \sum_{\alpha_i > 0} \alpha_i y_i \kappa(\boldsymbol{x}_i, \boldsymbol{x}) + b
]

🎯 对偶形式中 (\boldsymbol{x}) 只以内积形式出现 → 核函数可以直接”插入”！

6.4.3 什么函数可以作为核函数？—— Mercer 定理（定理 6.1）

定理 6.1（核函数充要条件）：

令 (\mathcal{X}) 为输入空间，(\kappa(\cdot, \cdot)) 是 (\mathcal{X} \times \mathcal{X}) 上的对称函数。则 (\kappa) 是核函数当且仅当对于任意数据集 (D = {\boldsymbol{x}_1, \dots, \boldsymbol{x}_m})，其核矩阵 (\boldsymbol{K}) 总是半正定的：

[
\boxed{\boldsymbol{K} = \begin{bmatrix}
\kappa(\boldsymbol{x}_1, \boldsymbol{x}_1) & \cdots & \kappa(\boldsymbol{x}_1, \boldsymbol{x}_m) \
\vdots & \ddots & \vdots \
\kappa(\boldsymbol{x}_m, \boldsymbol{x}_1) & \cdots & \kappa(\boldsymbol{x}_m, \boldsymbol{x}_m)
\end{bmatrix} \succeq 0}
]

（即对任意 (\boldsymbol{v} \in \mathbb{R}^m)，有 (\boldsymbol{v}^T \boldsymbol{K} \boldsymbol{v} \ge 0)）

两个必要条件的通俗理解
条件 为什么必须？
对称性 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \kappa(\boldsymbol{x}_j, \boldsymbol{x}_i)) 内积具有对称性：(\phi(\boldsymbol{x}_i)^T \phi(\boldsymbol{x}_j) = \phi(\boldsymbol{x}_j)^T \phi(\boldsymbol{x}_i))
核矩阵半正定 保证存在一个特征空间（RKHS）使 (\kappa) 等于该空间的内积

6.4.4 正定核与再生核希尔伯特空间（RKHS）

对于满足 Mercer 条件的半正定核，总能找到一个映射 (\phi) 和一个特征空间与之对应，这个空间叫做再生核希尔伯特空间（Reproducing Kernel Hilbert Space, RKHS）。

🔑 **”再生性”**：在 RKHS 中，函数值可以通过与核函数做内积来”再生”：
[
\langle f, \kappa(\boldsymbol{x}, \cdot) \rangle_{\mathcal{H}} = f(\boldsymbol{x})
]

核心结论：
[
\text{对称 + 核矩阵半正定} \quad\Longleftrightarrow\quad \text{是一个合法的核函数} \quad\Longleftrightarrow\quad \text{隐式定义了一个 RKHS}
]

6.4.5 常用核函数

名称 表达式 参数 特点
线性核 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j) — 等同于原始空间 SVM，文本数据常用
多项式核 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d) (d \ge 1) (d) 太大易过拟合
高斯核（RBF） (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \exp!\left(-\frac{|\boldsymbol{x}_i - \boldsymbol{x}_j|^2}{2\sigma^2}\right)) (\sigma > 0) 最常用，映射到无穷维
拉普拉斯核 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \exp!\left(-\frac{|\boldsymbol{x}_i - \boldsymbol{x}_j|}{\sigma}\right)) (\sigma > 0) 对参数不那么敏感
Sigmoid 核 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \tanh(\beta \boldsymbol{x}_i^T \boldsymbol{x}_j + \theta)) (\beta>0, \theta<0) 源于神经网络，但不是正定核（仍有时使用）
RBF 高斯核的参数影响
(\sigma) 效果
太小 每个样本只影响周围极小区域 → 过拟合
太大 平滑区域过大，边界模糊 → 欠拟合

6.4.6 核函数选择的实用经验

  • 文本数据 → 线性核（高维稀疏数据已经接近线性可分）
  • 不确定时 → 先试高斯核（RBF）
  • 先验知识表明是非线性 → 多项式核或 RBF
  • 核函数的选择是 SVM 的最大变数——选错核函数 ≈ 把数据映射到了错误的特征空间，性能可能极差

6.4.7 核函数本质总结

1
2
3
4
5
6
7
graph TD
    A[线性不可分数据] --> B[映射 φ 到高维]
    B --> C[高维空间线性可分<br/>但计算内积太贵<br/>维数灾难]
    C --> D[核技巧<br/>κ = φᵀφ]
    D --> E[低维计算 = 高维内积]
    E --> F[Mercer 定理]
    F --> G[对称 + 半正定<br/>⇔ 合法核函数<br/>⇔ 隐式定义 RKHS]

6.5 影响变量总结

变量 含义 如何影响 SVM
(\boldsymbol{w}) 超平面法向量 决定分类边界的方向
(b) 位移项 决定超平面与原点的偏移
(\alpha_i) 拉格朗日乘子 (\alpha_i > 0) → 支持向量；稀疏性的来源
(C) 惩罚因子 平衡间隔大小与错分容忍度
(\xi_i) 松弛变量 样本违反硬间隔的程度
核函数 特征映射 决定模型能否处理非线性可分问题
核参数（如 (\sigma, d)） 映射空间性质 RBF的(\sigma)越小 → 越复杂，易过拟合；越大 → 越平滑

6.6 支持向量机的过拟合问题与解决方法

6.6.1 SVM 为什么会过拟合？

原因 说明
硬间隔过于严格 要求所有样本必须分对，一个离群点就能大幅扭曲超平面
核函数映射维度过高 映射到高维甚至无穷维后，模型复杂度（VC 维）暴涨
支持向量由少数点决定 若噪声点恰好成为支持向量（(\alpha_i > 0)），直接扭曲整个决策边界
“线性可分”可能是假象 西瓜书原话——即使找到核函数使训练集线性可分，也很难断定这不是过拟合造成的

6.6.2 解决方法一：软间隔（Soft Margin）

核心思想

允许部分样本不满足硬间隔约束，牺牲部分训练精度换取更强的泛化能力。

数学形式

引入松弛变量 (\xi_i \ge 0)：

[
\min_{\boldsymbol{w}, b, \xi_i} \frac{1}{2}|\boldsymbol{w}|^2 + C \sum_{i=1}^{m} \xi_i
]
[
\text{s.t.} \quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0
]

(\xi_i) 的三种情况
位置 (\xi_i) 值 直观理解
间隔外、正确分类 (\xi_i = 0) “完美公民”，满足硬间隔
间隔内部、但仍分对 (0 < \xi_i \le 1) “擦边球”，入侵了隔离带但没跨线
被错误分类 (\xi_i > 1) “越界犯规”，跨过了超平面
恰在间隔边界 (\xi_i = 0) 支持向量，定义了边界位置
(\xi_i) 样本状态 对偶中 (\alpha_i)
(\xi_i = 0) 在间隔外，正确分类 (\alpha_i = 0) 或 (0 < \alpha_i < C)
(0 < \xi_i \le 1) 在间隔内部，但仍分对 (\alpha_i = C)（被”卡”在边界）
(\xi_i > 1) 被错误分类 (\alpha_i = C)

6.6.3 解决方法二：调节惩罚因子 C

📌 C 是 SVM 防止过拟合最关键的超参数。

C 的本质

[
\min_f \underbrace{\Omega(f)}{\text{结构风险}} + \underbrace{C \sum{i=1}^{m} \ell(f(\boldsymbol{x}i), y_i)}{\text{经验风险}}
]

  • (\Omega(f) = \frac{1}{2}|\boldsymbol{w}|^2)：正则化项，追求大间隔（简单模型）
  • (\sum \ell)：在训练集上的错误惩罚
  • C 在两者之间做权衡
C 的调节方向
C 取值 效果 过拟合/欠拟合
(C \to \infty) 等价于硬间隔，零容忍错分 ⚠️ 极易过拟合
C 较大 决策边界复杂，尽量拟合所有点 过拟合风险高
C 较小 允许更多样本违规，边界更平滑 ✅ 泛化能力强，防过拟合
(C \to 0) 几乎只追求最大间隔，不管分对没有 ⚠️ 可能欠拟合

🔑 防过拟合 → 减小 C。 直觉：C 小了，模型对个别”捣乱”样本不那么较真了，边界就平滑了。

对偶形式中的体现

软间隔下对偶约束变为：
[
0 \le \alpha_i \le C
]

C 限制了每个支持向量能有多大的”话语权”。C 越小 → (\alpha_i) 上限越低 → 单个样本影响越小 → 越不容易被噪声牵着走。

6.6.4 解决方法三：调节核函数参数

高斯核（RBF）的 (\sigma) / (\gamma)

[
\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = \exp\left(-\frac{|\boldsymbol{x}_i - \boldsymbol{x}_j|^2}{2\sigma^2}\right)
]

在 LIBSVM 等实现中常用 (\gamma = \frac{1}{2\sigma^2})：

(\gamma) 大（(\sigma) 小） (\gamma) 小（(\sigma) 大）
每个样本影响范围极小 每个样本影响范围大
决策边界高度弯曲、复杂 决策边界平滑
⚠️ 极易过拟合 ✅ 泛化能力强

🎯 直觉： (\sigma) 小 → 高斯函数像一个很尖的钟形 → 只有离得非常近的点才互相影响 → 模型把每个局部噪声都拟合进去。增大 (\sigma) → 钟形变宽 → 每个点的影响范围扩大 → 更加平滑。

多项式核的 d

[
\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d
]

  • (d) 越大 → 特征空间维度越高 → 模型越复杂 → 过拟合风险越大
  • (d = 1) → 退化为线性核，最简单

6.6.5 解决方法四：选择合适的核函数

西瓜书强调：核函数选择是 SVM 的最大变数，选错 ≈ 映射到错误空间 → 性能极差。

场景 建议
特征数 ≈ 样本数（如文本分类） 线性核（高维稀疏数据已接近线性可分）
特征数少，样本量适中 高斯核（RBF）
不确定用什么 先试高斯核，通过交叉验证调 (\gamma)
想防止过拟合 优先用线性核或低次数多项式核

6.6.6 完整防过拟合策略总结

方法 机制 防过拟合时怎么调
软间隔 允许违反约束 启用（通常默认）
惩罚因子 C 平衡间隔与误差 减小 C ⬇️
RBF 的 (\gamma) 控制单样本影响范围 减小 (\gamma)（增大 (\sigma)）⬇️
多项式次数 (d) 控制映射空间维度 减小 (d) ⬇️
核函数选择 控制整体复杂度 优先线性核，必要时才用非线性
交叉验证 评估泛化性能 k 折交叉验证选最优超参数

6.6.7 正则化视角的统一理解

SVM 本质上是从结构风险最小化出发的模型：

[
\min_f \underbrace{\frac{1}{2}|\boldsymbol{w}|^2}{\text{L2 正则化}} + C \sum{i=1}^{m} \underbrace{\max(0, 1 - y_i f(\boldsymbol{x}i))}{\text{Hinge Loss}}
]

  • 第一项（L2 正则化）→ 让 (\boldsymbol{w}) 的分量尽可能稠密但数值小，降低复杂度
  • 第二项（Hinge Loss）→ 衡量训练误差
  • C → 两者间的平衡棒

这和线性回归中岭回归（L2 正则化）防止过拟合的思路完全一致——只不过 SVM 是从”追求大间隔”推导出 L2 正则化项的。

6.7 支持向量回归（SVR）— SVM 向回归问题的推广

6.7.1 从分类到回归：思路的转变

SVM 解决的是分类问题。而现实中大量任务需要回归（预测连续值，如预测房价、预测温度）。

传统回归（如线性回归）对预测偏差”零容忍”：

传统回归 SVR
对偏差的态度 每个偏差都要惩罚 偏差 ≤ ε 时不计损失
正确条件 预测值 = 真实值 预测值 ∈ [真实值-ε, 真实值+ε]
核心机制 最小化所有偏差的平方和 构建 ε-间隔带，只惩罚带外偏差

🎯 SVR 的核心思想： 以 (f(\boldsymbol{x})) 为中心，构建宽度为 (2\varepsilon) 的间隔带。样本落入带内 → 不计损失；超出带外 → 才计算损失。

6.7.2 (\varepsilon)-不敏感损失函数

[
\ell_\varepsilon(z) =
\begin{cases}
0, & |z| \le \varepsilon \
|z| - \varepsilon, & |z| > \varepsilon
\end{cases}
]

ε-不敏感损失的形状： 在 ([-ε, +ε]) 区间内损失为 0（平坦），超出的部分以斜率 1 线性增长。形状像一个”平底锅”——底部是平的，两侧向上倾斜。

和 SVM 的 Hinge Loss 对照：Hinge Loss 惩罚”分错和离边界太近”，(\varepsilon)-不敏感损失惩罚”偏离真实值超过 (\varepsilon)“。

6.7.3 SVR 的数学形式

原始问题（引入松弛变量）

每个样本需要两个松弛变量（一个管”超过上界”，一个管”跌破下界”）：

[
\begin{aligned}
\min_{\boldsymbol{w}, b, \xi_i, \hat{\xi}i} \quad & \frac{1}{2}|\boldsymbol{w}|^2 + C \sum{i=1}^{m} (\xi_i + \hat{\xi}_i) \
\text{s.t.} \quad & f(\boldsymbol{x}_i) - y_i \le \varepsilon + \xi_i \quad \text{（不超过上界）}\
& y_i - f(\boldsymbol{x}_i) \le \varepsilon + \hat{\xi}_i \quad \text{（不低于下界）}\
& \xi_i \ge 0,\ \hat{\xi}_i \ge 0
\end{aligned}
]##### SVR 的原始问题示意图

区域 含义 松弛变量
上虚线 (\text{f(x)}+\varepsilon) ε-间隔带的上界 —
下虚线 (\text{f(x)}-\varepsilon) ε-间隔带的下界 —
带内样本 ● 预测值接近真实值，”正确” (\xi_i = 0, \hat{\xi}_i = 0)
带外样本 ● 偏离真实值太远，”犯规” (\xi_i > 0) 或 (\hat{\xi}_i > 0)
SVR 的解（核化形式）

通过拉格朗日对偶求解后：
[
\boxed{f(\boldsymbol{x}) = \sum_{i=1}^{m} (\hat{\alpha}_i - \alpha_i) , \kappa(\boldsymbol{x}_i, \boldsymbol{x}) + b}
]

满足 (\hat{\alpha}_i - \alpha_i \neq 0) 的样本就是 SVR 的支持向量（落在 (\varepsilon)-间隔带外的点）。

6.7.4 SVR vs SVM 对照

维度 SVM（分类） SVR（回归）
输出 离散标签 ±1 连续实数值
“正确”的含义 分到正确的一侧且离边界 ≥ 1 预测值在真实值 ±ε 范围内
损失函数 Hinge Loss (\varepsilon)-不敏感损失
支持向量 在间隔边界上或内部 在 ε-间隔带外部
解的系数 (\alpha_i \ge 0) (\hat{\alpha}_i - \alpha_i)（可正可负）
模型形式 (\sum \alpha_i y_i \kappa(\boldsymbol{x}_i, \boldsymbol{x}) + b) (\sum (\hat{\alpha}_i - \alpha_i) \kappa(\boldsymbol{x}_i, \boldsymbol{x}) + b)

6.8 核方法 — SVM 向最一般形式的推广

6.8.1 观察：SVM 和 SVR 的共同模式

模型 解的形式
SVM 分类 (f(\boldsymbol{x}) = \sum \alpha_i y_i \kappa(\boldsymbol{x}_i, \boldsymbol{x}) + b)
SVR 回归 (f(\boldsymbol{x}) = \sum (\hat{\alpha}_i - \alpha_i) \kappa(\boldsymbol{x}_i, \boldsymbol{x}) + b)

两者都是核函数在训练样本上的线性组合：(f(\boldsymbol{x}) = \sum_{i=1}^{m} c_i \kappa(\boldsymbol{x}_i, \boldsymbol{x}))

这不是巧合——是表示定理保证的！

6.8.2 表示定理（定理 6.2，P134）

定理 6.2（表示定理，Representer Theorem）：

令 (\mathcal{H}) 为核函数 (\kappa) 对应的再生核希尔伯特空间，(\Omega: [0, \infty) \to \mathbb{R}) 为严格单调递增函数，(\ell: \mathbb{R}^m \to \mathbb{R} \cup {\infty}) 为任意损失函数。则优化问题

[
\min_{f \in \mathcal{H}} \quad \Omega\big(|f|_{\mathcal{H}}\big) + \ell\big(f(\boldsymbol{x}_1), \dots, f(\boldsymbol{x}_m)\big)
]

的最优解总可表示为：

[
\boxed{f^*(\boldsymbol{x}) = \sum_{i=1}^{m} \alpha_i \kappa(\boldsymbol{x}_i, \boldsymbol{x})}
]

解读
符号 含义
(\Omega(|f|_{\mathcal{H}})) 正则化项（结构风险），控制 (f) 在 RKHS 中的”大小”
(\ell(\dots)) 损失函数（经验风险），衡量 (f) 在训练集上的拟合程度
结论 不管 (\Omega) 和 (\ell) 长什么样，最优解一定是核函数的线性组合！

6.8.3 结构风险最小化（SRM）统一框架

表示定理意味着，SVM 可以推广为极其通用的学习框架：

[
\boxed{\min_{f \in \mathcal{H}} \underbrace{\Omega\big(|f|{\mathcal{H}}\big)}{\text{结构风险}} + C \cdot \underbrace{\sum_{i=1}^{m} \ell\big(f(\boldsymbol{x}i), y_i\big)}{\text{经验风险}}}
]

通过选择不同的损失函数 (\ell) 和正则化项 (\Omega)，可以”变出”各种学习方法：

损失函数 (\ell) 正则化项 (\Omega) 得到的模型
Hinge Loss (\frac{1}{2}|\boldsymbol{w}|^2) SVM（分类）
(\varepsilon)-不敏感损失 (\frac{1}{2}|\boldsymbol{w}|^2) SVR（回归）
平方损失 (\frac{1}{2}|\boldsymbol{w}|^2) 核岭回归（KRR）
对率损失 (\frac{1}{2}|\boldsymbol{w}|^2) 核逻辑回归
任意损失 (|f|_{\mathcal{H}}^2) 表示定理保证 → 解 = (\sum \alpha_i \kappa(\boldsymbol{x}_i, \boldsymbol{x}))

6.8.4 核方法的思想

🔑 核方法（Kernel Method）： 通过核函数，将任意线性学习器隐式地推广为非线性学习器。

不需要改动原始算法！只需把算法中出现的内积 (\boldsymbol{x}_i^T \boldsymbol{x}_j) 全部换成核函数 (\kappa(\boldsymbol{x}_i, \boldsymbol{x}_j))。

经典核方法举例：

线性方法 核化后
线性判别分析（LDA） KLDA（核线性判别分析）
主成分分析（PCA） KPCA（核主成分分析）
岭回归 KRR（核岭回归）
SVM 已经是核方法！

6.8.5 推广层次总结

1
2
3
4
5
6
7
8
9
graph TD
    A[SVM 分类，硬间隔] --> B[软间隔<br/>C, ξ]
    A --> C[核函数<br/>非线性]
    A --> D[SVR 回归<br/>ε-不敏感损失]
    B --> E[结构风险最小化<br/>min Ω + C·Σℓ]
    C --> E
    D --> E
    E --> F[表示定理 定理6.2<br/>最优解=Σαᵢκ]
    F --> G[任意核方法<br/>KPCA, KLDA, KRR…]

🎯 一句话： SVM → 软间隔（C, ξ） → SVR（ε-不敏感损失） → 结构风险最小化（通用框架） → 表示定理（解必为核函数线性组合） → 所有核方法的理论基础。

第 5 章 神经网络

5.1 神经元模型

5.1.1 M-P 神经元模型

定义： M-P 神经元（McCulloch-Pitts 模型，1943）是神经网络最基础的组成单元，模拟了生物神经元”接收信号→整合→激活→输出”的过程。

[
\boxed{y = f\left(\sum_{i=1}^{n} w_i x_i - \theta\right)}
]

数据流： 输入信号 (x_1, \dots, x_n) → 加权求和 (\sum w_i x_i) → 减阈值 (\theta) → 激活函数 (f(\cdot)) → 输出 (y)

部分 符号 含义
输入信号 (x_i) 来自前一层 n 个神经元的输出
连接权重 (w_i) 每个输入的重要性，正=兴奋、负=抑制
阈值 (\theta) 神经元”激活的底线”——总输入需超过 θ 才会被激活
净输入 (\sum w_i x_i - \theta) 加权信号 - 阈值的整合结果
激活函数 (f(\cdot)) 将净输入映射为输出值

5.1.3 激活函数

类型 公式 特点
阶跃函数（理想） ( \text{sgn}(x) = \begin{cases} 1, & x \ge 0 \ 0, & x < 0 \end{cases} ) 非0即1，但不连续、不可导
Sigmoid（常用） ( \text{sigmoid}(x) = \frac{1}{1+e^{-x}} ) 挤压到 (0,1)，光滑可导，BP 算法的基础

🎯 Sigmoid 又称”挤压函数”——不管输入多大，输出都被压进 (0,1) 之间。

5.2 感知机与多层网络

5.2.1 感知机的定义与结构

定义： 感知机（Perceptron，Rosenblatt，1957）由两层神经元组成——输入层接收信号，输出层为 M-P 神经元。

结构： 输入层(仅传递信号 (x_1, \dots, x_n)) → 加权求和 (\sum w_i x_i) → 与阈值比较 → 激活函数 (f) → 输出 (\hat{y})

🔑 关键： 只有一层功能神经元（输出层），输入层不处理信息。学习能力非常有限。

5.2.2 感知机能处理哪些问题？

能处理 ✅ 不能处理 ❌
与（AND） 异或（XOR）
或（OR） 任何非线性可分问题
非（NOT） —

💡 本质原因： 感知机学习到的决策边界是线性的（一条直线/一个超平面）。异或问题线性不可分，一条直线无法分开。

问题 线性可分？ 直观理解
AND（与） ✅ (0,0)→0, (0,1)→0, (1,0)→0, (1,1)→1——一条直线分开
OR（或） ✅ (0,0)→0, (0,1)→1, (1,0)→1, (1,1)→1——一条直线分开
NOT（非） ✅ 单输入取反
XOR（异或） ❌ (0,0)→0, (0,1)→1, (1,0)→1, (1,1)→0——怎样画直线都分不开

5.2.3 感知机学习规则

[
w_i \leftarrow w_i + \Delta w_i, \quad \Delta w_i = \eta , (y - \hat{y}) , x_i
]

  • (\eta)：学习率（0 < η < 1）
  • (y)：真实标签，(\hat{y})：预测标签
  • 只对错分样本更新权重

5.2.4 多层前馈网络

要解决非线性可分问题，需要在输入层和输出层之间加入隐含层（Hidden Layer）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
graph LR
    subgraph 输入层
        x1[x₁]
        x2[x₂]
        x3[x₃]
        x4[x₄]
    end
    subgraph 隐层
        h1[○]
        h2[○]
    end
    subgraph 输出层
        y1[y₁]
        y2[y₂]
        y3[y₃]
    end
    x1 --> h1
    x2 --> h1
    x3 --> h1
    x4 --> h1
    x1 --> h2
    x2 --> h2
    x3 --> h2
    x4 --> h2
    h1 --> y1
    h1 --> y2
    h1 --> y3
    h2 --> y1
    h2 --> y2
    h2 --> y3

特征： 全互连（每层与下一层全连接）、无同层连接、无跨层连接。

“前馈”意味着拓扑结构无环无回路，信息单向向前流动。

5.3 误差逆传播（BP）算法

5.3.1 简称与结构

  • 简称： BP（Error BackPropagation，误差逆传播）
  • 结构： 多层前馈网络，通常 3 层（输入层 + 单隐层 + 输出层）
  • 思想： 基于梯度下降策略，以目标函数的负梯度方向调整参数

5.3.2 符号约定（P102-103）

符号 含义
(d) 输入层神经元数
(q) 隐层神经元数
(l) 输出层神经元数
(v_{ih}) 输入层第 i 个→隐层第 h 个的连接权
(w_{hj}) 隐层第 h 个→输出层第 j 个的连接权
(\gamma_h) 隐层第 h 个神经元的阈值
(\theta_j) 输出层第 j 个神经元的阈值
(\alpha_h = \sum_{i=1}^{d} v_{ih} x_i) 隐层第 h 个神经元的输入
(b_h = f(\alpha_h - \gamma_h)) 隐层第 h 个神经元的输出
(\beta_j = \sum_{h=1}^{q} w_{hj} b_h) 输出层第 j 个神经元的输入
(\hat{y}_j^k = f(\beta_j - \theta_j)) 输出层第 j 个神经元的输出

5.3.3 均方误差（式 5.4）

[
E_k = \frac{1}{2} \sum_{j=1}^{l} (\hat{y}_j^k - y_j^k)^2
]

其中 k 表示第 k 个训练样本。

5.3.4 公式 5.11—5.15 完整推导

推导前准备：定义 (g_j) 和 (e_h)

先从输出层开始。根据链式法则，(w_{hj} \to \beta_j \to \hat{y}_j^k \to E_k)：

[
\frac{\partial E_k}{\partial w_{hj}} = \frac{\partial E_k}{\partial \hat{y}_j^k} \cdot \frac{\partial \hat{y}j^k}{\partial \beta_j} \cdot \frac{\partial \beta_j}{\partial w{hj}}
]

逐项计算：

[
\frac{\partial E_k}{\partial \hat{y}_j^k} = \hat{y}_j^k - y_j^k
]

[
\frac{\partial \hat{y}_j^k}{\partial \beta_j} = f’(\beta_j - \theta_j) = \hat{y}_j^k (1 - \hat{y}_j^k) \quad \text{（Sigmoid 求导性质：} f’ = f(1-f)\text{）}
]

[
\frac{\partial \beta_j}{\partial w_{hj}} = b_h
]

合并前两项，定义：
[
\boxed{g_j = -\frac{\partial E_k}{\partial \hat{y}_j^k} \cdot \frac{\partial \hat{y}_j^k}{\partial \beta_j} = \hat{y}_j^k (1 - \hat{y}_j^k)(y_j^k - \hat{y}_j^k)} \quad \text{（式 5.10）}
]

于是：
[
\boxed{\Delta w_{hj} = -\eta \frac{\partial E_k}{\partial w_{hj}} = \eta , g_j , b_h} \quad \text{（式 5.11）}
]

式 5.12：输出层阈值 (\theta_j) 的更新

同理，(\theta_j \to \hat{y}_j^k \to E_k)：
[
\frac{\partial E_k}{\partial \theta_j} = \frac{\partial E_k}{\partial \hat{y}_j^k} \cdot \frac{\partial \hat{y}_j^k}{\partial \theta_j} = (\hat{y}_j^k - y_j^k) \cdot \bigl(-\hat{y}_j^k(1-\hat{y}_j^k)\bigr) = -g_j
]

[
\boxed{\Delta \theta_j = -\eta \frac{\partial E_k}{\partial \theta_j} = -\eta , g_j} \quad \text{（式 5.12）}
]

式 5.13：隐层连接权 (v_{ih}) 的更新

更复杂一些：(v_{ih} \to \alpha_h \to b_h \to \beta_j \to \hat{y}_j^k \to E_k)（通过所有输出神经元传播）：

[
\frac{\partial E_k}{\partial v_{ih}} = \frac{\partial E_k}{\partial b_h} \cdot \frac{\partial b_h}{\partial \alpha_h} \cdot \frac{\partial \alpha_h}{\partial v_{ih}}
]

其中：
[
\frac{\partial E_k}{\partial b_h} = \sum_{j=1}^{l} \frac{\partial E_k}{\partial \beta_j} \cdot \frac{\partial \beta_j}{\partial b_h} = \sum_{j=1}^{l} (-g_j) \cdot w_{hj} = -\sum_{j=1}^{l} w_{hj} g_j
]

[
\frac{\partial b_h}{\partial \alpha_h} = f’(\alpha_h - \gamma_h) = b_h (1 - b_h)
]

[
\frac{\partial \alpha_h}{\partial v_{ih}} = x_i
]

定义：
[
\boxed{e_h = -\frac{\partial E_k}{\partial b_h} \cdot \frac{\partial b_h}{\partial \alpha_h} = b_h(1-b_h)\sum_{j=1}^{l} w_{hj} g_j} \quad \text{（式 5.15）}
]

于是：
[
\boxed{\Delta v_{ih} = -\eta \frac{\partial E_k}{\partial v_{ih}} = \eta , e_h , x_i} \quad \text{（式 5.13）}
]

式 5.14：隐层阈值 (\gamma_h) 的更新

同理，(\gamma_h \to b_h \to \beta_j \to \dots)：
[
\frac{\partial E_k}{\partial \gamma_h} = \frac{\partial E_k}{\partial b_h} \cdot \frac{\partial b_h}{\partial \gamma_h} = \left(-\sum_{j=1}^{l} w_{hj} g_j\right) \cdot \bigl(-b_h(1-b_h)\bigr) = e_h
]

注意这里有两个负号相消：(\frac{\partial b_h}{\partial \gamma_h} = -b_h(1-b_h))

[
\boxed{\Delta \gamma_h = -\eta \frac{\partial E_k}{\partial \gamma_h} = -\eta , e_h} \quad \text{（式 5.14）}
]

公式推导路线图
1
2
3
4
5
6
7
8
9
10
链式求导路径：

w_hj → β_j  → ŷ_j^k → E_k          → Δw_hj = η·g_j·b_h       (5.11)
θ_j  → ŷ_j^k → E_k                → Δθ_j  = -η·g_j           (5.12)
v_ih → α_h → b_h → β_j → ŷ_j^k → E_k → Δv_ih = η·e_h·x_i    (5.13)
γ_h  → b_h → β_j → ŷ_j^k → E_k       → Δγ_h  = -η·e_h        (5.14)

其中两个关键中间量：
  g_j = ŷ_j^k(1-ŷ_j^k)(y_j^k - ŷ_j^k)              (5.10)
  e_h = b_h(1-b_h) Σ_{j=1}^{l} w_hj·g_j           (5.15)

5.3.5 标准 BP vs 累积 BP

标准 BP 累积 BP
更新频率 每个样本更新一次 整个训练集（一个 epoch）更新一次
类比 随机梯度下降（SGD） 批量梯度下降
优点 更新频繁，大数据集下更快获得好解 收敛过程更稳定
缺点 各样本更新可能相互抵消 累积误差降到一定程度后极慢

5.3.6 BP 网络过拟合的解决方法

方法 原理 操作
早停（Early Stopping） 验证集误差不再下降（甚至上升）→ 停止训练 训练中持续监控验证集
正则化（Regularization） 在目标函数中加入权重的平方和，偏好”小权重” (E = \lambda \frac{1}{m}\sum E_k + (1-\lambda)\sum w_i^2)

🎯 正则化的直觉： 小权重 → 网络输出更平滑 → 对输入微变不敏感 → 泛化能力更强。

5.4 全局最小与局部极小

5.4.1 定义

误差函数 (E(w)) 随参数 (w) 变化：像一片连绵的山脉，有几个”山谷”（局部极小），其中最低的那个山谷才是”海平面”（全局最小）。

1
2
3
4
5
6
graph TD
    A[误差函数 E] --> B[局部极小 A<br/>邻域内最小]
    A --> C[局部极小 B<br/>另一个山谷]
    C --> D[全局最小 C<br/>整个空间最低点]
    B -.->|"走不出"| B
    D -.->|"真正最优"| D
概念 定义
局部极小 该点的邻域内所有点的误差都 ≥ 该点
全局最小 整个参数空间中所有点的误差都 ≥ 该点

5.4.2 为什么容易陷入局部极小？

梯度下降的策略是通过计算梯度 → 只向着下坡走。一旦走入一个局部极小值的”坑”里，因为四周都比它高，梯度为 0 → 算法以为到了最低点 → 再也走不出去。

💡 类比：在一个多山地形中蒙眼下山，走到第一个洼地就停住了，但那可能只是个小水坑，不是整个区域的最低点。

5.4.3 跳出局部极小的策略

方法 原理
多组不同参数初始化 多练几组，取误差最小的——不同的起点可能走到不同的终点
模拟退火（Simulated Annealing） 以一定概率接受更差的解（概率随”温度”降低而减小），有机会跳出局部极小
随机梯度下降（SGD） 每次用单样本计算梯度，梯度自带随机噪声 → 天然具备跳出局部极小的能力
遗传算法（Genetic Algorithm） 群体搜索，多个点同时探索，不容易全部困在同一局部极小

5.5 其他常见神经网络

5.5.1 RBF 网络（径向基函数网络）

维度 说明
结构 单隐层前馈网络
隐层激活函数 径向基函数：(\rho(\boldsymbol{x}, \boldsymbol{c}_i) = e^{-\beta_i |\boldsymbol{x} - \boldsymbol{c}_i|^2})
输出层 隐层输出的线性组合
训练 ① 确定 RBF 中心 (\boldsymbol{c}_i)（聚类/随机采样）；② 用 BP 训练 (w_i, \beta_i)
特点 局部逼近——每个隐层神经元只对输入空间中某个局部区域敏感

5.5.2 ART 网络（自适应谐振理论）

维度 说明
类型 竞争性学习，胜者通吃（Winner-Take-All）
结构 比较层 + 识别层 + 识别阈值 + 重置模块
核心优势 增量学习/在线学习——新样本不会覆盖旧知识，解决”可塑性-稳定性窘境”
工作方式 新样本与已有模式比较 → 相似度 > 阈值 → 归入该模式并更新权重；否则 → 新增神经元

5.5.3 SOM 网络（自组织映射）

维度 说明
类型 无监督竞争学习
目标 将高维输入映射到低维空间（通常 2D），保持拓扑结构
输出层 二维网格排列的神经元
训练 找到最佳匹配单元（BMU）→ 调整 BMU 及其邻域神经元的权向量
应用 数据可视化、聚类

5.5.4 级联相关网络（Cascade-Correlation）

维度 说明
类型 结构自适应网络——网络结构本身也是学习目标
两个机制 级联（新神经元连接所有旧神经元）+ 相关（最大化新神经元输出与残差的相关性）
优点 无需预设层数和隐层神经元数，训练速度快
缺点 小数据集容易过拟合

5.5.5 Elman 网络

维度 说明
类型 递归神经网络（RNN）——最常用的之一
结构 隐层输出反馈回来，与下一时刻的输入一起作为隐层输入
特点 t 时刻状态取决于 t 时刻输入 + t-1 时刻状态 → 有记忆能力
训练 推广的 BP 算法（BPTT）

5.5.6 Boltzmann 机

维度 说明
类型 基于能量的模型——最小化能量达到稳定状态
神经元 布尔型（0/1），全连接
结构 显层 + 隐层，每层内也互相连接
问题 全连接结构 → 训练复杂度极高
改进 受限 Boltzmann 机（RBM）：去掉层内连接，仅保留层间全连接，用 CD（对比散度）算法训练

5.6 深度学习

5.6.1 什么是深度学习？

典型的深度学习模型就是很深层的神经网络——增加隐层数量。

增加隐层数比增加隐层神经元数更有效（增加的不只是参数，还有激活函数的嵌套层数，非线性表达能力指数级增长）。

5.6.2 为什么深度网络难以训练？

经典 BP 算法在深层网络中误差在逆传播时容易发散/梯度消失（Sigmoid 的导数最大才 0.25，多层相乘 → 梯度指数衰减）。

5.6.3 深度网络的训练方法

方法 原理 代表
无监督逐层训练 每次只训练一层（无监督预训练），最后整个网络联合微调 DBN（深度信念网络）
权共享（Weight Sharing） 一组神经元使用相同的连接权，大幅减少参数量 CNN（卷积神经网络）
ReLU 激活函数 导数在正半轴恒为 1，缓解梯度消失 现代深度网络标配
Batch Normalization 每层输入标准化，稳定梯度传播 —
残差连接（Residual Connection） 跨层直连，梯度可”跳过”中间层 ResNet

5.6.4 深度学习的本质

可理解为特征学习（表示学习）——逐层将”低层”特征转化为”高层”特征。浅层学到边角纹理，深层学到语义概念。

5.7 课后习题精讲

习题 5.1：将线性函数用作激活函数的缺陷

答： 若激活函数为线性 (f(x) = ax + b)，则无论多少层神经网络的叠加，输出始终是输入的线性组合。

  • 若输出层也用线性函数 → 等价于线性回归
  • 若输出层用 Sigmoid → 等价于逻辑回归

🔑 失去了深度网络最重要的优势——多层的非线性表达能力。深层网络之所以强大，就是因为激活函数的非线性嵌套。

习题 5.2：Sigmoid 激活函数与对率回归的联系

答：

对率回归 带 Sigmoid 的神经元
本质 使用 Sigmoid 作为联系函数的广义线性模型 同左
输出 (>0.5) → 判为 1（离散决策） 直接输出连续值 (sigmoid(x))
关系 可以看作带 Sigmoid 神经元的二分类特化版本 更通用的形式

若对率回归的输出不取阈值、直接输出概率值，则两者在数学上等价。

习题 5.4：学习率取值对 BP 训练的影响

答：

学习率 (\eta) 影响
过大 误差函数在最小值附近来回震荡，甚至发散，无法收敛
过小 收敛极慢，需要大量迭代次数，训练效率低
适中 快速且稳定地收敛到最优解附近

🎯 实践中常用自适应学习率方法（Adam, RMSProp）或学习率衰减策略。

习题 5.7：构造能解决异或问题的单层 RBF 神经网络

答： 使用两个 RBF 神经元即可。

数据： XOR 问题——(X=[(0,0), (0,1), (1,0), (1,1)])，(y=[0, 1, 1, 0])

网络结构：

1
2
3
4
5
6
graph LR
    x1[x₁] --> r1["ρ₁=exp(-β‖x-c₁‖²)"]
    x2[x₂] --> r2["ρ₂=exp(-β‖x-c₂‖²)"]
    r1 -->|w₁=1| sum[Σ]
    r2 -->|w₂=1| sum
    sum --> y[ŷ]

设置： 取两个中心 (\boldsymbol{c}_1 = (0,1))、(\boldsymbol{c}_2 = (1,0))（两个输出为 1 的点），(\beta) 取足够大（如 (\beta=10)）。

  • 当 (\boldsymbol{x}=(0,1))：(\rho_1 \approx 1)，(\rho_2 \approx 0)
  • 当 (\boldsymbol{x}=(1,0))：(\rho_1 \approx 0)，(\rho_2 \approx 1)
  • 当 (\boldsymbol{x}=(0,0)) 或 ((1,1))：两个 RBF 输出都接近 0

输出层权重设为 (w_1=1, w_2=1)，偏置=0 → 输入 (0,1) 或 (1,0) 时输出 ≈1，否则 ≈0 → XOR 解决！ ✅

📝 复习题资料汇编（2024 机器学习复习题）

来源：2024机器学习_复习题1.pdf（31页）、2024机器学习_复习题2.pdf（15页）
按西瓜书章节整理，标注 [选] = 选择题、**[多]** = 多选题、**[简]** = 简答题、**[计]** = 计算题

第 2 章 模型评估与选择

核心概念题

编号 类型 题目 答案/要点
— 简 简述分类问题与回归问题的定义与区别 分类：标签 y 为离散值；回归：标签 y 为连续值；分类依据类别标签划分空间，回归拟合 x 与 y 的映射
— 简 简述聚类问题的定义 给定样本集 {x_i}，学习 x 到类别 y 的映射（无标签）
20 选 回归问题和分类问题的区别 A. 前者连续值，后者离散值
26 选 过拟合现象中 A. 训练误差小，测试误差大
36 选 过拟合现象的描述 A. 训练误差小，测试误差大
58 选 “过拟合”现象的出现范围 C. 监督学习和非监督学习中都可能出现
31 选 增加欠拟合风险的方法 D. 数据增强（会增加欠拟合）
60 选 k 折交叉验证中 k 的说法 D. 以上所有：k 越大评估时间越大、bias 越小、需最小化方差
65 选 关于交叉验证说法错误的是 A. 交叉验证不能直接提升模型准确率
36 多 划分测试集和训练集的方法 ABC：留出法、交叉验证法、自助法

简答题

编号 题目 答案要点
14 从误差分解角度简述泛化误差 泛化误差 = 偏差 + 方差 + 噪声；偏差度量算法拟合能力；方差度量数据扰动影响；噪声刻画问题本身难度
15 欠拟合和过拟合现象是什么 过拟合：训练好、验证差；欠拟合：训练和验证误差都高
16 降低过拟合和欠拟合的方法 降低过拟合： 数据增强、降低模型复杂度、正则化、集成学习；降低欠拟合： 添加新特征、增加模型复杂度、减小正则化系数

第 3 章 线性模型

核心概念题

编号 类型 题目 答案/要点
4 选 属于线性分类方法的是 B. 感知机
6 选 LDA 描述最准确的是 B. 类内距离最小，类间距离最大
73 选 关于逻辑回归说法不正确的是 B. 逻辑回归是分类模型，不是回归模型
30 选 岭回归中 λ 较大时 C. 偏差增大，方差减小
54 选 L1 + L2 范数在 Logistic 中的作用 A. 特征选择 + 防止过拟合
14 多 属于线性分类方法的是 AD：线性回归、Fisher 鉴别
26 多 各算法对应的损失函数正确的是 ABCD：最小二乘-Square loss、SVM-Hinge Loss、Logistic-交叉熵、AdaBoost-指数损失

简答题

编号 题目 答案要点
1 阐述 LDA（线性鉴别分析）的分类思想 通过最大化类间距离 + 最小化类内方差，将数据投影到低维空间，实现有效类别分离
4 为什么通常要进行标准化处理 ①使不同特征数值范围一致 ②减小训练难度加速收敛 ③提高模型鲁棒性。方法：Z-score 标准化 (z = (x-\mu)/\sigma)

计算题

编号 题目 关键方法
6 求 Fisher 最优鉴别矢量 ①计算类内均值 μ₁, μ₂ ②计算类内散度矩阵 S_w ③最优鉴别矢量 ω = S_w⁻¹(μ₁-μ₂)
11 利用 Fisher 鉴别分析求投影方向 同上，给定数据逐步计算

第 4 章 决策树

核心概念题

编号 类型 题目 答案/要点
5 选 不受数据归一化影响的是 D. 决策树
12 选 决策树节点划分指标正确的是 B. 信息增益越大越好
13 选 属于决策树策略的是 D. 最大信息增益
59 选 大数据集上训练决策树，为减少时间 C. 减少树的深度
10 多 属于非线性模型的是 ACD：决策树、多层感知机、M-P 模型
17 多 决策树常见组件有 ACD：基分类器、剪枝方法、划分目标
18 多 决策树剪枝策略 AB：预剪枝、后剪枝
30 多 可以不对特征做归一化处理的是 AD：随机森林、决策树

计算题

编号 题目 关键方法
4 给定 5 个样本，分别使用 ID3、C4.5、CART 计算第一次节点划分的最优特征 详见下方完整推导 ↓
🍉 决策树计算题完整推导（ID3/C4.5/CART）

题目： 5 个样本，4 个特征（年龄、长相、工资、写代码），二分类标签。分别用 ID3、C4.5、CART 找第一次划分的最优特征。

重构数据表（由计算结果反推）：

样本 年龄 长相 工资 写代码 标签
1 青年 帅 高 会 好
2 青年 帅 高 不会 差
3 中年 普通 低 会 好
4 老年 丑 低 会 好
5 老年 普通 低 不会 差

📌 核心在于掌握计算方法，具体数字可随数据不同而变化。

预备：根结点信息熵

5 样本：3 好 + 2 差：

[
\text{Ent}(D) = -\frac{3}{5}\log_2\frac{3}{5} - \frac{2}{5}\log_2\frac{2}{5} = 0.971
]

一、ID3 — 信息增益（选最大值）

公式： (\text{Gain}(D, a) = \text{Ent}(D) - \sum_{v} \frac{|D^v|}{|D|} \cdot \text{Ent}(D^v))

以”写代码”为例：

取值 样本 好:差 熵 Ent(D^v)
会 {1,3,4} 3:0 (-1\log_2 1 - 0 = 0)
不会 {2,5} 0:2 (-0 - 1\log_2 1 = 0)

[
\text{Gain}(D, \text{写代码}) = 0.971 - \left(\frac{3}{5}\times 0 + \frac{2}{5}\times 0\right) = \boxed{0.971}
]

汇总各特征信息增益：

特征 信息增益 排名
写代码 0.971 🥇
长相 0.42 🥈
工资 0.42 🥈
年龄 0.171 🥉

🎯 ID3 选择：写代码 — 信息增益最大。

二、C4.5 — 增益率（先筛高于平均增益，再选最大增益率）

公式： (\text{Gain_ratio}(D, a) = \frac{\text{Gain}(D, a)}{\text{IV}(a)})

其中固有值：(\text{IV}(a) = -\sum_{v} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|})

依次计算：

特征 Gain IV(a) Gain_ratio
写代码 0.971 (-\frac{3}{5}\log_2\frac{3}{5} - \frac{2}{5}\log_2\frac{2}{5} = 0.971) 0.971/0.971 = 1.000
年龄 0.171 (-\frac{2}{5}\log_2\frac{2}{5}\times 2 - \frac{1}{5}\log_2\frac{1}{5} = 0.722) 0.171/0.722 = 0.236
长相 0.42 1.371 0.42/1.371 = 0.306
工资 0.42 1.371 0.42/1.371 = 0.306

C4.5 启发式： 先筛出增益高于平均水平（均值 ≈ 0.50）的特征：

特征 Gain > 0.50？ Gain_ratio
写代码 ✅ 0.971 1.000
长相 ❌ —
工资 ❌ —
年龄 ❌ —

🎯 C4.5 选择：写代码 — 唯一高于平均增益的特征。

三、CART — 基尼指数（选最小值）

公式： (\text{Gini}(D) = 1 - \sum_k p_k^2)，(\text{Gini_index}(D, a) = \sum_{v} \frac{|D^v|}{|D|} \cdot \text{Gini}(D^v))

以”写代码”为例：

取值 样本数 好:差 Gini(D^v)
会 3 3:0 (1 - (1^2 + 0^2) = 0)
不会 2 0:2 (1 - (0^2 + 1^2) = 0)

[
\text{Gini_index}(D, \text{写代码}) = \frac{3}{5}\times 0 + \frac{2}{5}\times 0 = \boxed{0}
]

基尼指数 = 0 → 子集完全纯净，最优划分。

🎯 CART 选择：写代码 — 基尼指数最小。

方法对比口诀
方法 准则 选什么 记忆
ID3 信息增益 最大 “熵减最多”
C4.5 增益率（先筛增益>均值） 最大 “归一化后再挑”
CART 基尼指数 最小 “越纯越小说了算”

第 5 章 神经网络

核心概念题

编号 类型 题目 答案/要点
27 选 可用作神经元非线性激活函数的是 A. logistic 函数
37 选 不可以做激活函数的是 D. y=2x（线性函数）
29 选 梯度下降算法正确步骤 B. 4→3→1→5→2（初始化→输入→算误差→改权重→迭代）
45 选 RNN 中处理梯度爆炸的方法 A. 梯度裁剪
50 选 主要负责在神经网络中引入非线性 B. ReLU
51 选 有反馈连接、处理序列数据 A. 循环神经网络
52 选 神经网络中处理过拟合的方法 D. 都可以（Dropout、BN、正则化）
34 选 CNN 正确结论 C. Pooling 层用于减少图片的空间分辨率
31 多 分类模型有哪些 ACD：最近邻、朴素贝叶斯、逻辑回归
19 多 可通过神经网络形式实现的算法 BD：Logistic 回归、最小二乘估计
20 多 属于深度学习的是 ABD：CNN、RNN、受限玻尔兹曼机
21 多 影响深度神经网络训练效果的因素 ABCD：学习率、训练集规模、网络深度、激活函数
32 多 隐层输出含 -1.5，激活函数不可能是 ABC：Sigmoid、Tanh（输出范围 [-1,1] 含 -1.5 不可能）、ReLU（输出 ≥0）

简答题

编号 题目 答案要点
5 线性函数用作激活函数的缺陷 多层堆叠无法引入非线性，无论多少层都退化成一个线性回归
6 学习率取值对神经网络训练的影响 过小→收敛缓慢、易陷局部极小；过大→训练不稳定、振荡或无法收敛；合适→快速稳定收敛
7 神经网络为什么会产生梯度消失 传统激活函数（sigmoid/tanh）是双线性饱和的，梯度 ∇f(x) 在 [0,1] 区间，多层连乘 [∇f(x)]ⁿ→0
18 简述 ReLU 激活函数的优缺点 优点： 形式简单、计算高效、缓解梯度消失；缺点： 神经元死亡（输出恒零）、不适用所有场景
8 CNN 卷积层参数计算 详见下方详解
CNN 卷积层计算详解

题目： 输入 3 个 32×32 特征图，卷积核 10 个 5×5，Stride=1，Pad=2。求输出特征图尺度和卷积层参数数量。

一、输出特征图尺度

通用公式：

[
\boxed{H_{\text{out}} = \left\lfloor \frac{H_{\text{in}} + 2 \times \text{pad} - K}{\text{stride}} \right\rfloor + 1}
]

同理宽度 (W_{\text{out}}) 用同样的公式。当输入为正方形（H=W）时，输出亦为正方形。

逐项代入：

符号 值 含义
(H_{\text{in}}) 32 输入特征图高度
pad 2 边缘填充圈数
(K) 5 卷积核大小
stride 1 滑动步长

[
H_{\text{out}} = \frac{32 + 2 \times 2 - 5}{1} + 1 = \frac{32 + 4 - 5}{1} + 1 = 31 + 1 = 32
]

输出结果： (10 \times 32 \times 32)（10 个通道，每通道 32×32）

因为 pad=2 恰好补偿了卷积核收缩的影响（5-1=4=2×2），所以输出尺度等于输入尺度。

二、卷积层参数量

通用公式：

[
\boxed{\text{参数总数} = (K \times K \times C_{\text{in}} + 1) \times C_{\text{out}}}
]

部分 含义
(K \times K) 单个卷积核的空间尺寸（5×5 = 25 个权重）
(C_{\text{in}}) 输入通道数（每个卷积核需要同时处理所有输入通道）
(+1) 每个卷积核的偏置（bias）
(C_{\text{out}}) 输出通道数 = 卷积核个数

🎯 核心理解： 每个输出通道对应一个完整的 3D 卷积核（5×5×3 权重 + 1 偏置）。10 个输出通道 = 10 个卷积核。

逐项代入：

[
\begin{aligned}
\text{参数总数} &= (5 \times 5 \times 3 + 1) \times 10 \
&= (25 \times 3 + 1) \times 10 \
&= (75 + 1) \times 10 \
&= 76 \times 10 \
&= 760
\end{aligned}
]

三、公式记忆技巧
你想求的 公式 形象理解
输出尺寸 (\frac{H_{in} + 2p - K}{s} + 1) “填了 2p，减了 K，每 s 步踏一次，首尾都算”
参数量 ((K^2 \cdot C_{in} + 1) \cdot C_{out}) “一个 3D 核 + bias → 再乘以核的个数”
四、计算量（BONUS，面试常考）

FLOPs（浮点运算次数）公式：

[
\text{FLOPs} = 2 \times (K \times K \times C_{\text{in}}) \times H_{\text{out}} \times W_{\text{out}} \times C_{\text{out}}
]

其中 ×2 是因为每个乘法-加法对算两次浮点运算。

本例中：
[
\text{FLOPs} = 2 \times (5 \times 5 \times 3) \times 32 \times 32 \times 10 = 2 \times 75 \times 1024 \times 10 = 1{,}536{,}000
]
| — | 简述深度学习定义与训练方法 | 深度学习 = 很深层的神经网络。有效训练方法：无监督逐层训练（预训练+微调）、权共享（CNN）、ReLU 缓解梯度消失、残差连接（ResNet） |

第 6 章 支持向量机

核心概念题

编号 类型 题目 答案/要点
7 选 SVM 原理可简单描述为 C. 最大间隔分类
8 选 SVM 算法性能取决于 D. 以上所有（核函数选择、核参数、软间隔 C）
9 选 SVM 对偶问题是 C. 凸二次优化
10 选 对支持向量描述正确的是 C. 最大间隔支撑面上的向量
11 选 增加核函数阶数后 A. 过拟合
19 选 软间隔 SVM 的 C→∞ 时 A. 只要最佳分类超平面存在就能全部正确分类
38 选 容易引起过拟合的是 D. SVM 使用高斯核代替线性核
68 选 SVM 损失函数说法错误的是 D. 分类 SVM 常用平方误差损失（实际用 Hinge Loss）
69 选 SVM 核函数说法错误的是 C. 核函数映射维度不是越高越好（会过拟合）
72 选 用线性手段实现非线性学习 A. 核函数方法
41 多 解决非线性可分问题的方法 BCD：神经网络、决策树、最近邻分类器

简答题

编号 题目 答案要点
2 简要介绍 SVM 设计思想 寻找能够最大化类别间间隔的超平面，使数据点距离超平面的最小距离（间隔）最大
3 分析 SVM 对噪声敏感的原因 SVM 追求边界最大间隔，决策边界由支持向量决定。当增加噪声时，噪声可能成为支持向量，直接扭曲决策边界

第 7 章 贝叶斯分类器

核心概念题

编号 类型 题目 答案/要点
3 选 朴素贝叶斯分类器的特点是 C. 假设样本各维属性独立
49 选 没有考虑先验分布的是 D. 最大似然估计
55 选 属于生成式模型的是 D. 朴素贝叶斯模型
56 选 属于判别式模型的是 A. 支持向量机
61 选 不属于贝叶斯分类器参数估计准则的是 C. 最大间隔
71 选 关于朴素贝叶斯说法错误的是 D. 朴素贝叶斯估计了联合概率（实际上是估计了的）
11 多 属于贝叶斯网络的有 BD：隐马尔可夫模型、朴素贝叶斯分类器

计算题

编号 题目 关键方法
5 硬币正面概率的极大似然估计 L(p) = C(30,12)·p¹²·(1-p)¹⁸，求导得 p=0.4
7 贝叶斯网络推理 P(S=1|G=1)、P(R=1|G=1) 因子分解 + 条件概率求和
8 最小错误率贝叶斯决策 比较 P(ω₁|x) 和 P(ω₂|x)
9 最小风险贝叶斯决策 将 x 判为风险最小的类别，计算 rⱼ(x) = Σ L(θⱼ,θᵢ)·P(ωᵢ|x)
10 朴素贝叶斯分类器 利用属性独立性假设，比较 P(Y=0|A,B,C) vs P(Y=1|A,B,C)

第 8 章 集成学习

核心概念题

编号 类型 题目 答案/要点
14 选 集成学习中基分类器怎样选效率好 D. 分类器多样、差异大
15 选 基分类器正确率最低要求 A. 50% 以上
16 选 Bagging 方法特点 A. 构造训练集时采用 Bootstraping
17 选 Boosting 方法特点 D. 预测结果时分类器比重不同
18 选 随机森林属于 B. Bagging 方法
32 选 增加哪些超参数导致随机森林过拟合 B. 决策树深度
41 选 Adaboost 描述错误的是 D. 同时独立学习多个弱分类器（实际是串行的）
16 多 集成学习描述正确的是 AD：Bagging 可并行、Boosting 基学习器比重不同
33 多 关于集成学习正确的是 BC：Bagging 降低方差、Boosting 降低偏差

简答题

编号 题目 答案要点
9 随机森林为何比决策树 Bagging 训练更快 Bagging 需考察结点所有属性，随机森林只需随机考察一个属性子集，减少了每棵树训练时需考虑的特征数

第 9 章 聚类

核心概念题

编号 类型 题目 答案/要点
1 选 属于监督学习的是 A. 贝叶斯分类器
2 选 属于无监督学习的是 C. 层次聚类
35 选 k-means 算法描述正确的是 B. 初始值不同，最终结果可能不同
39 选 属于无监督学习算法的是 D. K-Means 聚类
47 选 不带标签时使数据分离的技术 B. 聚类
57 选 属于无监督学习的是 A. k-means
70 选 K-means 说法错误的是 D. 初始聚类中心选择对聚类结果影响很大（不是不大）
77 选 聚类说法错误的是 D. 同一类内样本间差异较大（应该较小）
78 选 k-means 说法不正确的是 D. 不适合处理非凸型数据
2 多 对聚类问题描述不正确的是 ACD：不是监督学习、非线性决策、增量学习
3 多 属于聚类方法的是 ABD：k-means、层次聚类、密度聚类
4 多 影响 K-Means 结果的主要因素 BC：相似性度量、初始聚类中心
6 多 层次聚类方法有 CD：自底向上、自顶向下

简答题

编号 题目 答案要点
17 K 均值算法的优缺点及调优 优点： 大数据集有效、简单易懂实现、O(NKt) 近似线性；缺点： 对初始中心敏感、对异常值敏感、需事先指定 K；调优： 鲁棒初始化、合理选 K、数据归一化、离群点预处理

计算题

编号 题目 关键方法
12 k-means 聚类计算 初始化质心→归类→更新质心→迭代至收敛
13 自底向上层次聚类 每个点初始为一类→计算簇间距离→合并最近的两簇→重复至只余一类

第 10 章 降维与度量学习

核心概念题

编号 类型 题目 答案/要点
24 选 主成分分析是什么方法 C. 降维方法
25 选 PCA 优先选取哪些特征 A. 协方差矩阵最大特征值对应特征向量
22 多 特征降维带来的好处 ABD：节省通信开销、节省存储资源、加快计算速度
23 多 特征选择和特征提取描述正确的是 BC：特征选择是从原始 d 个特征选 k 个；特征提取是形成 k 个新特征
43 选 侧重考虑向量方向的距离 D. 余弦距离
24 多 计算两个向量相似度的方法 ABD：欧式距离、夹角余弦、曼哈顿距离

简答题

编号 题目 答案要点
10 L1 和 L2 范数的计算方法及使用场景 L1：‖x‖₁=∑|x_i| → 特征稀疏化；L2：‖x‖₂=√∑x_i² → 防止过拟合
11 为什么 L1 范数可以进行特征选择 L1 范数惩罚项引入稀疏性，使部分特征的权重变为零，实现自动特征选择
12 主成分分析的主要步骤 ①数据标准化 ②计算协方差矩阵，求特征值和特征向量 ③按特征值从大到小排序，选前 k 个 ④将样本投影到选取的特征向量上

第 14 章 概率图模型

核心概念题

编号 类型 题目 答案/要点
28 选 有向图条件独立性判断 根据 d-分离准则判断
42 选 HMM 中已知观察序列和状态序列 D. 极大似然估计
44 选 解决 HMM 预测问题的算法 D. 维特比算法
66 选 可应用 HMM 模型的选项 D. 所有以上（基因序列、电影浏览、股票市场）
67 选 EM 算法说法不正确的是 A. EM 算法不是分类算法
12 多 无向图的团和极大团 团：完全连接的结点子集；极大团：不被其他团包含的团

计算题

编号 题目 关键方法
1 概率图模型因子分解 有向图：(P(A,B,C,D)=P(A)P(D)P(B|A,D)P(C|A,B,D))；无向图：(P(A,B,C,D)=\frac{1}{Z}\psi_{ABC}\psi_{BCD})
2 HMM 前向-后向算法计算 P(x|λ) 前向 α：递推初始化→递推→终止求和；后向 β：初始化→递推→终止
3 HMM 维特比算法求最可能状态序列 递推 δ_t(j) = max_i [δ_{t-1}(i)·a_{ij}]·b_j(o_t) + 回溯
7 贝叶斯网络概率推理 利用因子分解式和变量消元法

综合考点速查

监督学习 vs 无监督学习

监督学习 无监督学习
贝叶斯分类器、SVM、Logistic 回归、决策树、最近邻 K-Means、层次聚类、PCA、高斯混合聚类、密度聚类

生成式模型 vs 判别式模型

生成式（建模联合概率） 判别式（直接建模后验概率）
朴素贝叶斯、HMM、高斯混合模型 SVM、逻辑回归、CNN、线性判别分析

过拟合完整应对策略

方法 类别
获取更多训练数据 数据层面
降低模型复杂度（减少树深度、核参数等） 模型层面
L1/L2 正则化、Dropout、Batch Normalization 正则化
早停（Early Stopping） 训练策略
集成学习（Bagging 降低方差） 集成方法

欠拟合应对策略

方法
添加新特征（特征工程）
增加模型复杂度（更多层、更深树）
减小正则化系数

常用损失函数对照

算法 损失函数
最小二乘/线性回归 Square Loss（平方损失）
SVM Hinge Loss（合页损失）
Logistic 回归 交叉熵损失
AdaBoost 指数损失
SVR ε-不敏感损失

📌 提示：本文档将持续更新，按章节顺序覆盖更多知识点。有问题随时提问！