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

Approximate message passing with spectral initialization for generalized linear models*

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

作者： Mondelli, Marco Venkataramanan, Ramji Inst Sci & Technol IST Klosterneuburg Austria Univ Cambridge Dept Engn Cambridge England

We consider the problem of estimating a signal from measurements obtained via a generalized linear model. We focus on estimators based on approximate message passing (AMP), a family of iterative algorithms with many appealing features: the performance of AMP in the high-dimensional limit can be succinctly characterized under suitable model assumptions;AMP can also be tailored to the empirical distribution of the signal entries, and for a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms. However, a major issue of AMP is that in many models (such as phase retrieval), it requires an initialization correlated with the ground-truth signal and independent from the measurement matrix. Assuming that such an initialization is available is typically not realistic. In this paper, we solve this problem by proposing an AMP algorithm initialized with a spectral estimator. With such an initialization, the standard AMP analysis fails since the spectral estimator depends in a complicated way on the design matrix. Our main contribution is a rigorous characterization of the performance of AMP with spectral initialization in the high-dimensional limit. The key technical idea is to define and analyze a two-phase artificial AMP algorithm that first produces the spectral estimator, and then closely approximates the iterates of the true AMP. We also provide numerical results that demonstrate the validity of the proposed approach.

关键词： machine learning message-passing algorithms statistical inference learning theory

来源：评论

学校读者我要写书评

暂无评论

Survey-propagation decimation through distributed local computations -: art. no. P11016

引用

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

作者： Chavas, J Furtlehner, C Mézard, M Zecchina, R ISI I-10133 Turin Italy Univ Paris 11 Ctr Sci Orsay LPTMS F-91405 Orsay France Int Ctr Theoret Phys I-34100 Trieste Italy

We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey propagation (SP) algorithm. The first solver, called the 'SP diffusion algorithm', diffuses as dynamical information the maximum bias over the system, so that variable nodes can decide to freeze in a self-organized way, each variable making its decision on the basis of purely local information. The second solver, called the 'SP reinforcement algorithm', makes use of time-dependent external forcing messages on each variable, which are adapted in time in such a way that the algorithm approaches its estimated closest solution. Both methods allow us to find a solution of the random 3-SAT problem in a range of parameters comparable with the best previously described serialized solvers. The simulated time of convergence towards a solution ( if these solvers were implemented on a fully parallel device) grows as log(N).

关键词： heuristics message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

An exactly solvable ansatz for statistical mechanics models

引用

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

作者： Kim, Isaac H. Univ Sydney Sydney NSW Australia

We propose a family of 'exactly solvable' probability distributions to approximate partition functions of two-dimensional statistical mechanics models. While these distributions lie strictly outside the mean-field framework, their free energies can be computed in a time that scales linearly with the system size. This construction is based on a simple but nontrivial solution to the marginal problem. We formulate two non-linear constraints on the set of locally consistent marginal probabilities that simultaneously (i) ensure the existence of a consistent global probability distribution and (ii) lead to an exact expression for the maximum global entropy.

关键词： exact results numerical simulations message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Uncovering the non-equilibrium stationary properties in sparse Boolean networks

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2022年第5期2022卷 053303-053303页

作者： Torrisi, Giuseppe Kuhn, Reimer Annibale, Alessia Kings Coll London Dept Math London WC2R 2LS England

Dynamic processes of interacting units on a network are out of equilibrium in general. In the case of a directed tree, the dynamic cavity method provides an efficient tool that characterises the dynamic trajectory of the process for the linear threshold model. However, because of the computational complexity of the method, the analysis has been limited to systems where the largest number of neighbours is small. We devise an efficient implementation of the dynamic cavity method which substantially reduces the computational complexity of the method for systems with discrete couplings. Our approach opens up the possibility to investigate the dynamic properties of networks with fat-tailed degree distribution. We exploit this new implementation to study properties of the non-equilibrium steady-state. We extend the dynamic cavity approach to calculate the pairwise correlations induced by different motifs in the network. Our results suggest that just two basic motifs of the network are able to accurately describe the entire statistics of observed correlations. Finally, we investigate models defined on networks containing bi-directional interactions. We observe that the stationary state associated with networks with symmetric or anti-symmetric interactions is biased towards the active or inactive state respectively, even if independent interaction entries are drawn from a symmetric distribution. This phenomenon, which can be regarded as a form of spontaneous symmetry-breaking, is peculiar to systems formulated in terms of Boolean variables, as opposed to Ising spins.

