2021年10月17日 OR Talk 第29期，Facebook田渊栋博士：使用引导策略搜索方法解决优化问题。主持人介绍田博士及OR Talk背景后，田博士开始演讲。田博士现任Facebook人工智能研究院研究员及经理，研究方向包括深度强化学习、表示学习和优化。他曾获2012年ICML杰出论文提名奖及2013年CVPR马尔奖提名，曾任Google无人驾驶团队软件工程师，拥有上海交大本硕学位及卡耐基梅隆大学机器人研究所博士学位，也是ELF Open Go项目的首席研究及工程负责人。

大家好，今天受邀分享近期工作。由于摄像头问题，我将直接开始。本次演讲主题是如何通过机器学习解决优化问题。首先从强化学习讲起，这是近年热门方向，主要突破在于游戏领域。强化学习能解决围棋、国际象棋等复杂游戏，OpenAI的Dota和DeepMind的Starcraft也展示了其强大能力。自2016年AlphaGo以来，强化学习在游戏上取得巨大成功。

田博士曾参与AlphaGo相关工作。2015年，团队开发围棋软件“黑暗森林”，利用卷积神经网络自动学习策略，短时间内达到与拥有数十年人工经验软件相当的水平。2018年，参照AlphaZero思路，团队开发了名为AlphaGo的围棋软件，使用2000块GPU训练两周。该软件在不限思考时间的情况下，以单GPU每步50秒的速度战胜多位韩国棋院棋手，证明强化学习在完全信息博弈中的巨大成功。

接下来探讨强化学习在游戏之外的应用。2020年，Google展示AI自动设计芯片，将设计流程从数周缩短至数小时，开辟了除游戏外的新思路。强化学习可提高实际环境中的搜索效率，替代人类多年积累的经验知识。本次演讲主题即如何将机器学习应用于优化问题，如旅行商问题、作业调度和背包问题等，旨在寻找函数最优解。

优化问题多为NP-hard，理论上在最坏情况下无高效解，但实际数据常满足特定分布，可能存在更优启发式策略。传统理论分析追求通用算法，而缩小问题范围可能找到更优解。游戏领域利用机器学习学习人类直觉和搜索策略，降低搜索复杂度，提高分支效率。这一思路可自然引入优化问题，通过神经网络建模，将人类知识融入搜索过程，以找到更优解。

将优化问题建模为强化学习有多种方案，与游戏不同，对应关系不直观。一种端到端预测方法直接从问题定义训练神经网络预测最终解；另一种渐进式预测方法逐步预测解的部分并拼接；还有一种从初始可行解出发，利用机器学习模型逐步改进解。高级方案甚至无需人工指定行动空间，让模型通过探索自动学习。本次演讲将重点介绍后两类方法。

首先介绍Local Rewriting Framework，这是一种逐步优化现有解的方法。从可行解出发，通过机器学习找到更优解，直至无法改进。该方法称为“局部”，是因为它不改变解的整体结构，而是提取部分结构进行变换优化后再放回，通过重复此过程获得更优解。该方案应用于在线作业调度、表达式简化和路径规划等小规模组合优化问题，效果优于简单启发式算法且耗时更短。

局部优化可能导致陷入局部最优，但在某些情况下可获得全局最优解。这源于田博士博士期间的图像对齐工作，通过加入机器学习模型（如最近邻算法）获得更好解，并在样本量足够时保证全局最优。相比纯机器学习的一次性预测，局部改进方法降低了复杂度。这一早期工作展示了局部优化在特定条件下的理论保证和优势。

接下来介绍今年ACM CCom 2021收录的文章，利用强化学习优化网络规划问题。以数据中心连接为例，需满足带宽、冗余等约束，构建整数线性规划模型。目标是最小化成本，同时满足光纤容量支撑数据流量、不超过频段总容量等条件。此类问题变量庞大，可达十万至百万量级，传统求解器难以高效处理，因此引入强化学习寻找可行解并优化网络结构。

啊去解，你看，如果必须解的话，你可能需要花那个时成成那个成天或者成周的时间去解，对吧？那么怎么办呢？就是对于人类来说呢，就是我们可以找到一种找一种设计一些人工的啊设计的那一些一些一些一些策略啊，然后这些策略呢啊可以把这问题变得比较简单啊，但代价呢是牺牲啊它的啊牺牲它的那个。啊，optimize啊，最优的那个条件，你可能通过人工方式得到一个次优的解，不是特别好，但是很快能得到。那么这样的话可以满足这个需求，当然最后的那个cost会高一点。啊，那比如说，我们可以通过把整个图啊，这整张上上一张图，那么这个整个图分解成啊几块部分啊来决定。对吧？然后呃，你比如说这张图里面，你有很多的那个结构啊，每每一块呃，每一块有对应，比如说一个一个一个一个大陆，比如北美这块有一块，然后中国有一块，对吧？那这这这这些这些这些这这些块呢，我们可以先拆开啊，变成变成比较小的部分，先解一个小规模的优化问题，然后把它拼起来。那么通过这个方式呢，我们可以解找到一个解。那么这个解可能啊没有那么好，但是它能满足要求啊。所以呢，就是说啊，那么现在的这样的问题就是，我们能不能通过呃那个

RL 的方式呢，能找到一个比较好的解啊？那么这边呢，其实针对的是这边的一个痛点，就是说啊，为什么这个问题特别难呢？是因为啊，我们这个啊，像 IP solver 对这种问题，就是首先第一个很难找到一个最那个 feasible solution，就能还没还先找不到一个可行解，就更更何况能不能找能就是更何况也不要找到一个最优解。啊，所以就是说我们这边设计呢是先用一个 reinforcement learning agent 去找到一个可行解，找到可行解之后呢，然后把它放进 IP solver。那么这个可行解其实啊对 IP solver 的 solution 啊就非常有大的帮助，因为可行解其实啊让呃这个整个搜索啊有了一个那个 starting point，啊有了一个那个初始的那个位置，也可以通过加一些约束让这个整个 IP solver solve 那个 solution 那变得啊 solve

