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

• arxiv url: http://arxiv.org/abs/2406.02175v2
• Date: Fri, 21 Jun 2024 13:45:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-24 19:07:12.507289
• Title: Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees
• Title（参考訳）: Branches: 最適な決定木のための高速な動的プログラミングとブランチ&バウンドアルゴリズム
• Authors: Ayman Chaouki, Jesse Read, Albert Bifet,
• Abstract要約: 決定木学習は、解釈可能な機械学習の基本的な問題である。 実用的なアルゴリズムが登場したのはごく最近で、主に動的プログラミング(DP)とブランチ&バウンド(B&B)の技術を活用している。 本稿では,両パラダイムの強みを統合する新しいアルゴリズムである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. Furthermore, Branches does not necessitate binary features. Theoretical analysis demonstrates that Branches has a lower complexity bound compared to state-of-the-art methods, a claim validated through extensive empirical evaluation. Our results illustrate that Branches outperforms the state of the art in terms of speed and number of iterations while consistently yielding 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)
• How Smart Guessing Strategies Can Yield Massive Scalability Improvements for Sparse Decision Tree Optimization [18.294573939199438]
  現在のアルゴリズムは、いくつかの実世界のデータセットに対して最適な木またはほぼ最適な木を見つけるために、しばしば非現実的な時間とメモリを必要とする。 本稿では,任意の分岐とバウンダリに基づく決定木アルゴリズムに適用可能なスマート推測手法を用いてこの問題に対処する。 提案手法では, 連続的特徴量, 木の大きさ, 最適決定木に対する誤差の下位境界を推定できる。
  論文  参考訳（メタデータ） (2021-12-01T19:39:28Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• 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)

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

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