第一章统计学习导论与线性回归回顾

1.1 统计学习基础

1.1.1 课程目标与结构

这节课有三个核心目标。首先是介绍统计学习的基本概念，让我们理解什么是统计学习以及它的基本思想。其次是建立回归和分类问题的数学框架，这个框架是后续所有方法的基础。最后是回顾线性回归，因为线性回归是最基础的方法，理解它对理解更复杂的方法至关重要。

课程内容分为五个部分：统计学习导论、统计学习的一般设定（包括统计建模简要回顾、监督学习的统计模型、经验风险最小化）、回归问题（介绍回归问题、二次损失/最小二乘法）、线性回归（普通最小二乘、几何解释、统计性质）以及附录。

1.1.2 机器学习的定义与学科定位

机器学习有一个被广泛接受的定义：它是研究计算方法的学科，这些方法通过将知识获取机械化来提高性能，而这个知识来自经验。这个定义的核心在于"从经验中学习"，而这里的经验指的就是数据。这就是为什么数据在机器学习中如此重要——它是经验的载体。

统计学习处于一个跨学科的交叉点。从计算机科学的角度看，人工智能是计算机科学的一个分支，而机器学习又是人工智能的一个子领域。从数学科学的角度看，统计学是数学的一个分支。这两条路径最终汇聚到统计学习。这种跨学科性质意味着统计学习既关注算法和计算（来自计算机科学），又关注数学理论和不确定性量化（来自统计学）。需要注意的是，在实践中，"机器学习"和"统计学习"这两个术语经常被互换使用，它们指的是同一类问题和方法，只是强调的侧重点略有不同。

1.1.3 监督学习的典型例子

房地产定价问题

第一个例子是预测爱荷华州Ames市的房地产价格。数据集包含1460个房地产交易记录，每个记录包含销售价格和79个属性。这些属性描述了房子的各种特征，比如建筑类别、分区分类、沿街长度、地块面积、街道类型、巷子类型、地块形状等。

这是一个监督学习问题，因为每个样本都有标签——在这里标签就是销售价格。我们的目标是学习一个函数，能够根据一栋房子的79个属性来预测它的价格。这里的"监督"指的是我们在训练时知道正确答案（实际销售价格），模型可以通过比较预测值和真实值来学习。

手写字符识别问题

第二个例子来自MNIST数据库的一个子集，包含70000张手写数字图像，每张图像大小为 28 \times 28 像素。数据集被分为60000个训练样本和10000个测试样本。

这同样是一个监督学习问题，但与房价预测不同，这是一个分类问题而非回归问题。这里的类别充当了标签的角色——每张图像对应0到9中的某个数字。我们的目标是学习一个分类器，能够将新的手写数字图像正确分类到10个类别之一。与回归问题预测连续值不同，分类问题预测的是离散的类别标签。

1.1.4 统计学习的应用领域

统计学习方法被应用在众多领域。计算机视觉处理图像和视频理解问题。语音识别将语音信号转换为文本。自然语言处理理解和生成人类语言。欺诈检测识别异常交易模式。个性化医疗根据个体特征制定治疗方案。自动驾驶车辆感知环境并做出决策。推荐系统和定向营销预测用户偏好。这些应用展示了统计学习方法的广泛适用性。

1.2 统计建模框架

1.2.1 数据的形式化表示

在开始统计学习之前，我们需要明确如何形式化地表示数据。用 d \in \mathcal{D} 来表示待分析的数据，这里 \mathcal{D} 是数据所在的空间。数据可以有多种形式。

第一种情况是在 n 个对象或个体上测量一个标量量。此时数据可以表示为 d = (d_1, \ldots, d_n)，其中每个 d_i \in \mathbb{R}，整个数据空间为 \mathcal{D} = \mathbb{R}^n。这里 n 是样本数量，每个样本只有一个测量值。

第二种情况更复杂：在 n 个对象上测量 p 个标量量，这些量可能具有不同的性质。此时每个个体 i 的数据不再是单个数值，而是一个向量

d_i = (d_i^{(1)}, \ldots, d_i^{(p)})^\top \in \mathbb{R}^p

整个数据集表示为 d = (d_1, \ldots, d_n)，对应的数据空间为 \mathcal{D} = \mathbb{R}^{n \times p}。这里 p 是特征维度，n 是样本数量。这种表示方式对应于我们前面看到的房价预测问题——79个属性就对应于 p=79。

第三种情况包含更复杂的数据结构，比如时间序列、符号数据、图结构等。这些数据不能简单地用实数向量表示，需要更一般的数学结构。

1.2.2 概率建模的核心思想

统计学习的基础是概率建模。这个思想的核心在于：我们不把观测到的数据 d 看作固定的确定性量，而是将其视为某个随机变量 D 的一次实现。这里"先验地"（a priori）意味着在观测数据之前，我们假设存在一个生成数据的随机机制，用随机变量 D 来刻画这个机制。一旦数据被观测，我们得到的 d 就是 D 的一个具体取值。

这种建模方式的意义在于：它承认数据中存在不确定性和随机性。如果我们重新收集数据，得到的结果会略有不同，而这种变化可以通过随机变量的概率分布来描述。

1.2.3 观测空间的定义

观测空间 (\mathcal{D}, \mathcal{A}) 是随机变量 D 取值的数学结构。\mathcal{D} 是一个可测空间，D 在其中取值。在大多数情况下，我们使用 \mathcal{D} = \mathbb{R}^n 配合 \mathcal{A} = \mathcal{B}(\mathbb{R}^n)（\mathbb{R}^n 上的Borel \sigma-代数）。更一般地，当数据是 n \times p 矩阵时，我们使用 \mathcal{D} = \mathbb{R}^{n \times p} 配合 \mathcal{A} = \mathcal{B}(\mathbb{R}^{n \times p})。

这里的 \mathcal{A} 是 \sigma-代数，它定义了哪些子集是"可测的"，即我们可以为其赋予概率。虽然这在理论上很重要，但在实际应用中，我们通常直接使用标准的Borel \sigma-代数，不需要过多关注这个技术细节。

1.2.4 统计建模的完整框架

统计建模基于一个概率空间 (\Omega, \mathcal{F}, \mathbb{P})。这个概率空间携带了所有的随机性：\Omega 是样本空间（所有可能结果的集合），\mathcal{F} 是事件空间（\Omega 上的 \sigma-代数），\mathbb{P} 是概率测度。

这个概率空间包含观测到的随机变量 D，以及任何我们可能需要的其他未观测随机变量。为什么需要未观测的随机变量？因为在很多模型中，数据的生成过程涉及隐变量或参数，这些量我们无法直接观测，但它们对建模至关重要。

关键点在于：概率测度 \mathbb{P} 并不是完全已知的。在现实中，我们不知道数据的真实生成机制。因此，我们考虑一个概率分布的集合 \mathcal{P}，它定义在 (\Omega, \mathcal{F}) 上，我们假设真实的概率测度包含在这个集合中。这就是统计推断的本质：我们试图从数据中推断 \mathcal{P} 中哪个分布最接近真实的 \mathbb{P}。

1.2.5 观测值的分布

用 \mathbb{P}^D 表示当底层概率测度为 \mathbb{P} 时，随机变量 D 的分布。这是 D 的边缘分布，它由 \mathbb{P} 通过 D 的定义诱导出来。我们有一个可能的分布集合

\mathcal{P}^D = \{\mathbb{P}^D : \mathbb{P} \in \mathcal{P}\}

这个集合包含了所有与 \mathcal{P} 中概率测度相对应的 D 的可能分布。

1.2.6 统计模型的形式化定义

统计模型被正式定义为一个三元组

\mathcal{M} = (\mathcal{D}, \mathcal{A}, \mathcal{P}^D)

这个定义将三个要素结合在一起：观测空间 \mathcal{D}（数据取值的空间）、\sigma-代数 \mathcal{A}（定义可测集）、以及分布族 \mathcal{P}^D（可能的概率分布集合）。这个三元组完整地描述了我们对数据生成过程的假设。

需要理解的是，对于给定的统计模型 \mathcal{M}，我们可以构造多个不同的概率空间 (\Omega, \mathcal{F}, \mathcal{P}, D) 来实现它。不同的构造方式可能包含不同的辅助随机变量，但它们都产生相同的观测数据分布族 \mathcal{P}^D。

特别地，当我们只关心观测到的随机变量 D 时，可以使用典型模型（canonical model）。在这个模型中，我们直接令 \Omega = \mathcal{D}（样本空间就是数据空间），\mathcal{F} = \mathcal{A}（事件空间就是观测空间的 \sigma-代数），\mathcal{P} = \mathcal{P}^D（概率测度族直接就是分布族），D = \mathrm{I}_{\mathcal{D}}（D 是恒等映射）。这个构造的优雅之处在于它消除了所有不必要的复杂性，直接将数据空间作为概率空间，使得理论分析更加简洁。

1.3 监督学习的统计模型

1.3.1 实例空间与标签空间

在监督学习中，我们需要明确两个基本空间。实例空间 \mathcal{X} 是输入数据所在的空间，每个实例 x_1, \ldots, x_n \in \mathcal{X} 代表一个待预测的对象。标签空间 \mathcal{Y} 是输出所在的空间，每个标签 y_1, \ldots, y_n \in \mathcal{Y} 对应于实例的真实答案。

以MNIST数据集为例，每张图像是 28 \times 28 像素，像素值在 [0,1] 范围内，因此实例空间为 \mathcal{X} = [0,1]^{28 \times 28}。标签空间包含十个类别，即 \mathcal{Y} = \{\text{"zero"}, \ldots, \text{"nine"}\}。

在本课程及后续课程中，我们始终假设实例空间为 \mathcal{X} = \mathbb{R}^p，其中 p 是特征维度。对于标签空间，有两种情况：当 \mathcal{Y} = \mathbb{R}^q 时，这是回归问题；当 \mathcal{Y} = \{0,1\} 时，这是分类问题。需要注意的是，\mathcal{Y} = \{0,1\} 更精确地说是二元分类。然而，二元分类方法同样可以应用于多类问题（比如MNIST的十分类问题），通常通过one-vs-rest或one-vs-one等策略实现。

1.3.2 监督学习的概率框架

监督学习的核心假设是：我们拥有一个独立同分布（iid）的样本，样本量为 n，记作

(X_1, Y_1), \ldots, (X_n, Y_n) \stackrel{\text{iid}}{\sim} \mathbb{P}^{X,Y}

这里 \mathbb{P}^{X,Y} 是定义在 \mathcal{X} \times \mathcal{Y} 上的未知概率测度。"未知"意味着我们不知道数据的真实生成机制，学习的目标就是从样本中推断这个机制。

独立同分布假设包含两层含义。"同分布"表示所有样本对都服从相同的联合分布 \mathbb{P}^{X,Y}，这保证了数据来自同一个稳定的过程。"独立"表示不同样本之间互不影响，一个样本的观测不会改变其他样本的分布。这个假设简化了理论分析，也是大多数统计学习方法的基础。

除非明确说明，我们对这个分布不做任何参数化假设。这被称为非参数设定，意味着我们不假设数据服从某个特定的参数族（如正态分布、泊松分布等）。这种灵活性使得方法具有更广的适用范围，但也带来了更大的挑战。

为了简化记号，我们用 (X, Y) 表示一对服从相同分布 \mathbb{P}^{X,Y} 的随机变量。观测到的数据点记作 D_i = (X_i, Y_i) \in \mathcal{D} = \mathcal{X} \times \mathcal{Y}，这里 \mathcal{D} 是数据空间。

1.3.3 监督学习的目标

监督学习的目标是从数据中学习一个预测函数

h : \mathcal{X} \to \mathcal{Y}, \quad x \mapsto y = h(x)

这个函数将实例映射到标签，使得对于新的输入 x，预测值 h(x) 与真实标签 Y 尽可能接近。这里"接近"的含义需要形式化定义。

为了量化预测的好坏，我们引入损失函数

L : \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}, \quad (y, \tilde{y}) \mapsto L(y, \tilde{y})

损失函数 L(y, h(x)) 量化了当真实标签是 y 而预测值为 h(x) 时所产生的损失。不同的问题需要不同的损失函数：回归问题常用平方损失，分类问题常用0-1损失或交叉熵损失。

严格来说，预测函数应该写成 h(x) = h(x; (X_1, Y_1), \ldots, (X_n, Y_n))，因为它是从训练数据中学习得到的，依赖于所有训练样本。但为了记号简洁，我们通常省略对训练数据的依赖。当标签空间 \mathcal{Y} 是有限集时，预测函数也称为分类函数或分类器。

1.3.4 风险函数的定义

给定损失函数 L 和预测函数 h，风险（也称泛化误差）定义为

R(h) = \mathbb{E}[L(Y, h(X))]

这里期望是关于随机变量对 (X, Y) 的，即关于联合分布 \mathbb{P}^{X,Y}。风险衡量的是预测函数在整个数据分布上的平均表现，而不仅仅是在训练样本上的表现。

将风险展开为积分形式，可以更清楚地看到它对未知分布的依赖：

R_\theta(h) = \iint_{\mathcal{X} \times \mathcal{Y}} L(y, h(x)) \mathbb{P}^{X,Y}(\mathrm{d}x, \mathrm{d}y)

这里用 \theta = \mathbb{P}^{X,Y} 表示未知分布，强调风险对分布的依赖性。从现在开始，当上下文清楚时，我们简单记为 R(h)。

风险的概念至关重要，因为它将"接近"这个模糊的概念转化为可以优化的数学目标。然而，由于分布 \mathbb{P}^{X,Y} 未知，我们无法直接计算 R(h)，这正是统计学习面临的核心困难。

1.3.5 最优预测函数

最优预测函数是使风险最小的函数，记作

h^* = h^*(\mathbb{P}^{X,Y}) = \arg\min_h R(h)

这个函数依赖于未知分布 \mathbb{P}^{X,Y}，因此在实践中无法直接获得。需要注意的是，最优预测函数的存在性和唯一性并不总是得到保证，这取决于损失函数的性质和函数空间的结构。

对应的最优风险为

R^* = \inf_h R(h)

这是在所有可能的预测函数中能达到的最小风险值。

现在我们可以明确监督学习的完整目标：从观测数据 (X_1, Y_1), \ldots, (X_n, Y_n) 出发，构造一个预测函数 \hat{h} : \mathcal{X} \to \mathcal{Y}，使得其风险 R(\hat{h}) 尽可能接近最优风险 R^*。这个目标的困难之处在于，我们既不知道真实分布 \mathbb{P}^{X,Y}（因此无法计算 R(\hat{h})），也不知道最优函数 h^*（因此无法直接模仿它）。统计学习的各种方法正是为了在这种不确定性下，找到性能良好的预测函数。

1.4 经验风险最小化

1.4.1 从理论风险到经验风险

前面我们定义了风险 R(h) = \mathbb{E}[L(Y, h(X))]，它衡量预测函数的好坏。然而，这个定义存在一个根本问题：联合分布 \mathbb{P}^{X,Y} 是未知的，因此我们无法计算 R(h)。这就像要评估一个函数的平均表现，却不知道数据从哪个分布中产生。

统计学习解决这个困境的核心思想是：用样本平均来近似期望。我们定义经验风险为

\hat{R}_n(h) = \iint_{\mathcal{X} \times \mathcal{Y}} L(y, h(x)) \hat{\mathbb{P}}_n(\mathrm{d}x, \mathrm{d}y) = \frac{1}{n} \sum_{i=1}^n L(Y_i, h(X_i))

这里 \hat{\mathbb{P}}_n 是经验测度，定义为

\hat{\mathbb{P}}_n = \frac{1}{n} \sum_{i=1}^n \delta_{X_i, Y_i}

其中 \delta_{X_i, Y_i} 是集中在点 (X_i, Y_i) 的狄拉克测度。经验测度的意义在于，它用观测样本的离散分布来替代未知的真实分布。对于任何可测集合 A \subseteq \mathcal{X} \times \mathcal{Y}，经验测度给出的概率 \hat{\mathbb{P}}_n(A) 就是落在 A 中的样本比例。

经验风险 \hat{R}_n(h) 就是在训练数据上的平均损失，这个量我们可以直接计算。根据大数定律，当样本量 n 足够大时，\hat{R}_n(h) 会收敛到真实风险 R(h)。这为用经验风险代替理论风险提供了理论依据。

1.4.2 经验风险最小化原则

有了经验风险这个可计算的代理目标，我们可以制定一般的学习方法。这个方法包含两个步骤。

第一步是选择一个预测函数族 \mathcal{H}。这个函数族定义了我们考虑的所有候选预测函数。为什么需要限制函数族？如果允许任意函数，我们可以构造一个函数在训练数据上完美拟合（经验风险为零），但在新数据上表现很差。通过限制 \mathcal{H}，我们引入了归纳偏置，帮助模型泛化。

第二步是选择使经验风险最小的函数

\hat{h}^{\text{ERM}} = \arg\min_{h \in \mathcal{H}} \hat{R}_n(h)

这就是经验风险最小化（ERM）原则。这个原则将学习问题转化为一个优化问题：在函数族 \mathcal{H} 中找到在训练数据上表现最好的函数。

需要理解各个组成部分在学习中的作用。标签空间 \mathcal{Y} 决定了问题的性质——是回归还是分类。损失函数 L 和可用的数据共同构成了ERM原则，它们定义了"好"的标准以及如何从数据中学习。函数族 \mathcal{H} 定义了候选预测函数的集合，它可以是线性函数、非线性函数等。这个方法的合理性依赖于 \mathcal{H} 不能太大——如果 \mathcal{H} 过于复杂，模型会过拟合训练数据。当函数族过于复杂时，需要引入惩罚项，这就是正则化的思想，将在下一讲中讨论。

1.5 回归问题

1.5.1 回归的定义与术语

从这里开始，我们专注于回归问题，即标签空间 \mathcal{Y} = \mathbb{R}。回归问题要预测的是连续值，而非离散类别。这个问题有着悠久的历史，最早由Francis Galton在1886年研究遗传身高时提出。Galton发现，父母身高与子女身高之间存在线性关系，但子女身高会"回归"到平均水平，这就是"回归"一词的来源。

在回归的语境中，有一套标准术语。输入变量 X 被称为解释变量（explanatory variable）、自变量（independent variable）、预测变量（predictor）、协变量（covariate）、属性（attribute）或特征（feature）。这些术语在不同领域中使用，但指的是同一个概念。输出变量 Y 被称为响应变量（response variable）、因变量（dependent variable）、被预测变量（predictand）或目标（target）。

1.5.2 回归中的常用损失函数

回归问题可以使用多种损失函数，它们对预测误差 y - \tilde{y} 有不同的惩罚方式。

二次损失（L_2 损失）定义为 L(y, \tilde{y}) = (y - \tilde{y})^2。这是回归中最常用的损失函数。它对误差的惩罚是平方的，意味着大误差受到更严厉的惩罚。

L_1 损失定义为 L(y, \tilde{y}) = |y - \tilde{y}|。与二次损失相比，L_1 损失对异常值更加鲁棒，因为它对误差的增长是线性的而非平方的。

Huber损失是二次损失和 L_1 损失的折中：在误差较小时使用二次损失，在误差较大时使用 L_1 损失。这使得它在保持平滑性的同时对异常值具有鲁棒性。

\epsilon-不敏感损失在误差小于 \epsilon 时为零，超过 \epsilon 后线性增长。这个损失函数在支持向量回归中使用，它允许一定范围内的误差不被惩罚。

1.5.3 二次损失与最优预测函数

二次损失 L(y, \tilde{y}) = (y - \tilde{y})^2 有一个重要的理论性质。对于二次损失，最优预测函数具有明确的形式。

命题指出：对于二次损失，对于任意 x \in \mathcal{X}，最优预测函数为

h^*(x) = \mathbb{E}[Y \mid X = x]

这个结果说明，在二次损失下，最优预测就是条件期望。为什么是条件期望？因为条件期望 \mathbb{E}[Y \mid X = x] 是在给定 X = x 的条件下，Y 的所有可能取值按概率加权的平均，它最小化了平方误差的期望。这个函数有时被称为回归函数（regression function），这里的"回归"是数学意义上的条件期望，而非统计学习方法的名称。

从现在开始直到另行通知，我们将始终使用二次损失。这个选择不仅因为它在理论上有良好的性质，还因为它在计算上带来便利——许多优化问题在二次损失下有闭式解。

1.5.4 候选函数族

在经验风险最小化框架下，我们需要指定候选函数族 \mathcal{H}。不同的函数族代表了不同的建模假设。

线性（仿射）预测函数是最简单的选择：

\mathcal{H} = \left\{ h : \mathbb{R}^p \to \mathbb{R} \mid \exists \beta \in \mathbb{R}^{p+1}, \forall x \in \mathcal{X}, h(x) = \beta_0 + \beta_1 x^{(1)} + \ldots + \beta_p x^{(p)} \right\}

这里 \beta_0 是截距项，\beta_1, \ldots, \beta_p 是各个特征的系数。虽然称为"线性"，但严格来说这是仿射函数，因为有常数项。

更一般的是带基函数的线性模型。这种模型首先通过已知的基函数 h_k : \mathcal{X} \to \mathbb{R} 对输入进行非线性变换，然后在变换后的空间中进行线性组合：

h(x) = \beta_1 h_1(x) + \ldots + \beta_K h_K(x)

基函数可以是多项式、样条函数、径向基函数等。这种方法的优势在于，虽然对原始特征是非线性的，但对参数 \beta 仍然是线性的，保留了计算上的便利性。

加性模型进一步放宽假设，允许每个特征独立地以非线性方式影响输出：

h(x) = h_1(x^{(1)}) + \ldots + h_p(x^{(p)})

每个 h_j 可以是任意函数。这种模型在保持可解释性的同时增加了灵活性。

神经网络和决策树代表了更复杂的非线性函数族。神经网络通过多层非线性变换构建复杂的函数，决策树通过递归分割输入空间来建模。这些方法的表达能力更强，但可解释性较差，也更容易过拟合。

1.6 最小二乘方法

1.6.1 最小二乘估计量的定义

当使用二次损失时，经验风险具有特殊的形式

\hat{R}_n(h) = \frac{1}{n} \sum_{i=1}^n (y_i - h(x_i))^2

最小化这个经验风险得到的估计量被称为最小二乘估计量

\hat{h}^{\text{LS}} = \arg\min_{h \in \mathcal{H}} \sum_{i=1}^n (y_i - h(x_i))^2

这里我们直接优化平方误差之和，而不是平均值，因为两者的最小化点相同（只差一个常数因子 1/n）。

需要注意术语上的区别。经验风险 \hat{R}_n(h) 也被称为均方误差（mean-squared error）。目标函数 \text{RSS}(h) = \sum_{i=1}^n (y_i - h(x_i))^2 被称为残差平方和（residual sum of squares，RSS）。这里"残差"指的是观测值与预测值之间的差异 y_i - h(x_i)。

1.6.2 模型评估指标

有两个常用的指标来评估最小二乘拟合的质量。

第一个是残差平方和 \text{RSS}(\hat{h}^{\text{LS}})，它直接衡量模型在训练数据上的拟合误差。RSS越小，说明模型对训练数据的拟合越好。

第二个是决定系数 R^2，定义为

R^2 = \frac{\sum_{i=1}^n (y_i - \hat{h}^{\text{LS}}(x_i))^2}{\sum_{i=1}^n (y_i - \bar{y}_n)^2} = 1 - \frac{\text{RSS}(\hat{h}^{\text{LS}})}{\text{TSS}}

这里 \bar{y}_n = \frac{1}{n} \sum_{i=1}^n y_i 是响应变量的样本均值，\text{TSS} = \sum_{i=1}^n (y_i - \bar{y}_n)^2 是总平方和（total sum of squares）。

R^2 的含义可以这样理解：TSS衡量响应变量自身的总变异性，如果我们不使用任何预测变量，只用均值 \bar{y}_n 来预测所有样本，误差就是TSS。RSS衡量使用模型预测后的剩余变异性。因此 R^2 = 1 - \text{RSS}/\text{TSS} 表示模型解释了多少比例的变异性。R^2 的取值范围是 0 \leq R^2 \leq 1，其中 R^2 = 1 当且仅当 y_i = x_i^\top \hat{\beta}^{\text{OLS}} 对所有 i 成立，即模型完美拟合所有数据点。R^2 越接近1，说明模型的解释能力越强。

1.6.3 与最大似然估计的联系

最小二乘方法看似是一个纯粹的优化过程，但它与统计推断中的最大似然估计有深刻的联系。

假设数据生成模型为 Y_i = h_0(X_i) + \varepsilon_i，其中误差项 \varepsilon_i \stackrel{\text{iid}}{\sim} \mathcal{N}(0, \sigma^2) 服从独立同分布的正态分布。在这个假设下，给定 X_i，Y_i 服从正态分布 Y_i \mid X_i \sim \mathcal{N}(h_0(X_i), \sigma^2)。

条件对数似然函数为

\ell(h) = \log(\mathcal{L}(h)) = \log \left( \prod_{i=1}^n \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left( -\frac{(y_i - h(x_i))^2}{2\sigma^2} \right) \right)

利用对数的性质，这可以简化为

\ell(h) = -\frac{n}{2} \log(2\sigma^2) - \frac{1}{2\sigma^2} \sum_{i=1}^n (y_i - h(x_i))^2

最大化对数似然等价于最小化 \sum_{i=1}^n (y_i - h(x_i))^2，因为其他项不依赖于 h。这说明最小二乘方法等价于在正态误差假设下的最大条件似然估计。

此外,方差参数 \sigma^2 的最大条件似然估计为

\hat{\sigma}^2 = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{h}^{\text{LS}}(x_i))^2

这正是残差的样本方差。这个联系揭示了最小二乘方法的概率解释：它隐含地假设了误差的正态分布和同方差性。

1.7 线性回归

1.7.1 线性模型的设定

现在我们专注于线性预测函数族。可用数据为 \{(x_1, y_1), \ldots, (x_n, y_n)\}。我们考虑形如

h(x) = \beta_0 + \beta_1 x^{(1)} + \ldots + \beta_p x^{(p)} = \beta^\top x

的预测函数，其中参数向量和扩展输入向量分别为

\beta = \begin{pmatrix} \beta_0 \\ \beta_1 \\ \vdots \\ \beta_p \end{pmatrix}, \quad x = \begin{pmatrix} 1 \\ x^{(1)} \\ \vdots \\ x^{(p)} \end{pmatrix}

这里我们将输入向量扩展为 (p+1) 维，第一个分量为1，这样可以将截距 \beta_0 统一到向量表示中。参数 \beta_0 被称为截距（intercept），它表示当所有输入特征为零时的预测值基准。

图示展示了线性回归的几何意义：对于每个样本点 (x_i, y_i)，模型给出预测值 \hat{y}_i = \beta_1 x_i + \beta_0，观测值与预测值之间的垂直距离 e_i = y_i - \hat{y}_i 就是残差。最小二乘方法的目标是找到一条直线，使得所有残差的平方和最小。

普通最小二乘估计量定义为

\hat{\beta}^{\text{OLS}} = \arg\min_{\beta \in \mathbb{R}^{p+1}} \sum_{i=1}^n (y_i - x_i^\top \beta)^2

这是一个关于参数 \beta 的无约束二次优化问题。

1.7.2 矩阵-向量记号

为了更简洁地表示和求解最小二乘问题，我们引入矩阵-向量记号。定义设计矩阵

X = \begin{pmatrix} 1 & x_1^{(1)} & \ldots & x_1^{(p)} \\ 1 & x_2^{(1)} & \ldots & x_2^{(p)} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_n^{(1)} & \ldots & x_n^{(p)} \end{pmatrix}, \quad y = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}

设计矩阵 X 的大小是 n \times (p+1)，第一列全为1对应截距，其余列对应各个特征。响应向量 y 的长度为 n。

利用这个记号，残差平方和可以表示为

\text{RSS}(\beta) = ||y - X\beta||^2 = (y - X\beta)^\top (y - X\beta)

将其展开得到

\text{RSS}(\beta) = \beta^\top X^\top X \beta - 2y^\top X\beta + y^\top y

这是关于 \beta 的二次型，第一项是二次项，第二项是线性项，第三项是常数项。这个展开形式对于求解最优化问题至关重要。

1.7.3 普通最小二乘估计量的闭式解

在假设 X^\top X 可逆的条件下，最小化问题有唯一解

\hat{\beta}^{\text{OLS}} = (X^\top X)^{-1} X^\top y

这个解被称为普通最小二乘（OLS）估计量。为什么这是最优解？对 \text{RSS}(\beta) 关于 \beta 求导并令其为零，得到正规方程 X^\top X \beta = X^\top y。当 X^\top X 可逆时，直接求解得到上式。

