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

• arxiv url: http://arxiv.org/abs/2404.10099v1
• Date: Mon, 15 Apr 2024 19:15:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-17 20:48:29.933939
• Title: Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach
• Title（参考訳）: 硬度制約による線形SVMの特徴選択--スケーラブルなSDP分解アプローチ
• Authors: Immanuel Bomze, Federico D'Onofrio, Laura Palagi, Bo Peng,
• Abstract要約: 線形支援ベクトルマシン(SVM)における組込み特徴選択問題について検討する。 濃度制約が適用され、完全に説明可能な選択モデルが導かれる。 問題は、濃度制約が存在するためNPハードである。
• 参考スコア（独自算出の注目度）: 3.7876216422538485
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 a fully explainable selection 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 SDP 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 SDPs. Numerical results on classical benchmarking datasets are reported, showing the efficiency and effectiveness of our approach.
• Abstract（参考訳）: 本稿では, 線形サポートベクトルマシン(SVM)の組込み特徴選択問題について検討し, 濃度制約を適用し, 完全に説明可能な選択モデルを提案する。 この問題は、元の線形SVMが多項式時間で解ける問題に等しいにもかかわらず、濃度制約の存在によりNPハードである。 この問題に対処するために、まず2つの混合整数式を導入し、新しいSDP緩和を提案する。 緩和のスパーシティパターンをエクスプロイトし、問題を分解し、より小さな円錐内で等価な緩和を得ることにより、円錐アプローチをスケーラブルにする。 分解緩和を最大限に活用するために,最適解の情報を用いたヒューリスティックスを提案する。 さらに、混合整数分解SDPの列を解くことによって、正確な手順を提案する。 従来のベンチマークデータセットの数値計算結果を報告するとともに,提案手法の有効性と有効性を示した。

関連論文リスト

• 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)
• Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs [16.006893624836554]
  本稿では,VBMLE (Value-Biased Maximum Likelihood Estimation) のレンズによる線形MDPの解法を提案する。 VBMLEは、各時間ステップで1つの最適化問題だけを解決する必要があるため、計算的により効率的である。 後悔する解析では、線形MDPにおけるMLEの一般収束結果が、新しいスーパーマーチンゲール構造を通して提供される。
  論文  参考訳（メタデータ） (2023-10-17T18:27:27Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• 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)
• Bayesian preference elicitation for multiobjective combinatorial optimization [12.96855751244076]
  DM(Decision Maker)のノイズ応答に対処できる新しいインクリメンタルな選好推論手法を提案する。 DMの選好はパラメータが未知の集約関数で表され、その不確実性はパラメータ空間上の密度関数で表されると仮定する。
  論文  参考訳（メタデータ） (2020-07-29T12:28:37Z)
• 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)

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

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