論文の概要: MurTree: Optimal Classification Trees via Dynamic Programming and Search
- arxiv url: http://arxiv.org/abs/2007.12652v4
- Date: Tue, 28 Jun 2022 21:14:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-07 05:57:02.879451
- Title: MurTree: Optimal Classification Trees via Dynamic Programming and Search
- Title（参考訳）: MurTree: 動的プログラミングと検索による最適な分類木
- Authors: Emir Demirovi\'c, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James
Bailey, Christopher Leckie, Kotagiri Ramamohanarao, Peter J. Stuckey
- Abstract要約: 動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
- 参考スコア（独自算出の注目度）: 61.817059565926336
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision tree learning is a widely used approach in machine learning,
favoured in applications that require concise and interpretable models.
Heuristic methods are traditionally used to quickly produce models with
reasonably high accuracy. A commonly criticised point, however, is that the
resulting trees may not necessarily be the best representation of the data in
terms of accuracy and size. In recent years, this motivated the development of
optimal classification tree algorithms that globally optimise the decision tree
in contrast to heuristic methods that perform a sequence of locally optimal
decisions. We follow this line of work and provide a novel algorithm for
learning optimal classification trees based on dynamic programming and search.
Our algorithm supports constraints on the depth of the tree and number of
nodes. The success of our approach is attributed to a series of specialised
techniques that exploit properties unique to classification trees. Whereas
algorithms for optimal classification trees have traditionally been plagued by
high runtimes and limited scalability, we show in a detailed experimental study
that our approach uses only a fraction of the time required by the
state-of-the-art and can handle datasets with tens of thousands of instances,
providing several orders of magnitude improvements and notably contributing
towards the practical realisation of optimal decision trees.
- Abstract（参考訳）: 決定木学習は機械学習において広く使われているアプローチであり、簡潔で解釈可能なモデルを必要とするアプリケーションに好まれる。
ヒューリスティック法は伝統的に、合理的に高い精度で素早くモデルを生産するために使用される。
しかし、一般的に批判されるポイントは、結果のツリーが必ずしも正確さとサイズの観点からデータの最良の表現であるとは限らないことである。
近年では、局所最適決定のシーケンスを実行するヒューリスティックな手法とは対照的に、決定木をグローバルに最適化する最適分類木アルゴリズムの開発が動機となっている。
そこで本研究では,動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
本アルゴリズムは,木の深さとノード数に関する制約をサポートする。
本手法の成功は,分類木に特有の特性を生かした,一連の特殊技術によるものである。
最適な分類木に対するアルゴリズムは、伝統的に高いランタイムと限られたスケーラビリティに悩まされてきたが、我々の手法は最先端技術で要求される時間のごく一部しか使用せず、数万のインスタンスでデータセットを処理可能であることを示し、いくつかの大幅な改善を提供し、特に最適な決定木の実現に寄与している。
関連論文リスト
- Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
効率的なレコメンデーションのために,Deep Tree-based Retriever (DTR)を提案する。
DTRは、トレーニングタスクを、同じレベルでツリーノード上のソフトマックスベースのマルチクラス分類としてフレーム化している。
非リーフノードのラベル付けによって引き起こされる準最適性を緩和するため、損失関数の補正法を提案する。
論文 参考訳（メタデータ） (2024-08-21T05:09:53Z) - LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - Online Learning of Decision Trees with Thompson Sampling [12.403737756721467]
決定木は解釈可能な機械学習のための顕著な予測モデルである。
オンライン環境で最適な決定木を生成できるモンテカルロ木探索アルゴリズムを考案した。
論文 参考訳（メタデータ） (2024-04-09T15:53:02Z) - Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。
我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
論文 参考訳（メタデータ） (2024-02-06T07:40:53Z) - A Mathematical Programming Approach to Optimal Classification Forests [1.0705399532413618]
本稿では,与えられた木を同時に構築する数学的最適化手法を提案する。
分類規則は、森林の樹木の中で最も頻繁に予測される分類をそれぞれの観察に割り当てることによって導かれる。
提案手法は,最先端木分類法と同等あるいは優れた性能を示す。
論文 参考訳（メタデータ） (2022-11-18T20:33:08Z) - 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) - Optimal randomized classification trees [0.0]
分類と回帰木(英: Classification and Regression Trees、CART)は、現代の統計学と機械学習における既成の技術である。
CARTはgreedyプロシージャによって構築され、分割予測変数と関連するしきい値を逐次決定する。
この強欲なアプローチは、木を非常に高速に木に分類するが、その性質上、それらの分類精度は他の最先端の手順と競合しないかもしれない。
論文 参考訳（メタデータ） (2021-10-19T11:41:12Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-06-15T19:00:11Z) - Sparsity in Optimal Randomized Classification Trees [3.441021278275805]
斜め切断に基づく疎い最適分類木を構築するための連続最適化手法を提案する。
空間性、すなわち局所性と大域性は、多面体ノルムの正規化によってモデル化される。
グリーディーアプローチと異なり、我々の分類精度の一部で容易に取引できる能力は、グローバル・スパシティーの獲得に寄与する。
論文 参考訳（メタデータ） (2020-02-21T09:09:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。