Temporal Click Model for Sponsored Search

Temporal Click Model for Sponsored Search

解决的问题:找出位置和周围广告质量是怎么样影响用户行为的。利用用户的点击广告的顺序数据,预测用户的点击行为,也就是预测用户可能按照那种顺序点击广告,

目的:是根据点击顺序的概率,可以计算出任意一个广告的概率。

一个广告的展示序列A<a1,a2>按照位置排序。点击序列:有5种可能的点击顺序,c1<,>; c2<a1,>; c3<a2,>; c4<a1,a2>; c5<a2;a1>按照点击时间排序。

背景:研究表明,在线广告中的外部因素(广告所在的位置,相邻广告的质量等)对用户的点击行为会有影响。

* 眼部跟踪实验,用户不偏好点击位置低的结果,即使低位是放的“最好”的结果。

* 收到位置影响,也受用户感知的广告质量结果的影响。

* 用户看到结果后是从上到下浏览,基于假设:只点击一次。无法解释多次点击的广告。以后的研究只是针对如何relaxing这个假设,1,依赖于已经点击过的广告继续点击;2,依赖于落地页质量的继续点击。

* 以上的几个都没考虑特定广告的吸引力(质量)或者与广告周围邻居的相关性。又有些结果考虑了广告之前的影响,结论是只被上面的影响不被下面的影响,这在搜索引擎中不合适。

* 有些提出了一些理性假设,用户首先比较广告质量再点击最好的那个,不是从高向低位置浏览的。但是只用来研究竞价机制。不适合用来做ctr预估。甚至没验证外部因素的影响。

* 所以,作者首先证明在搜索广告中确实存在外部因素,然后用个综合模型去解释位置和周围质量因素的影响。。

为了分析,在某个特定广告上相邻广告质量对用户点击行为的影响,作者做了实验:只收集了顶部和底部中只有2个广告的数据,这里用广告的历史ctr代表广告质量。将所有第一个位置的ctr相同的展示作为一组,并计算第二个位置上的ctr的均值。发现如下现象:

在north的两个相近位置上的广告,ctr的值并不是同时增加的,这表明,当广告质量很高时(>0.2)会对另外一个位置上的ctr产生负面影响。

另外在south的两个相邻位置上,ctr变化趋势是这样的:

clip_image001[4]

这说明,在广告质量都很低的时候,不会对另外一个位置的ctr产生负面影响(有积极作用???)。

以上表明广告质量会影响点击率。

另外验证是否广告的质量会影响用户首先点击哪个广告。结果发现:

clip_image002[4]

无论对于north还是south,随着广告质量增加,用户首先点击该广告的比例增加。

综上,高质量广告会对其它广告的ctr产生负面影响,而且会影响点击顺序。因此,作者认为点击序列的时序能用来研究对用户点击行为产生影响的外部因素。

基于数据的分析作者假定:用户看到返回的广告结果后,先examine每个广告并估计认为给出一个质量值,然后对比各个广告的质量。一般是按照先后顺序点击,除非用户觉得第二个广告的质量比第一个广告质量高很多。

生成过程:clip_image004[6]

所以作者提出一种时间序列的点击模型TCM,对于一个展示A=<a1,a2>,图模型如下:clip_image005[6]

首先用户看到结果A,然后根据位置信息和自己的判断哪个更好,然后再去点击这个广告。这里有个假设:在不懂的组合中,展示和点击的序列是互相独立的。

//A={A1,A2,…,AN}表示N种广告展示组合序列,每个Ai有1到M个广告,例如A1=<a1,a2>,C={C1,C2,…,CN}表示每种展示组合对应的点击组合序列。R={R1,R2,…,RM}表示用户自己估计的广告质量,U={U1,U2,…,UM}表示位置信息。//

对应于:用户是否关注返回的结果建模:clip_image006[6]

然后估计选哪一个:

clip_image007[6]

其中,用户估计的广告质量和位置信息由展示组合序列计算得到:clip_image008[6]

最后点击该广告的概率。

clip_image009[6]

以上只是点击某个组合中第i个广告的概率。

那么整个组合的概率计算是:

clip_image011[4]

由所有可能组合的概率,计算单个广告的点击率:clip_image013

这个方法与其它方法的不同之处:考虑了广告点击的顺序,这个是其它广告所没有考虑过的。并预测点击序列的概率,即可能先点哪个后点哪个。

