细语呢喃

技术改变生活

0%

『我爱机器学习』集成学习（四）LightGBM

发表于 分类于 ， 阅读次数： 评论数：

本文介绍LightGBM，它是一款常用的GBDT工具包，由微软亚洲研究院（MSRA）进行开发，在Github上开源的三天内收获1000 star。其速度比XGBoost快，并且精度也相当的不错。

接下来看看其算法的内容。

注意其设计理念：

  1. 单个机器在不牺牲速度的情况下，尽可能多地用上更多的数据；
  2. 多机并行的时候，通信的代价尽可能地低，并且在计算上可以做到线性加速。

于是其使用分布式 GBDT，选择了基于 histogram 的决策树算法。

直方图算法

回顾一下XGBoost中的Exact greedy算法：

  1. 对每个特征都按照特征值进行排序
  2. 在每个排好序的特征都寻找最优切分点
  3. 用最优切分点进行切分

这个算法比较精确，但是缺点明显：

  1. 空间消耗大。需要保存数据的特征值。XGBoost采用Block结构，存储指向样本的索引，需要消耗两倍的内存。
  2. 时间开销大。在寻找最优切分点时，要对每个特征都进行排序，还要对每个特征的每个值都进行了遍历，并计算增益。
  3. 对Cache不友好。使用Block块预排序后，特征对梯度的访问是按照索引来获取的，是一种随机访问，而不同特征访问顺序也不一样，容易照成命中率低的问题。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的Cachemiss。

使用直方图算法进行划分点的查找可以很好的克服这些缺点。

PS: XGBoost不是有Cache aware access优化么？但是看LightGBM的对比实验，还是直方图的快。

直方图算法

直方图算法(Histogram algorithm)的做法是把连续的浮点特征值离散化为k个整数（其实又是分桶的思想，而这些桶称为bin）比如\([0,0.1) \rightarrow 0,\ [0.1,0.3) \rightarrow 1\)。

同时，将特征根据其所在的bin进行梯度累加。这样，遍历一次数据后，直方图累积了需要的梯度信息，然后可以直接根据直方图，寻找最优的切分点。

LightGBM-histogram

其算法大致描述如下：

LightGBM-histogram-algorithm

仔细看上面的伪代码，相信你有几个问题：

  • 如何将特征映射到bin呢？即如何分桶？
  • 如何构建直方图？直方图算法累加的g是什么？
  • 构建完直方图如何找最优特征，有用到二阶信息么？

如何分桶呢？

首先，在读取数据后，就决定每个特征如何分桶。（在feature_group.h文件中，FeatureGroup 的其中一个构造函数）

那么如何分桶呢？对于数值型特征和类别特征采用不同的做法。

数值型特征

