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

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

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

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Approximate survey propagation for statistical inference

引用

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

作者： 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 message-passing approach to random constraint satisfaction problems with growing domains

引用

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

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Constraint satisfaction problems with isolated solutions are hard

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2008年第12期2008卷 P12004-P12004页

作者： Zdeborova, Lenka Mezard, Marc Univ Paris Sud LPTMS UMR8626 CNRS 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

We study the phase diagram and the algorithmic hardness of the random 'locked' constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of Boolean formulae or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand, we show empirically that the clustered phase of these problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard constraint satisfaction problems.

关键词： analysis of algorithms message-passing algorithms random graphs networks typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Shortest node-disjoint paths on random graphs

引用

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

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An efficient CDMA decoder for correlated information sources

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2009年第07期2009卷 P07039-P07039页

作者： Efraim, Hadar Yacov, Nadav Shental, Ori Kanter, Ido Bar Ilan Univ Minerva Ctr IL-52900 Ramat Gan Israel Bar Ilan Univ Dept Phys IL-52900 Ramat Gan Israel Univ Calif San Diego CMRR La Jolla CA 92093 USA

We consider the detection of correlated information sources in the ubiquitous code-division multiple-access (CDMA) scheme. We propose a message-passing based scheme for detecting correlated sources directly, with no need for source coding. The detection is done simultaneously over a block of transmitted binary symbols (word). Simulation results are provided, demonstrating a substantial improvement in bit error rate in comparison with the unmodified detector and the alternative of source compression. The robustness of the error-performance improvement is shown under practical model settings, including wrong estimation of the generating Markov transition matrix and finite length spreading codes.

关键词： message-passing algorithms error correcting codes

来源：评论

学校读者我要写书评

暂无评论

Statistical mechanics of budget-constrained auctions

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2009年第07期2009卷 P07002-P07002页

作者： Altarelli, F. Braunstein, A. Realpe-Gomez, J. Zecchina, R. ISI Fdn I-10133 Turin Italy Politecn Torino I-10129 Turin Italy

Finding the optimal assignment in budget-constrained auctions is a combinatorial optimization problem with many important applications, a notable example being in the sale of advertisement space by search engines (in this context the problem is often referred to as the off-line AdWords problem). On the basis of the cavity method of statistical mechanics, we introduce a message-passing algorithm that is capable of solving efficiently random instances of the problem extracted from a natural distribution, and we derive from its properties the phase diagram of the problem. As the control parameter (average value of the budgets) is varied, we find two phase transitions delimiting a region in which long-range correlations arise.

关键词： cavity and replica method message-passing algorithms applications to game theory and mathematical economics

来源：评论

学校读者我要写书评

暂无评论

Typical reconstruction performance for distributed compressed sensing based on l_2,1-norm regularized least square and Bayesian optimal reconstruction: influences of noise

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第6期2016卷 063304-063304页

作者： Shiraki, Yoshifumi Kabashima, Yoshiyuki NTT Corp NTT Commun Sci Labs Atsugi Kanagawa 2430198 Japan Tokyo Inst Technol Dept Math & Comp Sci Yokohama Kanagawa 2268502 Japan

A signal model called joint sparse model 2 (JSM-2) or the multiple measurement vector problem, in which all sparse signals share their support, is important for dealing with practical signal processing problems. In this paper, we investigate the typical reconstruction performance of noisy measurement JSM-2 problems for l(2,1)-norm regularized least square reconstruction and the Bayesian optimal reconstruction scheme in terms of mean square error. Employing the replica method, we show that these schemes, which exploit the knowledge of the sharing of the signal support, can recover the signals more precisely as the number of channels increases. In addition, we compare the reconstruction performance of two different ensembles of observation matrices: one is composed of independent and identically distributed random Gaussian entries and the other is designed so that row vectors are orthogonal to one another. As reported for the single-channel case in earlier studies, our analysis indicates that the latter ensemble offers better performance than the former ones for the noisy JSM-2 problem. The results of numerical experiments with a computationally feasible approximation algorithm we developed for this study agree with the theoretical estimation.

关键词： analysis of algorithms message-passing algorithms source and channel coding

来源：评论

学校读者我要写书评

暂无评论

On the properties of the Bethe approximation and loopy belief propagation on binary networks

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2005年第11期2005卷 P11012-P11012页

作者： Mooij, JM Kappen, HJ Radboud Univ Nijmegen Inst Neurosci Dept Biophys NL-6525 EZ Nijmegen Netherlands

We analyse the local stability of the high-temperature fixed point of the loopy belief propagation (LBP) algorithm and how this relates to the properties of the Bethe free energy which LBP tries to minimize. We focus on the case of binary networks with pairwise interactions. In particular, we state sufficient conditions for convergence of LBP to a unique fixed point and show that these are sharp for purely ferromagnetic interactions. In contrast, in the purely antiferromagnetic case, the undamped parallel LBP algorithm is suboptimal in the sense that the stability of the fixed point breaks down much earlier than for damped or sequential LBP;we observe that the onset of instability for the latter algorithms is related to the properties of the Bethe free energy. For spinglass interactions, damping LBP only helps slightly. We estimate analytically the temperature at which the high-temperature LBP fixed point becomes unstable for random graphs with arbitrary degree distributions and random interactions.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：