检索结果-内蒙古大学图书馆

Exactness of belief propagation for some graphical models with loops

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2008年第10期2008卷 P10016-P10016页

作者： Chertkov, Michael Los Alamos Natl Lab Div Theoret Los Alamos NM 87545 USA Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA

It is well known that an arbitrary graphical model of statistical inference defined on a tree, i.e. on a graph without loops, is solved exactly and efficiently by an iterative belief propagation ( BP) algorithm convergent to the unique minimum of the so-called Bethe free energy functional. For a general graphical model on a loopy graph, the functional may show multiple minima, the iterative BP algorithm may converge to one of the minima or may not converge at all, and the global minimum of the Bethe free energy functional is not guaranteed to correspond to the optimal maximum likelihood (ML) solution in the zero-temperature limit. However, there are exceptions to this general rule, discussed by Kolmogorov and Wainwright (2005) and by Bayati et al (2006, 2008) in two different contexts, where the zero-temperature version of the BP algorithm finds the ML solution for special models on graphs with loops. These two models share a key feature: their ML solutions can be found by an efficient linear programming (LP) algorithm with a totally uni-modular (TUM) matrix of constraints. Generalizing the two models, we consider a class of graphical models reducible in the zero-temperature limit to LP with TUM constraints. Assuming that a gedanken algorithm, g-BP, for finding the global minimum of the Bethe free energy is available, we show that in the limit of zero temperature, g-BP outputs the ML solution. Our consideration is based on equivalence established between gapless linear programming (LP) relaxation of the graphical model in the T -> 0 limit and the respective LP version of the Bethe free energy minimization.

关键词： spin glasses (theory) analysis of algorithms exact results message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2017年第7期2017卷 073403-073403页

作者： Lesieur, Thibault Krzakala, Florent Zdeborova, Lenka Univ Paris Saclay CEA CNRS Inst Phys Theor F-91191 Gif Sur Yvette France Ecole Normale Super Lab Phys Stat Paris France Sorbonne Univ Univ Pierre & Marie Curie Paris France

This article is an extended version of previous work of Lesieur et al (2015 IEEE Int. Symp. on Information Theory Proc. pp 1635-9 and 2015 53rd Annual Allerton Conf. on Communication, Control and Computing (IEEE) pp 680-7) on low-rank matrix estimation in the presence of constraints on the factors into which the matrix is factorized. Low-rank matrix factorization is one of the basic methods used in data analysis for unsupervised learning of relevant features and other types of dimensionality reduction. We present a framework to study the constrained low-rank matrix estimation for a general prior on the factors, and a general output channel through which the matrix is observed. We draw a parallel with the study of vector-spin glass models-presenting a unifying way to study a number of problems considered previously in separate statistical physics works. We present a number of applications for the problem in data analysis. We derive in detail a general form of the low-rank approximate message passing (Low-RAMP) algorithm, that is known in statistical physics as the TAP equations. We thus unify the derivation of the TAP equations for models as di. erent as the Sherrington-Kirkpatrick model, the restricted Boltzmann machine, the Hopfield model or vector (xy, Heisenberg and other) spin glasses. The state evolution of the Low-RAMP algorithm is also derived, and is equivalent to the replica symmetric solution for the large class of vector-spin glass models. In the section devoted to result we study in detail phase diagrams and phase transitions for the Bayesoptimal inference in low-rank matrix estimation. We present a typology of phase transitions and their relation to performance of algorithms such as the Low-RAMP or commonly used spectral methods.

关键词： analysis of algorithms message-passing algorithms statistical inference cavity and replica method

来源：评论

学校读者我要写书评

暂无评论

Replica Plefka expansion of Ising systems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2012年第04期2012卷 P04002-P04002页

作者： Yasuda, Muneki Kabashima, Yoshiyuki Tanaka, Kazuyuki Tohoku Univ Grad Sch Informat Sci Dept Appl Informat Sci Aoba Ku Sendai Miyagi 9808579 Japan Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Midori Ku Yokohama Kanagawa 2268502 Japan

The replica extension theory has been developed for the purpose of investigating spin glass systems in the replica symmetry breaking phase. The replica extension theory is a replica theory for a specific sample and has the scheme of the one-step replica symmetry breaking ansatz. In this paper, using the Plefka expansion, we propose the perturbative expansion of Gibbs free energies of Ising systems with the replica extension theory, and we derive the explicit form of the second- and third-order approximations. Our Plefka expansion systematically provides perturbative approximations taking the one-step replica symmetry breaking into account. In some numerical experiments, we show that our perturbative approximations are quantitatively superior to conventional perturbative approximations that do not take the one-step replica symmetry breaking into account in the spin glass phase.

