超越AB-Test，算法参数化与Google实验架构

更多！更好！更快！是不是很像更高更快更强的奥运会箴言？而这个，却是用来描述一项浩大的技术工程的箴言。这个技术工程，就是google的实验架构。要知道，google工程师文化的一个很值得骄傲的特点就是：所有产品及算法功能的修改的决策都是以数据为基础，谁说了都不算，数据说了算。从这个角度来看，这套东西对于google的价值一点都不逊色于广为人知的google三驾马车。

关于对比实验，你很容易会想到A-B测试，实际上这个领域还有很多被广为研究的构型，如单层的实验架构，多因素架构，还有本文要讲的google多层混叠实验架构。以下讲述的内容多来自于这篇文章《Overlapping Experiment Infrastructure: More, Better, Faster Experimentation》，但有所省略，也有所扩展。

算法的参数化与最优化

因为拥有在学术界混迹的那几年经验，我不知觉地把google这套利用实验来达到目标利益最大化的方法归纳为一种新型的用户驱动的最优化方法，即把算法的优化工作由原来的机器驱动转化为用户驱动。第一步，把算法参数化；第二步，为算法构造参数空间，明确优化目的；第三步，利用算法实验架构，在参数空间中搜索以得到最优化的参数设置。一改以往的诸如梯度下降、牛顿法、共轭梯度等等机器驱动型的工程最优化方法。

原来google的实验架构

Google的系统更新包括代码更新与数据更新两部分，代码更新是定期进行的（如一周一次），而数据更新则相对频繁得多。这里的数据更新实际上是系统的参数更新，每个系统总有一套默认参数。但总有这样的一套机制，对新的参数进行实验测试、评估，如果能得到比原来更好的结果，则把它们作为新的系统默认值上线（通常是逐步灰度上线）。而这套机制，就是google的实验架构。

Google原来的实验架构是模块化、单层实验架构，属于独占型的，一个请求只能做一个实验。优点是可以分治优化各个模块，不同的实验也可在不同的模块内部完成，功能解耦。缺点：截流与有偏。所谓截流，即上流模块占用了过多的资源，导致下游模块的实验无法完成，处于长期的等待与饥饿状态。如UI展示模块处于搜索排序模块的下游，如果排序模块占用了太多的请求用于实验，UI的实验就无法进行。而所谓有偏，考虑这样的一种情况，如果上游模块需要使用来自中国的访问请求来做实验，那么留给下游可用的就只剩下非中国的请求了，这样得到的实验结果必定是有偏的。

多层混叠实验架构

正因为原来的架构存在着诸多问题，在google需要做的实验越来越多，实验资源越显不足，冲突越来越严重时，多层混叠实验架构出现了。

图1、关于多层混叠实验架构的几个例子

图1是关于多层混叠实验架构的几个例子，结合着下面的概念介绍应该很好懂。

概念介绍：

Domain：流量的子集，图中的白底框。
Layer：参数的子集，图中灰色框部分，包含在domain中，但layer也可以包含另一个domain。
Experiment：包含在layer中的实验，利用流量的子集在参数的子集上进行的实验。

流量分配函数：

因为要把流量无偏地分割给不同的实验，所以就有了流量分配函数。有四种流量分配函数，user_id mods，cookies mods，cookie-day mods，以及random。Random就是随机分配，很简单，这里单说cookies mods，因为剩下的两种其实与之类似。常用的一种做法是把用户cookie转换为一个数字，对其取模，Experiment就可以指定取哪个模的流量作为训练样本。可以把这个模的表达式为f(cookie) % 1000，意为把流量分割为1000块。更合理的表达式为f(cookie, layer) % 1000，这个式子与之前的式子不同之处在于把layer也作为变量引入进来，这样可以保证layer之间的实验是独立的。考虑取第一个式子的情况，如果layer1的实验E11，取mod=1的流量，layer2的实验E21也取mod=1的流量，则这两个实验是相关的。所以如果要保证layer间实验的独立性，使用第二个式子即可保证同一个访问在不同层的模不会完全一样。

要决定一个访问是否能用于一个实验，除了分配函数，还有另一个因素：condition。这个因素引入了比“模”这种随机标识更为丰富的访问本身的特性，如访问来自的国别、语言、浏览器等等，以便于定制更为有针对性的实验。如果还需要更为细致的访问定义，则可由trigger这个东西来完成，但因为这方面的特征过于复杂，所以它是定义在实验内部的，并不在流量分发阶段完成判断。

图2、实验流程图

图2是google基于多层混叠架构实现的整套实验流程，结合着上面的图与内容应该也比较好懂，如果不太好理解可以阅读一下原文。我的感觉是一套优雅的架构，它的本质都是简单的，也即是说它有可能会生长得很茂盛很复杂，但其基本的构件以及生长规则都是简单的，就是搭积木一般。这也是我进行架构设计的一个主要原则：简单够用、一致，这样的架构就是优雅的。

论文中除了介绍技术，还有与这些技术相关的google内部的配套措施，如实验交流社区、实验效果仲裁专家等等，充满了工程师文化的意味。最后不能免俗，介绍成功经验的同时把这些成功综述为更多（可以同时进行更多实验）、更好（实验出错率降低）、更快（更快地得到实验结果及结论）三个方面。

这篇论文最初是从canbian同学的一篇豆瓣日记（好像删了，无法得到回链）中得知的，一直没有时间看，直到去年年底才仔细地阅读了一番，感觉启发良多，就记录下来。

关于作者

阿稳, 豆瓣, 算法工程师

推荐系统；数据挖掘；算法架构及实现的可扩展性；R环境编程

如果你的问题已经能从我的博客中得到解答，就最好不过了：