机器学习导论与分类基础

机器学习核心定义

机器学习是一种设计预测函数的方法论，其特点在于设计过程是非显式的，不手动编写规则，而是让系统从大量示例数据中自动归纳规律并泛化到新情况。

机器学习问题涉及三个基本要素：待解释的数据 x（传感器测量值、文字、图片、音频等），预测结果 y（决策、分类标签、数值预测等），训练样本集 D = \{(\boldsymbol{x}_i, y_i)\}（由若干输入输出对组成的已知正确答案的例子）。

整个机器学习的目标可以用映射关系表达：

给定训练数据集 D 和新输入 \boldsymbol{x}，系统输出对应的预测 y。核心假设是训练样本包含了完成预测任务所需的全部有用信息，预测器本质上是一个插值器，在训练数据点之间进行插值，遇到新数据点时根据它与已知数据点的关系推断输出。

学习系统的两个阶段

学习阶段（训练阶段）接收训练数据库作为输入，通过估计算法输出模型参数：

其中 W 代表预测器的特征参数，在神经网络中是权重参数，在线性模型中是回归系数。

预测阶段（测试阶段）使用学到的模型处理新数据：

预测阶段会被反复执行，因此计算效率对实际应用至关重要。

参数化预测函数

预测函数是参数化的函数 F，接受输入 \boldsymbol{x} 和参数 W，输出预测值 y：

分号前的 \boldsymbol{x} 是函数的自变量（每次预测都不同），分号后的 W 是函数的参数（学习完成后固定不变）。学习的任务是从训练数据中找到最优参数 W，通过最小化准则函数 L 实现：

准则函数 L 通常称为损失函数或目标函数，量化模型预测与真实标签之间的差距，整个学习过程本质上是优化问题。

学习类型分类

监督学习的训练数据包含完整标注信息，每个输入样本对应明确的目标输出，如手写数字识别、垃圾邮件过滤、图像分类。

无监督学习处理没有标注的原始数据，算法自己发现数据中的结构和模式，如聚类分析和降维。

半监督学习的训练数据只有一部分带有标注，利用大量未标注数据中蕴含的结构信息辅助学习。

强化学习没有直接的输入输出对，智能体在环境中采取动作并根据结果获得奖励或惩罚，目标是找到最大化长期累积奖励的策略。

预测类型分类

分类任务的输出是离散的类别标签，二分类只有两个可能输出，多分类有多个可能类别。

回归任务的输出是连续的数值，如预测气温、股票价格等。

分类与回归的本质区别在于输出空间结构：分类的输出是无序的离散集合，回归的输出是有序的连续区间。

构建机器学习系统的步骤

第一步是获取训练数据。以手写数字识别为例，MNIST包含60000张训练图像和10000张测试图像，每张是28×28像素的灰度图。

第二步是数据预处理与特征提取。原始二维图像维度高、包含噪声、数据结构不均匀。特征提取将高维、有噪声、异构的原始数据转换为低维、干净、同构的特征向量。

第三步是选择学习方法，需要确定问题类型（分类/回归）、学习范式（监督/无监督）、数据性质、数据集规模，然后选择预测器的函数形式（决策树、SVM、神经网络等）。

第四步是优化，定义函数空间和损失函数，选择优化器，验证学习过程是否正常进行。

第五步是评估，在独立于训练集的测试集上评估模型的泛化能力。

学习率的影响

学习率为1.0时曲线剧烈震荡，模型无法稳定收敛；学习率为0.1时仍有明显震荡；学习率为0.01和0.001时曲线平滑，能稳定收敛；学习率过小如0.0001及以下时收敛速度极慢。学习率既不能太大（导致不稳定）也不能太小（导致收敛过慢）。

评估指标

对于分类任务，平均错误率是被错误分类的样本占总样本的比例。混淆矩阵的第 i 行第 j 列元素表示真实类别为 i 但被预测为 j 的样本数量，对角线元素表示正确分类。精确率是预测为正类的样本中真正为正类的比例，召回率是所有正类样本中被正确预测出来的比例。

对于回归任务，均方误差计算预测值与真实值之差的平方的平均值。

特征提取的必要性

原始数据通常无法直接用于学习算法：数据中包含噪声，原始数据维度往往很高，真正有用的信息被淹没在大量冗余或无关的数据中。

特征设计在多个目标之间寻找平衡：表达能力（能否充分描述数据的关键特性）、不变性（是否对无关变化保持稳定）、鲁棒性（是否能抵抗噪声干扰）、特征维度（是否足够紧凑）、计算成本（提取是否高效）。

通用预测链结构

信号源集合 S = \{s_1, \ldots, s_K\} 经传感器转换为测量数据 I \in \mathbb{R}^N，再经特征提取得到特征向量 \mathbf{x} \in \mathbb{R}^d（d 通常远小于 N），预测算法输出结果 y \in A = \{a_1, \ldots, a_L\}：

端到端学习

传统机器学习流程将特征提取和预测分为两个独立阶段，特征由人工设计。现代深度学习方法将整个处理链整合为统一的可学习系统，从原始测量数据 I \in \mathbb{R}^N 到特征向量 \mathbf{x} \in \mathbb{R}^d 再到预测输出 y，通过学习自动发现最适合任务的特征表示。

深度学习网络的层次化特征：低层特征对应网络前几层，学习简单视觉元素如边缘、颜色块；中层特征组合低层特征形成更复杂模式；高层特征学习抽象的视觉概念，直接与识别任务相关。

分类问题的两种策略

生成式方法先对数据本身进行建模，理解数据如何生成，然后基于模型做决策。生成式模型能够生成（采样）新数据，因为它完整描述了数据的概率分布 P(\mathbf{x}, y)。

判别式方法跳过数据生成机制的建模，直接从数据中学习决策边界。判别式模型是统计模型而非概率模型，可以输出决策的不确定性，但不能生成新数据样本。

概率建模基础

训练数据集 \mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^N 被视为从联合分布 P(\mathbf{x}, y) 中抽取的 N 个样本。关键假设是所有样本独立同分布（i.i.d.）。

联合分布 P(\mathbf{x}, y) 描述 \mathbf{x} 和 y 同时取特定值的概率。边缘分布 P(\mathbf{x}) 是数据的先验分布，P(y) 是标签的先验分布。条件分布 P(\mathbf{x}|y) 称为类条件似然，描述每个类别的数据分布；P(y|\mathbf{x}) 称为后验分布，描述观察到数据后各类别的概率。

联合分布通过条件分布分解：

左边的分解 P(\mathbf{x}|y)P(y) 对应生成式方法，右边的分解 P(y|\mathbf{x})P(\mathbf{x}) 对应判别式方法。

独立性假设

一般独立性：

条件独立性（在给定第三个变量条件下两变量相互独立）：

朴素贝叶斯分类器假设在给定类别标签条件下各特征之间相互独立。

样本量与学习方差

当样本量较小时，随机性导致的波动很明显，难以准确推断真实分布形态。随着样本量增加，经验分布越来越接近真实分布，估计的方差减小。训练数据量不足时，学到的模型可能只捕捉到特定抽样的偶然特征，而非数据的本质规律。

集中不等式

Markov不等式：

非负随机变量 X 取值超过 t 的概率不超过其期望值除以 t。

Hoeffding不等式：

样本均值与真实期望偏差超过 t 的概率上界随样本量 n 增加呈指数衰减。

贝叶斯决策理论

目标是找到决策函数 F: \mathbf{x} \mapsto y^*，最小化期望损失：

0/1损失函数：

预测正确时为0，错误时为1。在0/1损失下，期望风险等于错误率。

最优决策函数是贝叶斯分类器：

即对每个输入选择后验概率最大的类别。

贝叶斯公式与分类

通过贝叶斯公式计算后验：

P(y) 是类先验，P(\mathbf{x}|y) 是类条件似然，P(\mathbf{x}) 是数据的边缘分布。

由于 P(\mathbf{x}) 对所有类别相同，决策函数简化为：

只需建模类条件似然 P(\mathbf{x}|y) 和类先验 P(y)。

贝叶斯错误率

贝叶斯错误率是任何分类器所能达到的错误率下界：

如果数据的类条件分布有大量重叠，贝叶斯错误率就会很高，反映分类任务本身的内在难度。

多元高斯模型

概率密度函数：

\boldsymbol{\mu} 是均值向量，决定分布的中心位置。\boldsymbol{\Sigma} 是 d \times d 协方差矩阵，刻画各维度之间的相关性和变异程度。指数项中的 (\mathbf{x}-\boldsymbol{\mu})^t\boldsymbol{\Sigma}^{-1}(\mathbf{x}-\boldsymbol{\mu}) 是马氏距离的平方。

协方差矩阵结构决定分布形状：单位矩阵时等高线是圆；对角但不相等时等高线是轴对齐椭圆；有非零非对角元素时等高线是倾斜椭圆。

高斯模型参数的最大似然估计

对数似然函数：

均值的最大似然估计量（样本均值）：

协方差矩阵的最大似然估计量（样本协方差矩阵）：

这个估计量是有偏的，无偏估计需要将分母从 N 改为 N-1。

高斯判别分析的决策边界

二分类问题中，决策规则为判断对数似然比的符号：

展开后：

这是 \mathbf{x} 的二次函数，决策边界是二次曲面，称为二次判别分析（QDA）。

当两个类别共享相同协方差矩阵 \boldsymbol{\Sigma}_1 = \boldsymbol{\Sigma}_2 = \boldsymbol{\Sigma} 时，二次项相互抵消：

决策边界变成超平面，称为线性判别分析（LDA）。

LDA假设更强、参数更少、在假设成立时更稳定；QDA假设更弱、灵活性更高、但需要估计更多参数，样本量不足时可能过拟合。

分类错误的来源

确定区域：某类别似然值远高于另一类别，分类器可做出高置信度正确判断。

模糊区域：两个类别似然值相近，密度曲线明显重叠，无论选择哪个类别都有相当概率错误，这是数据本身的内在模糊性导致的。

异常区域：两个类别似然值都很低，数据点可能来自未知的第三类或是测量错误。

拒绝机制

在后验概率上设置阈值，如果最大后验概率 \max_k P(y=k|\mathbf{x}) 低于阈值则拒绝做出分类决策。阈值越高，拒绝的样本越多，决策错误率越低；阈值越低，拒绝的样本越少，但决策错误率上升。

高斯模型的局限性

协方差矩阵 \boldsymbol{\Sigma} 需要估计 \frac{d(d+1)}{2} 个参数。当特征维度 d 很大时参数量急剧增长，d=100 时需要估计5050个协方差参数。样本量不够时估计出的协方差矩阵可能是奇异的（不可逆）。

朴素贝叶斯方法

假设在给定类别 y 条件下各特征维度相互独立：

使用对数似然避免数值下溢：

分类决策：

参数量从 O(d^2) 降低到 O(d)，适用于高维特征空间。由于假设特征独立，等高线只能是轴对齐的椭圆，无法表达特征间的相关结构。

二元线性判别

决策函数由权重向量 \mathbf{w} 和偏置 b 定义：

\mathbf{w}^t \cdot \mathbf{x} 是内积，表示 \mathbf{x} 在 \mathbf{w} 方向上的投影。决策边界是使 \mathbf{w}^t \cdot \mathbf{x} + b = 0 的点的集合，在 d 维空间中是 d-1 维超平面。

最小二乘法

将分类问题当作回归问题，目标函数是平方误差：

矩阵形式：

解析解（正规方程）：

缺点：对异常值非常敏感，平方误差会放大远离决策边界的错误样本的影响。

逻辑回归

直接对后验概率建模：

sigmoid函数将任意实数映射到 (0, 1) 区间。当 a \to +\infty 时 \sigma(a) \to 1，当 a \to -\infty 时 \sigma(a) \to 0，当 a = 0 时 \sigma(a) = 0.5。

交叉熵损失函数（负对数似然）：

其中 z_n = \sigma(\mathbf{w}^t\mathbf{x}_n + b)。

梯度：

逻辑回归对异常值敏感性较低，因为sigmoid函数饱和特性使得远离决策边界的样本梯度接近零。

Fisher线性判别分析

寻找投影方向使两类数据对比度最大，通过Rayleigh准则量化：

分子 (m_1 - m_2)^2 是类间距离（两类中心投影后的距离），分母 s_1^2 + s_2^2 是类内分散程度。好的投影方向使类间距离大、类内分散小。

K近邻方法基本原理

基于假设：特征空间中相近的样本应具有相似的预测结果。

设训练集为 \mathcal{L} = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}，对于新样本 x，找到距离最小的样本索引：

预测结果：

整个过程不需要显式训练阶段，训练就是存储所有训练样本，称为懒惰学习。

K近邻方法

将所有训练样本按距离排序：

选取距离最近的 k 个样本进行多数投票：

\delta 是Kronecker delta函数，\sum_{i=1}^{k} \delta(y, y_{(i)}) 计算前 k 个近邻中属于类别 y 的样本数量。

加权投票让距离更近的邻居拥有更大话语权：

K近邻的计算代价

计算 N 个距离的复杂度为 O(Nd)，排序复杂度为 O(N \log N)。KD树可将平均查询复杂度降至 O(\log N)。对于超大规模数据库可使用近似最近邻搜索算法如乘积量化。

维度灾难

当特征空间维度 d 增大时，任意两点间距离趋于相等：

当维度趋于无穷时，最近邻和最远邻之间的相对距离差异趋于消失，最近邻概念失去意义。K近邻方法只在低维空间中效果良好，高维问题必须先进行降维处理。

K近邻方法的统计性质

当训练样本数量 N 趋于无穷时，1-近邻分类器的错误率不超过贝叶斯最优错误率的两倍，k-近邻分类器的错误率收敛到贝叶斯最优错误率。

决策树与集成方法

决策树基本原理

决策树通过一系列封闭问题来实现分类，所谓封闭问题是指答案数量有限的问题。这些问题被组织成树形结构：从根节点开始，根据当前问题的答案选择下一个分支，进入子节点继续回答下一个问题，直到到达叶节点给出最终的分类预测。

决策树中的问题可以有多种形式：直接询问某个特征属性的取值，询问某个逻辑表达式是否为真，询问某个数值是否落在某个区间内，询问某个值是否属于某个集合。这些问题既可以针对离散属性也可以针对连续数值属性。

决策树的结构组成

每个样本被编码为一组属性的集合。决策节点是树中的内部节点，每个决策节点关联一个针对某个属性的测试或问题。分支从决策节点出发，代表该属性可能的取值或问题可能的回答。终端节点（叶节点）不再进行任何测试，直接关联一个类别标签作为预测输出。

决策树的空间划分

决策树的预测过程本质上是对特征空间的递归划分。每个问题都在当前的属性空间中切割出若干子区域，每个终端节点对应空间划分后的一个区域，落入该区域的所有样本都会被赋予相同的预测类别。

对于离散属性，划分方式是直接按照属性的取值进行分组。对于连续属性，划分方式是将属性值与某个阈值进行比较，产生形如 X_1 < 1.2 或 X_2 \geq 0.9 的测试，将平面划分成多个矩形区域。决策树只能产生轴平行的决策边界，无法直接产生斜线边界。

构建决策树的问题

全局问题涉及树的整体设计：选择什么样的树结构，每个节点应该有多少分支，何时停止划分。局部问题涉及每一步的具体决策：在当前节点应该选择哪个属性进行测试，如何进行剪枝，如果某个叶节点包含多个类别的样本应该标记为哪个类别。

学习问题的形式化

设训练数据集为 X = \{(x_j, y_j)\}_{j \leq N}，其中 N 是样本数量。每个样本 x_j 由 M 个属性描述，记为 x_j = \{A_i^j\}_{1 \leq i \leq M}。学习的目标是找到与训练数据 X 兼容的最小决策树。

根据奥卡姆剃刀原则，在所有能够解释数据的假设中应该选择最简单的那个。然而寻找最优决策树是一个NP完全问题，因此实际中采用启发式方法，通过贪心策略逐步构建树。

决策树的递归构建算法

算法的伪代码如下：

函数 Construire-arbre(X)

如果 X 中所有样本属于同一类别，则创建一个叶节点，将该类别作为预测输出。

否则：选择最佳的属性-测试对 (A_i, \text{test}) 来创建一个决策节点。这个测试将数据集 X 分成两个子集 X_g（左子集）和 X_d（右子集）。然后递归调用构建左子树和右子树。

算法的关键在于如何选择最佳的属性-测试对，一个好的划分应该使得子节点中的样本尽可能属于同一类别，即子节点的纯度应该尽可能高。

节点纯度的度量标准

设当前节点包含 N 个样本，其中属于类别 c_k 的样本有 N_k 个，则类别 c_k 的概率估计为：

熵是信息论中的概念，用于度量随机变量的不确定性：

当所有样本属于同一类别时，H = 0，表示没有不确定性。当样本均匀分布在所有类别时，熵达到最大值。熵被ID3和C4.5算法采用。

基尼指数定义为：

随机抽取一个样本，它属于类别 c_k 的概率是 p(c_k)，将它错误分类为其他类别的概率是 1 - p(c_k)，基尼指数就是这种错误的期望值。当所有样本属于同一类别时，基尼指数为0。CART算法采用基尼指数。

错误率指数定义为：

表示如果将当前节点的所有样本都预测为多数类会产生的错误率。

信息增益与最优划分

