論文の概要: Approximating the Log-Partition Function
- arxiv url: http://arxiv.org/abs/2102.10196v1
- Date: Fri, 19 Feb 2021 22:57:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-23 14:36:39.515609
- Title: Approximating the Log-Partition Function
- Title（参考訳）: ログ分割関数の近似
- Authors: Romain Cosson, Devavrat Shah
- Abstract要約: 基礎となるグラフ構造の性質を通じて近似比を定量化する手法を提案する。
グラフの有効抵抗を最小に抑えた平方根の逆に等しい近似比を実現するニアリニアタイム変量を提供する。
- 参考スコア（独自算出の注目度）: 16.59989033959959
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Variational approximation, such as mean-field (MF) and tree-reweighted (TRW),
provide a computationally efficient approximation of the log-partition function
for a generic graphical model. TRW provably provides an upper bound, but the
approximation ratio is generally not quantified.
As the primary contribution of this work, we provide an approach to quantify
the approximation ratio through the property of the underlying graph structure.
Specifically, we argue that (a variant of) TRW produces an estimate that is
within factor $\frac{1}{\sqrt{\kappa(G)}}$ of the true log-partition function
for any discrete pairwise graphical model over graph $G$, where $\kappa(G) \in
(0,1]$ captures how far $G$ is from tree structure with $\kappa(G) = 1$ for
trees and $2/N$ for the complete graph over $N$ vertices. As a consequence, the
approximation ratio is $1$ for trees, $\sqrt{(d+1)/2}$ for any graph with
maximum average degree $d$, and $\stackrel{\beta\to\infty}{\approx}
1+1/(2\beta)$ for graphs with girth (shortest cycle) at least $\beta \log N$.
In general, $\kappa(G)$ is the solution of a max-min problem associated with
$G$ that can be evaluated in polynomial time for any graph.
Using samples from the uniform distribution over the spanning trees of G, we
provide a near linear-time variant that achieves an approximation ratio equal
to the inverse of square-root of minimal (across edges) effective resistance of
the graph. We connect our results to the graph partition-based approximation
method and thus provide a unified perspective.
Keywords: variational inference, log-partition function, spanning tree
polytope, minimum effective resistance, min-max spanning tree, local inference
- Abstract（参考訳）: 平均場(MF)や木重み付け(TRW)などの変分近似は、汎用的なグラフィカルモデルのためのログ分割関数の計算効率の高い近似を提供する。
TRWは上界を証明できるが、近似比は一般に定量化されない。
この研究の主な貢献として、基礎となるグラフ構造の性質を通して近似比を定量化するアプローチを提案する。
具体的には、(ある変種) TRW は、グラフ $G$ 上の任意の離散ペアワイズグラフィカルモデルに対する真のログ分割関数 $\frac{1}{\sqrt{\kappa(G)}}$ 内の推定値を生成し、$\kappa(G) \in (0,1]$ は、木に対して $\kappa(G) = 1$ と $N$ 頂点上の完全なグラフに対する $/N$ を持つ木構造から $G$ がどのくらいあるかを捕捉する。
その結果、木に対する近似比率は、最大平均次数 $d$ の任意のグラフに対する $\sqrt{(d+1)/2}$ と、ガース付きグラフに対する $\stackrel{\beta\to\infty}{\approx} 1+1/(2\beta)$ と、少なくとも $\beta \log N$ である。
一般に、$\kappa(G)$は、任意のグラフに対して多項式時間で評価できる$G$に付随する極小問題の解である。
Gのスパンニングツリー上の均一な分布のサンプルを使用して、グラフの有効抵抗の最小(横縁)の平方根の逆と等しい近似比を達成するほぼ線形時間の変形を提供します。
結果とグラフ分割に基づく近似法を結合し,統一的な視点を提供する。
キーワード:変分推論、対数分割関数、スパンニングツリーポリトープ、最小有効抵抗、min-maxスパンニングツリー、ローカル推論
関連論文リスト
- Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - Correlation detection in trees for partial graph alignment [3.5880535198436156]
グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。
我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。
この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
論文 参考訳（メタデータ） (2021-07-15T22:02:27Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。
我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
論文 参考訳（メタデータ） (2020-05-18T14:23:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。