gbdt lr
gbdt+lr是facebook提出在线广告模型，我们知道LR之前在广告和推荐系统由于其快速的计算
而被广泛使用，使用由于lr是线性模型，其模型表现能力不强，需要做大量的特征工程。
facebook提出提出使用决策树进行特征embedding。
为了提升线性分类器的准确度，有两种方法进行特征变换：
- 对于连续特征。先进行离散化bin，然后把bin的编号作为离散型特征。这样的话，线性模型可以分段的学习到一个非线性的映射，在每一段内的映射是不变的。另外，对于bin边界的学习非常重要
- 对于离散特征。做笛卡尔积，生成的是tuple input features。笛卡尔积穷举了所有的特征组合，其中也包含部分没用的组合特征，不过可以筛选出来。
提升决策树(boosted decision tree)就可以很方便很好的实现上面我们说的这种非线性和tuple特征变换。对于一个样本，针对每一颗树得到一个类别型特征。该特征取值为样本在树中落入的叶节点的编号。举例来说：
上图中的提升决策树包含两棵子树，第一棵树包含3个叶节点，第二棵树包含2个叶节点。输入样本x，在两棵树种分别落入叶子节点2和叶子节点1。那么特征转换就得到特征向量[0 1 0 1 0]。也就是说，把叶节点编号进行one-hot编码。
那么， 怎么样直观的理解这种特征变化：
- 看做是一种有监督的特征编码。把实值的vector转换成紧凑的二值的vector。
- 从根节点到叶节点的一条路径，表示的是在特征上的一个特定的规则。所以，叶节点的编号代表了这种规则。表征了样本中的信息，而且进行了非线性的组合变换。
- 最后再对叶节点编号组合，相当于学习这些规则的权重。
核心思想
- 数据更新
由于推荐和广告等相关的问题，是一个动态的环境，需要对模型进行实时更新，所有对于lr进行在线学习和更新，gbdt可以每天或者几天更新一次。
- 在线学习的学习率如何设置
一般情况有很多学习率更新的方法，可以根据当前系统进行实验得到最好的学习率设置策略。论文中给出一下几种方法:
- Per-coordinate learning rate:
η t , i = α β + ∑ j = 1 t ▽ j , i 2 \eta_{t,i}=\frac{\alpha}{\beta+\sqrt{\sum_{j=1}^{t}}\bigtriangledown_{j,i}^2} ηt,i=β+∑j=1t ▽j,i2α
其中， α , β \alpha, \beta α,β是两个超参数. - Per-weight square root learning rate:
η t , i = α n t , i \eta_{t,i}=\frac{\alpha}{\sqrt{n_{t,i}}} ηt,i=nt,i α
其中， n t , i n_{t,i} nt,i是特征i所有实例的前t次的总和。 - Per-weight learning rate:
η t , i = α n t , i \eta_{t,i}=\frac{\alpha}{n_{t,i}} ηt,i=nt,iα - Global learning rate:
η t , i = α t \eta_{t,i}=\frac{\alpha}{\sqrt{t}} ηt,i=t α - Constant learning rate:
η t , i = α \eta_{t,i}=\alpha ηt,i=α
-
为了保证数据的新鲜性，需要进行在线数据加入，所有的曝光的实例，设置时间t，在时间t内被点击设置为label=1,否则设置label=0,注意时间t不能太大也不能太小，根据现实业务进行设置.
-
样本的均匀采样和负样本数据的下采样，由于负样本太多需要对负样本进行下采样。
-
Model Re-Calibration
负样本欠采样可以加快训练速度并提升模型性能。但是同样带来了问题：改变了训练数据分布。所以需要进行校准。
q = p p + ( 1 − p ) / w q=\frac{p}{p+(1-p)/w} q=p+(1−p)/wp
其中:
- w是采样率
- p是在采样后空间中给出的CTR预估值
- 计算得到的q就是修正后的结果
面试十问
- lr的权重个数和gbdt的什么有关?
lr的权重个数，等于gbdt所有叶子节点的个数.
- 负样本欠采样之后会对模型有什么影响，怎么解决?
负样本欠采样可以加快训练速度并提升模型性能。但是同样带来了问题：改变了训练数据分布。所以需要进行校准。
q = p p + ( 1 − p ) / w q=\frac{p}{p+(1-p)/w} q=p+(1−p)/wp
- GBDT特征的重要性是如何评估的?
特征j的全局重要度通过特征j在单颗树中的重要度的平均值来衡量:
J ^ j 2 = 1 M ∑ m = 1 M J ^ j 2 ( T m ) \hat J_j^2=\frac{1}{M}\sum_{m=1}^{M}\hat J_j^2(T_m) J^j2=M1m=1∑MJ^j2(Tm)
其中，M是树的数量，特征j在单棵树中的重要度如下:
J ^ j 2 ( T ) = ∑ t = 1 L − 1 i ^ j 2 I ( v t = j ) \hat J_j^2(T)=\sum_{t=1}^{L-1}\hat i_j^2 I(v_t=j) J^j2(T)=t=1∑L−1i^j2I(vt=j)
- gbdt+lr如何训练
一般是先训练gbdt在训练lr，首先将数据data分成两部分a和b，a用来训练gbdt，b用来训练lr。其中用a训练gbdt的时候，需要将a分成train_a, valid_a, test_a, 得到gbdt之后。将b通过gbdt得到所有对应叶子节点的下标进行one-hot编码.
继续训练b，将b通过gbdt得到update_b, 将update_b分成训练、验证和测试集，训练得到LR.
- 为什么建树采用ensemble决策树?
一棵树的表达能力很弱，不足以表达多个有区分性的特征组合，多棵树的表达能力更强一些。GBDT每棵树都在学习前面棵树尚存的不足，迭代多少次就会生成多少颗树。按paper以及Kaggle竞赛中的GBDT+LR融合方式，多棵树正好满足LR每条训练样本可以通过GBDT映射成多个特征的需求。
- 为什么建树采用GBDT而非RF?
RF也是多棵树，但从效果上有实践证明不如GBDT。且GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，这应该也是用GBDT的原因。
- GBDT与LR融合方案
AD ID类特征在CTR预估中是非常重要的特征，直接将AD ID作为feature进行建树不可行，故考虑为每个AD ID建GBDT树。但互联网时代长尾数据现象非常显著，广告也存在长尾现象，为了提升广告整体投放效果，不得不考虑长尾广告。在GBDT建树方案中，对于曝光充分训练样本充足的广告，可以单独建树，发掘对单个广告有区分度的特征，但对于曝光不充分样本不充足的长尾广告，无法单独建树，需要一种方案来解决长尾广告的问题。
综合考虑方案如下，使用GBDT建两类树，非ID建一类树，ID建一类树。
1）非ID类树：不以细粒度的ID建树，此类树作为base，即便曝光少的广告、广告主，仍可以通过此类树得到有区分性的特征、特征组合。
2）ID类树：以细粒度 的ID建一类树，用于发现曝光充分的ID对应有区分性的特征、特征组合。如何根据GBDT建的两类树，对原始特征进行映射？以如下图3为例，当一条样本x进来之后，遍历两类树到叶子节点，得到的特征作为LR的输入。当AD曝光不充分不足以训练树时，其它树恰好作为补充。
面试真题
- 为什么建树采用GBDT而非RF?