计算广告--笔记

文章目录

• • 概念
  • • 大数据与广告的关系
  • 二.计算广告基础
  • • 广告的有效性原理
  • 计算广告的技术特点
  • • 技术和计算导向
    • 效果的可衡量性
    • 创意和投放方式的标准化
    • 媒体概念的多样化
    • 计算广告的核心问题
    • 核心问题是为一系列用户与环境的组合找到最合适的广告投放策略以优化整体广告活动的利润
  • 三.在线广告产品概览
  • • 在线广告产品进化
    • 1.商业产品的设计原则
    • • 设计原则
      • 关键点
    • 2.需求方层级组织与接口
    • 3.供给方广利接口
  • 四.合约广告
  • • 概念
    • 1.广告位合约
    • 2.受众定向
    • • 受众定向方法
      • 受众定向标签体系
    • 展示量合约
    • • 流量预测
      • 流量塑性
      • 在线分配
  • 五.索与竞价广告
  • • 搜索广告产品新形势
    • 搜索广告产品策略
    • 查询匹配
    • 广告放置
    • 产品案例
    • 位置拍卖与竞价设计
    • • 定价问题
      • 市场保留价
      • 价格挤压
    • 广告网络
    • • • 广告网络的产品策略
        • 广告检索
        • 广告排序
      • 产品案例
    • 竞价广告需求方产品
    • • 搜索引擎营销
      • 媒体购买平台
  • 六.程序化交易广告
  • 七、移动互联与原生广告
  • • 原生广告相关产品
    • • 信息流广告
      • 搜索广告
      • 软文广告
      • 联盟
    • 移动广告的现状与挑战
    • • 移动广告的特点
      • 移动广告的创意形式
      • 移动广告的挑战
    • 原生广告平台
    • 原生广告与程序化交易
    • 延伸思考
  • 八、在线广告产品实践
• 主流产品核心技术概述
• • 九、计算广告技术概览
  • • 个性化系统框架
    • 各类广告系统优化目标
    • 计算广告系统框架
    • • 广告投放引擎
      • • 广告投放机器（ad server）
        • 广告检索（ad retrieval）
        • 广告排序（ad ranking）
        • 收益管理（yield management）
        • 广告请求接口
        • 定制化用户划分（customized audience segmentation）
      • 数据公路高速
      • 离线数据处理
      • 在线数据处理
    • 计算广告系统主要技术
    • 用开源工具搭建计算广告系统
  • 互联网广告的商业模式
  • • 互联网广告的竞价排序
    • 社交广告
    • 广告审核
    • 创建广告
    • 管理广告
    • 广告优化
  • 十.基础知识准备
  • • 匹配和相关技术
    • 信息检索（Information Retrieval，IR）
    • • 倒排索引
      • 向量空间模型
    • 最优化方法
    • • 拉格郎日法与凸优解
      • 下降单纯形法
      • 梯度下降法
      • 拟牛顿法
      • Trust-Region方法
    • 统计机器学习
    • • 最大熵与指数族分布
      • 混合模型和EM算法
      • 贝叶斯学习
    • 统计模型分布式计算优化框架
  • 十一.合约广告核心技术
  • • 广告排期系统
    • 担保式投送系统
    • • 流量预测
      • 频次控制
    • 在线分配
    • • 在线分配问题
      • • 供给与需求二部图
        • 需求约束与供给约束
        • 问题框架
      • 在线分配问题举例
      • • GD问题
        • AdWords 问题
        • 极限性能研究
        • 使用优化算法
  • 十二.受众定向核心技术
  • • 受众定向技术分类
    • 上下文定向
    • • 半在线抓取系统
      • 文本主题挖掘
      • • LSA模型
        • PLSI 模型和 GaP 模型
        • LDA模型
        • 有监督主题模型
    • 行为定向
    • • 行为定向建模问题
      • 行为定向特征生成
      • 行为定向决策过程
      • 行为定向的评测
    • 人口属性预测
  • 十三.

概念

广告主/出资人
广告商/媒体
受众

大数据与广告的关系

C类: 采样显著降低数据处理的复杂程度, 同时解决问题的效果没有太大的下降
A类: 不能通过处理一小小部分的数据来达到全量数据的效果,随采样数量的下降,收益会快速下降
B类: 数据达到一定规模后, 效果提升不明显

二.计算广告基础 广告的有效性原理

计算广告的技术特点 技术和计算导向 效果的可衡量性 创意和投放方式的标准化

如 视频广告的VAST标准和实时竞价的OpenRTB标准

媒体概念的多样化 计算广告的核心问题 核心问题是为一系列用户与环境的组合找到最合适的广告投放策略以优化整体广告活动的利润

其中auc分别为广告用户与环境.

三.在线广告产品概览 在线广告产品进化

1.商业产品的设计原则 设计原则

• 用户产品的设计原则:简单, 直观, 快捷
• 产品设计集中于: 关键功能的突出, 操作的流畅性

关键点

• 特别关注产品中的策略部分
• 特别光柱数据, 让运营和产品优化形成闭环

2.需求方层级组织与接口

• 需求方提供的广告是分层次管理的
• 广告的层次:
• • 广告主
• • 广告(推广)计划
• • 广告(推广)组
• • 广告创意

3.供给方广利接口

添加, 删除, 查看 各广告位的云隐数据

四.合约广告

概念

包括按 CPM 计费的展示量合约广告和按 CPT 结算的广告位合约。

• CPT, Cost Per Time
• CPM, Cost Per Mille

1.广告位合约