设测试 T 将节点 V 划分为若干子节点 V_j，划分带来的同质性增益定义为：

I(V) 是划分前节点 V 的不纯度，I(V_j) 是子节点 V_j 的不纯度，p(V_j) 是样本落入子节点 V_j 的比例作为权重。增益表示划分前后不纯度的减少量，增益越大说明划分越有效。在每个节点，算法遍历所有可能的属性和测试，选择使 Gain(V, T) 最大的那个。

连续属性的处理

对于连续数值属性 A_i，将该属性的所有取值按升序排列，在相邻值之间的每个位置尝试设置阈值，计算每个候选阈值的信息增益，最终选择增益最大的阈值。

考试例题：决策树构建

考试题目给出如下二分类问题的数据分布：

图中横轴为 x_1，纵轴为 x_2，范围均为 [-2, 2]。星形（★）和圆形（●）分别代表两类数据点，需要构建一棵深度为2的决策树。

计算初始熵

首先统计两类样本数量。从图中可以看到星形有9个，圆形有9个，共18个样本。因此：

初始熵为：

判断测试 (x_2 > n) 是否有意义

观察图中数据分布，沿 x_2 方向（纵向）划分时，无论选择什么整数阈值 n，划分后的上下两个区域中星形和圆形的比例都与原始分布相近。这是因为星形和圆形在纵向上是交错分布的，没有明显的分离趋势。因此类型为 (x_2 > n) 的测试没有意义，信息增益接近0。

计算测试 (x_1 > 0) 的信息增益

按 x_1 > 0 划分后：

• 左子集（x_1 \leq 0）：统计图中 x_1 \leq 0 的点，假设有5个星形，4个圆形，共9个
• 右子集（x_1 > 0）：统计图中 x_1 > 0 的点，假设有4个星形，5个圆形，共9个

左子集的熵：

右子集的熵：

由于两个子集的类别分布对称，H(\text{左}) = H(\text{右})。

条件熵：

信息增益：

计算测试 (x_1 > 1) 的信息增益

按 x_1 > 1 划分后，观察图中 x_1 > 1 的区域只有圆形点，x_1 \leq 1 的区域包含所有星形和部分圆形。

假设 x_1 > 1 的区域有0个星形，3个圆形，则该区域熵为0（纯净）。x_1 \leq 1 的区域有9个星形，6个圆形，共15个。

右子集的熵：

左子集的熵：

条件熵：

信息增益：

由于 (x_1 > 1) 能产生一个纯净的子节点，其信息增益通常大于 (x_1 > 0)，因此 (x_1 > 1) 是更好的第一个测试。

构建深度为2的决策树

根节点使用测试 (x_1 > 1)：右分支（x_1 > 1）为纯圆形，直接作为叶节点预测圆形。左分支（x_1 \leq 1）继续划分。

在左分支中，选择下一个最佳测试（如 x_1 > -1 或其他），继续划分直到深度为2。每个叶节点的决策为该节点中多数类，概率分数为该类别在该节点中的比例。

决策树的过拟合问题

当树的结构过于精细时，会过度适应训练数据中的噪声和特殊情况，导致在新数据上的泛化能力下降。左图显示原始数据，中图展示良好的划分，右图展示过拟合的划分，决策边界变得极其复杂。

复杂度控制方法

控制决策树复杂度的方法包括：限制树的最大深度，设置同质性增益的最小阈值，在损失函数中加入复杂度惩罚项，设置每个节点的最小样本数。

决策树总结

优势：具有良好的可解释性，训练和预测都很快速高效。劣势：容易过拟合，对噪声和异常点敏感。决策树既可以用于分类任务也可以用于回归任务，能够同时处理数值型属性和符号型属性。

集成方法的基本概念

集成方法通过聚合多个分类器来进行预测。产生多样化分类器的途径有两种：对数据进行不同的采样，或修改分类器本身的结构。最终的预测类别通过融合所有分类器的预测结果来确定。

核心原则：通过组合多个性能一般的弱分类器，可以构建出一个性能优异的强分类器。这种方法能够降低学习过程中的方差，单个分类器可能在某些样本上犯错，但不同分类器犯错的位置往往不同，当它们的预测被综合起来时，错误会相互抵消。

两种主要的集成策略

Bagging并行地训练多个模型，每个模型在不同的数据子集上独立训练，最后将所有模型的预测结果合并。Boosting串行地训练多个模型，每个新模型都专注于纠正前面模型的错误。

Bagging方法

Bagging的名称来源于Bootstrap Aggregating（自助聚合）。从原始训练集 X 出发，通过有放回抽样构建 K 个新的数据集 \tilde{X}_1, ..., \tilde{X}_K。

一个样本在单次抽样中不被选中的概率是 1 - 1/N，在 N 次抽样后某个特定样本始终未被选中的概率为：

当 N \to \infty 时，这个概率趋近于 e^{-1} \approx 0.3679。每个新数据集大约包含原始数据集中63.2%的不同样本。

在每个数据集 \tilde{X}_k 上训练一个基分类器 f_k，然后通过投票或平均聚合：

随机森林

随机森林是Bagging方法在决策树上的扩展，除了通过Bagging对数据进行采样外，还对属性空间引入随机性。在每个节点选择划分属性时，不是从所有 M 个属性中选择，而是先随机抽取 m 个属性（m < M），然后只在这 m 个属性中寻找最优划分。

随机森林算法流程

循环 k = 1 \ldots K：通过有放回抽样生成数据集 \tilde{X}_k，从全部 M 个属性中随机抽取 q 个属性，构建决策树 G_k，得到分类函数 f_k。

聚合阶段，对于回归任务：

对于分类任务：

偏差与方差的概念

假设真实的数据生成过程为 y = f(x) + \epsilon，其中 f(x) 是真实的底层函数，\epsilon 是随机噪声。

偏差是预测的平均值与真实值之间的差距，反映模型的系统性偏离。方差是预测值围绕其平均值的波动程度，反映模型对训练数据变化的敏感程度。

偏差-方差分解

对于给定的输入 x，预测误差可以分解为：

第一项 \epsilon^2 是不可约误差。第二项是偏差的平方，高偏差意味着模型过于简单（欠拟合）。第三项是方差，高方差意味着模型对训练数据过于敏感（过拟合）。

1次多项式：方差低但偏差高（欠拟合）。5次多项式：偏差和方差都较低（理想平衡）。20次多项式：偏差低但方差高（过拟合）。

集成方法降低方差的原理

当单个预测器是无偏的，集成预测器的方差为：

\sigma^2 是单个预测器的方差，\rho 是任意两个预测器之间的相关系数，K 是集成中预测器的数量。

当 K \to \infty 时，总方差趋近于 \rho\sigma^2。当 \rho \approx 0 时，总方差趋近于 \sigma^2/K。这解释了为什么随机森林要在属性选择上引入随机性：降低树之间的相关性 \rho，使集成效果更好。

随机森林总结

优势：优秀的预测性能，能够很好地处理高维数据，对噪声和异常值具有较强的鲁棒性。劣势：训练时间相对较长，但可以通过并行化缓解。使用建议：树的深度通常选择较小的值（2到5之间），其他超参数通过交叉验证确定。

AdaBoost算法

AdaBoost通过迭代的方式最小化集成分类器的全局误差。核心思想是在每次迭代中，调整模型使其对困难样本（被之前模型错误分类的样本）给予更大的关注。

初始化每个样本的权重：

循环 t = 1 \ldots K：

在当前权重 d^{k-1} 下训练弱分类器 f_k：

计算加权错误率：

计算该弱分类器的权重：

更新样本权重：

当样本被正确分类时，y_i \hat{y}_i = 1，权重降低。当样本被错误分类时，y_i \hat{y}_i = -1，权重增加。

最终的强分类器：

梯度提升

梯度提升迭代地构建强分类器：

每一步的目标是最小化经验风险：

AdaBoost使用指数损失函数：

其他损失函数选择：

LogitBoost使用对数损失：l(y, f(x)) = \log_2(1 + \exp[-2y \cdot f(x)])

L_2 Boost使用平方损失：l(y, f(x)) = (y - f(x))^2 / 2

梯度提升模型的更新公式：

Boosting总结

优势：通过自适应聚合多个弱分类器构建强大的集成模型，有坚实的理论保证，能够提升几乎任何类型的基分类器的性能。劣势：对异常数据点敏感。使用建议：弱学习器不应太强，通常使用深度很浅的决策树（如深度为1的决策桩）。

考试例题：交叉验证与K-NN

考试题目给出如下数据分布：

图中十字形状和菱形形状分别表示两类数据。

留一法交叉验证比较1-NN和3-NN

留一法（Leave-One-Out）是交叉验证的极端情况，每次只留一个样本作为验证集，其余全部用于训练。对于每个样本，用剩余所有样本作为训练集，预测该样本的类别，最后统计错误率。

对于1-NN：观察图中数据，中心位置有一个被十字包围的菱形点。当这个菱形点作为测试样本时，它的最近邻很可能是周围的十字点，导致被错误分类为十字类。

对于3-NN：同样对于中心位置的菱形点，3-NN会考虑最近的3个邻居进行投票。如果3个邻居中有2个或以上是菱形，则预测正确；如果2个或以上是十字，则预测错误。由于3-NN通过多数投票，鲁棒性更好。

在这个例子中，使用留一法可以最大化利用有限的数据，公平比较1-NN和3-NN的泛化能力。从数据分布来看，3-NN通常是更优秀的分类器，因为它能够抵抗单个噪声点的影响。

统计学习理论基础

泛化问题引入

考虑回归问题，存在一个真实的底层函数 f(x)，这个函数是我们想要估计的目标但本身未知。我们能够获得的只是一组观测数据：

观测值 y_i 并不等于 f(x_i)，而是被噪声 \epsilon 污染了：

预测器与误差度量

目标是找到一个预测器 f(x; \mathbf{w})，其中 \mathbf{w} 是需要学习的参数向量。为了量化预测器的好坏，引入均方根误差（RMSE）：

先对每个样本计算预测误差的平方，然后求所有样本的平均值，最后取平方根使得误差的量纲与原始数据一致。

广义线性模型

将预测器表示为一组基函数 \phi_k(x) 的线性组合：

\mathbf{w} = [w_0, w_1, \ldots, w_M]^t 是权重向量，\phi(x) = [\phi_0(x), \phi_1(x), \ldots, \phi_M(x)]^t 是将输入 x 映射到 M+1 维特征空间的基函数向量。模型对于参数 \mathbf{w} 是线性的，但由于基函数可以是 x 的任意非线性函数，因此模型对于输入 x 可以是非线性的。

典型选择是令基函数为单项式 \phi_k(x) = x^k，此时预测器变为 M 次多项式：

最小二乘解

定义设计矩阵 \mathbf{\Phi} 为 n \times (M+1) 的矩阵，元素为 \Phi_{i,k} = \phi_k(x_i)。令 \mathbf{y} = [y_1, y_2, \ldots, y_n]^t 为观测值向量。最优参数的闭式解：

矩阵 (\mathbf{\Phi}^t \mathbf{\Phi})^{-1} \mathbf{\Phi}^t 称为 \mathbf{\Phi} 的伪逆。

模型复杂度与拟合效果

当 M=0 时，模型退化为常数，完全无法捕捉数据中的变化趋势（欠拟合）。当 M=1 时，模型为直线，能捕捉大致趋势但无法表达曲线弯曲特性。当 M=3 时，三次多项式能较好地逼近真实函数。当 M=9 时，九次多项式试图穿过每一个数据点，在数据点之间剧烈震荡（过拟合）。

训练误差与测试误差

当 M 很小时，模型容量不足，训练误差和测试误差都很大（欠拟合）。随着 M 增加到中等水平，两者都处于较低水平。当 M 继续增大到接近样本数量时，训练误差趋近于零，但测试误差急剧上升（过拟合）。

泛化误差

泛化误差是指模型在新数据（训练时未见过的数据）上产生的误差。训练数据的作用是作为建模的手段，最终评判模型好坏的标准是它在新数据上的表现。

两种需要避免的极端情况：过于简单的模型（训练误差和测试误差都很大），过拟合（训练集上表现优异但测试集上表现很差）。

偏差-方差分解

在回归问题 y = f(\mathbf{x}) + \epsilon 中，存在两个独立的随机性来源：观测噪声 \epsilon，训练数据的采样 D_n。

对于给定的输入 \mathbf{x}，预测误差可以精确分解为：

噪声项 \epsilon^2 是不可约减的，来自数据本身的随机性。偏差项度量模型的平均预测与真实值的偏离程度，高偏差意味着模型系统性地偏离目标。方差项度量模型预测随训练集变化的波动程度，高方差意味着模型对数据过于敏感。

偏差-方差权衡可视化

多项式次数为1时：所有拟合曲线都非常接近（方差小），但平均与真实函数相差很大（偏差大）。多项式次数为5时：偏差和方差都处于较低水平，达到良好平衡。多项式次数为20时：拟合曲线极度分散（方差大），但平均曲线与真实函数吻合（偏差小）。

过拟合的本质：系数爆炸

当 M=9 时，系数的绝对值达到数十万甚至百万级别。巨大的系数导致多项式曲线在相邻数据点之间剧烈震荡，这是过拟合的数学表现：模型通过极端的参数值来记忆每个训练样本。

岭回归（正则化最小二乘）

正则化的核心思想是在原有损失函数的基础上添加惩罚项，阻止系数变得过大：

\lambda \geq 0 是正则化系数，\|\mathbf{w}\|^2 = \sum_j w_j^2 是参数向量的平方范数。第一项要求预测值接近观测值，第二项要求参数值不要太大。

最优参数的闭式解：

与不带正则化的解相比，唯一区别是矩阵对角线上增加了 \lambda。这保证矩阵可逆，同时使最优解各分量趋向于更小的值。

正则化系数的影响

当 \lambda 很小时，正则化几乎不起作用，模型处于过拟合状态。随着 \lambda 增大，测试误差先下降后上升，存在一个最优的 \lambda 值。当 \lambda 过大时，模型被迫使用很小的参数值，导致欠拟合。\lambda 可以被理解为复杂度控制参数：\lambda 越大，模型的有效复杂度越低。

数据量的影响

使用相同的九次多项式（M=9）：当 N=10 时严重过拟合，当 N=15 时过拟合程度缓解，当 N=100 时拟合曲线变得平滑。数据量本身也是一种隐式的正则化手段。

三个容易混淆的概念

经验风险（训练数据上计算的平均损失）：

泛化误差（整个数据分布上的期望损失）：

优化准则（实际优化的目标）：

三者的关系：最小化优化准则来训练模型，希望得到的模型具有较低的泛化误差，而经验风险是泛化误差的一个有偏估计。

K折交叉验证

将全部训练数据划分为 k 个大小相等的子集。选择其中一个子集作为验证集，其余 k-1 个子集合并作为训练集。轮换验证集的选择，让每个子集都恰好充当一次验证集，共进行 k 次训练和验证。最终的泛化误差估计值是 k 次验证误差的平均值。

留一法

留一法（LOO）是 k 折交叉验证的极端情况，其中 k = n。每次只留出一个样本作为验证集，用其余 n-1 个样本训练模型。优点是每次训练都使用了几乎全部数据，估计的偏差较小。缺点是计算代价高，需要训练 n 个模型。

交叉验证调参流程

将原始数据集划分为训练数据和测试数据。对于每一组待选的超参数值，在训练数据上进行交叉验证。选择使交叉验证误差最小的超参数。使用最优超参数在全部训练数据上重新训练模型。最后在测试数据上评估最终模型的性能。

经验风险最小化原理

考虑预测函数 f: \mathcal{X} \to \mathcal{Y}。训练数据集 D_n = \{(x_i, y_i)\}_{1 \leq i \leq n} 包含 n 个独立同分布样本。

