监督学习

监督学习是机器学习中最常见、应用最广泛的算法，其核心特征就是训练数据有标签。

回归任务

监督学习最主要包括分类任务和回归任务。分类任务输出标签，回归任务输出数值。

我们以线性回归为例，讲解回归任务与相关重点概念。

学习算法

在机器学习基础中，我们已经提到过：如果一个计算机程序在任务T上的性能（由度量P衡量），随着经验E的增加而提升，则称该程序能够从经验中“学习”。

学习过程本身并非任务，我们的任务是得到完成任务的能力。比如说我们的目标是让机器人学会行走，那么行走便是我们的任务。

---

任务T

常见的机器学习任务包括：

1. 分类：根据给定输入来预测分类标签
2. 输入缺失分类：常见于医疗诊断（缺少病人的某项检查）、金融风控（用户没有填全资料）
3. 回归：根据给定输入来预测数值
4. 转录：比如OCR、语音识别
5. 机器翻译
6. 结构化输出：从杂乱的信息或文本中提取关键信息并填入模板
7. 异常检测：比如信用卡欺诈
8. 合成和采样：本质上还是结构化输出，只不过不需要限制输入和输出的唯一映射
9. 缺失值填补
10. 去噪
11. 密度估计、概率质量函数估计

---

性能度量P

为了评估机器学习算法的能力，我们必须设计其性能的定量度量。

常见的度量包括：

1. 准确率 accuracy
2. 错误率 error rate
3. 测试集 test set上的性能

---

经验E

根据学习过程中的不同经验，机器学习算法一般被分为无监督和监督算法。无监督算法参见无监督学习笔记。

监督学习算法训练含有很多特征的数据集，数据集中的每个样本都包含标签或目标；无监督学习则没有这些标签。

有时候，无监督学习和监督学习之间的界线是模糊的。比如说，原本我们要学习一个向量 \(\mathbf{x}\) 的联合分布（这是典型的无监督学习，比如密度估计）。通过 链式法则 ，我们可以把它拆解成 \(n\) 个条件概率问题。每一个 \(p(x_i \mid \dots)\) 其实都可以看作是一个监督学习问题（已知前 \(i-1\) 个特征，预测第 \(i\) 个特征）：

\[ p(\mathbf{x}) = \prod_{i=1}^{n} p(x_i \mid x_1, \dots, x_{i-1}) \]

又比如说，原本我们要解决的是预测标签 \(y\) 的监督学习问题。我们可以先用无监督的方法去学习 \(\mathbf{x}\) 和 \(y\) 的联合概率分布 \(p(\mathbf{x}, y)\)，然后通过贝叶斯公式推导出条件概率：

\[ p(y \mid \mathbf{x}) = \frac{p(\mathbf{x}, y)}{\sum_{y'} p(\mathbf{x}, y')} \]

尽管两者有重叠，但为了方便分类，传统上我们还是这样区分：

• 监督学习 ：解决回归、分类或结构化输出问题（目标明确）。
• 无监督学习 ：解决密度估计等其他任务（探索数据本身的结构）。

损失函数

线性回归是最基本也是最简单的机器学习算法，同时也是多层感知机的基本组成成分。

线性的意思就是说，我们假设输入和输出是线性关系的，那么我们可以写作：

\[ f_{\theta}(\boldsymbol{x}) = \boldsymbol{\theta}^{\text{T}}\boldsymbol{x} = \theta_1x_1 + \cdots + \theta_dx_d \]

为了方便计算，通常增加一个常数特征 \(x_0=1\)，这样就把截距项合并进了向量乘法里。在 \(d\) 维空间里，这个公式代表一个 \(d\) 维超平面 。它试图穿过所有数据点，找到最平直的规律。这个函数被叫做预测函数。

我们的目的是找到最小损失函数的一组参数，因此我们的重点将在损失函数上。

我们用平方损失（Squared Loss） 衡量模型在某一个数据点上的损失：

\[ \mathcal{L}(y_i, f_{\theta}(\boldsymbol{x}_i)) = \frac{1}{2}(y_i - f_{\theta}(\boldsymbol{x}_i))^2 \]

之所以用平方，是因为这样可以消除正负号的影响（预测高了和预测低了都是误差）。由于是二次方，误差越大，损失会呈爆炸式增长。这迫使模型必须重点关注那些离群太远的“坏点”。1/2的作用是数学上的优雅，当你对这个公式求导时，平方项抛下来的 \(2\) 会和 \(1/2\) 抵消，让最后的导数公式看起来更干净。

对于所有样本误差的平均值，我们使用均方误差 (Mean Squared Error, MSE) ：

\[ J(\boldsymbol{\theta}) = \frac{1}{2N} \sum_{i=1}^{N}(y_i - f_{\theta}(\boldsymbol{x}_i))^2 \]

我们的任务是找到一组最优的 \(\boldsymbol{\theta}\)，使得总损失最小。这就是公式里的：

\[ \min_{\theta} J(\boldsymbol{\theta}) \]

---

我们现在知道如何衡量损失，接着我们就需要考虑对于一组数据，我们如何找到最优的一组参数。由于线性回归几乎总是能找到最优解，因此我们可以直接求出解析解；对于数据量大的情况，我们也可以使用梯度下降，不断调整参数，来找到MSE最低的一组参数。

在线性回归中，总损失函数 \(J(\boldsymbol{\theta})\) 是一个“碗状”的凸函数。 想要找到这个碗的最低点，在数学上最直接的方法就是： 求导，并令导数为 0 。

为了计算方便，我们将所有数据打包成特征矩阵 \(\boldsymbol{X}\) 和标签向量 \(\boldsymbol{y}\)。 此时总损失可以写成简洁的矩阵形式：

\[ J(\boldsymbol{\theta}) = \frac{1}{2}(\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\theta})^{\text{T}}(\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\theta}) \]

对参数 \(\boldsymbol{\theta}\) 求偏导数。 经过一系列矩阵微分运算，得到导数公式：

\[ \frac{\partial J}{\partial \boldsymbol{\theta}} = -\boldsymbol{X}^{\text{T}}\boldsymbol{y} + \boldsymbol{X}^{\text{T}}\boldsymbol{X}\boldsymbol{\theta} \]

令导数为 0 ：

\[ 0 = -\boldsymbol{X}^{\text{T}}\boldsymbol{y} + \boldsymbol{X}^{\text{T}}\boldsymbol{X}\boldsymbol{\theta} \]

通过移项和矩阵求逆，我们得到了最终的解析解公式：

\[ \boldsymbol{\theta} = (\boldsymbol{X}^{\text{T}}\boldsymbol{X})^{-1}\boldsymbol{X}^{\text{T}}\boldsymbol{y} \]

这个公式就是解析解，也称为Normal Equation。其中\(X\)是特征，\(y\)是标签，将特征和标签代入，即可算出\(\min_{\theta} J(\boldsymbol{\theta})\)。

评价指标

相比于分类问题关注“对不对”，回归问题关注的是预测值与真实值之间的“差值”有多大。评估回归模型性能的核心在于衡量残差（Residuals） 的大小。以下是工业界和学术界最常用的评价指标：

（1）平均绝对误差 MAE，Mean Absolute Error，即预测值与真实值差值的绝对值的平均。

\[ MAE = \frac{1}{n} \sum_{i=1}^{n} |y_i - \hat{y}_i| \]

• 优点 ：单位与原始数据一致，含义直观（平均差了多少）。
• 缺点 ：在坐标轴上不连续，不可导，优化时计算稍复杂。

（2）均方误差 MSE，Mean Squared Error，即差值的平方的平均。

\[ MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 \]

• 特点 ：因为用了平方，它会放大离群点（Outliers）的影响。如果模型预测错了一个大数，MSE 会迅速飙升。

（3）均方根误差 RMSE，Root Mean Squared Error，即 MSE 的平方根。

\[ RMSE = \sqrt{\frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2} \]

• 意义 ：虽然保留了 MSE 惩罚异常值的特性，但通过开方让指标的 单位回到了原始量纲 ，更方便观察。

（4）决定系数 \(R^2\) Score

这是回归问题中最常用的“综合分数”，范围通常在 \([0, 1]\) 之间。

\[ R^2 = 1 - \frac{\sum (y_i - \hat{y}_i)^2}{\sum (y_i - \bar{y})^2} \]