的速度变得更快。那么第一个 stage 呢，就是说我们怎么样去学一个 reinforcement agent，对吧？那么这个 reinforcement agent 呢，就非常的好学，就是这边呢，目的是这样，就是说我这边我希望学到一个 reinforcement agent，啊，这个 agent 呢，能够通过它是通过不停的增加啊这个边上的啊那 capacity。然后找到一个可行解啊，所以就说一开始呢，我们这个有这poly之后呢，我们假设这上边上的所有的capacity啊，所有的最大流的流量啊，这个数字呢等于零啊，那么等于零的情况下呢，这个整个poly这这整个网络结构呢，绝对不可能有最那个有可行解的，因为都没有有流量的那个没有没有任何的那个最大流量，就是虽然相当于你没有花钱租任何光纤，你是没有办法完成你的任务。啊，所以它肯定没有任何的那个啊 feasible

solution，没有任何可行解啊。但是呢，你通过不停的加在上面，就是加一一些减加一些那个流量的那个最大值。啊，一点点的把这 capacity 加上去，加上去之后呢，你总会有一天发现，哎，整个整个网络通了啊，然后你其实可以完成你之前的目标啊。那么现在的问题就是说，我们能不能通过 reinforcement learning 找到一个比较有效率的啊，加这些网络的那个 capacity 的方法？啊，这就是啊，这个这这这这第一个 stage 的一个一个目的，对。那么这样的一个过程呢，我们可以啊，我们可以通过训练强化学习啊 agent

来呃来来完成啊。那么这边有一些很有意思的一一个东西呢，首先第一个就是说，嗯。就是说，我们这边是为什么这个方式就可以？我们可以用同样强化学习来做这样的事情呢？啊，首先第一个就是说，啊啊，强化学习我们要条件是说，我们整个流程走一遍呢是不够，也别不能太慢的。如果太慢的话呢，你还不如直接还是解这个问题。呃，就它的一个好处呢是说，啊，我们给定了一个 capacity，给定 capacity 之后呢，啊，我们能够。很快的知道这个 capacity 是不是 feasible 啊，是不是可以？这个这个比又找到一个最好的啊 capacity，找到一个那个最好的那个网络流的那个 traffic，它这个速度要快很多。所以就是说那个 feasibility，它那个你要 checking 这个

feasibility，其实已经就是比啊你要那个最小化它的代价要要要快非常多啊。对，那么啊，这是第一点。第二点呢，就是说，就是如嗯，在对于这种 check 这种可那个 feasibility 的问题上来说，我们需要更好的啊一些方式去进一步加速啊这个啊这个这个 checking 的过程。那在这边呢，我们用两个方式，一个叫 source aggregation。就是说，我们可以把这个图啊里面那些 node 啊一些那个节点的相互之间合并，变成一个比较简单的，或者说相对来说比较啊比较比较简单，就是复杂度低一点的图。然后在这个图上，我们 check 这个 feasibility，啊，这是可以的。那么第二个呢，就是说我们这个叫 stateful failure checking，就什么叫 stateful failure checking 呢？因为我们这边发现，就是说，我们每次做 action

的时候，每次在那强化学习的上面做 action 的时候呢，我们只加 capacity，不减 capacity。啊，因为它只加 capacity，那么那么所以就说，我以前如果我们某个啊某个 constraint 已经满足了，那加 capacity 之后它还是满足，所以你就不需要再 check 一遍啊。这样的话其实可以减少很多啊 capacity 啊那个那个啊 constraint check 的那个时间啊。那么通过这个方式呢，我们可以让整个呃强化学习的训练方训练速度变得很快啊。那么一旦强化学习找到了一个比较好的solution呢，啊，我们就可以啊把这solution带回呃原来的那个integer linear program整数规划问题，然后得到一个更好的啊解啊。那么是这样的一个过程。然后呢，我们啊我们通过呃在我们通过在那个 I O P

啊这个问题上加一些那个约束啊的呃的的方式啊，然后我可以找找那达到一个 local search 的一个。一一个一个方案啊，就是说我们现在有 AI solution，这 solution 有了，有了之后呢，这 solution 相当于每一个边上呢，我们有一个 capacity 啊，我们把这个 capacity 啊数字乘上一个阿尔法，这个阿尔法呢叫 relaxed factor，这阿尔法可以是比如说一点五或者二啊，那么然后我说我要求说限制每条边上的 capacity 不能大于等于，呃，必须得小于等于阿尔法乘上原 AI solution 的 capacity。那么这样的话呢，我把这些 constraint 加进去了之后，我再去解 IP 方程就会方就会方便很多，因为你有更多的思路，更多的 constraint 之后，同时你有 feasible solution 之后呢，啊，就是你在解那个

integer linear program 的时候，你可以通过剪枝啊，或者说通过啊各种方式，让整个搜索空间变得非常小，那么搜索就超就就做起来就非常快啊。那么呃，当然了，另外一些还有一些，接下来就是有些比较细、比较小的细节。那些就是说，首先第一个啊，我们怎么样去啊？就是建做一个 AI agent，啊，那么这 agent 呢其实是有一些结构，那么这结构是这样子，就是啊，我们训练一个 agent，我希望它输输入我们当前的网络结构，啊，网络结构输入之后呢，然后它能够输出啊， actor 跟那个当前的那下一步我们要 take 什么 action， action 的意思就是说我要在哪条边上加我们的 capacity。啊，同时我们也输出一个 value 啊，这个 value 就是说我们呃我们 expected

我们多少次，或者说多过了多久，就可你可以认为它对应就是它过了多久能够，啊能够啊啊能够得到一个可行解。啊，所以那么然后呢，这个输入的网络的结构呢，我们是通过基因来来进行编码的。啊，通过这个方式，我们可以啊学到一个 representation，啊，我们就可以得到学到一个啊 reinforcement agent。 OK。行，然后这边是我们讲一下最后的那个结果啊。首先一个是速度问题啊，速度呢就是说，因为我们这边有个两个比较大的 heuristic 啊，一个叫 source aggregation 啊，另外一个叫 state feasible feasibility checking。那么，那么这个其实可以看到，就是加了这两个。比较大的 heuristic 之后呢，这个运行的速度呢变得非常快，啊，它比那个就是啊，比那个完全不加叫 vanilla，或者说加一点要要快很多，啊，所以这个是我们这边 A

