DMLC和Petuum并行计算框架的搭建与使用

        DMLC的ps-lite以及Petuum的bosen两者都是目前比较流行的Parameter Server计算框架的实现,PS(Parameter Server)计算框架在并行机器学习系统中被广泛使用,之前并行机器学习领域比较流行的是基于MPI的All Reduce计算框架,AR(All Reduce)计算框架下,算法需要严格同步,节点之间需要等待; 而PS不需要严格同步,通过一些方法在一定的Error Bound条件下完成异步训练。
        由于是在实际中用到并行模型进行CTR预估训练,因此选择基于ps-lite的difacto以及基于bosen实现的mlr,前者是并行版本的factorization machine, 这个模型也是我在2014年参加Cretio在kaggle上举办的广告CTR预估竞赛时用过的,取得了17名的成绩,现在也被越来越多的公司在实际中使用;后者是并行版本的logistics regression模型,这个是最普遍被使用的模型。
     1 difacto
     编译dmlc-core,编译之前要将difacto_dmlc/dmlc-core/make/config.mk中关于使用HDFS的选项设置为:USE_HDFS = 1
      编译ps-lite, ps-lite依赖6个第三方库:gflags glog protobuf zmq lz4 cityhash。 由于所使用的机器不能连接外网,因此我先将这六个库先下载到ps-lite文件夹下,并且修改difacto_dmlc/ps-lite/make/deps.mk文件,避免在编译之前将已经下载好的第三方库给删除了。
      编译FM模型,进入文件夹:difacto_dmlc/src/difacto,执行命令:make即可,得到的可执行文件在build文件夹中。
    使用yarn提交job, run_yarn.sh内容为:
    ../../dmlc-core/tracker/dmlc_yarn.py –jobname dmlc_wxs –vcores 1 -mem 512 -n 2 -s 1 build/difacto.dmlc guide/dmlc.fm.conf –log_dir=log –sync_timeout 500 -alsologtostderr -v 10
     其中dmlc.fm.conf中内容为:
     train_data = “hdfs:///dmlc/data/agaricus.txt.train”
     val_data = “hdfs:///dmlc/data/agaricus.txt.test”
     model_out = “hdfs:///dmlc/data/out/”
     max_data_pass = 3
    在执行sh run_yarn.sh之前,记得将训练数据和测试数据放到dmlc.fm.conf中指定的路径下。
     过程中遇到过以下几个问题:

     (1)重新编译dmlc-core会遇到错误提示:
    In file included from src/io.cc:17:0: src/io/hdfs_filesys.h:10:18: 致命错误:hdfs.h:没有那个文件或目录 #include <hdfs.h>
  解决方法:设置HADOOP_HDFS_HOME的环境变量为:export HADOOP_HDFS_HOME=/home/worker/xiaoshu/hadoop/hadoop-2.7.1即可。
    2 mlr:
    第一次使用petuum是在2014年的6月份,当时在360搜索广告算法组实习做广告CTR预估。可以用三种方式使用petuum提供的算法:1,Local: 数据放在local机器上,单机训练;2,HDFS + ssh:将数据放到hdfs上,使用ssh提交job并行训练;3,HDFS + YARN,将数据放到hdfs上,使用yarn提交job并行训练。
     2.1  local模式:
        修改launch.py中train_file, test_file, output_file_prefix(输出路径),执行./launch.py
     2.2 HDFS+ssh模式:
        进入文件夹:petuum/bosen, 将defns.mk.template文件名修改为defns.mk,并将其中关于HDFS选项uncomment:  HAS_HDFS = -DHAS_HADOOP # Uncomment this line to enable hadoop。然后make 即可。
        随后进入:petuum/bosen/app/mlr文件夹,执行make命令编译mlr模型。
        进入petuum/bosen/app/mlr/script文件夹,修改launch.py中的几项配置:
   “train_file”: “hdfs://10.101.2.88:9000/user/worker/petuum/mlr/covtype.scale.train.small”
       “test_file”: “hdfs://10.101.2.88:9000/user/worker/petuum/mlr/covtype.scale.test.small”
        “output_file_prefix”: “hdfs://10.101.2.88:9000/user/worker/petuum/mlr/out”
     2.3 HDFS+YARN模式:
        需要用到launch_on_yarn.py和run_local.py这两个文件,只需要修改 run_local.py中的某些配置就可以:
   “train_file”: “hdfs://10.101.2.88:9000/user/worker/petuum/mlr/covtype.scale.train.small”
    “test_file”: “hdfs://10.101.2.88:9000/user/worker/petuum/mlr/covtype.scale.test.small”
    “output_file_prefix”: “hdfs://10.101.2.88:9000/user/worker/petuum/mlr/out”
        然后执行:./launch_on_yarn.py
       遇到的一些问题:
    (1)copy到新机器上直接运行./launch.py,会出现:
        /home/worker/xiaoshu/petuum_local/bosen/app/mlr/bin/mlr_main: error while loading shared libraries: libboost_thread.so.1.58.0: cannot open shared object file: No such file or directory
        重新make就行了。
    (2)执行./launch_on_local_with_hdfs.py
      重新在boson中make,成功;然后在mL中make,提示/usr/bin/ld: cannot find -lhdfs:
      进入/home/worker/xiaoshu/hadoop/hadoop-2.7.1/lib/native,里面有libhadoop.a libhadoop.so    libhadooputils.a  libhdfs.so libhadooppipes.a  libhadoop.so.1.0.0  libhdfs.a         libhdfs.so.0.0.0。
     执行:sudo cp * /usr/lib, 并执行sudo config生效
    (3)在执行./launch_on_local_with_hdfs.py,提示:Environment variable CLASSPATH not set! getJNIEnv: getGlobalJNIEnv failed F0810 04:20:17.638351 39658 hdfs.hpp:185] Cannot connect to HDFS. Host: 10.101.2.88, port: 9000
      执行:export CLASSPATH=`hadoop classpath –glob`:$CLASSPATH;然后即可成功执行./launch_on_local_with_hdfs.py

