知识准备-倒排索引 文档集 索引 关键思想：将文档初筛变成O(1)的时间复杂度 D0=``谷歌地图之父跳槽Facebook“ D3=``谷歌地图创始人跳槽Facebook与Wave项目取消有关“ D4=``谷歌地图创始人拉斯加盟社交网站Facebook“ 索引 谷歌→{D1, D2, D3, D4, D5} 地图→{D1, D2, D3, D4, D5} 之父→{D1, D2, D4, D5} 跳槽→{D1, D4,}， Facebook→{D1, D2, D3, D4, D5}， 加盟→{D2, D3, D5 }， … 关键思想：将文档初筛变成O(1)的时间复杂度

信息检索-向量空间模型 Bag of words IDF计算方法 文档相似度-余弦距离 关键思想：给出一种非训练的文档排序基线方法 D = (x1, x2, … ,xM) xm一般采用词表中第m个词在D中对应的TFIDF(Term frequency - Inverse Document Frequency)值 IDF计算方法 DF(m ) 为词m在其中出现的文档总数目，N 为总文档数目 IDF (m )=log(N / DF(m )) 文档相似度-余弦距离 cos(D1, D2) = D1T D2 / |D1||D2| 关键思想：给出一种非训练的文档排序基线方法

最优化方法-基本思路 最优化问题： 非约束优化： 问题不连续（自变量或目标函数离散取值） 问题连续但不宜求导 问题连续可导 组合优化(Combinatorial Optimization) 问题连续但不宜求导 下降单纯性法(Downhill Simplex) 问题连续可导 梯度下降法→牛顿法→拟牛顿法→L-BFGS Objective Constraints

最优化方法-拉格朗日方法 原问题(Primary problem) 拉格朗日(Lagrangian) 对偶函数(Dual function) 对偶问题 (Dual problem) 等式约束下的几何意义见右 KKT条件为保证此方法有效 的条件 凸优化情形下满足KKT条件， 但注意一些非凸优化也满足

常用统计模型 指数族分布: 指数族混合分布: Canonical form: 举例: Gaussian, multinomial, maximum entropy 最大似然(Maximum likelihood, ML)估计可以通过充分统计量(sufficient statistics)链接到数据 指数族混合分布: 例: Mixture of Gaussians, Hidden Markov Models, Probabilistic Latent Semantic Analysis (PLSI) ML估计可以通过EM算法迭代得到. 每个迭代中, 我们使用上一个迭代的统计量更新模型. 5 5

统计机器学习-Bayes 贝叶斯公式 几种学习体系

Map/Reduce 统计学习流程 框架流程: 在mapper中仅仅生成比较紧凑的统计量, 其大小正比于模型参数量, 与数据量无关 这样的流程可以抽象出来, 而具体的模型算法只需要关注统计量计算和更新两个函数 7 7

合约广告

广告位售卖和排期系统 供给方：广告排期系统 需求方：代理商 代表: 帮助媒体自动执行多个合同的排期 不提供受众定向，可以将广告素材直接插入页面 需求方：代理商 帮助广告商策划和执行排期 用经验和人工满足广告商质和量的需求 代表: 4A公司

担保式投送 担保式投送(Guaranteed Delivery, GD) 广告投放机(Ad server) 基于合约的广告机制，约定的量未完成需要向广告商补偿 量(Quantity)优先于质(Quality)的销售方式 多采用千次展示付费(Cost per Mille, CPM)方式结算 广告投放机(Ad server) CPM方式必然要求广告投送由服务器端完成决策 受众定向，CTR预测和流量预测是广告投放机的基础 GD合约下，投放机满足各合约的量，并尽可能优化各广告主流量的质

在线分配(Online Allocation)问题 … a=1 a=2 a=3 a=4 a=A … 在线到达的页面和用户 … c1 ,u1 c2 ,u2 Display ad problem 其他问题：Maximally Representative allocation Adwords problem 注意此处为NGD情形

简化匹配模型 假设：节点内部的流量差异可以忽略 需求节点(Demand Nodes, 订单要求的定向标签组合) 供给节点(Supply Nodes, 定向标签的最细组合) 假设：节点内部的流量差异可以忽略

