极往知来，运筹帷幄–腾讯OMG的合约广告大脑揭秘

序言问题描述

二部图左侧表示库存，即供给结点；右侧表示订单，即需求结点。若某个供给结点满足某个需求结点的受众定向约束时，我们用两个结点之间的连线来表示定向符合关系。供给结点可以是一个曝光、一个用户或者一个流量单元，上图采用

si

表示供给结点能够提供的曝光数；相似地，

dj

表示需求结点所需的曝光总量。

xij

表示了第

i

个供给结点能够提供给第

j

个需求结点的曝光数或曝光占比；若第

i

个供给结点与第

j

个需求结点定向关系不成立，即两者之间不存在连线时，可以认为

xij=

。

基本思路

数据采集与管理

数据分析与预测

针对供给结点，机器学习算法能从数据中寻求规律与知识（例如时间序列的周期性、不同定向库存的关联性），准确预估未来若干天库存（PV）以及人群分布（UV）；针对需求结点，挖掘订单的价格、定向特征，并考虑订单随时间的增减，预测价格与需求量的分布。供给结点的预测数据可用于支撑分配算法的建立，而需求结点的预测数据更进一步支持全局收益的最优规划。

决策建模与求解

建模与求解

决策优化的数学建模是通过解一个优化问题，得到最优解，使得目标函数在约束条件下最优。其核心为两大要素：

约束条件

目标函数

si

：第

i

个供给结点的库存

dj

：第

j

个需求结点的需求

xij

：第

i

个供给结点提供给第

j

个需求结点的曝光占比

Γ(i)

：第

i

个供给结点连接的订单，即库存

i

匹配的订单集合

Γ(j)

：第

j

个需求结点连接的库存，即订单

j

定向的库存集合

fij

：第

j

个订单在第

i

个库存上的播放限制，可用于表示频次控制（如某个订单最多投放N次给任意UV）

pj

：第

j

个订单的单位曝光价值

cij

：第

j

个订单在第

i

个库存上的点击率

约束1：需求约束，即订单投放量小于等于需求量

Σi∈Γ(j)si∗xij≤dj

约束2：供给约束，即库存供给占比小于等于100%

Σj∈Γ(i)xij≤1

约束3：频控约束，即每个库存供给占比小于频控限制的要求

xij≤fij

约束4：非负约束，即变量的物理意义不能等于0

xij,uj≥

如上所述，约束条件由分配问题的基础约束和业务系统的附加约束构成。基础约束是相对固定不变的，因此可以直接建模为数学问题求解；然而，附加约束随着媒体的业务发展需要支持快速上线与修改，不适合作为模型约束条件，而适合在基础约束之上利用启发式的规则求解。

目标1：订单投放量最大

maxΣj∈JΣi∈Γ(j)si∗xij

目标2：全局收入最大

maxΣj∈Jpj∗Σi∈Γ(j)si∗xij

目标3：全局点击数（效果）最大

maxΣj∈JΣi∈Γ(j)si∗xij∗cij

已知约束条件与目标函数便能推导出这个问题的数学模型，但是实际问题依然有几大问题亟须解决：

库存的时序变化：一方面，近两年在线视频蓬勃发展，用户量、观看视频数量稳定增长；另一方面，人的观看行为产生视频观看量，因此必然导致库存服从自然人的作息的周期特征，如观看量工作日少于非工作日，平时少于节假日、寒暑假等。

不同维度库存的相关性：库存可以依据用户信息（如性别、年龄）、上下文（如频道、剧目）等特征划分为不同的流量单元。由于特征的内在相关性，不同流量单元将展现出非常强的相关性。例如上海的男性库存和北京的男性库存可能会呈现出非常相似的涨跌趋势。

其他非时间、空间分布的特征：例如，大剧首播可能会导致频道的库存分布变化，九三阅兵等突发事件会产生库存暴涨，甚至节假日天气是晴是雨也与库存涨跌具备一定的相关性。

其三，在保证约束条件与第一目标的基础上，提升第二目标则主要有两个步骤构成：1）用户、上下文、广告关联度的建立，通常高关联度的场景意味着更高的点击、更好的转化；2）第二目标的局部优化算法建模。首先，建立关联度需要深入挖掘用户、上下文、广告的特征。从用户的角度讲，根据用户基础属性、历史观看兴趣等能够建立较好的人群特征；从上下文的角度讲，信息流通过自然语言处理挖掘广告插入位置附近的文章关键字、主题等特征，视频一来通过媒资信息挖掘剧目、演员等特征，二来通过图像识别、分割技术获得视频播放进度的图像特征；从广告的角度讲，广告主行业、素材文字图片等可作为特征。然后，建立衡量用户、上下文、广告关联度高低的预测模型，并以此于依据影响选单逻辑。例如通过在线实时动态匹配与反馈的方式贪心地优化第二目标，抑或利用列生成之类的离线运筹优化算法来计算满足约束条件与第一目标最优的情况下第二目标的局部最优解。

系统架构

综合考虑数学方法、工程架构等因素，我们设计了如下图所示的系统架构。整个系统由若干个子模块组成，主要模块有：

数据平台：负责海量、异构数据的离线与实时采集与存储。

库存预估：挖掘历史曝光数据的时序关联、空间分布等特征，精准预估未来近半年的库存。

价格模型：依据历史曝光与订单价格，预估未来需求量-价格的分布。

特征挖掘：从订单、上下文、用户等三个角度挖掘特征，建立关联度预估模型。

分配引擎：基于库存预估的分配引擎能够满足订单保量的基本目标（第一目标）；基于库存预估、价格模型的分配引擎既保证任意时刻的优化目标，也能给出考虑未来需求的下单建议（第二目标）；在此基础之上融入特征挖掘的分配引擎能够针对广告效果进一步优化（第三目标）。

售卖系统 & 投放系统：两个系统结合各自不同的业务侧重点调用分配引擎对外提供服务。售卖系统主要解决任意时刻给定一组订单定向决策当前可供售卖的最大库存；投放系统主要解决任意实时针对一个曝光求解应当播放的具体订单。

结语