《大数据》 第八章 Web广告的二分图匹配 adwords问题 Balance算法

1.Web广告

Web广告可定制的特性可以利用用户的信息来确定应该对用户显示哪些广告，而不管他们在浏览哪个网页。相较于传统媒体介质的广告Web广告确实存在许多优势，Web广告在保证用户范围更广的情况下，还能够根据用户信息定制广告 ，提高广告投放的准确度，但是Web广告的精准性也意味着其在展示的时候也会面临许多问题：
 1.广告的排序问题
 2.过度相似广告的处理问题
 3.广告与查询词项匹配度的问题
 4.广告的展示机会问题
以上并非所有内容都会在本章中被提及，本章主要关注广告与搜索查询关键词的匹配问题(二分图匹配)以及针对关键词如何选择广告商的问题(adwords问题)。
 

2.Web广告的二分图匹配

在介绍Web广告二分图匹配之前需要先了解几个相关的基本概念

2.1离线算法

算法先获取到完整的数据再进行数据的处理，同时算法可以以任意顺序访问数据。
 

2.2在线算法

算法一次只能接收一个或者一批输入，这意味着我们必须在对未来一无所知时对当前每个元素进行决策，同时在此过程中做出的决定不可撤销，其形式比较类似于数据流模型。
 

2.3竞争率(Competitive Ratio)

$c=\frac{当前最小化在线算法}{最优离线算法}$ $(0<c<1)$
最优离线算法的概念相对容易理解，即离线算法中可以达到最好效果的算法，针对离线算法当然也可以采用贪心等思想来解决，但是贪心往往不能在离线处理的过程中达到时空的最优。
当前最小化在线算法指的是，使用的在线算法的最坏可能，比如贪心算法往往被认为不是最优的，同时贪心算法根据初始化不同可能产生不同的结果，假设使用某种贪心算法作为在线算法，则最小化的在线算法就是指贪心算法中最坏的情况，这一点在2.4章节中会有例子。
 

2.4Web广告的二分图匹配

我们可以将广告与搜索查询的匹配问题可以抽象简化为二分图匹配问题，假设我们已知广告商与搜索关键字之间的关系如下：{(1,a), (1,c), (2,b), (3,b), (3,d), (4,a)}

在讨论二分图匹配的在线算法之前，我们首先对于几个概念有以下定义：
匹配：一个由边构成的子集。
完美匹配：如果对于上述这些边而言满足，1.任何一个节点都不会同时是两条或多条边的端点。2.所有的节点都出现在这个匹配中。可以称这个匹配是完美匹配，但是需要注意的是，当且仅当左集合和右集合中的节点个数一样时才可能出现完美匹配。图示的完美匹配集合为：{(1,c), (2,b), (3,d), (4,a)}
最大匹配：所有匹配中最大的匹配，所有完美匹配都是最大匹配。
最大匹配贪心算法：按照任意但确定的次序来考虑边。当考虑边(x,y)时，如果x和y都不是已有匹配中边的端点，则将其加入，否则跳过。
对于图例中，假定按照节点的词典顺序贪心，最终选出的序列为{(1, a),(2, b),(3, d)}，显然非最大匹配。
 

2.5二分图匹配贪心算法的竞争率

2.5.1上界的证明

如果贪心算法以{(1,a), (3,b)}开始贪心，则后续没有任何边可以加入集合，此时竞争率为2/4，且找不到比此种顺序更差的贪心顺序。
由于算法的竞争率是算法在所有可能的输入下所得到的最小值和最优结果的比值，因此我们知道1/2是竞争率的上界。
 

2.5.2下界的证明

对二分图有以下定义：
1.$M_g$为贪心算法得到的匹配
2.$M_o$ 为贪心算法得到的匹配
3.L为是在$M_o$ 中匹配但在$M_g$ 中不匹配的左节点集合
4.R是L中所有节点所连接的边的右节点的集合
 
则有断言，R中的每个节点在$M_g$中都有匹配，证明方法如下(用反证法可以证明结论)：
假设不成立，即R中存在某个节点r在$M_g$中没有匹配。那么贪心算法最终会考虑某条边(I, r) ，其中来l属于L。此时，由于我们假定不论是l还是r都没被贪心算法所匹配，因此这条边的两个端点都不在已有匹配中，该结果与贪心算法的流程定义相矛盾。
 