最后作者做了2个实验,一个是自然搜索结果顶部广告数据;一个是自然搜索底部广告数据。数据中分别有30万(3%)和11万不同的query(5%),每个query分别有1亿和6.5亿个组合。这样的数据,可以直接通过统计做出很好的ctr预估,为了防止tcm模型的预测被这样的数据主导,就删除掉,只保留了频率小于1000次的query。

结论:无论是在NAD还是在SAD中,tcm模型的精度都很好,随着query频率增加,

clip_image014[4]

左边是顶部广告,右边是底部广告。这说明作者的假设是符合实际的。

不过随着query频率增加相比其它模型的优势在减少,

clip_image015

clip_image016[4]

原因:对于热搜的词,此时的假设“用户先估计质量分再对比确定点击哪个广告”的假设不成立,因为:用户更相信搜索的结果,因为用户可能认为搜索引擎是按照用户的反馈(点击次数)排序的。

clip_image017

如何读论文

一直以来,也看了不少论文,但是总有一个问题,当别人问我这篇论文主要讲的什么的时候,我总是答不好,或者是回答之后别人还是不明白。

这不是一个小问题,也曾经让我很苦恼,所以我后来分析了一下原因。

之前,我看论文重点在模型以及算法公式的推导,总会针对论文中的公式推导来推导去,一定要把每个步骤都搞清楚心里才踏实。这样的做法,第一,很费时间,第二,会陷入局部而不知全局,也就是不能hold住论文的整体。另外,我基本不看论文的实验部分,这是一个很大的遗憾和错误。

所以,以后看论文要关注一下几点:

1,这篇论文的模型和算法是什么(不是公式怎么推导),解决的什么问题,为什么这个模型和算法在这篇论文中适用?

2,尝试从另外的角度去思考论文中的问题,思考如何扩展论文作者的idea,看能否想出更好的解决问题的方法。

3,怎样改进论文中的模型和算法使得它能够解决新的问题。

4,实验部分:用的什么数据,什么数据格式,数据如何分割的,实验是如何做的,如何评估实验结果的。

以后慢慢改进方法,要做个能动脑又能动手的人。

 

有些论文,一定要精读,读完之后才会有感觉。现在读论文开始思考为什么他们的方法好,模型方面还是算法方面,怎么变好的,他们的假设是什么。另外一个想法就是遇到公式时,要解释公式而不是只推导公式,我觉得这个对理解问题非常重要,要锻炼自己解释公式的能力,如果能把公式解释好,向别人讲时就能讲明白,否则就讲不明白,亲身经历。

Large-scale behavioral targeting

    download:http://www.cc.gatech.edu/~zha/CSE8801/ad/p209-chen.pdf

    利用用户历史行为数据为用户选择合适的广告,目前最好的是线性泊松模型,通过用户行为数据预测ctr。Ctr的点击率提高了20%。可用的用户行为数据:点击,浏览,网页浏览,搜索词和搜索词点击。工业界BT的数据虽然很稀疏,但是数据量也都很大。如果要减少泛化误差,需要大量的数据。

BT不依赖于上下文信息(比如查询词,网页内容这些content),这使得BT也可以用于图片类型的广告(这些广告没有内容的)。BT主要是依赖隐式反馈。利用用户历史数据计算一个分数,超过一定的阈值就给用户展示广告,这个分数实际上就是ctr。

线性泊松回归。点击数符合泊松分布,y是观察到的点击数据,clip_image002是泊松分布的期望(lamda与y是什么关系?)clip_image003

用最大似然估计的方法做参数估计,求使得上式的对数最大的参数w,对p(y)求导:

clip_image004

求和符号,是因为所有训练数据的所有样本对应的p(y)求最大似然值。

对于关于参数w的迭代公式,可以使用梯度下降方法,也可以使用收敛更快的拟牛顿法,但是论文作者选择了另外一种方法(为什么选这个?好处是什么?):文献【11】中的方法,迭代公式是这样的: clip_image005

下面讲讲文献【11】,下载地址:http://hebb.mit.edu/people/seung/papers/nmfconverge.pdf

———————————————————开始————————————————————-

论文中是这么说的:在非负矩阵分解问题clip_image006中,要用W和H两个矩阵逼近原始的矩阵V,用损失函数1:最小方差clip_image007

以及损失函数2:KL散度clip_image008

