搜索引擎利用IR的方法对于一个特定的query检索出该关键词上的出价广告后,就需要对SERP页面上的广告栏分配给出价的广告主,牵扯到搜索广告的排序问题。一般共识是左侧的广告位(即搜索结果页上面的广告位)被看到和点击到的可能性最大,后侧的则按照从高到底排序,越靠上的广告位越好。简单的说就是谁出钱多谁得到的位置越好,复杂的研究这里面牵扯到博弈论之类的问题,假设存在n个对该关键词出价的广告主,k个广告位,每个广告主衡量自己想得到的广告位的价值,并根据他人的出价(有可能是透明,有可能不透明)来决定自己的出价,从而达到自己的宣传效果,同时又想尽可能的减少广告的CPC,而广告竞价又是一个不断变化的过程,如何达到某种相对的均衡状态。

常用竞拍模式

  • First-Price Sealed-bid:一次性竞价,所有人同时出价,出价最高者获得物品,并支付他的出价。
  • Second-Price Sealed-bid:出价方式同上,不同的是实际的支付价格是第二高的竞价。Vickrey拍卖。
  • Open Ascending-bid:最常见的竞价方法,轮流喊,谁喊的最高谁拿,支付他的出价。称为英式拍卖。
  • Open Descending-bid:荷式拍卖,拍卖人从高到低不断的减少定价,第一个能接受价格的人获得物品。

搜索广告的拍卖

Generailized Frist-Price Auction(GFP):第一代拍卖方式,由Overtune.com提出,按照广告主的出价高低对广告进行排名,也引入了CPC机制,使得Overtune.com获得了巨大的成功并成为Yahoo和MSN的SE提供服务。GFP的结果是出价十分不稳定,动态的环境中每个广告主都会不断的调整自己的出价,希望尽可能的降低CPC,获得更高的回报。例如由两个广告位,分别吸引到200个Click和100个Click,之前的出价分别为4$和2$,但可能会不断的调整,调整到2$和2.01$。此时有可能广告主希望获得第一个广告位,出价2.02$,就这样不断的递增,然后递增到一定阈值后,索性放弃,又降到最低的2$,再一次竞价,该过程甚至可以由robot来完成,如下图。

image

Generailized Second-Price Auction(GSP):Google与2002年实现,即每个广告主获得第i个位置实际支付的CPC由第i-1高的支付价决定,可能会略高一点(0.01$),随后Overtune和Yahoo也采用了GSP这种方式,对广告主出价博弈更加友好。GSP的方式一般分为两种

  1. Bid Ranking:按照广告的出价排序,位于第i位的广告的实际CPC为第i+1位的出价,如下图5个广告主在las vagas travel关键词上出价,有4个广告位:               image
  2. Revenue Ranking:按照实际的收益排序,此类排名考虑了每个广告的质量评分,即每个广告的CTR(表示的是广告与query的相关度,广告本身质量等,与位置无关的CTR), 这样可以避免用户看到一些无关的、比较粗糙的广告会对搜索引擎本身产生反感。位置i上的广告主实际支付价格为 bid(i+1)*ctr(i+1)/ctr(i),如果自身广告的质量评分远高于低一位的广告,则可以获得更低的支付价格。image

迄今为止,使用最广告的竞价是GSP,该模型简单有效,也容易向客户进行解释,同时采用广告评分机制,能激励广告商尽可能的优化自己的广告,良好的广告信息对搜索引擎是有益的,对用户是友好的。此外,Vickery-Clark-Groves(VCG)拍卖也会在各个广告拍卖模型中被提起,VCG模型是一次性的对k个物品,n个竞拍者进行拍卖的过程,每一个竞拍者的实际出价由该竞拍者参与后对系统中其他竞拍者带来的损失决定。假设有两个广告位点击率分别为200和100,三个竞价者出价分别为$10,$4,$2。按照VCG模型,获得第二个广告位的人应该支付的价格为$2*100=$200,即因为他的参与,使得出价$2的参与者失去了第二个广告位,系统损失为$200。而第一个广告位获得者的支付价格为$600=$400+$200,$200是由于他的参与使得第三个竞拍者未获得广告位,而$400=$4*100,即他的参与使得出价$4的竞价者失去了以$4的CPC点击100次的广告效应。VCG的计算过程和讲解过程都很复杂,还没找到确切的文档资料说某个搜索引擎完全采用了VCG,有一些猜测G可能换了VCG。