关键词： cavity and replica method message-passing algorithms dynamical heterogeneities kinetic Ising models

来源：评论

学校读者我要写书评

暂无评论

Optimal resource allocation in random networks with transportation bandwidths

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2009年第3期2009卷 P03029-P03029页

作者： Yeung, C. H. Wong, K. Y. Michael Hong Kong Univ Sci & Technol Dept Phys Hong Kong Hong Kong Peoples R China

We apply statistical physics to study the task of resource allocation in random sparse networks with limited bandwidths for the transportation of resources along the links. Recursive relations from the Bethe approximation are converted into useful algorithms. Bottlenecks emerge when the bandwidths are small, causing an increase in the fraction of idle links. For a given total bandwidth per node, the efficiency of allocation increases with the network connectivity. In the high connectivity limit, we find a phase transition at a critical bandwidth, above which clusters of balanced nodes appear, characterized by a pro. le of homogenized resource allocation similar to the Maxwell construction.

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

来源：评论

学校读者我要写书评

暂无评论

Blind sensor calibration using approximate message passing

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2015年第11期2015卷 1-1页

作者： Schuelke, Christophe Caltagirone, Francesco Zdeborova, Lenka Univ Paris 07 Sorbonne Paris Cite F-75013 Paris France Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy Ecole Normale Super CNRS Lab Phys Stat UMR 8550 F-75231 Paris France Univ Paris 06 F-75231 Paris France CEA Saclay Inst Phys Theor F-91191 Gif Sur Yvette France CNRS URA 2306 F-91191 Gif Sur Yvette France

The ubiquity of approximately sparse data has led a variety of communities to take great interest in compressed sensing algorithms. Although these are very successful and well understood for linear measurements with additive noise, applying them to real data can be problematic if imperfect sensing devices introduce deviations from this ideal signal acquisition process, caused by sensor decalibration or failure. We propose a message passing algorithm called calibration approximate message passing (Cal-AMP) that can treat a variety of such sensor-induced imperfections. In addition to deriving the general form of the algorithm, we numerically investigate two particular settings. In the first, a fraction of the sensors is faulty, giving readings unrelated to the signal. In the second, sensors are decalibrated and each one introduces a different multiplicative gain to the measurements. Cal-AMP shares the scalability of approximate message passing, allowing us to treat large sized instances of these problems, and experimentally exhibits a phase transition between domains of success and failure.

关键词： message-passing algorithms statistical inference

来源：评论

学校读者我要写书评

暂无评论

Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control

引用

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

作者： Sakata, Ayaka Obuchi, Tomoyuki Inst Stat Math Dept Stat Inference Math Midori Cho Tachikawa Tokyo 1908562 Japan Grad Univ Adv Sci SOKENDAI Dept Stat Sci Hayama Kanagawa 2400193 Japan JST PRESTO 4-1-8 Honcho Saitama 3320012 Japan Kyoto Univ Grad Sch Informat Sakyo Ku 36 1 Yoshida Honmachi Kyoto 6068501 Japan

We consider a reconstruction problem of sparse signals from a smaller number of measurements than the dimension formulated as a minimization problem of nonconvex sparse penalties: smoothly clipped absolute deviations and minimax concave penalties. The nonconvexity of these penalties is controlled by nonconvexity parameters, and the l (1) penalty is contained as a limit with respect to these parameters. The analytically-derived reconstruction limit overcomes that of the l (1) limit and is also expected to overcome the algorithmic limit of the Bayes-optimal setting when the nonconvexity parameters have suitable values. However, for small nonconvexity parameters, where the reconstruction of the relatively dense signals is theoretically expected, the algorithm known as approximate message passing (AMP), which is closely related to the analysis, cannot achieve perfect reconstruction leading to a gap from the analysis. Using the theory of state evolution, it is clarified that this gap can be understood on the basis of the shrinkage in the basin of attraction to the perfect reconstruction and also the divergent behavior of AMP in some regions. A part of the gap is mitigated by controlling the shapes of nonconvex penalties to guide the AMP trajectory to the basin of the attraction.