Hadoop 集群安装过程

        最近研究并行机器学习并将在工作中用来训练CTR模型,因此申请了3台机器(ReadHeat系统),准备把目前比较流行的Parameter server并行计算框架搭建起来,由于会用到HDFS和YARN,因此先安装Hadoop集群,其中一台机器作为master,其余两台机器作为slave。。
    这里初步记录一下搭建Hadoop环境的过程,也欢迎大家提出意见和问题进行交流。
一,环境设置
    1,安装Java,执行命令:yum install java,然后通过whereis java命令可以看到idk所在的路径。
    对三台机器分别进行环境变量的设置:
    有两种方式:
        对所有用户生效:sudo vi /etc/profile,添加
        export JAVA_HOME=/usr/local/jdk1.7/
        export PATH=$JAVA_HOME/bin:$PATH
        然后:  source /etc/profile
        只对当前用户有效:sudo vi ~/.bashrc,添加:
        export JAVA_HOME=/usr/local/jdk1.7/
        export PATH=$JAVA_HOME/bin:$PATH
        然后source ~/.bashrc
    2,修改hosts文件(在三台机器上都进行下面的操作)
        sudo vi /etc/hosts
        添加(或者修改):
        10.101.2.88 master
        10.101.2.89 slave1
        10.101.2.90 slave2
        IP和hostname之间空格分隔。
      3,修改hostname文件(在三台机器上都进行下面的操作)
        sudo vi /etc/hostname
        在master主机上此文件中内容修改为:master
        在slave1主机上此文件中内容修改为:slave1
         在slave2主机上此文件中内容修改为:slave2
      4,ssh免密码登录:
        说明:master必须能免密码登录slave1, slave2, 并且要能免密码登录本机。
        ssh-keygen
        ssh-copy-id worker@10.101.2.89(slave1)
        ssh-copy-id worker@10.101.2.90(slave2)
        cat ~/.ssh/id_rsa.pub>>~/.ssh/authorized_keys(如果authorized_keys中已经有master的rsa,一定要先删除)
二, 安装Hadoop
    1, 下载hadoop-2.7.2, 解压到master机器的任意一个文件夹中
        cd hadoop-2.7.2
        mkdir hdfs;
        mkdir hdfs/name;
        mkdir hdfs/data;
        mkdir tmp
    2, 修改配置文件:
        2.1 ,进入hadoop-2.7.1/etc/hadoop文件夹,core-site配置文件如下:
    <configuration>
    <property>
         <name>hadoop.tmp.dir</name>
         <value>/home/worker/xiaoshu/hadoop/hadoop-2.7.1/tmp</value>
     </property>
     <property>
         <name>fs.defaultFS</name>
         <value>hdfs://master:9000</value>
     </property>
     <property>
        <name>fs.hdfs.impl</name>
        <value>org.apache.hadoop.hdfs.DistributedFileSystem</value>
        <description>The FileSystem for hdfs: uris.</description>
     </property>
