1. 决策树基本原理#

• 概念：决策树是一种常用的监督学习分类方法，它通过一系列if-then规则对数据进行分类，其模型结构呈树状，非常直观且易于解释。
• 基本结构：
  • 根节点 (Root Node)：包含整个数据集，是决策的起始点。
  • 内部节点 (Internal Node)：代表一个特征或属性的测试。
  • 分支 (Branch)：代表内部节点上特征测试的每个可能结果。
  • 叶子节点 (Leaf Node)：代表一个类别标签，是决策的最终结果。
• 预测过程：对于一个待分类的样本，决策过程从根节点开始，根据样本在当前节点的特征值，选择对应的分支下行，到达下一个节点，重复此过程，直到抵达一个叶子节点，该叶子节点的类别即为样本的预测类别。
• 训练（构建）过程：训练决策树是一个递归地选择最优特征并根据该特征对数据集进行分割，从而构建树的过程。主要包括三个阶段：
  1. 特征选择：决定用哪个特征来划分当前的数据集。
  2. 决策树生成：根据选定的特征递归地生成子树。
  3. 决策树剪枝：防止模型过拟合，提升泛化能力。

2. 最优特征选择准则#

选择最优特征的核心思想是，希望经过划分后，各个子集中的样本尽可能属于同一类别，即子集的纯度越来越高。

• 信息熵 (Entropy)

  • 熵是度量随机变量不确定性或样本集纯度的指标。熵越大，不确定性越大，纯度越低。
  • 对于一个数据集 D，其信息熵的计算公式为： $$H(D) = -\sum_{i=1}^{k} p_i \log_2 p_i$$ 其中，$k$ 是类别的数量，$p_i$ 是第 $i$ 类样本所占的比例。

• 信息增益 (Information Gain)

  • 定义：信息增益指得知特征 A 的信息后，使得数据集 D 的信息不确定性减少的程度。它等于划分前的信息熵减去划分后的条件熵。
  • 计算公式： $$g(D, A) = H(D) - H(D|A)$$ 其中，$H(D)$ 是划分前数据集 D 的熵，$H(D|A)$ 是在已知特征 A 的条件下 D 的条件熵，计算方式为： $$H(D|A) = \sum_{v=1}^{n} \frac{|D^v|}{|D|} H(D^v)$$ 这里特征 A 有 $n$ 个可能的取值， $D^v$ 是 D 中特征 A 取值为 $v$ 的样本子集。
  • 应用：ID3 算法使用信息增益作为特征选择的标准。选择信息增益最大的特征进行划分。

• 信息增益比 (Gain Ratio)

  • 动机：信息增益准则对可取值数目较多的特征有所偏好（例如样本编号），为了减少这种偏好带来的不利影响，引入了信息增益比。
  • 定义：信息增益比是信息增益与特征 A 本身的熵（也称为“分裂信息”）之比。
  • 计算公式： $$g_R(D, A) = \frac{g(D, A)}{H_A(D)}$$ 其中，$H_A(D)$ 是数据集 D 关于特征 A 的取值熵，计算方式为： $$H_A(D) = -\sum_{v=1}^{n} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$$
  • 应用：C4.5 算法使用信息增益比作为特征选择的标准。

3. 代表性算法及剪枝#

• ID3 算法：核心是使用信息增益作为划分标准，递归地构建决策树。但它偏向于选择取值多的特征，且不能处理连续值特征。
• C4.5 算法：是对 ID3 的改进。
  • 使用信息增益比来选择特征，克服了 ID3 的缺点。
  • 能够处理连续值特征（通过二分法）。
  • 引入了剪枝操作来防止过拟合。
• 决策树剪枝 (Pruning)
  • 目的：解决决策树容易过拟合的问题，增强模型的泛化能力。
  • 预剪枝 (Pre-pruning)：在决策树生成过程中，对每个节点在划分前进行评估，若当前节点的划分不能带来泛化性能的提升，则停止划分并将当前节点标记为叶节点。
  • 后剪枝 (Post-pruning)：先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来泛化性能的提升，则将该子树替换为叶节点。C4.5 采用此策略。

4. 习题相关考点#

• 考点1：决策树的预测过程 (对应问题1)

  • 核心要点：决策树的预测（分类）过程是一个自上而下的遍历过程。对于一个给定的测试样本，它总是从根节点开始，根据样本在当前节点的特征值选择一个分支向下移动，直到到达一个叶子节点，该叶子节点的类别就是最终的预测结果。
  • 解题关键：抓住关键词“从根节点开始”、“下行”和“直到叶节点”。这完全匹配了选项 D 的描述。

• 考点2：信息增益的定义 (对应问题2)

  • 核心要点：信息增益的本质是不确定性的减少量。一个特征的信息增益越大，意味着使用这个特征进行划分后，数据集的纯度提升得越多。
  • 公式定义：信息增益 = 划分前的信息熵 - 划分后的条件信息熵，即 $g(D,A) = H(D) - H(D|A)$。这个定义直接对应了选项 A 的描述。

1. EM算法与变分推理基础#

这部分是理解VAE等概率生成模型的理论基础。

