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

message-passing algorithms and Improved LP Decoding

IEEE TRANSACTIONS ON INFORMATION THEORY 2012年第12期58卷 7260-7271页

作者： Arora, Sanjeev Daskalakis, Constantinos Steurer, David Princeton Univ Dept Comp Sci Princeton NJ 08540 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA Cornell Univ Dept Comp Sci Ithaca NY 14850 USA

Linear programming (LP) decoding for low-density parity-check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance-coming close to that of iterative decoding algorithms-and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05 fraction of correctable errors for rate-1/2 codes;this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a "locally optimal" solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a "reweighted" version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.

关键词： Linear programming (LP) decoding low-density parity-check (LDPC) codes message-passing algorithms min-sum algorithm

来源：评论

学校读者我要写书评

暂无评论

message-passing algorithms for Inference and Optimization "Belief Propagation" and "Divide and Concur"

引用

JOURNAL OF STATISTICAL PHYSICS 2011年第4期145卷 860-890页

作者： Yedidia, Jonathan S. Disney Res Boston Cambridge MA 02142 USA

message-passing algorithms can solve a wide variety of optimization, inference, and constraint satisfaction problems. The algorithms operate on factor graphs that visually represent and specify the structure of the problems. After describing some of their applications, I survey the family of belief propagation (BP) algorithms, beginning with a detailed description of the min-sum algorithm and its exactness on tree factor graphs, and then turning to a variety of more sophisticated BP algorithms, including free-energy based BP algorithms, "splitting" BP algorithms that generalize "tree-reweighted" BP, and the various BP algorithms that have been proposed to deal with problems with continuous variables. The Divide and Concur (DC) algorithm is a projection-based constraint satisfaction algorithm that deals naturally with continuous variables, and converges to exact answers for problems where the solution sets of the constraints are convex. I show how it exploits the "difference-map" dynamics to avoid traps that cause more naive alternating projection algorithms to fail for non-convex problems, and explain that it is a message-passing algorithm that can also be applied to optimization problems. The BP and DC algorithms are compared, both in terms of their fundamental justifications and their strengths and weaknesses.

关键词： message-passing algorithms Factor graphs Belief propagation Divide and concur Difference-map Optimization Inference Constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

message-passing algorithms and Improved LP Decoding

Message-Passing Algorithms and Improved LP Decoding

引用

41st Annual ACM Symposium on Theory of Computing

作者： Arora, Sanjeev Daskalakis, Constantinos Steurer, David Princeton Univ Princeton NJ 08544 USA

ISBN: (纸本)9781605586137

Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance -coming close to that of iterative decoding algorithms- and its amenability of finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes;this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. unlike other techniques, our analysis directly works with the primal linear program and exploits and explicit connection between LP decoding and message passing algorithms. An interesting byproduct of our method is a notion of a "locally optimal" solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a "re-weighted" version of the min-sum algorithm, obviating the need for linear programming. Our analysis implies, in particular, that this re-weighted version of the min-sum decoder corrects up to a 0.05-fraction of errors.

关键词： LDPC codes LP decoding min-sum algorithm message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

An integrated CSP-based tool for the visualisation, animation and performance evaluation of message passing algorithms 3

An integrated CSP-based tool for the visualisation, animatio...

引用

3rd IEEE International Conference on Formal Engineering Methods

作者： Abdallah, AE Green, M S Bank Univ Sch Comp Informat & Math Ctr Appl Formal Methods London SE1 0AA England

ISBN: (纸本)0769508227

This paper presents ongoing research and development on an integrated tool for the visualisation and animation of message-passing communicating systems described in Hoare's CSP (Communicating Sequential Processes). It introduces major new developments to the original VisualNets implemented in C++ and reported in [4]. The new tool is implemented partly in Java and partly in the functional programming language Haskell. Nor only does the new tool enjoy greater expressive power and a better user interface, it has new capabilities for aiding the user in animating, analysing, and reasoning about CSP specifications. These includes provisions for nested parallelism within a single node, improved profiling and animation, and the possibility of applying generic timing cast models for performance evaluation. The paper briefly describes the new features, explains the methods by which they have been implemented and illustrates their use with examples.

