Predicting Clicks Estimating the Click-Through Rate for New Ads

Predicting Clicks Estimating the Click-Through Rate for New Ads:http://wwwconference.org/www2007/papers/paper784.pdf

        对经常展示的广告,可以根据历史数据估计ctr,对新广告,没有历史数据,必须用其它方法。论文中用了广告的特征,词组,广告主的数据预测新广告的ctr。论文中是cpc的方式。

        对于那些用历史数据估计ctr的,结果会有较大方差。论文针对新的广告创意,新注册的广告主。广告长度,词数。广告指向的页面;和广告相关的广告的统计数据。

        广告位置对ctr预估的影响力非常大。很多人只看第一页的广告,对展示很多次的广告,可以用最简单的二值最大似然估计的方法,论文【19】用了和已经存在的广告有相同竞价词以及主题聚类的信息。本论文作者实验发现用相同竞价词的信息效果方差也很大。

        作者将广告被点击的过程理解为:1,被看到的概率,2,被看到后点击的概率:clip_image001

。因为看到后点击与否与位置并不再相关,所以成为:

clip_image002

即在第二个过程中将位置的影响因素去掉。

        模型:

Logistic regression:clip_image003

        用L-BFGS算法做优化。有交叉熵损失函数加上0均值的高斯先验。将标准差大于5的特征剪枝为5.用KL散度衡量模型的性能。

        根据广告里的term估计:clip_image004

        N(term)是含有这个广告词的广告数,CTR(term)是这些含有这个term的ctr平均数。clip_image005是训练数据中所有广告的ctr的均值。

对于一个关键词t,以及一个广告ad,做如下定义:

clip_image006

m是广告中比广告词t少的词的个数,n是比广告词t中多的词的个数。

        例如clip_image007表示比广告词t多无限多个词,也就是该广告词t对应的广告的一个超集。例子:广告词t是:red shoes,对于一个广告buy red shoes,比t多一个词buy,所以是clip_image008,对于广告blue shoes,它比广告词t多了一个blue且少了一个red,所以是clip_image009

所以有相关关键词t的新广告的ctr估计为:clip_image010

Relational Click Prediction for Sponsored Search

Relational Click Prediction for Sponsored Search:下载链接:http://www.cs.cmu.edu/~cx/paper/relational_click_prediction_for_sponsored_search.pdf

        公式又成了黑方块,唉。。。

        搜索广告的点击率预估文章,ctr的精确估计可以用在广告的排序和出价方面。论文做ctr预估时考虑了广告之间的关系对预估值的影响。广告与周围越相似,点击率越低。

        广告排序:1,广告主对某个搜索关键词的出价,2,搜索引擎估计的用户点击广告主广告的概率。

        有些点击率是根据历史点击估计的【8】【15】,但是,对于新广告或者大部分的广告,是没有历史数据的,怎么办?

        个性化点击率预估,加入用户人口统计学信息。

        【7】【11】【12】【21】也是使用了广告间的相互关系,但是它们主要是为了挖掘用户的点击行为,或者是为了设计竞价机制,而且没有仔细研究具体是广告之间哪些交互因素起作用。【21】的结论是质量好的广告会影响质量差的广告。

        本论文有个结论是质量因素的影响小于相似度因素的影响。论文的假设1,ctr和自身天然属性有关,比如广告和搜索词之间的关系,广告的质量,历史点击率。2,与周围广告的相似度。

模型:

        传统ctr预估的建模过程:clip_image002[4]是广告,u是用户,q是搜索词,clip_image004[4]是第clip_image006[4]个广告的位置,clip_image008[6]是一个二值变量,clip_image008[7]=1表示点击了第i个位置上的广告。clip_image009[4]是该广告的点击率。其中clip_image011[6]是从u,q,p,a四个因素中抽取出来的特征。

        论文作者不仅仅使用单个广告的信息,而是考虑了广告之间的信息,要估计的是整个list中的广告的ctr,这个list可以认为是在某个位置紧邻出现的广告。clip_image012[4]

这个就是作者要求的目标:一序列的广告的ctr,X是所有广告特征clip_image011[7]的集合。R是广告之间的相似度。F输出的结果是一个n维向量,第i个值就是广告clip_image002[5]的ctr。

        连续的条件随机场模型,兼顾广告本身的特征及与周围广告相似度。可以用最大似然估计,也可以推理出解析解。用最大似然估计的方法做参数估计,并用随机梯度下降的方法学习参数(目前不做算法的详细推导,以免掉入坑内)。

 

