背景

在CTR预估的早期，使用最多的方法时逻辑回归，逻辑回归通过Sigmoid函数，将函数值映射到0-1区间，映射之后的值就是CTR的预估值。

逻辑回归是线性模型，容易并行处理，而且可以轻松处理上亿条数据，但是学习能力有限，需要进行大量的特征工程，而且大量的特征工程并不一定会带来效果的提升，同时又耗时耗力。

FM模型通过隐变量的方式，虽然发现特征之间的两两组合关系，但也仅限于两两特征之间，在后来使用神经网络之前，GBDT也是一中有效思路。

为什么使用GBDT

对于单颗的决策树模型来说，表达能力有限，多棵树的表达能力更强，可以更好的发现有效的特征和特征组合。GBDT每棵树都在学习前面树一棵树尚存的不足，迭代多少次就生成多少颗树。相比较随机森林，GBDT的效果更加明显，而且对于GBDT来说，靠前的树，特征分裂主要体现对多数样本有区分度的特征，靠后的树，主要体现的是经过前面的N棵树，残差仍然较大的少数样本，也就是说，优先选用在整体上有区分度的特征，在选用针对少数样本由区分度的特征。

GBDT+LR的融合方案

关于GBDT和LR的融合方案，首先看一下Facebook的paper的例子：

图中有两棵树，x为一条输入样本，遍历两棵树后，x样本分别落在两棵树的叶子节点上，每个叶子节点对应LR的一维特征，通过遍历树，就得到了该样本对应的所有LR的特征。由于树的每条路径，是通过最小化均方差等方法最终分割出来的有区分性路径，根据该路径得到的特征以及特征组合都相对由区分性。其中，构造的新特征向量是取值0/1的。比如说，上图有两棵树，左树有三个叶子节点，右树有两个叶子节点，最终的特征即为五维的向量。对于输入x，假设它落在左树第一个节点，编码[1,0,0]，落在右树第二个节点则编码[0,1]，所以整体的编码为[1,0,0,0,1]，然后作为特征，输入到LR中进行分类。

GBDT 建树方案

对于广告来说，ID类特征在CTR预估中是非常重要的特征，而且广告也存在长尾问题。直接将ID作为特征建树并不可行，所以可以考虑为每个ID建树。针对长尾问题，在GBDT建树方案中，对于曝光充分、训练样本充足的广告，可以单独建树，发掘单个广告有区分度的特征，但对于曝光度不高、训练样本不足的广告，无法单独建树。

综合考虑，使用GBDT，非ID类建一类树，ID建一类树。1. 非ID类树：不以ID建树，此类树作为base，即便曝光少的广告、广告主，仍可以通过此类树得到有区分性的特征、特征组合。2. ID类树：以ID建一类树，用于发现曝光充分的ID对应有区分性的特征、特征组合。

对上述两类树，进行原始特征的映射，当一条样本进来之后，遍历两类树到叶子节点，得到的特征作为LR的输入。当AD曝光不充分不足以训练树时，其它非ID类树恰好作为补充。

GBDT 映射得到的特征空间维度， GBDT树有多少个叶子节点，通过GBDT得到的特征空间就有多大。如下图所示，一个叶子节点对应一种有区分度的特征或者特征组合，对应LR的一维特征。这棵树有8个叶子节点，既对应LR的8维特征。通过GBDT转换得到的特征空间较低，假设Base树、ID类树各N棵，则特征维度最高为 $(N+N\times 广告数+N\times 广告主数+N\times 广告类数)\times 叶子节点个数$ ，其中广告数、广告主数、广告类目数都是有限的，所以GBDT的特征空间维度并不高，而且不是每个ID样本都足以训练多棵树，所以实际维度更低。