# 牛顿法与优化进阶

[[MCS/day7/00 学习指南|day7 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day7/阅读核验与疑问|阅读核验与疑问]] · 下一篇：[[MCS/day7/02 大 O、小 o 与牛顿误差的追问|大 O、小 o 与牛顿误差的追问]]

> 来源：[[MCS/day7牛顿法与优化进阶|day7牛顿法与优化进阶]]。用途：主线。原有推导、追问与解答保留；阅读时请结合本日核验说明。

## 从求根到求驻点

我们用切线不断逼近方程的根，这种方法叫牛顿法。我们用牛顿法求了 $\sqrt{2}$,三步就得到了很高的精确度。
切线法可以用来求 $f(x)=0$。今天要求 $F^{\prime}(x)=0$ ,因为记住：极小值一定先满足导数为零。
所以，优化里的牛顿法并不是另一套方法，它本质上就是对导数再做一次牛顿求根。

1. Min f -> f' = 0 : 从“求最小”到“求零点”

• 含义：当我们寻求一个函数 $f(x)$ 的最小值（Min f）时，数学上的一个必要条件是它的导数等于 0（$f'(x) = 0$）。
• 理解：这一步是降维打击。原本我们要解决的是一个“优化问题”（找最低点），但通过求导，我们把它变成了一个“求根问题”（找 $f'(x) = 0$ 的点）。
• 这就呼应了你笔记里的那句话：“极小值它一定是先满足导数为零。”

1. 牛顿-拉佛森方法（Newton-Raphson Method）：用来“求零点”的工具

• 含义：既然我们现在手里拿到的任务是“$f'(x) = 0$ 的根”，那么就需要一个专门求根的算法，这个算法就是牛顿-拉佛森方法（其实这就是我们常说的牛顿法）。



## 局部收敛与 Hessian

康托洛维奇：起步离根不太远，导数不太病态的时候，牛顿法是局部二阶收敛（误差以平方缩小）
1 e-3/1 e-6
回想一下牛顿法的迭代公式：$x_{n+1}=x_n-\frac{g(x_n)}{g^{\prime}(x_n)}$
现在我们的方程是 $g(x)=f^{\prime}(x)$。
代入公式，得到：$x_{n+1}=x_n-\frac{f^{\prime}(x_n)}{f^{\prime\prime}(x_n)}$。
这个公式，就是优化领域里的“牛顿法”迭代公式(利用一阶导和二阶导，即 Hessian 矩阵)。
路德维希 黑塞

一维二阶信息 $f''(x)$  
多维 每个方向 每两个方向地交叉 都有一个二阶偏导
黑塞矩阵
中文名叫**海森矩阵**，我们就叫它“海森”就好了。

你可以把它想象成一张**地形的曲率表**：这块地往东有多弯、往北有多弯、往南有多弯、往西有多弯；正着走、反着走、斜着走又会怎么样。这就是它给你讲的这张表。

## 拟牛顿法与 L-BFGS

后来我们又讲到了**拟牛顿法**。我不具体展开讲了。1959 年有一个人提出，1970 年是四个人。海森矩阵是 $n\times n$ 的，nn 到百万级别时，光存储就不现实，求逆更不可能。所以在 1959 年，**Davidon** 提出：不需要真的去算海森矩阵，只需要用最近几步梯度的变化去估算曲率就可以了。这就是拟牛顿法最早的源头。昨天的推导你已经看过了。

到了 1970 年左右，**BFGS** 这四个人几乎同时得到了同一类公式。BFGS 就是这四个人名字的首字母，这是一个算法，我们前面讲过，昨天也看过了，记得回去好好翻翻。

后来还有 **L-BFGS**。我们要知道，这个算法是用来做近似的。

上世纪 80 年代，**Nocedal** 做了 L-BFGS。翻到昨天的笔记就能知道：他说矩阵干脆就不要存了，我只记最近 mm 次迭代的向量。

所以在 scaling 当中，我们做什么？**Logistic regression**，这叫**逻辑回归**。

sklearn 逻辑回归 solver='lbfgs'

## Adam 与自适应步长

然后我们又讲到了 **Adam**。Adam 是 2014 年提出的，2014 年我们做的是**尺度再换一次**。

在 2014 年的时候，有一个人叫 **Kingma**（你叫他卡马、K 马都可以，也有人叫他王马或者马王，他是外国人），他和 **维尔**（Welling）一起发表了 **Adam** 这篇论文。如果需要的话，你可以来问我要。

