GBDT(勾配ブースティング)系モデルにNaNが入るのってナンでなん？

# GBDT(勾配ブースティング)系モデルにNaNが入るのってナンでなん？

## はじめに

この記事はNTTテクノクロス Advent Calendar 2022の2日目です。

こんにちは、NTTテクノクロスの広瀬です。  
三次元点群や画像などのメディア系研究開発から、XRシステムやクラウド分析基盤構築などの開発支援をしたり、データ分析の講師をしています。

さて、2022年はWhy do tree-based models still outperform deep learning on tabular data?[^1]というタイトルの論文が公開されて、Kaggle界隈を中心に激震が走りました。  
内容は、**初手LightGBM**という言葉があるように、感覚的に理解していたテーブルデータではNNよりもGBDTが強い事実を、実験により明確に示したものとなっています。

初手LightGBMのメリットは、特徴量スケーリングや欠損値をそのまま扱う事ができる点にあります。  
この**欠損値をそのまま扱える**というのはどういう事なのでしょうか。  

この記事では、LightGBMが欠損値をどの様に扱っているかを紹介していきます。

## 結論

早速ですが、結論としては下記のようになります。  

1. 数値とカテゴリで欠損の扱い方が変わる
2. 数値の場合は、学習(分岐の探索)時に分岐点の特徴量に欠損が入っているかを記録し、推論時に振り分けている

|特徴量種類|学習時|推論時(学習時欠損有り特徴)| 推論時(学習時非欠損特徴)|
|:--:|:--:|:--:|:--:|
|数値|情報利得を最大化する枝を割当|学習時に割り当てた枝を通す|欠損をゼロに置換|
|カテゴリ|右側の枝に割当|右側の枝を通す|右側の枝を通す|

:::note info
**Point!** NaNを埋める方法の採用ではなく、枝の探索時に欠損を考慮する工夫によって処理が可能になっている
:::

## 欠損値の扱い方を調べる

ここからは、LightGBMによる欠損値をどの様に扱っているか、コードを動かしながら確認していきます。

- 学習時に欠損を含む数値型
- 学習時に欠損を含まない数値型
- カテゴリ型

の3パターンについてそれぞれ見ていきましょう。

### 1. 学習時に欠損を含む数値型

学習時に欠損が登場する場合のアルゴリズムについては、GBDT系別のモデルであるXGBoostの原著[^2]に詳しく書かれています。  
以下は本文中3.4 Sparsity-aware Split Findingに掲載されている擬似コードと、欠損時における分岐についての図(Figure 4)です。

|擬似コード|Figure 4|
|:--:|:--:|
|![](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/350454/864cd5ef-2112-9be3-e57e-bef3d0e52eaa.png)|![](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/350454/c9501bc2-8b8c-7cef-f3f0-5dda1ad190c3.png)|

LightGBMでも基本的な処理は同一です。Sparsity-aware Split Findingアルゴリズムをざっくり追ってみると以下のとおりです。

1. 欠損していない値をソートして中点を得る(6と7の間は6.5)
2. 初期予測値と目的変数の残差をとる
   1. 予測値と目的変数の残差なので欠損していても問題ない
3. とある中点をしきい値に左右に分割する枝を考え、欠損の残差を左に与えて情報利得を計算する
4. 同様に、欠損の残差を右に与えて情報利得を計算する
5. すべての中点で計算した後、最も情報利得が大きくなる分割点と、左右のデフォルトを決定する

|Sparsity-aware Split Finding概要|
|:--:|
|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/350454/d9f9a103-eb2e-6f32-25cc-b42d0d418786.png" width=80%>|

#### コードで動作を確認する

アルゴリズムについては難しいので、やんわり理解した上でLightGBMは実際にどの様な出力をするのか確認しましょう。  
今回は、欠損値が含まれたデータを実際に学習させてみてノードがどの様な値を持つかを可視化してみます。

