Category Archives: 计算广告学

百度计算广告学沙龙笔记

夏粉的分享:

        首先解释计算广告学,追求的是,在一定环境下用户与广告的最佳匹配,这里的一定环境下,包括用户的query,当前浏览的网页,也有一些用户个人信息,但是比较少,这是用户的隐私数据,不好拿到。

        点击率预估的问题:

                1表示用户点击,0表示没有点击或者用户根本没看到,这个和推荐系统中用户评分差不多啊,没评分的可能表示用户根本不感兴趣或者用户根本没看到。关键的问题是:特征维度高,数据量大(每天可能上亿次的请求)。

        数据预处理的问题,首先是展示于点击日志的拼接,我之前以为是在一起的。包括两方面:日志->数据,这是行上的处理,比如抽样,去除缺失数据什么的;日志->特征,这是矩阵中列的处理。

        数据/特征规模的问题:百亿广告(行),千亿/百亿级的特征(列),一个问题是类别不平衡(点击的少,未点击或者用户根本没看到的多),噪声大(恶意点击等等)。

        特征复杂度高:特征之间高度非线性,举个栗子:不同性别不同年龄段的人关注的广告不同,人工组合方式把特征的非线性表示出来,例如:什么样的人在什么时间应该展示出什么样的广告。话说我觉得应该是response与特征之间的高度非线性问题吧?不是特征之间的非线性,response可能依赖于非线性的某些特征,而这些特征根需要人工或者机器组合得到。

时效性高:点击率随着时间变化,也就是随着时间人的兴趣会变化。

话说核心还是人啊,有些情况下即使输入的query和广告毫不相关,用户也可能以很大的概率点击广告。当然,大部分情况下,query还是能反映出用户的一些意图的,从而推断用户的后续行为。

        新广告或者流量的上下线。

        数据训练频繁:包括模型更新,比如从LR->DeepLearning.另一个是策略调整(不明觉厉)。因此需要快速,要做的是1获取主要信息,2去噪,所以选择对点击概率分布足够多的样本。

        数据处理,去除一些可见/不完整样本,或则机器学习的方法进行样本采样。google的做法:某个query对应的广告一个都没被点击过,则以概率p去掉该query,但是在训练时对那些以P为概率删除的样本乘以一个权重r.目的是为了补偿它。具体见google的论文<>

        要用尽可能少的特征表示模型的数据,具体方法包括特征选择与特征删减。模型要小,满足速度上的需求。

        主要包括大量id类特征,少量连续型特征。注意是大量id类,少量连续型。id类特征使用one-hot encoding的编码方式。

        然后是一个loss function,和之前见到不同的是在非正则化项前加的C,等值线随着C的增大扩张,直到与约束(正则化项)相遇,最常见的是L1范数正则化。其实和之前的都一样。

        特征删减:虽然特征那么高维,其实模型真正能用上的特征是比较少的。可以在训练前判断哪些特征的权重可能为0,比如可以根据点击的情况,也就是真实的反馈判断哪些特征权值为0,可以用一个公式衡量特征的分数,例如百度的Fea-G算法(screening test?),新的特征以概率P加入;bloomfilter + 次数超过n次的才加入;google的做法。

        人工特征工程:构造高阶组合特征,描述特征间非线性关系(我还是觉得应该是response所需要的非线性特征之间的关系。ps:到底是特征间非线性关系,还是response与非线性特征之间的关系(线性or非线性)?),如下方法:1,人工经验,耗时,也容易达到上界;2,枚举,太慢了;这两种都无法泛化(泛化能力很弱)。

         下面,高大上的Deep Learning登场:

             DL能自动学习feature,在语音和图像上的情况是:特征少,数据量大。比如28*28的图片可以有几千万张。但是在计算广告学领域,特征的特点是大规模稀疏特征,1,目前尚无专门针对大规模稀疏特征的深度特征学习算法,2,主要是样本相对特征不充分,样本量相对特征量来说比较少。

            针对第一个问题,需要降维的方法,针对第二个问题,需要把样本相对多的找出来(比如PV比较多的feature,要充分学习一个feature,需要包含该feature的样本充足)。

