基于最优停止理论的神经架构搜索：秘书问题及其变体在高效发现高性能神经网络中的应用与实证分析

本综述创新性地将最优停止理论（OST）中的秘书问题（SP）应用于神经架构搜索（NAS），提出通过随机探索约37%的搜索空间即可高效发现高性能架构。研究进一步扩展出"足够好"（GEP）和"回调"（CBP）策略，将搜索成本分别降低至15%和4%，为计算资源受限的研究者提供了理论支持与实证验证（基于MNIST/CIFAR-10数据集20,000次实验），显著解决了NAS计算成本高（如GPT-4训练耗资7,800万美元）与探索效率间的矛盾。

　　

2 最优停止理论与秘书问题

在数学领域，最优停止（Optimal Stopping）是确定何时终止任务以最大化预期结果的关键过程。这一理论因其能优化有限资源分配而被广泛应用于金融衍生品市场、彩票策略、军工生产乃至人际关系匹配等领域。最优停止问题通常表现为决策理论、统计序列推断或实验统计设计三种形式，其核心在于通过控制随机序列和统计决策来定义停止时间（Markov时间τ），而秘书问题（Secretary Problem, SP）正是有限范围马尔可夫决策过程中的著名决策难题。

秘书问题又称挑剔的求婚者问题、苏丹嫁妆问题或最佳选择问题，其经典形式包含六个特征：单一职位空缺、已知申请人数量n、按随机顺序依次面试、仅基于已面试者的相对排名决策、拒绝后不可召回、且只接受最佳人选。通过概率模型推导，当面试并拒绝前r名申请人后选择首个优于所有前者的候选人时，成功选择最佳人选的概率P(r,n)可表示为公式(1)的求和形式。为最大化成功概率，最优面试人数r需满足双重不等式关系(2)，经简化后得到关键不等式(3)。

分析表明，当r较小时不等式左半部分被违反，r较大时右半部分被违反，唯存在唯一最优r值使两边同时成立。如图1所示，最优面试比例r_opt/n随n增大快速收敛于e^-1≈0.368，即最优策略τ_π≈0.37。这意味着面试官应拒绝前37%的申请人，然后选择首个相对最佳者，超越此比例后的边际收益递减（图2）。

3 实验材料与方法

为验证OST在NAS中的应用效果，研究构建了包含672种独特神经网络架构的全信息搜索空间，其设计自由度限制如表1所示，包括输入/隐藏层激活函数、优化算法和全连接层节点数的限制性组合。选择MNIST和CIFAR-10两个差异显著的基准数据集以确保实验无偏性，前者产生更高性能模型，后者提供显著性能差异以测试SP变体的普适性。

实验依托美国国防部高性能计算现代化计划中的Gaffney系统（峰值性能3,029 TFLOPS）和两个本地非HPC系统。共训练评估6,720个模型，处理130,000张图像，完成436.8百万数据流和489.99万亿参数调整。每个架构获得图像分类准确度评分，经五次运行平均后形成两组"主"性能得分集。如表2所示，不同数据集上的架构性能得分差异显著，符合实验目标。

性能数据集按得分排序后赋予静态键值标识性能等级R_i（其中R₁为最佳）。由此构建的全信息搜索空间为OST应用奠定基础。

4 SP变体的应用与分析

4.1 CSP应用分析

在20,000次循环测试中，CSP最优策略独立于数据集选择最佳模型(R₁)的频率比次优模型(R₂)高278%，比第三至第五名分别高603%、1,225%和2,335%。前1%表现者(R_1-7)贡献总累积分布函数的63%，其余模型平均贡献仅0.05%。前5%表现者的选择结果几乎相同，两数据集结果高度一致。