损失函数 l(y, y') 度量真实标签与预测值之间的差异。0-1损失函数：

真实风险（在整个数据分布上的期望损失）：

经验风险（训练样本上的平均损失）：

ERM算法在预测器族 \mathcal{F} 中找到使经验风险最小的预测器：

误差的结构分解

学到的预测器与最优预测器之间的差距分解为：

f^* = \arg\min_{f \in \mathcal{F}} L(f) 是预测器族 \mathcal{F} 中真实风险最小的函数，L^* = \inf_f L(f) 是贝叶斯误差。

逼近误差度量模型族 \mathcal{F} 的表达能力限制，是确定性的，只取决于模型族选择和问题本身。估计误差度量由于只有有限训练数据而导致的误差，是随机的，依赖于具体抽取到的训练数据。

PAC学习核心定理

在简化情形下（有限预测器族、可实现假设），可以证明：

这个不等式给出了泛化误差超过 \epsilon 的概率上界，依赖于模型族大小 |\mathcal{F}|、训练样本数 n 和误差容忍度 \epsilon。

样本复杂度

如果希望以至少 1 - \delta 的概率保证泛化误差不超过 \epsilon，只需让 |\mathcal{F}|e^{-n\epsilon} \leq \delta，解得：

m(\epsilon, \delta) 称为样本复杂度，给出达到指定精度和置信度所需的最小样本数量。样本复杂度不依赖于数据的真实分布（分布无关性）。

PAC可学习的定义

预测器族 \mathcal{F} 被称为PAC可学习的，如果存在函数 m: ]0,1[^2 \to \mathbb{N} 和学习算法，使得：

PAC（Probably Approximately Correct）：通过足够多的样本，可以以高概率获得近似正确的预测器。

不可知PAC学习

当 \min_{f \in \mathcal{F}}L(f) > 0 时（模型族中不存在完美预测器），以概率 1 - \delta：

样本复杂度：

不可知情形对 \epsilon 的依赖从 1/\epsilon 变为 1/\epsilon^2。

Hoeffding不等式

设 Z_1, Z_2, \ldots, Z_n 是独立同分布的随机变量，取值在 [0, 1] 区间内。则：

样本均值偏离期望值的概率随 n 和 \epsilon^2 指数衰减。

增长函数

增长函数定义为：

在输入空间中选取 n 个点，看模型族中所有预测器在这 n 个点上能够产生多少种不同的输出组合。对于二分类问题，G_{\mathcal{F}}(n) \leq 2^n。

VC维度

如果对于一组 n 个数据点，无论给这些点赋予什么样的二元标签组合（共 2^n 种），都存在模型族中的某个预测器能够完美实现这种标签划分，则称模型族打散（shatter）了该点集。

VC维度定义为能够被模型族打散的最大点集的大小：

Sauer引理

如果 \text{VC-dim}(\mathcal{F}) = d < \infty，则：

当 n > d + 1 时，G_{\mathcal{F}}(n) \leq (e \cdot n/d)^d。一旦 n 超过VC维度，增长函数从指数增长变为多项式增长。

VC维度示例

\mathbb{R}^2 中的线性分类器（直线）：对于三个不共线的点，所有 2^3 = 8 种标签组合都能由某条直线实现。但对于四个点，无论怎么放置都无法被直线打散。因此 \text{VC-dim} = 3。

更一般地，\mathbb{R}^d 中线性分类器的VC维度为 d + 1。

VC维度与估计误差

如果 \text{VC-dim}(\mathcal{F}) = d 有限，则以概率 1 - \delta：

如果模型族的VC维度有限，则该模型族是PAC可学习的。如果VC维度是无穷大，则该模型族不是PAC可学习的。这是统计学习的基本定理。

常见模型族的VC维度

\mathbb{R}^d 中超平面：d + 1。\mathbb{R}^2 中轴对齐矩形：4。\mathbb{R}^2 中任意方向矩形：7。\mathbb{R}^2 中凸多边形：\infty。

ReLU神经网络（W 个参数，L 层）：

Rademacher复杂度

定义为：

\sigma_i 是独立同分布的Rademacher随机变量，以等概率取值 +1 或 -1。

Rademacher复杂度度量模型族与纯随机噪声标签的最大相关程度，依赖于数据的具体分布，可以给出比VC维度更精细的界。

与增长函数的联系：

以概率 1 - \delta：

样本复杂度总结

有限模型族可实现情形（|\mathcal{F}| < \infty，\inf L(f) = 0）：

有限模型族不可知情形：

无限模型族可实现情形（\text{VC-dim} = d）：

无限模型族不可知情形：

深度学习中的误差分解

考虑优化误差后，泛化误差分解为：

随机梯度下降具有隐式正则化效果，倾向于收敛到平坦的极小值点，这些极小值通常对应更好的泛化性能。

双下降现象

经典观点：随着模型容量增加，测试风险先下降后上升，呈U形曲线。

现代观察：当模型容量达到刚好能完美拟合训练数据的临界点（插值阈值）时，测试风险达到峰值。但当模型容量继续增大进入过参数化区域时，测试风险不升反降。

这挑战了经典偏差-方差权衡的简单图景，表明深度学习中存在传统理论未能捕捉的机制。

正则化与支持向量机

支持向量机概述

支持向量机（SVM）是一种通过最大化分离间隔来寻找最优分类超平面的算法。核心思想是：在所有能够正确分类训练数据的超平面中，选择距离两类数据最远的那个。

线性分类器

超平面的方程为：

线性分类器的决策函数：

类别标签 y_i 取值为 -1 或 +1。分类误差为：

超平面选择问题

对于线性可分的数据，存在无穷多个能够正确分类的超平面。从泛化角度考虑，最好的超平面应该位于两类数据的中间位置，与两侧的数据点都保持足够的距离。

大间隔分类器

SVM选择能最大化到最近数据点距离的超平面。间隔大意味着分类器对数据中的小扰动具有更强的鲁棒性。

间隔的数学推导

分类约束条件：对于正类样本（y_i = 1）要求 \mathbf{x}_i \cdot \mathbf{w} + b \geq 1，对于负类样本（y_i = -1）要求 \mathbf{x}_i \cdot \mathbf{w} + b \leq -1。

支持向量是那些恰好位于边界上的样本点，满足 \mathbf{x}_i \cdot \mathbf{w} + b = \pm 1。

点到超平面的距离为：

间隔宽度：

因此最大化间隔等价于最小化 \|\mathbf{w}\|。

SVM的优化问题

标准形式：

约束条件：

这是带线性约束的二次规划问题。

软间隔分类

实际数据往往不是严格线性可分的。软间隔分类允许一部分样本违反约束，但对违反程度进行惩罚。

引入松弛变量 \varsigma_i，约束修改为：

当 \varsigma_i = 0 时满足硬间隔约束，当 0 < \varsigma_i < 1 时样本位于间隔区域内，当 \varsigma_i \geq 1 时样本被错误分类。

目标函数修改为：

参数 C 控制间隔最大化与约束违反惩罚之间的权衡。

无约束等价形式

最优的松弛变量取值为：

代入后得到无约束优化问题：

其中 \max(0, 1 - y_i(w \cdot x_i + b)) 是hinge损失函数。

软间隔SVM与正则化框架

软间隔SVM可以重新整理为标准的经验误差加正则化形式：

正则化项 r(\mathbf{w}) = \frac{1}{C}\|\mathbf{w}\|^2，损失函数 l = \max(0, 1 - y_i(\mathbf{w} \cdot \mathbf{x}_i + b))。

损失函数比较

0-1损失：l(y, y') = \mathbf{1}[yy' \leq 0]（不可微，无法直接优化）

Hinge损失：l(y, y') = \max(0, 1 - yy')（SVM使用）

平方损失：l(y, y') = (y - y')^2

指数损失：l(y, y') = \exp(-yy')（AdaBoost使用）

对偶问题

通过拉格朗日对偶理论，原始问题转化为：

约束条件：0 \leq \alpha_i \leq C

根据KKT条件，最优权重向量可以表示为：

只有 \alpha_i > 0 的样本（支持向量）才参与这个组合。

非线性可分数据的处理

通过非线性变换 \phi(\boldsymbol{x}) 将原始数据映射到更高维的空间，使得在新空间中数据变得线性可分。

核技巧

对偶问题中数据点只以点积形式出现。定义核函数：

某些核函数可以直接在原始空间中高效计算，无需显式执行映射。

基于核函数的决策函数：

常用核函数

多项式核：K(\boldsymbol{x}, \boldsymbol{y}) = (\boldsymbol{x} \cdot \boldsymbol{y} + 1)^d

高斯核（RBF核）：K(\boldsymbol{x}, \boldsymbol{y}) = \exp\left(-\frac{(\boldsymbol{x} - \boldsymbol{y})^T(\boldsymbol{x} - \boldsymbol{y})}{2\sigma^2}\right)

直方图交叉核：K(\boldsymbol{x}, \boldsymbol{y}) = \sum_i \min(x^i, y^i)

多类别分类

一对一策略（OVO）：为每一对类别训练一个二分类器，共 N(N-1)/2 个，预测时投票。

一对其余策略（OVR）：为每个类别训练一个分类器，共 N 个，预测时选输出分数最高的类别。

回归

回归问题的数学表述

模型形式：

f(x, W) 是确定性预测函数，\varepsilon 是随机误差项（通常假设服从高斯分布）。

广义线性模型

引入基函数后，模型变为：

基函数 \phi_i(\mathbf{x}) 可以是任意复杂的非线性函数，但模型对于参数 \mathbf{w} 仍然是线性的。

误差准则

平方误差：

最小二乘解

设计矩阵 \Phi 是 N \times M 矩阵，元素为 \Phi_{n,j} = \phi_j(\mathbf{x}_n)。

最优参数的闭式解：

(\mathbf{\Phi}^T \mathbf{\Phi})^{-1} \mathbf{\Phi}^T 称为伪逆。

正则化最小二乘

在损失函数中添加惩罚项：

加入L2正则化后的解析解：

\lambda 是正则化系数，控制数据拟合与参数惩罚之间的权衡。

L2正则化的几何理解

数据拟合项形成椭圆形等高线，正则化项形成以原点为中心的圆形等高线。最优解位于两者的平衡点，正则化将解向原点方向拉近。

L1与L2正则化对比

L2正则化（Ridge）：约束区域是圆形，解通常各分量非零。

L1正则化（Lasso）：约束区域是菱形，解倾向于落在坐标轴上，产生稀疏性。

更多正则化方法

Elastic-Net：\psi(\mathbf{w}) = \|\mathbf{w}\|_1 + \gamma\|\mathbf{w}\|_2^2（结合L1和L2）

Group Lasso：\psi(\mathbf{w}) = \sum_{g \in G} \eta_g \|\mathbf{w}_g\|_2（整组选择或排除特征）

Fused-Lasso：惩罚相邻参数差异，产生分段常数解

支持向量回归

优化目标：

使用 \epsilon-不敏感损失：

预测误差在 \epsilon 范围内不计入损失，超过后线性增长。

贝叶斯回归

将模型参数视为随机变量。似然函数：

先验分布：

取后验分布的负对数：

正则化系数与贝叶斯超参数的关系：\lambda = \frac{\alpha}{\beta}

贝叶斯回归的后验演变

随着观测数据增多，后验分布逐渐收缩，不确定性减小。大样本情况下，贝叶斯估计与最大似然估计趋于一致。

预测分布

对新输入的预测对所有可能参数值加权平均：

参数不确定性自然传递到预测不确定性中。

粉色阴影表示置信区间，绿色曲线是从后验采样的函数。数据点增多时，置信区间收窄，采样曲线趋于一致。

深度学习中的回归

神经网络的基函数通过学习自动获得。常用的正则化策略包括：权重衰减（L2正则化）、Dropout（随机置零部分神经元）、早停（验证集误差上升时停止）、添加噪声、多任务学习。

六维姿态估计应用

从图像估计物体的位置（3个平移参数）和朝向（3个旋转参数）。网络同时输出类别（分类）和6D姿态（回归）。

深度学习图像超分辨率

从低分辨率图像重建高分辨率图像。各种架构（VDSR、SRResNet、EDSR等）都使用端到端的深度卷积网络，通过残差学习和跳跃连接缓解训练困难。

回归模型评估

以预测为目标：关注泛化能力，通过测试集计算预测误差，超参数通过交叉验证选择。

以建模为目标：关注解释能力，使用 R^2（决定系数）和p值等统计检验指标。

高维数据处理策略

特征投影与构造：通过PCA等降维技术

特征选择：挑选最相关的特征子集

稀疏方法：通过L1正则化自动实现特征选择

异常值处理

正则化可以减轻异常值影响

鲁棒估计器使用对异常值不敏感的损失函数（如Huber损失）

RANSAC通过随机采样识别内点，排除异常值

神经网络导论

人工智能的历史演进

人工智能的发展存在两条并行的技术路线：符号主义和连接主义（神经网络）。

1943年McCulloch和Pitts提出了神经元的数学激活模型。1957年到1962年间，Rosenblatt开发了感知机，这是第一个可以学习的神经网络模型。1969年Minsky和Papert指出单层感知机无法解决异或（XOR）等线性不可分问题，导致神经网络研究进入第一次寒冬。

1986年Rumelhart等人提出了反向传播算法，使得训练多层神经网络成为可能。2012年AlexNet在ImageNet竞赛中大幅领先，深度学习开始崛起。

深度学习的成功依赖于四个关键要素：数据（ImageNet提供了1400万张图像）、软件生态（TensorFlow、PyTorch等框架）、硬件支持（GPU并行计算）、算法创新。

生物神经元与人工神经元

生物神经元由树突（接收信号）、胞体（整合信号）、轴突（传递信号）组成。当输入信号累积超过阈值时，神经元产生电脉冲。

人工神经元的数学表达式：

每个输入 x_i 通过权重 w_i 加权，所有加权输入求和后加上偏置 b，然后通过激活函数 f 产生输出。

激活函数

Sigmoid函数：\sigma(x) = \frac{1}{1+e^{-x}}，输出范围 (0,1)，存在梯度消失问题。

tanh函数：输出范围 (-1,1)，零中心，同样存在梯度消失问题。

ReLU函数：\max(0,x)，计算简单，正区间梯度恒为1，是现代深度网络最常用的激活函数。存在神经元死亡问题。

Leaky ReLU：\max(0.1x, x)，在负区间保留小斜率，避免神经元死亡。

从单神经元到网络

将多个神经元组合成层，向量形式：

权重矩阵 \boldsymbol{W} \in \mathbb{R}^{p \times d}，每一行对应一个神经元的所有输入权重。

感知机学习算法

算法首先用随机值初始化权重向量。对于每个样本，计算线性组合 z_i = \mathbf{w}^T \mathbf{x}_i + b，通过阶跃函数得到预测输出。如果分类错误，更新参数：

当一整轮没有任何错误时退出循环。

感知机的局限性

AND和OR运算可以用直线分开，但XOR运算无论怎样画直线都无法将两类分开。单层感知机连简单的异或逻辑都无法学习。

多层神经网络

多层网络通过堆叠多层神经元来增强函数的表达能力：

非线性激活的必要性

在原始输入空间中，两类数据点呈现XOR分布，用任何直线都无法分开。经过激活函数的非线性变换后，在变换后的隐藏空间中，两类数据点被清晰地分开。

通用逼近定理

只需要一个隐藏层加上非多项式的激活函数，神经网络就能以任意精度逼近任意连续函数。Cybenko在1989年证明了Sigmoid网络的逼近能力。

优化问题的形式化

最优参数定义为：

代价函数度量预测误差的统计量：

梯度下降算法

沿着函数下降最快的方向迭代移动：

\lambda 是学习率，控制每一步移动的距离。

梯度下降的实践问题

狭窄山谷问题：梯度方向与指向最优点的方向有较大偏差，算法会在山谷两侧来回震荡。

局部极小值问题：非凸函数存在多个局部极小值点，梯度下降可能被困住。

学习率过大会震荡甚至发散，过小则收敛速度很慢。

随机梯度下降

用梯度的无偏估计代替精确梯度，每次迭代只随机抽取一小批样本：

batch大小为1时梯度估计方差很大，轨迹呈锯齿形震荡。batch较大时轨迹更平滑但每步计算量更大。实践中通常选择32到256之间的batch大小。

反向传播与链式法则

标量情况的链式法则：

向量情况的链式法则：

向量形式：

多层网络中的反向传播

m 层全连接网络，每层计算：

梯度的反向传播：

参数梯度：

单层雅可比矩阵

F_j 对前一层输出的偏导数：

F_j 对权重矩阵的偏导数：

F_j 对偏置的偏导数：

常用代价函数

均方误差（用于回归）：

二元交叉熵（用于二分类）：

多分类交叉熵：

Softmax函数将任意实数向量映射为概率分布：

神经网络训练流程

从训练集中采样一批样本（batch）。执行前向传播，计算所有层激活值。计算代价函数值。执行反向传播，计算所有参数的梯度。进行梯度下降，更新网络参数。根据调度策略更新学习率。

训练准确率和验证准确率在训练初期都快速上升，然后趋于平稳。训练损失持续下降，验证损失在下降到某点后可能开始上升。两条曲线差距很大说明发生了过拟合。

学习曲线的解读

传统机器学习理论：随着模型复杂度增加，偏差降低但方差升高，总误差呈U形曲线。

从梯度下降角度看：训练集准确率单调上升，测试集准确率先上升后下降。两条曲线分离的点标志着过拟合开始，此时应该停止训练（Early Stopping）。

神经网络的反直觉现象

Grokking现象：模型在训练集上很快达到完美准确率，但在验证集上长时间停滞，然后突然跃升。

Double Descent现象：随着模型复杂度增加，测试误差先下降、后上升，但继续增加复杂度后又开始下降。

这一现象挑战了传统的偏差-方差权衡理论。

正则化技术

传统正则化：在损失函数中添加 L_2 惩罚项 \lambda \|\mathbf{W}\|_2^2。

神经网络特有的正则化：Dropout（随机将部分神经元输出置零）、自适应学习率方法（如Adam）、Batch Normalization（对每层输入进行标准化）。

本章总结

人工神经网络是通用的参数化函数逼近器。学习问题形式化为最小化依赖于数据的代价函数。网络架构决定函数空间的结构。随机梯度下降是训练的通用算法。反向传播使梯度计算可以自动完成。向量化的数学表达使计算可以在GPU上高效并行执行。

深度学习导论

深度网络的动机

深度网络的设计灵感来源于大脑的层状结构。视觉皮层从初级到高级区域，神经元逐渐从检测简单的边缘、纹理发展到识别复杂的物体和场景。

深度网络的核心思想是将复杂任务分解为多个简单功能的组合，同时完成特征提取和分类。浅层捕捉局部的、细粒度的特征（如边缘、角点），深层整合这些局部特征形成全局的、语义级别的表示（如物体部件、整体形状）。

从函数逼近理论角度，对于某些类型的函数，使用深层网络可以用指数级更少的神经元来逼近，而浅层网络则需要指数级更多的神经元。

端到端学习框架

传统方法首先通过人工设计的特征提取函数 T 将原始数据映射为特征向量：

然后预测函数 F 根据特征向量给出预测结果：

深度网络将特征提取 T 和预测 F 统一到一个端到端可训练的框架中，中间的特征表示由网络自动学习得到。

卷积神经网络的历史演进

Neocognitron（1980年）是第一个引入卷积层概念的神经网络模型，由交替排列的 S 层（特征检测）和 C 层（空间池化）组成。

LeNet（1989年）将反向传播算法应用于卷积层的训练，使整个网络可以端到端地通过梯度下降优化。

LeNet5（1998年）接收 32 \times 32 灰度图像，采用卷积层与池化层交替的结构，总参数量约6万。

AlexNet（2012年）在ImageNet上取得突破，top-5错误率从26%降至16.4%。输入 227 \times 227 \times 3 RGB图像，总参数量约6200万，是LeNet5的1000倍。

AlexNet成功的关键因素：ReLU激活函数、Dropout防止过拟合、GPU并行计算、数据增强。

经典卷积网络架构

VGGNet（2014年）只使用 3 \times 3 卷积核，通过堆叠多个小卷积核获得大感受野。Top-5准确率92.30%，参数量138M。

Inception（2014年）在同一层同时使用多个不同尺寸的卷积核，将输出在通道维度拼接。Top-5准确率93.30%，参数量仅6.4M。

ResNet（2015年）引入残差连接，使训练数百层的网络成为可能。ResNet-152 Top-5准确率95.51%，参数量60.3M。

全连接网络处理图像的局限性

将整幅图像展平成一维向量输入全连接层存在两个问题：参数数量过于庞大，忽略了图像的空间结构。卷积层通过局部连接和权重共享解决这两个问题。

卷积操作

卷积核在输入图像上滑动，每个位置将卷积核覆盖的区域与卷积核逐元素相乘再求和。

不同的卷积核权重对应不同的滤波效果，如边缘检测：

水平边缘检测Sobel滤波器：

多通道卷积

处理多通道输入时，为每个输入通道配备一个二维卷积核，将各通道的卷积结果相加得到单通道输出。

卷积的数学形式化

输出特征图在位置 (h, l) 处的值：

卷积层通过权重共享和局部连接，将参数数量从 O(H^2 \times L^2)（全连接层）降低到 O(\delta_H \times \delta_L)。

多输出通道的卷积

使用多个卷积核产生多个输出通道，每个卷积核学习检测一种特定的特征模式。

感受野

感受野是输出特征图上某个神经元所能"看到"的输入图像区域。

连续三个 3 \times 3 卷积：第一层感受野 3 \times 3，第二层 5 \times 5，第三层 7 \times 7。每增加一层 3 \times 3 卷积，感受野边长增加2。

步长与填充

步长控制卷积核滑动的间隔，步长大于1时实现下采样。

填充在输入边界填充额外的值（通常为零），使输出尺寸与输入相同。

输出尺寸计算公式

给定输入尺寸 W_1 \times H_1，卷积核尺寸 F，步长 S，填充量 P：

池化层

池化层降低特征图的空间分辨率，减少计算量、扩大感受野、提供平移不变性。

最大池化在每个池化窗口内取最大值：

VGG16架构详解

16个权重层，统一使用 3 \times 3 卷积核。总内存约24M个数值（约96MB每张图像），总参数量约138M。

参数主要集中在全连接层（约90%），内存占用主要集中在早期卷积层。

梯度下降的困难

损失曲面存在平坦区域（梯度接近零）、鞍点（既非极大也非极小）、局部极小值。

改进的优化算法

动量法：

更新方向是历史梯度的指数加权平均，能够穿越平坦区域并减少震荡。

RMSprop引入自适应学习率：

Adam结合动量法和RMSprop的优点，是目前最常用的优化器。

激活函数选择

ReLU：\text{ReLU}(x) = \max(0, x)，正区间梯度恒为1，计算简单。存在神经元死亡问题。

Leaky ReLU：\max(0.1x, x)，负区间保留小斜率，避免神经元死亡。

实践建议：ReLU是默认首选，如果遇到神经元死亡问题可尝试Leaky ReLU。不推荐Sigmoid或tanh作为隐藏层激活函数。

批归一化

对每个神经元的激活值进行归一化：

使训练过程更加稳定和快速，通常能带来更好的泛化性能。

残差层

输入 x 不仅经过卷积层得到 F(x)，还通过恒等映射路径与 F(x) 相加，输出为 F(x) + x。

梯度可以通过跳跃连接直接从深层传递到浅层，避免梯度消失，使训练超过100层的网络成为可能。

Dropout

训练时以概率 p 随机将部分神经元输出置零。测试时使用所有神经元，权重需要缩放。

相当于隐式的集成学习，同时训练了指数级数量的不同子网络。

批量大小的影响

较大的批量更新更稳定但更新频率更低。经验法则：学习率与批量大小的平方根成比例：

Xavier初始化

使每层的输入和输出具有相同的方差。神经元输出 Y 是 n 个输入的加权和：

为使 \text{var}(Y) = \text{var}(X)，需要 \text{var}(W) = \frac{1}{n}。

数据增强

通过对现有数据施加保持语义不变的变换扩充训练集：旋转、翻转、裁剪、颜色变换等。

AutoAugment等方法可以自动学习增强策略。

迁移学习与微调

直接使用：完整的预训练网络，适用于相同任务。

固定特征提取：冻结卷积层参数，只训练新分类器，适用于数据量较少的情况。

微调：底层冻结、高层允许更新，同时训练新分类器。使用较小的学习率，避免破坏预训练特征。

基础模型

基础模型在大规模、多样化的数据上进行预训练，然后通过适配应用于各种下游任务。训练数据涵盖文本、图像、语音等多种模态。同一个基础模型可以被应用于问答、情感分析、图像描述、物体识别等多种任务。

稠密预测网络

U-Net用于图像分割：编码器-解码器结构加跳跃连接。编码器通过卷积和池化降低分辨率、提取语义特征；解码器通过上采样恢复分辨率；跳跃连接帮助恢复细节信息。

Transformer用于序列到序列任务：核心机制是多头自注意力。编码器将输入序列编码为上下文表示，解码器自回归地生成输出序列。

总结

深度学习的核心是多层神经元网络通过随机梯度下降进行端到端学习。优化过程是关键挑战，需要精心选择算法、学习率、初始化方法。架构设计的细节对性能有显著影响。对于图像、文本和语音，深度学习已成为最主流和最有效的方法。

无监督学习

机器学习的三大范式

监督学习：每个输入样本都有对应的正确输出标签，包括分类任务（离散类别）和回归任务（连续数值）。

无监督学习：训练数据没有标签，模型需要自己发现数据中隐藏的结构和模式，包括聚类（将相似数据点分组）和降维（减少数据维度）。

强化学习：智能体通过与环境交互，根据奖励信号学习最优策略。

无监督学习的必要性

高维数据带来的挑战：信息冗余和不相关性，维度灾难（50个维度、每维20个级别，空间单元格数量为 20^{50}），处理时间随维度急剧上升。

大规模数据的需求：有效存储和提取相关信息，全局可视化理解数据结构。标注成本高昂，大多数数据是无标注的。

无监督学习的典型应用

蛋白质结构预测中的预训练：对2.5亿条蛋白质序列进行无监督学习，使用预训练模型在蛋白质折叠分类任务上准确率达70.6%到82.4%，而不使用预训练仅为32.4%到36.6%。

三维点云去噪：在没有干净数据作为监督信号的情况下学习去除噪声。

表示学习

PCA的直观理解

主成分分析的核心思想类似于选择画三维物体的最佳视角。从正上方或正前方看鱼都丢失太多信息，侧面视角能清晰呈现鱼的特征。PCA寻找数据变化最大的方向，沿这些方向投影能最大程度保留数据的差异性。

PCA的几何目标

两种等价的设计原则：

近似原则：最小化重构误差

表示原则：最大化投影后数据的方差

PCA的两种等价原理

设投影方向为单位向量 \mathbf{u}，投影后数据的方差为：

根据勾股定理：\|\mathbf{a}_i\|^2 = \|w_i\mathbf{c}\|^2 + \|\mathbf{a}_i - w_i\mathbf{c}\|^2

左边是常数，因此最大化投影方差等价于最小化重构误差。

PCA的求解方法

使用拉格朗日乘数法，构造：

对 \mathbf{u} 求导并令导数为零，得到特征值问题：

最优投影方向 \mathbf{u} 是协方差矩阵 \mathbf{X}\mathbf{X}^T 的特征向量。

PCA = 对协方差矩阵做特征值分解，取最大的几个特征值对应的特征向量作为主成分方向。

重构误差与特征值的关系

选择前 p 个特征向量时，重构误差为：

重构误差等于被舍弃的那些特征值的平方和。

PCA应用实例

三维鱼形数据的特征值矩阵：

前两个主成分捕获了约97%的方差，投影到前两个主成分清晰保留了鱼的轮廓形状。

字典学习

字典定义为矩阵 \mathbf{D} = [\mathbf{d}_1, \ldots, \mathbf{d}_m] \in \mathbb{R}^{d \times m}，数据表示为字典原子的线性组合：

追求稀疏编码，最优编码定义为：

L_1 范数促使许多系数变为零，产生稀疏解。

自监督学习

不需要人工标注就能学习数据表示。设计前置任务（如预测图像旋转角度、解决拼图问题、填补被遮挡区域），任务标签可以从数据本身自动生成，但解决任务需要模型理解数据的内在结构。

对比学习

核心原则是拉近相似样本的表示，推远不相似样本的表示。对比损失函数：

分子衡量正样本对的相似度，分母是与所有样本相似度的总和。

聚类分析

聚类的准则

邻近性准则：根据数据点之间的距离进行分组

相似性准则：根据共享的特征进行分组

密度准则：根据数据点的出现频率进行分组

不同算法在不同数据分布上表现差异显著。K-Means假设簇是凸形的，谱聚类和DBSCAN能处理非凸形状。

K-means算法

代价函数：

交替优化两个步骤：

分配步骤：将每个数据点分配到距离最近的簇中心

更新步骤：重新计算每个簇的中心（质心）：

K-means保证收敛到局部最优解，结果高度依赖于初始化。

K-means假设簇具有紧凑的球形结构，不适合处理非凸形状的簇。

谱聚类

将聚类问题转化为图的分割问题。构建相似度矩阵 \mathbf{W}，定义拉普拉斯矩阵：

对拉普拉斯矩阵进行特征分解，取最小特征值的特征向量，在变换后的空间中运行K-means。能够发现基于连接性而非欧氏距离的簇结构。

DBSCAN算法

基于两个参数：邻域半径 \epsilon 和最小点数 MinPts。

核心点：\epsilon 邻域内包含至少 MinPts 个点

边界点：不是核心点但落在某个核心点邻域内

噪声点：既不是核心点也不在任何核心点邻域内

优势：自动确定簇数量，能识别离群点，能发现任意形状的簇。

Mean Shift算法

迭代的密度模式检测算法。从任意点出发，计算邻域内所有点的加权平均位置：

结果会向密度更高的方向偏移，最终汇聚到密度峰值处。收敛到同一模式的所有点被归为一类。

可视化

t-SNE降维方法

t-SNE的目标是找到低维表示，使得数据点之间在低维空间中的相似性关系反映高维空间中的相似性关系。

高维空间中的相似度（高斯核）：

对称化：p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}