关键词： Communicating Sequential Processes visualisation animation performance evaluation message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Analysis of random sequential message passing algorithms for approximate inference

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2022年第7期2022卷 073401-073401页

作者： Cakmak, Burak Lu, Yue M. Opper, Manfred Tech Univ Berlin Artificial Intelligence Grp D-10587 Berlin Germany Harvard Univ John Paulson Sch Engn & Appl Sci Cambridge MA 02138 USA Univ Birmingham Ctr Syst Modelling & Quantitat Biomed Birmingham B15 2TT W Midlands England

We analyze the dynamics of a random sequential message passing algorithm for approximate inference with large Gaussian latent variable models in a student-teacher scenario. To model nontrivial dependencies between the latent variables, we assume random covariance matrices drawn from rotation invariant ensembles. Moreover, we consider a model mismatching setting, where the teacher model and the one used by the student may be different. By means of dynamical functional approach, we obtain exact dynamical mean-field equations characterizing the dynamics of the inference algorithm. We also derive a range of model parameters for which the sequential algorithm does not converge. The boundary of this parameter range coincides with the de Almeida Thouless (AT) stability condition of the replica-symmetric ansatz for the static probabilistic model.

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

来源：评论

学校读者我要写书评

暂无评论

Random field Ising model in two dimensions: Bethe approximation, cluster variational method and message passing algorithms

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2015年第7期000卷 P07003-P07003页

作者： Dominguez, Eduardo Lage-Castellanos, Alejandro Mulet, Roberto Univ Havana Fac Phys Henri Poincare Grp Complex Syst Havana 10400 Cuba Univ Havana Dept Theoret Phys Fac Phys Havana 10400 Cuba

We study two free energy approximations (Bethe and plaquette-CVM) for the Random Field Ising Model in two dimensions. We compare results obtained by these two methods in single instances of the model on the square grid, showing the difficulties arising in defining a robust critical line. We also attempt average case calculations using a replica-symmetric ansatz, and compare the results with single instances. Both, Bethe and plaquette-CVM approximations present a similar panorama in the phase space, predicting long range order at low temperatures and fields. We show that plaquette-CVM is more precise, in the sense that predicts a lower critical line (the truth being no line at all). Furthermore, we give some insight on the non-trivial structure of the fixed points of different message passing algorithms. A study of the Monte Carlo dynamics for an arbitrary sample shows that GBP states are very well correlated with states that are attractors of the stochastic dynamics.

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

来源：评论

学校读者我要写书评

暂无评论

Analysis of high-dimensional Gaussian labeled-unlabeled mixture model via message-passing algorithm

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2025年第3期2025卷 033404-033404页

作者： Gu, Xiaosi Obuchi, Tomoyuki Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan

Semi-supervised learning (SSL) is a machine learning methodology that leverages unlabeled data in conjunction with a limited amount of labeled data. Although SSL has been applied in various applications and its effectiveness has been empirically demonstrated, it is still not fully understood when and why SSL performs well. Several existing theoretical studies have attempted to address this issue by modeling classification problems using the so-called Gaussian mixture model (GMM). These studies provide notable and insightful interpretations. However, their analyses are focused on specific purposes, and a thorough investigation of the properties of GMM in the context of SSL has been lacking. In this paper, we conduct a detailed analysis of the properties of the high-dimensional GMM for binary classification in the SSL setting. To this end, we employ the approximate message-passing and state evolution methods, which are widely used in high-dimensional settings and originate from statistical mechanics. We deal with two estimation approaches: the Bayesian one and the & ell;(2)-regularized maximum likelihood estimation (RMLE). We conduct a comprehensive comparison of these two approaches, examining aspects such as the global phase diagram, estimation error for the parameters, and prediction error for the labels. A specific comparison is made between the Bayes-optimal (BO) estimator and RMLE, as the BO setting provides the optimal estimation performance and is ideal as a benchmark. Our analysis shows that with appropriate regularizations, RMLE can achieve a near-optimal performance in terms of both the estimation error and prediction error, especially when there is a large amount of unlabeled data. These results demonstrate that the & ell;(2) regularization term plays an effective role in estimation and prediction in SSL approaches.

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