矩阵 X^\top X 的可逆性要求什么？它要求设计矩阵 X 的列向量线性无关，即特征之间不存在完全的线性相关性，且样本量 n 不少于参数个数 p+1。如果存在多重共线性（特征高度相关），X^\top X 可能接近奇异，数值计算会不稳定。

回顾决定系数的定义

R^2 = \frac{\sum_{i=1}^n (y_i - x_i^\top \hat{\beta}^{\text{OLS}})^2}{\sum_{i=1}^n (y_i - \bar{y}_n)^2} = 1 - \frac{\text{RSS}(\hat{\beta}^{\text{OLS}})}{\text{TSS}}

R^2 满足 0 \leq R^2 \leq 1，且 R^2 = 1 当且仅当模型完美拟合所有训练点，即 y_i = x_i^\top \hat{\beta}^{\text{OLS}} 对所有 i 成立。需要注意的是，R^2 高并不一定意味着模型好——它只衡量训练数据上的拟合程度，可能掩盖过拟合问题。在后续内容中，我们将讨论如何评估模型的泛化能力。

1.8 几何解释

1.8.1 列空间与投影的观点

线性回归有一个很漂亮的几何解释，将 X 的列向量记作 \underline{x}^{(0)}, \underline{x}^{(1)}, \ldots, \underline{x}^{(p)}，其中 \underline{x}^{(0)} = (1, 1, \ldots, 1)^\top 对应截距项，其余列 \underline{x}^{(j)} 对应第 j 个特征在所有样本上的取值。同时将 X 的行向量记作 x_1^\top, x_2^\top, \ldots, x_n^\top，每一行对应一个样本的扩展特征向量。

普通最小二乘估计量的优化问题

\hat{\beta}^{\text{OLS}} = \arg\min_{\beta \in \mathbb{R}^{p+1}} ||y - X\beta||^2 = \arg\min_{\beta \in \mathbb{R}^{p+1}} ||y - (1\beta_0 + \underline{x}^{(1)}\beta_1 + \ldots + \underline{x}^{(p)}\beta_p)||^2

从几何角度，这个最小化问题等价于在列向量 \{1, \underline{x}^{(1)}, \ldots, \underline{x}^{(p)}\} 张成的空间中，寻找距离 y 最近的向量（在 L^2 范数意义下）。换句话说，我们将响应向量 y 投影到由设计矩阵列向量张成的子空间上。

为什么这是投影？在欧几里得空间中，一个向量到子空间的最短距离对应于正交投影——连接向量与其投影点的线段垂直于子空间。在我们的问题中，y \in \mathbb{R}^n 是 n 维空间中的一个点，设计矩阵的列向量张成一个 (p+1) 维子空间（假设列向量线性无关），最小二乘解 \hat{y} = X\hat{\beta}^{\text{OLS}} 就是 y 在这个子空间上的正交投影。

1.8.2 投影的几何图示

图示展示了这个几何关系。在三维空间中，y 是蓝色箭头表示的向量，\underline{x}^{(0)} 和 \underline{x}^{(1)} 张成一个二维平面（红色），\hat{y} 是 y 在这个平面上的投影。从投影点到 y 的残差向量垂直于这个平面。

投影向量可以表示为

\hat{y} = X\hat{\beta}^{\text{OLS}} = X(X^\top X)^{-1}X^\top y = Py

这里定义了投影矩阵

P = X(X^\top X)^{-1}X^\top

投影矩阵将任意向量映射到列空间上。注意这个矩阵只依赖于 X，不依赖于 y——它完全由设计决定。

1.8.3 投影矩阵的性质

投影矩阵 P 被称为帽子矩阵（hat matrix），因为它将 y 变成 \hat{y}（加上了"帽子"）。这个矩阵有几个重要的性质。

首先，I_n - P 也是一个投影矩阵，它将向量投影到设计矩阵列空间的正交补空间。这个正交补空间就是残差向量 e = y - \hat{y} = (I_n - P)y 所在的空间。两个投影矩阵 P 和 I_n - P 将 \mathbb{R}^n 分解为两个正交的子空间。

其次，P 是幂等矩阵，即 PP = P。这个性质的几何意义是：对一个向量投影两次等于投影一次。如果一个向量已经在子空间中，再次投影不会改变它。这可以验证：

PP = X(X^\top X)^{-1}X^\top X(X^\top X)^{-1}X^\top = X(X^\top X)^{-1}X^\top = P

第三个性质是投影矩阵的迹。我们有

\text{tr}(P) = \text{tr}\left(X(X^\top X)^{-1}X^\top\right) = \text{tr}\left(X^\top X(X^\top X)^{-1}\right) = \text{tr}(I_{p+1}) = p+1

这里利用了迹的循环性质 \text{tr}(AB) = \text{tr}(BA)。投影矩阵的迹等于子空间的维数，这是因为迹等于特征值之和，而投影矩阵的特征值只能是0或1（对应于垂直于子空间或在子空间中的方向），1的个数等于子空间维数。

1.8.4 杠杆分数

投影矩阵的对角元素 P_{ii} 被定义为杠杆分数（leverage score），它衡量第 i 个数据点对模型的影响力。为什么称为"杠杆"？因为它量化了第 i 个观测值对其自身预测值的影响程度。

从关系式可以看出

\hat{y}_i = P_{ii}y_i + \sum_{j \neq i} P_{ij}y_j

P_{ii} 表示 y_i 对 \hat{y}_i 的直接贡献权重。在线性模型中，预测值 \hat{y}_i 是所有观测值 y_j 的线性组合，P_{ii} 给出了 y_i 的自我影响。

杠杆分数满足 0 \leq P_{ii} \leq 1。如果某个样本的 P_{ii} 接近1，说明这个样本对自己的预测有很大影响，可能是一个异常点或高影响力点。如果 P_{ii} 接近0，说明该样本的预测主要由其他样本决定。所有杠杆分数之和等于 p+1（投影矩阵的迹），因此平均杠杆分数为 (p+1)/n。如果某个样本的杠杆分数明显高于平均值，需要特别关注，因为它可能对拟合结果产生不成比例的影响。

1.9 统计性质

1.9.1 统计假设

为了研究估计量的统计性质，我们需要将数据视为底层随机变量的实现。回顾我们有

(X_1, Y_1), \ldots, (X_n, Y_n) \stackrel{\text{iid}}{\sim} \mathbb{P}^{X,Y}

我们做出以下假设。首先，假设 X_i 是确定性的，或者等价地说，我们在给定 X_i 的条件下工作。这个假设意味着我们将输入变量视为固定的设计点，不确定性只来自于响应变量 Y_i。在实践中，这对应于实验设计的情形，研究者可以控制输入变量的取值。即使在观测数据中，这个假设也可以理解为条件分析——我们关心的是给定观测到的 X 值时，Y 的条件分布。

进一步假设存在参数 \beta^* \in \mathbb{R}^{p+1} 使得线性模型成立：

(i) 对于所有 i，Y_i = X_i^\top \beta^* + \varepsilon_i

这个假设说明真实的数据生成过程是线性的，加上一个误差项 \varepsilon_i。这里 \beta^* 是我们希望估计的真实参数，\varepsilon_i 捕捉了模型无法解释的随机波动。

对于误差项 \varepsilon_i，我们进一步假设：

(ii) 中心化：\mathbb{E}[\varepsilon_i] = 0

这个假设保证误差的平均效应为零，不存在系统性偏差。如果误差有非零均值，可以将其吸收到截距项中。

(iii) 不相关：i \neq j \Rightarrow \text{Cov}[\varepsilon_i, \varepsilon_j] = 0

这个假设说明不同样本的误差之间相互独立，一个样本的误差不会影响另一个样本。这在时间序列或空间数据中可能被违反，但对于独立抽样的横截面数据通常成立。

(iv) 同方差性：\text{Var}[\varepsilon_i] = \sigma^2 对某个 \sigma^2 > 0

这个假设要求所有误差项具有相同的方差。这意味着预测误差的大小不依赖于输入变量的值。如果这个假设被违反（称为异方差性），虽然OLS估计量仍然无偏，但不再是最优的。

这些假设合起来可以用矩阵形式表示为 Y = X\beta^* + \varepsilon，其中 \mathbb{E}[\varepsilon] = 0，\text{Var}[\varepsilon] = \sigma^2 I_n。

1.9.2 OLS估计量的基本性质

在上述假设下，我们可以推导OLS估计量的统计性质。

命题指出：在假设(i)-(iv)下，\hat{\beta}^{\text{OLS}} 是一个无偏估计量，即

\mathbb{E}[\hat{\beta}^{\text{OLS}}] = \beta^*

为什么无偏？将OLS估计量展开

\hat{\beta}^{\text{OLS}} = (X^\top X)^{-1}X^\top Y = (X^\top X)^{-1}X^\top (X\beta^* + \varepsilon) = \beta^* + (X^\top X)^{-1}X^\top \varepsilon

由于 X 是确定性的，\mathbb{E}[\varepsilon] = 0，我们有 \mathbb{E}[\hat{\beta}^{\text{OLS}}] = \beta^* + (X^\top X)^{-1}X^\top \mathbb{E}[\varepsilon] = \beta^*。无偏性意味着如果我们重复采样多次，估计值会围绕真实参数波动，平均来说等于真值。

协方差矩阵为

\text{Var}[\hat{\beta}^{\text{OLS}}] = \sigma^2 (X^\top X)^{-1}

这个结果如何得到？由于 \hat{\beta}^{\text{OLS}} - \beta^* = (X^\top X)^{-1}X^\top \varepsilon，利用方差的性质

\text{Var}[\hat{\beta}^{\text{OLS}}] = (X^\top X)^{-1}X^\top \text{Var}[\varepsilon] X(X^\top X)^{-1} = (X^\top X)^{-1}X^\top (\sigma^2 I_n) X(X^\top X)^{-1} = \sigma^2 (X^\top X)^{-1}

这个协方差矩阵告诉我们估计量的不确定性。对角元素给出各个参数估计的方差，非对角元素给出参数估计之间的协方差。矩阵 (X^\top X)^{-1} 的结构完全由设计矩阵决定——如果特征之间高度相关（多重共线性），这个矩阵的元素会很大，导致估计的不确定性增加。

1.9.3 Gauss-Markov定理

Gauss-Markov定理是线性回归理论中的一个基石性结果。它说明在假设(i)-(iv)下，\hat{\beta}^{\text{OLS}} 是 \beta^* 的最佳线性无偏估计量（BLUE，Best Linear Unbiased Estimator）。

"最佳"是什么意思？对于任何形如 \tilde{\beta} = MY 的线性无偏估计量（M 是某个矩阵），对于任意向量 v \in \mathbb{R}^{p+1}，我们有

v^\top \text{Var}[\hat{\beta}^{\text{OLS}}] v \leq v^\top \text{Var}[\tilde{\beta}] v

这意味着在所有线性无偏估计量中，OLS的方差最小。这里"线性"指估计量是观测值 Y 的线性函数，"无偏"指期望等于真值，"最佳"指在方差意义下最优。这个定理的强大之处在于，它不需要假设误差的正态分布——只要满足前四个假设，OLS就在所有线性无偏估计量中最优。

1.9.4 正态性假设与分布理论

如果我们增加一个额外的假设：

(v) 正态性：\varepsilon_1, \ldots, \varepsilon_n 联合服从正态分布

那么假设(i)-(v)合起来给出 \varepsilon_i \stackrel{\text{iid}}{\sim} \mathcal{N}(0, \sigma^2)。在这个更强的假设下，普通最小二乘估计量等价于最大条件似然估计量，方差的估计量为

\hat{\sigma}^2 = \frac{1}{n} \sum_{i=1}^n (y_i - x_i^\top \hat{\beta}^{\text{OLS}})^2

Student定理给出了估计量的精确分布。在正态性假设下：

\hat{\beta}^{\text{OLS}} \sim \mathcal{N}\left(\beta^*, \sigma^2 (X^\top X)^{-1}\right)

这说明OLS估计量服从多元正态分布，均值为真值，协方差矩阵为 \sigma^2 (X^\top X)^{-1}。

方差估计量服从缩放的卡方分布：

\hat{\sigma}^2 \sim \frac{\sigma^2}{n} \chi^2(n - p - 1)

其中 \chi^2(n-p-1) 表示自由度为 n-p-1 的卡方分布。自由度是 n-p-1 而非 n，因为我们估计了 p+1 个参数，损失了相应的自由度。

最重要的是，\hat{\beta}^{\text{OLS}} 和 \hat{\sigma}^2 是独立的。这个独立性对于构造检验统计量至关重要。

1.9.5 统计推断

有了分布理论，我们可以进行统计推断。给定 \hat{\beta}_j^{\text{OLS}} \sim \mathcal{N}(\beta_j, \sigma^2 v_j)，其中 v_j = [(X^\top X)^{-1}]_{jj} 是协方差矩阵的第 j 个对角元素，我们可以构造枢轴统计量

T = \frac{\hat{\beta}_j^{\text{OLS}} - \beta_j}{\sqrt{\frac{n \hat{\sigma}^2 v_j}{n-p-1}}} \sim \mathcal{T}(n - p - 1)

这个统计量服从自由度为 n-p-1 的Student t分布。为什么是t分布而非正态分布？因为分母中包含了未知方差的估计量 \hat{\sigma}^2。如果方差已知，统计量会服从标准正态分布。由于方差未知需要估计，引入了额外的不确定性，导致分布的尾部更重，这正是t分布相对于正态分布的特点。

需要注意分母中的项

\frac{n\hat{\sigma}^2}{n-p-1} = \frac{1}{n-p-1} \sum_{i=1}^n (Y_i - X_i^\top \hat{\beta}^{\text{OLS}})^2

是 \sigma^2 的无偏估计量。这个估计量除以 n-p-1 而非 n，进行了自由度修正。

利用这个枢轴统计量，我们可以构造置信区间、进行假设检验等推断。例如，检验 H_0: \beta_j = 0（第 j 个特征是否显著），可以计算t统计量并与临界值比较，或计算p值判断显著性。

1.10 本章小结

本讲涵盖了监督学习的基本概念。我们首先介绍了实例空间和标签空间的概念，然后建立了支撑学习任务的统计模型，包括损失函数和经验风险最小化的框架。

在回归部分，我们讨论了常见的损失函数，重点关注二次损失及其与最大似然估计的联系，并介绍了最小二乘准则。

线性回归的回顾包含三个方面：普通最小二乘的计算公式及其闭式解、几何解释（投影和帽子矩阵的概念）、以及统计性质（无偏性、协方差矩阵、Gauss-Markov定理和正态性假设下的分布理论）。这些内容为后续更高级的方法奠定了基础。

第二章模型评估与选择

2.1 引言

这一讲的核心内容是如何评价一个机器学习模型的好坏，以及如何在多个候选模型中选择最优的那个。整个讲座围绕五个关键问题展开：首先是偏差-方差权衡这个贯穿机器学习的基本矛盾，其次是如何定义和估计模型在未见数据上的表现即泛化误差，第三是交叉验证这一实用的模型评估技术，第四是正则化回归方法，最后是系统性的模型选择策略。课程内容分为四个板块：偏差-方差权衡、泛化误差（包含过拟合问题、训练-测试集划分和交叉验证）、正则化回归（岭回归和LASSO）以及模型选择方法。

2.1.1 回归问题的基本设定

在开始讨论模型评估之前，我们需要明确回归问题的基本框架。我们拥有 n 个训练样本，每个样本是一个输入-输出对 (x_i, y_i)，其中 i 从 1 到 n。我们的目标是从一个候选函数族 \mathcal{H} 中找到一个预测函数 h。学习算法的本质是通过最小化经验损失来选择函数，具体形式为

\hat{h} = \arg\min_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^{n} L(y_i, h(x_i))

这个公式表达的是：遍历候选函数族中的所有函数，计算每个函数在训练数据上的平均损失，选择损失最小的那个函数作为我们学到的模型。

2.1.2 统计建模视角

从统计学的角度看，我们需要将数据看作随机变量。每一个数据点 (X_i, Y_i) 都是从某个联合分布 \mathbb{P}^{X,Y} 中独立同分布采样得到的。这里用大写字母表示随机变量，强调数据本身具有随机性。我们将整个数据集记为 D = \{(X_1, Y_1), \ldots, (X_n, Y_n)\}，这个数据集本身也是随机的。关键的一点是：我们学到的预测函数 \hat{h} 依赖于训练数据，因此应该写成 \hat{h}(x; D) 的形式，这表明不同的训练数据会产生不同的预测函数。

2.2 偏差-方差权衡

2.2.1 二次损失下的预测误差

我们首先需要回顾一个重要结论：在二次损失函数下，最优的预测函数是条件期望，即

h^*(x) = m(x) \stackrel{\text{def}}{=} \mathbb{E}[Y \mid X = x]

这个函数 m(x) 代表了给定输入 x 时，输出 Y 的期望值，它是理论上能达到的最好预测。现在考虑一个新的查询点 x \in \mathcal{X}，我们想知道用学到的函数 \hat{h}(x) 进行预测时会产生多大的误差。给定训练数据 D，预测误差可以写成

\mathbb{E}\left[(Y - \hat{h}(x))^2 \mid X = x, D\right]

这个期望是对 Y 的随机性求平均，而 X 和 D 是给定的。接下来我们要把这个误差展开。核心技巧是加入并减去真实的条件期望 m(x)：

\mathbb{E}\left[(Y - \hat{h}(x))^2 \mid X = x, D\right] = \mathbb{E}\left[(Y - m(x) + m(x) - \hat{h}(x))^2 \mid X = x, D\right]

展开这个平方项，得到三项：(Y - m(x))^2、2(Y - m(x))(m(x) - \hat{h}(x)) 和 (m(x) - \hat{h}(x))^2。对第一项求期望得到 \text{Var}[Y \mid X = x]，这是 Y 在给定 x 时的固有波动，无论我们的模型多好都无法消除。对第二项求期望，由于 \mathbb{E}[Y - m(x) \mid X = x] = 0，而 m(x) - \hat{h}(x) 在给定 D 时是确定的，所以这一项为 0。第三项 (m(x) - \hat{h}(x))^2 在给定 D 时也是确定的，求期望后保持不变。最终得到

\mathbb{E}\left[(Y - \hat{h}(x))^2 \mid X = x, D\right] = \left(\hat{h}(x) - m(x)\right)^2 + \text{Var}[Y \mid X = x]

这告诉我们：预测误差由两部分组成，一部分是我们的预测函数与真实条件期望之间的差距的平方，另一部分是数据本身的噪声。

2.2.2 期望预测误差与偏差-方差分解

上面的分析是针对固定的训练集 D 进行的。但在实践中，训练集本身是随机的。如果我们重新采样得到不同的训练集，就会学到不同的 \hat{h}。因此我们需要对 D 再取一次期望，得到期望预测误差。对之前得到的公式关于 D 求期望：

\mathbb{E}\left[(Y - \hat{h}(x; D))^2 \mid X = x\right] = \mathbb{E}\left[\left(\hat{h}(x; D) - m(x)\right)^2\right] + \text{Var}[Y \mid X = x]

现在关键是处理第一项。我们再次使用加减同一项的技巧，加入并减去 \mathbb{E}[\hat{h}(x; D)]，即所有可能训练集下学到的预测函数的平均：

\mathbb{E}\left[\left(\hat{h}(x; D) - m(x)\right)^2\right] = \mathbb{E}\left[\left(\hat{h}(x; D) - \mathbb{E}[\hat{h}(x; D)] + \mathbb{E}[\hat{h}(x; D)] - m(x)\right)^2\right]

展开这个平方，同样会得到三项。其中交叉项的期望为零，因为 \mathbb{E}[\hat{h}(x; D) - \mathbb{E}[\hat{h}(x; D)]] = 0。剩下的两项分别是：\mathbb{E}\left[\left(\hat{h}(x; D) - \mathbb{E}[\hat{h}(x; D)]\right)^2\right]，这正是 \hat{h}(x; D) 的方差，记为 \text{Var}[\hat{h}(x; D)]；以及 \left(\mathbb{E}[\hat{h}(x; D)] - m(x)\right)^2，这是平均预测函数与真实函数的差距，其平方称为偏差的平方。最终得到著名的偏差-方差分解：

\mathbb{E}\left[(Y - \hat{h}(x; D))^2 \mid X = x\right] = \underbrace{\left(\mathbb{E}[\hat{h}(x; D)] - m(x)\right)^2}_{\text{bias}^2} + \underbrace{\text{Var}[\hat{h}(x; D)]}_{\text{variance}} + \underbrace{\text{Var}[Y \mid X = x]}_{\text{irreducible error}}

这个分解揭示了预测误差的三个来源。偏差衡量的是：当我们用一个相对简单的模型去逼近复杂的真实关系时，即使平均来看，这个模型也无法完美拟合真实函数，这是模型表达能力不足导致的系统性误差。方差衡量的是：由于训练数据的随机性，不同的训练集会导致学到的模型有所不同，这是模型对训练数据过于敏感导致的不稳定性。不可约误差则是数据本身的噪声，无论模型多么复杂都无法消除。

2.2.3 偏差-方差权衡的本质

要最小化预测误差，我们需要同时控制偏差的平方和方差，但这两者通常是矛盾的。这就是偏差-方差权衡的核心：如果我们选择非常简单的模型（比如低次多项式），这个模型可能无法捕捉数据中的复杂模式，导致高偏差；但另一方面，简单模型对训练数据的依赖较小，不同训练集学到的模型差别不大，因此方差较低。反之，如果我们选择非常复杂的模型（比如高次多项式），模型有能力拟合各种复杂关系，偏差会很低；但这样的模型会对训练数据中的每个细节（包括噪声）都过度拟合，导致高方差。

通过两个极端例子可以清楚地看到这一点。第一个例子：如果我们的预测函数始终输出 \hat{h}(x; D) = 0，不管训练数据是什么，预测都是零。这个模型的方差为零，因为它完全不依赖于训练数据，但偏差非常高，因为它忽略了所有输入信息。第二个例子：对于确定性设计（所有可能的训练集包含相同的 x 值，只是 y 值不同），如果查询点 x 恰好在训练集中，比如 x = x_i，我们直接用这个点对应的观测值 Y_i 作为预测，即 \hat{h}(x_i; D) = Y_i。这个模型是无偏的，因为 \mathbb{E}[Y_i \mid X = x_i] = m(x_i)，但方差很高，等于 \text{Var}[Y_i \mid X = x_i]，因为不同训练集中这个点的 y 值可能差别很大。

2.3 线性回归中的偏差-方差分析

2.3.1 线性回归的设定

现在我们通过线性回归这个具体例子来深入理解偏差-方差权衡。假设数据的生成过程为 Y_i = x_i^{\top} \beta^0 + \varepsilon_i，用矩阵形式可以写成 Y = X\beta^0 + \varepsilon。这里 x_i 是第 i 个样本的特征向量，\beta^0 是真实的参数向量，\varepsilon_i 是噪声项。我们采用确定性设计，意味着所有可能的训练集中，输入 x_1, \ldots, x_n 是固定的，只有输出 y_1, \ldots, y_n 因为噪声而变化。噪声项满足三个条件：均值为零（中心化）、彼此不相关、方差恒定为 \sigma^2（同方差性）。

我们考虑的线性回归模型形式为

h(\tilde{x}) = \tilde{x}^{(0)}\beta_0 + \ldots + \tilde{x}^{(q)}\beta_q = \tilde{x}^{\top}\beta

这里 \tilde{x} 是从原始特征 x 衍生出来的特征向量，比如 \tilde{x}^{(j)} = h_j(x) 可能是 x 的多项式项或其他变换。关键是要理解：这里的 \tilde{x} 是我们构造的特征空间，它决定了模型的复杂度。普通最小二乘估计量为

\hat{\beta}^{\text{OLS}} = \left(\tilde{X}^{\top} \tilde{X}\right)^{-1} \tilde{X}^{\top} Y

这个公式的推导来自于最小化平方损失，通过对 \beta 求导并令导数为零得到。这个估计量具有两个重要性质：它的期望值为 \mathbb{E}[\hat{\beta}^{\text{OLS}}] = \left(\tilde{X}^{\top} \tilde{X}\right)^{-1} \tilde{X}^{\top} X\beta^0，这里用到了 \mathbb{E}[Y] = X\beta^0；它的方差为 \text{Var}[\hat{\beta}^{\text{OLS}}] = \sigma^2 \left(\tilde{X}^{\top} \tilde{X}\right)^{-1}，这是因为 Y 的随机性完全来自噪声项 \varepsilon，其方差为 \sigma^2 I。

2.3.2 设计点上的平均预测误差

现在我们计算在所有训练数据点上的平均期望预测误差。对于每个训练点 x_i，我们想知道用学到的模型 \hat{h}(X) 预测时会产生多大的误差。这个平均误差为

\frac{1}{n}\sum_{i=1}^{n} \mathbb{E}\left[\left(Y - \hat{h}(X)\right)^2 \mid X = x_i\right]

由于我们用的是线性模型 \hat{h}(X) = \tilde{X}\hat{\beta}^{\text{OLS}}，而真实数据生成过程是 Y = X\beta^0 + \varepsilon，预测误差可以写成 Y - \hat{h}(X) = X\beta^0 + \varepsilon - \tilde{X}\hat{\beta}^{\text{OLS}}。将 \hat{\beta}^{\text{OLS}} = \left(\tilde{X}^{\top} \tilde{X}\right)^{-1} \tilde{X}^{\top} Y 代入，得到

Y - \hat{h}(X) = X\beta^0 + \varepsilon - \tilde{X}\left(\tilde{X}^{\top} \tilde{X}\right)^{-1} \tilde{X}^{\top} Y

注意到 \tilde{P} = \tilde{X}\left(\tilde{X}^{\top} \tilde{X}\right)^{-1} \tilde{X}^{\top} 是投影矩阵，它将任意向量投影到 \tilde{X} 的列空间上。因此 \tilde{X}\hat{\beta}^{\text{OLS}} = \tilde{P}Y 是 Y 在这个空间上的投影。误差向量可以写成

Y - \hat{h}(X) = X\beta^0 + \varepsilon - \tilde{P}(X\beta^0 + \varepsilon) = (I_n - \tilde{P})X\beta^0 + (I_n - \tilde{P})\varepsilon

现在计算这个误差的平方范数的期望。展开得到

\mathbb{E}\left[\left\|X\beta^0 + \varepsilon - \tilde{X}\hat{\beta}^{\text{OLS}}\right\|^2\right]

由于 (I_n - \tilde{P}) 是幂等矩阵且对称，我们可以把平方范数写成

\left\|(I_n - \tilde{P})X\beta^0\right\|^2 + \left\|(I_n - \tilde{P})\varepsilon\right\|^2 + 2\varepsilon^{\top}(I_n - \tilde{P})X\beta^0

对期望值求值时，交叉项消失因为 \mathbb{E}[\varepsilon] = 0。对于第二项，利用 \mathbb{E}[\varepsilon^{\top}A\varepsilon] = \sigma^2 \text{tr}(A) 这个性质，得到

\mathbb{E}\left[\left\|(I_n - \tilde{P})\varepsilon\right\|^2\right] = \sigma^2 \text{tr}(I_n - \tilde{P}) = \sigma^2(n - q)

这里 q 是 \tilde{X} 的列数，即特征的个数。将所有项组合起来，得到

\frac{1}{n}\sum_{i=1}^{n} \mathbb{E}\left[\left(Y - \hat{h}(X)\right)^2 \mid X = x_i\right] = \frac{1}{n}\left\|(I_n - \tilde{P})X\beta^{(0)}\right\|^2 + \frac{q}{n}\sigma^2 + \sigma^2

第一项 \frac{1}{n}\left\|(I_n - \tilde{P})X\beta^{(0)}\right\|^2 是偏差平方的总和。它衡量的是：真实的响应向量 X\beta^0 与其在特征空间 \tilde{X} 上的投影之间的差距。如果 X\beta^0 完全落在 \tilde{X} 的列空间中，那么投影就是它本身，偏差为零；否则偏差非零。第二项 \frac{q}{n}\sigma^2 是方差的总和，它只依赖于特征的个数 q，而不依赖于特征的具体取值。第三项 \sigma^2 是不可约误差。

2.3.3 偏差和方差的具体表现