在线随机最差性能研究 (with Free disposal) 原问题： 对偶问题： 对每个a, 初始化对偶变量βa为0 当展示i在线到达时, 将其分配给a’以最大化μia − βa 令xia’ = 1. 如果a’已经得到Ca’次展示, 令i’为使得此值最小的展示, 令xia’ = 0 在对偶问题中, 令zi=μia’ − βa’ , 并按照一定规则更新βa’ , 不同更新规则对应了不同的算法

Exponential Weighting 策略 算法 有效性 Greedy 对每个a, βa是分配给a的前Ca个高权重展示中最低的权重, 也即a接受一个新的展示需要抛弃的权重 1/2 competitive Uniform Weighting 对每个a, βa是分配给a的前Ca个高权重展示的权重的算术平均. 如果分配给a的展示少于Ca个, βa是这些展示总权重与Ca的比. Exponential Weighting 对每个a, βa是分配给a的前Ca个高权重展示的权重的指数加权。即：设μ1 ≤ μ2≤ …≤ μCa，则： 当Ca对每个a 都充分大时为(1 − 1/e) competitive

流量预测指导下的在线分配 目的 HWM(High Water Mark)算法 利于历史数据为在线分配提供指导 在线决策时避免存储xia(compact allocation plan) HWM(High Water Mark)算法 离线计划： 令每个人群维度组合k的剩余supply等于预测量rk = sk 按照分配优先级对每个a，解下式得到其serving rate αa : 对Γ(a)中的每个k, 令rk = rk – min{rk, skαa} 在线分配 对在线到来的某个impression, A = {a1, a2, …, a|A|}为按照分配优先级排序的所有满足要求的广告 按照A中的每个广告的serving rate随机分配其展示机会

核心业务： GD, 无法分配的流量转接到NGD(non-guaranteed delivery, 即Rightmedia exchange)进行变现 GD市场广告主数量为几千，年收入为Billion量级 其他点评： 采用compact allocation plan完成线上决策 提供下列受众定向 地域、人口属性、 行为(较为粗浅，常用的仅有几十个分类) 合约式销售中，品牌广告主对曝光有独占要求

流量预测 可以视为query为a, 对(u,c)进行检索的反向retrieval问题 由于(u,c) 联合空间规模过大，需要对u,c分别处理 c, #impressionc, pc(eCPM) 预测过程： 给定a, 首先通过c的索引找出所有符合条件c的集合 对每个c估计e(a, c)，并根据pc(eCPM)得到a在c上胜出的百分比p(a, c), 并将a的流量累加p(a, c)ⅹ #impressionc 上下文页面 该页面流量 该页面eCPM分布

合约广告投送系统

受众定向

中国互联网用户桌面

受众售卖 vs 广告位售卖

定向方法综述 阶段 定向方式 (见DSP部分) 曝光(exposure) 效果 上下文 (2.1, 3.1) 关注(attention) 重定向 (2.2, 2.3, 3.1) 行为 (2.3, 3.1) Look-alike (2.3, 3.1, 4.1, 6.1) 理解(comprehension) Hyper-local (2.3, 4.1) 地域 (2.3, 4.1) 信息接受 (message acceptance) 网站/频道 (2.3, 3.1, 4.2) 人口属性 (2.3, 3.1, 6.1) 保持 (retention) 购买(purchase) 作用阶段 (见DSP部分)

上下文定向(Contextual targeting) 举例 频道/URL定向，操作系统定向 按关键词、主题、分类等进行定向 与行为定向相比，架构有较大区别 常用方法 用规则将页面归类到一些频道或主题分类 提取页面中的关键词 提取页面入链锚文本中的关键词 提取页面流量来源中的搜索关键词 用主题模型将页面内容映射到语义空间的一组主题上

半在线(Near-line)抓取系统 用在线cache系统存储url -> 特征表以提供实时访问 不预先加载任何cache内容，对cache中不存在的url, 立刻返回空特征, 同时触发相应的页面爬虫和特征提取 设置cache系统合适的失效时间以完成特征自动更新