On Stopping Rules and Spatial Adaptation for CART

機械学習という、コンピュータがデータから予測を行う方法を学ぶ広大な風景の中で、最も永続的で信頼されているツールのひとつが決定木（ディシジョン・ツリー）である。データに関する一連の単純な質問——例えば「温度は70度を超えているか？」や「所得は5万ドルより多いか？」といったもの——を投げかけ、答えを最終的な結論へと導くフローチャートを想像してみてほしい。これらのモデルは、人間にとって読みやすく理解しやすい一方で、はるかに複雑なシステムとも競合できるほど強力であるため、人気がある。これらの木を構築するための標準的な手法であるCARTは、貪欲な探索者のように機能する。すなわち、各ステップにおいて、現在のデータのグループを、互いにできるだけ異なった2つの部分に分割する単一の質問を探し出すのである。この質問を繰り返すことで、データ空間をより小さく矩形のボックスへと刻み込み、停止を決定するまでプロセスを継続する。

統計学者たちを長年悩ませてきた謎は、木がいかに成長するかではなく、いつ停止するかである。停止のルールは極めて重要である。なぜなら、それらが最終的なボックスのサイズ、すなわち予測を行うための局所的な近傍となるサイズを決定するからである。もし木が早く停止しすぎれば、ボックスは大きくなりすぎ、予測は局所的な詳細を見逃した大まかな平均値になってしまう。もし停止が遅すぎれば、ボックスは極小となり、真のパターンではなくデータのランダムなノイズを捉えてしまう。分割箇所を選択する方法については広く研究されてきたが、停止ルールの統計的な役割については、いまだ不明瞭な部分が多い。研究者たちは、これらの貪欲な木が、データの複雑さを正確に教えられなくても、データの局所的な複雑さに自動的に適応できるのか（つまり、荒々しく凹凸のある領域では細かく詳細な予測を行い、平坦で穏やかな領域では滑らかで単純な予測を行うことができるのか）という疑問を長年抱いてきた。

シンガポール国立大学の研究チームは、この問いに対して決定的な答えを提示し、標準的なCARTアルゴリズムが特定の種類の停止ルールを使用する場合に限り、確かにこのような空間的適応を実現できることを証明した。彼らの研究は、最も一般的な停止決定法である「すべての最終的なボックスに最小限のデータポイントが含まれることを要求する」という手法が、適応に失敗することを明らかにしている。この硬直したルールは、滑らかで予測可能な領域と、混沌としてノイズの多い領域を、全く同じレベルの詳細さで扱うことを強いるため、一方または両方の領域においてパフォーマンスの低下を招く。対照的に、分割によって得られる改善が特定の閾値を下回ったときに木を停止させるという異なるルールを用いることで、アルゴリズムが完璧なバランスを見つけられることを、研究者たちは証明した。この閾値ベースのルールは、感度の高い計器のように機能し、さらなる分割が新しい情報を明らかにしているのではなく、単にランダムな変動を追いかけているだけであると自動的に検知するのである。

研究者たちは、この閾値ベースのルールを使用した場合、木がデータの変化が激しい領域では小さく詳細なボックスを、データが滑らかな領域では大きく単純なボックスを自然に作成することを示した。彼らは、これがデータセット全体にわたって同時に起こることを数学的に証明した。つまり、どこに粗い部分や滑らかな部分があるかを事前に知ることなく、木が至る所で局所的な詳細を正しく捉えられることを意味している。この発見は、決定木がなぜ実用において効果的なのかを説明する上で重要である。決定木は単なる硬直した構造ではなく、データの景観に合わせて自らの解像度を調整できる適応型のツールなのである。また、本研究は、この適応が、データに意味のある分割を見つけ出すための十分な信号が含まれているという特定の構造的条件に依存していることを明らかにし、データが純粋にランダムである場合や、分割プロセスを混乱させるような構造を持つシナリオを除外した。

なぜ一般的な「最小リーフサイズ」ルールが失敗するのかを理解するために、世界の一部の場所では値がゆっくりと変化し、別の場所では急速に変化するというシナリオを考えてみよう。もしルールが、すべての最終的なボックスに、例えば50個のデータポイントが含まれていなければならないと要求する場合、木はその両方の領域において同じサイズのボックスを作ることを強制される。滑らかな領域では、このボックスは不必要に小さくなり、ノイズを捉えて予測をジリジリとしたものにする。一方で、荒れた領域では、このボックスは大きすぎて重要な詳細を滑らかにしてしまい、予測をぼやけさせてしまう。研究者たちは、単一の最小ボックスサイズでは、両方の領域のニーズを同時に満たすことはできないことを示した。一つのサイズが、すべての局所的なタスクに適合することは不可能なのである。

