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

On tuning a mean-field model for semi-supervised classification

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

作者： Bergamim, Emilio Breve, Fabricio UNESP Inst Geociencias & Ciencias Exatas Ave 24A 1515 Rio Claro SP Brazil

Semi-supervised learning (SSL) has become an interesting research area due to its capacity for learning in scenarios where both labeled and unlabeled data are available. In this work, we focus on the task of transduction-when the objective is to label all data presented to the learner-with a mean-field approximation to the Potts model. Aiming at this particular task we study how classification results depend on beta and find that the optimal phase depends highly on the amount of labeled data available. In the same study, we also observe that more stable classifications regarding small fluctuations in beta are related to configurations of high probability and propose a tuning approach based on such observation. This method relies on a novel parameter gamma and we then evaluate two different values of the said quantity in comparison with classical methods in the field. This evaluation is conducted by changing the amount of labeled data available and the number of nearest neighbors in the similarity graph. Empirical results show that the tuning method is effective and allows NMF to outperform other approaches in datasets with fewer classes. In addition, one of the chosen values for gamma also leads to results that are more resilient to changes in the number of neighbors, which might be of interest to practitioners in the field of SSL.

关键词： machine learning inference of graphical models message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Palette-colouring: a belief propagation approach

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2011年第5期2011卷 P05010-P05010页

作者： Pelizzola, Alessandro Pretti, Marco van Mourik, Jort Politecn Torino CNR Ist Sistemi Complessi I-10129 Turin Italy Politecn Torino CNISM Dipartimento Fis I-10129 Turin Italy Politecn Torino Ctr Computat Studies I-10129 Turin Italy INFN Sez Torino I-10125 Turin Italy HuGeF Torino I-10126 Turin Italy

We consider a variation of the prototype combinatorial optimization problem known as graph colouring. Our optimization goal is to colour the vertices of a graph with a fixed number of colours, in a way to maximize the number of different colours present in the set of nearest neighbours of each given vertex. This problem, which we pictorially call palette-colouring, has been recently addressed as a basic example of a problem arising in the context of distributed data storage. Even though it has not been proved to be NP-complete, random search algorithms find the problem hard to solve. Heuristics based on a naive belief propagation algorithm are observed to work quite well in certain conditions. In this paper, we build upon the mentioned result, working out the correct belief propagation algorithm, which needs to take into account the many-body nature of the constraints present in this problem. This method improves the naive belief propagation approach at the cost of increased computational effort. We also investigate the emergence of a satisfiable-to-unsatisfiable 'phase transition' as a function of the vertex mean degree, for different ensembles of sparse random graphs in the large size ('thermodynamic') limit.

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

来源：评论

学校读者我要写书评

暂无评论

Universality laws for Gaussian mixtures in generalized linear models

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2024年第10期2024卷 104015-104015页

作者： Dandi, Yatin Stephan, Ludovic Krzakala, Florent Loureiro, Bruno Zdeborova, Lenka Ecole Polytech Fed Lausanne IdePHICS Lab CH-1015 Lausanne Switzerland ENS Dept Informat PSL F-75230 Paris 05 France CNRS F-75230 Paris 05 France Ecole Polytech Fed Lausanne SPOC Lab CH-1015 Lausanne Switzerland

Let (xi,yi)i=1,...,n denote independent samples from a general mixture distribution Sigma c is an element of C rho cPcx, and consider the hypothesis class of generalized linear models (y) over cap =F(Theta inverted perpendicular x). In this study, we investigate the asymptotic joint statistics of a family of generalized linear estimators (Theta 1,...,Theta M) obtained either from (a) minimizing an empirical risk (R) over capn(Theta;X,y) or (b) sampling from the associated Gibbs measure exp(-beta n (R) over capn(Theta;X,y)). Our main contribution is to characterize under which conditions the asymptotic joint statistics of this family depends (in a weak sense) only on the means and covariances of the class conditional features distribution Pcx. In particular, this allows us to prove the universality of different quantities of interest, such as the training and generalization errors, redeeming a recent line of work in high-dimensional statistics working under the Gaussian mixture hypothesis. Finally, we discuss the applications of our results in different machine learning tasks of interest, such as ensembling and uncertainty quantification.

