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

A message-passing approach to random constraint satisfaction problems with growing domains

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2011年第2期2011卷

作者： Zhao, Chunyan Zhou, Haijun Zheng, Zhiming Xu, Ke Beihang Univ State Key Lab Software Dev Environm Beijing 100191 Peoples R China Beihang Univ Sch Math & Syst Sci Beijing 100191 Peoples R China Chinese Acad Sci Inst Theoret Phys Beijing 100190 Peoples R China Beihang Univ LMIB Beijing 100191 Peoples R China

message-passing algorithms based on belief propagation (BP) are implemented on a random constraint satisfaction problem (CSP) referred to as model RB, which is a prototype of hard random CSPs with growing domain size. In model RB, the number of candidate discrete values (the domain size) of each variable increases polynomially with the variable number N of the problem formula. Although the satisfiability threshold of model RB is exactly known, finding solutions for a single problem formula is quite challenging and attempts have been limited to cases of N similar to 10(2). In this paper, we propose two different kinds of message-passing algorithms guided by BP for this problem. Numerical simulations demonstrate that these algorithms allow us to find a solution for random formulas of model RB with constraint tightness slightly less than p(cr), the threshold value for the satisfiability phase transition. To evaluate the performance of these algorithms, we also provide a local search algorithm (random walk) as a comparison. Besides this, the simulated time dependence of the problem size N and the entropy of the variables for growing domain size are discussed.

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

来源：评论

学校读者我要写书评

暂无评论

Entropic gradient descent algorithms and wide flat minima*

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2021年第12期2021卷

作者： Pittorino, Fabrizio Lucibello, Carlo Feinauer, Christoph Perugini, Gabriele Baldassi, Carlo Demyanenko, Elizaveta Zecchina, Riccardo Bocconi Univ Inst Data Sci & Analyt AI Lab I-20136 Milan Italy Politecn Torino Dept Appl Sci & Technol I-10129 Turin Italy

The properties of flat minima in the empirical risk landscape of neural networks have been debated for some time. Increasing evidence suggests they possess better generalization capabilities with respect to sharp ones. In this work we first discuss the relationship between alternative measures of flatness: the local entropy, which is useful for analysis and algorithm development, and the local energy, which is easier to compute and was shown empirically in extensive tests on state-of-the-art networks to be the best predictor of generalization capabilities. We show semi-analytically in simple controlled scenarios that these two measures correlate strongly with each other and with generalization. Then, we extend the analysis to the deep learning scenario by extensive numerical validations. We study two algorithms, entropy-stochastic gradient descent and replicated-stochastic gradient descent, that explicitly include the local entropy in the optimization objective. We devise a training schedule by which we consistently find flatter minima (using both flatness measures), and improve the generalization error for common architectures (e.g. ResNet, EfficientNet).

关键词： deep learning machine learning message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

The large deviations of the whitening process in random constraint satisfaction problems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第5期2016卷

作者： Braunstein, Alfredo Dall'Asta, Luca Semerjian, Guilhem Zdeborova, Lenka Politecn Torino Corso Duca Abruzzi 24 I-10129 Turin Italy Human Genet Fdn Via Nizza 52 I-10126 Turin Italy Collegio Carlo Alberto Via Real Collegio 30 I-10024 Moncalieri Italy Univ Paris 06 Sorbonne Univ PSL Res Univ LPTENSEcole Normale SuperCNRSUMR 8549 24 Rue Lhomond F-75005 Paris France Univ Paris Saclay CEA CNRS Inst Phys Theor F-91191 Gif Sur Yvette France

Random constraint satisfaction problems undergo several phase transitions as the ratio between the number of constraints and the number of variables is varied. When this ratio exceeds the satisfiability threshold no more solutions exist;the satisfiable phase, for less constrained problems, is itself divided in an unclustered regime and a clustered one. In the latter solutions are grouped in clusters of nearby solutions separated in configuration space from solutions of other clusters. In addition the rigidity transition signals the appearance of so-called frozen variables in typical solutions: beyond this threshold most solutions belong to clusters with an extensive number of variables taking the same values in all solutions of the cluster. In this paper we refine the description of this phenomenon by estimating the location of the freezing transition, corresponding to the disappearance of all unfrozen solutions (not only typical ones). We also unveil phase transitions for the existence and uniqueness of locked solutions, in which all variables are frozen. From a technical point of view we characterize atypical solutions with a number of frozen variables different from the typical value via a large deviation study of the dynamics of a stripping process (whitening) that unveils the frozen variables of a solution, building upon recent works on atypical trajectories of the bootstrap percolation dynamics. Our results also bear some relevance from an algorithmic perspective, previous numerical studies having shown that heuristic algorithms of various kinds usually output unfrozen solutions.

