北航2025机器学习期末复习[BUAA-ML]

北航机器学习期末复习

写在前面

ML 是一门23级才加入大二必修的专业课（此前主要是本科大三的选修课和研究生的必修课，但授课老师基本一致），主要学习方式以每周2学时的理论课和4次实验为主，考核方式是期末闭卷考试+团队大作业，本文汇总了北航机器学习期末考试题型和例题，基本涵盖核心知识点。

从往年期末考察的内容和今年题型分布来看，依赖往年题和核心考点拟合的成功率较高，建议结合往年题与PPT内容进行复习。
转载来源：凉宫秋月的文艺部

---

目录

• 贝叶斯决策
• 使用感知机准则求判别函数
• 主成分分析（PCA）
• 支持向量机（SVM）
• K-Means算法和EM算法
• 集成学习
• 决策树
• 反向传播算法
• 开放性试题
• 分类器性能度量

---

贝叶斯决策

【例题】 细胞有正常 ($w_1$)，异常 ($w_2$) 两类，其先验概率为 $P(w_1)=0.9$, $P(w_2)=0.1$。有一个待识别的细胞，观测值为x，现在已知如果细胞是正常的，$P(x|w_1)$ 出现的概率为0.2；如果细胞是异常的，$P(x|w_2)$ 出现的概率是0.4。决策的损失表如下：

决策	$w_1$	$w_2$
$w_1$	0	6
$w_2$	1	0

1. 基于最小错误率原则对待识别细胞进行归类
2. 基于最小风险原则对待识别细胞进行归类

【解答】

1. 基于最小错误率原则
   应用贝叶斯公式：
   已知x，细胞属于$w_1$的概率为：
   $P(w_1|x) = \frac{P(x|w_1)P(w_1)}{P(x|w_1)P(w_1) + P(x|w_2)P(w_2)} = \frac{0.2 \times 0.9}{0.2 \times 0.9 + 0.4 \times 0.1} = \frac{0.18}{0.22} = 0.818$

   已知x，细胞属于$w_2$的概率为：
   $P(w_2|x) = \frac{P(x|w_2)P(w_2)}{P(x|w_1)P(w_1) + P(x|w_2)P(w_2)} = \frac{0.4 \times 0.1}{0.2 \times 0.9 + 0.4 \times 0.1} = \frac{0.04}{0.22} = 0.182$

   因为 $P(w_1|x) > P(w_2|x)$，所以应该决策为$w_1$。

2. 基于最小风险原则
   决策为$w_1$的风险为：
   $R(w_1) = \lambda_{11}P(w_1|x) + \lambda_{12}P(w_2|x) = 0 \times 0.818 + 6 \times 0.182 = 1.092$

   决策为$w_2$的风险为：
   $R(w_2) = \lambda_{21}P(w_1|x) + \lambda_{22}P(w_2|x) = 1 \times 0.818 + 0 \times 0.182 = 0.818$

   因为 $R(w_2) < R(w_1)$，所以应该决策为$w_2$。

---

使用感知机准则求判别函数

【讲解】 问题的格式是：现有样本集 ${x_1, \cdot\cdot\cdot, x_n}$ 属于$w_1, w_2$两类，寻找向量a，使得：$\forall x \in w_1, a^T x > 0,$ 且 $\forall x \in w_2, a^T x < 0$。即使用一个仿射流形把样本分成两半，这时称样本是线性可分的。其具体操作步骤是：

1. 构造规范化增广样本向量。
   这一步的关键是增广和规范化。因为一般线性流形的表达式是 $w^T x+b$ 但是我们要把这个b包含在w里面，就要把样本进行增广。增广的操作步骤是给样本的坐标前面补充1个1。
   规范化的意思是，如果样本是正例(属于$w_1$)，就保持不变；否则，它的每个坐标都变成相反数。
   规范化增广样本向量记作 ${y_1, \cdot\cdot\cdot, y_n}$。

2. 在y集合上循环迭代： 对于每个y，计算$a^T y$，如果 $a_k^T y \le 0,$ 则 $a_{k+1}=a_k+y;$ 否则，$a_{k+1}=a_k$。直到对于某个a，所有的y都满足 $a^T y > 0$，那么这就是最终结果。
   这实际上是梯度下降法的过程，推导略。

【例子】 现有数据集:

1. 类别1: $x_1^T=(-2,2)$, $x_2^T=(-2,-2)$
2. 类别2: $x_3^T=(2,1)$, $x_4^T=(2,-1)$
   初始化权: $a_0^T=(0,2,1)$, 利用感知机准则求判别函数。

【解答】

1. 构造规范化增广样本向量:
   $y_1^T=(1,-2,2)$, $y_2^T=(1,-2,-2)$
   $y_3^T=(-1,-2,-1)$, $y_4^T=(-1,-2,1)$

2. 迭代
   i. $a_1^T y_1=(0,2,1) \cdot (1,-2,2)^T = -2 \le 0,$ $a_2=a_1+y_1=(1,0,3)^T$
   ii. $a_2^T y_2=(1,0,3) \cdot (1,-2,-2)^T = -5 \le 0$, $a_3=a_2+y_2=(2,-2,1)^T$
   iii. $a_3^T y_3=(2,-2,1) \cdot (-1,-2,-1)^T = 1 > 0,$ $a_4=a_3$
   iv. $a_4^T y_4=(2,-2,1) \cdot (-1,-2,1)^T = 3 > 0,$ $a_5=a_4$
   v. $a_5^T y_1=(2,-2,1) \cdot (1,-2,2)^T = 8 > 0,$ $a_6=a_5$
   vi. $a_6^T y_2=(2,-2,1) \cdot (1,-2,-2)^T = 4 > 0,$ $a_7=a_6$
   vii. $a_7^T y_3=(2,-2,1) \cdot (-1,-2,-1)^T = 1 > 0,$ $a_8=a_7$
   viii. $a_8^T y_4=(2,-2,1) \cdot (-1,-2,1)^T = 3 > 0,$ $a_9=a_8$
   至此，对于 $a^T=(2,-2,1)$，所有的y都满足 $a^T y > 0$, 那么这就是最终结果。

---

主成分分析(PCA)