低维空间中的相似度（t分布）：

t分布具有更重的尾部，中等距离的点对会被推得更远，解决了拥挤问题。

最小化KL散度：

t-SNE可视化实例

左图：图像数据库可视化，相似图像被聚集在一起

右图：MNIST手写数字，同一数字的样本聚集，不同数字形成分离的簇

perplexity参数的影响

\sigma = 1：只考虑非常近的邻居，许多小的分散簇

\sigma = 30：十个数字类别形成清晰分离的簇

较小的perplexity强调局部结构，较大的perplexity更多保留全局结构。

其他降维可视化方法

多维缩放（MDS）：使低维距离尽可能接近高维距离：

局部线性嵌入（LLE）：假设每个点可由邻居线性组合表示，保持局部线性关系

UMAP：使用不同的相似度度量，更好地保留全局结构，计算效率优于t-SNE

注意：t-SNE及其变体不提供显式映射函数，主要目的是保持局部邻近关系，应关注局部簇结构而不应过度解读全局布局。

题目：逻辑回归可以用于分类。用对/错回答，并用一句简短的话进行说明。

答案：对。逻辑回归本质上是一个分类算法。逻辑回归通过sigmoid函数将线性组合的输出映射到 (0, 1) 区间，这个输出可以解释为样本属于正类的概率，设定阈值后即可进行分类决策。

题目：可以使用测试集通过交叉验证来调整学习算法的超参数。用对/错回答，并用一句简短的话进行说明。

答案：错。测试集的唯一目的是评估最终模型的泛化性能。如果用测试集调参，模型就间接地从测试集中学习了信息，导致对泛化能力的评估过于乐观。正确做法是使用训练集上进行交叉验证来选择超参数。

题目：当降低输入数据的维度时，存在过拟合的风险。用对/错回答，并用一句简短的话进行说明。

答案：错。降维通常是一种正则化手段，它通过减少特征数量来降低模型复杂度，从而减少过拟合的风险而非增加。过拟合通常发生在模型过于复杂、参数过多的情况下，而降维恰恰是在减少模型需要学习的参数量。当然，如果降维过度导致丢失了关键信息，可能会出现欠拟合

题目：在训练阶段，k-NN算法在计算时间上比逻辑回归更高效。用对/错回答，并用一句简短的话进行说明。

答案：对。k-NN是一种惰性学习算法，它在训练阶段几乎不做任何计算，只是简单地存储所有训练数据，而逻辑回归需要通过迭代优化（如梯度下降）来学习参数，训练时间与数据量和迭代次数相关。需要注意的是，k-NN虽然训练快，但预测阶段需要计算新样本与所有训练样本的距离，预测时间反而长。

题目：当SVM的核函数是线性的时，权重向量 w 是数据的线性组合。用对/错回答，并用一句简短的话进行说明。

答案：对。根据SVM的对偶形式，权重向量可以表示为：

其中 \alpha_i 是拉格朗日乘子，y_i 是标签，x_i 是数据点。这个表达式清楚地表明 w 是所有训练样本的线性组合，其中只有支持向量对应的 \alpha_i 非零。

题目：SVM的系数 C 可以为负值，前提是松弛变量为正。用对/错回答，并用一句简短的话进行说明。

答案：错。参数 C 是正则化系数，它控制对误分类样本的惩罚程度，在SVM的优化目标中出现为：

由于 C 乘以的是松弛变量 \xi_i 的和，而我们希望最小化这个目标函数同时惩罚误分类，C 必须为正值。如果 C 为负，优化过程会倾向于让松弛变量无限大，这与我们希望减少误分类的目标完全矛盾。

题目：C 越大，间隔越大。用对/错回答，并用一句简短的话进行说明。

答案：错。C 越大意味着对误分类的惩罚越严重，模型会更加努力地正确分类每一个训练样本，这会导致决策边界更加贴近数据点，从而使间隔变小。相反，C 越小，模型对误分类的容忍度越高，允许一些样本被误分类以换取更大的间隔。这体现了SVM中间隔最大化与训练误差最小化之间的权衡。

题目：不是支持向量的数据点，其对应的系数为零。用对/错回答，并用一句简短的话进行说明。

答案：对。在SVM的对偶问题中，每个数据点 x_i 都有一个对应的拉格朗日乘子 \alpha_i。根据KKT条件，只有那些位于间隔边界上或间隔内部的点（即支持向量）才有 \alpha_i > 0，而远离决策边界、被正确分类且不在间隔边界上的点，其 \alpha_i = 0。这意味着最终的决策函数只由支持向量决定，与其他数据点无关。

题目：计算分布的初始熵 H(Y) = -\sum_{i} P(Y = i) \log_2 P(Y = i)

根据图中的数据分布，共有16个数据点，其中星形（★）8个，圆形（●）8个。两类的概率分布为：

将概率代入熵的公式：

初始熵为1比特，这是二分类问题中熵的最大值，说明在没有任何属性信息的情况下，两类的不确定性最大。

题目：类型为 (x_2 > n) 的测试是否有意义？请基于划分后区域的同质性进行推理，无需进行计算。

答案：没有意义。观察数据分布可以发现，星形和圆形在 x_2 方向上的分布是交替混合的。无论选择哪个整数 n 作为 x_2 的分割阈值，划分后的两个区域内都会同时包含星形和圆形两类数据点，无法实现类别的有效分离。

题目：详细计算测试 (x_1 > 0) 的信息增益。

提示：信息增益定义为 IG(A) = H(Y) - H(Y|A)，且

按 (x_1 > 0) 进行垂直划分：

右半边 (x_1 > 0)：共8个点，★ 2个、● 6个

左半边 (x_1 \leq 0)：共8个点，★ 6个、● 2个

计算右半边的条件熵：

左半边的概率分布与右半边对称（3/4和1/4互换），熵值相同：

加权平均条件熵：

信息增益：

答案：IG(x_1 > 0) \approx 0.1887 bit

