#016. 常用算法直觉：输入、输出、步骤与失效条件

#学习目标与概念起点

本章不是把算法背成公式，而是把公式翻译成“机器能执行、人也能解释”的流程。面试里真正要讲清楚的是：算法拿什么作为输入、想优化或估计什么、每一步为什么这样走、最后输出什么、哪些情况下输出会不可信。

学习目标

你应该能用同一套语言解释梯度下降、Newton、最小二乘、PCA、MLE/MAP、Monte Carlo、CVaR：输入、输出、目标、步骤、最小例子、失效条件。

概念起点

算法通常只做三类事：优化一个函数、把高维数据压成更清楚的结构、用样本估计未知量。不同算法的差异，主要在于“局部信息怎么用”和“误差来自哪里”。

面试表达顺序

先说对象，再说目标，再说更新规则，最后说边界。不要先甩公式，因为公式本身不说明样本、初始值、数值稳定性和失败场景。

输入数据、目标函数、概率模型、初始点、超参数、置信水平或样本数。
输出参数估计、主方向、低维表示、期望估计、风险阈值或尾部损失。
目标最小化 loss、最大化似然、保留最大方差、估计期望或估计极端损失。
步骤把数学条件改写成可重复执行的更新、分解、排序或平均。
失效常来自假设不成立、样本太少、矩阵病态、目标非凸、尾部事件稀少或数值尺度不合适。

统一直觉：优化算法问“下一步往哪里走”；线性代数算法问“数据主要沿哪些方向变化”；统计算法问“哪些参数或样本平均最能解释我看到的数据”；风险算法问“最坏的一小段世界长什么样”。把这个问题问对，算法就不再只是符号。

#梯度下降：只看当前位置的一阶斜率

梯度下降用于最小化一个可导目标函数。它不试图一次算出最优解，而是在当前位置看局部斜率，然后沿着让函数下降的方向走一小步。

输入

目标函数 \(f(x)\)、梯度 \(\nabla f(x)\)、初始点 \(x_0\)、学习率 \(\eta\)、停止条件，例如梯度足够小或迭代次数达到上限。

输出

一个候选解 \(x_T\)，通常希望它接近局部最小值。非凸问题中，它不保证是全局最小值。

目标

让 \(f(x)\) 尽量小。机器学习里 \(f\) 常是训练 loss；量化里也可能是拟合误差、风险惩罚或交易成本后的负收益。

\[ x_{t+1}=x_t-\eta\nabla f(x_t) \]
第 1 步在当前位置 \(x_t\) 计算梯度 \(\nabla f(x_t)\)。梯度越大，说明局部上升越快。
第 2 步取负梯度方向，因为负梯度会让一阶 Taylor 近似下降。
第 3 步乘上学习率 \(\eta\)，控制每次走多远。
第 4 步重复更新，直到 loss 不再明显下降，或者梯度接近 0。

最小例子：最小化一维二次函数

