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

Clusters of solutions and replica symmetry breaking in random k-satisfi ability

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2008年第04期2008卷 P04004-P04004页

作者： Montanari, Andrea Ricci-Tersenghi, Federico Semerjian, Guilhem Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Stat Stanford CA 94305 USA Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy Univ Roma La Sapienza CNR INFM I-00185 Rome Italy Univ Paris 06 CNRS UMR 8549 LPTENS F-75231 Paris 05 France Univ Paris 06 ENS Associee UPMC F-75231 Paris 05 France

We study the set of solutions of random k-satisfiability formulas through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We re. ne substantially this picture by: (i) determining the precise location of the clustering transition;(ii) uncovering a second 'condensation' phase transition in the structure of the solution set for k >= 4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m = 1 via a correspondence with the tree reconstruction problem) and new large-k expansions.

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

来源：评论

学校读者我要写书评

暂无评论

Inference algorithms for gene networks: a statistical mechanics analysis

引用

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

作者： Braunstein, A. Pagnani, A. Weigt, M. Zecchina, R. Inst Sci Interchange I-10133 Turin Italy Politecn Torino I-10129 Turin Italy

The inference of gene regulatory networks from high throughput gene expression data is one of the major challenges in systems biology. This paper aims at analysing and comparing two different algorithmic approaches. The first approach uses pairwise correlations between regulated and regulating genes;the second one uses message-passing techniques for inferring activating and inhibiting regulatory interactions. The performance of these two algorithms can be analysed theoretically on well-defined test sets, using tools from the statistical physics of disordered systems like the replica method. We find that the second algorithm outperforms the first one since it takes into account collective effects of multiple regulators.

关键词： cavity and replica method regulatory networks (theory) message-passing algorithms genomic and proteomic networks

来源：评论

学校读者我要写书评

暂无评论

Approximate inference techniques with expectation constraints

引用

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

作者： Heskes, T Opper, M Wiegerinck, W Winther, O Zoeter, O Radboud Univ Nijmegen SNN Nijmegen Netherlands Univ Southampton Sch Elect & Comp Sci ISIS Southampton SO9 5NH Hants England Tech Univ Denmark DK-2800 Lyngby Denmark

This paper discusses inference problems in probabilistic graphical models that often occur in a machine learning setting. In particular it presents a unified view of several recently proposed approximation schemes. Expectation consistent approximations and expectation propagation are both shown to be related to Bethe free energies with weak consistency constraints, i.e. free energies where local approximations are only required to agree on certain statistics instead of full marginals.

关键词： analysis of algorithms message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

The patient-zero problem with noisy observations

引用

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

作者： Altarelli, Fabrizio Braunstein, Alfredo Dall'Asta, Luca Ingrosso, Alessandro Zecchina, Riccardo 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

A belief propagation approach has been recently proposed for the patient-zero problem in SIR epidemics. The patient-zero problem consists of finding the initial source of an epidemic outbreak given observations at a later time. In this work, we study a more difficult but related inference problem, in which observations are noisy and there is confusion between observed states. In addition to studying the patient-zero problem, we also tackle the problem of completing and correcting the observations to possibly find undiscovered infected individuals and false test results. Moreover, we devise a set of equations, based on the variational expression of the Bethe free energy, to find the patient-zero along with maximum-likelihood epidemic parameters. We show, by means of simulated epidemics, that this method is able to infer details on the past history of an epidemic outbreak based solely on the topology of the contact network and a single snapshot of partial and noisy observations.

关键词： message-passing algorithms network dynamics epidemic modelling statistical inference

来源：评论

学校读者我要写书评

暂无评论

Fermions and loops on graphs: I. Loop calculus for determinants

引用

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

作者： Chernyak, Vladimir Y. Chertkov, Michael Wayne State Univ Dept Chem Detroit MI 48202 USA Los Alamos Natl Lab Div Theoret Los Alamos NM 87545 USA Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA

