图论在计算广告中的应用

2016年11月19日 | By News | Filed in: 未分类.

Source: http://zhuanlan.zhihu.com/p/23562855?utm_campaign=rss&utm_medium=rss&utm_source=rss&utm_content=title

背景是这样的,我们是一家初创 DSP 公司,然后在接入腾讯 Ad Exchange 的时候,腾讯抛给我们了这么一个限制:一次广告请求中可能含有多个广告位,但我们不能拿相同广告主的广告进行重复竞价。举个例子来说,假如一次请求中含有 A、B、C 三个广告位,我们手头有 a、b、c、d 四个广告主的广告可供参与竞价,假使我们拿广告主 a 的广告去参与广告位 A 的竞价,那就不能拿 a 去参与 B 和 C 的竞价了。

好了,那作为公司的商业智能,我们要面对的问题就是,在这个约束下,如何使我们投放广告的利润最大化?这篇专栏文章即是这个问题的最优解决方案。

如果我们不考虑这个约束,那么我们可以利用最简单的公式来求得期望:

eCPM = pCTR \times CPC

其中 CPC 是由广告主在后台设定的,pCTR 是由统计模型预测的点击率,那么 eCPM 即为本次投放的期望价值,不熟悉计算广告名词的可以自行百度一下。如果以传统策略来说,对于每一个广告位,我们都是返回 eCPM 最高的那个广告进行竞价,辅以平滑预算模型即可最大化我们和广告主的利润。但如果增加了上述约束的话,就没那么简单了,假如a、b、c、d对A、B、C的 eCPM 如下(Slot是广告位,Ad是广告,值就表示价值):

如果我们用暴力的方法来解决的话,那么我们需要进行A_{4}^{3} 次选择,可见计算复杂度是阶乘级别的,随着广告主或者广告位数量的增加,要求100ms内响应请求就变得不那么实际。

那如果我们仍以之前贪心的策略来呢?这样我们可能会选取到如下结果:

即从广告位A开始挑最大的,再B,再C,那么价值和为12。但实际上,我们可以获取更大价值:

在这种选取方式下,价值和为14。如果运气好,我们以C->B->A的方式来做贪心,还是可以找到最优解的。那么我们可以从任一一个广告位出发,枚举完所有路径做一遍贪心策略,复杂度仍然是阶乘级别的(Slot全排列个数 * Ad个数)。

如果你有图论基础的话,这个表格应该一眼就能看出来,其本质上是一个邻接矩阵,那我们就可以把它给画出来,边上是有权值的,表示的就是广告位和广告主之间的价值:

画得比较粗糙,手工PS绘制,红色描边的就是我们要的最优解。搞过 ACM 竞赛或者熟悉图论的同学应该一眼就能看出这是一个「二分图」了,并且我们的目标是二分图的最大权值匹配

——————————–

在聊最大权值匹配之前,我们要先认识什么是「二分图匹配」,以及如何去做权值相等的最大二分匹配,在这之后我们才能更深入理解这个问题,去解决带权值的最大匹配问题。

二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交集 U 和 V ,使得每一条边都分别连接 U 、 V 中的顶点。如果存在这样的划分,则此图为一个二分图。二分图的一个等价定义是:不含有「含奇数条边的环」的图。

最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。

完美匹配
:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。图 4 是一个完美匹配。显然,完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突)。但并非每个图都存在完美匹配。

举一个更简单的例子,下图中的边表示男生和女生彼此喜欢,问最多能有多少配对?这就是一个经典的求无权二分图最大匹配问题。

这时候,有一个来自匈牙利的数学家 Edmonds 跳出来了说他可以解决这个问题,所以就有了一个「匈牙利算法」(为什么不叫 Edmonds 算法?),这个算法的核心是不断去寻找增广路径,在介绍这个算法前,还有两个概念需要知道:

交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…… 形成的路径叫交替路。

增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。

以上图为例,我们可以找到这么一条增广路,其中 1->6 和 4->8 是已匹配的边:

那么「匈牙利算法」其实就很简单了,就是不断找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到最大匹配(增广路定理)

所以我们可以简洁地用 DFS 或者 BFS 来实现这个过程,代码就不贴了,如果有兴趣夯实这一基础,可以移步:程序员必须掌握哪些算法? – SimonS 的回答 寻找 OJ 上对应的题。

——————————–

