作者: 沈慧

目前，许多WEB应用通过广告而维持生计，从在线广告中获益最多的是搜索应用，“adwords”模型就是一种用于搜索查询和广告匹配的模型。这一章介绍了在线广告的相关问题、在线算法、Adwords实现和问题等，具体框架如下图1所示。

图1  Web广告主要框架图

一、在线广告相关问题

1、当前WEB广告机会：网站上的展示广告、在线上商店自主选择的广告、搜索广告。

2、直投广告，通过应答查询词项时展示或者通过查询者查询广告具体参数来查询。采用“最近最优”策略，并度量广告的吸引力。

3、定向广告可能会引起隐私问题，但是WEB上可以通过用户信息来制作定向广告确实是一种比较高效的广告方式。

二、在线算法

1、离线算法：将算法所需的所有数据准备好才产生答案的传统算法。

在线算法：只能保存有限的流数据，但是需要在某个流元素到达之后就以输出的方式对查询进行应答，此时是在对未来的数据一无所知的情况下对当前元素进行决策的过程。

2、一般情况下会寻找搜索引擎收益和广告上显示次数同时的最大化，因为无法保证在线算法与离线算法一样有效。

3 贪心算法：采用贪心策略，综合考虑关键词与广告的匹配程度、广告商竞价、广告商剩余预算等因素，通过最大化当前输入元素信息的某个函数得到当前的最优值。

4 竞争率：存在某个小于1的常数c,使得对于任意输入，一个具体的在线算法的结果至少是最优离线算法结果的c倍。

三、广告的匹配问题

1、二部图：设G=(V,E）是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B），并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二分图。

2、最大匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，选择这样的边数最大的子集称为图的最大匹配问题。

3、完美匹配：在一个匹配中，所有的节点都不会同时是两条或者多条边对的端点且所有的节点都出现，则匹配是完美的。

4、最大匹配的贪心算法：按照任意次序来考虑边，当考虑边（x,y）时，如果x和y都不是已有匹配中边的端点则加入，否则跳过。贪心算法产生的匹配不一定是最大匹配，很可能结果会不尽人意。

5、贪心匹配算法的竞争率为1/2。因为算法的竞争率是算法所有可能的输入下所得到最小值和最优结果的比值，因此1/2是竞争率的上界。又设Mo是最大匹配、Mg是贪心算法匹配，L为在Mo中匹配但在Mg中不匹配的左节点结合，R为L中所有节点连接的边右节点的集合。由于|M0|<=|M0|+|L| ,|L|<=|R|，|R|<=|Mg| ，可以推导得到|M0|<=2|Mg|，竞争率至少为1/2。因此竞争率为1/2。

四、Adwords问题

1、Adwords问题定义：

给定信息为：广告商为搜索查询设定的投标价格集合；每个广告商-查询对所对应的点击率；每个广告的预算；每个搜索查询所显示的广告数目上限。每一个搜索查询后，得到的结果：

（1） 结果集合大小不超过每条查询显示广告数的上限

（2） 集合中每个广告商对于本条搜索的出价

（3） 每个广告商必须剩余足够的预算为广告的点击付费。

这样，一次广告选择的收益为：每个选出的广告的价值之和，其中每条广告的价值等于对应查询的出价和广告点击率的乘积。

2、简化后的Adwords问题：

（1）   每条查询只显示一个广告

（2）   所有广告商的预算都相等

（3）   所有广告的点击率都相等

（4）   所有的出价不是0就是1

简化后的Adwords问题可以通过贪心算法,促使搜索引擎将广告分配给对查询投标并有剩余预算的广告商。竞争率1为1/2。

3、Balance算法：是对贪心算法的改进。它将查询分配给出价最高且剩余预算最多的广告商，若多个广告商的剩余预算相等，则随机选择一个。如果只有两个广告商，竞争率正好为3/4，广告商增多时，竞争率可以达到1-1/e 约为63%。

4、Balance算法竞争率的下界：

按照书中例8.8，分类讨论在最优算法中分配给A1的查询在Balance算法中的分配情况，可以证明， Balance算法的竞争率就是3/4。

5、多投标者的Balance算法：

Balance最差的情况：

（1）有N个广告商A1、A2...An；

（2）每个广告商的预算为B=N!.

（3）有N个查询q1、q2...qn；

（4）广告商 Ai只为 q1、q2...qi出价，而不对其他查询出价。

（5）查询序列包括N轮，第i轮有查询 qi的B次构成。

最优算法的收益为NB。

Balance算法会优先考虑剩余预算最高的广告商，将第一轮每个查询等分为N分，第二轮等分为N-1分，在第i轮中，到会各自得到B/(N-i)个查询。最终最低轮次j=N(1-1/e)时，分配更多的广告商预算会被花光。Balance的收益近似为 BN(1-1/e)，竞争率为(1-1/e)。

6、一般性的Balance算法

当现实中出价和预算为任意值，出价大小的权重难以设立。会在选择时倾向于出价高的广告，并对剩余预算处理更加人性，并倾向于广告商的部分预算，使得任意广告商的预算不会剩余太多。设 Ai预算中的节余比例为fi,将广告分配给 φi=Xi(1-e^(-fi))最大的广告商。 （这边看了还是有点糊涂，和他们再讨论讨论）。

五、Adwords实现

1、投标和搜索查询的匹配:将投标关键词集合按照词典顺序排列,并建立投标哈希表值.同样地,搜索查询也对词排序并映射为哈希值,找到匹配的投标。另外，由于内存的限制，全部的哈希表中的桶分割到几台机器。当搜索查询的到达速度过快时，查询流会分割为多段，每一段交给一组机器来处理。

2、较为复杂的匹配：当投标关键词和投标完全一致时，匹配较为简单。现实中，常常需要用投标和更大的文档匹配，比如邮件和推文。此时的匹配法则是：若投标集合的所有词都出现在文档中，不管词语是否与投标中同序，也不管是否相邻，都认为投标和文档匹配。

3、文档与投标之间的匹配算法：

首先要将投标按照低频优先的方式排序成词语表，并且每个词语列表都会有一个状态信息用以存储列表中从头开始和当前文档已经匹配的词语数目。

然后将投标将存放在哈希表中，其中哈希键是投标按照词频逆序方式得到的第一个关键词。另外还有一张哈希表，保存已经部分匹配的投标的副本。

文档中的词按照低频优先的方式处理。只有投标在其最低频词出现在文档时才会复制到第二个哈希表中，这样可以大大地减少哈希表的大小。