VCG最主要的特性是truth-telling的占优策略,即如何所有的竞价者都真实的评估自己所想要得到的广告位价值,并按照此标准出价。而对于GSP动态中的均衡,Edelman引入了一种Locally envy free equilibrium,是纳什均衡的一种特例,在这种均衡状态下,每一个广告主都无法通过和自己前一位的广告交换出价交换位置得到更高的payoff。(payoff = c(i) * [v(i) – p(i)], c(i)是第i个位置的点击率,v(i)是广告主对第i位的真实估算价值,p(i)是实际的CPC)。

实际上搜索广告的排序除了出价以及广告质量外,还可能受其他各种各样的因素的影响,包括用户的地域、广告主的余额,以及广告主设定的策略等。

参考资料

Internet Advertising and the Generalized Second Price Auction, Edelman

,

搜索引擎的检索结果页下方一般会提示多个相似的搜索关键词,这些词可以被看作查询关键词query的rewriting。在计算广告中,当某一个query没有对应的bid phase出价广告,或者该query对应的bid phase较少的时候,可以利用query rewriting获取相似query对应的广告进行显示,以期望获得更多的click。相似query的确定可以利用用户session中的搜索关键词上下文,但此方法需要确定query的边界,例如用户搜索过程中可能会突然跳到一个完全不相干的搜索,然后又跳回来。或者利用传统的文本相似度匹配,而由于query一般都很短,传统相似度匹配的语料也不足。

image

Simrank

Simrank算法是一种用于衡量结构上下文中个体相似度的方法,直观上的含义是利用已有个体的相似度来推算其他与有关联个体的相似度。形式化的定义如下:

有向图G={V,E}中,节点a的入边集合记为I(a),而出边集合记为O(a),则两个节点a,b(a != b时)相似度s(a,b)按照如下公式计算,其含义是个体a,b的相似度取决于所有与a,b相连节点的相似度,s(a,b)∈[0,1];当a=b时,s(a,b)=1;如果a != b,且只有同一个入节点c,我们不希望从c计算得到的s(a,b)也为1,因此c做为衰减因子,取值是[0,1],即s(a,b) = C。

image

对于二分图G’ = (V1,V2,E),对于任意的(A,a)∈E,有A∈V1和a∈V2,则所有V1集合中的节点相似度按照出度O(A)计算。V2集合中的节点相似度则按照上述公式,利用入度I(a)计算。

image

在搜索广告中,把query和ad看作节点,当用户搜索某个查询关键词q时,点击了广告a,则建立q至a的一条边,这样构成一个由query和ad组成的二分图G=(V,E),其中V=Vq∪Va,任何边e=(q,a,w),q∈Vq并且a∈Va,可以利用simrank算法来求query之间的相似度。E(q)表示q的边,N(q)表示E(q)的个数:

image

按照上述算法,我们看以下的例子,假设C等于0.8,则利用上述公式计算出的sim(pc,camera)的相似度在前5次迭代中都大于sim(camera,digital camera),但从直观上说,由于camera和digital camera的共同邻居较多,应该具备更高的相似度,而simrank的结果是反直观的。针对上述问题,Antonellis等人在VLDB 08上提出了Simrank在计算广告方面的改进——Simrank++。

image

阅读全文…

, ,

简介

计算广告学于2008年由Yahoo Research的A.Broder提出,详细的定义参看百度百科,广义的定义是通过科学计算来选择最优的广告投放,主要研究的是互联网上的广告投放,其中典型的是在搜索引擎上查询关键词结果页出现的“推广链接”。

计算广告(或者说互联网广告)相比于传统的媒体广告的优势在于以下几点:

  1. 投放的介质范围更广。传统的媒体广告一般只有相对较少的场合,例如报纸、杂志、电视、影院、路边广告牌,而互联网上除了大流量网页的banner等,搜索引擎上的一个词语就是一个投放介质。
  2. 广告价格差距。cctv1的广告价格表,稍微像样的时段,30秒的广告都在10万人民币以上,就不提春晚这种露个脸就要上千万的地了。
  3. 个性化。互联网广告可以根据人查询的关键字、Location以及个人信息等进行较为精确的投放。
  4. 衡量投资回报率(ROI)。传统广告很难去衡量这个东西。

目标:

Find the “best match” between a given user in a given context and a suitable adverstiment.

互联网广告常用的付费方式有如下类型

  • CPM(Cost Per Thousand Impressions),按照展示次数付费,主要用于一些图形广告和首页banner。
  • CPC(Cost Per Click),按点击付费,搜索引擎的关键词广告常用付费方式。
  • CPT/CPA(Cost Per Transcation/Action),针对达到成功的营销效果的事务进行付费,例如购物类网站、酒店机票订购,用户消费后像广告投放商进行付费。
  • 此外还有淘宝等国内网站的一种CPT(Cost Per Time),即时间计费,可以包月包日。

