Category Archives: 机器学习

我用过的CTR预估模型

        之前也想过把实习和工作中曾经用过的模型总结一下,但是由于工作的原因一直抽不出时间,最近刚好有时间做一下总结。总体上来说只是记录个大概,因为有太多东西要写了,所以有兴趣的朋友可以在合适的时间,采用对话的形式针对每个细节讨论。主要包括以下几个模型:LR,GBDT,FM,FFM,DNN,还有一些自己对分布式系统的想法。

       第一次看到工业界使用LR模型,是在阿里实习的时候,当时用它来做展示广告的CTR预估,我们作为一个业务部门使用公司内部的分布式机器学习平台,当时还是用MPI实现的。后来在百度实习,用到了LR和DNN模型,LR也是用MPI实现的,有多种优化算法可选,SGD,LBFGS,OWLQN,对于做广告CTR预估的我们来说,选用OWLQN的最多,毕竟我们对模型的稀疏性有要求,OWLQN能对带有L1正则项的目标函数进行优化。DNN用的现在比较有名的paddle,当时还没开源但是内部已经开始用了。最后一份实习在360,当时主要是探索DNN在搜索广告上的效果,由于内部没有可用的分布式深度学习系统,在经过对比之后就选择了Petuum(http://www.petuum.com/),在这里感谢一下Petuum团队的朋友们,感谢他们非常热情的回复邮件帮我解答问题,希望我那蹩脚的英文也曾给他们带来过一些欢乐。。。 主要工作是根据360搜索广告已有数据构造特征,并针对petuum系统修改源代码做一些小改动,例如改变激活函数类型、参数初始化方式等。在360实习期间和纽约大学的一个小伙伴参加了kaggle上的一个展示广告CTR预估比赛,用到了FM模型,主要还是特征的处理,特别是连续值特征的离散化处理,成绩一般般第16名。

       毕业之后在第一家公司做风险控制,用到了GBDT和GBRT模型,因为是不同的业务需求,前者用来做分类,后者用来做回归。第二家公司,先是用GBDT做新闻推荐,后来使用ps-lite实现了用ftrl做优化算法的LR模型,又使用MPI实现集成了LR、FM、FFM三个模型的系统,同时提供了SGD和FTRL优化算法,本来要再提供OWLQN优化算法,但是要测性能,OWLQN的代码写完后就没来得及测。主要目的是打算做online learning,做出来之后做过一些性能测试实验,通过观察测试集AUC,FM在初期学习速率比LR快,例如LR在40次迭代之后达到0.7,FM在20次迭代之后就达到了,但是最终的结果FM并没有比LR高,两者的结果是差不多的,这和当时没有充分调参有关。

       总体上来说,LR是使用最广泛的模型,一般是结合onehot encoding之后的特征使用,我总结它有以下几个优点:1,模型简单,可以尽管拍脑袋加特征,2,容易debug,线上出了问题很容易就能根据模型和结果定位到是哪些特征出了问题,并且可以马上采取补救措施,例如人工修改模型权重,以达到增强或者减弱某些特征对结果的影响。3,有非常多的优化算法可选择,例如SGD,CD,LBFGS,OWLQN,FTRL等等,而且这些优化算法又有各种变体,可以尽管尝试,4,繁多的优化算法中,有些算法可以有效的产生稀疏模型并使得效果不损失,这对上线非常有利,也有利于减少线上平响时间。缺点:1,只是个线性模型,不是对所有的数据都能很有效,不同的业务其数据分布都不同,有些业务的数据可能还是需要非线性的模型来学习。

       GBDT也是一个被广泛使用的模型,一般是配合连续值特征使用,它的特点是:1,特征值在不断变化,knowledge存在于数据和模型中,因此,即使模型更新频率低一些,结果也暂时不会差到哪里去,从这个角度来讲,GBDT比较“稳定”。2,非线性模型,能学习复杂的数据分布。和LR相比,他不需要那么频繁的更新模型,而且基本上不存在线上特征miss的问题,如果是LR模型,可能一天之内某些ID特征就发生了很大的变化,导致线上出现大量的新ID特征无法命中。

       FM比LR、GBDT更晚一些,它的发明者是来自德国的一个大神也就是libFM的作者。与LR模型相比较,输入给FM模型的每个特征,除了学到一个对应的权重之外,还能得到一组权重,存在于vector之中,当需要把特征a和特征b进行组合时,就把a的那个vector和b的那个vector拿来做内积,这么做的好处:1,可以自动的进行特征组合,是的模型具有更强的学习能力。2,不但能做特征组合,vector的方式还解决了特征组合后维度过大的问题。关于FM模型的数学推导,可以找到那篇论文进行学习。现在FM模型也被各个公司广泛使用了。

       FFM是FM的增强版,它也能做特征组合,而且对于每个特征,它可以得到好几个vector,例如,对于特征a它可以有v1,v2两组权重,这两组权重分别用来和其它不同特征做组合,当特征a和特征b组合时用v1,当特征a和特征c组合时用v2. 这么做的好处是,即使是同一个特征,和其它不同特征组合时是有强弱之分的,这样使得模型更“个性化”,从而得到更好的效果。关于FFM模型的数学推导,也可以参考原始论文。目前在线上用FFM的并不多,因为线上预测时平响相对较大。

       DNN模型很多人都非常熟悉了,一般使用连续值特征,否则离线训练时间难以承受。优点是:非线性,模型表达能力强,只需简单的三层就能表示任意阶的函数。缺点是:1,离线训练时间较慢,不过目前好在有TensorFlow,Mxnet这样的分布式训练系统。2,线上预测时间较长,这也是阻碍DNN被广泛使用的原因之一。

       以上LR,GBDT,FM,FFM,DNN模型,都有相关的论文可以阅读学习,最好是找到关于理论推导方面的论文进行研究。

       从最开始的LR,GBDT到后来的FM,DNN,关于这些模型在广告和推荐问题上的应用的论文也越来越多,从简单到复杂,从单模型到模型融合,比如LR和GBDT,LR和DNN,FM和DNN各种各样的模型组合方式:stacking,bagging,boosting, 相信以后这方面的论文会越来越多。

       另外就是关于oneline learning,以上几个模型除了GBDT无法做online learning之外,其它几个模型理论上都是可以的,online learning的好处是可以更快地学到用户的行为,但这会造成它的模型不太稳定,整体上来看最终结果不一定比batch learning更好。因此,一般是采用一个离线的稳定模型+增量模型的方式,这又涉及到几个问题:1,模型的更新频率;2,增量模型中新特征参数的加入方式;2,增量模型中旧特征参数的加入方式。以上三个因素会严重影响online learning的效果。online learning一般是结合特定的优化算法例如SGD,FTRL来实现的,目的是为了使得模型更新频率更快,FTRL会让得到的模型更稀疏。

       关于优化算法,对于LR模型来说,使用不同的正则项就选择对应的优化算法,L2正则就选LBFGS或者SGD,不过SGD一般很少用,L1正则就选择OWLQN或者FTRL,OWLQN是用来做batch learning,FTRL是用来做online learning,现在FTRL已经被非常多的使用了。针对FM,FFM模型,目前最常用的方式也是FTRL,而且对于这两个模型,可以分别针对w和v采用不同的优化算法,例如DMLC的wormhole中对FM模型的优化就采用了两种不同优化算法。这取决于用户是否希望v更稀疏,如果希望得到dense的v就不对v加L1约束,如果希望得到sparse的v就对v加L1约束,这要看用户是打算如何使用FM产出的v向量,是否要和其它模型组合使用等。DNN模型常用的优化算法就是SGD了,也有不少是结合分布式框架做的一些SGD优化。还有些优化算法能在模型训练过程中自适应调整学习率,这一般是在参数较多时使用,有些reinforcement learning的意思了。一般在实际工作中去研究优化算法的并不是非常多,因为它是和分布式训练系统紧密结合的,想改变一个优化算法,需要改动分布式训练系统的代码,这一般很难做到,除非分布式系统的代码就是由自己管理。所以一般情况下业务部门都比较喜欢自己来实现分布式训练系统,方便自己根据业务需求灵活定制相应的模型和算法。

       在2013年年初的时候我就有自己动手实现分布式机器学习模型的想法,当时不知道用什么手段实现分布式,后来听说了MPI,就开始研究如何用MPI实现分布式LR。当时花了不少时间在MPI的用法上,现在想想MPI只是个通信库,即使不用MPI也可以用ZMQ,也可以用socket,其实重点应该是怎么设计算法的并行方式,怎样使得整个训练系统更快更准。就像现在各种开源或者自研的深度学习训练系统一样,用什么网络库不重要,重要的是怎么设计整个分布式系统。我分别仔细研读过TensorFlow和mxnet的代码,个人认为mxnet代码解耦合模块化做的很好,结构很清晰,这可能也和我最初先研究了ps-lite代码有关,我在这篇文章中对比过mxnet和TensorFlow的分布式框架:http://www.doesbetter.com/836/。以后会记录更多的关于这两个分布式深度学习框架的对比笔记。

       在实际业务中,分为召回、排序、策略这三个环节,算法工程师大部分时间都是在做特征做策略。特征工程方面,分为几个步骤,首先是特征准备,根据实际的业务特点和数据选择出足够多的候选集出来;其次是特征处理,一般情况下是对离散值最onehot encoding,对连续值做归一化或者等频、等值离散化等等;最后是特征选择,可以看单特征AUC,也可以加新特征到已有特征集合中,可以观察单日AUC变化,可以观察多日AUC衰减情况,也可以根据ROC曲线形状判断等等。特征工程是和业务和数据紧密结合的,关于这方面的工作,有很多方法可能要真正做业务的时候才能具体情况具体对待,所以在这里就不做深入拓展。策略是和业务结合最紧密的,是最直接影响业务指标的,所以有不少部分策略都是在指标出来之后做的应对方案。

       关于以上模型的实际应用,是无法通过笔记来充分表达的,所有的工作都体现在实验过程中。也欢迎各位感兴趣的同行可以针对一些细节进行深入讨论,刚好也帮我回忆一下那些实验过程。

               

计算广告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;

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的效果很惨的原因。

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

 

 

先到这里。

建立模型与设计算法

      不知道从什么时候开始出现的现象,每当我遇到一个问题,第一件事就是要先把问题抽象一下,抽象成数学问题,猜测是属于哪个类别的数学问题,然后再考虑从这类数学问题中拿出数学方法尝试解决问题,我在想,这是不是思维定式?不知道这个习惯是好还是坏……

       前几天想了一下关于模型和算法的问题,想把这两者弄清楚,便于以后对问题的抽象。

        首先,个人觉得模型的建立和算法的设计是不一样的,当我们面对一个问题想要解决它,要先分析问题。拿计算广告学这个应用领域来说,作为publisher(比如一些门户网站Yahoo!网易等等)想要提高收益怎么办?开始分析问题,想提高收益就要有广告住在我们这里投放广告,怎样使得Advertiser(广告主)愿意投放广告呢?要使得Advertiser投放的广告有效,即有user愿意点击广告或者进一步购买广告中的商品,所以,第一步就是要提高广告的点击率,就可以简单的转化为一个CTR预估的问题。

        第一阶段分析完毕,已经定位了问题。

        其次,如何做CTR预估呢?我认为这就是一个如何建模的问题了,即为定位到的问题建立一个模型,使得其公式化,比如,我们已知Ad(广告)的一些属性,比如广告创意,大小,等等;用户的一些属性U,比如年龄,性别;用户浏览的C(网页内容)信息;可以为之建立一个模型,可以分别为ad,u,c建模p(ad),p(u),p(c),然后得到p(click|ad,u,c)=P(ad)p(u)p(c)。然后要确定点击概率的目标函数f(x)=p(ad)p(u)p(c),约束条件,例如:ad>0,u>0,c>0;至此,建模过程结束。

        现在要针对模型的学习过程设计算法,前面通过建模得到了模型具体公式,确定了目标函数,约束条件等等,现在要用算法来学习模型的参数,例如,当目标函数是max f(x),可以使用梯度下降法或者牛顿法,算法设计的目的是使得参数学习的又快又好。

        最后,是编程实现阶段,通过代码将具体算法细节变为可执行的程序在工业界应用,其中又涉及到很多技术,比如并行,多线程等等。

    建模过程中,是由思想转化为公式的过程,将实际的问题抽象为数学问题,数学公式;模型学习的过程是通过算法来学习模型参数;编程实现是将算法转化为可运行代码。

推荐系统总结。

前段时间看了一些论文,总结一下。

推荐系统分为1,content-based:用户或者商品的显式profile,比如年龄,性别,职业等。弊端:但是这些数据不容易获得。我觉得这个挺困难的,哪有那么多数据啊。

2,Collaborative Filtering:包括neighborhood model,以及latent factor model。又可分为概率CF(比如贝叶斯网络,这个没深入研究过)以及非概率CF(近邻模型就是非概率的)。

neighborhood model又分为user-based(根据同趣用户购买的商品做推荐,比如甲的好基友买了个打篮球用的护腕,于是甲也可能想买)和item-based(比如甲买了个护腕,结果发现再买个护膝就能更帅了,所以就可能再买个护膝)

latent factor model主要是基于矩阵分解的技术。关于矩阵分解的技术,数学上有三大矩阵分解技术:LU,SVD,QR。其中LU分解是将一个矩阵分为下三角矩阵*上三角矩阵(过段时间我把这个c++代码贴出来,其实实际中用不上的),主要用在数值分析中,比如用来求线性方程的解。SVD,这个貌似是推荐系统中一个经典算法,在LSA(论文在此http://www.stat.cmu.edu/~cshalizi/350/2008/readings/Deerwester-et-al.pdf)中,就是用的纯粹的SVD,之所以说它纯粹,是因为论文中用到的是纯正的数学分解方法,然后再利用SVD的分解结果。