从这个结果可以清楚看到偏差-方差权衡的机制。偏差取决于 \tilde{X} 的列空间对 X\beta^{(0)} 的逼近程度。如果我们构造的特征 \tilde{x} 恰好包含了真实模型所需的基函数，使得 X\beta^0 可以被 \tilde{X} 的列张成，那么偏差为零；否则偏差通常不为零。方差则只取决于特征的个数 q。这里揭示了一个核心矛盾：当我们增加特征数量时，比如考虑嵌套模型序列 \mathcal{H}_1 \subset \mathcal{H}_2 \subset \ldots，偏差平方会单调递减，因为更大的特征空间可以更好地逼近真实函数；但方差会单调递增，因为 \frac{q}{n}\sigma^2 中的 q 变大了。不可约误差 \sigma^2 是常数项，与模型选择无关。

2.4 泛化误差与模型评估

2.4.1 泛化误差的定义

前面我们一直在讨论特定查询点或训练点上的预测误差。但模型的整体质量应该如何衡量呢？我们需要考虑所有可能的输入值。泛化误差的定义是：给定一个学到的模型 \hat{h}（它依赖于训练数据 D），在一个新的测试点 (Y, X)（这个点从与训练数据相同的分布中独立采样）上的期望损失，记为

R(\hat{h}) = \mathbb{E}\left[L(Y, \hat{h}(X)) \mid D\right]

这个期望是对新数据点 (X, Y) 求的，给定训练集 D。期望泛化误差则是对训练集 D 也取期望，得到 \mathbb{E}[R(\hat{h})] = \mathbb{E}[L(Y, \hat{h}(X))]。泛化误差是评估拟合模型的目标指标，因为它衡量的是模型在未见数据上的表现。但在实践中，我们无法直接计算泛化误差，因为我们不知道数据的真实分布。我们通常需要估计期望泛化误差。

2.4.2 经验风险的重用问题

一个直观的想法是用经验风险来估计泛化误差。经验风险定义为模型在训练数据上的平均损失：

\hat{R}(\hat{h}) = \frac{1}{n}\sum_{i=1}^{n} L(Y_i, \hat{h}(X_i))

但这里有一个问题：\hat{h} 本身就是通过最小化训练数据上的损失得到的，所以经验风险会系统性地低估真实的泛化误差。为了理解这一点，我们考虑泛化误差在训练设计点上的限制版本，即

\bar{R}(\hat{h}) = \frac{1}{n}\sum_{i=1}^{n} \mathbb{E}\left[L(Y_i, \hat{h}(X_i)) \mid D\right]

这里的期望是对新的响应变量 Y_i 求的，但输入 X_i 与训练数据相同。关键区别是：虽然 X_i 与训练时相同，但 Y_i 和训练时看到的 Y_i 是独立的，都以 X_i 为条件。

在一个重要的命题中，假设数据生成过程为 Y_i = X_i^{\top}\beta^0 + \varepsilon_i，噪声项彼此独立、均值为零、方差为 \sigma^2。对于OLS估计量，可以证明期望经验风险为

\mathbb{E}\left[\hat{R}(\hat{\beta}^{\text{OLS}})\right] = \sigma^2\left(1 - \frac{p+1}{n}\right)

而期望泛化误差（限制在训练设计点上）为

\mathbb{E}\left[\bar{R}(\hat{\beta}^{\text{OLS}})\right] = \sigma^2\left(1 + \frac{p+1}{n}\right)

这里 p+1 是参数的个数（包括截距项）。比较这两个公式，可以看到经验风险比泛化误差小了 \frac{2(p+1)}{n}\sigma^2。这个差距正是因为我们用同一份数据既训练又评估模型造成的。经验风险是泛化误差的有偏估计，当模型复杂度 p 增大时，这个偏差也增大。

2.4.3 过拟合现象

过拟合是机器学习中的核心问题之一，其特征是模型在训练数据上表现极好，但在未见过的数据上表现很差。通过多项式回归的例子可以直观理解这个现象。考虑用不同次数的多项式去拟合数据点。当使用2次多项式时，模型相对简单，拟合曲线比较平滑，虽然不能完美通过所有训练点，但整体趋势合理。随着多项式次数增加到5次和8次，模型开始更好地拟合训练点，曲线开始出现更多波动来逼近这些点。当次数达到11次时，模型几乎完美地通过了所有训练点，但曲线出现了剧烈的振荡，特别是在数据点之间和边界区域。这些剧烈振荡显然不是数据背后真实规律的反映，而是模型过度拟合了训练数据中的噪声。真实函数（虚线）通常是平滑的，而高次多项式为了完美拟合每个训练点（包括噪声），不得不产生不合理的波动。

2.4.4 模型评估的完整图

模型评估图直观展示了偏差-方差权衡随模型复杂度变化的完整过程。横轴是模型复杂度，可以理解为参数个数或模型的自由度。纵轴是预测误差。图中包含两条关键曲线：蓝色曲线代表经验风险 \hat{R}_n，即模型在训练数据上的表现；红色曲线代表测试集误差，即模型在独立测试数据上的真实表现。

在模型复杂度很低时（图的左侧），两条曲线都很高，这是高偏差低方差的区域。模型太简单，无法捕捉数据的真实模式，因此在训练集和测试集上都表现不好。随着复杂度增加，两条曲线都开始下降。蓝色曲线（训练误差）持续单调下降，因为更复杂的模型总能更好地拟合训练数据。但红色曲线（测试误差）在达到某个最优点后开始上升，这个转折点正是偏差和方差达到最佳平衡的位置。继续增加复杂度进入图的右侧，测试误差持续上升进入高方差低偏差区域，而训练误差继续下降甚至接近零。这时训练误差和测试误差之间的差距越来越大，表明模型严重过拟合。每条曲线周围的淡色区域表示不同训练集下的变化范围，可以看到高方差区域的这个范围明显更大。

2.5 交叉验证

2.5.1 训练-测试集划分

前面我们看到经验风险是泛化误差的负偏估计，即它系统性地低估了真实误差。这个偏差随着参数个数 p 增加而增大。因此模型性能必须在未见过的数据上评估才有意义。最基本的方法是将可用数据划分为两个互斥的部分：训练集 D_{\text{train}} 和测试集 D_{\text{test}}。我们用训练集学习模型 \hat{h}(x; D_{\text{train}})，然后在测试集上计算测试误差：

\hat{R}_{\text{test}} = \frac{1}{n_{\text{test}}} \sum_{(X,Y)\in D_{\text{test}}} L(Y, \hat{h}(X; D_{\text{train}}))

这个测试误差 \hat{R}_{\text{test}} 是 R(\hat{h}) 的无偏估计。为什么是无偏的？因为测试数据在训练过程中完全没有被使用过，模型 \hat{h} 对测试集来说就像是一个固定的函数，而测试集是从总体分布中独立采样的，所以测试误差的期望正好等于泛化误差。典型的划分比例是将80%的数据用于训练，20%用于测试，但这个比例可以根据数据量和问题特点调整。

2.5.2 k折交叉验证

训练-测试集划分有一个明显的缺点：我们为了评估而牺牲了一部分数据，这些数据没有被用于训练。当数据量较小时，这个代价可能很大。交叉验证提供了一个更有效利用数据的方案。k折交叉验证的过程是：首先将所有可用数据划分为 k 个大小基本相等的子集 \underline{D}_1, \ldots, \underline{D}_k。然后进行 k 轮训练和评估：在第 i 轮中，用除了 \underline{D}_i 之外的所有数据（即 \underline{D} \setminus \underline{D}_i）训练模型，然后在 \underline{D}_i 上评估，得到这一折的误差。

具体来说，第 i 折的误差是 \frac{1}{\text{card}(\underline{D}_i)} \sum_{(X,Y)\in\underline{D}_i} L(Y, \hat{h}(X; \underline{D}\setminus\underline{D}_i))。最终的交叉验证误差是 k 折误差的平均：

\hat{R}_{\text{CV}} = \frac{1}{k}\sum_{i=1}^{k} \frac{1}{\text{card}(\underline{D}_i)} \sum_{(X,Y)\in\underline{D}_i} L(Y, \hat{h}(X; \underline{D}\setminus\underline{D}_i))

这个公式表达的是：每个数据点恰好被用作验证集一次（在某一折中），被用作训练集 k-1 次（在其他折中）。需要理解的关键点是：\hat{R}_{\text{CV}} 并不是估计用全部数据 \underline{D} 训练的模型的泛化误差，因为在每一折中，训练集大小只有 n(k-1)/k，小于全部数据量 n。不同折使用的训练集也不相同。因此 \hat{R}_{\text{CV}} 实际上是大小为 n(k-1)/k 的训练集的期望泛化误差的无偏估计。

一个极端情况是留一法交叉验证（leave-one-out），即令 k = n。这时每个子集只包含一个样本，每次用 n-1 个样本训练，在剩下的那一个样本上测试。虽然这种方法最大化了训练集大小，但计算代价很高，需要训练 n 次模型。在实践中，常用的选择是 k = 5 或 k = 10，这在计算效率和估计质量之间取得了较好的平衡。

2.6 正则化回归

2.6.1 普通最小二乘法的局限性

现在我们进入正则化回归部分。在讨论具体方法之前，需要理解为什么普通最小二乘法（OLS）在某些情况下会失效。回顾一下，设计矩阵 \underline{X} 的大小是样本数乘以变量数，即 n \times (p+1)，这里 p+1 包括了 p 个特征加上截距项。

从预测准确性的角度看，之前讨论的偏差-方差权衡表明：当我们使用大量解释变量运行OLS时，虽然偏差平方会减小，但方差会急剧增加。这导致模型在训练数据上表现很好，但在新数据上表现糟糕。从数值计算的角度看，OLS估计量依赖于矩阵 \underline{X}^{\top}\underline{X} 的逆。当这个矩阵奇异或者病态（条件数很大）时，计算会变得不稳定或根本无法进行。这种情况典型地发生在两种场景下：第一种是变量个数大于样本数，即 p + 1 > n，此时 \underline{X}^{\top}\underline{X} 必然奇异，因为秩最多为 n；第二种是解释变量之间存在强相关性，即使 p+1 \leq n，如果某些变量几乎是其他变量的线性组合，矩阵也会接近奇异。

高维数据的实例

一个具体的例子来自阿尔茨海默病诊断研究。数据表展示了通过在线手写测试收集的 p = 451 个特征，用于描述 n = 174 个人的手写特征，其中一些人患有阿尔茨海默病。这是一个典型的高维问题，特征数远大于样本数。在医学领域，这种情况非常常见：医学影像可能产生数千个特征（每个像素或体素），基因表达数据可能包含上万个基因，但受试者数量通常只有几十到几百人，因为收集医学数据成本高昂且耗时。在这种 p > n 的情况下，普通最小二乘法完全失效，因为系统是欠定的，存在无穷多组参数都能完美拟合训练数据。

2.6.2 正则化回归的基本思想

正则化核心思想是在经验风险中加入一个惩罚项：

\hat{\beta}^{\text{pen}} = \arg\min_{\beta} \underbrace{\|y - X\beta\|^2}_{\text{data "fidelity"}} + \underbrace{\lambda}_{\text{hyperparameter}} \underbrace{\text{pen}(\beta)}_{\text{regularization}}

这个目标函数由两部分组成。第一部分 \|y - X\beta\|^2 是数据保真项，它衡量模型对训练数据的拟合程度，这与OLS的目标相同。第二部分 \lambda \text{pen}(\beta) 是正则化项，其中 \text{pen}(\beta) 是对参数 \beta 的惩罚函数，通常设计成当参数值较大时惩罚也较大；\lambda 是超参数，控制正则化的强度。惩罚函数的典型目标是将 \beta 推向零，即鼓励稀疏或小幅度的解。

正则化带来的好处: 首先，即使在 p > n 的情况下，通过加入惩罚项，优化问题可以有唯一解，解决了数值计算的问题。其次，正则化可以避免过拟合，因为它限制了模型的复杂度。当候选函数族很大时（比如特征数很多），正则化通过惩罚复杂的模型，在偏差和方差之间找到更好的平衡点。第三，正则化后的模型通常更容易解释，因为不重要的特征对应的系数会被压缩到接近零，甚至完全为零，从而实现了自动的特征选择。第四，惩罚项可以被解释为融入了先验信息，这与贝叶斯方法有自然的联系。

2.6.3 贝叶斯视角的解释

正则化回归可以从贝叶斯统计的角度给出优雅的解释。假设数据生成过程为 Y_i = X_i^{\top}\beta + \varepsilon_i，其中噪声 \varepsilon_i 独立同分布服从 \mathcal{N}(0, \sigma^2)。在贝叶斯框架下，我们对参数 \beta 指定一个先验分布 \pi(\beta)，其形式为

\pi(\beta) \propto \exp(-\gamma\text{pen}(\beta))

这个先验分布的对数正比于负的惩罚函数，\gamma 控制先验的集中程度。先验分布编码了我们对参数的预期：如果惩罚函数在 \beta = 0 附近较小而在远离零处较大，那么先验就表达了我们相信大多数参数应该接近零。

根据贝叶斯定理，给定数据后，参数的后验分布为

\pi(\beta \mid X, y) = \frac{f(\beta, X, y)}{f(X, y)} \propto f(X, y \mid \beta)\pi(\beta) \propto \prod_{i=1}^{n} f(y_i \mid x_i, \beta)\pi(\beta)

由于噪声是高斯分布，似然函数为 f(y_i \mid x_i, \beta) \propto \exp\left(-\frac{(y_i - x_i^{\top}\beta)^2}{2\sigma^2}\right)。将似然和先验相乘，后验分布正比于

\exp\left(\sum_{i=1}^{n} -\frac{(y_i - x_i^{\top}\beta)^2}{2\sigma^2} - \gamma\text{pen}(\beta)\right)

取对数，最大化后验分布等价于最小化

\arg\min_{\beta} \frac{1}{2\sigma^2}\|y - X\beta\|^2 + \gamma\text{pen}(\beta) = \arg\min_{\beta} \|y - X\beta\|^2 + \underbrace{2\sigma^2\gamma}_{\lambda}\text{pen}(\beta)

这正是正则化回归的目标函数。通过令 \lambda = 2\sigma^2\gamma，我们看到正则化估计量等价于贝叶斯框架下的最大后验估计（MAP）。这个联系揭示了正则化的本质：惩罚项对应于参数的先验分布，超参数 \lambda 控制先验信息与数据信息的相对权重。当 \lambda 很大时，先验占主导，参数被强烈地拉向零；当 \lambda 很小时，数据占主导，估计接近OLS。

2.6.4 岭回归

岭回归是最经典的正则化方法之一。它选择的惩罚函数是参数向量的平方L2范数：

\text{pen}(\beta) = \|\beta\|^2 = \sum_{j=1}^{p} \beta_j^2

这个惩罚函数对所有参数的平方求和，因此当参数的绝对值较大时会受到更严重的惩罚。将这个惩罚项加入到OLS的目标函数中，得到岭回归的优化问题：

\hat{\beta}^{\text{Ridge}} = \arg\min_{\beta} \|y - X\beta\|^2 + \lambda\|\beta\|^2

从贝叶斯角度看，L2惩罚对应于高斯先验分布。具体来说，如果我们为参数选择先验 \beta \sim \mathcal{N}(0, \tau^2 I_{p+1})，即每个参数独立地服从均值为零、方差为 \tau^2 的正态分布，那么最大后验估计正好等价于岭回归，其中超参数之间的关系为 \lambda = 2\sigma^2/\tau^2。

岭回归的一个重要优势是存在闭式解。通过对目标函数关于 \beta 求导并令其为零，可以直接得到：

\hat{\beta}^{\text{Ridge}} = \left(X^{\top}X + \lambda I_{p+1}\right)^{-1} X^{\top}y

这个公式与OLS的解 (X^{\top}X)^{-1}X^{\top}y 非常相似，唯一的区别是在矩阵 X^{\top}X 上加了 \lambda I_{p+1}。这个修改带来了关键的数值改进：当 \lambda 增大时，矩阵 X^{\top}X + \lambda I_{p+1} 的条件数会改善。条件数衡量矩阵的病态程度，条件数越小，矩阵求逆越稳定。通过在对角线上加入正的 \lambda，我们增加了矩阵的特征值，使其远离奇异。这就是为什么即使在 X^{\top}X 奇异或接近奇异的情况下，岭回归仍然能够计算。

观察两个极端情况可以帮助理解 \lambda 的作用。当 \lambda = 0 时，没有正则化，\hat{\beta}^{\text{Ridge}} = \hat{\beta}^{\text{OLS}}，我们回到普通最小二乘。当 \lambda \to +\infty 时，惩罚项占据主导地位，为了最小化目标函数，参数必须接近零，因此 \hat{\beta}^{\text{Ridge}} \to 0。

岭回归系数路径

通过一个实际例子可以直观理解 \lambda 如何影响岭回归的系数。图中展示了七个不同变量（MOCAGE、TEMPE、SRMH2O、LNO2、LNO、WindMOD、WindANG）的系数随 \lambda 变化的轨迹，横轴是 \lambda 的对数尺度，纵轴是标准化后的系数值。当 \lambda 很小（图的左侧）时，岭回归接近OLS，不同变量的系数保持其原始值，有些系数绝对值较大。随着 \lambda 增加，所有系数的绝对值都开始平滑地减小，被正则化项逐渐压缩向零。重要的是观察到岭回归的系数变化是连续且光滑的，每条曲线都逐渐趋向零但永远不会精确为零。不同变量的系数以不同的速率收缩，这取决于它们在数据中的重要性：对预测更重要的变量的系数收缩得更慢，而不太重要的变量更快地接近零。

2.6.5 LASSO回归

LASSO（最小绝对收缩和选择算子）是另一种重要的正则化方法，它使用L1范数作为惩罚函数：

\text{pen}(\beta) = \|\beta\|_1 = \sum_{j=0}^{p} |\beta_j|

L1惩罚对参数的绝对值求和，而不是平方。这看似微小的差别导致了本质上不同的性质。LASSO的优化问题为：

\hat{\beta}^{\text{LASSO}} = \arg\min_{\beta} \|y - X\beta\|^2 + \lambda\|\beta\|_1

从贝叶斯角度，L1惩罚对应于Laplace分布（双指数分布）先验。如果为 \beta 的每个分量选择独立的Laplace先验，最大后验估计就等价于LASSO。与岭回归不同，LASSO没有闭式解，除了某些特殊情况。这是因为L1范数在零点不可微，导致优化问题更加复杂。实践中通常使用迭代算法求解，常用的方法包括坐标下降法和最小角回归。

2.6.6 正则化回归的约束形式

正则化回归可以用另一种等价的形式表述，这种表述从几何上更容易理解。首先注意到一个恒等式：\|y - X\beta\|^2 = \|X(\beta - \hat{\beta}^{\text{OLS}})\|^2 + c，其中 c 是一个常数。这意味着最小化 \|y - X\beta\|^2 等价于最小化 \|X(\beta - \hat{\beta}^{\text{OLS}})\|^2，即寻找离OLS解最近的点。利用这个关系，LASSO可以重写为：

\hat{\beta}^{\text{LASSO}} = \arg\min_{\beta} \|X(\beta - \hat{\beta}^{\text{OLS}})\|^2 + \lambda\text{pen}\beta

更进一步，在惩罚函数满足一定正则性条件下，可以证明存在某个常数 c_\lambda \in \mathbb{R}^+ 使得：

\hat{\beta}^{\text{pen}} = \arg\min_{\text{pen}(\beta) \leq c_\lambda} \|X(\beta - \hat{\beta}^{\text{OLS}})\|^2

这个形式将问题表述为：在满足约束 \text{pen}(\beta) \leq c_\lambda 的参数空间中，寻找距离OLS解最近的点。这里 \lambda 扮演了拉格朗日乘数的角色，它将约束优化问题转化为无约束的惩罚优化问题。对于岭回归和LASSO，约束形式分别为：

\hat{\beta}^{\text{Ridge}} = \arg\min_{\|\beta\|^2 \leq c_\lambda^{\text{Ridge}}} \|X(\beta - \hat{\beta}^{\text{OLS}})\|^2

\hat{\beta}^{\text{LASSO}} = \arg\min_{\|\beta\|_1 \leq c_\lambda^{\text{LASSO}}} \|X(\beta - \hat{\beta}^{\text{OLS}})\|^2

2.6.7 岭回归与LASSO的几何对比

约束形式揭示了岭回归和LASSO在几何上的本质差异。考虑只有两个参数 \beta_1 和 \beta_2 的简单情况。岭回归的约束 \beta_1^2 + \beta_2^2 \leq c_\lambda^{\text{Ridge}} 定义了一个圆形区域，而LASSO的约束 |\beta_1| + |\beta_2| \leq c_\lambda^{\text{LASSO}} 定义了一个菱形区域。OLS的目标函数 \|X(\beta - \hat{\beta}^{\text{OLS}})\|^2 的等高线是以 \hat{\beta}^{\text{OLS}} 为中心的椭圆。正则化的解是椭圆等高线与约束区域首次相切的点。

对于岭回归，圆形约束区域是光滑的，椭圆通常在区域内部的某个点与圆相切，此时两个参数都非零。但对于LASSO，菱形的顶点位于坐标轴上，比如点 (\beta_1, 0) 或 (0, \beta_2)。当椭圆首次与菱形相切时，很容易恰好触碰到某个顶点，此时对应的解中某些参数精确为零。这就是LASSO产生稀疏解的几何直觉：L1约束的"尖角"使得解更容易落在坐标轴上，从而实现自动的变量选择。

LASSO系数路径图进一步验证了这个性质。与岭回归不同，LASSO的系数轨迹不仅收缩，而且会在某个 \lambda 值处精确变为零并保持为零。不同变量的系数在不同的 \lambda 值处被"淘汰"，实现了逐步的变量选择。

2.6.8 实践中的技术细节

在实际应用正则化回归时，有几个重要的技术要点。首先，截距项 \beta_0 通常不被惩罚。惩罚函数只作用于斜率参数，即岭回归使用 \text{pen}(\beta) = \sum_{j=1}^{p} \beta_j^2，LASSO使用 \text{pen}(\beta) = \sum_{j=1}^{p} |\beta_j|。这是因为截距只是调整预测的整体水平，不影响模型的复杂度。为了明确这一点，我们引入记号 \beta_{\sim 0} = (\beta_1, \ldots, \beta_p)^{\top} 表示不包含截距的参数向量，X_{\sim 0} 表示设计矩阵中不包含截距列（全1列）的部分。

在这种设定下，我们可以先对 \beta_0 求OLS解。最小化 \|y - 1\beta_0 - X_{\sim 0}\beta_{\sim 0}\|^2 + \lambda\text{pen}(\beta_{\sim 0}) 关于 \beta_0，由于惩罚项不涉及 \beta_0，对 \beta_0 求导得到：

\hat{\beta}_0 = \frac{1}{n}1^{\top}(y - X_{\sim 0}\beta_{\sim 0}) = \bar{y} - \bar{X}_{\sim 0}\beta_{\sim 0}

其中 \bar{y} 是响应变量的均值，\bar{X}_{\sim 0} 是特征矩阵每列的均值向量。将这个表达式代回原问题，正则化问题可以重写为：

\hat{\beta}^{\text{pen}}_{\sim 0} = \arg\min_{\beta_{\sim 0}} \left\|y - 1(\bar{y} - \bar{X}_{\sim 0}\beta_{\sim 0}) - X\beta_{\sim 0}\right\|^2 + \lambda\text{pen}(\beta_{\sim 0})

化简后得到：

\hat{\beta}^{\text{pen}}_{\sim 0} = \arg\min_{\beta_{\sim 0}} \|y^c - X^c_{\sim 0}\beta_{\sim 0}\|^2 + \lambda\text{pen}(\beta_{\sim 0})

这里 y^c 和 X^c_{\sim 0} 分别是 y 和 X_{\sim 0} 的中心化版本，即减去各自的均值。这表明在不惩罚截距时，可以先对数据进行中心化，然后只对中心化后的数据进行正则化回归。

另一个重要问题是变量的尺度。不同的解释变量通常具有不同的测量单位和数量级。假设我们将第 j 个解释变量乘以某个因子 a > 1，即用 a\tilde{x}^{(j)} 替换 \tilde{x}^{(j)}。为了保持模型预测不变，对应的系数必须调整为 \beta_j/a。但在惩罚项中，平方惩罚变为 (\beta_j/a)^2 = \beta_j^2/a^2，L1惩罚变为 |\beta_j/a| = |\beta_j|/a。这意味着重新缩放后，系数 \beta_j 会被"更多倍数"地惩罚。不同单位的变量会受到不同程度的惩罚，这是不公平的，因为惩罚的强度应该反映变量的重要性而不是测量单位的选择。

为了消除这种单位依赖性，标准做法是在拟合模型之前对每个解释变量进行标准化。具体来说，对第 j 个中心化后的特征列，计算其标准化版本：

\tilde{x}^{(j)c} = \frac{x^{(j)c}}{\|x^{(j)c}\|}, \quad \forall j = 1, \ldots, p

这里 \|\cdot\| 是向量的L2范数。标准化后，每个特征列的范数都为1，处于相同的尺度上。对数据进行中心化和缩放的整个过程称为数据标准化。标准化确保了正则化对所有变量一视同仁，惩罚的强度只取决于系数的大小而不受原始变量单位的影响。

2.7 模型选择

2.7.1 模型选择的两个核心问题

前面我们讨论了如何评估单个模型以及如何通过正则化改进模型。现在面临的核心问题是：在众多候选模型中，如何系统性地选择最优的那个？模型选择涉及两个层面的问题。

问题一：选择好的函数族

第一个问题是如何选择合适的函数族 \mathcal{H}，特别是确定其大小或复杂度 k_J。这个问题在两种典型场景下出现。

第一种场景是变量选择。假设我们有 p 个可用的解释变量，但不确定应该使用哪些变量。如果选择一个子集 J \subset \{1, \ldots, p\}，预测函数的形式为：

h(x) = \beta_0 + \sum_{j\in J} \beta_j x^{(j)}

这个函数族 \mathcal{H}_J 包含 k_J = \text{card}(J) + 1 个参数，即选中的变量数加上截距。问题的核心是：应该选择哪些变量进入模型？这决定了集合 J，进而决定了函数族的大小 k_J。

第二种场景是基函数展开的截断。假设我们用一组基函数 \{\psi_0(x), \psi_1(x), \psi_2(x), \ldots\} 来表示预测函数，比如多项式基或傅里叶基。如果我们在第 J 阶截断，预测函数为：

h(x) = \sum_{k=0}^{J} \beta_j \psi_j(x)

这个函数族 \mathcal{H}_J 包含 k_J = J + 1 个参数。问题变成：应该在哪个阶数截断？选择过低的 J 会导致欠拟合，选择过高的 J 会导致过拟合。两种场景的共同点是：我们需要确定函数族的大小，即参数的个数，这直接影响模型在偏差-方差权衡中的位置。

问题二:选择超参数

大多数现代机器学习方法都涉及超参数的调优。超参数是在训练之前需要指定的参数，它们控制学习算法的行为但不是模型本身的参数。对于岭回归和LASSO，核心的超参数就是正则化参数 \lambda。估计量的形式为 \hat{\beta} = \arg\min \hat{R}^{\text{pen}}_{n,\lambda}，其中惩罚化的经验风险为：

\hat{R}^{\text{pen}}_{n,\lambda}(\beta) = \hat{R}_n(\beta) + \lambda\sum_j |\beta_j|^q, \quad q \in \{1, 2\}

这里 q=2 对应岭回归，q=1 对应LASSO。不同的 \lambda 值会产生完全不同的模型：\lambda 过小导致过拟合，\lambda 过大导致欠拟合。问题是：如何为这些超参数选择合适的数值？

2.7.2 验证集方法

解决这两个问题的关键思想是引入验证集。基本策略是将可用数据分成三个互斥的部分，而不是之前的两部分。训练集用于给定函数族和超参数后构建模型 \hat{h}，这是模型学习的阶段。验证集用于选择函数族 \mathcal{H}、超参数 \lambda 等，通过在验证集上比较不同配置的性能来做出选择。测试集只在最终使用，用于评估选定模型的泛化误差，给出对模型真实性能的无偏估计。

最简单的验证方法称为留出验证或简单验证。将数据按比例划分为三部分，典型的划分是训练集60%、验证集20%、测试集20%。具体流程是：首先在训练集上用不同的 \mathcal{H} 或 \lambda 训练多个模型；然后在验证集上评估每个模型的性能，选择验证误差最小的配置；最后在测试集上评估选定模型，报告其泛化误差。这种方法简单直接，但当数据量有限时，将20%的数据用于验证显得奢侈。

2.7.3 交叉验证用于超参数选择