• \(R^2 = 1\) ：模型完美预测。
• \(R^2 = 0\) ：模型水平和直接取平均值（瞎猜）一样。
• 意义 ：它反映了模型解释数据变动的比例。例如 \(R^2 = 0.8\) 意味着模型解释了数据中 80% 的方差。

（5）平均绝对百分比误差 MAPE

Mean Absolute Percentage Error，反映误差占真实值的比例。

\[ MAPE = \frac{100\%}{n} \sum_{i=1}^{n} \left| \frac{y_i - \hat{y}_i}{y_i} \right| \]

• 场景 ：适用于目标变量跨度很大的情况（例如预测股价或销量），10% 的误差比绝对误差更有参考价值。

欠拟合与过拟合

当我们找到能使损失函数最小化的一组参数后，我们就算是训练好了模型。然而，一个模型的好坏，不仅取决于它的损失函数值是否能很低，更取决于该模型是否能在未知的数据上做出正确的预测。换句话说，如果模型分析的太仔细，可能会出现过拟合（Overfitting）的情况；但如果没记住，则可能出现欠拟合（Underfitting） 的情况。

这种权衡来自于数据本身，因为机器学习是从数据中学习的。我们必须知道，数据中既有模式（Pattern），也有噪声（Noise）。我们的目标是让模型捕捉到模式，同时尽可能忽略噪声。

一般使用正则化约束、核方法、超参数、交叉验证等方法来防止欠拟合或过拟合，提升模型精度：

• 正则化直接作用在损失函数上，限制权重参数变得过大
• 核方法可以在欠拟合的情况下找到更加合适的切割方法
• 超参数可以人为控制模型复杂度
• 交叉验证则是在评估流程上防止过拟合

泛化能力

机器学习与单纯的“优化问题”之间的本质区别：

• 训练误差 (Training Error)： 模型在训练集上的错误率。我们的目标是降低它，这本质上是一个数学优化过程。
• 泛化误差 (Generalization Error)： 也叫 测试误差 。模型在从未见过的“新输入”上的误差期望。

机器学习真正的挑战不在于对旧数据的拟合，而在于对新数据的预测能力。

我们来对比一下两者。

训练误差：

\[ \frac{1}{m^{(\text{train})}} \left\| X^{(\text{train})} w - y^{(\text{train})} \right\|_2^2 \]

• \(m^{(\text{train})}\) : 训练样本的数量。
• \(X^{(\text{train})}\) : 训练集的输入矩阵。
• \(w\) : 模型的权重参数。
• \(y^{(\text{train})}\) : 训练集的真实标签。
• \(\| \dots \|_2^2\) : L2 范数的平方（即残差平方和）。
• 含义 ：这是我们在训练阶段通过算法（如梯度下降）去直接最小化的量。

测试误差：

\[ \frac{1}{m^{(\text{test})}} \left\| X^{(\text{test})} w - y^{(\text{test})} \right\|_2^2 \]

• 含义 ：形式上与训练误差一致，但数据来源于 测试集 。
• 关键点 ：在实际开发中，我们不能直接针对这个公式进行优化（因为训练时看不到测试集），但它才是衡量模型好坏的最终指标。

机器学习的任务是 通过最小化训练误差，间接地降低泛化误差 。之所以这种“间接”的方法能奏效，是因为我们假设了训练集和测试集遵循相同的 数据生成分布 (\(p_{\text{data}}\)) 。如果这两个分布不一致（例如用猫的照片训练去识别狗），泛化就会失败。

正则化约束

如果出现欠拟合的情况，我们可以增加模型的复杂度，增加训练轮数等。而如果训练过拟合，我们则一般需要使用正则化手段来解决。换句话说，正则化（Regularization）的目的在于干扰训练，防止过拟合。

我们来看线性回归的损失函数和解析解为：

\[ J(\boldsymbol{\theta}) = \frac{1}{2N} \sum_{i=1}^{N}(y_i - f_{\theta}(\boldsymbol{x}_i))^2 \]

\[ \boldsymbol{\theta} = (\boldsymbol{X}^{\text{T}}\boldsymbol{X})^{-1}\boldsymbol{X}^{\text{T}}\boldsymbol{y} \]

我们在损失函数中加入一个惩罚项，防止参数 \(\boldsymbol{\theta}\) 变得过大或过复杂。前一部分是标准的 MSE ，后一部分是 \(L_2\) 惩罚项 （即 \(\lambda \sum \theta_j^2\)）：

\[ J(\boldsymbol{\theta}) = \frac{1}{2}(\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\theta})^{\text{T}}(\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\theta}) + \lambda \|\boldsymbol{\theta}\|^2 \]

即使 \(\boldsymbol{X}^{\text{T}}\boldsymbol{X}\) 不可逆，加上 \(\lambda \boldsymbol{I}\) 后矩阵一定可逆。限制权重整体规模，让模型对噪声不敏感。进而我们可以得到\(L_2\)正则化的解析解：（也被称为Ridge Regression 岭回归）

\[ \boldsymbol{\theta} = (\boldsymbol{X}^{\text{T}}\boldsymbol{X} + \lambda \boldsymbol{I})^{-1}\boldsymbol{X}^{\text{T}}\boldsymbol{y} \]

\(L_2\) 正则化通过惩罚参数的平方和来防止过拟合，它倾向于让所有参数都变得很小，但不会变为 0。岭回归最迷人的地方在于它依然拥有一步到位的解析解。通过在对角线上加上这个“微小的岭”\(\lambda \boldsymbol{I}\) ，确保了矩阵一定可逆，从而保证模型一定有解。

---

\(L_1\) 正则化通过惩罚参数的绝对值之和来工作，它的最大特点是能够产生 稀疏解 ，即让不重要的特征权重直接归零。

\[ J(\boldsymbol{\theta}) = \frac{1}{2N} \sum_{i=1}^{N}(y_i - f_{\theta}(\boldsymbol{x}_i))^2 + \lambda \|\boldsymbol{\theta}\|_1 \]

前一部分是 MSE ，后一部分是 \(L_1\) 惩罚项 （即 \(\lambda \sum |\theta_j|\)）。实现 特征自动筛选 ，把无用的维度直接砍掉。

由于绝对值函数在 0 点处不可导，LASSO 没有封闭形式的解析解公式 。通常使用梯度下降法求解，其梯度包含符号函数：

\[ \nabla J(\boldsymbol{\theta}) = -\boldsymbol{X}^{\text{T}}\boldsymbol{y} + \boldsymbol{X}^{\text{T}}\boldsymbol{X}\boldsymbol{\theta} + \lambda \text{sgn}(\boldsymbol{\theta}) \]

其中 \(\text{sgn}(x)\) 在 \(x>0\) 时为 1，\(x<0\) 时为 -1。

---

上图展示了L1正则化与L2正则化约束的对比。

核方法

线性回归只能在数据中用一刀切的方式来分类，然而现实中的数据往往是纠缠在一起的，用直线切不开。为了处理复杂非线性数据，我们将原始特征 \(x\) 通过函数 \(\phi(x)\) 映射到高维空间。高维空间的维度可能极高甚至无穷（如高斯核），直接计算 \(\phi(x)\) 的坐标会导致计算量爆炸。利用内积（相似度） 来绕过显式的特征转换，直接在高维空间进行线性运算。

映射函数 \(\phi(\boldsymbol{x})\)的示意图如下所示：

一旦数据升到了高维，计算就会变得极其恐怖。如果你想计算两个高维向量的相似度（内积），你可能需要计算成千上万次的乘法。核方法（Kernel Methods） 的出现是为了“偷懒”。它的精髓在于：它能直接在低维空间通过简单的运算，算出两个样本在高维空间里的内积结果。

核方法在效果上实现了升维，即通过核函数\(K(\boldsymbol{x}_i, \boldsymbol{x}_j) = \phi(\boldsymbol{x}_i)^{\text{T}}\phi(\boldsymbol{x}_j)\)。只要你写出了核函数，就意味着你在模型里引入了对应的映射 \(\phi\)。核函数最迷人的地方在于，有些核（如 RBF 高斯核 ）对应的映射维度是无限维的。如果你试图手动升维到无限维，计算机直接就死机了。但核函数只需要计算一个简单的指数函数 \(\exp(-\gamma\|\boldsymbol{x}_i - \boldsymbol{x}_j\|^2)\)，就轻而易举地实现了无限维空间的线性计算。

---

