論文の概要: Learning Optimal Classification Trees: Strong Max-Flow Formulations

• arxiv url: http://arxiv.org/abs/2002.09142v2
• Date: Wed, 13 May 2020 02:24:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 01:01:23.242281
• Title: Learning Optimal Classification Trees: Strong Max-Flow Formulations
• Title（参考訳）: 最適分類木を学習する:強いマックスフロー定式化
• Authors: Sina Aghaei, Andres Gomez, Phebe Vayanos
• Abstract要約: 線形プログラミングの緩和を強くした最適二分分類木に対するフローベースMIP定式化を提案する。 我々はこの構造と最大フロー/最小カットの双対性を利用してベンダーズ分解法を導出する。
• 参考スコア（独自算出の注目度）: 8.10995244893652
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 programming (MIP) technology. Yet, existing approaches from the literature do not leverage the power of MIP to its full extent. Indeed, they rely on weak formulations, resulting in slow convergence and large optimality gaps. To fill this gap in the literature, we propose a flow-based MIP formulation for optimal binary classification trees that has a stronger linear programming relaxation. Our formulation presents an attractive decomposable structure. We exploit this structure and max-flow/min-cut duality to derive a Benders' decomposition method, which scales to larger instances. We conduct extensive computational experiments on standard benchmark datasets on which we show that our proposed approaches are 50 times faster than state-of-the art MIP-based techniques and improve out of sample performance up to 13.8%.
• Abstract（参考訳）: 最適な二分分類木を学習する問題を考察する。 この話題に関する文献は近年、ヒューリスティックアプローチの実証的最適性と、混合整数型プログラミング(mip)技術の大幅な改善の両方によって動機づけられつつある。 しかし、文献からの既存のアプローチは、MIPのパワーを最大限に活用していない。 実際、それらは弱い定式化に依存し、緩やかな収束と大きな最適性ギャップをもたらす。 このギャップを埋めるために,より強い線形プログラミング緩和を持つ最適二分分類木に対するフローベースのmip定式化を提案する。 我々の定式化は魅力的な分解可能な構造を示す。 この構造とmax-flow/min-cut双対性を利用して、より大きなインスタンスにスケールするベンダー分解法を導出する。 標準ベンチマークデータセットに関する広範な計算実験を行い,提案手法が最先端mipベース手法の50倍高速であることを示し,サンプル性能を最大13.8%向上させることを示した。

関連論文リスト

• 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)
• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  効率的なレコメンデーションのために,Deep Tree-based Retriever (DTR)を提案する。 DTRは、トレーニングタスクを、同じレベルでツリーノード上のソフトマックスベースのマルチクラス分類としてフレーム化している。 非リーフノードのラベル付けによって引き起こされる準最適性を緩和するため、損失関数の補正法を提案する。
  論文  参考訳（メタデータ） (2024-08-21T05:09:53Z)
• Rolling Lookahead Learning for Optimal Classification Trees [0.0]
  本稿では,木構築における最適手法の展望と,ミオピックアプローチの相対的拡張性を組み合わせた転がりサブツリールックアヘッドアルゴリズムを提案する。 提案手法は1330件のうち808件において最適, 筋電図的アプローチよりも優れ, サンプル外精度を最大で23.6%, 14.4%向上した。
  論文  参考訳（メタデータ） (2023-04-21T09:17:00Z)
• A Mathematical Programming Approach to Optimal Classification Forests [1.0499611180329806]
  本稿では,WOCF(Weighted Optimal Classification Forests)を紹介する。 WOCFは決定木の最適なアンサンブルを利用して、正確かつ解釈可能な分類器を導出する。 全体として、OCFはCART、最適分類木、ランダムフォレスト、XGBoostといった既存のメソッドを補完する。
  論文  参考訳（メタデータ） (2022-11-18T20:33:08Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• 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)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  ROC曲線 (AUC) の下の領域は、不均衡学習やレコメンダシステムといった問題に対するよく知られたランキング基準である。 本稿では,マルチクラスAUCメトリクスを最適化することで,多クラススコアリング関数を学習する問題について検討する。
  論文  参考訳（メタデータ） (2021-07-28T05:18:10Z)
• Strong Optimal Classification Trees [8.10995244893652]
  最適二分分類木を学習するための直感的なフローベースMIO定式化を提案する。 我々の定式化は、解釈可能かつ公平な決定木の設計を可能にするために、サイド制約を満たすことができる。 提案手法は最先端MIO技術よりも29倍高速であることを示す。
  論文  参考訳（メタデータ） (2021-03-29T21:40:58Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。