对于数值型的特征，关键是寻找分割点，关键代码如下，其中max_bin为最大bin的数量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
std::vector<double> GreedyFindBin(const double* distinct_values, const int* counts,
    int num_distinct_values, int max_bin, size_t total_cnt, int min_data_in_bin) {
	  // counts为特征取值计数

    std::vector<double> bin_upper_bound;
    CHECK(max_bin > 0);
	// 特征取值数比max_bin数量少，直接取distinct_values的中点放置
    if (num_distinct_values <= max_bin) {
      bin_upper_bound.clear();
      int cur_cnt_inbin = 0;
      for (int i = 0; i < num_distinct_values - 1; ++i) {
        cur_cnt_inbin += counts[i];
        if (cur_cnt_inbin >= min_data_in_bin) {
          auto val = Common::GetDoubleUpperBound((distinct_values[i] + distinct_values[i + 1]) / 2.0);
          if (bin_upper_bound.empty() || !Common::CheckDoubleEqualOrdered(bin_upper_bound.back(), val)) {
            bin_upper_bound.push_back(val);
            cur_cnt_inbin = 0;
          }
        }
      }
      cur_cnt_inbin += counts[num_distinct_values - 1];
      bin_upper_bound.push_back(std::numeric_limits<double>::infinity());
    } 
	else { // 特征取值比max_bin来得大，说明几个特征取值要共用一个bin
      if (min_data_in_bin > 0) {
        max_bin = std::min(max_bin, static_cast<int>(total_cnt / min_data_in_bin));
        max_bin = std::max(max_bin, 1);
      }
      double mean_bin_size = static_cast<double>(total_cnt) / max_bin;

      // mean size for one bin
      int rest_bin_cnt = max_bin;
      int rest_sample_cnt = static_cast<int>(total_cnt);
      std::vector<bool> is_big_count_value(num_distinct_values, false);

	  // 标记一个特征取值数超过mean，因为这些特征需要单独一个bin
      for (int i = 0; i < num_distinct_values; ++i) {
        if (counts[i] >= mean_bin_size) {
          is_big_count_value[i] = true;
          --rest_bin_cnt;
          rest_sample_cnt -= counts[i];
        }
      }

	  //剩下的特征取值中平均每个bin的取值个数
      mean_bin_size = static_cast<double>(rest_sample_cnt) / rest_bin_cnt;
      std::vector<double> upper_bounds(max_bin, std::numeric_limits<double>::infinity());
      std::vector<double> lower_bounds(max_bin, std::numeric_limits<double>::infinity());

      int bin_cnt = 0;
      lower_bounds[bin_cnt] = distinct_values[0];
      int cur_cnt_inbin = 0;
      for (int i = 0; i < num_distinct_values - 1; ++i) {
        if (!is_big_count_value[i]) {
          rest_sample_cnt -= counts[i];
        }
        cur_cnt_inbin += counts[i];
        // need a new bin，当前的特征如果是需要单独成一个bin，或者当前几个特征计数超过了mean_bin_size，或者下一个是需要独立成列的
        if (is_big_count_value[i] || cur_cnt_inbin >= mean_bin_size ||
          (is_big_count_value[i + 1] && cur_cnt_inbin >= std::max(1.0, mean_bin_size * 0.5f))) {
          upper_bounds[bin_cnt] = distinct_values[i]; // 第i个bin的最大就是 distinct_values[i]了
          ++bin_cnt;
          lower_bounds[bin_cnt] = distinct_values[i + 1]; //下一个bin的最小就是distinct_values[i + 1]，注意先++bin了
          if (bin_cnt >= max_bin - 1) { break; }
          cur_cnt_inbin = 0;
          if (!is_big_count_value[i]) {
            --rest_bin_cnt;
            mean_bin_size = rest_sample_cnt / static_cast<double>(rest_bin_cnt);
          }
        }
      }
      ++bin_cnt;
      // update bin upper bound
      bin_upper_bound.clear();
      for (int i = 0; i < bin_cnt - 1; ++i) {
        auto val = Common::GetDoubleUpperBound((upper_bounds[i] + lower_bounds[i + 1]) / 2.0);
        if (bin_upper_bound.empty() || !Common::CheckDoubleEqualOrdered(bin_upper_bound.back(), val)) {
          bin_upper_bound.push_back(val);
        }
      }
      // last bin upper bound
      bin_upper_bound.push_back(std::numeric_limits<double>::infinity());
    }
    return bin_upper_bound;
  }

上述的代码找到了数值型特征取值的各个bin的切分点，即bin_upper_bound，之后只需要根据这个对特征的取值查找其相应的bin中即可（用二分搜索）。

类别特征

对于类别特征来说，主要代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// sort by counts
Common::SortForPair<int, int>(counts_int, distinct_values_int, 0, true);
// avoid first bin is zero
if (distinct_values_int[0] == 0) {
    if (counts_int.size() == 1) {
        counts_int.push_back(0);
        distinct_values_int.push_back(distinct_values_int[0] + 1);
    }
    std::swap(counts_int[0], counts_int[1]);
    std::swap(distinct_values_int[0], distinct_values_int[1]);
}
// will ignore the categorical of small counts
int cut_cnt = static_cast<int>((total_sample_cnt - na_cnt) * 0.99f);
size_t cur_cat = 0;
categorical_2_bin_.clear();
bin_2_categorical_.clear();
num_bin_ = 0;
int used_cnt = 0;
max_bin = std::min(static_cast<int>(distinct_values_int.size()), max_bin);
cnt_in_bin.clear();
while (cur_cat < distinct_values_int.size()
       && (used_cnt < cut_cnt || num_bin_ < max_bin)) {
    if (counts_int[cur_cat] < min_data_in_bin && cur_cat > 1) {
        break;
    }
    bin_2_categorical_.push_back(distinct_values_int[cur_cat]);
    categorical_2_bin_[distinct_values_int[cur_cat]] = static_cast<unsigned int>(num_bin_);
    used_cnt += counts_int[cur_cat];
    cnt_in_bin.push_back(counts_int[cur_cat]);
    ++num_bin_;
    ++cur_cat;
}