【讲解】 PCA的考法有两种，第一种是基于最大方差准则进行推导，第二种是给你一些二维向量，让你降成一维。

【例题1】 基于最大方差准则推导PCA的方法

【解答1】 问题是把D维数据集 ${x_n}$ 降为1维。定义投影方向为D维向量u，且满足 $u^T u=1$。
则样本均值为 $\overline{x}$，投影后样本均值为 $u^T \overline{x}$。
投影后样本的方差为：
$\frac{1}{N}\sum_{i=1}^{N}(u^T x_i - u^T \overline{x})^2 = u^T (\frac{1}{N}\sum_{i=1}^{N}(x_i - \overline{x})(x_i - \overline{x})^T) u = u^T S u$
其中S是协方差矩阵。那么优化问题为：
$\text{maximize } u^T S u$
$\text{s.t. } u^T u = 1$
利用拉格朗日乘数法，写出其拉格朗日函数：
$L(u,\lambda) = u^T S u + \lambda(1 - u^T u)$
对u求导，并置零，有：
$S u = \lambda u$
这意味着，$\lambda$是S的特征值，u是S的特征向量。当$\lambda$是S最大特征值时，u是对应的特征向量$u_1$，此时方差取到极大值，称为第一主成分。
于是，我们得到利用PCA降维的操作步骤：

1. 计算所有样本点的均值 $\overline{x}$
2. 对所有样本点进行零均值化: $x_i = x_i - \overline{x}$
3. 计算协方差阵: $S = \frac{1}{N}\sum_{i=1}^{N} x_i x_i^T$
4. 计算协方差阵的最大的特征值和与其对应的特征向量u
5. 进行投影: $y=u^T x$

---

最小均方误差准则下的PCA完整推导流程

一、问题设定与基本思想

1. 目标: 将D维数据{x}降维到M维空间 $(M<D)$, 使得重建误差最小。
2. 核心思想: 用M维子空间表示数据时, 舍弃(D-M)个方向上的信息损失最小。

二、数学建模

1. 完整正交基: 设 ${u_1, ..., u_D}$ 是D维空间的标准正交基, 满足 $u_i^T u_j = \delta_{ij}$ (正交归一条件)。
2. 数据表示: 原始数据点可表示为: $x_n = \sum_{i=1}^{D} \alpha_{ni} u_i$, 其中系数 $\alpha_{ni}=x_n^T u_i$。
3. 降维表示: 用前M个基向量表示: $\tilde{x}_n = \sum_{i=1}^{M} z_{ni} u_i + \sum_{i=M+1}^{D} b_i u_i$
   • 前M项: 保留的主成分 ($z_{ni}$ 待定)
   • 后(D-M)项: 常数补偿项 ($b_i$ 待定)

三、优化目标建立

1. 重建误差: $J = \frac{1}{N}\sum_{n=1}^{N} |x_n - \tilde{x}_n|^2$
2. 误差表达式推导: 假设用均值补偿舍弃的维度，即 $b_i = \overline{x}^T u_i$，并令 $z_{ni} = x_n^T u_i$。
   $x_n - \tilde{x}_n = \sum_{i=1}^{D} (x_n^T u_i) u_i - (\sum_{i=1}^{M} (x_n^T u_i) u_i + \sum_{i=M+1}^{D} (\overline{x}^T u_i) u_i)$
   $= \sum_{i=M+1}^{D} ((x_n - \overline{x})^T u_i) u_i$
3. 目标函数化简:
   $J = \frac{1}{N}\sum_{n=1}^{N} |\sum_{i=M+1}^{D} ((x_n - \overline{x})^T u_i) u_i|^2 = \frac{1}{N}\sum_{n=1}^{N} \sum_{i=M+1}^{D} ((x_n - \overline{x})^T u_i)^2$
   $= \sum_{i=M+1}^{D} u_i^T (\frac{1}{N}\sum_{n=1}^{N} (x_n-\overline{x})(x_n-\overline{x})^T) u_i = \sum_{i=M+1}^{D} u_i^T S u_i$
   其中S是协方差矩阵: $S = \frac{1}{N}\sum_{n=1}^{N} (x_n - \overline{x})(x_n - \overline{x})^T$

四、优化求解

1. 带约束优化问题:
   $\min_{u_i} \sum_{i=M+1}^{D} u_i^T S u_i$
   s.t. $u_i^T u_j = \delta_{ij}$
2. 拉格朗日函数:
   $\tilde{J} = \sum_{i=M+1}^{D} u_i^T S u_i + \sum_{i=M+1}^{D} \lambda_i (1 - u_i^T u_i)$
3. 求导得最优条件:
   $\frac{\partial \tilde{J}}{\partial u_i} = 2Su_i - 2\lambda_i u_i = 0 \Rightarrow Su_i = \lambda_i u_i$
4. 解的分析:
   • $u_i$ 必须是S的特征向量。
   • 误差值: $J=\sum_{i=M+1}^{D} \lambda_i$
   • 为使J最小, 应选择S的最小的(D-M)个特征值，这意味着用于构建子空间的前M个基向量$u_i$应该是S的最大的M个特征值对应的特征向量。

---

【例题2】 对以下五个二维向量，利用PCA降为一维
$x_{(1)}=\begin{bmatrix} 2 \\ 5 \end{bmatrix}$, $x_{(2)}=\begin{bmatrix} 3 \\ 3 \end{bmatrix}$, $x_{(3)}=\begin{bmatrix} 5 \\ 4 \end{bmatrix}$, $x_{(4)}=\begin{bmatrix} 4 \\ 6 \end{bmatrix}$, $x_{(5)}=\begin{bmatrix} 6 \\ 2 \end{bmatrix}$

【解答2】

1. 计算样本均值:
   $\overline{x} = \frac{1}{5} \left( \begin{bmatrix} 2 \\ 5 \end{bmatrix} + \begin{bmatrix} 3 \\ 3 \end{bmatrix} + \begin{bmatrix} 5 \\ 4 \end{bmatrix} + \begin{bmatrix} 4 \\ 6 \end{bmatrix} + \begin{bmatrix} 6 \\ 2 \end{bmatrix} \right) = \frac{1}{5} \begin{bmatrix} 20 \\ 20 \end{bmatrix} = \begin{bmatrix} 4 \\ 4 \end{bmatrix}$