</configuration>
    2.2,hdfs-site.xml配置内容如下:
<configuration>
    <property>
            <name>dfs.namenode.name.dir</name>
            <value>/home/worker/xiaoshu/hadoop/hadoop-2.7.1/hdfs/name</value>
    </property>
    <property>
            <name>dfs.datanode.data.dir</name>
            <value>/home/worker/xiaoshu/hadoop/hadoop-2.7.1/hdfs/data</value>
    </property>
    <property>
            <name>dfs.replication</name>
            <value>2</value>
    </property>
    <property>
        <name>dfs.permissions</name>
        <value>false</value>
    </property>
</configuration>
    2.3,yarn-site.xml配置内容如下:
<configuration>
<property>
<name>yarn.nodemanager.aux-services</name>
<value>mapreduce_shuffle</value>
</property>
<property>
<name>yarn.nodemanager.aux-services.mapreduce.shuffle.class</name>
<value>org.apache.hadoop.mapred.shuffleHandler</value>
</property>
<property>
<name>yarn.nodemanager.vmem-pmem-ratio</name>
<value>100</value>
</property>
<property>
<name>yarn.resourcemanager.address</name>
<value>master:8032</value>
</property>
<property>
<name>yarn.resourcemanager.scheduler.address</name>
<value>master:8030</value>
</property>
<property>
        <name>yarn.resourcemanager.resource-tracker.address</name>
                <value>master:8031</value>
                    </property>
<property>
        <name>yarn.resourcemanager.admin.address</name>
                <value>master:8033</value>
                    </property>
<property>
        <name>yarn.resourcemanager.webapp.address</name>
                <value>master:8088</value>
                    </property>
</configuration>
    2.4,mapred-site.xml配置内容如下:
<configuration>
    <property>
    <name>mapreduce.framework.name</name>
    <value>yarn</value>
    </property>
</configuration>
    配置完毕之后,将hadoop-2.7.2文件夹分别copy到slave1和slave2机器上,文件夹所在路径最好路径相同。
    3, 格式化namenode:
    只在master机器上执行:
    (格式化之前:要在hadoop-2.7.1/重新创建hdfs文件夹)
    ssh master ‘/home/worker/xiaoshu/hadoop/hadoop-2.7.1/bin/hdfs namenode -format -clusterId cluster1’
    4,启动namenode,datanode和resourceManager、nodeManager
    4.1 启动namenode:
    在master上执行:
    ssh master ‘/home/worker/xiaoshu/hadoop/hadoop-2.7.1/sbin/hadoop-daemon.sh start namenode’
    4.2 启动slave1上的datanode:
    在master上执行:
    ssh slave1 ‘/home/worker/xiaoshu/hadoop/hadoop-2.7.1/sbin/hadoop-daemon.sh start datanode’
    4.3 启动slave2上的datanode:
    ssh slave2 ‘/home/worker/xiaoshu/hadoop/hadoop-2.7.1/sbin/hadoop-daemon.sh start datanode’
    4.4 启动YARN:
    在master上执行:
    ssh master ‘/home/worker/xiaoshu/hadoop/hadoop-2.7.1/sbin/start-yarn.sh’
    最后,在master上输入jps,看到:
    5863 ResourceManager
    5657 NameNode
    5545 Jps
    在两个slave上输入jps看到:
    37136 NodeManager
    37009 DataNode
    86469 Jps
    出现以上结果表明hadoop集群已经安装成功。
    master节点上有NameNode,slave节点上有DataNode说明HDFS已经正常启动;master节点上有ResourceManager,slave节点上有NodeManager,说明YARN已经正常启动。

2014年总结

