百度网盟广告相关技术

[TOC]

  • 视频:http://www.chuanke.com/v2889565-173289-848527.html
  • 笔记:http://www.yittoo.com/blog/index.php/2016/05/13/large-scale-ml-ctr-prediction/
  • 笔记:http://www.doesbetter.com/638/

广告系统流程

  1. 广告位展现
  2. 广告候选:初选,简单规则,触发
  3. 点击率预估:对初选集合进行预估,机器学习方法
  4. 竞价排序:auction机制

维度约简

  • 离散到离散 hashing:10000x1000dim (q,u)vector -> 1000dim hash table (有collision)
  • 离散到统计 statistics:10000x1000dim (q,u)vector -> historic ctr, historic impr

维度约减

关键是减少信息的损失

分布式计算架构

  • 数据并行:每台机器存储部分数据、所有参数,适合图像数据
  • 模型并行:每台机器存储所有数据、部分参数,适合基因数据
  • 数据模型并行:每台机器存储部分数据、部分参数,适合广告数据

技术实战

数据采样

Google KDD’13

采样

  • 正样本:被点击的query
  • 负样本:$r \in (0,1]$ 的概率选取未被点击的query

矫正

  • $w_t = 1$ 如果事件t在被点击的query
  • $w_t = \frac1r$ 如果事件t在未被点击的query

原理:采样后的期望损失等于原损失

百度的改进:在期望之外还保证方差相等。

噪音检测

SA算法

计算CTR随时间变化趋势,可以把非人为的随机点击样本过滤掉。

通过对每个时间片断波峰和波谷的观察,知道随机噪音的值在什么范围,通过分值可以对噪音进行过滤。

  • 随机噪音:sa=0.00275
  • 正常样本:sa=-10.977

特征删减

背景:模型大小占特征大小比例极低

挑战:训练之前,判断哪些特征权值为0

特征类型:categorical features,连续值特征

特征表示:one-hot编码

Google:新特征按概率p加入;Bloom Filter+次数超过N;AucLoss升高。

特征删减

Fea-G算法

理论保证删减特征AUC效果无损

在模型训练之前,就知道几个有效特征在哪儿,或者可以找到尽可能小的包含有效特征的集合。谷歌的技术是启发性的,有可能会带来损失。而百度的技术是用理论保障,经过严格的推导,它可以在效果无损的情况下,删减的非常多的无效特征。

自动调参

AdaLasso算法

智能选择超参 $c_j$

深度特征学习技术

由于广告特征维度太高,无法直接使用DNN,解决方法:

  1. 特征压缩,减少特征维度
  2. 原始特征,找出稠密特征,在此基础上再做特征组合 【注】样本比较密集才能把一个特征描述清楚。

DANOVA

大规模稀疏特征的深度特征学习算法。听起来是分布式的ANOVA?

上线效果:特征挖掘效率显著提升上千倍;CTR、CPM显著增长

单特征->二阶组合->…->高阶组合:逐层贪婪学习

模型时效性

模型更新越快,对新广告和新广告主效果好。

要模型更新快,模型更新时,训练数据需要尽可能少。

技术挑战:稀疏性、时效性、稳定性

方法:稀疏在线算法 => 增量数据->增量模型->…->增量数据->增量模型

现状:大部分在线算法非稀疏;Google FTRL保留前N次模型梯度方法(FTRL-Proximal)——不够稳

SOA算法

模型稳定性更好

训练架构:batch处理改为online learning,节省存储资源50%以上

在线学习平台:大数据分钟级别在线学习

经验:时效性上的收益是非线性的,半小时内的收益非常显著。

模型训练

LBFGS近似Hessian矩阵,convergence较慢

寻找更好的优化方向+步长,减少迭代次数

Shooting算法

针对广告数据特征分布不均衡的特点,改进了算法迭代求解的方向和步长,在广告数据上取得了比业界常用的大规模优化算法LBFGS快十倍的性能。估计类似adagrad、adam之类?

性能变化:相比LBFGS训练轮数从平均50轮下降到5轮,且训练更充分

总结展望

  • 一代:人工规则
  • 二代:特征压缩,小规模非线性模型
  • 三代:原始高维特征,大规模线性模型,模型实时更新
  • 四代:Pulsar 大规模、复杂模型、实时更新

百度Pulsar

  • 数据量:千亿样本、千亿特征
  • 模型:浅层到深层灵活支持(深层代价高,对简单业务用浅层就够了)
  • DNN:万亿链接神经网络
  • 调研:自动化特征学习&参数调节(自适应样本采集、特征学习、参数调整、结构学习)
  • 时效性:分钟级别更新模型
  • 评估:可视化模型&数据分析

Reference

  • FTRL-Proximal:Ad Click Prediction: a View from the Trenches, KDD’13 https://www.eecs.tufts.edu/~dsculley/papers/ad-click-prediction.pdf
  • Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization http://www.jmlr.org/proceedings/papers/v15/mcmahan11b/mcmahan11b.pdf
  • 百度BDL:http://bdl.baidu.com/index.html
  • BDL publications:http://bdl.baidu.com/publication.html
  • A Survey of Algorithms and Analysis for Adaptive Online Learning, arxiv 2015, http://arxiv.org/pdf/1403.3465v3.pdf
  • Scaling Distributed Machine Learning with the Parameter Server, OSDI’14 https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-li_mu.pdf
  • A Comparison of Lasso-type Algorithms on Distributed Parallel Machine Learning Platforms, NIPS’14 http://stanford.edu/~rezab/nips2014workshop/submits/plasso.pdf
  • A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization, arxiv 2016, http://arxiv.org/pdf/1604.03763.pdf
  • Paddle:Parallel Distributed Deep Learning at Baidu https://github.com/baidu/Paddle