我用过的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曲线形状判断等等。特征工程是和业务和数据紧密结合的,关于这方面的工作,有很多方法可能要真正做业务的时候才能具体情况具体对待,所以在这里就不做深入拓展。策略是和业务结合最紧密的,是最直接影响业务指标的,所以有不少部分策略都是在指标出来之后做的应对方案。

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

               

基于MPI的分布式LR、FM、FFM模型

        MPI版本的分布式LR模型是最先实现的,我在读研一时就有这个打算,当时就想着用自己实现的分布式模型做CTR预估,直到去年才真正实现。将代码实现的一些细节简单记录一下,方便以后继续优化。代码地址在:https://github.com/xswang/Field-aware-Factorization-Machine-mpi

       程序启动后会根据参数启动对应的进程数,每个进程功能是等价的,都要负责计算,不过会指定某个节点做参数的allreduce, 在代码中我指定了rank 0。

       hosts文件中是集群IP地址。

       n2n_config.h是配置文件,用来设置是否online,FTRL的各种参数等等。

       main.cpp主要就是MPI rank设置,程序启动过程。

       param.h是参数的设置,基本不需要改动。

       predict.h是计算AUC的,是个分布式来算的。基于MPI实现的可分布式计算AUC的代码在这里:https://github.com/xswang/AUC-caculate-mpi , 就不再单独用一篇笔记解释代码,一般每人关注AUC的算法细节,只需要记得在算ROC曲线下面积时按纵横轴scale就行了,剩下的就很好理解。

       learner中提供了几种优化算法,主要是FtrlLearner,在这个算法实现中,通过一些方式可以在实现LR模型的同时,也实现了FM和FFM模型。OWLQN没在这里实现,可以看这里:https://github.com/xswang/logistic-regression-owlqn-mpi/blob/master/src/owlqn.h,不过这个并行的OWLQN并没有有来的及做正确性测试,所以它目前是不能用的。

       在ftrl_learner.h中update_w()函数和update_v()函数,其中update_w()函数就是标准的参数w的更新算法,update_v是针对FM和FFM模型的更新算法,在第98行,如果用户配置只是用LR模型,直接break。第102行,f是FFM模型中每个特征拥有的latnet factor vector个数,如果用户只是用FM模型,则将f设置为0,也就是每个特征只对应一个latent factor vector,这针对这一个vector更行,否则将更新特征对应的所有的latent factor vector.

       在ftrl_learner.cpp中,run()函数是入口,根据配置文件选择是哪种训练方式。无论哪种方式,都使用了线程池,多线程之间需要同步的地方通过加锁实现。allreduce_gradient()函数主要负责梯度的收集,allreduce_weight负责模型更新和发送。整个过程体现了星型拓扑结构:rank 0作为主节点,收集梯度并更新模型之后,将参数发送给其它节点。

       在代码实现时用到了openblas科学计算库已经一个修改过的线程池。

       在代码写完之后,我使用了三台机器对LR和FM模型进行了测试,根据测试集AUC变化情况,FM的ROC曲线在最开始更陡峭,但是最终和LR差不多,也就是FM能更快的学习,但是最终结果并不明显比LR好,这可能也和当时没有充分调参有关。不过至少说明这个分布式FM模型代码是可用的。FFM模型并没有测,主要是速度太慢。

       比较遗憾的是并没有对MPI版本的LR和ps-lite版本的LR进行对比过。

       目前Parameter Server框架比较流行,也许没人会再用MPI同步训练模型了。LR模型基本上都已经在各个公司上线,FM也有不少公司开始探索,基于ps-lite的FM和FFM模型是我的下一个计划。2014时用DNN做CTR预估还是个很神秘的事情,然而现在也被打破了神秘感,不少公司都在探索。不过目前DNN模型还没有一个很好的离散特征值输入的分布式训练系统,线下训练可能会比较慢,上线也比较困难。

       

分布式FTRL优化算法的实现

