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

Solving the spherical p-spin model with the cavity method: equivalence with the replica results

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2020年第11期2020卷 113302-113302页

作者： Gradenigo, Giacomo Angelini, Maria Chiara Leuzzi, Luca Ricci-Tersenghi, Federico Gran Sasso Sci Inst Laquila Italy UOS Roma Inst Nanotechnol CNR Nanotec Rome Italy Sapienza Univ Roma Dipartimento Fis Rome Italy Ist Nazl Fis Nucl Sez Roma1 Rome Italy

The spherical p-spin is a fundamental model for glassy physics, thanks to its analytical solution achievable via the replica method. Unfortunately, the replica method has some drawbacks: it is very hard to apply to diluted models and the assumptions beyond it are not immediately clear. Both drawbacks can be overcome by the use of the cavity method;however, this needs to be applied with care to spherical models. Here, we show how to write the cavity equations for spherical p-spin models, both in the replica symmetric (RS) ansatz (corresponding to belief propagation) and in the one-step replica-symmetry-breaking (1RSB) ansatz (corresponding to survey propagation). The cavity equations can be solved by a Gaussian RS and multivariate Gaussian 1RSB ansatz for the distribution of the cavity fields. We compute the free energy in both ansatzes and check that the results are identical to the replica computation, predicting a phase transition to a 1RSB phase at low temperatures. The advantages of solving the model with the cavity method are many. The physical meaning of the ansatz for the cavity marginals is very clear. The cavity method works directly with the distribution of local quantities, which allows us to generalize the method to diluted graphs. What we are presenting here is the first step towards the solution of the diluted version of the spherical p-spin model, which is a fundamental model in the theory of random lasers and interesting per se as an easier-to-simulate version of the classical fully connected p-spin model.

关键词： cavity and replica method ergodicity breaking message-passing algorithms random graphs networks

来源：评论

学校读者我要写书评

暂无评论

Finite size corrections to random Boolean networks

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2006年第12期2006卷 P12012-P12012页

作者： Leone, Michele Pagnani, Andrea Parisi, Giorgio Zagordi, Osvaldo ISI Fdn I-10133 Turin Italy Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy Scuola Int Super Studi Avanzati ISAS I-34014 Trieste Italy

Since their introduction, Boolean networks have been traditionally studied in view of their rich dynamical behaviour under different update protocols and for their qualitative analogy with cell regulatory networks. More recently, tools borrowed from the statistical physics of disordered systems and from computer science have provided a more complete characterization of their equilibrium behaviour. However, the largest number of results have been obtained in the thermodynamic limit, which is often far from being reached when dealing with realistic instances of the problem. The numerical analysis presented here aims at comparing-for a specific family of models-the outcomes given by the heuristic belief propagation algorithm with those given by exhaustive enumeration. In the second part of the paper some analytical considerations on the validity of the annealed approximation are discussed.

关键词： message-passing algorithms random graphs networks

来源：评论

学校读者我要写书评

暂无评论

Low-temperature excitations within the Bethe approximation

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2013年第4期2013卷 P04011-P04011页

作者： Biazzo, I. Ramezanpour, A. Politecn Torino Dept Phys I-10129 Turin Italy Politecn Torino Ctr Computat Sci I-10129 Turin Italy

We propose the variational quantum cavity method to construct a minimal energy subspace of wavevectors that are used to obtain some upper bounds for the energy cost of the low-temperature excitations. Given a trial wavefunction we use the cavity method of statistical physics to estimate the Hamiltonian expectation and to find the optimal variational parameters in the subspace of wavevectors orthogonal to the lower-energy wavefunctions. To this end, we write the overlap between two wavefunctions within the Bethe approximation, which allows us to replace the global orthogonality constraint with some local constraints on the variational parameters. The method is applied to the transverse Ising model and different levels of approximations are compared with the exact numerical solutions for small systems.

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

来源：评论

学校读者我要写书评