这里的A等于V,B等于WH。对于这两个损失函数,作为目标函数最小化它时,它只对W或者只对H其中一个作为变量时为凸函数,对两个同时作为变量时就不是凸函数,所以无论对于哪个损失函数,都没有有效的方法求得全局最优解,因为W,H都是我们要求的变量,而此时函数又非凸,对于非凸函数,只能找到合适的求解局部最优解的方法。

在求解这两个损失函数最优值的方法中,梯度下降是最简单的,但是收敛慢,共轭梯度法虽然在局部最值附近能快速收敛,但是实现起来很困难,所以,作者针对两种不同的损失函数提出了两种不同的迭代方法,证明过程在草稿纸上,打出来太麻烦了。

—————————结束———————————-

在本论文中,作者使用的损失函数为KL散度。也就是使用了这个迭代公式:

clip_image010。既然使用了文献【11】中的方法,那一定是有原因的,也就是本论文中针对的问题一定是和文献【11】中的问题类似的。

   continue;

RBM受限玻尔兹曼机

关注Deep Learning时学习了RBM相关的知识,也看了几篇论文。这里是我当时写的一个程序,用的Movielevens的数据集,打算做个用户电影推荐的,效果不好。这几天要用它来试试ctr预估,用一下公开数据集kddcup 2012 track 2的数据,如果公司的数据允许用的话,或许可以试试公司的数据。参考这篇博客:http://blog.echen.me/2011/07/18/introduction-to-restricted-boltzmann-machines/

 

这是设计文档,数据可以自己去网上下载(我不知道怎么在我的博客里提供数据):

基于RBM模型的推荐系统示例

1,RBM结构:

1682部电影,所以共1682个显层节点,18个电影类型,共18个隐藏层节点。

2,流程:

(1) 首先用符合标准正态分布的随机数初始化权值矩阵w[1682][18].

(2) 初始化显层输入数据,由于有943个用户,所以有:v[943][1682],每一列的数据为0:表示用户不喜欢这个电影,或者1:表示用户喜欢这个电影。将u.data中的打分超过2分的都看作用户喜欢这部电影。

(3) 开始训练模型:

1.初始化隐藏层节点数据矩阵hidden[943][18],其中hidden = v[943][1682]*w[1682][18],使用logistics函数处理hidden中每一个元素的值,并将元素值与随机数rand()比较,大于rand()的设置为1,否者设置为0。得到的hidden的每一行为0:用户喜欢该电影类型,或者为1:用户不喜欢该电影类型。

2,计算显层和隐藏层之间节点同时为1的个数。初始化v的转置矩阵transformV[1682][943],关联矩阵Association1[1682][18] = transformV[1682][943] * hidden[943][18].

3,由隐藏层矩阵重构显层矩阵,初始化重构后的显层矩阵virtualV[943][1682]。首先得到权值矩阵的转置transformW[18][1682],virtualV[943][1682] = hidden[943][18] * transformW[18][1682]。再对每个重构后的元素调用进行logistics函数计算。

4,由重构后的显层矩阵virtualV[943][1682],计算隐层矩阵,此时可以直接使用前面定义过的矩阵hidden[943][1682],hidden[943][18] = virtualV[943][1682] * w[1682][18]。

5,计算重构后的显层与隐层节点同时为1的个数。初始化virtualV[943][1682]的转置矩阵transformVirtualV[1682][943],Association2[1682][18] = transformVirtualV[1682][943]*hidden[943][18].

6,更新权值矩阵。初始化deltw[1682][18]. deltw[1682][18] = (Association1[1682][18] – Association2[1682][18])/943.

7, w[1682][18] -= deltw[1682][18].

所需初始化的矩阵:

全局变量:权值矩阵w[1682][18],局部变量:deltw[1682][18]。

局部变量:显层节点矩阵v[943][1682],重构后的显层节点矩阵virtualV[943][1682]

局部变量:隐层节点矩阵hidden[943][18]

局部变量:显层节点矩阵转置transformV[1682][943]

局部变量:权值矩阵转置tranformw[18][1682].

测试数据:自定义了一个1行18列的数组p[1][18] = {0,0,0,0,1,1,1,1,1,0,1,1,0,1,0,1,0,1}

代码:https://github.com/xswang/Machine-Learning/blob/master/rbm.cpp

先试一下简单的logistic regression,然后再找一下这个RBM的效果很惨的原因。