論文の概要: Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation

• arxiv url: http://arxiv.org/abs/2004.06370v1
• Date: Tue, 14 Apr 2020 09:10:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 10:08:53.400588
• Title: Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation
• Title（参考訳）: LP緩和を用いた組合せ探索による厳密なMAP推論
• Authors: Stefan Haller, Paul Swoboda, Bogdan Savchynskyy
• Abstract要約: 我々は、その最適値に対する下界を自然に定義する緩和の族を提案する。 この族は常にゆるやかな緩和を含んでおり、我々はそれを見つけることができるアルゴリズムを与え、したがって、最初の非緩和NP-ハード問題を解く。 緩和を考えると、元の問題を2つの非重複部分(LP-tight 部分と難しい部分)に分解する。
• 参考スコア（独自算出の注目度）: 19.660527989370646
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the MAP-inference problem for graphical models, which is a valued constraint satisfaction problem defined on real numbers with a natural summation operation. We propose a family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for its optimum. This family always contains a tight relaxation and we give an algorithm able to find it and therefore, solve the initial non-relaxed NP-hard problem. The relaxations we consider decompose the original problem into two non-overlapping parts: an easy LP-tight part and a difficult one. For the latter part a combinatorial solver must be used. As we show in our experiments, in a number of applications the second, difficult part constitutes only a small fraction of the whole problem. This property allows to significantly reduce the computational time of the combinatorial solver and therefore solve problems which were out of reach before.
• Abstract（参考訳）: 本稿では,実数に対して自然和演算で定義される制約満足度問題であるグラフィカルモデルに対するmap-inference問題を考える。 我々は、その最適値の下限を自然に定義する緩和(有名なシェラリ・アダムス階層とは異なる)の族を提案する。 この族は常にゆるやかな緩和を含み、それを見つけることができるアルゴリズムを与え、したがって、最初の非緩和NP-ハード問題を解く。 緩和を考えると、元の問題を2つの非重複部分(LP-tight 部分と難しい部分)に分解する。 後者については、組合せ解法を用いる必要がある。 我々の実験で示したように、いくつかの応用において、第2に難しい部分は問題全体のごく一部にすぎない。 この性質により、組合せソルバの計算時間を著しく短縮することができ、従ってそれまで到達できなかった問題を解くことができる。

関連論文リスト

• Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
  一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。 ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-10-24T19:57:56Z)
• Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
  線形支援ベクトルマシン(SVM)における組込み特徴選択問題について検討する。 濃度制約が適用され、完全に説明可能な選択モデルが導かれる。 問題は、濃度制約が存在するためNPハードである。
  論文  参考訳（メタデータ） (2024-04-15T19:15:32Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
  合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。 本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
  論文  参考訳（メタデータ） (2023-07-14T19:59:18Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
  ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。 バイマックス性能問題を解くための優れた外挿が得られることが示されている。
  論文  参考訳（メタデータ） (2022-01-19T16:14:27Z)
• Adaptive Combinatorial Allocation [77.86290991564829]
  割り当てが繰り返し選択され、戻り値は不明だが学習可能であり、決定には制約が伴う。 我々のモデルは、複雑な制約があっても、両側のマッチングと一方のマッチングをカバーしています。
  論文  参考訳（メタデータ） (2020-11-04T15:02:59Z)
• A H\"olderian backtracking method for min-max and min-min problems [0.0]
  本稿では,凸空間外におけるmin-maxあるいはmin-min問題の解法を提案する。 我々は、学習においてユビキタスな剛性を仮定し、この手法を多くの最適化問題に適用する。
  論文  参考訳（メタデータ） (2020-07-17T08:12:31Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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