按CPT结算广告位合约：强曝光属性带来品牌冲击，或横幅位置长期独占购买有利于形成橱窗购买。

按照广告位轮播售卖，常见于中国门户网站的品牌广告中。

2.受众定向

按展示量结算合约广告产品的基础是按照受众售卖

受众定向方法

地域定向（geo-targeting）：广告主业务有区域性，上下文，查表；

人口属性定向（demographical targeting）：年龄、性别、教育程度、收入水平等；

频道定向（channel targeting）：内容分类体系将库存按照频道划分；

上下文定向（contextual targeting）：根据网页的具体内容来匹配相关广告，上下文定向粒度是关键词、主题或根据广告主需求确定的分类；

行为定向（behaviorial targeting）：根据用户历史访问行为了解用户兴趣，从而投送广告；

精确位置定向（hyper-local targeting）

重定向（retargeting）：对某个广告主过去一段时间的访客投放广告以提升效果；

新客推荐定向（look-alike targeting）：根据广告主提供的种子访客信息，结合广告平台更丰富数据，为广告主找到行为上相似的潜在客户；

团购（group-parchase）

受众定向标签体系

分类法制定一个层次标签体系，上层标签是下层的父节点，结构化标签体系。

不存在明确父子关系的半结构化或非结构化标签体系。

当标签作为广告投放直接标识，往往采用结构化标签体系；当标签仅仅是投放系统需要的中间变量，则没必要选择结构化标签。

展示量合约

CPM虽然是比较传统交易模式，但已经反映互联网广告计算驱动的本质：分析得到用户和上下文的属性，并由服务端根据这些属性及广告库情况动态决定广告候选。

流量预测

广告里一般的流量预测问题，可以描述成对流量 t（u，b）这个函数的估计，其中第一个参数 u 是给定的人群标签或人群标签的组合，第二个参数 b 是出价。在展示量合约中，由于没有竞价，可以看成是上述问题在 b→∞情形下的特例。

流量塑性

流量塑形的典型场景是综合性门户网站上售卖的展示量合约广告。

在线分配

各个合约要求的人群很可能大量交叠，如何设计分配策略，使得各个合约都尽可能被满足，将其简化为一个二部图（bipartite graph）匹配的问题。二部图的一方是表示广告库存的供给节点，每个节点代表的是所有人群标签都相同的广告流量集合；二部图的另一方是表示广告合约的需求节点，每个节点代表的是一个广告合约的人群标签条件。

五.索与竞价广告

广告竞价标定的物：上下文页面中的关键词，用户行为加工的兴趣标签，广告位。

• 搜索广告几乎全是竞价广告, CPC结算Cost Per Click
• 特点:
• 变现效率高
• 精准定向
• 竞价交易模式
• 搜索展示和自然结果展示形式接近

搜索广告变现能力，即eCPM远高于一般的展示广告；
搜索广告的受众定向标签，即是上下文的搜索查询。eCPM 由一般情形下的 r（a，u，c）退化成了 r（a，c）；
搜索广告的展示形式与自然结果的展示形式非常接近，往往仅仅在底色和文字链接中有不太引人注目的提示；
从搜索广告发展起来的竞价交易模式已经逐渐发展成为互联网广告最主流的交易模式；

搜索广告产品新形势

• 超越文字链的创意
• 弱相关广告形式
• 原生化探索

搜索广告产品策略

搜索广告的整个决策过程可以分为查询扩展、检索、排序、放置、定价等几个阶段。查询扩展是搜索广告独有的策略，目的是给广告主自动地拓展相关的查询词，扩大采买流量；广告检索和将候选广告根据 eCPM 排序是广告系统较为通用的核心流程，而定价是竞价广告非常核心的策略。
在搜索广告中，排序的依据，即 eCPM，可以简单地表示成 r（a，c）=µ（a，c）·bidCPC（a）。

查询匹配

精确匹配

不对广告主提供的关键词做任何形式的扩展，保证忠实按照广告主意图精准执行。

短语匹配

当用户的查询完全包含广告主关键词及关键词（包括关键词的同义词）的插入或颠倒形态时，就认为匹配成功，可以触发相应的广告候选。

广泛匹配

当用户的查询词与广告主的关键词高度相关时，即使广告主并未提交这些查询词，也可能被匹配。

否定匹配

同时向广告主提供否定匹配的功能，即明确指出哪些词是不能被匹配的，这样可以灵活地关停一些低效的流量。

广告放置

广告候选完成排序以后，需要分别确定北区数（North Foot Print，NFP，或 Average Show Number，ASN）和东区的广告条数，这个环节称为广告放置（ad placement），最关键的是进入北区的条件。从两各方面考虑：一是该广告相关性是否足够；二是该广告的 RPM （千次展示收益，Revenue per Mille，RPM）是否足够。前者是为了确保用户体验，后者是为了高效地利用展示位置

搜索广告的决策一般来说不太考虑用户 u 的影响，但是在确定北区广告条数这个问题上是个例外，这就是个性化的广告放置。

产品案例

Google AdWords

CPM->CPC->eCPM

淘宝直通车

在一些高商业价值的垂直搜索引擎（如电商、房产、汽车、应用下载）之中，利用搜索广告的产品体系进行变现是需要最优先考虑的流量变现方式。

位置拍卖与竞价设计