下面我们来看一下核方法的推导过程。

在线性回归中，我们的目标是找到一个最优的参数 \(\boldsymbol{\theta}\)。当我们引入 \(L_2\) 正则化（岭回归）后，损失函数为：

\[ J(\boldsymbol{\theta}) = \frac{1}{2}\|\boldsymbol{y} - \boldsymbol{X}\boldsymbol{\theta}\|^2 + \frac{\lambda}{2} \|\boldsymbol{\theta}\|^2 \]

通过求导并令导数为 0，我们得到了那个著名的解析解：

\[ \boldsymbol{\theta} = (\boldsymbol{X}^{\text{T}}\boldsymbol{X} + \lambda \boldsymbol{I})^{-1}\boldsymbol{X}^{\text{T}}\boldsymbol{y} \]

这个公式是基于特征空间的——如果特征有 \(d\) 维，我们就需要求一个 \(d \times d\) 矩阵的逆。但这里隐藏着一个深层的数学联系：最优的权重向量 \(\boldsymbol{\theta}\) 实际上可以表示为训练样本的线性组合。 也就是说，\(\boldsymbol{\theta} = \boldsymbol{X}^{\text{T}}\boldsymbol{\alpha}\)。

为了证明这一点，我们需要利用矩阵恒等式：\((\boldsymbol{P}\boldsymbol{Q} + \lambda \boldsymbol{I})^{-1}\boldsymbol{P} = \boldsymbol{P}(\boldsymbol{Q}\boldsymbol{P} + \lambda \boldsymbol{I})^{-1}\)。

我们将解析解中的 \(\boldsymbol{P} = \boldsymbol{X}^{\text{T}}\) 和 \(\boldsymbol{Q} = \boldsymbol{X}\) 代入，神奇的变化发生了：

\[ \boldsymbol{\theta} = (\boldsymbol{X}^{\text{T}}\boldsymbol{X} + \lambda \boldsymbol{I})^{-1}\boldsymbol{X}^{\text{T}}\boldsymbol{y} = \boldsymbol{X}^{\text{T}}(\boldsymbol{X}\boldsymbol{X}^{\text{T}} + \lambda \boldsymbol{I})^{-1}\boldsymbol{y} \]

注意等式最右边的部分。我们定义 \(\boldsymbol{\alpha} = (\boldsymbol{X}\boldsymbol{X}^{\text{T}} + \lambda \boldsymbol{I})^{-1}\boldsymbol{y}\)，于是 \(\boldsymbol{\theta} = \boldsymbol{X}^{\text{T}}\boldsymbol{\alpha}\) 得到了严格证明。

当我们预测一个新样本 \(\boldsymbol{x}\) 时，代入新的 \(\boldsymbol{\theta}\) 表达式：

\[ f(\boldsymbol{x}) = \boldsymbol{x}^{\text{T}}\boldsymbol{\theta} = \boldsymbol{x}^{\text{T}}(\boldsymbol{X}^{\text{T}}\boldsymbol{\alpha}) = (\boldsymbol{x}^{\text{T}}\boldsymbol{X}^{\text{T}})\boldsymbol{\alpha} \]

展开来看，这其实是：

\[ f(\boldsymbol{x}) = \sum_{i=1}^{N} \alpha_i (\boldsymbol{x}^{\text{T}}\boldsymbol{x}_i) \]

这是一个本质的飞跃： 预测不再直接依赖于权重的累加，而是取决于新样本 \(\boldsymbol{x}\) 与训练集每一个样本 \(\boldsymbol{x}_i\) 之间的 相似度（内积） 。原本的线性回归，现在变成了“根据相似度对标签进行加权”。

当线性模型无法拟合非线性数据时，我们考虑将数据映射到高维空间 \(\phi(\boldsymbol{x})\)。按照上面的逻辑，所有的内积 \(\boldsymbol{x}^{\text{T}}\boldsymbol{x}_i\) 都会变成高维内积 \(\phi(\boldsymbol{x})^{\text{T}}\phi(\boldsymbol{x}_i)\)。

但显式地计算高维坐标是极其昂贵的，甚至是不可能的（比如映射到无限维）。于是我们引入 核函数（Kernel Function） ：

\[ K(\boldsymbol{x}, \boldsymbol{x}_i) = \phi(\boldsymbol{x})^{\text{T}}\phi(\boldsymbol{x}_i) \]

核技巧的精髓在于：我们直接定义内积的计算规则，而不必关心映射后的坐标。 例如高斯核（RBF），它在低维空间直接算出高维相似度，赋予了模型处理极其复杂边界的能力。

至此，我们完成了从普通线性回归到核方法的完整进化。我们定义 核矩阵 \(\boldsymbol{K}\)* ，其中 *\(K_{ij} = K(\boldsymbol{x}_i, \boldsymbol{x}_j)\)。

训练阶段 ：我们不再求解特征权重 \(\boldsymbol{\theta}\)，而是求解样本权重系数 \(\boldsymbol{\alpha}\)：

\[ \boldsymbol{\alpha} = (\boldsymbol{K} + \lambda \boldsymbol{I})^{-1}\boldsymbol{y} \]

预测阶段 ：对于新样本 \(\boldsymbol{x}\)，通过核函数计算它与所有训练样本的相似度，加权求和得出结果：

\[ f(\boldsymbol{x}) = \sum_{i=1}^{N} \alpha_i K(\boldsymbol{x}, \boldsymbol{x}_i) \]

核方法通过将“解析解重构”，把对特征的依赖转化为了对样本间内积的依赖。它让我们能够利用高维空间的强大拟合能力，同时又巧妙地规避了高维空间的计算成本。

超参数与验证集

在上面我们已经知道了一个模型的权重会随着数据集训练而不断迭代优化。除此之外，在训练过程中还有一些由人工提前制定的超参数（hyperparameter），他们在训练过程中保持固定不变。

超参数不是由学习算法本身通过训练集学习出来的。如果在训练集上优化超参数，算法总是会倾向于选择 最大可能的可选模型容量 。这会导致严重的过拟合。因此，我们需要构建验证集（Validation Set）。

最常见的构造方法就是从原始训练数据中分出两个部分：

• 训练集 （约 80%）：用于学习普通参数（权重）。
• 验证集 （约 20%）：用于估算泛化误差，并据此 更新/挑选超参数 。

因为我们根据验证集表现来挑选超参数，所以验证集上的误差会低于真实的泛化误差。所有的超参数优化完成后，必须通过测试集来获得对模型性能的公正评估。

---

当你为了防止模型过拟合而引入 \(L_2\) 正则化（岭回归）时，你引入了一个最重要的超参数： 正则化系数 \(\lambda\)* 。如果你不使用解析解，而是使用*梯度下降算法来求解 \(\boldsymbol{\theta}\)，那么你会遇到控制训练节奏的超参数：学习率、训练轮数、批量大小。

由于超参数无法自动更新，开发者需要通过实验来寻找最佳值，这个过程被称为调参（Tuning）。调参过程高度依赖于经验：

• 重复实验 ：指定一组超参数，训练模型并观察验证集表现；如果结果不佳，则调整超参数并重新初始化模型，重复优化流程。
• 平衡复杂度 ：超参数的数量会影响寻找最优模型的时间。过多的超参数会让调参过程变得非常困难。
• 经验价值 ：优秀的算法工程师能根据任务特点和数据分布，凭借经验快速确定超参数的调试范围。

虽然传统上超参数需要手动调整，但诸如自动机器学习（AutoML） 等领域的研究目标就是让计算机自动优化模型的结构和超参数，减少人工干预的成本。

交叉验证

交叉验证是从评估流程上防止我们被“运气”欺骗。将数据集随机分成 \(K\) 份，轮流进行训练和验证，最后取平均误差。它能确保我们选出的超参数是在“整本书”上表现都稳健的，而不是刚好在某几个特定题目（验证集）上蒙对了答案，从而防止过拟合。

模型选择

• NFL 告诉我们：没有无敌的算法，必须 根据问题选模型 。
• i.i.d. 告诉我们：只要 训练和测试环境一致 ，学习就有数学保障。
• 模型选择 告诉我们：要在拟合能力和稳定性之间寻找平衡。

没有免费午餐定理

NFL 定理在数学上定义了学习的 边界 。

假设我们有一个算法 \(a\)。我们在训练集 \(\mathcal{D}\) 上训练它，得到一个假设 \(h = a(\mathcal{D})\)。我们想知道它在测试集（未见过的数据）上的误差。

