論文の概要: An improved column-generation-based matheuristic for learning classification trees

• arxiv url: http://arxiv.org/abs/2308.11477v2
• Date: Mon, 22 Jan 2024 21:06:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-24 19:33:05.561471
• Title: An improved column-generation-based matheuristic for learning classification trees
• Title（参考訳）: カラムジェネレーションに基づく分類木学習のための数学的改良
• Authors: Krunal Kishor Patel, Guy Desaulniers, Andrea Lodi
• Abstract要約: 決定木は機械学習(ML)における分類問題の解法として高度に解釈可能なモデルである 決定木を訓練するための標準的なMLアルゴリズムは高速だが、精度の点で最適木を生成する。 citefirat 2020column氏は、意思決定木を学習するためのカラムジェネレーションベースのアプローチを提案した。
• 参考スコア（独自算出の注目度）: 9.07661731728456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision trees are highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision trees are fast but generate suboptimal trees in terms of accuracy. Other discrete optimization models in the literature address the optimality problem but only work well on relatively small datasets. \cite{firat2020column} proposed a column-generation-based heuristic approach for learning decision trees. This approach improves scalability and can work with large datasets. In this paper, we describe improvements to this column generation approach. First, we modify the subproblem model to significantly reduce the number of subproblems in multiclass classification instances. Next, we show that the data-dependent constraints in the master problem are implied, and use them as cutting planes. Furthermore, we describe a separation model to generate data points for which the linear programming relaxation solution violates their corresponding constraints. We conclude by presenting computational results that show that these modifications result in better scalability.
• Abstract（参考訳）: 決定木は機械学習(ML)の分類問題を解くための非常に解釈可能なモデルである。 決定木を訓練するための標準的なMLアルゴリズムは高速だが、精度の点で最適木を生成する。 論文の他の離散最適化モデルは最適性問題に対処するが、比較的小さなデータセットでのみうまく機能する。 \cite{firat2020column} は列生成に基づく決定木学習のためのヒューリスティックアプローチを提案した。 このアプローチはスケーラビリティを改善し、大規模なデータセットで動作する。 本稿では,このカラム生成手法の改良について述べる。 まず、サブプロブレムモデルを変更し、マルチクラス分類インスタンスにおけるサブプロブレムの数を大幅に削減する。 次に,マスタ問題におけるデータ依存制約が含意していることを示し,それらを切断平面として用いる。 さらに,線形計画緩和解が対応する制約に違反するデータポイントを生成するための分離モデルについて述べる。 これらの修正によってスケーラビリティが向上することを示す計算結果を提示して結論付ける。

関連論文リスト

• Efficient Optimization Algorithms for Linear Adversarial Training [9.933836677441684]
  逆行訓練は摂動に対して堅牢なモデルを学ぶのに使える。 本稿では,線形モデルの対数学習のための最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-16T15:41:08Z)
• Optimal Sparse Regression Trees [24.03491277969824]
  本研究は,確率的最適スパース回帰木の構築に対する動的プログラミングとバウンドのアプローチを提案する。 ラベル集合上の1次元におけるk平均クラスタリングアルゴリズムの最適解に基づいて、新しい下界を利用する。
  論文  参考訳（メタデータ） (2022-11-28T00:43:21Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  本稿では,値関数近似を用いたオフラインRLにおけるモデル選択の問題について検討する。 対数係数まで最小値の速度-最適不等式を実現するオフラインRLの最初のモデル選択アルゴリズムを提案する。 そこで本研究では,優れたモデルクラスを確実に選択できることを示す数値シミュレーションを行った。
  論文  参考訳（メタデータ） (2022-11-03T17:32:34Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs [52.52570805621925]
  本研究では,高階グラフ畳み込みからの効率的な学習と,ノード分類のための隣接行列から直接学習する。 得られたモデルが新しいグラフと残留スケーリングパラメータをもたらすことを示す。 提案手法は,非親和性パラメータのノード分類における精度の向上を実証する。
  論文  参考訳（メタデータ） (2022-09-12T04:46:55Z)
• 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)
• A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds [9.546094657606178]
  本研究では,異なる回帰モデルに対する決定木の一般化性能について検討する。 これにより、アルゴリズムが新しいデータに一般化するために(あるいは作らない)仮定する帰納的バイアスが引き起こされる。 スパース加法モデルに適合する大規模な決定木アルゴリズムに対して、シャープな2乗誤差一般化を低い境界で証明する。
  論文  参考訳（メタデータ） (2021-10-18T21:22:40Z)
• Data Summarization via Bilevel Optimization [48.89977988203108]
  シンプルだが強力なアプローチは、小さなサブセットのデータを操作することだ。 本研究では,コアセット選択を基数制約付き双レベル最適化問題として定式化する汎用コアセットフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-09-26T09:08:38Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  半教師付き学習における簡単なメタ学習アルゴリズムを提案する。 その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
  論文  参考訳（メタデータ） (2020-07-08T08:48:56Z)

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

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