关键点有：

  1. 首先对特征取值按出现的次数排序（大到小）,
  2. 取前min(max_bin, distinct_values_int.size())中的每个特征做第3步（这样可能忽略一些出现次数很少的特征取值）：
  3. 然后用\(bin\_2\_categorical\_\)（vector类型）记录b对应的特征取值，以及用\(categorical\_2\_bin\_\)(unordered_map类型) 将特征取值到哪个bin和一一对应起来。这样，以后就能很方便的进行bin到特征取值和特征取值到bin的转化。

构建直方图

给定一个特征的取值，我们现在已经可以转化为对应的bin了。现在我们就可以构建直方图了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void ConstructHistogram(const data_size_t* data_indices, data_size_t num_data,
                          const score_t* ordered_gradients, const score_t* ordered_hessians,
                          HistogramBinEntry* out) const override {
    const data_size_t rest = num_data & 0x3;
    data_size_t i = 0;
    for (; i < num_data - rest; i += 4) {
        const VAL_T bin0 = data_[data_indices[i]];
        const VAL_T bin1 = data_[data_indices[i + 1]];
        const VAL_T bin2 = data_[data_indices[i + 2]];
        const VAL_T bin3 = data_[data_indices[i + 3]];

        out[bin0].sum_gradients += ordered_gradients[i];
        out[bin1].sum_gradients += ordered_gradients[i + 1];
        out[bin2].sum_gradients += ordered_gradients[i + 2];
        out[bin3].sum_gradients += ordered_gradients[i + 3];

        out[bin0].sum_hessians += ordered_hessians[i];
        out[bin1].sum_hessians += ordered_hessians[i + 1];
        out[bin2].sum_hessians += ordered_hessians[i + 2];
        out[bin3].sum_hessians += ordered_hessians[i + 3];

        ++out[bin0].cnt;
        ++out[bin1].cnt;
        ++out[bin2].cnt;
        ++out[bin3].cnt;
    }
    for (; i < num_data; ++i) {
        const VAL_T bin = data_[data_indices[i]];
        out[bin].sum_gradients += ordered_gradients[i];
        out[bin].sum_hessians += ordered_hessians[i];
        ++out[bin].cnt;
    }
}

可以看到，累加了一阶和二阶梯度，同时还累加了梯度的和还有个数。（当然还有其它的版本，当\(\bf is\_constant\_hessian\)为true的时候是不用二阶梯度的）

寻找最优切分点

对每个特征都构建好直方图后，就可以进行最优切分点的构建了。

遍历所有的特征，对于每个特征调用FindBestThreshold如下函数：

1
2
3
4
5
6
void FindBestThreshold(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint, SplitInfo* output) {
    output->default_left = true;
    output->gain = kMinScore;
    find_best_threshold_fun_(sum_gradient, sum_hessian + 2 * kEpsilon, num_data, min_constraint, max_constraint, output);
    output->gain *= meta_->penalty;
}

同样的，对于数值型和类型特征，处理方法find_best_threshold_fun_是不一样的。

在讲具体做法前，首先讲一个Trick，可以加速直方图计算过程，即直方图做差加速。

直方图做差加速

直方图算法还可以进一步加速：一个叶子节点的直方图可以由它的父亲节点的直方图与其兄弟的直方图做差得到。

LightGBM-histogram-subtraction

原来构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的#bin个桶。使用这个方法，构建完一个叶子的直方图后，可以用非常微小的代价得到它兄弟的直方图，相当于速度提升了一倍。

数值型特征

对于数值型特征，find_best_threshold_fun_函数如下（我去除了一些if条件，这里只是为了说明计算过程）:

1
2
3
4
5
6
7
8
9
10
11
12
void FindBestThresholdNumerical(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint, SplitInfo* output) {
    is_splittable_ = false;
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
                                         meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
    FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, true, false);
    FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, true, false);
    output->gain -= min_gain_shift;
    output->monotone_type = meta_->monotone_type;
    output->min_constraint = min_constraint;
    output->max_constraint = max_constraint;
  }

