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

• arxiv url: http://arxiv.org/abs/2301.10369v4
• Date: Wed, 13 Nov 2024 10:35:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-14 19:24:48.175882
• Title: Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms
• Title（参考訳）: 再パラメータ化と補間による厳密なフラクショナル推論 : 木重重みと信念の伝播-アルゴリズム
• Authors: Hamidreza Behjoo, Michael Chertkov,
• Abstract要約: 積として$Z$を表現する方法を示す: Z=Z(lambda)tilde Z(lambda)$ ここで乗法補正である$tilde Z(lambda)$はノードに依存しない確率分布に対する期待値である。 また,画像デノイズ化問題に対する本手法の適用性についても論じる。
• 参考スコア（独自算出の注目度）: 0.4527270266697462
• License:
• Abstract: Computing the partition function, $Z$, of an Ising model over a graph of $N$ \enquote{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 (\enquote{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. Our 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 variation in $\lambda_*$ estimates with an increase in $N$ for instances from a particular random Ising ensemble, where $[2::4]$ indicates a range from $2$ to $4$. We also discuss the applicability of this approach to the problem of image de-noising.
• Abstract（参考訳）: 分割関数を計算し、$N$ \enquote{spins} のグラフ上のイジングモデルの$Z$は、おそらく$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_*)}$のようなユニークな(\enquote{exact})$\lambda_*$が存在することを保証している。 フロフp{wainwright_tree-based_2002} の再パラメトリゼーションアプローチと \citep{chertkov_loop_2006} のループ級数アプローチを一般化し、積として $Z$ を $\forall \lambda:\ Z=Z^{(\lambda)}{\tilde Z}^{(\lambda)}$ で表現する方法を示す。 我々の理論解析は、中規模および大規模の平面およびランダムグラフ上のイジングアンサンブルのモデルによる広範な実験によって補完される。 例えば${\tilde Z}^{(\lambda)}$ with $O(N^{2::4})$ fractional sample and suppress of variation in $\lambda_*$ estimates with a increase of $N$ for instance from a particular random Ising ensemble, where $[2::4]$ indicate a range to $2$ to $4$。 また,画像デノイズ化問題に対する本手法の適用性についても論じる。

関連論文リスト

• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Classical shadows of fermions with particle number symmetry [0.0]
  我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。 ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
  論文  参考訳（メタデータ） (2022-08-18T17:11:12Z)
• 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)
• $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)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• 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)

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

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