論文の概要: Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees
- arxiv url: http://arxiv.org/abs/2406.02175v1
- Date: Tue, 4 Jun 2024 10:11:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-05 16:51:53.726757
- Title: Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees
- Title（参考訳）: Branches: 最適な決定木のための高速な動的プログラミングとブランチ&バウンドアルゴリズム
- Authors: Ayman Chaouki, Jesse Read, Albert Bifet,
- Abstract要約: 決定木学習は、解釈可能な機械学習の基本的な問題である。
両パラダイムの長所を統合する新しいアルゴリズムであるBranchesを紹介する。
- 参考スコア（独自算出の注目度）: 12.403737756721467
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decision Tree Learning is a fundamental problem for Interpretable Machine Learning, yet it poses a formidable optimization 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 breakthroughs led to the development of two distinct approaches. Algorithms like DL8.5 and MurTree operate on the space of nodes (or branches), they are very fast, but do not penalise complex Decision Trees, i.e. they do not solve for sparsity. On the other hand, algorithms like OSDT and GOSDT operate on the space of Decision Trees, they solve for sparsity but at the detriment of speed. In this work, we introduce Branches, a novel algorithm that integrates the strengths of both paradigms. Leveraging DP and B&B, Branches achieves exceptional speed while also solving for sparsity. Central to its efficiency is a novel analytical bound enabling substantial pruning of the search space. Theoretical analysis demonstrates that Branches has lower complexity compared to state-of-the-art methods, a claim validated through extensive empirical evaluation. Our results illustrate that Branches not only greatly outperforms existing approaches in terms of speed and number of iterations, it also consistently yields optimal Decision Trees.
- Abstract（参考訳）: 決定木学習(Decision Tree Learning)は、解釈可能な機械学習の基本的な問題である。
1990年代初期までさかのぼる多くの努力にもかかわらず、実用的なアルゴリズムが登場したのはごく最近であり、主に動的プログラミング(DP)とブランチ&バウンド(B&B)の技術を活用している。
これらのブレークスルーは、2つの異なるアプローチの開発につながった。
DL8.5やMurTreeのようなアルゴリズムはノード(または分岐)の空間で動作し、非常に高速であるが、複雑な決定木をペナライズしない。
一方、OSDT や GOSDT のようなアルゴリズムは、決定木(Decision Trees)の空間で動作し、スパース性は解決するが、速度は低下する。
本稿では,両パラダイムの強みを統合する新しいアルゴリズムであるBranchesを紹介する。
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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。