決定木と勾配ブースティング

レッスン03の線形モデルは、データに1本の直線の境界を引きます。決定木は代わりに階段を描きます。軸に平行な切断を1回ずつ重ねていき、教えられなくても特徴量間の相互作用を見つけます。単体ではひどく過学習します。勾配ブースティングで組み合わせると、表形式データのコンペティションの大半を制し、構造化データ向けの本番スコアリングシステムの大半を支えるモデルになります。本レッスンでは、scikit-learnに同梱の乳がんデータセットに両方を当てはめ、深さが何をするかを示し、すべての特徴量重要度のプロットに添えるべき注意点で締めくくります。

木とは何か

決定木は、単一の特徴量についての「はい・いいえ」の質問の列です。根（ルート）ですべての学習行から始めます。「worst perimeterは106.1以下か」と問います。はいと答えた行は左へ、残りは右へ行きます。各子ノードでまた別の質問をし、ノードが純粋になる（すべて同じクラス）か停止規則に達するまで続けます。葉は、そこに到達した学習行の多数派クラスを予測します。確率が欲しければ各クラスの割合を返します。

重みも勾配も学習率もありません。学習は貪欲探索です。各ノードで、すべての特徴量と、ソート後の隣り合う値の間のすべてのしきい値を試し、候補となる分岐をそれぞれ採点し、最良のものを残します。スコアは、その分岐が不純度をどれだけ減らすかです。

分岐を1つ手計算する

ノードのGini不純度は、1からクラスごとの割合の2乗の和を引いたものです。各クラス50%のノードは0.5で、2クラスでは最悪の値です。純粋なノードは0です。

このデータセットには30個の測定値で記述された569個の腫瘍があり、悪性か良性かのラベルが付いています。75%を学習用に分割すると学習行は426行で、悪性159、良性267です。根のクラス割合は0.373と0.627なので、Gini不純度は1−0.139−0.393で0.468です。探索が見つける最良の分岐は、worst perimeterが106.1以下かどうかです。左に259行を送り、うち11が悪性（不純度0.081）、右に167行を送り、うち148が悪性（不純度0.202）です。子ノードの重み付き不純度は、259×0.081＋167×0.202を426で割って約0.128です。この分岐は不純度を0.468から0.128に減らし、他のどの特徴量としきい値もこれを上回りません。この1つの質問、すなわちスタンプ（切り株）と呼ばれる深さ1の木は、すでに使い物になる分類器です。

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

data = load_breast_cancer()
X, y = data.data, data.target
print("samples:", X.shape[0], " features:", X.shape[1],
      " classes:", data.target_names.tolist())

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=0, stratify=y)

stump = DecisionTreeClassifier(max_depth=1, random_state=0).fit(X_train, y_train)
print(export_text(stump, feature_names=list(data.feature_names)))
print("depth-1 test accuracy:", round(stump.score(X_test, y_test), 3))

samples: 569  features: 30  classes: ['malignant', 'benign']
|--- worst perimeter <= 106.10
|   |--- class: 1
|--- worst perimeter >  106.10
|   |--- class: 0

depth-1 test accuracy: 0.888

このデータセットの符号化では、クラス1が良性です。1つの測定値に対する1つのしきい値が、未知の腫瘍の88.8%を正しく分類します。図は木を1段深くしたもので、各ノードの行数を示しています。

葉を読んでください。左端、周長が小さく凹点が少ない葉は、良性239に対して悪性1で、右端は悪性128に対して良性2です。真ん中の2つの葉はほぼ互角で、さらに質問が必要でしょう。2段目が両側で同じ特徴量を問いながら、しきい値が異なる点に注目してください。これは木が自力で見つけた相互作用です。意味のあるconcave pointsの切り方は、perimeterに依存するのです。線形モデルは、手作りの特徴量なしにこれを表現できません。

深さ、過学習、そして差

すべての葉が純粋になるまで木を育てると、学習精度は100%になります。すべての学習行が自分のクラスの葉に振り分けられるからです。それは暗記であって学習ではありません。下のブロックは深さを増やしながら木を当てはめ、学習精度の隣に、学習行での5分割交差検証精度を報告します。後者はレッスン06が詳しく説明する正直な推定値です。

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.tree import DecisionTreeClassifier

data = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.25, random_state=0, stratify=data.target)

print("depth  train   cv(5)   leaves")
for depth in (1, 2, 3, 4, 6, 8, None):
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
    cv = cross_val_score(tree, X_train, y_train, cv=5).mean()
    tree.fit(X_train, y_train)
    label = "full" if depth is None else str(depth)
    print(f"{label:>5}  {tree.score(X_train, y_train):.3f}   {cv:.3f}   {tree.get_n_leaves()}")

depth  train   cv(5)   leaves
    1  0.930   0.897   2
    2  0.932   0.927   4
    3  0.977   0.925   8
    4  0.986   0.923   13
    6  1.000   0.925   18
    8  1.000   0.925   18
 full  1.000   0.925   18

