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)。
- depth-first (level-wise) :順番は固定で、通常左から右の順で伸ばす。
- best-first (leaf-wise) :もっとも利得がある(分岐することで不純度・予測誤差を下げる)枝から伸ばす
一般的に使われるものはdepth-firstだが、LightGBMはbest-firstを使っている。
これらは枝を伸ばす順番が違うだけで、木を完全に成長させた場合(終端ノードの不純度がゼロになるまで分岐させた場合)は同じ木になる。
ただし、best-firstだと決定木の剪定(pruning)のアルゴリズムの選択肢がdepth-firstに比べて増える
決定木の剪定アルゴリズム
剪定アルゴリズムは2種類ある
- pre-pruning:さらなる分岐を行うことで予測誤差を下げるなら分岐し、下げないなら分岐しない
- 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させるのとハイパーパラメータで分岐を止めるのとどちらが良いのかはわからないが)
参考文献
-
なぜ-infという極端な値になっているのかはわからなかった↩