根据上述的假设与推论我们可以得到一些结论：
1.在所有的左节点中，只有L中的节点才在$M_o$ 而不是$M_g$ 中找到匹配,因此有：
|$M_o$ | <= |$M_g$| +| L |
2.因为在$M_o$ 中， L 中的所有节点都能找到匹配，因此有：
| L | <= | R |
3.R 中的所有节点在M_g中都能找到匹配，因此有：
| R | <= |$M_g$|
由(2)(3)得到| L |<=|$M_g$|，又由(1)知|$M_o$ |<=2*|$M_g$|,因此竞争率c>=1/2，c的下界为1/2。
又因为上界也是1/2，所以贪心算法的c=1/2。
 

3.adwords问题

3.1 adwords问题的定义

给定下列信息：
1.一组广告商对搜索查询的出价。
2.每个广告商—查询对的点击率。
3.每个广告客户的预算（比如 1 个月）。
4.每个搜索查询显示的广告数量限制。

对每个搜索查询，算法会给出一系列广告商的应答结果集合：
1.集合的大小不大于每次查询的广告数量限制。
2.每个广告商对搜索查询都有出价。
3.如果广告被点击，每个广告商都有足够的预算来支付广告费用。
 

3.2 简化adwords问题的解决方案

在实际应用中的adwords问题会非常复杂，这里将adwords进行简化，暂时忽略广告的点击率，广告商出价不同等因素的影响，以较为简化的一个形式来解决adwords问题，简化如下：
1.每个查询显示 1 个广告
2.所有广告客户的预算相同，都设为B
3.所有广告被点击的可能性相同
4.每个广告的价值相同都设为1

3.2.1 简化adwords问题的贪心解决

此时解决简化adwords问题的最直接方法是贪心：对每条搜索查询，贪心算法会选择出价为1的广告商。
对于adwords的贪心算法，思路非常简单，那么接下来需要计算贪心算法的竞争率，则应求出最坏贪心与最优离线的结果：
对于广告商 A 和 B，有以下场景：
A对查询x投标，A的预算为2
B对查询x与y投标，B的预算为2
假设当月的搜索序列为: x x y y
最坏贪心策略: B B _ _
最优离线策略: A A B B
c <= 1/2
由此可得c<=1/2，同理根据二分图匹配的贪心算法的推导，可知c>=1/2，所以c=1/2
 

3.2.2 简化adwords问题的Balance算法解决

Balance算法是对贪心算法的一种改进。Balance算法核心思想是，将查询分配给出价最高且剩余预算最多的广告商。如果多个广告商的剩余预算相等，那么就随意地选择其中一个。

3.2.2.1 Balance算法的上界证明

对于广告商 A 和 B:
A对查询x投标，A的预算为2
B对查询x与y投标，B的预算为2
假设当月的搜索序列为: x x y y
Balance算法: B A B _ 或者 A B B _
最优离线策略: A A B B
c <= 3/4

3.2.2.2 Balance算法的下界证明

假设有两个广告商$A_1$和$A_2$，预算都是B。假定每个查询都会按照最优算法的结果分配给相应的广告商。再假定两个广告商的预算都被最优算法花光。否则，我们可以降低预算。则对于最优离线算法，我们可以画出示意图如下，注意此时分配给$A_1$和$A_2$的查询的颜色。

因为在最优离线算法下，我们有$A_1$和$A_2$的均等分配，所以易得：Balance算法必须用尽至少一位广告商的预算。否则，我们就在二者都还有预算的情况下，对某次查询没有进行分配。

此时根据Balance算法我们可以做出分配图如下：

显然，如上论证，Balance算法必须用尽至少一位广告商的预算。否则，我们就在二者都还有预算的情况下，对某次查询没有进行分配，与最优算法中每次查询都至少有一位广告商出价相互矛盾。
因此，假设$A_2$已经被分配了B个查询，这些查询在最优算法下不一定全部属于原来的$A_2$。同时令$A_1$被分配到的总数为y，x=B-y代表在Balance算法中未被分配的查询。
此时计算Balance算法的下界，目标就转化为了证明：y>=x，则可以保证c>=3/4