B C D E 呢是五个不同的网络结构，A 是最最简单的，然后 E 是最最复杂的。那么当然了，就说E是个非常大的网络，然后这个网络呢，嗯啊，这个网络呢，可能是啊有非常大，相当于越接近于就是工业界标准的这样的网络。那么你会发现，就是在这种情况下，特别是在 E 的情况下呢，如果你完全不用前面这两个 heuristic，你没有任何办法，就是这个这个打炸这个差是差超时了，没有办法得到一个可行解啊。但是啊，我们通过增加这两个啊那个工程上的 heuristic，能够让它在做 reinforcement learning 时候变得非常快。啊，那么第二张图呢，就是讲了一下，就是最后的那个解的 quality，啊，因为这是非常重要的，就是我们现在有了一个新的方法叫 neural planning，啊，这个叫 neural plan， neural plan，啊，这个方式跟我们传统的加了 heuristic

的 integer linear programming 相比啊，到底好不好？啊，最后的结果是不是比原来要好？你这张图可以看出来，啊，你可以可以看到，就是说啊，在那个如果我们 normalize on ILP 这个 heuristic。拿过来搜索之后呢，你会发现就是啊，我们用 neural plan算出来的那个 cost，其实要低于啊那个 I L P 加 heuristic 算出来的 cost，这是好事情。啊，那么那么同时呢，如果你只跑一下 LIP 不加 heuristic 呢，就是基本上从 B 开始，基本上是没有办法跑出来的，是特别慢，啊，所以 time out，啊，所以基本上就是说啊，我可以我可以说就是这个 neural plan 这样的一个算法，就是我们这个算法呢，其实 automatically 自动的学会了啊比较好的那个

heuristic，就比较好的那个啊。那个那个那个呃，怎么样去搜索空间的一个方案啊？那么我们这边已经把代码开源了啊，如果大家有兴趣的话呢，可以点进去看。好，然后呢？那么这是第一部分。那么第二部分呢？就是说我们讲一下我们最新的这一一另外一系列的工作叫 Learn Action Space。那么这个我们之前啊，我也是说过了，就是 Optimal 就优化问题呢，其实跟一般的强化学习问题并不相同。啊，因为优化问题呢，啊，它里面的搜索空间是一个啊完整搜索空间啊，它里面就是状态和行动空间呢，并没有完全被定义清楚，所以呢，其实有各种各样不同的建模方式。啊，有些建模方式呢，可能对于非常好、非常好好解的那个啊 reinforcement learning problem，有建模方式呢，可能对应一些比较差的 reinforcement

learning。那个那个那个结果对吧？那么你接下来的问题是我们能不能从中学会啊这个这个这个比较好的那个行动空间？那么这个其实是啊接下来下一部分那个那个那个那。这个文章啊，下一部分这个这个就是这个 talk

的啊，它的一些啊，它的一些内容啊。那么这边其实讲了一些呃具体的例子啊，就比如说对于围棋来说啊，我的行动空间非常是固定的啊，我们可以说在十九乘十九的棋盘上，我随便下一个子，这个子在哪就是你的行动空间的啊啊那个结构，对吧？那么这个是一个固定的一个结构。那么，但是呢，就说这个虽然固定，但是对于对实际的优化问题来说呢，这种空间是不固定的啊。那么就是比如说，对于神经网络搜索来说呢，我到底是啊先优化，我先决定那个滤波器的数量呢，还是说先决定网络的宽度或者网络高度呢？这个其实并没有限制啊。你想找到一个最优的那个那个顺序，能够让这个效果更好，就是才是王道。所以呢，在这一块呢上来说呢，我们想要找到一个方案去自动优化它啊。那么这里举举一个非常简单的一个例子啊，这个例子其实是啊神经网络搜索的一个一个简单例子啊。假设呢啊我们有啊一个非常小的那空间小搜索空间啊，这个空间里面有一千三百六十四个啊神经网络啊。那么这这神经网络从哪来？那么是通过啊那个改变这三种不同的参数啊深度啊那个啊channel的size。啊，和那个

kernel size，那么我们的目标呢，当然是从这一千多种神经网络中呢，能找到神经网络能够这个使得这神经网络的那个 accuracy 最高啊。那么当然是非常简单，就如果你知道知道你有 1064 个神经网络，那你完全可以从头到尾扫一遍，找到一个最优解，这个是简单的，不能再简单的方案，对吧？但是呢，就我们的目的是，我们希望通过最少的啊寻找次数，获得最大的收益啊。因为对实际问题来说，啊，神经网络搜索的这个大小空间是非常非常大的，是可能十的二十次方，或者说更大，或者说也就是说七十四十次方，你不可能穷举所有可能的啊神经网络，啊，所以你只能啊找到一些比较比较好的优优化搜索算法，能够很快搜索。那么这边呢，我们这边这个图呢是用来比较两种不同的行动空间定义啊，然后它对应的搜索效率啊。这边定义的这边有两种不同的行动空间，一种是叫 sequential action space。那么什么叫那个

sequential space 呢？就是说我一层一层的往上加，我先加一层，加完一层之后呢，我把它的那个 kernel size 和那个 channel size 定下来，然后再加一层。啊，那么第二种啊 action space 呢叫 global action space，就是我先定下来这个网络多少层，然后我再设它们的 k 和它们的 c 啊。是这样子，那么你会发现呢，就是如右图所示，就是你会发现这个 global space 呢，效果要比 sequence space 要好。这个很有意思。那么这个对于人类来说呢，是有很强的 intuition 的，因为啊，对人来说，我们如何设计神经网络，第一反应是神经网络深度是最重要的，对吧？那个深的一定比浅的好一点。所以，因为有这个性质，有这个这这个思路呢，所以我们下意识的把适应度作为第一个或者最重要的这样的一个 action

去先做完，啊，然后之后呢再去把那些细枝末节的那个部分呢给给决定好。那么这部分呢，就是说就说明行动空间的选取是对于最终的那个结果是有很大的不很有会有会有产生很大的不同啊。所以这部分呢，其实是啊超出了传统的强化学习的啊学习的这样的框架，因为传统的强化学习呢，其实是在给定的行动空间、在给定的啊搜索空间、在给定的那个状态空间上找到一个最优解。但这边呢，我们想找到我们想找到超越这样的一个传统的这样一个 formulation，找到啊一个更好的

