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

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

---

第 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）的——只能画出与坐标轴平行的横平竖直的线：

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)？	另一条斜线

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）
• 把所有噪声和偶然特性都学进去
• 对新样本几乎毫无预测能力

训练误差 → 0
泛化误差 → 爆炸 💥

缺陷 2：与纯度准则的本质差异

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

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

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

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

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

划分前：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）。

直观理解：

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 求解过程总结

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 核函数本质总结

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 推广层次总结

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）：

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）}
]

公式推导路线图

链式求导路径：

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) 变化：像一片连绵的山脉，有几个”山谷”（局部极小），其中最低的那个山谷才是”海平面”（全局最小）。

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])

网络结构：

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	ε-不敏感损失

---

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