二分搜索

分类: 深度学习基础

二分搜索

定义

在有序搜索空间内通过反复将区间折半来快速定位目标值的算法，时间复杂度 $O(\log n)$。

数学形式

每次迭代取中间值：

根据评估结果更新搜索区间：若满足条件则 $M_{\max} \leftarrow M_t$，否则 $M_{\min} \leftarrow M_t$。

核心要点

前提：目标函数关于搜索变量具有单调性

在 AMP 中利用”信息熵随 MLP 隐层大小单调递减”的性质，二分搜索满足熵变约束的最小隐层维度

最多 $t_{\max} = 6$ 次迭代即可从 $M_0 = 6144$ 定位到 64 精度范围

代表工作

AMP (2026): 用二分搜索为每个 Transformer block 自适应确定 MLP 剪枝幅度，替代手动设定统一压缩比

相关概念

信息熵

MLP 模块