Mobvista 海外移动变现核心技术

之前受邀在QCON进行了名为海外移动变现核心技术的演讲。正好近期也在总结过去一段时间的工作,所以就直接在这儿总结了。

流量分类

Mobvista的移动变现业务,从流量侧来看,主要分三类流量:

  1. 外部Affliliates的流量,这个就是传统的买量,很多时候我们也不知道流量的来源,仅根据数据表现,以及运营人工经验评判流量渠道的好坏
  2. Mobvista的自有流量,其实也是和开发者谈下来的流量:和开发者签订协议,将Mobvista的SDK达到开发者的app中,之后出Mobvista的广告。一般内部我们就叫该系统为M系统
  3. 程序化买量:Mobvista建立DSP,从各大ADExchange买量

Affiliates买量过程人工运营成分比较多,而DSP可以是一个专门的TOPIC,所以此处就主要介绍Mobvista的自有流量业务的挑战,以及解决方案。

挑战

移动变现,特别是国际化移动变现过程中,面临的挑战非常多,以下是主要的挑战:1,广告样式多样化:banner,appwall, offerwall, native, interstitial, native video, rewarded video。 样式丰富,效果表现不一,导致要进行算法抽象,数据共享的时候存在较大挑战

2,转化路径较长:impression -> click -> install(安装激活) -> 应用内付费。。 甚至impression之前的展示广告是否返回成功,SDK加载是否成功等都是问题

3,流量参差不齐,不同国家间网络基础设施也有较大差异

4,移动广告的归因方式, 决定了产业中出现了较多的黑科技。这个之后值得用大篇幅进行介绍

以上这些问题,都是对算法的较大挑战,也早就叫较多算法优化点以及衍生的创收的黑科技。

技术应对方案

为了应对上述挑战, 我们必须有较为完善的架构, 算法解决这些挑战。 以下为Mobvista变下架构, 主要包含如下及部分,从左至右分别为流量侧到广告主侧

1.SDK:我们会开发SDK对开发者变现流量进行托管, SDK不仅支持IOS系统, 也支持ANDROID系统, 同时支持多种广告形式, 包括native, appwall和video等广告样式, 从功能上SDK主要负责广告分发, 展现控制, 缓存机制及消费空。 其中自创的缓存机制配合算法, 不仅能大幅减少广告请求交互, 提升广告加载, 展现速度,同时还能保证开发这的ECPM

2.Mobvista会对对外的API进行封装, 所以提供直接的OPEN API供开发者调用。 当然, 一般需要配合SDK的控制机制, 才能达到较高的受益

3.Mobvista同时提供完善的广告设置管理portal对广告素材,预算, 展现机制等进行管理控制,方便对广告的金细化运营

4.同时系统中还有完善的实验机制及样式模板管理, 方便整个系统对效果的优化

5.画红线的部分主要包括我们使用大数据平台对ECPM的模型训练及预估机制

对于模型相关的组件, 在省略了工程细节后, 主要是以下算法策略在系统中的重要组件。

与传统变现系统的较大差别, 在于我们为了处理长转化路径问题,对模型进行了拆分, 拆分为CTR预估模型及CVR模型;

同时为了解决多样性问题, 我们设计了定制的优质campaign探索机制, 及Mobvista的Exploration&Exploitation机制;

同时我们使用模型assabling的方法, 对LR, GBDT, FM等模型进行组合,提升预估精度

Ecpm就是我们预估的目标, 以下是我们对ecpm的拆解方法: 其中 ctr及cvr是未知量, 需要模型进行预估。

预估的方法比较直接: 我们寻找优质高效特征对样本进行描述, 同时使用点击和安装作为labels, 之后训练模型对ctr, cvr进行预估, 最后 使用 ecpm = 1000 * ctr * cvr * price 的方式计算ecpm, 并按照计算ecpm进行广告排序推荐

每次模型升级后会使用a/b test机制进行效果测试, 选出效果最好的模型

下图为我们的模型算法框架图。

为了适应我们全球化的变现业务需求, 我们的大数据机器学习平台是给予亚马逊aws云计算搭建的。

平台分为在线预估部分和离线部分,离线部分又分为日志处理及模型训练与配置模块

我们的日志具有较强的多样性及复杂性, 主要体现在两方面:

1.Mobvsita流量覆盖230+个国家, 故我们再多国及地区均有服务器, 数据需要从多地多服务器进行快速收集汇总

2.Mobvista有多条产品线, 不同产品线为适应业需求特性, 会使用不同存储系统对数据进行存储, 故须要从不同系统中对数据进行收集汇总, 包括DynamoDB, MongoDB, 以及内部的多种API接口

数据均使用AWS EMR分布式系统进行汇总, 计算机清洗。 我们会使用azkaban任务调度系统周期性定时启动生成EMR平台, 对数据进行处理, 处理后的日志按照访问实时性要求高低分别存放在 AWS redshift和S3上。 同时我们会根据数据量大小及计算任务复杂度动态调整EMR集群资源, 在保证计算任务实时性要求的同时, 减少计算资源浪费。 并在AWS上搭建机器学习平台进行模型训练。

更多内容可以参见PPT:

更多内容可直接访问: semocean.com

 

 

如何使用机器学习解决实际问题-以关键词相关性模型为例

本文以百度关键词搜索推荐工具字面相关性模型为基础,介绍一个机器学习任务的具体设计实现。包括目标的设定,训练数据准备,特征选择及筛选, 以及模型的训练及优化。该模型可扩展到语意相关性模型,搜索引擎相关性及LTR学习任务的设计实现。该模型的设计调研实现,也可以很容易移植解决其他包括语义相关性的问题

目标设定:提升关键词搜索相关性

作为一个搜索+推荐产品,百度关键词搜索推荐系统的产品形态是向凤巢用户推荐适合他业务的关键词。例如一个卖鲜花的广告主,他想在百度上做关键词搜索推广时,需要提交和他业务相关的关键词,而且提交的关键词需要业务相关,例如他需要提交和卖鲜花业务相关的关键词。例如鲜花快递,鲜花速递等。此时他可以在百度关键词搜索推荐系统中进行搜索查询,选择适合他的关键词。

百度关键词搜索推荐系统query搜索

这是一个典型的搜索问题,具体的从输入query,到触发,到排序等会涉及到很多因素,例如如何查倒排,如果处理地域因素等;要提升搜索的质量,我们首先需要保证输入的query和推荐出来的推荐词的相关性,此处我们要解决的主要问题, 就是如何快速,准确地判断两个关键词(输入query和推荐词)的相关性,需要特别注明的是,我们主要的目标是让用户觉得该产品结果很靠谱, 所以该处我们仅考虑字面相关性,更多的语意扩展该模型并未考虑。

注:该模型的调研实验实现方式, 可以很容易平移到语义相关性。例如加入更多语意特征,例如plsa的bm25特征和word2vec的相似度特征(或者和扩展的相关性校验,例如将待推荐词扩展为baidu搜索结果的摘要扩展)提高语义特征的贡献。

相关性也是所有搜索问题的基石,只不过在不同的系统中使用方式不一样, 在一般的搜索中,相关性占有较大权重, 排序基本就以相关性为依据; 在商业系统中,相关性则经常作为搜索展现的门槛用于控制商业推广结果的质量(如果仅考虑CTR, 用户搜索鲜花快递时,给用户展现艳照门的结果,CTR会更高,但相关性较差)。  当然,判断相关性我们可以简单使用某一种方法进行直接判定,例如直接进行两个关键词的TF-IDF计算,或是进行两个关键词的BM25。但这样的方式效果都不太理想,想要达到更好的效果,就需要使用更多特征,而更多特征很自然地,需要使用模型组合这些特征,达到最终的预期效果。

