大规模机器学习技术

夏粉
  2015年3月30日
 

Outline

• 广告背景
  • 大数据机器学习
  • 深度学习与CTR
  • 总结展望
 

搜索广告:
 
 
 Search
 Ads
 

展示广告：Display
 Ads
 

广告与点击
  率预估



广告核 心问题

• 给定环境下，用户与广告的最佳匹配 



流量 变现 profit = PV *CTR * ACP



方法

• 依赖机器学习和大数据，做精准CTR预估 

搜索  广告  系统 



Google  AdWords  

百度凤巢 



广告系统介绍
 

大致流程



展示  广告  系统 



Google  AdSense 

百度网盟 

RTB 

(Real Time  Bidding) 



广告候选 有广告位的展现



点击率预估



竞价排序

点击率（CTR）预估问题
 

Query l
例：鲜花



l
 cookie\历史搜 索



用户



l
 把广告放在第一位 l
 广告被用户点击的

概率



点击率 预估



广告商 l
鲜花网

展现 样式

Outline

• 广告背景
  • 大数据机器学习
  • 深度学习与CTR
  • 总结展望
 

大数据机器学习



大型分布式模型训练 



核心  技术 



大规模线性Logistic  Regression模型 



点击率



现状 



（CTR） 预估 



未来 



问题规模： 

• 数据存储和管理：上万台机器  • 数据量：百亿到千亿级  • 特征数：百亿到千亿级 （稀疏离散值特征） 



大规模深度学习模型 

 

CTR预估的机器学习流程
 



特征生成 

• 把广告展现成一个向量 



线上预测 

• 把模型用到新的广告展现上 



概率模型 

• 把向量变成点击率 



模型训练 

• 从历史数据学习模型参数 

离散特征生成
 



• 假设



:
 
 10000
 查询;
 1000
 用户;
 100
 广告
 



• 查询(q)：1
 ,
 2
 ,
 …
 ,
 10000
 



• 用户(u)：1
 ,
 2
 ,
 …
 ,
 1000
 



• 广告(a)：1
 ,
 2,
 …
 ,
 100
 



• 原始特征向量:
 q=1,u=2,ad=3
 



2
  3



64[ |1, 0,{.z. . , 0} ][ |0, 1, 0{,z. . . , 0} ][ |0, 0, 1,{0z, . . . , 0} ]75

10000-dim q-vector 1000-dim u-vector 100-dim ad-vector

高阶特征生成
 



• 1st
 阶：3
 种单维度特征 q,u,ad
 





46[ |1, 0,{.z. . , 0} ][ |0, 1, 0{,z. . . , 0} ][ |0, 0, 1,{0z, . . . , 0} ]75

10000-dim q-vector 1000-dim u-vector 100-dim ad-vector




 • 2nd
 阶： q*u 查询和用户特征组合


 
  [ |0, 0, . . . , 0{,z1, 0, . . . , 0} ]

10000⇥1000 dim q ⇥ u vecotr

超大  维度 

百亿到千亿量级 



离散特征影响
 

稀疏  特征 



特征  类型 



每个样本只有百个非零元 



百个特征类型 

维数约简
 



• 离散到离散：Hashing
 
 








  [ |0, 0, . . . , 0{,z1, 0, . . . , 0} ] ! 4[ 0|, . . .{,z1, . .}. ][ |0, . . .{,z1, . .}. ]5



10000⇥1000 dim q ⇥ u vecotr



1000dim hash table 1000 dim hash table



• 离散到统计：sta-s-cs
 





[ |0, 0, . . . , 0{,z1, 0, . . . , 0} ] ! 4 |0{.z4}



10000⇥1000 dim q ⇥ u vecotr



historic CTR



• 更多先进技术?
 



|1{0z3} · · · 5

historic show

模型:
 LogisIc
 Regression
 



• 模型假设 
 



– 输入向量
 x、输出点击率 ctr、模型参数 w
 




 


 



ctr



=



1 1 + exp(



w>x)



• 模型训练
 



– 训练数据
  (x1, y1), . . . , (xn, yn)

• X:
 特征向量
  • Y:
 {-­‐1,+1}
 
 
 ,
 
 -­‐1:
 未点检 ,
 +1：点检
 



Xn



– 求解优化问题：
  min

w



ln(1 + exp( w>xiyi)



i=1

模型:
 LogisIc
 Regression
 



• 正则化
 



– 减少模型大小
 




  Xn




 



min ln(1 + exp(

w i=1




 



• 求解算法
 



w>xiyi) + Ckwk1



Xd



， kwk1 =



|wj |



j =1




 wt wt 1 ⌘tdt ， dt :
 梯度方向(梯度或者牛顿方向)



– LBFGS:
 使用
 1st
 阶梯度近似Hessian矩阵
  – 坐标梯度下降:
 使用单维特征梯度
  – 随机梯度下降(SGD):
 
 使用单个样本梯度
 



w = [w1, . . . , wd]

分布式计算架构



数据并行 

Ø 每台机器存储所 有参数

Ø 每台数据存储部 分数据



模型并行 

Ø 每台机器存储所 有数据

Ø 每台机器存储部 分参数



数据&模型并行 

Ø 每台机器存储部 分数据

Ø 每台机器存储部 分参数

Outline

• 广告背景
  • 大数据机器学习
  • 深度学习与CTR
  • 总结展望
 

• CTR
 预估模型
 

日志处理



人工特征工程
 



特征抽取



模型训练



模型评估



单特征



组合特征



•site •Site-­‐Ad



•Ad •Site-­‐hour



•hour



•Ad-­‐cookie



•Cookie



•……




  •……



– 需要加入组合特征来提升LR的表达能力
 



–



假设有N个单特征类，组合特征类：
  2N −1



≈



C



1 N



+



C



2 N



+



C



3 N



+



...



+



C



N N



−1



– 人工挖掘，先验知识给出候选特征集合，依次加入模型训练
 



Ø 耗时！耗力！
 

深度特征学习技术



• 特征学习
 

– 深度学习在语音、图像上取得突破性进展
  – 广告数据特征维数非常高（单特征百亿），尚无大规模稀疏特征学习算法
 

• DANOVA:
 
 首个直接应用于大规模稀疏特征的深度特征学习算
 



高阶组合：Site-Ad-


  Cookie，…

二阶组合：Site-Ad, SiteHour, …

单特征：Site, Ad, Hour,  Cookie, …

• 上线效果
 

– 特征挖掘效率提升上千倍
  – CTR，CPM显著增长
 



…… 



逐 层 贪

婪 学

习

Outline

• 广告背景
  • 大数据机器学习
  • 深度学习与CTR
  • 总结展望
 

大数据点击率预测技术发展
 



一代：人工规则  
   

二代:
 40%+ 点击率提升 
 



简单特征
  小规模非线性模型
 



Yahoo,
 Facebook,
   Microso_,
 etc.
 



三代:
 10%+ 点击率提升 
 



高维特征
  大规模线性模型
 

模型实时更新
 



Google,
 Baidu,
 etc.
 



百度新一代模型
 

20%＋点击率提升
 



大规模



复杂模型




  
  技术全球领先
 

实时更新
 



流式计算
  模型在线更新
 

Google,
  Baidu,
 

etc.
 

Thanks！