【IT168 评论】本文根据【2016 第七届中国数据库技术大会】现场演讲嘉宾王兴星老师分享内容整理而成。录音整理及文字编辑IT168@ZYY@老鱼
讲师简介
▲王兴星
美团高级技术专家，目前任职于美团外卖，高级技术专家，负责外卖变现相关技术工作。加入美团前，任职于搜狗广告技术部，担任资深研究员，负责搜狗PC、无线联盟检索、排序等算法。所研发的特征框架、训练系统应用于搜狗联盟广告、DSP等多个产品线。曾获公司年度最佳个人、技术部犀牛、MVP等奖项。也是数据挖掘爱好者，曾获百度电影推荐大赛第一名、品友互动RTB算法竞赛Offline/Online第一名，KDDCUP2012全球第三名等奖项。
正文
大家下午好!我是来自美团的王兴星。我今天分享的主题是 《在线学习在广告系统中的应用》，首先先来回顾一下互联网广告的发展历史：
互联网广告的发展历史跟互联网的发展历史息息相关。首先看一下互联网的发展历史，最开始是门户，之后是搜索引擎。就像百度一开始跟新浪合作做搜索应用，后来独立出来做搜索引擎一样，再往后就是垂直类网站，随后是移动互联网的兴起。互联网广告的发展历史和互联网的发展历史是相对应的，门户时代的互联网广告其实是照搬杂志的广告模式，通常以Banner广告为主，搜索时代以搜索广告为主，随着垂直类网站地兴起，这部分站长有流量变现有强烈诉求，在这种情况下诞生了广告网络或RTB广告，移动广告到目前一个成功的产品是原生广告Native Ads，比如我们熟知的Feed流广告。
下面我们简单看一下搜索广告，当一个用户输入预查询文字之后，我们会反馈一个检索结果。通常来说，排在前面的都是一些商业门户，比如上图所示的京东商城。
展示广告，若你去一些地图的网站，看到一些旅游相关的信息，因为它们可能判断我们会想去旅游。
再比如，我们在搜索里面输入了一些感兴趣的东西，比如我对编程感兴趣。当我在其他网站浏览时，就可能会看到一些搜索给我推送这方面的广告，我们把这种广告称之为文字链广告或搜索词广告，这些是目前展示广告的形式。
这里也罗列了两个信息流产品，我们将广告插入到用户的流量流中，这样自然结果与商业形式上更加统一，用户体验更加好，商业结果的效果也就更加好。还有一些产品线，例如淘宝的广告，商业结果与自然结果天然就是一样的，效果会更加好。
我们再看两个典型的例子，一是搜索广告，二是展示广告，首先看建模对象，在搜索广告里，用户输入一个查询词，就会显示一个广告列表，所以建模对象是查询词和广告对，在展示广告里，还会根据用户去触发广告，所以会考虑ad，user，context三个因素。为什么搜索广告没有考虑用户呢?因为做搜索广告就会发现，query是一个非常强烈的情况，他基本能够表达80%或90%的信息，所以个性化在这之中就不是非常重要了。索引规模以数量展示方面，搜索广告通常是十亿级规模，展示广告大概是百万、千万的规模。特征规模二者大概都是从亿到千亿，当然每个公司会不太一样，综合上面几点会发现这其实是一个非常大的规模。这时就会涉及到效率问题，因为我们要做线上策略迭代，如果问题很大，框架又不能有效处理的话，就会非常影响效果。
我们简单看一下广告的投放过程，比如有两个广告主要买广告，我们会根据这些信息形成广告库，当用户在网上输入query时，我们会对query进行一些分析，然后将这些分析结果在广告库里进行检索，这样我们就拿到了广告候选集，但最终展示的数量是有些的，就会进行广告排序筛选，最终得到合适的结果。
这个过程大致可以分为这样几个阶段，我们把它称之为漏斗模型，这个名字十分形象，就像广告库有10万个广告，经过层层筛选，最终展现出来的只有3个，这其实就像一个漏斗，每一层都会进行一次过滤，这个漏斗可能会经过几个重要的步骤，第一个称之为检索，我们根据用户的query检索相关的广告，第二个称之为排序，第三步就是展现。对应各个领域也会有核心的技术，跟检索相关的通常是用信息检索和数据挖掘的方法，至于排序，熟悉的都是CTR，最后的展现和物料技术十分重要。今天主要讲的是在线学习在检索、CTR预估方面应用。
我们首先看一下CTR常见的技术方案，我们需要的因素，第一是Query，第二是User，第三是Ad，三者彼此之间会有一些组合，所以我们需要考虑七种情况，比如交互其实是不同特征象限之间的关系，可以通过人工feature学习这种关系，也可以通过模型学习这些关系。通常有两种处理方式，一种是只挖掘1、2、3象限特征，通过非信息模型学习，它的特征方程比较简单，但计算量很大。采用这种方法线上预测的耗时会稍长一点。另外人工做feature分析线性模型其中的关系，资源消耗可能会少一点，进行线上预测也比较节约时间，这对于不同应用来说影响是不一样的，比如你每天有10亿的数据和展示广告，由于规模比较大，会要求响应时间尽可能降低，这时线性模型比较适合。
传统的解决方案是Batch Learning，联盟广告每天的展示大概是百亿级别，每个公司的数据量具体不一样，每次使用30到90天的数据，特征量级别是1亿到百亿的量级，如果我们用50台机器去训练的话，大概需要迭代100个左右，这样花的时间是10小时左右。10个小时是什么意义呢?每天24个小时，这个模型只能训练两次，第一次供线上使用，第二次可以做试验，如果要进行第三次，时间是不够用的。所以我们需要一套更加高效的系统。
在Batch Learning做消息同步，需要把所有机器上的信息集合，大概分为两步，第一步把整个节点建成二叉树的组织形式，第二步每个子节点会把它上面的信息发给父节点，父节点将子节点以及它支撑的信息合成之后，汇总到root节点，这时就可以拿到全局的和了。有了这个之后，再经过一些逆向操作，节点就可以达到信息同步的状态了。
上面提到Batch learning不够高效，Online Learning相比于Batch Learning来说，除了效率有所提高，时效性也有改善。比如一天的training model供线上使用，如果线上环境实时发生变化，那我们的模型是捕获不到的，这时需要模型做实时反馈。理论依据：low regret f*为全局最优解，regret的值越小，其实是保证在线算法的效果越好，与看到的整个样本得到的算法效果尽可能接近，这是该模型背后的理论依据。
广告通常来说二值类型比较多，稀疏的线性模型比较合适，我下面列举的是我们曾经尝试过的一些稀疏线性模型：
我们尝试完一圈之后的感想就是，Online之所以获得稀疏在线模型，非常核心的原因是能够把历史信息利用起来，这样可以提高效率。
除此之外，微软在CTR方面做了一个贝叶斯方法，不再假设参数是一个固定的值而是一个分布，学习是Sequential Learning，通过后验代替先验，所以是一个天然的在线学习。
有了模型之后还需要一个框架，以上是一个典型的框架。线上用户浏览和点击是实时发生的，我们有基于storm做的collector，它会实时在线上抓取PV/Click，除了抓之外也会做一些日志清洗、拼接，我们会把log发给实时训练器，它根据数据做出训练，然后把参数实时更新到参数服务器，参数服务器除了接收训练器实时的参数推送外，也会接收一些线上预估请求，参数服务器反馈预估结果，这是整个过程。
这里大概列举了三种方案，如果说展示广告的点击率非常低，正负样本非常失衡，比如点击率是千分之一或万分之一的时候，我们会做采样，使正样本和负样本达到1比10的比率，这是一种方案。其缺点是点击率较高时，采用采样会有一些损失。另一个方法是单个机器计算完后用AllReduce的方法进行各个机器间的同步，第三个是异步学习方法，通常来说异步的效果会更好一点，但也会有一些不好控制的地方，比如调试时因为是异步的，所以每次的调试信息都不一样，这些可能需要注意的。
第二个方案是L2M信息检索，传统的检索大概分为三部分，第一部分是做数据采集，比如用户浏览的网页，我们会把类似的这些信息收集下来，之后我们会做一些结构化分析，我们称之为离线分析，分析完之后会有结构化的结果线上使用，比如一个线上请求来的时候会看到该用户以前浏览的网页，兴趣点是什么，这时线上就会用到线下的分析结果，我们把该阶段称之为在线触发。
获取信息有哪些具体方法呢?大概是这样几个方面，第一根据用户行为猜测当前应该展示的广告类型，比如可以看用户的历史query，用户的兴趣标签，第二个方法是基于上下文，比如我们看用户当前在浏览什么网页，就展示相关类型的广告，第三个方法称之为基于站点的方法，因为基于用户的当前页面可能太细了，太细了之后就会造成范围过小，如果粗一点，就会照顾到更多的点。另外，Look-alike的效果也比较好，通常在实践中都是几种方法混合在一起，那传统做触发的方法会有什么问题呢?比如我们在PC到无线网触发过程中遇到的问题。
首先，我们做广告的最终目标就是追求更高的ECPM处理，在这里可能不那么直接，比如做检索的时候，通常人多的情况下不是跟ECPM直接相关，这样会带来一个问题——效果打折，第二是数据覆盖问题，比如PC时，用户覆盖率很高，到无线时，用户覆盖率就很低，这时候我们怎么办呢?比如以前收集符合用户的query，那到无线的时候，有些设备跟用户都不一样;其次，用户信息覆盖率较低时，如何做触发?我们也发现了无线跟PC的其他不同之处，比如PC时，用户浏览的是一些商业价值比较高的网页，比如医疗网页，但无线时，通常会有很多商业价值比较低的网页，比如小说，这对我们的广告投放帮助不是特别大，这种情况下应该怎么办呢?
想解决上述问题，可以把信息分为AB两类，A类称之源信息，比如用户当前用的OS是什么，设备是什么，浏览器是什么，我们称为弱信息。这时，我们根据A去检索广告，广告就是我们的检索对象，把它称之为B，其实我们是想在AB之间做一个匹配，这样成本低，也非常直接，我们需要对AB预估ECPM，ECPM大概可以分为两部分，第一部分称之为CTR，第二部分称之为Bid，Bid可以通过一些简单的统计方法去做，CTR要难一些，有几种做的方法：
第一种方法人工设计A跟B的匹配关系，第二种稀疏特征，使用隐因子模型;第三种是使用稠密特征，使用非线性模型。
隐因子模型是给推荐中的常见的方法，需要预测用户对电源的打分，用户、电源各有一个隐因子模型，到后面发现用户、电源会有偏置，就诞生了Bias-LFM，在往后发现有些人会认为时间比较重要，我们又把时间加进去，做了Times Bias-LFM，每次变化需要做哪些工作呢?更新预测函数、学习过程及对应的代码。后来经过改进，思路是：每个features都会有Bias，任意两个features之间都会做一个拓展，这样增加特征就不需要修改function，也不需要动code，我直接通过这样一个模型，只加这样一个特征，就可以表达的更清楚，L2M就是基于这样一个模型做的。
L2M针对传统的FM有几点改进：1，改为分类;2，学习方法借鉴FTRL的Adaptive Learning Rate;3，超参数的学习。
该模型使用大概分为两步，一是探索，在线上单独开一份流量出来做探索，比如我们会拿5%的流量出来，假设在A里面有100个B，做随机的尝试，我们把它称之为探索，这时我们会有一些样本，首先根据这些样本做一些训练，然后是利用模型进行反馈，大概是这样一个过程。
我今天的演讲到此结束，谢谢大家!