対照的に、閾値ベースのルールは、分割から実際に得られる価値を測定することによって機能する。木がデータをより小さな断片へと刻んでいくにつれ、各新しいカットによる利得は次第に減少していく。滑らかな領域では、利得は急速に低下し、木に早期停止を促して大きなボックスを残させる。荒れた領域では、利得はより長く高い状態を維持するため、細かい詳細に到達するまで木に切り続けさせる。研究者たちは、この停止点が、その特定の場所における予測を行うための最適なサイズと正確に一致することを証明した。彼らは、データの信号が背景ノイズと区別できなくなる瞬間に、木が正確に分割を停止し、最終的なボックスが大きすぎず、かつ小さすぎないことを示した。

研究はまた、データが多くの異なる特徴を持つ高次元の設定における木の挙動についても扱った。彼らは、データが関連する特徴に焦点を当てることを可能にする特定の構造的パターンに従っている限り、同じ適応メカニズムが保持されることを見出した。これは、決定木が、無関係な情報を無視し、データが変化している方向に対してのみボックスを精緻化できることを意味する。研究者たちは、これらの条件を満たす複雑な関数の例を提示し、理論が幅広い現実的なシナリオに適用できることを示した。

論文は、アルゴリズムの理論的な保証に焦点を当てているが、実世界のデータ分析に対する示唆は明白である。それは、決定木の成功が偶然ではなく、深い統計的特性に基づいていることを示唆している。すなわち、適切な停止ルールが、木の構造をデータの局所的な幾何学形状に一致させる能力である。最小不純度減少ルールが局所予測において最高の精度率を達成することを証明することで、研究者たちは、これらのモデルの経験的な成功に強固な理論的基礎を与えた。彼らの研究は、実装が容易に見えるかもしれないが、最終的にはモデルが問題の真の複雑さに適応することを妨げてしまう、より単純で硬直した停止ルールを使用することへの警告としても機能している。

研究者たちは、正しいルールが機能することを証明するにとどまらず、なぜ間違ったルールが失敗するのかをも正確に示した。詳細な数学的議論を通じて、彼らは、単一のグローバルな停止パラメータでは、滑らかさのレベルが異なる2つの地点において、バイアスと分散のトレードオフを同時に最適化することはできないことを示した。これは、最小リーフサイズ・アプローチの根本的な限界である。この証明は、粗い地点における最適なボックスサイズが、滑らかな地点における最適なボックスサイズとは劇的に異なる特定の例を構築することに基づいている。これにより、単一のグローバルな制約が両方を正しく扱うことは不可能であることを示したのである。

実験において、研究者たちは、粗くギザギザしたセクションと滑らかな線形セクションを組み合わせたハイブリッド信号を用いて、これらの違いを可視化した。彼らは、閾値ルールを用いた木が、粗いセクションには小さく複雑なボックスを、滑らかなセクションには大きく単純なボックスを作成することを観察した。しかし、最小リーフサイズ・ルールを用いた木は、両方のセクションでほぼ同一のサイズのボックスを生成し、モデルの構造とデータの現実との間に明らかなミスマッチを生じさせた。この視覚的な証拠は、彼らの理論的発見を補強し、適応的な挙動が単なる数学的な好奇心ではなく、アルゴリズムの具体的な特徴であることを示した。

論文は、停止ルールが単なる実装上の細部ではなく、アルゴリズムの統計的な力の中心的な構成要素であることを強調して締めくくられている。それは、木を、硬直した「一律のサイズ」の構造から、柔軟で局所的に適応可能な推定器へと移行させるメカニズムである。この適応が発生する正確な条件を確立することで、研究者たちは、最小不純度減少ルールの統計的な役割を明確にした。彼らの研究は、決定木の実際的な成功と、なぜそれらが機能するのかという理論的な理解との間の溝を埋め、複雑で不均質な現実世界のデータに対してナビゲートする能力についての精密な説明を提供している。