論文の概要: Optimal Sparse Decision Trees

• arxiv url: http://arxiv.org/abs/1904.12847v6
• Date: Tue, 26 Sep 2023 19:10:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-29 03:55:31.602088
• Title: Optimal Sparse Decision Trees
• Title（参考訳）: 最適スパース決定木
• Authors: Xiyang Hu, Cynthia Rudin, Margo Seltzer
• Abstract要約: この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。 このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。 我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
• 参考スコア（独自算出の注目度）: 25.043477914272046
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decision tree algorithms have been among the most popular algorithms for interpretable (transparent) machine learning since the early 1980's. The problem that has plagued decision tree algorithms since their inception is their lack of optimality, or lack of guarantees of closeness to optimality: decision tree algorithms are often greedy or myopic, and sometimes produce unquestionably suboptimal models. Hardness of decision tree optimization is both a theoretical and practical obstacle, and even careful mathematical programming approaches have not been able to solve these problems efficiently. This work introduces the first practical algorithm for optimal decision trees for binary variables. The algorithm is a co-design of analytical bounds that reduce the search space and modern systems techniques, including data structures and a custom bit-vector library. Our experiments highlight advantages in scalability, speed, and proof of optimality. The code is available at https://github.com/xiyanghu/OSDT.
• Abstract（参考訳）: 決定木アルゴリズムは1980年代初頭から、解釈可能な(透明な)機械学習の最も一般的なアルゴリズムである。 決定木アルゴリズムの登場以来、決定木アルゴリズムに悩まされてきた問題は、最適性の欠如、または最適性に近いことの保証の欠如である。 決定木最適化の困難さは理論的かつ実践的な障害であり、注意深い数学的プログラミングアプローチでさえこれらの問題を効率的に解けていない。 本研究は,バイナリ変数の最適決定木に対する最初の実用的なアルゴリズムを提案する。 このアルゴリズムは、検索空間と、データ構造やカスタムビットベクトルライブラリを含む現代的なシステム技術を減らす解析的境界の共設計である。 我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。 コードはhttps://github.com/xiyanghu/OSDT.comで入手できる。

関連論文リスト

• Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees [12.403737756721467]
  決定木学習は、解釈可能な機械学習の基本的な問題である。 実用的なアルゴリズムが登場したのはごく最近で、主に動的プログラミング(DP)とブランチ&バウンド(B&B)の技術を活用している。 本稿では,両パラダイムの強みを統合する新しいアルゴリズムであるBranchesを紹介する。
  論文  参考訳（メタデータ） (2024-06-04T10:11:46Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• 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)
• How Smart Guessing Strategies Can Yield Massive Scalability Improvements for Sparse Decision Tree Optimization [18.294573939199438]
  現在のアルゴリズムは、いくつかの実世界のデータセットに対して最適な木またはほぼ最適な木を見つけるために、しばしば非現実的な時間とメモリを必要とする。 本稿では,任意の分岐とバウンダリに基づく決定木アルゴリズムに適用可能なスマート推測手法を用いてこの問題に対処する。 提案手法では, 連続的特徴量, 木の大きさ, 最適決定木に対する誤差の下位境界を推定できる。
  論文  参考訳（メタデータ） (2021-12-01T19:39:28Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• 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)

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

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