大家好，今天非常荣幸能到运筹帷幄这样的一个论坛来。我讲一下我们最近的工作啊，对。然后这次的那个讲座呢，主要还是用中文来讲，因为希望那个让大家可能更能够听懂更多一点。呃，对。然后这次主要讲的内内容呢，就是如何在那个优化这样的一个问题中用蒙特卡洛树搜索。那么在这中间呢，我们其实提了一个比较有意思的一个算法叫latent action啊，就是learning latent action。这样的一个一个一个一个，就是怎么样去学习一个隐的状态空间、隐的行动空间，通过这个方式能更好的进行优化。
现在主要是通过呃就就是这个想法，然后我们做了若干的一系列的工作。首先第一个就是如果大家还没有用的话可以试用一下。就是我们的代码呢已经开源，并且放在网上了啊。如果大家想用的话呢可以点击或者说是拷贝，或者说是那个用手机扫描这个QR代码啊可以进入这个网站。然后可以用一下我们这边算法。那么这个算法呢就主要是用来做黑盒优化的，啊就是说一个函数这个函数呢可能你并不知道它是什么但是我可以通过黑盒优化的方式找到它的最优解。
这样的一个一个这样的一个库啊呃对。那么黑盒优化的意思就是说如果你有一个函数f那么这个函数f呢它是它并不知道里面的导数也并不知道里面的任何的一些信息。那么你能做的呢就是说我从这个函数出发我每次可以那个调用这个函数得到一个数字，那么通过这个数字的值然后决定下一步我要去哪里再做搜索。啊通过这个方式呢能达到这个函数的最优解。那么这边呢我们提供了一个代码库，代码库呢能够呃更好的优化这个函数以最小的代价啊获取比较大的那个函数值的一个收益。
那么基本上这样的一个一个库啊，呃这边先讲完了之后呢我们肯定先讲一下就是这个这个库的一个最后的那个思路是什么啊或者我们这边的研究的创新点是什么。首先就是那个优化问题呢其实是一个非常广泛的一个一个问题，很多的领域呢就是不仅仅是计算机啊而且很多其他领域呢其实都要去解决这个优化这样的一个问题。那么比如说我们呃我们要找那个把所有的城市连在一起这样的一个叫做那个旅行商问题，那么怎么样找到一条路径呢能够让这条路径的那个和啊那个距离的长度是最短的。
然后同时呢能够让这条路径呢跨越那个所有的给定的那个城市啊这种叫旅行商问题。那么这个问题呢其实是一个N P hard 的问题，就所谓 N P hard 的问题就是说在最差情况下。呃你可能需要花很多的你要花指数级的时间才能解决啊这个问题啊得到最优解啊。那么相似的问题还有其他的，比如说像那个 job scheduling 这么蛋白质折叠啊这些问题都有。那么在各行各业里面都有存在这样的一个问题。
那么像这类的问题呢其实完全可以用啊深度学呃可以用比如说是呃不仅可以用传统的优化方法，而且现在最近现在有流行的比如说用。呃神经网络或者说用强化学习啊来找到它的最优解啊这样的一个方法，就是说你把这个呃优化问题呢变成一个sequential decision嘛就是序列式的那个求解或者说序列式的。呃优化的那个决策优化的这样的问题，啊然后在每一步呢就是找到下一个呃位置的时候呢其实用神经网络去呃预测啊比如说我下一步应该怎么走。
那么通过这个方式，我们就利用神经网络的一些泛化能力能够找到更好的解啊有些时候呢可能可以比啊就是常规的求解器的解法呃速度更快啊或者说同样时间之内呢得到更好的解啊这样是一个比较这个大致的一个思路。那么这个也这样的一个方法呢其实是不是可以也会用来做其他的问题呢你现在只是一个啊非常大的或者说一个比较呃比较那个呃比较广泛的或者比较open的这样的问题。大家很难现在还没有一个定论需要每个问题要具体分析，具体问题具体分析。
那么呃这里面我讲一下就是说如果你用强化学习来做呃优化问题，和呃用强化学习来做游戏啊这两个之间有什么大的区别。我们大家都知道强化学习一开始出道的或者说成名的那个作品呢就是OK，我们怎么样用深度强化学习来做比如说围棋，或者说来做啊象棋。或者说来做星际这样的一些游戏，那么这些游戏里面呢就是因为游戏呢就是里面有一个很有意思的点就是它的行动空间呢是固定的。
啊比如说左边这张图啊这是一个围棋的一个局面，那么稍微懂围棋知识的人可能大家都知道就是围棋走棋的时候呢每一步是走在它的交叉点上的。啊你现在有三百六十个三百六十个交叉点就是整个围棋盘是九十一乘九九十一的，啊那你在三百六十个交叉点上你可以找一个地方这个地方找到空了就可以下子。那么这个就是围棋的行动空间，那么这个空间就是三百六十维的，啊这个非常的直观啊非常明确是确实是这样子。
但是呢其实对于呃一般的优化问题来说一个优化问题呢其实它本质呢是你从一个初始值出发啊这个初始值在一个高维空间里面。那么怎么样找到一个嗯一个局部的或者全局的一个最优解啊是这样的一个问题。但是对于优化问题来说呢你并不需要就是定死行动空间啊你完全可以通过各种方式走过去啊。也许呢你可以选择我们走直线来走过去，或者说我们可以选择绕远路。但是绕远路呢有好处呢也许我们可以绕过比如说山峰啊，我们可以绕过峡谷啊，我们可以达到最大最最优点。
所以就是说在高空、各在高位空间中呢其实这个呃可选的这个行动空间呢是非常非常大的，啊是大到你很难想象的一个一个程度。所以呢对于不同行动空间的这样的一个参数化呢其实可能会有完全不同的搜索性能啊。所以这个其实是这次呃我讲座的一个一个主要的一个点，那么有什么样的方法能够自动的去学会啊这个行动空间啊能够自动的找到更好的行动空间使得这个最后的那个效搜索效率能够提高。
那么呢呃如果我们看以前的那个一些文章呢你会发现其实有很多的文章啊他们都是通过人工的设计来设计行动空间的。呃像比如说有一篇文章是比较有名的就是怎么样用，呃神那个随机，呃怎么样的那种强化学习来做神经网络的搜索啊就是左边这边。那么这边有一张很明显的图，这张图里面就是跟你说了我们非常很清楚的设计了行动空间然后每一步把行动空间里面要做的事情都写下来。
比如说这个图里面表示就是第一步可以呃设定，比如说前面那层的啊那个数那个filter数目是多少然后高度是多少宽度是多少。啊然后每个那个卷积层的参数是多少这一步步的通过呃一个呃卷积层一个那个RNN去生成出来，啊那么这个空间其实是固定死的。非常清楚的固定死一个行动空间，啊那么右边是最近有一篇文章是做那个旅行商问题也是用reinforcement learning。你它的行动空间呢就是说啊给定当前的状态我现在在哪个城市里啊那么下一步我要去哪哪个更哪一个比较近的城市。
那么通过这个方式呢我们可以得到一条路径啊这些那这些都设计过了，就是说但是呢就是这个有这些那个之前的文章呢你会自然而然就想到就是也许对于呃优化来说呢行动空间本身也是可以被优化的。啊这是以很多其他过去的文章没有没有做的或者说忽略的一个点。那么接下来这张这张图呢就是说显示了一下就是不同的行动空间啊可能对结果呢会有很大的不同。这里是一个非常简单的一个一个example，这个是在那个呃神经网络architecture神经网络搜索这样的一个啊问题这个具体的那个应用上做的一个一个一个example。
那么这里面呢就是说我们设计了一个非常简单的一个搜索空间啊啊神经网络现在有我们把它简化成三个参数啊一个是深度。嗯一个是那个channel的数目，还有一个是那个kernel size的大小啊。现在有五种深度可以选然后两个channel可以选然后两种kernel size可以选。所以啊你通过一些乘法呢就是你会得到一些不同的大小的那个网络好有这么一个大小的网络空间之后。
然后我们接下来就是说OK，我们在这空间里面怎么搜索啊有很多种方法可以搜索。当然可以说我们穷举这样的话我们可能很容易的得到了就是最优的解是多少啊所以我们知道最优解是在哪里的。但是呢我们这边想要模拟一下就是说如果我们使用不同的行动空间是不是能更更快找到最优解。所以，我们这边试了两种不同的行动空间比如说一个是非常简单的sequential action space这是什么意思呢就是这跟之前的那个Google那边的方法是一样的。
我每次加一层啊上去然后每次加一层的时候呢设置一下它的那kernel size和那个channel大小啊。第一层设计完之后再去设计第二层一层层的往上叠。这样一个行动空间非常非常直观，非常简单啊。那么另外一种行动空间呢我们可以搞得稍微的高级一点。哎我我先设定一下这个行动空间的整个神经网络的那个深度啊先设完深度之后然后我们再设每一层的k跟c，是这样子。
那么这行动两个向行动空间看起来有一点点不一样就是那个global的action space呢它是设先设那个深度的。但是你会发现照这两个行动空间来搜啊你可以用我们的卡路数搜索，搜索来来搜你会发现它的那个效率是不一样的。右边这个图呢就表现出它的效率不同啊如果这个图什么意思呢就是说我搜了多少样多少样本，对应的就到到现在为止的那个最优的呃那个正确率是多少。
我们当然希望这个曲线呢能够做到就是给你两个样本它就马上跳到最高那这是最好的，那这是不太可能了。一般来说呢就是它随着样本数变多这个数字会变得变大。它单调肯定是单调的，但是啊能都快速单调这个是我们想要追求的目标。所以你会发现呢在这个图里面呢呃如果你用 global 的 action space，它的这个这根线的那个那个起来的一个速度呢要快于那个 sequential 的 action space。
所以就意味着就是行动空间不一样呢它的搜索效率是不一样的。所以这个是一个很有意思的一个例子，那么为什么它的原因啊下面这张图呢其实显示了一下这是一种。比如说我们就从根节点开始，根节点的它第一个选择比如说对于 sequential action space来说这第一个选择呢就是我要加这一层这一层的 k 是多少啊这是第一个选择。但是对于 global 的那个行动空间呢它第一个选择是我要是啊哪一个那个我的深度是要多少多深对。
所以你会很清楚的发现就是如果我第一个选择是神经网络有多深啊它对不同的深度呢它这个平均的 accuracy，它们的峰值的差距是很大的。这其实是呃非常符合我们的直觉。对于我们直觉来说我们可能会觉得神经网络里面每一层的具体的那个 kernel size 没有特别大特别大的用处，最大的还是看有多深这是最重要的一个点对吧。因为这个呢所以我们在做决策的时候呢就是我们先会把最重要的决策放最前面做啊那么这个这样的话你就可以提高它的搜索效率。
那么接下来就是说OK，这个是一个很好的一个想法。那么接下来就是说为什么我们怎么样才能做到这一点我们要去学到这个呃action space啊就是首先这边我们就要想，就是如果你要做这这点首先第一个我们要怎么定义这个action space。我们可以先以那个 tic tac toe 为例就是井字棋为例啊这个游戏非常简单嘛就是大家画叉和圈，对吧。然后三个叉和三个圈啊在横竖呃斜方向上只要它能够连在一起那就赢了。
所以你会发现在这个很简单游戏里面呢就是你每次做一个决策那么这个决策呢实际上是把整个的那个游戏的最后的那个结果呢切分成了几块对吧。所以你的这个决策越多呢你最后切分呢就越小然后最后你把这个游戏的那个区间切分到非常非常小的时候呢这个游戏的结局就已经注定了。所以那么照这个想法呢你其实可以想到这个切分的方式呢就是对于顶次器来说这当然是固定的，但是对于我们一般的那个 optimization 来说啊优化来说呢其实这个切分方式是不固定的是可以自动可以自己学的。
所以这个是个很有意思的一个一个现象对吧？那么右边呢其实给你看了一个非常清楚的一个图。这图是说啊我怎么样能够切分这个整个搜索空间，使得我最后的那个切分之后的结果呢能够有更好的结果。就比如说这边根据不同的切分呢你会画出一个图来啊这是左边是切分，右边是根据这个切分画出了一个一个一个一个树对吧。你先把整个空间切分成两块一块是啊绿红的还有一块是绿的这边啊，然后绿的这一块呢它可以再切分成一个蓝色的还有一个咖啡色的。
所以通过这个方式呢就可以把空间切开那个这种切分的方式呢就是行动空间的一个定义。那么有了这个定义之后呢其实我们可以看到，就是我们可以回到刚才那个问题这个问题上是就是说根据不同的行动空间的切分呢你其实可以看到对应的那个值的分布呢是不一样的。所以这个其实就给大家提供了一个很好的基础说为什么切分行动空间是很有道理的。那么这个图呢其实就说了出来就是我们有两个那个action space，对吧一个是 sequential 的，一个还一个是 global 的。
对 sequential 来说你会发现就是在行动空间的切分的这个结构之下呢你就会发现就是每一个子树切分完的子树上呢就是它的有些点呢很好，有些点很差。这些点就这这个点呢是指它的那个 accuracy。所以你会发现就是其实这些很好很差的点之间可以离得可以离得非常非常近啊。所以每棵树切完之后呢其实你并不能保证这棵树里面所有东西都是好的。那么这样的话，其实增加搜索的难度因为你搜索的话你就必须把所有的树都变了一遍然后才慢慢慢找到啊最优的解。
因为每棵树的里面呢都有可能出现最优解，这是一个很大的很麻烦的地方。那么这个会增加你的搜索难度，但是呢如果你把行动空间换一种定义方法比如说定义成 global 的。啊那你会发现它的那个好的点和坏的点呢它们之间的结构呢就相对来说比较规整一点。比如说啊这边有一个很大的一个枝，这个枝上的那个很多点都是好。那边这些质量很多点都是差的。
所以你会发现就是说形成空间不同的话呢它就自然把这个啊问题切分成呃好的区域和坏的区域。那么坏的区域呢你就不用太多再做建模了，然后好的区域你可以再继续切分下去。那么这样的话呢你就会有一个啊更好的一个函数那个值函数的一个分布。那么这是更好的值函数分布呢那最后的结果呢就是说你的效你效果会更好啊其实就是这个这就其实就是整个思呃整个文章这一系列文章的一些一个思路。
好那么有了这个思路之后呢我们来接下来看一下具体的算法是什么啊所以这个算法呢一开始呢我们是用在神经网络上的网神经网络的那个搜索上的。呃所以现在先讨论的就是具体的那个应用呢是神经网络搜索啊，所以这个神经网络搜索呢就是我们怎么样去把这个方法这个想法应用到上面去。这是一个我们现在这样的一个非常高非常那个初步的一个示意图啊所以这个示意图是这样的，就是左边那个呢是啊我们当时看到的其他的文章。
这些文章是怎么做的呢我们先从一个空的神经网络出发啊我们在上面一点一点的加每一加一一层一层加上去。所以每一层加上去之后呃你这个树呢就往下走一个一直走到最后，子节点就是一个完整的神经网络啊这神经网络里面就是你可以做一下那个训练然后看它的效效果有多少，效果有多好。
那另外右边呢这个图呢就是我们的方法。那方法是什么样子的呢就是根据刚才我们说的，就我们一开始呢是从一个整个那个神经网络的设计空间出发。然后我每个
行动，或者说每个行动呢，其实是在这个设计空间上的一个切分。所以我们每次把这个设计空间切成好的和坏的两块，那么这个切可以继续下去，一直再继续到比如说一个好的那个节点，最后有一个叶节点。这个比较左边的叶节点呢，其实就是说我希望前面切分切完之后呢，这叶节点对应的那个神经网络的那个子集，这个子集里面的那个节点呢都是还是不错的。
通过这个方式去学，然后这个切分的方案其实在整个的搜索过程中是可以动态的去调整、去学习。它可以通过根据以前的所有搜索过的东西，动态地去生成一个新的那个切分方案，然后用这个切分方案去反复的再去切分原来的行动空间。能够让最后的那个切分出来结果更好。
那么根据这个想法呢，就自然而然就会有这样一个算法。那么这个算法有一两个步骤交替进行。首先就是说我们给定了一棵树，那么这棵树的这个结构是给定的，那它的行动空间的定义呢是没有给定的。所以我们可能先要随机的训练、随机的那个采样一些点，根据这些点的位置呢去把行动空间的那大致的结构或者大致的那个划分给切分开。
有了这个切分开了之后呢，好，然后我们定义了行动空间，那我们就可以用蒙特卡洛树搜索去根据这个行动空间去搜索什么样的那个节点呢是比较有希望的，或者说你能在上面找到更好的节点。那么做到一定程度之后呢，然后我们把这些数据拿过来，然后再去训练一遍我们的行动空间。
那么行动空间根据新的那个节点，那我们可以就重新再切分，一些地方可能切的不好，那么我们可以继续切分。切分完之后呢，那么回到第一步啊，然后用这在用在第一步上呢用那个神经网络的、用我们的卡奥斯搜索呢继续去切分，诸如此就是这样的迭代。
然后就看就是我给定了多少样本之后呢我们最后最高能达到什么样的效果啊？那么这里面有几步是要讨论的。第一步嘛，就是说我们怎么样去学习这个行动空间啊？那么这边呢先讲一下就是怎么做线性的非常简单的线性方案。
这个非常简单，基本上就是属于机器学习101的一些简单的那个想法对吧？就比如说吧假设你这个动作空间是由两个参数组成的，一个是一个是那个宽度啊一个是那个深度还有一个是那个每一层的决策的数目。那么这两个参数呢就可以根据这两个参数你可以给可以得到一个performance啊。
那么根据这个呢你就可以在上面切一刀，我希望切完之后呢能够把所有好的都切到一边去然后坏的呢切到另外一边去啊。所以这样的话这一刀切完之后呢就是有一边是左边的还有一边是右边的这么这样一种新的模型就出来了。
这就是一个非常简单的一个一个想法对吧？所以就说这根红线呢就表示就是什么方向能够让那个性能升的最快啊。那么沿这个方向上你横过来切一刀那上面和下面就是好的坏的结构啊。所以用这个呢可以拿来做行动空间的一个定义是这样子。
那么大家会说了就是说这是线性的非常简单，那么完全可以做非线性的对吧？所以接下来就是这篇其实已经中了是我们投到了那个NeurIPS，后来最近是啊中了。那么这边呢就是我们怎么样去拓展它怎么拓展呢？
就是我们可以把行动空间的那个空定义从线性变成非线性。我可以先去学一个啊我们先做个简单的聚类，可以把好的跟坏的两块呢就是聚类出来。那么就是变成二和三然后二和三加上这个剧烈标记之后呢可以用SVM再训练一遍得到一个非线性的一个boundary。
那么用这个方式去切分的整个action space，有这个切分之后呢你这个行动空间那个定义也就有了啊然后你可以iteratively做这个事情。好，然后我说到这儿呢就是说大家可能就已经清楚了什么叫行动空间然后怎么去定义行动空间怎么样自动去学习行动空间。
但是呢大家可能并不理解是为什么我们要去做蒙特卡洛树搜索啊就是为什么MCTS呢在这个方面是有用的啊。这边这里面我们先简先跟大家讲一下，就是有一些就是在实际应用中你会发现有很多的疑难杂症呢其实没有那么简单啊。
像这边是一个非常简典型的例子啊啊，就是说我们假设就这棵树，这棵树只有两个枝一个是左边一个右边啊。然后你在切完之后呢你可能会发现就是因为样本数不足啊所以呢这左边和右边这两个区间呢就是也许你左边看到的那个结结果那个它解呢都还可以啊但没有一个没有非常好的。
那右边那一块呢其实大部分的解都非常糟糕黑点子啊但是有一个解或者有一小区域是非常好的是optimal solution。那么在这种情况下呢如果你开始建立行动空间的时候呢就是你只采样到了那些左边那些还OK的、还可以的那个解。
那你你可能会本能的觉得左边比右边好啊那如果左边比右边好的话呢你就会发现啊我把这个刀一刀切下来之后我把左边右边分开了。然后按照这个切的逻辑如果我没有任何的exploration、没有任何探索，我会觉得我就一直往左边探索就行了我就不想往右边走。
那么这样的话你就会呃失去这个找到optimal的机会啊所以这就是为什么我们还是要做exploration，就是虽然我我现在觉得右边不好但是呢就是我保留呃去右边那边探索的权利啊也许他探索了一阵子之后呢他会真正发现一个更好的解。
那么有了这个之后呢我们在下次决定行动空间的时候呢就是我会自然而然的把右边的一些点划到左边去啊那这样的话呢就是行动空间重新定义了。然后我在下一步的那个搜索的时候我就能找到一个最优解所以因为这个呢所以我们其实是需要做exploration在这个优化的那个情况下。
那么这边可能要回顾一下我们那个蒙特卡洛树搜索的那个具体的工作的过程啊这个是一个非常简单的一个非常基本的一个算法那么这个算法是在围棋上呢获得了一个很大的成功啊就是阿尔法Go这个系列里面就用了这个算法啊我们这边的围棋的软件呢也是用这个算法然后有更好的结果。
那么这个想法非常简单，就是说我我在每时每刻呢是维护了一棵树那么这棵树的根节点呢是当前的状态啊然后它所有子节点呢是在下完几步之后呢得到新的状态啊。那每次你在做那个探索的时候啊你其实是希望就是它在探索的时候它有两个选择，一个选择是我希望沿着以前胜利道路走。
我希望就是我每次走的道路呢是以前证明过是比较有希望赢的道路就比如说B那边那那条红线啊这是一个。那么但是呢除此之外呢其实我还是希望加一些exploration、加一些探索。
那么这探索呢完全取决于啊就是每个节点上的那个被访问过的次数。如果有节点没被访问过很少的次数呢那么有可能这个节点还不错也许我会、我需要花点时间去探索它啊虽然这节点目前胜率不高但是我还是需要花时间探索它。
因为探索的那个快贴源是在右下角就这个就叫那个UCB的一个快贴源啊叫PUCT啊这个可以呃用在很多不同的地方。那么这个时候你只要维护每个节点上的一个探索的那个次数呢就可以算出来对吧？
通过这个方式然后每次探索完整个pass之后呢然后你就会做一次那个back trace。这个back trace呢会把每个节点上的一些当前的胜率啊和当前的访问次数这个数字更新一下然后整个过程重新开始。
其实是这样的一个算法好那用这算法呢其实它就平衡了就是呃我当前利用我现在对于这个每个节点的胜率的预测和那个exploration和一些探索啊如果我们希望兼顾探索呢同时也要利用那个之前的探索的结果啊希望这两边能够平衡那么最后结果比较好。
那么这个算法最后一个问题呢就是我怎么样去采样就在一个具体的那个树节点上采样啊这个是很重要的因为在按照文成海的树搜索里面呢其实有一个很有意思的点就是你每次到根节点的时候呢你希望就是再往前走一步啊我希望拓展这棵树的那个节点。
那么对于我们这边来说因为每个节点对应的是一个子区域对吧？所以有这个子区域之后呢如果我们要探索更细的子区域的话呢我们就需要在原来子区域上去做一些样本。有了样本之后我才能继续呃做那个线性分割或者是非线性分割让这个区域再分成两个更小的子区域。
所以为此呢你必须在每个子区域里面啊做一些采样。那么怎么做采样呢？就是这边我们提供两个方法，一个是简单的就是在线性空间里面可以采样的因为如果你每一个行动空间都是线性切分的那么你最后的那个树节点呢它其实是一堆啊线性切分的交。
因为这对线性约束的交呢所以就是最后它得到一个polytop，这个polytop呢其实可以比较有效的采样有一些算法可以做的啊这是一种方案。
那么另外一种方案呢就是说如果大家都比较懒也不愿意搞一些非常fancy的方法那我们总可以做reject sampling。的意思就是说我完全可以啊先创建一个比较大的区域那么这个区域可能就包括了或者说大部分包括了这个最后的那个节点的一个区域。
然后采完之后呢就是每个点我可以从很简单的步骤去判断它是不是在这个区域里面啊然后把那些不在这个区域里面的点给去掉。这个很简单你就可以把那个从这个节点到所有的父节点呢它的constraint都查一遍他们都全部都要通过才能保证这个节点确实在这个区域里面。
那么这个方式呢你也可以通过采样那么这个方法就是有一个问题就是你必须有一个initial的点去做种子然后在这种子附近呢就是找地方采样。那么这种子很简单就是说你可以把已有的样本点拿过来做种子啊在它上面附近采样就可以OK。
那么还有一种方法呢其实是也许我不做采样，那么我可以在这个子区域的那个周围或者说在子区域里面我可以去做一个高斯的啊就是fitting，假设我有一个就是高斯过程啊这高斯过程其原则上可以拟合任何函数那么你可以在这个子区里面去拟合一个函数。
通过我们现在已有样本去你可以去拟合一个函数这函数拟合了之后呢啊你就可以用这个函数然后去找这个函数在这个区域里面的一个比较大的一个值啊那么这个呢已经是有比较好的方法可以做了啊高斯process已经有做了可以做。
那么这有这里这样的做法呢其实有很多好处啊我这边列了四个，一个呢是说因为这个区域比较小啊所以你用高斯process来那个fit这个区域呢其实是比较容易的。这是一个很好的一个一个性质啊刚才傅老师的问题就是说它虽然说fit能力很、它的拟合能力很强但是如果区域很大的话它就需要指数级的样本去拟合它啊。
所以呃如果区域小的话呢它的优势会体现出来啊对，然后呢还有就是说如果你做采样、如果你做采的话呢计算几何呢不是说这个区域的最大值而是区域的平均值。但是如果你找这个区域上一个函数的max呢其实是它能够预测这个区域的最大值啊这是跟我们的目的呢是一致的。
对，然后呢还第三个好处呢就是说比如说对于高斯过程来说它的拟合的那个复杂度呢其实是一个非常呃不是一个非常好的它不是线性的啊因为点越多其实你需要解你就需要解一个比较复杂的矩阵。如果你有n个点呢你就要解一个就你要去对一个n乘n的矩阵去做求逆那么这个其实要花很多时间的对吧？
你可能要花那个平方或者立方的时间才能把这个矩阵给逆回来那么这样的话呢你就呃会浪费时间特别点多的时候非常慢啊。但是呢我们这边比较好的地方是啊因为每个区域都比较小所以里面的点也不多。
点里面点一旦多了呢它就会分成两个小的子区域那么这样的话呢你其实啊永远不会碰到就是我需要大量点来拟合一个高阶高次过程这样一个是这样一个问题啊所以这是一个很有趣的一个trade off。
那么有这些的呢那其实那个最后的很自然就是我们希望最后每个区域呢就是高层破财来拟合的。那么接下来就是现在算法呢基本上讲完了，然后我们现在讲一下就是它在一个是神经网络搜索上的应用啊还有呢就是说啊它在那个一个黑盒优化上的。
那么这个呢是神经网络搜索一个一个这样这样一个问题啊就是这个有一个神经网络里面有一个搜索空间叫NASNet，那么这NASNet呢其实是一个人工定义的一个搜索空间啊这里面是就是说如果你输入样本呢你可以通过很多层啊这些层呢是一个normal cell和reduction cell的一个交替。
然后最后输出得到一个classification的结果那么这个每个层里面这个cell的结构呢是啊经过参数化是可以让计算机自动自动设计的啊它有一些比较复杂的一个设计的设计空间。
那么在这个一个空间里面呢其实我们完全可以再继续用我们的那个NAS啊、我们的那个搜索算法。那么这是一个比较有趣的结果那么这个结果呢可能现在out of date啊但是现应该不是最优最optimal，但是它可以表现出来就是它确实效果呢也是不错的。
这边子线是我们的然后其他的颜色的线呢是各种各样的其他算法啊你可能会发现就是很有意思的地方是，我们的算法在很很少用了很少的样本呢就会得到非常高的那个accuracy啊。这个可能是因为我们这边确实学到了一个比较好的action space，我们action space用这个action来做搜索效果比较高。
那么这边呢是一些更多的一些结果啊，这个结果基本上就是显示出来我们的算法呢还是相对来说比较reasonably good它的formance还是不错的。然后呢我们也在YouTube上面做了实验，就是说我们因为前面的那些都是有数据集的什么样数据集呢？
就是我们先有一个比如说10K的这样一个数据集啊然后里面每一个architecture都是经过计算过的，然后都已经算出来它的formance是多少然后把它们静态的放在一个数据集里面然后让这个搜索算法去搜索得到波动结果。
那么别人可能会问了就是OK如果我们并没有把每一个那个architecture都做过evaluation我让它在空间中自由的探索是不是会更好的结果？答案当然是，但是也会有问题就是说用空间可能太大了可能效果不一定好啊。
但是呢我们会发现就是我们的方案呢其实用黑的来表示啊你会发现就是我们的方案在那个Cifar 10上呢它的Top 1 Error其实还是非常低的，而且我们用的那个搜索的次数可能就是八百次啊相对来其他其他的方案来说这数字是很小很小的嗯。
那么这是第一张表，那第二张表呢其实用了叫Win Shot。那么Win Shot的一些改进呢其实就是说我在采样每个样本点之后啊如果是用传统的方法呢这个样本点是一个神经网络那么这神经网络你需要通过训练然后得到它的那个最后的结果。
那么Win Shot的方法就是我用一个非常简单的一个直函数去代替这个训练过程，就直函数会给你一个比较差的但是还不错的估计。那么这估计呢你可以做很快的搜索，那么这种情况下你也可以得到一个还不错的效果。
那效果肯定没有原来的好但是啊效果也还是挺好啊而且还也会这样的话你可以节省大量GPU的时间啊然后我们可以发现就是用我们这个网络呢可以在那个ImageNet上做，然后你发现效果也还是不错的。
好，然后我们也可以拿这个算法呢用来做成为把它当成一个meta method啊前面因为我们说过是啊我们的每一个那个每个叶节点这个叶节点里面其实可以用任何的approximate的函数approximate来做函数的拟合啊我之前说过了我们可以用那比如说别的，我们可以用Gaussian process、我们可以用其他东西。
那么在里面你可以做一个就是你可以把一个任何一个solver套到里面去这个solver会告诉你最优解是在哪里啊。那么如果套上这个solver的话那我们想看到这个结果是不是更好啊？你会发现，就是我们的方法加上一个已有的solver在每一个节点上它的效果呢其实是高于这个solver。
本身的。啊，这是一个很有意思的一个现象啊，像比如说这边列举了两个啊人工的函数，这两个函数是比较复杂的啊，一个是叫阿克里，一个叫那个啊罗斯布洛克。阿克里呢，就是说有很多的local minimum，会发现这是二d的版本，它有很多很多的坑啊，如果使用传统的求解算法呢，它会掉在一个另外掉在任何一个坑里面啊，然后最优解呢，其实在零点附近啊，但就在零点上。
啊，你会发现就是说，呃，如果用我们的那个 A M C T S 的方法去做搜索的话呢，啊，我们的这个搜索效率呢其实是高于如果你只用，比如 Base Optimization，或者用最近的 Open 那边提出来那个 Tube，啊，所以我们的效率呢是比他们要高一点的。
啊，这是很有意思的一个现象。那么，特别是在高维空间，那么在高维空间呢，你会发现啊啊，我们这边这个曲线呢，啊，就那个实的曲线呢是啊，是我们用了这我们的方法，而那个虚线呢是没有用啊我们这方法。你发现就是特别在高维空间里面，这个实的曲线呢，它的掉的速度会更快，说明它的搜索效率更高。
啊，那么一在一百维的空间里面呢，你会发现就两根纯线呢是非常非常的啊短的短了一截，这是为什么呢？啊，主要问题是特别是在虚线的情况下呢，因为一百维空间你如果用啊base optimization呢，这个速度是非常慢的啊，所以啊，这是一个问题，然后就还要花很长时间才能把它跑出来。
但是同样的那个情况下呢，就会发现我们还是MPC加AI MPC加完之后呢，它的效果呢，它的降降下降速度还是比较快。呃，然后呢，我们也用这个方法呢，然后用它来做啊母周库的task啊。
那么这边呢，就是说母周库呢这边我们没有用这个gradient descent方法来做，我们就用的是啊，就是我们假设有个零点policy，这边policy的parameter呢是要通过黑盒优化优化出来的。啊，那么就是怎么样才能让它优化的更快，效率更高？
啊，那这个时候呢，就是我们没有用那个 reinforcement 那个方法，但是我们就把它当成一个黑盒函数来来做。啊，你会发现，就是说，特别是在高，特别是在高维的函数、高维的那个啊问题上，比如说 e e 和 f，一个是 ant，还有一个是那个 humanoid。
啊，这两个情况下呢，你会发现，就是啊，我们的算法呢，就是那个蓝线呢，其实效率要比啊其他方法呢要高很多很多。
啊，就是说，这说明就是我们的方法可能在高维空间里面呢，效果会比其他的黑盒优化的方法要好。啊，我们作为对比的那些函数呢，那那些方案呢，就是大部分呢就是属于在比如说进化算法啊这个框架里面，或者说传统的那个贝叶斯优化的一个框架。
啊，所以有很多函数是很很多的那个算法是作为baseline比较，啊，然后我们的方法呢相对来说跟感觉上还是不错的，就是主要是这些。
当然，如果那个我们真的跟那些基于梯度的方式来来做比较的话呢？啊，我们的方法可能不会特别的好，因为在梯度的在基于梯度的方案上，啊，在这个问题上呢其实基于梯度的方案会比较好。因为像母优过这个task呢，就是你用当前的梯度啊来计算它的下一步的那个优化的那个方向，这个效率是比较高的啊，而且是很快就能达到更好的结果啊。
但是我们对于这些，但我的方法相对来说是一个啊没有用梯度的方案，是一个那 gradient free 的啊一个 approach。所以呢，这边呢我们就跟啊所有的 gradient free 的其他的黑油优化方法进行比较。
OK，所以我们这边再说了一遍，就是我们的代码已经开源啊，然后呢我们希望大家嗯欢迎大家来过来使用啊。所以这个代码里面呢是包含了那个我们这边黑盒优化的算法，也包含了之前啊用它来做神经网络搜索啊这样的一个一个一个算法。
所以大家如果有兴趣的话呢可以欢迎大家使用啊一做啊王林南在这个问题上做了很多的时间，花很多大家时间去做这个事情啊。我们在此我感谢他的辛勤工作啊所以啊这就是我这次的讲的内容啊如果大家有问题呢可以给可以提出非常感谢大家。
youtube_search:yuandong OR TALKS 2020 youtube_search:yuandong OR TALKS 2020 youtube_search:yuandong OR TALKS 2020
昨天。呃，行可以可以啊我看到了我会回答一下这个问题嗯好这边有几个问题一个问题是那个请问好的结果和坏的结果的判断标准是什么？
这篇这篇这边判断标准呢其实有很多的criteria就一个简单的标准是一个神经网络训练的时候啊它的最后的训练结果它在测试集上的结果是什么那么这个标准是人定的啊是其实是独立于整个框架之外的就是说因为这个你可以定义比如说我们希望找到更优的啊神经网络它的效果是它的测试集效果是最好的啊这是一个。
然后第二个呢就是说我们可以说我们希望这个神经网络呢效果还不错但是呃但是呢我们希望这个神经网络大小啊比较小那么这样的话你这个判断标准呢就变成了就是呃也许你需要对每个部分加权对吧你希望这神经网络的效果很好还不错但同时呢要减去它的代价就是比如说神经网络非常大那么我也不喜欢所以这个呃判断标准是人可以预先设计的。
然后这个算法呢在这个判断判断标准的基础上去做啊去去去去去做那个训练的就是这样子一个一个问题啊。对，然后第二个问题是这种随机搜索会不会陷入局部最优的情况啊？
呃这个肯定是可能会出现的但是因为呃这边用了蒙特卡洛树树搜索所以呃局部最优的如果你训练足够长的时间或者说你进行足够多的那个搜索的话呢那个你总是会有机会跳出啊局部最优解然后得到最得到全局最优解。所以它有这个性质，当然了就是说所花的那个时间呢可能是比较大的啊是的对。
所以但具体的就是说你需要花多久？你需要花定量的或有个有没有一个算法复杂度？那么这部分呢现在还没有啊所以需要呃需要我们继续再做下去啊。所以这里面有没有一个比如说那个理论能够支持这个算法？这个是接下来想要做的一个一个方向啊。
好，下面一个问题是可以简单举例运用高斯过程吗？我不知道这个问题是什么意思啊不知道那个呃如果哪位是把问这个问题的你可以解释一下。
呃，下问题是应用在神经网络中是替代了梯度下降算法吗？哦答案不是的因为呃神经网络搜索呢是在梯度下降呃上面的啊一个啊一个更大的一个meta的一个算法。对，就是说我们希望不仅找到神经网络更优的参数而且呢我们希望找到神经网络的架构啊其实是这样子就是架构的搜索。
所以就是说给定架构之后呢你完全可以用梯度下降去跑它啊但是在梯度下降跑完之后或者说在梯度下降跑之前你是希望找到一个更优的啊神经网络的架构那么这个架构呢跟这个梯度下降呢是两回事情啊。
是，主要是这样子所以所谓的神经网络搜索呢是怎么去找更好的架构？那么这有了架构之后呢你完全可以用现在的那个训练算法去跑它啊。
好，下一个问题是在Go和Poker之类的game上有用吗？呃因为这两个游戏呢其实是已经是有了一个固定的系统空间的啊所以在这上面如果你要做这样的一个方案呢其实我觉得用处啊没有特别大啊因为就是这些action space这些行动空间呢他们在这几张游戏上已经定义下定义好了。
啊，当然了就是我怀疑也许是有用的就是因为人真正在下棋的时候或者是在做战略决策的时候呢其实还是会有个大致战略思路然后再把这这件事应用在具体的游戏的那个行动空间上啊。
呃，但是这个问题可能呃可能是本身是个研究的问题啊所以没有特别的清楚答案可能需要慢慢的去去想啊啊这是一个很大的问题。呃目前看起来我觉得还是用限额方法去跑 go 和 poke那么效果会更好一点啊。
后面是相比梯度方法，用梯度的优势是什么？啊那么一般来说呢有梯度总是更好的啊。一般来说有了梯度之后呢你总是可以跑更好更有效率的结果但是不用梯度的好处呢一个是也许它能够比有梯度的方法呢能够跳出啊 local minimum。
有梯度的问题是它局部很准对吧它可以很让很快让你到一个比较好的解但你并不知道这个解到底有没有效果啊也许这个解是个 local minimum 然后你又跳不出去。所以这种情况下呢你不用梯度呢也许你能够跳出 local minimum 啊这是第一个问题。
像我们最后那个母锥库的 task，那个task呢相对来说还是啊还是梯度的那个优势还是比较大的因为最后的那个解啊还是能够通过梯度找到的。但是对于其他一些tasks呢你所以你所以这个梯度本身呢就是可能是比较误导的啊这是其中一个。
然后第二个呢就是说有些呃目标函数是根本没有梯度的啊比如说目有些目标函数是啊你这个你这个呃调度函数跑调度程序跑一天得到一个啊比较好的那个值比如说你今天赚了多少钱啊有一个很大的系统这里系统里面你有很多参数要调啊这些参数你随便调一下得到个值今天赚了多少钱那明天又赚了多少钱？
但是你并不知道就是你赚钱跟嗯你里面每一个参数之间的梯度啊这个是很难算出来因为它只是个大R系统所以它不是一个数学上可以算的函数。那么在这种情况下呢你只能用gradient free的approach就是无梯度的方法来做。
而且这种情况其实在很多的应用场景中出现的次数还是很多非常常见啊所以这个是一个不用梯度方法的一个优势啊。
请问这个黑盒求解的源码直接调用吗？呃你可以看一下它的 README 然后你可以啊用这个方法去啊你可以看一下它怎么做的。其实这个思路很简单就是说你可以自己写一个简单的类，这个类就包括了就是一个简单的呃调用的那个接口啊。
就这个类可能就是说我有个函数这函数怎么定义的？给定这个函数的输入输出是什么？只要有这个之后呢就可以调用这个那个这个求解器啊是这样子。
呃，如何平衡求解精度和求解速度啊？就是这个就是说是如果你有很多的啊CPU有很多计算资源那比较好的地方是你这个算因为我们这个呃我们这个算法呢其实是叫Anytime Algorithm就是说你可以一直跑下去。
你可以跑到就是天荒地老如果你你想跑多久跑多久那么跑的越久它效果会越好啊其实是这样的一个算法因为整个门槛速搜索都是这样的一个算法所以这就是你可以啊通过速度和呃和那个和你的那个计算资源去呃去给你的精度交换。
好像这个算法有什么样的应用场景？因为它是一个黑盒优化算法所以它应用场景还是比较多的只要是有黑盒优化的那个背景的问题就是有一个黑盒的函数这个函数调这函数花很多时间然后你要求这函数最优解那只要是有这样的应用场景呢应该就可以使用啊。
SVM的kernel如何定义，是不是通用的？啊对这边我们用的还是比较简单的Kernel应该是高线Kernel吧。嗯你可以用别的Kernel来做这个，这个是个一个参数可以调的啊。
这个应该是只要不要找一些非常奇葩的Kernel应该是可以work嗯BO不支持高维是因为里面选择GPR嘛？对啊。
对，就只要是不它不是高维的原因呢是因为它的它必须它作为高它是高斯ian process所以高斯ian process呢就是说它把所有点放在一起认为它们满足一个联合高斯分布。
啊，然后用这个呢去算出来每一个点的后验这后验的那个均值呢就是你预测出来的那个啊y，预测出来你你的那个函数的值啊。所以但是你这个高多元高分布它的协方差矩阵呢是啊跟你的那个数那个跟你的那个点的数目的乘平方关系的啊。
所以呃如果高维维数越大的话呢那你的那计算代价就越大这是一个问题啊。然后第二个问题就是维数灾难的问题，就是如果你需要那个拟合一个高维函数那这高维函数需要啊其实原则上你需要指数个点才能把它拟合的很准啊所以这是一个很大的问题。
这个问题更肯定更加更加 fundamental 啊，架构是表示神经元数量、层数吗？或者说是全连接层啊？对对，架构其实是表它其实是一个非常广义的概念它可以表示任何东西就是神经网的神经元的任何架构任何的那个那个 hyperparameter 任何超超参数都可以啊对。
如x高维是怎么办？呃就是这跟输入这是呃这个怎么回答？呃就说是你其实是这样就是你的神经元呃x高维的话那就意味着呃你的那个神经网络的第一层的。
呃，第一层的那个输入层的那个大小也是很大的对吗？啊或者说是你用卷积的话那第一层的输入大小跟你的神经元的那个数目是是不一，是是是是是是脱钩的那就没有关系。呃这个是另外一个问题。
请问每一次训练都是需要很多trial吗？呃我不知道你在说不知道你想问什么我们跳过这个问题。
Tubal为什么可以支持高级数据优化啊？这个问题很好。Tubal呢它是这样子，呃它可以是相当于在BO的外面呢加了一层这层是说我同时优化很多的小的区域。
然后每每次优化只优每每次在优化小区的时候把这小区变小一倍然后再在一个更小区里面再去优化。那么这样的话呢其实它没有啊它在细化优化的时候呢啊它是把这个整个区域的大小变小了啊。
那这样的话呢其实它其实是就是它做了一项 trade off，它选择了这个区域然后在这区里面做继续的优化而不是把很大的一个区域一起做优化那么这样的话它的效率会变高。
啊，它是这样但这样它有个牺牲点这牺牲点就是说有些区域它一开始放弃了它以后再也不会回来了。
可以再解释一下怎么和 Tube 求解使用吗？这个你可以看代码，代码里面有写。啊对就是Tube其实是就是放在那个LMC TS里面的啊是相当于 Tube 用来做局部的一个求解器。
然后我们的那个整个算法呢是个大的框架，然后这个框架里面调用它局部求解器可以得到一个啊更好的呃结果啊这样子。
呃，这个框架下与梯度方向怎么结合啊？先探索空间然后再使用梯度吗？这可以啊你可以先探索空间得到一个大致的解然后从这解出发你可以跑梯度这个没问题可以做。
另外，它是白 noise 情况下表现如何啊？这个我没有试过哦你可以试一下嗯对不是特别清楚会怎么样这可能跟你的核函数的选择有关系啊。
行，那基本上是这些还有什么问题吗？好如果没有的话那就结束吧嗯会非常欢迎非常感谢大家的参与。
youtube_search:yuandong OR TALKS 2020 youtube_search:yuandong OR TALKS 2020 youtube_search:yuandong OR TALKS 2020 youtube_search:yuandong OR TALKS 2020 youtube_search:yuandong OR TALKS 2020 youtube_search:yuandong OR TALKS 2020