• 期望最大化 (EM) 算法：

  • 目的：EM算法是一种迭代算法，用于求解含有隐变量或缺失数据的概率模型的最大似然估计或最大后验估计。
  • 核心思想：当直接优化对数似然函数 $L(\theta) = \ln p(X|\theta) = \ln \int p(X,Z|\theta)dZ$ 困难时，EM算法通过迭代优化一个更易处理的下界来逼近最优解。
  • 算法步骤：
    1. E步 (Expectation)：固定当前模型参数 $\theta^{(t)}$，计算对数联合概率分布关于隐变量后验分布 $p(Z|X, \theta^{(t)})$ 的期望，即 $Q(\theta|\theta^{(t)}) = \mathbb{E}_{Z|X,\theta^{(t)}}[\ln p(X,Z|\theta)]$。
    2. M步 (Maximization)：最大化E步中求得的期望 $Q(\theta|\theta^{(t)})$，以更新模型参数 $\theta^{(t+1)} = \arg\max_\theta Q(\theta|\theta^{(t)})$。
  • 交替执行E步和M步，直至模型参数收敛。

• 变分推理 (Variational Inference, VI)：

  • 目的：当模型的后验分布 $p(Z|X, \theta)$ 难以计算（intractable）时，变分推理提供了一种近似计算的方法。
  • 核心思想：引入一个更简单的、可参数化的变分分布 $q_\phi(Z|X)$，通过优化其参数 $\phi$，使其尽可能地接近真实的后验分布 $p(Z|X, \theta)$。
  • 优化目标：最大化证据下界 (Evidence Lower Bound, ELBO) $L(\theta, \phi, x)$。最大化ELBO等价于最小化 $q_\phi(Z|X)$ 与 $p(Z|X, \theta)$ 之间的KL散度。ELBO可以分解为： $$\mathcal{L}(\theta,\phi,x) = \mathbb{E}_{q_{\phi}(z|x)}[\log p_{\theta}(x|z)] - D_{KL}(q_{\phi}(z|x) || p_{\theta}(z))$$
    • 重构项 ($\mathbb{E}_{q_{\phi}(z|x)}[\log p_{\theta}(x|z)]$)：鼓励模型生成的样本与原始输入相似。
    • 正则化项 ($-D_{KL}(...)$)：约束变分后验分布 $q$ 接近先验分布 $p$，防止过拟合。

2. 变分自编码器 (Variational Autoencoder, VAE)#

VAE是一种结合了变分推理和神经网络的深度生成模型。

• 结构：
  • 编码器 (Encoder)：一个神经网络，输入为数据 $x$，输出为隐变量 $z$ 的概率分布参数（通常是高斯分布的均值 $\mu_z(x)$ 和方差 $\sigma_z(x)$）。这个网络学习的是变分后验分布 $q_\phi(z|x)$。
  • 解码器 (Decoder)：另一个神经网络，输入为从隐分布中采样的 $z$，输出为重构的数据 $x'$。这个网络学习的是数据的生成分布 $p_\theta(x|z)$。
• 训练过程：
  • 通过最大化ELBO作为损失函数进行端到端的训练。
  • 重参数化技巧 (Reparameterization Trick)：为了在训练中进行反向传播，VAE不直接从 $q_\phi(z|x)$ 中采样。而是先从一个标准正态分布中采样一个噪声 $\epsilon \sim \mathcal{N}(0, I)$，然后通过 $z = \mu_z(x) + \sigma_z(x) \cdot \epsilon$ 来计算 $z$。这样，梯度就可以通过确定性节点 $\mu$ 和 $\sigma$ 反向传播到编码器的参数 $\phi$。
• 生成过程：
  • 训练完成后，编码器被丢弃。
  • 从先验分布（如标准正态分布 $\mathcal{N}(0,I)$）中随机采样一个隐变量 $z$。
  • 将采样得到的 $z$ 输入解码器，生成一个新的数据样本 $x'$。

3. 生成式对抗网络 (Generative Adversarial Network, GAN)#

GAN通过两个神经网络的对抗性博弈来学习数据分布并生成高质量样本。

• 结构与博弈过程：
  • 生成器 (Generator, G)：输入一个随机噪声向量 $z$，输出一个伪造的数据样本 $G(z)$。它的目标是生成足够逼真的样本来“欺骗”判别器。
  • 判别器 (Discriminator, D)：一个二分类器，输入一个样本（真实的或伪造的），输出该样本为真实的概率。它的目标是尽可能准确地分辨出真实样本和生成器伪造的样本。
• 优化目标：
  • 这是一个极小极大博弈 (Minimax Game)。判别器 D 试图最大化其判别准确率，而生成器 G 则试图最小化 D 的准确率。
  • 理想的平衡点是，生成器 G 能够完美复制真实数据的分布，此时判别器无法分辨真伪，输出概率恒为0.5。
  • 为了解决原始损失函数在训练初期可能导致的梯度消失（饱和）问题，通常会将生成器的目标从最小化 $E[\log(1-D(G(z)))]$ 修改为最大化 $E[\log D(G(z))]$。
• 应用与变体：
  • CycleGAN：用于非成对的图像风格迁移，通过引入“循环一致性损失”来保证转换前后图像内容的保留。