formulation。那么怎么去做这件事情呢？就是我们这里呢，其实是啊把行动空间啊定义为呃那个搜索空间的一个分割啊，所以就是假设这整个是大的搜索空间，那么我们要从中分割出几块来，找到一块比较好的区域。那么这个分割的过程呢，就是你的行动空间的过程。那么这个分割本身是可以变化的啊，根据问题的不同，不同的分割应该是不一样的。所以呢，其实啊，这个对于这个分割的最优化呢，其实是啊，就相当于优化了自己的那个行动空间。那么这里呢，其实这是一张图来那个表现，就是不同的分割啊，其实对于啊那个最后的那个好和坏的解的分布是影响是非常大的啊。如果你我们就用这个 sequential

action，你会发现啊，这个好的点和坏的点啊，它们之间是混在一起的。混在一起的坏处是说，你必须那个进入那个每棵树的每一个节点，然后才能找到它们最优解啊！因为大家都混在一起，所以你每个节点都得看一遍。啊，所以这个是非常没有效率的。但是如果你分割的比较好的话呢，你会发现有一支啊树里面全都是非常差的解。那么如果你知道这件事情的话，你就会倾向于把整棵树砍掉，我把整棵子树给切掉啊，然后呃那集中火力啊找到那个比较好的那个那个解啊。那么这就是行动空间啊的学习啊学习行动空间或者说学习那个啊状态空间的分割啊这样的意义所在啊。

那么这个学习空间呢，其实非常简单啊，我们就可以通过啊那个先在这个空间里面搜呃选取一些点啊，选完点之后呢，我们可以啊那个搜索啊，我们可以找到他们好的点和坏的点之间的一个一个 boundary 啊一个 boundary 啊一个边界，然后用这边界去切分空间啊，然后然后我们可以通过这个方式 recursive 地切分，一直到比较小的那个空间为止。那么这样的话，就啊，就就相当于也那个带出了我们这篇这部分这一个算法，这叫AMCTS啊，这个是去年我们NeurIPS的paper。

那么这空间这个 idea 非常简单，就是说啊，我们交替的做以下两件事情啊。第一件事情是给定现在的点，我们去学行动空间啊，学到这个 action space，把这空间切分，或者说进行那些啊进行比较呃层次式的切分啊。然后给定了切分之后呢，我们在这切分的空间之后空间里面进行搜索。那空间切分完之后呢，我们可以知道左边一定比右边好啊，这是 by definition，所以我们会更花更多时间去搜索左边的那那个子树。

那么这部分的子树呢，非常有可能会给我带来更好的啊那个下一个solution。那么同时呢，我们也要照顾右边的啊子树。那么他们虽然在上次的切分中被归到不好的一类，但是他们有可能在其中也会有啊好的一些解啊。所以为了平衡这两者呢，我们这边用了那个蒙特卡洛tree search叫蒙特卡洛树搜索的方。那么这方法呢，其实之前是在围棋的啊方法中是用过的啊。

那么这个 idea 呢，其实非常简单，就是说啊，我每个节点保留两个信息，一个信息是。这个点上啊，这个点上的啊性质，这个点上那个解的大致质量是多少？这是第一个。另外一个呢，是我哈，我已经在这个点，在这个解，在这个那个节点上花了多少的那个啊啊搜索次数？那么我们要平衡这两者啊，我们既然要既要平衡，既要找到那些比较好的那个节点，那同时呢，也要照顾那些节点，也许一开始不是很好，但是它的搜索次数很少，所以我们要偶尔去访问他们一次，也许会找到一些宝藏。

这样的一个思路，啊，对，这个其实是这张图呢，其实是这个思路的一个图像的具现化啊。那么你会发现，就是说这一块可能是好的啊空间，这个空间里面可能有很多solution还不错，但是呢最优解不在这儿，最优解在右边这一部分，对吧？所以就是说你在搜索好的空间的时候呢，你同时还要搜索啊，偶尔去访问一些，比如说很好的空间，也就从里面找到更好的解啊。

一旦找到更好的解之后呢，那么这个解呢，啊，它会在啊下一次的那个 learning action space 的这样一个流程中被归到啊好的行动空间里面去，那么就会让搜索变得更有效率啊。那么我们把这个方式，这个方法其实被用在了广泛用在各种各样的地方。那么首先就是一开始呢，我们把它用在啊，神经网络搜索啊这样的一个问题上啊，你会发现就是随着这个数据集的变大啊，我们这个那这个算法的它的搜索的效率呢会变得越来越高啊，你会发现就是就跟其他的一些那个进化算法相比呢，就它很快的时间之内能找到一个比较好的啊比较好的解。

那么我们也用把这个方法用在那个 open domain 啊上面啊，然后在上面得到了一些比较好的解。然后呢，用同样的方法呢，可以把它用在。啊，用在那个啊那个黑盒优化的问题上啊。那么这个黑盒优化，我们叫搭配，就是现有的那个 solver，我们可以让现有的 solver 啊变得更强啊。那么对黑盒黑盒优化来说呢，就是常用常用的 solver，一个叫贝叶斯 optimization 啊，叫贝叶斯优化，还有一个最近那个就是之前 Uber 这个实验室提出来的叫 Turbo 啊。

那这两个算法呢，就是相对来说啊，Turbo 最最近提出来效果也比较好。但我们发现，我们把我们这个算法和那个这些 solver 结合起来之后呢，效果会更好啊！你会发现，就是说啊，就是就这两根实线呢是结合的结果，实线结合的结果，你发现它的那个降那个降的速度呢，啊，比虚线的要快啊。右边是有是一个那个最小化的问题啊，所以谁降的最快呢？啊，谁的效果就最好。

那么这部分的代码呢已经开源了啊，然后啊，值得一提的是呢，就这个方法在去年的啊 NeurIPS 二零二零啊的黑盒优化的比赛里面呢，被两个 team 已经用到了啊，一个 team 的名列未未名列第三，第二个 team 名列第八啊，他们都用了我们的方法啊，在上面做了一些小小的改进啊，所以就是这个证明我们这个方法还是非常有效的。