关键词： analysis of algorithms cavity and replica method message-passing algorithms spin glasses

来源：评论

学校读者我要写书评

暂无评论

Lowering the error floor of Gallager codes: a statistical-mechanical view

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2014年第10期2014卷 P10042-P10042页

作者： Pretti, Marco Politecn Torino CNR ISC Dipartimento Sci Applicata & Tecnol DISAT I-10129 Turin Italy

The error correction for Gallager's low-density parity-check codes is a problem famously equivalent to that of computing marginal Boltzmann probabilities for an Ising-like model with multispin interactions in a non-uniform magnetic field. Since the graph of interactions is locally a tree, the solution is very well approximated by a generalized mean-field (Bethe-Peierls) approximation. Belief propagation (BP) and similar iterative algorithms are an efficient method to perform the calculation, but they sometimes fail to converge, or converge to non-codewords, giving rise to a non-negligible residual error probability (error floor). On the other hand, provably-convergent algorithms are far too complex to be implemented in a real decoder. In this work we consider the application of the probability-damping technique, which can be regarded either as a variant of BP, from which it retains the property of low complexity, or as an approximation of a provably-convergent algorithm, from which it is expected to inherit better convergence properties. We investigate the algorithm behaviour on a real instance of Gallager code, and compare the results with state-of-the-art algorithms.

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

来源：评论

学校读者我要写书评

暂无评论

A spin glass approach to the directed feedback vertex set problem

引用

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

作者： Zhou, Hai-Jun Chinese Acad Sci Key Lab Theoret Phys Inst Theoret Phys Zhong Guan Cun East Rd 55 Beijing 100190 Peoples R China

A directed graph (digraph) is formed by vertices and arcs (directed edges) from one vertex to another. A feedback vertex set (FVS) is a set of vertices that contains at least one vertex of every directed cycle in this digraph. The directed feedback vertex set problem aims at constructing a FVS of minimum cardinality. This is a fundamental cycle-constrained hard combinatorial optimization problem with wide practical applications. In this paper we construct a spin glass model for the directed FVS problem by converting the global cycle constraints into local arc constraints, and study this model through the replica-symmetric (RS) mean field theory of statistical physics. We then implement a belief propagation-guided decimation (BPD) algorithm for single digraph instances. The BPD algorithm slightly outperforms the simulated annealing algorithm on large random graph instances. The RS mean field results and algorithmic results can be further improved by working on a more restrictive (and more difficult) spin glass model.

关键词： spin glasses (theory) message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Classification and sparse-signature extraction from gene-expression data

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2009年第05期2009卷 P05001-P05001页

作者： Pagnani, Andrea Tria, Francesca Weigt, Martin Inst Sci Interchange I-10133 Turin Italy

In this work we suggest a statistical mechanics approach to the classification of high dimensional data according to a binary label. We propose an algorithm whose aim is twofold: first it learns a classifier from a relatively small number of data;second it extracts a sparse signature, i.e., a lower dimensional subspace carrying the information needed for classification. In particular the second part of the task is NP-hard;therefore we propose a statistical mechanics based message-passing approach. The resulting algorithm is tested on artificial data to prove its validity, but also to elucidate possible limitations. As an important application, we consider the classification of gene-expression data measured in various types of cancer tissues. We find that, despite the currently low quantity and quality of available data (the number of available samples is much smaller than the number of measured genes, thus strongly limiting the predictive capacities), the algorithm performs slightly better than many state-of-the-art approaches in bioinformatics.

关键词： cavity and replica method gene expression and regulation (theory) message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：