ハクソク

世界を動かす技術を、日本語で。

決定木 - ネストされた意思決定ルールの非合理的な力

70日前原文(mlu-explain.github.io)

概要

  • 決定木はデータを繰り返し分割し、分類を実現する手法
  • 分割基準にはエントロピーやジニ不純度を利用
  • 情報利得（Information Gain）を最大化することで分割点を決定
  • 過学習や高い分散といった課題も存在
  • ランダムフォレストなどの手法で安定性向上が可能

決定木の基礎とエントロピー

  • 決定木 は、上から下へと連続的な条件分岐を作成し、データを分類するアルゴリズム

  • 各ノードで データ分割の基準 を選択する必要性

  • 分割基準を決めるために エントロピー という指標を利用

  • エントロピーは 情報量や不確実性 を測定する尺度

  • エントロピーの計算式： エントロピー = -Σ(p_i * log(p_i)) （p_iは各クラスの確率）

    • エントロピーの性質
      • すべてのp_iが0で一つだけ1の場合、エントロピーは0（完全な純粋さ）
      • すべてのp_iが等しい時、エントロピーは最大（最大の不純度）
      • 確率が均等に近づくほどエントロピーは増加

  • ノード内に複数クラスが混在→ 不純（impure）ノード

  • ノード内が単一クラス→ 純粋（pure）ノード

  • エントロピーを使ってノードの純度を数値化

情報利得とID3アルゴリズム

  • 情報利得（Information Gain） は、分割前後のエントロピー差で情報の増加量を測定

  • 分割前のエントロピーから、各分割後のエントロピーの重み付き平均を引いて計算

  • 最大の情報利得 を与える分割点を選択

  • ID3 はこの情報利得を最大化するよう再帰的に木構造を作るアルゴリズム

    • ID3の手順
      • 各特徴量ごとにエントロピーを計算
      • さまざまな分割値でデータセットを分割
      • 分割ごとに情報利得を計算
      • 最も情報利得が大きい分割を選択し、決定ノードを作成
      • これ以上分割できない場合、葉ノードを作成しラベルを付与（分類の場合は最頻クラス、回帰の場合は平均値）
      • 各サブセットで再帰的に処理を繰り返す
      • すべての要素が同じクラスになったら再帰終了
      • 追加の停止条件として、葉あたりの最小サンプル数や最大深さの制約も可能

分割の選択例と可視化

  • 例えば Diameter ≤ 0.45 での分割は、情報利得を最大化する条件として選択された
  • すべての特徴量と分割値で情報利得を計算し、最も高いものを採用
  • 可視化ツールなどで分割境界を動かすことで、分割後の各ノードのエントロピーや情報利得の変化を確認可能

ジニ不純度との比較

  • ジニ不純度（Gini impurity） もエントロピーと同様に純度を測る指標
  • ジニ不純度はエントロピーより計算が高速（対数演算を使用しないため）
  • エントロピーとジニ不純度のどちらを使っても、ほとんどの場合で結果は類似
  • クラス不均衡が強い場合はエントロピーがより慎重に動作する傾向

決定木の長所と短所

  • 長所

    • シンプルで直感的なモデル
    • 解釈性が高い
    • 学習が高速
    • 前処理が少なくて済む
    • 外れ値への耐性

  • 短所

    • データの微小な変動に非常に敏感（高分散・不安定）
    • エントロピー最小化を追求しすぎると木が深くなり過学習しやすい
    • 決定木単体では新規データへの汎化性能が低下しやすい

過学習・分散対策とランダムフォレスト

  • 過学習や高分散に対する対策

    • 木の最大深さ制限
    • 葉ノードの最小サンプル数設定
    • 葉ノード数の上限
    • 剪定（pruning） による木の簡略化

  • さらなる対策として ランダムフォレスト のようなアンサンブル手法の利用

    • 複数の決定木を異なるサブセットや特徴量で訓練
    • 予測を多数決や平均で統合し、分散を低減
    • 汎化性能の向上

