计算广告|5.竞价广告-精细数据变现

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

竞价交易问题

将对象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和大文档集时查询速度被巨大的计算量缩限制。

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优化过程中，最重要的操作原则是什么？

计算广告

计算广告竞价广告

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

计算广告|6.多方数据变现-程序化交易上一篇

计算广告|4.合约广告下一篇