假设有一组广告位可以被占用，将这些广告位按照其经验价值排名，分别记为 s=1，2，···，S（对横幅广告而言，这里的 S 一般为 1）。在某次广告请求中，有一组广告 a=1，2，···，A 出价参与拍卖，每个广告的出价记为 ba，系统将前 S 个高出价的广告
依次放到前面排序好的 S 个广告位上，这样的问题称为位置拍卖（position auction）。根据前文的讨论，当某个广告 a 被放在 s 位置上时，其期望收益即 eCPM 为r_{as}=mu _{s}cdot upsilon _{a}。这里我们作了一些假设，比如，点击率 µ仅与位置 s 有关，而点击价值 ν 仅与广告 a 有关。

定价问题

整个竞价系统处于纳什均衡（Nash equilibrium）状态，即每个广告主都通过出价得到最符合自己利益的位置。其表达式如下：

V_s指的是排在 s 位置上的广告的点击价值，并非 s 位置带来的点击价值，而 q_{s} 指的是市场向排在 s 位置上的广告收取的费用，即定价，也就是广告主的单次投入。这一均衡状态的意义很容易理解：对于最终位置排名竞价结果中的每一条广告，其收益都比排在其他位置上要高。

常见的定价策略有GSP(Generalized Second Price)方案和VCG（Vickrey-Clarke-Groves）定价策略。

广义第二高价（GSP），指的是在只有一个位置的拍卖中，向赢得该位置的广告主收取其下一位广告主的出价。广义第二高价却有着实现简单、容易向广告主解释等诸多操作中的优点，因此在实际的竞价广告系统中是最主流的定价策略。

VCG，其基本思想是：对于赢得了某个位置的广告主，其所付出的成本应该等于他占据这个位置给其他市场参与者带来的价值损害。

市场保留价

为了控制广告的质量和保持一定的出售单价，竞价广告市场往往要设置一个赢得拍卖位置的最低价格，这一价格我们称为市场保留价（Market Reserve Price，MRP），俗称“起价”或“底价”。当竞争较充分、广告主深度足够时，MRP 可以设置得比较高；反之则应适当降低。

价格挤压

在 CPC 结算的广告产品中，eCPM 可以表示成点击率和出价的乘积，
但是在竞价的机制设计中，有时会对此公式做一些微调，把它变成下面的形式：

其中的 κ kappa κ为一个大于 0 的实数。可以考虑两种极端情况来理解kappa的作用：当 κ kappa κ→∞时，相当于只根据点击率来排序而不考虑出价的作用；反之，当 κ kappa κ→0 时，则相当于只根据出价来排序。因此，随着 κ kappa κ的增大，相当于我们在挤压出价在整个竞价体系中的作用，因此我们把这个因子叫做价格挤压（squashing）因子。
价格挤压因子的作用主要是能够根据市场情况更主动地影响竞价体系向着需要的方向发展。比如说，如果发现市场上存在大量的出价较高但品质不高的广告主，则可以通过调高 κ kappa κ来强调质量和用户反馈的影响；如果发现市场的竞价激烈程度不够，则可以通过降低 κ kappa κ来鼓励竞争，如果存在短期的财务压力，这样就可以短期使得整体营收有所上升；如果为了鼓励广告主提高广告质量和相关性，则可以通过提高 κ kappa κ来降低出价的影响。

广告网络

合约式的售卖方式必然无法消耗所有的库存，实际销售中为了控制售卖比例以获得更高的品牌溢价空间，未通过合约售卖的广告流量很多。这部分流量我们称为剩余流量（remnant inventory）。

竞价广告产品关键是，售卖的标的主要是人群，而广告位被淡化了。当流量满足多个广告活动的要求时，简单采用竞价模式而不用考虑量的合约。有下面几个关键特点：

• 竞价方式不向广告主做量的约定，而是根据变现能力，即 eCPM，来决定每次展示分配给哪个广告主；
• 由于是按人群售卖，广告网络会极力淡化媒体和广告位的概念，不适合广告主的品牌类需求；
• 从商业角度，提高市场流动性，改善广告网络运营方现金流；

广告网络的产品策略

决策过程分为检索、排序、定价等几个阶段。

广告检索

广告与搜索面对的文档其实不同，它往往是一个用布尔表达式表达的投放条件，而不是可以简单看成一个词的集合。

搜索广告检索与搜索基本一致，用常规的倒排索引技术就可以解决。展示广告网络与搜索广告不同，由于用户意图不明确，我们往往要将更多的关键字、兴趣标签同时用于检索过程。

广告排序

竞价广告中排序的准则是 eCPM，而在 CPC 结算的情形下，对 eCPM 的估计转化为对点击率的估计问题。广告网络中的 CTR 预测有两方面的困难：

• 点击数据更加稀疏，而且需要同时考虑上下文和用户量方面的信息，这使得各种新广告、新策略的冷启动问题非常突出；
• 广告网络中由于广告位的差别巨大，点击率的变动范围很大，这使得稳健地估计点击率变得相对困难；

产品案例

Google Display Network

淘宝客

竞价广告需求方产品

竞价广告需求可以分解为两个基本问题：

• 如何挑选合适目标人群；
• 如何对目标人群给出合适的出价；

搜索引擎营销

通过竞价采买搜索引擎关键词来做推广，这就是搜索引擎营销，即SEM。在SEM中具体表现是关键词和出价。

媒体购买平台

面向展示广告网络的一站式采买平台称为媒介采买平台，与之类似的概念还有交易终端（Trading Desk，TD）。难点在于ROI优化。

六.程序化交易广告

询价、出价和竞价在展示时进行，产生了以实时竞价即RTB为核心的程序化交易。由此产生广告交易平台ADX，其主要特征是用RTB的方式实时得到广告候选，并按照出价简单完成投放决策。与ADX对应的采买方，成为需求方平台DSP。