NFL 定理指出，如果对所有可能的目标函数 \(f\)（即所有可能的规律）求平均：

\[ \sum_{f} E_{gen}(a, f) = C \quad (\text{常数}) \]

无论你的算法是“深度神经网络”还是“扔硬币”，只要把所有可能的问题加起来，大家的得分是一样的。为什么现实中算法有优劣？因为 现实世界的规律只占“所有可能规律”中极小的一部分 。机器学习不是“炼金术”，它必须依赖于 归纳偏置（Inductive Bias） 。也就是说，你必须先假设世界是有某种规律的（比如平滑性、周期性），你的算法才有效。

独立同分布

既然 NFL 说没有万能算法，那我们要想让学习有意义，就必须给数据加限制。i.i.d. 就是最核心的限制。

假设数据集 \(\mathcal{D} = \{(x_1, y_1), \dots, (x_m, y_m)\}\)。

独立性(Independent)：

\[ P(x_1, x_2, \dots, x_m) = P(x_1)P(x_2)\dots P(x_m) \]

这意味着样本之间互不干扰。抽到第一个人的身高，不会影响抽到第二个人的身高。

同分布(Identically Distributed)：

\[ \forall i, \quad P(x_i, y_i) \sim p_{\text{data}} \]

这意味着训练集和测试集是从同一个口袋里掏出来的。

根据 大数定律 (Law of Large Numbers) ，当样本量 \(m\) 足够大时，我们在训练集上计算的平均误差（经验风险）会收敛于在整个分布上的期望误差（期望风险）：

\[ \frac{1}{m} \sum_{i=1}^{m} L(f(x_i), y_i) \xrightarrow{m \to \infty} \mathbb{E}_{(x,y) \sim p_{\text{data}}} [L(f(x), y)] \]

如果没有 i.i.d.，训练误差和测试误差之间就没有必然的数学联系，学习也就成了瞎猜。

偏差-方差分解

有了 i.i.d. 保证了“学习可行”，我们就要面对 NFL 提出的挑战：选哪个模型？ 这里的核心数学框架是 偏差-方差分解 (Bias-Variance Decomposition) 。

对于一个测试点 \(x\)，我们的预测值是 \(\hat{f}(x)\)，真实值是 \(y\)（包含噪声 \(\epsilon\)）。其期望误差可以拆解为：

\[ \text{Error}(x) = \mathbb{E}\left[(y - \hat{f}(x))^2\right] \]

通过代数运算，它可以分解为三部分：

1. \(\text{Bias}^2\) (偏差的平方)： \((\mathbb{E}[\hat{f}(x)] - f(x))^2\)
   • 衡量：模型预测的平均值与真实值之间的差距。
   • 代表：模型的 拟合能力 。
2. \(\text{Variance}\) (方差)： \(\mathbb{E}\left[(\hat{f}(x) - \mathbb{E}[\hat{f}(x)])^2\right]\)
   • 衡量：模型在不同训练集下表现的波动。
   • 代表：模型的 稳定性 。
3. \(\sigma^2\) (不可约误差)： 噪声。

模型选择的本质： 就是根据数据的规模和复杂度，寻找一个模型，使得 \(\text{Bias}^2 + \text{Variance}\) 的总和最小。

• 简单模型（如线性回归）： 高偏差、低方差。模型太固执，学不会复杂的规律（欠拟合）。
• 复杂模型（如深层神经网络）： 低偏差、高方差。模型太敏感，连训练集里的噪声都学进去了（过拟合）。

分类任务

逻辑回归（Logistic Regression） 是一个分类算法，并不是回归算法。所有的预测结果会被分类为一个二元分类，比如+1和-1。我们以逻辑回归为例，讲解分类任务与相关重点概念。

Sigmoid

逻辑回归的思路非常巧妙：

1. 使用线性回归模型来计算一个分数
2. 这个分数越高，模型就越倾向于认为样本属于+1类；分数越低，模型越倾向于认为样本属于-1类。若分数为0，则表示模型犹豫不决，在决策边界上。
3. 我们用Sigmoid函数（也叫做Logistic函数） 来把这个任意大小的分数压扁到(0,1)的区间内，这样它才能成为一个合法的概率值：

上图就是Sigmoid函数和图像。

---

Softmax

如果我们用Softmax替代Sigmoid，那么就可以得到多类别逻辑回归：

\[ \text{softmax} \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_K \end{bmatrix} = \frac{1}{\sum_{k=1}^{K} \exp(a_k)} \begin{bmatrix} \exp(a_1) \\ \exp(a_2) \\ \vdots \\ \exp(a_K) \end{bmatrix} \]

上述公式可以将一个实数向量\([a_1, a_2, \ldots, a_K]\)映射为一个概率分布：

\[ \text{softmax}(a_i) = \frac{\exp(a_i)}{\sum_{k=1}^{K} \exp(a_k)} \]

其特点是每个输出值都在(0,1)区间内，所有输出值之和为1等。常用于分类模型、多分类神经网络的输出层。

人工神经网络都可以把Softmax接在线性层（回归层）之后输出概率，从而实现分类。比如判断一张图是猫、狗还是猪，模型输出：猫(2.0), 狗(1.0), 猪(0.1)。这些数字很难直观解释。Softmax 函数的作用就是把这些分值压缩到 (0, 1) 之间，并且保证 所有类别的概率之和等于 1 。

最大似然估计

首先介绍一个数学概念：似然（likelihood）。

“概率”是已知参数预测结果，“似然”是已知结果推测参数。

举例来说，假设有一个硬币，我们讨论它的“正面朝上率” \(\theta\)。

• 概率 (Probability) ：
  • 前提 ：我已经知道硬币是均匀的（参数 \(\theta = 0.5\) 固定）。
  • 问题 ：我抛 10 次硬币，出现 7 次正面的可能性是多少？
  • 逻辑 ：参数 \(\to\) 数据（预测未来）。
• 似然 (Likelihood) ：
  • 前提 ：我不知道硬币均不均匀（参数 \(\theta\) 未知），但我已经抛了 10 次， 结果确实出现了 7 次正面 （数据固定）。
  • 问题 ：在这种情况下，这枚硬币均匀（\(\theta = 0.5\)）的可能性大，还是灌铅了（\(\theta = 0.7\)）的可能性大？
  • 逻辑 ：数据 \(\to\) 参数（反推真相）。

虽然似然和概率在日常生活中听起来差不多，但在公式里，它们其实用的是 同一个函数 ，只是变量变了：

\[ P(X|\theta) \]

• 当你固定参数 \(\theta\)，变动数据 \(X\) 时，它是 概率函数 。
• 当你固定观测到的数据 \(X\)，变动参数 \(\theta\) 时，它是 似然函数 。

---

在构建逻辑回归的数学大厦时，确定优化目标是至关重要的一步。对于概率分布问题，我们通常采用最大似然估计（Maximum Likelihood Estimation, MLE） 的思想，其核心在于寻找一组参数 \(\theta\)，使得模型在训练数据上预测出正确标签的概率达到最大。

具体而言，设共有 \(N\) 个样本 \(\boldsymbol{x}_1, \dots, \boldsymbol{x}_N\)，类别分别为 \(y_1, \dots, y_N\)。对于每一个样本 \(\boldsymbol{x}_i\)，当 \(y_i = 0\) 时，模型预测正确的概率为 \(1 - f_{\theta}(\boldsymbol{x}_i)\)；而当 \(y_i = 1\) 时，概率为 \(f_{\theta}(\boldsymbol{x}_i)\)。为了将这两种情形统一处理，我们得到单样本预测正确的概率表达式为 \(f_{\theta}(\boldsymbol{x}_i)^{y_i}(1 - f_{\theta}(\boldsymbol{x}_i))^{1-y_i}\)。假设样本之间是两两独立的，那么模型将所有样本全部分类正确的总概率即为似然函数：

\[ L(\theta) = \prod_{i=1}^{N} f_{\theta}(\boldsymbol{x}_i)^{y_i}(1 - f_{\theta}(\boldsymbol{x}_i))^{1-y_i} \]

为了方便计算并避免计算机处理连乘时可能出现的浮点数下溢问题，我们通常对似然函数取对数，转化为 对数似然（log-likelihood） ，将连乘运算转化为求和运算：