4. 扩散模型 (Diffusion Models)#

扩散模型是一类强大的生成模型，通过模拟一个逐渐加噪和去噪的过程来生成数据。

• 核心思想：

  1. 前向/扩散过程 (Forward Process)：这是一个固定的、不可学习的马尔可夫链过程。它从一个真实数据样本 $x_0$ 开始，在 $T$ 个时间步内，逐步、微量地向其添加高斯噪声，直至其完全变成一个纯高斯噪声样本 $x_T$。
  2. 反向/去噪过程 (Reverse Process)：这是模型需要学习的部分。它从一个纯噪声样本 $x_T$ 开始，通过一个神经网络（通常是U-Net结构）在 $T$ 个时间步内逐步地去除噪声，最终恢复（生成）一个清晰的样本 $x_0$。

• 训练：模型训练的核心是训练一个噪声预测器 $\epsilon_\theta(x_t, t)$。在任意一个加噪步骤 $t$，给定加噪后的图像 $x_t$，模型的目标是准确地预测出当初为了得到 $x_t$ 而添加的噪声 $\epsilon$。

• 稳定扩散 (Stable Diffusion)：

  • 这是一个潜在扩散模型 (Latent Diffusion Model, LDM)。
  • 改进：为了解决在原始像素空间进行扩散计算量过大的问题，LDM首先使用一个预训练好的自编码器 (Autoencoder) 将图像从高维像素空间压缩到一个低维的潜在空间 (Latent Space)。然后，扩散和去噪过程完全在这个低维、计算高效的潜在空间中进行。生成完成后，再用解码器将潜在表示恢复成高分辨率图像。
  • 条件生成：通过交叉注意力机制 (Cross-Attention)，可以方便地将文本提示等外部条件信息融入去噪过程，从而实现对生成内容的精确控制。

• 考点1：EM算法 (对应问题1)

  • 核心功能：EM算法主要用于解决含有隐变量的概率模型的参数估计问题（如最大似然估计），当直接优化似然函数困难时，它提供了一个有效的迭代求解方案。 (对应选项 C 正确)
  • 算法流程：EM算法是一个迭代过程，它明确地交替执行两个步骤：E步（求期望） 和 M步（求最大化）。 (对应选项 D 正确)
  • 辨析：最大似然估计(MLE)和最大后验估计(MAP)结果通常不同，后者会受先验分布的影响；EM算法既可以用于MLE，也可以用于MAP（只需在M步中加入先验项）。因此选项 A 和 B 不正确。

• 考点2：变分自编码器 (VAE) (对应问题2)

  • 学习方式：VAE 从无标签数据中学习数据的潜在表示和生成方式，属于非监督学习。(对应选项 B 正确)
  • 生成机制：训练完成后，生成新数据只需要解码器。通过从先验分布（如高斯分布）中采样一个隐变量$z$，然后将其送入解码器即可。这个过程不涉及编码器。(对应选项 C 正确)
  • 训练关键：VAE的编码器输出的是一个分布的参数（如均值和方差），直接从中采样会导致梯度无法回传。因此，必须使用重参数化技巧，将随机采样步骤移出计算图，从而保证整个模型（包括编码器）的参数都可以通过梯度下降进行优化。(对应选项 D 正”确)
  • 网络角色：编码器网络参数化的是变分后验分布 $q_\phi(z|x)$，而解码器网络参数化的是生成分布（似然函数）$p_\theta(x|z)$。选项 A 的描述正好相反，因此不正确。

• 考点3：生成式对抗网络 (GAN) (对应问题3)

  • 训练判别器：判别器的任务是区分真伪。在训练它时，必须给它提供真实样本（标签为1）和生成器产生的虚假样本（标签为0），所以判别器需要知道样本的真实来源。(对应选项 D 正确)
  • 理想平衡点：GAN 的理想状态是生成器以假乱真，导致判别器完全无法区分，此时判别器的准确率应为 50%（相当于随机猜测），而非最高。(选项 A 错误)
  • 分布假设：GAN 的一个主要优点就是它不需要对数据分布做任何显式假设，它通过对抗训练直接学习这个分布。(选项 B 错误)
  • 损失函数选择：虽然两个生成器损失函数在目标上相似，但它们的梯度特性不同。max E log D(G(z)) 这个形式在训练初期能提供更强的梯度，有效避免了 min E log(1-D(G(z))) 可能出现的梯度饱和（消失）问题，因此两者的训练效果不完全相同。(选项 C 错误)

• 考点4：扩散模型 (对应问题4)

  • 生成过程：扩散模型是一种生成模型。它的正向过程是给数据逐渐加噪，而其逆向过程则是逐渐去噪。真正的数据生成是通过这个逆向的去噪过程完成的。从噪声开始，逐步还原出清晰的图像。(对应选项 D 正确)
  • 选项A辨析：“通过逐步加噪声来生成数据” 这个说法不准确。生成数据是通过去噪。但整个模型框架确实是基于“加噪-去噪”这一对过程的，所以该选项可能存在表述歧义，但在某些语境下可能被认为是描述了其核心机制的一部分。
  • 稳定扩散改进：稳定扩散模型是扩散模型的改进，其主要目的是通过在低维潜在空间中进行扩散来大幅提升计算效率，并实现更好的条件控制，而不是为了生成“多样性小的”图像。其生成图像的质量和多样性通常更高。(选项 B 错误)
  • 稳定扩散应用：虽然稳定扩散以其文生图能力而闻名，但其基础框架（LDM）是通用的，可以应用于其他数据模态，如音频、视频等。(选项 C 错误)

