推荐系统时代前沿（10）：探微参数&性能关系，把模糊的点 ...

JoshWindsor · 发表于 2022-4-23 16:03

Saying

1. CEM，遗传算法，粒子群算法都属于“点”方法，贝叶斯优化属于“面”方法
2. 看到“贝叶斯”这几个字可以自动替换成“先验”“后验”两个词，贝叶斯优化中，每一步都可区分反馈前的先验分布和反馈后的后验分布

本篇是【从零单排推荐系统】系列的第37讲。除了CEM和强化学习以外，在参数搜索这件事情本身上还有更多技术点，本讲先介绍基于点的其他方法如遗传算法，粒子群算法等（不要担心，这些算法都很好懂，但是后面的贝叶斯优化不容易懂），然后介绍如何建模参数与性能的函数关系（重点）。
有一套搜参的算法是遗传算法，遗传算法的核心思想是模拟基因重组变异过程+环境淘汰。假设我们把每一组参数都能表示成一个0-1的字符串，那么遗传算法的操作过程是：

生存模拟，得到当前所有点的性能，按照某个比例淘汰最差的那一部分
基因重组，选择一些“父母”，用0-1字符串表示他们，并从某个地方分开，两边互换，生成新的个体，把新的个体加入到族群中。比如父母分别是010000和100010，从中间位置分开，产出的个体就是010010和100000
基因变异，以某个概率在字符串中将0-1互换
重复上面的1-3直到生成的后代与父代不再有显著差异，算法视为收敛。

就拿多任务融合权重这件事来说，目前还没有看到遗传算法应用的例子。原因有两点，其一是淘汰的太慢了，我们调参的时候每一个参数要占据一组流量，很多在尝试的流量桶都是在承受损失，好的点如果不尽快出现时是很致命的，这也是CEM相比遗传算法的很大优势，出现了好的点，下一次迭代所有的点都会向它靠近。其二是常见的遗传算法需要把参数编码到二进制字符串上，但是在多任务融合这里都是浮点数，我想了想也没想到很好的办法能完成这个转换。
第二种拾遗的算法是粒子群算法，这种算法参考了鸟类的行为。每个鸟在自己找吃的的过程中，还会不停地看其他鸟什么情况。如果看到其他鸟找到大量食物就赶紧靠过去。把鸟抽象成一个个粒子，他们当前的策略就分成两部分，一部分是自己的搜索，称为自身认知项，一部分是观测其他粒子得到的参考，称为群体认知项。除此之外，还有自己之前经验的记忆项。设想每个粒子在移动时都有速度，它可以表示为

$v_i=wv_i+c_1rand()(pbest_i-x_i)+c_2rand()(gbest_i-x_i)$
这里的 $v$ 表示速度， $w$ 表示惯性，表示当前位置。pbest是自己历史中发现的最好位置，gbest是所有粒子中发现的最好位置， $c_1c_2$ 是两个系数。公式中的三个部分分别对应记忆项，自身认知项和群体认知项。粒子群算法的操作流程是：

从当前粒子中淘汰差的一批
按照当前表现，更新每个粒子的pbest和所有粒子的gbest
按照上面的公式更新粒子的速度
重复1-3直至收敛

相比遗传算法，粒子群算法具有“所有点及早向最优值靠近”的性质，它是可以用在多任务参数融合这个场景下的。
<hr/>上面的算法都是“基于点”的，某几个点的性能怎么样，然后我要如何迁移到下一个点上去。这样的认知还不够全面，有没有办法把参数和性能直接挂钩，建模一个函数的关系，从而知道整个“面”上的性能表现呢？这就是建模一个随机函数了，需要请出无数人上学时候的噩梦——随机过程。我们这里来介绍一个高斯过程+贝叶斯优化搜参的方法。
首先要区分搜参的过程。把所有参数空间均匀分，打成网格是一种搜法（grid search）；先随机选点，再调整也是一种方法（CEM以及上面介绍的其他方法），而贝叶斯优化搜参就是另一种，不停调整函数估计来选取下一个要探索的点。看到贝叶斯这几个字，就知道和先验后验概率脱不了关系。一句话概括，就是“我有一个先验分布，根据它选参数探索，观察到结果后调整后验分布，再从校正的分布里面选下一轮参数”。每一步执行之前我们对函数的认知都是先验分布，然后在这个分布上找出最好的点，拿去试，得到一个新性能。然后这个点的性能要反过来帮助我们修正分布，这时候就是后验分布。什么时候是先验后验也不重要，我们总是不停地在修正认知而已。
在上述过程中需要两个工具：（1）一个拟合函数的工具或者模型，称为替代模型；（2）下一轮要搜索的点的选择方法，会有一个采集函数，这个函数最大值对应的位置是下一个要采集的点。
为帮助理解，这里举一个一维的随机函数做例子的示意图可视化一下贝叶斯优化是在做什么：