令 \(f(x)=(x-3)^2\)，梯度是 \(f'(x)=2(x-3)\)。从 \(x_0=0\) 出发，学习率 \(\eta=0.1\)。

第 0 步：\(x_0=0\)，梯度 \(f'(0)=-6\)，所以

\[ x_1=0-0.1(-6)=0.6 \]

第 1 步：\(x_1=0.6\)，梯度 \(f'(0.6)=-4.8\)，所以

\[ x_2=0.6-0.1(-4.8)=1.08 \]

可以看到 \(x\) 从 0 往最优点 3 靠近，但不是一步到位。学习率越小越稳但慢，越大越快但可能越过最优点来回震荡。

失效条件表现应对思路
学习率过大loss 震荡、发散，参数来回跳。减小学习率、使用 warmup、line search 或自适应优化器。
学习率过小loss 下降很慢，训练看似卡住。调大学习率，或用动量、Adam、预条件方法。
曲率病态某些方向很陡，某些方向很平，更新呈“之”字形。标准化特征、使用二阶近似或预条件。
非凸鞍点梯度接近 0，但不是好解。随机扰动、不同初始化、动量和更好的优化器。

#Newton 法：用二阶曲率直接估计最优点

Newton 法比梯度下降更“贪心”：它不仅看斜率，还看弯曲程度。它在当前位置用一个二次函数近似原函数，然后直接跳到这个二次近似的最小点。

输入

目标函数 \(f(x)\)、梯度 \(g(x)=\nabla f(x)\)、Hessian \(H(x)=\nabla^2 f(x)\)、初始点 \(x_0\)。

输出

候选极值点 \(x_T\)。如果 Hessian 在最优点附近正定，Newton 法通常会很快收敛。

目标

利用二阶局部模型减少迭代次数，尤其适合维度不太高、Hessian 可计算且比较稳定的问题。

\[ x_{t+1}=x_t-H(x_t)^{-1}g(x_t) \]
第 1 步在 \(x_t\) 处计算梯度 \(g\) 和 Hessian \(H\)。
第 2 步构造局部二次近似：\(f(x_t+\Delta)\approx f(x_t)+g^T\Delta+\frac12\Delta^TH\Delta\)。
第 3 步对 \(\Delta\) 求最小，得到线性方程 \(H\Delta=-g\)。
第 4 步解出 \(\Delta\)，更新 \(x_{t+1}=x_t+\Delta\)。

最小例子：Newton 法一步解二次函数

还是 \(f(x)=(x-3)^2\)。梯度 \(g(x)=2(x-3)\)，Hessian \(H(x)=2\)。从 \(x_0=0\) 开始。

\[ \Delta=-H^{-1}g=-\frac{1}{2}\cdot(-6)=3 \]
\[ x_1=x_0+\Delta=0+3=3 \]

因为原函数本身就是二次函数，Newton 的局部二次模型就是原函数，所以一步到达最优点。实际问题通常不是完美二次函数，因此需要多次迭代，也常加 damping：\(x_{t+1}=x_t+\alpha\Delta\)，其中 \(0<\alpha\le 1\)。

为什么会失效：Newton 法相信二次近似。如果 Hessian 不正定，二次模型可能往下开口或鞍形，解出来的方向未必下降；如果 Hessian 接近奇异，\(H^{-1}\) 会放大噪声；如果维度很高，显式形成和求逆 Hessian 也可能太贵。

#最小二乘：把观测投影到特征能解释的空间

最小二乘用于拟合线性关系。它假设目标 \(y\) 可以被特征矩阵 \(X\) 的列线性组合解释，选择参数 \(\beta\)，让预测 \(X\beta\) 尽量靠近真实 \(y\)。

输入

设计矩阵 \(X\in\mathbb{R}^{n\times d}\)、目标向量 \(y\in\mathbb{R}^n\)。每一行是一个样本，每一列是一个特征。

输出

参数 \(\hat\beta\in\mathbb{R}^d\)，以及预测值 \(\hat y=X\hat\beta\)、残差 \(r=y-\hat y\)。

目标

最小化平方残差和：\(\min_\beta\|X\beta-y\|_2^2\)。平方会惩罚大误差，也让问题有清晰的线性代数解。

\[ X^TX\hat\beta=X^Ty \]
第 1 步写出预测 \(\hat y=X\beta\)，残差 \(r=y-X\beta\)。
第 2 步最小化 \(\|r\|_2^2\)，对 \(\beta\) 求导。
第 3 步令导数为 0，得到正规方程 \(X^TX\beta=X^Ty\)。
第 4 步如果 \(X^TX\) 可逆，解 \(\hat\beta=(X^TX)^{-1}X^Ty\)；工程上更常用 QR 或 SVD。

最小例子：拟合过原点的直线

假设模型是 \(y=\beta x\)，两个样本是 \((1,2)\)、\((2,3)\)。此时 \(X=[1,2]^T\)，\(y=[2,3]^T\)。

\[ X^TX=1^2+2^2=5,\qquad X^Ty=1\cdot2+2\cdot3=8 \]
\[ \hat\beta=\frac{8}{5}=1.6 \]

预测为 \(\hat y=[1.6,3.2]^T\)，残差为 \([0.4,-0.2]^T\)。这个解的直觉是：直线不能同时穿过两个点，所以选择一个让总平方误差最小的折中斜率。

失效条件为什么出问题面试可说的修正
特征共线\(X^TX\) 接近不可逆，小噪声会导致参数大幅变化。用 Ridge、SVD、删掉重复特征或做正则化。
异常值严重平方损失会放大大残差，少数点能主导结果。使用 Huber loss、分位数回归或稳健估计。
关系非线性线性组合解释不了真实结构。加非线性特征、核方法或换模型。
噪声异方差不同样本误差方差不同，普通最小二乘不再高效。用加权最小二乘或重新建模噪声。

#PCA：找数据波动最大的正交方向

PCA 是降维方法，但“降维”只是结果，不是解释。更准确地说，PCA 在中心化后的数据里寻找方差最大的方向。第一个主成分解释最大波动，第二个主成分在与第一个正交的前提下解释剩余最大波动。

输入

数据矩阵 \(X\in\mathbb{R}^{n\times d}\)，通常先对每个特征减去均值。也可以输入协方差矩阵。

输出

主成分方向、每个方向的解释方差、低维坐标 \(Z=XW_k\)。

目标

在 \(k\) 维子空间里尽量保留原数据的方差，也等价于在平方重构误差意义下找最佳线性低维近似。

第 1 步中心化每一列特征，使均值为 0。没有中心化时，第一主成分可能被均值方向污染。
第 2 步计算协方差矩阵 \(\Sigma=\frac{1}{n}X^TX\) 或 \(\frac{1}{n-1}X^TX\)。
第 3 步对 \(\Sigma\) 做特征分解，得到特征值和特征向量。
第 4 步按特征值从大到小选择前 \(k\) 个特征向量作为主方向。
第 5 步把样本投影到这些方向上，得到低维表示。

最小例子：四个点的第一主成分

中心化后的样本是 \((1,1)\)、\((-1,-1)\)、\((1,-1)\)、\((-1,1)\)。协方差矩阵为

\[ \Sigma=\begin{bmatrix}1&0\\0&1\end{bmatrix} \]

两个方向的方差一样大，所以 PCA 没有唯一的第一主成分。任意单位正交方向都同样好。这说明 PCA 的主方向不是“真实因子”的保证，它只是样本方差结构的结果。

为什么会失效：PCA 对尺度敏感。收入用“元”表示、收益率用“小数”表示时，数值尺度大的特征会主导协方差。PCA 也只看线性方差，不知道标签、不知道因果、不知道未来分布是否变化；异常值会把主方向拉歪。

#MLE 与 MAP：从“最能解释数据”到“带先验的解释”

MLE 和 MAP 都是在估计模型参数。MLE 只看观测数据：哪个参数让这批数据出现的概率最大，就选哪个参数。MAP 在此基础上再加入先验：如果某些参数本来就更可信，就给它们额外加分。

输入

数据 \(D=\{x_1,\ldots,x_n\}\)、概率模型 \(p(D\mid\theta)\)。MAP 还需要先验分布 \(p(\theta)\)。

输出

参数点估计：MLE 输出 \(\hat\theta_{\mathrm{MLE}}\)，MAP 输出 \(\hat\theta_{\mathrm{MAP}}\)。

目标

MLE 最大化数据似然；MAP 最大化后验概率。实际计算通常最大化 log 形式，因为乘法会变加法，更稳定。

\[ \hat\theta_{\mathrm{MLE}}=\arg\max_\theta\log p(D\mid\theta) \]
\[ \hat\theta_{\mathrm{MAP}}=\arg\max_\theta\left[\log p(D\mid\theta)+\log p(\theta)\right] \]
第 1 步选定概率模型，例如 Bernoulli、Gaussian、Categorical 或语言模型的 token 条件分布。
第 2 步写出 likelihood：这批数据在参数 \(\theta\) 下出现的概率。
第 3 步取 log，把样本上的乘积变成求和。
第 4 步MLE 只最大化 log-likelihood；MAP 再加上 log prior。
第 5 步能解析求解就求导；不能解析就用梯度下降、EM 或其他数值优化方法。

最小例子：硬币正面概率

投硬币 5 次，观察到 4 次正面、1 次反面。令正面概率为 \(p\)。

MLE 的似然为 \(L(p)=p^4(1-p)\)，log-likelihood 为

\[ \ell(p)=4\log p+\log(1-p) \]

求导并令 0：

\[ \frac{4}{p}-\frac{1}{1-p}=0\quad\Rightarrow\quad 4(1-p)=p\quad\Rightarrow\quad p=0.8 \]

所以 \(\hat p_{\mathrm{MLE}}=0.8\)。如果 MAP 使用 Beta 先验 \(p\sim\mathrm{Beta}(2,2)\)，相当于先验里有“1 次正面、1 次反面”的平滑，MAP 会被拉向 0.5，避免小样本下过度自信。

失效条件表现关键解释
模型错设估计很稳定，但解释错了。MLE 只能在你给定的模型族里选最像数据的参数。
样本太少估计极端，例如 1 次正面就估 \(p=1\)。MAP 或正则化可以降低过拟合，但依赖先验。
局部最优复杂模型训练结果依赖初始化。需要多次初始化、优化诊断和验证集。
先验不合理MAP 被拉向错误区域。先验是信息也是偏见，不能无条件认为更好。

#Monte Carlo：用随机样本平均近似期望

Monte Carlo 的核心很朴素：如果一个量可以写成期望，但积分或枚举太难，就通过反复采样来平均。它的优点是通用，缺点是收敛慢，尤其对尾部事件很吃样本。

输入

可采样的随机变量 \(X\)、要估计的函数 \(f(X)\)、样本数 \(n\)、随机数生成方式。

输出

期望 \(\mathbb{E}[f(X)]\) 的估计值，以及可选的不确定性估计，例如样本标准误。

目标

用样本平均替代难算的积分、求和或未来情景枚举。

\[ \mathbb{E}[f(X)]\approx \frac{1}{n}\sum_{i=1}^n f(X_i) \]
第 1 步确定要估计的期望，例如未来收益、模型输出概率、策略回报或损失尾部。
第 2 步从目标分布采样 \(X_1,\ldots,X_n\)。
第 3 步对每个样本计算 \(f(X_i)\)。
第 4 步取平均，必要时计算方差和置信区间。

最小例子：估计一次随机收益的均值

假设模拟得到 5 个收益样本：\(-1\)、\(2\)、\(0\)、\(3\)、\(1\)。用 Monte Carlo 估计期望收益。

\[ \hat\mu=\frac{-1+2+0+3+1}{5}=1 \]

这个 1 只是随机估计，不是真理。如果重新采样，结果会变。样本数越大，平均值通常越稳定，但误差按 \(1/\sqrt n\) 缩小：想把误差降到原来的十分之一，通常需要约 100 倍样本。

为什么会失效：如果样本不是从正确分布来，平均得再多也只是稳定地错；如果目标是极端尾部事件，普通随机采样很可能根本抽不到关键场景；如果样本强相关，表面样本数很大，有效样本数却很小。

#CVaR 风险估计：不要只问阈值，还要问尾部平均有多坏

VaR 和 CVaR 都用于描述损失尾部。VaR 是分位数：在置信水平 \(\alpha\) 下，损失通常不会超过多少。CVaR 进一步看超过这个阈值之后，平均损失是多少。面试中要强调：VaR 是门槛，CVaR 是门槛之后的平均严重程度。

输入

损失样本 \(L_1,\ldots,L_n\)，其中损失越大越坏；置信水平 \(\alpha\)，例如 \(95\%\) 或 \(99\%\)。

输出

\(\mathrm{VaR}_\alpha\) 和 \(\mathrm{CVaR}_\alpha\)。VaR 是损失分位数，CVaR 是尾部条件平均损失。

目标

估计极端坏情景下的损失水平，服务于仓位控制、保证金、止损线和压力测试。

第 1 步把收益转成损失，统一“越大越坏”的方向。
第 2 步按损失从小到大排序。
第 3 步取 \(\alpha\) 分位数作为 VaR。
第 4 步取超过 VaR 的尾部样本平均，得到经验 CVaR。样本少时可以采用插值或保守定义。

最小例子：从 10 个损失样本估计尾部风险

损失样本排序后为 \(0,1,1,2,2,3,4,5,8,12\)，取 \(\alpha=0.8\)。

80% 分位数大约落在第 8 个样本附近，所以经验 VaR 可取 \(5\)。超过或达到该阈值的尾部样本是 \(5,8,12\)，因此一个保守的经验 CVaR 为

\[ \mathrm{CVaR}_{0.8}\approx \frac{5+8+12}{3}=\frac{25}{3}\approx 8.33 \]

VaR 只告诉你“80% 情况下损失不超过 5 左右”，CVaR 告诉你“一旦进入最坏尾部，平均损失约为 8.33”。后者更能反映尾部厚度。

失效条件为什么危险修正方向
尾部样本太少95% 或 99% 风险只由少数点决定，估计方差很大。增加历史窗口、情景模拟、压力测试、极值理论。
历史不代表未来平静期估出来的 VaR/CVaR 会低估危机。加入 regime 判断、波动率缩放、压力情景。
损失方向弄反把收益分位数当损失分位数，风险解释完全反。先统一定义 \(L=-R\) 或明确损失为正。
组合相关性变化危机时相关性上升，分散化失效。用条件相关、压力相关矩阵和组合级回测。

#完整数值例子：从拟合到风险估计的一条链

下面把多个算法放在一个小链路里：先用最小二乘拟合一个简单收益模型，再用梯度下降看同一个目标如何迭代优化，最后用模拟残差估计尾部风险。

题目

有 3 天的特征 \(x\) 和收益 \(y\)：\((1,1)\)、\((2,2)\)、\((3,2)\)。用无截距模型 \(y=\beta x\) 拟合；然后从 \(\beta_0=0\) 用梯度下降做两步；最后假设策略损失样本为 \(0,1,1,2,4\)，估计 80% VaR 和 CVaR。

1. 最小二乘解析解。

\[ X^TX=1^2+2^2+3^2=14,\qquad X^Ty=1\cdot1+2\cdot2+3\cdot2=11 \]
\[ \hat\beta=\frac{11}{14}\approx0.786 \]

预测为 \(0.786,1.571,2.357\)，残差约为 \(0.214,0.429,-0.357\)。这个模型只用一条过原点的直线解释三个点，所以只能折中。

2. 同一个目标用梯度下降。目标函数为

\[ J(\beta)=\frac12\sum_i(\beta x_i-y_i)^2 \]

梯度为

\[ J'(\beta)=\sum_i x_i(\beta x_i-y_i)=14\beta-11 \]

从 \(\beta_0=0\) 出发，取学习率 \(\eta=0.05\)。

\[ \beta_1=0-0.05(14\cdot0-11)=0.55 \]
\[ \beta_2=0.55-0.05(14\cdot0.55-11)=0.55-0.05(-3.3)=0.715 \]

两步后 \(\beta\) 已经靠近解析解 \(0.786\)，但还没到。梯度下降是逐步靠近，最小二乘解析解是在条件好时直接解线性方程。

3. 用损失样本估计风险。损失样本排序后为 \(0,1,1,2,4\)，80% 分位数取第 4 个附近，VaR 约为 \(2\)。尾部样本取 \(2,4\)，则

\[ \mathrm{CVaR}_{0.8}\approx\frac{2+4}{2}=3 \]

这个风险估计非常粗糙，因为只有 5 个样本。它适合教学，不适合真实交易决策。

#常见误区

误区为什么错正确说法
梯度下降一定找到全局最优非凸目标可能有局部最优、鞍点和平坦区。凸问题有更强保证；深度学习通常依赖经验优化和泛化验证。
Newton 一定比梯度下降好二阶信息贵，Hessian 不正定或病态时方向可能错。Newton 在合适条件下快，但常需要 damping、trust region 或拟牛顿。
最小二乘就是求逆显式求逆数值不稳定，且 \(X^TX\) 可能不可逆。理解为投影；工程上优先 QR/SVD/正则化。
PCA 找到“最重要因子”PCA 只看方差，不看标签、因果或业务收益。它找最大线性波动方向，不保证可解释或可预测。
MLE 总是客观，MAP 总是主观MLE 也依赖模型假设；MAP 的先验可能是领域知识，也可能是偏见。两者都要说明模型、数据和先验来源。
Monte Carlo 多采样就没问题分布错、尾部抽不到、样本相关时，多采样不能消除系统偏差。区分随机误差和偏差；必要时做重要性采样、方差缩减和诊断。
VaR 足够描述风险VaR 不告诉超过阈值后会亏多惨。CVaR 更关注尾部平均损失，但也依赖样本和分布假设。

#LLM 与 Quant 连接

同一个算法，在 LLM 和量化面试中关注点不同。LLM 更关心训练目标、梯度信号、表示压缩和采样估计；Quant 更关心估计误差、稳定性、尾部风险和分布漂移。

算法LLM 面试连接量化面试连接
梯度下降训练 loss 通过反向传播给每个参数方向；学习率、batch 噪声和曲率影响训练稳定性。优化组合权重、拟合因子模型或校准策略参数；过拟合和交易成本会改变目标。
Newton完整 Hessian 在大模型中太贵，但二阶直觉解释预条件、自然梯度和曲率校正。均值方差优化、凸风险目标和小维度校准中常见；Hessian 病态会导致仓位极端。
最小二乘线性 probe、embedding 回归、logit lens 的基础直觉都是线性解释。因子暴露估计、收益预测、风险归因；共线性和非平稳是核心问题。
PCA理解 embedding 或 activation 的低维结构，但不能直接等同语义因子。收益协方差降维、风险因子提取、噪声过滤；危机期主成分可能变化。
MLE/MAP语言模型最大化 token 条件似然；交叉熵就是负 log-likelihood 的常见形式。估计分布参数、波动率模型、状态转移概率；MAP 可加入先验或正则。
Monte Carlo采样估计生成质量、RL rollout 回报、pass@k 或不确定性。路径模拟、期权定价、风险情景；误差收敛慢，尾部要特别处理。
CVaR可类比安全评估中“最坏输出尾部”的平均严重性，而不是只看平均表现。仓位风控、止损、保证金和压力测试；比 VaR 更关注尾部损失大小。

面试 insight：强回答不是“这个算法叫什么”，而是能指出它依赖的局部信息、统计假设和样本质量。比如梯度下降依赖局部一阶近似，PCA 依赖方差代表信息，MLE 依赖模型族正确，CVaR 依赖尾部样本可信。能说出这些依赖，就能自然说出失效条件。

#最后检查清单