論文の概要: Fast Optimization of Weighted Sparse Decision Trees for use in Optimal
Treatment Regimes and Optimal Policy Design
- arxiv url: http://arxiv.org/abs/2210.06825v1
- Date: Thu, 13 Oct 2022 08:16:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-14 14:40:02.962809
- Title: Fast Optimization of Weighted Sparse Decision Trees for use in Optimal
Treatment Regimes and Optimal Policy Design
- Title（参考訳）: 最適処理系および最適政策設計のための重み付きスパース決定木の高速最適化
- Authors: Ali Behrouz, Mathias Lecuyer, Cynthia Rudin, Margo Seltzer
- Abstract要約: 本稿では,効率的な重み付き決定木最適化のための3つのアルゴリズムを提案する。
最初のアプローチでは、重み付き損失関数を直接最適化するが、大規模なデータセットでは計算的に非効率である傾向がある。
第二のアプローチは、より効率的にスケールし、重みを整数値に変換し、データ重複を使って重み付けされた決定木最適化問題を非重み付き(より大きい)問題に変換する。
より大きなデータセットにスケールする第3のアルゴリズムは、各データポイントをその重みに比例した確率でサンプリングするランダム化された手順を使用する。
- 参考スコア（独自算出の注目度）: 16.512942230284576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse decision trees are one of the most common forms of interpretable
models. While recent advances have produced algorithms that fully optimize
sparse decision trees for prediction, that work does not address policy design,
because the algorithms cannot handle weighted data samples. Specifically, they
rely on the discreteness of the loss function, which means that real-valued
weights cannot be directly used. For example, none of the existing techniques
produce policies that incorporate inverse propensity weighting on individual
data points. We present three algorithms for efficient sparse weighted decision
tree optimization. The first approach directly optimizes the weighted loss
function; however, it tends to be computationally inefficient for large
datasets. Our second approach, which scales more efficiently, transforms
weights to integer values and uses data duplication to transform the weighted
decision tree optimization problem into an unweighted (but larger) counterpart.
Our third algorithm, which scales to much larger datasets, uses a randomized
procedure that samples each data point with a probability proportional to its
weight. We present theoretical bounds on the error of the two fast methods and
show experimentally that these methods can be two orders of magnitude faster
than the direct optimization of the weighted loss, without losing significant
accuracy.
- Abstract（参考訳）: スパース決定木は最も一般的な解釈可能なモデルの1つである。
近年の進歩は、予測のためにスパース決定木を完全に最適化するアルゴリズムを生み出しているが、アルゴリズムは重み付きデータサンプルを処理できないため、ポリシー設計には対応していない。
具体的には、損失関数の離散性に依存するため、実数値重みを直接使うことはできない。
例えば、既存の手法のどれも、個々のデータポイントに対する逆相対性重み付けを含むポリシーを作らない。
我々は,効率的な重み付き決定木最適化のための3つのアルゴリズムを提案する。
最初のアプローチでは、重み付き損失関数を直接最適化するが、大規模なデータセットでは計算効率が低下する傾向がある。
より効率的にスケールする2つ目のアプローチは、重みを整数値に変換し、重み付き決定木最適化問題を非重み付き(より大きい)値に変換する。
より大きなデータセットにスケールする第3のアルゴリズムは、各データポイントをその重みに比例する確率でサンプリングするランダム化プロシージャを使用します。
本研究では, 2つの高速手法の誤差に関する理論的境界を示し, 重み付き損失の直接的最適化よりも2桁高速で, 精度を損なうことなく, 実験結果を示す。
関連論文リスト
- A Closed-form Solution for Weight Optimization in Fully-connected Feed-forward Neural Networks [2.1301560294088318]
本研究は、完全連結フィードフォワードニューラルネットワークにおける重み付け最適化問題に対処する。
提案手法は最小二乗法 (LS) を用いて閉形式における重み最適化の解を提供する。
シミュレーションおよび実験結果から,提案手法であるBPLSは,既存の手法と精度で競合するが,実行時間ではかなり上回っていることがわかった。
論文 参考訳（メタデータ） (2024-01-12T17:03:55Z) - Efficient Bi-Level Optimization for Recommendation Denoising [31.968068788022403]
暗黙のフィードバックは高いノイズを持ち、推奨品質を著しく損なう。
両レベルの最適化問題としてデノナイズをモデル化する。
内部最適化は、推奨のための効果的なモデルと重量決定を導くことを目的としている。
重み発生器を用いて重みの保存と1ステップの勾配マッチングに基づく損失を回避し、計算時間を著しく短縮する。
論文 参考訳（メタデータ） (2022-10-19T06:36:21Z) - 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) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Accelerate CNNs from Three Dimensions: A Comprehensive Pruning Framework [40.635566748735386]
ほとんどのニューラルネットワークプルーニング手法は、計算予算を満たすために、ネットワークモデルを1つ(深さ、幅、解像度)に沿ってプルークする。
刈り取りは3次元を包括的に行うべきだと論じる。
提案アルゴリズムは最先端のプルーニングアルゴリズムやニューラルアーキテクチャ検索アルゴリズムを超越している。
論文 参考訳（メタデータ） (2020-10-10T02:30:47Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。
アルゴリズムは最悪の場合でも差分プライバシーを満たす。
現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
論文 参考訳（メタデータ） (2020-07-10T15:46:05Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-06-15T19:00:11Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Optimal Sparse Decision Trees [25.043477914272046]
この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。
このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。
我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
論文 参考訳（メタデータ） (2019-04-29T17:56:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。