计算广告学主要研究的是文本类广告(Textual Ads),文本类广告的投放主要分为两种,由搜索关键词驱动的广告投放和由页面内容决定的广告投放,即Google大名鼎鼎的Adwords和Adsense。当然随着社交网络和SNS的发展,还会出现基于人际关系以及人的特性、行为的”Ad Profile”,例如之前某Boss去米国,一下飞机登录他的Facebook,发现右侧的广告是有关于“英语学习”和”美国回中国机票”。

文本广告组成

一个完整的搜索竞价广告示例,包括出价词语(Bid Phrase)、出价(Bid),标题(Title),描述(Creative),显示的Url(Display URL),而Landing URL是点击该广告的登录页面URL,Landing Page也经常用于关键词广告匹配过程。

image

检索方法概述

广告也可以看作成是一种信息,因此广告的匹配过程可以根据用户输入的查询关键词以及其他一些信息,例如之前搜索的内容、用户的Location等,采用一些传统的IR方法,将广告的出价词语、标题、描述以及Landing Page当做广告文档的语料,用来和用户输入的query进行文档相似度匹配。

A.Broder在SIGIR 2007提出了一种利用web search的结果来对query进行分类、从而进行广告选择的方法。用户在搜索引擎中输入的查询关键词一般都很短,有时候很难通过关键词了解到用户到底需要寻找什么,而通常如果看到了搜索结果的网页,就会了解用户到底要找什么,例如用户搜索一个v880,通过搜索结果页可以了解用户需要找一款Android的手机,此时就可以投放相应的手机广告了,即利用搜索结果为广告的选择提供额外的信息。

image

该方法需要研究的内容就是如何利用搜索结果页,是利用前几项片段还是利用整个结果页,是利用搜索结果页上的快照信息还是利用原网页信息,以及多个搜索结果并不统一,是采用整合还是投票选择机制。

计算广告学其中有很多问题需要算法来进行解决,包括广告分析、Query分析与重写、广告排序(纯粹谁出价高谁排前面就算了)之类的可以学习,本笔记的学习资料来源在这里

, ,

前几天去吃葫芦头的路上,大飞哥给详细的讲解了他在比较文本相似度实验时对Google的simhash方法高效的惊叹,回来特意去找了原文去拜读。

Simhash

传统IR领域内文本相似度比较所采用的经典方法是文本相似度的向量夹角余弦,其主要思想是根据一个文章中出现词的词频构成一个向量,然后计算两篇文章对应向量的向量夹角。但由于有可能一个文章的特征向量词特别多导致整个向量维度很高,使得计算的代价太大,对于Google这种处理万亿级别的网页的搜索引擎而言是不可接受的,simhash算法的主要思想是降维,将高维的特征向量映射成一个f-bit的指纹(fingerprint),通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。

simhash算法很精巧,但却十分容易理解和实现,具体的simhash过程如下:

1. 首先基于传统的IR方法,将文章转换为一组加权的特征值构成的向量。

2.初始化一个f维的向量V,其中每一个元素初始值为0。

3.对于文章的特征向量集中的每一个特征,做如下计算:

利用传统的hash算法映射到一个f-bit的签名。对于这个f- bit的签名,如果签名的第i位上为1,则对向量V中第i维加上这个特征的权值,否则对向量的第i维减去该特征的权值。

4.对整个特征向量集合迭代上述运算后,根据V中每一维向量的符号来确定生成的f-bit指纹的值,如果V的第i维为正数,则生成f-bit指纹的第i维为1,否则为0。

simhash

simhash和普通hash最大的不同在于传统的hash函数虽然也可以用于映射来比较文本的重复,但是对于可能差距只有一个字节的文档也会映射成两个完全不同的哈希结果,而simhash对相似的文本的哈希映射结果也相似。Google的论文中取了f=64,即将整个网页的加权特征集合映射到一个64-bit的fingerprint上。

比起simhash,整片文章中Google所采用的查找与给定f-bit的fingerprint的海明距离(Hamming Distance)小于k的算法相对还稍微难理解点。

fingerprint的Hamming Distance

问题:一个80亿的64-bit指纹组成的集合Q,对于一个给定64-bit的指纹F,如何在a few millionseconds中找到Q中和f至多只有k(k=3)位差别的指纹。

思想:1. 对于一个具有2^d个记录的集合,只需要考虑d-bit hash。2. 选取一个d’使得|d’-d|十分小,因此如果两fingerprint在d’-bits上都相同,那么在d-bits也很可能相同。然后在这些d-bit match的结果中寻找整个f-bit的Hamming Distance小于k的fingerprint。 简单的说,就是利用fingerprint少量特征位数比较从而首先缩小范围,然后再去确定是否差异小于k个bit。

