論文の概要: Breiman meets Bellman: Non-Greedy Decision Trees with MDPs

• arxiv url: http://arxiv.org/abs/2309.12701v5
• Date: Sun, 01 Jun 2025 16:37:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-03 20:53:52.755822
• Title: Breiman meets Bellman: Non-Greedy Decision Trees with MDPs
• Title（参考訳）: ブレイマン、ベルマンと会談。非グレーディ決定木とMDP
• Authors: Hector Kohler, Riad Akrour, Philippe Preux,
• Abstract要約: 我々は、欲求と最適なアプローチのギャップを埋めるフレームワークDPDT(Dynamic Programming Decision Trees)を提案する。 DPDTはマルコフ決定プロセスの定式化と分割生成を組み合わせ、ほぼ最適決定木を構築する。 実験の結果,DPDTは既存の最適解法よりも桁違いに少ない演算でほぼ最適損失を達成できた。
• 参考スコア（独自算出の注目度）: 8.530182510074983
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In supervised learning, decision trees are valued for their interpretability and performance. While greedy decision tree algorithms like CART remain widely used due to their computational efficiency, they often produce sub-optimal solutions with respect to a regularized training loss. Conversely, optimal decision tree methods can find better solutions but are computationally intensive and typically limited to shallow trees or binary features. We present Dynamic Programming Decision Trees (DPDT), a framework that bridges the gap between greedy and optimal approaches. DPDT relies on a Markov Decision Process formulation combined with heuristic split generation to construct near-optimal decision trees with significantly reduced computational complexity. Our approach dynamically limits the set of admissible splits at each node while directly optimizing the tree regularized training loss. Theoretical analysis demonstrates that DPDT can minimize regularized training losses at least as well as CART. Our empirical study shows on multiple datasets that DPDT achieves near-optimal loss with orders of magnitude fewer operations than existing optimal solvers. More importantly, extensive benchmarking suggests statistically significant improvements of DPDT over both CART and optimal decision trees in terms of generalization to unseen data. We demonstrate DPDT practicality through applications to boosting, where it consistently outperforms baselines. Our framework provides a promising direction for developing efficient, near-optimal decision tree algorithms that scale to practical applications.
• Abstract（参考訳）: 教師付き学習では、決定木は解釈可能性と性能で評価される。 CARTのような強欲な決定木アルゴリズムは、その計算効率のために広く使われているが、正規化されたトレーニング損失に対して、しばしば準最適解を生成する。 逆に、最適決定木法はより良い解を見つけることができるが、計算集約的であり、典型的には浅い木や二項的特徴に限られる。 我々は、欲求と最適なアプローチのギャップを埋めるフレームワークDPDT(Dynamic Programming Decision Trees)を提案する。 DPDTはマルコフ決定過程の定式化とヒューリスティック分割生成を組み合わせ、計算複雑性を著しく低減した最適決定木を構築する。 本手法では,各ノードにおける許容スプリットのセットを動的に制限し,ツリーの正規化トレーニング損失を直接最適化する。 理論的解析により、DPDTは少なくともCARTと同様に正規化トレーニング損失を最小限に抑えることができることが示された。 実験の結果,DPDT は既存最適解法よりも桁違いに少ない演算でほぼ最適損失を達成できることを示す。 さらに重要なことは、広範なベンチマークにより、CARTと最適決定木の両方に対してDPDTを統計的に有意に改善したことを示唆している。 DPDTの実用性をアプリケーションの強化を通じて実証し、ベースラインを一貫して上回ります。 我々のフレームワークは、実用的なアプリケーションにスケールする効率的で最適に近い決定木アルゴリズムを開発するための有望な方向を提供する。

関連論文リスト

• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。 重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。 フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
  論文  参考訳（メタデータ） (2024-08-16T02:07:34Z)
• Online POMDP Planning with Anytime Deterministic Optimality Guarantees [9.444784653236157]
  近似解と最適解の間の離散POMDPに対する決定論的関係を導出する。 我々の導出は、新しいアルゴリズムセットの道を提供し、既存のアルゴリズムにアタッチできることを示します。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features [5.663538370244174]
  本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。 提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
  論文  参考訳（メタデータ） (2022-06-23T17:19:29Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。 また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。 木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2022-01-25T17:37:34Z)
• Modularity in Reinforcement Learning via Algorithmic Independence in Credit Assignment [79.5678820246642]
  提案手法は, 事前決定の順序に対して, スパース変化のみを必要とする伝達問題に対して, 政策段階の手法よりも, より標本効率が高いことを示す。 我々は最近提案された社会的意思決定の枠組みをマルコフ決定プロセスよりもよりきめ細かい形式主義として一般化する。
  論文  参考訳（メタデータ） (2021-06-28T21:29:13Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。