关键词： cavity and replica method spin glasses (theory) message-passing algorithms statistical inference

来源：评论

学校读者我要写书评

暂无评论

The cavity master equation: average and fixed point of the ferromagnetic model in random graphs

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2020年第7期2020卷

作者： Dominguez, E. Machado, D. Mulet, R. Univ Havana Phys Fac Dept Theoret Phys Grp Complex Syst & Stat Phys Havana Cuba

The cavity master equation (CME) is a closure scheme to the usual master equation representing the dynamics of discrete variables in continuous time. In this work we explore the CME for a ferromagnetic model in a random graph. We first derive and average equation of the CME that describes the dynamics of mean magnetization of the system. We show that the numerical results compare remarkably well with the Monte Carlo simulations. Then, we show that the stationary state of the CME is well described by BP-like equations (independently of the dynamic rules that let the system toward the stationary state). These equations may be rewritten exactly as the fixed point solutions of the cavity equation if one also assumes that the stationary state is well described by a Boltzmann distribution.

关键词： kinetic Ising models message-passing algorithms spin glasses

来源：评论

学校读者我要写书评

暂无评论

Optimizing spread dynamics on graphs by message passing

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2013年第9期2013卷

作者： Altarelli, F. Braunstein, A. Dall'Asta, L. Zecchina, R. Politecn Torino DISAT I-10129 Turin Italy Politecn Torino Ctr Computat Sci I-10129 Turin Italy Coll Carlo Alberto I-10024 Moncalieri Italy Human Genet Fdn I-10126 Turin Italy

Cascade processes are responsible for many important phenomena in natural and social sciences. Simple models of irreversible dynamics on graphs, in which nodes activate depending on the state of their neighbors, have been successfully applied to describe cascades in a large variety of contexts. Over the past decades, much effort has been devoted to understanding the typical behavior of the cascades arising from initial conditions extracted at random from some given ensemble. However, the problem of optimizing the trajectory of the system, i.e. of identifying appropriate initial conditions to maximize (or minimize) the final number of active nodes, is still considered to be practically intractable, with the only exception being models that satisfy a sort of diminishing returns property called submodularity. Submodular models can be approximately solved by means of greedy strategies, but by definition they lack cooperative characteristics which are fundamental in many real systems. Here we introduce an efficient algorithm based on statistical physics for the optimization of trajectories in cascade processes on graphs. We show that for a wide class of irreversible dynamics, even in the absence of submodularity, the spread optimization problem can be solved efficiently on large networks. Analytic and algorithmic results on random graphs are complemented by the solution of the spread maximization problem on a real-world network (the Epinions consumer reviews network).

关键词： message-passing algorithms network dynamics optimization over networks

来源：评论

学校读者我要写书评

暂无评论

Partition function expansion on region graphs and message-passing equations

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2011年第12期2011卷 L12001-L12001页

作者： Zhou, Haijun Wang, Chuang Xiao, Jing-Qing Bi, Zedong Chinese Acad Sci State Key Lab Theoret Phys Inst Theoret Phys Beijing 100190 Peoples R China Chinese Acad Sci Inst Appl Math Acad Math & Syst Sci Beijing 100190 Peoples R China

Disordered and frustrated graphical systems are ubiquitous in physics, biology, and information science. For models on complete graphs or random graphs, deep understanding has been achieved through the mean-field replica and cavity methods. But finite-dimensional 'real' systems remain very challenging because of the abundance of short loops and strong local correlations. A statistical mechanics theory is constructed in this paper for finite-dimensional models based on the mathematical framework of the partition function expansion and the concept of region graphs. Rigorous expressions for the free energy and grand free energy are derived. message-passing equations on the region graph, such as belief propagation and survey propagation, are also derived rigorously.

关键词： rigorous results in statistical mechanics cavity and replica method spin glasses (theory) message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

The solution space structure of planted constraint satisfaction problems with growing domains

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2022年第3期2022卷

作者： Xu, Wei Zhang, Zhe Univ Sci & Technol Beijing Sch Math & Phys Beijing 100083 Peoples R China

