机器学习范式与问题形式化：从经验风险最小化到结构风险最小化

机器学习的研究范式根植于统计推断与优化理论的交汇点，其核心承诺在于：通过数据驱动的方式构建预测模型，使计算系统能够从经验中自动提取模式，并对未见样本做出准确泛化。作为整部著作的基石，本章将严格形式化监督学习这一最基本的学习范式，将其精确地表述为在假设空间中搜索最优函数的数学优化问题。我们将首先构建监督学习的标准形式化框架，明确定义输入空间、输出空间、假设空间、损失函数以及期望风险与经验风险等核心概念。在此基础上，深入剖析经验风险最小化（Empirical Risk Minimization, ERM）原则——这一最直接的学习准则——的直觉 appeal 与内在缺陷，特别是其在高容量假设空间中必然导致的过拟合风险。进而，本章将引入结构风险最小化（Structural Risk Minimization, SRM）框架，揭示正则化理论如何作为ERM与SRM之间的桥梁，通过在优化目标中显式纳入模型复杂度惩罚，在拟合能力与泛化能力之间取得审慎平衡。为弥合抽象理论与具体实践之间的鸿沟，我们将以房价预测这一贯穿全书的综合案例为线索，逐步展示如何将现实世界问题转化为可计算的优化问题：从线性回归的ERM解出发，观察到多项式特征扩展带来的过拟合现象，最终通过岭回归（L2正则化）与Lasso（L1正则化）实践SRM原则。本章还将建立全书的统一符号体系，确保后续各章在讨论线性模型、核方法、决策树及集成学习算法时拥有共同的概念语言。最终，本章旨在传递一种深刻的机器学习哲学：学习不仅是关于在训练数据上达到低误差，更是关于对未知泛化能力的系统性追求；ERM是必要的起点，但SRM才是通向可靠模型的必由之路。

监督学习的形式化定义

监督学习（Supervised Learning）是机器学习中最成熟、应用最广泛的研究范式，其名称源于训练数据中每个输入样本均配有“监督信号”——即对应的输出标签或目标值。形式化地，我们定义输入空间（input space）$\mathcal{X}$ 与输出空间（output space）$\mathcal{Y}$。在回归（regression）任务中，$\mathcal{Y} \subseteq \mathbb{R}$ 为实数子集；在分类（classification）任务中，$\mathcal{Y}$ 为有限离散集合，如 $\{1,2,\dots,K\}$。学习过程基于一个训练集（training set）$S = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$，其中 $\mathbf{x}_i \in \mathcal{X}$ 为特征向量（feature vector），$y_i \in \mathcal{Y}$ 为对应标签。关键假设是：这些样本独立同分布（independent and identically distributed, i.i.d.）地采样自某个未知的联合概率分布 $P(X,Y)$。这一i.i.d.假设是统计学习理论的基石，它保证了训练样本能代表总体分布，但实际应用中需警惕数据依赖或时间序列等场景下的违反。

学习的核心是选择一个函数 $h: \mathcal{X} \to \mathcal{Y}$ 来近似未知的潜在关系。所有可能被考虑的候选函数构成假设空间（hypothesis space）$\mathcal{H}$。$\mathcal{H}$ 的选择反映了学习者的先验知识：例如，若认为目标与特征呈线性关系，则 $\mathcal{H}$ 可为所有线性函数；若认为关系复杂，则 $\mathcal{H}$ 可能包含深度神经网络。$\mathcal{H}$ 的容量（capacity）——即其表达复杂函数的能力——是过拟合与欠拟合权衡的核心。

为了评估函数 $h$ 的优劣，我们引入损失函数（loss function）$L: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_+$。损失函数量化了预测值 $h(\mathbf{x})$ 与真实值 $y$ 之间的误差。常用损失包括：

• 回归任务：均方误差（Mean Squared Error, MSE）$L(y, \hat{y}) = (y - \hat{y})^2$，或平均绝对误差（MAE）$L(y, \hat{y}) = |y - \hat{y}|$。
• 分类任务：0-1损失 $L(y, \hat{y}) = \mathbb{I}(y \neq \hat{y})$，但因其不可微，实践中常用替代损失如交叉熵（cross-entropy）或铰链损失（hinge loss）。