可以看到FindBestThresholdSequence被调用了两次，分别是从左到右和从右向左，类似XGBoost的缺失值自动寻找划分方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void FindBestThresholdSequence(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint, double min_gain_shift, SplitInfo* output, int dir, bool skip_default_bin, bool use_na_as_missing) {
    
    const int8_t bias = meta_->bias;
    double best_sum_left_gradient = NAN;
    double best_sum_left_hessian = NAN;
    double best_gain = kMinScore;
    data_size_t best_left_count = 0;
    uint32_t best_threshold = static_cast<uint32_t>(meta_->num_bin);

    if (dir == -1) { // from right to left
		.......
    } else { // from left to right
      double sum_left_gradient = 0.0f;
      double sum_left_hessian = kEpsilon;
      data_size_t left_count = 0;

      int t = 0;
      const int t_end = meta_->num_bin - 2 - bias;

      for (; t <= t_end; ++t) {

	    sum_left_gradient += data_[t].sum_gradients;
	    sum_left_hessian += data_[t].sum_hessians;
	    left_count += data_[t].cnt;
       
        data_size_t right_count = num_data - left_count;
        double sum_right_hessian = sum_hessian - sum_left_hessian;
        double sum_right_gradient = sum_gradient - sum_left_gradient;
        // current split gain
        double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                            meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
                                            min_constraint, max_constraint, meta_->monotone_type);
        // gain with split is worse than without split
        if (current_gain <= min_gain_shift) continue;

        // mark to is splittable
        is_splittable_ = true;
        // better split point
        if (current_gain > best_gain) {
          best_left_count = left_count;
          best_sum_left_gradient = sum_left_gradient;
          best_sum_left_hessian = sum_left_hessian;
          best_threshold = static_cast<uint32_t>(t + bias);
          best_gain = current_gain;
        }
      }
    }

    if (is_splittable_ && best_gain > output->gain) {
      // update split output information
      .....
    }
  }

而这个关键的GetSplitGains是什么呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
static double GetSplitGains(double sum_left_gradients, double sum_left_hessians,
                              double sum_right_gradients, double sum_right_hessians,
                              double l1, double l2, double max_delta_step,
                              double min_constraint, double max_constraint, int8_t monotone_constraint) {
    double left_output = CalculateSplittedLeafOutput(sum_left_gradients, sum_left_hessians, l1, l2, max_delta_step, min_constraint, max_constraint);
    double right_output = CalculateSplittedLeafOutput(sum_right_gradients, sum_right_hessians, l1, l2, max_delta_step, min_constraint, max_constraint);
    if (((monotone_constraint > 0) && (left_output > right_output)) ||
      ((monotone_constraint < 0) && (left_output < right_output))) {
      return 0;
    }
    return GetLeafSplitGainGivenOutput(sum_left_gradients, sum_left_hessians, l1, l2, left_output)
      + GetLeafSplitGainGivenOutput(sum_right_gradients, sum_right_hessians, l1, l2, right_output);
  }

而第一个调用的函数如下（其实就是类似XGBoost的最优叶子节点输出：\(w_j = – \frac{G_j}{H_j+\lambda}\)）：

1
2
3
4
5
6
7
8
9
10
static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step,
                                            double min_constraint, double max_constraint)  => 调用：
static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step) {
    double ret = -ThresholdL1(sum_gradients -  l1) / (sum_hessians + l2);
    if (max_delta_step <= 0.0f || std::fabs(ret) <= max_delta_step) {
      return ret;
    } else {
      return Common::Sign(ret) * max_delta_step;
    }
}

得到了叶子结点输出后，GetLeafSplitGainGivenOutput其实就是左右子树累加起来，\(G_jw_j + \frac{1}{2} (H_j + \lambda) w_j^2\)：和XGBoost一样。

1
2
3
4
static double GetLeafSplitGainGivenOutput(double sum_gradients, double sum_hessians, double l1, double l2, double output) {
    const double sg_l1 = ThresholdL1(sum_gradients, l1);
    return -(2.0 * sg_l1 * output + (sum_hessians + l2) * output * output);
  }