2. 零均值化:
   $x'_{(1)}=\begin{bmatrix} -2 \\ 1 \end{bmatrix}$, $x'_{(2)}=\begin{bmatrix} -1 \\ -1 \end{bmatrix}$, $x'_{(3)}=\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, $x'_{(4)}=\begin{bmatrix} 0 \\ 2 \end{bmatrix}$, $x'_{(5)}=\begin{bmatrix} 2 \\ -2 \end{bmatrix}$

3. 计算协方差矩阵:
   $S = \frac{1}{5} \sum_{i=1}^{5} x'_i {x'_i}^T$
   $= \frac{1}{5} \left( \begin{bmatrix} 4 & -2 \\ -2 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & 4 \end{bmatrix} + \begin{bmatrix} 4 & -4 \\ -4 & 4 \end{bmatrix} \right)$
   $= \frac{1}{5} \begin{bmatrix} 10 & -5 \\ -5 & 10 \end{bmatrix} = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}$

4. 计算特征值和特征向量:
   $|S - \lambda I| = (2-\lambda)^2 - 1 = 0 \Rightarrow \lambda^2 - 4\lambda + 3 = 0 \Rightarrow (\lambda-3)(\lambda-1) = 0$
   最大的特征值为 $\lambda_1=3$。
   $(S-3I)u = \begin{bmatrix} -1 & -1 \\ -1 & -1 \end{bmatrix} u = 0 \Rightarrow u_1 + u_2 = 0$.
   对应的单位特征向量为: $u = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix}$ or $\begin{bmatrix} -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix}$

5. 进行投影:
   $y = u^T x'$

---

【例题3】 简述PCA和Fisher准则的区别
【解答3】 (以下文字是AI生成的)
PCA(主成分分析)和Fisher准则(Fisher线性判别分析)都是降维技术,但它们的目标和方法有所不同:

1. 目标不同:
   • PCA: 主要目的是数据压缩和特征提取,通过正交变换将数据转换到新的坐标系,使得数据的任何投影的第一大方差在第一个坐标(称为第一主成分)上,第二大方差在第二个坐标上,依此类推。PCA不涉及监督学习,即不考虑数据的标签信息。
   • Fisher准则: 是一种监督学习的降维技术,目的是寻找最佳的投影方向,使得不同类别的数据在该方向上的距离尽可能远,而同类数据尽可能近。它利用了数据的类别标签信息。
2. 方法不同:
   • PCA: 通过协方差矩阵的特征值和特征向量来确定主成分,选择的是数据方差最大的方向。
   • Fisher准则: 通过最大化类间散度与类内散度的比值来确定最佳投影方向,选择的是区分不同类别最有效的方向。
3. 应用场景不同:
   • PCA: 适用于无监督学习场景,比如数据压缩、去噪等。
   • Fisher准则: 适用于监督学习场景,尤其是分类问题中的特征提取和降维。
4. 对数据的要求不同:
   • PCA: 对数据的分布没有特别的要求,可以处理各种类型的数据。
   • Fisher准则: 要求数据是分类的,需要知道每个数据点的类别标签。

总结来说,PCA是一种无监督的降维方法,关注于数据的方差;而Fisher准则是一种监督的降维方法,关注于类别的区分度。

---

支持向量机

【来源】 参考文献1、2、3、4、5

【讲解】 支持向量机的考法一般是让你简述一下原理,然后问一下软间隔和核函数。

【例题】 SVM的基本思想,模型表达式,软间隔和硬间隔的物理含义,如何用来解决非线性问题

【解答】
对于分类问题：在空间中找一个超平面，最大化地分开不同数据点。对于样本 ${x_i, t_i}$，其中$x_i$是空间中的点，$t_i \in \{-1, 1\}$是标签。找一个分类器 $y(x) = w^T x + b$, 使得:
$t_i = \begin{cases} 1, & y(x_i) > 0 \\ -1, & y(x_i) < 0 \end{cases}$
为了鲁棒性，我们要求 $t_i(w^T x_i + b) \ge 1$。
SVM的思想是，寻找一个超平面，使其两端的空白区（margin）最大。间隔为 $\frac{2}{|w|}$。最大化间隔等价于最小化 $|w|$。

硬间隔SVM:
问题等价为：
$\min_{w,b} \frac{1}{2} w^T w$
s.t. $t_i(w^T x_i + b) \ge 1$
这就是SVM的基本型。利用拉格朗日乘数法，可以写出其对偶问题:
$\max_{\alpha} \left( \sum_{i=1}^{N} \alpha_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j t_i t_j x_i^T x_j \right)$
s.t. $\alpha_i \ge 0$
$\sum_{i=1}^{N} \alpha_i t_i = 0$
其中 $w = \sum_{n=1}^{N} \alpha_n t_n x_n$ and b可以从支持向量（即$\alpha_i>0$的样本）中解出。

软间隔SVM与非线性问题:

• 软间隔: 当数据有噪声或者不是线性可分时，硬间隔的条件无法满足。这时可以用软间隔法。对于每一个样本引入一个松弛变量 $\xi_i \ge 0$，原始问题变成：
  $\min_{w,b,\xi} \frac{1}{2} w^T w + C \sum_{i=1}^N \xi_i$
  s.t. $t_i(w^T x_i + b) \ge 1 - \xi_i$
  $\xi_i \ge 0$
  对偶问题中的约束变为 $0 \le \alpha_i \le C$。参数C是惩罚项，控制着对误分类样本的惩罚程度。