Balance算法的分配在此时可以分为两种情况，这取决于是否有更多在最优算法中分配给$A_1$的查询会在Balance算法中分配给$A_1$或者$A_2$

情况一：假设这些查询中至少有一半会被Balance算法分配给$A_1$
此时显然有y>=B/2(如红框所示)，所以y>=x必然成立

情况二：假设这些查询中有一半多会被Balance算法分配给$A_2$
考虑这些查询中的后部分查询q被Balance算法分配给$A_2$ (如红框所示)，此时，$A_2$剩余的预算至少和$A_1$一样多，否则的话，Balance算法会像最优算法一样将q分配给$A_1$。又知道当这部分被分配时，$A_2$的剩余预算少于B/2。因此，此时$A_1$的剩余预算也会少于B/2。所以我们知道x<B/2，于是因为x+y=B，所以y>x

综上所述，c=3/4
 

3.3 多广告商的Balance算法

针对一个简化的adwords问题，我们计算出c=3/4。此时我们将adwords的一个条件还原，即广告商数量增加不再限制为两个广告商，此时c会下降，但是仍然存在下界，针对Balance算法，我们可以得到算法最差情况如下：
N 个广告商: $A_1$, $A_2$, … $A_n$ ，每个广告商预算B相等且大于 N
查询： 一共N轮，每一轮都有B个查询
针对每轮查询投标的具体情况如下:
第1轮投标 : $A_1$, $A_2$, … $A_n$
第2轮投标 : $A_2$, … $A_n$
第i轮投标 : $A_i$, … $A_n$
最优离线算法:
将第i轮查询分配给$A_i$
最终收益为N*B

而根据Balance算法，第i轮投标将被均匀分配给$A_i$, … $A_n$ 的所有广告商
则对于$A_n$ 来说投标到第k轮时，有 $S_n={\sum }_k^{i=1}\frac{B}{N-(i-1))}$
如果我们找到最小的k使得$S_n$>=B，那么经过k轮后就不能将任何查询分配给任何广告商

根据欧拉证明: $H_n={\sum }_n^{i=1}\frac{1}{i}\approx ln(n)$ (当n较大时成立)

由$S_k$=1 可知: $H_N$−k=ln⁡(N)−1=ln⁡(N/e)…(1)
同时由公式可知: $H_N$−k=ln⁡(N−k)…(2)
联立(1)(2)得: N−k=N/e
因此有: k=N(1−1/e) ，所以c=1−1/e
 

3.4 更一般的Balance算法

前面的算法都建立在广告商出价非0即1的情况，当出价有差别时，Balance无法对所有出价大小设置合理的权重。
例如广告商$A_1$与$A_2$对查询q同时出价：
$A_1$出价为1, 预算为110
$A_2$出价为10,预算为100
假设当月的搜索序列为: q q q q q
最优离线：$A_2$ $A_2$ $A_2$ $A_2$ $A_2$
Balance算法：$A_1$ $A_1$ $A_1$ $A_1$ $A_1$
显然Balance算法效果很差，可以考虑以下更改，在选择时，我们必须要倾向于出价高的广告。考虑剩余的预算比例而非考虑剩余预算的大小，这样我们就倾向于使用每个广告商的部分预算。

针对当前查询q，每一个广告商 $A_i$有以下定义：
出价 = $x_i$
预算 = $b_i$
广告商i的目前花费 = $m_i$
预算剩余比例 $f_i$ = 1-$m_i$/$b_i$
定义 ${\psi }_i(q)=x_i(1-e^{-f_i})$

当前查询q最终分配给${\psi }_i(q)$ 最大的广告商。进一步推广，考虑不同广告的点击率不同这种可能性，在计算${\psi }_i(q)$ 时将出价和点击率相乘，最终使该预期收益最大化。
当然在实际中还必须要考虑查询的历史频率，如果已知Ai的预算足够小，当月后续查询保证满足Ai的需要，那么如果某些广告商Ai的费用已经花光时提高${\psi }_i(q)$ 就毫无意义。也就是说，只要我们可以预计本月当中将有足够的查询给Ai以花光其全部预算，那么就可以维持${\psi }_i(q)=x_i(1-e^{-1})$。
 