学習精度は深さとともに上がり、深さ6で100%に達します。そこで木は18枚の葉を持ち、もう分けるものがありません（より深い設定でも同じ木になります）。交差検証精度は0.897から深さ2で0.927に上がり、その後は約0.925で横ばいになる一方、2つの列の差は0.005から0.075へと開いていきます。深さ2より先に木が学んだことはすべて、学習行に固有のものでした。この差が過学習の尺度であり、max_depth（または、子ノードが小さくなりすぎる分岐を止めるmin_samples_leaf）がその制御です。正しい深さは、保留スコアの改善が止まるところであって、学習スコアが最も高いところではありません。

木はまた不安定です。学習行を数行変えるだけで根の分岐の特徴量が変わり、その下の木全体が組み替わることがあります。過学習と不安定さ、この2つの問題こそ、アンサンブルが直すものです。

勾配ブースティング

考え方は、多数の小さな木の和としてモデルを作り、それぞれがそれまでの和の誤差を修正するというものです。回帰の損失ではこう進みます。定数の予測、つまりラベルの平均から始めます。各事例の残差、ラベル−現在の予測を計算します。浅い木を残差に当てはめます。その木の予測を、0.1などの学習率でスケールしてモデルに加えます。残差を再計算すると、今度は小さくなっているので、数百ラウンド繰り返します。

ラベルが10、20、30の3つで最初のラウンドを追ってみます。定数の出発点は20なので、残差は−10、0、10です。1つ目の事例を他の2つから分けるスタンプは、左に−10、右に5（0と10の平均）を予測します。学習率0.1で、モデルは1つ目の事例に19、他には20.5となります。新しい残差は−9、−0.5、9.5です。各ラウンドは、木が表現できる方向に残りの誤差の10分の1を取り除き、十分なラウンドの後、スタンプの和はラベルを削り出しています。

「勾配」という言葉があるのは、残差が予測に関する二乗誤差損失の負の勾配だからです。分類器の対数損失などの他の損失では、同じ手順で各木を代わりにその損失の負の勾配に当てはめます。これはレッスン04の学習ループで、一歩が木になったものです。学習率が同じ役割を果たし、ラウンド数も同様です。高すぎる学習率でラウンドが多すぎると、アンサンブルはノイズに当てはまり始めます。

HistGradientBoostingClassifierはscikit-learnの高速な実装です。学習前に各特徴量を最大255個のヒストグラムのビンに分けるので分岐の探索が安価になり、欠損値も扱え、数万行をノートPCで無理なく処理できます。

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import HistGradientBoostingClassifier

data = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.25, random_state=0, stratify=data.target)

tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X_train, y_train)
print("depth-3 tree test accuracy:", round(tree.score(X_test, y_test), 3))

for n_trees in (10, 50, 200):
    gb = HistGradientBoostingClassifier(
        max_iter=n_trees, learning_rate=0.1, max_depth=3, random_state=0)
    gb.fit(X_train, y_train)
    print(f"boosting, {n_trees:3d} trees, test accuracy: {gb.score(X_test, y_test):.3f}")

depth-3 tree test accuracy: 0.916
boosting,  10 trees, test accuracy: 0.937
boosting,  50 trees, test accuracy: 0.944
boosting, 200 trees, test accuracy: 0.958

1本1本は弱い深さ3の木200本が、テストセットで0.958を取り、深さ3の単一の木は0.916です。テストセットは143行なので、1パーセントポイントは約1.4個の腫瘍にあたり、50本と200本の差はそのうちの2個分です。交差検証で裏付けが取れない限り、小さな差はノイズとして扱ってください。重要なパラメータはmax_iter（ラウンド数）、learning_rate、各木の大きさで、これらはトレードオフの関係にあります。学習率を小さくするとラウンド数が多く必要になり、たいてい汎化は少し良くなります。早期終了（HistGradientBoostingClassifierが大きめのデータセットでは自動的に有効にします）は、検証スコアを監視し、改善が止まったら木の追加をやめます。

ランダムフォレストは、もう1つ出会うことになる木のアンサンブルです。行と特徴量の無作為な部分集合で多数の深い木を独立に学習し、平均します。ブースティングは浅い木を順に学習し、それぞれが前の木を直します。表形式データでは精度はたいていブースティングが勝ち、フォレストはうっかり過学習させにくいという利点があります。古典的機械学習のハブで両者を比較しています。

特徴量重要度と、その注意点

木モデルには、特徴量ごとに魅力的な数値が付いてきます。その特徴量がどれだけ寄与したか、です。デフォルトの不純度ベースの重要度は、各特徴量での分岐すべてによる不純度の減少を、その分岐が触れた行数で重み付けして足し合わせたものです。安価であり、学習行で計算されます。それが第1の問題です。モデルがノイズを暗記するために使った特徴量も高いスコアを取ります。

第2の問題はバイアスです。異なる値を多く持つ特徴量は探索に多くの候補しきい値を提供するので偶然に分岐を勝ち取りやすく、連続値の特徴量は、情報を持つ二値特徴量より、それだけの理由で上位に来ます。