まとめ

  • 決定木は、特徴量空間を条件ごとに分割しながら分類・回帰を行うアルゴリズム
  • エントロピーやジニ不純度を用いてノードの純度を測定し、情報利得最大化で分割点を決定
  • ID3アルゴリズムは情報利得最大化のための代表的な手法
  • 過学習や高分散という課題もあるが、剪定やランダムフォレストによって対策可能
  • 決定木はシンプルかつ強力な機械学習モデルとして広く活用

参考文献・リソース

  • "A Mathematical Theory Of Communication"（Claude E. Shannon, 1948）
  • "Induction of decision trees"（John Ross Quinlan, 1986）
  • "A Study on End-Cut Preference in Least Squares Regression Trees"（Luis Torgo, 2001）
  • "The Origins Of The Gini Index: Extracts From Variabilità e Mutabilità"（Corrado Gini, 1912）
  • D3.js（Mike Bostock & Philippe Rivière）
  • d3-annotation（Susie Lu）
  • KaTeX（Emily Eisenberg & Sophie Alpert）

追加学習リソース

  • Dive into Deep Learning テキストブック
  • YouTube動画、自己学習コース
  • 記事に関する意見や質問はJaredまたはLucíaまで

ご拝読ありがとうございました！

Hackerたちの意見

面白いウェブサイトで、プレゼンテーションも素晴らしいね。ただ、いくつかのテキストの色のコントラストが悪くて、読みづらいのが気になったかな。

└

まさにその通りだね。FFのリーダービューは神のような存在だよ。『アクセス可能な』コンテンツは障害のある人だけのためじゃなくて、色のセンスが悪い人にも助けになるしね。まあ、読みやすいコンテンツに関しての悪いセンスってことだけど ;)

とても美しいプレゼンテーションだったね！

面白い事実だけど、単一ビットのニューラルネットワークは決定木なんだ。理論的には、ほとんどのニューラルネットワークをif-else文の連鎖に「コンパイル」できるってことだけど、こういうアプローチがうまくいくのはあまり理解されていないんだよね。

└

これをやってくれるソフトウェア知ってる？それとも関連する論文とか？週末の楽しいプロジェクトになりそうだね。

└

シングルビットニューラルネットワークは決定木です。ここで何を意味しているのか正確には理解できなかったので、少し調べてみました。「ニューラルネットワークは決定木である」という興味深い論文があります[1]。問題は、これがニューラルネットワークを決定木にうまくマッピングすることを意味しないということです。ニューラルネットワークに対応する木は非常に大きいです。この論文が決定木の概念を少し拡張しているように感じます。また、あなたが何を意味しているのか正確にはわからないので、もう少し詳しく説明してもらえますか？ :) [1] https://arxiv.org/pdf/2210.05189

決定木は素晴らしいよ。僕のお気に入りの古典的な機械学習アルゴリズム、というかアルゴリズムのグループだね。決定木にはいろんな微妙なバリエーションがあるからね。GNU Guileで純粋に関数型（ちょっと素朴な）並列実装を書いたよ： https://codeberg.org/ZelphirKaltstahl/guile-ml/src/commit/25... なんで「素朴」かっていうと、GuileのエコシステムにはNumPyやデータフレームがないから、データの表現がかなり非効率的なんじゃないかな。

└

numpyやデータフレームは、Guileにすでにある決定木のロジックに対してどんな利点があるの？素朴な疑問です。Guileのような言語は決定木に非常に適していて、木を操作するのが得意だからです。唯一、決定木を機械語にコンパイルするのが少し手間かもしれませんが、そうすればランタイム構造をたどる必要がなくなり、効率的です。ちなみに、Lushを見てみてください。気に入るかもしれません。 https://lush.sourceforge.net/ https://news.ycombinator.com/item?id=2406325 Guileでベクトルやテンソルを探しているなら、これがありますよ。 https://wedesoft.github.io/aiscm/

専門家のあいまいな意思決定は、シンプルな決定木や決定チェーン（連結リスト）でモデル化できることが多いんだ。専門家が自分の意思決定がもっと複雑だと思っていても、シンプルな決定木の方が専門家の意思決定をよくモデル化できるんだ。回帰や距離ベースのクラスタリング技術に比べると、決定木はちょっと素朴に見えて長い間無視してきたけど、決定木は間違いなく非常に効果的だよ。オックスフォードの専門知識ハンドブックの第7章を見てみて。すごく興味深いよ！