为了更有效地利用数据，可以将交叉验证技术应用于超参数选择。假设我们已经将数据分为训练+验证集合（比如80%）和测试集（比如20%）。现在的问题是如何在训练+验证集合中选择最优超参数。我们将训练+验证集合进一步划分为 k 折，比如 k=5，每折占20%。

具体流程分为两个阶段。第一阶段是超参数选择：对于每个候选的超参数值（或函数族配置），执行 k 折交叉验证，计算交叉验证误差 \hat{R}_{\text{CV}}；比较所有候选配置的交叉验证误差，选择误差最小的超参数。第二阶段是最终训练和评估：使用选定的最优超参数，在合并的训练集和验证集（即最初划分的80%数据）上重新训练模型，得到最终模型 \hat{h}；在之前未使用过的测试集上评估这个最终模型，得到泛化误差的无偏估计。

这个两阶段策略的关键在于：交叉验证只用于选择超参数，不用于最终模型训练；测试集完全独立，只在最后使用一次，确保泛化误差估计的无偏性。

2.8 本章小结

本讲内容涵盖了机器学习中模型评估、选择和正则化的完整框架。在模型评估部分，我们理解了偏差-方差权衡这一核心矛盾，学习了如何定义和估计泛化误差与期望泛化误差，掌握了训练-测试集划分和交叉验证这两种实用的评估技术。在正则化回归部分，我们引入了惩罚函数的概念及其贝叶斯解释，详细研究了岭回归和LASSO这两种重要方法，理解了它们在处理高维数据和实现变量选择方面的不同特点。在模型选择部分，我们学习了如何通过留出验证和交叉验证来系统性地选择函数族和调优超参数。这些方法共同构成了构建和评估机器学习模型的完整工具箱。

第三章分类与核方法导论

3.1 分类问题的基本框架

3.1.1 数据与空间设定

分类问题从数据开始。我们有 n 个训练样本 (X_1, Y_1), \ldots, (X_n, Y_n)，这些样本是独立同分布地从联合分布 \mathbb{P}^{X,Y} 中抽取出来的。这里的独立同分布（i.i.d.）假设意味着每个样本的产生过程相同且互不影响，这是统计学习理论的基础假设。为什么需要这个假设？因为我们希望从有限的训练数据中学到的模式能够推广到未来的新数据上。如果训练数据和未来数据遵循不同的分布，那么学到的规律就失去了意义。

特征空间 \mathcal{X} \subset \mathbb{R}^p 表示每个输入是 p 维实数向量，这里 p 是特征的数量。比如识别手写数字时，如果图像是 28 \times 28 像素，那么 p = 784。标签空间 \mathcal{Y} = \{0, 1, \ldots, C-1\} 包含 C 个离散的类别。与回归问题的连续输出空间 \mathcal{Y} \subset \mathbb{R} 形成对比，分类的输出是离散的。本章主要讨论二分类问题，即 C = 2，\mathcal{Y} = \{0, 1\}。

我们的目标是构建一个预测函数 h: x \mapsto \{0, 1\}，它接受一个特征向量 x 作为输入，输出一个类别标签。这个映射关系就是我们要从数据中学习的分类器。

3.1.2 分类的几何直观

在二维特征空间（p = 2）中，可以将数据点画在平面上，每个点的颜色代表其类别。通常会观察到同类的点倾向于聚集在一起，形成一定的聚类结构。这种聚类现象是分类问题可解的基础——如果不同类别的数据完全随机混合，没有任何模式，那么分类就不可能实现。

然而，两个类别之间通常存在重叠区域，在这些区域中两类数据点混杂在一起。这种重叠意味着即使是理论上的最优分类器也无法达到100%的准确率，总会存在一定的贝叶斯误差。这个误差反映了问题本身的内在不确定性，而不是模型的缺陷。

决策边界是将特征空间划分成不同预测区域的边界。对于二分类，决策边界将空间分成两部分：边界一侧的点被预测为类别0，另一侧被预测为类别1。如果决策边界是直线（或在高维中是超平面），我们称之为线性分类器；如果是曲线（或曲面），则是非线性分类器。

许多实际问题是线性不可分的，意味着不存在一个线性边界能够完美分离两类数据。这时需要非线性分类器，但这引入了模型复杂度的权衡问题。过于简单的模型（如线性模型）可能欠拟合，无法捕捉数据的复杂模式；过于复杂的模型可能过拟合，在训练数据上表现很好但泛化性能差。核方法提供了一种优雅的解决方案：通过将数据映射到高维空间，在高维空间中寻找线性边界，这个线性边界对应于原始空间中的非线性边界。

3.2 硬分类器与软分类器

3.2.1 硬分类器

硬分类器 h: \mathcal{X} \rightarrow \{0, 1\} 直接输出离散的类别标签，给出确定性的二元决策。对于每个输入，它明确地说"这属于类别0"或"这属于类别1"，没有中间状态。

3.2.2 软分类器

软分类器 h: \mathcal{X} \rightarrow [0, 1] 输出一个连续值，通常在0到1之间。这个输出可以理解为分类器对样本属于类别1的置信度或概率估计。比如输出0.8意味着模型认为该样本有80%的可能属于类别1。软分类器提供了比硬分类器更丰富的信息——不仅告诉预测结果，还告诉对这个预测有多大把握。

3.2.3 两者的关联

硬分类器和软分类器通过阈值 \delta \in [0, 1] 建立联系：

x \mapsto \mathbb{1}_{h(x) \geq \delta}

这个映射的含义是：当软分类器的输出 h(x) \geq \delta 时，预测为类别1；否则预测为类别0。最常用的阈值是 \delta = 0.5，这对应于"选择概率更大的类别"。但在实际应用中，阈值可以根据具体需求调整。比如在医疗诊断中，为了减少漏诊（假阴性），可能会使用较低的阈值，宁可多一些误报也要确保不漏掉真正的病例。

软分类器的输出 h(x) 通常被解释为条件概率 \mathbb{P}(Y = 1 \mid X = x)，即给定特征 x 时样本属于类别1的概率。这种概率解释不仅在理论分析中提供了坚实的数学基础，在实际应用中也很有价值，因为它量化了预测的不确定性。

3.3 损失函数

损失函数是衡量预测错误程度的函数，它将预测值与真实值的差异转化为一个数值，这个数值越大表示预测越差。

3.3.1 0/1损失

0/1损失的定义：

L_{0/1}(y, \hat{y}) = \mathbb{1}_{y \neq \hat{y}} = \begin{cases} 1 & \text{if } y \neq \hat{y} \\ 0 & \text{if } y = \hat{y} \end{cases}

当预测正确时（y = \hat{y}），损失为0；当预测错误时（y \neq \hat{y}），损失为1。所有的错误都被同等对待，不管是"差一点就对了"还是"完全错了"。

使用0/1损失时，分类器的期望风险 R(h) = \mathbb{E}[L(Y, h(X))] 正好等于误分类概率 \mathbb{P}(Y \neq h(X)) ，证明两者相等

期望风险（Expected Risk）：

R(h) = \mathbb{E}[L(Y, h(X))]

其中 L 是损失函数，期望是对联合分布 (X, Y) \sim \mathbb{P}^{X,Y} 取的。

误分类概率：

\mathbb{P}(Y \neq h(X))

即预测值不等于真实值的概率。

将0/1损失代入期望风险的定义：

R(h) = \mathbb{E}[L_{0/1}(Y, h(X))] = \mathbb{E}[\mathbb{1}_{Y \neq h(X)}]

现在关键是理解指示函数的期望值。对于任何事件 A，指示函数 \mathbb{1}_A 的期望值等于该事件发生的概率：

\mathbb{E}[\mathbb{1}_A] = 1 \cdot \mathbb{P}(A) + 0 \cdot \mathbb{P}(A^c) = \mathbb{P}(A)

即

\mathbb{E}[\mathbb{1}_A] = \mathbb{P}(A)

应用到我们的情况，令 A = \{Y \neq h(X)\}：

R(h) = \mathbb{E}[\mathbb{1}_{Y \neq h(X)}] = \mathbb{P}(Y \neq h(X))

然而，0/1损失在优化上存在两个严重问题。第一，它是非凸且不连续的函数，这使得基于梯度的优化方法无法使用。第二，它无法区分不同程度的错误，一个输出0.49的软分类器（差一点就正确）和输出0的软分类器（完全错误）在0/1损失下得到相同的惩罚。

3.3.2 对数损失

对数损失（也称为交叉熵损失）定义为：

L(y, \hat{y}) = \begin{cases} -\log(\hat{y}) & \text{if } y = 1 \\ -\log(1 - \hat{y}) & \text{if } y = 0 \end{cases}

这可以统一写成一个表达式：

L(y, \hat{y}) = -y\log(\hat{y}) - (1-y)\log(1-\hat{y})

当 y = 1 时，第二项变为0，只剩第一项 -\log(\hat{y})；当 y = 0 时，第一项变为0，只剩第二项 -\log(1-\hat{y})。

对数损失的关键特性是"越错越罚"：当预测值 \hat{y} 接近真实标签时，损失接近0；当预测值远离真实标签时，损失趋向无穷大。比如当真实标签 y = 1 时，如果预测 \hat{y} = 0.9，损失是 -\log(0.9) \approx 0.105；如果预测 \hat{y} = 0.1，损失是 -\log(0.1) \approx 2.303；如果预测 \hat{y} = 0.01，损失是 -\log(0.01) \approx 4.605。

对数损失是凸函数，这保证了优化问题有全局最优解，不会陷入局部最优。更深层的意义在于，最小化对数损失等价于最大似然估计：如果将 \hat{y} 解释为 \mathbb{P}(Y = 1 \mid X = x)，那么对数损失就是负对数似然，最小化损失就是最大化数据的似然。

3.4 最优分类器

3.4.1 0/1损失下的最优分类器

在0/1损失下，最优硬分类器（也称为贝叶斯分类器）的决策规则是：

h(x) = \begin{cases} 1 & \text{if } \mathbb{P}(Y = 1 \mid X = x) > \frac{1}{2} \\ 0 & \text{if } \mathbb{P}(Y = 1 \mid X = x) < \frac{1}{2} \end{cases}

这个规则的直观含义是选择后验概率更大的类别。为什么这是最优的？考虑在点 x 处的期望损失：

选择1：预测为类别1，即 h(x) = 1

此时的期望损失（条件期望损失）为：

\begin{align} L_1(x) &= \mathbb{E}[L_{0/1}(Y, 1) | X = x] \\ &= \mathbb{P}(Y \neq 1 | X = x) \\ &= \mathbb{P}(Y = 0 | X = x) \end{align}

因为当我们预测为1时，只有当真实标签 Y = 0 时才会出错。

选择2：预测为类别0，即 h(x) = 0

此时的期望损失为：

\begin{align} L_0(x) &= \mathbb{E}[L_{0/1}(Y, 0) | X = x] \\ &= \mathbb{P}(Y \neq 0 | X = x) \\ &= \mathbb{P}(Y = 1 | X = x) \end{align}

因为当我们预测为0时，只有当真实标签 Y = 1 时才会出错。

要最小化期望损失，我们应该选择损失较小的决策：

如果 L_1(x) < L_0(x)，即 \mathbb{P}(Y = 0 | X = x) < \mathbb{P}(Y = 1 | X = x)，则选择 h(x) = 1
如果 L_1(x) > L_0(x)，即 \mathbb{P}(Y = 0 | X = x) > \mathbb{P}(Y = 1 | X = x)，则选择 h(x) = 0

注意到：

\mathbb{P}(Y = 0 | X = x) + \mathbb{P}(Y = 1 | X = x) = 1

因此：

\mathbb{P}(Y = 0 | X = x) < \mathbb{P}(Y = 1 | X = x)

等价于：

\mathbb{P}(Y = 1 | X = x) > \frac{1}{2}

这就得到了贝叶斯分类器的决策规则：

h^*(x) = \begin{cases} 1 & \text{if } \mathbb{P}(Y = 1 | X = x) > \frac{1}{2} \\ 0 & \text{if } \mathbb{P}(Y = 1 | X = x) < \frac{1}{2} \end{cases}

如果预测为1，错误概率是 \mathbb{P}(Y = 0 \mid X = x)；如果预测为0，错误概率是 \mathbb{P}(Y = 1 \mid X = x)。要最小化错误概率，应该选择错误概率较小的决策，即当 \mathbb{P}(Y = 1 \mid X = x) > 0.5 时选择类别1。

即使是这个理论上的最优分类器，其误分类率（称为贝叶斯误差）通常也不为零。贝叶斯误差反映了数据的内在不确定性——即使知道真实的条件概率分布，在某些区域两类的后验概率可能非常接近，任何决策都有较高的错误风险。

3.4.2 对数损失下的最优分类器

在对数损失下，最优软分类器是：

h(x) = \mathbb{P}(Y = 1 \mid X = x)

最优策略就是输出真实的后验概率。这可以通过求解期望损失的最小值来证明：给定 x，期望对数损失是 \mathbb{E}[L(Y, \hat{y}) \mid X = x]，对 \hat{y} 求导并令其为0，可得最优解正是 \hat{y} = \mathbb{P}(Y = 1 \mid X = x)。这解释了为什么我们将软分类器的输出解释为概率——在对数损失下，输出概率是最优策略。

证明: 在对数损失下，最优软分类器是

h^*(x) = \mathbb{P}(Y = 1 | X = x)

对于给定的 x，软分类器输出 \hat{y} \in [0,1]。我们需要找到使条件期望损失最小的 \hat{y}。

对数损失函数为：

L(y, \hat{y}) = -y\log(\hat{y}) - (1-y)\log(1-\hat{y})

在点 x 处的条件期望损失为：

\begin{align} \mathbb{E}[L(Y, \hat{y}) | X = x] &= \sum_{y \in \{0,1\}} L(y, \hat{y}) \cdot \mathbb{P}(Y = y | X = x) \\ &= L(0, \hat{y}) \cdot \mathbb{P}(Y = 0 | X = x) + L(1, \hat{y}) \cdot \mathbb{P}(Y = 1 | X = x) \end{align}

代入对数损失的具体形式：

\begin{align} &= -[0 \cdot \log(\hat{y}) + 1 \cdot \log(1-\hat{y})] \cdot \mathbb{P}(Y = 0 | X = x) -[1 \cdot \log(\hat{y}) + 0 \cdot \log(1-\hat{y})] \cdot \mathbb{P}(Y = 1 | X = x) \\ &= -\log(1-\hat{y}) \cdot \mathbb{P}(Y = 0 | X = x) - \log(\hat{y}) \cdot \mathbb{P}(Y = 1 | X = x) \end{align}

为了找到最小值，对 \hat{y} 求导：

\frac{\partial}{\partial \hat{y}} \mathbb{E}[L(Y, \hat{y}) | X = x] = \frac{\mathbb{P}(Y = 0 | X = x)}{1-\hat{y}} - \frac{\mathbb{P}(Y = 1 | X = x)}{\hat{y}}

令导数为零：

\frac{\mathbb{P}(Y = 0 | X = x)}{1-\hat{y}} - \frac{\mathbb{P}(Y = 1 | X = x)}{\hat{y}} = 0

交叉相乘：

\mathbb{P}(Y = 0 | X = x) \cdot \hat{y} = \mathbb{P}(Y = 1 | X = x) \cdot (1-\hat{y})

展开：

\mathbb{P}(Y = 0 | X = x) \cdot \hat{y} = \mathbb{P}(Y = 1 | X = x) - \mathbb{P}(Y = 1 | X = x) \cdot \hat{y}

移项：

\mathbb{P}(Y = 0 | X = x) \cdot \hat{y} + \mathbb{P}(Y = 1 | X = x) \cdot \hat{y} = \mathbb{P}(Y = 1 | X = x)

提取 \hat{y}：

\hat{y} \cdot [\mathbb{P}(Y = 0 | X = x) + \mathbb{P}(Y = 1 | X = x)] = \mathbb{P}(Y = 1 | X = x)

由于 \mathbb{P}(Y = 0 | X = x) + \mathbb{P}(Y = 1 | X = x) = 1：

\hat{y} = \mathbb{P}(Y = 1 | X = x)

计算二阶导数：

\frac{\partial^2}{\partial \hat{y}^2} \mathbb{E}[L(Y, \hat{y}) | X = x] = \frac{\mathbb{P}(Y = 0 | X = x)}{(1-\hat{y})^2} + \frac{\mathbb{P}(Y = 1 | X = x)}{\hat{y}^2}

由于 \mathbb{P}(Y = 0 | X = x) \geq 0，\mathbb{P}(Y = 1 | X = x) \geq 0，且 \hat{y} \in (0,1)，所以二阶导数恒为正。

这证明了 \hat{y} = \mathbb{P}(Y = 1 | X = x) 确实是使条件期望损失最小的点。

综上所述，我们证明了，在对数损失下，最优软分类器是：

h^*(x) = \mathbb{P}(Y = 1 | X = x)

一个关键的观察是，由于 Y \in \{0, 1\} 是二元随机变量，条件概率和条件期望之间存在等价关系：

\mathbb{P}(Y = 1 \mid X = x) = \mathbb{E}[Y \mid X = x]

这是因为

\mathbb{E}[Y \mid X = x] = 0 \cdot \mathbb{P}(Y = 0 \mid X = x) + 1 \cdot \mathbb{P}(Y = 1 \mid X = x) = \mathbb{P}(Y = 1 \mid X = x)

这个等价关系建立了分类与回归之间的深刻联系：对数损失下估计条件概率（分类问题）等价于估计条件期望（回归问题）。因此，使用对数损失的软分类在数学上等价于一个回归问题，目标是预测 Y 的条件期望。这解释了为什么许多为回归设计的技术（如正则化、核方法、神经网络）可以直接应用于分类问题——只要使用适当的损失函数，分类就可以转化为回归。

3.5 逻辑回归

3.5.1 模型构建

逻辑回归的目标是建模条件概率 \mathbb{P}(Y = 1 \mid X = x)。这里遇到的核心问题是维度不匹配：线性模型 x^T\beta 的输出范围是整个实数域 \mathbb{R}，可以是任何正数、负数或零，而概率必须严格限制在 [0, 1] 区间内。如果直接将线性输出当作概率使用，比如 x^T\beta = -2 会得到负概率，x^T\beta = 3 会得到大于1的概率，这在数学上没有意义。

解决这个问题的方法是引入sigmoid函数（也称为逻辑函数）进行变换：

h(x) = s(x^T\beta) = \frac{\exp(x^T\beta)}{1 + \exp(x^T\beta)}

其中线性部分 x^T\beta = \beta_0 + \beta_1 x_1 + \ldots + \beta_p x_p，\beta_0 是截距项，\beta_1, \ldots, \beta_p 是各特征的系数。这个变换的巧妙之处在于，无论 x^T\beta 取什么值，分母 1 + \exp(x^T\beta) 总是大于分子 \exp(x^T\beta)（因为分母比分子多了1），所以输出始终小于1。同时，由于指数函数始终为正，输出也始终大于0。这样就保证了 h(x) \in (0, 1)。

3.5.2 逻辑函数性质

逻辑函数 s(t) = \frac{\exp(t)}{1 + \exp(t)} 是一个从实数域 \mathbb{R} 到开区间 (0, 1) 的双射函数。它具有几个关键性质。

首先，它是严格递增的，即当 t_1 < t_2 时，必有 s(t_1) < s(t_2)。这个性质保证了线性部分 x^T\beta 越大，预测样本属于类别1的概率就越高，符合我们的直觉。

其次，函数无限次可微，导数在任何点都存在且连续。这对基于梯度的优化算法至关重要，因为我们需要计算梯度来更新参数。具体地，sigmoid函数的导数有一个优美的形式：

s'(t) = s(t)(1 - s(t))

函数图像呈S形曲线，具有三个特征点：当 t \to -\infty 时，\exp(t) \to 0，所以 s(t) \to 0；当 t \to +\infty 时，\exp(t) \to \infty，分子分母同时除以 \exp(t) 得 s(t) \to 1；当 t = 0 时，s(0) = \frac{1}{2}，这是转折点。函数在 t = 0 附近变化最快（斜率最大），向两端逐渐趋于平缓。

逻辑函数的逆函数是logit函数：

\text{logit}(p) = \log\left(\frac{p}{1-p}\right)

其中 \frac{p}{1-p} 称为几率（odds），表示事件发生与不发生的概率之比。如果某事件发生概率是0.8，则几率是 \frac{0.8}{0.2} = 4，意味着发生的可能性是不发生的4倍。

这个逆变换揭示了逻辑回归的另一种理解方式：虽然概率 \mathbb{P}(Y = 1 \mid X = x) 与特征 x 是非线性关系，但对数几率（log-odds）与特征是线性关系：

\text{logit}(\mathbb{P}(Y = 1 \mid X = x)) = x^T\beta

这意味着特征每增加一个单位，对数几率线性增加相应系数的量，但是在概率空间呈非线性增加。

3.5.3 参数估计

参数 \beta 通过最小化对数损失来估计，也就是最小化负对数似然，也就是最大化似然，也就是经验风险来估计，使用对数损失：

\hat{\beta} = \arg\min_{\beta} \sum_{i=1}^{n} \left[ -y_i x_i^T \beta + \log\left(1 + \exp(x_i^T \beta)\right) \right]

下面给出推导过程:

对数损失：

L(y, \hat{y}) = -y\log(\hat{y}) - (1-y)\log(1-\hat{y})

逻辑回归预测：

\hat{y} = h(x) = \frac{\exp(x^T\beta)}{1 + \exp(x^T\beta)}

步骤1：计算 h(x) 和 1-h(x)

h(x) = \frac{\exp(x^T\beta)}{1 + \exp(x^T\beta)}

1 - h(x) = 1 - \frac{\exp(x^T\beta)}{1 + \exp(x^T\beta)} = \frac{1 + \exp(x^T\beta) - \exp(x^T\beta)}{1 + \exp(x^T\beta)} = \frac{1}{1 + \exp(x^T\beta)}

步骤2：计算对数值

\log(h(x)) = \log\left(\frac{\exp(x^T\beta)}{1 + \exp(x^T\beta)}\right)

使用对数性质 \log\left(\frac{a}{b}\right) = \log(a) - \log(b)：

\log(h(x)) = \log(\exp(x^T\beta)) - \log(1 + \exp(x^T\beta)) = x^T\beta - \log(1 + \exp(x^T\beta))

同样地：

\log(1-h(x)) = \log\left(\frac{1}{1 + \exp(x^T\beta)}\right) = \log(1) - \log(1 + \exp(x^T\beta)) = -\log(1 + \exp(x^T\beta))

步骤3：代入对数损失

将上述结果代入损失函数：

\begin{align} L(y, h(x)) &= -y\log(h(x)) - (1-y)\log(1-h(x)) \\ &= -y[x^T\beta - \log(1 + \exp(x^T\beta))] - (1-y)[-\log(1 + \exp(x^T\beta))] \end{align}

步骤4：展开并化简

\begin{align} L(y, h(x)) &= -yx^T\beta + y\log(1 + \exp(x^T\beta)) + (1-y)\log(1 + \exp(x^T\beta)) \\ &= -yx^T\beta + y\log(1 + \exp(x^T\beta)) + \log(1 + \exp(x^T\beta)) - y\log(1 + \exp(x^T\beta)) \\ &= -yx^T\beta + \log(1 + \exp(x^T\beta)) \end{align}

步骤5：写出完整的优化问题

对所有训练样本求和，得到经验风险：

\hat{\beta} = \arg\min_{\beta} \sum_{i=1}^{n} L(y_i, h(x_i)) = \arg\min_{\beta} \sum_{i=1}^{n} \left[-y_ix_i^T\beta + \log(1 + \exp(x_i^T\beta))\right]

这个优化问题等价于最大似然估计。假设每个 y_i 服从参数为 h(x_i) 的伯努利分布，即 \mathbb{P}(Y_i = 1 \mid X_i = x_i) = h(x_i)，则似然函数为：

L(\beta) = \prod_{i=1}^{n} h(x_i)^{y_i} (1 - h(x_i))^{1-y_i}

取负对数似然 -\log L(\beta) 正好得到上述经验风险。这不是巧合，而是反映了对数损失与概率建模之间的内在联系：使用对数损失训练分类器，本质上是在做最大似然估计。

目标函数是 \beta 的凸函数，这可以通过计算Hessian矩阵并证明其正定性来验证。凸性保证了任何局部最优解都是全局最优解，不会陷入局部极小值。然而，这个优化问题没有闭式解，不像线性回归可以直接求解 \beta = (X^TX)^{-1}X^Ty，必须使用迭代优化算法。

Newton-Raphson算法利用目标函数的二阶导数信息，能够实现二次收敛速度。更新公式为：

\beta^{(t+1)} = \beta^{(t)} - H^{-1} g

其中 g 是梯度向量，第 j 个分量是 g_j = \sum_{i=1}^{n} x_{ij}(h(x_i) - y_i)；H 是Hessian矩阵，第 (j,k) 个元素是 H_{jk} = \sum_{i=1}^{n} x_{ij}x_{ik}h(x_i)(1 - h(x_i))。Newton方法收敛快但每步计算量大，需要计算和求逆Hessian矩阵。

梯度下降是另一种选择，只使用一阶导数信息，更新规则为 \beta^{(t+1)} = \beta^{(t)} - \eta g，其中 \eta 是学习率。对于大规模数据，随机梯度下降（SGD）更高效，每次只用一个或一小批样本估计梯度。

3.5.4 正则化

当样本量小或特征维度高时，逻辑回归容易过拟合。特别是当 p > n（特征数超过样本数）时，模型有无穷多个完美拟合训练数据的解，但泛化性能可能很差。

Ridge正则化（L2正则化）在目标函数中添加惩罚项 \lambda \|\beta\|_2^2 = \lambda \sum_{j=1}^{p} \beta_j^2：

\hat{\beta}_{\text{Ridge}} = \arg\min_{\beta} \left[ \sum_{i=1}^{n} L(y_i, h(x_i)) + \lambda \sum_{j=1}^{p} \beta_j^2 \right]

注意通常不惩罚截距项 \beta_0。Ridge正则化倾向于产生较小但非零的系数，所有特征都保留在模型中但影响被削弱。这特别适合处理共线性问题，当多个特征高度相关时，Ridge会将权重均匀分配给相关特征。

LASSO正则化（L1正则化）添加 \lambda \|\beta\|_1 = \lambda \sum_{j=1}^{p} |\beta_j| 项：

\hat{\beta}_{\text{LASSO}} = \arg\min_{\beta} \left[ \sum_{i=1}^{n} L(y_i, h(x_i)) + \lambda \sum_{j=1}^{p} |\beta_j| \right]

LASSO的特点是产生稀疏解，许多系数会被压缩到正好为0，实现自动特征选择。这是因为L1范数在原点处不可微，优化路径倾向于沿坐标轴移动，容易到达某些系数为0的点。

正则化参数 \lambda 控制偏差-方差权衡。\lambda 越大，正则化越强，模型越简单（高偏差、低方差）；\lambda 越小，正则化越弱，模型越复杂（低偏差、高方差）。\lambda = 0 时退化为普通逻辑回归。通常通过交叉验证选择最优的 \lambda：将数据分成训练集和验证集，对不同的 \lambda 值训练模型，选择验证集性能最好的。

3.5.5 决策边界

逻辑回归输出软预测 h(x) = s(x^T\hat{\beta})，这是一个概率值。要得到硬分类决策，需要通过阈值 \delta 转换：

h_\delta(x) = \mathbb{1}_{h(x) \geq \delta}

分类边界满足：

h_\delta(x) = 1 \Longleftrightarrow x^T\hat{\beta} \geq \text{logit}(\delta)

当 h(x) \geq \delta 时预测为类别1，否则预测为类别0。分类边界是使得 h(x) = \delta 的所有点的集合，即满足：

s(x^T\hat{\beta}) = \delta

应用logit函数到两边：

x^T\hat{\beta} = \text{logit}(\delta) = \log\left(\frac{\delta}{1-\delta}\right)

这揭示了一个重要的几何事实：虽然概率函数 h(x) 是非线性的（通过sigmoid变换），但决策边界仍然是线性的，是一个超平面。边界方程 x^T\hat{\beta} = c（其中 c = \text{logit}(\delta)）定义了一个 (p-1) 维超平面，在二维特征空间中是一条直线，在三维中是一个平面。

参数 \hat{\beta} 决定了边界的方向和位置:

常用的阈值是 \delta = 0.5，此时 \text{logit}(0.5) = 0，决策边界简化为 x^T\hat{\beta} = 0。但这不一定是最优选择。在不平衡数据集中（某一类样本远多于另一类），可能需要调整阈值来平衡精确率和召回率。在成本敏感的应用中，不同类型的错误有不同代价，比如医疗诊断中假阴性（漏诊）的代价远高于假阳性（误诊），应该降低阈值。

