論文の概要: Support Vector Machines with the Hard-Margin Loss: Optimal Training via Combinatorial Benders' Cuts

• arxiv url: http://arxiv.org/abs/2207.07690v1
• Date: Fri, 15 Jul 2022 18:21:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-19 18:40:15.456030
• Title: Support Vector Machines with the Hard-Margin Loss: Optimal Training via Combinatorial Benders' Cuts
• Title（参考訳）: ハードマージン損失を伴うベクトルマシンのサポート:コンビネーションベンダーによる最適トレーニング
• Authors: \'Italo Santana, Breno Serrano, Maximilian Schiffer, Thibaut Vidal
• Abstract要約: 我々は、グローバルな最適性のために、ハードマージンのSVMモデルをトレーニングする方法を示す。 本稿では,この問題を解くための反復サンプリングと部分分解アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 8.281391209717105
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical hinge-loss support vector machines (SVMs) model is sensitive to outlier observations due to the unboundedness of its loss function. To circumvent this issue, recent studies have focused on non-convex loss functions, such as the hard-margin loss, which associates a constant penalty to any misclassified or within-margin sample. Applying this loss function yields much-needed robustness for critical applications but it also leads to an NP-hard model that makes training difficult, since current exact optimization algorithms show limited scalability, whereas heuristics are not able to find high-quality solutions consistently. Against this background, we propose new integer programming strategies that significantly improve our ability to train the hard-margin SVM model to global optimality. We introduce an iterative sampling and decomposition approach, in which smaller subproblems are used to separate combinatorial Benders' cuts. Those cuts, used within a branch-and-cut algorithm, permit to converge much more quickly towards a global optimum. Through extensive numerical analyses on classical benchmark data sets, our solution algorithm solves, for the first time, 117 new data sets to optimality and achieves a reduction of 50% in the average optimality gap for the hardest datasets of the benchmark.
• Abstract（参考訳）: 古典的ヒンジロス支持ベクトルマシン(SVM)モデルは、損失関数の非有界性に起因する外乱観測に敏感である。 この問題を回避するために、近年の研究は、不等級または中等級のサンプルに一定のペナルティを関連付けるハードマージン損失のような非凸損失関数に焦点を当てている。 この損失関数を適用することは、重要なアプリケーションにとって非常に必要なロバスト性をもたらすが、現在の厳密な最適化アルゴリズムはスケーラビリティに乏しいが、ヒューリスティックスは一貫して高品質なソリューションを見つけることができないため、トレーニングを難しくするnpハードモデルにつながる。 このような背景から,我々はSVMモデルをグローバルな最適性にトレーニングする能力を大幅に向上させる新しい整数プログラミング戦略を提案する。 本稿では,より小さなサブプロブレムを用いてBendersの切断を分離する反復サンプリングと分解手法を提案する。 これらのカットは分岐とカットのアルゴリズムで使われ、グローバルな最適化に向けてより迅速に収束することができる。 従来のベンチマークデータセットに対する広範囲な数値解析により,本アルゴリズムは117個の新しいデータセットを初めて最適に解き,ベンチマークの最も難しいデータセットの平均最適ギャップを50%削減した。

関連論文リスト

• Unified Framework for Neural Network Compression via Decomposition and Optimal Rank Selection [3.3454373538792552]
  本稿では,決定された階数制約内での複合圧縮損失を利用して,分解と最適な階数選択を行う統一的な枠組みを提案する。 提案手法は連続空間におけるランクの自動探索を含み,トレーニングデータを用いることなく最適なランク設定を効率的に同定する。 様々なベンチマークデータセットを用いて,包括的解析により本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2024-09-05T14:15:54Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Robust support vector machines via conic optimization [0.8594140167290099]
  本研究では,不確実性に頑健な凸計算機の問題点を考察する。 提案した推定器は, 降圧器の存在下では, 降圧器が無く, より良くなることにより, SVM と競合することを示す。
  論文  参考訳（メタデータ） (2024-02-02T05:42:50Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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