Download presentation
Presentation is loading. Please wait.
1
知识准备-倒排索引 文档集 索引 关键思想：将文档初筛变成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)的时间复杂度
2
信息检索-向量空间模型 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| 关键思想：给出一种非训练的文档排序基线方法
3
最优化方法-基本思路 最优化问题： 非约束优化： 问题不连续（自变量或目标函数离散取值） 问题连续但不宜求导 问题连续可导
组合优化(Combinatorial Optimization) 问题连续但不宜求导 下降单纯性法(Downhill Simplex) 问题连续可导 梯度下降法→牛顿法→拟牛顿法→L-BFGS Objective Constraints
4
最优化方法-拉格朗日方法 原问题(Primary problem) 拉格朗日(Lagrangian) 对偶函数(Dual function)
对偶问题 (Dual problem) 等式约束下的几何意义见右 KKT条件为保证此方法有效 的条件 凸优化情形下满足KKT条件， 但注意一些非凸优化也满足
5
常用统计模型 指数族分布: 指数族混合分布: 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
6
统计机器学习-Bayes 贝叶斯公式 几种学习体系
7
Map/Reduce 统计学习流程 框架流程: 在mapper中仅仅生成比较紧凑的统计量, 其大小正比于模型参数量, 与数据量无关
这样的流程可以抽象出来, 而具体的模型算法只需要关注统计量计算和更新两个函数 7 7
8
合约广告
9
广告位售卖和排期系统 供给方：广告排期系统 需求方：代理商 代表: 帮助媒体自动执行多个合同的排期
不提供受众定向，可以将广告素材直接插入页面 需求方：代理商 帮助广告商策划和执行排期 用经验和人工满足广告商质和量的需求 代表: 4A公司
10
担保式投送 担保式投送(Guaranteed Delivery, GD) 广告投放机(Ad server)
基于合约的广告机制，约定的量未完成需要向广告商补偿 量(Quantity)优先于质(Quality)的销售方式 多采用千次展示付费(Cost per Mille, CPM)方式结算 广告投放机(Ad server) CPM方式必然要求广告投送由服务器端完成决策 受众定向，CTR预测和流量预测是广告投放机的基础 GD合约下，投放机满足各合约的量，并尽可能优化各广告主流量的质
11
在线分配(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情形
12
简化匹配模型 假设：节点内部的流量差异可以忽略 需求节点(Demand Nodes, 订单要求的定向标签组合)
供给节点(Supply Nodes, 定向标签的最细组合) 假设：节点内部的流量差异可以忽略
13
在线随机最差性能研究 (with Free disposal)
原问题： 对偶问题： 对每个a, 初始化对偶变量βa为0 当展示i在线到达时, 将其分配给a’以最大化μia − βa 令xia’ = 1. 如果a’已经得到Ca’次展示, 令i’为使得此值最小的展示, 令xia’ = 0 在对偶问题中, 令zi=μia’ − βa’ , 并按照一定规则更新βa’ , 不同更新规则对应了不同的算法
14
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
15
流量预测指导下的在线分配 目的 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随机分配其展示机会
16
核心业务： GD, 无法分配的流量转接到NGD(non-guaranteed delivery, 即Rightmedia exchange)进行变现 GD市场广告主数量为几千，年收入为Billion量级 其他点评： 采用compact allocation plan完成线上决策 提供下列受众定向 地域、人口属性、 行为(较为粗浅，常用的仅有几十个分类) 合约式销售中，品牌广告主对曝光有独占要求
17
流量预测 可以视为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分布
18
合约广告投送系统
19
受众定向
20
中国互联网用户桌面
21
受众售卖 vs 广告位售卖
22
定向方法综述 阶段 定向方式 (见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部分)
23
上下文定向(Contextual targeting)
举例 频道/URL定向，操作系统定向 按关键词、主题、分类等进行定向 与行为定向相比，架构有较大区别 常用方法 用规则将页面归类到一些频道或主题分类 提取页面中的关键词 提取页面入链锚文本中的关键词 提取页面流量来源中的搜索关键词 用主题模型将页面内容映射到语义空间的一组主题上
24
半在线(Near-line)抓取系统 用在线cache系统存储url -> 特征表以提供实时访问
不预先加载任何cache内容，对cache中不存在的url, 立刻返回空特征, 同时触发相应的页面爬虫和特征提取 设置cache系统合适的失效时间以完成特征自动更新
Similar presentations
