論文の概要: 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_*$ゆらぎの抑制。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。