题目：对 (x_1 > 1) 进行同样的计算，并得出最佳的第一个测试的结论。

按 (x_1 > 1) 进行垂直划分：

右侧 (x_1 > 1)：共4个点，★ 1个、● 3个

左侧 (x_1 \leq 1)：共12个点，★ 7个、● 5个

计算右侧的条件熵：

计算左侧的条件熵：

加权平均条件熵：

信息增益：

结论：

最佳的第一个测试选 (x_1 > 0)，它能带来更大的信息增益。

题目：提出一棵深度为2的决策树，并给出每个叶子节点的决策和相关的概率分数。

第一层选择测试 (x_1 > 0)，将数据分为左右两部分。第二层需要在每个子区域内继续选择最优的划分。

对于左侧分支 (x_1 \leq 0)：该区域有6个★，2个●。可以选择测试 (x_1 > -1) 进一步划分。

对于右侧分支 (x_1 > 0)：该区域有2个★，6个●。可以选择测试 (x_1 > 1) 进一步划分。

决策树结构：

                      [x_1 > 0?]
                     /          \
                   否            是
                   /              \
            [x_1 > -1?]        [x_1 > 1?]
            /        \          /        \
          否          是      否          是
          /            \      /            \
      叶节点1      叶节点2  叶节点3      叶节点4

各叶节点的决策和概率分数（根据图中数据的具体分布）：

叶节点1（x_1 \leq -1）：决策为★，

叶节点2（-1 < x_1 \leq 0）：决策为★，

叶节点3（0 < x_1 \leq 1）：决策为●，

叶节点4（x_1 > 1）：决策为●，P(\text{●}) = \frac{3}{4} = 0.75，P(\text{★}) = \frac{1}{4} = 0.25

题目：我们想要构建一个应用程序，能够从一张RGB图像中自动识别出一个披萨的配料组成。共有10种可能的配料。我们拥有一个包含5000张大小为64x64的图像数据库。需要实现什么类型的函数？如何评估它？

这是一个多标签分类问题。与传统的多分类问题不同，多分类是从多个类别中选择唯一的一个，而多标签分类允许一个样本同时属于多个类别。在本问题中，一张披萨图片可以同时包含多种配料，例如同时有蘑菇、培根和番茄。

需要实现的函数是 f: \mathbb{R}^{64 \times 64 \times 3} \rightarrow \{0, 1\}^{10}，输入是一张64×64的RGB图像，输出是一个长度为10的二值向量，每个位置表示对应配料是否存在。实际实现中，网络输出的是10个介于0和1之间的概率值，通过设定阈值（通常为0.5）转换为二值预测。

评估指标可以采用多种方式。逐标签的准确率、精确率、召回率和F1分数是常用的指标。也可以使用汉明损失（Hamming Loss），它衡量预测错误的标签比例。对于整体评估，可以使用精确匹配率（Exact Match Ratio），即预测的标签集合与真实标签集合完全一致的样本比例。

题目：应该使用什么类型的学习方法？使用什么损失函数？

应该使用监督学习方法，具体而言是深度卷积神经网络，因为输入是图像数据，CNN能够有效提取图像的空间特征和层次化表示。

损失函数应该使用二元交叉熵损失（Binary Cross-Entropy Loss），也称为BCE损失。对于多标签分类，我们将问题分解为10个独立的二分类问题，每个配料对应一个二分类任务。损失函数为：

其中 N 是样本数量，y_{ij} \in \{0, 1\} 是第 i 个样本第 j 个配料的真实标签，\hat{y}_{ij} \in (0, 1) 是模型预测的概率。网络最后一层使用sigmoid激活函数而非softmax，因为各个配料的存在与否是相互独立的。

----------------------------------------------------------------
        Layer (type)               Output Shape         Param #
================================================================
            Conv2d-1           [64, 32, 64, 64]           2,432
            Conv2d-2           [64, 64, 32, 32]          18,496
           Linear-3                   [64, 10]         655,370
================================================================
Total params: 676,298
Trainable params: 676,298
Non-trainable params: 0
----------------------------------------------------------------
Input size (MB): 3.00
Forward/backward pass size (MB): 96.00
Params size (MB): 2.58
Estimated Total Size (MB): 101.58
----------------------------------------------------------------
SimpleCNN3(
  (conv1): Conv2d(3, 32, kernel_size=(5, 5), stride=(1, 1), padding=(2, 2))
  (conv2): Conv2d(32, 64, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1))
  (final): Linear(in_features=65536, out_features=10, bias=True)
)

题目：画出该网络的架构（要清楚地标明张量的结构）

首先理解 torchsummary 输出中张量形状的含义。PyTorch 中张量形状的标准格式是 NCHW：

本题中 batch_size 设为 64 只是示例，网络参数数量与 batch_size 无关。

网络架构详细分析如下：

输入层

输入是 RGB 图像，大小为 64 \times 64，共 3 个通道。输入张量形状为 [64, 3, 64, 64]，其中第一个 64 是 batch size，3 是颜色通道数。

Conv2d-1 层

网络定义：Conv2d(3, 32, kernel_size=(5, 5), stride=(1, 1), padding=(2, 2))

输入通道数为 3，输出通道数为 32，卷积核大小 5 \times 5，步长为 1，填充为 2。

关于输出尺寸的计算，卷积输出尺寸公式为：

其中 H_{in} 是输入高度，P 是填充，K 是卷积核大小，S 是步长。

步长（stride）决定了卷积核每次滑动的距离。stride=1 时卷积核每次移动 1 个像素；stride=2 时每次移动 2 个像素，输出尺寸约减半。

填充（padding）是在输入图像边缘补零。当 stride=1 时，若希望输出尺寸与输入相同，需要填充量 P = (K-1)/2。对于 5 \times 5 卷积核，P = (5-1)/2 = 2。

代入公式验证：

输出形状为 [64, 32, 64, 64]，空间尺寸保持不变。

隐含的池化层

观察 Conv2d-1 输出 [64, 32, 64, 64] 和 Conv2d-2 输出 [64, 64, 32, 32]，空间尺寸从 64 \times 64 变为 32 \times 32，恰好减半。

但 Conv2d-2 的参数是 stride=1, padding=1, kernel=3 \times 3。对于 3 \times 3 卷积核，padding=1 时输出尺寸不变（因为 P = (3-1)/2 = 1）。因此可以推断在两层之间存在一个 2 \times 2 的最大池化层（MaxPool2d，stride=2）。

选择最大池化而非平均池化的原因：最大池化选取局部区域的最大值，只要特征在该区域内被检测到就会保留，提供平移不变性并保留显著特征。平均池化会平滑响应，可能弱化强特征，更适合网络末端的全局信息汇聚。对于披萨配料检测这种需要识别局部特征的任务，最大池化更合适。

池化层没有可训练参数，所以 torchsummary 可能省略了它，或者它在 forward 函数中以函数调用形式实现。

池化后形状为 [64, 32, 32, 32]。

Conv2d-2 层

网络定义：Conv2d(32, 64, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1))

输入通道 32，输出通道 64，stride=1，padding=1。

输出形状为 [64, 64, 32, 32]。

关于通道数从 32 增加到 64 的意义：每个输出通道对应一个卷积核，学习检测一种特定特征。浅层学习简单的低级特征（边缘、纹理），深层将低级特征组合成高级特征（具体配料的形状）。高级特征种类更多，需要更多通道来表示。同时空间尺寸减小、通道数增加是 CNN 的常见设计模式，用更丰富的特征种类补偿位置信息的损失。

Flatten 层

将三维特征图展平为一维向量。Flatten 操作只改变每个样本的特征表示形式，batch 维度保持不变。

Conv2d-2 输出 [64, 64, 32, 32] 中，第一个 64 是 batch size，后面的 64 \times 32 \times 32 是每个样本的特征图。展平后每个样本的向量长度为：

展平后形状为 [64, 65536]，即 64 个样本(batch)，每个样本 65536 维。

Linear-3 层

网络定义：Linear(in_features=65536, out_features=10, bias=True)

输出形状 [64, 10] 中，64 是 batch size，10 是输出特征数（对应 10 种配料）。

完整架构图

输入: [64, 3, 64, 64]
    (batch=64, channels=3, height=64, width=64)
         ↓
    Conv2d-1: kernel=5×5, stride=1, padding=2
    输出尺寸: (64 + 2×2 - 5)/1 + 1 = 64
         ↓
特征图: [64, 32, 64, 64]
    (batch=64, channels=32, height=64, width=64)
         ↓
    MaxPool2d: kernel=2×2, stride=2 (隐含层)
    输出尺寸: 64/2 = 32
         ↓
特征图: [64, 32, 32, 32]
    (batch=64, channels=32, height=32, width=32)
         ↓
    Conv2d-2: kernel=3×3, stride=1, padding=1
    输出尺寸: (32 + 2×1 - 3)/1 + 1 = 32
         ↓
特征图: [64, 64, 32, 32]
    (batch=64, channels=64, height=32, width=32)
         ↓
    Flatten: 将每个样本的特征图展平
    展平维度: 64 × 32 × 32 = 65536
         ↓
向量: [64, 65536]
    (batch=64, features=65536)
         ↓
    Linear-3: in=65536, out=10
         ↓
输出: [64, 10]
    (batch=64, classes=10)

题目：说明右侧列 Param # 中的第一个数字 2432 是如何得到的。

Conv2d-1 的参数包括卷积核权重和偏置。

每个输出通道对应一个卷积核，这个卷积核需要在所有输入通道上进行卷积。卷积核是一个三维张量，形状为 [\text{输入通道数}, \text{卷积核高}, \text{卷积核宽}] = [3, 5, 5]。

每个卷积核的权重参数数量：3 \times 5 \times 5 = 75

共有 32 个卷积核（对应 32 个输出通道），权重参数总数：32 \times 75 = 2400

每个输出通道有 1 个偏置参数，共 32 个偏置。

总参数数量：2400 + 32 = 2432

Conv2d-2 参数数量 18,496 的计算

层的定义

Conv2d(32, 64, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1))

输入通道数 in_channels = 32，输出通道数 out_channels = 64，卷积核大小 = 3 \times 3。

理解卷积核的完整结构

一个卷积核并不只是一个二维的 3 \times 3 矩阵，而是一个三维张量。因为卷积核需要同时处理所有输入通道，所以它的形状是：

卷积时，这个三维卷积核与输入的 32 个通道分别做二维卷积，然后将 32 个结果相加，得到一个输出通道的一个像素值。

计算权重参数

一个卷积核的权重参数数量：

共有 64 个输出通道，意味着有 64 个这样的卷积核，权重总数：

加上偏置参数

每个输出通道有 1 个偏置参数，共 64 个输出通道：

总参数数量

通用公式

Conv2d 参数数量公式：

Linear-3 参数数量 655,370 的计算

层的定义

Linear(in_features=65536, out_features=10, bias=True)

输入特征数 = 65536，输出特征数 = 10。

理解全连接层的结构

全连接层的作用是将输入向量的每个元素与输出向量的每个元素建立连接。权重矩阵的形状是：

每个输出神经元需要与所有 65536 个输入神经元连接，所以每个输出神经元有 65536 个权重参数。

计算权重参数

权重矩阵的参数数量：

加上偏置参数

每个输出神经元有 1 个偏置参数，共 10 个输出神经元：

总参数数量

通用公式

Linear 层参数数量公式：

题目：说明网络最后一个线性层的输入数字 65536 是如何得到的。

Linear-3 的输入是将 Conv2d-2 的输出展平后得到的一维向量。

Conv2d-2 的输出形状为 [64, 64, 32, 32]，其中第一个 64 是 batch size，不参与展平计算。每个样本的特征图形状是 [64, 32, 32]（通道数 × 高度 × 宽度）。

展平后每个样本的特征向量长度：

题目：该网络共包含 676,298 个参数：它是否适合所提出的问题？请提出并论证架构上的修改建议。

这个网络对于当前问题存在严重的过拟合风险。数据集只有 5000 张图像，而模型有超过 67 万个参数，参数数量远超样本数量。根据经验法则，训练样本数量应该至少是参数数量的几倍到十几倍，否则模型容易记住训练数据而无法泛化。

参数过多的主要原因是最后的全连接层。Conv2d-2 输出的特征图尺寸为 64 \times 32 \times 32 = 65536，直接接全连接层导致参数量爆炸（65536 \times 10 + 10 = 655370，占总参数的 97%）。

修改建议如下：

第一，增加池化层或使用更大步长的卷积来降低特征图的空间尺寸。例如在每个卷积层后添加 2 \times 2 的最大池化层。如果将特征图从 32 \times 32 进一步降到 4 \times 4，全连接层的输入变为 64 \times 4 \times 4 = 1024，参数量大幅减少。

第二，使用全局平均池化（Global Average Pooling）替代展平操作。全局平均池化对每个通道计算所有空间位置的平均值，输出长度等于通道数。使用后全连接层输入仅为 64 维，参数量降为 64 \times 10 + 10 = 650。

第三，增加正则化手段，如 Dropout 层、Batch Normalization 层，以及 L2 权重正则化，帮助防止过拟合。

第四，使用数据增强技术扩充训练集，如随机裁剪、旋转、翻转、颜色抖动等，人为增加数据多样性。

第五，考虑使用预训练模型进行迁移学习。加载在 ImageNet 上预训练的 ResNet 或 VGG 等模型作为特征提取器，只训练最后的分类层，能利用预训练模型学到的通用图像特征，在小数据集上取得较好效果。

题目 Q1.1 (2分)：你训练了一个二分类器，它在训练集上的错误率很低，但在测试集上的错误率很高。造成这种差异的原因可能是什么（可多选）：

A. 这是过拟合的情况（over-fitting）。
B. 这是欠拟合的情况（under-fitting）。
C. 学习过程正则化不当。
D. 训练集和测试集来自不同的分布。

答案：A、C、D

选项A正确：训练误差低而测试误差高是过拟合的典型表现。模型过度学习了训练数据中的细节和噪声，将这些特定于训练集的模式当作一般规律，导致在新数据上无法泛化。

选项B错误：欠拟合的特征是训练误差和测试误差都很高，因为模型过于简单，连训练数据的基本规律都没有学到。

选项C正确：正则化的作用是限制模型复杂度以防止过拟合。如果正则化强度不足（如L2正则化的系数 \lambda 太小），模型会过于复杂；如果正则化方式选择不当，也无法有效约束模型。正则化不当是导致过拟合的常见原因之一。

选项D正确：如果训练集和测试集的数据分布不同（称为分布偏移或协变量偏移），即使模型在训练集上学得很好，在测试集上也会表现不佳。这不是传统意义上的过拟合，而是数据采样或划分时出现了问题。

题目 Q1.2 (2分)：三个分类器在相同的数据上进行了训练。决策边界如图所示（从左到右复杂度逐渐增加）。哪些说法是正确的？

A. 左边的分类器鲁棒性强但判别能力弱（poor fit）。
B. 左边的分类器既鲁棒又有判别能力（high fit）。
C. 右边的分类器鲁棒性强但判别能力弱。
D. 右边的分类器鲁棒性弱但判别能力强。

答案：A、D

题目 Q1.4 (3分)：描述用于模型选择的交叉验证的一般方法。对于上述分类问题（图中有两组数据点，十字形和菱形分别表示两类），使用留一法(leave-one-out)交叉验证来证明在1-NN和3-NN之间选择最佳分类器的合理性。

答案：

交叉验证是一种在有限数据条件下评估模型泛化能力的方法。其基本思想是将数据集划分为若干个互不重叠的子集，轮流使用其中一部分作为验证集，其余部分作为训练集，多次训练和验证后取平均性能作为模型的评估指标。以 k 折交叉验证为例，将数据分成 k 份，每次用 k-1 份训练，剩余1份验证，重复 k 次，最终性能是 k 次验证结果的平均值。

留一法（Leave-One-Out，简称LOO）是交叉验证的一种极端情况。设数据集有 n 个样本，每次只留出1个样本作为验证集，用其余 n-1 个样本训练模型，然后在这1个样本上测试。这个过程重复 n 次，每个样本都恰好被用作验证集一次。最终的错误率是 n 次测试中错误次数的比例。留一法的优点是最大化利用了数据进行训练，特别适合样本量较小的情况；缺点是计算成本高，需要训练 n 个模型。

对于图中的分类问题，数据量很少（约10个左右的样本点），使用留一法可以充分利用每一个样本。观察数据分布，左侧有一组十字形样本，右侧有菱形样本，但中间区域有一个十字形样本混在菱形样本之中。

对于1-NN分类器，每次留出一个样本时，该样本会被分类为其最近邻的类别。可能被错分。1-NN对噪声和离群点非常敏感。

对于3-NN分类器，分类决策基于最近的3个邻居的多数投票。即使最近的1个邻居属于错误的类别，只要另外2个邻居属于正确的类别，最终投票结果仍然正确。这种投票机制使得3-NN对噪声更加鲁棒。在留一法验证中，3-NN的错误率预期会低于1-NN。

通过对每个样本执行留一法验证并统计错误率，可以定量比较1-NN和3-NN的泛化性能。在这个数据集上，3-NN更可能获得较低的留一法错误率，因此应选择3-NN作为最佳分类器。

题目 Q2.1 (8分)：使用以下数据库来估计一个人是悲伤还是快乐，根据他/她鞋子的颜色、外套上纽扣的数量以及是否戴眼镜。我们试图通过构建一个二叉决策树来实现。

