論文の概要: Non-approximate Inference for Collective Graphical Models on Path Graphs via Discrete Difference of Convex Algorithm

• arxiv url: http://arxiv.org/abs/2102.09191v1
• Date: Thu, 18 Feb 2021 07:28:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-19 14:31:05.037823
• Title: Non-approximate Inference for Collective Graphical Models on Path Graphs via Discrete Difference of Convex Algorithm
• Title（参考訳）: 凸アルゴリズムの離散差による経路グラフ上の集合グラフモデルの非近似推論
• Authors: Yasunori Akagi, Naoki Marumo, Hideaki Kim, Takeshi Kurashima and Hiroyuki Toda
• Abstract要約: 本稿では,パスグラフ上の集合的グラフィカルモデル(CGM)に対するMAP推論の新しい手法を提案する。 まず、MAP推論問題を(非線形)最小コストフロー問題として定式化できることを示す。 提案手法では,dcaの重要なサブルーチンを最小凸コストフローアルゴリズムにより効率的に計算できる。
• 参考スコア（独自算出の注目度）: 19.987509826212115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The importance of aggregated count data, which is calculated from the data of multiple individuals, continues to increase. Collective Graphical Model (CGM) is a probabilistic approach to the analysis of aggregated data. One of the most important operations in CGM is maximum a posteriori (MAP) inference of unobserved variables under given observations. Because the MAP inference problem for general CGMs has been shown to be NP-hard, an approach that solves an approximate problem has been proposed. However, this approach has two major drawbacks. First, the quality of the solution deteriorates when the values in the count tables are small, because the approximation becomes inaccurate. Second, since continuous relaxation is applied, the integrality constraints of the output are violated. To resolve these problems, this paper proposes a new method for MAP inference for CGMs on path graphs. First we show that the MAP inference problem can be formulated as a (non-linear) minimum cost flow problem. Then, we apply Difference of Convex Algorithm (DCA), which is a general methodology to minimize a function represented as the sum of a convex function and a concave function. In our algorithm, important subroutines in DCA can be efficiently calculated by minimum convex cost flow algorithms. Experiments show that the proposed method outputs higher quality solutions than the conventional approach.
• Abstract（参考訳）: 複数の個人のデータから算出される集計カウントデータの重要性は、増加し続けている。 collective graphical model (cgm) は、集計データの分析に対する確率的アプローチである。 CGMにおける最も重要な操作の1つは、与えられた観測の下で観測されていない変数の最大後部推定(MAP)である。 一般CGMに対するMAP推論問題はNPハードであることが示されており、近似問題を解くアプローチが提案されている。 しかし、このアプローチには2つの大きな欠点がある。 まず、計算表の値が小さい場合、近似が不正確になるため、ソリューションの品質が低下します。 第二に、連続緩和が適用されるので、出力の積分性制約が破られる。 そこで本論文では,パスグラフ上のCGMに対するMAP推論の新しい手法を提案する。 まず、MAP推論問題を(非線形)最小コストフロー問題として定式化できることを示す。 そこで、凸関数と凹関数の和として表される関数を最小化する一般的な手法である凸アルゴリズムの違い(DCA)を適用します。 提案手法では,dcaの重要なサブルーチンを最小凸コストフローアルゴリズムにより効率的に計算できる。 実験の結果,提案手法は従来の手法よりも高い品質のソリューションを出力することがわかった。

関連論文リスト

• Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
  一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。 ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-10-24T19:57:56Z)
• Flow Priors for Linear Inverse Problems via Iterative Corrupted Trajectory Matching [35.77769905072651]
  本稿では,MAP推定器を効率的に近似する反復アルゴリズムを提案し,様々な線形逆問題の解法を提案する。 本アルゴリズムは,MAPの目的を局所MAP'の目的の和で近似できるという観測によって数学的に正当化される。 我々は,超解法,デブロアリング,インペイント,圧縮センシングなど,様々な線形逆問題に対するアプローチを検証する。
  論文  参考訳（メタデータ） (2024-05-29T06:56:12Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  ガウスのプロセスはデータセットのサイズとともに違法にスケールする。 多くの近似法が開発されており、必然的に近似誤差を導入している。 この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。 本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
  論文  参考訳（メタデータ） (2022-05-30T22:16:25Z)
• Mean Field Approximation for solving QUBO problems [0.0]
  平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。 提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
  論文  参考訳（メタデータ） (2021-06-06T20:35:28Z)
• 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)
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems [2.335152769484957]
  我々は、勾配近似(PG)アプローチに基づく効率的なコンセンサスアルゴリズムの理論解析を導出し、詳述する。 提案アルゴリズムは、異常検出タスクに対する別の特別な畳み込み問題にも適用できる。
  論文  参考訳（メタデータ） (2020-11-19T20:52:48Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)
• Approximate MMAP by Marginal Search [78.50747042819503]
  本稿では,グラフィカルモデルにおける最小値MAPクエリの戦略を提案する。 提案した信頼度尺度は,アルゴリズムが正確であるインスタンスを適切に検出するものである。 十分に高い信頼度を得るために、アルゴリズムは正確な解を与えるか、正確な解からハミング距離が小さい近似を与える。
  論文  参考訳（メタデータ） (2020-02-12T07:41:13Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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