論文の概要: Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees

• arxiv url: http://arxiv.org/abs/2406.02175v3
• Date: Fri, 04 Oct 2024 15:44:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-07 15:06:45.924743
• Title: Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees
• Title（参考訳）: Branches: 最適な決定木のための高速な動的プログラミングとブランチ&バウンドアルゴリズム
• Authors: Ayman Chaouki, Jesse Read, Albert Bifet,
• Abstract要約: 決定木(DT)学習は、解釈可能な機械学習の基本的な問題である。 両アプローチの長所を組み合わせた新しいアルゴリズムであるブランチを導入する。 DPとB&Bは効率的な刈り出しのための新しい解析的境界を持つため、ブランチは速度とスパーシティの最適化の両方を提供する。
• 参考スコア（独自算出の注目度）: 12.403737756721467
• License:
• Abstract: Decision Tree (DT) Learning is a fundamental problem in Interpretable Machine Learning, yet it poses a formidable optimisation challenge. Despite numerous efforts dating back to the early 1990's, practical algorithms have only recently emerged, primarily leveraging Dynamic Programming (DP) and Branch & Bound (B&B) techniques. These methods fall into two categories: algorithms like DL8.5, MurTree and STreeD utilise an efficient DP strategy but lack effective bounds for pruning the search space; while algorithms like OSDT and GOSDT employ more efficient pruning bounds but at the expense of a less refined DP strategy. We introduce Branches, a new algorithm that combines the strengths of both approaches. Using DP and B&B with a novel analytical bound for efficient pruning, Branches offers both speed and sparsity optimisation. Unlike other methods, it also handles non-binary features. Theoretical analysis shows its lower complexity compared to existing methods, and empirical results confirm that Branches outperforms the state-of-the-art in speed, iterations, and optimality.
• Abstract（参考訳）: 決定木(DT) 学習は、解釈可能な機械学習の基本的な問題であるが、恐ろしいほど最適化の課題をもたらす。 1990年代初期までさかのぼる多くの努力にもかかわらず、実用的なアルゴリズムが登場したのはごく最近であり、主に動的プログラミング(DP)とブランチ&バウンド(B&B)の技術を活用している。 DL8.5、MurTree、STreeDのようなアルゴリズムは効率的なDP戦略を利用するが、検索空間を刈り取るための効果的な境界がない。 両アプローチの長所を組み合わせた新しいアルゴリズムであるブランチを導入する。 DPとB&Bは効率的な刈り出しのための新しい解析的境界を持つため、ブランチは速度とスパーシティの最適化の両方を提供する。 他のメソッドとは異なり、非バイナリ機能も扱う。 理論的解析は、既存の手法と比較して複雑さが低いことを示し、実験的な結果は、分岐が速度、反復、最適性において最先端であることを示す。

関連論文リスト

• 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)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization [1.471992435706872]
  CluSPT(Clustered Shortest-Path Tree Problem)は、実生活における様々な最適化問題において重要な役割を果たしている。 近年、CluSPTを扱うためにMFEA(Multifactorial Evolutionary Algorithm)が導入されている。 本稿では,MFEAに基づくCluSPTの解法について述べる。
  論文  参考訳（メタデータ） (2021-02-12T13:36:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)
• Optimal Sparse Decision Trees [25.043477914272046]
  この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。 このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。 我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
  論文  参考訳（メタデータ） (2019-04-29T17:56:34Z)

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

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