关键词： cavity and replica method message-passing algorithms spin glasses (theory) typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2012年第8期2012卷

作者： Krzakala, Florent Mezard, Marc Sausset, Francois Sun, Yifan Zdeborova, Lenka CNRS F-75005 Paris France ESPCI ParisTech UMR Gulliver 7083 F-75005 Paris France Univ Paris 11 F-91405 Orsay France CNRS UMR8626 LPTMS F-91405 Orsay France Beihang Univ LMIB Beijing 100191 Peoples R China Beihang Univ Sch Math & Syst Sci Beijing 100191 Peoples R China CEA Saclay IPhT Inst Phys Theor F-91191 Gif Sur Yvette France CENS Lab Leon Brillouin CNRS URA 2306 F-91191 Gif Sur Yvette France

Compressed sensing is a signal processing method that acquires data directly in a compressed form. This allows one to make fewer measurements than were considered necessary to record a signal, enabling faster or more precise measurement protocols in a wide range of applications. Using an interdisciplinary approach, we have recently proposed in Krzakala et al (2012 Phys. Rev. X 2 021005) a strategy that allows compressed sensing to be performed at acquisition rates approaching the theoretical optimal limits. In this paper, we give a more thorough presentation of our approach, and introduce many new results. We present the probabilistic approach to reconstruction and discuss its optimality and robustness. We detail the derivation of the message passing algorithm for reconstruction and expectation maximization learning of signal-model parameters. We further develop the asymptotic analysis of the corresponding phase diagrams with and without measurement noise, for different distributions of signals, and discuss the best possible reconstruction performances regardless of the algorithm. We also present new efficient seeding matrices, test them on synthetic data and analyze their performance asymptotically.

关键词： cavity and replica method message-passing algorithms error correcting codes statistical inference

来源：评论

学校读者我要写书评

暂无评论

Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2007年第6期2007卷

作者： Zhou, Jie Ma, Hui Zhou, Haijun Chinese Acad Sci Inst Theoret Phys Beijing 100080 Peoples R China

In a finite-connectivity spin glass at the zero-temperature limit, long-range correlations exist among the unfrozen vertices (whose spin values are non-fixed). Such long-range frustrations are partially removed through the first-step replica-symmetry-broken (1RSB) cavity theory, but residual long-range frustrations may still persist in this mean-field solution. By way of population dynamics, here we perform a perturbation-percolation analysis to calculate the magnitude of long-range frustrations in the 1RSB solution of a given spin-glass system. We study two well-studied model systems, the minimal vertex-cover problem and the maximal 2-satisfiability problem. This work points to a possible way of improving the zero-temperature 1RSB mean-field theory of spin glasses.

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

来源：评论

学校读者我要写书评

暂无评论

Fast inference of ill-posed problems within a convex space

引用

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

作者： Fernandez-de-Cossio-Diaz, J. Mulet, R. Ctr Mol Immunol Dept Syst Biol Havana Cuba Univ Havana Grp Complex Syst & Stat Phys Dept Theoret Phys Fac Phys Havana Cuba

In multiple scientific and technological applications we face the problem of having low dimensional data to be justified by a linear model defined in a high dimensional parameter space. The difference in dimensionality makes the problem ill-defined: the model is consistent with the data for many values of its parameters. The objective is to find the probability distribution of parameter values consistent with the data, a problem that can be cast as the exploration of a high dimensional convex polytope. In this work we introduce a novel algorithm to solve this problem efficiently. It provides results that are statistically indistinguishable from currently used numerical techniques while its running time scales linearly with the system size. We show that the algorithm performs robustly in many abstract and practical applications. As working examples we simulate the effects of restricting reaction fluxes on the space of feasible phenotypes of a genome scale Escherichia coli metabolic network and infer the traffic flow between origin and destination nodes in a real communication network.

关键词： disordered systems (theory) message-passing algorithms metabolic networks peer-to-peer networks

来源：评论

学校读者我要写书评

暂无评论

Approximate survey propagation for statistical inference

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2019年第2期2019卷