图:相关性在关键词系统中的位置

此处将会使用机器学习的方法解决该问题。本文以下内容会从数据准备, 特征选择, 模型选择, 模

型调优等步骤介绍百度关键词搜索推荐系统如何解决该问题

数据,特征,模型

说到使用机器学习解决问题,我们经常提到的优化思路就是3方面的优化: 数据,特征,模型。首先找到充足的,准确的label数据(该出仅考虑有监督学习任务,例如相关性,或是LTR),之后提取贡献较大的特征作为input space,以label作为output /ground true label,之后优化模型(Hypothesis) )。下面会分别从这3方面对整个优化过程进行阐述

准备训练数据

训练数据的获取一般有几种方式:

  1. 人工标注: 优点是质量较高,噪音较少;缺点是标注结果和标注者本身的认识相关,例如在搜索引擎中,判定苹果和手机的相关性,对于年轻人,一般都认为相关;但对于比较多的老人,可能认为不相关;另外一个缺点就是人工获取标注的成本较高
  2. 从日志中进行挖掘:优点是数据量相对更大,获取成本较低(编写几个hadoop脚本对日志进行统计);缺点是噪音较多,例如搜索引擎中的恶意抓取访问导致的噪音数据

在相关性模型中,一开始我们使用百度关键词搜索推荐系统的人工反馈数据作为label对模型进行训练,分别提取1.5W query-推荐词pair作为正负例进行特征提取,模型训练。

 

如图所示,在交互上,当用户喜欢该关键词时,就会点击‘大拇指’表示该结果符合用户需求(正反馈,该query-推荐词 pair可作为正例);如用户认为该关键词不符合需求,就会点击‘垃圾桶’,将该关键词扔入回收站(负反馈,该query-推荐词 pair 可作为负例)

在实验中,我们发现正例没有问题, 不过负例中会存在较多这样的情形: query-推荐词是相关的, 但该用户不做该业务,所以被定义为负例,所以负例个性化较强。所以后来我们让产品经理同学又对负例子进行筛选,重新标注1.5W负例,进行后续特征提取, 模型训练。

之后我们将正负例打散后(直接使用python random.shuffle)分成10份,进行cross-validation

模型训练前,先定标准和样本

注: 训练样本的挑选完全决定了我们的问题目标,所以在一开始就需要准确选择,如果可能,所有的case都最好人工来搞,或者至少需要人工review。 确定没有问题后,再开展后续工作。特别是相关性类似的问题,比较主观,例如PM和RD在该问题的判断上就可能存在一定差异。

确定完训练样本, 评估标准,之后再小布快跑, 优化模型。

特征提取

一般特征的选择及处理会极大地影响学习任务的效果,而进行特征选择的时候,一般是先增加特征,并实验效果。 对于相关性模型, 我们可以先将传统的信息检索的特征加上,这些特征一般分为以下几类:

  1. query/候选词的一般结构特征: 例如query/候选词长度,term数等
  2. query-候选词的相关性度量:例如TF-IDF, bm25, LMIR及多重变种, plsa相似度度量,word2vec语意向量相似度等; 很多时候,关键词自身信息较少,还可以使用关键词在搜索引擎上的摘要扩展进行相似度度量
  3. 关键词自身在信息检索维度的重要性度量,例如关键词idf, 从语言模型方面的重要度等

在一开始的时候,我们可以先将能够想到,构造出来的特征均加入特征向量进行实验,而且每加一类特征,都可以看下该类特征对整体目标的提升程度。以便对该特征的贡献度有一个直观的感受。

以下数据可以简单看出随着特征的增加,效果的提升,其中的特征仅加不减(模型使用random forest   进行二分类):

等到特征加得差不多,模型准确性已经提升不多的时候, 可以考虑砍特征,有一种比较简单粗暴有效的砍特征的方法,就是使用树模型,就是直接砍掉特征贡献程度及特征重要性较低的特征,例如直砍掉特征贡献度为0的特征,对相关性模型的准确性几乎没有影响

特征贡献度

当增加特征已经很难提升效果, 考虑到为了防止过拟合,同时考虑到模型online预测,需要对特征进行挑选。在使用树模型时,可以直接使用数节点特征贡献度和节点使用次数,判断是否需要去除该特征,以下为使用树模型进行选择特征的例子:

对于特征贡献度和分裂特征使用次数为0的特征,在调研时,直接去除对模型效果几乎没有影响,而且能提升预测的效率。

在选择特征的时候, 有一些经验值得分享:

  1. bm25特征及term weight特征对分类任务有极大贡献
  2. 一些单独的比值类特征并没有太大贡献,例如query,推荐词共同term与query term数,推荐词term数的比值,这些特征并没有太大贡献,但是这些特征与query,推荐词的term数结合到一起,贡献就非常多;所以有些特征需要联合在一起,才有较大作用。
  3. 特征选择需要和目标一致:例如word2vec是非常高大上,且非常靠谱的技术,但用在字面相关性,对目标并没有太大贡献(如果目标是语意相关,那么类似于PLSA,word2vec将会有很大贡献)
  4. 有些特征就就是用来解决特殊case的,虽然贡献不大,但需要保留(当然也可以直接设置为强规则与模型配合),例如query与推荐词拼音一致

模型选择

经典模型

最开始我们尝试了最大熵,SVM和adaboost模型, 考虑到online使用的效率,最终我们选择了adaboost模型作为线上使用的模型,虽然效果不是最好的,但使用简单的weak learner构建的模型的确比较快(参见博文:《adaboost》),并且使用adaboost进行上线并取得较好效果:上线后不仅召回增加,准确性上90%的case相关性高于等于原有结果(采用非模型的版本)

评估结果分布图(2到-2分别代表扩召回结果相关性高于、略高于、等于、略低于、低于线上策略)

集成树模型

现在特别喜欢使用树模型,因为使用的时候,连特征归一化都省了: 如果使用SVM类似的模型,还需要对特征进行归一化等处理, 但使用树模型,直接将特征向量及label扔给模型, 模型自己会根据信息增益,或是基尼系数等标准选择最合适的拆分点进行树节点的拆分(具体的拆分标准可参见博文:《使用impurity选择树模型拆分节点》),开源的树模型,例如大名鼎鼎的Quinlan的C4.5或是C5.0都在调研时都可以拿来试试作为特征选择的依据。

特别是集成树模型的出现,更是极大地提升了树模型效果。所以现在的项目中,我比较喜欢在增加特征的时候就使用集成树模型进行效果实验。 具体树模型使用参见《集成树类模型及其在搜索推荐系统中的应用

集成树模型配置选择

此处的配置选择和传统的模型参数稍有区别,该出的树模型配置主要指集成树模型中树的数量,每棵树的特征选择因子和样本使用因子等。在项目中,考虑到准确率和速度,最终确定的参数是树的数量是20, 特征选择因子和样本选择因子均为0.65(每棵树随机选择0.65的样本和特征进行训练)

具体产品效果可参见www2.baidu.com中百度关键词搜索推荐系统的排序结果:

如何个性化