```python: 学習時に欠損を含む数値型
from sklearn.datasets import load_iris

iris = load_iris()
X, y = iris.data, iris.target
# Randomにnanを代入して、擬似的に欠損を作る
X[np.random.choice(list(range(X.shape[0])), 60), np.random.choice(list(range(X.shape[1])), 60) ] = np.nan
# ~~~ データセット作成 ~~~
model = lgb.train({"objective": "multiclass", "num_class":3}, lgb_train, valid_sets=lgb_eval)
# モデルの各ノードの情報をdataframeで出力する
model.trees_to_dataframe()
```

trees_to_dataframe()メソッドを呼び出し、学習結果のデータフレームを出力させています。  
学習結果のデータフレームは以下のようなものが得られます。

|モデルのノード情報のデータフレーム|
|:--:|
|![](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/350454/814b92fa-decb-39a6-4234-055bbc58831d.png)|

赤枠で囲っている部分が、学習された分岐点に欠損値が含まれていた場合の対応を記録したものです。  
GBDTは複数の決定木を組み合わせたアンサンブル手法であるので、tree_indexで何番目の木であるかを示し、node_indexでどの分岐であるかが示されます。  
今回得られた出力の、0個目の木の1層目の分岐では、**missing_typeがNaNのときmissing_directionをrightとする**様に学習されていることがわかるかと思います。  
決定時の情報利得の値であるsplit_gainも63.66320となっている事が確認できますね。

### 2. 学習時に欠損を含まない数値型
続いては欠損を含まない場合を見ていきます。
欠損のない数値型を学習した場合、推論時にはゼロで埋めて処理します。  

