Approximation-Free Differentiable Oblique Decision Trees

技術的概要：近似なしの微分可能な斜め決定木

問題定義
決定木（DT）は、解釈性と表形式データに対する有効性から、医療診断などの安全クリティカルな領域で高く評価されています。しかし、特徴量の線形結合による分割（軸に平行でない分割）を行う「斜め」DT の正確な学習は、探索空間が NP 困難であるため、計算上困難です。最近の微分可能なアプローチは勾配ベースの学習を可能にしますが、学習プロセスの整合性を損なう近似に依存しています：

1. ソフト DT： 木を微分可能にするために確率的な「ソフト」境界（シグモイド活性化など）を使用しますが、これらを「ハード」な意思決定に変換すると、精度が低下する傾向があります。
2. ストレートスルー推定子（STE）： DGT や ICCT などの手法で、微分不可能なハードな意思決定を通じた勾配を近似するために使用されます。これにより、フォワードパス（評価）とバックワードパス（最適化）の間に意味的な不一致が生じます。回帰タスクでは、この不一致が偏った勾配更新、構造的な不安定性、およびリーフノードの未利用を引き起こします。内部パラメータはすべての回帰器に基づいて更新される一方で、実際には 1 つのみが選択されるためです。

手法：DTSemNet
著者は、ハードな斜め DT の意味的に等価かつ可逆的な表現を提供する新しいニューラルネットワークアーキテクチャ「DTSemNet」を提案します。先行研究とは異なり、DTSemNet は近似なしで標準的な勾配降下法を用いたエンドツーエンドの学習を可能にします。

• アーキテクチャ： DTSemNet は、$m$個の内部ノードと$n$個のリーフを持つ DT を、ReLU 活性化と線形演算を用いたニューラルネットワークに符号化します。
  • 内部ノード： $\langle A_i, x \rangle + b_i$を計算する線形層で表現されます。
  • 分岐： 正（$\top$）と負（$\bot$）の結果を分離するために ReLU 活性化を使用し、測度ゼロの境界を除き、任意の入力に対して正確に 1 つの分岐のみがアクティブになるようにします。
  • リーフ： 固定重みの線形層がアクティブな分岐を集約し、各リーフのロジットを生成します。
• 意味的等価性： 定理 1 は、任意の入力$x$に対して、ハード DT が選択するリーフと、DTSemNet ネットワークで最大出力ロジットを持つリーフが同一であることを証明しています。したがって、評価関数（フォワードパス）と最適化関数（バックワードパス）は意味的に同一です。

回帰戦略：Annealed Top-k
分類は（argmax 経由で）この定式化と自然に整合しますが、回帰ではルーティング（内部ノード）とリーフ回帰器を共同で最適化する必要があります。著者は、単一の STE（以前の会議論文で使用されたもの）を使用すると、内部ノードがすべての回帰器に基づいて更新される一方で、各ステップでは1 つの回帰器のみが更新されるため、不安定になると指摘しています。

これを解決するため、本論文ではAnnealed Top-k法を導入します：

1. メカニズム： 学習中のハードな Top-1 選択の代わりに、モデルは当初、Top-$k$セレクター（$k \ge 2$）と温度スケーリングされた Softmax を組み合わせて使用します。これにより、モデルは複数のエキスパート（リーフ）に同時に入力をルーティングし、有益な勾配を提供できます。
2. アニーリング： $k$の値は、学習エポックを通じて$k \ge 2$から$k=1$へ徐々に減少します。
3. 利点：
   • 勾配の一貫性： STE と異なり、フォワードパスとバックワードパスは各ステップ$k$で同じ意味を共有します。
   • バランスの取れた更新： 内部ノードのパラメータは、選択されたトップ$k$の回帰器のみに基づいて更新されるため、遠く離れた未選択のリーフによる不安定化の影響を防ぎます。
   • 探索： 単一のサンプルに対して複数の回帰器が更新されるため、学習の後半でルーティング決定が変化した場合でもモデルが適応できます。
4. 微調整： $k=1$に達すると、内部ノードは固定され、リーフ回帰器は過学習を防ぐために拡張サンプルを用いて微調整されます。

主要な貢献

1. DTSemNet アーキテクチャ： ハードな木と意味的に等価な斜め DT の微分可能な符号化。分類において近似なしの正確な勾配降下学習を可能にします。
2. 回帰のための Annealed Top-k： 回帰における STE ベースの手法に内在する近似とバイアスを排除する新しい学習手順。ルーティングとリーフパラメータの安定かつ正確な共同最適化を確保します。
3. プログラム的 RL ポリシー： 離散および連続動作空間の両方で標準的なニューラルネットワーク（NN）を置き換えるプログラム的ポリシーとしての DTSemNet の実証。

実験結果
著者は、DTSemNet を分類、回帰、および RL ベンチマークにおいて、最先端の手法（TAO、DGT、CRO-DT、CART、ICCT、VIPER）と比較評価しました。

• 分類： DTSemNet は、簡潔な木および高密度な木を含むすべてのテストデータセットで最良のパフォーマンスを達成しました。非勾配手法（TAO、CRO-DT など）および勾配ベースの近似（DGT）を大幅に上回り、Optical Recognition などの困難なベンチマークでは分類誤差を最大 10% 削減しました。学習時間は DGT と同等でしたが、大域的探索手法よりも大幅に高速でした。
• 回帰： Top-k を用いた DTSemNet は、ほぼすべてのデータセットで競合他社を上回りました。TAO-Linear に対して平均 RMSE で 3% の改善を達成し、STE を使用した DTSemNet-STE を大幅に上回りました。アブレーション研究により、STE がリーフの未利用傾向にあるのに対し、Top-k はよりバランスの取れたリーフ利用と安定した重みの進化をもたらすことが確認されました。
• 強化学習：
  • 離散動作： LunarLander や Zerglings などの環境において、DTSemNet は NN の性能と同等かそれ以上であり、他の DT ベースのポリシー（DGT、ICCT、VIPER）を大幅に上回りました。
  • 連続動作： SAC と Top-k アニーリング戦略を併用することで、DTSemNet は Continuous LunarLander および BipedalWalker において NN ベースラインおよび STE ベースの DT を上回りました。これは、近似なしの学習が連続制御においても優れたポリシーをもたらすことを示しています。

意義と主張
本論文は、DTSemNet が分類および回帰の両方の設定において斜め DT の近似なし学習を達成した最初のアーキテクチャであると主張しています。評価と最適化の間の意味的不一致を排除することで、STE ベースのアプローチの不安定性とバイアスを克服します。著者は、これが記号モデル（DT）の解釈性と勾配ベース学習のスケーラビリティの間のギャップを埋め、安全クリティカルなアプリケーションや複雑な RL 環境において、高性能かつ解釈可能なモデルを実用的なものにすると論じています。

限界と将来の課題
著者は、DTSemNet は DT であるため、複雑な形状の処理に苦しみ、画像のような高次元入力には適さないことを認めています。将来の課題としては、固定された木の高さをハイパーパラメータとするのではなく、適応的な木成長と剪定のための微分可能な手法の開発に焦点を当てることが挙げられます。