从需求方来看，定制化的用户划分能力使得广告主可以像优化自己的推荐系统那样优化广告购买，唯一的区别是这个推荐系统是放在站外的。出价需求的存在和广告主预算范围内的套利要求 DSP 具备点击率预测、点击价值估计、流量预测、站外推荐等多方面的运算能力。

RTB催化了另一个重要的市场：数据交易平台（data exchange）和数据管理平台 DMP

• 以实时竞价RTB为核心的程序化交易市场
• RTB的产生–>ADX平台(广告交易平台)
• RTB : real time bidding
• ADX: Ad Exchange
• DSP: Demand-Side Platform

七、移动互联与原生广告 原生广告相关产品 信息流广告

移动+社交
个性化推荐, 短视频

特点:

• 产品形式丰富
• 流量大,多样性强
• 可以承载几乎所有广告类型, 交易方式
  

搜索广告

在竞价广告产品中， 我们重点介绍了搜索广告， 现在可以换一个视角再作解读。搜索广告的展示形式与自然搜索结果基本一
致， 也可以看成是存在于同一个信息流当中。 因此， 它的高变现能力也部分地源于这种类原生的产品形式。 另外， 搜索广告的另一个特点， 即用一个明确的查询来触发广告， 对我们探索原生广告也很有启发： 要想真正做到“内容即广告”， 显然在广告决策过程中要明确考虑用户当前的任务和意图， 并直接根据这些来触发广告。搜索广告与内容的混合方式有两种， 一种是将广告在固定的位置上展现， 另一种是将广告与内容混合排列在一起。 当然， 在实际的搜索引擎中， 广告与内容也是来源于不同的服务， 前者按照 eCPM 排序， 后者按照相关性排序， 两者混合的规则也是一些固定的逻辑， 并没有实现按同一准则的统一排序。 应该说， 如果按照内容即广告的思路前进， 那么在搜索引擎中， 内容与广告按照同一准则的统一排序将会是一个有价值的发展方向。

软文广告

在这种广告类型中， 内容本身就是为了委婉地宣传某种产品而生产的。 很多网站的内容营销实际上指的就是这种软文广告。 这种方式也从一个独特的角度体现了“原生”的意义： 较高质量的软文往往让读者可以像接受普通文章一样接受其内容， 因而宣传效果也会比较好。http://news.pedaily.cn/201410/20141021372531.shtml给出了一条典型的软文“揭秘单品餐饮的暴利账本： 一道冒菜如何年入2亿？ ”请大家参考。 不过这种软文广告的生产和传播过程很难被标准化，往往只适用于比较大的品牌广告主， 不是产品化交易的对象， 因此并不是我们重点讨论的广告产品。

联盟

在前面介绍广告网络时， 我们提到了一种联盟（affiliate） 模式， 即由媒体从广告库中自由选择要推广的对象， 并按照自己控制的展现方式进行推广。 虽然说这是比较原始的广告产品形式，但也对原生的思路有一定启发： 只有给媒体一定的选择广告的权限， 才能比较容易地做到广告与内容在主题上的和谐， 也才会产生像淘宝客那样可以将广告自由地嵌入博客和各种网站。不过还是要说明， 这样简单的联盟方式并不是我们理想中的原生广告形式。 因为在这种方式下， 数据基本上无法发挥作用， 而且也并没有一个强大的第三方平台专业化地负责广告的运营和投放， 因此其市场相对原始， 规模化程度也有限。

移动广告的现状与挑战

移动互联网广告的产品和交易形式可以视为PC 互联网广告的自然延伸： 无论是PC上展示广告网络的方式还是搜索竞价排名的方式都在移动流量被变现的一开始就被移植到了移动环境下。

移动广告的特点

• 情境广告的可能性
• 大量潜在的本地化广告主

移动广告的创意形式

上面说到， 移动广告就其交易形态而言， 与PC广告并无本质区别。 但在广告的展现和转化路径上体现出比较独特的一面， 这也使得移动广告在 PC 广告创意形式的基础上衍生出一些新的形式， 如插屏广告和积分墙等。 这些新的创意形式， 一方面为传统的横幅广告提供了符合移动设备特点的补充， 另一方面也使得大家开始专门探讨和设计面向移动的创意方案。 就目前市场来看， 移动展示广告主要的创意形式有横幅、 插屏、 开屏、 锁屏、 推荐墙、 积分墙等。

移动广告的挑战

• 应用生态造成的行为数据割裂
• 许多PC时代广告主移动化程度还不够， 无法充分消化广告带来的流量
• 移动广告的产品形态需要一次革命

原生广告平台 原生广告与程序化交易 延伸思考 八、在线广告产品实践 主流产品核心技术概述 九、计算广告技术概览 个性化系统框架

一般个性化系统由四部分组成：用于实时响应请求，完成决策的在线投放（online serving）引擎，离线的分布式计算（distributed computing）数据处理平台，用于在线实时反馈的流计算（stream computing）平台，链接和运转以上三部分数据流的数据告诉公路（data highway）。

各个个性化系统由于其数据来源、产品形态、优化目标不同，细节上也会呈现不同。以个性化推荐、计算广告和搜索系统为例，如下。

各类广告系统优化目标

广告优化的目的是提高广告产品的利润：

在广告系统中，每次展示的 r 是由在线的投放引擎来决策的，而离线数据处理平台和流计算平台所做的都是为了准备 a i a_{i} ai​, u i u_{i} ui​, c i c_{i} ci​这三个变量或其组合的一些特征。主要广告产品优化目标分解：