不过,网盟团队研发了能直接应用于大规模sparse特征的深度特征学习算法DANNOVA。逐层贪婪算法(这个信息比较有用):单特征->二阶组合->高阶组合。PPT上有个图。另外的问题:训练数据要少,模型需要稀疏才行,这样速度才会快。

            优化算法:google保留前N次的梯度,这个貌似是针对L-BFGS说的?每条样本要多训练几次,一次学不完样本中的所有信息(这个我没明白,一次不久行了吗?)。SOA算法,貌似是模型优化算法?

            对于L-BFGS算法来说,每一次的梯度之差,步长之差都要保留,为了根据割线定理计算hession矩阵?,由于是个向量,而且维度上千亿,所以对内存是个很大的挑战,而且,当特征矩阵的谱很大时(特征值变化范围较大),收敛速度慢;启动慢,每次重新训练时都要先得到历史上m次的梯度之差,当初始点离真实的解很近时不能很快收敛到真实解。百度自己的shooting算法,对hession矩阵分块,使得特征值差不多的靠的更近。

    陈雨强的分享:

        首先说广告中的长尾分布,长尾query,百度每天有约20%的query是历史记录中从没有出现过的。长尾问题,是针对query的长尾。不是广告的长尾(展示广告中是广告长尾?)理解点击:1,广告并不是用户所需要的信息(这个容易理解)2,不只是<ad-query>语义。做搜索还行,做广告就不行,对搜索广告来说,语义不是最关键的。

        数据比较复杂,则模型也要复杂;数据与模型要线性的?(模型与非线性特征之间的线性?)。常用的方法:大量特征+线性模型;小量特征+非线性模型。

    各大公司的方法,来自于论文以及各种传说:

        1,小规模feature + 非线性模型:MS:浅层ANN;yahoo!:GBDT;淘宝:局部线性LR(从盖坤的PPT上可以看到);facebook:二层结构,low hierarchies + high hierarchies

        2, 大规模特征+线性模型:百度,特征精细描述用户行为,比如query是否有空格等等。

        已经证实LR对ctr预估问题有效。通过设计特征提升准确度,feature engineering.

        L-BFGS:特征向量上千亿维,一条历史记录的梯度都要占用很大内存。可以使用坐标下降法,随机挑选n列(虽然是随机,但是要尽量使得能遍历全部)update。

        优化数据流:所用时间少。

        LR:人工加特征,组合特征。但是,人工的方式目前已经没法做了,如何改进?

高大上Deep Learning:

        1,学习高层特征,2,逐层贪心算法学习(again)。

        DL所遇到的问题:1,特征维度太高,2,模型不能太大,因为要数十毫秒内给出结果(只在线上的时候)。所以要对特征降维:各种降维算法(主要针对id类的,embedding function),连续值型的没必要了。

        对于大规模feature,使用cpu/LBFGS即可;小规模feature(容量合适的情况下),可以使用GPU()。

        另一个问题:E&E问题,这个就是机制的问题了。baseline算法比如LR可以接触到更多的badcase,从而很好的训练模型,DL接触的机会小,难以说明是不是改进的算法不行。

        大家提的一些问题:

         1,特征降维:根据特征的层级性。2,数据分布不一致:迁移学习,原数据->目标数据,通过学习数据量比较多的原数据的特征,加入到目标数据中,另外,定义元数据与目标数据的相似度。3,要实用更通用的特征,泛化能力强。4,分布式,SGD不适合分布式,mini-batch SGD,一般是100左右的batch。异步SGD。

总结:

    核心还是人。

    网搜和商搜用DL的方式不同:网搜直接针对高维稀疏特征,输入是单特征;商搜是先降维(有监督、无监督方法),针对categorical variable降维。方法还是逐层训练不是直接BP。

    另外夏粉提到的数据压缩Fea-G,不知道是指的哪些方法。

    DL省去了人工组合特征,让机器自己找,有监督的方法会不会更好些?特征可以是高阶,但是特征和模型要线性。

    以前考虑广告数据和图像语音数据的不同,图像,语音数据具有结构性,可以抽象出直观的high level feature,所以DL取得的效果比较好。现在觉得,那并不是主要原因吧,关键应该还是非线性模型对线性低阶特征的拟合。

    至少知道了我之前的想法中哪些是合理的,哪些是无解的。没办法,没人带就自己一点点儿琢磨吧…

计算广告ctr预估的想法

做CTR预估的目的:就是使得ctr尽可能估计的准确,这里的准确,既不是过高估计某广告的ctr,又不是过低估计某广告的ctr。而是要“合理”地估计其ctr。

ctr预估不准的原因,1是因为模型使用错误,也就是建模不对。2是选择了合适的模型却因为数据的稀疏或者训练数据较小导致结果不准确。

如何准确的估计ctr,我将其分为两类:

1,利用较为稀疏的数据或者包含噪音的数据准确的预测ctr,这里首先要保证模型的正确性。

