論文の概要: Efficient semidefinite bounds for multi-label discrete graphical models
- arxiv url: http://arxiv.org/abs/2111.12491v1
- Date: Wed, 24 Nov 2021 13:38:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-25 16:14:12.281179
- Title: Efficient semidefinite bounds for multi-label discrete graphical models
- Title（参考訳）: マルチラベル離散グラフィカルモデルのための効率的な半定義境界
- Authors: Valentin Durante, George Katsirelos, Thomas Schiex
- Abstract要約: このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。
従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
- 参考スコア（独自算出の注目度）: 6.226454551201676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: By concisely representing a joint function of many variables as the
combination of small functions, discrete graphical models (GMs) provide a
powerful framework to analyze stochastic and deterministic systems of
interacting variables. One of the main queries on such models is to identify
the extremum of this joint function. This is known as the Weighted Constraint
Satisfaction Problem (WCSP) on deterministic Cost Function Networks and as
Maximum a Posteriori (MAP) inference on stochastic Markov Random Fields.
Algorithms for approximate WCSP inference typically rely on local consistency
algorithms or belief propagation. These methods are intimately related to
linear programming (LP) relaxations and often coupled with reparametrizations
defined by the dual solution of the associated LP. Since the seminal work of
Goemans and Williamson, it is well understood that convex SDP relaxations can
provide superior guarantees to LP. But the inherent computational cost of
interior point methods has limited their application. The situation has
improved with the introduction of non-convex Burer-Monteiro style methods which
are well suited to handle the SDP relaxation of combinatorial problems with
binary variables (such as MAXCUT, MaxSAT or MAP/Ising). We compute low rank SDP
upper and lower bounds for discrete pairwise graphical models with arbitrary
number of values and arbitrary binary cost functions by extending a
Burer-Monteiro style method based on row-by-row updates. We consider a
traditional dualized constraint approach and a dedicated Block Coordinate
Descent approach which avoids introducing large penalty coefficients to the
formulation. On increasingly hard and dense WCSP/CFN instances, we observe that
the BCD approach can outperform the dualized approach and provide tighter
bounds than local consistencies/convergent message passing approaches.
- Abstract（参考訳）: 多くの変数の結合関数を小さな関数の組み合わせとして簡潔に表現することで、離散グラフィカルモデル(gms)は相互作用変数の確率的および決定論的システムを分析する強力な枠組みを提供する。
そのようなモデルにおける主要なクエリの1つは、このジョイント関数の極小を特定することである。
これは、決定論的コスト関数ネットワークにおける重み付き制約満足問題(WCSP)や、確率的マルコフランダム場に関する最大ポストエリ(MAP)推論として知られている。
近似WCSP推論のアルゴリズムは通常、局所的な一貫性アルゴリズムや信念の伝播に依存する。
これらの手法は線形プログラミング(LP)緩和と密接に関連しており、しばしば関連するLPの双対解によって定義される再パラメータ化と結合する。
Goemans と Williamson のセミナルな業績から、凸 SDP 緩和は LP に優れた保証を与えるとよく理解されている。
しかし、内部点法の本質的な計算コストは応用を制限している。
この状況は、バイナリ変数(MAXCUT、MaxSAT、MAP/Isingなど)との組合せ問題に対するSDP緩和に適した非凸のBurer-Monteiroスタイルの手法の導入によって改善された。
行ごとの更新に基づくBurer-Monteiroスタイルの手法を拡張し,任意の値と任意のバイナリコスト関数を持つ離散的ペアワイズグラフィカルモデルに対する低階SDP上下位境界を計算する。
従来の双対制約アプローチと,定式化に大きめのペナルティ係数を導入することを避ける専用ブロックコーディネートDescentアプローチを考える。
ますますハードで密度の高いWCSP/CFNインスタンスでは、BCDアプローチが双対化アプローチより優れ、局所的なコンバージェント/収束メッセージパッシングアプローチよりも厳密な境界を提供する。
関連論文リスト
- Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。
ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-10-24T19:57:56Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
線形支援ベクトルマシン(SVM)における組込み特徴選択問題について検討する。
濃度制約が適用され、完全に説明可能な選択モデルが導かれる。
問題は、濃度制約が存在するためNPハードである。
論文 参考訳（メタデータ） (2024-04-15T19:15:32Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - Nonconvex Stochastic Bregman Proximal Gradient Method for Nonconvex Composite Problems [9.202586157819693]
非合成対象関数の勾配法は、典型的には微分可能部分のリプシッツ滑らかさに依存する。
非目的の非Lipschitz勾配を扱う近似モデルを提案する。
ステップ選択感度の観点から最適なロバスト性が得られることを示す。
論文 参考訳（メタデータ） (2023-06-26T08:54:46Z) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Consistent Second-Order Conic Integer Programming for Learning Bayesian
Networks [2.7473982588529653]
連続観測データからBNのスパースDAG構造を学習する問題について検討する。
この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。
ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
論文 参考訳（メタデータ） (2020-05-29T00:13:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。