論文の概要: Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition

• arxiv url: http://arxiv.org/abs/2410.19131v1
• Date: Thu, 24 Oct 2024 19:57:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-28 13:37:51.585244
• Title: Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition
• Title（参考訳）: ベンダーの分解による因子グラフの後方推定の最大化
• Authors: Harsh Vardhan Dubey, Ji Ah Lee, Patrick Flaherty,
• Abstract要約: 一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。 ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
• 参考スコア（独自算出の注目度）: 0.38233569758620056
• License:
• Abstract: Many Bayesian statistical inference problems come down to computing a maximum a-posteriori (MAP) assignment of latent variables. Yet, standard methods for estimating the MAP assignment do not have a finite time guarantee that the algorithm has converged to a fixed point. Previous research has found that MAP inference can be represented in dual form as a linear programming problem with a non-polynomial number of constraints. A Lagrangian relaxation of the dual yields a statistical inference algorithm as a linear programming problem. However, the decision as to which constraints to remove in the relaxation is often heuristic. We present a method for maximum a-posteriori inference in general Bayesian factor models that sequentially adds constraints to the fully relaxed dual problem using Benders' decomposition. Our method enables the incorporation of expressive integer and logical constraints in clustering problems such as must-link, cannot-link, and a minimum number of whole samples allocated to each cluster. Using this approach, we derive MAP estimation algorithms for the Bayesian Gaussian mixture model and latent Dirichlet allocation. Empirical results show that our method produces a higher optimal posterior value compared to Gibbs sampling and variational Bayes methods for standard data sets and provides certificate of convergence.
• Abstract（参考訳）: 多くのベイズ統計推論問題は、潜伏変数の最大アポテリオリ(MAP)割り当てを計算することに起因している。 しかし、MAP代入を推定する標準的な方法は、アルゴリズムが一定点に収束したことを有限時間保証しない。 従来の研究では、MAP推論は、非ポリノミカルな制約数を持つ線形プログラミング問題として二重形式で表現できることがわかった。 双対のラグランジアン緩和は、線形プログラミング問題として統計的推論アルゴリズムをもたらす。 しかしながら、緩和においてどの制約を取り除くかという決定は、しばしばヒューリスティックである。 本稿では,Benders 分解を用いた完全緩和双対問題に対する制約を逐次追加する一般ベイズ因子モデルにおいて,a-posteriori の最大推定法を提案する。 提案手法では,各クラスタに割り当てる最小限のサンプル数と,マスタリンクやnot-linkなどのクラスタリング問題において,表現型整数と論理的制約を組み込むことが可能である。 このアプローチを用いて,ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。 実験結果から,本手法は標準データセットに対するギブスサンプリング法や変分ベイズ法よりも高い最適後方値を示し,収束証明を提供する。

関連論文リスト

• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• Tightening Discretization-based MILP Models for the Pooling Problem using Upper Bounds on Bilinear Terms [2.6253445491808307]
  線形項による非最適化問題の解法として,離散化に基づく手法が提案されている。 本稿では,離散化に基づくMILPモデルを用いてプール問題の解法を提案する。
  論文  参考訳（メタデータ） (2022-07-08T05:28:59Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Non-approximate Inference for Collective Graphical Models on Path Graphs via Discrete Difference of Convex Algorithm [19.987509826212115]
  本稿では,パスグラフ上の集合的グラフィカルモデル(CGM)に対するMAP推論の新しい手法を提案する。 まず、MAP推論問題を(非線形)最小コストフロー問題として定式化できることを示す。 提案手法では,dcaの重要なサブルーチンを最小凸コストフローアルゴリズムにより効率的に計算できる。
  論文  参考訳（メタデータ） (2021-02-18T07:28:18Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• 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)

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

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