2,在实际中做出探测策略,目的是为了多收集一些数据,便于更准确的做ctr预估。也就是explore and exploit问题。

第一种方法,是用机器学习的方法预测ctr,比较容易理解。

第二种方法,我的感觉是只是为了收集更多的数据而已,并没有用收集来的数据做ctr预估。比如UCB的方法,在对策略做更新时,稍微能体现出“学习”特性的只是更新variance的部分。

    ctr预估经常被建模成一个分类问题,利用用户查询词,广告,用户信息以及其它上下文信息预测是否会发生一次点击。

    在上面所讲的2个问题中,第二个问题并不是一定会出现的。现在讲讲第2个问题出现的原因:历史点击行为是公认的有效特征,但是如果太依赖于历史点击行为,对于历史上没有被展示过的广告(包括那些虽然质量很高但是由于太新或者点击模型的失误未被展示的广告)就很少有机会展示给用户,点击预测模型就会逐渐把结果固定在一些“老面孔”上。因此需要实现探索与利用的关系。

    所以,如果想要避免第二个问题出现,即避免点击预测模型的结果只局限于某些广告集合中,其中一个方法就是削弱历史点击行为在点击模型中的重要性,而使用其它的同样甚至更好的feature取代它。

    另外,web数据一个很大的特点就是动态性。传统的机器学习是建立在“静态”的数据假设下:样本从未知的确定分布中抽取得到。而互联网广告数据时动态的,当模型发生变化时,广告主也会改变其竞标数据,比如不再竞标bid word A 而去竞标bid word B;当一个广告主的数据发生变化时,也会带来其他广告主数据的变化,这些广告主数据的变化最终又会影响模型的最优性。如何在这种环境下使用机器学习的方法是一个巨大的挑战。

最近考虑用deep learning做ctr预估。原因是这样的:1,DL在图像和语音上取得了公认的很好的效果;如果把模型的输入都当做数据的话,据我了解,对于图像数据,有一个特点就是它具有结构性,比如,在一张人脸图像中,看到一只眼睛的位置,即使没看到另一只眼睛,也能大概猜测出另一只眼睛的位置在哪里,总之,我觉得,图像数据维度之间是有一定的“关系”的(我不清楚具体是什么关系,但是确实是有关系的),我想,是不是因为这样的“关系”使得DL作用在图像上的效果比较好。2,如果真的是因为这样的“关系”使得DL在图像语音上效果比较好,那么,针对做点击率预估的广告数据,是否也有这样的“关系”?有两种答案:(1)有,(2)没有。对于(1),如果真的有这样的“关系”,实际的效果会怎么样的呢?这就需要做实验。对于(2),如果没有,是否可以通过人工的方法对广告数据做下处理,使得尽可能广告数据之间的关系和图像数据之间的“关系”类似呢?如果可以,效果会怎么样?如果不可以,效果又会怎么样?所以我打算试试。
但是我对广告的数据不了解,不知道广告数据,或者说是互联网数据有没有结构,或者说就是一团杂乱无章的集合呢?

——————–2013年9月16日—————————-

后来又重新考虑了这个问题,也找了老师讨论,重新有了认识:从直觉上来说,广告数据确实没有图像数据那么直观的“high level feature”,但是,并不是人能理解的才是存在的,对于广告数据来说,虽然人不能抽象出“high level feature”,但是只要是机器是可以“理解”的就行,机器学习嘛,又不是人学习,“机器知我心”即可。所以,我觉得是可以用dnn来做ctr预估的,不过可能也需要做一下pre-process。
———————2013年12月17日————————–
根据前天百度技术沙龙的内容,网盟使用Deep Learning做ctr预估的方法是直接针对高维稀疏特征,也就是对id类数据one-hot encoding之后的特征。具体算法不详,layer-wise的贪心算法,之前以为会是经典的BP,但是夏粉和陈雨强都提到了逐层训练,那肯定就不是BP了;商搜是先降维,有两种可能:一是对one-hot encoding之后的特征降维,二是针对categorical变量,换一种方式表达,尽量使用较少的个数(维度),可能是real numbers(比如这篇论文《Conversion of categorical variables into numerical variables via Bayesian network classifiers for binary classifications》)。夏粉分享的一个PPT,关于google在ctr预估上如何使用deeplearning的:http://weibo.com/2187763790/zyjA3bfCE?type=repost#_rnd1387366449021