This paper is the first in a series devoted to evaluation of the partition function in statistical models on graphs with loops in terms of the Berezin/fermion integrals. The paper focuses on a representation of the determinant of a square matrix in terms of a finite series, where each term corresponds to a loop on the graph. The representation is based on a fermion version of the loop calculus, previously introduced by the authors for graphical models with finite alphabets. Our construction contains two levels. First, we represent the determinant in terms of an integral over anti-commuting Grassmann variables, with some reparametrization/gauge freedom hidden in the formulation. Second, we show that a special choice of the gauge, called the BP (Bethe-Peierls or belief propagation) gauge, yields the desired loop representation. The set of gauge. xing BP conditions is equivalent to the Gaussian BP equations, discussed in the past as efficient (linear scaling) heuristics for estimating the covariance of a sparse positive matrix.

关键词： rigorous results in statistical mechanics message-passing algorithms gauge theories

来源：评论

学校读者我要写书评

暂无评论

Comparative study for inference of hidden classes in stochastic block models

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2012年第12期2012卷 P12021-P12021页

作者： Zhang, Pan Krzakala, Florent Reichardt, Joerg Zdeborova, Lenka CNRS F-75005 Paris France ESPCI ParisTech UMR Gulliver 7083 F-75005 Paris France Univ Wurzburg Inst Theoret Phys D-97074 Wurzburg Germany CEA Saclay Inst Phys Theor IPhT F-91191 Gif Sur Yvette France CENS Lab Leon Brillouin CNRS URA 2306 F-91191 Gif Sur Yvette France

Inference of hidden classes in stochastic block models is a classical problem with important applications. Most commonly used methods for this problem involve naive mean field approaches or heuristic spectral methods. Recently, belief propagation was proposed for this problem. In this contribution we perform a comparative study between the three methods on synthetically created networks. We show that belief propagation shows much better performance when compared to naive mean field and spectral approaches. This applies to accuracy, computational efficiency and the tendency to overfit the data.

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

来源：评论

学校读者我要写书评

暂无评论

The computational core and fixed point organization in Boolean networks

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2006年第3期2006卷 P03002-P03002页

作者： Correale, L Leone, M Pagnani, A Weigt, M Zecchina, R Politecn Torino I-10129 Turin Italy ISI Fdn I-10133 Turin Italy Abdus Salaam Int Ctr Theoret Phys I-34100 Trieste Italy

In this paper, we analyse large random Boolean networks in terms of a constraint satisfaction problem. We first develop an algorithmic scheme which allows us to prune simple logical cascades and underdetermined variables, returning thereby the computational core of the network. Second, we apply the cavity method to analyse the number and organization of fixed points. We find in particular a phase transition between an easy and a complex regulatory phase, the latter being characterized by the existence of an exponential number of macroscopically separated fixed point clusters. The different techniques developed are reinterpreted as algorithms for the analysis of single Boolean networks, and they are applied in the analysis of and in silico experiments on the gene regulatory networks of baker's yeast ( Saccharomyces cerevisiae) and the segment-polarity genes of the fruitfly Drosophila melanogaster.

关键词： regulatory networks (theory) message-passing algorithms random graphs networks genomic and protemic networks

来源：评论

学校读者我要写书评

暂无评论

Reconstruction of financial networks for robust estimation of systemic risk

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2012年第3期2012卷 P03011-P03011页

作者： Mastromatteo, Iacopo Zarinelli, Elia Marsili, Matteo Scuola Int Super Studi Avanzati I-34014 Trieste Italy CNRS LPTMS F-91405 Orsay France Univ Paris 11 UMR8626 F-91405 Orsay France Abdus Salam Int Ctr Theoret Phys I-34014 Trieste Italy