• 核技巧: 应对非线性可分问题的另一种方法。如果 ${x_i, t_i}$ 不是线性可分的，则可能存在一个映射 $\phi: \mathbb{R}^d \rightarrow \mathbb{R}^{d'}$, 使得 ${\phi(x_i), t_i}$ 在 $\mathbb{R}^{d'}$ 中是线性可分的，其中一般有 $d' \ge d$。此时，SVM的对偶问题变为：
  $\max_{\alpha} \left( \sum_{i=1}^{N} \alpha_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j t_i t_j \phi^T(x_i)\phi(x_j) \right)$
  s.t. $0 \le \alpha_i \le C$
  $\sum_{i=1}^{N} \alpha_i t_i = 0$
  所谓的核技巧，就是寻找一个函数 $k(x_i, x_j)$，使得 $k(x_i, x_j) = \phi^T(x_i)\phi(x_j)$，且计算$k(x_i, x_j)$的复杂度远低于先计算$\phi(x)$再做内积。这样就能够高效地在更高维空间中寻找分界。常用的核有：

  1. 线性核: $k(x_i, x_j) = x_i^T x_j$
  2. 多项式核: $k(x_i, x_j) = (\gamma x_i^T x_j + c)^d$
  3. 高斯核 (RBF核): $k(x_i, x_j) = \exp(-\gamma|x_i - x_j|^2)$

---

K-Means算法和EM算法

【讲解】 一般都是考概念题,问你K均值算法、高斯混合模型、EM算法分别是什么,有什么改进空间等。

K均值算法 (K-Means)

定义: 给定D维空间上的数据集 $X=\{x_1, ..., x_N\}$，这些数据对应类别未知。K均值算法将数据集划分成K个簇，每个簇有一个聚类中心 $\mu_k$, 并将每一个样本 $x_n$ 划归到离该样本最近的聚类中心。

K均值算法的一般流程:

1. 初始化: 随机选择K个样本点作为初始聚类中心 $\mu_1, ..., \mu_k$。
2. E-step (分配): 将每个数据点划分给最近的聚类中心。用$r_{nk}=1$表示$x_n$属于簇k，否则为0。
   $r_{nk} = \begin{cases} 1 & \text{if } k = \arg\min_j |x_n - \mu_j|^2 \\ 0 & \text{otherwise} \end{cases}$
3. M-step (更新): 重新计算每个簇的中心。最小化准则函数 $J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} |x_n - \mu_k|^2$。对 $\mu_k$ 求导并置零可得：
   $\frac{\partial J}{\partial \mu_k} = 2\sum_{n=1}^{N} r_{nk}(x_n - \mu_k) = 0 \Rightarrow \mu_k = \frac{\sum_n r_{nk}x_n}{\sum_n r_{nk}}$
4. 迭代: 重复步骤2和3, 直到满足终止条件(聚类中心不再发生显著变化或达到最大迭代次数)。

K-means的改进

• K-means++

  • 基本思想: 针对K-means的簇中心初始化做了改进。假设已选取了n个初始聚类中心(0 < n < k)，在选取第n+1个中心时，距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。具体来说，选择下一个中心$x$的概率正比于$D(x)^2$，其中$D(x)$是点x到已选中心的最短距离。这使得初始聚类中心互相离得更远。

• Kernel K-means

  • 基本思想: 传统K-means采用欧式距离进行样本间的相似度度量，这并不适用于所有数据集。参照SVM中核函数的思想，将所有样本映射到另外一个特征空间(一般为高维)中再进行聚类。

高斯混合模型 (GMM)

定义: GMM是一种统计模型, 用于表示一组数据是由多个高斯分布混合而成的。GMM是多个高斯分布的线性组合，每个高斯分布称为一个混合成分，每个混合成分都有一个对应的混合系数(先验概率)，所有混合系数的和为1。
$p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x | \mu_k, \Sigma_k)$, 其中 $\sum_{k=1}^{K} \pi_k = 1$
GMM能够捕捉数据的多峰特性，广泛应用于聚类分析、图像分割等领域。

EM算法 for GMM

使用期望最大化(EM)算法来估计GMM的参数($\pi_k, \mu_k, \Sigma_k$)。