计算广告系统框架

广告系统的建立应该是循序渐进的，对一个刚起步的广告产品，有广告投放机和相应的日志系统，实现简单的定向投放逻辑，就可以开始使用。随着对广告效果深入优化的需求，需要建立起完整的广告排序和用户行为反馈模型；而当中小广告主大量增加时，就需要实现广告的倒排索引和相应的检索功能。

广告投放引擎

广告系统的投放引擎采用类搜索的架构，即检索加排序的两阶段决策过程。

广告投放机器（ad server）

接受广告前端 Web 服务器发来的请求，完成广告投放决策并返回最后页面片段的主逻辑。广告投放机的主要任务是与其他各个功能模块打交道，并将它们串联起来完成在线广告投放决策。最重要的指标是每秒查询数（Query per Second，QPS）以及广告决策的延迟（latency）。

广告检索（ad retrieval）

在线时根据用户标签（user attributes）与页面标签（page attributes）从广告索引（ad index）中查找符合条件的广告候选。

广告排序（ad ranking）

是在线高效地计算广告的 eCPM，并进行排序的模块。eCPM 的计算主要依赖于点击率估计，这需要用到离线计算得到的 CTR 模型和特征（CTR Model&Features），有时还会用到流计算得到的实时点击率特征（real-time features）。在需要估计点击价值的广告产品（如按效果结算的 DSP）中，还需要一个点击价值估计的模型。

收益管理（yield management）

在各种广告系统中将局部广告排序的结果进一步调整，以全局收益最优为目的做调整的功能，如 GD 系统中的在线分配、DSP 中的出价策略等。

广告请求接口 定制化用户划分（customized audience segmentation）

由于广告是媒体替广告主完成用户接触，那么有时需要根据广告主的逻辑来划分用户群，这部分也是具有鲜明广告特色的模块。

数据公路高速 离线数据处理 在线数据处理

在线反作弊、计费、在线行为反馈、实时索引

计算广告系统主要技术

特征提取、eCPM估计（点击率预估）、在线分配、强化学习（reinforement learning）、个性化推荐（效果类DSP重定向

用开源工具搭建计算广告系统

nginx+zookeeper+lucene+thrift+flume+hadoop+redis+storm+spark

互联网广告的商业模式

CPM 每千次展示收费
CPC 每次点击收费
CPA 每次有效注册/激活计费

互联网广告的竞价排序

CPM出价: eCPM=CPM
CPC: eCPM=CPC*pCTR(预估点击率)1000
CPA: eCPM=CPApCVR(预估转化率)pCTR1000

以竞价排第二的价格来扣费

社交广告

信息流广告
CPT 按市场计价
GD Guarentee Dilivery
CPM
CPC
oCPC optimization CPC

广告审核 创建广告

创建广告账户
创建广告流程

管理广告

预览,操作,查看广告消息, 投放数据分析

广告优化 十.基础知识准备 匹配和相关技术 信息检索（Information Retrieval，IR） 倒排索引 向量空间模型 最优化方法 拉格郎日法与凸优解 下降单纯形法 梯度下降法 拟牛顿法 Trust-Region方法 统计机器学习 最大熵与指数族分布 混合模型和EM算法 贝叶斯学习 统计模型分布式计算优化框架

spark

十一.合约广告核心技术

合约广告的关键特征是广告投放的价格和量由双方协商约定。

广告排期系统

按 CPT 结算的广告位合约，媒体一般采用广告排期系统来管理和执行。广告排期系统与我们后面要讨论的各种广告系统都不同，因为它并不是一个个性化系统，也不太需要服务器端的动态决策。

担保式投送系统

与展示量合约对应的广告系统称为担保式投送（Guaranteed Delivery，GD）系统 。

这一系统的核心技术是在线分配的算法，除此之外，还有流量预测和频次控制两项重要技术。

流量预测

给定一组受众标签组合以及一个 eCPM 的阈值，估算在将来某个时间段内符合这些受众标签组合的条件、并且市场价在该 eCPM 阈值以下的广告展示量。

流量预测一般的方法其实并不是预测，而是根据历史数据的统计来拟合未来的流量。

工程上的主要挑战在于，给定的受众标签组合可能性非常多，不可能将所有这些组合都预先做好统计。可行的思路是将其视为一个反向检索的问题：在一般的广告检索问题中，索引的文档是广告 a，而查询是（u，c）上的标签；而在流量预测问题中，索引的文档由广告 a 变成了每次展示，而文档的内容即是这次展示上的（u，c）上的标签，而查询由（u，c）上的标签变成了广告设置的受众条件。

主要有以下几个步骤：

（1）准备文档。将历史流量中，（u，c）上的所有标签的展示合并为一个供给节点 i，并统计其总流量 si以及这部分流量上 eCPM 的直方图 h i s t i hist_{i} histi​。这样的每个供给节点作为流量预测反向索引的一篇文档。
（2）建立索引。对上一步生成的每个供给节点建立倒排索引，文档的 terms 即为此供给节点（u，c）上的所有标签。同时，在索引的正排表部分记录 s i s_{i} si​和 h i s t i hist_{i} histi​。
（3）查询结果。对一条输入的广告 a，将其限定的标签条件作为查询，得到所有符合条件的供给节点的集合。
（4）估算流量。遍历上一步得到的每个供给节点，对于某个供给节点 i，首先计算其与该广告 a 的 eCPM 即 r ( a , u i , c i ) = μ ( a , u i , c i )   b i d a r(a,u_{i},c_{i})=mu (a,u_{i},c_{i}), bid_{a} r(a,ui​,ci​)=μ(a,ui​,ci​)bida​，然后根据相应的 eCPM 直方图 h i s t i hist_{i} histi​计算 a 能获得的流量。这样，就可以估算出 a 在出价 b i d a bid_{a} bida​情形下近似能获得的流量。