学习的终极目标是使模型在任意新样本上表现良好，即最小化期望风险（expected risk）或泛化误差（generalization error）： $$ R(h) = \mathbb{E}_{(X,Y) \sim P} [L(Y, h(X))] = \int_{\mathcal{X} \times \mathcal{Y}} L(y, h(\mathbf{x})) \, dP(\mathbf{x},y). $$ 然而，分布 $P$ 未知，无法直接计算 $R(h)$。唯一可利用的信息是训练集 $S$。由此自然导出经验风险（empirical risk）或训练误差（training error）： $$ \hat{R}(S, h) = \frac{1}{n} \sum_{i=1}^n L(y_i, h(\mathbf{x}_i). $$ 经验风险是期望风险在训练样本上的平均近似。监督学习问题因此可形式化为：在给定假设空间 $\mathcal{H}$ 和训练集 $S$ 的条件下，寻找一个假设 $h \in \mathcal{H}$ 使得经验风险最小化，或更一般地，使得某个关于经验风险与模型复杂度的联合目标最小化。

经验风险最小化原则及其局限性

经验风险最小化（ERM）是机器学习中最朴素、最直观的学习原则：既然无法直接优化期望风险 $R(h)$，便退而求其次，优化其可观测的代理——经验风险 $\hat{R}(S, h)$。即求解优化问题： $$ h_{\text{ERM}} = \arg\min_{h \in \mathcal{H}} \hat{R}(S, h). $$ ERM 的吸引力在于其简洁性与普适性：无论 $\mathcal{H}$ 是线性函数、决策树还是神经网络，无论损失函数是MSE还是交叉熵，学习过程均可统一表述为上述优化问题。许多经典算法均可视为ERM在特定 $\mathcal{H}$ 和 $L$ 下的实例：线性回归与逻辑回归分别对应线性 $\mathcal{H}$ 与MSE/交叉熵损失；支持向量机（SVM）对应线性（或核映射后） $\mathcal{H}$ 与铰链损失；决策树通过递归划分特征空间来最小化节点内样本的损失 impurity。

然而，ERM 原则存在一个根本性缺陷：当假设空间 $\mathcal{H}$ 容量过大（即模型过于复杂）时，ERM 解往往会导致过拟合（overfitting）。过拟合指模型在训练集上表现优异（经验风险极低），但在新样本上泛化能力差（期望风险高）。其本质是模型不仅学习了数据中真实的潜在规律（signal），还过度拟合了训练数据中的随机噪声（noise）。由于经验风险 $\hat{R}(S, h)$ 是期望风险 $R(h)$ 的随机变量，对于复杂 $\mathcal{H}$，总存在某个 $h \in \mathcal{H}$ 能对训练集进行“记忆”甚至“臆造”，使得 $\hat{R}(S, h)$ 异常低，但 $R(h)$ 却很高。

考虑一个回归问题的直观例子。假设真实函数为二次函数 $f(x) = x^2 + \epsilon$，其中 $\epsilon \sim \mathcal{N}(0, 0.1)$ 为高斯噪声。我们生成 $n=20$ 个训练样本。若采用多项式回归，假设空间 $\mathcal{H}_p$ 为所有次数不超过 $p$ 的多项式。当 $p=2$（与真实模型一致）时，ERM 解能较好捕捉二次趋势；但当 $p=9$（远高于真实次数）时，ERM 会找到一个振荡剧烈的高次多项式，恰好穿过所有训练点（训练误差接近0），但在点间剧烈波动，对噪声过度敏感，导致测试误差远高于 $p=2$ 的模型。此现象揭示了 ERM 的固有风险：在有限数据下，最小化训练误差并不保证最小化泛化误差。

从统计角度看，过拟合的发生与 $\mathcal{H}$ 的 VC 维（Vapnik-Chervonenkis dimension）或更一般的 Rademacher 复杂度密切相关。当 $\mathcal{H}$ 的容量远大于有效信息量时，经验风险 $\hat{R}(S, h)$ 与期望风险 $R(h)$ 之间的差距可能很大，且该差距的界随 $\mathcal{H}$ 容量增长而扩大。ERM 仅关注 $\hat{R}(S, h)$ 的最小化，却无视了 $R(h) - \hat{R}(S, h)$ 这一项可能因模型复杂而剧增。因此，单纯追求训练误差的最小化是危险的，尤其在小样本场景下。

过拟合的深入分析：偏差-方差权衡

理解过拟合的钥匙在于偏差-方差权衡（bias-variance tradeoff）。对于回归任务，给定一个学习算法 $\mathcal{A}$ 在训练集 $S$ 上产生的模型 $h_S$，其在某一点 $\mathbf{x}$ 的预测误差可分解为： $$ \mathbb{E}_S \left[ (y - h_S(\mathbf{x}))^2 \right] = \underbrace{\left( \mathbb{E}_S[h_S(\mathbf{x})] - f^*(\mathbf{x}) \right)^2}_{\text{偏差}^2} + \underbrace{\text{Var}_S(h_S(\mathbf{x}))}_{\text{方差}} + \underbrace{\sigma^2}_{\text{不可约误差}}. $$ 其中 $f^*(\mathbf{x}) = \mathbb{E}[Y|X=\mathbf{x}]$ 为真实条件期望，$\sigma^2$ 为噪声方差。偏差（bias）衡量模型假设空间 $\mathcal{H}$ 与真实函数 $f^*$ 之间的系统性差距；方差（variance）衡量模型对训练集随机波动的敏感度。

• **高偏差（欠拟合）**：当 $\mathcal{H}$ 过于简单（如用线性模型拟合非线性关系），即使训练数据充足，模型也无法捕捉真实模式，导致训练误差与测试误差均高。此时 $\mathbb{E}_S[h_S(\mathbf{x})]$ 远离 $f^*(\mathbf{x})$，偏差大，但不同训练集产生的 $h_S$ 差异小，方差低。
• **高方差（过拟合）**：当 $\mathcal{H}$ 过于复杂，模型能完美拟合训练数据（包括噪声），导致训练误差极低，但不同训练集产生的 $h_S$ 差异巨大，在测试点预测值波动大，方差高。此时 $\mathbb{E}_S[h_S(\mathbf{x})]$ 可能接近 $f^*(\mathbf{x})$（偏差低），但单个 $h_S$ 的预测因噪声而偏离。

ERM 在复杂 $\mathcal{H}$ 下倾向于选择方差极高的模型。例如，在多项式回归中，高次多项式拥有更多参数，对训练数据中的噪声点“言听计从”，导致模型在不同训练集上剧烈变化。直观上，模型复杂度与方差正相关，与偏差负相关。理想模型应在偏差与方差间取得平衡，使总误差最小。

下图以多项式回归为例，示意模型复杂度（多项式次数 $p$）与训练误差、

偏差-方差分解揭示了过拟合的统计本质：模型方差过高，意味着其对训练数据的随机扰动过度敏感。然而，仅理解这一分解不足以指导我们构建实际模型。我们需要一个系统性的原则，在优化目标中主动控制模型复杂度，从而在拟合训练数据与保持泛化能力之间取得平衡。这一原则即结构风险最小化（Structural Risk Minimization, SRM），由Vapnik等人从统计学习理论中系统提出。SRM并非替代ERM，而是对其的理性修正：它承认ERM作为学习基础的必要性，但强调必须将模型复杂度的惩罚纳入优化目标，以最小化泛化误差的上界。

结构风险最小化原则的形式化

SRM的核心思想是：泛化误差 $R(h)$ 可被分解为经验风险 $\hat{R}(S, h)$ 与一个依赖于假设空间 $\mathcal{H}$ 容量及样本量 $n$ 的复杂度惩罚项 $\Omega(h)$ 之和的上界。即存在某个函数 $\Phi$，使得对所有 $h \in \mathcal{H}$，以高概率有： $$ R(h) \leq \hat{R}(S, h) + \Omega(\mathcal{H}, n). $$ 这里的 $\Omega(\mathcal{H}, n)$ 通常与 $\mathcal{H}$ 的VC维 $d_{VC}$ 或 Rademacher 复杂度 $\mathfrak{R}_n(\mathcal{H})$ 相关，经典VC理论给出的界为： $$ R(h) \leq \hat{R}(S, h) + \mathcal{O}\left(\sqrt{\frac{d_{VC} ( \log(n/d_{VC}) + 1)}{n}}\right). $$ 该界表明：当样本量 $n$ 固定时，假设空间容量 $d_{VC}$ 越大，复杂度惩罚项越大，泛化误差的上界越宽松。因此，仅最小化 $\hat{R}(S, h)$ 是不够的；我们需要最小化一个同时包含经验风险与复杂度惩罚的结构风险（structural risk）： $$ R_{struct}(h) = \hat{R}(S, h) + \lambda \cdot \text{Complexity}(h), $$ 其中 $\lambda > 0$ 是权衡参数，$\text{Complexity}(h)$ 衡量单个假设 $h$ 的复杂度（如参数范数）。SRM原则即：在假设空间 $\mathcal{H}$ 中，寻找使结构风险 $R_{struct}(h)$ 最小的假设 $h_{SRM}$。

SRM提供了一种构造学习算法的通用方案：首先将假设空间 $\mathcal{H}$ 组织为一个嵌套序列 $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \mathcal{H}_3 \subset \dots$，其中每个 $\mathcal{H}_i$ 的容量递增（例如，线性函数、二次多项式、三次多项式...）。然后在每个子空间 $\mathcal{H}_i$ 中执行ERM，得到经验风险最小的假设 $h_i$。最后，选择使结构风险（或直接使泛化误差估计）最小的子空间及对应假设。这一过程本质上是在模型复杂度轴上做选择：简单模型（小 $\mathcal{H}_i$）偏差高但方差低，复杂模型（大 $\mathcal{H}_i$）偏差低但方差高；SRM旨在找到那个使总误差最小的“甜蜜点”。

正则化：从SRM原则到可计算目标

SRM原则本身是概念性的：它要求我们最小化一个包含未知泛化误差上界的表达式，这无法直接操作。正则化（regularization）是SRM在实践中的具体实现机制。其核心洞见是：若无法直接优化泛化误差上界中的复杂度项 $\Omega(\mathcal{H}, n)$，我们可以用一个关于假设 $h$ 本身的可计算复杂度度量 $\text{Complexity}(h)$ 来近似替代，从而将结构风险转化为一个可优化的目标函数。

最常用的正则化形式是参数范数惩罚（parameter norm penalty）。考虑假设空间 $\mathcal{H}$ 由某参数化模型族定义：$h_{\mathbf{w}}(\mathbf{x})$，其中 $\mathbf{w} \in \mathbb{R}^d$ 为模型参数。此时，模型复杂度常与参数向量 $\mathbf{w}$ 的范数相关。正则化后的优化问题变为： $$ \min_{\mathbf{w}} \frac{1}{n} \sum_{i=1}^n L(y_i, h_{\mathbf{w}}(\mathbf{x}_i)) + \lambda \cdot \mathcal{R}(\mathbf{w}). $$ 这里 $\mathcal{R}(\mathbf{w})$ 是正则化项（regularizer），$\lambda \geq 0$ 是正则化强度（regularization strength），控制着对复杂度惩罚的力度。当 $\lambda = 0$ 时，退化为纯ERM；当 $\lambda \to \infty$ 时，参数被强制趋近于零，模型趋于最简单。正则化项 $\mathcal{R}(\mathbf{w})$ 的选择直接体现了对“简单模型”的先验偏好，不同的选择导致不同的正则化方法，具有不同的统计性质和几何解释。

L2正则化（岭回归）

L2正则化使用参数向量的欧几里得范数平方作为惩罚项： $$ \mathcal{R}_{\text{L2}}(\mathbf{w}) = \|\mathbf{w}\|_2^2 = \sum_{j=1}^d w_j^2. $$ 对应的优化问题（以线性回归MSE损失为例）为： $$ \min_{\mathbf{w}} \frac{1}{n} \sum_{i=1}^n (y_i - \mathbf{w}^\top \mathbf{x}_i)^2 + \lambda \|\mathbf{w}\|_2^2. $$ 此即岭回归（Ridge Regression）。其解可通过求导得到闭式解： $$ \mathbf{w}_{\text{ridge}} = (\mathbf{X}^\top \mathbf{X} + \lambda n \mathbf{I})^{-1} \mathbf{X}^\top \mathbf{y}, $$ 其中 $\mathbf{X} \in \mathbb{R}^{n \times d}$ 为设计矩阵，$\mathbf{I}$ 为单位阵。与普通最小二乘（OLS）解 $\mathbf{w}_{\text{OLS}} = (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X}^\top \mathbf{y}$ 相比，岭回归在矩阵 $\mathbf{X}^\top \mathbf{X}$ 的对角线上添加了 $\lambda n$，这保证了矩阵的可逆性（即使 $\mathbf{X}^\top \mathbf{X}$ 奇异），并使得所有参数被收缩（shrinkage） towards zero，但不会精确为零。

几何解释：L2正则化在参数空间中定义了一个以原点为中心的球形（或超球形）约束区域 $\|\mathbf{w}\|_2^2 \l