机器学习速通
机器学习
监督学习和 PAC 学习
在监督学习中，我们有一个输入空间 \(\mathcal{X}\)（比如图片的像素特征）和一个标签空间 \(\mathcal{Y}\)（比如分类类别）。
自然界中存在一个未知的数据分布 \(\mathcal{D}\)，我们所有的训练数据 \(S = \{(x_1, y_1), \dots, (x_m, y_m)\}\) 都是从这个分布中独立同分布（i.i.d.）采样得到的。
这里存在一个根本的矛盾，也是机器学习理论要解决的核心问题：
- 真实风险 (True Risk / Generalization Error, \(L_{\mathcal{D}}(h)\))：这是我们真正想要最小化的目标。它衡量的是模型 \(h\) 在整个未知分布 \(\mathcal{D}\) 上的预期表现。
因为分布 \(\mathcal{D}\) 是未知的，真实风险永远无法直接计算。
- 经验风险 (Empirical Risk / Training Error, \(L_S(h)\))： 这是我们实际能算出来的目标。它衡量的是模型在已知的训练集 \(S\) 上的平均错误率 。
在实际操作中，我们使用的是经验风险最小化 (ERM, Empirical Risk Minimization) 策略，即选出在训练集上表现最好的模型 \(h_S = \arg\min_{h \in \mathcal{H}} L_S(h)\) 。但这会带来一个致命陷阱：过拟合（Overfitting）。在训练集上表现完美，并不代表在真实分布上表现好。
为了解决上述矛盾，Leslie Valiant 提出了 PAC 学习框架。既然我们无法保证选出的模型 \(h\) 百分之百完美（因为数据是随机抽样的，存在运气极差抽到极端数据的可能），那我们就退而求其次，给出一个概率论意义上的保证。PAC 这个名字包含了两个核心指标：
-
近似正确 (Approximately Correct, \(\epsilon\))：我们容忍模型有一定的误差，只要它的真实风险 \(L_{\mathcal{D}}(h) \le \epsilon\)（比如误差小于 1%），我们就认为它是个好模型。
-
极大概率 (Probably, \(1-\delta\))：由于抽样的随机性，我们无法保证每次训练都能得到好模型。我们只要求，在绝大多数情况下（概率至少为 \(1-\delta\)，比如 99% 的情况下），算法都能输出一个“近似正确”的模型。
一个假设空间（模型集合）\(\mathcal{H}\) 被称为是 PAC 可学习 的，如果存在一个学习算法和一个多项式级别的函数 \(m_{\mathcal{H}}(\epsilon, \delta)\)，使得对于：
- 任意的数据分布 \(\mathcal{D}\)
- 任意的精度参数 \(\epsilon \in (0, 1)\)
- 任意的置信度参数 \(\delta \in (0, 1)\)
只要训练样本量 \(m \ge m_{\mathcal{H}}(\epsilon, \delta)\)，该算法在独立同分布的样本集 \(S\) 上运行后，输出的假设 \(h\) 满足以下不等式：
考试中经常会区分这两种 PAC 模型：
-
可实现 PAC (Realizable PAC)： 这是一个强假设。它假设自然界中那个产生真实标签的完美函数 \(f\)，本身就包含在我们选择的假设空间 \(\mathcal{H}\) 里面。因此，算法总能在假设空间中找到一个在训练集上误差为 0 的模型 。
-
不可知 PAC (Agnostic PAC)： 这是更符合真实世界的假设。它不假设完美函数存在于 \(\mathcal{H}\) 中（甚至标签可能含有噪声） 。在这种情况下，我们的目标不再是追求绝对误差小于 \(\epsilon\)，而是追求与假设空间中最优模型的差距小于 \(\epsilon\) 。 其数学表达变为：
VC维、Sauer引理与统计学习理论基本定理
当假设空间 \(\mathcal{H}\) 是有限的，我们可以简单地用 \(\log|\mathcal{H}|\) 来衡量它的复杂度。但对于大多数实用模型（如线性分类器、神经网络），参数是连续的，\(\mathcal{H}\) 的大小是无限的。为了在无限空间中建立概率误差界限，我们引入了基于组合数学的测度。
-
对分 (Dichotomy) 与 生长函数 (Growth Function, \(\tau_{\mathcal{H}}(m)\))：对于包含 \(m\) 个样本的数据集 \(C = \{x_1, \dots, x_m\}\)，空间 \(\mathcal{H}\) 中的模型最多能给这 \(m\) 个点打出多少种不同的二值标签组合？这个数量的最大值就是生长函数 \(\tau_{\mathcal{H}}(m)\) 。显然，它的绝对上限是 \(2^m\)（即所有的正负组合都被模型实现了） 。
-
打散 (Shattering)：如果 \(\tau_{\mathcal{H}}(m) = 2^m\)，这就意味着无论这 \(m\) 个点被标记成什么样，我们的假设空间 \(\mathcal{H}\) 里总能挑出一个模型把它们完美分类（误差为 0）。一旦模型能打散数据，说明它具备了绝对的“死记硬背”能力，我们在训练集上看到的 0 误差，就无法证明它真的学到了规律，它可能只是把答案背下来了 。
为了量化这种死记硬背的极限，我们定义 VC 维度：空间 \(\mathcal{H}\) 的 VC 维 \(d\) 是它能够打散的最大样本集的大小 ：如果对于任意大小的 \(m\)，\(\mathcal{H}\) 都能打散，那么 \(\text{VCdim}(\mathcal{H}) = \infty\) 。
要严格证明 \(\text{VCdim}(\mathcal{H}) = d\)，需完成两步：下界：找到某一个大小为 \(d\) 的样本集，证明它可以被 \(\mathcal{H}\) 打散。上界：证明任意大小为 \(d+1\) 的样本集，都绝对不能被 \(\mathcal{H}\) 打散。
Sauer 引理：如果 \(\text{VCdim}(\mathcal{H}) = d < \infty\)，那么对于所有的 \(m\)，生长函数必定满足：
当 \(m > d\) 时，上述多项式和可以被严格放缩为 ：
这表明当 \(m\) 超过 VC 维度 \(d\) 时，生长函数的增长速度从指数级骤降为多项式级。
统计学习理论基本定理 (The Fundamental Theorem) 一个假设空间 \(\mathcal{H}\) 是（不可知）PAC 可学习的，当且仅当它的 VC 维是有限的（\(\text{VCdim}(\mathcal{H}) < \infty\)） 。
为了达到 PAC 保证 \(\mathbb{P}[L_{\mathcal{D}}(h) \le L_{\mathcal{D}}(h^*) + \epsilon] \ge 1 - \delta\)，所需的样本量 \(m\) 必须满足：
-
可实现情形 (Realizable Case)：\(m_{\mathcal{H}}(\epsilon, \delta) \le C \frac{d \log(1/\epsilon) + \log(1/\delta)}{\epsilon}\)
-
不可知情形 (Agnostic Case)：\(m_{\mathcal{H}}(\epsilon, \delta) \le C \frac{d + \log(1/\delta)}{\epsilon^2}\)
模型的选择与偏差-方差权衡
假设真实世界的数据生成规律是 \(y = f(x) + \epsilon\)，其中 \(\epsilon\) 是均值为 0、方差为 \(\sigma^2\) 的固有白噪声（Irreducible Noise）。我们利用训练集 \(S\) 训练出了一个模型 \(\hat{f}_S(x)\)。当我们把这个模型放到未知的测试点 \(x\) 上去预测时，它的期望均方误差 (Expected Squared Error) 可以被分解为三个部分：
这三个部分代表了误差的三个不同来源：
- 固有噪声 (\(\sigma^2\))：数据本身自带的随机性，这是任何模型都无法消除的“天花板”误差。
- 偏差 (Bias)：定义为 \(\mathbb{E}_S[\hat{f}_S(x)] - f(x)\)。它衡量的是我们模型的平均预测值与真实规律之间的差距。它反映了我们所选的假设空间 \(\mathcal{H}\) 本身的局限性（即 Approximation Error）。
- 方差 (Variance)：定义为 \(\mathbb{E}_S \left[ (\hat{f}_S(x) - \mathbb{E}_S[\hat{f}_S(x)])^2 \right]\)。它衡量的是在不同训练集 \(S\) 上，模型预测值的波动程度。它反映了模型对训练集随机波动的敏感性（即 Estimation Error）。
- 高偏差 (High Bias) \(\rightarrow\) 欠拟合 (Underfitting)：
- 表现：模型太简单、太僵化（例如用一条直线去拟合复杂的正弦曲线）。
-
特点：无论你怎么换训练集，它画出的线都差不多（方差极低），但它永远抓不住真实的数据趋势（偏差极大）。增加模型的偏差会降低方差，但同时会增加近似误差 。
-
高方差 (High Variance) \(\rightarrow\) 过拟合 (Overfitting)：
- 表现：模型太复杂、太灵活（例如用 100 次多项式去穿过每一个数据点，把噪声也当成了规律）。
- 特点：它能在当前训练集上做到 0 误差（偏差极低），但只要训练集稍微变动一点点，它画出的曲线就会发生剧烈扭曲（方差极大）。
No Free Lunch Theorem：没有任何一个单一的学习算法能够在所有可能的数据分布上都表现最优 。你必须根据具体的任务，引入特定的先验知识（Inductive Bias）。
结构风险最小化 (Structural Risk Minimization, SRM)：为了控制方差，SRM 在 ERM 的基础上引入了对模型复杂度的惩罚：
这里的 \(\text{Penalty}(h)\) 与模型的 VC 维度高度相关。模型越复杂，惩罚越大。在实际应用中，这就演变成了我们熟知的 正则化 (Regularization)（如 L1/L2 惩罚项）。
交叉验证 (Cross-Validation)：在工程实践中，我们通过保留一部分数据作为验证集（Validation Set），来模拟测试环境，从而画出偏差-方差的 U 型曲线，找到那个让总测试误差降到最低的“甜点 (Sweet Spot)”。
线性回归模型和逻辑回归模型 (Linear & Logistic Regression)
线性回归假设输出 \(y\) 是输入特征 \(x\) 的线性组合，即 \(y = w^T x + b\)。
损失函数：均方误差 (Mean Squared Error, MSE)
如果假设观测值 \(y\) 的误差服从高斯分布（正态分布），那么最大化观测数据的 似然函数（Maximum Likelihood Estimation, MLE），在数学上完全等价于最小化均方误差。
目标函数（经验风险）：
向量化表示：令设计矩阵为 \(X \in \mathbb{R}^{m \times d}\)，标签向量为 \(y \in \mathbb{R}^m\)，则
闭式解 (Closed-form Solution / 解析解)
这是一个极其优良的凸二次规划问题。对 \(w\) 求导并令梯度为零：
求解得到著名的正规方程 (Normal Equation)：
当特征维度 \(d\) 大于样本数 \(m\) 时，\(X^T X\) 不可逆（奇异矩阵），这就必须引入正则化（如 L2 岭回归）来保证其可逆性并控制模型复杂度。
逻辑回归 (Logistic Regression)
Sigmoid (Logistic) 函数定义：\(\sigma(z) = \frac{1}{1 + \exp(-z)}\)
模型输出：预测样本属于正类 (\(y=1\)) 的概率为 \(P(y=1|x) = \sigma(w^T x)\)。
损失函数：交叉熵 (Cross-Entropy / Log-Loss)：基于极大似然估计，我们希望最大化所有样本产生真实标签的联合概率。取负对数后，就得到了交叉熵损失：
它的梯度形式极其简洁优美：
决策树模型
决策树是一种典型的非参数 (Non-parametric) 模型。它不预设数据的整体分布（比如不假设数据是线性可分的），而是采用分而治之的策略，通过一系列的“如果-那么 (If-Then)”规则，将高维特征空间正交地切割成一个个互不相交的矩形子区域（叶子节点）。
-
分类树 (Classification Tree)：在每个子区域内，采用多数表决（输出该区域内样本数最多的类别）。
-
回归树 (Regression Tree)：在每个子区域内，输出该区域所有样本标签的平均值（即分段常数逼近）。
决策树生长的核心问题是：在当前节点，应该选择哪个特征、哪个切分点来划分子区域？大纲中的三种常用指标分别是：
ID3 算法与信息熵 (Information Entropy)
假设当前数据集 \(D\) 中第 \(k\) 类样本的比例为 \(p_k\)，则 \(D\) 的信息熵定义为：
我们计算按特征 \(A\) 划分前后，系统信息熵的减少量。我们总是选择让信息熵下降最快的那个特征：
其中 \(D^v\) 是根据特征 \(A\) 的第 \(v\) 个取值划分出的子集。
C4.5 算法与信息增益率 (Information Gain Ratio)
信息增益天生偏好那些取值非常多的特征（比如把每个样本的“身份证号”作为一个特征，划分后每个子节点只有一个样本，纯度极高，但毫无泛化能力）。故引入特征 \(A\) 本身的固有熵 \(IV(A)\) 作为惩罚项：
CART 算法与基尼指数 (Gini Index)CART (Classification and Regression Trees)
永远只做二叉划分。它为了计算效率，放弃了对数运算，采用泰勒展开的一阶近似（因为 \(\ln(p) \approx p - 1\)），得到了基尼指数：
如果任由决策树生长，直到每个叶子节点里都只有一个样本（纯度 100%），这就相当于在训练集上实现了 0 误差。此时它的 VC 维度极高，方差极大，会把所有的噪声都死记硬背下来。
为了落实结构风险最小化 (SRM)，我们必须限制树的复杂度。
-
预剪枝 (Pre-pruning)：在分裂过程中，如果节点样本数少于阈值，或者纯度提升达不到阈值，就提前停止生长。
-
后剪枝 (Post-pruning)：先让树长到极大，然后从底向上评估。如果剪掉某个子树并将其替换为叶子节点后，在验证集上的代价复杂度（Cost-Complexity，即 误差 + \(\alpha \times\) 叶子节点数）降低了，就果断剪掉。这就完美呼应了我们之前总结的模型选择理论。
最近邻算法 (K-Nearest Neighbors, KNN)
KNN 是一种典型的非参数 (Non-parametric) 和基于实例 (Instance-based) 的学习方法。它不做任何关于数据分布的底层假设（不像线性回归假设了高斯噪声和线性关系），完全依赖训练集中已有的样本来决定新样本的类别或数值。
-
分类 (Classification)：对于一个未知的测试样本 \(x_{test}\)，在训练集中找到离它最近的 \(K\) 个样本。这 \(K\) 个邻居中，哪个类别出现的次数最多（多数表决），\(x_{test}\) 就被判定为哪个类别。
-
回归 (Regression)：找到最近的 \(K\) 个邻居，将这 \(K\) 个邻居的目标值取平均，作为 \(x_{test}\) 的预测值。
KNN 的核心是如何定义两点之间的“距离”。最常用的泛化形式是 闵可夫斯基距离 (Minkowski Distance)：给定两个 \(n\) 维向量 \(x = (x_1, \dots, x_n)\) 和 \(y = (y_1, \dots, y_n)\)：
\(K\) 值的选择直接决定了 KNN 模型的复杂度，容易作为考点。
Cover-Hart 定理：当训练样本量 \(N \to \infty\) 时，\(1\)-NN的渐进错误率最坏不会超过贝叶斯最优错误率（理论上的绝对极限）的两倍。
当特征维度 \(d\) 变大时：
-
数据稀疏性：为了维持相同的点密度，所需的样本量必须随维度呈指数级增长。在实际有限的样本下，高维空间显得极度空旷。
-
距离失效：随着维度升高，在高维空间中，任意两个随机点之间的距离差会趋近于零（即最短距离和最长距离变得几乎一样）。这意味着“最近邻”的概念在数学上失去了区分度，KNN 的有效性会遭受毁灭性打击。
支持向量机模型与核方法 (SVM & Kernel Methods)
硬间隔 SVM (Hard Margin)：
纯粹的几何与不等式对于线性可分的数据集，存在无数个超平面 \(w^T x + b = 0\) 可以将正负类分开。
SVM 的核心目标是：最优的超平面应该使得离它最近的样本点（支持向量）之间的“间隔 (Margin)”最大化。
样本点到超平面的几何距离为 \(\frac{|w^T x + b|}{||w||}\)。通过缩放 \(w\) 和 \(b\)，我们可以强制令离超平面最近的样本点满足 \(|w^T x + b| = 1\)。此时，正负类支持向量之间的总间隔为 \(\frac{2}{||w||}\)。
最大化间隔 \(\frac{2}{||w||}\)，等价于最小化 \(\frac{1}{2}||w||^2\)。这是一个经典的带线性不等式约束的凸二次优化问题：
软间隔 (Soft Margin) 与 Hinge Loss
现实数据通常存在噪声，不可能完美线性可分。如果强行用硬间隔，会导致优化无解，或者为了迁就几个异常点而使得间隔极窄（高方差、过拟合）。
- 松弛变量 (Slack Variables, \(\xi_i\))：允许样本点突破间隔边界，甚至被分错类别，但要付出代价 \(\xi_i \ge 0\)。
超参数 \(C\) 控制着偏差与方差的权衡。\(C\) 越大，对分错的容忍度越低（逼近硬间隔，容易过拟合）；\(C\) 越小，间隔越宽（容易欠拟合）。
- 等价的无约束形式 (Hinge Loss)：将约束条件代入目标函数，SVM 其实等价于带有 L2 正则化的经验风险最小化，其损失函数被称为 合页损失 (Hinge Loss)：
拉格朗日对偶与 KKT 条件
为了处理不等式约束并引入核技巧，我们需要将原问题转化为对偶问题 (Dual Problem)。
构造拉格朗日函数：引入非负乘子 \(\alpha_i \ge 0\)：
强对偶性 (Strong Duality)：由于原问题是凸二次规划且满足 Slater 条件，原问题的极小极大等价于对偶问题的极大极小（即 \(\min_{w,b} \max_{\alpha} \mathcal{L} = \max_{\alpha} \min_{w,b} \mathcal{L}\)）。
求导与代换：令 \(\mathcal{L}\) 对 \(w\) 和 \(b\) 的偏导为零，得到：
KKT 互补松弛条件 (Complementary Slackness)：最优解必须满足 \(\alpha_i [y_i(w^T x_i + b) - 1] = 0\)。
核技巧 (The Kernel Trick)
如果数据在原始空间完全非线性，我们可以通过一个映射函数 \(\phi(x)\) 将其映射到极高维甚至无限维的特征空间，使其变得线性可分。
观察将 \(w\) 代回后的对偶问题目标函数，你会发现，所有的样本 \(x\) 都是以 内积 \(\langle x_i, x_j \rangle\) 的形式出现的。
如果我们能找到一个 核函数 \(K(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle\)，我们就可以在原空间中直接计算出高维空间的内积。
Mercer 定理：判断一个函数能否作为核函数的充要条件是：对于任意有限个样本点，其构成的核矩阵 (Gram Matrix) 是对称半正定的。
常用核函数： * 多项式核 (Polynomial)：\(K(x, z) = (\gamma \langle x, z \rangle + r)^d\)
- 高斯径向基核 (RBF/Gaussian)：\(K(x, z) = \exp(-\gamma ||x - z||^2)\)
压缩感知 (Compressed Sensing)
传统的信号处理遵循奈奎斯特采样定理：为了无失真地恢复一个信号，采样频率必须至少是信号最高频率的两倍。这导致我们在处理高分辨率图像或宽带信号时，需要采集海量的数据，然后再进行压缩（比如 JPEG），丢弃掉大部分无用的信息。
既然绝大部分采集到的信息最终都要被丢弃（因为信号在某种变换域下是稀疏的），我们为什么不能在采样的同时直接获取被压缩的信号？
核心前提：信号 \(x \in \mathbb{R}^N\) 本身，或者它在某个正交变换基 \(\Psi\)（如傅里叶变换、小波变换）下的表示 \(s = \Psi^T x\)，只有极少数 \(K\) 个非零元素（\(K \ll N\)）。
假设我们要测量一个极高维的稀疏信号 \(x \in \mathbb{R}^N\)。我们用一个非常扁的测量矩阵 \(\Phi \in \mathbb{R}^{M \times N}\)（其中测量次数 \(M \ll N\)）对信号进行线性投影，得到极其简短的测量向量 \(y \in \mathbb{R}^M\)：
因为 \(M \ll N\)，方程的个数远少于未知数的个数，这是一个严重的欠定方程组，存在无穷多个解。不过既然我们提前知道 \(x\) 是稀疏的，我们只需要在无穷多个解中，挑出那个非零元素最少的解。这在数学上表达为最小化 \(L_0\) 范数：
但求解 \(L_0\) 最小化是一个经典的 NP-Hard 问题，无法求解。
凸松弛 (Convex Relaxation) 与 \(L_1\)
人们证明了，在一定条件下，我们可以将极其棘手的 \(L_0\) 最小化，完美等价地松弛为极其友好的 \(L_1\) 最小化问题：
基追踪 (Basis Pursuit, BP)：上述的 \(L_1\) 最小化问题是一个标准的凸优化问题（甚至可以转化为线性规划 Linear Programming），可以用极其高效的内点法或近端梯度下降法 (Proximal Gradient Descent) 来快速求解。
这要求我们的测量矩阵 \(\Phi\) 必须满足 约束等距性 (Restricted Isometry Property, RIP)：如果对于任意一个 \(K\)-稀疏的向量 \(x\)，测量矩阵 \(\Phi\) 都能极其稳定地保持它的欧氏长度使得下式成立：
其中常数 \(\delta_K \in (0, 1)\) 足够小，我们就说 \(\Phi\) 满足 RIP 条件。
真题
(Spring, 2025, A1) Let \(\mathcal{H}\) be a class of binary classifiers over a domain \(\mathcal{X}\). Let \(\mathcal{D}\) be an unknown distribution over \(\mathcal{X}\), and let \(f\) be the target hypothesis in \(\mathcal{H}\). Fix some \(h \in \mathcal{H}\). Show that the variance of the empirical loss \(L_S(h)\), over all possible samples \(S\) of size \(m\) drawn from \(\mathcal{D}\), is inversely proportional to \(m\) . That is, show the following relationship:
More specifically, prove the exact expression:
解答：设 \(Z_i = \mathbb{I}[h(x_i) \neq f(x_i)]\)，则 \(L_S(h) = \frac{1}{m} \sum_{i=1}^m Z_i\)。由于 \(Z_i\) 是独立同分布的二项随机变量，且 \(P(Z_i = 1) = L_{\mathcal{D},f}(h)\)，我们有：
因此，
(Spring, 2025, A2) Let \(\mathcal{X}\) be a domain, and let \(\mathcal{D}_1, \mathcal{D}_2, \dots, \mathcal{D}_m\) be a sequence of distributions over \(\mathcal{X}\). Let \(\mathcal{H}\) be a finite class of binary classifiers over \(\mathcal{X}\), and let \(f \in \mathcal{H}\). Suppose we obtain a sample \(S = \{(x_1, y_1), \dots, (x_m, y_m)\}\), where the \(i\)-th instance \(x_i\) is sampled from \(\mathcal{D}_i\) and \(y_i = f(x_i)\). Let \(\overline{\mathcal{D}}_m\) denote the average as:
Fix an accuracy parameter \(\epsilon = \frac{1}{4}\). Show that
Hint: \(\ln(\frac{3}{4}) < -\frac{1}{4}\)
解答：设 \(p_i=\mathbb{P}_{x \sim \mathcal{D}_i}[h(x) \neq f(x)]\)，则 \(L_{(\overline{\mathcal{D}}_m, f)}(h) = \frac{1}{m} \sum_{i=1}^m p_i>\epsilon\)。
而 \(\mathbb{P}_{S|x \sim \mathcal{D}^m}[L_{(S,f)}(h) = 0] = \prod_{i=1}^m (1-p_i) \le (1-\epsilon)^m=e^{m \ln(1-\epsilon)} \le e^{\frac{-m}{4}}\)。
(Spring, 2025, A3) Let \(\mathcal{H}\) and \(\mathcal{H}'\) be two families of functions mapping from \(\mathcal{X}\) to \(\{0,1\}\) with finite VC dimensions.
(a) [5 pts.] Show that
(b) [4 pts.] Use this to determine the VC dimension of the hypothesis set formed by the union of axis-aligned rectangles and triangles in dimension 2. You may use the fact that the VC dimension of the hypothesis set formed by the union of triangles in dimension 2 is 7, without any proof.
解答：\((a)\)：
若 \(m > d + d' + 1\)，则
矛盾！
\((b)\)：\(4+7+1=12\)
常见假设空间的 VC 维
-
简单一维空间 (\(\mathbb{R}^1\))：射线：\(h(x) = \mathbb{I}[x \ge a]\) 或 \(\mathbb{I}[x \le a]\) VC 维 = 1。闭区间 (Intervals)：\(h(x) = \mathbb{I}[x \in [a, b]]\) VC 维 = 2。带符号的区间 (Signed Intervals) VC 维 = 3。
-
二维与高维几何空间 (\(\mathbb{R}^d\))：半空间 (Halfspaces)：\(h(x) = \text{sign}(w^T x + b)\) VC 维 = \(d + 1\) 。轴对齐矩形 (Axis-aligned Rectangles)：\(d\) 维空间 (\(\mathbb{R}^d\)) VC 维 = \(2d\)。同心圆 (Concentric Circles)：\(h_r(x) = \mathbb{1}_{\{||x|| \le r\}}\)。VC 维 = 1。凸多边形 (Convex Polygons)：具有 \(k\) 个顶点的凸多边形。VC 维 = \(2k + 1\)。
-
正弦波分类器 (Sine Waves)：\(h(x) = \text{sign}(\sin(\omega x))\)，其中 \(\omega\) 是唯一的参数。VC 维 = \(\infty\)。
(Spring, 2025, A4) Prove the following two statements:
(a) [5 pts.] Let \(\mathcal{D}\) be a distribution. Let \(S = (z_1, \dots, z_m)\) be an i.i.d. sequence of examples. Let \(A\) be a learning algorithm that is on-average replace-one stable with rate \(\epsilon(m)\). Then:
(b) [5 pts.] Let \(L\) be a convex \(\rho\)-Lipschitz loss function. The regularised Empirical Risk Minimisation (ERM) satisfies:
where \(w^* = \arg\min_{w \in \mathcal{H}} L_{\mathcal{D}}(w)\).
解答：\((a)\)：设 \(S^{(i)}\) 是将 \(S\) 中的第 \(i\) 个样本替换为一个独立同分布的样本 \(z_i'\) 后得到的样本集。则：
如果我们引入一个全新的测试样本 \(z'\)，真实风险的期望可以写成：
如果 我们将 \(z'\) 替换为 \(z_i\)，经验风险的期望可以写成：
经验风险是训练集上的平均误差：
将真实风险的期望也写成 \(m\) 项取平均的形式（因为每项期望都相等）：
代回稳定性定义即得。
\((b)\)：ERM 定义的算法 \(A(S)\) 实际上是在最小化以下目标函数：
我们有
取期望有
带回 \((a)\) 的结果：
现在只需证明 \(\epsilon(m) \le \frac{2\rho^2}{\lambda m}\) 即可。设 \(u = A(S)\)，\(v = A(S^{(i)})\)。
因为 \(F_S\) 是 \(\lambda\)-强凸的，根据强凸性一阶条件：
两边约去即得。
(Autumn, 2025, A9) Let \(\mathcal{H}\) be the class of signed intervals, that is,
where
Calculate \(VCdim(\mathcal{H})\).
解答：考虑依次四个点分别取 \(1,-1,1,-1\)，则不能被 \(\mathcal{H}\) 完全打乱。三个点可以被 \(\mathcal{H}\) 完全打乱。故 \(VCdim(\mathcal{H})=3\)。
如果函数 \(f(x)\) 是 \(L\)-smoothness 的，意味着它的梯度是 \(L\)-Lipschitz 连续的。对于定义域内的任意 \(x, y\)，满足：\(\(||\nabla f(x) - \nabla f(y)|| \le L ||x - y||\)\)等价的二阶泰勒展开上限形式：
还有一个等价条件是 \(\frac{L}{2}||x||^2 - f(x)\) 是凸函数
如果函数 \(f(x)\) 是 \(\mu\)-strong convexity 的，说明它不仅是一个凸函数，而且至少和一个二次函数一样“凸”。对于任意 \(x, y\)，满足：\(\(f(y) \ge f(x) + \langle \nabla f(x), y-x \rangle + \frac{\mu}{2}||y-x||^2\)\)或者用梯度的单调性表示：\(\(\langle \nabla f(x) - \nabla f(y), x - y \rangle \ge \mu ||x - y||^2\)\)
(Autumn, 2025, A10) Strong Convexity Properties. Show the following holds. Let \(f: \mathbb{R}^d \rightarrow \mathbb{R}\). Then:
(a) The function \(f(w) = \lambda||w||^2\) is \(2\lambda\)-strongly convex.
(b) If \(f\) is \(\lambda\)-strongly convex and \(g\) is convex, then \(f+g\) is \(\lambda\)-strongly convex.
(c) If \(f\) is \(\lambda\)-strongly convex and \(u\) is a minimiser of \(f\), then for any \(w\),
解答：\((a)\)：我们需要证明对于任意 \(x,y\)，满足：
这等价于
代入 \(y=x+(y-x)\) 展开即得。
\((b)\)：由于 \(f\) 是 \(\lambda\)-强凸的，满足：
由于 \(g\) 是凸的，满足：
相加即得。
\((c)\)：由于 \(u\) 是 \(f\) 的最小值点，满足 \(\nabla f(u) = 0\)。代入即得。
(Autumn, 2025, A11) Let \(\mathcal{X} = \mathbb{R}^2\), \(\mathcal{Y} = \{0, 1\}\), and let \(\mathcal{H}\) be the class of concentric circles in the plane, that is,
where \(h_r(x) = \mathbb{1}_{\{||x|| \le r\}}\) Prove that \(\mathcal{H}\) is PAC learnable (assume realisability), and its sample complexity is bounded by
解答：我们只需取离原点最近的正样本点 \(x_{min}\)，令 \(r = ||x_{min}||\) 即可。此时对于真实的圆 \(r^*\)，模型的真实误差 \(L_{\mathcal{D}}(h_{\hat{r}})\) 就等于这个圆环区域在真实分布 \(\mathcal{D}\) 下的概率。
对 \(m\) 个独立的点，全不落在该圆环内的概率为 \((1-\epsilon)^m\le e^{-\epsilon m}\)。
因此为满足 \(\mathbb{P}[L_{\mathcal{D}}(h_{\hat{r}}) > \epsilon] \le \delta\)，我们需要 \(e^{-\epsilon m} \le \delta\)，即 \(m \ge \frac{\log(1/\delta)}{\epsilon}\)。
(Autumn, 2025, A12) We initialise \(w_1 \in \mathcal{W}\). At round \(t = 1, 2, \dots,\) we obtain a random estimate \(\hat{g}_t\) of a subgradient \(g_t \in \partial F(w_t)\) so that \(\mathbb{E}[\hat{g}_t] = g_t\), and update the iterate \(w_t\) as follows:
where \(\eta_t\) is a suitably chosen step-size parameter, and \(\Pi_{\mathcal{W}}\) denotes projection on \(\mathcal{W}\). Assume \(F\) is \(\lambda\)-strongly convex, and that
for all \(t\). Consider Stochastic Gradient Descent with step sizes \(\eta_t = \frac{1}{\lambda t}\). Show that for any \(w \in \mathcal{W}\), the following inequality holds:
解答：根据投影的非扩张性，我们有：
(Autumn, 2025, A13) Neural Networks are universal approximators: Let \(f: [-1, 1]^n \rightarrow [-1, 1]\) be a \(\rho\)-Lipschitz function. Fix some \(\epsilon > 0\). Construct a neural network \(N: [-1, 1]^n \rightarrow [-1, 1]\) with the sigmoid activation function, such that for every \(x \in [-1, 1]^n\) it holds that
Hint: Partition \([-1, 1]^n\) into small boxes. Use the Lipschitzness of \(f\) to show that it is approximately constant at each box. Finally, show that a neural network can first decide which box the input vector belongs to, and then predict the averaged value of \(f\) at that box.
解答：将 \([-1, 1]^n\) 均匀划分成 \(M^n\) 个小立方体，这里 \(M> \frac{2\rho \sqrt{n}}{\epsilon}\)。此时每个小立方体中函数值之差不超过 \(\epsilon\)，取 \(c_k\) 为该立方体中函数的平均值。
Sigmoid 函数 \(\sigma(z) = \frac{1}{1 + e^{-z}}\)。对大 \(K\) 考虑 \(\sigma(Kz)\)，它就会变成阶跃函数。
对于一维区间 \([a, b]\)，我们可以用两个并排的神经元来构造它的指示函数：
当 \(x_i\) 落在 \([a, b]\) 内时，前一项约为 1，后一项约为 0，差值为 1。落在外面则差值为 0。
对于高维的小立方体 \(B_k\)，构造
只有当 \(x\) 的每个坐标都落在对应的区间 \([a_i, b_i]\) 内时，内部的和才会达到 \(n\)，使得 \(\sigma\) 的输入大于 0.5，输出约为 1。否则至少有一个坐标不满足，和最多为 \(n-1\)，使得 \(\sigma\) 的输入小于 0.5，输出约为 0。
最后取 \(N=\sum_{k=1}^{M^n} c_k I_{B_k}(x)\) 即可。