算法:

1. 首先对于集合Q构建多个表T1,T2…Tt,每一个表都是采用对应的置换函数π(i)将64-bit的fingerprint中的某p(i)位序列置换换到整个序列的最前面。即每个表存储都是整个Q的fingerprint的复制置换。

2.对于给定的F,在每个Ti中进行匹配,寻找所有前pi位与F经过π(i)置换后的前pi位相同的fingerprint。

3.对于所有在上一步中匹配到的置换后的fingerprint,计算其是否与π(i)(F)至多有k-bit不同。

算法的重点在于对于集合Q的分表以及每个表所对应的置换函数,假设对于64-bit的fingerprint,k=3,存储16个table,划分参考下图:

HammingTable

将64-bit按照16位划分为4个区间,每个区间剩余的48-bit再按照每个12-bit划分为4个区间,因此总共16个table并行查找,即使三个不同的k-bit落在A、B、C、D中三个不同的区块,此划分方法也不会导致遗漏。

以上方法是对于online的query,即一个给定的F在集合中查找相似的fingerprint。如果爬虫每天爬取了100w个网页,快速的查找这些新抓取的网页是否在原集合中有Near-duplication,对于这种batch-query的情况,Map-Reduce就发挥它的威力了。

batch-query

不同的是,在batch-query的处理中,是对待查集合B(1M个fingerprint)进行复制置换构建Table而非8B的目标集合,而在每一个chunkserver上对Fi(F为整个8B的fingerprint)在整个Table(B)中进行探测,每一个chunkserver上的的该Map过程输出该Fi中与整个B的near-duplicates,Reduces过程则将所有的结果收集、去重、然后输出为一个sorted file。

Haffman编码压缩

上述的查询过程,特别是针对online-version的算法,可以看出需要对8B的fingerprint进行多表复制和构建,其占据的容量是非常大的,不过由于构建的每一个置换Table都是sorted的,因此可以利用每一个fingerprint与其前一个的开始不同的bit-position h(h∈[0,f-1]) 来进行数据压缩,即如果前一个编码是11011011,而自身是11011001,则后一个可以编码为(6)1,即h=6,其中6表示从第6位(从0开始编号)开始和上一个fingerprint不相同(上一个为1,这个必然为0),然后再保存不相同位置右侧的编码,依次生成整个table。

Google首先计算整个排序的fingerprint表中h的分布情况,即不同的h出现次数,依据此对[0,f-1]上出现的h建立Haffman code,再根据上述规则生成table(例如上面的6就表示成对应的Haffman code)。其中table分为多个block,每一个block中的第一个fingerprint保存原数据,后面的依次按照编码生成。

将每一个block中所对应的最后一个fingerprint保存在内存中,因此在比对的时候就可以直接根据内存中的fingerprint来确定是哪一个block需要被decompress进行比较。

8B个64-bit的fingerprint原占据空间大约为64GB,利用上述Haffman code压缩后几乎会减少一般,而内存中又只对每一个block保存了一个fingerprint。

 

每次看Google的论文都会让人眼前一亮,而且与很多(特别是国内)的论文是对未来进行设想不同,Google的东西都是已经运行了2,3年了再到WWW,OSDI这种顶级会议上灌个水。再次各种羡慕能去这个Dream Company工作的人,你们懂得。

参考:

Detecting Near-Duplicates for Web Crawling(Paper)

Detecting Near-Duplicates for Web Crawling(PPT)

, ,

Google于2010年4月将一个新的增量索引架构Percolator部署到了websearch index上,并命名为Caffeine(咖啡因)。自己最近发现网上写的日志什么会很快的被Google索引到,而百度则要慢得多,因此特意去找了这篇paper的原文来仔细拜读了下。

Google的Percolator增量索引更新是针对在一个大的数据源中只有少部分被更新需要重新索引而设计的,并没有取代之前的Map/Reduce方式,即原来的索引更新是当增量的数据到达一定规模时,对repository进行MR重新建立索引并加入全局索引。而采用了新的Percolator系统后,每天处理和之前相同规模的文档,平均的生命周期缩短了50%(即从网页被爬取下来到处理,索引完成可以被搜索引擎搜索到的时间间隔)。

Percolator的架构图:

Percolator由Worker, Bigtable, GFS三部分组成,Percolator提供了一系列的observer关联在worker上,这些observer定义需要观察的data table中的columns,当该columns发生变化时,对应的observer会作为一个function call被worker process调用,Percolator的应用程序就是由一系列的observers组成的,每个observer。

阅读全文…

,