频次控制

频次，指的是某个用户在一段时间内看到某个或某组广告的曝光次数。

传统广告三打理论（three hit theory）。在互联网广告中，随着某个用户看到同一个创意频次的上升，点击率呈下降的趋势这一点是可以被验证的。

广告主有时会要求根据频次控制（frequency capping）某个用户接触到某创意的次数，以达到提高性价比的目的。
注：在 CPC 结算的竞价广告中，可以将频次作为 CTR 预估的特征之一，从而隐式地对广告的重复展示进行控制。

频次控制有客户端和服务端两种解决方案，客户端解决方案把某个用户对某个广告创意的频次记录在cookie中，简单易行但扩展性不好；服务端是在后台专门设置用于频次记录和更新缓存，存在高并发读写要求。

在线分配 在线分配问题 供给与需求二部图

在线分配问题有两个主要的挑战：一是要在量的约束下优化效果；二是要实时对每一次展示作出决策。，一般将此问题简化为一个二部图（bipartite graph）匹配的问题。代表广告库存的供给节点（集合记为I，其中某个节点代表的是所有标签都相同的流量库存）和代表广告合约的需求节点（集合记为 A）。

如果某个供给节点的受众标签能够满足某个需求节点的要求，就在相应的两个节点间建立一条连接边。我们把这个二部图记为 G = （ I ∪ A ， E ） G=（I∪A，E ） G=（I∪A，E），其中 E 为 I 与 A 之间边的集合。任务就是求解由 i ∈ I i∈I i∈I到 a ∈ A a∈A a∈A的分配比例，使得满足供给方和需求方的约束的同时，某个与广告效果相关的目标函数达到最优。

这样的二部图结构实际上假设了在同样一组供给节点和需求节点之间发生的广告展示，其目标函数或回报 r 是没有差别的。r 由
（ a ， u ， c ） （a，u，c） （a，u，c）组合的函数变成了供给节点 i 和需求节点 a 的函数，将其记为$ r_{ia}$，目标函数表示为如下的形式：
F ( s , x ) = s i x i a r i a F(s,x)=s_{i}x_{ia}r_{ia} F(s,x)=si​xia​ria​

s i s_{i} si​为供给节点 i 的总供给量，而 X = X i a ∣ I ∣ × ∣ A ∣ X={X_{ia}}_{left | I right |times left | A right |} X=Xia​∣I∣×∣A∣​中的每个元素表示 s i s_{i} si​分配给合约 a的比例，这就是在线分配问题求解的变量。

需求约束与供给约束

在线分配问题的第一个约束条件是分配给某广告合约 a 的收益要至少等于其约定的量 d a d_{a} da​，这个约束称为需求约束（demand constraint）:

∑   ∈ Γ ( a )   q i a s i x i a ⩽ d a ,   ∀ a ∈ A sum, _{in Gamma (a)}, q_{ia}s_{i}x_{ia}leqslant d_{a},, forall ain A ∑∈Γ(a)​qia​si​xia​⩽da​,∀a∈A

其中 q i a q_{ia} qia​为将供给节点 i 连接到需求节点 a 的单位流量惩罚。

在线分配问题的另一个约束条件是每个供给节点被分配出去的量不能多于其总流量，这个约束称为供给约束（supply constraint）：

∑   a ∈ Γ ( i ) x i a ⩽ 1 ,   ∀ i ∈ I sum, _{a in Gamma (i)}x_{ia}leqslant 1,, forall iin I ∑a∈Γ(i)​xia​⩽1,∀i∈I

问题框架

根据上面讨论，引入供给约束与需求约束，得到下面的在线分配优化问题框架表示：

m a x   ∑   ( i , a ) ∈ E   s i x i a r i a max, sum,_{(i,a)in E}, s_{i}x_{ia}r_{ia} max∑(i,a)∈E​si​xia​ria​

s . t .   ∑   a ∈ Γ ( i ) x i a ⩽ 1 ,   ∀ i ∈ I s.t. , sum, _{a in Gamma (i)}x_{ia}leqslant 1,, forall iin I s.t.∑a∈Γ(i)​xia​⩽1,∀i∈I

∑   ∈ Γ ( a )   q i a s i x i a ⩽ d a ,   ∀ a ∈ A sum, _{in Gamma (a)}, q_{ia}s_{i}x_{ia}leqslant d_{a},, forall ain A ∑∈Γ(a)​qia​si​xia​⩽da​,∀a∈A

x i a ⩾ 0 ,   ∀ ( i , a ) ∈ E x_{ia}geqslant 0 ,, forall (i,a)in E xia​⩾0,∀(i,a)∈E

在线分配问题举例

在线分配技术并不仅仅适用于 GD 问题，其他典型的问题还有 AdWords 问题、展示广告问题、最大代表性分配（Maximal Representative Allocation，MRA）问题以及广告交易平台中的询价优化问题等。

GD问题

在 GD 合约的情形下，由于按 CPM 售卖广告在所有合约都满足时，如果不考虑合约 a未完成的惩罚，收益是一定的常数。那么 GD 的优化问题可以写成：
m a x   C max, C maxC