最近还是在继续做DNN,针对的问题还是广告CTR预估。DNN model理论方面的资料实在太少,看到的更多是一些pre-trianing这些的,而且大部分都是做图像,文本,语音的。所以干脆只关注如何求解,也就是如何优化DNN,调研了一些SGD方面的paper,重点看了Tong zhang的paper,不过我觉得针对非凸优化,那些方法不一定可行,先继续研究研究再说吧。
中间参加了一次面试,有些总结:1,我之前从不关注feature的,觉得那没啥意思没什么技术含量,经过面试才发现,对方还是很关注feature engineering的,特征的人工选择,如何选择,选了哪些作为feature等等。这个以后要注意,多玩数据,研究研究feature。2,对于model,我最开始学习机器学习时是很看重这个的,但是把李航那本统计学习方法的看了几遍,公式也推了一遍。以及后来的prml(这本书可真不好懂,最近在和几个小伙伴一起读第二遍)和ESL,也都看了。后来发现实际工业界用的也就那几种而已,完全没有必要个个都搞的很深(但是最好要都熟悉或者了解),而且我有时候觉得搞模型没啥意思啊,来个新数据,加个圈,就提出了一个新model,对我个人来说,不是很感兴趣。但是面试时会被问到不同的model的优缺点,为什么好为什么差,之前没仔细考虑过,以后要考虑清楚为什么DNN要比LR或者GBDT效果更好。估计要找不少paper,又会有很多时间是在做无用功,我心理上已经做好了准备。3,我之前看的很多的优化算法也有问到,owlqn这个我当时靠它把优化算法给串了一遍,结果面试时有些忘记说了,还是因为没有经常用到吧。以后要经常总结,多回顾。其实我觉得优化算法才是工业界可能做的最多的事情,model不会轻易改,也不好改,太难了;但是优化算法是可以尝试实验的,有数据有计算资源,肯定可以玩玩。
最近也看了google的FTRL,也说说自己的想法吧:一连串的paper读下来,发现牛人也是要站在巨人的肩膀上的,没有什么是突兀出现的,这也给我了一些启发,我一直想做好非凸优化这件事,那我就需要把相关paper串起来找灵感,而不是拍脑袋!另外,google的这篇paper也验证了工业界易算法不易做model的情况。
可能要关注的如下:
首先,LR,GBDT,DNN这三者在广告ctr预估上的优越性对比,模型的优缺点,为什么好为什么坏,这个是重点要掌握的,切记;
其次,FTRL,sgd,L-BFGS,owlqn,cdn,conjugate gradient descent,重点关注SGD以及各种变形。
最后,模型上的LR,GBDT,dnn,navie bayesian,maximum entropy,knn,SVM,LDA以及阿里的MLR,百度的DANOVA,实在太多了,只重点关注几个,比如LDA,现在我几乎不用了,但是也怕面试会再被问到。
以后打算重点关注large scale machine learning,这个信息量很大,绝对不是只扯model.加油!

附上之前关于deep learning的想法:

我的疑问:为什么大家都在讲deep learning?deep learning是什么?不就是多层的神经网络吗?多层神经网络不是早就有了吗?怎么突然大家像是找到了宝藏一样疯狂?不讲deep leaning你都不好意思和别人说你做机器学习的……
神经网络早就有了,多层神经网络也肯定早就出现过,但是在模型训练时 浅层还好,比如2层的(不算输入层,即只有输入层,单隐藏层,输出层的结构),使用BP方法训练,可以有不错的效果,可是,层数若是增加几层,比如弄个7,8层的隐藏层,使用BP方法训练时就会出现一种叫“梯度弥散”的问题,也就是说,在远离输出层的隐藏层训练其权值时,模型输出值与真实值之间的误差已经不能有效的指导权值的更新(这是BP算法自身性质造成的)。所以,多层神经网络效果不太好,因为没法很好的训练。
后来,针对这种深层网络,有人提出了新的训练算法,抛弃了BP方法。新的方法不再把整个网络中的权值作为一个整体同时训练,而是提出greedy的训练方法逐层训练:首先,只针对输入层与第一隐藏层进行训练,可以用auto-encode,rbm等等算法;然后,固定输入层,使用第一隐藏层与第二隐藏层进行训练,算法同上。依此类推…每一层的学习都是无监督的self-learning(自学习)也就是自己学习自己,至于能学出个什么东西来,我也不知道…应该是和数据和选定的算法有关吧。最后,在输出层与最后一层隐藏层训练时输入label做有监督学习,并根据训练误差做反向fine-tune(微调),具体怎么微调的,我也不知道。。。
我的个人观点:deep learning相对于神经网络的改进主要在以下几个方面:(1)由之前的作为整体训练改进为逐层贪心训练;(2)由之前的基于优化的思路(比如BP中的梯度下降求解)改进为即可有优化思路(比如auto-encode等)也可以有概率推理思路(比如RBM等)。
deep leaning是否有效的关键:(1)greedy训练过程中所选定的算法,比如,对某一个问题,auto-encode好还是RBM好?(2)据说deep leaning不适合解决离散信号(离散值)问题,而适合解决连续信号(离散值)问题。
另外,deep learning不一定单指deep神经网络,deep的思想可以用在其它模型中,而且貌似还挺有用。

