《计算广告 互联网商业变现的市场与技术》读书笔记。 书籍下载
三、 计算广告关键技术
9. 计算广告技术概述
个性化系统与搜索系统都是互联网时代具有挑战性的大规模计算问题。由于数据规模的要求，它们一般都采用检索（retrieval）加排序（ranking）这样类搜索的系统架构。将离线的分布式计算平台和在线的流计算平台相结合已经成为这样的系统生成个性化特征的常用方案。
9.1 个性化系统框架
一般的个性化系统由四个主体部分构成：
- 在线投放（online serving）引擎：用于实时响应请求，完成决策；
- 离线的分布式计算（distributed computing）数据处理平台；
- 用于在线实时反馈的流计算（stream computing）平台；
- 连接和转运以上三部分数据流的数据高速公路（data highway）
这几部分的协作流程：
- 在线投放系统的日志接入数据高速公路，再由数据高速公路快速转运到离线数据处理平台和在线流计算平台；
- 离线数据处理平台周期性地以批处理方式加工过去一段时间的数据，得到人群标签和其他模型参数，存放在高速缓存中，供在线投放系统决策时使用；
- 在线流计算平台则负责处理最近一小段时间的数据，得到准实时的用户标签和其他模型参数，也存放在高速缓存中，供在线投放系统决策时使用，这些是对离线处理结果的及时补充和调整。
9.2 各类广告系统优化目标
广告系统的优化目标是提高广告产品的利润也就是第 2 章中提到的计算广告核心挑战：
在广告系统中，每次展示的 $r$ 是由在线的投放引擎来决策的，而离线数据处理平台和流计算平台所做的都是为了准备 $a_i$，$u_i$，$c_i$ 这三个变量或其组合的一些特征。
9.3 计算广告系统架构
在一个完整的广告系统架构中，数据的记录、交易、流转、建模和使用，是广告系统最核心的驱动力，也从本质上决定了广告产品的变现能力和利润空间。
9.3.1 广告投放引擎
一般来说，广告系统的投放引擎采用类搜索的架构，即检索加排序的两阶段决策过程。另外，广告投放引擎还有一个独特模块，就是要从全局优化的角度对整体收益进行管理。
- 广告投放机（ad server）：串联各模块，最重要的指标是每秒查询数（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）：这部分来统一代表在各种广告系统中将局部广告排序的结果进一步调整，以全局收益最优为目的做调整的功能
- 广告请求接口：
- 定制化用户划分（customized audience segmentation）：这个部分指的是从广告主处收集用户信息的产品接口，而收集到的数据如果需要较复杂的加工，也将经过数据高速公路导入受众定向模块来完成
9.3.2 数据高速公路
数据高速公路完成的功能是将在线投放的数据准实时传输到离线分布式计算平台与流计算平台上，供后续处理和建模使用，它非常类似于人体的循环系统。由于在进行受众定向建模时需要用到广告系统以外的其他用户产品日志或者第三方提供的数据，因此，数据高速公路也担负着收集这些数据源的任务。
9.3.3 离线数据处理
计算广告最具挑战的算法问题大多都集中在离线数据处理的部分。离线数据处理有两个输出目标：
- 统计日志得到报表、dashboard 等，供决策人进行决策时作为参考；
- 利用数据挖掘、机器学习技术进行受众定向、点击率预估、分配策略规划等，为在线的机器决策提供支持。
离线数据处理有下面几个主要模块：
- 用户会话日志生成：从各个渠道收集的日志需要先整理成以用户 ID 为键的统一存储格式，这样的日志称为用户会话日志（session log）
- 行为定向（behaviorial targeting）：这部分功能完成挖掘用户日志，根据日志中的行为给用户打上结构化标签库（structural label base）中的某些标签并存储
- 上下文定向（contextual targeting）：这部分包括半在线页面抓取（near-Line page Fetcher）和上下文页面标签的缓存，与行为定向互相配合，负责给上下文页面打上标签，用于在线的广告投放中。
- 点击率建模（click modeling）：它的功能是在分布式计算平台上训练得到点击率的模型参数和相应特征（click model&features），加载到缓存中供线上投放系统决策时使用
- 分配规划（planning）：为在线的收益管理模块提供服务，它根据广告系统全局优化的具体需求，利用离线日志数据进行规划，得到适合线上执行的分配方案（allocation plan）。
- 商业智能（business intelligence，BI）系统。这部分包括 Extract-Transform-Load（ETL）过程、dashboard 和 cube，这些是所有以人为最终接口的数据处理和分析流程的总括，担负着对外信息交流的任务。
- 广告管理系统。这部分是广告操作者，即客户执行（Account Execute，AE）与广告系统的接口。
9.3.4 在线数据处理
在线数据处理是为了满足广告系统对实时数据反馈的要求，解决那些离线分布式计算平台无法快速响应的计算问题，经常选用流式管理平台作为基础设施。 在线数据处理主要包括以下模块：
- 在线反作弊（anti-spam）。实时判断流量来源中是否有作弊流量，并且将这部分流量从后续的计价和统计中去除掉，是广告业务非常重要的部分。此模块是所有后续在线数据处理必须经过的前置模块。
- 计费（billing）。
- 在线行为反馈，包括实时受众定向（real-time targeting）和实时点击反馈（realtime click feedback）等部分。这部分是将短时内发生的用户行为和广告日志及时地加工成实时用户标签以及实时的点击率模型特征。对于在线广告系统，这部分对于效果提升的意义重大：在很多情形下，把系统信息反馈调整做得更快比把模型预测做得更准确效果更加显著。
- 实时索引（real-time indexing）。这部分的主要功能是实时接受广告投放数据，建立倒排索引。
9.4 计算广告系统主要技术
从算法优化的角度看，主要有下面的一些问题，解决这些问题需要广泛用到机器学习、数据挖掘等一些相关学科的技术。
- 公式 2.2 中的特征提取，即对（a，u，c）打标签以方便后续建模和市场售卖的问题，是计算广告中非常核心的受众定向问题（参见第 12 章）。
- 如果不考虑全局最优，计算广告系统主要靠 eCPM 估计，特别是点击率预测（参见 13.5 节）来完成每一次展示时的局部优化。
- 如果考虑到量的约束和投放时即时决策的要求，则产生了在线分配的问题（参见 11.3 节）。
- 为了在多方博弈的市场中达到动态平衡时的收益最大化，则需要对市场的机制设计（mechanism design）（参见 5.2 节）深入研究，进而确定合理的定价策略。
- 为了更全面地采样整个（a，u，c）的空间以便更准确地估计点击率，需要用到强化学习（reinforcement learning）中的探索与利用（explore and exploit，E&E）（参见13.6 节）方法。
- 在实时竞价快速发展的今天，个性化推荐（personalized recommendation）技术也被广泛使用在效果类 DSP 的个性化重定向中（参见 14.2 节）。
从系统架构的角度看，计算广告在系统架构方面涉及以下一些技术问题。
- 由于广告主的预算、定向条件等信息在设置后需要快速在线上生效，需要用实时索引技术服务于广告候选的检索。
- 需要用 NoSQL 数据库为投放时提供用户、上下文标签和其他特征。
- 广泛使用 Hadoop 这样的 MapReduce 分布式计算平台进行大规模数据挖掘和建模，也用到流计算平台实现短时用户行为和点击反馈。
- 在广告交易市场中实现高并发、快速响应的实时竞价接口，这是一项广告中用到的独特技术
9.5 用开源工具搭建计算广告系统
对于初创型企业和变现业务方向尚需探索的企业来说，需要根据最小值原型（Minimum Value Prototype，MVP）的原则，低成本、短平快地搭建系统，然后在实际业务中进行快速迭代。
- Web 服务器 Nginx
- 分布式配置和集群管理工具 ZooKeeper
- 全文检索引擎 Lucene
- 跨语言通信接口 Thrift
- 数据高速公路 Flume
- 分布式数据处理平台 Hadoop
- 特征在线缓存 Redis
- 流计算平台 Storm
- 高效的迭代计算框架 Spark
10. 基础知识准备
10.1 信息检索
为了达到面向大量中小广告主时良好的扩展性，计算广告采用的是类搜索的技术框架，即检索加排序两段的决策过程。这里主要介绍倒排索引和向量空间模型。