那么接下来呢，我可能简要讲一下啊，我们就最近做的一两篇那个进一步改进的一文章啊，那么也是怎么样去切分啊行动空间。那么呃，第一篇呢是关于怎么样去呃把这这个 idea 呢送进那个就是用应用于叫 path planning 问题，path planning 问就是说啊就是叫路线规划问题，路线规划问题就是说啊我们还是要找到一个啊最优黑盒函数的啊最优解，那这黑盒函数呢现在有结构，这个结构呢就是说这 x 呢并不是一个啊随机的一个向量，而是一系列行动啊和啊和那个状态的一个集合啊。

啊，那么这个这个问题其实有很广泛的引用啊，比如包括啊，我们怎么样在无人车的这个问题情况，我们怎么样去做路线规划，或者怎么样对机器手做路线规划等等啊。那么啊，这个通过我们用我们把这个方法把我们现在这个啊 learning space partition 的方式呢啊用在啊我们的这个啊路径规划问题上呢，你会发现它有很多比较神奇的效果啊。这是一张啊比较明显的一张图。

那么这张图是这样，就是如果比如说我们这个点是啊这机器人的那个 starting point，那么这个点呢是个机器人最终想达到想达到目的地。如果你做那个随机搜索的话呢，它是没有效率的，因为它会花很多时间在这个原点附近呃兜圈子啊。但是如果你要做局部搜索的话呢，那么局部搜索可能会陷入局部极小值。比如说像对你这样的迷宫来说呢，就是说你这个这里一块是局部极小值，因为它的因为它这个点的欧氏距离跟你的目标它们之间距离是最小的。但是呢，就是其实这条路径必须先背离这个欧氏距离最小的那个区域，才能绕开，然后最后达到最终的目的。

啊，那么对于我们的方法来说，我们的方法就会通过啊那个平衡那个 exploration 和 exploitation，啊我们可以，我们可以就是啊一首先一就是我们可以就是绕开啊现在这一块的局部极小值，啊从外面绕回来最后得到的最优解。那么这是啊一个啊有意思的现象，就是通过用我的方法，我可以得到这样的一集啊。

那么另外一个我们这边那个改进呢，就是说啊，我们可以用啊叫latent representation啊去啊represent这个问题啊。那么就是对于这样的一个走迷宫这样的问题呢，因为我们可以把整个啊图像啊通过一个representation变成一个啊vector，那么用这个vector做搜索。在这种情况下呢，那么就这个 vector 它相对来说，它对于这个信息的那个压缩程度呢是比较大的啊。那么我们希望这个比较大的那个用这个 vector 去做搜索的效率，会比原来用原原来用原来用那个原来的图像来做搜索的效率要高得多啊。

那么它主要有两个好处，就是如果你通过学习，你可以学习 latent space。那么一个好处呢是说，在这个新的 latent space 上呢，我本来需要用非线性拟合的啊这样的一个啊行动空间的那个那个边界呢，我可以用线性函数拟合啊，甚至是比较简单的函数拟合。那么这样的话呢，就能提高的泛化能力。那么第二个呢，就是说，如果你有个好的 latent space 呢，在这些啊在那个节点里面去做采样呢，它的效率会提高。

同时呢，我们啊，同时我们这边还附加了一个啊比较简单的一个一个分析啊，这分析就是说啊，为什么啊切分空间呢啊效果会比没有切分空间要好啊？那么这边呢，就因为啊它是它的这个理论呢比较啊比较复杂，我就啊暂时跳过了啊。那么主要的逻辑在这了，就是说，首先第一个我们还可以证明它的那个 regret bound 是。几乎是线性的啊，就相当于啊，这是没有办法避免的啊，因为我们有总是有那个 curse of dimensionality，就是维数的灾难，这是不可能不可避免，因为这个函数本身的结构呢，你并不知道啊。

但是呢，就是说你可以看到一些有意思的现象，就是如果你对那一个区域进行切分。如果切完满足某个条件的话呢，它会啊导致啊比较小的 regrets，或者说比较小的那个后悔值啊。那么它主要的机制是在于就是，如果你切分完之后呢，你就会就是这个数字呢可能会变小啊，但这个数字呢不会呃不会变大，那么这样的话你整个 regret 会就变小啊。它是这样的一个一个大的一个思路。那么第二的话就是从呃从那个理论上去说明啊为什么分空间切分呢？啊对于整个啊啊整个 optimization 对于整个啊优化呢是有意义的啊。

那么这篇文章呢我们做很多很多实验。那么这边我可能就只讲一个实验，就是啊就怎么样用它来进行啊进行就是小分子的一个设计啊。那么这部分呢其实非常简单，就是说 OK 我有一个。我有个小分子啊，我我相当于在一个非常大的那个分那小分子空间里面，就是做搜索啊，然后我搜索找到一些分子，这个分子能够满足各种要求啊，要求很多种了啊，一个是说啊，这个分子本身必须像一个药药的结构啊，或者说这个分子的啊，它是不是对于确特定的那个啊特定的疾病有治疗作用啊，或者说这个分子呢是不是没有毒？

啊，那么它有很多很多的那个条件，很多很多的目标函数，那么我们可以选取一些目标函数，然后用我们的啊，用我们的算法啊来进行啊优化啊，然后我们会发现就是我们的算法优化了之后呢，啊，我们发现我们这个啊这个方法其实叫那个LAP三啊，但是这是它的老名字，我们在camera ready的时候我们就把它改掉了啊，这篇文章其实是今年刚中稿了那个Europs啊二二十twenty twenty one。啊，你会发现就是说啊，在这四个不同的那个 metric 上呢，我们的算法啊，通过优化呢，就是我们可以得到更好的啊对应的那个结果啊。

而且很很有意思的是，就是我们这个算法就是可以突破一些局部极小值啊，但是相对来说，其他的算法，比如说 C E M 这种随机那个 local search 方法呢，可能在某个局部角质那边会卡住啊，然后再也不能往再往上走。OK，所以最后呢，我们讲一下就是另外一篇我们最近刚投的一篇文章啊，也是一个啊这个方法的一个extension啊。

那么就刚就刚才那张图上我们可以讲到，就是制药或者说做那个分子的那个结构的设计，它不仅有一个目标函数，其实有很多目标函数，但是我们过去的方法只能解决啊一个目标函数是单目标优化问题。那么下一部分呢，我们可以做多目标优化问题啊。那么有个问题是这样的，就是说我们有两到三个，或者说更多个不同的目标要一同时优化，啊，我们要同时最优化这些，呃，这些所有的函数。

