竞价广告 - 精细数据变现

市场经济的规则:机制设计问题

竞价交易问题

  • 将对象a={1,2,…,A}排放到位置s={1,2,…,S}
  • 对象a的出价(bid)为$b_a$,而其对位置s的计价为$r_{as}=u_{s}v_{a}(u_1>u_2>…>u_S)$
  • $v_a$为点击价值,$u_s$视为点击率
  • 对称纳什均衡(Symmetric Nash equilibrium)
    • (vs-ps)xt >= (vs-pt)xt,其中pt=bs+1
    • 寻找收入最大化且稳定的纳什均衡状态是竞价系统设计的关键

P2.广义第二高价和VCG

  • 广义第二高价(Generalized Second Pricing)
    • 与VCG机制相比,会收取广告主更多的费用
    • 整体市场不是truth-telling的
    • 简单易行,为在线广告系统广泛采用
    • CPM情形下:$q_s = b_{s+1}+1$
    • CPC情形下:$q_s = r_{s+1}/u_+1=u_{s+1}b_{s+1}/u_s+1$
  • VCG(Vickrey-Clarke-Groves)机制
    • 某对象的收费等于给他人带来的价值损害
    • 整体市场是truth-telling的

      P2.市场保留价和价格挤压

  • 市场保留价(Market Reserve Price,MRP)
    • 即“底价”,出价高于MRP才能参与竞价
    • 收费如果小于底价,按底价计费
    • 可以根据不同的竞价标的设置不同的底价
  • 价格挤压
    • r = u * v -> r =u^k * v [r为eCPM,u为点击率,v为单价]
    • k为正数:当其充分大时,指根据点击率排序;当其接近0时,指根据点击单价排序

P2.整体计价过程

  • 见《计算广告》书中代码

P2.GSP广告竞价示例(货币单位:元,MRP=0.25)

###思考:如果竞价广告采用明拍,有什么优势。

最赚钱的广告产品:搜索广告

搜索广告基本产品形式

  • 分为北(North)、东(East)、南(South)三个区域
  • 广告一般带有底色
  • 位置次序:North1,North2,…,East1,East2,East3…
  • 南区或重复北区、或重复东区

搜索广告产品新形式

  • 原生广告探索:1.结构化的搜索结果,搜索结果页直接可以操作。2.将网站频道直接显示
  • 弱相关广告形式:东区,1.放弱相关的广告。2.相关推荐词

移动搜索广告

  • wap网页,没有东区
  • 淘宝:搜索结果页直接插入广告
  • 大众点评:搜索结果中间插入广告

搜索广告产品策略

  • 搜索广告产品策略
    • 1.查询扩展->检索->排序->放置->定价
  • 关键产品策略:
    • 查询扩展、广告排序、广告放置

搜索广告计算概貌

  • 优化目标:max u(a,c)*bid_cpc(a)
  • 关键特点:
    • 搜索广告的变现能力,即eCPM高于一般现实广告
    • 搜索广告的手中定向标签,即是上下文的搜索查询
    • 搜索广告样式与自然结果的展示形式非常接近,有原生广告的意味。
    • 从搜索广告展现起来的竞价交易模式,已经逐渐发展成互联网广告最主流的交易模式。

搜索广告系统架构

查询扩展主要模式

  • 精确匹配
    • 英语培训 -> {英语培训,培训英语}
  • 短语匹配
    • 英语培训 -> {英语培训暑假班,哪个英语培训机构好,英语的培训,英语相关培训,培训英语,英文培训,…}等
  • 广泛匹配
    • 英语培训 -> {外语培训班,四级证书,…}
  • 否定匹配

查询扩展主要方法

  • 基于推荐的方法
    • 在{Session,query}矩阵上通过推荐技术来产生相关的关键词
    • 利用的是搜索的日志数据
  • 基于主题模型的方法
    • 根据文档主题模型,对某个查询扩展出主题相似的其他查询
    • 利用的是一般的文档数据
  • 基于历史效果的方法
    • 记录某些对特定广告主eCPM较高的关键词
    • 利用广告本身的历史eCPM数据。

广告位智能放置

  • 广告放置(Ad Placement)问题
    • 广告候选完成排序以后,需要分别确定北区和东区广告条数
  • 用户体验指标
    • 北区广告的平均条数,即North Foot Print(NFP)或Average Serving Number(ASN)
  • 广告放置策略优化

思考

  • 1.搜索广告与展示广告最根本的技术区别是什么?
  • 2.社交信息流的广告放置问题应该如何建模。

Google AdWords

  • 产品概况
    • Google推出的关键词竞价广告产品
  • 其他点评:
    • 最早按CPM售卖,销售不理想
    • 后来采用Overture的CPC售卖,并创造性的引入点击率概念表达广告相关性,取得了非常高的营收
    • 2013年营收374亿美元。