注意到上面的增益计算出来是左子树+右子树，然后和min_gain_shift比较，而XGBoost是如下形式: \[ Gain = \frac{1}{2}[\underbrace{\frac{G_L^2}{H_L+\lambda}}_{左子树分数} + \underbrace{\frac{G_R^2}{H_R+\lambda}}_{右子树分数} – \underbrace{\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}}_{分裂前分数}] – \underbrace{\gamma}_{新叶节点复杂度} \] 难道不一样？其实是一样的，min_gain_shift计算方式一开始的代码就给出了，即：

1
2
3
double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
                                         meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;

就是分裂前的分数！

因此，是和XGBoost一样的。

直方图算法小结

可以看出，直方图算法的有点有：

  • 可以减少内存占用，比如离散为256个Bin时，只需要用8位整形就可以保存一个样本被映射为哪个Bin(这个bin可以说就是转换后的特征)，对比预排序的Exact greedy算法来说（用int_32来存储索引+ 用float_32保存特征值），可以节省7/8的空间。
  • 计算效率也得到提高，预排序的Exact greedy对每个特征都需要遍历一遍数据，并计算增益，复杂度为\(O(\#feature \times \#data)\)。而直方图算法在建立完直方图后，只需要对每个特征遍历直方图即可，复杂度为\(O(\#feature \times \#bins)\)。
  • 提高缓存命中率，因为它访问梯度是连续的（直方图）。
  • 此外，在数据并行的时候，直方图算法可以大幅降低通信代价。（数据并行、特征并行在本文后面讲解）

当然也有不够精确的缺点：

当然，Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。

直方图算法改进

直方图算法仍有优化的空间，建立直方图的复杂度为\(O(\#feature \times \#data)\)，如果能降低特征数或者降低样本数，训练的时间会大大减少。以往的降低样本数的方法中，要么不能直接用在GBDT上，要么会损失精度。而降低特征数的直接想法是去除弱的特征（通常用PCA完成），然而，这些方法往往都假设特征是有冗余的，然而通常特征是精心设计的，去除它们中的任何一个可能会影响训练精度。因此LightGBM提出了GOSS算法和EFB算法。

Gradient-based One-Side Sampling（GOSS）

在AdaBoost中，权重向量w很好的反应了样本的重要性。而在GBDT中，则没有这样的直接权重来反应样本的重要程度。但是梯度是一个很好的指标，如果一个样本的梯度很小，说明该样本的训练误差很小，或者说该样本已经得到了很好的训练(well-trained)。

要减少样本数，一个直接的想法是抛弃那些梯度很小的样本，但是这样训练集的分布会被改变，可能会使得模型准确率下降。LightGBM提出 Gradient-based One-Side Sampling (GOSS)来解决这个问题。

GOSS的做法伪代码描述如下：

LightGBM-Gradient-based-One-Side-Sampling

即：

  1. 根据梯度的绝对值将样本进行降序排序
  2. 选择前\(a \times100\%\)的样本，这些样本称为A
  3. 剩下的数据\((1-a) \times100\%\) 的数据中，随机抽取\(b \times100\%\)的数据，这些样本称为B
  4. 在计算增益的时候，放大样本B中的梯度\((1-a) / b\) 倍
  5. 关于g，在具体的实现中是一阶梯度和二阶梯度的乘积，见Github的实现（ LightGBM/src/boosting/goss.hpp）

使用GOSS进行采样，使得训练算法更加的关注没有充分训练(under-trained)的样本，并且只会稍微的改变原有的数据分布。

原有的在特征j值为d处分数据带来的增益可以定义为： \[ V_{j|O}(d) = \frac{1}{n_O}\left(\frac{(\sum_{x_i\in O:x_{ij} \le d}g_i)^2}{n_{l|O}^j(d)} + \frac{(\sum_{x_i\in O:x_{ij} \gt d}g_i)^2}{n_{r|O}^j(d)} \right) \] 其中：

  • O为在决策树待分裂节点的训练集
  • \(n_o = \sum I(x_i \in O)\)
  • \(n_{l|O}^j(d) = \sum I[x_i \in O: x_{ij} \le d]\ and\ n_{r|O}^j(d) = \sum I[x_i \in O: x_{ij} \gt d]\)

而使用GOSS后，增益定义为： \[ V_{j|O}(d) = \frac{1}{n_O}\left(\frac{(\sum_{x_i\in A_l} g_i + \frac{1-a}{b} \sum_{x_i\in B_l} g_i)^2 }{n_{l}^j(d)} + \frac{(\sum_{x_i\in A_r} g_i + \frac{1-a}{b} \sum_{x_i\in B_l} g_r)^2 }{n_{r}^j(d)} \right) \] 其中:

  • \(A_l = \{x_i \in A: x_{ij} \le d\}, A_r = \{x_i \in A: x_{ij} \gt d\}\)
  • \(B_l = \{x_i \in B: x_{ij} \le d\}, B_r = \{x_i \in B: x_{ij} \gt d\}\)

Exclusive Feature Bundling（EFB）

一个有高维特征空间的数据往往是稀疏的，而稀疏的特征空间中，许多特征是互斥的。所谓互斥就是他们从来不会同时具有非0值（一个典型的例子是进行One-hot编码后的类别特征）。

LightGBM利用这一点提出Exclusive Feature Bundling（EFB）算法来进行互斥特征的合并，从而减少特征的数目。做法是先确定哪些互斥的特征可以合并（可以合并的特征放在一起，称为bundle），然后将各个bundle合并为一个特征。

这样建立直方图的时间将从\(O(\#feature \times \#data)\)变为\(O(\#bundle \times \#data)\)，而\(\#bundle << \#feature\)，这样GBDT能在精度不损失的情况下进一步提高训练速度。

那么，问题来了：

  1. 如何判断哪里特征应该放在一个Bundle中？
  2. 如何将bundle中的特征合并为一个新的特征？

Greedy bundle

对于第1个问题，将特征划分为最少数量的互斥的bundle是NP问题（可以根据图着色问题来证明）。

因此，同样采用近似算法。我们可以构建一张图，图上的顶点代表特征，若两个特征不互斥，则在他们之间连一条边。

更进一步的，通常有少量的特征，它们之间并非完全的独立，但是绝大多数情况下，并不会同时取非0值。若构建Bundle的算法允许小的冲突，就能得到更少数的bundle，进一步提高效率。可以证明，随机的污染一部分特征则最多影响精度\(O([1-\gamma]n)^{-2/3}\), \(\gamma\)为最大的特征冲突率，也是在速度和精度之间达到平衡的有效手段。

因此，LightGBM的构建bundle算法描述如下（算法3）：

LightGBM-greedy-bundling

即：

  1. 构造带权图G，边的权重代表两个feature之间冲突的数量
  2. 对特征按度降序排序
  3. 按顺序对排好序的特征进行遍历，对于当前特征i，查看是否能加入已有的bundle（冲突要小），若不行，则新建一个bundle

上述的算法复杂度为\(O(\#feature^2)\)，当特征数很大的时候，仍然效率不高。

算法3可以进一步优化：不建立图，直接按特征的非0值的个数进行排序。（这也是一种贪心，非0值越多，越可能冲突）。

Merge Exclusive Features

现在来回答第2个问题，我们已经有了一个个的bundle，如何将bundle中的特征合并为一个新的特征呢？

回想起在直方图算法中，我们将连续的特征变为一个个离散的bins值，这是以特征为粒度的，即一个特征一张直方图。而合并后，一个很关键的点是合并后原本不同特征的值要有所体现，这样在新的特征中遍历直方图才能相当于遍历原来好几个直方图，从而找到切分点。

这可以通过对原始特征的值添加偏移来实现，从而将互斥的特征放在不同的bins中。例如，一个Bundle中有两个特征A和B，\(A \in [0,10),\ B \in [0,20)\)，可以给特征B添加偏移量10，使得B的值域范围变为\(B \in [10,30)\)，然后，A和B就可以合并成值域为\([0,30]\)新特征。这就是Merge Exclusive Features（MEF）算法。

伪代码描述如下：

LightGBM-merge-exclusive-features

通过MEF算法，将许多互斥的稀疏特征转化为稠密的特征，降低了特征的数量，提高了建直方图的效率。

树的生长策略

在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝，如下图所示：

LightGBM-level-wise-tree-growth

Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

而LightGBM采用的是Leaf-wise tree growth：

Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

LightGBM-leaf-wise-tree-growth

并行计算

本小节主要根据LightGBM的官方文档中提到的并行计算优化进行讲解。

在本小节中，工作的节点称为worker

特征并行

特征并行主要是并行化决策树中寻找最优划分点(“Find Best Split”)的过程，因为这部分最为耗时。

传统算法

传统算法的做法如下：

  1. 垂直划分数据（对特征划分），不同的worker有不同的特征集
  2. 每个workers找到局部最佳的切分点{feature, threshold}
  3. workers使用点对点通信，找到全局最佳切分点
  4. 具有全局最佳切分点的worker进行节点分裂，然后广播切分后的结果（左右子树的instance indices）
  5. 其它worker根据收到的instance indices也进行划分
LightGBM-feature-parallelization

传统算法的缺点是：

  1. 无法加速split的过程，该过程复杂度为\(O(\#data)\)，当数据量大的时候效率不高
  2. 需要广播划分的结果（左右子树的instance indices），1条数据1bit的话，大约需要花费\(O(\#data / 8)\)

LightGBM中的特征并行

每个worker保存所有的数据集，这样找到全局最佳切分点后各个worker都可以自行划分，就不用进行广播划分结果，减小了网络通信量。过程如下：

  1. 每个workers找到局部最佳的切分点{feature, threshold}
  2. workers使用点对点通信，找到全局最佳切分点
  3. 每个worker根据全局全局最佳切分点进行节点分裂

但是这样仍然有缺点：

  1. split过程的复杂度仍是\(O(\#data)\)，当数据量大的时候效率不高
  2. 每个worker保存所有数据，存储代价高

数据并行

传统算法

数据并行目标是并行化整个决策学习的过程：

  1. 水平切分数据，不同的worker拥有部分数据
  2. 每个worker根据本地数据构建局部直方图
  3. 合并所有的局部直方图得到全部直方图
  4. 根据全局直方图找到最优切分点并进行分裂
LightGBM-data-parallelization

在第3步中，有两种合并的方式：

  • 采用点对点方式(point-to-point communication algorithm)进行通讯，每个worker通讯量为\(O(\#machine * \#feature * \#bin)\)
  • 采用collective communication algorithm(如“All Reduce”)进行通讯（相当于有一个中心节点，通讯后在返回结果），每个worker的通讯量为\(O(2 * \#feature * \#bin)\)

可以看出通信的代价是很高的，这也是数据并行的缺点。

LightGBM中的数据并行

  1. 使用“Reduce Scatter”将不同worker的不同特征的直方图合并，然后workers在局部合并的直方图中找到局部最优划分，最后同步全局最优划分。
  2. 前面提到过，可以通过直方图作差法得到兄弟节点的直方图，因此只需要通信一个节点的直方图。

通过上述两点做法，通信开销降为\(O(0.5 * \#feature * \#bin)\)

Voting Parallel

LightGBM采用一种称为PV-Tree的算法进行投票并行(Voting Parallel)，其实这本质上也是一种数据并行。

PV-Tree和普通的决策树差不多，只是在寻找最优切分点上有所不同。

其算法伪代码描述如下：

LightGBM-pv-tree
  1. 水平切分数据，不同的worker拥有部分数据。
  2. Local voting: 每个worker构建直方图，找到top-k个最优的本地划分特征
  3. Global voting: 中心节点聚合得到最优的top-2k个全局划分特征（top-2k是看对各个worker选择特征的个数进行计数，取最多的2k个）
  4. Best Attribute Identification： 中心节点向worker收集这top-2k个特征的直方图，并进行合并，然后计算得到全局的最优划分
  5. 中心节点将全局最优划分广播给所有的worker，worker进行本地划分。
LightGBM-voting-parallelization

可以看出，PV-tree将原本需要\(\#feature \times \#bin\) 变为了\(2k \times \#bin\)，通信开销得到降低。此外，可以证明，当每个worker的数据足够多的时候，top-2k个中包含全局最佳切分点的概率非常高。

小结

LightGBM 和 XGBoost对比如下：

LightGBM-VS-XGBoost

参考资料

请我喝杯咖啡吧~