实验:

    数据分3部分,第一部分做特征抽取,第二部分做训练,第三部分做测试。去掉只有一个广告的list.抽取查询词-广告对,独立的查询词,独立的广告,广告主的竞价信息,广告与查询词之间的关系,等等作为特征。

        用【4】【19】中的logistic regression作为baseline算法,这些算法只用单独的广告信息(local)。在论文中使用的CRF模型中,使用线性回归函数作为local model,即,用线性函数f = clip_image014[4]为单个广告建模。

Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine。

周末看了一下这篇论文,觉得挺难的,后来想想是ICML的论文,也就明白为什么了。

先简单记录下来,以后会继续添加内容。

主要参考了论文Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine(下载链接:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.165.5644&rep=rep1&type=pdf)以及百度网盟CTR预估技术负责人夏粉老师分享的资料(下载链接:http://pan.baidu.com/share/link?shareid=484272&uk=4010619712)。

有不对的地方,希望能指出:(2012wxs@gmail.com)。

前面部分就不说了。从第3节Online Bayesian Probit Regression开始

第三节 Online Bayesian Probit Regression

X是要输入的N维特征X->(clip_image002),特征的每一个维度clip_image004有M个取值,即: clip_image004[1]->(clip_image006),其中clip_image008的取值只能是0或者1,且clip_image004[2]中所有元素的和等于1,也就是说clip_image004[3]中的元素只能有一个取值为1,其余的必须取值为0。

作者假设样本分布符合高斯分布,分布函数为:

clip_image010,                                                                                (1)

其中clip_image012                                                                      (2)

即密度函数为标准正态分布:clip_image013

假设W的先验分布为:

clip_image015,                                                                  (3)

其中f为正态分布函数clip_image013[1]

clip_image017的精确后验公式为:

clip_image019

因为clip_image021,

所以:clip_image023,                                              (4)

(1) ,(3)可知(4)为:

clip_image025

clip_image027

clip_image029是对分子clip_image031关于w的积分,所以:

clip_image033

clip_image035                                                            (5)

由公式(2)可知

clip_image037                                                                          (6)

公式6就是关于w的精确后验的公式,从公式中可以看到由于积分区间和积分式中都出现了w,所以没有关于w的解析解。因此,论文使用message passing方法近似求解w的后验概率。

w的精确求解公式(4)可知,近似求解公式为:

clip_image039                                                                                               (7)

其中,clip_image041是先验概率,clip_image043是似然函数,也就是在对w的假设clip_image041[1]的情况下,实际结果y取值0或者1的概率。为了能够对似然函数进行分解,引入了两个隐变量s,t,将似然函数clip_image045分解为clip_image046

所以公式(7)成为这种形式:clip_image047

 

 

    可以理解为一个如下的生成过程:

clip_image048

 

    <1>w的值是从高斯分布中得到的,因为假设其先验符合高斯分布。

    <2>得到w的值之后,可以得到一个分数s,分数s的值为clip_image050,取得这个值的概率为clip_image052,即clip_image054

    <3>得到分数s之后,对这个分数clip_image050[1]加上一个均值为0,方差为clip_image056的标准正态高斯噪声。最终得到变量t的分布为均值为s,方差为clip_image056[1]的正态分布clip_image057

    <4>得到t之后,需要根据t计算y值,是由符号函数sign计算得到的,即y的取值为y = sign(t),只有两种值即y = 0,y = 1,其取值概率为:clip_image058

    由<1>步得到的p(w)等价于w的近似后验公式7中的先验pw);由<2><3><4>步得到的clip_image058[1]等价于w的近似后验公式(7)中的似然函数。

<1><2><3><4>的各个公式的乘积等价于w的近似后验公式(7),另外,由因子图中因子节点的乘积为变量的联合概率分布可知,<1><2><3><4>中各个公式的乘积为变量w,s,t,y的联合分布clip_image059,所以在论文中有讲是等价的:clip_image060

    另外,根据论文中所讲,等价式是变量w,s,t,y的联合分布clip_image059[1],因此,我认为那个factor graph 1应该这么画:

clip_image061

 

    至此,模型已经建立:由于无法精确求解w的后验,将求解w后验的问题转化为一个因子图中的生成过程,并且将求解问题分解为计算一个个的local message,最后将这些local message相乘就行了。

    下面是推理部分

    也就是如何训练模型的过程,

    首先,根据历史数据,比如历史平均点击率,给出W的先验,另外,有训练数据(xy)。根据w的先验和训练数据(x,y),推理出w的后验概率(在factor graphmodel中等价于clip_image059[2]),这个过程叫upward message

clip_image062

其次,根据第一步得到的w的后验概率(此时的w的先验概率是第一步得到的后验概率),以及特征x,可以计算出对于输入的一个特征向量x,得到的预测值y的分布clip_image064,这个过程叫downward message:

clip_image065

 

 

先到这里。