論文の概要: On multivariate randomized classification trees: $l_0$-based sparsity,
VC~dimension and decomposition methods
- arxiv url: http://arxiv.org/abs/2112.05239v1
- Date: Thu, 9 Dec 2021 22:49:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-14 01:51:07.773164
- Title: On multivariate randomized classification trees: $l_0$-based sparsity,
VC~dimension and decomposition methods
- Title（参考訳）: 多変数ランダム化分類木について:$l_0$-based sparsity, vc~dimension and decomposition methods
- Authors: Edoardo Amaldi, Antonio Consolo, Andrea Manno
- Abstract要約: Blanquero et alで提案された非線形連続最適化の定式化について検討する。
我々はまず、$l_0$ノルムの凹凸近似に基づいて、そのような木をスパース化する代替手法を検討する。
より大規模なデータセットを用いた実験により,提案手法は精度を損なうことなく,学習時間を著しく短縮できることが示された。
- 参考スコア（独自算出の注目度）: 0.9346127431927981
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decision trees are widely-used classification and regression models because
of their interpretability and good accuracy. Classical methods such as CART are
based on greedy approaches but a growing attention has recently been devoted to
optimal decision trees. We investigate the nonlinear continuous optimization
formulation proposed in Blanquero et al. (EJOR, vol. 284, 2020; COR, vol. 132,
2021) for (sparse) optimal randomized classification trees. Sparsity is
important not only for feature selection but also to improve interpretability.
We first consider alternative methods to sparsify such trees based on concave
approximations of the $l_{0}$ ``norm". Promising results are obtained on 24
datasets in comparison with $l_1$ and $l_{\infty}$ regularizations. Then, we
derive bounds on the VC dimension of multivariate randomized classification
trees. Finally, since training is computationally challenging for large
datasets, we propose a general decomposition scheme and an efficient version of
it. Experiments on larger datasets show that the proposed decomposition method
is able to significantly reduce the training times without compromising the
accuracy.
- Abstract（参考訳）: 決定木は、解釈可能性と精度の良さから、広く使われている分類と回帰モデルである。
CARTのような古典的な手法は強欲なアプローチに基づいているが、近年は最適な決定木に注目が集まっている。
そこで,Blanquero et al. (EJOR, vol. 284, 2020; COR, vol. 132, 2021) で提案される非線形連続最適化の定式化について検討した。
スパーシリティは機能選択だけでなく、解釈可能性の向上にも重要である。
まず最初に、$l_{0}$ ``norm の凹凸近似に基づいて、そのような木をスカラー化する方法を検討する。
有望な結果は24のデータセットで得られ、$l_1$と$l_{\infty}$正規化と比較される。
次に、多変量ランダム化分類木のVC次元のバウンダリを導出する。
最後に,大規模データセットではトレーニングが計算上困難であるため,汎用的な分解スキームと,その効率的なバージョンを提案する。
より大きなデータセットに対する実験により,提案手法は精度を損なうことなく,トレーニング時間を著しく短縮できることが示された。
関連論文リスト
- Adaptive Split Balancing for Optimal Random Forest [8.916614661563893]
そこで本研究では,新しい適応型分割バランス法を用いて木を構築するランダムフォレストアルゴリズムを提案する。
本手法は,データから木構造を適応的に学習しながら,シンプルでスムーズなシナリオで最適性を実現する。
論文 参考訳（メタデータ） (2024-02-17T09:10:40Z) - An improved column-generation-based matheuristic for learning
classification trees [9.07661731728456]
決定木は機械学習(ML)における分類問題の解法として高度に解釈可能なモデルである
決定木を訓練するための標準的なMLアルゴリズムは高速だが、精度の点で最適木を生成する。
citefirat 2020column氏は、意思決定木を学習するためのカラムジェネレーションベースのアプローチを提案した。
論文 参考訳（メタデータ） (2023-08-22T14:43:36Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - bsnsing: A decision tree induction method based on recursive optimal
boolean rule composition [2.28438857884398]
本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。
商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
論文 参考訳（メタデータ） (2022-05-30T17:13:57Z) - Optimal randomized classification trees [0.0]
分類と回帰木(英: Classification and Regression Trees、CART)は、現代の統計学と機械学習における既成の技術である。
CARTはgreedyプロシージャによって構築され、分割予測変数と関連するしきい値を逐次決定する。
この強欲なアプローチは、木を非常に高速に木に分類するが、その性質上、それらの分類精度は他の最先端の手順と競合しないかもしれない。
論文 参考訳（メタデータ） (2021-10-19T11:41:12Z) - 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) - Solving Long-tailed Recognition with Deep Realistic Taxonomic Classifier [68.38233199030908]
ロングテール認識は、現実世界のシナリオにおける自然な非一様分散データに取り組む。
モダンは人口密度の高いクラスではうまく機能するが、そのパフォーマンスはテールクラスでは著しく低下する。
Deep-RTCは、リアリズムと階層的予測を組み合わせたロングテール問題の新しい解法として提案されている。
論文 参考訳（メタデータ） (2020-07-20T05:57:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。