論文の概要: Efficient semidefinite-programming-based inference for binary and multi-class MRFs

• arxiv url: http://arxiv.org/abs/2012.02661v2
• Date: Sat, 1 May 2021 03:44:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-22 20:49:45.649582
• Title: Efficient semidefinite-programming-based inference for binary and multi-class MRFs
• Title（参考訳）: バイナリおよびマルチクラスmrfのための効率的な半定義型プログラミングに基づく推論
• Authors: Chirag Pabbaraju, Po-Wei Wang, J. Zico Kolter
• Abstract要約: 分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
• 参考スコア（独自算出の注目度）: 83.09715052229782
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic inference in pairwise Markov Random Fields (MRFs), i.e. computing the partition function or computing a MAP estimate of the variables, is a foundational problem in probabilistic graphical models. Semidefinite programming relaxations have long been a theoretically powerful tool for analyzing properties of probabilistic inference, but have not been practical owing to the high computational cost of typical solvers for solving the resulting SDPs. In this paper, we propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF by instead exploiting a recently proposed coordinate-descent-based fast semidefinite solver. We also extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver. We show that the method substantially outperforms (both in terms of solution quality and speed) the existing state of the art in approximate inference, on benchmark problems drawn from previous work. We also show that our approach can scale to large MRF domains such as fully-connected pairwise CRF models used in computer vision.
• Abstract（参考訳）: ペアワイズマルコフ確率場(mrfs)における確率的推論、すなわち 分割関数の計算や変数のマップ推定の計算は、確率的グラフィカルモデルにおける基礎的な問題である。 半定義型プログラミング緩和は、確率的推論の性質を分析するための理論的に強力なツールであるが、典型的な解法の計算コストが高いため実用的ではない。 本稿では,最近提案された座標descent-based fast semidefinitesolvrを利用して,分割関数やMAP推定をペアのMDFで効率的に計算する手法を提案する。 また、通常の二元的MDFから完全多クラス設定への半定緩和を拡張し、この解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。 提案手法は, 先行研究から得られたベンチマーク問題に対して, 近似推論による既存の技術状況(ソリューションの品質と速度の両方)を大幅に上回ることを示す。 また,本手法はコンピュータビジョンで使用される完全接続型ペアワイドCRFモデルなど,大規模なMRF領域に拡張可能であることを示す。

関連論文リスト

• Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
  一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。 ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-10-24T19:57:56Z)
• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  最適公正表現はいくつかの有用な構造特性を持つことを示す。 そこで,これらの近似問題は,凹凸プログラミング法により効率的に解けることを示す。
  論文  参考訳（メタデータ） (2024-09-26T08:46:48Z)
• Neural Network Approximators for Marginal MAP in Probabilistic Circuits [11.917134619219079]
  ニューラルネットワークを用いてPC内の(M)MAP推論を近似する手法を提案する。 新しい手法の2つの大きな利点は、自己教師型であり、ニューラルネットワークが学習された後、解を出力するのに線形時間しか必要としない点である。 いくつかのベンチマークデータセットに対する我々の新しいアプローチを評価し、競合する線形時間近似よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-02-06T01:15:06Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds [7.428782604099876]
  Gibbs分布の実践的応用に対する大きな障害は、それらの分割関数を見積もる必要があることである。 本稿では,分割関数を厳密に推定する計算複雑性を低減する手法を提案する。
  論文  参考訳（メタデータ） (2021-11-14T15:42:02Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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