啊，那么为什么能优化这些所有的函数呢？就是说，首先第一个就是说，我们没有办法啊，我们的目标呢，就是说，我们要找到一些解，这些解呢，在所谓的叫帕累托 frontier，叫帕累托的那个前前锋。啊，这样的呃，这样点上，那么这些点呢，就是说会比较好，因为这些点是所有解空间里面啊最相对来说比较优的点。然后解空间里面其他的点呢，一定是在各方面都不如啊这个这个这个前锋的某个点。

啊，那么因为这些点其实是覆盖了其他前锋、其他的点，所以你只要找到这些点的啊，就可以相当于把这个优化你解决了啊。那么，那么就是这样的一个啊，这样的一个问题。那么，如果在这种情况下呢，我们怎么样去用我们的呃 space partition 呢？啊，这个 idea 其实也非常简单，就是我们我们现在有这样的一个优化问题，我们比较还是我们有两个不同的变量啊，两个不同的函数 f 一和 f 二，对吧？那么我们要优化两个函数，这两个函数同时要优化啊，这本身就是啊，这是我们要找到一个啊叫替代的那个。

那那个单目标的函数去优化它们，那么这边替代单目标函数呢，叫啊叫 dominance number 啊，我们提供了这个函数，就是 number 函数，这函数就是说，我看这对于每个 solution 这个点啊，是不是被很多的 node dominant 啊， dominant 就是说啊，我存在另外一个解，这个解各方面都好于它。那么这种情况下，那么这对这个解对这个解来说呢，就是啊，我不如选这个解。那么这也可以完全扔掉啊。如果一个点的 dominance number 特别大的话呢，就意味着它被很多的、被众多的其他的解啊给给给盖住了。那么这个解的质量就不不会很好啊。

那如果是就是如果是在这种最前锋的解，那么这些解是无可替代的，因为它一定会在某个方面表现的比其他点更为杰出。那么有这些结构之后呢，我们可以把啊，从而把这个空间切分成好的和坏的，然后我们啊就是做那个 Monte Carlo search，就非常简单。啊，那么这篇文章其实也加了一个理论，那么这理论是解释为什么通过这个方式呢，我们的会得到一个比较好的解，啊，这部分我就跳过了，啊，然后呢，我们把这个方法呢就用在了很多实际问题上，啊，那么这边有三个不同的问题，啊，一个是非常简单的一个静态啊函数，啊，就是一个人工构造出来的函数，它有两个目标函数，同时是二维的，啊。

那么在不同的函数上啊，我们会发现啊，我们的方案，我们的那个算法呢，其实是优于啊其他的一些一些算法，包括一些比较啊比较接近或者说比较大家用的比较多的一些算法，像 N C G 一啊 N C G 二和 N C G 三啊，这可能相对来说是啊比较啊比较用的比较多的进化算法，用来做多目标优化的。然后这边的 metric 呢叫那个 hyper volume difference。比如说，我们对于每个问题，我们算出来它最优的 hyper volume 是多少？ hyper volume 的意思就是说啊，我们找到了前锋那个 pilot frontier，然后这 pilot frontier 啊把整个空间的覆盖覆盖了多大的那个体积啊？

那么我们如果找到了解，它的解内空间覆盖体积啊是接近于最优体积的话呢，那说明我们解是最优的。对，就说如果这个数字啊变得很小，就变成负无穷的话呢，那就意味着啊，我们的找我们确实找到了最优的啊那个啊最优的那个critical frontier。对，你会发现就是这这些啊解呢都是还是不错的。那么我们同样用这个啊，同样的算法去做 molecule design 啊。那么这种情况下呢，就是你会发现啊，在三两目标、三目标甚至四目标的情况下呢，这个啊效果呢还是啊比较好的啊，就是我们确实能够找到很好的那个 hyper保留的值。

所以基本上就这样的一些啊一些一些工作，然后最后呢，我们这边解释一下，就是啊这个算法是怎么工作的啊。这边就是啊我们用一个非常啊非常简单的一个函数啊，叫反正 Byron Curry 这样一个简单的函数啊。这个函数上你可以看到，就是如果你在上面跑我们的算法。那么这个算法就会啊，把不通过不停的切分这个空间啊，然后找寻来设法找到这个这一块区域。那么这块区里面包含了所有的那个帕雷托的那个optimal啊，那那个对应的那个值在哪里？那么通过，然后我只要在这里面进行啊大量的那个搜索呢，我们就会很快的效率啊找到所有的那个potential optimum的啊location。

然后呢，这边呢就是说我们比较了一下，如果我们用呃，如果我们只有 objective 多于就是大于两个或者三个的话，如果我们用指导 objective 会怎么样啊？就是我们的效果呢也会比很多的方法要好。行，然后这个就是我今这次那个分享啊，大家有什么问题可以提。哎，田博士你好，那个问题已经整理了，还差最后一个问题，现在还在整理中，您先回答前五个问题吧。啊，已经发到那个群里面了。

呃，行，OK，第一个问题是，FB 的 Go AI 相当于 AlphaGo 有什么区别呢？感觉 AlphaGo 更为人熟知一点。对，就是当然了，就是这边我就说实话了，我觉得我们这边特别是达 forest 的效果肯定没有 AlphaGo 好。当时二零一五年的时候，对，因为二因为达 forest 当时做的时候呢，啊，我们只用了策略网络，没有用啊值函数，所以效果就没有那么好。啊，当时我们的效果呢是跟最优的软件叫 Zen 打了一个差不多的水平。啊，但是当时 AlphaGo

的效果呢要比它好很多。啊，可能就达到了啊，就是。弱的业余棋手，呃，弱的那个职业棋手的水平啊，所以这个还是，啊，这个还是非常非常强的，啊，所以当时是造成了很大的轰动啊，当时我们就差一点点，就是一开始没有，啊，没有把直参数加进去，直参数其实很难训练的啊，我们当时也试过，也没有那么容易做，呃，对，这个是啊，这个是它的区别吧，啊。对，就是说，我就说可以，可以，应该可以这么说嘛。就是说，因为很其实有很多组在做相关的东西，但是最终能够能够产生大的新闻的，可能就只有啊，最后的那个最后那个成功的那个啊，这个样子。那么后面那个我们的那个 Open Go 呢，其实相当于是复制了那个啊 Alpha Zero 的啊这样的一个一篇文章啊，当时是想看一下那个效果会怎么样，同时用这个方式呢啊，然后来然后让啊让团队能够熟悉就是搜索这样的一个一个问题，或者说啊锻炼这个团队的那个对于啊大规模的问题的一个执行的效率。