思考两个问题:

(1)为什么要降维?降维的好处在哪里?降维前与降维后效果有什么差别?

(2)需要如何处理广告数据的feature?找出与图像的“同构”?还是把图像与广告数据都映射到一个新的“空间”,再找其中的关系?

2013年总结

大概从去年9月份(研一开学)开始接触机器学习。到目前为止也有一年多,最近身心无力,有一种严重的挫败感。

最开始的时候关注搜索引擎,大概在去年8,9月份吧,最初是从北京理工大学的一篇论文开始的,那篇论文貌似是发表在2010年的KDD,主要讲的是根据标签密度抽取网页内容的方法。也是偶然从一个QQ群里看到有人讨论这篇论文,然后就拿来读了读,用C++写了网页爬取的程序,爬了一些新浪博客的内容,又用C++简单实现了一下论文的方法,先调用一个xml库将网页解析成DOM tree,然后获得tag之间的内容,密度值设置30左右时效果最好。后来就没有继续在做,主要是觉得太机械,不够智能。现在挺怀念那段时间的,虽然什么都不懂什么都不会,但是有很多时间可以尝试去做自己感兴趣的事情。而且那时候心态一直很好,什么问题都敢问,即使被人嘲笑了也觉得无所谓,就觉得自己很差被别人嘲笑也没什么,还有很多时间去学习,去做自己喜欢的事情。

九月份研究生开学,最初的一个月我一直处于恍惚之中,不是精神恍惚,是有些不敢相信现实:在社会上晃悠了将近2年的我,怎么现在又坐在教室里了?呵呵,现在想起来自己挺搞笑的。最初的一个月,几乎没怎么睡觉,每天都很亢奋,晚上睡的很晚,早上起得很早,从网上查机器学习的基本模型算法,计划一个个先学习一遍。花了将近一个月学习决策树,主要时间花在了看懂源码上了。现在觉得不该那么学习,方法不对,特别是要读懂上千行的代码,感觉有些不值得。

后来,爬微博上的内容,从网上搜集了一些资料,模拟登录新浪微博,以浏览网页方式爬取微博内容,用python写的,不过大部分代码都是从网上找的,根据微博ID一个一个爬,从文件中读取ID,发送命令,获取返回字符串,保存到硬盘里。微博ID是从梁斌博士那里copy的,那天上午我跑到清华,但梁博士说不在学校,然后我就在清华东门附近晃悠了一中午,午饭吃了肠粉,真不好吃,扔了。下午找到梁博士,copy,走人,在此向梁斌博士表示感谢。。话说我看到一个牌子上写搜狗与清华联合实验室什么的,感慨他们的条件真不错。记得临走时梁斌和我说:这些数据你拿着,预祝你在科研上能取得进步!唉,很可惜,自己并没有在科研上有什么进展。由于实验室没有服务器,我的小破笔记本又太慢,所以每个ID只爬取45条微博,我算了一下,如果只用笔记本的话,要爬到第二年8月份..于是我到处找服务器用,但是没找到,后来找到2个同学借用了实验室台式机。爬回来的数据占用空间太大,又用C++写程序提取内容,本来打算用之前实现的北理工论文方法的,但是效果不太好,微博本来就140字,一不小心一条微博就被丢掉了,所以就基于标签匹配的方式提取内容,主要是有转发的情况不好处理,不过,调调程序,总算搞定了。大概持续了将近一个月吧,也不知道爬回来的数据怎么用,就没继续做了。现在想想,那个时候还处于原始阶段,也就只能弄个爬虫基于规则写个程序什么的,太简单太原始,太傻太天真。

