广告中的计算问题精要.pptx

在线广告中的计算问题 360商业产品首席架构师 刘鹏 微博：@北冥乘海生 大数据与计算广告的关系 A：典型大数据问题，解决问题的效果随着采样率降低显著降低，例如计算广告、个性化推荐等 C：一般数据分析，非大数据问题，解决问题的效果在采样率降低时变化很小，例如各种洞察、单维度统计等 B：过渡类型问题，解决问题的效果随采样率降低温和下降，例如文本主题分析等 中美主要广告市场变化趋势 计算广告核心挑战 计算广告的核心问题，是为一系列用户与环境的组合，找到最合适的广告投放策略以优化整体广告活动的利润。 优化问题描述： 广告 用户 上下文 收入(eCPM) 成本 决策对象：一组广告展示 广告收入的分解 点击率 点击价值 计算广告中的技术问题 从优化角度来看 特征提取：受众定向 微观优化：eCPM估计 宏观优化：机制设计 受限优化：在线分配 强化学习：探索与利用 个性化重定向：推荐技术 从系统角度来看 整体框架：广告服务器 候选查询：实时索引 特征存储：No-sql技术 离线学习：Hadoop 在线学习：流计算 交易市场：实时竞价 主要广告产品优化目标分解 广告合约的流量分配模型 供给节点(Supply Nodes, 定向标签的最细组合) 需求节点(Demand Nodes,订单要求的定向标签组合) 假设：节点内部的流量差异可以忽略 I: A: E: 在线分配问题框架 问题目标函数 供给约束 需求约束 分配比例非负约束 供给节点i的总量 将供给节点i连接到 需求节点a的收益 优化变量xia：将供给节点i 分配给需求节点a的比例 在线分配典型问题 GD问题： Adwords问题： 基于对偶算法的紧凑分配方案 紧凑分配方案(Compact Allocation plan) 变量数正比于|A|，而非|E|或|I| 分配策略最好是无状态的，这样可以避免服务器之间的同步 由α恢复β和分配变量x: 由历史数据求解上述问题规模太大，需要对数据作一些采样以便更高效地得到分配方案。 行为定向建模 定向标签 该标签广告的 归一化点击数 频繁性参数 泊松分布 原始行为 N个特征选择函数 待优化系数 行为定向特征选择过程 位置拍卖市场 位置拍卖(Position auctions) 将对象 a={1, 2, … A} 排放到位置s={1, 2, …, S} 对象a的出价(bid)为ba , 而其对位置s的计价为uas=vaxs ,(x1x2 …xS) 将va视为点击价值，xs视为点击率，该模型可近似描述广告系统竞价问题(对显示广告，S = 1) 对称纳什均衡(Symmetric Nash equilibrium) (vs – ps) xs = (vs – pt) xt , 其中pt = bs+1 寻找收入最大化且稳定的纳什均衡状态是竞价系统设计的关键 机制设计-定价 广义第二高价(Generalized second pricing)机制 与VCG机制相比，会收取广告主更多的费用 整体市场不是truth-telling的 简单易行，为在线广告系统广泛采用 CPM情形下： ps = bs+1+1 CPC情形下：ps = rs+1 / μs+1= μs+1bs+1 / μs+1 VCG(Vickrey–Clarke–Groves)机制 某对象的收费等于给他人带来的价值损害： 整体市场是truth-telling的 Weight-And (WAND) 检索算法 文档和Query相似度: Term贡献上界ut，文档相关性上界Ua 算法概要 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. 点击率预测问题 点击率预测，在(a, u, c)组合与点击间建立关系： Regression比Ranking合适一些 广告的实际排序是根据eCPM，因此需要尽可能准确估计CTR，而不仅仅是各候选的CTR排序正确 新广告的cold-start 捕获点击率的动态特性 逻辑回归(Logistic Regression) 参数 特征 Logistic Regression模型 视角1：Generalized linear model 在Binomial error情形的特例 视角2：Maximum entropy model在类数目为2时的特例 优化方法 – L-BFGS BFGS (Broyden, Fletcher, Goldfarb, and Shanno) Quasi-New