\[ l(\theta) = \log L(\theta) = \sum_{i=1}^{N} [y_i \log f_{\theta}(\boldsymbol{x}_i) + (1 - y_i) \log(1 - f_{\theta}(\boldsymbol{x}_i))] \]

由于对数函数是单调递增的，优化 \(l(\theta)\) 与 \(L(\theta)\) 会得到相同的参数结果。因此，我们的优化目标正式定为 \(\max_{\theta} l(\theta)\)。

为了找到使 \(l(\theta)\) 最大的参数，我们需要对其求梯度。利用 Sigmoid 函数的导数特性，对 \(l(\theta)\) 求梯度后可以得到：

\[ \nabla l(\theta) = \sum_{i=1}^{N} \left[ \frac{\nabla f_{\theta}}{f_{\theta}} y_i - \frac{\nabla f_{\theta}}{1 - f_{\theta}} (1 - y_i) \right] \]

代入 \(f_{\theta}(\boldsymbol{x}) = \sigma(\boldsymbol{\theta}^{\text{T}}\boldsymbol{x})\) 并利用 \(\nabla_{\theta}\sigma(\boldsymbol{\theta}^{\text{T}}\boldsymbol{x}) = \sigma(\boldsymbol{\theta}^{\text{T}}\boldsymbol{x})(1 - \sigma(\boldsymbol{\theta}^{\text{T}}\boldsymbol{x}))\boldsymbol{x}\) 进行化简，最终梯度的表现形式非常简洁：

\[ \nabla l(\theta) = \sum_{i=1}^{N} (y_i - \sigma(\boldsymbol{\theta}^{\text{T}}\boldsymbol{x}_i))\boldsymbol{x}_i \]

习惯上，我们将优化目标转化为最小化损失函数 \(J(\theta) = -l(\theta)\)。根据梯度下降算法，设学习率为 \(\eta\)，则 \(\theta\) 的迭代更新公式为：

\[ \theta \leftarrow \theta + \eta \nabla l(\theta) = \theta + \eta \sum_{i=1}^{N} (y_i - \sigma(\boldsymbol{\theta}^{\text{T}}\boldsymbol{x}_i))\boldsymbol{x}_i \]

在工程实现中，为了消除样本规模对学习率的影响并提高计算效率，我们通常会对样本取平均，并定义样本矩阵 \(\boldsymbol{X} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_N)^{\text{T}}\) 和标签向量 \(\boldsymbol{y} = (y_1, \dots, y_N)^{\text{T}}\)。此时，梯度的矩阵形式写为 \(\nabla J(\theta) = -\nabla l(\theta) = \boldsymbol{X}^{\text{T}}(\sigma(\boldsymbol{X}\theta) - \boldsymbol{y})\)，相应的参数更新矩阵形式则为：

\[ \theta \leftarrow \theta + \eta \boldsymbol{X}^{\text{T}}(\boldsymbol{y} - \sigma(\boldsymbol{X}\theta)) \]

为了进一步提升模型的泛化能力，我们会在模型中加入 \(L_2\) 正则化约束 。设定正则系数为 \(\lambda\) 后，完整的优化目标与迭代公式变为：

\[ \min_{\theta} J(\theta) = \min_{\theta} -l(\theta) + \frac{\lambda}{2} \|\theta\|_2^2 \]

\[ \nabla J(\theta) = -\boldsymbol{X}^{\text{T}}(\boldsymbol{y} - \sigma(\boldsymbol{X}\theta)) + \lambda\theta \]

\[ \theta \leftarrow (1 - \lambda\eta)\theta + \eta \boldsymbol{X}^{\text{T}}(\boldsymbol{y} - \sigma(\boldsymbol{X}\theta)) \]

逻辑回归的损失函数是凸函数，这意味着无论从哪个初始参数开始，梯度下降的轨迹最终都能收敛到最优解 \(\theta^*\)。

当面对多分类任务时，逻辑回归需要扩展为 Softmax 回归 。我们采用柔性最大值函数将线性预测结果 \(\boldsymbol{\theta}^{\text{T}}\boldsymbol{x}\) 映射到多分类概率上，其定义为：

\[ \sigma(z)_i = \frac{e^{z_i}}{\sum_{j=1}^{K} e^{z_j}} \]

这里 \(z\) 是一个 \(K\) 维的得分向量，每一维 \(z_j \in (-\infty, +\infty)\) 代表第 \(j\) 类的得分。Softmax 函数能将得分映射到 \((0, 1)\) 区间且保证所有类别概率之和为 1，这使其可以被视作一个离散随机变量的概率分布。

值得注意的是，Softmax 函数保留了原始得分的大小顺序，且通过指数运算避免了直接取最大值导致的不可导问题。事实上，当类别数 \(K=2\) 时，Softmax 函数会退化为逻辑回归函数。换言之，逻辑回归只是 Softmax 函数在二分类前提下的一个特例。

交叉熵损失函数

基于最大似然估计原理，我们使用交叉熵损失函数来作为逻辑回归的损失函数。

在分类任务中，模型的输出不再是“月薪 20k”这种具体数值，而是“概率”（比如 80% 的概率是猫）。

• 真实情况（\(y\)） ：通常是一个“One-hot”向量。比如真的是猫，就是 \([1, 0]\)。
• 模型预测（\(\hat{y}\)） ：是一个概率分布。比如模型说是猫的概率是 \([0.8, 0.2]\)。

交叉熵的任务就是衡量这两组概率分布之间的“距离”。如果预测得越准，交叉熵就越小；预测得越离谱，交叉熵就越大。

交叉熵损失函数（Cross-Entropy Loss）如下：

\[ L = -[y \ln(\hat{y}) + (1-y) \ln(1-\hat{y})] \]

其中\(y\)是真实标签，\(\hat{y}\)是预测概率。作用如下：

\[ L = - \big[ \underbrace{y}_{\text{样本真实分布}} \cdot \underbrace{\log(\hat{y})}_{\text{模型预测似然}} + \underbrace{(1 - y)}_{\text{补集真实分布}} \cdot \underbrace{\log(1 - \hat{y})}_{\text{补集预测似然}} \big] \]

假设我们要算的是一个“程序员是否能拿到Offer”的分类判断，在式子中其具体含义就是：

\[ L = - \big[ \underbrace{y}_{\text{真实：拿没拿}} \cdot \underbrace{\log(\hat{y})}_{\text{对成功信心的惩罚}} + \underbrace{(1 - y)}_{\text{真实：拒没拒}} \cdot \underbrace{\log(1 - \hat{y})}_{\text{对失败信心的惩罚}} \big] \]

MSE计算的是预测值和真实值之间的物理距离，而交叉熵计算的是预测概率和真实分布之间的信息差异。之所以用交叉熵损失函数来作为分类任务的损失函数，而不是用MSE（均方误差），是因为当预测错的离谱的时候，MSE最大也就是接近1，然而交叉熵可以让损失达到很大的数值，从而让模型调整参数的时候朝正确的方向更多的调整。

评价指标

在机器学习的分类问题中，评估模型好坏不能只看“准确率”。根据数据的分布（是否平衡）以及业务对错误容忍度的不同，我们需要从多个维度进行评价。

在讨论具体指标前，必须理解混淆矩阵。它记录了模型预测值与真实值的匹配情况：

• TP (True Positive) ：真阳性，预测为正，实际也为正。
• TN (True Negative) ：真阴性，预测为负，实际也为负。
• FP (False Positive) ：假阳性（误报），预测为正，实际为负。
• FN (False Negative) ：假阴性（漏报），预测为负，实际为正。

最常用的核心指标包括：

（1）准确率 (Accuracy) 表示模型预测正确的样本占总样本的比例，是最直观的指标：

\[ Accuracy = \frac{TP + TN}{TP + TN + FP + FN} \]

但在样本不平衡时（例如 99% 的样本是负样本），准确率会产生严重误导，因此需要引入精确率和召回率。

（2）精确率 (Precision) 又称查准率，表示在模型预测为正的样本中，真正为正的比例。它适用于对“误报”敏感的场景，如垃圾邮件过滤，为了不把正常邮件误判，需要极高的精确率：

\[ Precision = \frac{TP}{TP + FP} \]

（3）召回率 (Recall) 又称查全率，表示在所有实际为正的样本中，被模型正确预测出来的比例。它适用于对“漏报”敏感的场景，如癌症检测或地震预警，目标是尽可能抓取所有正例：