这种两阶段方法的优势在于灵活性：先训练一个软分类器来估计概率，这部分是纯粹的统计学习问题；然后根据具体应用需求选择合适的阈值，这部分是决策问题。两者分离使得同一个训练好的模型可以适应不同的应用场景。

3.6 分类性能评估指标

3.6.1 混淆矩阵

混淆矩阵是一个2×2的表格（对于二分类），系统地展示预测结果与真实标签的所有可能组合。它包含四个基本元素，每个都有特定的含义。

四个基本元素：真负例（TN）是实际为负且预测为负的样本数；真正例（TP）是实际为正且预测为正的样本数；假负例（FN）是实际为正但预测为负的样本数，称为第二类错误；假正例（FP）是实际为负但预测为正的样本数，称为第一类错误。

这四个数字总和等于样本总数：TN + TP + FN + FP = n。混淆矩阵不仅给出整体准确率，还揭示错误的分布模式。比如一个分类器可能整体准确率高，但只是因为很好地识别了负类，对正类识别能力很差。

3.6.2 真正例率与真负例率

真正例率（True Positive Rate, TPR）定义为：

\text{TPR} = \frac{TP}{P} = \frac{TP}{TP + FN}

其中 P = TP + FN 是数据中实际正类样本的总数。TPR回答的问题是："在所有真正的正类样本中，模型正确识别出了多少？"这个指标也称为敏感度（Sensitivity）或召回率（Recall）。值域是 [0, 1]，TPR = 1表示所有正类都被正确识别，TPR = 0表示没有识别出任何正类。

真负例率（True Negative Rate, TNR）定义为：

\text{TNR} = \frac{TN}{N} = \frac{TN}{TN + FP}

其中 N = TN + FP 是数据中实际负类样本的总数。TNR回答的问题是："在所有真正的负类样本中，模型正确识别出了多少？"这个指标也称为特异度（Specificity）。值域同样是 [0, 1]，TNR = 1表示所有负类都被正确识别。

TPR和TNR之间存在内在的权衡关系。考虑两个极端情况：一个极端保守的分类器总是预测为负类，这时TNR = 1（所有负类都正确），但TPR = 0（没有识别出任何正类）。相反，一个极端激进的分类器总是预测为正类，这时TPR = 1（所有正类都正确），但TNR = 0（没有识别出任何负类）。理想的分类器应该同时具有高TPR和高TNR，但实际中往往需要在两者间权衡。

3.6.3 信号处理术语

漏检率（Miss Rate）定义为 1 - \text{TPR} = \frac{FN}{TP + FN}，表示实际为正类但未被检测到的比例。这就是假负例率（False Negative Rate）。

虚警率（False Alarm Rate）定义为 1 - \text{TNR} = \frac{FP}{TN + FP}，表示实际为负类但系统发出警报的比例。这就是假正例率（False Positive Rate）。虚警虽然会浪费资源，但通常被认为代价相对较小。

3.6.4 阈值选择与性能权衡

对于软分类器 h: \mathcal{X} \rightarrow [0, 1]，通过选择阈值 \delta \in [0, 1] 可以构造硬分类器：

h_\delta: x \mapsto \mathbb{1}_{h(x) \geq \delta}

阈值的选择直接影响TNR和TPR之间的权衡。当 \delta 增大时，分类器变得更"保守"——需要更高的置信度才会预测为正类。这会导致更少的样本被预测为正类，因此FP减少（TNR上升），但同时FN增加（TPR下降）。反之，当 \delta 减小时，分类器变得更"激进"——较低的置信度就足以预测为正类，导致TPR上升但TNR下降。

当 \delta = 0.5 时，使用标准的概率阈值，即选择概率更大的类别。这时决策边界位于概率为0.5的等概率面上。错误分类的样本通常集中在决策边界附近，因为这些区域的样本具有较高的分类不确定性——模型给出的概率接近0.5。

考虑三个不同的阈值设置来理解其影响。当 \delta = 0.1 时，只要模型认为样本有10%以上的可能是正类就预测为正类。这导致决策边界大幅向负类区域移动，几乎所有样本都被预测为正类，产生大量FP但很少FN。当 \delta = 0.5 时，边界处于平衡位置。当 \delta = 0.9 时，需要90%以上的置信度才预测为正类，边界大幅向正类区域移动，只有最明确的正类样本才被识别，产生大量FN但很少FP。

没有普遍适用的"最佳"阈值，合适的选择取决于具体应用的需求和约束。在医疗诊断中，漏诊癌症（FN）的代价——延误治疗可能危及生命——远高于误诊（FP）的代价——可能需要额外检查，因此应选择较低的阈值。在垃圾邮件过滤中，将重要邮件误判为垃圾（FP）可能导致错过重要信息，比漏掉一些垃圾邮件（FN）更不可接受，因此应选择较高的阈值。

3.6.5 ROC曲线

ROC（Receiver Operating Characteristic）曲线通过绘制不同阈值下的真正例率（TPR，纵轴）对假正例率（FPR，横轴）的关系，完整展示了分类器在所有可能阈值下的性能表现。注意FPR = 1 - TNR，表示负类被错误分类为正类的比例。

构建ROC曲线的过程如下：对软分类器输出的每个可能阈值（从0到1连续变化），计算对应的TPR和FPR，在坐标系中标出点(FPR, TPR)，将这些点连接起来形成曲线。曲线上的每个点对应一个特定的阈值选择。当 \delta 接近0时，几乎所有样本都被预测为正类，因此TPR接近1但FPR也接近1，对应曲线右上角。当 \delta 接近1时，几乎没有样本被预测为正类，因此FPR接近0但TPR也接近0，对应曲线左下角。

3.6.6 AUC

AUC（Area Under the ROC Curve）是ROC曲线下的面积，提供了一个单一数值来总结分类器的整体性能。AUC的值域是 [0, 1]，其中0.5对应随机猜测（对角线下的面积），1.0对应完美分类器（整个单位正方形的面积）。

AUC有一个重要的概率解释：它等于随机选择一个正类样本的预测分数高于随机选择一个负类样本的预测分数的概率。数学表述为，如果随机选择正类样本 x^+ 和负类样本 x^-，则：

\text{AUC} = \mathbb{P}(h(x^+) > h(x^-))

这个解释说明AUC本质上衡量的是分类器对样本进行正确排序的能力——将正类样本排在负类样本前面的能力。即使不设定具体阈值，一个好的分类器应该倾向于给正类样本更高的分数。

AUC作为模型比较的工具特别有用，因为它不依赖于特定的阈值选择，而是综合考虑了所有可能的阈值。这使得AUC成为一个稳健的性能度量，特别适合在不同数据集或不同类别分布下比较分类器。比如，即使测试集的正负类比例与训练集不同，AUC仍然能够提供有意义的性能评估。

然而，AUC也有其局限性。它对整个ROC曲线的所有部分给予同等权重，但在实际应用中，我们可能只关心曲线的某个特定区域。比如在高风险应用中，可能只关心低FPR区域（ROC曲线的左侧）的性能，这时部分AUC（在特定FPR范围内的AUC）可能更有意义。此外，在极度不平衡的数据集上，AUC可能给出过于乐观的评估，因为大量的真负例会使FPR保持在较低水平。

3.7 多分类问题

3.7.1 基本设定

从二分类扩展到多分类，标签空间从 \mathcal{Y} = \{0, 1\} 扩展为 \mathcal{Y} = \{0, 1, \ldots, K-1\}，其中 K \geq 3 表示类别总数。使用整数标签 0, 1, ..., K-1 是标准做法，这简化了数学表示和算法实现。需要强调的是，这些数字仅仅是类别的标识符，它们之间没有任何顺序或数值关系。类别0并不比类别1"小"，类别2也不是类别1的"两倍"。如果把猫标记为0，狗标记为1，鸟标记为2，这些数字只是符号，可以任意重新分配而不影响问题本质。

3.7.2 0/1损失的推广

0/1损失在多分类中保持其原始形式：

L(y, \hat{y}) = \mathbb{1}_{y \neq \hat{y}}

这个定义的优雅之处在于它无需任何修改就能处理任意数量的类别。无论是二分类、三分类还是百分类，预测正确时损失为0，预测错误时损失为1。这种一致性使得许多二分类的理论结果可以直接推广到多分类。

但这种简单性也带来局限：所有的错误都被同等对待。将类别0误分类为类别1，与误分类为类别99，产生相同的损失。在许多实际应用中，不同类型的误分类可能有截然不同的严重程度。比如在医疗诊断中，将良性肿瘤误诊为某种恶性肿瘤，与将一种恶性肿瘤误诊为另一种恶性肿瘤，后果可能大不相同。这时需要更复杂的损失函数，如代价矩阵，其中 L(i, j) 表示将真实类别 i 误分类为 j 的代价。

在0/1损失下，最优分类器是：

h^*(x) = \arg\max_{c \in \{0, \ldots, C-1\}} \mathbb{P}(Y = c \mid X = x)

这是贝叶斯分类器的多类版本——选择后验概率最大的类别 c 。为什么这是最优的？在点 x 处，如果预测为类别 k，错误概率是 1 - \mathbb{P}(Y = k \mid X = x)。要最小化错误概率，应该选择使 \mathbb{P}(Y = k \mid X = x) 最大的 k。这个决策规则将特征空间划分为 K 个决策区域，每个区域对应一个类别，区域边界是后验概率相等的点集。

3.7.3 对数损失与概率建模

多分类的软分类器输出一个长度为 C 的概率向量 p = (p_0, p_1, \ldots, p_{C-1})。这个向量必须满足两个约束：非负性约束 p_c \geq 0 对所有 c 成立，以及归一化约束 \sum_{c=0}^{C-1} p_c = 1。第 c 个分量 p_c 表示模型估计样本属于类别 c 的概率。

目标是估计真实的条件概率分布 p_c = \mathbb{P}(Y = c \mid X = x)，对所有 c \in \{0, ..., C-1\}。这比二分类复杂得多：二分类只需估计一个概率值（另一个由归一化自动确定），而 C 分类需要同时估计 C-1 个独立概率（第 C 个由约束确定）。这些概率之间存在复杂的相互依赖关系，增加了建模和优化的难度。

多分类的对数损失（也称为交叉熵损失）定义为：

L(y, p) = -\sum_{c=0}^{C-1} \mathbb{1}_{y=c} \log(p_c) = -\log(p_y)

第一个表达式展示了完整形式：对每个类别 c，如果它是真实类别（\mathbb{1}_{y=c} = 1），则贡献 -\log(p_c) 到损失；否则贡献0。第二个表达式是简化形式：只有真实类别 y 对应的预测概率 p_y 影响损失。

这个损失函数的行为与二分类类似：当 p_y 接近1时（对正确类别有高置信度），-\log(p_y) 接近0；当 p_y 接近0时（对正确类别置信度很低），损失趋向无穷大。这种"越错越罚"的特性鼓励模型不仅要预测正确的类别，还要对正确预测有高置信度。

从信息论角度，这个损失衡量的是真实分布（one-hot编码，即除了真实类别为1其余都为0的确定性分布）和预测分布之间的KL散度。最小化这个损失等价于最大似然估计，其中假设每个样本的类别服从参数为 p 的多项分布。

3.7.4 多分类逻辑回归

一对多策略

将多分类问题分解为多个二分类问题的一种自然方式是一对多（one-vs-rest）策略。选择一个类别（通常是类别0）作为参考类别，然后对其余每个类别建立相对于参考类别的二元逻辑回归模型。

对每个非参考类别 k \in \{1, \ldots, K-1\}，建立log-odds模型：

\log\left(\frac{\mathbb{P}(Y = k \mid X = x)}{\mathbb{P}(Y = 0 \mid X = x)}\right) = x^T\beta^{(k)}

这个方程告诉我们，类别 k 相对于类别0的对数几率（log-odds）是特征 x 的线性函数，系数向量是 \beta^{(k)}。直观理解：x^T\beta^{(k)} 越大，样本属于类别 k 而非类别0的相对可能性越高。

为什么选择类别0作为参考？这个选择是任意的——我们可以选择任何类别作为参考，最终的预测概率不会改变，尽管参数 \beta^{(k)} 的具体值会不同。这类似于物理学中选择参考系：绝对位置依赖于参考系选择，但相对位置（这里是相对概率）是不变的。

这种参数化使用 K-1 个参数向量 \beta^{(1)}, \ldots, \beta^{(K-1)}，每个向量的维度是 p+1（p 个特征加1个截距）。总共需要估计 (K-1) \times (p+1) 个参数。注意参考类别不需要自己的参数向量，因为它相对于自己的log-odds始终为0（\log(1) = 0）。

Softmax变换

从log-odds模型推导出各个类别的概率需要求解一个方程组。我们有 K-1 个独立的log-odds方程，加上归一化约束 \sum_{c=0}^{K-1} \mathbb{P}(Y = c \mid X = x) = 1，正好 K 个方程求解 K 个未知概率。

通过代数推导（设 p_k = \mathbb{P}(Y = k \mid X = x)，从 \log(p_k/p_0) = x^T\beta^{(k)} 得到 p_k = p_0 \exp(x^T\beta^{(k)})，代入归一化约束），可以得到：

对参考类别0：

\mathbb{P}(Y = 0 \mid X = x) = \frac{1}{1 + \sum_{k=1}^{K-1} \exp(x^T\beta^{(k)})}

对其他类别 k \in \{1, \ldots, K-1\}：

\mathbb{P}(Y = k \mid X = x) = \frac{\exp(x^T\beta^{(k)})}{1 + \sum_{j=1}^{K-1} \exp(x^T\beta^{(j)})}

这就是softmax函数，它是sigmoid函数在多分类情况下的自然推广。当 K = 2 时，softmax退化为sigmoid函数。分母是归一化因子（在统计物理中称为配分函数），确保所有概率和为1。分子中的指数函数确保概率为正，而相对大小由线性组合 x^T\beta^{(k)} 决定。

Softmax函数有几个重要性质。第一，它保持相对顺序：如果 x^T\beta^{(i)} > x^T\beta^{(j)}，则 \mathbb{P}(Y = i \mid X = x) > \mathbb{P}(Y = j \mid X = x)。线性组合越大，对应的概率越高。第二，它是可微的，这对基于梯度的优化方法至关重要。第三，它具有"赢者通吃"的特性：当某个线性组合 x^T\beta^{(k)} 远大于其他所有组合时，对应的概率 p_k 接近1，而其他概率都接近0。

对称参数化

实际实现中，常使用更对称的参数化方式：为每个类别（包括类别0）都分配一个参数向量 \beta^{(0)}, \beta^{(1)}, \ldots, \beta^{(K-1)}，然后使用标准的softmax形式：

\mathbb{P}(Y = k \mid X = x) = \frac{\exp(x^T\beta^{(k)})}{\sum_{j=0}^{K-1} \exp(x^T\beta^{(j)})}

这种参数化更对称，每个类别都被同等对待。但它是过度参数化的：如果在所有 \beta^{(k)} 上加上相同的向量 v，即 \beta^{(k)} \leftarrow \beta^{(k)} + v 对所有 k，预测概率不会改变（因为分子分母都乘以 \exp(x^Tv)，可以约分）。这种参数的不唯一性需要通过正则化或约束来解决，常见做法是添加L2正则化项，或约束 \beta^{(0)} = 0（回到之前的参考类别形式）。

在计算实现中，直接计算softmax可能导致数值问题。当某些 x^T\beta^{(k)} 很大时，\exp(x^T\beta^{(k)}) 可能溢出。标准解决方案是利用softmax的平移不变性：先计算 m = \max_j x^T\beta^{(j)}，然后计算：

\mathbb{P}(Y = k \mid X = x) = \frac{\exp(x^T\beta^{(k)} - m)}{\sum_{j=0}^{K-1} \exp(x^T\beta^{(j)} - m)}

这不改变结果（分子分母都除以 \exp(m)），但避免了溢出。

参数估计仍然通过最大似然进行，等价于最小化训练集上的交叉熵损失。优化问题依然是凸的，可以用梯度下降、牛顿法或拟牛顿法求解。但参数数量随类别数线性增长：从二分类的 p+1 个参数增长到 K 分类的 (K-1) \times (p+1) 个（或对称参数化的 K \times (p+1) 个）。当类别数很大（如ImageNet的1000个类别）时，参数数量可能变得庞大，需要更高效的优化算法和近似方法。

3.8 正则化核回归

3.8.1 线性模型的局限

线性模型（如线性回归、逻辑回归）虽然在许多问题上表现良好，具有简单、可解释、计算高效等优点，但在面对复杂非线性模式时显得力不从心。

考虑一个非线性回归问题，数据点呈现明显的波浪形或周期性模式。如果用线性模型 y = \beta_0 + \beta_1 x 拟合，无论如何调整参数 \beta_0 和 \beta_1，最好也只能得到一条直线。这条直线可能穿过数据点的"中心"，但完全无法捕捉数据的波动特征。在波峰处，线性模型会低估；在波谷处，会高估。这种系统性的预测偏差不是因为数据不足或噪声太大，而是模型假设本身的限制——线性模型只能表示输入和输出之间的线性关系。

再考虑一个非线性分类问题，比如异常检测场景：正常样本（红色点）集中在特征空间的中心区域，形成一个紧密的簇；异常样本（绿色点）分布在外围，包围着正常样本。理想的决策边界应该是一个圆形或椭圆形，将中心的正常样本圈起来。但任何线性分类器的决策边界都是直线（或高维中的超平面），无论如何放置这条直线，都会造成大量误分类。这就是线性不可分问题，在实际应用中非常普遍。

3.8.2 特征变换

面对非线性问题，一个自然的想法是：能否通过某种变换，将非线性问题转化为线性问题？这正是核方法的基本思想。

考虑刚才的圆形分类问题。在原始二维特征空间 (x^{(1)}, x^{(2)}) 中，两类数据无法用直线分离。但如果定义新的特征空间，其坐标为 ((x^{(1)})^2, (x^{(2)})^2)，即将每个特征平方，神奇的事情发生了：在这个新空间中，原本混杂的两类数据变得线性可分。

为什么会这样？原始空间中的圆形决策边界方程是 (x^{(1)})^2 + (x^{(2)})^2 = r^2。如果令 z_1 = (x^{(1)})^2，z_2 = (x^{(2)})^2，这个方程变成 z_1 + z_2 = r^2，这是新特征空间中的线性方程！原始空间中的非线性边界（圆）在变换后的空间中成为线性边界（直线）。

这个例子展示了特征变换的威力：通过巧妙选择变换，可以将复杂的非线性问题转化为简单的线性问题。一旦在新特征空间中用线性方法解决了问题，就可以将解映射回原始空间，得到非线性的解。关键问题是：如何系统地、自动地找到合适的特征变换？

3.8.3 特征映射的形式化

形式化地，定义特征映射 \Phi: \mathcal{X} \rightarrow \tilde{\mathcal{X}}，它将原始实例空间 \mathcal{X} 中的每个点映射到新的特征空间 \tilde{\mathcal{X}} 中。对每个输入 x \in \mathcal{X}，映射后得到 \Phi(x) \in \tilde{\mathcal{X}}。

关键创新在于：特征空间 \tilde{\mathcal{X}} 被赋予希尔伯特空间结构，配备内积运算 \langle \cdot, \cdot \rangle_{\tilde{\mathcal{X}}}。希尔伯特空间是完备的内积空间，这意味着它不仅有内积结构（可以定义长度、角度、正交性），还满足完备性（每个柯西序列都收敛）。这种丰富的几何结构使得我们能够在特征空间中使用所有基于内积的线性方法：线性回归、主成分分析、支持向量机等。

原始空间 \mathcal{X} 中的两个点 x_1 和 x_2，它们之间可能有复杂的非线性关系。通过映射 \Phi，它们被送到特征空间中的 \Phi(x_1) 和 \Phi(x_2)。虽然 x_1 和 x_2 在原始空间中的关系复杂，但 \Phi(x_1) 和 \Phi(x_2) 在特征空间中可以用标准的线性代数工具处理——计算内积、投影、线性组合等。

特征空间的维度可以很高，甚至可以是无限维的。例如，d 次多项式特征映射将 p 维输入映射到所有不超过 d 次的单项式组成的空间，维度是 \binom{p+d}{d}，随 d 急剧增长。更极端的，径向基函数（RBF）特征映射实际上映射到无限维的希尔伯特空间。

高维或无限维特征空间看似会带来计算灾难——如何存储和计算无限维向量？这正是核技巧要解决的问题：我们不需要显式计算 \Phi(x)，只需要计算特征空间中的内积 \langle \Phi(x_1), \Phi(x_2) \rangle_{\tilde{\mathcal{X}}}，而这可以通过核函数在原始空间中高效计算。

3.9 核函数

核函数是核方法的核心概念，它提供了一种巧妙的方法：在不显式计算特征映射的情况下，直接计算特征空间中的内积。

3.9.1 定义

核函数 K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R} 的定义是：

K(x_1, x_2) = \langle \Phi(x_1), \Phi(x_2) \rangle_{\tilde{\mathcal{X}}}

这个定义的深刻之处在于计算的分离：核函数 K 接受原始空间 \mathcal{X} 中的两个点 x_1 和 x_2 作为输入，直接在原始空间中进行某种计算，但输出的结果恰好等于这两个点映射到特征空间 \tilde{\mathcal{X}} 后的内积。这意味着我们可以隐式地在高维甚至无限维的特征空间中工作，而实际计算却只在原始的低维空间中进行。

为什么这如此重要？回想前面提到的多项式特征映射，如果显式计算所有多项式特征，维度会随多项式次数指数增长。但通过核函数，我们可以直接计算内积而绕过显式的特征计算。比如二次多项式核 K(x_1, x_2) = (x_1^T x_2 + c)^2 对应的特征空间包含所有二次项，但计算核函数只需要一个内积和一次平方运算。

3.9.2 对称性

由于内积运算本身的对称性 \langle a, b \rangle = \langle b, a \rangle，核函数必然满足对称性：

K(x_1, x_2) = K(x_2, x_1)

这个性质不是我们额外施加的约束，而是从核函数的定义自然推导出来的。根据定义，K(x_1, x_2) = \langle \Phi(x_1), \Phi(x_2) \rangle_{\tilde{\mathcal{X}}}，而内积是对称的，所以 \langle \Phi(x_1), \Phi(x_2) \rangle_{\tilde{\mathcal{X}}} = \langle \Phi(x_2), \Phi(x_1) \rangle_{\tilde{\mathcal{X}}} = K(x_2, x_1)。

对称性使得核矩阵（也称为Gram矩阵）是对称矩阵，这在计算上带来很多便利：对称矩阵的特征值都是实数，可以进行Cholesky分解，存储只需要上三角或下三角部分等。

3.9.3 正定性

核函数的另一个关键性质是正定性。对任意正整数 n \in \mathbb{N}_+，任意 n 个点 x_1, \ldots, x_n \in \mathcal{X} 和任意 n 个实数系数 a_1, \ldots, a_n \in \mathbb{R}，半正定必须满足：

\mathbf{a}^T K \mathbf{a} \ge 0 \quad \forall \mathbf{a} \in \mathbb{R}^n

其中

\mathbf{a} = [a_1, a_2, \ldots, a_n]^T

展开这个式子：

\mathbf{a}^T K \mathbf{a} = \sum_{i=1}^n \sum_{j=1}^n a_i a_j K_{ij} = \sum_{i=1}^n \sum_{j=1}^n a_i a_j K(x_i, x_j)

因此半正定必须满足如下公式

\sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j K(x_i, x_j) \geq 0

下面证明，根据核函数定义：

\sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j K(x_i, x_j) = \sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j \langle \Phi(x_i), \Phi(x_j) \rangle_{\tilde{\mathcal{X}}}

利用内积的双线性性质，可以将系数提取出来：

= \left\langle \sum_{i=1}^{n} a_i \Phi(x_i), \sum_{j=1}^{n} a_j \Phi(x_j) \right\rangle_{\tilde{\mathcal{X}}}

注意两个求和实际上是同一个向量，所以：

= \left\langle \sum_{i=1}^{n} a_i \Phi(x_i), \sum_{i=1}^{n} a_i \Phi(x_i) \right\rangle_{\tilde{\mathcal{X}}} = \left\| \sum_{i=1}^{n} a_i \Phi(x_i) \right\|_{\tilde{\mathcal{X}}}^2 \geq 0

最后一步是因为范数的平方总是非负的。这个推导展示了正定性的深层原因：双重求和实际上是特征空间中某个向量的范数平方。

