Tree における単調性制約
XGBoost における単調性制約 - 2
はじめに
前回 XGBoost での単調性制約を与える方法について紹介しましたが、そのメカニズムについて調べました。
線形モデルはデータと目的変数間の単調性（増加・減少）を捉えるモデルです。 非線形モデルを使うのは、単調性にとどまらない表現力を利用したい場合があるからです。
実データを用いていると、特定の説明変数にはすでに単調性があることが分かっていたりします。そして非線形モデルを使う場合、特定の説明変数に単調増加の制約を与えるなど、局所的にコントロールしたいときがあります。
例えば、決定木・XGBoost などでモデリングをしていると、バイアスの低さにとても助けられますが、同時に強力すぎる分割の力をなんとか制御したいと思うこともあります。
そのような、モデルの複雑さをコントロールするためにも単調性制約は使えます。
また、決定木などツリー系はロジックそのものが木で表現できるので、複雑度をうまくコントロールすると説明性が上がります。
Tree における単調性制約の考え方と実装
単調性を持った問題への分類ツリーの活用については以下の論文が理論的にあります。
http://helios.mm.di.uoa.gr/~rouvas/ssi/sigkdd/sigkdd.vol4.1/potharst.pdf
実装の考え方については、次の記事に非常に分かりやすくかつ詳しく書いてあったので、ほぼそのまま引用させてもらいました。
towardsdatascience.com
以下は、上記の記事の意訳になります。
この記事では、単調性制約の与え方を 2 段階に分けて説明しています。
1. 左右子ノードの重みで分割の是非を判断する
Tree における単調性制約の基本的な考え方は、
枝を生やしていく過程で、分割した際に単調性ではない関係が作られた場合は、その分割を取りやめる。
ことです。
例えば、特徴量 f に単調増加制約を与えたいとして、あるノードの分割の際に f がピックアップされ分割される場合を考えてみます。
この時、制約が単調増加なので、右子ノードの重み w_R は左子ノードの重み w_L よりも大きいことが期待されます。
アルゴリズムでは
w_L <= w_R の場合のみ分割し、そうでなければ分割をしない
となります。
この処理は XGBoost の以下のコード L.441,442 に相当します*1。
この単調性制約の実装はとてもわかりやすい方法です。
しかしながら、単純にこの方法を実装しただけではうまく機能しないことにすぐ気づくと思います。
なぜならば、そのノード・その特徴量にのみ注目する限りに於いてはうまくいっていますが、木全体を見た場合単調性制約が守られない場合があるからです。(局所的には守られているが、大域的には破綻している）
もし、下流のノードで同じ特徴量が再度分割対象として取り上げられたらどうなるでしょう？
そのノードでも単調増加制約が守られ、左左子ノードと左右子ノードが単調増加性を持って重み w_LL <= w_LR となるように分割されたとしても、w_LR が右子ノードの重み w_R よりも高くなる場合がありえます。
このように、単調増加関係を木全体に渡って維持するためには、右子ノードの重み w_R は左子ノードの重み w_L よりも高いだけでなく、その子孫ノード { LL, LR, LLL, LLR, LRL LRR....} の重みよりも常に高くないとなりません。
それでは、どのようにして、この様なケースに対処するのでしょうか。
言い方を変えると、どのように制約を木の深さを超えて与えることができるのか、ということです。
2. 単調性制約を木全体に与える
XGBoost では次のように対処しています。
ノードを分割する時、子ノード(LL, LR)の重み(w_LL または w_LR)は親ノード(L)と親ノードの兄弟ノード(R)の重みの平均を境界とします*2。
この制約を与えると、特徴 f が木の分割の中で何度も分割されたとしても、重みが祖先ノードよりも高く（或いは低く）なり、木全体に渡って単調性制約に違反しないことが保証されます。
上記のこの書き方だと少し分かりづらいので、具体的な例で考えてみます。
あるノードを単調増加性をもって左子ノード(L)と右子ノード(R)に分割し、更に左子ノードを分割(LL, LR)する場合、 分割の際に w_LL <= w_LR の条件に加えて、w_LR <= mean(w_L, w_R) の条件を課します。*3
この２つの条件を課すことで、特徴 f の分割に関しての単調性制約は木全体でも保持されることとなります。
この条件の実装はXGBoost の以下のコード L.464-467 に相当します。
github.com
フロー
上記の２つの条件を、フローにしてみます。
特徴 x1 に単調増加制約を与えるとします。
ルートノードでは、w_0 のみが生成されます。
ルートノードの分割に於いて、特徴 x1 がピックアップされた場合、w_L <= w_R の条件に適合する分割のみ採用され、その中でゲインが最良の分割値で分割されます。*4
左子ノード(L)の分割をします。 特徴 x1 がピックアップされた際、w_LL < w_LR になる分割のみ採用されます。
ルートノード以降の分割では 3 に加えて次の条件を課します。 w_LL < mean(w_L, w_R), w_LR < mean(w_L, w_R)
同様に、右子ノード(R)を分割する際にも 3,4 の制約を与えます。
但し、4 に相当する条件は w_RL => mean(w_L, w_R), w_RR => mean(w_L, w_R) となります。木を生成する過程で 3,4,5 の手順が守られると、x1 に対して左の部分木の重みは右の部分木の重みよりも常に小さくなります。したがって、単調増加性制約は木の全体に対して課せられます。
このフローに従った分割は下図となります。
まとめ
この記事の内容紹介をしながら、XGBoost における単調性制約の考え方と実装を見てみました。
次回は、木の数がひとつで、XGBoost よりもシンプルな決定木アルゴリズムにこの条件を実装し、動きを見てみたいと思います。