来源：评论

学校读者我要写书评

暂无评论

Loop corrections for hard spheres in Hamming space

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2025年第3期2025卷 033401-033401页

作者： Ramezanpour, Abolfazl Moghimi-Araghi, Saman Shiraz Univ Coll Sci Dept Phys Shiraz 71454 Iran Leiden Univ Fac Sci Leiden Acad Ctr Drug Res Med Syst Biophys & Bioengn Leiden Netherlands Sharif Univ Technol Phys Dept POB 11155-9161 Tehran Iran

We begin with an exact expression for the entropy of a system of hard spheres within the Hamming space. This entropy relies on probability marginals, which are determined by an extended set of belief propagation (BP) equations. The BP probability marginals are functions of auxiliary variables that are introduced to model the effects of loopy interactions on a tree-structured interaction graph. We explore various reasonable and approximate probability distributions, ensuring that they align with the exact solutions of the BP equations. Our approach is based on an ansatz for (in)homogeneous cavity marginals respecting the permutation symmetry of the problem. Through a thorough analysis, we aim to minimize errors in the BP equations. Our findings support the conjecture that the maximum packing density asymptotically conforms to the lower bound proposed by Gilbert and Varshamov. The presented formulation of the problem is useful to obtain upper bounds for the packing entropy within a class of BP probability marginals. Moreover, it enables different approximations in both the structure of BP messages and the role of auxiliary variables.

关键词： cavity and replica method glasses (colloidal polymer etc) error-correcting codes message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Energy-Saving Cellular Network Management Using message-passing

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2017年第1期66卷 635-644页

作者： Lee, Sang Hyun Sohn, Illsoo Pusan Natl Univ Dept Elect Engn Busan 46241 South Korea Gachon Univ Dept Elect Engn Seongnam 13120 South Korea

This paper presents a distributed energy-saving management strategy for green cellular networks. During off-peak periods, an energy-saving operation is activated. A subset of base stations (BSs) in the network enters an energy-saving state, i.e., switched-off mode, while satisfying traffic demands without discontinuity of user services. To this end, the remaining operating BSs should compensate for the coverage holes by taking over the responsibility of user service. Such a scenario can be formulated into a combinatorial optimization that maximizes the overall energy savings of the network. To address this computationally demanding task, we develop a distributed algorithm that provides an efficient solution by using a state-of-the-art technique based on amessage-passing framework. The simulation results confirm considerable energy-saving gains over previously existing techniques and prove the viability for this strategy for self-organizing green cellular networks.

关键词： Energy-saving management green cellular networks message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Principled Graph Matching algorithms for Integrating Multiple Data Sources

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2015年第10期27卷 2784-2796页

作者： Zhang, Duo Rubinstein, Benjamin I. P. Gemmell, Jim Twitter San Francisco CA 94103 USA Univ Melbourne Dept Comp & Informat Syst Parkville Vic 3010 Australia Trov Danville CA 94526 USA

This paper explores combinatorial optimization for problems of max-weight graph matching on multi-partite graphs, which arise in integrating multiple data sources. In the most common two-source case, it is often desirable for the final matching to be one-to-one;the database and statistical record linkage communities accomplish this by weighted bipartite graph matching on similarity scores. Such matchings are intuitively appealing: they leverage a natural global property of many real-world entity stores-that of being nearly deduped-and are known to provide significant improvements to precision and recall. Unfortunately, unlike the bipartite case, exact max-weight matching on multi-partite graphs is known to be NP-hard. Our two-fold algorithmic contributions approximate multi-partite max-weight matching: our first algorithm borrows optimization techniques common to Bayesian probabilistic inference;our second is a greedy approximation algorithm. In addition to a theoretical guarantee on the latter, we present comparisons on a real-world entity resolution problem from Bing significantly larger than typically found in the literature, on publication data, and on a series of synthetic problems. Our results quantify significant improvements due to exploiting multiple sources, which are made possible by global one-to-one constraints linking otherwise independent matching sub-problems. We also discover that our algorithms are complementary: one being much more robust under noise, and the other being simple to implement and very fast to run.

关键词： Data integration weighted graph matching message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：