Chapter 3 优化基础与线性回归
我们要讲的故事
疾旋鼬想买房。它收集了全城过去几年的成交记录：面积、房间数、房龄……以及成交价。它想从这些数据中找到一个"公式"，输入新房子的信息就能算出大概的价格。
最简单的假设：房价 \(y\) 和面积 \(x\) 之间的关系可以用一条直线描述：
\(w\) 是斜率——面积每增加 1 平米，房价平均上涨多少万。\(b\) 是截距——一块地皮本身的价值。
线性回归最核心的思想：用一条直线（在高维是超平面），去拟合数据点背后隐藏的线性规律。
一、线性回归模型
问题与数据假设
- 数据：\(\mathcal{D} = \{(x^{(1)}, y^{(1)}), \ldots, (x^{(m)}, y^{(m)})\}\)
- \(x^{(i)} \in \mathbb{R}^d\)：特征向量
- \(y^{(i)} \in \mathbb{R}\)：标签（连续值）
- 基本假设：样本独立同分布
模型形式
其中 \(w \in \mathbb{R}^d\) 是权重，\(b \in \mathbb{R}\) 是偏置。在特征空间中寻找一个超平面，使得所有数据点到该超平面的预测误差尽可能小。
最小二乘法
决策变量：\(w\) 和 \(b\)。目标函数——最小化残差平方和 (SSE)：
简化表示：令 \(\hat{w} = [w^T, b]^T\)，\(\hat{x}^{(i)} = [(x^{(i)})^T, 1]^T\)，模型简化为 \(y = \hat{w}^T \hat{x}\)。
矩阵形式：定义设计矩阵 \(X = [\hat{x}^{(1)}, \ldots, \hat{x}^{(m)}] \in \mathbb{R}^{(d+1) \times m}\)，标签向量 \(Y = [y^{(1)}, \ldots, y^{(m)}]^T \in \mathbb{R}^m\)。目标函数写为：
离散属性的处理
若有"序"（如大、中、小），则连续化为 0, 0.5, 1；否则转化为 \(k\) 维向量（One-Hot 编码）。
二、统计视角：最大似然估计
高斯噪声假设
给定 \(x\)，标签 \(y\) 服从以 \(w^T x\) 为均值、\(\sigma^2\) 为方差的高斯分布：
即 \(y = w^T x + \epsilon\)，\(\epsilon \sim \mathcal{N}(0, \sigma^2)\)。由中心极限定理，大量独立随机因素之和近似服从正态分布，这为高斯噪声假设提供了理论依据。
似然函数
对所有独立同分布样本，联合概率密度（似然函数）为：
取对数似然：
最大化 \(\ell(w)\) 等价于最小化残差平方和。
结论：在高斯噪声假设下，线性回归的最小二乘估计等价于极大似然估计。
三、精确解法
凸优化基础
凸集：集合 \(C\) 是凸的，若对任意 \(x_1, x_2 \in C\) 和 \(\lambda \in (0,1)\)，有 \(\lambda x_1 + (1-\lambda)x_2 \in C\)。
凸函数：\(f\) 是凸的，若对定义域内任意 \(x_1, x_2\) 和 \(\lambda \in [0,1]\)：
关键定理：对于无约束凸优化问题，\(x^*\) 是全局极小点当且仅当 \(\nabla f(x^*) = 0\)。
线性回归的目标函数 \(f(w) = \frac{1}{2}\|Y - X^T w\|_2^2\) 是关于 \(w\) 的凸函数。
矩阵求导与正规方程
令梯度为零：\(-X(Y - X^T w^*) = 0\)，即正规方程：
若 \(XX^T\) 可逆，则精确解为：
复杂度：矩阵乘法 \(O(d^2 m)\) + 求逆 \(O(d^3)\)。当 \(m\) 或 \(d\) 很大时，计算成本高。
岭回归（Ridge Regression）
当 \(XX^T\) 不满秩时，精确解不唯一。引入 L2 正则化：
闭式解：\(w^* = (XX^T + \alpha I)^{-1}XY\)。\(\alpha I\) 保证矩阵可逆。
岭回归的"岭"源于"岭分析"——目标函数在参数空间中形成狭长平坦的"山脊"，岭回归正是为了解决这个病态问题。
四、梯度下降法
动机
当数据量极大、\(XX^T\) 不可逆或求逆计算成本过高时，需要迭代优化方法。
疾旋鼬不知道最优解在哪，但它可以"摸索"过去。它从一个随机猜测的 \(w\) 和 \(b\) 开始，环顾四周看看哪个方向能让误差下降最快（梯度反方向），然后朝着这个方向走一小步（步长/学习率）。不断重复，最终到达误差最小点。
算法描述
其中 \(\alpha_k > 0\) 称为步长 (stepsize) 或学习率 (learning rate)。
对线性回归：\(\nabla f(w) = X(X^T w - Y)\)。
收敛性分析
下降性：对足够小的 \(\alpha_k\)，利用一阶泰勒展开：
序列 \(\{f(w_k)\}\) 单调递减。由于 \(f\) 有下界（损失函数非负），由单调收敛定理，\(\{f(w_k)\}\) 必然收敛。
收敛点： - 一般可微问题：收敛到稳定点（\(\nabla f = 0\)） - 凸问题：稳定点就是全局最优点，故梯度下降收敛到全局最优
函数性质与收敛速度
\(L\)-光滑性 (Lipschitz Smooth)
定义：可微函数 \(f\) 是 \(L\)-光滑的，若其梯度是 \(L\)-Lipschitz 连续的：
等价的一阶不等式：
二阶充分条件：若 \(f\) 二阶连续可微，\(L\)-光滑 \(\Leftrightarrow\) \(\nabla^2 f(x) \preceq LI\)（Hessian 最大特征值 \(\leq L\)）。
在线性回归中：Hessian 为 \(XX^T\)，\(L = \lambda_{\max}(XX^T)\)。
\(\mu\)-强凸性 (Strongly Convex)
定义：\(f\) 是 \(\mu\)-强凸的（\(\mu > 0\)），若 \(f(x) - \frac{\mu}{2}\|x\|^2\) 是凸函数。
等价的一阶不等式：
二阶充分条件：\(\nabla^2 f(x) \succeq \mu I\)（Hessian 最小特征值 \(\geq \mu\)）。
在线性回归中：当 \(X\) 列满秩时，\(XX^T\) 正定，\(\mu = \lambda_{\min}(XX^T) > 0\)。
定理：强凸函数的全局最小点唯一。
判定方法： - 零阶（定义）：直接验证 - 一阶：验证一阶不等式 - 二阶：验证 Hessian 矩阵的特征值
收敛速率定理
定理 1（凸且 \(L\)-光滑）：设步长 \(\alpha_k \equiv 1/L\)，则：
次线性收敛 \(O(1/T)\)。需要 \(O(1/\epsilon)\) 次迭代使误差小于 \(\epsilon\)。
证明：由 \(L\)-光滑性：
由凸性：\(\|\nabla f(x_k)\|^2 \geq 2L(f(x_k) - f(x^*))^2 / \|x_k - x^*\|^2\)……（利用 \(f(x_k) - f(x^*) \leq \nabla f(x_k)^T(x_k - x^*)\)）。
对 \(k = 0, \ldots, T-1\) 求和得结果。\(\square\)
定理 2（\(\mu\)-强凸且 \(L\)-光滑）：
线性收敛 \(O(\rho^T)\)，\(\rho = 1 - \mu/L \in (0,1)\)。条件数 \(\kappa = L/\mu\) 越小（问题越"良态"），收敛越快。
步长设置方法
| 方法 | 描述 | 优缺点 |
|---|---|---|
| 固定步长 | \(\alpha_k \equiv \alpha\) | 需要知道 \(L\)；太大震荡发散，太小收敛慢 |
| 精确线搜索 | \(\alpha_k = \arg\min_\alpha f(x_k - \alpha \nabla f(x_k))\) | 当前方向最大下降，但需解一维子问题 |
| 回溯线搜索 | Armijo 条件：\(f(x_k - \alpha \nabla f(x_k)) \leq f(x_k) - c\alpha\|\nabla f(x_k)\|^2\) | 避免精确求解，迭代检验 |
| Adam | 自适应步长：结合一阶矩和二阶矩 | 深度学习首选 |
回溯线搜索的 Armijo 条件理解：保证每一步都有"足够"的函数值下降。\(c \in (0, 1/2)\) 控制"足够"的阈值。由泰勒展开可知，对于足够小的 \(\alpha\)，条件一定满足。
复杂度比较
| 方法 | 计算复杂度 | 说明 |
|---|---|---|
| 精确解 \((XX^T)^{-1}XY\) | \(O(d^2 m) + O(d^3)\) | 求逆运算主导 |
| 梯度下降 | \(O(dm) \times T\) | 单轮 \(O(dm)\)，总取决于迭代次数 \(T\) |
当 \(d\) 或 \(m\) 非常大时，梯度下降的单轮低复杂度使其比精确解更可行。
五、随机梯度下降 (SGD)
动机
每次计算全量梯度 \(\nabla f(w) = X(X^T w - Y)\) 需要全部 \(m\) 个样本。当数据是百万、千万级别时，这一步太慢了。
疾旋鼬的策略：每次随机抽查一套房子，计算基于这套房子的梯度方向，走一小步。再抽查另一套，再走一步。虽然每步方向因"抽样"带有随机噪声，但长期来看，大量随机步的期望方向就是正确的方向。
算法
关键性质：随机梯度是真实梯度的无偏估计：
Mini-Batch SGD
其中 \(B_k\) 是均匀随机采样的子集（如 32、128 个样本）。精度和速度的权衡。
收敛性分析
凸情形（步长 \(\gamma_t = R/(B\sqrt{T})\)）：
需 \(O(1/\epsilon^2)\) 次迭代。
强凸情形（递减步长 \(\gamma_t = \gamma/t\)，\(\gamma > 1/(2\mu)\)）：
需 \(O(1/\epsilon)\) 次迭代，快于凸情形。
六、更快的优化算法
Heavy-Ball 动量法
引入"惯性"项 \(\theta_t(w^t - w^{t-1})\)，模拟物理中的动量。减少在峡谷状路径上的振荡。
对强凸二次函数：迭代复杂度 \(O(\sqrt{\kappa}\log(1/\epsilon))\)，优于 GD 的 \(O(\kappa\log(1/\epsilon))\)。
Nesterov 加速梯度法
先沿动量方向"展望"，然后在展望点计算梯度校正。
- 凸且光滑：\(O(1/\sqrt{\epsilon})\)，优于 GD 的 \(O(1/\epsilon)\)
- 强凸且光滑：\(O(\sqrt{\kappa}\log(1/\epsilon))\)，达到一阶优化算法的最优复杂度
"One of the most beautiful and mysterious results in optimization."
Adam 优化器
结合动量（一阶矩估计）和自适应学习率（二阶矩估计）：
偏差修正 \(1-\beta^t\) 解决初始化时 \(m_0 = v_0 = 0\) 的问题。Adam 因高效、稳定和较少的超参数调优需求，成为深度学习最主流的优化器。
性能极限
| 问题类型 | 下界 | 可达算法 |
|---|---|---|
| 强凸且光滑 | \(O(\sqrt{\kappa}\log(1/\epsilon))\) | Nesterov |
| 凸且光滑 | \(O(1/\sqrt{\epsilon})\) | Nesterov |
| 随机优化 | \(O(\sigma^2/\epsilon^2)\) | SGD |
存在"很烂"的目标函数，使得任意基于梯度的算法的复杂度都不低于上述下界。
七、模型评估
回归评估指标
- 均方误差 (MSE)：\(\frac{1}{m}\sum_{i=1}^m (\hat{y}^{(i)} - y^{(i)})^2\)
- 平均绝对误差 (MAE)：\(\frac{1}{m}\sum_{i=1}^m |\hat{y}^{(i)} - y^{(i)}|\)
- 决定系数 (\(R^2\))：
几何解释：\(R^2 = \cos^2\theta\)，其中 \(\theta\) 是真实值中心化向量 \((y - \bar{y})\) 与预测值中心化向量 \((\hat{y} - \bar{y})\) 的夹角。越接近 1 表示拟合越好。
- \(R^2 = 1\)：完美预测
- \(R^2 = 0\)：预测能力等同于猜均值
- \(R^2 < 0\)：比猜均值还差（在测试集上可能出现）
多重共线性
多元线性回归中，特征之间存在高度线性相关的现象。违背特征独立性假设，导致 \(X\) 近似不满秩，模型参数估计不稳定。
诊断：计算特征间的相关系数矩阵，通过热图可视化。经验上，相关系数绝对值低于 0.5 通常可接受。
八、过拟合与正则化
过拟合与欠拟合
疾旋鼬发现：模型在训练集上预测误差很小，但在新房子上误差很大。这就是过拟合 (overfitting)——死记硬背，把训练数据中的噪声和偶然误差都记录下来，失去了泛化能力。
- 过拟合：训练集好，测试集差。模型过度学习了噪声
- 欠拟合：训练集和测试集都不好。模型未能捕捉基本规律
正则化技术
在损失函数中添加惩罚项，限制模型参数大小，降低模型复杂度。
L2 正则化（岭回归）：
效果：权重整体变小，但通常不会精确为零。相当于对模型说："别让任何一个特征的影响力特别突出。"
L1 正则化（Lasso 回归）：
效果：倾向于产生稀疏解——将不重要特征的权重直接压缩到零。相当于自动完成特征选择："小区里有多少桃旋鼬 \(x_{520}\) 这个特征没啥用，可以从公式里删掉了。"
L1 的稀疏性来源于 L1 范数的"棱角"——在坐标轴附近，L1 的等高线更容易与损失函数的等高线在坐标轴上相切。
Elastic Net：
结合 L1 和 L2 的优点。
临近梯度下降法
对于 L1 正则化，\(\|w\|_1\) 不可微。使用临近算子：
这是软阈值函数——先在光滑部分做梯度下降，再在不可微部分做临近映射。
通过正则化，我们得到了一个也许在训练数据上不是"满分"，但在未知数据上更稳健的模型。
疾旋鼬最终拿到一个 \(R^2\) 不错、经得起业务常识检验（面积越大越贵）的模型，自信地告诉客户："这套房子大概值这个价。现在请支付我们提供咨询的费用——大概是您这套房价的 100 倍。"
2026.06