问题：可能的问题有哪些？树的最大叶子数是多少？最大深度是多少？

答案：

由于要构建的是二叉决策树，每个问题必须将数据分成两个子集。对于每个属性，可能的二元问题如下：

鞋子颜色属性有三个取值（红色、绿色、蓝色），可以构造的二元问题包括：鞋子是红色吗？鞋子是绿色吗？鞋子是蓝色吗？每个问题都将数据分为该颜色与非该颜色两组。

纽扣数属性有两个取值（2和3），可以构造的二元问题是：纽扣数是2吗？（或等价地：纽扣数是3吗？）

眼镜属性有两个取值（是和否），可以构造的二元问题是：戴眼镜吗？

因此总共有 3 + 1 + 1 = 5 种可能的问题。

关于树的最大叶子数，需要考虑数据中不同的属性组合数。观察数据，实际出现的组合有：（红色，2，是）、（红色，2，否）、（绿色，2，否）、（蓝色，2，否）、（蓝色，3，是），共5种不同的组合。理论上，如果每个组合都对应一个叶节点，最大叶子数为5。但从二叉树结构考虑，用3个属性构建的完全二叉树最多有 2^3 = 8 个叶节点。实际上，由于某些分支可能提前终止（子集已经纯净），叶子数取决于数据的分布。

树的最大深度是指从根节点到叶节点经过的边数（不包括根节点本身）。由于只有3个属性，每条从根到叶的路径最多经过3个问题，因此最大深度为3。

问题：在任何问题之前，初始熵是多少？

答案：

初始熵衡量的是在没有任何属性信息时，目标变量（情绪）的不确定性。数据集共有9个样本，其中悲伤5个，快乐4个。

初始熵计算如下：

计算各项：

问题：当我们将"他/她的鞋子是蓝色的吗？"作为第一个问题时，平均熵减少量是多少？

答案：

首先统计按"鞋子是蓝色"划分后的数据分布：

鞋子是蓝色（是）：共3个样本，全部是快乐（0悲伤，3快乐）

鞋子不是蓝色（否）：共6个样本，其中5个悲伤，1个快乐

计算各分支的条件熵：

对于蓝色分支，所有样本都是快乐，分布完全纯净：

对于非蓝色分支：

加权平均条件熵：

平均熵减少量（信息增益）：

问题：当我们将"他/她戴眼镜吗？"作为第一个问题时，平均熵减少量是多少？

答案：

统计按"戴眼镜"划分后的数据分布：

戴眼镜（是）：共2个样本，其中1个悲伤（红色，2，是），1个快乐（蓝色，3，是）

不戴眼镜（否）：共7个样本，其中4个悲伤，3个快乐

计算各分支的条件熵：

对于戴眼镜分支：

对于不戴眼镜分支：

加权平均条件熵：

平均熵减少量（信息增益）：

问题：最佳的第一个问题应该是什么？（直觉解释）

答案：

比较两个问题的信息增益："鞋子是蓝色吗"的信息增益为0.558比特，而"戴眼镜吗"的信息增益仅为0.003比特。显然应该选择"鞋子是蓝色吗"作为第一个问题。

从直觉上理解，一个好的问题应该能够将数据划分成尽可能"纯净"的子集。观察数据可以发现，所有穿蓝色鞋子的人都是快乐的（3/3），这是一个完美纯净的子集。而眼镜属性的划分几乎没有提供有用的信息：戴眼镜的人中悲伤和快乐各占一半（1:1），不戴眼镜的人中悲伤和快乐的比例（4:3）与原始比例（5:4）几乎相同。这说明眼镜属性与情绪之间几乎没有关联，而鞋子颜色（特别是蓝色）与情绪有很强的关联。

题目 Q3.1 (3分)：设 i,j 为2个相对整数，考虑函数 f_{i,j} 从 \mathbb{R}^2 到 \mathbb{R}：

求以下值：f_{i,j}(i,j)、f_{i,j}(i+1,j)、f_{i,j}(i-1,j)、f_{i,j}(i,j+1)、f_{i,j}(i,j-1)

答案：

首先理解这个函数的结构。ReLU函数定义为 \text{relu}(x) = \max(0, x)。对于任意实数 u，有：

这是因为当 u \geq 0 时，\text{relu}(u) = u，\text{relu}(-u) = 0，和为 u = |u|；当 u < 0 时，\text{relu}(u) = 0，\text{relu}(-u) = -u，和为 -u = |u|。

利用这个性质，函数可以简化为：

这个函数描述的是以 (i, j) 为中心的一个金字塔形状（或帐篷形状），在中心点取值为1，沿着曼哈顿距离线性下降，当曼哈顿距离达到1时变为0。

计算各点的值：

f_{i,j}(i,j)：此时 |x_1 - i| = 0，|x_2 - j| = 0

f_{i,j}(i+1,j)：此时 |x_1 - i| = 1，|x_2 - j| = 0

f_{i,j}(i-1,j)：此时 |x_1 - i| = 1，|x_2 - j| = 0

f_{i,j}(i,j+1)：此时 |x_1 - i| = 0，|x_2 - j| = 1

f_{i,j}(i,j-1)：此时 |x_1 - i| = 0，|x_2 - j| = 1

f_{i,j} 在整数集上的值： 在整数格点上，f_{i,j} 仅在点 (i, j) 处取值为1，在所有其他整数格点上取值为0。这是因为任何其他整数格点 (m, n) 与 (i, j) 的曼哈顿距离 |m-i| + |n-j| \geq 1，使得 1 - |m-i| - |n-j| \leq 0，经过ReLU后变为0。

题目 Q3.2 (3分)：解释如何使用函数 f_{i,j} 来记忆一个学习数据库？f_{i,j} 是否像经典的多层感知器(MLP)？如果是，它的结构是什么（层数和每层神经元数）。

答案：

假设有一个学习数据库，包含若干个训练样本 \{(x^{(k)}_1, x^{(k)}_2, y^{(k)})\}，其中 (x^{(k)}_1, x^{(k)}_2) 是整数坐标的输入，y^{(k)} 是对应的标签或输出值。由于 f_{i,j} 在整数格点上仅在 (i,j) 处为1，在其他所有整数格点为0，可以利用这个性质构造一个函数来精确记忆整个数据库：

当输入某个训练样本的坐标 (x^{(m)}_1, x^{(m)}_2) 时，只有 f_{x^{(m)}_1, x^{(m)}_2} 这一项为1，其他所有项为0，因此 F(x^{(m)}_1, x^{(m)}_2) = y^{(m)}，完美地"记住"了该样本的标签。

关于MLP结构，f_{i,j} 确实可以用一个多层感知器来实现。分析其计算过程：

第一层（输入层）：接收输入 (x_1, x_2)

第二层（隐藏层1）：计算4个中间值，分别是 \text{relu}(x_1-i)、\text{relu}(-(x_1-i))、\text{relu}(x_2-j)、\text{relu}(-(x_2-j))，共4个神经元

第三层（隐藏层2）：将上一层的4个输出相加并从1中减去，然后通过ReLU，即计算 \text{relu}(1 - \sum)，共1个神经元

第四层（输出层）：输出最终结果，1个神经元f_{i,j}

因此，f_{i,j} 对应一个具有2层隐藏层的MLP，结构为：2（输入）→ 4（隐藏层1）→ 1（隐藏层2）→ 1（输出）。

题目 Q3.3 (3分)：设 g(x) = \text{relu}(1 - \text{relu}(1-x_1) - \text{relu}(1-x_2))。验证当 x_1<0 或 x_2<0 时，g(x) 为零。同时验证当 x_1 \geq 1 且 x_2 \geq 1 时，g(x) 严格为正。

答案：

情况1：当 x_1 < 0 时

由于 x_1 < 0，有 1 - x_1 > 1，因此 \text{relu}(1-x_1) = 1 - x_1 > 1。

此时内部表达式 1 - \text{relu}(1-x_1) - \text{relu}(1-x_2) < 1 - 1 - 0 = 0（因为 \text{relu}(1-x_2) \geq 0）。

经过外层ReLU，g(x) = \text{relu}(\text{负数}) = 0。

同理，当 x_2 < 0 时，\text{relu}(1-x_2) > 1，内部表达式也为负，g(x) = 0。

情况2：当 x_1 \geq 1 且 x_2 \geq 1 时

由于 x_1 \geq 1，有 1 - x_1 \leq 0，因此 \text{relu}(1-x_1) = 0。

由于 x_2 \geq 1，有 1 - x_2 \leq 0，因此 \text{relu}(1-x_2) = 0。

此时内部表达式 1 - 0 - 0 = 1 > 0。

经过外层ReLU，g(x) = \text{relu}(1) = 1 > 0。

这个函数学习的是由 x_1 \geq 1 且 x_2 \geq 1 定义的象限区域（一个半无限锥体），在该区域内取正值，在 x_1 < 0 或 x_2 < 0 的区域取零值。边界区域（0 \leq x_1 < 1 或 0 \leq x_2 < 1）的行为是过渡性的。

题目 Q3.4 (2分 困难)：如何使用它来学习由 ax_1+bx_2+c \geq 0 和 a'x_1+b'x_2+c' \geq 0 定义的半锥体？

答案：

函数 g(x) 学习的是由 x_1 \geq 1 和 x_2 \geq 1 两个不等式定义的区域。要推广到任意线性不等式定义的半锥体，需要进行坐标变换。

核心思想是将原始坐标 (x_1, x_2) 通过线性变换映射到新坐标 (u_1, u_2)，使得在新坐标下，两个约束条件变为 u_1 \geq 1 和 u_2 \geq 1 的形式。

具体地，定义变换：

当 ax_1+bx_2+c \geq 0 时，u_1 \geq 1；当 a'x_1+b'x_2+c' \geq 0 时，u_2 \geq 1。

将变换后的坐标代入 g 函数：

这个函数在同时满足 ax_1+bx_2+c \geq 0 和 a'x_1+b'x_2+c' \geq 0 的区域内取正值，在违反任一条件的区域取零值，从而学习了由两个任意线性不等式定义的半锥体。

Question : La régression logistique peut être utilisée pour la classification. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Vrai. La régression logistique est essentiellement un algorithme de classification. Elle utilise la fonction sigmoïde pour mapper la combinaison linéaire vers l'intervalle (0, 1), cette sortie peut être interprétée comme la probabilité qu'un échantillon appartienne à la classe positive, et une décision de classification peut être prise après avoir fixé un seuil.

Question : On peut utiliser l'ensemble de test pour ajuster les hyperparamètres d'un algorithme d'apprentissage par validation croisée. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Faux. L'unique objectif de l'ensemble de test est d'évaluer la performance de généralisation du modèle final. Si l'on utilise l'ensemble de test pour ajuster les paramètres, le modèle apprend indirectement des informations de l'ensemble de test, ce qui conduit à une évaluation trop optimiste de la capacité de généralisation. La bonne pratique est d'utiliser la validation croisée sur l'ensemble d'entraînement pour sélectionner les hyperparamètres.

Question : Lors de la réduction de la dimensionnalité des données d'entrée, il existe un risque de surapprentissage. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Faux. La réduction de dimensionnalité est généralement une méthode de régularisation qui réduit la complexité du modèle en diminuant le nombre de caractéristiques, réduisant ainsi le risque de surapprentissage plutôt que de l'augmenter. Le surapprentissage se produit généralement lorsque le modèle est trop complexe avec trop de paramètres, et la réduction de dimensionnalité réduit précisément le nombre de paramètres à apprendre. Cependant, si la réduction de dimensionnalité est excessive et entraîne une perte d'informations clés, un sous-apprentissage peut survenir.

Question : Pendant la phase d'entraînement, l'algorithme k-NN est plus efficace en temps de calcul que la régression logistique. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Vrai. k-NN est un algorithme d'apprentissage paresseux qui n'effectue pratiquement aucun calcul pendant la phase d'entraînement, il stocke simplement toutes les données d'entraînement, tandis que la régression logistique nécessite une optimisation itérative (comme la descente de gradient) pour apprendre les paramètres, le temps d'entraînement dépend de la quantité de données et du nombre d'itérations. Il faut noter que bien que k-NN soit rapide à entraîner, la phase de prédiction nécessite de calculer la distance entre le nouvel échantillon et tous les échantillons d'entraînement, le temps de prédiction est donc plus long.

Question : Lorsque le noyau du SVM est linéaire, le vecteur de poids w est une combinaison linéaire des données. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Vrai. Selon la forme duale du SVM, le vecteur de poids peut s'exprimer comme :

où \alpha_i sont les multiplicateurs de Lagrange, y_i sont les étiquettes, x_i sont les points de données. Cette expression montre clairement que w est une combinaison linéaire de tous les échantillons d'entraînement, où seuls les \alpha_i correspondant aux vecteurs de support sont non nuls.

Question : Le coefficient C du SVM peut être négatif, à condition que les variables d'écart soient positives. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Faux. Le paramètre C est le coefficient de régularisation qui contrôle le degré de pénalisation des échantillons mal classés, il apparaît dans l'objectif d'optimisation du SVM comme :

Puisque C multiplie la somme des variables d'écart \xi_i, et que nous voulons minimiser cette fonction objectif tout en pénalisant les erreurs de classification, C doit être positif. Si C était négatif, le processus d'optimisation tendrait à rendre les variables d'écart infiniment grandes, ce qui contredit complètement notre objectif de réduire les erreurs de classification.

Question : Plus C est grand, plus la marge est grande. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Faux. Un C plus grand signifie une pénalisation plus sévère des erreurs de classification, le modèle s'efforcera davantage de classifier correctement chaque échantillon d'entraînement, ce qui conduit à une frontière de décision plus proche des points de données, réduisant ainsi la marge. Inversement, un C plus petit signifie une plus grande tolérance aux erreurs de classification, permettant à certains échantillons d'être mal classés en échange d'une marge plus grande. Cela reflète le compromis dans le SVM entre la maximisation de la marge et la minimisation de l'erreur d'entraînement.

Question : Les points de données qui ne sont pas des vecteurs de support ont un coefficient correspondant égal à zéro. Répondez par vrai/faux et expliquez brièvement en une phrase.

Réponse : Vrai. Dans le problème dual du SVM, chaque point de données x_i a un multiplicateur de Lagrange correspondant \alpha_i. Selon les conditions KKT, seuls les points situés sur la frontière de la marge ou à l'intérieur de la marge (c'est-à-dire les vecteurs de support) ont \alpha_i > 0, tandis que les points éloignés de la frontière de décision, correctement classés et non sur la frontière de la marge, ont \alpha_i = 0. Cela signifie que la fonction de décision finale est déterminée uniquement par les vecteurs de support, indépendamment des autres points de données.

Question : Calculer l'entropie initiale de la distribution H(Y) = -\sum_{i} P(Y = i) \log_2 P(Y = i)

Selon la distribution des données dans la figure, il y a 16 points de données au total, dont 8 étoiles (★) et 8 cercles (●). La distribution de probabilité des deux classes est :

En substituant les probabilités dans la formule de l'entropie :

L'entropie initiale est de 1 bit, c'est la valeur maximale de l'entropie pour un problème de classification binaire, indiquant que sans aucune information d'attribut, l'incertitude entre les deux classes est maximale.

Question : Un test de type (x_2 > n) a-t-il un sens ? Raisonnez en fonction de l'homogénéité des régions après partition, sans effectuer de calculs.

Réponse : Non, cela n'a pas de sens. En observant la distribution des données, on peut constater que les étoiles et les cercles sont distribués de manière alternée et mélangée dans la direction x_2. Quel que soit l'entier n choisi comme seuil de division pour x_2, les deux régions résultantes contiendront simultanément des points de données des deux classes (étoiles et cercles), il est impossible de réaliser une séparation efficace des classes.

Question : Calculer en détail le gain d'information du test (x_1 > 0).

Indication : Le gain d'information est défini comme IG(A) = H(Y) - H(Y|A), et

Partition verticale selon (x_1 > 0) :

Moitié droite (x_1 > 0) : 8 points au total, ★ 2, ● 6

Moitié gauche (x_1 \leq 0) : 8 points au total, ★ 6, ● 2

Calcul de l'entropie conditionnelle de la moitié droite :

La distribution de probabilité de la moitié gauche est symétrique à celle de la droite (3/4 et 1/4 interchangés), la valeur de l'entropie est identique :

Entropie conditionnelle moyenne pondérée :

Gain d'information :

Réponse : IG(x_1 > 0) \approx 0.1887 bit

Question : Effectuer le même calcul pour (x_1 > 1), et conclure sur le meilleur premier test.

Partition verticale selon (x_1 > 1) :

Côté droit (x_1 > 1) : 4 points au total, ★ 1, ● 3

Côté gauche (x_1 \leq 1) : 12 points au total, ★ 7, ● 5

Calcul de l'entropie conditionnelle du côté droit :

Calcul de l'entropie conditionnelle du côté gauche :

Entropie conditionnelle moyenne pondérée :

Gain d'information :

Conclusion :

Le meilleur premier test est (x_1 > 0), il apporte un gain d'information plus élevé.

Question : Proposer un arbre de décision de profondeur 2, et donner la décision de chaque feuille ainsi que le score de probabilité associé.