正定性不仅是核函数的性质，更是判定一个函数是否为有效核函数的充要条件（这就是Mercer定理的内容）。换句话说，如果一个函数 K(x, x') 满足对称性和正定性，那么一定存在一个特征映射 \Phi(\cdot) ，使得

K(x, x') = \langle \Phi(x), \Phi(x') \rangle

即使我们可能无法显式地构造出这个映射

3.9.4 距离关系

核函数的一个重要应用是计算特征空间中两点间的距离，而不需要显式计算特征映射。特征空间中两个映射点 \Phi(x_1) 和 \Phi(x_2) 之间的平方距离是：

\|\Phi(x_1) - \Phi(x_2)\|_{\tilde{\mathcal{X}}}^2 = \langle \Phi(x_1) - \Phi(x_2), \Phi(x_1) - \Phi(x_2) \rangle_{\tilde{\mathcal{X}}}

展开这个内积：

= \langle \Phi(x_1), \Phi(x_1) \rangle_{\tilde{\mathcal{X}}} - 2\langle \Phi(x_1), \Phi(x_2) \rangle_{\tilde{\mathcal{X}}} + \langle \Phi(x_2), \Phi(x_2) \rangle_{\tilde{\mathcal{X}}}

用核函数表示：

\|\Phi(x_1) - \Phi(x_2)\|_{\tilde{\mathcal{X}}}^2 = K(x_1, x_1) + K(x_2, x_2) - 2K(x_1, x_2)

这个公式完全用原始空间中的核函数值表达了特征空间中的距离。注意 K(x, x) = \|\Phi(x)\|_{\tilde{\mathcal{X}}}^2 表示点 x 映射后在特征空间中的范数平方。

这个距离公式还揭示了核函数值的几何含义。如果 K(x_1, x_1) 和 K(x_2, x_2) 固定（比如很多核函数满足 K(x, x) = 1 对所有 x），那么 K(x_1, x_2) 越大，距离 \|\Phi(x_1) - \Phi(x_2)\|_{\tilde{\mathcal{X}}}^2 就越小，意味着两点在特征空间中越接近。因此核函数可以理解为一种相似性度量——核函数值大表示两个点相似，值小表示不相似。

核函数理论的精妙之处在于将线性方法的简单性与非线性模型的表达能力完美结合。通过选择合适的核函数，我们能够隐式地在极高维甚至无限维的特征空间中工作，同时保持计算的可行性。

3.10 表示定理

表示定理是核方法理论中的基石，它回答了一个关键问题：当在可能无限维的特征空间中寻找最优解时，解的形式是什么？=> 最优解总是可以表示为有限个基函数的线性组合。

3.10.1 定理表述

考虑训练数据集 \{(x_1, y_1), \ldots, (x_n, y_n)\} 和特征映射 \Phi: \mathcal{X} \rightarrow \tilde{\mathcal{X}}。对于任意损失函数 L、正则化参数 \lambda \geq 0 和 \mathbb{R}^+ 上的严格递增惩罚函数 \text{pen}，考虑如下优化问题：

\min_{\beta} \sum_{i=1}^{n} L\left(y_i, \langle \beta, \Phi(x_i) \rangle_{\tilde{\mathcal{X}}}\right) + \lambda \text{pen}\left(\|\beta\|_{\tilde{\mathcal{X}}}\right)

这里 h(x) = \langle \beta, \Phi(x) \rangle 是因为在核方法（如 SVM、核岭回归）中，我们不直接在输入空间 \mathcal{X} 上建模，而是把样本映射到一个高维（甚至无限维）空间：

\Phi: \mathcal{X} \rightarrow \tilde{\mathcal{X}}

这里 \beta \in \tilde{\mathcal{X}} 是我们要在特征空间中寻找的参数向量。第一项是经验损失，衡量模型在训练数据上的拟合程度；第二项是正则化项，惩罚参数的复杂度（通过范数衡量）。

表示定理：这个优化问题的最优解可以限制在 \{\Phi(x_1), \Phi(x_2), \ldots, \Phi(x_n)\} 的线性张成空间中寻找。具体地说，存在系数 \hat{a} = (\hat{a}_1, \ldots, \hat{a}_n)^T 使得最优解可以写成：

\hat{\beta} = \sum_{i=1}^{n} \hat{a}_i \Phi(x_i)

这个结果的深刻之处在于维度的降低。特征空间 \tilde{\mathcal{X}} 可能是无限维的，但训练数据只有 n 个点，它们的映像张成的子空间最多是 n 维的。表示定理告诉我们，不需要在整个无限维空间中搜索，只需在这个 n 维子空间中寻找就够了。

为什么最优解有这种形式？直观的解释是：正则化项 \text{pen}(\|\beta\|_{\tilde{\mathcal{X}}}) 倾向于选择范数较小的"简单"解。将 \beta 分解为两部分：一部分在训练点张成的子空间内，另一部分垂直于这个子空间。垂直部分对训练点上的预测没有任何贡献（因为与所有 \Phi(x_i) 正交），但会增加 \beta 的范数。因此，在正则化的作用下，垂直部分会被"削去"，只保留子空间内的部分。

3.10.2 核回归的实现

用核函数重写优化问题

有了表示定理，我们知道最优解的形式是 \beta = \sum_{i=1}^{n} a_i \Phi(x_i)，其中 a = (a_1, \ldots, a_n)^T 是待求的系数向量。将这个形式代入原始优化问题。

首先，模型在训练点 x_i 上的预测变为：

\langle \beta, \Phi(x_i) \rangle_{\tilde{\mathcal{X}}} = \left\langle \sum_{j=1}^{n} a_j \Phi(x_j), \Phi(x_i) \right\rangle_{\tilde{\mathcal{X}}}

利用内积的线性性质：

= \sum_{j=1}^{n} a_j \langle \Phi(x_j), \Phi(x_i) \rangle_{\tilde{\mathcal{X}}} = \sum_{j=1}^{n} a_j K(x_i, x_j)

其次，参数的范数平方变为：

\|\beta\|_{\tilde{\mathcal{X}}}^2 = \left\| \sum_{i=1}^{n} a_i \Phi(x_i) \right\|_{\tilde{\mathcal{X}}}^2 = \sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j K(x_i, x_j)

因此，原始的优化问题转化为：

\min_{a} \sum_{i=1}^{n} L\left(y_i, \sum_{j=1}^{n} a_j K(x_i, x_j)\right) + \lambda \text{pen}\left(\sqrt{\sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j K(x_i, x_j)}\right)

现在优化变量是 n 维向量 a，而不是可能无限维的 \beta。

格拉姆矩阵

定义格拉姆矩阵（Gram matrix）K \in \mathbb{R}^{n \times n}，其第 (i,j) 个元素为：

K_{ij} = K(x_i, x_j) = \langle \Phi(x_i), \Phi(x_j) \rangle_{\tilde{\mathcal{X}}}

这个矩阵完全刻画了训练数据在特征空间中的几何关系。由于核函数的对称性，格拉姆矩阵是对称的；由于核函数的正定性，格拉姆矩阵是半正定的。

使用矩阵记号，优化问题可以简洁地写为：

\min_{a} \sum_{i=1}^{n} L(y_i, (Ka)_i) + \lambda \text{pen}\left(\sqrt{a^T K a}\right)

这里 (Ka)_i 表示向量 Ka 的第 i 个分量，等于 \sum_{j=1}^{n} K_{ij} a_j。所有的计算都在 n 维空间中进行，完全避免了显式处理高维或无限维的特征空间。

预测函数

一旦求得最优系数 \hat{a}，对新输入 x 的预测为：

\hat{h}(x) = \langle \hat{\beta}, \Phi(x) \rangle_{\tilde{\mathcal{X}}} = \left\langle \sum_{i=1}^{n} \hat{a}_i \Phi(x_i), \Phi(x) \right\rangle_{\tilde{\mathcal{X}}}

= \sum_{i=1}^{n} \hat{a}_i \langle \Phi(x_i), \Phi(x) \rangle_{\tilde{\mathcal{X}}} = \sum_{i=1}^{n} \hat{a}_i K(x_i, x)

这个公式揭示了核方法预测的本质：新点的预测是所有训练点的加权组合，权重是 \hat{a}_i，而 K(x_i, x) 衡量训练点 x_i 与测试点 x 的相似度。相似度高的训练点（K(x_i, x) 大）对预测的影响更大。这种基于相似性的预测方式非常直观。

3.10.3 核岭回归

优化问题

在回归设置中，使用平方损失 L(y, \hat{y}) = (y - \hat{y})^2 和二次惩罚 \text{pen}(t) = t^2，优化问题变为：

\min_a \sum_{i=1}^{n} \left(y_i - \sum_{j=1}^{n} a_j K(x_i, x_j)\right)^2 + \lambda \sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j K(x_i, x_j)

用矩阵形式重写：

\min_a \|y - Ka\|^2 + \lambda a^T K a

这里 y = (y_1, \ldots, y_n)^T 是响应向量。目标函数包含两部分：\|y - Ka\|^2 是训练误差，衡量模型预测与真实值的差距；\lambda a^T K a 是正则化项，控制模型复杂度。

闭式解

这是一个凸二次优化问题，可以通过令梯度为零求得闭式解。计算目标函数关于 a 的梯度：

\nabla_a \left(\|y - Ka\|^2 + \lambda a^T K a\right)

对第一项，使用链式法则：\nabla_a \|y - Ka\|^2 = -2K^T(y - Ka)。对第二项：\nabla_a (a^T K a) = 2Ka（因为 K 对称）。

令梯度为零：

-2K^T(y - Ka) + 2\lambda Ka = 0

由于格拉姆矩阵 K 是对称的（K^T = K），方程简化为：

-K(y - Ka) + \lambda Ka = 0

整理得：

K(Ka + \lambda a) = Ky

如果 K 可逆（满秩），可以左乘 K^{-1}：

Ka + \lambda a = y

因此：

\hat{a} = (K + \lambda I_n)^{-1} y

这个解的形式：在格拉姆矩阵 K 上加一个"岭"（对角线上加 \lambda），然后求逆并乘以响应向量。正则化参数 \lambda 的作用是改善矩阵的条件数：即使原始的 K 接近奇异（如训练点几乎共线），K + \lambda I_n 也是可逆的。

\lambda 控制着偏差-方差权衡。当 \lambda 很大时，解趋向于 a \approx 0，模型非常平滑但可能欠拟合；当 \lambda 很小时，解接近最小二乘解，模型复杂但可能过拟合。通常通过交叉验证选择最优的 \lambda。

当格拉姆矩阵 K 不可逆时（比如有重复的训练点，或训练点数超过特征空间维度），解 \hat{a} 可能不唯一。但有趣的是，即使 \hat{a} 不唯一，预测函数 \hat{h}(x) = \sum_{i=1}^{n} \hat{a}_i K(x_i, x) 却是唯一确定的。这是因为不同的 \hat{a} 可能对应特征空间中的同一个 \hat{\beta}。

3.10.4 核岭回归与标准岭回归的联系

标准岭回归

在标准岭回归中，我们有 q 个基函数 h_1, \ldots, h_q，预测模型为：

h(x) = \sum_{j=1}^{q} h_j(x) \beta_j = \Phi(x)^T \beta

其中 \Phi(x) = (h_1(x), \ldots, h_q(x))^T 是基函数组成的向量，\beta = (\beta_1, \ldots, \beta_q)^T 是参数向量。

岭回归的优化问题是：

\hat{\beta}^{\text{Ridge}} = \arg\min_{\beta} \|y - \Phi\beta\|^2 + \lambda \|\beta\|^2

这里设计矩阵 \Phi \in \mathbb{R}^{n \times q} 的第 (i,j) 元素是 h_j(x_i)，即第 i 行是 \Phi(x_i)^T。通过令梯度为零，得到闭式解：

\hat{\beta}^{\text{Ridge}} = \left(\Phi^T\Phi + \lambda I_q\right)^{-1} \Phi^T y

等价性证明

现在考虑特殊情况：特征映射就是 \Phi(x) = (h_1(x), \ldots, h_q(x))^T \in \mathbb{R}^q，特征空间 \tilde{\mathcal{X}} = \mathbb{R}^q 配备标准内积。对应的核函数为：

K(x_1, x_2) = \Phi(x_1)^T \Phi(x_2) = \sum_{j=1}^{q} h_j(x_1) h_j(x_2)

格拉姆矩阵 K = \Phi\Phi^T，其中 K_{ij} = \Phi(x_i)^T \Phi(x_j)。核岭回归的解为：

\hat{a} = \left(\Phi\Phi^T + \lambda I_n\right)^{-1} y

预测函数为：

\hat{h}(x) = \sum_{i=1}^{n} \hat{a}_i K(x_i, x) = \sum_{i=1}^{n} \hat{a}_i \Phi(x_i)^T \Phi(x) = \Phi(x)^T \sum_{i=1}^{n} \hat{a}_i \Phi(x_i)^T

注意 \sum_{i=1}^{n} \hat{a}_i \Phi(x_i)^T 是一个 q 维行向量，转置后得到：

\hat{h}(x) = \Phi(x)^T \Phi^T \hat{a} = \Phi(x)^T \Phi^T \left(\Phi\Phi^T + \lambda I_n\right)^{-1} y

这里需要用到Woodbury矩阵恒等式（也称为矩阵求逆引理）：

\Phi^T(\Phi\Phi^T + \lambda I_n)^{-1} = (\Phi^T\Phi + \lambda I_q)^{-1} \Phi^T

这个恒等式可以通过验证两边都满足同一个方程来证明。代入后得到：

\hat{h}(x) = \Phi(x)^T \left(\Phi^T\Phi + \lambda I_q\right)^{-1} \Phi^T y = \Phi(x)^T \hat{\beta}^{\text{Ridge}}

这证明了核岭回归在使用线性核（K(x_1, x_2) = \Phi(x_1)^T \Phi(x_2)）时，确实退化为标准的岭回归。这个结果展示了核方法是线性方法的自然推广——当使用线性核时回到线性方法，使用非线性核时得到非线性模型。

3.10.5 核方法的灵活性

当前方法的局限

到目前为止，我们的方法是先定义特征映射 \Phi，然后推导出相应的核函数 K(x_1, x_2) = \langle \Phi(x_1), \Phi(x_2) \rangle。这种方法虽然概念清晰，但在实践中有明显的局限性。

首先，对于复杂的非线性问题，很难事先知道什么样的特征映射是合适的。我们可能需要尝试多种不同的特征映射，这既耗时又缺乏系统性。其次，许多有用的核函数对应的特征映射是无限维的。比如高斯（RBF）核函数对应的特征空间是无限维的希尔伯特空间，我们根本无法显式地写出这个映射。

直接设计核函数

一个关键的观察是：在整个核岭回归的求解过程中，我们只用到了核函数 K，从未显式使用特征映射 \Phi。求解系数时用的是格拉姆矩阵 K，预测时用的是 K(x_i, x)。这启发了一个重要问题：能否直接设计核函数，而完全不考虑背后的特征映射？

答案是肯定的。Mercer定理告诉我们，只要一个函数满足对称性和正定性条件（称为Mercer条件），它就是一个有效的核函数，必然对应着某个（可能是隐式的、无法显式构造的）特征空间和特征映射。这极大地扩展了核方法的应用范围。

这种直接设计核函数的方法带来了巨大的灵活性。我们可以根据问题的特点设计专门的核函数：对于周期性数据可以设计周期核，对于字符串数据可以设计字符串核，对于图数据可以设计图核。只要验证这些函数满足Mercer条件，就可以在核方法框架下使用它们，而完全不需要知道对应的特征空间是什么样的。这种灵活性正是核方法在机器学习中获得巨大成功的关键原因。

3.11 再生核希尔伯特空间

3.11.1 从核函数到特征空间的反向构造

之前我们的思路是从特征映射 \Phi 出发，通过内积定义核函数 K(x_1, x_2) = \langle \Phi(x_1), \Phi(x_2) \rangle。现在我们要考虑反过来的问题：如果给定一个满足某些条件的函数 K，它是否一定对应着某个特征空间和特征映射？

核心命题告诉我们：一个函数 K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R} 是对称正定函数，当且仅当存在一个希尔伯特空间 \mathcal{H} 和映射 \Phi: \mathcal{X} \rightarrow \mathcal{H}，使得对所有 x_1, x_2 \in \mathcal{X}，都有：

K(x_1, x_2) = \langle \Phi(x_1), \Phi(x_2) \rangle_{\mathcal{H}}

这个"当且仅当"建立了双向等价关系。正向说明每个内积都产生对称正定函数（这在前面已经证明）。反向说明每个对称正定函数都可以理解为某个希尔伯特空间中的内积。这个反向结果非常深刻，因为它意味着我们不需要先构造特征映射，只要验证一个函数满足对称性和正定性，就可以确信它背后存在一个（可能是隐式的、我们永远不会显式构造的）特征空间。

这彻底改变了我们处理核方法的方式。原来的流程是：设计特征映射 → 计算对应的核函数 → 使用核函数进行计算。现在的流程变成：直接设计满足条件的核函数 → 确信存在对应的特征空间（但不需要知道具体是什么）→ 使用核函数进行所有计算。这种灵活性使得我们可以为各种复杂问题设计专门的核函数，而不必担心如何显式构造对应的特征映射。

这个特征空间可以被实现为再生核希尔伯特空间（Reproducing Kernel Hilbert Space, RKHS），这是一个由函数构成的特殊希尔伯特空间。

3.11.2 RKHS的定义

考虑定义在集合 \mathcal{X} 上的实值函数构成的希尔伯特空间 \mathcal{H}_K。注意这里的元素不是向量，而是函数 f: \mathcal{X} \rightarrow \mathbb{R}。函数 K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R} 被称为 \mathcal{H}_K 的再生核，如果它满足两个条件。

第一个条件是：对每个 x \in \mathcal{X}，函数 K_x = K(x, \cdot) 属于 \mathcal{H}_K。这里 K_x 是将第一个参数固定为 x，第二个参数作为变量的函数。换句话说，K_x(t) = K(x, t) 对所有 t \in \mathcal{X}。这个条件保证了核函数的每个"切片"都是空间中的合法元素。

第二个条件是再生性质：对所有 f \in \mathcal{H}_K 和 x \in \mathcal{X}，有：

\langle f, K_x \rangle_{\mathcal{H}_K} = f(x)

这是RKHS最核心的性质。左边是函数空间中两个函数的内积，右边是函数 f 在点 x 处的值。这个等式说明，要计算函数在某点的值，只需要将函数与对应的核函数切片做内积。这就是"再生"的含义——内积操作"再生"（重现）了函数值。

满足这两个条件的函数空间 \mathcal{H}_K 被称为再生核希尔伯特空间。这个概念的深刻之处在于它建立了函数值与内积之间的联系。在一般的函数空间（如 L^2 空间）中，点态评估（求函数在某点的值）不是连续的线性泛函，但在RKHS中，点态评估是连续的，而且可以通过内积实现。

从RKHS的定义可以直接推导出核函数的对称性。根据再生性质，对任意 x_1, x_2 \in \mathcal{X}：

K(x_1, x_2) = K_{x_1}(x_2) = \langle K_{x_1}, K_{x_2} \rangle_{\mathcal{H}_K}

由于内积是对称的，所以 \langle K_{x_1}, K_{x_2} \rangle_{\mathcal{H}_K} = \langle K_{x_2}, K_{x_1} \rangle_{\mathcal{H}_K}，因此 K(x_1, x_2) = K(x_2, x_1)。

正定性也可以类似推导。对任意 n 个点 x_1, \ldots, x_n 和系数 a_1, \ldots, a_n：

\sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j K(x_i, x_j) = \sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j \langle K_{x_i}, K_{x_j} \rangle_{\mathcal{H}_K}

利用内积的双线性性：

= \left\langle \sum_{i=1}^{n} a_i K_{x_i}, \sum_{j=1}^{n} a_j K_{x_j} \right\rangle_{\mathcal{H}_K} = \left\| \sum_{i=1}^{n} a_i K_{x_i} \right\|_{\mathcal{H}_K}^2 \geq 0

传统的RKHS定义是从点态评估泛函的有界性出发。在一般的函数空间中，点态评估 \delta_x: f \mapsto f(x) 可能是无界的。但如果点态评估是有界的线性泛函，根据Riesz表示定理，存在唯一的元素（恰好就是 K_x）使得 \delta_x(f) = \langle f, K_x \rangle。我们这里直接从再生核出发定义RKHS，这种方法更构造性，直接展示了核函数的核心作用。

3.11.3 Moore-Aronszajn定理

Moore-Aronszajn定理是RKHS理论的基础定理，它保证了从核函数到RKHS的构造总是可能的。

定理内容：对于定义在 \mathcal{X} 上的对称正定核 K，存在唯一的希尔伯特空间 \mathcal{H}_K（由 \mathcal{X} 上的函数构成），使得 K 是其再生核。特别地，集合 \{K_x : x \in \mathcal{X}\} 的线性张成在所得的RKHS中是稠密的。

这个定理的存在性部分告诉我们，每个满足对称正定条件的函数都对应着一个RKHS。当我们选择一个核函数时，不需要担心是否真的存在对应的特征空间——定理保证了它一定存在。唯一性部分说明，给定核函数 K，对应的RKHS是唯一确定的。不同的构造方法会得到同一个空间（在等距同构意义下）。

稠密性条件 \overline{\text{span}\{K_x : x \in \mathcal{X}\}} = \mathcal{H}_K 意味着RKHS中的任何函数都可以被形如 \sum_{i} a_i K_{x_i} 的有限线性组合任意逼近。这与表示定理呼应——虽然RKHS可能是无限维的，但我们总可以用有限个基函数来逼近其中的任何元素，而这些基函数正是训练点对应的核函数。

这个定理带来了重要的范式转变。我们不需要显式构造RKHS或特征映射，而是可以通过指定核函数来隐式地确定它们。核函数完全决定了RKHS的结构——它的内积、范数、收敛性等所有性质都由核函数决定。

在这个框架下，特征映射可以理解为 \Phi(x) = K_x，即每个点 x 被映射到RKHS中的函数 K_x = K(x, \cdot)。验证一下这个映射是否满足我们的要求：

\langle \Phi(x_1), \Phi(x_2) \rangle_{\mathcal{H}_K} = \langle K_{x_1}, K_{x_2} \rangle_{\mathcal{H}_K} = K(x_1, x_2)

最后一个等式来自再生性质。所以这个映射确实满足核函数的定义。

通过选择不同的核函数，我们隐式地选择了不同性质的函数空间。多项式核对应的RKHS包含多项式函数；高斯核对应的RKHS包含光滑函数；拉普拉斯核对应的RKHS包含具有特定衰减性质的函数。核函数的选择编码了我们对解的先验假设——我们期望学到的函数具有什么样的性质。

3.11.4 表示定理的RKHS版本

现在我们从RKHS的角度重新表述表示定理。考虑数据集 \{(x_1, y_1), \ldots, (x_n, y_n)\} 和具有再生核 K 的RKHS \mathcal{H}_K。注意现在 \mathcal{H}_K 是函数空间，其中的元素是函数 h: \mathcal{X} \rightarrow \mathbb{R}。

优化问题现在变成在函数空间中寻找最优函数：

\hat{h} = \arg\min_{h \in \mathcal{H}_K} \sum_{i=1}^{n} L(y_i, h(x_i)) + \lambda \text{pen}(\|h\|_{\mathcal{H}_K})

这里 h(x_i) 是函数 h 在点 x_i 处的值，\|h\|_{\mathcal{H}_K} 是函数 h 在RKHS中的范数。表示定理告诉我们，这个优化问题的解可以表示为：

\hat{h} = \sum_{i=1}^{n} \hat{a}_i K_{x_i}

这个表述更加自然，因为我们直接在函数空间中工作，寻找的就是一个函数。与之前在参数空间中寻找参数向量不同，这里优化变量本身就是我们最终需要的预测函数。RKHS框架明确了我们搜索解的空间——不是在所有可能的函数中搜索，而是在一个具有特定结构（由核函数决定）的RKHS中搜索。

虽然RKHS可能是无限维的，表示定理保证最优解总是落在一个有限维子空间中——由训练点对应的核函数张成的子空间。这将无限维优化问题转化为有限维问题，维数不超过训练样本数 n。

3.12 常用核函数

3.12.1 线性核

线性核定义为 K(x_1, x_2) = x_1^T x_2，这是最简单的核函数。它对应的特征映射是恒等映射 \Phi(x) = x，不进行任何变换。对应的RKHS是所有形式为 h(x) = \beta^T x 的线性函数构成的空间。

使用线性核的核方法完全等价于相应的线性方法。比如使用线性核的核岭回归就是普通的线性岭回归。线性核适用于数据本身就是线性可分或线性关系的情况，这时非线性变换反而可能引入不必要的复杂性。

3.12.2 多项式核

多项式核定义为 K(x_1, x_2) = (1 + x_1^T x_2)^q，其中 q 是多项式的次数。这个核函数对应的RKHS包含所有次数不超过 q 的多项式函数。

具体来说，当 q = 2 时，展开得到：

K(x_1, x_2) = (1 + x_1^T x_2)^2 = 1 + 2x_1^T x_2 + (x_1^T x_2)^2

进一步展开 (x_1^T x_2)^2 = \sum_{i,j} x_1^{(i)} x_1^{(j)} x_2^{(i)} x_2^{(j)}，可以看到二次多项式核隐式地包含了常数项、所有一次项、所有二次项和所有交叉项。

常数项1的作用是确保核函数考虑所有低于 q 次的项，而不仅仅是恰好 q 次的项。如果使用 (x_1^T x_2)^q 而不加1，那么只会包含恰好 q 次的项，失去了低次项的信息。这种包含所有低次项的设计使得模型更灵活，能够自动选择合适的复杂度。

多项式核能够隐式地考虑特征之间的交互作用。比如在二次多项式核中，交叉项 x^{(i)} x^{(j)} 捕捉了第 i 个特征和第 j 个特征的交互效应。这在许多实际问题中很有用，因为特征之间往往存在非线性的交互关系。

3.12.3 高斯（RBF）核

高斯核（也称为径向基函数核或RBF核）定义为：

K(x_1, x_2) = \exp\left(-\frac{\|x_1 - x_2\|^2}{2\sigma^2}\right)

其中 \sigma 称为带宽参数。这是机器学习中最常用的核函数之一。

高斯核对应的RKHS是一个无限维的空间，包含所有无限次可微的函数。这可以从高斯函数的泰勒展开看出：

\exp(x) = \sum_{n=0}^{\infty} \frac{x^n}{n!}

这意味着高斯核隐式地包含了所有阶的多项式特征，赋予了它极强的表达能力。

高斯核的几何解释很直观：K(x_1, x_2) 度量两点之间的相似性，当 x_1 = x_2 时核函数值为1（最大相似性），随着两点距离增加，核函数值按指数速度衰减到0。带宽参数 \sigma 控制这种衰减的速度。当 \sigma 很小时，核函数快速衰减，只有非常接近的点才有显著的相似性，导致学习的函数非常"局部"，每个训练点只影响其小邻域。当 \sigma 很大时，核函数缓慢衰减，远距离的点也有较大的相似性，导致学习的函数更"全局"，训练点的影响范围更大。

高斯核的一个重要性质是平移不变性：K(x_1, x_2) 只依赖于 x_1 - x_2，即两点的相对位置，而不依赖于它们的绝对位置。这使得高斯核特别适合那些没有特定参考点的问题。

3.12.4 核函数的构造规则

核函数理论的一个重要结果是，可以从已知的核函数构造新的核函数。设 K_1 和 K_2 是两个对称正定核，则以下操作仍然产生对称正定核。

乘积规则：K(x_1, x_2) = K_1(x_1, x_2) \cdot K_2(x_1, x_2) 也是核函数。这可以理解为将两个特征空间进行张量积。如果 K_1 对应特征映射 \Phi_1，K_2 对应特征映射 \Phi_2，那么乘积核对应的特征映射包含所有 \Phi_1 的分量与 \Phi_2 的分量的乘积。

线性组合规则：对于非负系数 c_1, c_2 \geq 0，K(x_1, x_2) = c_1 K_1(x_1, x_2) + c_2 K_2(x_1, x_2) 也是核函数。这相当于将两个特征空间进行直和，新的特征向量是两个原始特征向量的拼接（适当加权）。

这些构造规则的实用价值在于可以组合不同核函数的优点。比如可以将多项式核（捕捉全局多项式模式）与高斯核（捕捉局部模式）组合：K = c_1 K_{\text{poly}} + c_2 K_{\text{RBF}}，得到既有全局视野又有局部敏感性的核函数。在实际应用中，这种组合核函数往往能够获得比单一核函数更好的性能。

3.13 高斯核的超参数影响

高斯核 K(x_1, x_2) = \exp\left(-\frac{\|x_1 - x_2\|^2}{2\sigma^2}\right) 在核岭回归中有两个关键超参数：正则化参数 \lambda 和带宽参数 \sigma。通过系统地改变这两个参数，可以观察到模型行为的显著变化。

3.13.1 正则化参数影响

当 \lambda = 1e-09（极小的正则化）时，正则化项 \lambda a^T K a 几乎为0，优化问题主要是最小化训练误差。模型会尽力拟合每个训练点，包括其中的噪声。结果是拟合曲线剧烈波动，在训练点处精确通过，但在训练点之间出现不合理的振荡。这是典型的过拟合——模型的复杂度过高，记住了训练数据的每个细节而不是学习底层的规律。

当 \lambda = 1e-05（中等正则化）时，模型在拟合训练数据和保持平滑性之间找到平衡。正则化项防止系数 a 过大，从而防止模型过度依赖个别训练点。拟合曲线通过训练点附近但不强制精确通过每个点，能够忽略一些明显的噪声点。这种设置通常能获得最好的泛化性能。

当 \lambda = 0.01（较强正则化）时，正则化项占主导地位，强烈惩罚模型的复杂度。模型变得过度平滑和保守，即使在训练数据密集的区域也不能很好地拟合。这是欠拟合的表现——模型太简单，无法捕捉数据中的真实模式。

3.13.2 带宽参数影响

当 \sigma = 0.1（小带宽）时，核函数 K(x_i, x) = \exp(-\|x_i - x\|^2/(2 \times 0.01)) 快速衰减。只有当测试点 x 非常接近训练点 x_i 时，K(x_i, x) 才有显著的值。这导致每个训练点只影响其很小的邻域，预测函数变得非常"局部"。如果正则化较弱，模型会在每个训练点附近形成尖锐的峰；如果正则化较强，模型可能在训练点之间的区域预测值接近0。

当 \sigma = 0.5（中等带宽）时，核函数的影响范围适中。每个训练点影响一定范围的邻域，相邻训练点的影响区域有适度重叠。这使得预测函数既能适应局部变化，又保持整体的连续性和平滑性。

当 \sigma = 2（大带宽）时，核函数衰减很慢，即使相距较远的点之间也有显著的核函数值。每个训练点影响很大的区域，所有训练点对任何位置的预测都有贡献。模型变得非常平滑和"全局"，但可能失去捕捉局部细节的能力。在极端情况下，当 \sigma \to \infty 时，高斯核趋向于常数核，模型退化为常数函数。

3.13.3 参数选择指导

\lambda 和 \sigma 共同控制模型的复杂度，但作用机制不同。\lambda 直接控制正则化强度，通过惩罚系数的大小来防止过拟合。\sigma 控制核函数的局部性，影响模型的灵活性——小 \sigma 使模型更灵活但容易过拟合，大 \sigma 使模型更平滑但可能欠拟合。

两个参数之间存在交互作用。当 \sigma 很小（局部核）时，模型本身就很灵活，通常需要较大的 \lambda（强正则化）来防止过拟合。当 \sigma 很大（全局核）时，模型本身就比较平滑，可以使用较小的 \lambda。

在实践中，这些超参数通常通过交叉验证选择。将数据分成训练集和验证集，在不同的参数组合下训练模型，选择验证集性能最好的参数。网格搜索是常用方法：在 \lambda 和 \sigma 的对数空间中均匀采样（如 \lambda \in \{10^{-6}, 10^{-5}, ..., 10^{-1}\}，\sigma \in \{0.01, 0.1, 1, 10\}），评估所有组合。从3×3的参数网格图可以看出，\lambda = 1e-05 和 \sigma = 0.5 的组合（中间的图）通常提供最平衡的结果——既能捕捉数据的主要模式，又不会过度拟合噪声。

3.14 本章小结

本章从分类问题的基本概念开始，建立了分类的数学框架。我们定义了硬分类器和软分类器，介绍了0/1损失和对数损失，并推导了在这两种损失下的最优分类器——贝叶斯分类器输出后验概率最大的类别，而对数损失下的最优分类器直接输出后验概率。