之前实现过Parameter Server框架下的分布式FTRL优化算法,用的是DMLC的ps-lite。在PS架构下,集群分为worker、server、scheduler三种线程。其中worker负责梯度的计算,server负责参数的更新和分布式存储,scheduler负责集群节点的管理和状态监控。将代码实现简单介绍如下:

        1.  在main.cpp中完成启三个线程的启动过程。

         2. 在worker.cpp中完成梯度的计算并向server 推送算得的梯度。其中,(1)oneline_learning_threadpool是做在线学习用的,数据流主要是从kafka中读取,所有数据只训练一遍;batch_learning_threadpool是做批量学习用的,数据主要是从磁盘或者HDFS中读取,训练数据可以反复训练多次。(2)calculate_batch_gradient_threadpool负责根据样本计算梯度,在计算过程中worker和server通过ps-lite提供的pull/push接口拉取模型参数和推送样本梯度值。针对梯度计算,过程如下:首先,读取一批训练数据,代码328行至339行得到该批次数据的所有特征ID:all_keys,340行至343行进行过滤得到唯一的特征ID,348行从server中拉取所需权重,且权重是按照特征ID值大小排序的。352行至363行,根据pull得到的特征权重,计算该批次中每条样本的w*x乘积,这里有个巧妙的方法可以在O(m)时间复杂度完成计算,最开始的做法是把pull回来的数据放到map中,这样需要m*O(logn)时间复杂度。经过试验对比,O(m)时间复杂度的算法速度快了很多。我曾经尝试过其它的hashmap来替代std::unordered_map,效果都没有明显提升。

        3. 在server.cpp中完成模型的更新,根据FTRL公式,server收到worker推送过来的梯度之后进行一系列的计算更新z和w,从而完成模型的更新。156行的Push函数是ps-lite会调用的回调函数,也是用户实现模型更新逻辑的地方。

        4. dump.cpp函数将二进制的模型文件转成明文。

        5. 在io文件夹中,io.h是所有io接口的声明。load_data_from_local.cc从磁盘读取数据,load_data_from_kafka.cc从kafka中读取流式数据。其中load_minibatch_hash_data_fread函数采用fread函数读取数据,比用std::cin读取一行之后再分割的方法,在速度上快了近8倍。

        代码地址在:https://github.com/xswang/Field-aware-Factorization-Machine-ps ,之前是在三台机器上测试过分布式版本的,目前修改成单机版,如果要改成多机版也非常方便。

TensorFlow的op placementce

关于op在device上的placement策略,目前还没有比较好的方法,TensorFlow目前也只是用了比较简单的策略,细节如下:

   1,用户明确指定了设备号,就尊重用户的意愿,例如:当代码中有with tf.device(“/job:local/task:0/gpu:0”):或者with tf.device(“/job:local/task:0/cpu:0”):

时,就把对应op放到用户明确指定的设备上去。

   2,除了source和sink的其它节点,优先分配设备等级较高的,其中GPU等级高于CPU,因此一般都会被分配到GPU:0。但是有以下三种例外:

2.1,generator节点,也就是0个输入且只有1个输出的节点,这样的节点会被放置到和输出节点相同的设备上。

2.2,元操作节点,例如reshape,该元操作节点放置在被操作的节点上。

2.3,明显需要在CPU上执行的op。

 

   以上就是TensorFlow的placement算法,从以上可以看出,如果想用机器上的多个GPU卡,需要用户明确指出,不然会默认用编号为0的GPU卡。

   在第二步中,在处理2.1和2.2两种情况时,用并查集算法找到整个计算图中的连通分量,节点之间的关联关系就是根据2.1和2.2得到的。找到连通分量之后,有两种处理方式,(1)已知连通分量中某个节点放到哪个设备,就将该连通分量中的所有节点都放置到该设备;(2)连通分量中所有节点都没有被指定设备,则选择设备级别最高的设备放置。

TensorFlow与mxnet分布式框架对比

Mxnet和TensorFlow是目前国内最流行的两个开源分布式深度学习训练系统, 两者在设计上有些不同.

mxnet是Parameter Server架构, server和worker是两个最主要的进程,另外还有个负责集群管理的scheduler进程。server负责分布式存储模型参数,worker负责计算,且worker之间不能直接通信,只能通过server互相影响,一般来说,mxnet常用来做数据并行,每个GPU设备上都训练完整的DL模型。TensorFlow主要由client,server,worker三种进程,它虽然也可以实现parameter server的功能,但它计算节点的通信方式并不是只能靠server来完成,TensorFlow的woker是可以互相通信的,可以根据op的依赖关系主动收发数据。