呃，第二个是强化学习是不是基于马尔可夫决策链吗？优化它们什么关系啊？所以这个其实是我这个 talk 的前面那部分的主要内容，就是说优化呢，其实可以把它建模成啊马尔可夫决策链。啊，所以但是就这个建模的方式有很多种啊，你有可你可以横横过来建模，竖着建模都行，就是你可以把它建模成一步决策链，也可以建模成很多步决策链。所以每种每种不同的啊决策链呢，其实效果是不一样的啊。所以这这部这这次这个演讲的主要主题就是说，你通过不同的方式建模你的决策链，你可能会有不同的啊优化的效率。

FB的实验室平时和总部有什么联系呢？FB比较关注哪个方向的研究？呃，我们AI research其实也是一个非常分布式的啊一个组织啊，然后可以像我像我就是在总部的，然后还有很多人啊，比如在纽约啊，或者在在巴黎，或者在伦敦啊，或者在那个匹兹堡啊，或者在那个蒙特利，所以所以说这个实验室呢是分布式的，有很多的啊很多的地方。那么哪个方向的研究比较关注啊？我们这边做的东西比较比较比较杂。啊，不同的方向都有啊，有C V啊，有那个N L P，有强化学习，有speech，啊，这个都是有的啊。

呃，一定要使用图网络呃编码吗？呃，你你是可能是问的是那篇那个 CCom 的 paper。对那篇，因为输入的啊，解输入的那个 observation 是一个图，对吧？它是一个网络拓扑结构图，所以啊，这个是非常的啊，这个是非常自然的，就是我要我们要使用图上的编码，这个是非常自然的，可以。所以我们没有试过不用的情况啊，也许也可以 work，但我不知道啊。

对第五个 L M P T 是对每个问题进行单独优化吗？是的啊，就是它是一相对是一个黑盒优化问题，黑盒优化的一个一个一个一个一个包啊，可以用的。那么接下来就说一个很大的自然的问题，就说这个东西能不能 generalize，就是我们是不是能够学习啊过去的优化的那个结果，我们可以对新的优化产生啊影响，这个也是可以的。当然这部分呢我们还没有系统的还是做啊，是可以做的，应该是可以做的。

最后一个报告的参考文献是什么呢？这篇文章呢是啊已经放上 archive 了，就是它的名字就叫啊 Learning State Space 啊 for 啊 Sorry 啊 Multi Objective Optimization 啊 by Learning State Space 啊你可以查到啊这个应该已经能找到了，就是在网上能有已经放上 archive。

七呃，请问这个目标方法有测试过经典组合优化吗？啊，回答是没有，还没有试过啊，还不知道效果好不好。嗯，所以这个可能是很有意思的一个问题。

呃，Markov决策过程优化问题建模成MDP的high level idea是什么？不知道这是具体是什么意思。呃，就是我这边再说一遍，就是说优化问题可以建模成很多不同的MDP啊，你可以建模成一部MDP，你可以建模成很多部MDP都行啊。就是说现在问题就是说什么样的MDP是对着优化问题建模是最好的啊？现在问题是并不知道。

呃，第八个是搜索空间划分和分支界定有什么关联吗？对这个问题很不错，很很有想法啊。我们还没有呃说有特别清楚的一个关联啊。分支界定的问题呢是呃是在于什么呢？就是说呃它的分支呢其实是很多时候分支界定是那个 axis aligned。啊，就说我又比如说有十个变量，然后分支的方案是一定要沿着某个变量去切的，对吧？就比如说啊，那个整数整数规划问题里面，就是如果有一个x一x一，你可以切成比如大于等于二，小于小于呃或者小于二，对吧？划分方式不一样。对，所以黄峰，然后呢，就是说这个这个这个切分呢本身啊是没有那个呃没有学习过程的啊，就是这个是说我我我们做分式界定的时候呢是OK，我就切两半，然后我通过呃然后通过我把这两半都都搜完，然后得到最后的结果啊。对，然后但是我们这边的搜索空间划分呢，其实是有学机器学习的过程啊。我通过过去的经验，我们可以找到一个比较好的啊那个 decision boundary，然后去切啊。所以这个切的它不一定是严格的，它有可能会漏掉解啊。但是呃代价是呃是就是说能更好的搜到更更更容易找到的更好的搜到那个解，所以它有一个代价在那里。呃，只是划分方式不同。呃，就是我刚才说了，就是呃，分支界分支定界呢是啊是没有那个什么深度在里面。啊，然后你要你要你要对两边解完的那个切完的空间，你要都要找那个下界和上界，对吧？对，但是我们这边做的空间划分呢，其实是啊，其实是通过机器学习方式来进行的，所以它有一定的泛化能力啊。如果你呃，如果你的你使用了机学，你的使你使用那个啊，机器学习的那个分类函数呢，是跟你最后的你最你这个函数本身是你契合的话呢，你这个切割会非常非常有效率。

r l，呃，r l得到的解怎么判断是不是爬了幺头点？你说是最后一篇文章吧？呃，对，最后一篇文章是，嗯。就这样，就是说，就是首先第一点就是这篇这篇文章跟 reinforcement 的具体的方案那个方案的关系不是特别大啊，所以这篇文章主要是通过那个空间切分啊，然后用空间切分的方法呢，很快速的定位啊 plateau 点的那个位置，然后在在在这个位置上呢，就是使劲使劲那个采样啊，使劲优化，那么这样的话能找到很能很有效率找到 plateau 的点。啊，那不是判断是不是？就首先就是说，你现在得到一一组那个解，那么这组这组解其实你能知你能知道的是这组解里面啊，到目前为止最优的那个不被任何其他解dominance的点是什么，这个是可以的。但是你并不知道这个点是不是帕累托的那个 frontier，对吗？所以我们只能无穷的接近帕累托 frontier，但是不能达到那里。啊，所以我们现在这个我们这边，呃的那个 metric 都是啊，我们现在的那个最优的不被任何东西扰动的这些点，它们组成的啊估计出来的 Pareto 那个 frontier，它们对应的那个啊 hyper volume 跟你最终的这个 maximum hyper volume 之间的 difference，啊，它用这个来做 metric。

