阿里新一代自动出价算法--Bid Optimization by Multivariable Control 超详细笔记
为何字节、阿里这些大公司纷纷推出这种新的出价产品？
今天解读阿里2019年的Bid Optimizaiton by Multivariable Control in Display Advertising 论文。
阿里的售卖机制从最早的cpm、cpc出价发展到ocpm、ocpc出价，做到区分PV价值，差异化出价；再发展到BCB、MCB，广告主不用设定出价，转为设置如预算或者 cpc 等任意后验指标的约束，进一步贴近了广告主考核需求。
本文分为如下三部分，从涉及到的背景知识开始，逐步解读mcb。
- RTB 生态环境
- PID 控制算法
- 阿里MCB出价
RTB生态环境
术语解释：
- DSP：Demand-Side Platform，需求方平台。为广告主或代理商提供实时竞价的投放平台。
- ADX：Ad-Exchange，广告交易市场。ADX的作用是组织竞价，撮合交易。Ad Exchange像股票交易市场一样，联系着广告交易的买方和卖方，也就是DSP平台和媒体流量方。
- RTB：Real Time Bidding，实时竞价。RTB 是指用户在访问媒体产生曝光机会时，众多家DSP根据曝光的上下文以及用户属性实时地评估曝光价值并给出报价，在ADX中竞价后最终出价最高的广告主赢得此次曝光机会。
下图描述了一个曝光从发生到实时竞标，直到最后获胜广告展示的全过程：
1) 用户（user）向媒体（publisher）发起访问请求
2) 产生广告请求时，媒体将携带用户标识（一般是cookie或设备号）的流量发送到Tencent AdExchange
3) Tencent AdExchange 向众多家 DSP 并行发起曝光竞标请求
4) DSP进行估值后决定是否参与出价并给出此次曝光的报价，Tencent AdExchange 集齐DSP报价返回后进行拍卖
5) Tencent AdExchange按照媒体广告模板进行样式渲染后，将获胜DSP的广告返回给用户展示
6) 用户浏览页面，看到广告，广告产生曝光
PID控制算法
PID(proportion比例 integration积分 differentiation微分) 是在工业界常用的控制算法，小到控制一个元件的温度，大到控制无人机的飞行姿态和飞行速度等等，都可以使用PID控制。
PID 是指可选比例，积分，微分三项作为控制信号，控制信号作为执行机构的输入，执行机构会影响系统状态。通常设置一个系统中的观测对象和对应的期望值，调控的目标就是使观测对象趋向于期望值，即将error e(t) 调控到0。
术语解释：
- r(t) : set point, 设定值
- y(t) : measure value, 系统中的观测变量
- e(t) : t时刻系统的error，代表系统中的观测变量与要求的设定值之间的差距。通常e(t) = y(t) - r(t) 或者 e(t) = y(t)/r(t) - 1
- u(t): 控制信号，执行器的输入
- Kp,Ki,Kd：比例，积分，微分三项各自的超参系数
- x(t): 系统的输入，即后面介绍的p,q
MCB中“问题定义”
在ocpc/ocpm 产品中需要广告主对于点击/曝光 有一个出价，这个值其实是广告主通过一段时间内在平台的收益推算出的在计费点的成本。
MCB出价产品则不需要广告主设定出价，省去了广告主推算的过程，只需要广告主设定总体预算和cpc 的成本约束（其实可以支持任意后验指标的约束设定）。
MCB是DSP站在广告主立场上的出价策略，目标是在预算和一些KPI指标的约束下带来最多的转化，即下面的LP1。
变量解释
- wpi: wining price, 当广告主的出价高于wpi则赢得该次曝光机会，并且在二价计费机制下会根据wpi 进行计费。
- xi：代表是否赢得该次展现，取值是0或者1
- B: 广告主的预算限制
- C: 广告主的CPC约束
注意下图的公式5中的分母，将CPC中的真实点击替换成了点击率，论文中说做如此替换方便后续推导。
问题求解
问题LP1是一个带约束的线性规划问题，论文中转化为对偶问题求解。线性规划问题可用互补松弛定理在已知对偶问题最优解时求原问题最优解，或者在已知问题最优解下求对偶问题最优解。
将LP1转换成对偶问题，然后用互补松弛定理求解对偶问题比较复杂，笔者在这里换个解法，改用拉格朗日乘子法求解LP1。
- 将LP1的求最大问题，加一个负号，从而将LP1转换为求最小问题 LP2
2. 加入拉格朗日算子p,q ，可写出其拉格朗日函数为（先忽略x的约束）:
其中p>=0, q>=0.
3. 由于约束公式4和5， 拉格朗日公式中的红框两部分都是小于0, 所以
所以LP2 转换为LP3：
4. 根据对偶问题和KKT条件，min max 问题可以转换为max min 问题，即LP3转换为LP4：
对里面的min 问题求偏导，极值点处偏导为0，可得：
求解之后得到论文中的bid公式：
因此换算到对于点击出价的c_bid:
超参分析
c_bid公式中的拉格朗日因子p,q 分别影响哪些因素呢？
- 参数p 用来控制预算的使用
下面中的实线是用来观察随着p变化（固定q），相比于基础虚线的变化。c_bid函数一定过（-q*C,0）这个点，随着 p 的减小，出价的直线的斜率逐渐增大，表示对于同一个横坐标值，纵坐标出价更高，同时消耗的 budget 也会更多; 当p 无限大时，直线完全跟横坐标重叠，c_bid 出价一直为0，预算不会再增加。
- 参数q用来控制cpc成本
下面中的实线是用来观察随着q变化（固定p），相比于基础虚线的变化。随着 q 的增大，出价的直线的斜率逐渐减小，c_bid 在C之下的流量出价相比变高，即会赢得更多的cpc低于C的流量，更加严格控制了cpc成本。
Model Predictive PID 控制器
通过上面的分析可知，参数 p 是被用来控制预算的使用，而参数 q 则是被用来控制点击成本。一种最简单的策略是用两个独立的 PID 来分别调控变量 p 和 q，调控的目标则是预算和点击成本。如下图所示，p和q的调控是独立的。
实质上 p,q 并不是完全独立的，比如说为了保点击成本进行提价或降价也会影响到预算的使用，反之亦然。因此两个完全独立的 PID 并不是最优的选择, 而是在控制中要考虑两个变量相互的影响。
MPC(model predict control) 专门去预测和抵消这种互相影响，但是建模复杂的RTB 环境是非常困难的，所以并没有应用MPC，而是通过两个线性回归模型直接建模变量 p、q 和目标 cost、CPC 的关系。
上图中的公式 16 里的 X 和 b 分别表示 2×2 的矩阵和 2×1 的矩阵，如果展开后其实就是两个线性回归模型。
公式 19 则是 paper 中提出的新调控方式。公式18中的Δcost 、 ΔCPC 分别通过 up(t)、uq(t) 量化; 同时只用两个变量 α 和 β 来近似矩阵 X 的逆。注意公式19中的u′p(t)、u′q(t)并不是指 up(t)、uq(t)的导数，而是定义出来的新调控信号变量。论文称做这些近似操作的好处是使得控制器更加鲁棒，而其中α 和 β 是从训练集中通过grid-search 找到最优值。
现在来审视一下 p、q 的新control signal u′p(t)、u′q(t)，发现两者p和q的调控并不是独立的了，而是up(t)、uq(t) 的线性组合，考虑了互相影响的因素。
下图描述是公式19表达的Model Predictive PID 控制器。经过Model Predictive Module 模块建模了p和q的相互影响，产生了新的控制信号。
实验细节
论文中并没有进行在线实验，而是通过离线方式进行评估。
采用的数据集是淘宝 40 个计划总共 20M 条 bid log，每条 bid log 的关键信息是wpi、CTR、CVR；同时根据时间划分了训练集和测试集。
传统的 PID 中所有的 error 的权值都是一样的，而论文中 PID 使用click(t)对 error 进行了加权，click(t) 代表这个小时的点击量，通过如此修改，PID 控制器持续关注累计cpc。
除了对 error 进行加权，上面的公式20 也很有特点，就是每次通过 control signal 调整系统输入时，不是基于上一次的值x(t)，而是基于最开始的值 x(0)，具体原因可能与具体业务相关，论文也没有详细说明。
此外，调价的频率是每小时调整一次，PID 中涉及的超参(kp、ki、kd)以及公式19中的 α 和 β 都是在训练集中通过 grid search 得到的。
因此，总体的实验步骤如下：
(1) 基于训练数据集计算出最优的 p 、q 作为其初始值
(2) 在测试数据集上用上面的最优出价公式和调价策略进行模拟竞价
(3）当计划的 budget 消耗完或者所有的日志回放完成则终止
结论
论文最重要的贡献是提供了一种多变量约束下的调价范式，虽然论文中只给出了预算和cpc的约束，但是我们可以根据真实业务需求，增加任意的后验考核指标约束。
更新：
讲解原文中用到的 对偶问题 和 互补松弛定理 的两个数学定理：
参考
[1]. https://dl.acm.org/doi/pdf/10.1145/3292500.3330681
[2]. https://www.ichdata.com/docs/programmatic-advertising/chap3/rtb
[3]. https://zhuanlan.zhihu.com/p/367610355
[4]. https://wulc.me/2020/07/19/%E3%80%8ABid%20Optimization%20by%20Multivariable%20Control%20in%20Display%20Advertising%E3%80%8B%E9%98%85%E8%AF%BB%E7%AC%94%E8%AE%B0/
首发于公众号“眼罩的世界”
总结真心不易，点个赞同 留个❤️
文章被以下专栏收录
