論文の概要: 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_*$ゆらぎの抑制など、興味深い観測をもたらす。
また,画像デノイズ化問題に対する本手法の適用性についても検証し,検討する。
関連論文リスト
- Manifold learning in Wasserstein space [3.2315169215372443]
距離空間 $(Lambda,W_Lambda)$ は、ノード $lambda_i=1N$ とエッジウェイト $W(lambda_i,lambda_j)$ のグラフからグロモフ-ワッサーシュタインの意味で復元可能であることを示す。
特に、測度空間 $(Lambda,W_Lambda)$ は、Gromov--Wasserstein の意味でノード $lambda_i_ を持つグラフから復元可能であることを示す。
論文 参考訳(メタデータ) (2023-11-14T21:21:35Z) - 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) - Asymptotic Theory of $\ell_1$-Regularized PDE Identification from a
Single Noisy Trajectory [2.0299248281970956]
線形および非線形進化的偏微分方程式(PDE)の一般クラスに対する1つの雑音軌道からの支持回復を証明した。
Local-Polynomialフィルタによって定義される単一の軌道データから、$mathbfc(lambda)のサポートが基礎となるPDEに関連する真の署名サポートに$ally収束することを保証する十分な条件のセットを提供します。
論文 参考訳(メタデータ) (2021-03-12T02:23:04Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - $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) - $\lambda$-Regularized A-Optimal Design and its Approximation by
$\lambda$-Regularized Proportional Volume Sampling [1.256413718364189]
本稿では,$lambda$-regularized $A$-optimal design problemについて検討し,$lambda$-regularized proportional volume sample algorithmを紹介する。
この問題は、リッジ回帰モデルにおける真の係数からリッジ回帰予測器の2乗誤差を最小化しようとする、リッジ回帰の最適設計から動機づけられている。
論文 参考訳(メタデータ) (2020-06-19T15:17:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。