如图是第一次迭代的时候。红色虚线是真正的函数形式，蓝色部分是我们目前预估的结果，其中实线是均值，背后的阴影是这里可能的浮动范围即方差。因为某种准则，选择了0.2附近这个点作为第一个探索点。拿这个点去验证，我们知道了这个点对应的性能是-0.2左右这样，此处的性能已经确定，因此方差会在这里缩到0（即图上蓝色背影缩到这一个点上）。由于目前对其他点没有任何知识，预估的函数是一条直线。下图的acquisition function是采集函数，由于0.2附近这个点已经探索过，没有采集的价值，这里就掉下去了。从采集函数上判断，下一个采集点应取在1.0附近（这里先忽略采集函数如何得到，下面会讲）。

接下来是第二次迭代，采集了1.0附近的点，得到它的性能是-0.6，我们就更新了预估函数形式和采集函数形式。注意到现在已经有两个点方差缩小到一个点上了，蓝色阴影变成了纺锤形。这时候可以继续在采集函数中选择最大值，在0.4附近

随着迭代的进行，函数形式会越来越接近真实结果，最终拿到全局中比较好的位置。

至此我们就弄明白贝叶斯优化在干啥了，接下来就看具体的替代模型和采集函数怎么做。这里的替代模型，不再是一个普通函数，而是具有随机性的。之前的CEM，每套参数是一个点，它的性能是一个随机变量，但现在我们要建模参数和性能之间存的函数映射，就是一个随机的函数了，也就是随机过程。最典型也最好用的随机过程是高斯过程，它假设任意一个点处的随机变量符合高斯分布，变量之间的联合分布也符合高斯分布。协方差矩阵可以写为

$[k(x_i,x_j)]_{ij}$
（公式编辑矩阵不太方便，这里把所有的ij展开到一个矩阵里），k是核函数，一般来说是个距离的度量，越接近，核函数值越大。这其实隐含了一个假设：距离接近的两个参数在性能上也是接近的。只要函数的形状不要长得太别扭，这个假设就可以接受。但要注意区分，高斯过程没有假设函数的形式，不要误解为函数的形式是高斯的！高斯过程最大的优点是它的先验后验分布都是高斯的，并且能较为简便的推导出来。这个推导过程非常长且复杂，读者可以参考https://app.yinxiang.com/fx/ddc8c1bb-c95c-41b3-a751-b5f3311b8bf7 ，重点是结论，使用高斯过程的过程是：

之前探索过的点记为 $x_i$ ， $i=1,2...K$ 。新的要探索的点是 $x’$ ，根据 $x'$ 和之前点的距离关系算出协方差矩阵新加的行列；
套上面文章中的公式，计算出对于新的点的均值方差的预估

所以到这里我们把什么高斯过程，贝叶斯优化等等名词都抛掉再看，这个算法很符合拍脑袋的直觉：在已有点的基础上，新的点是与已有点距离有关的性能的插值。这一套算法有概率上的各种考虑，但本质无外乎是这样。
那么采集函数，也就是选择点的时候以什么原则呢？一个常用的准则是期望提升函数（Expected Improvement）， $E(max(f(x)-f(x^*)),0)$ ，其中 $x^*$ 是之前性能最好的点，也就是哪个点比起上一次有最大的提升就选择那个点。以第三次迭代的结果为例，当前最优的点是下图中的红点，

选取下一个点时，每个坐标应当把这条线上面的部分取出来积分，看谁最大。利用高斯过程得到均值和方差之后，就可以很方便地带入求解某个点的期望提升有多大，然后选取最好的那个。除了EI之外，还可以有更简单的做法，比如按照均值+1倍方差最大的来选，那么采集函数就等于图中的阴影上边界。

下期预告

推荐系统时代前沿（11）：为什么要探索和利用？

		自动登录	找回密码
密码			立即注册

推荐系统时代前沿（10）：探微参数&性能关系，把模糊的点 ...

本帖子中包含更多资源