論文の概要: Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach

• arxiv url: http://arxiv.org/abs/2404.10099v2
• Date: Thu, 19 Dec 2024 11:06:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-20 16:51:51.802010
• Title: Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach
• Title（参考訳）: 硬度制約による線形SVMの特徴選択--スケーラブルSDP分解アプローチ
• Authors: Immanuel Bomze, Federico D'Onofrio, Laura Palagi, Bo Peng,
• Abstract要約: 本稿では, 線形支援ベクトルマシン(SVM)において, 濃度制約が適用された場合の組込み特徴選択問題について検討する。 この問題は、元の線形SVMが時間内に解決可能な問題に等しいにもかかわらず、濃度制約が存在するためNPハードである。 この問題に対処するために、まず2つの混合整数式を導入し、新しい半定緩和法を提案する。
• 参考スコア（独自算出の注目度）: 3.7876216422538485
• License:
• Abstract: In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to an interpretable classification model. The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a problem solvable in polynomial time. To handle the hard problem, we first introduce two mixed-integer formulations for which novel semidefinite relaxations are proposed. Exploiting the sparsity pattern of the relaxations, we decompose the problems and obtain equivalent relaxations in a much smaller cone, making the conic approaches scalable. To make the best usage of the decomposed relaxations, we propose heuristics using the information of its optimal solution. Moreover, an exact procedure is proposed by solving a sequence of mixed-integer decomposed semidefinite optimization problems. Numerical results on classical benchmarking datasets are reported, showing the efficiency and effectiveness of our approach.
• Abstract（参考訳）: 本稿では,線形サポートベクトルマシン (SVM) の組込み特徴選択問題について検討する。 この問題は、元の線形SVMが多項式時間で解ける問題に等しいにもかかわらず、濃度制約の存在によりNPハードである。 この問題に対処するために、まず、新しい半定緩和法を提案する2つの混合整数式を導入する。 緩和のスパーシティパターンをエクスプロイトし、問題を分解し、より小さな円錐内で等価な緩和を得ることにより、円錐アプローチをスケーラブルにする。 分解緩和を最大限に活用するために,最適解の情報を用いたヒューリスティックスを提案する。 さらに, 混合整数分解による半定値最適化問題を解くことによって, 正確な手順を提案する。 従来のベンチマークデータセットの数値計算結果を報告するとともに,提案手法の有効性と有効性を示した。

関連論文リスト

• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• Towards Convexity in Anomaly Detection: A New Formulation of SSLM with Unique Optimal Solutions [12.250410918282615]
  Support Vector Description (SVDD) Small and Large Sphere SVM (MvMs) として広く使われている手法における未解決問題 従来の非アプローチでは不可能であることを示す新しいSSLMを導入する。
  論文  参考訳（メタデータ） (2024-10-31T09:42:39Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
  この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。 これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
  論文  参考訳（メタデータ） (2024-02-14T10:48:00Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  連続観測データからBNのスパースDAG構造を学習する問題について検討する。 この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。 ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
  論文  参考訳（メタデータ） (2020-05-29T00:13:15Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  非剛体形状マッチングのための凸混合整数プログラミングの定式化。 効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-28T09:54:06Z)
• Naive Feature Selection: a Nearly Tight Convex Relaxation for Sparse Naive Bayes [51.55826927508311]
  そこで本稿では,特徴選択に使用可能なnaive Bayesのスパースバージョンを提案する。 余剰特徴の余剰寄与が減少するにつれて凸緩和境界が厳密になることを示す。 二項スパースモデルと多項スパースモデルの両方は、問題サイズにおいてほぼ線形な時間で解決可能である。
  論文  参考訳（メタデータ） (2019-05-23T19:30:51Z)

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

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