Algorithm Runtime Prediction: Methods & Evaluation
Frank Hutter, Lin Xu, Holger H. Hoos, Kevin Leyton-Brown
cs.AI, cs.LG, cs.PF, stat.ML
2012-11-06
用随机森林从实例特征预测 SAT/MIP/TSP 求解器运行时间,误差不到 3 倍,几百次采样即够,还能外推到未见参数配置。
NP 完全问题到处都是,SAT、混合整数规划(MIP)、旅行商(TSP)是三个最常被研究的。最坏情况下它们极难,但实际出现的实例往往能解。真正的麻烦在于:即便实例规模固定,同一个求解器在不同实例上的运行时间能差几个数量级,而同一个实例换个求解器,时间又能差出天际。理论上没人说清这是为什么。
过去十年,一个务实的路子是用监督学习的回归模型去拟合「算法在这个实例上跑多久」,论文里叫经验表现模型(EPM)。输入是实例特征(变量数、图结构、探针跑两秒的轨迹统计等),输出是运行时间的对数。这种模型是算法选择(SATzilla 这类组合)、参数调优(SMAC 这类)和构造难题基准的基础。这篇 2014 年发表于 Artificial Intelligence 期刊的论文(UBC 的 Hutter、Hoos、Leyton-Brown 团队)是这个领域的奠基性综述加推进:更好的模型、更全的特征、当时最大规模的实验、以及更正确地处理被截断的运行。
EPM 的设定很朴素:把实例特征和算法参数拼成一个输入向量,回归出 log 运行时间。取对数是因为运行时间跨好几个数量级,线性空间里没法拟合。论文系统比了六类模型:两种岭回归(RR 两阶段前向选择、SPORE-FoBa 前向-后向)、单隐层神经网络、高斯过程、回归树,再加上他们新加的两个,近似高斯过程(投影过程)和随机森林。
新东西的取舍都讲得出为什么:
特征上他们给 SAT/MIP/TSP 分别攒了 138/121/64 个,重点是两类新的:探针特征(让现成求解器跑两秒,读它的轨迹,比如 Zchaff 学了多少子句、CPLEX 预求解探了什么、Concorde/LK 在 TSP 上的局部最优统计)和计时特征(每组特征算花了多久)。探针特征还会迁移:用一个算法族(局部搜索)的探针去预测另一个族(树搜索)的表现。
11 个求解器、35 个实例分布、三种预测场景。新实例上,Minisat 在竞赛混合集上的运行时间跨了约 6 个数量级,随机森林的 RMSE 是 0.47(以 log10 运行时间计),换算下来平均预测误差不到 3 倍。
| 数据集 | 模型 | log10-runtime RMSE |
| Minisat 2.0-COMPETITION | 随机森林 | 0.47 |
| Minisat 2.0-COMPETITION | 岭回归 RR | 1.01 |
| CPLEX-BIGMIX(异构) | 随机森林 | 0.64 |
| CPLEX-BIGMIX(异构) | 岭回归 RR | 2.7×10⁸ |
随机森林是全面赢家:SAT 上每一项都最好,异构的 MIP 大杂烩 BIGMIX 也最好,训练只要 0.1 到 11 秒。岭回归在 BIGMIX 上被几个离群点带崩,RMSE 飙到 2.7×10⁸。树方法在异构数据上胜出,因为它们能把输入空间的不同区域分开建模,不会被远处数据带跑。
特征性价比也清楚:SAT 上用到「中等昂贵」一档就和全集不显著区别,但特征计算时间大幅下降;新特征在 MIP 上 12 项里 11 项显著变好。超参优化(DIRECT 搜 30 次)只换来微小提升,训练却可能慢到 3000 倍,实际不值。
换到新参数配置(SPEAR 有 8.34×10¹⁷ 种配置、CPLEX 有 1.90×10⁴⁷ 种),投影过程总体最好(靠那个汉明核),随机森林紧随其后,两者都甩开此前唯一能处理类别配置的回归树。神经网络和 SPORE-FoBa 表现差,说明选对特征组合并不容易。
最难的是同时外推到没见过的实例和没见过的参数配置。这套实验烧了 60 个 CPU 年,但结论是:最好的模型同时外推两边,几乎和只外推一边一样准;几百条数据就能把预测与真值的相关系数推到 0.9 以上(CPLEX-CORLAT 只要 30 条)。落到实践:单机一晚跑 150 次、每次截到 300 秒,就能给手头的算法和实例分布建一个够用的表现模型。
这套东西是现代 AutoML 和超参优化的方法论源头。Hutter 后来做的 SMAC,以及一整套贝叶斯优化的超参搜索,核心循环就是「学一个表现模型、用它挑下一个该试的参数、跑了回填」(SMBO)。对从业者直接的用处:如果你在调一个跑起来很贵的求解器或模型,随机森林加几百次运行就能给你一个可用的表现代理;而它原生处理类别超参和超时被截断的样本,正是真实调参里天天遇到的情况。
诚实讲,这是一篇 2014 年讲组合求解器的论文,不是讲大模型;Minisat 2.0、CPLEX 12.1 这些绝对数字今天不能照搬。能搬走的是方法论结论:随机森林在这类任务上稳定最强、小样本就够、截断数据得专门处理。这些结论过去十年基本没被推翻。
随机森林在观测数据之外外推很差,论文自己承认:要从短截断的训练数据去预测很长的运行,别的模型可能更合适。固定阈值的截断处理只做到约 2κ 以内无偏,相对几个数量级的跨度其实很有限,得靠「每个实例不同截断阈值」才好用。
整个框架依赖针对具体问题手工设计实例特征,得有领域专家写特征提取代码,不是「扔个算法进去就能预测」。预测质量的天花板就是特征质量。复现门槛也不低,联合空间那批实验烧了 60 个 CPU 年。求解器和硬件都是十几年前的,绝对数字已过时。