他们发表了 Adam。当参数规模到了千万甚至 **billion** 级别之后，Adam 解决了这个问题——百万级和十亿级参数下的优化问题。那么连 **L-BFGS** 它也进行了一个**偏重**。
DL 又改回了一阶
梯度加上动量又加上按坐标自适应步长

牛顿：看见曲率，一步看到谷底
拟牛顿：曲率估计
Adam：曲率估计不了，至少把每个步长参数给他调
问题扩大以后，不得已的选择，工具替换。
LOSS 函数，想看到谷底，这一点的高度是多少，坡度怎么样，弯的厉不厉害，弯的怎么样
要用学习率去一步步试
牛顿：看地面的弯曲。如果是抛物面，可以直接算的
求根是解 f(x)=0
求最优 f'(x)=0


要记住：如果今天讲课，你只记得牛顿法很快，却忘记了第三种可能，那就好好反思一下为什么会这样。

我们要知道，为什么会出现这些问题？肯定是有需求，才会出现这些方法。**一阶方法有三件事做不好**，所以人们才去研究二阶方法。是哪三件事？

**第一，学习率（learning rate）。**

**第二，病态。** 在狭长的山谷里面，横着走和顺着走，曲率能差上几十倍甚至几百倍。固定步长下，它就会走出“之字形”——知乎者也的“之”，之字形来来回回弹。这就是海森矩阵条件数很大时的样子。

**第三，尺度。** 有的变量是像素，有的变量是概率，梯度各分量的量级是不一样的。

所以，**精确牛顿法相当于按照曲率重新丈量了这片空间**，它是一个 space（空间度量）。因此，它对线性的缩放就没有那么敏感。

---

你问“哪三个方法”，结合上下文，应该是**一阶方法做不好的三件事**：

1. **学习率**：步长难选。
    
2. **病态**：条件数大时走之字形。
    
3. **尺度**：各变量量级不一致。



那为什么牛顿法当时没有把整个问题都解决掉呢？要记住，还是**海森矩阵的问题**。

海森矩阵是 $n\times n$。假设 nn 是 100 万，那么双精度存满大概需要 **8 TB** 这样的量级。这里可以记一下，随堂笔记记一下，大概是 **8 TB**。

求逆呢，复杂度是 $O(n^3)$。而在深度神经网络里，参数量动辄是 **billion** 级别，也就是上亿或十亿级别，根本算不起来。

所以才有了后面的：**阻尼修正、拟牛顿，以及我们 2014 年讲的 Adam**。

离最优点很远，黑森矩阵不正定、鞍点附近，牛顿法，它可以比梯度下降的更差，甚至是发散。