中间去过中科院信工所面试实习生,主要是想趁导师不在出去实习学点儿东西,也是想尽快做“真正的机器学习”,面试时问了我关于爬虫的事,貌似还有一些基本的机器学习算法的问题,一切顺利,但是问到实习时间时出问题了,时间达不到要求,然后就没去成。记得我还提了一个关于分类的想法,大概意思是:特征处理成向量形式,从前向后扫描时记录1所在的位置,对于每条样本,计算一个sum += exp(index_i),然后再根据每条样本计算得到的那个sum数值分类…,不过都是瞎想的,不可行。面试时信工所老师的意思是让我去做爬虫方面的事情,后来虽然没去,不过我细细想了一下:为啥是让我做爬虫?因为我当时的能力貌似只能做爬虫…然后我就想,不能这样,我得做些更有技术含量的事情。

回到学校后继续学习机器学习算法,李航的《统计学习方法》我是从前往后看的,特别是SVM那一章,不容易看懂,我就推公式,也泡图书馆查资料…推着推着,发现自己已经不是在学习机器学习的事情了,已经完全陷入了数学的包围圈,记得当时在图书馆读一本叫做least square什么什么的书,突然我又迷茫了:这样是不是不太好啊,这成了学数学了啊。我不讨厌数学,但是我更喜欢应用数学…于是,在20天左右之后,我又不知道该怎么办了。我焦虑,失眠,甚至有些失望,我每天呆在寝室学习,晚睡早起,目的就是想多学些东西,把我自大一以来浪费的时间,浪费的知识不会来,可是现在呢,感觉不到自己的进步…

快期末考试了,我继续东一下西一下的学习机器学习,看优化算法方面的书,把本科时的数值分析也重新翻了出来。后来我觉得可能是因为我没有实际的应用场景,所以不知道具体该学什么,所以我决定找个应用方向,当时是从自然语言处理,推荐系统,数据挖掘三个方向选的,思来想去,选择了推荐系统。然后开始学习LDA,读blei的那篇经典论文,和北航一个博士师兄一起推导论文中的公式,看源代码,关于变分推理那部分的代码,真是难,还有梯度求导,花了好几个星期,期间还要参看其它论文,总之,又是一段时间的亢奋,记得那时候我经常每晚快12点了才从北航骑车回学校,冻得要死。后来寒假放假,室友都走完了,我还是每天早起晚归,还好北邮离北航不算太远。

年后,导师从国外回来了,要派我去公司实习,我是真不想去,想继续跟着北航博士师兄做事情,后来不得不去,我抱着试一试的态度过去一看,不到20人的公司,老板说,我们的技术是“国内领先的”,听到这句话我已经明白了…然后就是找导师谈我的想法,说我已经做了很多努力,想在机器学习这条路上走下去,花了不少时间和精力,导师同意了,所以我必须回实验室。记得是今年(2013年)的3月22号,我搬到了实验室,我说打算做推荐系统,导师就说让我要找到新的问题,要多看论文,可是我不知道怎么去找到新的问题,导师告诉我说,就是多看论文,你做的东西我也不懂,全靠你自己了。然后我就到处搜集论文,到处查资料,先行综述看起,看了一些论文,做了一些PPT,然后,问题还没有找到,我也很着急,可是也没办法, 我问导师:关于如何找到新问题,如何读论文,有没有一套方法论的东西?导师说没有。那好吧,我实在没办法了,继续读论文吧。然后发现online learning应该是个不错的方向,所以就查资料,关于online learning的一些算法,以及reinforcement learning的资料,还找到了VW的源代码去看,可是,我又陷入了一个误区,看什么源代码啊,要发现问题思考问题啊,唉,时间就是这么浪费的…