3.5 投标与搜索查询的匹配

实际中广告商会对关键词集合投标。如果某个搜索查询正好是关键词集合的某个次序组合结果，那么就认为该投标和查询匹配而成为一个候选结果。则我们需要针对投标关键词的集合以及搜索查询进行数据处理以提高匹配的速度：
1.所有投标关键词的集合，可以按照词典顺序排列通过哈希表索引构建投标的哈希值。
2.搜索查询在哈希表中查找之前也对词进行排序。将排序后的查询词语映射成哈希值，然后在哈希表中找出所有和这些词语完全匹配的投标。由于只需要检查一个桶的内容，所以上述检索过程会非常快。
 

3.6 文档与投标之间的匹配

更加贴近实际情况的是多个投标(较小的词语集合)与多个文档(更大的词语集合)之间的匹配，此时需要将投标表示成某种排序下的词语表，同时表中加入两类信息：
1.对每个词语列表都有一个状态信息。该信息用整数表示，指出列表中从头开始巳经和当前文档匹配上的词语数目。当投标存储在索引中时，其状态值永远为0
2.由于词序只可能是词典顺序，我们可以按照低频优先的方式对词语排序来减少工作量。

以本书的英语原名为例“Mining of Massive Datasets” ：
“of”出现频率最高，“Massive”次之，“Datasets”与“Mining”都为低频但是“Datasets”相对更多。
于是整个文档按照逆序排序后得到“Mining Datasets Massive of”
投标存放在哈希表中，其中哈希键是投标按照上述次序的第一个关键词，投标对应的记录也包括当投标匹配之后要做的信息。若状态为0, 则不需要显式存储，还有一张哈希表，其任务是保存那些已经部分匹配的投标的副本。这些投标的状态至少是1，但是不高于集合中的词汇个数。如果状态是i， 那么该哈希表的哈希键是第(i+1)个词。

对于整个匹配过程有详细叙述如下：
(1)将文档中的词按照频率逆序排序，同时去掉重复词。
(2) 对排序列表中的每个词w, 进行如下操作。
( a ) 在部分匹配哈希表中使用w作为哈希键，查找以w为键的投标。
( b ) 对( a )中查找到的每个投标b, 如果w是b中最后的那个词，则将b移到已匹配投标表中。
( c )若w不是b中最后的那个词，则对b的状态值加1， 并利用比新状态值大1的位置上对应的词作为哈希键重新对b进行哈希处理。
( d ) 利用w作为所有投标表的哈希键，找到排序后第一个词为w的投标。
( e ) 对(d)中每个投标b, 如果在列表中仅有一个词，那么将它复制到已匹配投标中。
( f ) 如果b由不止一个词构成，则将它以状态1加到部分匹配投标表中，并使用b中的第二个词作为哈希键。
(3) 将已匹配投标表作为结果输出。

 

4 小结

4.1 在线算法，离线算法，贪心算法

在线算法一般不如离线算法优秀，最小化在线算法与最优离线算法的比值c被称为竞争率(0<c<1)。
在线算法一般都是贪心算法或者经过优化的贪心算法，贪心的每一步都根据最大化或者最小化某目标函数进行。
二部图匹配的在线算法竞争率为1/2，其核心思想就是对当前没有出现在匹配集合$M_g$中的端点贪心。

4.2 adwords问题与Balance算法

adwords问题的目标是最大化搜索引擎的收益。
adwords问题的贪心解决方案竞争率可以证明为1/2。
使用Balance算法解决adwords问题，在所有广告商预算相同的前提下，仅有两个广告商时竞争率为3/4，有多个广告商时，竞争率会趋近于1-1/e。
更一般化的adwords问题要求广告商的出价不同、预算不同且不同查询的点击率不同。 根据 ${\psi }_i(q)=x_i(1-e^{-f_i})$，取最大${\psi }_i(q)$的广告商。