淘宝直通车

  • 产品概况:
    • 淘宝专门服务于卖家的广告产品,在搜索结果等页面展示竞价广告
  • 其他点评:
    • 按CPC售卖,同样是按照eCPM排名
    • 广告主集中在电商行业,同时用户意图比通用搜索引擎更强烈
    • 与广告主是共生关系

剩余流量变现产品:竞价广告网络

竞价广告网络产品原理

广告网络产品示例

体验差/跟内容不相关

广告网络产品策略

  • 广告网络展示决策过程
    • 检索(根据受众标签)->排序->定价
  • 关键策略:
    • 广告检索、排序

广告网络计算概貌

  • 优化目标: max u(a,u,c)*bid_cpc(a)
  • 关键特点:
    • 竞价方式不向广告主做量的约定,而是根据变现能力,即eCPM,来决定每次展示分配给那个广告主。
    • 按人群售卖,淡化媒体和广告位的概念
    • 无需再满足广告主品牌独占的要求
    • 采用分成结算,运营方和现金流状况大为改善。【预充值】

广告网络系统架构

###思考

  • 1.广告网络适合品牌广告主么?为什么?
  • 2.广告网络和网盟有什么区别?

facebook audience networdk

  • 移动应用首选的变现方式
  • 对无FB张浩的用户不出广告oCPM/CPA的售卖方式
  • 目前供给和需求端都没有程序化接口

与搜索技术不同:广告检索技术

Lucene

  • 开源的全文检索引擎
    • 包括Index和Retrieval模块
    • 提供了简单易用的API,可以快速实现大量文档的检索
    • 采用分块索引提升Index响应速度
    • 实现了布尔查询、模糊查询等
  • 不支持相关性检索
  • 其他产品选择:Elastic Search

