論文の概要: How Smart Guessing Strategies Can Yield Massive Scalability Improvements for Sparse Decision Tree Optimization

• arxiv url: http://arxiv.org/abs/2112.00798v1
• Date: Wed, 1 Dec 2021 19:39:28 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-03 14:39:58.510704
• Title: How Smart Guessing Strategies Can Yield Massive Scalability Improvements for Sparse Decision Tree Optimization
• Title（参考訳）: スマートガイダンス戦略がスパース決定木最適化のための大規模スケーラビリティ向上を実現するには
• Authors: Hayden McTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, Margo Seltzer
• Abstract要約: 現在のアルゴリズムは、いくつかの実世界のデータセットに対して最適な木またはほぼ最適な木を見つけるために、しばしば非現実的な時間とメモリを必要とする。 本稿では,任意の分岐とバウンダリに基づく決定木アルゴリズムに適用可能なスマート推測手法を用いてこの問題に対処する。 提案手法では, 連続的特徴量, 木の大きさ, 最適決定木に対する誤差の下位境界を推定できる。
• 参考スコア（独自算出の注目度）: 18.294573939199438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse decision tree optimization has been one of the most fundamental problems in AI since its inception and is a challenge at the core of interpretable machine learning. Sparse decision tree optimization is computationally hard, and despite steady effort since the 1960's, breakthroughs have only been made on the problem within the past few years, primarily on the problem of finding optimal sparse decision trees. However, current state-of-the-art algorithms often require impractical amounts of computation time and memory to find optimal or near-optimal trees for some real-world datasets, particularly those having several continuous-valued features. Given that the search spaces of these decision tree optimization problems are massive, can we practically hope to find a sparse decision tree that competes in accuracy with a black box machine learning model? We address this problem via smart guessing strategies that can be applied to any optimal branch-and-bound-based decision tree algorithm. We show that by using these guesses, we can reduce the run time by multiple orders of magnitude, while providing bounds on how far the resulting trees can deviate from the black box's accuracy and expressive power. Our approach enables guesses about how to bin continuous features, the size of the tree, and lower bounds on the error for the optimal decision tree. Our experiments show that in many cases we can rapidly construct sparse decision trees that match the accuracy of black box models. To summarize: when you are having trouble optimizing, just guess.
• Abstract（参考訳）: スパース決定ツリーの最適化は、AIの誕生以来、最も根本的な問題の1つであり、解釈可能な機械学習のコアにおける課題である。 スパース決定木最適化は計算的に困難であり、1960年代以降の着実な努力にもかかわらず、この問題に対するブレークスルーは、主に最適なスパース決定木を見つけることの課題である。 しかし、現在の最先端のアルゴリズムは、現実のデータセット、特にいくつかの連続的な値を持つデータセットの最適あるいは至近のツリーを見つけるために、実用的でない量の計算時間とメモリを必要とすることが多い。 これらの決定木最適化問題の探索空間が巨大であることを踏まえると、ブラックボックス機械学習モデルと精度で競合するスパース決定木を実際に見つけることができるだろうか? 本稿では,任意の分岐・境界決定木アルゴリズムに適用可能なスマート推測手法を用いてこの問題に対処する。 これらの推定値を用いることで,生成した木がブラックボックスの精度と表現力からどの程度逸脱するかのバウンダリを提供しながら,実行時間を桁違いに削減できることを示す。 提案手法では, 連続的特徴量, 木の大きさ, 最適決定木に対する誤差の下位境界を推定できる。 実験結果から,ブラックボックスモデルの精度に合致したスパース決定木を,多くの場合,迅速に構築できることがわかった。 まとめると:最適化に苦労しているとき、推測するだけです。

関連論文リスト

• Can a Single Tree Outperform an Entire Forest? [5.448070998907116]
  一般的な考え方は、単一の決定木は、テスト精度において古典的なランダムな森林を過小評価する。 本研究では,斜め回帰木の試験精度を大幅に向上させることで,このような考え方に挑戦する。 本手法は,木習熟を非制約最適化タスクとして再編成する。
  論文  参考訳（メタデータ） (2024-11-26T00:18:18Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。 我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
  論文  参考訳（メタデータ） (2020-12-29T18:05:05Z)
• 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)
• ENTMOOT: A Framework for Optimization over Ensemble Tree Models [57.98561336670884]
  ENTMOOTは、ツリーモデルをより大きな最適化問題に統合するためのフレームワークである。 ENTMOOTは、ツリーモデルの意思決定とブラックボックス最適化への単純な統合を可能にしていることを示す。
  論文  参考訳（メタデータ） (2020-03-10T14:34:07Z)
• Optimal Sparse Decision Trees [25.043477914272046]
  この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。 このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。 我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
  論文  参考訳（メタデータ） (2019-04-29T17:56:34Z)

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

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