请问对ADMM算法了解吗？啊，我没有用太多，用过ADMM算法啊。这个是我能知道的，就是说它应该是有一个相当于加一些那个辅助项，对吧？然后，呃，把一个优化问题拆成两部分啊，一部分是f，一部分是g。啊，然后啊，如果你同时解F和G，不不是很好解。但是如果你同时分开解F和G，比如说啊，F本来是f x加g x，你现在变成f f x一加g x一加g x二。那么，如果是这样的话，你单独解f和单独解g呢，可能会有解一解，比如说这样子，对吧？有解一解的话呢，那这个算法效率就会比较高啊。那通过反复迭代呢，那个效率就会比啊，可能会比原来要要要高一点。啊，对，那么就是说，呃，那么这个东西的问题就在于，就是它还是依赖于函数的形式。啊，如果这个函数的形式是呃非常有结构的，比如说第一项是个凸的啊，第二项是也是个或者说是个凹的或者什么，就说那如果是这样的话呢，那你可能跑ADMM很有道理，因为你每部分的函数结构是非常有结构的，那我解起来会比较快，啊。是这样子，是一个一个，但是我们这边呢，就是啊，并不限于具体的函数结构啊，你可以对任使用任，你可以在任何函数上跑我们的什么上。

呃，那时间的比较是包括训练过程吗？啊，我们这边没有写时间的比较，我们这边都是写，呃，那个样本的那个复杂度，就是说横轴是我问了就是query了多少次，封神value啊，因为在实际问题中。呃，最问问题时间最最花的时间最多的是，OK，我们要计算这个函数值啊。如果你要做黑盒优化问题，比如说你要优化一个很长函数x f，那么这个函数可能呃可能非常难计算啊。你算这算一遍这个函数，你可能花比如说十分钟或者花一个小时，对吧？所以这其实是最大的问题。所以我们这我这边就是比较的，就是说我们要多少次分身call得到一个最那那然后比较同样的分身call下去的质量是怎么样子，对吧？对。对，所以这边呃，我没有计算过那个训练的那个时间过程，而且训练应该也比较快，因为点不是特别多。那主要是问题是，并不是训练速度有多快，而是你是卡在那个啊，在有限的点上如何得到最优解这个问题上面。

呃，可否总结一下学习求解优化未来的研究方向？呃，我觉得一个可能是怎么样把其实现在一些方案放进就是更大规模的呃优化上面去啊，这是一个很大的问题，因为现在大量的文章可能解的问题比较小规模啊，比如说一百个或者说一千个variable啊解一下，那么那么这样的话呢，就是理论上是可以work的，但是。但是问题是，就是说优化的人做优化的人可能对此不屑一顾，优化的人会觉得我们现在求解器能够求解上个上百万的变量的解，啊，所以就这样的话呢，神经链可能没有什么特别大的用处啊，所以最终说，如果我们神经链能够证明在呃非常大的规模问题上也会有更好的结果的话呢，啊，那这个就会啊非常有意思啊，这个是一个很大的一个问题。

那么另外一个可能的方向呢，就是说，呃。如何找到一个好的呃那个理论的一个一个一个一个结果啊？因为现在其实啊马氏令大家知道就是很多时候用神经网络，神经网络是黑盒子啊，黑盒子到底它找出来东西好不好，没有人知道啊，所以可能有很多做优化的或者说做运筹的呃学生呃或者说同学会觉得啊，你用马氏令做一下我们。我们这些一些很漂亮的那个上下界全都没了啊，然后解出来解你也不知道是什么东西啊，所以如果我们能够啊找到一些比较好的那 guarantee 的话，那其实对啊我们生产力是有很大的，对这个方向是有很有很大的助力啊。这个其实是一个很难的问题，但是也可能是一个很好的机会啊。这对强化学习来说呢，这也是很好的机会。

啊，因为强化学习里面有很多的环境啊，然后大部分环境是人工构造出来的，然后人工构造出来的问题是在于，就是这环境可以是任意的，所以到底哪些环境好，哪些环境贴近贴近实际，哪些环境是没有什么没什么意思，这其实是完全由主观决定啊。但是呢，那个优化呢，它其实提供了一个非常好的一个测试平台啊。优化里有很多问题是非常实际的，是非常有用的，是非常重要的问题啊。所以这些问题上，如果我们能够对强化学习啊的一些啊效果做了一些啊做一些那个分析的话呢，啊，这其实对强化学习本身的发展也是很有帮助的。

好，大家还有什么问题吗？嗯，现在来看的话，弹幕暂时是嗯没有什么问题了。OK，嗯，好的，好的，那我们这期 Talk 现在就到此结束了，非常感谢田渊栋博士的参与，这也是第二次、第三次来。参与了吧？非常感谢，非常感谢。这个应该是第三次吧，因为我呃有些有些东西我可能已经讲过啊，但是现在又讲一些就是现在就是之前的文章的 extension。嗯嗯，好的好的。好，那小王我们这边是怎么样？嗯，那我们呃第二十九期 Talk 的话，现在就正式结束了。然后跟大家预告一下，我们嗯下一期的 Talk 将会在十一月六号开启，到时候请关注我们的推送。好的，那嗯，田渊栋博士这边就可以结束了，然后我们这边也会陆续的把直播关掉。好，好，嗯，先这样吧。好的，感谢，嗯，谢谢，谢谢，嗯，大家周末愉快。嗯，周末愉快。Facebook 田渊栋博士：使用引导策略搜索方法解决优化问题。YouTube_search:yuandong 20211017 OR Talk NO 29 Facebook 田渊栋博士：使用引导策略搜索方法解决优化问题。Facebook 田渊栋博士：使用引导策略搜索方法解决优化问题。YouTube_search:yuandong 20211017 OR Talk NO 29 Facebook 田渊栋博士：使用引导策略搜索方法解决优化问题。