1. K-均值聚类 (K-means)#

K-均值聚类是一种应用广泛的、基于划分的聚类算法，它将数据点分配到预先指定数量K个的簇中。

• 核心思想：将数据划分为K个簇，使得每个数据点都属于离它最近的**聚类中心（均值/质心）**所对应的簇。
• 优化目标：最小化所有数据点到其所属簇中心的平方误差和 (SSE或WCSS)。 $$\arg\min \sum_{k=1}^{K} \sum_{n=1}^{N} I(z_n=k) \|x_n - \mu_k\|^2$$ 其中，$I(z_n=k)$ 是指示函数，如果样本 $x_n$ 属于第 $k$ 簇，则为1，否则为0。$\mu_k$ 是第 $k$ 簇的中心。
• 算法流程（批处理 K-均值）：这是一个迭代过程，通常被称为劳埃德算法（Lloyd’s algorithm）。
  1. 初始化：随机选择 K 个数据点作为初始的聚类中心 $\mu_1, \mu_2, \dots, \mu_K$。
  2. 分配步骤 (E-step)：对于每个数据点 $x_n$，计算其与 K 个中心的距离，并将其分配到距离最近的中心所在的簇。 $$z_n \leftarrow \arg\min_k \|x_n - \mu_k\|^2$$
  3. 更新步骤 (M-step)：根据新的簇划分，重新计算每个簇的中心。新的中心是该簇内所有数据点的均值。 $$\mu_k = \frac{1}{N_k} \sum_{n: z_n=k} x_n$$ 其中，$N_k$ 是第 $k$ 簇中数据点的数量。
  4. 重复：不断重复第2步和第3步，直到聚类中心不再发生变化或变化很小为止。
• 确定聚类数 K：K-均值算法需要预先指定 K 值。一种常用的方法是“肘部法则”，即尝试不同的 K 值，并绘制 SSE 随 K 值变化的曲线，曲线的“肘部”对应的 K 值通常是较好的选择。

2. 模糊K-均值聚类 (Fuzzy K-means)#

这是对K-均值“硬聚类”思想的扩展。

• 核心思想：与K-均值将每个点严格划分到某个簇不同，模糊K-均值允许每个数据点以一定的隶属度同时属于多个簇。
• 更新规则：其聚类中心的更新是一个加权平均的过程，所有的数据点都对每个中心的更新有贡献，权重由该点对该中心的隶属度决定。 $$\mu_k = \frac{\sum_{n=1}^{N} (d_{nk})^m x_n}{\sum_{n=1}^{N} (d_{nk})^m}$$ 其中 $d_{nk}$ 是样本 $x_n$ 对簇 $k$ 的隶属度，$m$ 是模糊化参数。

3. 高斯混合模型聚类 (GMM)#

GMM 是一种基于概率模型的聚类方法，它提供了比K-均值更灵活的簇形状描述。

• 核心思想：假设数据集是由 K 个不同的高斯分布混合生成的。每个高斯分布对应一个簇。因此，聚类问题转化为估计这K个高斯分布的参数（均值 $\mu_k$、协方差 $\Sigma_k$）以及它们的混合系数 $\pi_k$。
• 模型表示：数据点 $x$ 的概率密度是 K 个高斯分布的加权和： $$p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x | \mu_k, \Sigma_k)$$
• 参数估计：由于存在隐变量（每个点究竟来自哪个高斯分布是未知的），通常使用期望最大化 (EM) 算法进行参数估计。
  1. E-步：计算每个数据点 $x_n$ 由每个高斯分量 $k$ 生成的后验概率（也称为“责任”）。 $$p(z_{nk}=1|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)}$$
  2. M-步：使用E-步计算出的责任作为权重，更新每个高斯分量的参数。例如，均值的更新是所有样本点的加权平均： $$\mu_k = \frac{\sum_{n=1}^{N} p(z_{nk}=1|x_n) x_n}{\sum_{n=1}^{N} p(z_{nk}=1|x_n)}$$
  3. 重复：迭代执行E步和M步直至收敛。

4. 谱聚类 (Spectral Clustering)#

谱聚类是一种基于图论的聚类方法，它能有效处理非凸（例如环形、月牙形）的数据分布。

• 核心思想：它不直接在原始数据空间聚类，而是将聚类问题转化为对数据点构成的图进行最优切割的问题。
• 算法流程：
  1. 构建相似度图：将所有数据点看作图的顶点，计算每对顶点之间的相似度（如高斯相似度）作为边的权重，构建一个带权无向图。
  2. 计算拉普拉斯矩阵：根据相似度矩阵 W 和度矩阵 D，计算图的拉普拉斯矩阵 $L = D - W$。
  3. 特征分解（谱映射）：求解拉普拉斯矩阵的前 K 个最小的特征值及其对应的特征向量。
  4. 降维与聚类：将这 K 个特征向量堆叠起来，形成一个 N x K 的矩阵，其中每一行是原始数据点在新（谱）空间中的 K 维表示。最后，在这个新的 K 维空间上使用 K-均值算法进行聚类。
