論文の概要: A Generic Complete Anytime Beam Search for Optimal Decision Tree

• arxiv url: http://arxiv.org/abs/2508.06064v1
• Date: Fri, 08 Aug 2025 06:53:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:06.108165
• Title: A Generic Complete Anytime Beam Search for Optimal Decision Tree
• Title（参考訳）: 最適決定木のための総称完全任意のビーム探索
• Authors: Harold Silvère Kiossou, Siegfried Nijssen, Pierre Schaus,
• Abstract要約: CA-DL8.5は汎用的で完全かつ任意のビーム探索アルゴリズムである。 LDS-DL8.5とTopk-DL8.5を一般化する。 他のCA-DL8.5とBlossomアルゴリズムよりも優れたパフォーマンスを提供する。
• 参考スコア（独自算出の注目度）: 8.545202841051582
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding an optimal decision tree that minimizes classification error is known to be NP-hard. While exact algorithms based on MILP, CP, SAT, or dynamic programming guarantee optimality, they often suffer from poor anytime behavior -- meaning they struggle to find high-quality decision trees quickly when the search is stopped before completion -- due to unbalanced search space exploration. To address this, several anytime extensions of exact methods have been proposed, such as LDS-DL8.5, Top-k-DL8.5, and Blossom, but they have not been systematically compared, making it difficult to assess their relative effectiveness. In this paper, we propose CA-DL8.5, a generic, complete, and anytime beam search algorithm that extends the DL8.5 framework and unifies some existing anytime strategies. In particular, CA-DL8.5 generalizes previous approaches LDS-DL8.5 and Top-k-DL8.5, by allowing the integration of various heuristics and relaxation mechanisms through a modular design. The algorithm reuses DL8.5's efficient branch-and-bound pruning and trie-based caching, combined with a restart-based beam search that gradually relaxes pruning criteria to improve solution quality over time. Our contributions are twofold: (1) We introduce this new generic framework for exact and anytime decision tree learning, enabling the incorporation of diverse heuristics and search strategies; (2) We conduct a rigorous empirical comparison of several instantiations of CA-DL8.5 -- based on Purity, Gain, Discrepancy, and Top-k heuristics -- using an anytime evaluation metric called the primal gap integral. Experimental results on standard classification benchmarks show that CA-DL8.5 using LDS (limited discrepancy) consistently provides the best anytime performance, outperforming both other CA-DL8.5 variants and the Blossom algorithm while maintaining completeness and optimality guarantees.
• Abstract（参考訳）: 分類誤差を最小限に抑える最適な決定木を見つけることはNPハードであることが知られている。 MILP, CP, SAT, 動的プログラミングに基づく正確なアルゴリズムは最適性を保証するが、しばしば不適切な振る舞いに悩まされる。 これを解決するために、LSD-DL8.5、Top-k-DL8.5、Blossomなどの正確な方法の拡張が提案されているが、体系的に比較されていないため、相対的な効果を評価することは困難である。 本稿では,CA-DL8.5を提案する。CA-DL8.5は汎用的で完全かつ任意のビーム探索アルゴリズムであり,DL8.5フレームワークを拡張し,既存の時制戦略を統一する。 特にCA-DL8.5は、モジュラー設計による様々なヒューリスティックと緩和機構の統合を可能にすることで、以前のアプローチ LDS-DL8.5 と Top-k-DL8.5 を一般化している。 このアルゴリズムは、DL8.5の効率的な分岐とバウンドのプルーニングとトリエベースのキャッシュを再利用し、再起動ベースのビームサーチと組み合わせることで、プルーニング基準を徐々に緩和し、ソリューションの品質を時間とともに改善する。 我々は,(1) 多様なヒューリスティックと探索戦略を組み込むことが可能な,正確かついつでも決定木学習のための新しい汎用フレームワークを導入する; (2) パーティ,ゲイン,離散性,トップkヒューリスティックスに基づくCA-DL8.5のいくつかのインスタンス化に関する厳密な実証的な比較を行う。 標準分類ベンチマークによる実験結果によると、LCS(限定的な不一致)を使用したCA-DL8.5は、完全性と最適性の保証を維持しつつ、他のCA-DL8.5変種とBlossomアルゴリズムよりも優れた最高のパフォーマンスを提供する。

関連論文リスト

• WCDT: Systematic WCET Optimization for Decision Tree Implementations [4.95559363788634]
  安全な操作を確保するためには、機械学習モデルの最悪の実行時間(WCET)が必要である。 決定木実装のWCET最適化のための体系的アプローチを開発する。 我々は,サロゲートモデルとWCET最適化アルゴリズムの両方を実験的に評価した。
  論文  参考訳（メタデータ） (2025-01-29T06:01:39Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Less is KEN: a Universal and Simple Non-Parametric Pruning Algorithm for Large Language Models [1.5807079236265718]
  KENはカーネル密度推定(KDE)に基づく単純で普遍的で非構造化プルーニングアルゴリズムである Kenは、最適化されたトランスフォーマーを構築することを目的としており、最も重要なパラメータを選択的に保存し、他のパラメータをトレーニング前の状態に復元する。 Kenは、元の未実行バージョンと同等かそれ以上のパフォーマンスを達成し、パラメータの最小25%の削減を実現している。
  論文  参考訳（メタデータ） (2024-02-05T16:11:43Z)
• bsnsing: A decision tree induction method based on recursive optimal boolean rule composition [2.28438857884398]
  本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。 商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
  論文  参考訳（メタデータ） (2022-05-30T17:13:57Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Stochastic Optimization Forests [60.523606291705214]
  標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。 概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
  論文  参考訳（メタデータ） (2020-08-17T16:56:06Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)

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

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