首要需要考虑的是我们的数据样本,是否本身就是包含个性化的case(此处的答案是否定的); 假设我们的标注case是个性化的,也就是case中本身就包含了个性化结果时,在模型训练流程上其实并没有太大区别, 主要的区别就在于我们选取哪些能够区分这些个性化的特征, 例如百度凤巢中账户(单元)的plsa模型产出的pzd向量与query的相似度等

登录www2.baidu.com->关键词工具->搜索query->查看结果 即可。

更多内容也可参见: http://semocean.com

百度搜索引擎变现策略指标体系

下文就百度商业变现的指标体系进行概要描述,并针对一个类似于百度LBS系统的变现思路,阐述一个商业系统变现策略指标体系的建立过程。

为什么需要商业变现策略指标体系

一般情况下,一个互联网产品,或是一个移动端产品在发展前期,主要会关注流量及用户量的增长。当流量,用户量做到一定程度时,就会考虑商业变现。例如今日头条,美丽说,高德地图这样的产品现在都开始商业化变现。而要从变现效果,效率衡量整个系统,以及监控技术策略对系统变现的贡献时,就需要建立一套完善的策略指标体系监控系统当前的状况, 发现系统策略效果瓶颈并有的放矢地去提升。
之前在百度,在和一位高级技术经理聊天时,他就说过, 之所以百度内部一位从Google过来的VP很受老板的重视,一个非常大的贡献,就是他推动百度凤巢指标体系建立,保证公司收入灵活可控,保证每次百度都能在华尔街交出漂亮的财报
指标体系包含的内容

广告主关心的指标

在广告界的人士都知道广告主的这样一句名言:“我知道我投入的广告费用的一半是白费钱财,但问题是,我不知道是哪一半”。而搜索引擎的搜索一大优点,就是能够监控每一次搜索点击的效果。
对百度广告主来说,他们最关心的,和所有的商业投资一样,是:投资回报率 (ROI)。广告主们(商家)想知道在百度体系的广告的投入是否真的有回报,而这个回报是否能够超过投入的资金,超过的比例有多大,这一点上,搜索引擎商业变现系统是做了精心的设计的:
从商家的角度理解ROI,就要了解三个指标:
1.广告展现次数(简称show):当网民提供关键字,使用百度的搜索业务时候,相关的广告也会根据算法出现在页面相应的位置,用户投放的广告的展现次数,每天,每周,每月都会有统计。 当然,相对于传统的广告投放模式,只要展现了就要收费,百度对展现的广告是不收费的,哪怕用户看到了广告主企业的名字和推广口号,广告主已经获得了一定的广告收益,是要用户不点击广告链接,广告主不需要支付任何费用(针对竞价排名高,和右端广告而言)。这在传统的广告界是不可想象的,因为传统媒体,例如电视,包括门户网站上的banner广告,都是按照展现收费的:看到一次收一次的费用。
2.广告点击次数(简称clk) :用户看到广告后,点击了广告主提供的链接。 可以用每千次广告展现的点击率来计算。网民点了推广信息的链接。推广信息被点的次数被称为点击量,即Clicks,产生的费用叫做点击费用,平均到每次点击的费用被称为单次点击价格,即CPC,是Cost Per Click的缩写。推广信息点击量与展现次数之间的比值被称为点击率,即CTR,是Click-Through Rate的缩写,计算公式为:点击率=(点击量/展现量)×100%
3.点击率到商业收益的转换:用户点击了客户的广告,就会看到客户自己的网站页面,如果被客户提供的商业服务或者产品所吸引,而付费的话,那么客户就实现了一次成功的商业收益
因为商业系统必须要保证客户(广告主)的利益,这样才能长久合作,所以商业变现策略指标体系必须包含这些指标。
在类似于百度,360,或是Google这样的搜索引擎, 其能精准监控的,就是1,2, 对于最终的商业转化,因为是在商家的网站上完成的,所以除非网站上内嵌了搜索引擎单独提供的独立工具(例如百度的福尔摩斯),否则搜索引擎无法了解这些信息。
投资人关心的变现策略指标
以上是百度广告主需要关心的指标。对于百度这样的上市公司,每个季度的财报中都需要有公司详细的赚钱相关财报内容及各种指标分解,以便了解当前变现系统的健康程度及瓶颈及后续的突破点。
例如百度的投资人不仅关心这个季度百度多挣了多少钱,还会关心多挣的这些钱是来自于哪个环节的提升,是否可持续, 是否后续还有增长空间。 就和分析公司财务报表,或是分析股权收益率一致。
为了让大家对搜索引擎变现策略指标体系有一个对比了解,以下先用股权收益率说明问题。大家可以不用有较强的金融,财务知识也能看懂这个公式,而搜索引擎变现策略的指标体系,与此公式有异曲同工之处,都是将最终的收益(率),分解为各个相对独立的因素,以便发现系统挣钱效率的优势与瓶颈。
该公式主要的目的是让大家了解如何对最终目标指标进行拆解,如果大家不感兴趣可以跳过该节。
股权收益率
即在股市中,投资人购买的股票收益率, 设想一下,一个精明的投资人, 在购买了某个公司大宗股票后,一方面会关注每年的股票收益,另一方面也会分析股权收益是来自于哪些因素的上涨,这样才能分析公司增长是否健康,例如,股权收益率可以简单地使用以下公式计算ROE=净利润/权益。但如果要对这个公式进行细分,将其中对股权收益率相关的影响因素均拆分出来,那可以得到以下公式:
其中
  1. 税收负担比例:反映公司的税收负担情况,例如有一个季度百度的税率为腾讯的一半,因为百度和国家有什么高新技术的合作所以税收减免(记得百度可能是7%左右,腾讯13%左右,不是精确比例),类似的情况就可以在(1)中反映
  2. 为公司向债权人负担的利息比例, 借的钱越多,这个值越小
  3. 利润率:为每一块钱的销售额所带来的利润。
  4. 资产周转率:为公司资产的使用效率,例如家乐福,沃尔玛虽然利润率很低,但因为出货量大,所以照样赚钱
  5. 杠杆比例:公司资产与公司权益的比例,用于表示用于赚钱的钱中,有多少是自己的,有多少是别人的(例如银行)。例如:北京以前买房的人都发了,因为买的早,一方面房价便宜,一方面使用银行贷款,假设30%首付,那相当于剩下70%银行贷款在房产上的收益,也是自己的。
类似地,如果对百度商业变现体系的收入进行一个拆解,也能将其分解为类似的独立因子,对系统效率进行细化分析。
搜索引擎投资人关心的变现策略指标
从宏观上,我们假设投资人都是唯利是图的,收入是他们最关心的事。当然,很多投资人也会兼顾长远的收益,所以他们会关系收入是如何组成的。我们这里抛开运营,股权收益,利息支付,税收等各种公司的开销,我们仅考虑变现系统的名义收入,即搜索引擎中计费系统的计费和。此时可以将搜索引擎收入分解为以下独立因子:
Revenue =PV * PVR * ASN * CTR2 * ACP
以上公式就是百度,360,Google搜索广告变现收入的拆解。
要弄清楚以上公式的具体含义,需要了解下列指标的定义:
  1. CPM1:cost per thousand1 按每千次检索收费, 百度用户每使用百度一千次做搜索为百度带来的收益。 也就是用户使用了百度服务一千次所带来的百度的收入。这个是衡量百度赚钱能力的重要指标。是百度变现能力的基本衡量标准。是根据每个季度的总收入除以PV(Page View)算出来的。
  2. CPM2:cost per thousand2 按每千次展示收费,广告所在的网页被浏览了一千次,即认为该广告展示了一千次。 这个指标是衡量广告客户的广告展现了一千次的时候,客户交付的费用(注意客户是在用户点击广告后才付费的). 这个指标可以衡量用户对于广告的感兴趣程度。从广告客户的角度讲,也可以衡量在百度投放广告的费用多少,以及投放的有效性。
  3. CPM3:cost per thousand3 表示平均每千次有广告展现的检索请求对应的广告收入,衡量单次有广告展现检索的平均收入贡献。这个指标是衡量当搜索结果的页面有广告展现的时候,每展现一千次,百度能够拿到的收入。有的搜索结果是没有广告展示的(CPM1把这些PV也计算进去了)。
  4. CPC:cost per click 按每次点击收费,是目前最流行的搜索引擎营销的付费方式,即只有当用户点击观看了你的推广链接后,才发生费用。
  5. CPA:cost per action 按每次用户消费行动收费,被认为将是互联网广告未来必然的发展方向,但由于不同产品的广告对action的定义和回报率有太大差异,实现过于复杂,目前在全球范围尚无搜索引擎使用CPA收费的成功先例。