• 与图切割的联系：谱聚类的优化目标（如比率切割 Ratio Cut 或归一化切割 Normalized Cut）是最小化不同簇之间的边的总权重。这是一个离散的组合优化问题，难以直接求解。谱聚类通过数学推导，将其松弛为一个连续的特征值分解问题，从而将离散的图切割问题连续化，找到了近似解。

5. DBSCAN 聚类#

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一种基于密度的聚类算法。

• 核心思想：寻找被低密度区域分隔的高密度区域作为簇。它能发现任意形状的簇，并且能有效地识别噪声点。

• 关键概念：

  • 核心点：在其邻域半径 R 内，包含的样本点数量不少于一个阈值 minPoints 的点。
  • 边界点：不属于核心点，但落在某个核心点邻域内的点。
  • 噪声点：既非核心点也非边界点的点。

• 聚类形成：一个簇由一个核心点和所有从它密度可达（通过一连串核心点连接）的点组成。DBSCAN 不需要预先指定聚类数量 K

• 考点1：K-均值聚类 (对应问题1)

  • A. K均值算法需要预先设定K的数值：正确。这是K-均值算法的一个基本前提和主要限制。
  • B. K-均值算法得到的簇中心一定是某个样本点：错误。簇中心是簇内所有点的均值，它是一个计算出的坐标，通常不是原始样本点之一（除非在特殊情况下）。（K-Medoids算法的中心才是样本点）。
  • C. 模糊K-均值聚类算法在计算每个聚类中心时需要使用所有的样本点：正确。其中心是所有样本点的加权平均，权重是每个点对该簇的隶属度。
  • D. K-均值聚类算法在计算每个聚类中心时需要使用所有的样本点：错误。标准K-均值在更新一个簇的中心时，只使用被划分到该簇内的样本点，而非所有样本点。

• 考点2：高斯混合模型聚类 (GMM) (对应问题2)

  • A. 高斯混合模型聚类需要预先设定聚类数目K：正确。K值对应了混合模型中高斯分量的数量，需要预先指定。
  • B. 高斯混合模型聚类综合考虑样本之间的距离和样本分布的方差：正确。GMM用高斯分布来描述簇，高斯分布由均值（决定簇的中心，与距离有关）和协方差（决定簇的形状和延展方向，即方差）共同定义。
  • C. 高斯混合模型聚类在计算模型各个高斯成分的均值和方差时需要用到所有的样本点：正确。在M步中，每个高斯分量的参数（均值、方差）都是通过对所有样本点进行加权求和/平均来更新的，权重是该点属于该分量的后验概率（责任）。
  • D. 高斯混合模型聚类的结果最后根据隐变量z的后验分布得出：正确。对于一个给定的数据点，它最终的类别归属是由后验概率 $p(z_{nk}=1|x_n)$ 决定的，通常会将其分配给后验概率最大的那个簇。

• 考点3：谱聚类 (对应问题3)

  • A. 谱聚类通过将离散问题连续化，特征向量和特征值与最小割问题建立联系：正确。图的最小割是一个NP难的离散优化问题，谱聚类通过拉普拉斯矩阵的谱分解（求解特征值和特征向量），将这个问题松弛（近似）为一个可以在多项式时间内求解的连续问题。
  • B. 谱聚类中可以通过SVD进行降维，降维后的特征维度可以与聚类簇的数量不一致（请认真思考一下是否可以）：错误。在标准的谱聚类算法中，为了将数据划分成 K 个簇，通常选取拉普拉斯矩阵的前 K 个最小特征值对应的特征向量，将数据降维到 K 维，然后在 K 维空间中进行K-means聚类。降维后的维度与聚类簇的数量是一致的。
  • C. kmean无法很好的处理非凸的聚类簇，而谱聚类作为一种扩展可以较好的处理：正确。K-means只能发现球状（凸）的簇，而谱聚类通过将数据映射到谱空间，可以很好地处理环形、月牙形等任意形状的非凸簇。
  • D. 谱聚类是一种基于图论的聚类算法，将带权无向图划分为两个或两个以上的最优子图，使子图间距离尽量距离较远，以达到常见的聚类的目的：正确。这个描述基本正确，其目标是最小化子图之间的连接（切割边权重），这等价于让子图内部的连接尽可能紧密，而子图之间的连接尽可能稀疏（距离远）。

1. 主成分分析 (Principal Component Analysis, PCA)#

PCA 是一种应用最广泛的线性、无监督降维方法。它的目标是找到一个低维子空间来表示高维数据，同时尽可能多地保留原始数据的信息。

