盆暗の学習記録

データサイエンス ,エンジニアリング,ビジネスについて日々学んだことの備忘録としていく予定です。初心者であり独学なので内容には誤りが含まれる可能性が大いにあります。

LightGBMの「No further splits with positive gain」というwarningの意味

LightGBM関連の論文やソースコードを読んでいてわかったことをメモ

概要

LightGBMを使っているとたまに

No further splits with positive gain, best gain: -inf

のようなwarningが表示されることがある。

これはLightGBMが内部で決定木を成長させている際にpre-pruning(特徴空間をそれ以上分割しても情報利得が得られないので分割を停止する仕組み)が働いたことを示している1

ソースコード的には https://github.com/microsoft/LightGBM/blob/master/src/treelearner/serial_tree_learner.cpp#L197-L201 などにある。

// cannot split, quit
if (best_leaf_SplitInfo.gain <= 0.0) {
  Log::Warning("No further splits with positive gain, best gain: %f", best_leaf_SplitInfo.gain);
  break;
}

もう少し詳しく

決定木の成長アルゴリズム

決定木を学習させる際に「どの枝から伸ばすか」についてのアルゴリズムは主に2種類ある(Shi, 2007)。

  1. depth-first (level-wise) :順番は固定で、通常左から右の順で伸ばす。
  2. best-first (leaf-wise) :もっとも利得がある(分岐することで不純度・予測誤差を下げる)枝から伸ばす

一般的に使われるものはdepth-firstだが、LightGBMはbest-firstを使っている。

これらは枝を伸ばす順番が違うだけで、木を完全に成長させた場合(終端ノードの不純度がゼロになるまで分岐させた場合)は同じ木になる。

ただし、best-firstだと決定木の剪定(pruning)のアルゴリズムの選択肢がdepth-firstに比べて増える

決定木の剪定アルゴリズム

剪定アルゴリズムは2種類ある

  1. pre-pruning:さらなる分岐を行うことで予測誤差を下げるなら分岐し、下げないなら分岐しない
  2. post-pruning:まず決定木を完全に成長させ、次に最も予測誤差を下げる木のサイズを選択する

pre-pruningは本当に最適な木のサイズを発見できない可能性があるため精度が劣る可能性があるものの、計算がpost-pruningより少なくて済む。

LightGBMはpre-pruningを使っている。

本題

前述のソースコードは計算機と学習器に関するハイパーパラメータがデフォルト(device_type = cpu, tree_learner = serial, linear_learner = false)の場合に使われる決定木のコードで、コードとコメントから察するに最良の分岐を探索している箇所で、分岐による情報利得がゼロ以下なら打ち切るようになっている。

// Get a leaf with max split gain
int best_leaf = static_cast<int>(ArrayArgs<SplitInfo>::ArgMax(best_split_per_leaf_));
// Get split information for best leaf
const SplitInfo& best_leaf_SplitInfo = best_split_per_leaf_[best_leaf];
// cannot split, quit
if (best_leaf_SplitInfo.gain <= 0.0) {
  Log::Warning("No further splits with positive gain, best gain: %f", best_leaf_SplitInfo.gain);
  break;
}

今後は

No further splits with positive gain

のwarningが出たら「pre-pruningが行われたんだな」と考えて、min_samples_in_leaf などの別のハイパーパラメータを調整する手がかりにすればよいかもしれない(pruningさせるのとハイパーパラメータで分岐を止めるのとどちらが良いのかはわからないが)

参考文献

Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., ... & Liu, T. Y. (2017). Lightgbm: A highly efficient gradient boosting decision tree. In Advances in neural information processing systems (pp. 3146-3154).

Shi, H. (2007). Best-first decision tree learning (Doctoral dissertation, The University of Waikato).


  1. なぜ-infという極端な値になっているのかはわからなかった