Planting a solution into the random revised B (RB) model, which is a prototype of the random constraint satisfaction problem (CSP) with growing domains, can generate very hard satisfiable CSP benchmarks. We study the solution space structure of the planted RB model. In the thermodynamic limit, by the first moment method we find that this model goes through four phase transitions as the constraint density increases. In the replica symmetric phase, what we call the independent phase transition occurs, after which the planted cluster (cluster containing the planted solution) is separated from the giant cluster. From then on, the solution space except the planted cluster goes through the same clustering phase transition and the same satisfiability phase transition as on the random RB model. The planted cluster goes through the isolated phase transition, after which the planted cluster contains only one solution. When the instances have about 10(2) variables, experiments show that the last three phase transitions have already appeared as in the thermodynamic limit. This phase diagram provides strong evidence that this model can generate very hard satisfiable CSP benchmarks. Finally, we find when the constraint density goes to infinity, there is a single smooth valley in the energy landscape.

关键词： optimization over networks message-passing algorithms random graphs networks

来源：评论

学校读者我要写书评

暂无评论

A weighted belief-propagation algorithm for estimating volume-related properties of random polytopes

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2012年第11期2012卷 P11003-P11003页

作者： Font-Clos, Francesc Alessandro Massucci, Francesco Castillo, Isaac Perez Ctr Recerca Matemat E-08193 Bellaterra Barcelona Spain Univ Autonoma Barcelona Dept Matemat E-08193 Bellaterra Barcelona Spain Univ Rovira & Virgili Dept Engn Quim Tarragona 43007 Spain Kings Coll London Dept Math London WC2R 2LS England

In this work we introduce a novel weighted message-passing algorithm based on the cavity method for estimating volume-related properties of random polytopes, properties which are relevant in various research fields ranging from metabolic networks, to neural networks, to compressed sensing. We propose, as opposed to adopting the usual approach consisting in approximating the real-valued cavity marginal distributions by a few parameters, using an algorithm to faithfully represent the entire marginal distribution. We explain various alternatives for implementing the algorithm and benchmarking the theoretical findings by showing concrete applications to random polytopes. The results obtained with our approach are found to be in very good agreement with the estimates produced by the Hit-and-Run algorithm, known to produce uniform sampling.

关键词： cavity and replica method disordered systems (theory) message-passing algorithms metabolic networks

来源：评论

学校读者我要写书评

暂无评论

Geometrical organization of solutions to random linear Boolean equations

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2006年第10期2006卷 P10007-P10007页

作者： Mora, Thierry Mezard, Marc CNRS UMR 8626 Lab Phys Theor & Modeles Stat F-91405 Orsay France Univ Paris 11 F-91405 Orsay France

The random XORSAT problem deals with large random linear systems of Boolean variables. The difficulty of such problems is controlled by the ratio of number of equations to number of variables. It is known that in some range of values of this parameter, the space of solutions breaks into many disconnected clusters. Here we study precisely the corresponding geometrical organization. In particular, the distribution of distances between these clusters is computed by the cavity method. This allows one to study the 'x-satisfiability' threshold, the critical density of equations where there exist two solutions at a given distance.

关键词： cavity and replica method message-passing algorithms typical case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Adversarial satisfiability problem

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2011年第3期2011卷 P03023-P03023页

作者： Castellana, Michele Zdeborova, Lenka Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy Univ Paris 11 UMR8626 F-91405 Orsay France CNRS LPTMS F-91405 Orsay France Los Alamos Natl Lab Div Theoret Los Alamos NM 87545 USA Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA CEA Saclay Inst Phys Theor IPhT F-91191 Gif Sur Yvette France CNRS URA 2306 F-91191 Gif Sur Yvette France

We study the adversarial satisfiability problem, where the adversary can choose whether the variables are negated in clauses or not, in order to make the resulting formula unsatisfiable. This problem belongs to a general class of adversarial optimization problems that often arise in practice and are algorithmically much harder than the standard optimization problems. We use the cavity method to compute large deviations of the entropy in the random satisfiability problem with respect to the configurations of negations. We conclude that in the thermodynamic limit the best strategy the adversary can adopt is to simply balance the number of times every variable is negated and the number of times it is not negated. We also conduct a numerical study of the problem, and find that there are very strong pre-asymptotic effects that may be due to the fact that for small sizes exponential and factorial growth is hardly distinguishable. As a side result we compute the satisfiability threshold for balanced configurations of negations, and also the random regular satisfiability, i.e. when all variables belong to the same number of clauses.

关键词： message-passing algorithms random graphs networks

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：