暂无评论

Efficient inference in the transverse field Ising model

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2023年第3期2023卷 033301-033301页

作者： Dominguez, E. Kappen, H. J. Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav Nijmegen Netherlands

In this paper we introduce an approximate method to solve the quantum cavity equations for transverse field Ising models. The method relies on a projective approximation of the exact cavity distributions of imaginary time trajectories (paths). A key feature, novel in the context of similar algorithms, is the explicit separation of the classical and quantum parts of the distributions. Numerical simulations show accurate results in comparison with the sampled solution of the cavity equations, the exact diagonalization of the Hamiltonian (when possible) and other approximate inference methods in the literature. The computational complexity of this new algorithm scales linearly with the connectivity of the underlying lattice, enabling the study of highly connected networks, as the ones often encountered in quantum machine learning problems.

关键词： cavity and replica method message-passing algorithms inference of graphical models

来源：评论

学校读者我要写书评

暂无评论

A novel approach for studying realistic navigations on networks

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2007年第04期2007卷 P04007-P04007页

作者： Sen, Parongama Univ Calcutta Dept Phys Kolkata 700009 W Bengal India

We consider navigation or search schemes on networks which are realistic in the sense that not all search chains can be completed. We show that the quantity mu = rho/s(d), where sd is the average dynamic shortest distance and. the success rate for completion of a search, is a consistent measure for the quality of a search strategy. Taking the example of realistic searches on scale free networks, we. nd that scales with the system size N as N-sigma, where sigma decreases as the searching strategy is improved. This measure is also shown to be sensitive to the distinguishing characteristics of networks. In this new approach, a dynamic small world (DSW) effect is said to exist when delta similar to 0. We show that such a DSW does indeed exist in social networks in which the linking probability is dependent on social distances.

关键词： message-passing algorithms random graphs networks stochastic search communication supply and information networks

来源：评论

学校读者我要写书评

暂无评论

Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2015年第5期000卷 P05013-P05013页

作者： Barbier, Jean Schuelke, Christophe Krzakala, Florent Ecole Normale Super CNRS UMR 8550 Phys Stat Lab F-75231 Paris France Univ Paris 06 F-75231 Paris France Univ Paris 06 Sorbonne Univ UMR 8550 F-75231 Paris France Univ Paris Diderot Sorbonne Paris Cite F-75205 Paris France Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy

We study the behavior of approximate message-passing (AMP), a solver for linear sparse estimation problems such as compressed sensing, when the i.i.d matrices-for which it has been specifically designed-are replaced by structured operators, such as Fourier and Hadamard ones. We show empirically that after proper randomization, the structure of the operators does not significantly affect the performances of the solver. Furthermore, for some specially designed spatially coupled operators, this allows a computationally fast and memory efficient reconstruction in compressed sensing up to the information-theoretical limit. We also show how this approach can be applied to sparse superposition codes, allowing the AMP decoder to perform at large rates for moderate block length.

关键词： message-passing algorithms error-correcting codes statistical inference

来源：评论

学校读者我要写书评

暂无评论

Approximate inverse Ising models close to a Bethe reference point

引用

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

作者： Furtlehner, Cyril Univ Paris 11 Inria Saclay F-91405 Orsay France

We investigate different ways of generating approximate solutions to the inverse Ising problem (IIP). Our approach consists in taking as a starting point for further perturbation procedures, a Bethe mean-field solution obtained with a maximum spanning tree (MST) of pairwise mutual information, which we refer to as the Bethe reference point. We consider three different ways of following this idea: in the first one, we discuss a greedy procedure by which optimal links to be added starting from the Bethe reference point are selected and calibrated iteratively;the second one is based on the observation that the natural gradient can be computed analytically at the Bethe point;the last one deals with loop corrections to the Bethe point. Assuming no external field and using a dual transform we develop a dual loop joint model based on a well-chosen cycle basis. This leads us to identify a subclass of planar models, which we refer to as dual-loop-free models, having possibly many loops, but characterized by a singly connected dual factor graph, for which the partition function and the linear response can be computed exactly in respectively O(N) and O(N-2) operations, thanks to a dual weight propagation (DWP) message passing procedure that we set up. When restricted to this subclass of models, the inverse Ising problem being convex, becomes tractable at any temperature. Numerical experiments show that this can serve to some extent as a good approximation for models with dual loops.