└

以前、基本的に2D平面で意思決定を分割するビジュアライゼーションを見たことがあるんだ。その視点から見ると、決定木はkD-ツリーが可能性空間を分割して、ボリュームにアクションを付けるためのかっこいい言葉かもしれないね。その仮定を考えると、あいまいな意思決定は、専門家の決定が2つの異なるアクションを分ける表面の粒度においてより微妙であることから来ているのかもしれない。粗い技術かもしれないけど、それでもかなり良い近似を導き出せるはずだよ。

2010年頃にCERNで働いていたとき、ブーステッド決定木が最も人気のある分類器でした。説明可能性と表現力の両方が理由です。当時、物理分析に直接使われるモデルには、特にニューラルネットワークに対して文化的な嫌悪感がありました。時代は変わりましたね…

└

ブーステッド決定木はブーステッドランダムフォレストと同じですか？

└

時代は変わりましたね… これはちょっと心配になりますね。物理学におけるパラメータが豊富で不透明なモデルの使用について。プトレマイオスの体系は、コペルニクスの体系よりも惑星の動きをはるかに良くフィットさせました。なぜなら、彼の体系は普遍的な近似器だったからです。エピサイクル系はフーリエ解析の一形態で、滑らかな周期的運動をフィットさせることができます。しかし、エピサイクルは因果メカニクスを解明するために使うべきものではありませんでした。経験的には良いフィットでしたが。物理学では、単に正確な曲線フィッティング以上のことをしたいのです。

分類器を学ぶための「秘密兵器」として、まず良い線形分類器を学ぶのがとても役立ちました。これを教えるのはちょっとためらいますが（冗談です）。その線形分類器の出力の非閾値版を、決定木を学ぶための追加の特徴次元として使ってみてください。これをブーステッドツリーのシステムとしてまとめるんです（必要に応じて短い木を追加する感じで）。これがうまくいく理由の一つは、彼らの強みを活かすからです：（i）決定木は線形関数にフィットするのが難しくて、たくさんの内部ノードが必要になるからです。そして（ii）線形関数は、等ラベル領域が再帰的に分割された構造を持つ場合には最悪です。決定木の構築プロセスでは、最初のカットは追加した合成線形特徴に対して行われることが多く、これによって線形分類器の精度がすぐに得られます。残りは線形分類器が苦戦している部分に決定木アルゴリズムが取り組むことになります。このアイデアはブースティングとあまり変わらないですね。データの異なる（ランダムな）回転を考えて、上記のステップを使って木の森を作ることもできますが、通常は必要ありません。あるいは、すべての軸を学習した線形分類器に対して直交するように回転させることもできます。決定木が苦戦するのは、特徴自体が非常に（カラム）スパースな場合で、カットを置く場所があまりないからです。

└

（ii）線形関数は、等ラベル領域が分割された構造を持つ場合には最悪です。「等ラベル領域が分割された構造を持つ」というのはどういう意味ですか？

└

やりたいことに対する意思決定ツリーがあるよ。斜めの意思決定ツリー、モデルツリー（例えばM5ツリー）、ロジスティックモデルツリー（LMT）や階層的専門家混合モデル（HME）とかね。

同じサイトのランダムフォレスト: https://mlu-explain.github.io/random-forest/

それって人間（や動物）も同じように動いてるんじゃない？人間社会は実際の大きな相関関係を探して、分類を作るよね。科学的な考えを持つ人たちは、相関関係の背後にある理由も知りたがることが多いけど。デイヴィッド・ヒュームもそれに関わってたし… ちょっと挑発的な質問をしてみるね。結局、知識とバイアスの違いって何だと思う？

数年前に意思決定ツリーとランダムフォレストの分類器を使った製品にプロとして関わったことがあるんだ。数学のバックグラウンドは全然なかったから、これを学ぶのに苦労したけど、今やLLMやAIが注目されてるから、その努力が実を結んでる。これが一番いい説明だと思ってて、そのプロジェクトをすごく懐かしく感じる。何か個人的なものを作ってみようかな。今、みんな回帰モデルをほぼ常に使ってるのに、誰も自分でこれを使おうとしないのが不思議だよね。