In this paper we estimate the propagation of liquidity shocks through interbank markets when the information about the underlying credit network is incomplete. We show that techniques such as maximum entropy currently used to reconstruct credit networks severely underestimate the risk of contagion by assuming a trivial (fully connected) topology, a type of network structure which can be very different from the one empirically observed. We propose an efficient message-passing algorithm to explore the space of possible network structures and show that a correct estimation of the network degree of connectedness leads to more reliable estimations for systemic risk. Such an algorithm is also able to produce maximally fragile structures, providing a practical upper bound for the risk of contagion when the actual network structure is unknown. We test our algorithm on ensembles of synthetic data encoding some features of real financial networks (sparsity and heterogeneity), finding that more accurate estimations of risk can be achieved. Finally we find that this algorithm can be used to control the amount of information that regulators need to require from banks in order to sufficiently constrain the reconstruction of financial networks.

关键词： message-passing algorithms financial instruments and regulation risk measure and management network reconstruction

来源：评论

学校读者我要写书评

暂无评论

Path integral based convolution and pooling for graph neural networks*

引用

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

作者： Ma, Zheng Xuan, Junyu Wang, Yu Guang Li, Ming Lio, Pietro Princeton Univ Dept Phys Princeton NJ 08544 USA Univ Technol Sydney Fac Engn & Informat Technol Ctr Artificial Intelligence Sydney NSW Australia Univ New South Wales Max Planck Inst Math Sci Sydney NSW Australia Univ New South Wales Sch Math & Stat Sydney NSW Australia Zhejiang Normal Univ Dept Educ Technol Jinhua Zhejiang Peoples R China Univ Cambridge Dept Comp Sci & Technol Cambridge England

Graph neural networks (GNNs) extend the functionality of traditional neural networks to graph-structured data. Similar to CNNs, an optimized design of graph convolution and pooling is key to success. Borrowing ideas from physics, we propose path integral-based GNNs (PAN) for classification and regression tasks on graphs. Specifically, we consider a convolution operation that involves every path linking the message sender and receiver with learnable weights depending on the path length, which corresponds to the maximal entropy random walk. It generalizes the graph Laplacian to a new transition matrix that we call the maximal entropy transition (MET) matrix derived from a path integral formalism. Importantly, the diagonal entries of the MET matrix are directly related to the subgraph centrality, thus leading to a natural and adaptive pooling mechanism. PAN provides a versatile framework that can be tailored for different graph data with varying sizes and structures. We can view most existing GNN architectures as special cases of PAN. Experimental results show that PAN achieves state-of-the-art performance on various graph classification/regression tasks, including a new benchmark dataset from statistical mechanics that we propose to boost applications of GNN in physical sciences.

关键词： deep learning inference of graphical models message-passing algorithms random ordered microstructures

来源：评论

学校读者我要写书评

暂无评论

Loop series for discrete statistical models on graphs

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2006年第6期2006卷 P06009-P06009页

作者： Chertkov, Michael Chernyak, Vladimir Y. LANL Div Theoret Los Alamos NM 87545 USA LANL Ctr Nonlinear Studies Los Alamos NM 87545 USA Wayne State Univ Dept Chem Detroit MI 48202 USA

In this paper we present the derivation details, logic, and motivation for the three loop calculus introduced in Chertkov and Chernyak (2006 Phys. Rev. E 73 065102(R)). Generating functions for each of the three interrelated discrete statistical models are expressed in terms of a finite series. The first term in the series corresponds to the Bethe - Peierls belief - propagation (BP) contribution;the other terms are labelled by loops on the factor graph. All loop contributions are simple rational functions of spin correlation functions calculated within the BP approach. We discuss two alternative derivations of the loop series. One approach implements a set of local auxiliary integrations over continuous fields with the BP contribution corresponding to an integrand saddle-point value. The integrals are replaced by sums in the complementary approach, briefly explained in Chertkov and Chernyak (2006 Phys. Rev. E 73 065102(R)). Local gauge symmetry transformations that clarify an important invariant feature of the BP solution are revealed in both approaches. The individual terms change under the gauge transformation while the partition function remains invariant. The requirement for all individual terms to be nonzero only for closed loops in the factor graph (as opposed to paths with loose ends) is equivalent to. xing the first term in the series to be exactly equal to the BP contribution. Further applications of the loop calculus to problems in statistical physics, computer and information sciences are discussed.

关键词： rigorous results in statistical mechanics analysis of algorithms exact results message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：