$$x_{\mathrm{new}}=x-\frac{f'(x)}{f''(x)}$$

这是不是一维除以二维？它的比值拿 $x$ 去减。这是啥？

这是不是把 $g=f^{\prime}$ 当成新函数，对 $g(x)$ 做牛顿求根？

1. 一维情况：$x \leftarrow x - f'(x) / f''(x)$
- 这就是咱们之前推导的，把求根公式用在导数上。
- 分子 $f'(x)$ 是一阶导（梯度）。
- 分母 $f''(x)$ 是二阶导（曲率）。
- 本质是：用一维的梯度除以一维的曲率，也就是一个标量除以标量。

1. 多维情况：$x \leftarrow x - H^{-1} \cdot \text{梯度}$
- 这就是多维空间下的自然推广。
- 梯度不再是一个数，而是一个向量 ($\nabla f$)。
- 曲率不再是一个数，而是海森矩阵 $H$（一个 $n \times n$ 的矩阵）。
- 在矩阵运算中，“除以一个矩阵”等价于“乘以它的逆矩阵”，所以 $1/f''(x)$ 就变成了 $H^{-1}$。
- 公式变成了：参数更新 = 当前位置 - 海森矩阵的逆 $\times$ 梯度。


高斯消元法
所以说它每一步其实都在解什么？解**线性方程组**：

$$
Hd=-g
$$

然后我们就知道 $x_{\mathrm{new}}=x+d$。

可以推导到 xx。啊，这叫这是什么？这叫**高斯消元**。这边就是**高斯消元**了。

它是 dijdij​ 或 djidji​ 项是多少多少，我们叫什么？叫**对称矩阵**，是不是？对称矩阵。

它关键是什么？三方面：

1. **特征值全正**：这叫**正定**。
    
2. **特征值全负**：这叫**负定**。
    
3. **有正有负**：这叫**不定**，对应的是**马鞍面**，让我们看**鞍点**。
    

但是牛顿法的话，它还是不看这些。它是只奔着**梯度等于零**去做的。这个是牛顿法，它**一步到位**。

然后拟牛顿法，他说不管你真海森，是维护一个**对称矩阵 B** 去近似它。啊，其实就是什么？**割线**嘛。

你比如说满足我的割线方程：

$$
Bs=y
$$

那 ss 就相当于**走的多点**（自变量变化量），那 yy 就是**梯度变了多少**（梯度变化量）。意味着拟牛顿法就是说用**差商来代替 f′′f′′**，这叫**割线法**。


你看，我们要知道，第一个问题：一维从哪里来？
就是当前的点，我们把它设为 $x_n$。我们用多少？我们用二次多项式来代替 $f$，是不是？
那么 $f(x)$ 约等于：
$$f(x) \approx f(x_n) + f'(x_n)(x - x_n) + \frac{f''(x_n)}{2}(x - x_n)^2$$
然后我们对 $x$ 进行求导，令导数为零。是不是令导数为零？
我们是不是就是在解：
$$
f'(x_n) + f''(x_n)(x - x_n) = 0$$
我们就能得出来什么？
$$x = x_n - \frac{f'(x_n)}{f''(x_n)}$$

这就是一维牛顿法的来源：用二次函数局部近似原函数，然后直接跳到这个二次函数的极值点。


在**逻辑回归（Logistic Regression）**和**广义线性模型（GLM）**中，当**样本量中等**时，`scikit-learn`（sklearn）等主流机器学习库最常用的优化求解器是：

- ** `lbfgs` ** （拟牛顿法，Limited-memory BFGS）
    
- ** `newton-cg` ** （牛顿-共轭梯度法，Newton-Conjugate Gradient）


scipy.optimize.minimize(method=’BFGS’)L-BFGS-BI 把这个函数最小化交给库，拟合、校准、反演
视觉与 SLAM 里面的 Bundle Adjustment、相机标定：高斯牛顿/leven-berg
-marquardt,牛顿法在最小二乘的
pytorch
PyTorch 里面有 torch.optim.LBFGS，适合参数不多、loss 光滑的小问题 不太适合训练大模型（LM）
xgboost. LightGBM,Catboost
XGBoost(Extreme Gradient Boosting)极端梯度提升
原型：GBDT 梯度提升树 

本质是加法模型：训练一堆小树，不断拟合上一轮模型的残差，所有树的预测结果加在一起得到最终预测
GBDT 只用一阶导数（梯度）来优化损失
XGBoost：最大升级，用二阶泰勒展开


XGBoost 最大的升级，就是用了**二阶泰勒展开**。

所以说，XGBoost 在每一步构建树的时候，同时使用了损失函数的**一阶导**和**二阶导**。

明白吗？同时用了 gg 和 hh：一阶导数 gg，二阶导数 hh（也就是 Hessian 的对角线元素）。它们有了这样一个公式。

1.公式逐项拆解

$$L^{(t)}\approx\sum_i\left[g_iw_i+\frac{1}{2}h_iw_i^2\right]+\Omega(f_t)$$

· $L^{(t)}$:第 $t$ 轮迭代时的目标函数(损失函数)。

· $\sum_i$:对每一个样本 $i$ 进行求和。

· $g_i$:损失函数在当前预测值处的一阶导数(梯度)。对应你前面笔记的"梯度"。
· $h_i:$ 损失函数在当前预测值处的二阶导数(海森矩阵的对角线元素)。对应你前面笔记的"曲率"。
· $w_i:$ 当前样本落在的叶子节点的权重(预测值)。这是我们需要去求解的变量。
· $\Omega(f_t)$:正则化项，用来惩罚树的复杂度(比如叶子节点数量和叶子权重的大小),防止过拟合。
跑出来飞三（F 3）就上面那个，改完跑完，按 MSE 交上去，结束了。但是你为什么跑出来这个结果不知道？

怎么去修改这个结果，不知道怎么改参数，不知道。老师讲了啊，他说改 learning rate 啊，改了，改了之后呢，你的结果拿到 test 之后和 validation 是不行的，为什么？

你不知道如何去拟合呀？为啥？因为你不知道这个模型的原理是什么。


正则项控制树的复杂度，防止过拟合
我们都知道，XGBoost 有**五大核心特点**：

**第一，二阶泰勒损失。**  鲁棒性好，抗噪声
它用的是二阶泰勒展开，所以对于损失函数，它的收敛更快，因为它是一阶加二阶。一阶导数加二阶导数，收敛更快，对损失函数适配性更强。比如 MSE、Log Loss，它都是支持的。

**第二，它本身还自带正则化。**  
正则化限制树不要长得太复杂，强力抑制过拟合。这是 XGBoost 在表格数据上碾压普通 GBDT 的一个关键。这要记得。

**第三个特征，分裂节点的预排序或分箱。**  
这个叫什么？叫 **engineering accelerator**，工程加速。我们对特征进行预先排序，然后在候选分割点进行缓存，给它大幅度提速。然后还支持近似直方图分箱。PSIT 的同学应该懂，我已经在 PSIT 课讲过这个了，海量数据训练会更快。这是第三个特点。

**第四个，缺失值自动处理。**  
也就是说，不需要你人工处理。

**第五个，支持并行计算。**  
你要记住啊，就是树的迭代是……问你们啊，你觉得树的迭代是串行还是并行？扣 1 串行，扣 2 并行？大胆猜一下。树的迭代。

我之前前面还讲了，它的本质是什么模型啊？是不是**加法模型**？我们在硬件层面是不是加法器啊？是吧。

那按照这个逻辑去想，你应该思考到什么？**树的迭代是串行的**。为什么？它必须一颗一颗地加。记住了啊，**树的迭代是串行**。把这句话打在公屏上，或者发在学习群里面。多给自己几遍记忆：**树的迭代是串行的，它必须一颗一颗地加。**

并行，它只发生在哪里？只发生在——记住啊，**并行只发生在单棵树内部，特征分裂**。单棵并行，它只发生在单棵树内部特征分裂，多个特征同时找的时候，找的是最优分割点。

XGBOOST 适合结构化表格数据
/那么 XGBoost 第三个优点，训练速度快，支持自定义的损失函数（loss function）。

第四个优点就是，可以输出特征重要性量化。我们常用来做什么？做因子筛选。

所以它的优点是：

1. **表格数据效果极好**，鲁棒性好，抗噪声。
    
2. **自带正则，缺失值处理**，上手门槛很低。
    

所以它也被誉为——就是我们学习机器学习的**入门模型**。


图像文本这类非结构化谁做不了，那谁适合呀？

Deep learning 深度学习

LightGBM 你知道吧？它的原型就是 XGBoost，它是 XGBoost 的改进版。

所以你会看到它是一个整个线性的提升。它跟 XGBoost 相比，就是：**直方图算法，加上按叶子生长（Leaf-wise）**，速度更快，精度略接近。

要记得啊，因子的预测挖掘、分类，比如预测涨跌，是不是它可以用？因子筛选也可以，然后风险评估这些都可以用。

但是做风控的时候，一定要先做 **time series**，时间序列分析，序列回撤这比较多，然后下分（降采样/分箱）。

**Suffrage and test**（这里可能是口误，结合上下文，大概率想说的是 **Train / Validation / Test** 的划分，或者是 **Backtesting** 回测）。
**为什么深度学习不用牛顿法，而用 Adam？**

**第一，存不起海森矩阵。** 牛顿法没有办法存储海森矩阵。

**第二，mini-batch 的梯度是有噪声的。** 二阶导数更加有噪声，它更早（更敏感）。所以牛顿法更加不适合。

**第三，在神经网络里面，鞍点很多。** 牛顿法会奔着驻点去，不管是不是极小值。哇，这个影响很大呀。

**第四，它是非凸函数（non-convex）。** 在不可导点上没有正经的二阶导。记住了啊。

**说回 Adam。**

Adam 呢，它是一阶矩阵和二阶矩阵，这里它是用**一阶矩**和**二阶矩**，即梯度平方的滑动平均。
一阶矩 + 梯度平方
一阶矩：动量
二阶矩：梯度平方，自适应缩放
对不对啊，这里二阶它是**梯度平方**，它不是海森矩阵。

他用一阶矩和二阶矩做什么？做**对角**随机这样的一个**伪曲率**。

好处是什么？**便宜。**

牛顿法并未失败，而是问题的尺度换了

鞍点 = 梯度为零、但 Hessian 特征值有正有负的点；  
它是驻点，但不是极值点；  
牛顿法可能停在鞍点上，误以为找到了最小值。

在 sklearn 和 scipy 常见，LM 论文极少遇见