CTR——点击率,在这里特指广告或推广链接出现后被用户点击的机率。CTR还将可以进一步的细分。
  6. CTR1:表示平均每次检索请求对应的广告点击数,衡量单次广告检索的平均点击贡献。理论上 CTR1 可能大于 1。因为每次检索客户可以点击一个广告,看了后,在回去原来的检索页,点击下一个广告。
  7. CTR2:表示平均每次广告展现对应的广告点击数,衡量单次广告展现的平均点击贡献。
  8. CTR3:表示平均每次有广告展现的检索请求对应的广告点击数,衡量单次有广告展现检索的平均点击贡献。理论上 CTR3 可能大于 1。
  9. ARPU:户均消费,影响它的因素包括:点击流量大小、关键词的相关性、同一关键词的竞争度,以及客户在搜索引擎广告上的预算上限等。
  10. PV:检索量,百度搜索框的搜索次数
  11. ADPV:出广告的检索量,即PV中,有广告展现的搜索数量
  12. CLK:click number,广告的总点击次数
  13. CSM: 百度广告主的总广告费支出
  14. ASN:平均展现条数。即:如果展现了搜索推广广告,每次平均展现多少条
  15. ACP:Average Click Price 平均点击价格  总消费/总点击
  16. PVR:Page View Rates, PV比率,出广告的检索量 / 检索量
有了以上这些定义后,我们再来回顾变现系统的计算公式:
Revenue =PV * PVR * ASN * CTR2 * ACP
可以看出以上各因子表明了变现系统不同组成的效率
  1. PV:是百度能够用于变现的流量上限,由用户体验决定,百度越好用,口碑越好, PV越高。该指标在百度类似的搜索引擎公司,主要由搜索部门负责。
  2. PVR:就是PV中被用于变现的比例,PVR越高,说明在百度搜索中,出广告的概率越高,有可能导致用户体验的下降
  3. ASN:单次有广告展现的PV,展现的广告数量,表明单次有广告展现时的变现利用程度。ASN越高表明单次搜索出的广告越多,可能导致用户体验的下降
  4. CTR2:单条广告展现时, 广告北点击的概率。表明广告推的是否精准,是否满足用户需求(至少是感官上是否吸引用户)
  5. ACP:单次点击价格,相当于单价的高低
这样的指标分解非常有利于指导策略的优化,以下是几个case:
  • PV:搜索部门的重要指标,增加下降,都能立刻看出搜索部门的业绩,或是竞争对手带来的影响,例如,就百度而言,Google退出中国PV上升,360上了搜索, PV下降,都能直接看出来
  • 点击率预估:假设PV,PVR,ASN,ACP都固定,则要增加收入,需要提升用户对广告的点击率,此时可以用模型来对点击率预估,提升CTR2。各大搜索引擎公司,对CTR2的预估,基本上都是商业部门的重要机密,也是最重视的技术之一
  • 增加广告展现:在各上市公司(包括传统行业公司),都会有‘冲业绩’这么一说,就是极度末时,为了达到之前的营收计划,需要使用各种手段增加收入,例如我们经常听说的银行给高利息临时拉存款等,在百度则可以通过调参提升收入,比如增加ASN或是PVR,达到收入符合华尔街预期的效果
  • ASN的变化:如果收入的增长是来自于ASN的增长,则说明百度的点击卖得更贵了,广告主会不乐意。相反,ASN下降,说明点击卖便宜了,百度的收入有可能降低,所以类似于CTR2上升,ASN不变这样的策略,是最好的
有了以上定义即收入的拆解,则收入可以用其他集中形式表示:
Revenue = PV * CPM1
Revenue =PV * PVR * CPM3
Revenue =PV * PVR * ASN * CPM2
Revenue =PV * CTR1 * ACP
Revenue =PV * PVR * CTR3 * ACP
百度商业部门的工作,几乎每天都是在围绕着这些指标来进行的。每一次策略的调整,工作方式的改变,都希望在这些指标上做出正向的贡献,因为这些指标对百度的收入是直接造成影响的。从百度的收入(Revenue)的计算公式上就可以看出(每一种计算方法得到的结果都殊途同归)
如何建设LBS变现策略指标体系
拿百度地图类似的LBS产品为例,假设我们的转化漏斗路径是:推荐&搜索之后展示结果列表也,然后用户点击结果进入店家的表述页面(POI),之后如果用户感兴趣,则点击具体的团购,优惠券进行购买,搜索漏斗如下:
图:搜索漏斗
对应到线上系统,在评估衡量线上系统效果时,我们也需要分为这3阶段进行衡量,以及时发现线上策略效果的瓶颈所在, 快速找到提升重点。在以上3阶段中:
  1. 搜索or推荐:主要表明流量大小
  2. 点击详情页: 表现为用户带来的流量到详情页的浏览情况
  3. 转化:最终转化action
对于商业系统,我们最重要的目标就是保证在既定流量上,转化最高。
以下为我们需要关注的所有指标:
表:策略效果指标
如后续变现系统按转化收费,则整个LBS变现系统收入可定义为:
收入=  pv * pvr * easn * ctr2 * atr2 * aap
在产品的不同阶段,我们需要关注的重点不一样:
  • 在产品上线的阶段,我们需要关注用户体验,所以ctr2和atr2需要重点关注
  • 用户体验提升到一定程度,商户已经认可我们产品效果时,再考虑提升成单的单价(例如佣金等),同事可以考虑对商业POI进行放量,提升pvr和easn
物料召回及检索类指标
该类指标主要用于监控系统的检索量, 以及系统的召回能力。 检索量等指标是系统变现可以使用的所有资源,更多受用户产品影响;而召回能力相关指标则体现出CPR系统对商业物料的召回能力。
以下为重要指标说明:
  • 检索量: 发送到系统的所有请求量;通过统计检索日志条数得到;为能够变现的流量全集。
  • 查询用户数:所有发起请求的用户数;统计检索日志中去重后uid得到,体现参与检索的用户量。
  • 用户平均检索量:平均每个用户发起的请求数量;体现用户检索角度的活跃度。
  • 单次检索返回结果数:平均单次检索返回结果条数; 体现系统的召回能力(准确性参见相关性评估)
  • 商业结果检索量:出现商业结果的检索次数;
  • 商业结果检索用户数:出现商业结果的检索用户数;体现商业结果能够覆盖的客户群体
  • 商业检索占比:出现商业结果检索量占总体检索量占比;可根据改指标分析潜在变现流量。
  • 商业检索用户占比:看到商业结果的用户占所有检索用户占比;可根据该指标分析潜在变现用户。
  • 单次检索商业结果返回条数:一次出现商业结果的检索,返回的结果条数;