s . t .   ∑   a ∈ Γ ( i ) x i a ⩽ 1 ,   ∀ i ∈ I s.t. , sum, _{a in Gamma (i)}x_{ia}leqslant 1,, forall iin I s.t.∑a∈Γ(i)​xia​⩽1,∀i∈I

∑   ∈ Γ ( a )   s i x i a ⩽ d a ,   ∀ a ∈ A sum, _{in Gamma (a)}, s_{i}x_{ia}leqslant d_{a},, forall ain A ∑∈Γ(a)​si​xia​⩽da​,∀a∈A

x i a ⩾ 0 ,   ∀ ( i , a ) ∈ E x_{ia}geqslant 0 ,, forall (i,a)in E xia​⩾0,∀(i,a)∈E

AdWords 问题

AdWords 问题，也被称为有预算约束的出价（budgeted bidder）问题，讨论的是在CPC 结算的竞价广告环境下，给定各个广告主的预算，整体化市场营收的问题。其对应的在线分配问题体现为如下的形式：
m a x   ∑   ( i , a ) ∈ E   s i x i a r i a max, sum,_{(i,a)in E}, s_{i}x_{ia}r_{ia} max∑(i,a)∈E​si​xia​ria​

s . t .   ∑   a ∈ Γ ( i ) x i a ⩽ 1 ,   ∀ i ∈ I s.t. , sum, _{a in Gamma (i)}x_{ia}leqslant 1,, forall iin I s.t.∑a∈Γ(i)​xia​⩽1,∀i∈I

∑   ∈ Γ ( a )   q i a s i x i a ⩽ d a ,   ∀ a ∈ A sum, _{in Gamma (a)}, q_{ia}s_{i}x_{ia}leqslant d_{a},, forall ain A ∑∈Γ(a)​qia​si​xia​⩽da​,∀a∈A

x i a ⩾ 0 ,   ∀ ( i , a ) ∈ E x_{ia}geqslant 0 ,, forall (i,a)in E xia​⩾0,∀(i,a)∈E

把这里的供给节点 i 具体想象成搜索广告中的一个关键词。于是， q i a q_{ia} qia​代表的是将关键词 i 的一次点击分配给广告 a 的期望收益，即广告 a 对关键词 i 的出价； s i 为 s_{i}为 si​为关键词 i 的总点击量；而$ x_{ia}$为关键词 i 分配给广告 a 的流量比例。AdWords 问题的优化目标是整个市场的收入最大化；而需求约束的含义是每个广告主的花费应该小于该广告主的预算。

极限性能研究

极限性能研究的指标主要是某一在线分配策略的有效性。

所谓有效性可以描述如下：如果能够完全确知所有的流量分布情况，那么可以根据全局的信息求得一个分配的最优解；但是由于分配是在线执行，最优解并不一定能达到，如果某种在线分配策略在最差情形下能够达到上述最优解目标函数的 † † †倍，那么我们就说这一分配方案是†-competitive 的。显然，这里的†是一个[0，1]内的数，也就是该分配方案有效性的度量。

根据最优化拉格朗日算符可以表达为：

∑ ( i , a )   r i a s i x i a + ∑ i   a i [ ∑ a ∈ Γ ( i )   s i x i a − s i ] + ∑ a   β a [ ∑ a ∈ Γ ( a )   q i a s i x i a − d a ] − ∑ ( i , a )   r i a s i x i a small sum_{(i,a)}, r_{ia}s_{i}x_{ia}+sum_{i}, a_{i}[sum_{ain Gamma (i)}, s_{i}x_{ia}-s_{i}]+sum_{a}, beta _{a}[sum_{ain Gamma (a)},q_{ia}s_{i}x_{ia}-d_{a}]-sum_{(i,a)},r_{ia}s_{i}x_{ia} (i,a)∑​ria​si​xia​+i∑​ai​[a∈Γ(i)∑​si​xia​−si​]+a∑​βa​[a∈Γ(a)∑​qia​si​xia​−da​]−(i,a)∑​ria​si​xia​

不进行预测，把每次展示当作一个供给节点，则有small s_{i}=1，于是上式的对偶问题为：

m i n   ∑   a ∈ A d a β a + ∑   i ∈ I α i small min, sum, _{ain A}d_{a}beta _{a}+sum, _{iin I}alpha _{i} min∑a∈A​da​βa​+∑i∈I​αi​

s . t .   β a + α i ⩾ r i a small s.t., beta _{a}+alpha _{i}geqslant r_{ia} s.t.βa​+αi​⩾ria​

[ x i a , β a , a i ⩾ 0 ] small [x_{ia},beta _{a},a_{i}geqslant 0] [xia​,βa​,ai​⩾0]

原问题的每个约束条件对应着一个对偶变量，在线分配的一种优化方案有如下的几个步骤：

• 初始化每个需求约束的对偶变量 β a ← 0 small beta _{a}leftarrow 0 βa​←0
• 当一次展示 i 到达时，令 a 0 ← a r g   m a x a   r i a − β a small a^{0}leftarrow arg, max_{a}, r_{ia}-beta _{a} a0←argmaxa​ria​−βa​取得最大值的广告合约 a（即分配给收益最大的合约，如果该值对所有的广告都为负，则所有合约都不需要分配）
• 令 x i a 0 = 1 small x _{ia}0=1 xia​0=1，如果 a 0 small a^{0} a0已经被分配了 d a 0 small d_{a}0 da​0次展示，令 i 0 small i^{0} i0为其中最小的，并将 x i 0 a 0 small x_{i}0_{a}0 xi​0a​0设置为 0
• 在对偶问题中，令 a i = r i a 0 − β a 0 small a_{i}=r_{ia}0-beta _{a}0 ai​=ria​0−βa​0，并通过一定的更新规则来更新 β a 0 small beta _{a}0 βa​0。不同的更新规则对应了不同的分配算法，也相应地会导致不同的分配性能
  展示分配给最难满足的一个合约：是第 4 步如何更新 s m a l l β a 0 small beta _{a}0 smallβa​0，有如下几种典型策略：
  β a small beta _{a} βa​可以对应于将一个新的展示替换原有已分配给 a 的展示时，被替换掉的收益部分。

