論文の概要: Naive Feature Selection: a Nearly Tight Convex Relaxation for Sparse Naive Bayes
- arxiv url: http://arxiv.org/abs/1905.09884v3
- Date: Fri, 10 Jan 2025 14:18:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-15 13:27:07.589380
- Title: Naive Feature Selection: a Nearly Tight Convex Relaxation for Sparse Naive Bayes
- Title(参考訳): Naive Feature Selection: A Nearly Tight Convex Relaxation for Sparse Naive Bayes
- Authors: Armin Askari, Alexandre d'Aspremont, Laurent El Ghaoui,
- Abstract要約: そこで本稿では,特徴選択に使用可能なnaive Bayesのスパースバージョンを提案する。
余剰特徴の余剰寄与が減少するにつれて凸緩和境界が厳密になることを示す。
二項スパースモデルと多項スパースモデルの両方は、問題サイズにおいてほぼ線形な時間で解決可能である。
- 参考スコア(独自算出の注目度): 51.55826927508311
- License:
- Abstract: Due to its linear complexity, naive Bayes classification remains an attractive supervised learning method, especially in very large-scale settings. We propose a sparse version of naive Bayes, which can be used for feature selection. This leads to a combinatorial maximum-likelihood problem, for which we provide an exact solution in the case of binary data, or a bound in the multinomial case. We prove that our convex relaxation bounds becomes tight as the marginal contribution of additional features decreases, using a priori duality gap bounds dervied from the Shapley-Folkman theorem. We show how to produce primal solutions satisfying these bounds. Both binary and multinomial sparse models are solvable in time almost linear in problem size, representing a very small extra relative cost compared to the classical naive Bayes. Numerical experiments on text data show that the naive Bayes feature selection method is as statistically effective as state-of-the-art feature selection methods such as recursive feature elimination, $l_1$-penalized logistic regression and LASSO, while being orders of magnitude faster.
- Abstract(参考訳): 線形複雑性のため、ベイズ分類は、特に大規模環境では魅力的な教師あり学習方法である。
そこで本稿では,特徴選択に使用可能なnaive Bayesのスパースバージョンを提案する。
これは組合せの最大様相問題につながり、二項データの場合や多項データの場合の有界な解を与える。
我々は、シャプリー・フォルクマンの定理から導かれる事前双対性ギャップ境界を用いて、余分な特徴の限界寄与が減少するにつれて凸緩和境界がきつくなることを証明した。
これらの境界を満たす原始解の作り方を示す。
二項スパルスモデルと多項スパルスモデルの両方は、問題サイズのほぼ線形な時間で解決可能であり、古典的なネーブベイズと比較して非常に小さな相対コストを表わす。
テキストデータを用いた数値実験により, ベイズ特徴選択法は再帰的特徴除去, $l_1$-penalized logistic regression, LASSOなどの最先端特徴選択法と同じくらい統計的に有効であり, 桁違いに高速であることがわかった。
関連論文リスト
- Variational empirical Bayes variable selection in high-dimensional logistic regression [2.4032899110671955]
我々は,その新しい,計算効率の良い変分近似を開発した。
そのようなノベルティの1つは、回帰係数自身ではなく、モデル空間上の辺分布に対してこの近似を直接発展させることである。
シミュレーションにおいて,本手法の強い性能を実証し,我々の変分近似が近似している後部分布で満たされる強い選択整合性を引き継ぐことを証明した。
論文 参考訳(メタデータ) (2025-02-14T19:57:13Z) - Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳(メタデータ) (2024-11-21T10:26:17Z) - Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
本稿では, 線形支援ベクトルマシン(SVM)において, 濃度制約が適用された場合の組込み特徴選択問題について検討する。
この問題は、元の線形SVMが時間内に解決可能な問題に等しいにもかかわらず、濃度制約が存在するためNPハードである。
この問題に対処するために、まず2つの混合整数式を導入し、新しい半定緩和法を提案する。
論文 参考訳(メタデータ) (2024-04-15T19:15:32Z) - Optimal partition of feature using Bayesian classifier [0.0]
ネイブベイズでは、特定の特徴は独立特徴と呼ばれ、分類を予測する際に条件付き相関や依存を持たない。
本研究では,Naive Bayes法がもたらす課題を克服する手法として,Comonotone-Independence (CIBer)を提案する。
論文 参考訳(メタデータ) (2023-04-27T21:19:06Z) - Promises and Pitfalls of the Linearized Laplace in Bayesian Optimization [73.80101701431103]
線形化ラプラス近似(LLA)はベイズニューラルネットワークの構築に有効で効率的であることが示されている。
ベイズ最適化におけるLLAの有用性について検討し,その性能と柔軟性を強調した。
論文 参考訳(メタデータ) (2023-04-17T14:23:43Z) - Universal and data-adaptive algorithms for model selection in linear
contextual bandits [52.47796554359261]
モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。
データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。
我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
論文 参考訳(メタデータ) (2021-11-08T18:05:35Z) - Fast Bayesian Variable Selection in Binomial and Negative Binomial
Regression [9.774282306558465]
本稿では,二項回帰および負二項回帰における変数選択のための効率的なMCMCスキームを導入し,ロジスティック回帰を特別な事例として活用する。
実験では、17万の共変量を持つデータを含む、我々のアプローチの有効性を実証する。
論文 参考訳(メタデータ) (2021-06-28T20:54:41Z) - Fair Sparse Regression with Clustering: An Invex Relaxation for a
Combinatorial Problem [32.18449686637963]
我々のモデルにデバイアス/フェアネス制約を組み込むことは、性能に悪影響を及ぼさないことを示す。
また,各サンプルの隠れ属性の正確な値を復元することで,クラスタリング問題を解決する。
論文 参考訳(メタデータ) (2021-02-19T01:46:34Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
論文 参考訳(メタデータ) (2020-07-13T17:39:35Z) - MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
非剛体形状マッチングのための凸混合整数プログラミングの定式化。
効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
論文 参考訳(メタデータ) (2020-02-28T09:54:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。