[Spark on Angel] GBDT

GBDT(Gradient Boosting Decision Tree)的相关原理部分可以参考

1. GBDT在Spark on Angel上的实现

Spark中的RDD

  • instance: RDD[(Id, Instance)]：保存着训练样本的RDD，在算法循环迭代过程中，该RDD不会重新生成
  • gradient: RDD[(Id, (Gradient, Hessian)))]：保存每个样本对应的一阶、二阶梯度值，每棵树会生成新的RDD
  • prediction: RDD[(Id, Prediction)]：保存每个样本在当前模型下的预测值，每棵树会生成新的RDD

Angel PS上的PSMatrix

  • instanceLayout：保存instance RDD每个partition的样本落地哪个树节点的信息
  • gradHistogram：保存树的每个叶子节点的梯度直方图
  • gbtModel：包含三个矩阵，分别是树节点的分离的特征ID、特征值，以及叶子节点的权重
    • 每棵树中，每个节点分裂的特征ID
    • 每棵树中，每个节点分裂的特征值
    • 叶子节点的权重

GBDT的伪代码如下所示：

  1.   val instance: RDD[(Id, Instance)]
  2.   var gradient: RDD[(Id, (Gradient, Hessian)))]
  3.   var prediction: RDD[(Id, Prediction)]
  4.   val instanceLayout, gradHistogram, gbtModel: PSMatrix
  5.   sparkcontext.broadcast(createSketch(instance))
  6.   While (treeNum < maxTreeNum) {
  7.     (1) val tree = new Tree()
  8.     // Calculate instance gradient
  9.     (2) gradient = calcGrad(instance, prediction, instanceLayout)
  10.     While (tree.depth < maxDepth) {
  11.          // Build gradient histogram
  12.        (3.1) gradHistogram.push(buildHist(instance, gradient, instanceLayout))
  13.        // Find best split with PS function
  14.        (3.2) gbtModel.update(findSplit(gradHist))
  15.        (3.3) growTree(tree, gbtModel); layout.update(tree)
  16.      }
  17.      (4) prediction = updatePrediction(instance, gbtModel)
  18.   }

[Spark on Angel] GBDT - 图1

2 算法参数

  • 数据参数

    • classNum：训练数据类别数
    • validateFraction：验证集比例，范围：0~1.0
    • partitionNum：训练数据RDD的分区数

  • 算法参数

    • maxTreeNum：最大树棵数
    • maxDepth：树的最大深度
    • splitNum：每个特征的分位点数
    • featureSampleRate：参与每棵树训练的特征比例
    • learningRate：学习率
    • regLambda：L2正则系数
    • regAlpha：L1正则系数
    • loss：损失函数类型

3 算法Benchmark

// TODO