Le premier niveau choisit le test (x_1 > 0), divisant les données en deux parties gauche et droite. Le deuxième niveau doit continuer à choisir la partition optimale dans chaque sous-région.

Pour la branche gauche (x_1 \leq 0) : Cette région contient 6 ★, 2 ●. On peut choisir le test (x_1 > -1) pour une partition supplémentaire.

Pour la branche droite (x_1 > 0) : Cette région contient 2 ★, 6 ●. On peut choisir le test (x_1 > 1) pour une partition supplémentaire.

Structure de l'arbre de décision :

                      [x_1 > 0?]
                     /          \
                   Non           Oui
                   /              \
            [x_1 > -1?]        [x_1 > 1?]
            /        \          /        \
          Non        Oui      Non        Oui
          /            \      /            \
      Feuille1      Feuille2  Feuille3   Feuille4

Décision et score de probabilité de chaque feuille (selon la distribution spécifique des données dans la figure) :

Feuille 1 (x_1 \leq -1) : Décision ★

Feuille 2 (-1 < x_1 \leq 0) : Décision ★

Feuille 3 (0 < x_1 \leq 1) : Décision ●

Feuille 4 (x_1 > 1) : Décision ●, P(\text{●}) = \frac{3}{4} = 0.75, P(\text{★}) = \frac{1}{4} = 0.25

Question : Nous voulons construire une application capable d'identifier automatiquement la composition des garnitures d'une pizza à partir d'une image RGB. Il y a 10 garnitures possibles. Nous disposons d'une base de données de 5000 images de taille 64x64. Quel type de fonction faut-il implémenter ? Comment l'évaluer ?

C'est un problème de classification multi-étiquettes. Contrairement au problème de classification multi-classes traditionnel, où l'on choisit une seule classe parmi plusieurs, la classification multi-étiquettes permet à un échantillon d'appartenir simultanément à plusieurs classes. Dans ce problème, une image de pizza peut contenir plusieurs garnitures en même temps, par exemple des champignons, du bacon et des tomates simultanément.

La fonction à implémenter est f: \mathbb{R}^{64 \times 64 \times 3} \rightarrow \{0, 1\}^{10}, l'entrée est une image RGB de 64×64, la sortie est un vecteur binaire de longueur 10, chaque position indique si la garniture correspondante est présente. En pratique, le réseau produit 10 valeurs de probabilité entre 0 et 1, converties en prédictions binaires par un seuil (généralement 0.5).

Les métriques d'évaluation peuvent être diverses. La précision par étiquette, le rappel et le score F1 sont des indicateurs courants. On peut aussi utiliser la perte de Hamming (Hamming Loss), qui mesure la proportion d'étiquettes mal prédites. Pour une évaluation globale, on peut utiliser le taux de correspondance exacte (Exact Match Ratio), c'est-à-dire la proportion d'échantillons où l'ensemble des étiquettes prédites correspond exactement à l'ensemble des étiquettes réelles.

Question : Quel type de méthode d'apprentissage faut-il utiliser ? Quelle fonction de perte ?

Il faut utiliser une méthode d'apprentissage supervisé, plus précisément un réseau de neurones convolutif profond, car l'entrée est constituée d'images et les CNN peuvent extraire efficacement les caractéristiques spatiales et les représentations hiérarchiques des images.

La fonction de perte à utiliser est l'entropie croisée binaire (Binary Cross-Entropy Loss), aussi appelée perte BCE. Pour la classification multi-étiquettes, nous décomposons le problème en 10 problèmes de classification binaire indépendants, chaque garniture correspondant à une tâche de classification binaire. La fonction de perte est :

où N est le nombre d'échantillons, y_{ij} \in \{0, 1\} est l'étiquette réelle de la j-ème garniture du i-ème échantillon, \hat{y}_{ij} \in (0, 1) est la probabilité prédite par le modèle. La dernière couche du réseau utilise la fonction d'activation sigmoïde plutôt que softmax, car la présence de chaque garniture est indépendante des autres.

----------------------------------------------------------------
        Layer (type)               Output Shape         Param #
================================================================
            Conv2d-1           [64, 32, 64, 64]           2,432
            Conv2d-2           [64, 64, 32, 32]          18,496
           Linear-3                   [64, 10]         655,370
