論文の概要: Optimal Decision Trees for Nonlinear Metrics
- arxiv url: http://arxiv.org/abs/2009.06921v2
- Date: Fri, 15 Oct 2021 06:01:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-18 05:22:49.722045
- Title: Optimal Decision Trees for Nonlinear Metrics
- Title（参考訳）: 非線形計量に対する最適決定木
- Authors: Emir Demirovi\'c, Peter J. Stuckey
- Abstract要約: 本稿では,非線形メトリクスに対して最適な木を生成するための新しいアルゴリズムを提案する。
我々の知る限りでは、これは非線形メトリクスに対して証明可能な最適決定木を計算するための最初の方法である。
当社のアプローチは、線形メトリクスの最適化と比較した場合、トレードオフにつながります。
- 参考スコア（独自算出の注目度）: 42.18286681448184
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonlinear metrics, such as the F1-score, Matthews correlation coefficient,
and Fowlkes-Mallows index, are often used to evaluate the performance of
machine learning models, in particular, when facing imbalanced datasets that
contain more samples of one class than the other. Recent optimal decision tree
algorithms have shown remarkable progress in producing trees that are optimal
with respect to linear criteria, such as accuracy, but unfortunately nonlinear
metrics remain a challenge. To address this gap, we propose a novel algorithm
based on bi-objective optimisation, which treats misclassifications of each
binary class as a separate objective. We show that, for a large class of
metrics, the optimal tree lies on the Pareto frontier. Consequently, we obtain
the optimal tree by using our method to generate the set of all nondominated
trees. To the best of our knowledge, this is the first method to compute
provably optimal decision trees for nonlinear metrics. Our approach leads to a
trade-off when compared to optimising linear metrics: the resulting trees may
be more desirable according to the given nonlinear metric at the expense of
higher runtimes. Nevertheless, the experiments illustrate that runtimes are
reasonable for majority of the tested datasets.
- Abstract（参考訳）: f1-score、matthews相関係数、fowlkes-mallows indexのような非線形メトリクスは、機械学習モデルのパフォーマンスを評価するためによく使われ、特に、あるクラスよりも多くのサンプルを含む不均衡データセットに直面する場合である。
最近の最適決定木アルゴリズムは、線形基準(精度など)に関して最適であるが、残念ながら非線形指標は依然として課題である。
このギャップに対処するため,両目的最適化に基づく新しいアルゴリズムを提案し,各バイナリクラスの誤分類を別の目的として扱う。
我々は,多種多様なメトリクスに対して,最適木がパレート辺境にあることを示す。
その結果,本手法を用いて任意の非優占木の集合を生成できる最適木が得られる。
私たちの知る限りでは、これは非線形メトリクスの最適決定木を計算する最初の方法です。
提案手法は, 線形測度を最適化するよりも, 与えられた非線形測度に従って, より高いランタイムを犠牲にして得られる木の方が望ましいというトレードオフをもたらす。
それでも実験は、テストされたデータセットの大部分にとってランタイムが妥当であることを示している。
関連論文リスト
- Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
効率的なレコメンデーションのために,Deep Tree-based Retriever (DTR)を提案する。
DTRは、トレーニングタスクを、同じレベルでツリーノード上のソフトマックスベースのマルチクラス分類としてフレーム化している。
非リーフノードのラベル付けによって引き起こされる準最適性を緩和するため、損失関数の補正法を提案する。
論文 参考訳（メタデータ） (2024-08-21T05:09:53Z) - BooleanOCT: Optimal Classification Trees based on multivariate Boolean
Rules [14.788278997556606]
最適な分類木を導出するために,MIP(Mixed-integer Programming)の定式化を導入する。
提案手法は,F1スコアなどの非線形指標と同様に,精度,バランスの取れた精度,コストに敏感なコストを含む線形メトリクスを統合する。
提案したモデルでは,実世界のデータセットに対して現実的な可解性を示し,数万のサイズの処理を効果的に行う。
論文 参考訳（メタデータ） (2024-01-29T12:58:44Z) - Sample-and-Bound for Non-Convex Optimization [18.30858789210194]
我々はモンテカルロのベンチマークに適応して効率を向上する非次元目的最適化のための新しいサンプリング手法を提案する。
提案する高次ベースラインおよび競合ベンチマークアルゴリズムを積極的に評価する。
論文 参考訳（メタデータ） (2024-01-09T20:45:47Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。
ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。
我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文 参考訳（メタデータ） (2022-07-02T16:59:37Z) - Mixed integer linear optimization formulations for learning optimal
binary classification trees [0.0]
最適二分分類木を設計するための4つの混合整数線形最適化(MILO)法を提案する。
モデルをスケールする能力を示すために、13の公開データセットで実験を行います。
論文 参考訳（メタデータ） (2022-06-10T03:10:14Z) - On multivariate randomized classification trees: $l_0$-based sparsity,
VC~dimension and decomposition methods [0.9346127431927981]
Blanquero et alで提案された非線形連続最適化の定式化について検討する。
我々はまず、$l_0$ノルムの凹凸近似に基づいて、そのような木をスパース化する代替手法を検討する。
より大規模なデータセットを用いた実験により,提案手法は精度を損なうことなく,学習時間を著しく短縮できることが示された。
論文 参考訳（メタデータ） (2021-12-09T22:49:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。