160 lines
13 KiB
Markdown
160 lines
13 KiB
Markdown
---
|
||
title: 9 第九章 增广模型，树，以及相关方法
|
||
draft: false
|
||
tags:
|
||
- ESL
|
||
---
|
||
## [逻辑架构图]
|
||
|
||
本章探讨的是“带强结构假设的监督学习方法”，从系统架构的角度来看，这等同于**用硬件拓扑（模型结构先验）来优化内存随机访问（维数灾难）**。其内在逻辑可划分为四个层级：
|
||
|
||
1. **架构哲学（System Philosophy）**：引入结构假设，对抗维数灾难（用特定的寻址模式代替全局随机寻址）。
|
||
|
||
2. **基础算子层（Base Primitives）**：
|
||
|
||
- **GAM**：独立并行处理（SIMD无交互）。
|
||
|
||
- **Trees**：递归离散分支（Hard Branching）。
|
||
|
||
- **MARS**：连续分段查找表（Piecewise Linear LUT）。
|
||
|
||
- **PRIM**：掩码过滤与高频缓存挖掘（Bitmask Subgrouping）。
|
||
|
||
3. **动态调度机制（Dynamic Dispatching）**：**HME (混合专家)** 与 **EM算法**，本质是利用变分下界实现运行时的软路由（Soft Routing）与责任分配。
|
||
|
||
4. **串行流水线增强（Sequential Pipeline）**：**Boosting**，通过前向残差反馈（类似指令流水线的错误重放机制）将弱算子串联为强系统。
|
||
|
||
|
||
---
|
||
|
||
## [深度整理正文]
|
||
|
||
### 第零层：核心世界观 —— 结构假设与维数灾难
|
||
|
||
第 9 章不再走“通用算法”的路线，而是开始讨论一类“带强结构假设的监督学习方法”。它们的核心思想不是盲目地在高维空间里硬拟合一个任意复杂的函数，而是先相信“真实的回归函数大概率有某种简单结构”，再利用这个结构去降维、降复杂度，从而缓解维数灾难。
|
||
|
||
所谓“监督学习”，手里有输入 $X$ 和输出 $Y$，想学一个映射 $f(X)\approx Y$。回归里关心的是 $f(x)=\mathbb E[Y\mid X=x]$；分类里则是类别概率或决策边界。如果不加假设，直接在高维空间估计任意函数，数据需求会爆炸。一维需要局部样本，十维、二十维空间体积膨胀极快，样本变得极其稀疏，模型极不稳定。第 9 章方法本质是：别让函数“什么都能长”，给它加点骨架、形状约束，在较少数据下学得更稳。
|
||
|
||
但这需要付出“模型设错型”的代价（模型偏差）。这章的主线是经典权衡：**结构越强，越容易拟合、越省数据，但越可能错；结构越弱，更灵活，但越吃数据、越容易不稳**。
|
||
|
||
**{底层系统视角扩充}**：{维数灾难在计算机系统中等同于**极其稀疏的巨大地址空间（Sparse Address Space）**。如果不加结构假设，相当于用一个巨大的一维数组（Flat Memory）去映射高维数据，会导致极低的**缓存命中率（Cache Hit Rate）**。而本章介绍的方法，本质上是在构建特定的**内存分页表（Page Tables）或哈希索引（Hash Indices）**，通过引入系统层面的强一致性“约束”，强行提升数据的“空间局部性（Spatial Locality）”，用牺牲一部分灵活性（偏差）来换取访存性能的绝对稳定（方差）。}
|
||
|
||
---
|
||
|
||
### 第一层：基础算子与空间切割机制（GAM / Trees / MARS / PRIM）
|
||
|
||
这四种方法都在“回归函数的结构”上做文章。
|
||
|
||
#### 1. GAM（广义可加模型）：独立管道流
|
||
|
||
假设函数可以写成各个变量单独作用的和：$f(x_1,\dots,x_p)=\alpha+\sum_{j=1}^p f_j(x_j)$。它假设“每个变量各管各的，再加起来就行”。比如房价受面积、位置、楼层分别影响。优点是可解释性强，高维问题拆成很多一维问题；缺点是忽略强交互作用。
|
||
|
||
**{底层系统视角扩充}**：{GAM 相当于 CPU 中的 **SIMD（单指令多数据流）向量化运算**或多个**无数据依赖的独立线程**。各个 $f_j(x_j)$ 之间不存在内存竞争和同步锁，极度容易并行计算，但在面对需要“跨线程通信”（特征交叉）的任务时表现无力。}
|
||
|
||
#### 2. 树 (Decision Trees)：离散条件分支与递归划分
|
||
|
||
树不假设函数光滑，而是通过“如果……那么……”规则（如 $x_1 < 3.5$），将特征空间一层层切分成“长方体区域”，在每个区域输出局部常数（均值或多数类）。它把复杂整体变成一堆局部简单模型。
|
||
|
||
- **缓解维数灾难**：不在整个高维空间精细插值，只在局部区域估计简单量。
|
||
|
||
- **生成过程（贪心递归）**：找一个切分点使损失（平方误差、Gini、交叉熵）下降最多，递归左右子节点。
|
||
|
||
- **优缺点**：直观、天然处理变量交互。但不稳定、极易过拟合、边界是“硬切”的分段函数阶梯。
|
||
|
||
**{底层系统视角扩充}**：{树在汇编层面是一颗庞大的 `cmp`（比较）与 `jle` / `jg`（条件跳转）指令构成的决策图。由于数据分布的不确定性，极深且复杂的决策树在推理时会引发极高的**分支预测惩罚（Branch Misprediction Penalty）**，频繁清空 CPU 流水线。它是一种典型的控制流（Control-Flow）驱动模型，而非数据流驱动模型。}
|
||
|
||
|
||
#### 3. MARS (多元自适应回归样条)：连续插值查找表
|
||
|
||
MARS 的核心是用很多“折线零件”拼出一个复杂函数。它使用“铰链函数对”：$(x-t)_+ = \max(0, x-t)$ 与 $(t-x)_+ = \max(0, t-x)$。模型为：$\hat{f}(X) = \beta_0 + \sum_{m=1}^{M} \beta_m B_m(X)$。
|
||
|
||
- **自适应机制**：
|
||
|
||
- **前向选择（贪心拆解）**：从字典里穷举所有变量和节点，加入铰链函数对（及交互乘积），使 RSS 下降最多。
|
||
|
||
- **后向剪枝（结构优化）**：用 GCV（广义交叉验证）准则，在 MSE 和基函数数量间找帕累托最优，删掉冗余。
|
||
|
||
- **优缺点对比**：树是“区域常数，硬切”；MARS是“分段线性，平滑连续”。MARS 自动找折点、处理交互、适合连续数值，但模型结构复杂。
|
||
|
||
**{底层系统视角扩充}**：{铰链函数 $\max(0, x-t)$ 在底层其实就是现代神经网络中最常用的 **ReLU 激活函数**的原语。MARS 的前向生成可以视作一种**JIT (Just-In-Time) 编译期的代码生成技术**；而其后向剪枝过程，则完美等价于编译器优化中的 **Dead Code Elimination（死代码消除）**，剥离那些对最终计算结果（GCV评分）贡献甚微的分支逻辑。它是一种**连续内存分布的插值查找表（LUT）**。}
|
||
|
||
|
||
#### 4. PRIM (耐心规则归纳法)：高纯度内存块挖掘
|
||
|
||
PRIM 不是追求全局最优，而是找“特别纯”的区域（子群发现、高风险人群）。它在特征空间找一个高维盒子 $a_j \le x_j \le b_j$。
|
||
|
||
- **算法逻辑（耐心削苹果）**：从全空间开始，每次选一个边界稍微往里收缩，使盒子里的目标均值更高或纯度更强，直到满足条件。
|
||
|
||
- **优缺点**：适合做区域发现、异常子群分析，规则易解释。但找的是轴对齐盒子，不是完整预测器。
|
||
|
||
**{底层系统视角扩充}**：{PRIM 相当于在巨大的海量数据堆中进行掩码过滤（Bitmask Filtering）操作。它不关心全局的内存布局，而是通过剥离边界（Bitwise AND 操作）来锁定包含高频热点数据的 **Cache Line（缓存行）**。这在数据库系统中类似于建立一个专用的、针对极端异常值的 Partial Index（部分索引）。}
|
||
|
||
|
||
---
|
||
|
||
### 第二层：动态调度引擎 —— EM算法的系统解构与 HME (专家混合)
|
||
|
||
HME (混合专家) 引入了“分工合作”机制：专家模型负责不同子区域，门控模型决定在什么输入下相信哪个专家。HME 的训练极度依赖 **EM 算法 (Expectation-Maximization)**。
|
||
|
||
#### 1. EM 算法的数学推导与坐标上升机制
|
||
|
||
EM 是为了解决含隐变量 $Z$ 的对数似然 $\log p(X\mid \theta)=\log \sum_Z p(X,Z\mid \theta)$ 直接最大化极其困难的问题（$\log$ 在积分求和外，强耦合）。
|
||
|
||
- **构造下界 (Jensen 不等式)**：引入分布 $q(Z)$，得到变分下界 $\mathcal{L}(q,\theta) = \mathbb E_q[\log p(X,Z\mid\theta)] + H(q)$。
|
||
|
||
- **恒等式核心**：$\log p(X\mid\theta) = \mathcal{L}(q,\theta) + \mathrm{KL}(q(Z) \| p(Z\mid X,\theta))$。
|
||
|
||
- **交替优化 (Coordinate Ascent)**：
|
||
|
||
- **E 步（拉紧下界）**：固定 $\theta^{(t)}$，优化 $q$。让 $\mathrm{KL}=0$，得到 $q^{(t+1)}(Z)=p(Z\mid X,\theta^{(t)})$。算出“责任度 (Responsibility)”。
|
||
|
||
- **M 步（横向爬升）**：固定 $q^{(t+1)}$，最大化期望完整数据对数似然 $\theta^{(t+1)} = \arg\max_\theta \mathbb E_{Z\mid X,\theta^{(t)}}[\log p(X,Z\mid\theta)]$。
|
||
|
||
- **高斯混合模型 (GMM)** 是软 K-means。E步算软分配 $\gamma_{ik}$；M步用加权数据更新 $\pi_k, \mu_k, \Sigma_k$。
|
||
|
||
**{底层系统视角扩充}**：{直接最大化似然等同于试图获取一把**全局阻塞锁（Global Mutex）**，在海量隐变量存在时会导致系统完全死锁。EM 算法本质上是一种**无锁并发设计（Lock-Free Design）与交替状态机**。E 步（算后验）相当于执行一次非破坏性的 Read 阶段，为各个数据点打上**读时钟版本号（软权重分配）**；M 步相当于 Write 阶段，根据这些版本号进行局部数据的**原子更新（横向爬升）**。通过下界定理，EM 保证了每次迭代的内存状态（似然）绝对不会回退。}
|
||
|
||
|
||
#### 2. HME 中的 EM 实现：化嵌套为解耦
|
||
|
||
HME 的目标函数有两层嵌套的 $\log \sum$，直接求导是灾难。
|
||
|
||
- **E 步（算责任，拉下界）**：固定管理层（门控）和员工（专家），自下而上计算后验概率。如果专家预测准，加上门控预判，得到责任权重 $h_{ij}$。
|
||
|
||
- **M 步（各司其职，横向爬升）**：下界贴好后，死缠的参数**解耦**了。
|
||
|
||
- **专家的爬升**：加权最小二乘回归，拟合数据。
|
||
|
||
- **门控的爬升**：加权逻辑回归，优化路由眼光。
|
||
|
||
**{底层系统视角扩充}**：{HME 是一种带有**动态分支预测（Dynamic Branch Prediction）**和**动态链接（Dynamic Linking）**的计算架构。门控网络就是一个软路由器（Soft Router）。M 步的解耦操作，在底层系统上完美实现了**计算任务的打散（Scatter）与收集（Gather）**，每一个加权回归任务可以被独立丢进不同的 GPU Stream 中并发执行，因为它们在数学上已经被完全隔离。}
|
||
|
||
|
||
---
|
||
|
||
### 第三层：串行纠错流水线 —— Boosting (提升树)
|
||
|
||
如果随机森林（Bagging）是“民主投票”降方差（并行），HME 是“层级管理”（EM找局部最优），那么 Boosting 就是“错题集进阶法”，靠“串行”和“累加”降低偏差（Bias）。
|
||
|
||
- **加法模型与前向分布**：$F_m(x) = F_{m-1}(x) + \alpha_m h_m(x)$。采用前向分步算法，每一步只学一棵树，学完固定。
|
||
|
||
- **GBDT (Gradient Boosting)**：在第 $m$ 步，当前树拟合的不再是原 $y$，而是损失函数相对于当前预测值的**负梯度（残差）**：$r_{im} = -\left[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]_{F=F_{m-1}}$。利用学习率 $\eta$ 稳步更新。
|
||
|
||
- **AdaBoost**：通过增加前一棵树分错样本的权重，迫使新树重点关注困难样本。
|
||
|
||
**{底层系统视角扩充}**：{Boosting 模型在计算机体系结构中对应着**深层指令流水线（Deep Instruction Pipeline）**。前向分步算法的本质是一种存在严重**写后读（RAW - Read After Write）数据依赖**的串行执行模式。第 $m$ 棵树必须等待第 $m-1$ 棵树的计算结果（残差/梯度）写入寄存器后才能开始执行，因此它**极难进行树级别的并行化**。相比之下，Bagging 就像是完全解耦的 RAID 1 镜像阵列，而 Boosting 更像是带有增量前馈纠错机制的**误差反向放大器**，通过一系列微小的增量补丁（学习率 $\eta$ 控制的细粒度操作），最终把一个高延迟的弱指令序列（弱学习器）编译成了一个高度精准的强力程序（强分类器）。}
|
||
|
||
|
||
---
|
||
|
||
## [边界知识联动]
|
||
|
||
为了将此章节心智模型与更广泛的系统知识彻底打通，你可以做如下联想：
|
||
|
||
1. **特征切分（Trees/MARS） vs. 内存分页与段错误（Paging & Segfaults）**：决策树的“硬切割”类似于内存管理的**分页机制（Paging）**，边界是绝对的，跨界即发生上下文切换；MARS 的“折线平滑”则类似于计算机图形学中的**抗锯齿（Anti-Aliasing）渲染缓冲**。
|
||
|
||
2. **PRIM vs. OOM (Out Of Memory) 诊断**：PRIM 寻找高风险极值区域的逻辑，和系统运维中使用火焰图（Flame Graph）从海量进程栈中，逐级过滤收缩（Shrinking），最终定位到导致内存泄漏（高浓度异常区域）的特定函数代码块一模一样。
|
||
|
||
3. **EM 算法的 E-M 交替 vs. CPU Cache 的 MESI 协议**：E 步（计算责任度）相当于通过总线嗅探（Snooping）当前各 Cache Line 的共享状态并标记权限（Shared/Invalid）；M 步相当于拥有独占修改权（Modified）的核对其局部参数进行更新写入。
|
||
|
||
4. **Boosting 的残差拟合 vs. PID 控制器与信号处理**：在硬件控制系统中，GBDT 对负梯度的不断拟合，本质上是一个带有积分（Integral）和比例（Proportional）反馈的**数字 PID 控制回路**。前序树的偏差作为误差信号输入，下一棵树生成纠正信号进行补偿。 |