論文の概要: Near Optimal Decision Trees in a SPLIT Second
- arxiv url: http://arxiv.org/abs/2502.15988v1
- Date: Fri, 21 Feb 2025 22:57:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-25 15:53:23.986326
- Title: Near Optimal Decision Trees in a SPLIT Second
- Title（参考訳）: SPLIT第2次最適決定木
- Authors: Varun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer,
- Abstract要約: 決定木最適化は、解釈可能な機械学習の基本である。
最近のアプローチでは、分岐と動的プログラミングとのバウンドを使って、グローバルな最適化が見つかる。
我々はSPLITと呼ばれるアルゴリズムのファミリーを導入し、この理想的なバランスを達成するために私たちをかなり前進させます。
- 参考スコア（独自算出の注目度）: 16.99892407039875
- License:
- Abstract: Decision tree optimization is fundamental to interpretable machine learning. The most popular approach is to greedily search for the best feature at every decision point, which is fast but provably suboptimal. Recent approaches find the global optimum using branch and bound with dynamic programming, showing substantial improvements in accuracy and sparsity at great cost to scalability. An ideal solution would have the accuracy of an optimal method and the scalability of a greedy method. We introduce a family of algorithms called SPLIT (SParse Lookahead for Interpretable Trees) that moves us significantly forward in achieving this ideal balance. We demonstrate that not all sub-problems need to be solved to optimality to find high quality trees; greediness suffices near the leaves. Since each depth adds an exponential number of possible trees, this change makes our algorithms orders of magnitude faster than existing optimal methods, with negligible loss in performance. We extend this algorithm to allow scalable computation of sets of near-optimal trees (i.e., the Rashomon set).
- Abstract（参考訳）: 決定木最適化は、解釈可能な機械学習の基本である。
最も一般的なアプローチは、すべての決定ポイントで最高の機能を探すことであり、それは高速だが、証明可能な準最適である。
最近のアプローチでは、分岐と動的プログラミングとのバインドによるグローバルな最適化が見られ、スケーラビリティに多大なコストで精度とスパーシリティが大幅に改善されている。
理想的な解は最適手法の精度とグレディ手法のスケーラビリティである。
我々は,SPLIT(SParse Lookahead for Interpretable Trees)と呼ばれるアルゴリズム群を紹介し,この理想的なバランスを達成するために,私たちを大いに前進させます。
高品質な木を見つけるためには,すべてのサブプロブレムを最適に解決する必要はない。
各深さには指数関数的な木数が増えるため、この変更によりアルゴリズムは既存の最適手法よりも桁違いに高速になり、性能の損失は無視できる。
我々は、このアルゴリズムを拡張して、近似木(すなわちラショウモン集合)の集合のスケーラブルな計算を可能にする。
関連論文リスト
- 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) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。
基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。
我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文 参考訳（メタデータ） (2022-09-27T17:51:31Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳（メタデータ） (2020-08-17T16:56:06Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。