接下来我们就要面对本次的大BOSS了,即解决带权值的最大二分图匹配。这里要亮相的人物是 Kuhn-Munkres,他在「匈牙利算法」的基础上发明了「 KM 算法」,高效解决了带权值的问题,但是!为什么他就能以自己名字命名算法了……(黑人问号)

接下来的算法过程描述可能会比较复杂,我会尽可能用简单的语言来讲。想当年搞OI的时候听高三NOI保送的金牌大牛给我们上这个课,我刚听完的时候也是一脸懵逼。

「KM 算法」中引入了一个「顶标」的概念,其实就是给每个顶点加了一个标记位。我们设顶点X_{i} 的标记为A_{i} ,设顶点Y_{i} 的标记为B_{i} ,顶点X_{i} Y_{j} 之间的边权为W_{ij} ,很显然,对于任何边(i,j),总有A_{i} + B_{j} \geq W_{ij}。这里还有两个较为隐晦的概念:

相等子图:设G(V,E)为二部图, G'(V,E')为二部图的子图。如果对于G'中的任何边(i,j)满足L(x)+L(y)=W_{xy} ,我们称G'(V,E')G(V,E)的等价子图或相等子图(是 G 的生成子图)。

完备匹配:设G(V_{1},V_{2}, E)为二部图,|V_{1}|\leq |V_{2}|MG中一个最大匹配,且|M|=|V_{1}|,则称MV_{1}V_{2}的完备匹配。

如果你第一次可以无压力看懂上述两个概念,那说明你天赋比我高,我至少来回读了三四遍。最后,祭出「KM算法」的核心定理:

若二分图中的相等子图有完备匹配,那么这个完备匹配就是二分图的最大权匹配。

证明放到后面再讲,我们先理解了以上几个概念之后,「KM算法」按以下步骤执行,即可找到最大权匹配:

  1. 初始化采用贪心策略,设A_{i} 为与X_{i} 相连的最大边权,B_{i} 为 0;
  2. 利用「匈牙利算法」找到一个完备匹配M
  3. 如果M不存在,则修改顶标值,增加一些边;
  4. 重复第二步和第三步,直到找到完备匹配即为最大权匹配。

第三步展开来是这样的,从第一个节点开始扫描,如果有合法的增广路,那么将其反选,扩充路径;如果该节点没有合法的增广路,那么则将增广路上的所有A上的点加入点集S,将B上的所有点加入点集T,从S和不在T集合中的点里面,通过以下公式得到一个delta

delta = min\left\{ L(x)+L(y)-W_{xy}  \right\} (x\in S,y\in T)

计算后,将在S点集内的A的顶标减delta,在T点集的B的顶标加delta:

L(v) = L(v) - delta (v\in S)
L(v)=L(v)+delta(v\in T)

并且,将目前没有加入二分图的权值和等于顶标和的边作为未匹配边加入到二分图中,然后再在该节点寻找增广路。如果还是没有,则再次通过更改顶标来增加边,直到有增广路出现为止。之后重复寻找增广路的步骤以及更改顶标的步骤,直到出现完备匹配。

最后再做一个微小的证明工作:

M是相等子图G'的完备匹配,则M也是G的完备匹配,有:

W(M)=\sum_{e\in M}^{}{W(e)}=\sum_{v\in V(G)}^{}{L(v)}

M'G的任意一个匹配,则:

W(M')=\sum_{e\in M'}^{}{W(e)}\leq \sum_{v\in V(G)}^{}{L(v)}

可见M就是该二分图的最大权匹配。

——————————–

最后感叹一下,即使过了这么多年,仍然感激通过 ACM 竞赛带给我的知识。顺带一提,用传统的网络流也可以解决这一类问题,只不过感受上没有那么优雅。大致思路如下:

  1. X 集合连源点,边权为 1,花费 0;
  2. Y 集合连汇点,边权为 1,花费 0;
  3. X 连 Y 中任意元素,边权为 1,花费为权值的相反数;
  4. 最后得到的最小费用就是最大权匹配。

这个就不作证明了,读者可以自己思考。

下一期打算聊聊特征工程在传统计算广告点击率预测实现中的一些细节。

这个公式输入真的好累……

——————————–

参考阅读:

来源:知乎 www.zhihu.com

作者:SimonS

【知乎日报】千万用户的选择,做朋友圈里的新鲜事分享大牛。
点击下载


Comments are closed here.