S3.布尔表达式检索

  • 广告投放条件的过滤可以视为布尔表达式检索问题
  • 布尔表达式检索的一些概念
    • Doc DNF:{age IN {3} ^ state IN {NY}) V ({state IN {CA} ^ gender NOT_IN {M})
    • Conjunction: age IN {3} & state IN {NY}, state IN {CA} ^ gender NOT_IN {M}。同一属性在某Conjunction里只出现一次
    • Assignment:age IN {3}, state IN {NY}, state IN {CA}…
    • sizeof[Conjuncion]: conjunction包含非的Assignment的个数
  • 基本思想
    • 某查询满足conjunction,也就满足包括此conjunction的doc
    • 维护两层倒排关系:Conjunction->DocID,Assignment->ConjuncionID
    • 如果sizeof(Conjunction)大于sizeof(query),则无需考虑

S3.布尔表达式检索 - index示例

S3.相关性检索

  • 根据(u,c)检索广告时
    • query有可能比较长,且子term都是should
    • 搜索引擎方案:Term之间取或关系,然后计算相关性并找到Top-N,在长Query和大文档集时查询速度被巨大的计算量缩限制。
  • 相关性检索
    • 在查找候选过程中做近似的评估,切掉那些理论上不需要再考虑的文档,只对进候选的文档进行相关性计算,比Top-N最小堆最小值大的插入
    • 当相关性函数为线性时,存在有效的剪枝算法。

S3.Weight-And(WAND)检索算法

  • 关键点
    • 根据term贡献上界u_t,文档相关性上界U_a去掉无法胜出的候选
  • 算法概要
    • step-1:按doclist最前面的DocID对terms排序
    • step-2:迭代terms,并累加UB知道大于堆顶,设此时到达第n-1个term,如果terms[0].doc和terms[n-1].doc一样,逼出一个doc至最小堆;如果不一样,再前n个term挑选一个skip到terms[n-1].doc,跳转至step-1.

S3.最近邻检索

  • 当把广告与用户向量化后,检索这个向量空间里最相关的K篇文档等价于计算向量距离并取K近邻的问题
  • 局部敏感哈希(LSH)
  • 层次K均值数(HKM)
    • 数据相关的局部敏感哈希

S3.语义检索 - word2vec

思考: 倒排索引再广告系统中是必须的么?

让系统更快的学习:短时数据统计与反馈

短时用户行为反馈

  • 短时用户行为
    • 狭义:用户在一个session内的行为
    • 广义:用户在短时间(一般为一两天)内的行为
  • 短时用户行为的反馈
    • 短时受众定向:根据短时用户行为为用户打上标签
    • 短时点击反馈:根据短时广告交互计算的动态特征
  • 短时用户行为计算
    • 需要准实时(分钟级)对用户行为进行加工,不适合在Hadoop上进行
    • 可以利用流式计算(stream computing)平台,如S4,Storm,Spark Streaming等。

流式计算平台 - Storm

  • 大规模实时数据处理框架,自动完成数据分发和可靠性管理,开发者只需要关注处理逻辑。数据流基本在网络和内存进行。
  • 计算逻辑类似Map/Reduce,区别在调度数据而非调度计算。

S6. kafka by Linkedin

  • 分布式消息系统,数据消费方式支持pull模式
  • O(1)复杂度的吃酒化和很高的吞吐率
  • 用Zookeeper来管理brokers

S6.Apache Storm By twitter

  • 大规模实时处理框架,自动完成数据分发和可靠性管理,开发者只需要关注处理逻辑
  • Storm on YARN 可以与Hadoop共享计算资源

用算法优化收入:点击率预测

A2.点击率预测问题

  • 点击率预测,在(a,u,c)组合与点击间建立关系:
    u(a,u,c) = p(h=1|a,u,c)
  • Regression 比 Ranking合适一些
    • 广告的实际排序是根据eCPM,因此需要尽可能准确的估计CTR,而不仅仅是各候选的CTR排序正确。
  • 问题关键
    • 新广告的cold-start
    • 捕获点击率的动态特性

      A2.逻辑回归(Logistic Regression)

  • 逻辑回归问题
    p(h|a,u, c) = sigmod((2h-1)w^Tx(a,u,c))
  • 实际带有正则化的优化问题
  • 可视为最大熵模型的特例,因此IIS方法适用

A2.动态特征 - 多层次点击反馈

  • 在标签组合维度上聚合点击反馈统计作为CTR预测的特征
  • 优势
    • 工程架构扩展性强(与在线学习相比)
    • 对新(a,u,c)组合有将强的back-off能力
  • 缺点
    • 在线特征存储量大,更新要求高
  • 组合维度举例
    • cookie(u)and creative(a)
    • gender(u)and topic(c)
    • category(a)and category(u)
    • creative(a)and gender(u)

A2.归一化点击率 - COEC

  • 有效展示
    • 可以通过Eye tracking测算
    • 工程上可以使用Expected Click(EC)来近似有效展示
  • EC的计算
    • 实测法:实际随机流量测算
    • Bias模型法:只使用与广告决策无关的bias特征训练模型的CTR模型:EC=P_{bias}(a,u,c)
  • 归一化点击率:COEC = sum click / sum EC

A2.在线广告常见bias特征

  • 广告位位置
    • 搜索广告:North1,North2,…,East1,East2,…
    • 显示广告:相对页面的(x,y)
  • 广告位尺寸
  • 广告位类型
    • 门户首页,频道首页,内容页,客户端..
  • 操作系统和浏览器
  • 广告投放延迟
  • 日期和时间

A2.消除偏差的点击率模型训练过程

A2.点击反馈的平滑

  • 问题: 在数据稀疏的情况下较稳健的估计CTR或者COEC
  • 经验贝叶斯方案
    • 点击产生概率模型:p(x|u)=U^{x}(1-u)^{1-x}
    • 视u为随机变量,采用Beta分布共轭先验进行正则化

A2.点击率模型的校准

  • 正负样本不均衡带来的估计误差
  • 误差对一些广义线性模型都存在,包括LR
  • 可以通过数据计算并校准

A2.FM点击率模型

  • LR:所有组合特征需要用特征工程解决
  • 因子分解剂(Factorization Machines,FM)
    • 计算复杂度与LR相同
    • 优化方法:随级梯度下降、交替最小二乘

A2.深度学习点击模型

A2.评测指标- PR曲线和ROC曲线

思考:事件中点击率预估最有用的是哪类特征?

未知领域的冷启动:探索与利用

A5. 探索与利用(E&E)问题与思路

  • 问题
    • 为长尾的(a,u,c)创造展示机会以积累统计量,从而更准确预估CTR
    • 提升整体的广告收入,即需要严格控制探索的量和有效性
  • 方法思路
    • 通常描述为Multi-arm Bandit(MAB)问题
    • 有限个arms(或者收益提供者)a,每个有确定有限的期望收益E(r_{i,a})
    • 在每个时刻t,我们必须从arms中选择一个,最终目标是优化整体收益
    • 基本方法为e-greedy;将e比例的小部分流量用于随机探索
  • 广告问题的主要挑战
    • 海量的组合空间需要被探索
    • 各个arm的期望收益是被动变化的

如何利用竞价市场:竞价广告需求方产品

搜索引擎营销(SEM)

  • 产品目标
    • 帮助搜索广告主管理预算,优化商业目标
    • 主要商业目标:花费、ROI
  • 主要功能
    • 基础功能:管理campaign和关键词,实现便捷操作
    • 高级功能:拓词、自动价格优化

广告购买平台(Trading Desk)

  • 产品目标:
    • 帮助广告主按人群进行跨媒体和广告网络采买
  • 关键特征:
    • 连接到不同广告网络和DSP,提供统一市场
    • 非实时竞价投放的ROI优化能力
    • 广告代理功能大多有此概念型产品

非RTB流量的ROI优化

  • 目标
    • 给定总预算,在多广告网络中采买并优化ROI
  • 关键问题
    • 在合适的流量segment上投放广告
    • SEM中选词,显示广告网络中的标签组合选择
    • 在每个投放上合理的出价以优化ROI
    • 与RTB不同,采买方无法控制每次展示的出价
    • u,c的取值未知,需要在流量分割上估计其分布并合理出价

思考:在非RTB流量的ROI优化过程中,最重要的操作原则是什么?