使用优化算法

假定未来一段时间内需要投放的合约是已知的，如果广告流量的分布在各个循环周期内是近似一致的，那么在线分配的问题就可以在流量预测的指导下进行，这是大多数在线分配实用工程方法的基本出发点。

• 直接求解的原始分配方案

假定流量的分布是平稳的，我们会利用历史流量数据来拟合未来流量small s _{i}，把在线分配转化成离线问题。

• 基于对偶算法的紧凑分配方案

为了分配方案的紧凑性，可否只保留需求约束对应的对偶变量，通过数学变换恢复出供给约束的对偶变量和分配率 x。

• 综合分配方案 SHALE

采用原始对偶方法迭代进行求解，每次迭代的过程中改善对偶解。

• 启发式的分配方案 HWM

高水位（High Water Mark，HWM）算法不仅有 紧凑分配、无状态的特性，效果上也能近似最优。

十二.受众定向核心技术 受众定向技术分类 上下文定向 半在线抓取系统

这一系统的设计关键是不作任何离线抓取，而在在线服务产生实际需求后才尽快抓取。

文本主题挖掘 LSA模型 PLSI 模型和 GaP 模型 LDA模型 有监督主题模型 行为定向

根据某用户一段时期内的各种网络行为，将该用户映射到某个定向标签上。

行为定向建模问题 行为定向特征生成

行为定向特征生成有两点需要讨论：一是特征选择函数 x t n small x_{tn} xtn​的确定，一是对应模型的训练集的组织和生成方式。

最常用的特征选择函数 x t n ( b ) small x_{tn}(b) xtn​(b)是将一段时间内的原始用户行为映射到确定的标签体系上，同时计算出各行为在对应标签上的累积强度作为模型的特征输入。
如何将行为累计控制在一段时间以内，工程上有两种常用的方法，分别是滑动窗口法和时间衰减法，如下所示。

滑动窗口法计算公式：

x ~ ( d ) = ∑ δ = 0 D x ( d − δ ) small widetilde{x}(d)=sum_{delta =0}^{D}x(d-delta ) x (d)=δ=0∑D​x(d−δ)

其中， x ~ small widetilde{x} x 代表累积特征以区别于单时间片特征 x small x x。

时间衰减法计算公式：

x ~ ( d ) = α x ~ ( d − 1 ) + x ( d ) small widetilde{x}(d)=alpha widetilde{x}(d-1)+x(d) x (d)=αx (d−1)+x(d)

从工程角度看，我们更推荐使用第二种方案。
行为定向的训练过程实际上就是调整各个标签类别上各种特征权重的过程。影响训练结果和效率的因素主要有两个：

• 训练集的长度；
• 时间片的大小；

训练集的样本数目正比于训练集长度且反比于时间片长度。当用户数目较多、训练集长度较长，而时间片又较短时，总的训练样本数目是非常大的。

行为定向决策过程

行为定向计算过程比训练过程的数据准备要简单，因为不再需要准备目标值，只需要按照滑动窗口法或者时间衰减法得到累积特征 再根据 w m small w_{m} wm​加权求和得到得分 λ small lambda λ。由于这一计算过程也是线性的，当特征累积采用时间衰减法时，得分small lambda也可以通过昨天的得分衰减后累积上今天得分的方式得到，即：

λ t ( d ) = ∑   n w n α x ~ t n ( d − 1 ) + ∑   n w n x t n ( d ) = α λ t ( d − 1 ) + ∑   n w n x t n ( d ) small lambda_{t}(d)=sum, _{n}w_{n }alphatilde{x}_{tn}(d-1)+sum, _{n}w_{n}x_{tn}(d)=alpha lambda _{t}(d-1)+sum, _{n}w_{n}x_{tn}(d) λt​(d)=∑n​wn​αx~tn​(d−1)+∑n​wn​xtn​(d)=αλt​(d−1)+∑n​wn​xtn​(d)

在线上存储各用户的定向标签得分 λ small lambda λ的缓存中，在每个新的时间周期，在缓存中得分乘以 α small alpha α进行衰减，再将上一个时间周期收集到的原始行为 x t n small x_{tn} xtn​加权求和后累加上去即可。

行为定向的评测

行为定向可以通过 reach/CTR 曲线来进行半定量的评测。在正常情况下，较小的人群规模应该较为精准，也即对该类型广告的 CTR 较高；而随着人群规模的扩大，该 CTR 也会逐渐走低。我们把标签接触到的人群规模称为 reach，而这一 reach 和 CTR
构成的曲线是评价该标签上的定向是否合理、以及效果如何的重要依据。

工程中需要注意的是，生成 reach/CTR 曲线的过程需要仅仅访问一遍数据就能完成。因此，在前面受众定向的过程中，需要保留的是每个用户在各个标签上的得分值，而不是最后二元的判断结果。

人口属性预测 十三.