================================================================
Total params: 676,298
Trainable params: 676,298...
`....

Question : Dessiner l'architecture de ce réseau (en indiquant clairement la structure des tenseurs)

Commençons par comprendre la signification des formes de tenseurs dans la sortie de torchsummary. Le format standard des formes de tenseurs en PyTorch est NCHW :

Dans ce problème, batch_size est fixé à 64 uniquement comme exemple, le nombre de paramètres du réseau est indépendant du batch_size.

Analyse détaillée de l'architecture du réseau :

Couche d'entrée

L'entrée est une image RGB de taille 64 \times 64, avec 3 canaux. La forme du tenseur d'entrée est [64, 3, 64, 64], où le premier 64 est la taille du batch, 3 est le nombre de canaux de couleur.

Couche Conv2d-1

Définition du réseau : Conv2d(3, 32, kernel_size=(5, 5), stride=(1, 1), padding=(2, 2))

Le nombre de canaux d'entrée est 3, le nombre de canaux de sortie est 32, la taille du noyau de convolution est 5 \times 5, le stride est 1, le padding est 2.

Concernant le calcul de la taille de sortie, la formule de la taille de sortie de convolution est :

où H_{in} est la hauteur d'entrée, P est le padding, K est la taille du noyau de convolution, S est le stride.

Le stride détermine la distance de glissement du noyau de convolution à chaque pas. Avec stride=1, le noyau se déplace de 1 pixel à chaque fois ; avec stride=2, il se déplace de 2 pixels, réduisant la taille de sortie d'environ moitié.

Le padding consiste à ajouter des zéros aux bords de l'image d'entrée. Lorsque stride=1, si l'on souhaite que la taille de sortie soit identique à l'entrée, le padding nécessaire est P = (K-1)/2. Pour un noyau 5 \times 5, P = (5-1)/2 = 2.

Vérification par la formule :

La forme de sortie est [64, 32, 64, 64], la dimension spatiale reste inchangée.

Couche de pooling implicite

En observant la sortie de Conv2d-1 [64, 32, 64, 64] et la sortie de Conv2d-2 [64, 64, 32, 32], la dimension spatiale passe de 64 \times 64 à 32 \times 32, exactement réduite de moitié.

Mais les paramètres de Conv2d-2 sont stride=1, padding=1, kernel=3 \times 3. Pour un noyau 3 \times 3, avec padding=1, la taille de sortie reste inchangée (car P = (3-1)/2 = 1). On peut donc déduire qu'il existe une couche de max pooling 2 \times 2 (MaxPool2d, stride=2) entre les deux couches.

La raison de choisir le max pooling plutôt que l'average pooling : le max pooling sélectionne la valeur maximale de la région locale, tant que la caractéristique est détectée dans cette région elle sera conservée, offrant une invariance à la translation et préservant les caractéristiques saillantes. L'average pooling lisse les réponses, ce qui peut affaiblir les caractéristiques fortes, il est plus adapté à l'agrégation d'informations globales en fin de réseau. Pour la détection de garnitures de pizza qui nécessite l'identification de caractéristiques locales, le max pooling est plus approprié.

La couche de pooling n'a pas de paramètres entraînables, donc torchsummary peut l'avoir omise, ou elle est implémentée sous forme d'appel de fonction dans la fonction forward.

Forme après pooling : [64, 32, 32, 32].

Couche Conv2d-2

Définition du réseau : Conv2d(32, 64, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1))

Canaux d'entrée 32, canaux de sortie 64, stride=1, padding=1.

La forme de sortie est [64, 64, 32, 32].

Concernant la signification de l'augmentation du nombre de canaux de 32 à 64 : chaque canal de sortie correspond à un noyau de convolution qui apprend à détecter un type spécifique de caractéristique. Les couches peu profondes apprennent des caractéristiques simples de bas niveau (bords, textures), les couches profondes combinent les caractéristiques de bas niveau en caractéristiques de haut niveau (formes spécifiques des garnitures). Les caractéristiques de haut niveau sont plus variées, nécessitant plus de canaux pour les représenter. En même temps, la réduction de la dimension spatiale et l'augmentation du nombre de canaux est un modèle de conception courant dans les CNN, utilisant une plus grande variété de caractéristiques pour compenser la perte d'informations de position.

Couche Flatten

Aplatit la carte de caractéristiques tridimensionnelle en un vecteur unidimensionnel. L'opération Flatten ne change que la forme de représentation des caractéristiques de chaque échantillon, la dimension du batch reste inchangée.

La sortie de Conv2d-2 [64, 64, 32, 32], le premier 64 est la taille du batch, les 64 \times 32 \times 32 suivants sont la carte de caractéristiques de chaque échantillon. La longueur du vecteur de chaque échantillon après aplatissement est :

Forme après aplatissement : [64, 65536], soit 64 échantillons (batch), chaque échantillon de dimension 65536.

Couche Linear-3

Définition du réseau : Linear(in_features=65536, out_features=10, bias=True)

La forme de sortie [64, 10], 64 est la taille du batch, 10 est le nombre de caractéristiques de sortie (correspondant aux 10 garnitures).

Schéma complet de l'architecture

Entrée: [64, 3, 64, 64]
    (batch=64, channels=3, height=64, width=64)
         ↓
    Conv2d-1: kernel=5×5, stride=1, padding=2
    Taille de sortie: (64 + 2×2 - 5)/1 + 1 = 64
         ↓
Carte de caractéristiques: [64, 32, 64, 64]
    (batch=64, channels=32, height=64, width=64)
         ↓
    MaxPool2d: kernel=2×2, stride=2 (couche implicite)
    Taille de sortie: 64/2 = 32
         ↓
Carte de caractéristiques: [64, 32, 32, 32]
    (batch=64, channels=32, height=32, width=32)
         ↓
    Conv2d-2: kernel=3×3, stride=1, padding=1
    Taille de sortie: (32 + 2×1 - 3)/1 + 1 = 32
         ↓
Carte de caractéristiques: [64, 64, 32, 32]
    (batch=64, channels=64, height=32, width=32)
         ↓
    Flatten: aplatit la carte de caractéristiques de chaque échantillon
    Dimension aplatie: 64 × 32 × 32 = 65536
         ↓
Vecteur: [64, 65536]
    (batch=64, features=65536)
         ↓
    Linear-3: in=65536, out=10
         ↓
Sortie: [64, 10]
    (batch=64, classes=10)

Question : Expliquer comment le premier nombre 2432 dans la colonne Param # à droite est obtenu.

Les paramètres de Conv2d-1 comprennent les poids du noyau de convolution et les biais.

Chaque canal de sortie correspond à un noyau de convolution, ce noyau doit effectuer une convolution sur tous les canaux d'entrée. Le noyau de convolution est un tenseur tridimensionnel, de forme [\text{canaux d'entrée}, \text{hauteur du noyau}, \text{largeur du noyau}] = [3, 5, 5].

Nombre de paramètres de poids par noyau de convolution : 3 \times 5 \times 5 = 75

Il y a 32 noyaux de convolution (correspondant à 32 canaux de sortie), nombre total de paramètres de poids : 32 \times 75 = 2400

Chaque canal de sortie a 1 paramètre de biais, soit 32 biais au total.

Nombre total de paramètres : 2400 + 32 = 2432

Calcul du nombre de paramètres 18 496 de Conv2d-2

Définition de la couche

Conv2d(32, 64, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1))

Nombre de canaux d'entrée in_channels = 32, nombre de canaux de sortie out_channels = 64, taille du noyau de convolution = 3 \times 3.

Comprendre la structure complète du noyau de convolution

Un noyau de convolution n'est pas simplement une matrice bidimensionnelle 3 \times 3, mais un tenseur tridimensionnel. Parce que le noyau de convolution doit traiter simultanément tous les canaux d'entrée, sa forme est :

Lors de la convolution, ce noyau de convolution tridimensionnel effectue une convolution bidimensionnelle avec chacun des 32 canaux d'entrée, puis les 32 résultats sont additionnés pour obtenir la valeur d'un pixel d'un canal de sortie.

Calcul des paramètres de poids

Nombre de paramètres de poids d'un noyau de convolution :

Il y a 64 canaux de sortie, ce qui signifie qu'il y a 64 noyaux de ce type, nombre total de poids :

Ajout des paramètres de biais

Chaque canal de sortie a 1 paramètre de biais, 64 canaux de sortie au total :

Nombre total de paramètres

Formule générale

Formule du nombre de paramètres de Conv2d :

Calcul du nombre de paramètres 655 370 de Linear-3

Définition de la couche

Linear(in_features=65536, out_features=10, bias=True)

Nombre de caractéristiques d'entrée = 65536, nombre de caractéristiques de sortie = 10.

Comprendre la structure de la couche entièrement connectée

Le rôle de la couche entièrement connectée est d'établir une connexion entre chaque élément du vecteur d'entrée et chaque élément du vecteur de sortie. La forme de la matrice de poids est :

Chaque neurone de sortie doit être connecté à tous les 65536 neurones d'entrée, donc chaque neurone de sortie a 65536 paramètres de poids.

Calcul des paramètres de poids

Nombre de paramètres de la matrice de poids :

Ajout des paramètres de biais

Chaque neurone de sortie a 1 paramètre de biais, 10 neurones de sortie au total :

Nombre total de paramètres

Formule générale

Formule du nombre de paramètres de la couche Linear :

Question : Expliquer comment le nombre 65536 à l'entrée de la dernière couche linéaire du réseau est obtenu.

L'entrée de Linear-3 est le vecteur unidimensionnel obtenu en aplatissant la sortie de Conv2d-2.

La forme de sortie de Conv2d-2 est [64, 64, 32, 32], où le premier 64 est la taille du batch et ne participe pas au calcul d'aplatissement. La forme de la carte de caractéristiques de chaque échantillon est [64, 32, 32] (canaux × hauteur × largeur).

Longueur du vecteur de caractéristiques de chaque échantillon après aplatissement :

Question : Ce réseau contient 676 298 paramètres au total : est-il adapté au problème posé ? Proposer et justifier des modifications architecturales.

Ce réseau présente un risque sérieux de surapprentissage pour le problème actuel. L'ensemble de données ne contient que 5000 images, tandis que le modèle possède plus de 670 000 paramètres, le nombre de paramètres dépasse largement le nombre d'échantillons. Selon la règle empirique, le nombre d'échantillons d'entraînement devrait être au moins plusieurs fois à une dizaine de fois le nombre de paramètres, sinon le modèle risque de mémoriser les données d'entraînement sans pouvoir généraliser.

La principale raison du trop grand nombre de paramètres est la dernière couche entièrement connectée. La taille de la carte de caractéristiques en sortie de Conv2d-2 est 64 \times 32 \times 32 = 65536, connecter directement une couche entièrement connectée provoque une explosion du nombre de paramètres (65536 \times 10 + 10 = 655370, représentant 97% des paramètres totaux).

Les suggestions de modification sont les suivantes :

Premièrement, ajouter des couches de pooling ou utiliser des convolutions avec un stride plus grand pour réduire la dimension spatiale des cartes de caractéristiques. Par exemple, ajouter une couche de max pooling 2 \times 2 après chaque couche de convolution. Si l'on réduit la carte de caractéristiques de 32 \times 32 à 4 \times 4, l'entrée de la couche entièrement connectée devient 64 \times 4 \times 4 = 1024, le nombre de paramètres est considérablement réduit.

Deuxièmement, utiliser le Global Average Pooling pour remplacer l'opération d'aplatissement. Le Global Average Pooling calcule la moyenne de toutes les positions spatiales pour chaque canal, la longueur de sortie est égale au nombre de canaux. Après utilisation, l'entrée de la couche entièrement connectée n'est que de 64 dimensions, le nombre de paramètres tombe à 64 \times 10 + 10 = 650.

Troisièmement, ajouter des moyens de régularisation, comme les couches Dropout, les couches Batch Normalization, ainsi que la régularisation L2 des poids, pour aider à prévenir le surapprentissage.

Quatrièmement, utiliser des techniques d'augmentation de données pour étendre l'ensemble d'entraînement, comme le recadrage aléatoire, la rotation, le retournement, le jittering de couleur, etc., pour augmenter artificiellement la diversité des données.

Cinquièmement, envisager l'utilisation de modèles pré-entraînés pour le transfert learning. Charger des modèles pré-entraînés sur ImageNet comme ResNet ou VGG comme extracteurs de caractéristiques, et n'entraîner que la dernière couche de classification, peut exploiter les caractéristiques génériques d'images apprises par les modèles pré-entraînés et obtenir de bons résultats sur de petits ensembles de données.

Question Q1.1 (2 points) : Vous avez entraîné un classifieur binaire qui a un faible taux d'erreur sur l'ensemble d'entraînement, mais un taux d'erreur élevé sur l'ensemble de test. Quelles pourraient être les causes de cette différence (choix multiples) :

A. C'est un cas de surapprentissage (over-fitting).
B. C'est un cas de sous-apprentissage (under-fitting).
C. Le processus d'apprentissage est mal régularisé.
D. L'ensemble d'entraînement et l'ensemble de test proviennent de distributions différentes.

Réponse : A, C, D

L'option A est correcte : Une erreur d'entraînement faible et une erreur de test élevée est la manifestation typique du surapprentissage. Le modèle a trop appris les détails et le bruit des données d'entraînement, prenant ces modèles spécifiques à l'ensemble d'entraînement pour des règles générales, ce qui l'empêche de généraliser sur de nouvelles données.

L'option B est incorrecte : Le sous-apprentissage se caractérise par des erreurs d'entraînement et de test toutes deux élevées, car le modèle est trop simple et n'a pas appris les règles de base des données d'entraînement.

L'option C est correcte : Le rôle de la régularisation est de limiter la complexité du modèle pour prévenir le surapprentissage. Si l'intensité de la régularisation est insuffisante (par exemple, le coefficient \lambda de la régularisation L2 est trop petit), le modèle sera trop complexe ; si le type de régularisation est mal choisi, il ne peut pas contraindre efficacement le modèle. Une régularisation inadéquate est l'une des causes courantes du surapprentissage.

L'option D est correcte : Si les distributions de données de l'ensemble d'entraînement et de l'ensemble de test sont différentes (appelé décalage de distribution ou décalage de covariable), même si le modèle apprend bien sur l'ensemble d'entraînement, il aura de mauvaises performances sur l'ensemble de test. Ce n'est pas du surapprentissage au sens traditionnel, mais un problème d'échantillonnage ou de partitionnement des données.

Question Q1.2 (2 points) : Trois classifieurs ont été entraînés sur les mêmes données. Les frontières de décision sont montrées dans la figure (complexité croissante de gauche à droite). Quelles affirmations sont correctes ?

A. Le classifieur de gauche est robuste mais a une faible capacité de discrimination (poor fit).
B. Le classifieur de gauche est à la fois robuste et discriminant (high fit).
C. Le classifieur de droite est robuste mais a une faible capacité de discrimination.
D. Le classifieur de droite a une faible robustesse mais une forte capacité de discrimination.

Réponse : A, D

Question Q1.4 (3 points) : Décrire la méthode générale de validation croisée pour la sélection de modèles. Pour le problème de classification ci-dessus (la figure contient deux groupes de points de données, les croix et les losanges représentant respectivement deux classes), utiliser la validation croisée leave-one-out pour justifier le choix du meilleur classifieur entre 1-NN et 3-NN.

Réponse :

La validation croisée est une méthode d'évaluation de la capacité de généralisation d'un modèle avec des données limitées. L'idée de base est de diviser l'ensemble de données en plusieurs sous-ensembles disjoints, d'utiliser tour à tour une partie comme ensemble de validation et le reste comme ensemble d'entraînement, puis de prendre la performance moyenne après plusieurs entraînements et validations comme indicateur d'évaluation du modèle. En prenant la validation croisée à k plis comme exemple, les données sont divisées en k parties, à chaque fois k-1 parties sont utilisées pour l'entraînement et la partie restante pour la validation, répété k fois, la performance finale est la moyenne des k résultats de validation.

Le leave-one-out (LOO) est un cas extrême de validation croisée. Soit un ensemble de données de n échantillons, à chaque fois un seul échantillon est mis de côté comme ensemble de validation, les n-1 autres échantillons sont utilisés pour entraîner le modèle, puis tester sur cet échantillon. Ce processus est répété n fois, chaque échantillon est utilisé exactement une fois comme ensemble de validation. Le taux d'erreur final est la proportion d'erreurs parmi les n tests. L'avantage du leave-one-out est de maximiser l'utilisation des données pour l'entraînement, particulièrement adapté aux cas avec peu d'échantillons ; l'inconvénient est le coût de calcul élevé, nécessitant l'entraînement de n modèles.

Pour le problème de classification de la figure, la quantité de données est faible (environ 10 points d'échantillons), l'utilisation du leave-one-out peut exploiter pleinement chaque échantillon. En observant la distribution des données, il y a un groupe d'échantillons en forme de croix à gauche, des échantillons en losange à droite, mais dans la zone centrale il y a un échantillon en croix mélangé parmi les échantillons en losange.

Pour le classifieur 1-NN, à chaque fois qu'un échantillon est mis de côté, cet échantillon sera classé selon la classe de son plus proche voisin. Il peut être mal classé. 1-NN est très sensible au bruit et aux valeurs aberrantes.

Pour le classifieur 3-NN, la décision de classification est basée sur le vote majoritaire des 3 plus proches voisins. Même si le plus proche voisin appartient à la mauvaise classe, tant que les 2 autres voisins appartiennent à la bonne classe, le résultat du vote final sera correct. Ce mécanisme de vote rend 3-NN plus robuste au bruit. Dans la validation leave-one-out, le taux d'erreur de 3-NN devrait être inférieur à celui de 1-NN.

En effectuant la validation leave-one-out sur chaque échantillon et en comptabilisant le taux d'erreur, on peut comparer quantitativement les performances de généralisation de 1-NN et 3-NN. Sur cet ensemble de données, 3-NN est plus susceptible d'obtenir un taux d'erreur leave-one-out plus faible, donc 3-NN devrait être choisi comme meilleur classifieur.

Question Q2.1 (8 points) : Utiliser la base de données suivante pour estimer si une personne est triste ou heureuse, selon la couleur de ses chaussures, le nombre de boutons sur son manteau et si elle porte des lunettes. Nous essayons de réaliser cela en construisant un arbre de décision binaire.

Question : Quelles sont les questions possibles ? Quel est le nombre maximum de feuilles de l'arbre ? Quelle est la profondeur maximale ?

Réponse :

Puisqu'il faut construire un arbre de décision binaire, chaque question doit diviser les données en deux sous-ensembles. Pour chaque attribut, les questions binaires possibles sont les suivantes :

L'attribut couleur des chaussures a trois valeurs (rouge, vert, bleu), les questions binaires possibles incluent : Les chaussures sont-elles rouges ? Les chaussures sont-elles vertes ? Les chaussures sont-elles bleues ? Chaque question divise les données en deux groupes : cette couleur et non cette couleur.

L'attribut nombre de boutons a deux valeurs (2 et 3), la question binaire possible est : Le nombre de boutons est-il 2 ? (ou de manière équivalente : Le nombre de boutons est-il 3 ?)

L'attribut lunettes a deux valeurs (oui et non), la question binaire possible est : Porte-t-il des lunettes ?

Donc il y a au total 3 + 1 + 1 = 5 questions possibles.

Concernant le nombre maximum de feuilles de l'arbre, il faut considérer le nombre de combinaisons d'attributs différentes dans les données. En observant les données, les combinaisons qui apparaissent réellement sont : (rouge, 2, oui), (rouge, 2, non), (vert, 2, non), (bleu, 2, non), (bleu, 3, oui), soit 5 combinaisons différentes. Théoriquement, si chaque combinaison correspond à un nœud feuille, le nombre maximum de feuilles est 5. Mais du point de vue de la structure de l'arbre binaire, un arbre binaire complet construit avec 3 attributs peut avoir au maximum 2^3 = 8 nœuds feuilles. En pratique, comme certaines branches peuvent se terminer prématurément (sous-ensemble déjà pur), le nombre de feuilles dépend de la distribution des données.

La profondeur maximale de l'arbre est le nombre d'arêtes de la racine à une feuille (sans compter la racine elle-même). Comme il n'y a que 3 attributs, chaque chemin de la racine à une feuille passe par au maximum 3 questions, donc la profondeur maximale est 3.

Question : Quelle est l'entropie initiale avant toute question ?

Réponse :

L'entropie initiale mesure l'incertitude de la variable cible (humeur) sans aucune information d'attribut. L'ensemble de données contient 9 échantillons, dont 5 tristes et 4 heureux.

Calcul de l'entropie initiale :

Calcul de chaque terme :

Question : Quelle est la réduction moyenne de l'entropie lorsque nous prenons "Ses chaussures sont-elles bleues ?" comme première question ?

Réponse :

D'abord, comptons la distribution des données après partition selon "chaussures bleues" :

Chaussures bleues (oui) : 3 échantillons au total, tous heureux (0 triste, 3 heureux)

Chaussures non bleues (non) : 6 échantillons au total, dont 5 tristes, 1 heureux

Calcul de l'entropie conditionnelle de chaque branche :

Pour la branche bleue, tous les échantillons sont heureux, la distribution est parfaitement pure :

Pour la branche non bleue :

Entropie conditionnelle moyenne pondérée :

Réduction moyenne de l'entropie (gain d'information) :

Question : Quelle est la réduction moyenne de l'entropie lorsque nous prenons "Porte-t-il des lunettes ?" comme première question ?

Réponse :

Comptons la distribution des données après partition selon "porte des lunettes" :

Porte des lunettes (oui) : 2 échantillons au total, dont 1 triste (rouge, 2, oui), 1 heureux (bleu, 3, oui)

Ne porte pas de lunettes (non) : 7 échantillons au total, dont 4 tristes, 3 heureux

Calcul de l'entropie conditionnelle de chaque branche :

Pour la branche porte des lunettes :

Pour la branche ne porte pas de lunettes :

Entropie conditionnelle moyenne pondérée :

Réduction moyenne de l'entropie (gain d'information) :

Question : Quelle devrait être la meilleure première question ? (explication intuitive)

Réponse :

En comparant le gain d'information des deux questions : "Les chaussures sont-elles bleues" a un gain d'information de 0.558 bit, tandis que "Porte-t-il des lunettes" n'a qu'un gain d'information de 0.003 bit. Il faut donc évidemment choisir "Les chaussures sont-elles bleues" comme première question.

Intuitivement, une bonne question devrait pouvoir diviser les données en sous-ensembles aussi "purs" que possible. En observant les données, on peut constater que toutes les personnes portant des chaussures bleues sont heureuses (3/3), c'est un sous-ensemble parfaitement pur. Alors que la partition par l'attribut lunettes n'apporte presque aucune information utile : parmi ceux qui portent des lunettes, tristes et heureux sont à parts égales (1:1), parmi ceux qui ne portent pas de lunettes, le ratio tristes/heureux (4:3) est presque identique au ratio original (5:4). Cela montre que l'attribut lunettes n'a presque aucune corrélation avec l'humeur, tandis que la couleur des chaussures (en particulier le bleu) a une forte corrélation avec l'humeur.

Question Q3.1 (3 points) : Soient i,j deux entiers relatifs, considérons la fonction f_{i,j} de \mathbb{R}^2 vers \mathbb{R} :

Trouver les valeurs suivantes : f_{i,j}(i,j), f_{i,j}(i+1,j), f_{i,j}(i-1,j), f_{i,j}(i,j+1), f_{i,j}(i,j-1)

Réponse :

Commençons par comprendre la structure de cette fonction. La fonction ReLU est définie comme \text{relu}(x) = \max(0, x). Pour tout nombre réel u, on a :

Car lorsque u \geq 0, \text{relu}(u) = u, \text{relu}(-u) = 0, la somme est u = |u| ; lorsque u < 0, \text{relu}(u) = 0, \text{relu}(-u) = -u, la somme est -u = |u|.

En utilisant cette propriété, la fonction peut être simplifiée en :

Cette fonction décrit une forme pyramidale (ou en forme de tente) centrée en (i, j), prenant la valeur 1 au centre, décroissant linéairement selon la distance de Manhattan, et devenant 0 lorsque la distance de Manhattan atteint 1.

Calcul des valeurs en chaque point :

f_{i,j}(i,j) : Ici |x_1 - i| = 0, |x_2 - j| = 0

f_{i,j}(i+1,j) : Ici |x_1 - i| = 1, |x_2 - j| = 0

f_{i,j}(i-1,j) : Ici |x_1 - i| = 1, |x_2 - j| = 0

f_{i,j}(i,j+1) : Ici |x_1 - i| = 0, |x_2 - j| = 1

f_{i,j}(i,j-1) : Ici |x_1 - i| = 0, |x_2 - j| = 1

Valeurs de f_{i,j} sur l'ensemble des entiers : Sur les points de grille entiers, f_{i,j} prend la valeur 1 uniquement au point (i, j), et la valeur 0 à tous les autres points de grille entiers. Car tout autre point de grille entier (m, n) a une distance de Manhattan à (i, j) de |m-i| + |n-j| \geq 1, ce qui fait que 1 - |m-i| - |n-j| \leq 0, devenant 0 après ReLU.

Question Q3.2 (3 points) : Expliquer comment utiliser les fonctions f_{i,j} pour mémoriser une base de données d'apprentissage ? f_{i,j} ressemble-t-elle à un perceptron multicouche (MLP) classique ? Si oui, quelle est sa structure (nombre de couches et nombre de neurones par couche) ?

Réponse :

Supposons qu'il y ait une base de données d'apprentissage contenant plusieurs échantillons d'entraînement \{(x^{(k)}_1, x^{(k)}_2, y^{(k)})\}, où (x^{(k)}_1, x^{(k)}_2) sont les entrées à coordonnées entières, y^{(k)} est l'étiquette ou valeur de sortie correspondante. Puisque f_{i,j} vaut 1 uniquement en (i,j) sur les points de grille entiers et 0 à tous les autres points entiers, on peut utiliser cette propriété pour construire une fonction qui mémorise exactement toute la base de données :

Lorsqu'on entre les coordonnées d'un échantillon d'entraînement (x^{(m)}_1, x^{(m)}_2), seul le terme f_{x^{(m)}_1, x^{(m)}_2} vaut 1, tous les autres termes valent 0, donc F(x^{(m)}_1, x^{(m)}_2) = y^{(m)}, "mémorisant" parfaitement l'étiquette de cet échantillon.

Concernant la structure MLP, f_{i,j} peut effectivement être implémentée par un perceptron multicouche. Analysons son processus de calcul :

Première couche (couche d'entrée) : reçoit l'entrée (x_1, x_2)

Deuxième couche (couche cachée 1) : calcule 4 valeurs intermédiaires, respectivement \text{relu}(x_1-i), \text{relu}(-(x_1-i)), \text{relu}(x_2-j), \text{relu}(-(x_2-j)), soit 4 neurones

Troisième couche (couche cachée 2) : additionne les 4 sorties de la couche précédente et soustrait de 1, puis passe par ReLU, c'est-à-dire calcule \text{relu}(1 - \sum), soit 1 neurone

Quatrième couche (couche de sortie) : produit le résultat final, 1 neurone

Donc f_{i,j} correspond à un MLP avec 2 couches cachées, de structure : 2 (entrée) → 4 (couche cachée 1) → 1 (couche cachée 2) → 1 (sortie).

Question Q3.3 (3 points) : Soit g(x) = \text{relu}(1 - \text{relu}(1-x_1) - \text{relu}(1-x_2)). Vérifier que lorsque x_1<0 ou x_2<0, g(x) est nulle. Vérifier également que lorsque x_1 \geq 1 et x_2 \geq 1, g(x) est strictement positive.

Réponse :

Cas 1 : Lorsque x_1 < 0

Puisque x_1 < 0, on a 1 - x_1 > 1, donc \text{relu}(1-x_1) = 1 - x_1 > 1.

L'expression interne 1 - \text{relu}(1-x_1) - \text{relu}(1-x_2) < 1 - 1 - 0 = 0 (car \text{relu}(1-x_2) \geq 0).

Après le ReLU externe, g(x) = \text{relu}(\text{négatif}) = 0.

De même, lorsque x_2 < 0, \text{relu}(1-x_2) > 1, l'expression interne est aussi négative, g(x) = 0.

Cas 2 : Lorsque x_1 \geq 1 et x_2 \geq 1

Puisque x_1 \geq 1, on a 1 - x_1 \leq 0, donc \text{relu}(1-x_1) = 0.

Puisque x_2 \geq 1, on a 1 - x_2 \leq 0, donc \text{relu}(1-x_2) = 0.

L'expression interne 1 - 0 - 0 = 1 > 0.

Après le ReLU externe, g(x) = \text{relu}(1) = 1 > 0.

Cette fonction apprend la région du quadrant définie par x_1 \geq 1 et x_2 \geq 1 (un cône semi-infini), prenant des valeurs positives dans cette région et des valeurs nulles dans la région où x_1 < 0 ou x_2 < 0. Le comportement dans la région de transition (0 \leq x_1 < 1 ou 0 \leq x_2 < 1) est transitoire.

Question Q3.4 (2 points, difficile) : Comment l'utiliser pour apprendre le demi-cône défini par ax_1+bx_2+c \geq 0 et a'x_1+b'x_2+c' \geq 0 ?

Réponse :

La fonction g(x) apprend la région définie par les deux inégalités x_1 \geq 1 et x_2 \geq 1. Pour généraliser à un demi-cône défini par des inégalités linéaires arbitraires, il faut effectuer une transformation de coordonnées.

L'idée clé est de mapper les coordonnées originales (x_1, x_2) vers de nouvelles coordonnées (u_1, u_2) par une transformation linéaire, de sorte que dans les nouvelles coordonnées, les deux contraintes deviennent de la forme u_1 \geq 1 et u_2 \geq 1.

Concrètement, définissons la transformation :

Lorsque ax_1+bx_2+c \geq 0, u_1 \geq 1 ; lorsque a'x_1+b'x_2+c' \geq 0, u_2 \geq 1.

En substituant les coordonnées transformées dans la fonction g :

Cette fonction prend des valeurs positives dans la région satisfaisant simultanément ax_1+bx_2+c \geq 0 et a'x_1+b'x_2+c' \geq 0, et des valeurs nulles dans la région violant l'une ou l'autre condition, apprenant ainsi le demi-cône défini par deux inégalités linéaires arbitraires.