关键词： deep learning learning theory message-passing algorithms network dynamics

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 cavity approach for Steiner trees packing problems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2018年第12期2018卷 123401-123401页

作者： Braunsteinh, Alfredo Muntoni, Anna Paola Politecn Torino DISAT Corso Duca Abruzzi 24 Turin Italy Italian Inst Genet Med HuGeF Via Nizza 52 Turin Italy Coll Carlo Alberto Via Real Coll 1 Moncalieri Italy INFN Sez Torino Via P Giuria 1 I-10125 Turin Italy PSL Univ Sorbonne Univ Dept Phys ENS Lab Phys TheorEcole Normale SuperCNRS F-75005 Paris France

The belief propagation approximation, or cavity method, has been recently applied to several combinatorial optimization problems in its zero-temperature implementation, the max-sum algorithm. In particular, recent developments to solve the edge-disjoint paths problem and the prize-collecting Steiner tree problem on graphs have shown remarkable results for several classes of graphs and for benchmark instances. Here we propose a generalization of these techniques for two variants of the Steiner trees packing problem where multiple 'interacting' trees have to be sought within a given graph. Depending on the interaction among trees we distinguish the vertex-disjoint Steiner trees problem, where trees cannot share nodes, from the edge-disjoint Steiner trees problem, where edges cannot be shared by trees but nodes can be members of multiple trees. Several practical problems of huge interest in network design can be mapped into these two variants, for instance, the physical design of very large scale integration (VLSI) chips. The formalism described here relies on two components edge-variables that allows us to formulate a massage-passing algorithm for the V-DStP and two algorithms for the E-DStP differing in the scaling of the computational time with respect to some relevant parameters. We will show that through one of the two formalisms used for the edge-disjoint variant it is possible to map the max-sum update equations into a weighted maximum matching problem over proper bipartite graphs. We developed a heuristic procedure based on the max-sum equations that shows excellent performance in synthetic networks (in particular outperforming standard multi-step greedy procedures by large margins) and on large benchmark instances of VLSI for which the optimal solution is known, on which the algorithm found the optimum in two cases and the gap to optimality was never larger than 4%.

关键词： message-passing algorithms optimization over networks

来源：评论

学校读者我要写书评

暂无评论

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卷 L06001-L06001页

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

来源：评论

学校读者我要写书评

暂无评论

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

引用

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

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

来源：评论

学校读者我要写书评

暂无评论

Detection and localization of change points in temporal networks with the aid of stochastic block models

引用

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

作者： De Ridder, Simon Vandermarliere, Benjamin Ryckebusch, Jan Univ Ghent Dept Informat Technol Ghent Belgium Univ Ghent Dept Phys & Astron Ghent Belgium Univ Ghent Dept Gen Econ Ghent Belgium

A framework based on generalized hierarchical random graphs (GHRGs) for the detection of change points in the structure of temporal networks has recently been developed by Peel and Clauset (2015 Proc. 29th AAAI Conf. on Artificial Intelligence). We build on this methodology and extend it to also include the versatile stochastic block models (SBMs) as a parametric family for reconstructing the empirical networks. We use five different techniques for change point detection on prototypical temporal networks, including empirical and synthetic ones. We find that none of the considered methods can consistently outperform the others when it comes to detecting and locating the expected change points in empirical temporal networks. With respect to the precision and the recall of the results of the change points, we find that the method based on a degree-corrected SBM has better recall properties than other dedicated methods, especially for sparse networks and smaller sliding time window widths.

关键词： message-passing algorithms Network dynamics Random graphs Networks Statistical inference

来源：评论

学校读者我要写书评

暂无评论

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卷 L06001-L06001页

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：