• 两大等价思想：

  1. 最大化方差 (Maximum Variance)：寻找一组新的正交基（称为主成分），使得原始数据投影到这些基上之后，方差被最大化。因为方差通常对应着信号的主要信息。
     • 优化目标：找到投影矩阵 $U$，使得投影后数据的方差之和（即协方差矩阵的迹）最大。 $$\arg\max_{U} \text{Tr}(U^T S U) \quad \text{s.t.} \quad U^T U = I$$ 其中 $S$ 是原始数据的协方差矩阵。
  2. 最小化重构误差 (Minimum Reconstruction Error)：寻找一个低维子空间，使得所有原始数据点到它们在这个子空间上的投影点之间的距离（即重构误差）之和最小。
     • 优化目标：最小化原始数据 $x_n$ 与其重构数据 $\tilde{x}_n$ 之间的平方误差和。 $$J = \frac{1}{N}\sum_{n=1}^{N}\|x_{n}-\tilde{x}_{n}\|_{2}^{2}$$

• 数学解法：

  • 无论从最大化方差还是最小化误差出发，最终都归结为对原始数据协方差矩阵 $S$ 的特征值分解。
  • 协方差矩阵 $S$ 的计算公式为： $$S = \frac{1}{N} \sum_{i=1}^{N} (x_i - m(x))(x_i - m(x))^T$$ 其中 $m(x)$ 是数据均值。
  • 主成分就是协方差矩阵 $S$ 的特征向量。
  • 投影矩阵 $U$ 由 $S$ 的前 M 个最大特征值所对应的特征向量构成。
  • 由于协方差矩阵是对称的，其特征向量是相互正交的。因此，投影后得到的新特征（主成分）之间是互不相关的。

2. 核主成分分析 (Kernel PCA)#

核PCA是PCA的扩展，用于处理非线性的数据降维问题。

• 核心思想：当数据结构非线性时，线性PCA无法有效降维。核PCA通过一个非线性映射 $\phi(x)$ 将数据隐式地映射到一个更高维的特征空间，并假设数据在这个高维空间中是线性可分的，然后在这个高维空间中执行PCA。
• 核技巧 (Kernel Trick)：在高维空间中计算协方差矩阵是困难甚至不可能的。核PCA通过引入核函数 $k(x_i, x_j) = \phi(x_i)^T \phi(x_j)$，将高维空间的内积计算替换为原始空间中的核函数计算，从而避免了显式的非线性映射。
• 求解：PCA的求解最终依赖于对协方差矩阵的特征分解，而核PCA则将其转化为对核矩阵 K 的特征分解，其中 $K_{ij} = k(x_i, x_j)$。

3. 线性判别分析 (Linear Discriminant Analysis, LDA)#

LDA，也称为费舍尔判别分析（Fisher’s Discriminant Analysis），是一种经典的有监督线性降维算法。

• 核心思想：与PCA最大化数据总方差不同，LDA的目标是找到一个投影方向，使得投影后的数据**“类内散度”尽可能小，同时“类间散度”尽可能大**。这样可以最大化类别之间的可分性。

• 优化目标 (Fisher准则)：最大化类间散度矩阵 $S_B$ 与类内散度矩阵 $S_W$ 的比率。

  $$\arg\max_{W} J(W) = \frac{\text{Tr}(W^T S_B W)}{\text{Tr}(W^T S_W W)}$$

• 求解：该优化问题最终转化为一个广义特征值问题：

  $$S_B W = \lambda S_W W$$

  最优的投影矩阵 $W$ 由 $S_W^{-1}S_B$ 的前 M 个最大特征值对应的特征向量构成。

• 降维维度限制：由于类间散度矩阵 $S_B$ 的秩最多为 $C-1$（其中C是类别数），因此LDA降维后的维度最多为 C-1。

• LDA与分类：LDA本身是一种降维技术，它找到一个最适合分类的子空间。在数据被投影到这个低维空间后，还需要使用一个分类器（如贝叶斯决策、逻辑回归等）来进行最终的分类。

• 考点1：主成分分析 (PCA) (对应问题1)

  • A. 主成分分析方法需要计算原始特征的协方差矩阵：正确。PCA的核心就是对数据的协方差矩阵进行特征值分解，以找到数据变化最大的方向。
  • B. 通过PCA方法得到的新特征能够完全表达原始特征的信息：错误。PCA是一种降维方法，它通过舍弃对应较小特征值的主成分来减少维度，这个过程必然会损失一部分信息。它保留的是方差最大的“主要”信息。
  • C. PCA是线性降维方法，核PCA是非线性降维方法：正确。PCA通过线性投影（乘以一个矩阵）进行降维。核PCA通过核函数实现非线性映射，是一种非线性降维方法。
  • D. 第一主成分和第二主成分是互不相关的：正确。因为主成分是协方差矩阵的特征向量，而对称矩阵的特征向量是相互正交的。数据在正交基上的投影是互不相关的。

• 考点2：线性判别分析 (LDA) (对应问题2)

  • A. LDA是监督的降维方法：正确。LDA在计算类内/类间散度矩阵时需要用到数据的类别标签，因此是监督学习方法。
  • B. LDA可以将D维数据降维到任意M维数据（M<=D）：错误。LDA降维后的维度受类别数 C 的限制，其最大维度为 $C-1$。例如，对于一个二分类问题，LDA最多只能降到1维。
  • C. LDA用于分类时，在得到低维数据后需要使用分类算法进行分类：正确。LDA本身是用于特征提取和降维的，它负责找到一个利于分类的特征子空间。要完成分类任务，还需要在这个降维后的空间上训练一个分类器。
  • D. LDA假设类间协方差为对角阵：错误。LDA没有这个假设。它计算的是完整的类间散度矩阵 $S_B$ 和类内散度矩阵 $S_W$。