之前的想法是针对small-sample,high-dimension的数据。针对small-sample,暂时没有什么好的方法做这个问题,样本数就是那么多,也得不到更多的样本,除非:(1)实施Explore and Exploit策略来获得展示次数少的广告更多的训练样本。做实验是个问题,不过后续可能会考虑到。(2)据说,可以使用transfer learning的方法,对这个不懂,暂时不去考虑。

        当选定了一个机器学习模型,在模型训练阶段,每一个样本(x,y)送给模型之后,都能产生方程组当中的一个等式,也就是说,有多少个样本,方程组中就有多少个等式,例如,训练集中一共有100个样本,每个样本提取后的特征是1000维,就得到一个有100个等式1000个参数的方程组。
        对于这样一个方程组,当样本个数小于维度时,方程会有无穷多解,以求极小值做例子,也就是说可能有很多个局部极小值成为解的集合,那么,如果从这些解的集合中选择一个解之后,不能确保是全局极小值点。这必然带来模型精度上的损失。
        所以,不能把特征x中的所有特征都用上,在学习阶段,要逐渐使得A中的一些参数为0,这样得到的方程组各个等式中就会有很多为0的项(L1正则化),这样最终得到的方程组的参数比较少,进而使得方程组能得到一个确切解。
        对于上面的东西,需要进一步的思考验证。
        下一步要做的是:降维和加L1正则化,目的是否一样?哪一个对我要做的问题更好更有针对性?
—————————- 2013年9月19日——————————
        最近看到关于如何降维的论文,有这么几种方法:PCA,LDA,SVD…,主要针对高维数据。后来想了想,我要做的问题和他们解决的问题有个不同的地方是:我面对的是高维而且稀疏,他们好像只是针对高维,并没有强调稀疏。所以,我要针对样本少,特征维度高,而且特征稀疏的问题去学习。
        对于求解稀疏解:1提高精度;2,提高计算速度。如果从学术界->工业界的应用过程来看,第二种方法更实用。因为学术界取得的那一点儿精度上的提升,到了工业界首先不一定实用,其次就算实用,由于和其它模块的交互受其它因数的影响,那点儿优势估计也没了。但是,如果要发论文,还是很有意义的,因此不能放弃。
        高维稀疏数据有两类:1,含有噪声;2,存在缺失数据。对于互联网广告数据来说,应该不存在缺失数据的情况吧?比如公司的点击log数据,想要的特征应该都会有的。但是,噪声是会有的,比如一些点击log,有些点击可能是用户无意中点到的,这些数据对模型学习会带来不好的负面作用,因此看作噪声。
        所以,样本少,特征维度高&&而且特征稀疏,含有噪声/数据缺失可能是我最需要考虑的。

        实验准备:kddcup 2012 track 2的数据,腾讯soso提供的。解压之后原始数据有10G,对于只有一台笔记本的我来说,规模还是比较大的。

特征处理:采用one-hot coding的方式,维度有将近6千万维,也就是说,Logistic regression的参数theta有6000万个。不过其中的有效维度只有10个,非常非常稀疏。之前还用了另外一种特征形式:求出各个字段中各个数字的平均ctr作为特征,一共10维,基本上每个维度上都有非0值。  特征处理是在hadoop平台上做的,用python写的job.

实验过程:

最开始的时候,代码是自己写的,C++,linux平台,包括特征数据的读入,特征矩阵的形成,训练阶段,预测阶段。模型就是Logistic Regression,模型求解算法就是最常见的primal gradient decrease,也就是梯度下降,话说,为什么叫primal gradient decrease?

每次调参,差不多都要花费20分钟,其中数据的读入读书是个很花时间的过程。另外,用到了MPI并行化,进程之间也要有一定的通信。笔记本内存有16G,为了能灵活设置进程的个数,没有对数据做物理分割,而是每个进程都从文件中读入训练数据。之前也尝试过用一个进程读数据,然后把数据传送给其它进程,这样速度也挺慢的。

所以打算做一下改进,1,用redis做缓存,好处时只要不关机,数据可以一直在内存中,下次运行程序时可以直接从内存中读数据,节省了时间。坏处是会有将近4G(训练数据一共4G)的内存损失,也就是会有4G内存一直被占用。2,用MPI的目的是为了提高速度,学习MPI原理,之前开4个进程有些多了,所以减少为2个。另外之前的进程绑定也取消,因为绑定之后貌似速度还慢些。暂时先这么做。3,之前的训练数据用到了userID,貌似没有必要用了,应为kddcup给的数据,ID号都是经过处理的,就算有时间序列的特征,经过处理之后也没有了,同样的道理适用于广告id,以及广告主id ,总之,训练特征貌似要重新做。
下一步要做的事情,首先就是把userid这个给扔掉!2200万维啊,太noisey了。

