计算广告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变化时一直在减小……

4 thoughts on “计算广告ctr预估的想法”

  1. 博主写得很好,很多东西可以借鉴学习的。
    我目前也在机器学习的初步了解阶段,我想问一下,假如样本量很少,特征值比较多,有什么办法可以规避您文中提到的预测结果为0的问题?

Leave a Reply

Your email address will not be published. Required fields are marked *