另一个不同点是关于op和device的对应,一般情况下,mxnet常被用来做数据并行,每个GPU设备上都包含了计算图中所有的op。而TensorFlow是可以由用户指定op的放置的,大部分情况下,一个GPU设备只负责某个或者某几个op的训练任务,因此,也催生了关于op placement算法的研究,Google最近发表了一篇使用LSTM模型进行op placement优化的论文,我也在知乎上回答过该论文的详细内容:https://www.zhihu.com/question/61210638/answer/188682910,那个抱着双手的老虎就是我。

这篇笔记主要对比mxnet和TensorFlow在分布式框架下的一些不同,主要包括:进程类型、如何在分布式环境下启集群、如何做初始化。

1.进程类型

mxnet tensorflow
worker client
server server
scheduler worker

2.网络通信库

Mxnet tensorflow
zmq grpc

3.进程间通信模式

Mxnet tensorflow
Worker与scheduler,控制信息 Client与server,控制信息
Server与scheduler,控制信息 Server与worker,控制信息
Worker与server,数据 Worker与worker,数据

4.通信模式

Mxnet tensorflow
消息(队列),PostOffice负责多机之间消息收发,每个机器节点上都有唯一的postoffice单例对象。 消息(std::map),Rendezvous负责多机之间消息收发。每个机器节点上都有唯一的Rendezvous对象。

5,分布式启动

Mxnet tensorflow
各节点执行相同脚本。

根据集群host配置在每个节点上分别启动worker,server,scheduler进程,并进行集群初始化例如worker和server向scheduler的注册等等。

此时集群各个节点之间通信已ready,必要的节点之间可以互相收发数据。

各节点执行相同脚本。

根据集群host配置在每个节点上分别启动client,server,worker进程。完成集群初始化例如GRPC的service启动等。

此时集群各个节点通信已ready,必要的节点之间可以互相收发数据。

  1. 初始化流程6.1 Mxnet:系统初始化是由ps-lite这个模块完成的。每个节点都有个postoffice对象,该对象在系统初始化时进行一系列操作:
    1.     在构造函数中,根据环境变量设置当前节点的
    2.     根据配置文件给worker,server,scheduler进程分配编号。
    3.     调用Van对象初始化各个节点之间的通信,包含以下几个步骤:
      • 获取role为scheduler的ip和端口地址,并建立本节点与scheduler的通信。
      • 启动一个receiveing线程用来接收remote节点的消息。
      • 发送一个message给scheduler报告自己的情况。
      • 启动一个线程用来向scheduler发送heartbeat。

    6.2 TensorFlow:

    1. 启动GRPC Server
    2. 在各个节点上分别启动一个WorkerService线程和一个MasterService线程。
  2. 消息处理

7.1 Mxnet

worker和server以及worker->scheduler、server->scheduler之间通过发送message进行通信。这些消息都会被postoffice这个单例对象负责处理。

在6.3.2中,zmq收到的消息会被放到customer的ThreadsafeQueue<Message>队列中,在customer的Receiving函数中,从消息队列中取出消息并交给recv_handle_处理。而recv_handle_函数就是KVWorker和KVServer的Process函数。

KVWorker::Process函数是worker进程的函数,只是在收到消息后执行回调,例如对pull到的数据进行计算。

KVServer::Process函数是server进程的函数,收到消息之后,调用request_handle_进行处理。request_handle_是一个函数指针,其指向的函数在用户程序中,由用户负责实现。

7.2 Tensorflow

Tensorflow中数据的发送和接收是由send Op和recv Op分别实现的, 发送的消息由Rendezvous类负责处理。

对于send Op, 首先给要发送的消息构造一个unique key,并且交给Rendezvous处理Rendezvous会根据key在自己的消息map中查找是否有对应的recv请求,如果有,就执行recv注册的回调函数;如果没有,就把<key,message>对存放到自己的消息map中。

对于recv Op, 首先给要接收的消息构造一个unique key,并交由Rendezvous处理,Rendezvous根据key在自己的消息map中查找是否已经存在所需的消息,如果已存在,就直接copy消息;如果不存在,就调用GRPC的接口向remote节点发起异步远程调用。

以上所有,都只是关于分布式框架部分的流程,不涉及深度学习模型分布式训练的业务需求,这些以后会记录下来。