というタイトルの統数研の講座を受けたのでメモ。非常に役に立った。 アルゴリズムや、その背景の数式は、最悪、文献を読めば分かるが、なぜ、その問題を解こうと思ったのか、なぜ、この手法が良いと思われているのかというような研究の流れは、一線の研究者の説明を聞くのが一番早いなと思った。

決定木界隈の巨人3人

  • Breiman: Bagging / RF
  • Friedman: Gradient Boosting
  • Quinlan: C4.5

BFOS: 1984

決定木研究の古典文献

Classification and Regression Trees

  • breiman
  • friedman
  • olshen
  • stone

CARTを開発した人

  • CART: BFOS
    • briman
    • friedman
    • or
    • stone
      • ノンパラの偉い人
      • stoneの一致性定理

決定木の歴史

  • 概念学習という分野があった
    • 表データ・特に、論理関数の出力表みたいな（複数の入力論理値に対して出力論理値が定義されているような表）を再現するルールを作るアルゴリズムを考えるというような問題
  • 歴史的には論理学・論理回路への応用を念頭に考えられてた
    • 論理関数を作るような応用に実際に使われていた
      • だからよくXORの学習が出てくるんね

C4.5

  • CARTと並ぶ分類機の決定版的存在
  • 人間に理解しやすい・運用しやすいルールが得られる、のが良いとされたらしい
  • CARTとc4.5は何が違うんかね
    • cf: https://medium.com/@abedinia.aydin/survey-of-the-decision-trees-algorithms-cart-c4-5-id3-97df842831cd

交互作用の同定

  • AID: 1963
    • 多変量回帰の交互作用を踏まえて最適な説明変数を選ぶような問題意識
    • 伝統的には、掛け算した項を入れることで交互作用を考えたことにする
    • ただ、多変量回帰の文脈では、入れられる説明変数を全部入れるような乱暴な実践が批判的に捉えられていたので、交互作用を踏まえた説明変数の自動決定みたいなものを考えたくなった
    • AIDは、統計学のコミュニティでは割とボロクソに批判された
  • 参考2が面白い

非線形回帰

  • 木ベースの手法は振る舞いが制御しやすくて割と良い
  • 回帰手法のベースラインとしては「定数」回帰を入れよう！
    • 学習データがなんでも、予測特徴量がなんだったとしても、下手はこかない
    • 区分的に定数にしたら→回帰木
  • 拡張
    • 領域ごとに線形回帰する
    • MARS
      • 区分的線形（連続になるようにする）
      • サンプルが少ない場合に、どうしようもなくなる
    • 局所平均化推定量：理論的には、標本数無限大である種の一致性を保つことが示された（stoneの一致性。昔は、そういう推定量を作れるかどうかも理論的には不明だった）
      • 無理数の定義関数でも、局所平均化推定量で一致性を持たせられる！

