論文の概要: Exact Fractional Inference via Re-Parametrization & Interpolation
between Tree-Re-Weighted- and Belief Propagation- Algorithms
- arxiv url: http://arxiv.org/abs/2301.10369v1
- Date: Wed, 25 Jan 2023 00:50:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-26 16:04:29.796905
- Title: Exact Fractional Inference via Re-Parametrization & Interpolation
between Tree-Re-Weighted- and Belief Propagation- Algorithms
- Title(参考訳): 木重み付き木と信念伝播アルゴリズムの再パラメータ化と補間による厳密な分数推定
- Authors: Hamidreza Behjoo, Michael Chertkov
- Abstract要約: 分割関数($Z$)を計算するのに必要な推論の努力は、$N$スピンのグラフ上のIsingモデルの$N$の指数関数である可能性が高い。
積として$Z$を表現する方法を示す: Z=Z(lambda)cal Z(lambda)$ ここで乗法補正である$cal Z(lambda)$はノードに依存しない確率分布に対する期待値である。
- 参考スコア(独自算出の注目度): 2.005185530318604
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Inference efforts -- required to compute partition function, $Z$, of an Ising
model over a graph of $N$ ``spins" -- are most likely exponential in $N$.
Efficient variational methods, such as Belief Propagation (BP) and Tree
Re-Weighted (TRW) algorithms, compute $Z$ approximately minimizing respective
(BP- or TRW-) free energy. We generalize the variational scheme building a
$\lambda$-fractional-homotopy, $Z^{(\lambda)}$, where $\lambda=0$ and
$\lambda=1$ correspond to TRW- and BP-approximations, respectively, and
$Z^{(\lambda)}$ decreases with $\lambda$ monotonically. Moreover, this
fractional scheme 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 \cite{wainwright_tree-based_2002} and the loop
series approach of \cite{chertkov_loop_2006}, we show how to express $Z$ as a
product, $\forall \lambda:\ Z=Z^{(\lambda)}{\cal Z}^{(\lambda)}$, where the
multiplicative correction, ${\cal 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 (a) ability to estimate ${\cal Z}^{(\lambda)}$ with $O(N^4)$ fractional
samples; (b) suppression of $\lambda_*$ fluctuations with increase in $N$ for
instances from a particular random Ising ensemble.
- Abstract(参考訳): のグラフ上のIsingモデルのパーティション関数($Z$)を計算するのに必要な推論努力は、おそらく$N$で指数関数である。
Belief Propagation (BP) や Tree Re-Weighted (TRW) アルゴリズムのような効率的な変分法は、各(BP-またはTRW-)自由エネルギーをほぼ最小化する$Z$を計算する。
ここでは、$\lambda$-fractional-homotopy, $Z^{(\lambda)}$を構築し、$\lambda=0$と$\lambda=1$はそれぞれTRWおよびBP-approximationsに対応し、$Z^{(\lambda)}$は$\lambda$単調で減少する。
さらに、この分数的スキームは、魅力的な(強磁性)ケースにおいて、$Z^{(TRW)}\geq Z^{(\lambda)}\geq Z^{(BP)}$であり、$Z=Z^{(\lambda_*)}$であるようなユニークな(`exact)$\lambda_*$が存在することを保証している。
\cite{wainwright_tree-based_2002} の再パラメータ化アプローチと \cite{chertkov_loop_2006} のループ級数アプローチを一般化し、$z$ を積として表現する方法を示す:$\forall \lambda:\ z=z^{(\lambda)}{\cal z}^{(\lambda)}$ ここで、乗法補正 ${\cal z}^{(\lambda)}$ はノードごとの分数辺から構築されたノードに依存しない確率分布に対する期待である。
理論解析は,中・大規模の平面グラフとランダムグラフ上のイジングアンサンブルモデルを用いた大規模実験によって補完される。
経験的研究は、いくつかの興味深い観察をもたらす。
(a)${\cal Z}^{(\lambda)}$を$O(N^4)$分数サンプルで推定する能力。
(b)特定のランダム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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。