作者： Antenucci, Fabrizio Krzakala, Florent Urbani, Pierfrancesco Zdeborova, Lenka Univ Paris Saclay CNRS CEA Inst Phys Theor F-91191 Gif Sur Yvette France CNR NANOTEC Inst Nanotechnol Rome Unit Soft & Living Matter Lab Piazzale Aldo Moro 5 I-00185 Rome Italy CNRS Lab Phys Stat Paris France Sorbonnes Univ Paris France PSL Univ Ecole Normale Suprieure Paris France

Approximate message passing algorithm enjoyed considerable attention in the last decade. In this paper we introduce a variant of the AMP algorithm that takes into account glassy nature of the system under consideration. We coin this algorithm as the approximate survey propagation (ASP) and derive it for a class of low-rank matrix estimation problems. We derive the state evolution for the ASP algorithm and prove that it reproduces the one-step replica symmetry breaking (1RSB) fixed-point equations, well-known in physics of disordered systems. Our derivation thus gives a concrete algorithmic meaning to the 1RSB equations that is of independent interest. We characterize the performance of ASP in terms of convergence and mean-squared error as a function of the free Parisi parameter s. We conclude that when there is a model mismatch between the true generative model and the inference model, the performance of AMP rapidly degrades both in terms of MSE and of convergence, while for well-chosen values of the Parisi parameter s ASP converges in a larger regime and can reach lower errors. Among other results, our analysis leads us to a striking hypothesis that whenever s (or other parameters) can be set in such a way that the Nishimori condition M = Q > 0 is restored, then the corresponding algorithm is able to reach mean-squared error as low as the Bayes-optimal error obtained when the model and its parameters are known and exactly matched in the inference procedure. The remaining drawback is that we have not found a procedure that would systematically find a value of s leading to such low errors, this is a challenging problem let for future work.

关键词： message-passing algorithms statistical inference analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A dynamical mean-field theory for learning in restricted Boltzmann machines

引用

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

作者： Cakmak, Burak Opper, Manfred Tech Univ Berlin Artificial Intelligence Grp Berlin Germany

We define a message-passing algorithm for computing magnetizations in restricted Boltzmann machines, which are Ising models on bipartite graphs introduced as neural network models for probability distributions over spin configurations. To model nontrivial statistical dependencies between the spins' couplings, we assume that the rectangular coupling matrix is drawn from an arbitrary bi-rotation invariant random matrix ensemble. Using the dynamical functional method of statistical mechanics we exactly analyze the dynamics of the algorithm in the large system limit. We prove the global convergence of the algorithm under a stability criterion and compute asymptotic convergence rates showing excellent agreement with numerical simulations.

关键词： cavity and replica method machine learning message-passing algorithms spin glasses

来源：评论

学校读者我要写书评

暂无评论

Shortest node-disjoint paths on random graphs

引用

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

作者： De Bacco, C. Franz, S. Saad, D. Yeung, C. H. CNRS LPTMS F-91405 Orsay France Univ Paris 11 F-91405 Orsay France Aston Univ Nonlinear & Complex Res Grp Birmingham B4 7ET W Midlands England Hong Kong Univ Sci & Technol Dept Phys Hong Kong Hong Kong Peoples R China Hong Kong Inst Educ Dept Sci & Environm Studies Tai Po Hong Kong Peoples R China

A localized method to distribute paths on random graphs is devised, aimed at finding the shortest paths between given source/destination pairs while avoiding path overlaps at nodes. We propose a method based on message-passing techniques to process global information and distribute paths optimally. Statistical properties such as scaling with system size and number of paths, average path-length and the transition to the frustrated regime are analyzed. The performance of the suggested algorithm is evaluated through a comparison against a greedy algorithm.

关键词： cavity and replica method message-passing algorithms optimization over networks

来源：评论

学校读者我要写书评

暂无评论

On the exactness of the cavity method for weighted b-matchings on arbitrary graphs and its relation to linear programs

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2008年第6期2008卷

作者： Bayati, Mohsen Borgs, Christian Chayes, Jennifer Zecchina, Riccardo Microsoft Res Cambridge MA 02142 USA Politecn Torino Dept Phys I-10129 Turin Italy

We consider the general problem of finding the minimum weight b-matching on arbitrary graphs. We prove that, whenever the linear programing relaxation of the problem has no fractional solutions, then the cavity or bel... 详细信息

关键词： analysis of algorithms exact results message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：