点击行为类指标
该类指标主要用于衡量用户浏览搜索/推荐结果后的点击行为。该过程为转化漏斗第二阶段。
以下为具体指标及含义:
  • 点击条数:被点击的POI数量(包括自然POI和商业POI)
  • 有点击检索次数:产生点击行为的检索次数(包括自然POI和商业POI)。
  • 有点击用户数:产生点击的用户数量。
  • 商业POI点击条数:商业POI被点击的数量。
  • 商业POI有点击检索次数:出现商业POI,且产生商业POI点击的次数。
  • 商业POI点击用户数:点击商业POI的去重用户数。
  • 单次检索点击率:平均每次检索点击POI的概率;该值理论上可能大于1
  • 单次检索商业POI点击率:平均每次检索,点击商业POI的概率;该值理论上可以大于1
  • 单条商业POI展现点击率:平均每条商业POI展现的点击概率;用于衡量每条商业POI曝光产生点击的效率。
  • 单次有商业结果展现点击率:平均每次有商业POI展现的检索的点击概率;用于衡量出商业POI的流量产生点击的效率。
效用类指标
该类指标主要用于衡量用户点击进入POI详情页后,根据详情页信息,做出最终决策的阶段(包括点击‘预订’,‘成单’,‘下载’等行为)。该过程处于转化漏斗的第三阶段,也是最终阶段。
以下为具体指标定义:
  • POI展现数:包括自然POI和商业POI的展现次数。
  • POI展现用户数:浏览POI的去重用户数。
  • POI详情页转化数:此处的转化根据每个入口可能有所不同。
  • POI详情页转化率:POI详情页转化数/POI详情页展现数。
  • 单次转化收费: 完成单次转化后,向商户收取的平均费用。
以上密密麻麻的指标,在不同的商业变现系统中会有所差别,但基本上都是按照用户产品形态及转换漏斗进行设定,而每个策略的上线,都会使用类似的指标体系来衡量策略对不同漏斗部分的效率影响。
更多内容也可参见: http://semocean.com

推荐系统经典论文文献及业界应用

列了一些之前设计开发百度关键词搜索推荐引擎时, 参考过的论文, 书籍, 以及调研过的推荐系统相关的工具;同时给出参加过及未参加过的业界推荐引擎应用交流资料(有我网盘的链接), 材料组织方式参考了厂里部分同学的整理。
因为推荐引擎不能算是一个独立学科,它与机器学习,数据挖掘有天然不可分的关系,所以同时列了一些这方面有用的工具及书籍,希望能对大家有所帮助。
Survey方面的文章及资料
  1. Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[J]. Knowledge and Data Engineering, IEEE Transactions on, 2005, 17(6): 734-749. 2005年的state-of-the-art的推荐综述,按照content-based, CF, Hybrid的分类方法进行组织,并介绍了推荐引擎设计时需要关注的特性指标,内容非常全。
  2. Marlin B. Collaborative filtering: A machine learning perspective[D]. University of Toronto, 2004. 从传统机器学习的分类角度来介绍推荐算法,有一定机器学习背景的人来看该文章的话, 会觉得写得通俗易懂
  3. Koren Y, Bell R. Advances in collaborative filtering[M]//Recommender Systems Handbook. Springer US, 2011: 145-186.  RSs Handbook中专门讲述协同过滤的一章,其中对近年协同过滤的一些重要突破进行了介绍,包括因式分解,时间相关推荐,基于近邻的推荐以及多种方法的融合,内部不多,但其中引用的论文值得细看
  4. Su X, Khoshgoftaar T M. A survey of collaborative filtering techniques[J]. Advances in artificial intelligence, 2009, 2009: 4. 协同过滤的篇survey, 按照memory-base, model-based, hybrid分类方法介绍各种协同过滤方法及评价标准,并在其中给出基于netflix数据进行评估的效果对比
  5. Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37.  主要集中在因式分解实现协同过滤方法,如果看完Advances in collaborative filtering[M]//Recommender Systems Handbook的话,这篇文章就没有必要再看了
  6. Pazzani M J, Billsus D. Content-based recommendation systems[M]//The adaptive web. Springer Berlin Heidelberg, 2007: 325-341.从宏观上介绍content-based的策略架构
Content-based方法
content-based方法非常依赖于特定领域item的特征提取及处理,例如音乐推荐或是关键词推荐中很多细节内容信息处理过程都是不一样的,故这里仅列了content-based综述类的几篇文章。
  1. Pazzani M J, Billsus D. Content-based recommendation systems[M]//The adaptive web. Springer Berlin Heidelberg, 2007: 325-341.从宏观上介绍content-based的策略架构
  2. Lops P, de Gemmis M, Semeraro G. Content-based recommender systems: State of the art and trends[M]//Recommender Systems Handbook. Springer US, 2011: 73-105. RS Handbook中专门介绍content-based 算法的章节
  3. Jannach D, Zanker M, Felfernig A, et al. Content-based recommendation   [M] Charpter 3 Recommender systems: an introduction[M]. Cambridge University Press, 2010.
Collaborative Filtering方法
Neighbourhood Based Methods
  1. Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. ACM, 2001: 285-295. KNN进行item-based推荐的经典文章,其中也介绍了多种相似度度量标准
  2. Linden G, Smith B, York J. Amazon. com recommendations: Item-to-item collaborative filtering[J]. Internet Computing, IEEE, 2003, 7(1): 76-80. 经典的亚马逊item-based算法的文章
  3. Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing[C]//VLDB. 1999, 99: 518-529.  LSH
  4. Bell R M, Koren Y. Scalable collaborative filtering with jointly derived neighborhood interpolation weights[C]//Data Mining, 2007. ICDM 2007. Seventh IEEE International Conference on. IEEE, 2007: 43-52.
  5. Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998: 604-613. LSH
  6. Buhler J. Efficient large-scale sequence comparison by locality-sensitive hashing[J]. Bioinformatics, 2001, 17(5): 419-428. LSH应用
Model Based Methods
  1.  Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37.主要集中在因式分解实现协同过滤方法,如果看完Advances in collaborative filtering[M]//Recommender Systems Handbook的话,这篇文章就没有必要再看了
  2. Singh A P, Gordon G J. A unified view of matrix factorization models[M]//Machine Learning and Knowledge Discovery in Databases. Springer Berlin Heidelberg, 2008: 358-373.
Hybrid Methods
  1. Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008: 426-434. 因式分解与Neighbour-based方法融合
  2. Burke R. Hybrid recommender systems: Survey and experiments[J]. User modeling and user-adapted interaction, 2002, 12(4): 331-370.
  3. Burke R. Hybrid recommender systems: Survey and experiments[J]. User modeling and user-adapted interaction, 2002, 12(4): 331-370. 介绍了多种推荐算法进行融合的框架