逻辑回归展示了如何将线性模型扩展到分类问题。通过sigmoid变换，我们将线性组合映射到概率空间，保证输出是合法的概率值。虽然概率输出是非线性的，但决策边界仍然是线性的，这限制了模型处理复杂分类问题的能力。

分类器的评估不能只看准确率。混淆矩阵提供了错误分布的详细信息，TPR和TNR衡量了不同类型的性能，ROC曲线展示了所有可能阈值下的权衡，AUC提供了阈值无关的整体性能度量。这些工具帮助我们全面评估分类器，并根据具体应用需求选择合适的操作点。

核方法部分展示了如何突破线性模型的限制。通过特征映射 \Phi: \mathcal{X} \rightarrow \tilde{\mathcal{X}}，我们可以将非线性问题转化为高维空间中的线性问题。核函数 K(x_1, x_2) = \langle \Phi(x_1), \Phi(x_2) \rangle 提供了一种优雅的计算方式——不需要显式计算高维特征，只需要在原始空间中计算核函数。

表示定理是核方法的理论基石，它保证即使在无限维特征空间中，最优解也可以表示为 \hat{\beta} = \sum_{i=1}^{n} \hat{a}_i \Phi(x_i)，是有限个基函数的线性组合。这将无限维优化问题转化为有限维问题，使得计算变得可行。

RKHS理论提供了核方法的严格数学基础。Moore-Aronszajn定理保证每个对称正定函数都对应一个唯一的RKHS。在这个框架下，我们直接在函数空间中工作，核函数决定了空间的所有性质。不同的核函数对应不同性质的函数空间——线性核对应线性函数空间，多项式核对应多项式函数空间，高斯核对应光滑函数空间。

核岭回归结合了核方法和正则化技术。通过选择合适的核函数和调节超参数（\lambda 控制正则化强度，\sigma 控制核函数的局部性），我们可以在欠拟合和过拟合之间找到平衡，学习出既能拟合训练数据又有良好泛化能力的非线性模型。

第四章基于树的方法

4.1 决策树基础

4.1.1 决策树的基本结构

决策树是通过递归地询问一系列问题来进行预测的树形结构模型。这种递归询问实际上是在特征空间中进行逐步划分，每一次询问都将数据空间分割成更小的子空间。

决策树包含三种节点：根节点位于第0层，是决策过程的起点；内部节点位于中间层，继续进行条件判断；叶子节点位于最底层，不再分割而是给出最终预测结果。

这种层次化结构反映了决策过程的递归本质。从根节点开始，每个节点代表一个关于数据特征的问题或条件判断。根据数据样本在该特征上的取值，决策沿着不同分支向下传递，直到到达叶子节点。这种结构模拟了人类的决策过程，使得模型具有很强的可解释性。

4.1.2 CART算法

分类与回归树（CART）是构建二叉决策树的经典算法。CART的核心创新在于它提供了统一的框架来处理分类和回归两类不同的预测任务。"二叉"特性意味着每个内部节点只产生两个分支，这简化了树的构建过程，也使得算法更加高效。

对于分类树，目标标签 y 是分类变量，比如"有效"或"无效"、"是"或"否"等离散类别。分类树的任务是学习如何根据输入特征将数据点分配到正确的类别中。对于回归树，目标标签 y 取连续值，比如房价、温度、销售额等数值型变量。回归树的任务是学习如何根据输入特征预测一个连续的数值。

虽然分类和回归的目标不同，但CART算法使用相似的树构建机制：都通过递归地分割特征空间来构建树，都使用相同的树生长和剪枝策略。主要区别在于分割标准的选择（分类树通常使用基尼指数或信息增益，回归树使用均方误差）和叶节点的预测方式（分类树输出类别，回归树输出数值均值）。

4.2 决策树案例

4.2.1 分类树案例

我们看一个医学应用案例来理解分类树的工作原理。目标是预测某种安眠药对患者是否有效，这是典型的二分类问题。

解释变量定义为 x = (x^{(1)}, x^{(2)})，是二维特征向量。x^{(1)} 是二元变量，表示患者是否为儿童，捕捉年龄组别对药物反应可能存在的差异。x^{(2)} 是当前平均睡眠时间（小时），是连续变量，反映患者的睡眠状况基线。标签 y 表示药丸的有效性，取值为"有效"或"无效"。

模型的决策过程分为两个层次。第一层判断 x^{(1)} = \text{child}?，即首先询问患者是否为儿童。这个问题将所有患者分成儿童组和成人组，反映模型发现年龄组别是影响药物效果的重要因素。

对于儿童组，需要进一步决策。第二层规则是判断 x^{(2)} < 6?，即检查儿童患者的平均睡眠时间是否少于6小时。如果是，则预测药物"无效"；如果睡眠时间≥6小时，则预测药物"有效"。这暗示对于儿童患者，药物效果与其睡眠基线密切相关：睡眠严重不足的儿童可能对该药物反应不佳。

对于成人组，模型直接预测药物"无效"，不需要进一步条件判断。这表明在训练数据中，该安眠药对成人患者普遍无效。

特征空间的划分

特征空间的划分可以可视化为二维图。横轴表示年龄组别，纵轴表示平均睡眠时间。红色点代表药物无效的案例，蓝色点代表药物有效的案例。决策树将二维特征空间划分成不同的矩形区域。首先，垂直线将空间分为儿童区域和成人区域。在儿童区域内，水平线（x_2 = 6）进一步将空间分为两部分：下方红色区域（睡眠时间<6小时，预测无效）和上方蓝色区域（睡眠时间≥6小时，预测有效）。成人区域则完全被标记为红色（预测无效）。

这种矩形划分是决策树的典型特征，每个矩形区域对应树的一个叶节点。这种划分虽然简单，但能够有效捕捉数据中的非线性模式。同时也揭示了决策树的一个局限：它只能生成与坐标轴平行的决策边界，无法直接学习斜线或曲线边界，对于某些数据分布可能需要很深的树才能近似复杂的边界。

4.2.2 回归树案例

回归树与分类树在结构上非常相似，但其目标是预测连续的数值而不是离散的类别。回归树通过一系列的条件判断来预测一个连续的目标变量。根节点的第一个分割条件是 x^{(2)} < 26.2?，将整个数据空间分成两个主要部分。

对于满足 x^{(2)} < 26.2 的左分支，进一步通过 x^{(1)} < 113.7? 进行分割。如果 x^{(1)} < 113.7，再次通过 x^{(1)} < 85.85? 分割，最终得到两个叶节点，分别预测值为77.4和86.7。如果 x^{(1)} \geq 113.7，则直接预测108.1。这种递归分割体现了回归树如何逐步细化预测，每个分割都试图使得子区域内的目标值更加同质化。

对于右分支（x^{(2)} \geq 26.2），分割逻辑类似但使用不同的阈值。通过 x^{(2)} < 33.1? 进行第二层分割，然后继续递归分割，最终产生四个叶节点，预测值分别为99.5、148.7、196.1和278。注意右侧分支的预测值普遍高于左侧，这反映了 x^{(2)} 这个特征对目标变量有显著的正向影响。

回归树的可视化

从二维平面图的角度看，回归树将特征空间(x^{(1)}, x^{(2)})划分成多个矩形区域。每个矩形对应树的一个叶节点，区域内的所有点都被赋予相同的预测值。这种划分的特点是所有分割线都平行于坐标轴，因为每次分割都是基于单个特征的阈值判断。

三维图提供了回归树预测函数的立体视角，z轴表示预测值h(x)，(x^{(1)}, x^{(2)})构成底面的二维特征空间。红色点表示实际的训练数据点，而彩色的阶梯状曲面就是回归树的预测函数。

这清楚展示了回归树预测函数的"阶梯"特性：在每个矩形区域内，预测值是常数，形成平坦的"台阶"。不同区域之间存在明显的"跳跃"，这就是为什么称之为分片常数（piecewise constant）函数。这种特性既是回归树的优势（能够捕捉非线性关系和交互作用），也是其局限（无法产生平滑的预测曲面）。

4.3 分片常数预测函数

4.3.1 数学表达式

决策树的预测可以用数学语言精确地表达为一个分片常数函数：

h_\beta(x) = \sum_{k=1}^{m} \beta_k \mathbb{1}_{\mathcal{Z}_k}(x)

这个公式是理解决策树工作原理的核心。其中 \mathbb{1}_{\mathcal{Z}_k}(x) 是指示函数，当输入 x 落在区域 \mathcal{Z}_k 内时取值为1，否则为0。

\mathbb{1}_{\mathcal{Z}_k}(x) = \begin{cases} 1, & \text{if } x \in \mathcal{Z}_k \\ 0, & \text{otherwise} \end{cases}

这个指示函数充当了"开关"的角色，决定某个区域的预测值是否应该被激活。

\beta_k 是与区域 \mathcal{Z}_k 关联的系数，在回归问题中通常是该区域内训练样本目标值的均值，在分类问题中可能是该区域的类别概率。

整个求和式的工作机制是这样的：对于任意输入x，由于区域是互不重叠的，x只会落在某一个特定区域\mathcal{Z}_{k^*}中。因此，所有指示函数中只有\mathbb{1}_{\mathcal{Z}_{k^*}}(x) = 1，其余都为0。这样，预测值就简化为h_\beta(x) = \beta_{k^*}，即输入所在区域对应的系数值。

4.3.2 构建决策树的关键组成部分

构建决策树需要两个关键组成部分。第一是实例空间的一个分割 \{\mathcal{Z}_1, \ldots, \mathcal{Z}_m\}，这些区域互不重叠且覆盖整个特征空间。第二是与每个区域相关联的系数 \beta_1, \ldots, \beta_m。这两个组成部分共同定义了树的结构和预测能力。

对于给定的分割，模型在参数 \beta_1, \ldots, \beta_m 上是线性的。这意味着预测函数可以写成参数的线性组合，其中指示函数充当了固定的基函数。这个性质带来了重要的计算优势：一旦树的结构（即区域分割）确定了，优化系数就变成了一个简单的凸优化问题，可以高效求解。这种分离使得树的学习过程可以分为两步：首先确定最优的分割，然后在每个区域内独立地估计最优系数。

4.4 系数的估计

4.4.1 估计基本原理

系数估计遵循机器学习的标准范式：选择合适的损失函数，然后通过最小化经验风险来找到最优参数。损失函数L(y, h_\beta(x))衡量预测值h_\beta(x)与真实值y之间的差异。经验风险定义为所有训练样本上的平均损失：

\min_{\beta} \hat{R}_n(h_\beta) = \min_{\beta} \sum_{i=1}^{n} L(y_i, h_\beta(x_i))

将决策树的分片常数形式h_\beta(x) = \sum_{k=1}^{m} \beta_k \mathbb{1}_{\mathcal{Z}_k}(x)代入上式。由于每个样本x_i只会落在某一个区域中，我们可以将求和重新组织为先对区域求和，再对区域内的样本求和：

= \min_{\beta} \sum_{k=1}^{m} \sum_{x_i \in \mathcal{Z}_k} L(y_i, \beta_k)

关键洞察：总的经验风险等于各个区域内风险的总和。更重要的是，不同区域的参数\beta_k在损失函数中是完全独立的——改变\beta_k只影响区域\mathcal{Z}_k内的损失，不会影响其他区域。因此，全局优化问题可以分解为m个独立的局部优化问题：

= \sum_{k=1}^{m} \min_{\beta_k} \sum_{x_i \in \mathcal{Z}_k} L(y_i, \beta_k)

每个区域的最优系数可以独立计算：

\forall k, \quad \hat{\beta}_k = \arg\min_{\beta_k} \sum_{x_i \in \mathcal{Z}_k} L(y_i, \beta_k)

这个分解带来了巨大的计算优势。不需要同时优化所有参数，而是可以对每个叶节点独立地计算最优预测值。这也体现了决策树的局部性特征——每个区域的预测只依赖于落在该区域内的训练样本，与其他区域的数据无关。

4.4.2 两个重要的特殊情况

回归问题

当使用二次损失进行回归时，区域 \mathcal{Z}_k 的系数估计变为：

\hat{\beta}_k = \arg\min_{\beta_k} \sum_{i \in \mathcal{Z}_k} (y_i - \beta_k)^2 = \bar{y}_{\mathcal{Z}_k}

证明:

对目标函数关于\beta_k求导并令其为零：

\frac{\partial}{\partial \beta_k} \sum_{i \in \mathcal{Z}_k} (y_i - \beta_k)^2 = -2\sum_{i \in \mathcal{Z}_k} (y_i - \beta_k) = 0

解这个方程得到

\beta_k = \frac{1}{|\mathcal{Z}_k|} \sum_{i \in \mathcal{Z}_k} y_i = \bar{y}_{\mathcal{Z}_k}

这里 \bar{y}_{\mathcal{Z}_k} 表示区域 \mathcal{Z}_k 内所有训练样本目标值的均值。这个结果非常直观：在均方误差准则下，一个区域的最优常数预测就是该区域内样本的平均值。这也解释了为什么回归树的每个叶节点输出其覆盖的训练样本的平均值。从统计角度看，均值是使方差最小的估计量。

分类问题

对于有 C 个类别的多类分类问题，存在两种主要处理方式。

软分类输出每个类别的概率估计：

\hat{\beta}_k = \arg\min_{\beta_k \in \Delta^{C-1}} \sum_{x_i \in \mathcal{Z}_k} \sum_{c=0}^{C-1} -\mathbb{1}_{y_i=c} \log(\beta_k^{(c)})

这里 \Delta^{C-1} 是概率单纯形，即所有分量非负且和为1的向量集合。\beta_k^{(c)}表示区域 \mathcal{Z}_k 中预测为类别 c 的概率。最优解是经验概率分布：

\hat{\beta}_k^{(c)} = \frac{1}{\text{card}(\mathcal{Z}_k)} \cdot \text{card}(\{(x_i, y_i) : x_i \in \mathcal{Z}_k, y_i = c\})

这个公式计算的是区域\mathcal{Z}_k内类别c的相对频率。分子是该区域内属于类别c的样本数，分母是该区域内的总样本数。软分类的优势在于它不仅给出了预测类别，还提供了预测的置信度。比如，如果某个叶节点有70%的样本属于类别A，30%属于类别B，软分类会输出[0.7, 0.3]这样的概率向量。

硬分类方法则直接输出最可能的类别，采用多数投票规则：选择区域内出现频率最高的类别作为预测。这种方法实现简单，预测明确，但丢失了不确定性信息。在实践中，即使最终需要硬分类结果，通常也会先计算软分类概率，然后取概率最大的类别，这样可以在需要时获得置信度信息。

4.5 递归分割

4.5.1 递归分割的原理

递归分割的目标是从数据 (X, y) 构建实例空间 \mathcal{X} 的一个最优分割。这个过程的核心思想是通过迭代地细化分割来逐步提高模型的预测能力。每次分割都试图找到最能减少预测误差的分割点。

算法采用迭代方式构建一系列分割 (\mathcal{P}_m)_{m \geq 1}，其中 \mathcal{P}_m 表示包含 m 个子集的分割：

\mathcal{P}_m = \{\mathcal{Z}_1^{(m)}, \ldots, \mathcal{Z}_m^{(m)}\}

上标 (m) 表示这是第 m 步迭代的结果，每个 \mathcal{Z}_k^{(m)} 代表特征空间中的一个矩形区域。初始化时 \mathcal{P}_1 = \{\mathcal{X}\} ，即整个特征空间作为一个单一区域。这对应于只有根节点的树，所有样本都接收相同的预测值——在回归问题中是所有目标值的均值，在分类问题中是最频繁的类别。

4.5.2 分割过程

从 \mathcal{P}_m 到 \mathcal{P}_{m+1} 的转换是通过选择并分割某个现有的子集 \mathcal{Z}_{k_m}^{(m)} 实现的。这个过程涉及三个关键决策：选择哪个区域进行分割（ k_m ）、使用哪个变量进行分割（ j_m ）、以及在什么位置进行分割（ d_m ）。

假设我们选择了变量 j 和分割点 d_m ，那么原区域 \mathcal{Z}_{k_m}^{(m)} 被分割成两个新区域：

\tilde{\mathcal{Z}}_1 = \mathcal{Z}_{k_m}^{(m)} \cap \{x : x^{(j_m)} \leq d_m\}

\tilde{\mathcal{Z}}_2 = \mathcal{Z}_{k_m}^{(m)} \cap \{x : x^{(j_m)} > d_m\}

第一个区域 \tilde{\mathcal{Z}}_1 包含所有在第 j_m 个特征上取值不超过 d_m 的样本，第二个区域 \tilde{\mathcal{Z}}_2 包含剩余的样本。这种二分策略确保了两个新区域互不重叠且完全覆盖原区域，保持了分割的完整性。

选择最优分割的过程是计算密集的。对于每个可能被分割的区域，算法需要考虑所有特征，对于每个特征需要考虑所有可能的分割点。最优选择基于某种纯度改进准则，如信息增益或基尼指数的减少。这个准则量化了分割带来的"价值"——通过分割，我们能在多大程度上减少预测的不确定性。

递归过程会持续进行，每次迭代都选择当前最有价值的分割，直到满足停止条件。常见的停止条件包括：达到预设的最大深度（防止过拟合）、区域内样本数低于最小阈值（避免对噪声过度拟合）、纯度改进低于某个阈值（分割带来的收益太小）、或者区域已经完全纯净（所有样本属于同一类别或目标值相同）。

4.6 递归分割的详细示例

4.6.1 二维分割的迭代过程

通过一个二维特征空间（p=2）的例子来深入理解递归分割。当前的分割状态中，子集 \mathcal{Z}_{k_m}^{(m)} 是即将被分割的区域。这个区域目前包含整个矩形空间，我们将通过一次分割将其分成两个子区域。

迭代过程 \mathcal{P}_m \to \mathcal{P}_{m+1} 包含四个关键步骤。第一步是选择要分割的子集 \mathcal{Z}_{k_m}^{(m)} \in \mathcal{P}_m。在树的早期阶段，可能只有一个区域可供选择，但随着树的生长，需要决定哪个叶节点最值得进一步分割。这个选择通常基于潜在的纯度改进或误差减少。

第二步是选择分割变量 x^{(j_m)}。在这个例子中选择了 j_m = 2，意味着沿着第二个特征 x^{(2)} 进行分割。这个选择至关重要，因为不同的变量可能导致完全不同的分割质量。算法通常会尝试所有可能的变量，选择能够最大程度提高纯度的那个。

第三步是确定分割阈值 d_m。这个红色虚线表示的阈值将特征空间水平分割。阈值的选择决定了每个子区域包含多少样本，以及这些样本的类别分布。最优阈值通常通过网格搜索或其他优化方法找到，目标是最大化分割后两个子区域的纯度。

第四步是构建新的子集 \tilde{\mathcal{Z}}_1 和 \tilde{\mathcal{Z}}_2。分割后，原来的区域 \mathcal{Z}_{k_m}^{(m)} 被两个新区域替换，更新后的分割为：

\mathcal{P}_{m+1} = \mathcal{P}_m \bigcup \{\tilde{\mathcal{Z}}_1, \tilde{\mathcal{Z}}_2\} \setminus \{\mathcal{Z}_{k_m}^{(m)}\}

这个集合运算表达式准确描述了分割的更新过程：保留所有未被分割的区域（ \mathcal{P}_m 中除 \mathcal{Z}_{k_m}^{(m)} 外的部分），加入两个新创建的子区域，同时移除被分割的原区域。分割数从 m 增加到 m+1 ，树的复杂度增加了一层。

4.6.2 分类树分割的逐步演示

我们通过睡眠药物的例子来观察分类树的实际构建过程。初始数据包含两类样本：橙色点表示药物"有效"，蓝色点表示"无效"。数据的初始分布显示出明显的模式，但需要通过递归分割来捕捉这些模式。

第一次分割选择沿着 x^{(1)} （年龄组别）进行。这是一个二元分类变量，分割条件是" x^{(1)} = \text{child}? "。分割后形成两个区域：左侧的儿童区域包含20个样本，其中16个蓝色（无效）和4个橙色（有效），比例为16:4。右侧的成人区域包含10个样本，全部为蓝色（无效），比例为10:0。这个分割立即实现了重要的分离：成人区域变成了完全纯净的区域，这意味着该节点不需要进一步分割就可以做出确定的预测——对成人患者，药物总是无效的。

第一次分割的成功体现在两个方面。首先，它创建了一个完全纯净的区域（成人区域），这部分数据的预测问题已经完全解决。其次，虽然儿童区域仍然不纯，但相比原始数据，有效案例的比例从13.3%（4/30）提升到了20%（4/20），说明分割确实捕捉到了数据中的模式。

探索不同分割点

接下来展示了算法如何探索 x^{(2)}（睡眠时间）上的不同分割点。这个探索过程是找到最优分割的关键步骤。

首先尝试的分割点 x^{(2)} < d_1（其中 d_1 是某个较低的阈值）产生了两个区域：下方区域只有1个橙色样本（比例0:1），上方区域有16个蓝色和3个橙色样本（比例16:3）。虽然这个分割创建了一个完全纯净的小区域，但它只隔离了一个样本。从信息论角度看，这个分割的信息增益很小，因为它几乎没有减少整体的不确定性。而且，基于单个样本的规则很可能是过拟合的表现。

将阈值调整到 x^{(2)} < d_2 后，分割产生了不同的效果：下方区域现在包含1个蓝色和1个橙色样本（比例1:1），上方区域包含15个蓝色和3个橙色样本（比例15:3）。这个分割的问题在于下方区域完全不纯（50%-50%的分布），没有提供有用的分类信息。

这个例子说明了为什么简单地创建平衡的分割（每个区域样本数相近）并不总是最优的。我们追求的是纯度的提升，而不仅仅是样本的均匀分配。

继续调整到 x^{(2)} < d_{19}，这次产生了更好的结果：下方区域包含15个蓝色和4个橙色样本（比例15:4），上方区域只有1个蓝色样本（比例1:0）。虽然上方区域变成纯净的，这种分割几乎没有简化问题——我们仍然需要处理包含19个混合样本的大区域。

这一系列的尝试展示了分割点选择的挑战。每个可能的阈值都会产生不同的区域纯度和样本分布。算法需要在多个相互竞争的目标之间取得平衡：提高区域纯度（减少不确定性）、保持合理的区域大小（避免基于少数样本的规则）、以及创建可解释的决策规则（分割应该在领域知识上有意义）。

最优分割的选择

选择最优分割涉及多个相互竞争的目标。一方面，我们希望创建尽可能纯净的区域，这样可以做出更确定的预测。另一方面，我们需要避免创建太小的区域，因为这可能导致过拟合——模型记住了训练数据的特殊情况而不是学习到一般模式。

理想的分割应该在以下几个方面取得平衡：最大化纯度增益（每个子区域应该比父区域更纯），保持合理的区域大小（避免只包含少数样本的区域），以及产生可解释的决策规则（分割应该在业务或科学上有意义）。

这种逐步优化的过程将持续进行，每次选择当前最优的分割，直到满足停止条件。常见的停止条件包括：达到最大树深度、区域内样本数低于最小阈值、纯度改进低于某个阈值，或者区域已经完全纯净。

4.7 分割准则

分割准则是决策树算法的核心，因为它决定了树如何选择最优的分割点。理解分割准则就是理解决策树"智能"的来源——它如何从无数可能的分割中找到最好的那个。

4.7.1 异质性（纯度）度量

由于树是分片常数函数，我们的目标是让每个区域内的观察值尽可能同质。这个目标背后的逻辑很直观：如果一个区域内的所有样本都非常相似，那么用一个常数值来预测这个区域就会很准确。相反，如果区域内的样本差异很大，任何单一的预测值都会产生较大的误差。

在概率建模框架下，我们将 (X_i, Y_i) \overset{\text{iid}}{\sim} \mathbb{P}^{X,Y}，其中 X \in \mathcal{Z} 时，定义异质性（或称不纯度）度量为条件分布 \mathbb{P}^{Y|X \in \mathcal{Z}} 的函数，记为 H(Y | X \in \mathcal{Z})。这个度量量化了在给定 X 落在区域 \mathcal{Z} 内的条件下，Y 的不确定性或变异性。

回归问题的异质性度量

对于回归问题，异质性通常用方差来表示：

H(Y | X \in \mathcal{Z}) = \text{Var}[Y | X \in \mathcal{Z}]

方差衡量了目标值围绕其均值的分散程度。方差为零意味着区域内所有目标值都相同，这是理想情况；方差越大，说明目标值越分散，用均值作为预测的误差就越大。使用方差作为异质性度量，导致回归树倾向于创建目标值变化较小的区域。

使用方差作为异质性度量有深刻的统计学基础：在均方误差准则下，均值是最优的点估计，而方差恰好度量了这个估计的不确定性。

分类问题的异质性度量

对于分类问题，异质性度量是概率向量 p^{\mathcal{Z}} = (p_0^{\mathcal{Z}}, \ldots, p_{C-1}^{\mathcal{Z}})^T 的函数，其中 p_c^{\mathcal{Z}} = \mathbb{P}(Y = c | X \in \mathcal{Z}) 表示在区域 \mathcal{Z} 内类别 c 的概率。

两个最常用的分类异质性度量是熵和基尼指数。

熵（Entropy）源自信息论，由香农提出，衡量的是随机变量包含的信息量或不确定性：

H(Y | X \in \mathcal{Z}) = H(p^{\mathcal{Z}}) = -\sum_{c=0}^{C-1} p_c^{\mathcal{Z}} \log(p_c^{\mathcal{Z}})

熵的直觉解释是：它度量了为了确定一个随机选择的样本的类别，平均需要多少比特的信息。当所有类别概率相等时（最大不确定性），熵达到最大值 \log(C) ；当只有一个类别时（完全确定），熵为零。对数函数的使用使得熵对概率的变化更加敏感，特别是对接近0或1的概率值。这种敏感性在实践中是优势，因为它鼓励算法创建更纯净的节点。

基尼指数（Gini Index）可以理解为随机选择两个样本属于不同类别的概率：

H(Y | X \in \mathcal{Z}) = H(p^{\mathcal{Z}}) = 1 - \sum_{c=0}^{C-1} (p_c^{\mathcal{Z}})^2

基尼指数可以理解为：从区域 \mathcal{Z} 中随机选择两个样本（有放回），它们属于不同类别的概率。当区域完全纯净时（所有样本属于同一类），这个概率为0；当各类别均匀分布时，这个概率接近最大值 1-1/C 。相比熵，基尼指数的计算更简单（不需要对数运算），这在大规模数据集上可能带来计算优势。在实践中熵和基尼指数效果通常相似。

4.7.2 异质性的减少

对于包含分割 \{\mathcal{Z}_1, \ldots, \mathcal{Z}_m\} 的树 \mathcal{T}，整体异质性度量定义为：

R(\mathcal{T}) = \sum_{k=1}^{m} H(Y | X \in \mathcal{Z}_k) \mathbb{P}(X \in \mathcal{Z}_k)

这个公式是各区域异质性的加权平均，权重 \mathbb{P}(X \in \mathcal{Z}_k) 是样本落入该区域的概率。这种加权方式确保了大区域（包含更多样本）对整体异质性的贡献更大，这是合理的，因为大区域的预测误差会影响更多的样本。

通过分割 \mathcal{Z} = \mathcal{Z}_1 \bigcup \mathcal{Z}_2，整体异质性的减少（或增益）为：

\text{gain} = H(Y | X \in \mathcal{Z})\mathbb{P}(X \in \mathcal{Z}) - H(Y | X \in \mathcal{Z}_1)\mathbb{P}(X \in \mathcal{Z}_1) - H(Y | X \in \mathcal{Z}_2)\mathbb{P}(X \in \mathcal{Z}_2)

增益等于分割前的加权异质性减去分割后两个子区域的加权异质性之和。正的增益意味着分割减少了整体的不确定性，增益越大，分割越有价值。

算法的核心策略是贪婪地选择能够最大化异质性减少的分割。具体来说，对于每个可能被分割的区域，算法考虑所有可能的分割变量和分割点，计算每个组合的信息增益，然后选择增益最大的那个。这种贪婪策略不保证找到全局最优的树，但在实践中通常能产生良好的结果。

一个重要的理论结果是，如果选择异质性度量为：

H(Y | X \in \mathcal{Z}) = \min_{\beta} \mathbb{E}[L(Y, \beta) | X \in \mathcal{Z}]