\[ Recall = \frac{TP}{TP + FN} \]

（4）F1-Score 是精确率和召回率的调和平均数。由于两者往往是矛盾的（Trade-off），F1 值提供了一个综合权衡的参考标准：

\[ F1 = 2 \cdot \frac{Precision \cdot Recall}{Precision + Recall} \]

（5）ROC 曲线与 AUC 值 提供了更高维度的评估。ROC 曲线以假阳性率 (FPR) 为横轴，真阳性率 (TPR) 为纵轴，反映模型在不同阈值下的表现。AUC 是曲线下的面积，其值越接近 1 代表模型分类能力越强，且该指标对样本类别是否平衡不敏感。

（6）PR 曲线 (Precision-Recall Curve) 以召回率为横轴，精确率为纵轴。当数据集存在严重类别不平衡时（正样本极少），PR 曲线通常比 ROC 曲线更能真实地反映出模型的性能优劣。

案例应用

我们来看一个具体的案例，并讲解如何应用上面提到的若干个公式。

我们假设这样一个场景：预测一名程序员的“面试结果” 。

我们要观察的三个特征（自变量）分别是：

1. \(x_1\)： 刷题数 （如 500 题）
2. \(x_2\)： 项目经验 （如 3 个）
3. \(x_3\)： 工龄 （如 5 年）

每个特征对应一个 权重 (\(w\)) ，外加一个 截距 (\(b\)) 。

假设模型已经学到了参数：\(w_1=0.1, w_2=2, w_3=1, b=-10\)。

那么我们就可以根据线性回归，导入该程序员的特征值，获得预测结果：

\[ z = w_1x_1 + w_2x_2 + w_3x_3 + b = 51 \]

即该候选人的预测面试得分为51分。

---

逻辑回归就是在线性回归结果的基础上，将该结果转变为一个范围在0和1之间的函数。我们假设结果只有两种：拿 Offer (\(1\)) 或 拒信 (\(0\))。把刚才线性回归得到的原始分 \(z=51\) 扔进 Sigmoid 函数：

\[ P(Offer) = \frac{1}{1 + e^{-z}} = \frac{1}{1 + e^{-51}} \]

因为 \(51\) 很大，\(e^{-51}\) 趋近于 \(0\)。拿 Offer 的概率约为 99.9% 。分类角度来看，我们得出的分类预测结果就是：拿offer。

---

Softmax可以多分类，比如假设该程序员拿 Offer 后，要确定职级：初级、中级、高级。

这时，模型会有 三组不同的参数 （针对每个级别各有一套评分标准）：

• \(z_{初级} = 10\)（分低）
• \(z_{中级} = 30\)（分中）
• \(z_{高级} = 51\)（刚才算出的高分）

\[ P(高级) = \frac{e^{51}}{e^{10} + e^{30} + e^{51}} \]

由于 \(e^{51}\) 远大于其他项。模型几乎 100% 确定该人应定级为 高级 。

---

现实中，你看到这个候选人（500题/3项目/5年） 拿到了拒信 (\(y=0\)) 。但是刚才算出来的概率 \(P(Offer) = 0.999\)。这时我们发现，模型预测他稳拿 Offer，结果人家被拒了。这说明你的 \(w\) 和 \(b\) 设错了。

既然真实事实是“被拒”，那么“被拒”的概率就是 \(1 - 0.999 = 0.001\)。MLE 的目标是让 这个真实发生的概率 (\(0.001\)) 变大 。为了让 \(0.001\) 变大，算法会通过调整后，下一次模型算出的 \(z\) 就会变小，\(P(Offer)\) 就会降低。当模型参数使得“被拒”的概率看起来很合理（比如 \(0.9\)）时，MLE 就成功了。 梯度下降 ，强行把 \(w_1, w_2, w_3\) 调小，或者把 \(b\) 调得更负（比如 \(b = -100\)）。

常见监督学习算法/模型总结

下面列举一些常见的算法，并说明他们的损失函数与最优参数解法基本思路。具体的模型如果有学习需要，请参见对应的具体的章节笔记。

广义线性模型

广义线性模型（Generalized Linear Model，简称 GLM ）是线性回归的一种灵活推广。普通的线性回归要求数据必须服从 正态分布 ，且自变量和因变量之间是直线的关系。但在现实世界中，很多数据不听话（比如：邮件是不是垃圾邮件、某路口的事故发生次数），GLM 正是为了处理这些“不规则”数据而生的。

线性回归、逻辑回归等都属于广义线性模型。

线性回归

逻辑回归

双线性模型

假设我们有两个向量输入 \(\mathbf{x} \in \mathbb{R}^m\) 和 \(\mathbf{y} \in \mathbb{R}^n\)。一个标准的双线性映射可以表示为：

\[ f(\mathbf{x}, \mathbf{y}) = \mathbf{x}^\top \mathbf{W} \mathbf{y} \]

其中，\(\mathbf{W} \in \mathbb{R}^{m \times n}\) 是一个权重矩阵。

• 线性性体现： 如果固定 \(\mathbf{y}\)，函数对 \(\mathbf{x}\) 是线性的；如果固定 \(\mathbf{x}\)，函数对 \(\mathbf{y}\) 也是线性的。
• 交互项： 展开后，它实际上计算了所有可能的 \(x_i y_j\) 的加权和。

普通的线性模型（如 \(y = w_1x_1 + w_2x_2\)）假设变量之间是独立的。但在现实中，很多因素是相互影响的。在计算机视觉中，著名的“双线性模型”论文（Tenenbaum & Freeman）提出：

• 因子 A： 字母的 内容 （例如它是 'A' 还是 'B'）。
• 因子 B： 字母的 字体风格 （例如斜体还是粗体）。最终生成的图像是这两者的“乘积”效应。单靠线性加法（风格+内容）无法完美还原这种复杂的形变。

常见的应用场景还包括：

• 矩阵分解（Matrix Factorization）：用户的兴趣向量为 \(\mathbf{u}\)。物品的特征向量为 \(\mathbf{v}\)。用户对物品的评分预测为 \(r = \mathbf{u}^\top \mathbf{v}\)。
• 在深度学习（尤其是细粒度图像分类）中，为了捕捉特征图（Feature Map）中不同通道之间的空间相关性，会使用双线性池化：将同一个特征图在每个像素点上的特征向量与自身（或另一个特征图）做外积：\(\mathbf{z} = \mathbf{f} \mathbf{f}^\top\)。这能帮助模型识别非常微妙的特征，比如鸟类羽毛的特定纹理。
• 在早期的关系抽取或语义解析中，常用双线性变换来衡量两个实体（主语和宾语）之间的某种关系。

KNN算法

KNN算法是机器学习算法中最入门的算法，其原理十分简单，我们就从KNN开始，逐步学习机器学习的各个算法。神经网络架构相关的算法被统称为深度学习算法，参见深度学习章节。

KNN（K-Nearest Neighbors，K-最近邻算法） 不仅可以用于分类任务，也可以用于回归任务。

KNN 的核心逻辑是让当前样本的分类服从邻居中的多数分类。其中，\(K\) 的取值至关重要：

• \(K\) 取值太小： 分类结果容易受到待分类样本周围个别噪声数据的影响。
• \(K\) 取值太大： 可能将远处一些不相关的样本包含进来。 因此，应根据数据集动态调整 \(K\) 的大小。

KNN既可以用于回归，也可以用于分类。

对于分类任务，设已分类样本集合为 \(\boldsymbol{x}_0\)。对于待分类样本 \(\boldsymbol{x}\)，定义其邻居 \(N_K(\boldsymbol{x})\) 为 \(\boldsymbol{x}_0\) 中与 \(\boldsymbol{x}\) 距离最近的 \(K\) 个样本 \(\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_K\) 组成的集合。这些样本对应的类别分别为 \(y_1, y_2, \dots, y_K\)。统计集合 \(N_K(\boldsymbol{x})\) 中类别为 \(j\) 的样本数量，记为 \(G_j(\boldsymbol{x})\)：

\[ G_j(\boldsymbol{x}) = \sum_{\boldsymbol{x}_i \in N_K(\boldsymbol{x})} \mathbb{I}(y_i = j) \]