5月份的时候,我觉得推荐系统不好找到新问题,我觉得做个比较新的方向吧,应该容易找到新的问题,然后我就关注计算广告学,看刘鹏老师的视频,查相关资料,读相关论文。期间参加阿里实习生面试,通过了,6月底了才让去入职,话说效率好低。去了公司,亢奋,我每天6点就起床,先坐公交再坐地铁,7点10分左右能到公司,比别人早去2个小时。早班地铁上人少,我就拿起论文看。每天这样,一直到实习结束。实习的内容就是读读论文,讲讲论文,大部分都在读吧,一共讲了3次,然后就是一些小项目小程序,接触到了hadoop, 写了hadoop job, 对展示广告有了深入的了解,也做了一些实验。最大的收获是改掉了之前拿起论文就开始推导公式的坏毛病,都不看论文是解决什么问题的,这和之前的经历有关,之前做推荐方面的事情的时候,由于是跟着别人学习,所以自己just do, 没有问过why。也就是没有独自思考问题的能力。实习期间向刘鹏老师请教过,刘老师说E&E问题还有的搞,但是比较难,可是,我正是那种明知山有虎偏向虎山行的人,我一听比较难做,又亢奋了,就搞E&E了!所以整个暑假除了ctr预估方面论文,就是E&E的论文,快开学的时候,开始coding,打算把baseline实现了。开学后我把想法和导师一说,导师说只是个比例问题,还是不要搞了,所以就没继续做了。

回到实验室,重新开始关于ctr预估方面的学习,暑假的东西真是白做了,好痛心。又是一顿狂搜集资料,可惜的是这方面资料比较少。后来我一想,先实现baseline吧,就是线性模型logistic regression。找来kddcup 2012 track 2的数据自习研究,给自己的笔记本添了内存条,达到16G的土豪配置。然后学习MPI,Redis,处理数据,用C++编程…5900万的维度,1100万的样本,并行logistic regression,SGD的并行,读了AUC的资料,用C++写了个计算AUC的程序,一算,AUC最好才0.55,我还不如扔了算了……

过去的一年,我失败的一年,每天很忙碌,但是过的很乱,我现在很受伤,很受打击,最让我觉得毫无意义的是收集资料的时间,有时候想解决一个问题,论文就在那里,可是我却好不容易才找到,这些不是只靠输入关键词就能找到的论文,是最浪费我的生命的!我很羡慕那些有人指导有人带领的同学,他们的师兄师姐随手指定一些论文,就可以安心去读了。而我却还要一边读一边判断是否是我需要的,虽然有些是可以通过introduction或者conclusion直接判断的,但是有些是开始觉得是我想要的,然后看着看着就发现不是了,所以就丢掉继续找下一篇…就这样,TM的我的时间就这样没了!!!我到现在也没能仔仔细细认认真真读过超过20篇论文。时间总是在忧郁不觉中慢慢流逝,到头来什么也没得到。我有不少书,凸优化,PRML,MLAPP,每一本都是读一些,或者跳跃着读,从来没有系统的完整读过一本。

到现在我突然觉得自己一无所获,一无所有,搞了一年的机器学习,感觉还不如别人天天没事儿刷刷题。但是我不后悔自己的选择,只是,接下来的一年要改变学习策略了。从现在起,有一年的实习时间,如果能找到合适的实习机会,就继续把全部精力放到机器学习这件事,继续做自己喜欢的研究性学习。如果不能找到合适的实习机会,那就把时间放在安心读书上,首先要做一个合格的码农。

未来的计划一是花时间继续刷题,而是认真读书PRML,MLAPP,convx optimization(感觉不如numerical optimization好啊),matrix analysis…去TM的论文,再也不会像以前那样花大量的时间就为了找到一篇论文!受够了!!!

百度计算广告学沙龙笔记

夏粉的分享:

        首先解释计算广告学,追求的是,在一定环境下用户与广告的最佳匹配,这里的一定环境下,包括用户的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

早上好

到公司了,先喝杯咖啡,加油!

记录一下之前签到时间:

1,Published on: Dec 10, 2012 @ 6:45: 新的一天,开始追赶的脚步,加油!

2,Published on: Dec 11, 2012 @ 7:18: 继续前行!加油!

3,Published on: Mar 29, 2013 @ 9:43 :好久没写博客了,这段时间一直在看论文,我在想以后要把读论文的心得写下来,算是做个笔记吧。

4,Published on: Mar 31, 2013 @ 6:40

5, Published on: Aug 6, 2013 @ 2:36: 睡觉了,早上还得6点起。

 

如何读论文

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

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

之前,我看论文重点在模型以及算法公式的推导,总会针对论文中的公式推导来推导去,一定要把每个步骤都搞清楚心里才踏实。这样的做法,第一,很费时间,第二,会陷入局部而不知全局,也就是不能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;