論文の概要: Scalable Optimal Multiway-Split Decision Trees with Constraints

• arxiv url: http://arxiv.org/abs/2302.06812v1
• Date: Tue, 14 Feb 2023 03:48:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-15 16:29:06.932365
• Title: Scalable Optimal Multiway-Split Decision Trees with Constraints
• Title（参考訳）: 制約付きスケーラブルな最適マルチウェイ分割決定木
• Authors: Shivaram Subramanian, Wei Sun
• Abstract要約: 決定変数の個数が$N$とは独立な経路に基づく新しいMIP定式化を提案する。 本フレームワークは, 規則が短いため, 通常の二分木よりも解釈しやすいマルチウェイスプリットツリーを生成する。 我々は,最大1,008,372個のサンプルを含むデータセットについて,既存のMIPベースの決定木モデルでは数千点を超えるデータに対してうまくスケールしないことを示す。
• 参考スコア（独自算出の注目度）: 3.092691764363848
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: There has been a surge of interest in learning optimal decision trees using mixed-integer programs (MIP) in recent years, as heuristic-based methods do not guarantee optimality and find it challenging to incorporate constraints that are critical for many practical applications. However, existing MIP methods that build on an arc-based formulation do not scale well as the number of binary variables is in the order of $\mathcal{O}(2^dN)$, where $d$ and $N$ refer to the depth of the tree and the size of the dataset. Moreover, they can only handle sample-level constraints and linear metrics. In this paper, we propose a novel path-based MIP formulation where the number of decision variables is independent of $N$. We present a scalable column generation framework to solve the MIP optimally. Our framework produces a multiway-split tree which is more interpretable than the typical binary-split trees due to its shorter rules. Our method can handle nonlinear metrics such as F1 score and incorporate a broader class of constraints. We demonstrate its efficacy with extensive experiments. We present results on datasets containing up to 1,008,372 samples while existing MIP-based decision tree models do not scale well on data beyond a few thousand points. We report superior or competitive results compared to the state-of-art MIP-based methods with up to a 24X reduction in runtime.
• Abstract（参考訳）: 近年、ヒューリスティックな手法は最適性を保証せず、多くの実用アプリケーションにとって重要な制約を組み込むことが難しいため、MIP(Mix-integer Program)を用いた最適決定木学習への関心が高まっている。 しかし、arcベースの定式化に基づいて構築された既存のmipメソッドは、二進変数の数が$\mathcal{o}(2^dn)$の順であり、ここでは$d$と$n$は木の深さとデータセットのサイズを参照する。 さらに、サンプルレベルの制約と線形メトリクスのみを処理できる。 本稿では,決定変数の数が$N$に依存しない経路に基づく新しいMIP定式化を提案する。 MIPを最適に解くために,スケーラブルな列生成フレームワークを提案する。 本フレームワークは, 規則が短いため, 通常の二分木よりも解釈しやすいマルチウェイスプリットツリーを生成する。 提案手法はF1スコアなどの非線形メトリクスを処理でき,より広範な制約を組み込むことができる。 我々はその効果を広範な実験で実証した。 既存のmipベースの決定木モデルでは数千ポイントを超えるデータではスケールしないが,最大1,008,372 個のサンプルを含むデータセットについて結果を示す。 現状のMIPベースの手法と比較して,実行時の最大24倍の削減率を示す。

関連論文リスト

• Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
  教師なしの地上距離学習アプローチが導入されました 木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。 我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$mathcalO(n3)$複雑さを持つことを理論的かつ経験的に実証する。
  論文  参考訳（メタデータ） (2024-11-11T23:21:01Z)
• Constrained Prescriptive Trees via Column Generation [5.273277327802614]
  本稿では、列生成による最適ポリシーを効率的に識別する新しいパスベース混合整数プログラム(MIP)について紹介する。 提案手法の有効性を,合成データと実データの両方に対して広範な実験により実証する。
  論文  参考訳（メタデータ） (2022-07-20T19:30:22Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• 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)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• MLPruning: A Multilevel Structured Pruning Framework for Transformer-based Models [78.45898846056303]
  プルーニングは、大きな自然言語処理モデルに関連するメモリフットプリントと計算コストを削減する効果的な方法である。 我々は,頭部刈り込み,行刈り,ブロックワイズ刈りという3つの異なるレベルの構造化刈り込みを利用する,新しいマルチレベル構造化刈り込みフレームワークを開発した。
  論文  参考訳（メタデータ） (2021-05-30T22:00:44Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• Optimal Decision Trees for Nonlinear Metrics [42.18286681448184]
  本稿では,非線形メトリクスに対して最適な木を生成するための新しいアルゴリズムを提案する。 我々の知る限りでは、これは非線形メトリクスに対して証明可能な最適決定木を計算するための最初の方法である。 当社のアプローチは、線形メトリクスの最適化と比較した場合、トレードオフにつながります。
  論文  参考訳（メタデータ） (2020-09-15T08:30:56Z)
• Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization [6.037383467521294]
  我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。 私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。 実装をツールキットL0BnBでオープンソースにしています。
  論文  参考訳（メタデータ） (2020-04-13T18:45:29Z)

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

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