論文の概要: Strong Optimal Classification Trees
- arxiv url: http://arxiv.org/abs/2103.15965v1
- Date: Mon, 29 Mar 2021 21:40:58 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-31 14:37:09.045680
- Title: Strong Optimal Classification Trees
- Title（参考訳）: 強最適分類木
- Authors: Sina Aghaei, Andr\'es G\'omez, Phebe Vayanos
- Abstract要約: 決定木は最も人気のある機械学習モデルの一つであり、収益管理から医療まで、アプリケーションで日常的に使われている。
最適二分分類木を学習するための直感的なフローベースMIO定式化を提案する。
当社の提案手法は、最新のMIOベースの技術よりも31倍速く、サンプル性能を最大8%向上させます。
- 参考スコア（独自算出の注目度）: 10.243908145832393
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision trees are among the most popular machine learning models and are
used routinely in applications ranging from revenue management and medicine to
bioinformatics. In this paper, we consider the problem of learning optimal
binary classification trees. Literature on the topic has burgeoned in recent
years, motivated both by the empirical suboptimality of heuristic approaches
and the tremendous improvements in mixed-integer optimization (MIO) technology.
Yet, existing MIO-based approaches from the literature do not leverage the
power of MIO to its full extent: they rely on weak formulations, resulting in
slow convergence and large optimality gaps. To fill this gap in the literature,
we propose an intuitive flow-based MIO formulation for learning optimal binary
classification trees. Our formulation can accommodate side constraints to
enable the design of interpretable and fair decision trees. Moreover, we show
that our formulation has a stronger linear optimization relaxation than
existing methods. We exploit the decomposable structure of our formulation and
max-flow/min-cut duality to derive a Benders' decomposition method to speed-up
computation. We propose a tailored procedure for solving each decomposed
subproblem that provably generates facets of the feasible set of the MIO as
constraints to add to the main problem. We conduct extensive computational
experiments on standard benchmark datasets on which we show that our proposed
approaches are 31 times faster than state-of-the art MIO-based techniques and
improve out of sample performance by up to 8%.
- Abstract（参考訳）: 決定木は最も人気のある機械学習モデルの一つであり、収益管理や医療、バイオインフォマティクスといった応用で日常的に使われている。
本稿では,最適二分分類木を学習する問題を考える。
この話題に関する文献は、ヒューリスティックアプローチの経験的部分最適化性と、mio(mixed-integer optimization)テクノロジの大幅な改善の両方に動機づけられて、近年急増している。
しかし、文献からの既存のMIOベースのアプローチは、MIOのパワーを最大限に活用していない。
本稿では,このギャップを埋めるために,最適二分分類木を学習するための直感的なフローベースのmio定式化を提案する。
我々の定式化は、解釈可能かつ公正な決定木の設計を可能にするために、側面制約を満たすことができる。
さらに,我々の定式化は既存手法よりも強い線形最適化緩和を有することを示す。
計算速度を上げるために,本定式化とmax-flow/min-cut双対性を用いてベンダー分解法を導出する。
本稿では,MIOの実行可能な集合のファセットを,主問題に加える制約として確実に生成する,分解サブプロブレムの解法を提案する。
標準ベンチマークデータセットに関する広範な計算実験を行い,提案手法が最先端のmio技術よりも31倍高速であることを示し,サンプル性能を最大8%向上することを示した。
関連論文リスト
- Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
効率的なレコメンデーションのために,Deep Tree-based Retriever (DTR)を提案する。
DTRは、トレーニングタスクを、同じレベルでツリーノード上のソフトマックスベースのマルチクラス分類としてフレーム化している。
非リーフノードのラベル付けによって引き起こされる準最適性を緩和するため、損失関数の補正法を提案する。
論文 参考訳（メタデータ） (2024-08-21T05:09:53Z) - Advancing Model Pruning via Bi-level Optimization [89.88761425199598]
イテレーティブ・マグニチュード・プルーニング(IMP)は,「入賞券」の発見に成功するプルーニング法である
ワンショットプルーニング法が開発されているが、これらのスキームは通常IMPほど勝利のチケットを見つけることができない。
提案手法は,双線形問題構造を持つBLO問題の特別なクラスであることを示す。
論文 参考訳（メタデータ） (2022-10-08T19:19:29Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。
ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。
我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文 参考訳（メタデータ） (2022-07-02T16:59:37Z) - 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) - Mixed integer linear optimization formulations for learning optimal
binary classification trees [0.0]
最適二分分類木を設計するための4つの混合整数線形最適化(MILO)法を提案する。
モデルをスケールする能力を示すために、13の公開データセットで実験を行います。
論文 参考訳（メタデータ） (2022-06-10T03:10:14Z) - bsnsing: A decision tree induction method based on recursive optimal
boolean rule composition [2.28438857884398]
本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。
商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
論文 参考訳（メタデータ） (2022-05-30T17:13:57Z) - Robust Optimal Classification Trees Against Adversarial Examples [5.254093731341154]
本稿では,ユーザが特定した攻撃モデルに対して最適に堅牢な決定木を訓練する手法の集合を提案する。
逆学習において生じるmin-max最適化問題は、単一最小化定式化を用いて解くことができることを示す。
また,両部マッチングを用いた任意のモデルに対して,上界の対角精度を決定する手法を提案する。
論文 参考訳（メタデータ） (2021-09-08T18:10:49Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳（メタデータ） (2020-08-17T16:56:06Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-06-15T19:00:11Z) - Learning Optimal Classification Trees: Strong Max-Flow Formulations [8.10995244893652]
線形プログラミングの緩和を強くした最適二分分類木に対するフローベースMIP定式化を提案する。
我々はこの構造と最大フロー/最小カットの双対性を利用してベンダーズ分解法を導出する。
論文 参考訳（メタデータ） (2020-02-21T05:58:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。