关键词： message-passing algorithms random graphs networks network reconstruction

来源：评论

学校读者我要写书评

暂无评论

Statistical mechanics of reputation systems in autonomous networks

引用

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

作者： Manoel, Andre Vicente, Renato Univ Sao Paulo Inst Fis Dept Fis Geral BR-05314090 Sao Paulo Brazil Univ Sao Paulo Inst Matemat & Estat Dept Appl Math BR-05508090 Sao Paulo Brazil

Reputation systems seek to infer which members of a community can be trusted based on ratings they issue about each other. We construct a Bayesian inference model and simulate approximate estimates using belief propagation (BP). The model is then mapped onto computing equilibrium properties of a spin glass in a random field and analyzed by employing the replica symmetric cavity approach. Having the fraction of positive ratings and the environment noise level as control parameters, we evaluate in different scenarios the robustness of the BP approximation and its theoretical performance in terms of estimation error. Regions of degraded performance are then explained by the convergence properties of the BP algorithm and by the emergence of a glassy phase.

关键词： cavity and replica method message-passing algorithms communication supply and information networks

来源：评论

学校读者我要写书评

暂无评论

Optimal static and dynamic recycling of defective binary devices

引用

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

作者： Challet, D Castillo, IP Univ Oxford Inst Math Nomura Ctr Quantitat Finance Oxford OX1 3LB England Katholieke Univ Leuven Inst Theoret Fys B-3001 Heverlee Belgium

The binary defect combination problem consists in finding a fully working subset from a given ensemble of imperfect binary components. We determine the typical properties of the model using methods of statistical mechanics, in particular the region in the parameter space where there is almost surely at least one fully working subset. Dynamic recycling of a flux of imperfect binary components leads to zero wastage.

关键词： neuronal networks (theory) message-passing algorithms robust and stochastic optimization stochastic search

来源：评论

学校读者我要写书评

暂无评论

Disordered systems insights on computational hardness

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2022年第11期2022卷 114015-114015页

作者： Gamarnik, David Moore, Cristopher Zdeborova, Lenka MIT Operat Res Ctr Cambridge MA 02139 USA MIT Sloan Sch Management Cambridge MA 02139 USA Santa Fe Inst Santa Fe NM 87501 USA Ecole Polytech Fed Lausanne EPFL SPOC Lab Route Cantonale CH-1015 Lausanne Switzerland

In this review article we discuss connections between the physics of disordered systems, phase transitions in inference problems, and computational hardness. We introduce two models representing the behavior of glassy systems, the spiked tensor model and the generalized linear model. We discuss the random (non-planted) versions of these problems as prototypical optimization problems, as well as the planted versions (with a hidden solution) as prototypical problems in statistical inference and learning. Based on ideas from physics, many of these problems have transitions where they are believed to jump from easy (solvable in polynomial time) to hard (requiring exponential time). We discuss several emerging ideas in theoretical computer science and statistics that provide rigorous evidence for hardness by proving that large classes of algorithms fail in the conjectured hard regime. This includes the overlap gap property, a particular mathematization of clustering or dynamical symmetry-breaking, which can be used to show that many algorithms that are local or robust to changes in their input fail. We also discuss the sum-of-squares hierarchy, which places bounds on proofs or algorithms that use low-degree polynomials such as standard spectral methods and semidefinite relaxations, including the Sherrington-Kirkpatrick model. Throughout the manuscript we present connections to the physics of disordered systems and associated replica symmetry breaking properties.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：