1. 基本概念与理论基础#

• 核心要素：强化学习系统包含几个核心组成部分：

  • 智能体 (Agent)：学习者和决策者。
  • 环境 (Environment)：智能体外部的一切，与智能体进行交互。
  • 状态 (State, $s$)：对环境在某一时刻的描述，例如棋盘的布局。
  • 动作 (Action, $a$)：智能体可以执行的操作。
  • 奖励 (Reward, $r$)：环境对智能体在某个状态下执行某个动作后的即时反馈信号。RL的核心假设是所有目标都可以通过最大化期望累积奖励来表达。

• 策略 (Policy, $\pi$)：策略是智能体的“大脑”，它定义了智能体在给定状态下如何选择动作。

  • 确定性策略：在每个状态下都选择一个唯一的动作，即 $\pi(s) = a$。
  • 随机性策略：在每个状态下，给出一个选择各个动作的概率分布，即 $\pi(a|s) = p(a|s)$。

• 值函数 (Value Function)：值函数用于评估一个状态或一个状态-动作对的“好坏”，即从该点出发，遵循特定策略能获得的未来奖励的期望总和。

  • 状态值函数 $V_\pi(s)$：表示从状态 $s$ 开始，遵循策略 $\pi$ 所能获得的期望累积收益。 $$V_\pi(s) = \mathbb{E}_\tau[\sum_{t=0}^{\infty} \gamma^t r_{t+1} | s_0=s]$$
  • 动作值函数 $Q_\pi(s, a)$：表示在状态 $s$ 下执行动作 $a$，然后继续遵循策略 $\pi$ 所能获得的期望累积收益。

• 马尔可夫决策过程 (MDP)：是强化学习问题的标准数学框架，由一个五元组 $<S, A, P, R, \gamma>$ 定义，其中 P 是状态转移概率，R 是奖励函数，$\gamma$ 是折扣因子。