こちらはアルゴリズムと言うほどのものでもない為実装依存となり、あまりいい文献が見当たらなかったので[実装コード](https://github.com/microsoft/LightGBM/blob/a8c1e0a11a5cbfac62fb57d16901fea16de95412/include/LightGBM/tree.h#L259)と[欠損の定義コード](https://github.com/microsoft/LightGBM/blob/0a5c5838eb679a43fc45443f71adf31ec506de22/include/LightGBM/bin.h#L26)を覗きに行きました。[^3]

```c++: 学習時に欠損がない場合の処理
uint8_t missing_type = GetMissingType(decision_type_[node]);
if (std::isnan(fval)) {
  if (missing_type != 2) {
    fval = 0.0f;
  }
}
```

```c++: 欠損の定義
enum MissingType {
  None,
  Zero,
  NaN
};
```

推論時に入力された値がNaNであるにも関わらず、学習時に記録されたmissing_typeがNaNでない場合は0.0fが代入されるような実装となっていますね。  
この変数missing_typeは、先程確認したモデルのノード情報のmissing_typeを表しています。

#### コードで動作を確認する

数値の差が分かりやすいように、有名なFisher's Iris Dataset[^4]を使用して回帰分類として学習させています。  
推論時に与える変数に欠損を生じさせて、**0を入れたときとNaNを入れたときの出力が変わらないこと**を確認してみましょう。

```python: 学習時に欠損を含まない数値型
# 推論時のベースラインを作成
sample_df = pd.DataFrame()
sample_df["オリジナル"] = model.predict(X_test)

# すべてゼロにしてみる
iris_delete = X_test.copy()
iris_delete[:, 1] = 0
sample_df["一つのカラムを全てゼロ"] = model.predict(iris_delete)

# すべてNaNにしてみる
iris_delete[:, 1] = np.nan
sample_df["一つのカラムを全てNaN"] = model.predict(iris_delete)
```

出力は下記の通りで、0を入れたときとNaNを入れたときでほぼ同じ出力が得られていますね。  
実装を見ているので当たり前なのですが、狙い通りの結果を再現することが出来ました。

|欠損値を推論時に入れてみたときの出力|
|:--:|
|<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/350454/19874668-8701-897a-b7fd-364f0310be61.png", width=80%>|


### 3. カテゴリ型
最後はカテゴリ型です。  
カテゴリ型はいわゆる質的変数ではなく、**categorical_featureオプションによって指定された特徴量**を指します。  
こちらもあまりいい文献が見当たらなかったので、実装コードを覗きに行ったところ[// NaN is always in the right](https://github.com/microsoft/LightGBM/blob/a8c1e0a11a5cbfac62fb57d16901fea16de95412/include/LightGBM/tree.h#L303)と書かれているので、**常に右**で良いのでしょう。

常に右とはどういう状態でしょうか。

早速コードで確認しましょう。

#### コードで動作を確認する

Fisher's Iris Datasetには特徴量にカテゴリ値がありませんので、ダミーデータを用意します。  

- データ数100、0,1,2の3種類の特徴量
  - 25％をNaNに設定して欠損させる
- 目的変数は0 or 1の二値分類とする

この様な欠損を含むカテゴリ型のみが含まれたデータを学習させ、分岐がどの様に作成されるかを可視化してみます。

```python: カテゴリ型
# 欠損付きの学習データを作る。
X = np.random.randint(3, size=(100,1)).astype("float")
X[np.random.choice(list(range(X.shape[0])), 25)] = np.nan
# 特徴catをカテゴリ型として指定しています。
lgb_train = lgb.Dataset(pd.DataFrame(X, columns=["cat"]), np.random.randint(2, size=(100,1)))
model = lgb.train({"objective":"binary"}, lgb_train, categorical_feature=["cat"])
lgb.plot_tree(model)
```

学習結果として得られた一つの木構造を、graphvizで可視化します。  

|カテゴリ型を学習した木構造(欠損なし)|カテゴリ型を学習した木構造(欠損あり)|
|:--:|:--:|
|![](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/350454/89eaf1b6-052d-dd79-c513-bd5ab0739e8e.png)|![](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/350454/26608b29-1f1e-551e-9e5c-cb1772414677.png)|

カテゴリ型なので、**閾値(<=)による分岐ではなく、is or is not(=)の分岐**が出来上がっているのが分かるかと思います。  

そして、欠損なしの構造ではcat=2でもなくcat=1でもなければcat=0と判断できそうです。これはOne-Hot Encodingによる多重共線性回避のときと同じ考え方ですね。  
一方で、欠損がある場合はすべてのcatに対してis notを進んだ分岐が新たに登場しています。いかなるcatにも属さない新たな値としてNaNを扱っている事がわかります。

すべてのカテゴリをis notする分岐に進む事が、常に右側の分岐を通るということのようですね。

## おわりに
テーブルデータに対して強力な性能を発揮するLightGBMが欠損値をどの様に扱っているかを見てきました。
同じGBDT系のモデルでも、CatBoostではデフォルトは欠損を扱わず、オプションによってMin/Maxで埋めるようになっています。[^5]

最近話題のStable Diffusionなどデータサイエンス分野は、何も考えずにモデルを生み出しアウトプットが出せる様な環境となっていますが、データを生み出した過程や得られた結果の読み解き方を正しく理解して扱う事が出来るのがデータサイエンティストであると考えています。
素晴らしいモデルも十分に理解して扱うことで更に性能が発揮できるはずなので、この情報がなにかの役に立つことがあれば嬉しく思います。

明日は、@hara-stによるDevSevOps関連の記事となります。
引き続きNTTテクノクロスアドベントカレンダーをお楽しみください。


[^1]: [Grinsztajn, Léo, Edouard Oyallon, and Gaël Varoquaux. "Why do tree-based models still outperform deep learning on tabular data?." arXiv preprint arXiv:2207.08815 (2022).](https://arxiv.org/abs/2207.08815)
[^2]: [Chen, Tianqi, and Carlos Guestrin. "Xgboost: A scalable tree boosting system." Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. 2016.](https://arxiv.org/abs/1603.02754)
[^3]: [Microsoft. "Light Gradient Boosting Machine". GitHub. 2022. https://github.com/microsoft/LightGBM, (参照 2022/11/20)](https://github.com/microsoft/LightGBM)
[^4]: [R.A. Fisher. "The use of multiple measurements in taxonomic problems" Annual Eugenics, 7, Part II, 179-188. 1936. ](https://archive-beta.ics.uci.edu/dataset/53/iris)
[^5]: [YANDEX LLC. "Missing values processing". CatBoost. 2022. https://catboost.ai/en/docs/concepts/algorithm-missing-values-processing, (参照 2022/11/20)](https://catboost.ai/en/docs/concepts/algorithm-missing-values-processing)