推荐系统工业界应用
  1. Netflix:Netflix视频推荐的背后:算法知道你想看什么
  2. Netflix:Netflix Recommendations Beyond the 5 Stars
  3. Hulu:Recommender System Algorithm and Architecture-项亮
  4. Youtube:Davidson J, Liebald B, Liu J, et al. The YouTube video recommendation system[C]//Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010: 293-296.  Youtube推荐系统中的主要算法。 百度关键词搜索推荐系统对其进行了优化, 实现了任意类型的级联二部图推荐。 具体内容可参见博文: google youtube 电影推荐算法, 以及百度关键词搜索推荐级联二部图实现
  5. 豆瓣: 个性化推荐系统的几个问题_豆瓣网王守崑
  6. 豆瓣:阿稳_寻路推荐_豆瓣
  7. 豆瓣:豆瓣在推荐领域的实践与思考
  8. 百分点:量化美-时尚服饰搭配引擎
  9. weibo及考拉FM:停不下来的推荐实践_陈开江
  10. 阿里:天猫双11推荐技术应用
  11. 阿里:淘宝推荐系统
  12. 当当:当当网搜索和推荐_庄洪波
  13. 土豆:个性化视频推荐系统土豆_明洪涛
  14. 360:360推荐系统实践-杨浩
  15. 盛大:推荐系统实战与效果提升之道-陈运文
  16. 盛大:智能推荐系统的开发与应用-陈运文
推荐系统书籍
  1. Segaran T. Programming collective intelligence: building smart web 2.0 applications[M]. O’Reilly Media, 2007.寓教于乐的一本入门教材,附有可以直接动手实践的toy级别代码
  2. Shapira B. Recommender systems handbook[M]. Springer, 2011.  推荐系统可做枕头,也应该放在枕边的书籍,看了半本多。如果将该书及其中的参考文献都看完并理解,那恭喜你,你已经对这个领域有深入理解了
  3. Jannach D, Zanker M, Felfernig A, et al. Recommender systems: an introduction[M]. Cambridge University Press, 2010.  可以认为是2010年前推荐系统论文的综述集合
  4. Celma O. Music recommendation and discovery[M]. Springer, 2010. 主要内容集中在音乐推荐,领域非常专注于音乐推荐,包括选取的特征,评测时如何考虑音乐因素
  5. Word sense disambiguation: Algorithms and applications[M]. Springer Science+ Business Media, 2006. 如果涉及到关键词推荐,或是文本推荐, 则可以查阅该书
P.S. 想对某个领域或是工具有深入了解,可以找一本该行业的XX HandBook满怀勇气与无畏细心看完,然后就会对这个领域有一定(较深)了解,当然如果手头有相关项目同步进行,治疗效果更好^_^
推荐系统工具
  1. Mahout:基于hadoop的机器学习,数据挖掘,推荐系统开源工具。我厂的超低版本haodop集群居然不支持Mahout,想跑个Mahout还要进行移植,郁闷。。。该死!!
  2. scikit-learn:基于python的机器学习,数据挖掘库, 方便好用,适合数据量较小的调研任务,不过,一切不支持大数据的机器学习算法,(一定程度上)都是耍流氓。。。。
  3. weka:经典的数据挖掘工具, java版本
  4. R:R语言
  5. Cluto:聚类工具,集成了较多聚类算法及相似度度量方法
  6. RapidMiner:没用过,但据说使用量非常大
国内推荐系统站点
  1. http://www.resyschina.com/
因为我一直认为推荐系统不是一个独立的学科,它很多技术都是直接来自于机器学习,数据挖掘和信息检索(特别是文本相关的搜索推荐),所以以下也整理了一些之前工作及工作之余看过,了解过,或者准备看的这方面的资料
数据挖掘资料
  1. Han J, Kamber M, Pei J. Data mining: concepts and techniques[M]. Morgan kaufmann, 2006. 数据挖掘方面的handbook,教科书类型,虽然厚,却通俗易懂(再次提醒,要了解某一领域,找本该领域的啥啥handbook耐心认真读完,那你基本对该领域有一定认识了)
  2. Chakrabarti S. Mining the Web: Discovering knowledge from hypertext data[M]. Morgan Kaufmann, 2003.介绍了一个搜索引擎中的大部分技术,包括spider,索引建立,内部的机器学习算法,信息检索,而且非常具有实用性,我在百度商务搜索部开发的spider,就是按照其中的架构设计开发的
  3. Liu B. Web data mining: exploring hyperlinks, contents, and usage data[M]. Springer, 2007. 如果说 Mining the Web: Discovering knowledge from hypertext data更偏web mining更偏整体,工程的话,这本书就更偏策略,两本都读过的话,你对搜索引擎中的数据挖掘算法的了解,就比较全面了
  4. Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1-37. 专门将2006年评选出来的10大数据挖掘算法拎了出来讲讲
  5. Rajaraman A, Ullman J D. Mining of massive datasets[M]. Cambridge University Press, 2012.介绍如何使用hadoop进行数据挖掘,如果有hadoop环境则非常实用
  6. Feldman R, Sanger J. The text mining handbook: advanced approaches in analyzing unstructured data[M]. Cambridge University Press, 2007.文本挖掘的handbook
机器学习资料
  1. Tom M Mitchell,Machine Learning, McGraw-Hill Science/Engineering/Mat, 1997,非常早起的机器学习书籍,非常适合入门, 浅显易懂, 但对于工业界应用, 只能说是Toy级别的算法。
  2. Bishop C M, Nasrabadi N M. Pattern recognition and machine learning[M]. New York: springer, 2006. 进阶型的书籍,对每种算法都有较为具体的理论介绍
  3. 课程: 机器学习(Stanford->Andrew Ng)http://v.163.com/special/opencourse/machinelearning.html,大名鼎鼎的Andrew Ng的机器学习公开课,网易上字幕版本;配合课程stanford cs229对应的handout及习题一起学习效果更好
信息检索
  1. Agirre, Eneko, and Philip Glenny Edmonds, eds. Word sense disambiguation: Algorithms and applications. Vol. 33. Springer Science+ Business Media, 2006.
  2. Manning C D, Raghavan P, Schütze H. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008.
  3. MOFFAT A A, Bell T C. Managing gigabytes: compressing and indexing documents and images[M]. Morgan Kaufmann, 1999.一本很老的介绍搜索引擎的书了,不过09年的时候看还是被震撼到了,书中各种变着戏法使用几十M内存处理上G数据,感觉非常牛叉。
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

百度关键词搜索推荐系统交互流程

如果把百度凤巢系统比作商场,那这个商场的主要商品是什么?答案就是‘流量’,而关键词,就是流量对广告主最直观的表现载体。

客户想要在百度上做搜索广告,就需要找到能够准确描述自己推广意图的关键词集合;但另一方面,目前百度凤巢系统拍卖词接近10亿,百度每天有PV关键词约数十亿。从这些词海中淘出优质关键词,无论对于客户本身,还是为客户打理账户的客服而言都是一大挑战。
此时百度关键词搜索推荐工具(KR)就显现出它的重要作用。
那KR到底是什么呢?顾名思义,KR(Keyword Recommendation缩写)就是百度向客户推荐关键词的工具。当然,KR不仅提供诸如被动,主动,按URL,按行业等推荐形式为客户推荐个性化关键词,同时还提供像种子词,种子URL,Suggestion等引导提词技术;另外KR还提供客户账户诊断优化服务,一方面优化客户账户结构,提升客户提词,账户管理效率,同时也达到提升客户消费,提升百度凤巢系统整体消费的功能。

因为该工具是提供给百度广告主使用的,所以在网络上没有直接的入口,需要再www2.baidu.com上注册帐号后,找到‘关键词工具’后进行访问。

百度关键词搜索推荐交互