• 贝尔曼方程 (Bellman Equations)：是几乎所有强化学习算法的基础，它建立了当前状态值与后续状态值之间的递归关系。

  • 贝尔曼期望方程：描述了在给定策略 $\pi$ 下，值函数满足的迭代关系。它用于策略评估。 $$V_\pi(s) = \sum_a \pi(a|s) \left( R_s^a + \gamma \sum_{s'} P_{ss'}^a V_\pi(s') \right)$$
  • 贝尔曼最优方程：描述了在最优策略 $\pi_*$ 下值函数满足的关系，通过max算子代替了对策略的期望。它用于求解最优策略。 $$V_*(s) = \max_a \left( R_s^a + \gamma \sum_{s'} P_{ss'}^a V_*(s') \right)$$

2. 规划：有环境模型的评估与控制 (Model-Based)#

当环境的模型（即状态转移概率P和奖励函数R）已知时，可以通过动态规划来求解最优策略。

• 策略迭代 (Policy Iteration)：一种交替执行两个步骤的算法。

  1. 策略评估：固定当前策略 $\pi$，使用贝尔曼期望方程迭代计算其状态值函数 $V_\pi(s)$，直到收敛。
  2. 策略改进：根据评估出的 $V_\pi(s)$，计算出 $Q_\pi(s, a)$，然后通过贪心选择来更新策略：$\pi'(s) = \arg\max_a Q_\pi(s, a)$。 重复这两个步骤，直到策略不再改变。

• 值迭代 (Value Iteration)：一种更直接的方法，它将策略评估和改进合并为一步，直接通过迭代贝尔曼最优方程来寻找最优状态值函数 $V_*(s)$。

  $$V_{k+1}(s) = \max_a \left( R_s^a + \gamma \sum_{s'} P_{ss'}^a V_k(s') \right)$$

  当 $V(s)$ 收敛后，再从中提取最优策略。

3. 无环境模型的控制：基于值函数 (Model-Free Value-Based)#

当环境模型未知时，智能体必须通过与环境的交互（试错）来学习。

• 同策略 (On-policy) vs. 异策略 (Off-policy)：
  • 同策略：学习和改进的策略就是当前正在执行的策略。例如，SARSA。
  • 异策略：学习和改进一个策略（目标策略），而执行的是另一个策略（行为策略）。这允许智能体从过去的经验或专家的经验中学习。例如，Q-Learning。
• 时序差分 (TD) 学习：不需等待一个完整的轨迹结束，而是每走一步就利用得到的 $(s, a, r, s')$ 信息来更新值函数估计，这是蒙特卡洛方法和动态规划的结合。
  • SARSA：一种同策略TD算法。其名称来源于其更新依赖于 $(s, a, r, s', a')$ 五元组。它使用当前策略选择的下一个动作 $a'$ 来更新 $Q(s, a)$。
  • Q-Learning：一种异策略TD算法。它在更新 $Q(s, a)$ 时，总是假设在下一个状态 $s'$ 会采取最优的动作（即能使 $Q(s', a')$ 最大的那个动作），而不管实际执行了哪个动作。其更新规则直接源于贝尔曼最优方程。
  • 深度Q网络 (DQN)：当状态空间过大时，用神经网络来近似Q函数。它引入经验回放和目标网络等技巧来稳定训练。

4. 无环境模型的控制：基于策略 (Model-Free Policy-Based)#

这类方法不学习值函数，而是直接学习一个参数化的策略 $\pi_\theta(a|s)$。

• 策略梯度法：通过梯度上升来优化策略参数 $\theta$，以最大化期望总收益 $J(\theta)$。

• REINFORCE算法：一种蒙特卡洛策略梯度方法。它通过采样完整的轨迹，并使用该轨迹的总收益 $G(\tau)$ 来更新策略。

• 行动者-评论者 (Actor-Critic)：结合了基于值函数和基于策略的方法。

  • 行动者 (Actor)：一个策略网络，负责选择动作。
  • 评论者 (Critic)：一个值函数网络，负责评估行动者选择的动作的好坏，并提供一个低方差的梯度信号来指导行动者的更新。

• 考点1：强化学习基本概念

  • A. 使用强化学习来训练围棋策略时，通常状态是棋局：正确。棋盘上每个子的位置共同构成了当前的状态。
  • B. 强化学习需要标注数据集来训练模型，而监督学习不需要：错误。恰好相反，监督学习需要“输入-正确输出”这样的标注数据集；强化学习则不需要，它通过环境反馈的奖励信号进行学习。
  • C. 强化学习可以使用延迟奖励：正确。强化学习的目标是最大化累积收益，这天然地处理了奖励可能在多步之后才出现的情况（延迟奖励）。
  • D. 使用强化学习一定比使用监督学习更好：错误。两者适用于不同类型的问题。监督学习适用于有明确正确答案的预测任务，而强化学习适用于需要做出一系列决策以达成目标的任务。

• 考点2：值函数关系

  • A. 状态值函数V(s)是当前状态下所获得的奖励的期望：错误。V(s) 是在当前状态下，直到任务结束所能获得的未来累积奖励的期望，而不仅仅是下一步的即时奖励。
  • B. 通过状态动作值函数Q(s,a)可以获得状态值函数V(s)：正确。状态值函数是动作值函数在策略 $\pi$下的期望：$V_\pi(s) = \sum_a \pi(a|s) Q_\pi(s, a)$。
  • C. 通过当前的状态值V(s)可以获得当前的状态动作值Q(s,a)：正确。如果知道环境模型，可以通过贝尔曼期望方程计算：$Q_\pi(s,a) = R_s^a + \gamma \sum_{s'} P_{ss'}^a V_\pi(s')$。
  • D. 状态动作值函数 Q(s,a) 和状态值函数 V(s) 都是依赖于某个策略$\pi$的：正确。值函数是用来评估一个策略的好坏的，因此其定义总是与一个特定的策略 $\pi$ 绑定。

• 考点3：Model-Based算法比较

  • A. 策略迭代算法和值迭代算法都需要知道环境的状态-动作转移概率：正确。两者都属于基于模型的动态规划方法，都需要完整的环境模型（包括转移概率P和奖励R）来进行计算。
  • B. 策略迭代算法需要根据贝尔曼期望方程，交替执行策略评估和策略更新两个步骤：正确。这是策略迭代的核心流程。
  • C. 值迭代算法需要根据贝尔曼最优方程，交替执行策略评估和策略更新两个步骤：错误。值迭代是直接迭代贝尔曼最优方程来更新值函数，它没有显式的策略评估和策略更新的交替步骤。
  • D. 值迭代算法是一种贪婪的策略改进算法：错误。值迭代的核心是更新值函数，策略改进（贪婪地提取策略）是在值函数收敛之后才进行的一步操作。

• 考点4：基于贝尔曼最优方程的算法

  • A. 值迭代：正确。值迭代算法的更新公式就是贝尔曼最优方程的直接应用。
  • B. 策略迭代：错误。策略迭代的评估步骤用的是贝尔曼期望方程。
  • C. SARSA：错误。SARSA 是基于贝尔曼期望方程的TD方法。
  • D. Q学习：正确。Q-learning 的更新规则是贝尔曼最优方程在无模型情况下的应用，它通过 $\max_{a'} Q(s', a')$ 来估计最优未来价值。

• 考点5：基于策略的方法

  • A. 深度Q学习：错误。DQN是典型的基于值函数的方法，它用神经网络来近似Q值。
  • B. Actor-Critic算法：正确。这类算法有一个“Actor”组件，专门用来学习和输出一个策略，因此是基于策略的（或者是两者的混合）。
  • C. 蒙特卡洛控制：错误。蒙特卡洛控制是通过采样完整轨迹来估计动作值函数Q(s,a)，然后根据Q值来改进策略，属于基于值函数的方法。
  • D. 蒙特卡洛策略梯度：正确。这类方法（如REINFORCE）直接对策略的参数进行梯度优化，是典型的基于策略的方法。