論文の概要: 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は効率的な刈り出しのための新しい解析的境界を持つため、ブランチは速度とスパーシティの最適化の両方を提供する。 他のメソッドとは異なり、非バイナリ機能も扱う。 理論的解析は、既存の手法と比較して複雑さが低いことを示し、実験的な結果は、分岐が速度、反復、最適性において最先端であることを示す。

関連論文リスト

• Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound [1.3654846342364308]
  与えられたサイズ制限内でのトレーニング性能を最大化する最適な分類木はNPハードであり、実際にはほとんどの最先端手法は、深さ3の最適木を計算できない。 本稿では,分岐とバウンドを持つ動的プログラミングを用いて,連続的な特徴データに基づいて木を直接最適化する新しいアルゴリズムを提案する。 実験により、これらの手法は、最先端の最適手法よりも1桁以上の実行時間を改善するとともに、グレディよりもテスト精度を5%向上することを示した。
  論文  参考訳（メタデータ） (2025-01-14T07:46:33Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• 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)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• 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)

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

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