其中，\(\mathbb{I}(p)\) 是指示函数，当 \(p\) 为真时 \(\mathbb{I}(p)=1\)，反之为 \(0\)。最终，\(\boldsymbol{x}\) 的类别 \(\hat{y}(\boldsymbol{x})\) 判断为使 \(G_j(\boldsymbol{x})\) 最大的类别：

\[ \hat{y}(\boldsymbol{x}) = \arg \max_j G_j(\boldsymbol{x}) \]

---

对于回归任务，对于样本 \(\boldsymbol{x}\)，预测其对应的实数值 \(y\)。KNN 考虑 \(K\) 个邻居点 \(\boldsymbol{x}_i \in N_K(\boldsymbol{x})\)，将这些样本点对应的实数值 \(y_i\) 进行加权平均，得到预测结果 \(\hat{y}(\boldsymbol{x})\)：

\[ \hat{y}(\boldsymbol{x}) = \sum_{\boldsymbol{x}_i \in N_K(\boldsymbol{x})} w_i y_i, \quad \sum_{i=1}^K w_i = 1 \]

权重 \(w_i\) 代表邻居的重要性。常见的设置方法包括：

• 令所有 \(w_i = \frac{1}{K}\)（简单平均）。
• 根据距离设置权重（如权重与距离成反比）。
• 将权重作为模型参数通过学习得到。

---

我们来看一个KNN回归的例子——色彩迁移

我们知道RGB记录了三原色的色彩信息。计算机中还使用LAB来表示颜色，其中L代表亮度（light），A表示红绿方向的分量，B表示黄蓝方向的分量。简单来说，LAB主要记录亮度，这是为了模拟人类感知的。

我们可以利用LAB来完成色彩迁移。假设我们有一张黑白色的图片A，以及一张带有色彩的图片B。A中的LAB信息里只有L而没有AB；B中的LAB信息是全的。我们可以根据B的L与AB色彩的映射关系，来为A上色。

在这个过程中，L就是X，AB就是Y。我们把LAB的信息输入到model中，就可以train出来L和AB的映射关系。在此基础上，每一个L的值，都将对应一个AB值。

\[ f(L) \rightarrow (A, B) \]

我们可以用sklearn做一个快速的training：

knn = KNeighborsRegressor(n_neighbors=25, weights='distance', n_jobs=-1)
knn.fit(X_train, y_train)

具体来说，在黑白图片中有一个x点，其亮度L=50；然后我们在彩色图片中的几万个像素点中，挑出亮度最接近50的像素点，取25个，然后进行平均值，作为黑白图片x点的预测。weight='distance'表示颜色更接近的像素点将有更大的话语权，也就是说这25个像素点的色彩并不是直接取平均值的。

朴素贝叶斯

• 损失函数： 无显式损失函数 。
  • 它是一种生成模型，目标是最大化后验概率 \(P(Y|X)\)。
• 最小参数解法： 计数与频率估计 。
  • 参数求解就是计算先验概率和条件概率的经验估计（即查表计数）。为了防止概率为 0，通常引入 拉普拉斯平滑 (Laplace Smoothing) 。

SVM

• 损失函数： 合页损失 (Hinge Loss) + \(L_2\) 正则项。
  • 公式表达：\(L(w, b) = \sum \max(0, 1 - y_i(w^Tx_i + b)) + \lambda ||w||^2\)。
• 最小参数解法： 二次规划 (Quadratic Programming) 。
  • 通常转化为对偶问题，利用 SMO 算法 (Sequential Minimal Optimization) 迭代求解拉格朗日乘子。

决策树 (Decision Tree)

决策树是一种直观且强大的监督学习算法，既可用于分类也可用于回归。它的核心思想是通过一系列 if-else 判断将数据空间递归地划分为子区域，最终形成一棵树形结构。决策树的最大优势在于可解释性极强——你可以清楚地看到模型做出每个决策的依据。

分裂准则

决策树在每个节点上需要选择一个特征和一个阈值进行分裂。选择的依据是分裂后子节点的"不纯度"下降最多。不同的不纯度度量方法衍生出了不同的决策树算法。

（1）信息增益 (Information Gain) — ID3算法

信息增益基于信息熵（Entropy） 的概念。对于一个含有 \(K\) 个类别的数据集 \(S\)，其信息熵定义为：

\[ H(S) = -\sum_{k=1}^{K} p_k \log_2 p_k \]

其中 \(p_k\) 是第 \(k\) 类样本在 \(S\) 中的比例。熵越高，数据越"混乱"；熵为0表示数据完全纯净（只含一个类别）。

选择特征 \(A\) 对数据集 \(S\) 进行分裂后的信息增益为：

\[ \text{Gain}(S, A) = H(S) - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v) \]

ID3算法在每次分裂时选择信息增益最大的特征。但信息增益有一个缺陷：它偏好取值数目多的特征（极端情况下，如果用"ID"作为特征，每个样本一个分支，信息增益最大但毫无泛化能力）。

（2）信息增益率 (Gain Ratio) — C4.5算法

C4.5通过引入分裂信息 (Split Information) 来惩罚取值过多的特征：

\[ \text{GainRatio}(S, A) = \frac{\text{Gain}(S, A)}{H_A(S)} \]

其中 \(H_A(S) = -\sum_{v} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}\) 是特征 \(A\) 本身的熵。取值越多的特征，\(H_A(S)\) 越大，从而惩罚了信息增益的偏好。

（3）基尼系数 (Gini Impurity) — CART算法

CART (Classification and Regression Tree) 使用基尼系数作为不纯度度量：

\[ \text{Gini}(S) = 1 - \sum_{k=1}^{K} p_k^2 \]

基尼系数的直观含义是：从数据集中随机抽取两个样本，它们属于不同类别的概率。基尼系数越小，数据集纯度越高。

CART是目前最常用的决策树算法（Scikit-learn默认使用CART）。与ID3/C4.5的多叉树不同，CART构建的是二叉树——每次分裂只产生两个子节点。

（4）回归树的分裂准则

对于回归任务，CART使用均方误差（MSE） 作为分裂准则。对于节点 \(t\) 中的样本集合 \(S_t\)，其MSE为：

\[ \text{MSE}(S_t) = \frac{1}{|S_t|} \sum_{i \in S_t} (y_i - \bar{y}_t)^2 \]

其中 \(\bar{y}_t\) 是节点 \(t\) 中所有样本目标值的均值。选择使分裂后加权MSE下降最多的特征和阈值。

剪枝 (Pruning)

如果让决策树自由生长，它会不断分裂直到每个叶节点只包含一个样本，这必然导致严重的过拟合。剪枝是控制决策树复杂度的核心手段。

• 预剪枝 (Pre-pruning)：在树生长过程中提前停止。常用条件包括： * 设置最大深度 (max_depth) * 设置叶节点最少样本数 (min_samples_leaf) * 设置分裂所需最少样本数 (min_samples_split) * 设置最小不纯度下降阈值

• 后剪枝 (Post-pruning)：先让树完全生长，再自底向上地剪去那些对验证集性能贡献不大的子树。CART使用代价复杂度剪枝 (Cost-Complexity Pruning)，其目标函数为：

\[ C_\alpha(T) = \sum_{t=1}^{|T|} N_t \cdot \text{Impurity}(t) + \alpha |T| \]

其中 \(|T|\) 是叶节点数，\(\alpha\) 是正则化参数。\(\alpha\) 越大，剪枝越激进，树越简单。

决策树的优缺点

优点	缺点
可解释性强，可以可视化	容易过拟合（需要剪枝）
不需要特征标准化	对数据微小变化敏感（高方差）
能处理数值和类别特征	决策边界是轴对齐的（不擅长捕捉斜线关系）
能自动处理缺失值（CART）	贪心算法，无法保证全局最优

决策树的高方差问题——训练数据的微小变化可能导致完全不同的树结构——正是集成方法（Random Forest、Gradient Boosting）要解决的核心问题。

集成学习 (Ensemble Learning)

集成学习的核心思想是"三个臭皮匠顶个诸葛亮"——将多个弱学习器组合成一个强学习器。根据组合策略的不同，集成学习主要分为两大流派：

流派	核心思想	基学习器关系	代表算法
Bagging	并行训练，投票/平均	独立、并行	Random Forest
Boosting	串行训练，逐步修正	依赖、串行	AdaBoost, GBDT, XGBoost, LightGBM

随机森林 (Random Forest)

随机森林是Bagging思想与决策树的结合，由Leo Breiman于2001年提出。它通过构建大量决策树并汇总预测结果来降低模型的方差。