第二部: 決定木の学習アルゴリズム

  • 基本的には、「1つの特徴量での決定株decision stumpの学習」の再帰
    • 各サンプルの中間で区切った分割を総当たりで最も良いものを探す、以上
      • 厳密に全探索することに意味はない
      • サンプル数が多いと大変なので、ヒストグラムで近似しちゃうとか
      • アンサンブル学習の基底として使う時には厳密には意味ないよ
    • dtreeviz便利そう
  • 良さはジニ係数とかエントロピーとか(分類)、回帰だと事情誤差とかfriedman mseとか
    • 同点が発生しやすいので誤判別率よりは不純度を選ぶことが多い
    • 分割が「良い」とは不純度の改善量が大きいこと
  • 分類木も回帰木も、要はデータ依存型分割によるヒストグラム近似、と見れる
    • グリッドで領域分割すると高次元ではデータが入らない領域もあるけど木ベースの手法では、各領域は必ずデータを含む
  • よく考えると、「最適な」木が得られるかというと、実はその保証はない
    • けど、学習データに対して「最適」を追求しても、そんなに嬉しくない、つうのが潮流
      • 水平線効果
    • 解釈性などの観点では有利なのかもしれない
  • 剪定
    • cct_aplha
    • weakest link pruning
  • 欠損値
    • 学習時は単に無視する
    • 予測時は、いろいろな方法がある
      • 両方に送り、最終的にたどり着いた葉ノードの値を加重平均するとか
  • カテゴリ変数
    • 等号質問は不等号質問２回で作れるため、基本はlabel encodingでok
    • ２値分類の場合は、X=1になりやすい順にラベルエンコーディングすれば良い
  • 一般化
    • 境界を一次元射影できるのではなく、線形分割する
    • 各葉の中で定数でなく回帰する
    • 両者とも、結局あんまり使われなかった
  • 欠点について → アンサンブルに行った
    • 非平滑性：低次元だと気になるけど、10次元・20次元のような高次元でも滑らかなのが妥当なのかは疑問
    • 不安定性：ちょっとデータが変わる時の構造は大きい。low bias / high varな手法
      • この辺の欠点は、アンサンブルで改善できる
  • off the shelf: 分類木は

  • breiman, statistical modeling: the two cultures

  • 決定木の教師なし学習
    • sklearnにも2種類くらい入ってるらしい
      • isolation forest
      • random embedding
      • density forest
    • impurityを教師信号なしで定義できるやつを工夫する感じらしい
  • practicalな観点では、PCAによる主成分などを元の変数につけるとかやる

アンサンブル

  • sklearn.ensemble

  • bagging系と最適化形がある

  • bagging
    • ランダム部分集合をたくさん作って、それらに弱学習機を作る
      • 個々の弱学習機が相関を持たないことが大事
      • 個々の学習機は過学習してて良い
    • random forest
      • 個々の決定木の学習において、分岐の基準点を探すときに、毎回、各変数からランダムに選ぶ。シンプル
    • extra tree
      • 個々の決定木の分岐点において、分類の基準変数をランダムに選び、基準水準もランダムに選ぶ。なにそれて感じだが、これがworkする。baggingの威力
      • 良性過適合現象
  • 勾配ブースティング系
    • 「次」の弱学習機は、損失関数の勾配のデータ点での評価値を予測するように（加えたときに損失が一番効率よく減る方向に）構成する
    • 勾配ブースティングは、パラメータの調整が大事。各ステップで小さい木を使う必要があるが、どれくらい小さいのが適当なのかはチューニングが必要。random forest/extra treeをベースラインに比較するのが良さそう

実践

  • 可視化
    • dtreeviz
  • パラメータ
    • 木の数
    • max_leaf_nodes or max_depth: どれくらい複雑な木か
    • min_samples_leaf 一領域が小さすぎないように
    • ccp_alpha コストベースの剪定
    • bootstrap
  • 解釈性
    • 決定木は、分散が大きいので、実は個々の木の分岐はあまり意味がないと考えた方が良い
    • 重要度・PDP・SHAPなどをみる
  • 重要度
    • MDP: mean decrease in impurity 平均不純度改善
    • PFI: permutation feature importance
      • 学習済みモデルに、どれかの変数の値をランダムにシャッフルしたデータセットを入力したときに損失がどれくらい悪化するかを計算。大事な変数なら、大きく悪化するはず
  • PDP
    • 各変数の値だけを変化させた時の出力値変化の経験平均のプロット
      • 注目している変数以外はサンプル平均で代表化
  • SHAP: SHapley Additive exPlanations
    • yの平均値からの差分がどの要因で生まれたのか、をゲーム理論の考えを援用して定義する
    • データのインスタンス点ごとに値が出る
    • intaractiveなツールがあるので、探索的な分析には便利
  • 予測値の分散/信頼度
    • bagging系のものは、たくさんの予測値が手元にあるので、自然に予測値分散が計算できる
    • boosting系のものは、各弱学習機の予測値は改善幅なので、直接は使えない
      • 分位点回帰というのを使うらしい
    • scikit optimizeというツールが便利らしい