以下为关键词工具使用流程:

广告主进入KR入口(www2.baidu.com)中有多个入口,此时KR会根据广告主在凤巢中的历史操作行为,为其推荐种子关键词,广告主可以直接点击种子关键词进行搜索(种子关键词主要是面向对KR使用不熟练的客户,对他们的使用进行引导,百度搜索框也没有该功能,该功能为KR独有); 之后网民可输入搜索搜索query获取和该query字面,语义相似的关键词,同时系统会返回和这些关键词相关的属性。然后用户可以对关键词进行筛选及分组(系统会提供多种分组建议)

图: 百度关键词搜索推荐系统交互示意图

同时KR也提供传统推荐的方式为广告主推荐关键词。就是根据客户历史提词行为,使用SVD,图关系挖掘等协同过滤技术直接将结果推荐给广告主,广告主无需有任何交互输入,直接进入提词页面就能看到结果。

搜索系统策略架构

百度关键词搜索推荐系统(KR)不仅提供典型的推荐服务,即不搜既得,同时也提供搜索功能,即用户输入关键词进行搜索,KR推荐出与该关键词最相关的top n 关键词, 这些关键词不仅附带有容易理解的推荐理由(表明该关键词为何推荐出来),同时附带有关键词的各种属性(例如关键词在百度上的流量,竞争激烈程度等信息),同时对关键词按照字面,语义进行聚类;推荐出来的关键词默认已按照字面,语义相关性及marketing rule进行了排序。 以下为KR搜索过程online部分的策略架构(offline部分涉及较多数据挖掘逻辑,参见之前的文章介绍)

其中最底层为各种基础数据及这些基础数据经过预处理, 清洗后的存储, 以及基于这些过程的挖掘数据。当用户发起一次请求时,系统会经历以下主要步骤:

  1. 关键词触发: 根据经典的字面进行触发以及语义, 同购关系及复杂图关系的挖掘数据,触发出推荐关键词的候选。对应到百度搜索引擎上,该步骤就是query改写变换及文档的检索。
  2. 相关性准入:考虑到后续的过滤步骤, 触发的关键词量一般需要比最终需要的关键词数量多以保证召回。此时需要对这些候选关键词进行相关性过滤。例如使用GBDT模型进行二分类: 相关 or 不相关。
  3. audit:推荐出的关键词可能涉及黄赌毒, 为避免风险, 这些关键词需在推荐时尽早过滤。搜索引擎上,也需要对一些黄赌毒反内容进行过滤。
  4. ranking:为提升KR推荐的效率, 使用提词率模型,效用模型及价值模型对剩下的候选关键词进行排序,同时需要根据应用场景对关键词进行过滤(例如用户有pv过滤需求,则需要将pv值小于阈值的关键词过滤);对应到百度上, 最重要的技术就是ctr预估及质量度。
  5. marketing rule:此处集中了人工干预的逻辑,例如: 假设某个时间段需要KR推荐该消费的关键词,此时可以在此处增加逻辑对候选关键词队列进行重排序; 或者对于某些bad case进行过滤。搜索引擎上也需要有该逻辑层, 以便最快速度对结果进行人工干预。
  6. UI:关键词的展现, 以及保存等功能,同时包含传统推荐系统的正负反馈信息收集,反馈等机制; 以及KR独有的关键词分组功能,信息筛选功能等。对应到搜索引擎上就是前端的展示。

主动推荐策略架构

KR中的主动推荐,就是传统的推荐技术在百度关键词搜索推荐中的应用。所谓主动,是针对KR而言的:关键词,广告主无需发起交互操作,KR即使用传统推荐技术: content-based, collaborative filtering及多种技术混合的hybrid filtering方法向广告主推荐结果。

以下为KR主动推荐的策略架构, 一方面KR使用网民搜索日志,点击日志,广告库数据构建item候选集合,另一方面系统收集广告主的反馈(explicit or implicit)构建user profile,之后基于这些信息使用推荐算法向客户进行推荐。如果KR中的搜索功能是即搜即得, 那么主动推荐就是不搜即得

图:百度关键词搜索推荐系统主动推荐策略架构

按网页内容进行推荐

百度凤巢广告主都有自己的推广网站(或主页),而要达到较好的推广效果,广告主应该提交与网页相关性较高的关键词,否则即使广告主因为提交了一个高PV的关键词导致来到网站的流量较高, 也会因为内容与关键词不相关而导致转化较低而得不偿失。

KR为此提供了按URL进行推荐, 即广告主在KR搜索框中输入某一个网址(例如semocean.com),则KR会抓取该网站并分析其中的主题词进行推荐, 以下为主要的策略流程。

图:KR按URL推荐策略处理流程

 

每一种KR推荐算法, 或者做一个延伸:每一个商业搜索引擎中, 都会包含以下几个模块:触发,相关性过滤,rank,marketing rule。

