論文の概要: Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms

• arxiv url: http://arxiv.org/abs/2301.10369v3
• Date: Wed, 31 Jul 2024 16:00:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-01 13:43:16.321261
• Title: Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms
• Title（参考訳）: 再パラメータ化と補間による厳密なフラクショナル推論 : 木重重みと信念の伝播-アルゴリズム
• Authors: Hamidreza Behjoo, Michael Chertkov,
• Abstract要約: 製品として$Z$、$forall lambda: Z=Z(lambda)tilde Z(lambda)$をどう表現するかを示します。 Z=Z(lambda)tilde Z(lambda)$ ここで乗算補正である$tilde Z(lambda)$はノードに依存しない確率分布である。
• 参考スコア（独自算出の注目度）: 0.4527270266697462
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The computational complexity of inference -- required to compute the partition function, $Z$, of an Ising model over a graph of $N$''spins" -- is most likely exponential in $N$. Efficient variational methods, such as Belief Propagation (BP) and Tree Re-Weighted (TRW) algorithms, compute $Z$ approximately by minimizing the respective (BP- or TRW-) free energy. We generalize the variational scheme by building a $\lambda$-fractional interpolation, $Z^{(\lambda)}$, where $\lambda=0$ and $\lambda=1$ correspond to TRW- and BP-approximations, respectively. This fractional scheme -- coined Fractional Belief Propagation (FBP) -- guarantees that in the attractive (ferromagnetic) case $Z^{(TRW)} \geq Z^{(\lambda)} \geq Z^{(BP)}$, and there exists a unique (``exact") $\lambda_*$ such that $Z=Z^{(\lambda_*)}$. Generalizing the re-parametrization approach of \citep{wainwright_tree-based_2002} and the loop series approach of \citep{chertkov_loop_2006}, we show how to express $Z$ as a product, $\forall \lambda:\ Z=Z^{(\lambda)}{\tilde Z}^{(\lambda)}$, where the multiplicative correction, ${\tilde Z}^{(\lambda)}$, is an expectation over a node-independent probability distribution built from node-wise fractional marginals. Our theoretical analysis is complemented by extensive experiments with models from Ising ensembles over planar and random graphs of medium- and large-sizes. The empirical study yields a number of interesting observations, such as the ability to estimate ${\tilde Z}^{(\lambda)}$ with $O(N^{2::4})$ fractional samples and suppression of $\lambda_*$ fluctuations with an increase in $N$ for instances from a particular random Ising ensemble. We also verify and discuss the applicability of this approach to the problem of image de-noising.
• Abstract（参考訳）: N$'spins" グラフ上のイジングモデルのパーティション関数の計算に要する推論の計算複雑性は、おそらく$N$で指数関数である。 Belief Propagation (BP) や Tree Re-Weighted (TRW) アルゴリズムのような効率的な変分法は、各 (BP- または TRW-) 自由エネルギーを最小化することによって、およそ$Z$を計算する。 我々は,$\lambda$-fractional interpolation, $Z^{(\lambda)}$, $\lambda=0$と$\lambda=1$をそれぞれTRW-およびBP-approximationsに対応付けることで,変分スキームを一般化する。 この分数的スキームは、FBP(Fractional Belief Propagation)と呼ばれ、魅力的な(強磁性)ケース$Z^{(TRW)} \geq Z^{(\lambda)} \geq Z^{(BP)}$であり、$Z=Z^{(\lambda_*)}$のようなユニークな(`exact)$\lambda_*$が存在することを保証している。 フロフp{wainwright_tree-based_2002} の再パラメトリゼーションアプローチと \citep{chertkov_loop_2006} のループ級数アプローチを一般化し、積として $Z$ を $\forall \lambda:\ Z=Z^{(\lambda)}{\tilde Z}^{(\lambda)}$ で表現する方法を示す。 我々の理論解析は、中規模および大規模の平面およびランダムグラフ上のIsingアンサンブルのモデルによる広範な実験によって補完される。 経験的研究は、${\tilde Z}^{(\lambda)}$を$O(N^{2::4})$分数サンプルで推定する機能や、特定のランダムなIsingアンサンブルからインスタンスに対して$N$の増加を伴う$\lambda_*$ゆらぎの抑制など、興味深い観測をもたらす。 また,画像デノイズ化問題に対する本手法の適用性についても検証し,検討する。

関連論文リスト

• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Quantum-information theory of a Dirichlet ring with Aharonov-Bohm field [0.0]
  シャノン情報エントロピー$S_rho,gamma$、フィッシャー情報$I_rho,gamma$、オニスクエネルギー$O_rho,gamma$およびR'enyiエントロピー$R_rho,gamma(alpha)$を算出する。
  論文  参考訳（メタデータ） (2022-02-09T19:26:56Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity [3.4984289152418753]
  我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。 我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
  論文  参考訳（メタデータ） (2020-08-16T21:26:46Z)
• Variational Orthogonal Features [29.636483122130027]
  我々は,ある先行して,エビデンスローバウンド(ELBO)のミニバッチ推定を$mathcalO(M3)$コストで計算する機能を定義できることを示す。 我々は,不偏推定器をELBOに,$mathcalO(tildeNT+M2T)$および$mathcalO(tildeNT+MT)$で$T$ Monte Carloサンプルを用いて計算できる固定前カーネルの構成について述べる。
  論文  参考訳（メタデータ） (2020-06-23T17:18:07Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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