即异质性等于该区域内的最小期望损失，那么分割准则与系数估计遵循完全相同的优化原理。这种一致性意味着树的结构学习（决定如何分割）和参数学习（决定叶节点的预测值）在优化同一个目标函数。

4.7.3 信息增益的实际计算

在实践中，真实的概率分布 \mathbb{P}^{Y|X \in \mathcal{Z}} 是未知的，我们使用训练数据的经验分布来近似。这意味着用样本频率替代真实概率，用样本统计量替代总体参数。虽然这是一种近似，但随着样本量的增加，根据大数定律，经验分布会收敛到真实分布。

我们通过睡眠药物的例子来具体计算信息增益，这将展示理论如何转化为实际的计算过程。

初始状态下，根节点包含30个样本：26个无效（蓝色），4个有效（橙色）。根节点询问" x^{(1)} = \text{child}? "，产生两个子节点。左子节点（儿童）包含20个样本：16个无效、4个有效，类别分布为(0.8, 0.2)。右子节点（成人）包含10个样本：10个无效、0个有效，类别分布为(1.0, 0.0)。

信息增益的计算公式为：

\text{gain} = H(Y) - H(Y | X^{(1)} = \text{child}) \mathbb{P}(X^{(1)} = \text{child}) - H(Y | X^{(1)} = \text{adult}) \mathbb{P}(X^{(1)} = \text{adult})

首先计算父节点的熵。父节点的类别分布是 (26/30, 4/30) = (0.867, 0.133) ，使用经验概率：

H\left(\frac{16}{16+4}, \frac{4}{16+4}\right) - H\left(\frac{6}{6+4}, \frac{4}{6+4}\right) \cdot \frac{6+4}{16+4} - H\left(\frac{10}{10+0}, \frac{0}{10+0}\right) \cdot \frac{10+0}{16+4}

代入具体数值并简化：

= H(0.8, 0.2) - 0.5H(0.6, 0.4) - 0.5H(1, 0)

其中 H(0.8, 0.2) 表示80%无效、20%有效时的熵，H(0.6, 0.4) 表示60%无效、40%有效时的熵，H(1, 0) 表示100%无效时的熵（为0，因为完全纯净）。

这个计算过程展示了决策树如何定量评估每个分割的价值。通过比较不同分割的信息增益，算法可以客观地选择最优策略。在实际实现中，算法会系统地尝试所有可能的分割：对每个特征，尝试所有可能的分割点（对于连续特征）或分割方式（对于分类特征），计算相应的信息增益，最后选择增益最大的分割。

虽然理论上需要考虑无限多个分割点，但实践中有许多优化技巧来减少计算量。对于连续变量，一个关键观察是：最优分割点必定位于两个不同类别的相邻样本之间。因此，我们只需要在这些边界点处评估分割，这将候选分割点的数量从无限减少到最多 n-1 个。对于高基数的分类变量（比如邮政编码），完全搜索所有可能的二分方式可能不可行，此时可以使用启发式方法，比如根据目标变量的均值对类别进行排序，然后只考虑有序分割。

这些计算优化使得决策树算法即使在大规模数据集上也能高效运行，这也是决策树在实践中广受欢迎的原因之一。

4.8 何时停止树的生长

4.8.1 树的过度生长问题

初始状态只有一个包含所有20个儿童样本的节点，比例为16:4（16个无效，4个有效）。如果不设定停止准则，树会一直生长直到每个叶节点都变得完全纯净，这就引出了一个关键问题：我们应该在什么时候停止分割？

第一次分割后的状态，根节点通过 x^{(1)} = \text{child}? 分割，产生两个子节点：左侧儿童节点（6:4）和右侧成人节点（10:0）。成人节点已经完全纯净，不需要进一步分割，但儿童节点仍然混合，可以继续分割。

对儿童节点的进一步分割通过条件 x^{(2)} < 6.15?，将儿童节点分成两部分：睡眠时间少于6.15小时的（1:4）和大于等于6.15小时的（5:0）。这次分割创建了一个纯净的右子节点（全部无效）和一个主要为有效的左子节点。

完全展开的树中，左下角的节点（1:4）被进一步通过 x^{(2)} < 1.67 分割，创建了两个叶节点：一个纯净的有效节点（0:2）和一个主要有效的节点（1:2）。现在整个树有5个叶节点，每个都相对纯净或完全纯净。

4.8.2 停止准则

算法使用三个主要的停止准则来防止过度生长。

每个节点的最小样本数：当一个节点包含的样本数少于预设阈值（如5个或10个）时，停止分割该节点。这防止了基于极少数样本做出分割决策，这种决策往往不可靠且容易过拟合。从统计角度看，小样本的分割不具有统计显著性。

最大叶节点数：限制树的叶节点总数，这直接控制了模型的复杂度。更多的叶节点意味着更细粒度的空间划分，但也增加了记忆训练数据特殊模式的风险。

最大树深度：限制从根节点到叶节点的最长路径长度。深度限制是简单而有效的复杂度控制方法，它确保了决策过程不会过于复杂。在实践中，深度为5-10的树通常就足够捕捉大多数模式。

这些停止准则的选择涉及偏差-方差权衡。过早停止（浅树）会导致高偏差（欠拟合），模型无法捕捉数据的复杂模式。过晚停止（深树）会导致高方差（过拟合），模型记住了训练数据的噪声。

4.9 剪枝

4.9.1 剪枝的概念

剪枝就像园丁修剪树木以促进健康生长并去除枯枝一样，我们修剪决策树以去除那些不能提升泛化性能的分支。

剪枝的目标是从完全生长的树\mathcal{T}中识别并移除那些不能提升泛化性能的子树。完全生长的树可能包含许多深层分割，这些分割在训练数据上减少了误差，但实际上只是拟合了噪声。通过剪枝，我们希望保留捕捉真实模式的分割，而移除那些过度特化的分割。

4.9.2 成本复杂度剪枝

剪枝的核心是为每个可能的子树 \tilde{\mathcal{T}} \preceq \mathcal{T} 定义一个成本函数，然后选择成本最小的子树：

\mathcal{T}_\lambda = \arg\min_{\tilde{\mathcal{T}} \preceq \mathcal{T}} R_\lambda\left(\tilde{\mathcal{T}}\right) \stackrel{\text{def}}{=} R\left(\tilde{\mathcal{T}}\right) + \lambda\left|\tilde{\mathcal{T}}\right|

这个公式体现了机器学习中的基本原则：正则化。其中 R(\tilde{\mathcal{T}}) 是训练误差（衡量模型的拟合程度），|\tilde{\mathcal{T}}| 是叶节点数量（衡量模型复杂度），\lambda 是正则化参数（控制两者的权衡）。

当 \lambda = 0 时，只考虑训练误差，导致选择完全生长的树。随着 \lambda 增大，复杂度惩罚变得更重要，倾向于选择更简单的树。当 \lambda \to \infty 时，会选择只有根节点的树（最简单但可能欠拟合）。

这种成本复杂度剪枝方法的优势在于它提供了一系列嵌套的子树，随着 \lambda 从0增加到无穷大，最优子树从完全生长的树逐渐简化到只有根节点。这个序列中的每棵树都是某个 \lambda 值下的最优选择。通过交叉验证选择最优的 \lambda ，我们可以找到在新数据上表现最好的子树。

4.10 决策树的优缺点

4.10.1 优势

决策树的规则可以直接转化为人类可理解的if-then语句。这种透明性在医疗诊断、信贷审批等需要解释决策原因的领域特别重要。每个预测都可以通过追踪从根到叶的路径来完全解释。

与许多需要数值输入的算法不同，决策树可以直接处理分类变量，无需创建虚拟变量。这避免了维度膨胀问题，也保持了分类变量的自然结构。比如一个有10个类别的变量在逻辑回归中需要9个虚拟变量，但在决策树中只是一个变量。

4.10.2 劣势

单个决策树通常比其他现代方法（如神经网络、支持向量机）的预测准确性低。这是因为树的分片常数性质限制了它只能产生轴平行的决策边界，无法很好地逼近斜线或曲线边界。

树对数据的小变化非常敏感。数据的微小扰动可能导致完全不同的树结构。这种不稳定性源于树构建的贪婪和递归性质。早期分割的小变化会级联影响到所有后续分割，导致完全不同的树结构。这就是为什么需要集成方法（如随机森林）的主要动机——通过组合多个树来降低这种方差。

决策树的这些局限性直接引出了Bagging和随机森林。这些方法通过构建多个树并组合它们的预测来克服单个树的高方差问题。集成方法保留了树的优势（处理非线性、交互作用、混合类型数据），同时通过平均化减少了预测的不稳定性。

4.11 Bagging方法

4.11.1 群体智慧

Bagging的核心思想源于群体智慧。一个实验设置了场景：50名成员需要在10个类别中进行投票，每个类别有4个提名选项。关键的设置是，对于每个类别，只有15名投票者具有相关知识，这些"专家"由他们正确选择候选人的概率 P 来表征（因此 P = 0.25 意味着他们没有任何知识，只是随机猜测）。

这15名专家是从50人中随机选择的，实验运行了50次模拟来获得稳定的统计结果。橙色线（Consensus）展示了群体共识的准确率，而青色线（Individual）展示了个体的平均准确率。误差条表示一个标准差，反映了结果的变异性。

最引人注目的发现是，当专家的个体准确率 P 超过0.25（即优于随机猜测）时，群体共识的准确率始终高于个体平均水平。这种现象的数学基础在于大数定律：当多个独立的、略微准确的判断被聚合时，随机误差趋向于相互抵消，而正确的信号得到加强。即使每个专家只有0.5的准确率（仅比抛硬币好一点），群体共识的准确率可以达到接近0.8。

这个原理直接启发了机器学习中的集成方法。如果我们把每个决策树看作一个"专家"，那么通过聚合多个树的预测，我们可以获得比单个树更好的性能。关键在于确保这些树足够多样化（就像专家们的错误是独立的），这样它们的错误才不会系统性地重复。

4.11.2 模型聚合的理论基础

回顾统计学习理论中的偏差-方差分解：

\mathbb{E}\left[(Y - \hat{h}(X))^2\right] = (\mathbb{E}[h(x; D)] - \mathbb{E}[Y | X = x])^2 + \text{Var}[h(x; D)] + \text{Var}[Y | X = x]

这个分解告诉我们预测误差来自三个源头：偏差（模型的系统性错误）、方差（模型对训练数据变化的敏感度）和不可约误差（数据本身的噪声）。

决策树的主要问题是高方差。不同的训练集会产生截然不同的树结构和预测。假设我们有多个独立的数据集 D_1, \ldots, D_B ，在每个数据集上构建一个模型，然后聚合它们：

\hat{h}_{\text{ag}}(x) = \frac{1}{B} \sum_{b=1}^{B} h(x; D_b)

这种平均对偏差没有影响——如果每个模型平均而言偏离真实值 \delta ，它们的平均仍然偏离 \delta 。不可约误差也不受影响。但方差项会发生显著变化：

\text{Var}[\hat{h}_{\text{ag}}(x)] = \frac{1}{B^2} \sum_{b_1=1}^{B} \sum_{b_2=1}^{B} \text{Cov}[h(x; D_{b_1}), h(x; D_{b_2})]

当数据集完全独立时，不同数据集上训练的模型之间的协方差为零（ b_1 \neq b_2 时），只有对角线项（ b_1 = b_2 ）非零：

= \text{Var}[h(x; D_1)] \frac{1}{B^2} \sum_{b_1=1}^{B} \sum_{b_2=1}^{B} \rho(h(x; D_{b_1}), h(x; D_{b_2})) \leq \text{Var}[h(x; D_1)]

这个不等式是Bagging有效性的数学保证。聚合总是减少或至多保持方差不变。在理想情况下，如果模型完全独立（相关系数 \rho = 0 ），方差会减少到原来的 1/B 。即使模型有一定相关性（这在实践中不可避免），只要 \rho < 1 ，聚合仍然能减少方差。

4.11.3 Bootstrap方法

Bootstrap是一种巧妙的重采样技术，它解决了一个实际问题：我们通常只有一个训练数据集，如何创建多个"独立"的数据集来训练多个模型？Bootstrap的答案是通过有放回采样来创建数据的多个版本。

给定原始数据集 d = \{(x_1, y_1), \ldots, (x_n, y_n)\} ，Bootstrap通过有放回地随机抽取 n 次来创建新数据集。"有放回"是关键——每次抽取后，被选中的样本会放回原数据集，因此可能被再次选中。这导致Bootstrap样本中某些原始样本出现多次，而某些样本完全不出现。

每个数据点在某次抽取中被选中的概率是 1/n ，不被选中的概率是 (1-1/n) 。在 n 次独立抽取中都不被选中的概率是 (1-1/n)^n 。当 n 趋向无穷大时，根据著名的极限 \lim_{n \to \infty}(1-1/n)^n = e^{-1} ，这个概率收敛到约0.368。

因此，期望上每个Bootstrap样本包含原始数据集约 1 - e^{-1} \approx 0.632 （63.2%）的不同观测值。换句话说，约三分之一的原始数据不会出现在任何给定的Bootstrap样本中，而出现的数据点平均会重复约1.6次。

表格展示了具体的Bootstrap过程。原始数据索引从1到10，每个Bootstrap样本通过有放回采样得到。Bootstrap样本 d_1 是[6, 6, 9, 6, 8, 3, 6, 2, 5, 5]，数据点6出现了4次，而数据点1、4、7、10完全没有出现。这种重复和缺失创造了数据的"扰动"版本，每个Bootstrap样本强调数据的不同方面。

Bootstrap的理论基础是用经验分布代替真实分布。它不需要对数据分布做任何参数假设，因此被称为非参数方法。Bootstrap样本模拟了从总体中重复采样的过程，使我们能够评估统计量的采样变异性。

4.11.4 Bagging算法

Bagging（Bootstrap Aggregating的缩写）将Bootstrap采样和模型聚合结合起来。算法流程：从原始数据集生成 B 个Bootstrap样本 d_1, d_2, \ldots, d_B ，在每个Bootstrap样本 d_b 上独立训练一个模型 h(\cdot; d_b) ，通过某种聚合方式组合这些模型的预测

模型聚合的数学形式是：

h_{\text{ag}}(x) = \arg\min_{y} \sum_{b=1}^{B} L(h(x; d_b), y)

这个通用形式对于不同的损失函数有不同的具体实现。对于回归问题使用二次损失时，最优聚合是简单平均：

h_{\text{ag}}(x) = \frac{1}{B} \sum_{b=1}^{B} h(x; d_b)

这个结果很直观——在均方误差准则下，多个预测的平均是最优的组合方式。

对于分类问题使用0/1损失时，最优聚合是多数投票：每个模型为它认为最可能的类别投一票，最终预测是获得最多票数的类别。这种决策机制特别适合决策树，因为不同Bootstrap样本上训练的树会有不同的结构，从不同角度理解数据。有些树可能更关注某些特征，有些可能发现不同的交互模式，通过投票，我们综合了这些不同的视角。

4.11.5 袋外误差估计

Bagging的一个优雅特性是它提供了验证机制——袋外（Out-of-Bag, OOB）误差估计。Bootstrap中每个观测值约有36.8%的概率不出现在某个Bootstrap样本中。这意味着对于每个观测值，平均约有 B/3 个模型没有使用它进行训练。

袋外集合定义为：对于观测值 i ，它的OOB集合包含所有不含该观测值的Bootstrap样本对应的模型。我们可以用这些模型来预测观测值 i ，因为它们在训练时没有"见过"这个观测值。

以表格中的例子说明，观测值1没有出现在Bootstrap样本 d_1 和 d_2 中。因此，它的OOB预测由模型 h(x_1; d_1) 和 h(x_1; d_2) 的聚合给出。这个预测是很好的，因为这两个模型在训练时没有使用观测值1。

OOB误差通过对所有观测值计算其OOB预测误差并取平均得到：

\text{OOB Error} = \frac{1}{n}\sum_{i=1}^{n} L(y_i, h_{\text{OOB}}(x_i))

其中 h_{\text{OOB}}(x_i) 是观测值 i 的OOB预测。

这种方法的优美之处在于它近似了留一法交叉验证，但计算成本要低得多。在极限 B \to \infty 时，OOB误差等同于留一法交叉验证误差。这提供了对泛化性能的可靠估计，而不需要单独的验证集——这在数据量有限时特别有价值。

4.11.6 Bagging的性能特征

图清晰地展示了Bagging的效果。蓝色虚线表示原始单树的测试误差（约0.45），而绿色和橙色曲线分别表示使用Bagged树的两种聚合方式（共识和概率）的测试误差。随着Bootstrap样本数量的增加，Bagged树的误差迅速下降到约0.36，实现了约20%的性能提升。

Bagging通过平均化减少方差，但通常会略微增加偏差。对于决策树这种高方差、低偏差的模型，这种权衡通常是有利的。方差的减少远远超过偏差的小幅增加，导致整体预测性能的显著提升。

一个重要的观察是，增加Bootstrap样本的数量不会导致过拟合。从图中可以看出，测试误差在约50个Bootstrap样本后就稳定了，继续增加样本数量既不会改善也不会恶化性能。这与传统的模型复杂度不同——更多的Bootstrap样本不会增加模型容量，只是提供了更稳定的聚合估计。

实践中，通常使用100-500个Bootstrap样本就足够了。选择的原则是平衡计算成本和性能稳定性。由于各个模型可以并行训练，Bagging特别适合分布式计算环境。

贝叶斯分类器（图中的黑色虚线）代表了理论上的最优性能下界（约0.20）。虽然Bagging显著改善了单树的性能，但仍然与贝叶斯最优有差距，这激发了进一步的改进，如随机森林算法。

4.12 随机森林

4.12.1 核心动机

回顾Bagging中聚合模型的方差公式：

\text{Var}[\hat{h}_{\text{ag}}(x)] = \text{Var}[h(x; D_b)]\left(\frac{1}{B} + \frac{B-1}{B}\rho(h(x; D_1), h(x; D_2))\right)

这个公式揭示了关键洞察：聚合模型的方差不仅取决于个体模型的方差和模型数量 B，还严重依赖于模型间的相关系数 \rho。当 B 很大时，公式简化为 \text{Var}[h(x; D_b)] \cdot \rho，这意味着即使使用无限多的树，如果它们高度相关（\rho 接近1），方差减少的效果仍然有限。

Bootstrap样本可能产生高度相关的模型，这是Bagging的一个根本局限。虽然Bootstrap创造了数据的不同版本，但这些版本仍然来自同一个原始数据集，特别是当数据中存在一个非常强的预测变量时，大多数树都会选择这个变量作为顶层分割，导致树结构相似，相关性高。

4.12.2 随机特征选择

为了进一步降低树之间的相关性，随机森林在Bagging的基础上引入了额外的随机性源泉：每次分割时的随机特征选择。

具体机制是：当在某个节点构建树时，不是考虑所有 p 个解释变量，而是随机采样 \tilde{p} 个解释变量，然后只从这个子集中选择最佳分割。这种方法强制不同的树使用不同的变量组合，即使某个变量非常强大，它也不会出现在所有树的所有分割中。

参数 \tilde{p} 的选择对算法性能有重要影响。当 \tilde{p} = p 时，退化为经典的Bagged树，没有额外的随机性。常用设置是 \tilde{p} = \lfloor\sqrt{p}\rfloor，特别是对于分类问题。这个选择在随机性和信息保留之间取得了良好平衡。

\sqrt{p} 规则的直觉是：如果有100个特征，每次只考虑10个，这足以包含一些有信息的变量，但又足够小以创造多样性。这个经验法则在实践中表现出色，成为了许多软件包的默认设置。

4.12.3 决策边界的可视化比较

三幅图形象地展示了单个决策树、Bagged树和随机森林在同一二分类问题上的表现。数据点分为两类（深色和浅色），背景色表示模型的预测区域。

决策树展示了典型的轴平行矩形分割。决策边界是锯齿状的，反映了树的递归二分性质。边界过于复杂且不平滑，某些区域的分割可能是对训练数据噪声的过拟合。单个异常点可能创建一个专门的分割区域。

Bagged树的决策边界变得更加平滑和规则。通过平均多个树的预测，锯齿状的边界被"磨平"了。分类区域的形状更加合理，对个别异常点的敏感度降低。然而，边界仍然主要沿着某些主导方向，这反映了树之间仍存在相关性。

随机森林的决策边界最为平滑和自然。额外的随机性使得不同的树探索了特征空间的不同方面，产生了更加多样化的分割模式。当这些多样化的模式被平均时，结果是一个能够更好地逼近真实决策边界的平滑曲线。边界的形状不再被少数主导特征控制，而是反映了所有特征的综合贡献。

这种演进展示了方差减少的过程。单个决策树有高方差——小的数据变化会产生完全不同的边界。Bagging通过平均减少了这种不稳定性，但树间的相关性限制了改善程度。随机森林通过降低相关性，实现了更大程度的方差减少，产生了更稳定和可靠的决策边界。

4.12.4 模型可解释性的权衡

Bagging虽然显著提升了树的预测准确性，但产生的模型可解释性大大降低。图展示了原始树和Bagged森林中的多个树（b=1 到 b=5）。每棵树都有不同的结构，使用不同的变量和分割点。

原始的单个决策树可以轻松转换为一组if-then规则，每个预测都可以通过追踪从根到叶的路径来解释。而对于包含数百棵树的集成模型，理解为什么做出特定预测变得几乎不可能。

这种权衡反映了机器学习中的基本矛盾：简单模型易于理解但可能不够准确，复杂模型更准确但难以解释。在某些应用中（如医疗诊断、信贷决策），可解释性是法律或伦理要求，可能需要牺牲一些准确性。在其他应用中（如图像识别、推荐系统），准确性更重要，可以接受"黑盒"模型。

随机森林通过提供特征重要性度量，部分缓解了这个问题。虽然我们不能解释单个预测，但可以了解哪些特征对整体预测最重要。

4.12.5 特征重要性度量

随机森林虽然失去了单个决策路径的可解释性，但提供了全局的特征重要性度量，部分缓解了"黑盒"问题。有两种主要的重要性计算方法。

异质性减少方法

对于森林中的每棵树，计算给定解释变量 x^{(j)} 上的分割所带来的总异质性（不纯度）减少，表示为该树中总不纯度减少的比例。将这些比例在森林中所有树上取平均，得到 x^{(j)} 的重要性度量。

这个方法的直觉是：如果一个变量经常被用于分割，并且这些分割显著减少了不纯度，那么这个变量就很重要。重要性度量综合考虑了两个因素：变量被选择的频率（即使在随机特征选择下）和每次使用时的效果。

排列重要性

排列重要性是更加稳健和直观的方法。其基本思想是：如果一个特征很重要，那么破坏这个特征与目标变量的关系应该会显著降低模型性能。

具体计算过程如下。对森林中的每棵树，首先计算其在袋外（OOB）数据上的预测误差，记为\hat{R}_{\text{OOB}}^{\text{base}}。然后，对于特征x^{(j)}，在OOB数据中随机排列（打乱）其值，同时保持所有其他特征不变。这种排列破坏了x^{(j)}与目标变量Y之间的任何关系，同时保持了x^{(j)}的边际分布和其他特征的联合分布。使用排列后的数据重新计算OOB误差，记为\hat{R}_{\text{OOB}}^{\text{perm}}。

重要性度量是误差的增加：

\text{Importance}(x^{(j)}) = \frac{1}{B}\sum_{b=1}^{B}\left(\hat{R}_{\text{OOB},b}^{\text{perm}} - \hat{R}_{\text{OOB},b}^{\text{base}}\right)

在所有树上取平均得到特征x^{(j)}的排列重要性。

排列重要性的优势在于它直接测量了特征对预测准确性的贡献，而不仅仅是对树结构的贡献。它能够捕捉复杂的交互作用——如果一个特征只在与其他特征组合时才有用，排列它会破坏这种组合，导致性能下降。此外，排列重要性对特征的尺度不敏感，因为它只涉及排列操作，不依赖于特征的数值大小。

4.13 本章小结

本章系统介绍了基于树的方法，从单个决策树到强大的集成方法，展现了机器学习中模型演进的典型路径。

决策树采用递归分割的策略构建预测模型。算法在每个节点选择最优的特征和分割点，基于异质性（不纯度）度量的减少来评估分割质量。每次分割都将特征空间划分成更小的矩形区域，在每个区域内进行局部的参数估计。这种方法的优势在于能够自然地处理非线性关系和特征交互，同时保持高度的可解释性——每个预测都可以追溯到一系列简单的if-then规则。然而，决策树的主要弱点是高方差，对训练数据的小扰动非常敏感，以及相对较低的预测准确性，特别是在需要斜线或曲线决策边界的问题上。

Bagging方法通过集成多个模型来克服单个决策树的高方差问题。核心思想是利用Bootstrap采样创建训练数据的多个版本，在每个版本上训练一个模型，然后通过平均（回归）或投票（分类）聚合预测。数学分析表明，这种聚合能够显著减少方差而不增加偏差，特别适合像决策树这样的高方差低偏差学习器。Bagging的一个优雅特性是袋外（OOB）误差估计，它提供了验证机制，无需单独的验证集就能评估模型性能。

随机森林在Bagging的基础上引入了额外的随机性。通过在每次分割时只考虑随机选择的特征子集，随机森林进一步降低了树之间的相关性。方差分析表明，聚合模型的方差不仅取决于个体模型的方差，还严重依赖于模型间的相关性。双重随机性（Bootstrap采样加随机特征选择）创造了真正多样化的树集合，显著提升了预测性能。虽然随机森林牺牲了单个树的可解释性，但通过特征重要性估计，仍能提供对模型行为的全局洞察。

随机森林的成功启发了更多的集成方法，如梯度提升树（Gradient Boosting）和XGBoost，它们通过不同的方式组合决策树，在许多实际应用中取得了优异的性能。

分享

统计学习（整合版，第 1–4 章）

第一章 统计学习导论与线性回归回顾

1.1 统计学习基础

1.1.1 课程目标与结构

1.1.2 机器学习的定义与学科定位

1.1.3 监督学习的典型例子

房地产定价问题

手写字符识别问题

1.1.4 统计学习的应用领域

1.2 统计建模框架

1.2.1 数据的形式化表示

1.2.2 概率建模的核心思想

1.2.3 观测空间的定义

1.2.4 统计建模的完整框架

1.2.5 观测值的分布

1.2.6 统计模型的形式化定义

1.3 监督学习的统计模型

1.3.1 实例空间与标签空间

1.3.2 监督学习的概率框架

1.3.3 监督学习的目标

1.3.4 风险函数的定义

1.3.5 最优预测函数

1.4 经验风险最小化

1.4.1 从理论风险到经验风险

1.4.2 经验风险最小化原则

1.5 回归问题

1.5.1 回归的定义与术语

1.5.2 回归中的常用损失函数

1.5.3 二次损失与最优预测函数

1.5.4 候选函数族

1.6 最小二乘方法

1.6.1 最小二乘估计量的定义

1.6.2 模型评估指标

1.6.3 与最大似然估计的联系

1.7 线性回归

1.7.1 线性模型的设定

1.7.2 矩阵-向量记号

1.7.3 普通最小二乘估计量的闭式解

1.8 几何解释

1.8.1 列空间与投影的观点

1.8.2 投影的几何图示

1.8.3 投影矩阵的性质

1.8.4 杠杆分数

1.9 统计性质

1.9.1 统计假设

1.9.2 OLS估计量的基本性质

1.9.3 Gauss-Markov定理

1.9.4 正态性假设与分布理论

1.9.5 统计推断

1.10 本章小结

第二章 模型评估与选择

2.1 引言

2.1.1 回归问题的基本设定

2.1.2 统计建模视角

2.2 偏差-方差权衡

2.2.1 二次损失下的预测误差

2.2.2 期望预测误差与偏差-方差分解

2.2.3 偏差-方差权衡的本质

2.3 线性回归中的偏差-方差分析

2.3.1 线性回归的设定

2.3.2 设计点上的平均预测误差

2.3.3 偏差和方差的具体表现

2.4 泛化误差与模型评估

2.4.1 泛化误差的定义

2.4.2 经验风险的重用问题

2.4.3 过拟合现象

2.4.4 模型评估的完整图

2.5 交叉验证

2.5.1 训练-测试集划分

2.5.2 k折交叉验证

2.6 正则化回归

2.6.1 普通最小二乘法的局限性

高维数据的实例

2.6.2 正则化回归的基本思想

2.6.3 贝叶斯视角的解释

2.6.4 岭回归

岭回归系数路径

2.6.5 LASSO回归

2.6.6 正则化回归的约束形式

第一章统计学习导论与线性回归回顾

第二章模型评估与选择

第三章分类与核方法导论