1. 初始化: 初始化 $\mu_k, \Sigma_k, \pi_k$。
2. E-step (期望): 计算每个数据点$x_n$由每个分量k生成的后验概率(也称为“责任” $\gamma(z_{nk})$)。
   $\gamma(z_{nk}) = p(k|x_n) = \frac{\pi_k \mathcal{N}(x_n|\mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \mathcal{N}(x_n|\mu_j, \Sigma_j)}$
3. M-step (最大化): 使用E-step中计算的责任来更新模型参数。
   • $N_k = \sum_{n=1}^{N} \gamma(z_{nk})$ (每个分量的有效点数)
   • $\mu_k^{new} = \frac{1}{N_k} \sum_{n=1}^{N} \gamma(z_{nk}) x_n$
   • $\Sigma_k^{new} = \frac{1}{N_k} \sum_{n=1}^{N} \gamma(z_{nk}) (x_n - \mu_k^{new})(x_n - \mu_k^{new})^T$
   • $\pi_k^{new} = \frac{N_k}{N}$
4. 迭代: 重复E-step和M-step直到对数似然函数收敛。最终结果可能依赖于初始值，可以多次初始化取最好的结果。

---

集成学习

【例题】 简述集成学习的基本思想,简述Boosting和Bagging的原理和区别

【解答】
基本思想: 集成学习通过构建并结合多个学习器来完成学习任务，以获得比单一学习器更优的泛化性能。其关键是如何产生「好而不同」的个体学习器。

Bagging (Bootstrap Aggregating):

• 原理: Bagging是并行方法。它基于自主采样法(bootstrap sampling)，即从原始训练集中有放回地抽取样本，构造T个含m个样本的采样集。基于每个采样集独立地训练一个基学习器，最后将这些学习器进行组合（分类任务用投票，回归任务用平均）。随机森林是Bagging的一个扩展变体。
• 特点:
  • 关注于降低方差。
  • 基学习器之间没有强依赖，可以并行生成。
  • 对于不稳定的学习算法（如决策树）效果较好。
  • 无法显著降低偏差。

Boosting:

• 原理: Boosting是串行方法。它序贯地训练一系列基学习器，每个新的学习器都重点关注之前学习器学错的样本。具体做法是，先训练一个学习器，然后根据其表现调整训练样本的分布（或权重），使得先前错分的样本在后续训练中得到更多关注。如此重复，直到获得足够多的学习器，最后进行加权组合。AdaBoost是Boosting的代表算法。
• 特点:
  • 关注于降低偏差。
  • 个体学习器之间有强依赖关系，必须串行生成。
  • 通常使用弱学习器（性能略好于随机猜测），如浅层决策树。
  • 对噪声数据较为敏感。

区别总结:

1. 样本选择: Bagging采用有放回的随机采样；Boosting的每一轮训练样本是根据上一轮的学习结果进行调整的。
2. 学习器关系: Bagging的学习器是并行的、相互独立的；Boosting的学习器是串行的、相互依赖的。
3. 主要目标: Bagging主要减少方差；Boosting主要减少偏差。
4. 权重: Bagging的所有学习器权重相等（在投票或平均时）；Boosting的学习器有不同的权重，表现好的学习器权重更大。

---

决策树

【讲解】 考法是使用ID3构造决策树,然后简述预剪枝和后剪枝法。

【例题1】 用ID3算法对下面的数据集进行分类,根据星球的大小和轨道判断其是否宜居:

数量	大小	轨道	是否宜居
30	大	远	是
130	大	近	是
48	小	远	是
161	小	近	是
20	大	远	否
170	大	近	否
11	小	远	否
230	小	近	否

【解答】
总样本数 D = 30+130+48+161+20+170+11+230 = 800
宜居 (是): 30+130+48+161 = 369
不宜居 (否): 20+170+11+230 = 431

1. 计算根节点总信息熵:
   $H(D) = -(\frac{369}{800}\log_2\frac{369}{800} + \frac{431}{800}\log_2\frac{431}{800}) \approx 0.9957$

2. 计算属性"大小"的信息增益:

   • 大小=大: 总数 30+130+20+170 = 350. 是: 160, 否: 190.
     $H(D^{大}) = -(\frac{160}{350}\log_2\frac{160}{350} + \frac{190}{350}\log_2\frac{190}{350}) \approx 0.9947$
   • 大小=小: 总数 48+161+11+230 = 450. 是: 209, 否: 241.
     $H(D^{小}) = -(\frac{209}{450}\log_2\frac{209}{450} + \frac{241}{450}\log_2\frac{241}{450}) \approx 0.9963$
   • 条件熵: $H(D|大小) = \frac{350}{800}H(D^{大}) + \frac{450}{800}H(D^{小}) \approx 0.4375 \times 0.9947 + 0.5625 \times 0.9963 \approx 0.9956$
   • 信息增益: $G(D, 大小) = H(D) - H(D|大小) \approx 0.9957 - 0.9956 = 0.0001$

3. 计算属性"轨道"的信息增益:

   • 轨道=远: 总数 30+48+20+11 = 109. 是: 78, 否: 31.
     $H(D^{远}) = -(\frac{78}{109}\log_2\frac{78}{109} + \frac{31}{109}\log_2\frac{31}{109}) \approx 0.8614$
   • 轨道=近: 总数 130+161+170+230 = 691. 是: 291, 否: 400.
     $H(D^{近}) = -(\frac{291}{691}\log_2\frac{291}{691} + \frac{400}{691}\log_2\frac{400}{691}) \approx 0.9820$
   • 条件熵: $H(D|轨道) = \frac{109}{800}H(D^{远}) + \frac{691}{800}H(D^{近}) \approx 0.13625 \times 0.8614 + 0.86375 \times 0.9820 \approx 0.9656$
   • 信息增益: $G(D, 轨道) = H(D) - H(D|轨道) \approx 0.9957 - 0.9656 = 0.0301$

4. 选择第一个节点:
   因为 $G(D, 轨道) > G(D, 大小)$, 所以选择"轨道"作为根节点。

5. 对子节点进行划分:

   • T1 (轨道=近):
     • 样本集: 691个. 是: 291, 否: 400.
     • 因为 “否” (400) > “是” (291), 该分支下的样本多数为不宜居。如果我们不再划分，将此叶节点标记为“不宜居”。
   • T2 (轨道=远):
     • 样本集: 109个. 是: 78, 否: 31.
     • 因为 “是” (78) > “否” (31), 该分支下的样本多数为宜居。如果我们不再划分，将此叶节点标记为“宜居”。

如果这是一个简单的树，可以就此停止。* 在 T1 (轨道=近) 分支下, “大小=大” -> 是:130, 否:170 (多数为否); “大小=小” -> 是:161, 否:230 (多数为否)。
* 在 T2 (轨道=远) 分支下, “大小=大” -> 是:30, 否:20 (多数为是); “大小=小” -> 是:48, 否:11 (多数为是)。

由于两个子节点的多数类别已经确定，且在该子节点下根据另一属性划分后，其子节点的多数类别不变，我们可以将树构建如下：

---

ID3算法的问题与改进

• 信息增益的问题: 信息增益准则对可取值数目较多的属性有所偏好。例如，如果用“编号”作为属性，每个样本一个编号，那么每个分支都只包含一个样本（纯度最高），信息增益会是最大的，但这显然是不合理的。
• 增益率 (C4.5算法): 为了缓解这个问题，C4.5算法使用增益率来选择属性。
  $G_{ratio}(D, a) = \frac{G(D, a)}{H(a)}$
  其中 $H(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$ 称为属性a的“固有值”。属性a的取值越多，其固有值$H(a)$通常也越大，从而对信息增益进行惩罚。

---

【例题2】 描述预剪枝法和后剪枝法的方法和优缺点
【解答】 (以下内容由AI生成)

预剪枝法 (Pre-pruning)

• 具体方法: 预剪枝是在决策树生成的过程中,对每个节点在划分前先进行估计,如果当前节点的划分不能带来决策树泛化性能提升(例如，在验证集上的准确率没有提升),则停止划分,并将当前节点标记为叶子节点。常见的预剪枝策略包括限制树的最大深度、限制叶节点的最小样本数量、限制节点划分所需的最小信息增益等。
• 优点:
  1. 降低过拟合风险:通过限制树的生长,减少过拟合的可能性。
  2. 减少训练和测试时间:由于树的生长被提前终止,可以减少模型的训练和预测时间。
• 缺点:
  1. 欠拟合风险:由于提前停止树的生长,可能会错过一些对模型性能有益的分支,导致模型欠拟合。
  2. 视野效应问题:可能在当前划分看似不能提升性能的情况下,进一步的扩展能够显著提高性能,预剪枝会导致算法过早停止。

后剪枝法 (Post-pruning)

• 具体方法: 后剪枝是在决策树完全生长之后进行的剪枝,它首先生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升(例如，在验证集上准确率提升),则将该子树替换为叶结点。常见的后剪枝方法包括错误率降低剪枝(REP)、悲观错误剪枝(PEP)、代价复杂度剪枝(CCP)等。
• 优点:
  1. 泛化性能通常优于预剪枝:后剪枝保留了更多的分支,使得模型有更大的空间去学习和适应数据的复杂模式。
  2. 减少欠拟合风险:相较于预剪枝,后剪枝的欠拟合风险更小。
• 缺点:
  1. 训练时间开销大:后剪枝需要在生成完全决策树之后进行剪枝,因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
  2. 计算资源需求高:由于需要在完整的决策树上进行剪枝操作,后剪枝需要更多的计算资源。

---

反向传播算法

【讲解】
首先记住这个神经元的基本结构,尤其记住各个符号的含义:

1. $x_i$: 前一层的输入
2. $w_i$: 权值, 也是神经网络训练的目标
3. $\sum$: 求和器
4. $\theta$: 求和器阈值 (或偏置b, $a=\sum x_i w_i + b$)
5. $a$: 净激活，$a = \sum_{i=1}^{N} x_i w_i - \theta$
6. $f$: 激活函数, 就是ReLU、Sigmoid之类的
7. $y$: 神经元输出，$y=f(a)$

之后的神经网络图中,每一个「圆点」,其实都暗含了这些东西。

算法思想
反向传播算法基于梯度下降，目的是最小化损失函数，如均方误差:
$E(w) = \frac{1}{2}\sum_{n=1}^{N} (y(x_n, w) - t_n)^2$
算法可以分为两个阶段：

1. 前馈(正向过程): 从输入层经隐层逐层正向计算各单元的输出。
2. 学习(反向过程): 由输出误差逐层反向计算隐层各单元的误差梯度,并用此误差梯度更新前层的权值。

梯度计算 (链式法则)
考虑从j层到k层的权重 $w_{kj}$。损失E对$w_{kj}$的偏导为：
$\frac{\partial E_n}{\partial w_{kj}} = \frac{\partial E_n}{\partial a_k} \frac{\partial a_k}{\partial w_{kj}}$
我们定义误差项 $\delta_k = \frac{\partial E_n}{\partial a_k}$。因为 $a_k = \sum_j w_{kj} y_j$，所以 $\frac{\partial a_k}{\partial w_{kj}} = y_j$ (其中$y_j$是j层神经元的输出)。
因此: $\frac{\partial E_n}{\partial w_{kj}} = \delta_k y_j$

• 对于输出层节点k:
  $\delta_k = \frac{\partial E_n}{\partial a_k} = \frac{\partial E_n}{\partial y_k} \frac{\partial y_k}{\partial a_k} = (y_k - t_k) f'(a_k)$
• 对于隐藏层节点j:
  $\delta_j = \frac{\partial E_n}{\partial a_j} = (\sum_{k} \frac{\partial E_n}{\partial a_k} \frac{\partial a_k}{\partial a_j}) = (\sum_{k} \delta_k w_{kj}) f'(a_j)$

权重更新:
$w_{ji}^{(\tau+1)} = w_{ji}^{(\tau)} - \eta \frac{\partial E}{\partial w_{ji}^{(\tau)}} = w_{ji}^{(\tau)} - \eta \delta_j y_i$
其中 $\eta$ 是学习率。

一个有用的结论: 如果激活函数是Sigmoid函数 $\sigma(x) = \frac{1}{1+e^{-x}}$, 那么它的导数是 $\sigma'(x) = \sigma(x)(1-\sigma(x))$。

---

【例题1】
包含一层隐藏层的前馈神经网络如图所示,给定训练集 $D=\{(x_n, t_n)\}$, $x_n \in \mathbb{R}^D, t_n \in \mathbb{R}^K$。隐藏层激活函数为h，输出层激活函数为$\sigma$。准则函数为 $E_n(w) = \frac{1}{2}\sum_{k=1}^{K} (y_{nk} - t_{nk})^2$。网络包含D个输入神经元, M个隐层神经元, K个输出神经元。试推导反向传播算法中对每一层权值参数 $(w_{md}^{(1)}, w_{km}^{(2)})$ 的更新表达式。

【解答1】

1. 前向传播:

   • 隐层输入: $a_m = \sum_{d=0}^{D} w_{md}^{(1)} x_d$
   • 隐层输出: $z_m = h(a_m)$
   • 输出层输入: $a_k = \sum_{m=0}^{M} w_{km}^{(2)} z_m$
   • 网络输出: $y_{nk} = \sigma(a_k)$

2. 反向传播 (计算误差项 $\delta$)

   • 输出层 $\delta_k$:
     $\delta_k = \frac{\partial E_n}{\partial a_k} = \frac{\partial E_n}{\partial y_{nk}} \frac{\partial y_{nk}}{\partial a_k} = (y_{nk} - t_{nk}) \sigma'(a_k)$
   • 隐藏层 $\delta_m$:
     $\delta_m = \frac{\partial E_n}{\partial a_m} = (\sum_{k=1}^K \frac{\partial E_n}{\partial a_k} \frac{\partial a_k}{\partial a_m}) = (\sum_{k=1}^K \delta_k \frac{\partial a_k}{\partial z_m} \frac{\partial z_m}{\partial a_m}) = (\sum_{k=1}^K \delta_k w_{km}^{(2)}) h'(a_m)$

3. 计算梯度:

   • 输出层权重 $w_{km}^{(2)}$:
     $\frac{\partial E_n}{\partial w_{km}^{(2)}} = \frac{\partial E_n}{\partial a_k} \frac{\partial a_k}{\partial w_{km}^{(2)}} = \delta_k z_m$
   • 隐藏层权重 $w_{md}^{(1)}$:
     $\frac{\partial E_n}{\partial w_{md}^{(1)}} = \frac{\partial E_n}{\partial a_m} \frac{\partial a_m}{\partial w_{md}^{(1)}} = \delta_m x_d$

4. 权重更新:

   • $\Delta w_{km}^{(2)} = -\eta \frac{\partial E_n}{\partial w_{km}^{(2)}} = -\eta \delta_k z_m = -\eta (y_{nk} - t_{nk}) \sigma'(a_k) z_m$
   • $\Delta w_{md}^{(1)} = -\eta \frac{\partial E_n}{\partial w_{md}^{(1)}} = -\eta \delta_m x_d = -\eta (\sum_{k=1}^K \delta_k w_{km}^{(2)}) h'(a_m) x_d$

---

【例题2】
考虑只有一个神经元的多层神经网络，其中 $x_{i+1} = \sigma(w_i x_i + b_i)$ (i∈[1, 4]), C=Loss($x_5$), $\sigma$ 表示sigmoid函数 $f(x)=1/(1+e^{-x})$, 且 $|w_i|<1$。假设已知 $\frac{\partial C}{\partial x_5}$ 推导 $\frac{\partial C}{\partial b_i}$ (i∈[1,4]), 并阐述当神经网络层数过深时, 梯度消失的原因。

【解答2】
令 $z_i = w_i x_i + b_i$, 则 $x_{i+1} = \sigma(z_i)$。

1. 推导 $\frac{\partial C}{\partial b_i}$
   使用链式法则：

   • $\frac{\partial C}{\partial b_4} = \frac{\partial C}{\partial x_5} \frac{\partial x_5}{\partial z_4} \frac{\partial z_4}{\partial b_4} = \frac{\partial C}{\partial x_5} \sigma'(z_4) \cdot 1 = \frac{\partial C}{\partial x_5} \sigma'(z_4)$
   • $\frac{\partial C}{\partial b_3} = \frac{\partial C}{\partial x_5} \frac{\partial x_5}{\partial x_4} \frac{\partial x_4}{\partial z_3} \frac{\partial z_3}{\partial b_3} = \frac{\partial C}{\partial x_5} (\frac{\partial x_5}{\partial z_4} \frac{\partial z_4}{\partial x_4}) \sigma'(z_3) = \frac{\partial C}{\partial x_5} \sigma'(z_4) w_4 \sigma'(z_3)$
   • $\frac{\partial C}{\partial b_2} = \frac{\partial C}{\partial x_5} \frac{\partial x_5}{\partial x_4} \frac{\partial x_4}{\partial x_3} \frac{\partial x_3}{\partial z_2} \frac{\partial z_2}{\partial b_2} = \frac{\partial C}{\partial x_5} (\sigma'(z_4)w_4) (\sigma'(z_3)w_3) \sigma'(z_2)$
   • $\frac{\partial C}{\partial b_1} = \frac{\partial C}{\partial x_5} (\sigma'(z_4)w_4) (\sigma'(z_3)w_3) (\sigma'(z_2)w_2) \sigma'(z_1)$

2. 梯度消失的原因
   Sigmoid函数的导数 $\sigma'(z) = \sigma(z)(1-\sigma(z))$。其最大值在z=0时取到，为 $\sigma'(0) = 0.5 \times (1-0.5) = 0.25$。
   因此，$\sigma'(z) \le 0.25$。
   在上面的推导中，$\frac{\partial C}{\partial b_1}$ 的表达式包含了一系列 $\sigma'(z_i)$ 和 $w_i$ 的乘积。
   $\frac{\partial C}{\partial b_1} = \frac{\partial C}{\partial x_5} \prod_{i=1}^{3} w_{i+1}\sigma'(z_{i+1}) \cdot \sigma'(z_1)$
   由于题目给定 $|w_i| < 1$ 且 $\sigma'(z_i) \le 0.25$, 这个连乘项 $(w_i \sigma'(z_i))$ 的绝对值远小于1。当网络层数过深时，这个乘积会变得非常小，趋近于0。
   这就导致了靠近输入层的梯度（如 $\frac{\partial C}{\partial b_1}$）会变得非常小，使得这些层的权重更新极其缓慢，几乎不学习，这就是梯度消失现象。

---

开放性试题

【来源】 参考文献1、2、3、4、5

【例题1】 谈谈你对深度学习的理解,深度学习模型存在什么问题,你觉得深度学习未来会往什么方向发展。
【解答1】 (以下解答由AI生成)

• 我对深度学习的理解
  深度学习是机器学习的一个子领域,它基于人工神经网络的学习算法,特别是那些具有多个非线性变换的层(即“深度”)。这些层可以学习数据的复杂模式和层次化表示。深度学习模型能够自动从原始数据中提取特征(表示学习),而不需要人为设计特征提取器。这种能力使得深度学习在图像识别、语音识别、自然语言处理等领域取得了革命性的进展。

• 深度学习模型存在的问题

  1. 数据需求: 深度学习模型通常需要大量的标注数据来训练,这在某些领域(如医疗图像分析)可能是不切实际的。
  2. 可解释性: 深度学习模型通常被认为是“黑箱”,因为它们的决策过程缺乏透明度,难以解释。
  3. 计算资源: 训练深度学习模型需要大量的计算资源(GPU/TPU),这可能导致成本高昂和能源消耗问题。
  4. 过拟合: 在有限的数据集上训练时,深度学习模型可能会过拟合,即在训练数据上表现很好,但在未见过的数据上表现差。
  5. 对抗性脆弱性: 深度学习模型可能对精心设计的输入(对抗性样本)非常敏感,这些输入可以导致模型做出错误的预测。

• 深度学习未来的发展方向

  1. 更少的数据需求: 研究如何使用更少的数据来训练有效的模型,例如通过小样本学习、自监督学习、迁移学习和数据增强技术。
  2. 提高可解释性 (XAI): 使模型的决策过程更加透明和可理解，建立对模型的信任。
  3. 节能和效率 (Green AI): 寻找更节能的算法和硬件来训练和部署深度学习模型。
  4. 对抗性鲁棒性: 提高模型对对抗性攻击的鲁棒性,以确保模型在现实世界中的可靠性。
  5. 自动机器学习 (AutoML): 自动化深度学习模型的设计(网络结构搜索)、训练和调参过程。
  6. 多模态学习: 结合来自不同来源（如文本、图像、声音）的信息进行学习。
  7. 伦理和公平性: 确保模型的公平性,避免因数据偏见导致歧视性决策。

---

分类器性能度量

混淆矩阵、查准率、查全率、F1

1. 混淆矩阵(Confusion Matrix)
   定义:用于描述分类模型预测结果与真实标签的匹配情况,尤其适用于二分类问题(正例P/负例N)。

真实标签 \ 预测结果	预测正例	预测负例
真实正例 §	TP (真正例)	FN (假负例)
真实负例 (N)	FP (假正例)	TN (真负例)

• TP (True Positive): 真实为正例,预测为正例 (正确分类)
• FN (False Negative): 真实为正例,预测为负例 (漏报, 第II类错误)
• FP (False Positive): 真实为负例,预测为正例 (误报, 第I类错误)
• TN (True Negative): 真实为负例,预测为负例 (正确分类)

2. 查准率(Precision)与查全率(Recall)

   • 查准率 (Precision): 衡量预测为正例的样本中真正正例的比例。
     $Precision = \frac{TP}{TP + FP}$
   • 查全率 (Recall): 衡量真实正例中被正确预测的比例 (也叫灵敏度, Sensitivity)。
     $Recall = \frac{TP}{TP + FN}$
   • 二者关系 (Trade-off): 查准率和查全率通常是相互矛盾的。提高查准率（要求更严格地判断为正例）可能会导致一些不那么确定的正例被漏掉，从而降低查全率。反之亦然。
     • 高查准率需求: 垃圾邮件过滤 (宁可漏判, 不可误判正常邮件)。
     • 高查全率需求: 疾病筛查 (宁可误判, 不可漏掉真实患者)。

3. F1 度量 (F1-Score)
   定义:查准率与查全率的调和平均数,综合评估模型性能(尤其适用于不均衡数据)。
   $F_1 = \frac{2 \times Precision \times Recall}{Precision + Recall} = \frac{2TP}{2TP + FP + FN}$

---

生成式模型 vs. 判别式模型

• 生成式模型 (Generative Models)

  • 思想: 学习数据的联合概率分布 $P(X, Y)$。可以通过贝叶斯公式得到后验概率 $P(Y|X)$来进行分类。
  • 例子: 朴素贝叶斯, 高斯混合模型(GMM), 隐马尔可夫模型(HMM)。
  • 优点:
    • 可以生成新的数据样本。
    • 能够处理缺失数据。
    • 信息更丰富，能反映数据本身的分布。
  • 缺点:
    • 学习过程更复杂，需要更多数据。
    • 为了拟合分布，可能会牺牲一些分类性能。

• 判别式模型 (Discriminative Models)

  • 思想: 直接学习决策函数 $f(X)$ 或者条件概率分布 $P(Y|X)$。
  • 例子: 逻辑回归, 支持向量机(SVM), 决策树, 传统神经网络。
  • 优点:
    • 学习目标明确，直接面向分类任务，性能通常更好。
    • 学习过程更简单，需要的数据量相对较少。
    • 分类边界更灵活。
  • 缺点:
    • 无法生成数据。
    • 不能反映数据本身的特性。

关系: 由生成模型可以得到判别模型，但反之不行。

---

分类器准则与方法总结

1. Fisher准则 (线性判别分析, LDA)

• 核心思想: 将高维样本投影到一条直线上, 使得同类样本的投影点尽可能密集(类内离散度最小), 不同类样本的投影中心点尽可能分离(类间离散度最大)。
• 数学表达: 最大化目标函数 $J\_F(w) = \\frac{w^T S\_b w}{w^T S\_w w}$
• 特点: 监督学习，为分类任务寻找最佳投影方向，对数据分布有高斯假设。

2. 感知机准则

• 核心思想: 通过迭代修正权向量，直到所有样本被正确分类。每次用一个错分样本来更新权向量。
• 数学表达: 最小化错分样本的目标函数 $J_P(a) = \sum_{y \in \mathcal{Y}_{wrong}} (-a^T y)$。
• 特点: 仅适用于线性可分数据，解不唯一，不收敛于线性不可分数据。

3. 最小二乘准则

• 核心思想: 最小化模型预测值与真实标签的平方误差和。
• 数学表达: 最小化 $J_S(a) = |Ya-b|^2$, 有解析解 $a^*=(Y^T Y)^{-1}Y^T b$。
• 特点: 计算简单，有解析解，但对异常值敏感。

4. 逻辑回归 (Logistic Regression)

• 核心思想: 用Sigmoid函数将线性组合映射到(0,1)区间, 输出样本属于正类的概率。通过最大化对数似然函数求解参数。
• 数学表达: 模型 $P(y=1|x) = \frac{1}{1+e^{-w^T x}}$，损失函数为交叉熵。
• 特点: 输出具有概率意义，决策边界是线性的。

5. 支持向量机 (SVM)

• 核心思想: 寻找一个最大化分类间隔的超平面(硬间隔)。对线性不可分数据, 引入松弛变量(软间隔)或核技巧映射到高维空间。
• 数学表达: 目标函数 $\min_{w,b} \frac{1}{2}|w|^2 + C\sum\xi_i$
• 特点: 泛化能力强，通过核技巧能有效处理非线性问题，对噪声鲁棒。

六大分类器准则/方法的核心区别

准则/方法	优化目标	适用条件	输出特性	主要局限
Fisher准则	类间方差/类内方差最大化	二分类、线性可分	线性投影方向	假设协方差同质, 对分布敏感
感知机准则	最小化错分样本距离	严格线性可分	线性超平面	解不唯一; 线性不可分不收敛
最小二乘准则	最小化平方误差和	线性可分/不可分	线性超平面	对异常值敏感; 无概率输出
逻辑回归	最大化对数似然函数	线性可分/不可分	概率输出+线性边界	无法直接处理非线性数据
SVM(线性)	最大化分类间隔	线性可分/不可分	线性超平面	大规模数据计算慢
SVM(核方法)	高维空间最大化间隔	非线性数据	非线性决策边界	核函数选择与调参复杂