演讲者背景与研究历程
本次演讲由Facebook AI Research的研究科学家兼研究经理田渊栋主讲。田渊栋拥有卡内基梅隆大学（CMU）博士学位，其学术生涯横跨计算机视觉、强化学习及非凸优化领域。在博士期间，他主要研究非凸优化问题，特别是如何通过优化样本分布来降低样本复杂度，同时保证在非线性扭曲图片匹配等计算机视觉任务中能找到接近全局最优的参数解。这一阶段的工作曾获得ICCV 2013的马普奖荣誉提名，核心思路是利用问题的群结构或半群结构来复用样本，从而在较少样本下实现理论保证。
“我自己是二零零八年在CMU就读的博士，然后二零一三年毕业。那么在博士期间，主要工作呢有两个方面啊，一个是呃非凸的啊优化，还有一个是呢就是把它应用于那个基于计算机视觉的一些问题上啊。”
毕业后，田渊栋先后加入Google Waymo和Facebook AI Research。在Facebook期间，他的研究重心转向强化学习与神经网络理论解释。他早期参与了名为Dark Forest的围棋项目，该项目在AlphaGo之前数月即利用神经网络进行围棋对弈，并引起了MIT Technology Review的报道。随后，他带领团队复现并改进了AlphaZero的方法，开发了能够战胜人类顶尖棋手的AI系统。
强化学习在博弈中的应用案例
田渊栋团队在强化学习领域的另一项重要成果是AlphaGo的复现与实战验证。该团队与韩国棋院合作，使用仅一块GPU的AI系统对战四位韩国职业棋手。实验结果显示，该AI系统取得了二十连胜的惊人战绩，且每位棋手均未能战胜AI。值得注意的是，该AI系统每次思考下一步仅需50秒，而人类棋手则拥有无穷无尽的思考时间，部分对局甚至长达5到6个小时。这一案例证明了在特定分布的问题上，深度学习驱动的强化学习策略可以超越传统人类专家的水平。
| 对比维度 | AI系统 (AlphaGo复现版) | 人类棋手 (韩国职业棋手) |
|---|---|---|
| 硬件资源 | 1块GPU | 人类大脑 |
| 单次思考时间 | 50秒 | 无穷无尽 (部分对局5-6小时) |
| 对战结果 | 20连胜 | 0胜 |
| 训练数据 | 无人类样本 (自学习) | 人类经验 |
此外，团队还开发了高效的强化学习框架，如2017年的ALF（通过多线程提高效率）和基于PyTorch C++接口的ReLa框架。目前，该框架正应用于桥牌等非完全信息博弈的研究中，旨在通过自学习发现更优的叫牌约定和规则，而无需依赖人类数据。田渊栋指出，虽然这些强化学习项目多为合作指导，但他投入了大量精力指导实习生和合作者，旨在通过机器学习解决更复杂的组合优化问题。
组合优化中的深度学习新思路
演讲的核心议题转向组合优化（如Job Scheduling、GPU资源调度等）。传统观点认为，由于组合优化问题多为NP-hard，除非P=NP，否则不存在多项式时间的通用最优解。然而，田渊栋指出，现有的NP-hard证明多基于最坏情况保证（Worst-case guarantee），即构造极端复杂的问题需要指数级时间。但在现实应用场景中，问题往往服从特定的分布，这使得通过深度学习寻找针对特定分布的启发式搜索策略成为可能。
“现实情况上来说，啊，可能就是也许你碰到的那些问题，虽然说名义上来说啊是一个 NP hard 的问题，但是呃，对于某些特定的分布，那么这些特定的分布呢，也许我们会有找到一些啊更好的啊更好的那个启发式搜索的方法。”
此前，已有研究尝试直接利用神经网络解决组合优化，如2015年的Pointer Network，它将问题视为序列到序列的任务，直接输出凸包等问题的解；另有研究将Job的CPU和内存使用率映射为二维矩阵，由神经网络直接预测下一步操作。这些方法虽具启发性，但对于复杂问题，直接输出答案难度极大且训练成本高。
Local Rewriting 框架与核心机制
为克服直接端到端学习的困难，田渊栋团队提出了Local Rewriting（局部重写）框架。该框架不追求一步到位，而是采用迭代改进的策略：从初始解出发，每次选取解的一部分（子集），应用特定规则进行局部优化，再放回原解，通过多次迭代提升解的质量。这一过程将局部搜索转化为神经网络的优化问题，由AI代替人类寻找最优的启发式方案。
该框架包含两个核心策略（Policy）： 1. Region Picker（区域选择器）：根据当前状态，决定从解中选取哪个子集（Region）进行优化。 2. Rule Application（规则应用）：针对选定的子集，应用预定义的规则（Rule）进行局部修改，使解变得更好。
“我们每次从一个一个 solution 出发... 我先去找一块... 这样的一个子子集。那么这个子集呢？找到之后啊，然后我把这个子集拿出来啊，我用一个 U T 这个 rule 去啊去改它... 然后把它放回去。”
值得注意的是，规则（Rule）本身是人工预设的，但神经网络负责学习何时使用规则、使用频率以及选择哪个区域。这种“人机协作”的模式既利用了人类对问题结构的先验知识（规则），又利用了神经网络在复杂决策中的强大能力。田渊栋透露，后续研究还将尝试让神经网络自动学习规则，进一步减少人工干预，从而在特定问题子集上实现优于通用算法的性能。
强化学习框架：Actor-Critic与Q函数协同训练
在利用深度强化学习为组合优化寻找启发式策略时，核心难点在于策略网络（Policy）的训练稳定性。传统的Actor-Critic架构中，Critic网络负责评估当前状态的价值，但如果Critic的预测不够准确，会导致训练过程缓慢且难以收敛。为此，研究团队提出了一种两阶段训练方法：首先利用Q函数通过Tree Search（树搜索）预先学习出一个更精准的Critic模型，随后将该Critic作为Baseline引入到Actor-Critic框架中，进而优化Policy网络。这种先准后优的策略显著提升了学习效率。
“Critic本身的critic呢是需要我希望能够把它学的更准一点啊，不然的话呢，就它训练的时候会比较慢。”
该方法被成功应用于三个截然不同的组合优化场景：在线作业调度（Online Job Scheduling）、表达式简化（Expression Simplification）以及车辆路径规划（Vehicle Routing）。这种通用性证明了该框架在处理不同结构化数据时的潜力。通过这种精细化的训练机制，模型能够更准确地捕捉搜索空间中的潜在价值，从而在复杂的优化任务中表现出更强的适应能力。
在线作业调度：从贪心策略到互补资源并行
在线作业调度的目标是在资源受限的情况下，最小化作业的等待时间（Slowdown）。在一个典型场景中，存在多种资源（如红色和蓝色资源），不同作业对资源的占用需求各异，且到达时间（Arriving Time）和持续时间（Duration）各不相同。若采用Naive的贪心策略（如先到先服务），作业必须串行执行，导致资源闲置和等待时间增加。例如，Job 2在时刻2到达，但因资源被Job 1占用，需等待至时刻3；Job 3在时刻3到达，却需等待至时刻6。这种串行执行导致了显著的Slowdown区域（灰色区域）。
然而，通过观察发现，Job 2和Job 3的资源需求是互补的：Job 2主要占用蓝色资源，而Job 3主要占用红色资源。因此，在Job 1执行完毕后，Job 2和Job 3可以并行执行，从而大幅减少总等待时间。这种调度优化本质上是一个图结构优化问题，通过改变图中节点的执行顺序（即修改箭头指向），可以找到更高效的调度方案。为了将这种图结构输入神经网络，研究采用了Child Sum LSTM或图卷积网络（GCN）进行节点Embedding，将图信息扩散至全局，从而提取出更丰富的特征表示。
调度性能对比：超越传统启发式与离线最优
在在线作业调度任务中，研究团队提出的Neural Writer方法（黑色曲线）在多个维度上展现了优势。与传统的启发式算法（如最早作业优先EJF、最短作业优先SJF）以及深度学习方法（Deep IM，直接预测下一个调度作业）相比，Neural Writer的Slowdown得分更低，意味着其调度效率更高。值得注意的是，即使与离线最优算法（Offline Optimal，即预先知道所有作业到达时间的“作弊”情况）相比，该方法依然表现优异，证明了其在在线环境下的强大泛化能力。
| 方法类别 | 具体算法/模型 | 性能指标 (Slowdown Score) | 备注 |
|---|---|---|---|
| 传统启发式 | Earliest Job First (EJF) | 较高 | 基准对比 |
| 传统启发式 | Shortest Job First (SJF) | 较高 | 基准对比 |
| 深度学习方法 | Deep IM (DPM) | 2.81 (2资源) / 显著高于Neural Writer (多资源) | 直接预测调度 |
| 离线最优 | Offline Optimal | 理论下限 | 已知所有到达时间 |
| 本文方法 | Neural Writer | 2.53 (2资源) / 远低于DPM (多资源) | 一步前向传播，速度快 |
实验进一步揭示，当资源种类较少（如2种）时，Neural Writer与DPM差距不大（2.53 vs 2.81）；但当资源种类增加至20种时，Neural Writer的优势显著扩大。这表明该方法在处理高维、复杂资源约束的组合优化问题时，具有传统方法无法比拟的优势。此外，在数据分布从均匀（Uniform）变为非均匀（Non-uniform）的泛化实验中，Neural Writer依然能保持较好的性能，证明了其启发式策略的泛化能力。
表达式简化与反编译：自动化规则学习与代码重构
除了作业调度，该方法同样适用于表达式简化（Expression Simplification）。面对复杂的数学表达式，目标是将其化简为永真式。研究团队利用Hellaide开源框架中的现有规则，但不再依赖人工指定规则的应用顺序，而是让计算机通过强化学习自动学会如何应用这些规则。模型通过选择子树（Region Picker）并进行重写（Rewrite），逐步简化表达式。实验结果显示，该方法在简化效果上优于Z3定理证明器的预处理步骤，且速度远快于基于搜索的方法，因为Neural Writer只需一步前向传播即可预测修改位置。
“我们希望那个学的时候过程中呢，我们可以完全自动学会这个 rule 的种几种 rule 的种类。”
在反编译（Decompiler）领域，研究团队与UCSD合作，尝试从二进制代码恢复高级语言（如C代码）。由于二进制代码丢失了结构信息，直接生成往往充满错误。因此，采用两阶段策略：首先通过序列模型生成代码草图（Code Sketch），然后通过局部搜索和预测进行错误修正（Error Correction）。这种“生成-修正”的迭代过程，与之前的图优化思路一脉相承。实验表明，即使在训练数据规模较小（表达式长度<100）的情况下，模型仍能泛化到更长的表达式，验证了方法的通用性和可扩展性。
| 应用场景 | 对比基线 | 本文方法优势 | 关键机制 |
|---|---|---|---|
| 表达式简化 | Z3 Simplifier | 效果相当或更好 | 自动规则学习 |
| 表达式简化 | Search-based | 速度更快 | 一步前向预测 |
| 反编译 | 传统手动编写 | 开发效率高，自动化 | 草图生成+错误修正 |
基于AST与Attention的神经反编译架构
在代码反编译任务中，直接生成目标代码序列存在严重缺陷，因为生成的代码可能无法编译甚至包含错误。核心思路是采用Tree Encoder和Tree Decoder结构，通过编码合成树并解码高级代码的抽象语法树（AST），从而保证高级代码树的一致性。这种结构能够捕获交互依赖关系，直接生成完整的AST，确保括号对齐、for/while循环完整等语法正确性，避免了仅生成Token列表时难以保证基本语法的痛点。引入Attention机制使得翻译过程能根据输入树的具体节点位置映射到输出结果，显著提升了结构感知的准确性。
“如果你只生成一个token的list的话呢，也许很多的基本的语法都不能保证。”
迭代错误预测与修正算法
针对生成的AST可能存在的逻辑或变量名错误，团队采用了迭代错误预测（Iterative Error Prediction）算法进行修正。该算法流程类似于Ruby的调试过程：首先尝试编译生成的代码，若编译器报错或输出不正确，则利用编译器错误信息结合神经网络预测错误位置并进行修复。这一过程可重复执行多达十次，逐步将错误的C代码修正为可正确编译的程序。这种机制弥补了纯神经网络生成缺乏语法约束的不足，通过外部编译器反馈形成闭环修正。
合成实验与性能指标对比
为了验证方法有效性，团队进行了合成程序实验，使用已知编译器（C语言，-O0优化级别）将编译后代码翻译回高级代码。评估指标包括Token Accuracy和Program Accuracy，后者要求所有Token完全一致，标准远高于前者。实验对比了Sequence-to-Sequence模型与AST+Attention模型的效果。数据表明，AST加Attention的结构在性能上显著优于传统的序列模型，证明了结构化输出在保持代码一致性方面的优势。
| 模型架构 | 核心组件 | 语法保证能力 | 相对性能表现 |
|---|---|---|---|
| Sequence-to-Sequence | 序列编码/解码 | 弱（难以保证括号/循环结构） | 基准水平 |
| AST + Attention | 树编码/解码 + 注意力机制 | 强（直接生成完整AST，语法结构完整） | 显著优于Seq2Seq |
架构搜索中的Action Space自动学习
在架构搜索（Architecture Search）领域，传统方法依赖人类预设的固定Action（如逐层添加卷积层），这未必是最优策略。新方案主张从整个设计空间出发，通过神经网络自动学习Action Space，即每次将设计空间切分为“好”和“坏”两个区域，逐步收敛至高性能网络区域。以CIFAR-10上的简单网络搜索为例，对比了“Sequential”（逐层添加）和“Depth-First”（先定深度再定参数）两种Action Space。实验数据显示，Depth-First策略能更快发现深度对性能的关键影响，从而在相同样本数下获得更高的准确率，证明了自动学习Action Space能显著提升搜索效率。
“你这样的话呢，我就可以自动学那two action...都不需要通过人去estimate什么样的，或者人去design什么样的action是对的啊。”
蒙特卡洛树搜索与迭代优化机制
该框架假设存在一个固定的完全二叉树作为Action分支结构，通过迭代方法学习如何切分空间。首先固定切分方案，利用蒙特卡洛树搜索（MCTS）在定义的空间中搜索潜在的优秀网络结构；随后基于更多样本重新学习切分策略，使左侧节点对应更优网络，右侧对应较差网络。MCTS的使用平衡了探索（Exploration）与利用（Exploitation），既能利用现有结果寻找更优分支，又能通过探索避免陷入局部最优解。随着迭代进行，Action Space逐渐优化，搜索偏向性增强，最终能高效定位高性能的网络架构。
“通过不停的迭代呢，你就会发现啊，这action space变得越来越好...得到会会得到一些更好的那个node，更好的那个network structure。”
基于属性预测的启发式搜索方向学习
该研究提出了一种利用神经网络属性来指导组合优化搜索方向的方法。核心思路是将网络的具体参数（如深度、宽度、非线性激活函数类型、连接方式等）作为输入特征，预测样本在搜索空间中的最优移动方向。具体而言，研究者将这些参数映射到高维空间，寻找一个方向向量，使得该方向与性能指标（如准确率）的增长方向最大化一致。通过计算所有属性与目标性能的加权点积，设定一个阈值，若点积大于阈值则向一个方向搜索，反之则向另一个方向搜索。这种基于Latent Action（潜在动作）或LineX的方法，能够在复杂的神经网络搜索空间中，用极少的样本快速定位高准确率区域。
“你把这些样本呢放在那个空间里面，然后你去找一个方向，使得这个方向呢跟你这个accuracy或者说performance metric的那个方向增长方向是最大一致化的。”
这种方法在NAS-Bench-101数据集上进行了验证。该数据集由Google提供，包含在424,242个模型上训练得到的准确率数据。实验结果显示，蓝色曲线代表的LineX方法在样本效率上显著优于其他对比方法，即在相同样本数量下，LineX能获得更高的准确率，证明其能更有效地发现并利用有用的搜索区域。
NAS-Bench-101与Connect60K实验数据对比
为了验证方法的通用性和有效性，研究者在两个不同的基准测试数据集上进行了实验。第一个是NAS-Bench-101，这是一个由Google构建的大型基准，涵盖了大量神经网络架构及其对应的准确率。第二个是研究者自行构建的Connect60K数据集。实验重点考察在极少样本情况下，模型能否快速收敛到高性能架构。
以下是关键实验数据的对比表格，展示了不同方法在有限样本下的表现：
| 数据集 | 样本数量 | 方法 | 性能指标 (准确率/Comparable) | 备注 |
|---|---|---|---|---|
| NAS-Bench-101 | 少量样本 | LineX (本研究) | 高准确率 | 搜索效率高，能快速定位高准确率区域 |
| NAS-Bench-101 | 少量样本 | 其他对比方法 | 较低准确率 | 样本效率相对较低 |
| Connect60K | 少量样本 | LineX (本研究) | 良好表现 | 效果与NAS-Bench-101一致 |
在Connect60K实验中，LineX方法同样展现了优异的性能，证明了该方法在不同搜索空间中的鲁棒性。研究者指出，迭代策略本身可能并非最关键因素，关键在于如何在近乎无限的开放域（Open Domain）中找到更好的解，而不局限于特定的网络复杂度或层数限制。
开放域搜索与移动端约束下的性能表现
研究进一步探讨了在开放域（Open Domain）环境下的搜索效果，即不限制网络架构的复杂程度或层数，旨在近乎无限的搜索空间中寻找最优解。实验表明，即使仅使用800多个样本，LineX方法也能找到一个性能与现代新架构方法相当（Comparable）的架构。
此外，研究还引入了计算复杂度约束，设定FLOPs（浮点运算次数）小于600M，以模拟移动端部署场景。实验结果显示，在满足移动端计算资源限制的前提下，该方法生成的架构性能依然保持竞争力。这表明该方法不仅适用于理论上的大规模搜索，也具备实际工程应用潜力，能够在资源受限环境下找到平衡性能与效率的解决方案。
“我们希望这个search呢在这个在这个无近乎无限大小的空间里面，就能找到更好的solution。”
总结与未来挑战：工业级应用与理论保障
讲座总结指出，强化学习或机器学习可用于学习组合优化问题的启发式策略，目前在中小规模问题（变量和约束在100到1000之间）上已显示出良好的增益。然而，面向大规模工业级系统（如百万级参数）的应用仍处于实验阶段，需要更高效的基础设施和更多计算资源来验证其有效性。
未来研究方向包括： 1. 混合决策机制：将简单决策交给快速的启发式规则（纳秒级执行），将复杂战略决策交给机器学习模型，以兼顾速度与效果。 2. 理论保障：目前方法多为经验性（Ad-hoc），缺乏严格的理论保证（Spherical Guarantee），结合神经网络与优化理论是一个难点。 3. 复杂约束处理：对于多阶段资源分配等复杂约束问题，可通过动态Mask或惩罚机制处理非法动作；对于连续变量优化，建议结合梯度下降与强化学习技巧以跳出局部极小值。
“New AI Talk是不是有帮助啊？如果您有帮助的话呢，那当然是非常好的。那相当于就是整个东西都已经商业工业化了。”
在问答环节，研究者还提到，对于可行域稀疏的问题，可转化为对偶问题，通过优化对偶解逐步逼近可行解。对于多智能体路径规划，需根据具体问题结构选择全局优化或独立决策框架。总体而言，深度学习在自动发现启发式模式方面具有巨大潜力，但该领域仍处于起步阶段。
工程优化与启发式策略的核心地位
在组合优化的工程实践中，代码实现的精细程度对性能的影响极为显著。同样的算法，因代码编写质量不同，速度差异可达十倍，这在实际应用中属于正常现象。因此，工程层面的优化至关重要。以 SAT Solver（布尔可满足性求解器）为例，其内部包含大量高度优化的技巧（tricks），如 to-watch literal 和 unit propagation（单元传播）。这些启发式策略若运用得当，能极大提升求解效率，是工业级优化系统解决复杂问题的关键所在。
“你有可能有一个代码，你写的好，写的不好啊，同样的算法可能就差个十倍的速度，这是非常正常的。”
此外，单智能体与多智能体算法的效果对比是当前活跃的研究方向。虽然 Q-learning 等单智能体方法在某些场景下表现尚可，但在 桥牌 等多智能体博弈问题中，单智能体方法虽能取得一定结果，但面临根本性的差异，需要更大的创新。目前，求解器在中小规模问题中常作为 baseline，但在 几百万变量 的大规模问题中，底层依赖求解器、上层结合深度学习的混合方案将是必然趋势。
求解规模、随机性与落地现状
组合优化问题的求解规模因问题类型而异。以 SAT Solver 为例，目前能处理的变量数目和约束数目通常在 几百万 级别。然而，随着规模扩大，代码需进行极致优化，单个操作耗时仅 几纳秒至几十纳秒，导致代码极难阅读。对于图着色等其他问题，规模指标则有所不同。
在处理 随机参数 下的组合优化问题时，若存在相关理论（如 SAT 领域），可预测求解概率；若无理论支撑，随机参数因缺乏结构而难以处理。关于强化学习在 Facebook 的落地，内部已有实际应用，主要用于系统参数优化。鉴于工程师成本高昂，“让机器调”是大趋势，旨在通过成熟的算法替代人工微调，实现降本增效。
“什么东西都手调，大家会累啊累死……如果能让机器调，而且让机器调的很好的话，为什么要让工程师去调？所以这个是个大趋势嘛。”
算法设计：从 AlphaGo 到多目标优化
强化学习在设计搜索算法中的应用已有成熟案例，最典型的是 AlphaGo。其核心在于利用神经网络计算搜索的启发式策略（heuristic）或优先级（priority）。具体而言，Policy Neural Network 用于评估每一步 Action 的优劣，从而决定优先探索哪些分支，忽略低效路径。这种思路也被应用于 A* 搜索 等经典算法中，通过 RL 优化搜索顺序。
针对 多目标优化 问题，目标通常是寻找 帕累托前沿（Pareto Frontier）。常用方法是将多个目标通过线性组合转化为单目标问题，通过调整线性系数并反复求解，描绘出边界。此外，该领域受到 Yoshua Bengio、Caltech（易松等）、宋乐团队 及 MIT 等多方关注，旨在结合符号推理与感知能力，构建第一类系统。
“AlphaGo 对吧？就是说我在 search 的时候，我的 search 的 heuristic。或者 search 的那个 priority 就是用那个用 neural network 来来来来给你算出来的。”
理论差距、鲁棒性与安全部署
当前 RL 理论与应用之间存在显著 Gap，主要因为 Deep RL 是 “黑盒中的黑盒”，难以解释。然而，理论研究有助于深入理解算法有效性，避免仅凭感性调参。理论与实践需双管齐下，才能推动领域发展。在鲁棒性方面，RL 对参数敏感性较低，但如 Monte Carlo 搜索中的 PUCT 参数（权衡利用与探索）仍需精细调整，否则效果会显著下降。
为快速评价网络结构，最新研究采用 One-shot 方法 或训练 Vanilla Network 进行预测，避免每次重新串行评估，大幅提升效率。在时变环境中，为确保安全，通常将 RL Policy 置于 安全壳（Safety Shell） 中，若动作超出安全范围，则回退至传统策略。状态表达通常转化为 有向无环图（DAG），通过调整边指向来改变执行顺序。
“Deep 已经是个黑盒子，然后 RL 又是个黑盒子，然后这样拼在一起呢就黑中黑中更黑了……理论没有实践是不行的……两条腿一起走的呢可能就是将来可能会走得更好一点。”