42 KiB
第九章
不再走“通用算法”的路线，而是开始讨论一类“带强结构假设的监督学习方法”。它们的核心思想不是盲目地在高维空间里硬拟合一个任意复杂的函数，而是先相信“真实的回归函数大概率有某种简单结构”，再利用这个结构去降维、降复杂度，从而缓解维数灾难。
先把这段话拆开看。所谓“监督学习”，就是你手里有输入 (X) 和输出 (Y)，想学一个映射 (f(X)\approx Y)。在回归里，真正关心的是回归函数 (f(x)=\mathbb E[Y\mid X=x])；在分类里，关心的则是类别概率或决策边界。问题在于，如果你什么假设都不加，直接在高维空间里估计一个任意函数，数据需求会爆炸式增长，这就是“维数灾难”。比如一维里你可能只需要一些局部样本就能看出趋势，但到了十维、二十维，空间体积膨胀得非常快，样本会变得极其稀疏，模型很容易不稳。第 9 章的这些方法，本质上都是在说：别让函数“什么都能长”，给它加点骨架、加点形状约束，这样就能在较少数据下学得更稳。
但这也不是白捡的。你加了结构假设，就等于承诺“真实世界大概率长得像我假设的那样”。一旦假设错了，就会出现模型偏差，也就是你为了降低方差、减少维数灾难，付出了“模型设错型”的代价。所以这章的主线其实是一个经典权衡：结构越强，越容易拟合、越省数据，但越可能错；结构越弱，更灵活，但越吃数据、越容易不稳。作者说“在每种情形下都需要做出一个权衡”，指的就是这个。
这章列出的五种方法，虽然长相不同，但精神是一致的：都在“回归函数的结构”上做文章。
广义可加模型（GAM）假设函数可以写成各个变量单独作用的和，形式大致是
[
f(x_1,\dots,x_p)=\alpha+\sum_{j=1}^p f_j(x_j).
]
这意味着它不直接建模变量之间复杂的交互作用，而是假设“每个变量各管各的，再加起来就行”。这一下子就把高维问题拆成很多一维问题了。比如房价可能由面积、位置、楼层、房龄分别影响，GAM 假设这些影响先分开估，再相加。它的优点是可解释性强、维数灾难大幅缓解；缺点是如果真实关系里交互作用很强，比如“地段好时面积更值钱，地段差时面积不那么值钱”，那纯加性模型就会吃亏。
树（decision trees）走的是另一条路。它不假设函数是光滑的，而是假设特征空间可以被一层层切开，每个区域里输出相对简单。树通过“如果……那么……”的规则不断分裂空间，把复杂的整体函数变成一堆局部常数或局部简单模型。它特别适合处理变量间的非线性和交互，因为不同变量的组合会自然地对应到不同分支。优点是直观、可解释、能自动处理交互；缺点是单棵树通常不稳定、容易过拟合，而且边界是分段式的，不够平滑。
MARS（多元自适应回归样条）可以理解成“自动拼接的分段回归”。它试图用一组局部的样条基函数去拟合复杂关系，形式上比树更平滑，比纯线性模型更灵活。你可以把它看成在不同区间里用不同的斜率和弯曲程度来逼近函数。它的“自适应”体现在：哪些结点、哪些变量、哪些交互项需要引入，不是人工指定，而是算法自动搜索。它的优点是兼顾灵活性与平滑性；缺点是模型选择过程复杂，解释性一般也不如单棵树直接。
PRIM（Patient Rule Induction Method，耐心规则归纳法）更像是在高维空间里“耐心地挖箱子”。它不是想把整个函数都拟合得很精细，而是寻找某个区域，使得在这个区域里响应变量特别高或特别低。比如在医学里，你可能更关心“哪些人群属于高风险子群”，PRIM 就会一步步收缩区域，找出一个“盒子”——一个满足某些条件的样本子集，在这个子集里目标变量的平均值特别极端。它特别适合做子群发现、风险人群筛选、规则发现。它强调的是“找局部高浓度区域”，而不是全局精确函数拟合。
HME（混合层次专家）则是把“分工合作”的思想引入模型里。它由若干个“专家模型”和一个“门控模型”组成：不同专家负责不同子区域或不同模式，门控模型负责决定在什么输入下该更相信哪个专家。你可以把它理解成一种“树形的软版本”：树是硬切分，HME 是软分配；树是每个样本只能走一条路，HME 则允许不同专家按概率共同参与。它很适合真实世界里存在“多个机制”的情况，比如某些输入区间由一种规律主导，另一些区间由另一种规律主导。它的优势是能表达复杂分段结构；难点是训练更复杂，容易陷入局部最优。
所以，这一章的真正意思可以概括成一句话：当我们面对高维监督学习时，与其假设目标函数完全未知、任其自由生长，不如预先假设它有某种“可分解、可切分、可拼接、可局部规则化、可专家分工”的结构，然后利用这种结构去降低学习难度。你可以把这看成是“用先验结构对抗维数灾难”。
如果再往深一点理解，这一章和前面 3–6 章的关系是：前面讲的是更通用、更基础的学习思想；第 9 章开始进入“结构化建模”的世界。也就是说，模型不再单纯追求万能，而是开始追求“在某类问题上特别好用”。这也是统计学习里很重要的一步：真正强的模型，很多时候不是最自由的模型，而是最会利用问题结构的模型。
树：把特征空间一刀一刀切开，每个区域里给一个简单预测。
MARS：用很多“分段线性”的小零件，把函数拼出来。
PRIM：不追求拟合整个函数，只找那些响应特别高或特别低的“高纯度区域”。
1. 树：decision tree / regression tree 到底在干什么
树的方法的核心思想非常朴素：
不要直接拟合一个复杂函数，而是先把输入空间分成很多小块，再在每个小块里用简单规则预测。
比如你有两个变量 (x_1, x_2)，树可能先问：
“(x_1 < 3.5) 吗？”
如果是，走左边；如果不是，走右边。
然后在左边那块里再问：“(x_2 < 7) 吗？”
这样一层层切下去，最后每个叶子节点对应一个区域，在这个区域里输出一个常数，回归树就是取叶子里的均值，分类树就是取叶子里的多数类。
你可以把树理解成什么
它把整个特征空间切成很多个“长方体区域”或“块状区域”，每块内部假设目标函数比较简单。
所以它不是去拟合“全局平滑曲线”，而是拟合“分段常数函数”。
树为什么能缓解维数灾难
因为它不是在整个高维空间里做精细插值，而是只在局部区域里估计简单量，比如均值或类别比例。
高维问题难，是因为你要在整个空间里找精确形状；树把复杂问题拆成很多局部小问题，每个小问题样本需求更低。
树怎么长出来
典型的回归树或分类树，都是“贪心递归分裂”：
-
从根节点开始，考虑所有变量和所有切分点；
-
找一个切分，使得切完之后，损失下降最多；
-
继续对左右子节点重复这个过程；
-
直到达到停止条件，比如节点太小、纯度已经足够高、深度太深等。
回归树里常用的目标是让每个区域内部的平方误差最小；分类树里常用的是 Gini 指数、交叉熵或误分类率。
树的优点
它最大的优点是直观、可解释。
你可以把一棵树直接翻译成人话规则，比如“如果年龄大于 40 且收入低于某值，则……”。
它还能天然处理变量交互。
比如“面积大不大”对价格的作用，可能要结合“地段好不好”才有意义，树会自动把这种交互编码进不同分支里。
树的缺点
树也很有脾气。
第一，它不稳定。数据稍微变一点，切分点就可能换，树结构会大变。
第二，它容易过拟合，尤其是长得太深的时候。
第三，树的边界是“硬切”的，不平滑，预测函数像台阶。
第四，单棵树通常泛化一般，所以现实里经常会接随机森林、Boosting 这种“树的集成”。
ESL 里你应该抓住的重点
ESL 讲树，不只是让你会画树，而是让你理解：
“递归分割”是一种非常强的结构假设。
它假设真实函数可以通过区域划分来近似，而不是通过一个全局公式来近似。
2. MARS：Multivariate Adaptive Regression Splines
这个名字听着很吓人，但其实思想比树还“平滑”。
MARS 的核心可以概括成一句话：
用很多“折线零件”去拼一个复杂函数，而且这些零件的位置和形状是自动选出来的。
先理解 spline 是什么
样条（spline）最简单的理解就是分段多项式。
比如在某个点前后，函数用不同的线段或曲线描述，但在拼接点处要求连续，通常还要求导数也连续。
这样比硬切台阶更平滑。
MARS 最经典的基函数是这种“铰链函数”（hinge function）：
[
(x-t)+ = \max(0, x-t)
]
和
[
(t-x)+ = \max(0, t-x)
]
它们的意思很简单：
在阈值 (t) 的左边或右边，函数开始“启用”。
比如 ((x-5)_+) 在 (x \le 5) 时是 0，超过 5 后就开始线性增长。
这就像“过了某个门槛以后，变量才开始起作用”。
MARS 在做什么
它想表示的函数大致是：
[
f(x)=\beta_0+\sum_{m=1}^M \beta_m B_m(x)
]
这里 (B_m(x)) 不是普通多项式，而是由很多 hinge functions 组合出来的基函数，有时还包含变量交互。
为什么它叫“自适应”
因为这些结点 (t)、变量组合、交互阶数，不是人工指定的，而是算法自动搜索出来的。
典型过程分两步：
第一步：前向选择
从常数函数开始，逐渐加入新的基函数。
每次都尝试在某个变量、某个切点上加一对 hinge basis，让拟合误差下降最多。
注意这里“加一对”很关键。
因为一个切点通常会产生左右两边两个基函数，例如：
[
(x-t)+,\quad (t-x)+
]
这样模型能在切点两侧分别有不同的斜率。
第二步：后向剪枝
前向加入很多基函数后，模型可能太复杂，于是再从大模型里删掉一些不重要的项。
删的时候不是完全靠训练误差，而是用类似 GCV（generalized cross validation）这样的准则，平衡拟合程度和复杂度。
MARS 和树的区别
树是“区域常数模型”或“分段常数模型”，边界是硬的。
MARS 更像“连续折线/分段线性模型”，边界是平滑衔接的。
你可以粗暴地理解成：
树：这个区域一个值，那个区域另一个值。
MARS：在某个阈值之后，斜率变了，但函数还是连着的。
所以 MARS 比树更平滑，也往往更适合数值型回归问题。
MARS 的优点
第一，能自动发现非线性。
第二，能自动处理一部分变量交互。
第三，比树平滑，通常拟合连续关系更自然。
第四，可解释性还不错，因为你能看到哪些变量、哪些阈值被选中了。
MARS 的缺点
第一，模型结构比树复杂，理解和实现都更绕。
第二，如果交互关系很复杂，基函数会很多。
第三，对噪声也可能敏感。
第四，虽然比黑箱好一些，但解释性通常不如简单树那么直接。
你该怎么记它
记成一句话：
MARS = 自动找“折点”的分段回归，像在拼积木，但积木的每块都是线性零件。
3. PRIM：Patient Rule Induction Method
PRIM 这个方法很多人第一次看会觉得有点怪，因为它不是在追求“全局最优预测函数”，而是在找“特别纯”的区域。
它到底在做什么
它的目标通常是从数据里挖出一个区域，这个区域里面的响应变量特别高，或者特别低，或者某个类别特别集中。
也就是说，它关注的是“子群发现”：
-
哪一小块人群风险最高？
-
哪一小块样本的收益最高？
-
哪一类区域里目标值特别极端？
它不是想着把整个 (f(x)) 拟合得很准，而是更像在找“危险区”“高收益区”“异常区”。
为什么叫 patient
因为它的算法风格很“耐心”：
一点一点地缩小区域，慢慢挖，直到找到一个满意的盒子。
它的基本思想
PRIM 通常在特征空间里寻找一个“盒子”或“hyper-rectangle”：
[
a_j \le x_j \le b_j
]
对每个变量 (x_j) 给出上下界，最后形成一个高维盒子。
这个盒子里的样本，响应均值可能显著高于总体，或者某一类的比例显著更高。
它怎么找这个盒子
很直观：
-
从整个空间开始；
-
看哪个边界稍微往里收缩一点后，盒子里的目标均值会更高，或者纯度更强；
-
每次只“剥掉”一小层，像削苹果一样慢慢削；
-
继续重复，直到盒子已经足够“纯”，或者再削就不划算。
所以 PRIM 的操作不是“切成很多块”，而是“收缩一个区域”，把这个区域变得越来越浓缩。
PRIM 的“纯”是什么意思
“纯”不是道德纯洁，是统计意义上的纯。
意思是这个盒子里的样本，在你关心的响应变量上表现得很一致。
比如二分类任务里，一个盒子里 90% 都是正类，那这个盒子就很“纯”。
回归里，一个盒子里响应值显著高于全局平均，那也是一种“纯”。
PRIM 的适用场景
它特别适合：
-
想找高风险人群；
-
想找某种行为模式的局部区域；
-
想做规则发现；
-
想做异常子群分析。
它不像普通预测模型那样追求整体误差最小，而是更像“局部挖矿”。
PRIM 的优点
第一，非常适合做区域发现和规则提取。
第二，结果通常很容易解释，因为最后就是一个个变量范围组成的盒子。
第三，适合发现少数但重要的极端区域。
PRIM 的缺点
第一，它找的是轴对齐的盒子，所以表达能力有限。
第二，若真实高纯区域不是长方体形状，它可能拟合得不够好。
第三，和树相比，它更偏“发现区域”，不是完整预测器。
第四，算法偏贪心，结果可能依赖数据和参数。
你可以这样记
PRIM = 在高维空间里“慢慢收口”，找出一块目标值特别极端的盒子。
4. 三者放在一起对比
这三个方法很容易混，但只要抓住“它们对空间的处理方式”就不容易乱。
树：把空间切成很多块，每块一个简单输出。
MARS：用分段线性基函数，把函数平滑拼出来。
PRIM：找一个纯度高的盒子，重点是局部区域而不是全局拟合。
再说得更抽象一点：
树关注“分区”。
MARS 关注“基函数展开”。
PRIM 关注“子群挖掘”。
它们都在对抗维数灾难，但策略不同：
-
树：通过局部划分降低难度；
-
MARS：通过低维基函数组合降低难度；
-
PRIM：通过只关注少数关键区域降低难度。
5. 从学习目标看，它们各自像什么
树像一个“问答系统”。
你一层层回答条件，最后走到某个叶子，得到预测。
MARS 像一个“自动造函数”的工厂。
它不断加入折点和交互项，最后拼出一个曲线。
PRIM 像一个“采矿机”。
它不断缩小范围，挖出一块高价值矿脉。
6. ESL 里读这三章时最该抓的主线
你读 ESL 的时候，不要只记算法步骤，要记住它们为什么存在：
因为高维里直接拟合很难，所以我们要利用结构假设。
树假设：函数可以分区表达。
MARS 假设：函数可以由局部折线基函数拼出。
PRIM 假设：我们只关心某些局部高纯子区域。
所以这几章的共同哲学就是：
不是所有问题都值得用一个“全局大黑箱”去拟合，很多时候，聪明地限制函数形状，比疯狂增加模型自由度更有效。
MARS (多变量自适应样条) 深度总结
1. 核心模型表达式（函数展开）
MARS 的本质是将一个复杂的未知函数 f(X) 拆解为一系列**基函数（Basis Functions）**的线性加权组合：
\hat{f}(X) = \beta_0 + \sum_{m=1}^{M} \beta_m B_m(X)
-
$\beta_0$: 截距（全局偏置）。
-
$B_m(X)$: 从“基函数字典”中挑选出的特定函数。
-
$\beta_m$: 对应基函数的系数（通过最小二乘法拟合）。
2. 基函数字典：铰链函数对 (Hinge Functions)
这是 MARS 的“原子单位”。它不像多项式那样使用 $x^k$，而是使用成对的分段线性函数：
-
$c(x, t) = [+(x - t)] = \max(0, x - t)$
-
$c(t, x) = [+(t - x)] = \max(0, t - x)$
你的“字典”理解：
在训练开始前，字典里包含了所有变量 X_j 在所有观测值 x_{ij} 处可能形成的铰链函数。算法的任务就是从这个近乎无限的字典里，挑选出对降低 MSE 贡献最大的那一小部分。
3. 算法执行逻辑：两阶段优化
第一阶段：前向生长（Forward Pass）—— 贪心拆解
这对应你说的“按字典拆解”。
-
动作：从只有
\beta_0开始，反复迭代。每次寻找一对新的基函数（及其乘积形式）加入模型。 -
准则：穷举所有变量和所有节点，选择能使当前 残差平方和 (RSS) 下降最多的那一个对。
-
结果：为了捕捉复杂的非线性，模型会变得非常臃肿，包含大量细小的“折痕”，导致严重过拟合。
第二阶段：后向剪枝（Backward Pass）—— 结构优化
这对应你说的“调节参数直到最小”。但为了防止过拟合，它引入了广义交叉验证 (GCV)：
-
动作：逐个尝试删除基函数。
-
准则：使用 GCV 评分，它在 MSE 的基础上给基函数的数量加上了“惩罚项”。
-
目标：在“模型精度”和“模型复杂程度”之间找到帕累托最优解。
4. 关键特性总结（与回归树的对比）
| 维度 | MARS 的完全正确描述 | 对应你的直觉 |
| 函数形状 | 连续的分段线性曲线。在节点处相接，保证了预测值的平滑过渡。 | “分段拆解” |
| 特征交互 | 通过基函数相乘实现。例如 B_i \times B_j 捕捉变量间的协同效应。 |
“多变量自适应” |
| 自适应性 | 节点（Knots）的位置和数量完全由数据驱动生成。 | “特定的基函数字典” |
| 拟合本质 | 局部回归的一种。它通过局部线性来逼近全局非线性。 | “按照基函数展开” |
最终总结：
MARS 是一种自适应的非参数回归技术。它通过穷举搜索，将输入空间划分为多个由“铰链函数”定义的局部区域。在每个区域内，它利用分段线性函数的组合来拟合数据。它通过“前向生长”来捕捉复杂的局部趋势和特征交互，再通过“后向剪枝”利用 GCV 准则去除冗余，最终实现一个连续、平滑且具备强泛化能力的非线性拟合模型。
从你熟悉的 C++/Rust 视角来看：
如果回归树是 switch-case 语句，那么 MARS 就是一个自动生成的插值表 (Lookup Table)，它不仅存了每个区间的起始值，还存了每个区间内的斜率，并且确保了在每个 if 分支的边界处，计算结果是平滑对接的。
- 坐标上升法：类似调整法，每一次只动一个参数，实现在这个维度的最小化。
EM 算法最值得抓住的，其实就一句话：当直接最大化含隐变量的对数似然很难时，就先“猜”隐变量的分布，再在这个猜测下最大化参数。 它本质上是在做一个“交替优化”，只不过这个交替不是随便来的，而是由 Jensen 不等式和变分下界严格推出来的。
我按“从问题定义 → 为什么难 → 怎么造下界 → 为什么分成 E/M 两步 → 为什么单调上升 → 以高斯混合为例”的顺序给你一步一步推。
1. 问题到底长什么样
设观察到的数据是 (X={x_1,\dots,x_n})，模型参数是 (\theta)，另外还有一组你看不见的隐变量 (Z={z_1,\dots,z_n})。
如果隐变量也看得见，那么联合分布是：
[ p(X,Z\mid \theta) ]
对应的“完整数据对数似然”就是：
[ \log p(X,Z\mid \theta) ]
但现实里你只能看到 (X)，看不到 (Z)，所以真正要最大化的是“缺失数据对数似然”：
[ \ell(\theta)=\log p(X\mid \theta)=\log \sum_Z p(X,Z\mid \theta) ]
如果 (Z) 是连续的，就把求和换成积分：
[ \ell(\theta)=\log \int p(X,Z\mid \theta),dZ ]
困难就出在这里：log 在积分外面，积分里又有参数 (\theta)，一般没法直接求导后漂亮求解。
2. 为什么直接最大化这么难
直接对
[ \log \sum_Z p(X,Z\mid \theta) ]
求导，形式上会得到：
[ \nabla_\theta \ell(\theta)
\frac{1}{p(X\mid\theta)} \nabla_\theta \sum_Z p(X,Z\mid \theta) ]
整理后可以写成：
[ \nabla_\theta \ell(\theta)
\sum_Z p(Z\mid X,\theta)\nabla_\theta \log p(X,Z\mid\theta) ]
这个式子本身是对的，但问题是它仍然把 (p(Z\mid X,\theta)) 和 (\theta) 强耦合在一起。很多模型里这个后验分布并不好直接处理，于是我们引入 EM。
3. EM 的核心：先构造一个下界
关键一步是引入任意一个分布 (q(Z))。对边际似然：
[ \log p(X\mid\theta)=\log \sum_Z q(Z)\frac{p(X,Z\mid\theta)}{q(Z)} ]
若 (Z) 连续则为：
[ \log p(X\mid\theta)=\log \int q(Z)\frac{p(X,Z\mid\theta)}{q(Z)},dZ ]
因为 (\log) 是凹函数，所以 Jensen 不等式给出：
[ \log \int q(Z)\frac{p(X,Z\mid\theta)}{q(Z)},dZ \ge \int q(Z)\log \frac{p(X,Z\mid\theta)}{q(Z)},dZ ]
于是定义一个下界：
[ \mathcal{L}(q,\theta)
\int q(Z)\log p(X,Z\mid\theta),dZ
\int q(Z)\log q(Z),dZ ]
也就是
[ \mathcal{L}(q,\theta)
\mathbb E_q[\log p(X,Z\mid\theta)] + H(q) ]
其中 (H(q)) 是熵：
[ H(q)=-\mathbb E_q[\log q(Z)] ]
于是我们得到：
[ \log p(X\mid\theta)\ge \mathcal{L}(q,\theta) ]
这就是 EM 的“变分下界”思想，只不过传统 EM 里我们选的 (q) 很特殊。
4. 下界和真实似然之间的精确关系
把下界和真实似然差一下，可以得到一个非常重要的恒等式：
[ \log p(X\mid\theta)
\mathcal{L}(q,\theta) + \mathrm{KL}!\left(q(Z),|,p(Z\mid X,\theta)\right) ]
其中
[ \mathrm{KL}(q|p)=\int q(Z)\log\frac{q(Z)}{p(Z)},dZ \ge 0 ]
所以：
-
(\mathcal{L}(q,\theta)) 永远不超过真实对数似然；
-
当且仅当 [ q(Z)=p(Z\mid X,\theta) ] 时，KL 为 0，下界贴紧真实似然。
这个等式非常关键，因为 EM 的每一步其实都在让这个下界尽量贴住真实似然，并把它往上推。
5. EM 为什么分成 E 步和 M 步
我们想最大化 (\log p(X\mid\theta))，但它难。 于是改为交替最大化下界 (\mathcal{L}(q,\theta))。
E 步：固定 (\theta^{(t)})，优化 (q)
先在当前参数 (\theta^{(t)}) 下，令下界最紧。 因为
[ \log p(X\mid\theta^{(t)})
\mathcal{L}(q,\theta^{(t)}) + \mathrm{KL}!\left(q(Z),|,p(Z\mid X,\theta^{(t)})\right) ]
为了让 (\mathcal{L}) 最大，等价于让 KL 最小。KL 最小值是 0，所以最优解就是：
[ q^{(t+1)}(Z)=p(Z\mid X,\theta^{(t)}) ]
这就是 E 步。 它的含义非常直白：用当前参数，计算隐变量的后验分布。
M 步：固定 (q^{(t+1)})，优化 (\theta)
在 E 步把 (q) 变成当前后验之后，接着最大化下界：
[ \theta^{(t+1)}
\arg\max_\theta \mathcal{L}(q^{(t+1)},\theta) ]
由于 (H(q)) 与 (\theta) 无关，所以等价于最大化：
[ \theta^{(t+1)}
\arg\max_\theta \mathbb E_{q^{(t+1)}}[\log p(X,Z\mid\theta)] ]
而因为 (q^{(t+1)}=p(Z\mid X,\theta^{(t)}))，所以常写成：
[ Q(\theta,\theta^{(t)})
\mathbb E_{Z\mid X,\theta^{(t)}}[\log p(X,Z\mid\theta)] ]
M 步就是：
[ \theta^{(t+1)}=\arg\max_\theta Q(\theta,\theta^{(t)}) ]
这就是 EM 的标准形式。
6. 这两个步骤为什么合理
你可以这样理解：
E 步是在问： “按现在这套参数，我最相信隐变量怎么分布？”
M 步是在问： “既然隐变量大概是这样，那我应该把参数往哪调，才能让完整数据的解释最好？”
它的本质是一个坐标上升法，只不过上升的对象不是原始似然，而是下界。
7. 单调上升性怎么证明
这是 EM 最漂亮的一点：每次迭代都不会让观测数据对数似然变差。
设当前参数为 (\theta^{(t)})，下一步参数为 (\theta^{(t+1)})。
E 步后取
[ q^{(t+1)}(Z)=p(Z\mid X,\theta^{(t)}) ]
于是下界在当前点是紧的：
[ \log p(X\mid\theta^{(t)})=\mathcal{L}(q^{(t+1)},\theta^{(t)}) ]
M 步选择使下界增大的参数：
[ \mathcal{L}(q^{(t+1)},\theta^{(t+1)}) \ge \mathcal{L}(q^{(t+1)},\theta^{(t)}) ]
又因为下界永远不超过真实对数似然：
[ \log p(X\mid\theta^{(t+1)}) \ge \mathcal{L}(q^{(t+1)},\theta^{(t+1)}) ]
把这两句连起来：
[ \log p(X\mid\theta^{(t+1)}) \ge \mathcal{L}(q^{(t+1)},\theta^{(t+1)}) \ge \mathcal{L}(q^{(t+1)},\theta^{(t)})
\log p(X\mid\theta^{(t)}) ]
所以：
[ \log p(X\mid\theta^{(t+1)}) \ge \log p(X\mid\theta^{(t)}) ]
这就证明了 EM 的观测似然单调不下降。
注意，是“不下降”，不是“每次都找到全局最优”。 EM 常常只会收敛到局部最优或鞍点。
8. 一个更直观的理解：EM 在做“补全数据”
想象完整数据 (X,Z) 如果都知道，那参数估计很容易。 EM 就是在反复做：
-
先用当前参数“补全”缺失部分，得到隐变量的概率分配；
-
再拿这个“软补全”的完整数据去估计参数。
所以 EM 也常被叫成“soft assignment”的方法。 它不是硬把一个样本分给某个隐类，而是给出每个隐类的责任度（responsibility）。
9. 高斯混合模型（GMM）是 EM 最经典的例子
下面把公式彻底推一遍，这个是最有用的。
9.1 模型设定
假设数据 (x_1,\dots,x_n) 来自 (K) 个高斯混合成分。 引入隐变量 (z_i\in{1,\dots,K})，表示第 (i) 个样本属于哪个簇。
模型参数为：
[ \theta={\pi_k,\mu_k,\Sigma_k}_{k=1}^K ]
其中：
[ \pi_k\ge 0,\quad \sum_{k=1}^K \pi_k=1 ]
条件分布：
[ p(z_i=k)=\pi_k ]
[ p(x_i\mid z_i=k)=\mathcal N(x_i\mid \mu_k,\Sigma_k) ]
于是边际分布是：
[ p(x_i\mid\theta)=\sum_{k=1}^K \pi_k \mathcal N(x_i\mid \mu_k,\Sigma_k) ]
整个数据的对数似然：
[ \ell(\theta)=\sum_{i=1}^n \log \sum_{k=1}^K \pi_k \mathcal N(x_i\mid \mu_k,\Sigma_k) ]
这就是典型的“log-sum”结构，直接优化很麻烦。
9.2 完整数据似然
若 (z_i) 已知，那么完整数据似然变成：
[ p(X,Z\mid\theta)=\prod_{i=1}^n \prod_{k=1}^K \left[\pi_k \mathcal N(x_i\mid\mu_k,\Sigma_k)\right]^{\mathbf 1(z_i=k)} ]
取对数：
[ \log p(X,Z\mid\theta)
\sum_{i=1}^n\sum_{k=1}^K \mathbf 1(z_i=k) \left[ \log \pi_k+\log \mathcal N(x_i\mid\mu_k,\Sigma_k) \right] ]
如果 (z_i) 真知道，这个最大化其实就是分类统计，特别容易。
9.3 E 步：算责任度
E 步要计算后验：
[ \gamma_{ik}
p(z_i=k\mid x_i,\theta^{(t)}) ]
用贝叶斯公式：
[ \gamma_{ik}
\frac{ \pi_k^{(t)} \mathcal N(x_i\mid \mu_k^{(t)},\Sigma_k^{(t)}) }{ \sum_{j=1}^K \pi_j^{(t)} \mathcal N(x_i\mid \mu_j^{(t)},\Sigma_j^{(t)}) } ]
这个 (\gamma_{ik}) 就叫 responsibility，意思是“第 (k) 个成分对样本 (i) 负责的程度”。
注意它满足：
[ \gamma_{ik}\ge 0,\qquad \sum_{k=1}^K \gamma_{ik}=1 ]
它不是硬分类，而是软分配。
9.4 M 步：最大化期望完整数据对数似然
M 步要最大化：
[ Q(\theta,\theta^{(t)})
\mathbb E_{Z\mid X,\theta^{(t)}}[\log p(X,Z\mid\theta)] ]
把上面的完整数据对数似然代进去：
[ Q(\theta,\theta^{(t)})
\sum_{i=1}^n\sum_{k=1}^K \gamma_{ik} \left[ \log \pi_k+\log \mathcal N(x_i\mid\mu_k,\Sigma_k) \right] ]
接下来分别对 (\pi_k,\mu_k,\Sigma_k) 求最大。
9.4.1 更新 (\pi_k)
约束是 (\sum_k \pi_k=1)。 设：
[ N_k=\sum_{i=1}^n \gamma_{ik} ]
这表示第 (k) 个簇的“有效样本数”。
则最优更新为：
[ \pi_k^{(t+1)}=\frac{N_k}{n} ]
意思很简单：某个簇获得的总责任越多，它的混合权重越大。
9.4.2 更新 (\mu_k)
对 (Q) 关于 (\mu_k) 求导，利用高斯对数密度：
[ \log \mathcal N(x_i\mid\mu_k,\Sigma_k)
-\frac12\left[ d\log(2\pi)+\log|\Sigma_k|+(x_i-\mu_k)^\top\Sigma_k^{-1}(x_i-\mu_k) \right] ]
只看和 (\mu_k) 有关的部分：
[ -\frac12\sum_{i=1}^n\gamma_{ik}(x_i-\mu_k)^\top\Sigma_k^{-1}(x_i-\mu_k) ]
对 (\mu_k) 求导并令其为 0，可得：
[ \mu_k^{(t+1)}=\frac{1}{N_k}\sum_{i=1}^n\gamma_{ik}x_i ]
这就是加权均值。 权重就是样本对该簇的责任度。
9.4.3 更新 (\Sigma_k)
同理，对协方差求最大，得到：
[ \Sigma_k^{(t+1)}
\frac{1}{N_k}\sum_{i=1}^n \gamma_{ik} (x_i-\mu_k^{(t+1)})(x_i-\mu_k^{(t+1)})^\top ]
这也是加权协方差。
10. GMM 里的 EM 为什么特别像“软 K-means”
如果你把每个簇的协方差设成相同且是球形的，比如 (\Sigma_k=\sigma^2 I)，再进一步让 (\sigma^2) 固定，那么 E 步的责任度会越来越接近“谁近就分给谁”。 这时 EM 的行为就越来越像 K-means。
所以可以这么理解：
-
K-means 是硬分配；
-
GMM-EM 是软分配；
-
K-means 可以看成 GMM 在某些极限条件下的特例。
11. EM 的本质和几个常见误解
11.1 EM 不一定每次都“更好地拟合真实世界”
它只是让对数似然不下降。 但对数似然高，不代表泛化一定好。
11.2 EM 不保证全局最优
因为似然函数通常是非凸的。 所以初值很重要，常见做法是多次随机初始化。
11.3 E 步不是“凭空猜”
E 步其实是严格地算后验分布，只不过这个后验是在当前参数下计算出来的。
11.4 M 步不是总能解析求解
有些模型的 M 步没有闭式解，这时就要用数值优化，甚至会出现广义 EM（GEM）：不要求 M 步完全最优，只要让下界上升即可。
12. 从数学上再压缩成一个统一框架
EM 其实就是在最大化：
[ \log p(X\mid\theta) ]
但它不直接做，而是引入 (q(Z))，构造：
[ \mathcal{L}(q,\theta)=\mathbb E_q[\log p(X,Z\mid\theta)] + H(q) ]
然后交替：
[ q^{(t+1)}=\arg\max_q \mathcal{L}(q,\theta^{(t)}) ]
[ \theta^{(t+1)}=\arg\max_\theta \mathcal{L}(q^{(t+1)},\theta) ]
其中第一步给出：
[ q^{(t+1)}(Z)=p(Z\mid X,\theta^{(t)}) ]
第二步就是最大化：
[ Q(\theta,\theta^{(t)})
\mathbb E_{Z\mid X,\theta^{(t)}}[\log p(X,Z\mid\theta)] ]
这就是标准 EM。
13. 你真正要记住的直觉
如果把“隐变量”看成缺失的信息，那么 EM 的思路就是：
先根据当前模型把缺失信息补成“概率版答案”，再在这个答案上重新估参数。 它是“先软填空，再重算分数”。
14. 一个最简记忆版公式链
你复习时只记这条链就够了：
[ \log p(X\mid\theta)
\log \int p(X,Z\mid\theta),dZ ]
引入 (q(Z))：
[ \log p(X\mid\theta) \ge \mathbb E_q[\log p(X,Z\mid\theta)] + H(q) ]
E 步：
[ q(Z)=p(Z\mid X,\theta^{(t)}) ]
M 步：
[ \theta^{(t+1)}=\arg\max_\theta \mathbb E_{Z\mid X,\theta^{(t)}}[\log p(X,Z\mid\theta)] ]
GMM 里：
[ \gamma_{ik}
\frac{ \pi_k \mathcal N(x_i\mid\mu_k,\Sigma_k) }{ \sum_j \pi_j \mathcal N(x_i\mid\mu_j,\Sigma_j) } ]
[ \pi_k=\frac{N_k}{n},\quad \mu_k=\frac{1}{N_k}\sum_i \gamma_{ik}x_i,\quad \Sigma_k=\frac{1}{N_k}\sum_i\gamma_{ik}(x_i-\mu_k)(x_i-\mu_k)^\top ]
既然你已经彻底理解了 EM 的“拉动下界”和“横向爬升”，那么把这个逻辑套进 HME（分层专家混合） 就非常顺理成章了。
在 HME 中，我们面临的最大困难是：当观察到一个输入 x 产生输出 y 时，我们不知道这个任务在树状结构中到底走的是哪条路径（即：不知道哪个经理指派了哪个员工）。这些路径选择就是隐变量 $Z$。
下面我们用你最熟悉的“贴合-爬升”逻辑来拆解 HME 的训练：
1. HME 的“山坡”是什么？
HME 的目标函数（对数似然）是一个非常复杂的嵌套结构：
\ell(\theta) = \log \sum_{i} \text{Gate}_i(x) \left( \sum_{j} \text{SubGate}_{ij}(x) \cdot \text{Expert}_{ij}(x) \right)
你会发现这里面有两层 $\sum$ 嵌套在 \log 里面。直接求导简直是灾难。
2. E 步：拉动下界（算责任，找“贴合点”）
在这一步，我们固定所有的门控参数（管理层）和专家参数（员工）。
-
逻辑：我们要计算出，给定当前的参数，每一个样本
(x, y)归属于某条路径的后验概率。 -
操作：
-
自下而上：每个专家计算自己的预测误差。如果专家 A 预测得准，那么他在这个样本上的“信任分”就高。
-
贝叶斯修正：将门控给出的“预判概率”与专家的“信任分”结合。
-
-
结果：你得到了一组权重 $h_{ij}$（责任度）。这就是你说的**“拉动下界上升”**——你通过这组权重，构造了一个简单的线性加权函数作为下界，这个函数在当前参数点正好贴住了那个复杂的嵌套
\log函数。
3. M 步：横向爬升（各自优化，寻找 $\arg\max$）
现在下界已经贴好了，h_{ij} 已经固定成了常数。你会惊喜地发现，原本死死缠在一起的参数解耦了！
在下界函数上，我们可以分别对每一部分进行最大化：
A. 专家的爬升（员工内省）
每个专家只需解决一个加权最小二乘问题：
\theta_{expert}^{new} = \arg\max \sum (\text{责任权重} \times \text{预测准确度})
- 直觉：专家只看那些“点名”让他负责的样本。由于权重
h是常数，这变成了最简单的回归问题。
B. 门控的爬升（领导进化）
每个门控网络（老板或经理）只需解决一个加权逻辑回归问题：
\theta_{gate}^{new} = \arg\max \sum (\text{责任权重} \times \log \text{门控输出})
- 直觉：门控网络学习如何调整自己的“眼光”，以便下次能把任务更准地派发给那些责任权重高的专家。
完成这一步后，你就找到了这个下界函数的最高点 $\theta_{t+1}$。
4. 为什么要这样“贴近解释”？
把 HME 放入 EM 框架后，原本混乱的过程变得极度有序：
-
E 步是在“分配功劳和锅”：它根据结果倒推，看看在这个输入下，谁更有可能是真正的功臣。这一步通过调整 $q(Z)$（即责任权重）把下界拉到了真实似然的高度。
-
M 步是在“各司其职”：有了明确的责任分配，专家去练技能（拟合数据），领导去练眼光（优化路由）。大家都在各自的局部下界上往
\arg\max跑。
总结 HME 的训练闭环：
-
E 步：利用贝叶斯法则计算路径后验（责任权重），让虚拟的线性加权下界在当前点贴死真实的嵌套对数似然。
-
M 步：利用这些权重，独立地通过加权回归更新每个专家和门控，实现参数在下界上的横向爬升。
-
迭代：带着更新后的“能力”和“眼光”回到 E 步，重新分配责任。
这套逻辑最漂亮的地方在于：它把一个深层嵌套的非线性问题，转化成了一系列独立的、加权的线性问题。 对于你处理底层系统或者高性能算力任务来说，这种天然的解耦结构简直是并行化的天堂。
Boosting树
既然你已经精通了 **EM 算法的“下界爬升”**和 HME 的“分工演化”，那么理解 Boosting（提升法） 对你来说会非常直观。
如果说 随机森林（Random Forest） 是“民主投票”（大家独立思考，投票取平均），HME 是“层级管理”（各司其职），那么 Boosting 就是**“错题集进阶法”**。它的核心逻辑是：不要求专家是全才，只要后一个专家能解决前一个专家留下的“错题”，累加起来就是天才。
1. 产生背景：从“弱”到“强”的哲学
Boosting 起源于计算学习理论中的一个著名问题：一组弱学习器（比随机猜好一点点）能否组合成一个强学习器？
-
Bagging（随机森林）：靠“并行”和“平均”来降低方差（Variance）。
-
Boosting：靠“串行”和“累加”来降低偏差（Bias）。它通过不断拟合残差，让模型从“啥也不懂”逐渐变成“专家”。
2. 公式推导：加法模型与前向分布算法
Boosting 的本质是一个加法模型（Additive Model）：
F_m(x) = F_{m-1}(x) + \alpha_m h_m(x)
-
$F_{m-1}(x)$：前
m-1棵树累加的总分。 -
$h_m(x)$：当前第
m棵树。 -
$\alpha_m$：这棵树的权重。
核心目标
我们要寻找 h_m 和 $\alpha_m$，使得总损失函数 \sum L(y_i, F_m(x_i)) 最小。但一次性优化所有树太难了，所以我们采用前向分步算法（Forward Stagewise Algorithm）：每一步只学一棵树，学完就固定，绝不回头改之前的树。
以平方损失为例（梯度提升的雏形）
如果损失函数是 $L(y, F) = \frac{1}{2}(y - F)^2$，那么在第 m 步，我们要最小化：
L = \frac{1}{2}[y - (F_{m-1}(x) + h_m(x))]^2 = \frac{1}{2}[\underbrace{(y - F_{m-1}(x))}_{\text{残差 } r} - h_m(x)]^2
你看，第 m 棵树去拟合的“目标”，其实就是前 m-1 棵树剩下的残差。
3. 两种主流流派
A. AdaBoost (Adaptive Boosting) —— 换权重
-
由来：1995 年提出。它不直接拟合残差，而是给样本加权重。
-
逻辑：
-
第一棵树分错了样本 A。
-
第二棵树训练时，样本 A 的权重被调高。第二棵树为了降低损失，被迫“重点关注”样本 A。
-
最后把所有树加权求和。
-
B. GBDT (Gradient Boosting Decision Tree) —— 换目标
-
由来：2001 年由 Friedman 提出。这是目前工业界（XGBoost, LightGBM）的真正基石。
-
逻辑：既然我们要让损失函数
L最小，最好的下降方向就是负梯度。-
在第
m步，每一棵树拟合的目标不是原 $y$，而是损失函数相对于当前预测值的负梯度：r_{im} = -\left[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]_{F=F_{m-1}} -
如果是平方损失，负梯度刚好就是残差。
-
如果是其他损失（如 Logistic 损失），负梯度就是一个复杂的数值，但逻辑是一样的。
-
4. 具体的训练流程（以 GBDT 为例）
假设你要预测房价，用 3 棵树来做 Boosting：
Step 1：初始化
先给一个初始值（通常是所有房价的平均值）。
F_0(x) = \text{mean}(y)
Step 2：迭代（第 m=1, 2, \dots, M 轮）
-
算“残差”（负梯度）：
计算每个样本当前的残差 $r_i = y_i - F_{m-1}(x_i)$。
-
种一棵树拟合残差：
用回归树（还记得之前讲的 MSE 切分点吗？）去拟合这些 $r_i$。
这棵树会把空间切块，每个叶子节点输出一个值 $c_{mj}$。
-
寻找步长（学习率）：
为了稳健，我们通常给这棵树乘一个很小的学习率 $\eta$（比如 0.1）。
-
更新模型：
F_m(x) = F_{m-1}(x) + \eta \sum c_{mj} I(x \in R_{mj})
Step 3：输出
累加所有树的结果：$F(x) = \sum \text{Trees}(x)$。
5. 深度对比：HME vs Boosting
你刚学完 HME，对比一下会很有意思：
| 维度 | HME (专家混合) | Boosting (提升树) |
| 执行方式 | 并行/层级。所有专家同时存在，门控决定谁上。 | 串行。一棵接一棵种，后一棵纠正前一棵。 |
| 数据关系 | 分而治之。数据被“软切分”给不同专家。 | 错题进阶。数据被反复利用，权重/目标不断变化。 |
| 拟合目标 | 拟合原始数据 $y$。 | 拟合当前模型的残差（负梯度）。 |
| EM 联系 | 专家是隐变量，用 EM 找局部最优。 | 每一棵树都是在一个特定的、由前人留下的梯度场中寻找方向。 |
6. 为什么它这么强？
-
精确度极高：它通过不断的“修补”，可以无限逼近任何复杂的函数。
-
鲁棒性：由于每棵树只学一小步（学习率小），不容易被噪声带偏。
-
自动特征选择：树模型天然会挑选最重要的特征进行分裂。
对于你熟悉的底层架构：
-
随机森林 像 RAID 1：数据冗余，多份拷贝，坏了一两份（树长歪了）也没关系，平均一下很稳。
-
Boosting 像 增量备份/流水线指令：第一步做完，第二步基于第一步的结果继续补强。如果第一步错了，第二步会拼命修正它。
总结一句话： Boosting 就是通过前向分步算法，把一个复杂的全局优化问题，拆解成了多个简单的“拟合残差”局部优化问题。
这种**“不断迭代纠错”**的思想，是不是和你写代码时通过多次测试、根据报错信息不断重构系统的过程如出一辙？