核心机制：

1. Bootstrap采样：从原始数据集中有放回地抽取 \(N\) 个样本（约63.2%的原始样本会被选中，剩余的称为 OOB样本 (Out-of-Bag)）
2. 随机特征子集：在每个节点分裂时，不使用全部 \(d\) 个特征，而是随机选取 \(m\) 个特征（通常分类任务取 \(m = \sqrt{d}\)，回归任务取 \(m = d/3\)）
3. 独立生长：每棵树不剪枝，独立生长到最大深度
4. 聚合预测：分类任务用多数投票（Majority Voting），回归任务用均值

为什么随机森林有效？

设单棵树的方差为 \(\sigma^2\)，树与树之间的相关系数为 \(\rho\)。则 \(n\) 棵树集成后的方差为：

\[ \text{Var} = \rho \sigma^2 + \frac{1 - \rho}{n} \sigma^2 \]

随机森林通过样本随机和特征随机两重随机性来降低 \(\rho\)（树之间的相关性）。当 \(\rho\) 较小时，增加树的数量 \(n\) 可以有效降低第二项，从而降低整体方差。这就是为什么随机森林几乎不会过拟合——增加更多的树只会让方差继续下降（或持平），不会变差。

OOB评估：每棵树的OOB样本可以用来评估该树的泛化性能，汇总所有树的OOB评估结果即可得到整个模型的无偏估计，无需额外的验证集。

实践要点：

• 随机森林对超参数不敏感，默认参数通常就能获得不错的效果
• 可以通过OOB误差或特征重要性来辅助特征选择
• 天然支持并行计算（每棵树独立构建）
• 在表格型数据的分类和回归任务上，仍然是非常强的baseline

梯度提升树 (Gradient Boosting Decision Tree)

GBDT是Boosting流派的代表，由Jerome Friedman于1999年提出。与Bagging并行构建弱学习器不同，Boosting是串行的——每棵新树都试图纠正前面所有树的集体错误。

核心思想：

GBDT将模型的优化过程看作在函数空间中做梯度下降。设当前模型为 \(F_{t-1}(x)\)，第 \(t\) 棵树 \(f_t(x)\) 需要拟合的目标是损失函数关于当前模型预测值的负梯度：

\[ r_{ti} = -\frac{\partial L(y_i, F_{t-1}(x_i))}{\partial F_{t-1}(x_i)} \]

当损失函数为MSE时，负梯度恰好等于残差 \(y_i - F_{t-1}(x_i)\)，这也是"梯度提升"名字的直观来源。

更新过程为：

\[ F_t(x) = F_{t-1}(x) + \eta \cdot f_t(x) \]

其中 \(\eta\) 是学习率（shrinkage），通常设为一个较小的值（如0.01-0.1）。较小的学习率配合更多的树可以获得更好的效果，但训练时间更长。

XGBoost

XGBoost (eXtreme Gradient Boosting) 由陈天奇于2016年提出，是GBDT的高效工程实现和算法改进。XGBoost在Kaggle竞赛中大放异彩，至今仍是表格型数据竞赛和工业应用中最常用的模型之一。

相比GBDT的核心改进：

（1）二阶泰勒展开

GBDT只使用损失函数的一阶导数（梯度），而XGBoost同时使用了一阶导 \(g_i\) 和二阶导 \(h_i\)，对损失函数进行二阶泰勒展开：

\[ L^{(t)} \approx \sum_{i=1}^{N} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t) \]

其中：

• \(g_i = \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}\) 是损失对预测值的一阶导数
• \(h_i = \frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2}\) 是损失对预测值的二阶导数

二阶信息提供了损失函数曲面的曲率信息，类似于Newton法相对于梯度下降法的优势，使得每一步更新更加精确，收敛更快。

（2）正则化项

XGBoost在目标函数中显式加入了树的复杂度惩罚：

\[ \Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 \]

其中 \(T\) 是叶节点个数，\(w_j\) 是第 \(j\) 个叶节点的权重。\(\gamma\) 惩罚叶节点数量（鼓励更简单的树），\(\lambda\) 是L2正则化系数（限制叶节点权重的大小）。

（3）最优叶节点权重

将目标函数对叶节点权重 \(w_j\) 求导并令其为0，可以得到每个叶节点的最优权重：

\[ w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \]

以及该叶节点对目标函数的贡献（用于评价分裂增益）：

\[ \text{Score}_j = -\frac{1}{2} \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} \]

（4）分裂增益

XGBoost通过比较分裂前后的目标函数值来决定是否分裂：

\[ \text{Gain} = \frac{1}{2} \left[ \frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma \]

当 Gain > 0 时才执行分裂。\(\gamma\) 起到了预剪枝的效果。

（5）工程优化

• 列采样 (Column Subsampling)：类似随机森林的特征随机，进一步降低过拟合
• 缺失值处理：自动学习缺失值应该分到左子树还是右子树
• 加权分位数草图 (Weighted Quantile Sketch)：近似算法用于处理大规模数据
• 缓存优化和并行计算：特征预排序后可以并行计算每个特征的最佳分裂点

LightGBM

LightGBM 由微软于2017年提出，是XGBoost的有力竞争者。它在保持精度的同时，训练速度通常比XGBoost快数倍到数十倍，尤其在大数据量和高维特征场景下优势显著。

核心创新：

（1）Histogram-based 分裂（直方图算法）

XGBoost使用预排序（Pre-sorted）方法遍历所有特征值来寻找最佳分裂点，时间复杂度为 \(O(\text{data} \times \text{features})\)。LightGBM将连续特征值分桶（通常256个bin），只需要在bin的边界上搜索分裂点：

• 时间复杂度降为 \(O(\text{bins} \times \text{features})\)，其中 bins << data
• 内存从存储每个样本的特征值变为存储bin索引（uint8），大幅减少
• 通过直方图做差加速：父节点的直方图减去一个子节点的直方图即可得到另一个子节点的直方图

（2）GOSS（Gradient-based One-Side Sampling，单边梯度采样）

GBDT中，梯度大的样本对信息增益的贡献更大。GOSS保留所有梯度较大的样本（top \(a\)%），对梯度较小的样本只随机采样一部分（\(b\)%），并对采样的小梯度样本进行权重补偿。这样在保留关键信息的同时大幅减少了计算量。

（3）EFB（Exclusive Feature Bundling，互斥特征捆绑）

在高维稀疏数据中（如One-hot编码后），很多特征是互斥的（不会同时取非零值）。EFB将这些互斥特征捆绑为一个特征，有效降低特征维度。对于包含大量稀疏特征的数据集，这一优化效果显著。

（4）Leaf-wise 生长策略

策略	说明	特点
Level-wise（XGBoost默认）	逐层生长，同一层的所有节点都分裂	更均匀，不易过拟合，但效率较低
Leaf-wise（LightGBM默认）	每次选择增益最大的叶节点分裂	效率高，相同叶节点数下损失更低，但需要限制 max_depth 防止过拟合

CatBoost

CatBoost 由Yandex于2017年提出，其最大特色在于对类别特征（Categorical Features）的原生支持。

• Ordered Target Encoding：使用排列顺序来计算类别特征的编码，避免了传统Target Encoding的数据泄露问题
• Ordered Boosting：在训练过程中使用随机排列来避免预测偏移（Prediction Shift）
• 对称树 (Symmetric Tree)：构建完全对称的决策树，有利于GPU加速

XGBoost vs LightGBM vs CatBoost 对比

特性	XGBoost	LightGBM	CatBoost
分裂策略	Level-wise	Leaf-wise	Symmetric Tree
分裂搜索	预排序 / 直方图	直方图	直方图
训练速度	中等	快	中等
类别特征	需要手动编码	支持但有限	原生支持
缺失值	自动处理	自动处理	自动处理
GPU支持	支持	支持	支持（优化好）
最佳场景	通用	大数据量、高维	含大量类别特征

实践建议：

• 对于结构化/表格型数据的分类和回归任务，XGBoost和LightGBM仍然是2024-2025年工业界和竞赛中最常用的模型，在很多场景下其性能甚至超过深度学习模型
• 数据量较小（<10万行）时三者差异不大；数据量较大时LightGBM的速度优势明显
• 含大量类别特征时优先考虑CatBoost
• 实际项目中建议三者都尝试，通过交叉验证选择最优模型

---

评论