其中触发是根据输入,找到一个相对较大的候选集合, 之后的所有排序过滤都是针对该集合的(在学术界使用的数据;例如搜索引擎中,根据网民输入的query,进行简单的字面语义匹配后,找到潜在的候选集合作为后续处理的对,又例如在学术界使用的LTR任务的开放数据LETOR中,直接使用BM25进行校验,筛选出相关性较高的top N进行后续的ranking实验; 之后对返回的结果进行相关性过滤及排序,最后根据一些业务规则进行强制过滤及重排序,包括黄赌毒反动内容的过滤,或是某些特定的人工干预。

图:KR搜索推词逻辑

 

百度关键词工具介绍参见:http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596

google youtube 电影推荐算法

在面试实习生的时候,我有个习惯,就是面试快结束的时候,会像聊天一样和面试的学生聊一下他们对某个技术方向的看法。很多时候不是期望他们能提供什么灵感,也不期望能聊出太多结果,更多的是想通过这些沟通,看一下现在学生对这些问题的看法达到什么程度,而且这些沟通很能反映一个面试者的个性。 比如有些人对问题比较坚持, 或者叫做偏执,或者叫做执着,都能够反映出来。
前几天面试的时候到了最后环节的时候,忘了是说什么问题了,面试的实习生提到一般工业界使用的推荐算法都是比较简单的,不会去尝试复杂的算法。 我问他为什么,他说觉得工业界不会投入太多人力; 后来我告诉他还需要考虑处理的数据量和可维护性等因素。 当然他说的这个现象的确比较普遍: 工业界一般都倾向于使简单粗暴有效的算法,只有这些方法都搞不定时,才会尝试更复杂的潜在算法。
两个例子: 一个是 youtube 使用的电影推荐算法(参见论文: The Youtube Video Recommendation System);另一个例子就是Baidu关键词推荐系统中使用的级联二步图;  应该说Baidu关键词推荐系统中的级联二步图的思路是借鉴于youtube电影推荐算法并应用在关键词推荐的场景中。 下边就简单介绍下youtube Video推荐算法。
算法的思想其实比较简单:使用关联规则找到有关联的电影,计算权值后进行ranking推荐。其中的新意在于,这种关联关系能够进行多次传递,逐渐扩大和种子电影相关的电影集合(当然关系传递得越远,一般关联程度也会相应减弱)
具体的推荐过程可以分为3步:
建立video间的关系
建立video间关系的方式比较简单,使用关联规则中的共现方式即可。此处youtube使用的是24小时内session的co-visitation。具体为:
使用 r(vi, vj) = cij/f(vi,vj) 表示video i和video的关联程度, 其中 r为两个video/item的相关系数, ci为i,j共同出现次数, f 为 vi, vj归一化后的分母总量(最简单的方式就是ci * cj),这样就能找到相关的两个vedio
产生特定用户的video候选
该过程在经典信息检索中可以被理解为触发逻辑,及找到待推荐video/item的候选(触发逻辑在推荐系统中所处的位置及重要性参见另外一篇blog: 传统推荐引擎系统架构)
定义S为特定用户的种子video集合, 例如在youtube推荐系统中可以选择用户最新观看(或者最新完整观看的video),之后的问题就是怎么找到和种子词相关的video进行推荐。我们将其分为以下3步:
  1. 定义Cn(S)为和种子集合S相关联的,通过n步扩展后的推荐候选集合。 例如 C1(S) = 所有Ri的并, 其中Ri是与S中的vi相关联的v(寻找相关联v的过程参见上述:产生特定用户的video候选)。 相当于找到所有与S中种子vi想关联的v的并集;该做法的缺点是可能范围比较小且太相似。
  2. 使用Cn(S)进行触发, 即得到C(n-1)(S)后,再找到与C(n-1)(S)中每一个vi相关联的v,之后去除种子词S,我们称Cn(S)为对S的n步扩展。
  3. 同时在C(n)(S)中保留着每一个v被找到的原因, 便于后续ranking及给出explanation。
经过上述3步,对于特定user的候选video就触发完毕了。 该触发步骤可以说是该论文中的值得借鉴的点。 组里之前一位工程架构策略都很牛的同学指导实习生实现了一个通用的级联二步图算法框架, 该算法框架能够将有关联的节点的关系进行传递:
例如对于关键词,我们可以使用topic 主题(由topic model产生)建立关键词之间的跳转关系, 或是关键词中的核心term(一般是归一化后的核心term)建立跳转关系。 而该框架更令人着迷的是, 二步图的左右两边可以不是同样的item, 例如左边节点是keyword而右边是user, 则可以使用topic 直接建立keyword与user的关系进行推荐。
 Ranking
youtube 的ranking策略主要考虑以下3个因素:
  1. video质量, 这个可以通过网名对video投票打分得到。
  2. user specificity: 在触发后,可以通过使用user profile和电影的一些质量, 或是内容属性进行排序
  3. divercification:特别是类似video这种兴趣相关的内容, divercification的引入就显得非常重要了;相反, divercification在不同的场景下可能不同,百度关键词推荐中, 根据种子词直接检索得到的结果需要考虑与种子query的强相关性, 此时divercification的引入, 或者引入的程度需要比较慎重保守。
当然, ranking机制一般都会非常复杂, 论文中此处只是简单介绍; 例如在构造百度关键词推荐系统的过程中, 我们引入了提词率预估, 效用预估, 价值预估等模型对返回结果进行ranking。同时也需要结合user interaction的样式,算法出口等进行调整。 具体ranking机制会在后续blog中介绍。
效果上, 级联二步图的引入,能够找到非常多靠谱的结果(当然二步图边的建立是核心,选对了边的建立方式,才会有好效果),具体效果数据就不便透露了:)   反正是基本上能够覆盖全部凤巢用户,每个客户都能推出数量惊人的关键词(当然,需要使用字面, 语义等技术进行后续filtering and ranking)
更进一步, 级联二步图是图关系挖掘的一个简单有效的特例, 使用类似于pagerank等经典算法, 也能够很好地找出类似的关系进行推荐。
参考来源:
The Youtube Video Recommendation System
Google Adwords
也可关注微博: weibo.com
或者直接访问 http://semocean.com

google的商业产品之路

之前公司从google总部招了一位经验非常丰富的PM。入职后就请他给大家为大家布道google的商业产品推进的方法。 听了之后感触颇多, 在此与记录并与大家分享(因为自己也是学习别人在google的经验, 当中会加上一些自己工作中的感受, 其中有疑问的地方欢迎讨论)

        像google这样的公司, 做出的产品基本上能够直接影响到全球, 或者说是全人类的生活。 而它的商业产品, 也能够为这个公司成为你全球最大互联网公司提供收入保障。那google在进行商业产品的推进上,思路流程是怎样的呢?
        从系统产生, 项目开发的生命周期来看, 比较自然地就分为三个阶段: 提出想法, 设计, 执行/实现(即inspiration, design,   excution)
        首先是想法的提出(inspiration), google在提创意的原则是:‘ think big, start small’,作为世界级的公司,google 的产品都是直接影响全球的, 所以一般很多想法, 创意都是冲着改变整个产业去的(to change industry, to change world)。 例如google 比较成功的商业产品adwords,现在google大部分的收入, 都和这个产品有关; 又如百度的凤巢,贡献了百度绝大部分的变现。 当然不积跬步无以至千里, 一口也吃不成个胖子。 在一开始的时候虽然有着美好的憧憬和无端的自信, 做事的时候也是以某个具体的点入手, 开始逐步推进。
        然后是设计阶段(design)。  我们经常讲, 网民, 广告主, 搜索引擎三者参与商业产品的游戏, 三者相互关联, 获取自己想要的利益。  网民需要的是信息,  广告主进行自己信息的推广并希望在有限的支出下获取到最大的转化, 而搜索引擎希望从广告主获取最大化的利益。    而google 相较于通过搜索引擎从广告主获取最大利益, 更注重广告主的收益(至少我感觉跟国内搜索引擎公司相比), google的原则更像是: ‘make customers happy, and I’m happy’。 同时google认为advertisering is a repeat bussiness,让客户玩爽了, 客户才会持续地投入更多的钱, 从长远来说, 让客户爽就能挣更多的钱。 所谓细水长流, 才能天长地久; 但很多企业为了追求短期漂亮的财务报表, 不惜杀鸡取卵。
        另一个design阶段让我感触比较深的原则, 就是enpower users。 google(包括baidu等其他搜索引擎公司)其实是在做平台, 例如baidu未来的目标是成为全球第一大媒体平台, 全球有一半的人都在用baidu的产品。。。 而用户/客户才是平台上的主角, 平台的目的是让之上的参与者更高效, 所以google会有意地为客户提供各种提升效率的工具(self-help system and material helps customers),例如各种API, Batch工具,分析工具, 让客户随时随地能够满足自己的需求。 毕竟人民才是真正的用户,  PM,工程师的力量再大, 也大不过人民的群体智慧。
        在执行阶段, google 使用data driven的方式, 其实这个方式在很多策略型项目中都在使用:  dash board线性开发, 快速上线, 线上数据说话并根据效果的分析结论快速,持续迭代。 就算是失败, 也能从失败的数据中定位失败的原因, 然后迅速纠正。 总结起来就是: persistence(持续迭代优化), fail and learn(正确看待失败并从失败的经验,数据中进行改进), data driven(数据平台的建设)。  我是策略RD, 所以这方面感触比较深, 很多时候我们做的都是策略的优化,  最常见的情况是策略上线后效果不明显,甚至是负面效果, 此时对上线后的效果数据进行分析, 一般都能发现一些之前策略设计实现的时候没有碰到的问题, 之后策略中有针对性地对这些问题进行解决, 几次迭代后, 一般都能取得比较好的效果。
        当然google商业产品的思路, 远远不止这些, 而且各个公司的具体环境也不一样。种子只有在合适的突然才能发芽。此处也只记录了自己粗浅的理解及感受。
        写在最后,这位Google的PM大牛,就是现在力美的CTO梁信屏