論文の概要: Optimal Sparse Recovery with Decision Stumps
- arxiv url: http://arxiv.org/abs/2303.04301v1
- Date: Wed, 8 Mar 2023 00:43:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 15:25:51.964538
- Title: Optimal Sparse Recovery with Decision Stumps
- Title（参考訳）: 決定スランプを用いた最適スパース回復
- Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Max Springer
- Abstract要約: 木に基づく手法は,多種多様な条件下で,強力な特徴選択特性が得られることを示す。
また,本分析の副産物として,アクティブ機能数$s$が不明な場合でも,回復を確実に保証できることを示す。
- 参考スコア（独自算出の注目度）: 7.24496247221802
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision trees are widely used for their low computational cost, good
predictive performance, and ability to assess the importance of features.
Though often used in practice for feature selection, the theoretical guarantees
of these methods are not well understood. We here obtain a tight finite sample
bound for the feature selection problem in linear regression using single-depth
decision trees. We examine the statistical properties of these "decision
stumps" for the recovery of the $s$ active features from $p$ total features,
where $s \ll p$. Our analysis provides tight sample performance guarantees on
high-dimensional sparse systems which align with the finite sample bound of
$O(s \log p)$ as obtained by Lasso, improving upon previous bounds for both the
median and optimal splitting criteria. Our results extend to the non-linear
regime as well as arbitrary sub-Gaussian distributions, demonstrating that tree
based methods attain strong feature selection properties under a wide variety
of settings and further shedding light on the success of these methods in
practice. As a byproduct of our analysis, we show that we can provably
guarantee recovery even when the number of active features $s$ is unknown. We
further validate our theoretical results and proof methodology using
computational experiments.
- Abstract（参考訳）: 決定木は計算コストの低減、予測性能の向上、特徴の重要性を評価する能力に広く利用されている。
特徴選択によく用いられるが、これらの手法の理論的保証はよく理解されていない。
単層決定木を用いた線形回帰における特徴選択問題に対する厳密な有限標本を得る。
これらの「決定切り株」の統計的性質を$p$の総特徴から$s$のアクティブな特徴を回復するために検討する。
ラッソが取得した有限標本境界の$O(s \log p)$と整合する高次元スパース系において, 試料性能の厳密な保証を行い, 中央値および最適スプリッティング基準の双方について, 以前の限界を改良した。
本研究の結果は,非線型分布や任意の準ガウス分布にまで拡張し,木質法が多種多様な条件下で強い特徴選択性を持つことを示すとともに,実際的な手法の成功に光を当てている。
また,本分析の副産物として,アクティブ機能数$s$が未知であっても,回復を確実に保証できることを示す。
計算実験を用いて理論的結果と検証手法をさらに検証する。
関連論文リスト
- Diverse Randomized Value Functions: A Provably Pessimistic Approach for Offline Reinforcement Learning [11.304227281260896]
Q$-値の後方分布を推定するために,多種多様なランダム化値関数を用いた新しい戦略を導入する。
堅牢な不確実性定量化と、$Q$-値の低い信頼境界(LCB)を推定する。
また、ランダム化値関数内の多様性を強調し、ダイバーシティ正規化手法を導入し、ネットワークの必要数を減らすことで効率を向上させる。
論文 参考訳（メタデータ） (2024-04-09T10:15:18Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳（メタデータ） (2022-10-04T04:43:58Z) - A Huber loss-based super learner with applications to healthcare
expenditures [0.0]
本稿では,2乗誤差損失と絶対損失とを結合した「ロバスト」損失関数であるHuber損失に基づく超学習者を提案する。
提案手法は,ハマーリスクの最適化だけでなく,有限サンプル設定でも直接利用できることを示す。
論文 参考訳（メタデータ） (2022-05-13T19:57:50Z) - Parallel feature selection based on the trace ratio criterion [4.30274561163157]
本研究は,PFSTを用いた並列特徴選択という,新しい並列特徴選択手法を提案する。
提案手法は,Fisher's Discriminant Analysisで用いられるクラス分離性の尺度であるトレース基準を用いて特徴的有用性を評価する。
実験により,本手法は,比較対象の他の手法による時間的差のごく一部で,少数の特徴セットを生成できることが確認された。
論文 参考訳（メタデータ） (2022-03-03T10:50:33Z) - Sparsity-based Feature Selection for Anomalous Subgroup Discovery [5.960402015658508]
異常パターン検出は、正常性からの逸脱が明らかであり、ドメイン間で広く適用可能なインスタンスを特定することを目的としている。
効率的な発見のための原則的かつスケーラブルな特徴選択方法が欠如している点が一般的である。
本稿では,機能駆動オッズ比の分散化によるシステム結果のずれをエンコードする,疎度に基づく自動特徴選択フレームワークを提案する。
論文 参考訳（メタデータ） (2022-01-06T10:56:43Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Provably Efficient Reward-Agnostic Navigation with Linear Value
Iteration [143.43658264904863]
我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。
そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
論文 参考訳（メタデータ） (2020-08-18T04:34:21Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳（メタデータ） (2020-08-17T16:56:06Z) - Slice Sampling for General Completely Random Measures [74.24975039689893]
本稿では, 後続推定のためのマルコフ連鎖モンテカルロアルゴリズムについて, 補助スライス変数を用いてトランケーションレベルを適応的に設定する。
提案アルゴリズムの有効性は、いくつかの一般的な非パラメトリックモデルで評価される。
論文 参考訳（メタデータ） (2020-06-24T17:53:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。