现在要做的问题是小样本量,高维度数据的问题。分析了一下kddcup 2012 track 2 的数据:

其中,横轴表示广告id,纵轴表示1.5亿条训练样本中各个广告id对应的样本个数。共有641707个广告i的,我统计出各个广告id对应的展示次数之后,按照降序排序,然后画出了前1000个广告id的样本个数分布。可以看到,只有很少一部分广告(500/650000=0.0077%)的展示次数是比较多的,大部分展示次数比较少。

下面贴出一部分数据:

(1-20) (1000-1020) (6000-6020) (20000-20020)到这里只占整个数据集的3%
1350400
968428
856871
843525
661257
455095
402877
402295
401960
389247
380287
368704
356103
355550
352805
343217
331341
325578
324671
310237
17233
17221
17205
17177
17091
17082
17073
17027
17024
17002
16998
16970
16964
16952
16951
16948
16926
16914
16902
16897
3598
3597
3597
3596
3596
3596
3595
3595
3594
3594
3594
3593
3593
3593
3592
3591
3591
3590
3590
3590
1031
1031
1031
1031
1031
1031
1031
1031
1031
1031
1031
1030
1030
1030
1030
1030
1030
1030
1030
1030

这是腾讯soso给出的实际数据,另外根据从工业界的了解,像这种长尾数据现象也是非常显著的。为了能对整体广告的ctr做准确的估计,就要考虑一下这些长尾广告的准确率。

最近查阅了一些资料,发现很多都提到了降维这件事情。心里有个疑问,都在讲降维,都说降维好,但是为什么好呢?除了运算时间提高和数据存储方便之外,对模型的精度会有什么影响呢?为什么降维之后模型的算法精度上会有提高呢?

思考了一下这个问题之后,初步有了答案:(1)广告数据或者说互联网数据具有较强的动态性,因此我们更需要一个泛化能力强的模型,但是较高维的feature会导致模型的over-fitting,因此,在降维之后,能在模型的泛化能力上有所提升。(2)为什么会有这么高维度的feature呢,因为,对于样本少的广告来说,本来数据就很稀有很珍贵,所以需要把数据所包含的所有特征都收集起来,然后让机器自动学习该保留哪些该丢弃哪些,因此需要一些比较好的做特征选择的方法。

另外,对于CTR预估这个问题来说,和分类问题还是不一样的,CTR预估需要得到的是一个精确的值,而不是一个类别这样相对模糊的结果。就比如用svm来说,分类问题是算出数据点在分离超平面的哪一侧,而对于CTR来说,不仅需要算出数据点在分离超平面的哪一侧,还要求精确计算出数据点与超平面之间的距离的值。

我下一步要做的是:(1)降维的方法有哪些?(2)做实验验证是否降维真的能带来精度上的提升(3)除了降维,针对小样本,高维度数据,还要做些什么?(4)哪些模型适合high-dimension-low-sample-size(HDLSS)的情况?哪些模型不适合?

 

用机器学习来做这件事,就是一个预测的问题。首先根据训练数据得到一套参数,然后利用这套参数预测未知数据。一般来说是一个model-based到rule-based的过程。

对于广告数据来说,如果用到了ID类的特征,最后生成的特征向量维度就会非常高而且非常稀疏,因为固有属性也就几百几千个而已,其余大部分都是0,据说百度ctr预估用到的特征有百亿维。所以做ctr预估时要面对特征的高维度&&稀疏这个challenge。

所以,我打算专门针对高维度&&稀疏这个问题做研究,找出比较好的解决这个问题的方法。

为了达到使得论文所做问题既有理论创新又有实际意义,所以选择了从实际出发找问题。以上是我根据自己的一些了解总结的(具体可以参考前面几篇博文),但是由于对工业界接触有限,所以视野比较狭窄,因此提取出来的问题也许会有很大问题,甚至只是我个人猜想罢了。因此,希望能得到工业界的前辈们的指点。也希望能得到学术界前辈们的指导。非常感谢!

 

—————————-分割线—————————

实现了一个LR的程序,MLE做参数估计,梯度下降法做优化。数据时刘鹏老师在北大的计算广告学课程提供的数据,我处理了一下原始数据,用稀疏特征向量表示feature,一共267维。训练数据16万个样本,测试数据62532个样本。结果…预测出来的值都为0…..后来查了一下原因,由于点击太稀疏,在计算平均损失函数值的时候,使得损失值全部为正数,导致权重系数w变化时一直在减小……

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

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;

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

 

 

先到这里。