第3の問題は相関です。2つの特徴量が同じ情報を運んでいるとき、木は各分岐でどちらか一方を、しばしば恣意的に選び、重要度は有用性ではなくタイブレークを反映する形で両者に分配されます。片方を落とせば、もう片方のスコアはほぼ倍になります。

順列重要度（permutation importance）は第1の問題に対処します。当てはめたモデルと保留セットを取り、1列をシャッフルして情報を持たないようにし、スコアがどれだけ下がるかを測ります。新しいシャッフルで繰り返せばノイズが見えます。相関には対処しません。相関する2列の一方をシャッフルしても、その双子は無傷なので、モデルはほとんど困らず、両方とも重要でないように見えます。

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.ensemble import HistGradientBoostingClassifier
from sklearn.inspection import permutation_importance

data = load_breast_cancer()
names = np.array(data.feature_names)
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.25, random_state=0, stratify=data.target)

gb = HistGradientBoostingClassifier(max_iter=200, learning_rate=0.1,
                                    max_depth=3, random_state=0)
gb.fit(X_train, y_train)

# Permutation importance: shuffle one column of the test set and see how
# much accuracy falls. Repeated 10 times so the noise is visible.
result = permutation_importance(gb, X_test, y_test, n_repeats=10, random_state=0)
order = np.argsort(result.importances_mean)[::-1]
print("feature                   drop in accuracy (mean +/- std)")
for i in order[:6]:
    print(f"{names[i]:<24}  {result.importances_mean[i]:.3f} +/- {result.importances_std[i]:.3f}")

# How correlated is the top feature with its siblings?
corr = np.corrcoef(data.data.T)
top = order[0]
partners = np.argsort(np.abs(corr[top]))[::-1][1:4]
print(f"\nfeatures most correlated with '{names[top]}':")
for j in partners:
    print(f"  {names[j]:<24} r = {corr[top, j]:.3f}")

feature                   drop in accuracy (mean +/- std)
mean concave points       0.024 +/- 0.009
worst concave points      0.023 +/- 0.008
worst smoothness          0.021 +/- 0.004
worst texture             0.017 +/- 0.008
mean texture              0.014 +/- 0.005
worst area                0.013 +/- 0.012

features most correlated with 'mean concave points':
  mean concavity           r = 0.921
  worst concave points     r = 0.910
  worst perimeter          r = 0.856

最上位の特徴量をシャッフルすると、モデルは精度を2.4ポイント、プラスマイナス0.9失います。続く3つはその1標準偏差以内にあるので、それらの間の順位に意味はありません。そして最上位の特徴量はmean concavityと0.92、worst concave pointsと0.91の相関があるので、1つをシャッフルするとモデルは他を読み、3つとも過小評価されます。最初の節ですべての木の根の分岐だったworst perimeterが上位6つにまったく現れないのも同じ理由です。モデルはそれを、ほぼ複製であるworst areaやworst radiusで置き換えられるのです。

演習

1. 深さの掃引でmax_depthをmin_samples_leafに置き換え、1、5、10、20、50を試して、学習精度と交差検証精度を報告してください。このデータでより良い保留スコアを与える制御はどちらですか。
2. ブースティングのブロックをlearning_rate=0.02とmax_iter=1000で、次にlearning_rate=0.5とmax_iter=40で走らせてください。テスト精度と学習時間を比べ、どちらを出荷するかを述べてください。
3. HistGradientBoostingClassifierにはfeature_importances_属性がないので、同じ設定でGradientBoostingClassifierを当てはめ、同じ6つの特徴量について不純度ベースの重要度を出力し、2つの順位を比べてください。それからmean concave pointsを落として再学習し、mean concavityに何が起こるかを観察してください。

まとめ

• 決定木は、単一の特徴量に対するしきい値を、不純度を最も減らすように貪欲に選んだ列です。worst perimeterでの1回の分岐が未知の腫瘍の89%を分類します。
• 学習精度は深さとともに100%まで上がります。保留精度は早い段階で改善が止まり、両者の差が、max_depthまたはmin_samples_leafで制御すべき過学習です。
• 勾配ブースティングは、新しい浅い木をそれぞれ損失の負の勾配（二乗誤差なら残差）に当てはめ、学習率でスケールして加えます。弱い木200本が強い木1本に勝ちます。
• 不純度重要度は学習行で計算され、カーディナリティの高い特徴量を優遇します。保留行での順列重要度のほうが良いものの、相関する特徴量は依然として手柄を分け合い、隠し合います。
• どの重要度スコアも原因を意味しません。1つの特徴量が支配的なら、祝う前にリークを確認する理由になります。

さらに読む

• The Elements of Statistical Learning, Hastie, Tibshirani and Friedman: 9.2節が木を、第10章がブースティングを扱い、勾配の見方と学習率の役割も含みます。
• Greedy Function Approximation: A Gradient Boosting Machine, Friedman, 2001: ブースティングを関数空間での勾配降下法として定義した原論文。
• scikit-learn user guide, “Decision Trees”および“Ensembles: Gradient-boosted trees”: このページで使ったパラメータとヒストグラム実装。
• scikit-learn user guide, “Permutation feature importance”: 手法、相関する特徴量についての注意点、不純度重要度との比較例。