通过动态编程收集的四类算法执行数据集显示：最佳模型被拒绝概率37.17%，列表末位模型被选概率37.23%且平均等级符合正态分布(R_n/2=R₃₃₆)；62.83%情况下最佳模型仍存于剩余集(BOR)；62.87%情况下因相对较优而选择低于BOR的模型。BOR数据集平均等级1.58(标准差0.95)，BORS数据集平均等级2.69(标准差2.13)，两者最低等级均为R₁，最高等级分别为R₁₁和R₂₁。若R₁未被拒绝，所选模型平均等级2.03，最低选择等级上限满足公式(4)关系。

4.2 GEP应用分析

GEP变体引入"足够好"概念，允许研究者因发现满足性能阈值的"顶级模型"而提前停止搜索。如图4所示，当目标等级s扩大至R_s（s=1,2,5,10）时，所需搜索空间探索比例显著降低。s增大导致更多申请人被纳入，面试需求下降，成功发现指定等级内模型的概率大幅提升。

通过100规模总人口的测试，推导出最优策略τ_π(R_i)的近似公式(5)和成功发现等级i在等级s内概率的估计公式(6)。虽公式(5)在n较大时出现偏差，但通过引入误差校正值ρ≥2可确保估算保守性。公式(6)对s≤16(R₁₆)的情况保持个位数百分比误差，适用于较小等级范围。

建议研究者至少探索15%搜索空间(τ_π≥0.15)，此时成功发现R₁₀以内模型的概率约80%。表3显示不同人口规模下发现R_1-10等级模型的概率，表4则给出实现不同成功概率所需的模型等级边界和马尔可夫时间。需注意资源成本随n增长而增加，需权衡探索比例与单位人口访谈成本。

4.3 CBP应用分析

CBP变体引入"回调"功能，允许在任意马尔可夫时间召回已面试的最佳候选人。实际应用中，研究者可保存每个评估模型以备回调，若存储受限则仅保存当前最佳模型。如图8所示，独立于马尔可夫时间，最佳回调模型始终为R₁，可用回调模型的上界随τ增大而下降，平均等级满足公式(7)关系，上界近似由公式(8)定义。

图9显示公式(7)-(8)与实验数据的对比，虽两端存在偏差但仍提供有用决策参考。当计算资源成本纳入考量（本实验平均每模型耗时17分8秒），问题转化为平衡发现高性能模型与最小化计算成本的优化问题。图10展示整个τ频谱上的资源成本与模型等级关系，基线开销成为沉没成本，且NAS基础设施支持活动(NISAs)带来额外149.99%成本增长。

但NISAs多为固定成本，而NEAs为可变成本，多周期执行时NISA成本分摊至每模型降至2分34秒。建议研究者保存重建模型所需参数，至少探索4%搜索空间(τ_π≥0.04)，此时拒绝集平均等级低于选择等级，回调功能显现优势。

5 讨论与未来工作

OST应用于NAS的可行性取决于SP规则约束的满足：随机选择评估模型、模型间相对可排名、总模型数n≥20已知。可通过枚举空间后随机选择或随机组建唯一配置确保随机性；通过组合学乘积法则计算n，敏感度分析削减无关组件；将SP解应用于时间维度，分配相应比例时间执行搜索。

排名能力依赖自动化流水线实现从模型构建到性能评估的全流程，需注意工具链的数值精度、依赖库等技术细节。最关键的是，SP不保证发现绝对高性能模型，只保证相对高性能模型的发现概率，因此必须结合针对问题的智能搜索空间设计。

表5总结了各SP变体的关键约束、假设和建议。未来工作包括：精炼公式(4)-(8)以提高不同n值的准确性；将动态编程洞察扩展至GEP/CBP变体以指导硬件设计；探索与最先进NAS策略（如DARTS微搜索结构、一次性/知识蒸馏等技术）的集成可能性。

6 结论

秘书问题能为NAS研究提供有效的停止策略指导。严格遵循CSP可37%概率发现搜索空间内相对最佳模型，GEP和CBP变体分别将搜索成本降至15%和4%，带来6.7倍和25倍计算资源节约。成功实施需深入理解SP局限性、NAS设计决策和实验基础设施要求，未来将探索与其他先进NAS策略的集成效益。