A Max-Sum algorithm for training discrete neural networks

DOI10.1088/1742-5468/2015/08/P08008MaRDI QIDQ3302364zbMATH OpenFDO

Authors Carlo Baldassi, Alfredo Braunstein

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.05401

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We present an efficient learning algorithm for the problem of training neural networks with discrete synapses, a well-known hard (NP-complete) discrete optimization problem. The algorithm is a variant of the so-called Max-Sum (MS) algorithm. In particular, we show how, for bounded integer weights with $q$ distinct states and independent concave a priori distribution (e.g. $l_1$ regularization), the algorithm's time complexity can be made to scale as $Oleft(NlogNight)$ per node update, thus putting it on par with alternative schemes, such as Belief Propagation (BP), without resorting to approximations. Two special cases are of particular interest: binary synapses $Win-1,1$ and ternary synapses $Win-1,0,1$ with $l_0$ regularization. The algorithm we present performs as well as BP on binary perceptron learning problems, and may be better suited to address the problem on fully-connected two-layer networks, since inherent symmetries in two layer networks are naturally broken using the MS approach.

Recommendations

• scientific article; zbMATH DE number 1191259
• Maximum principle based algorithms for deep learning
• scientific article; zbMATH DE number 910890
• A neural algorithm for the maximum clique problem: Analysis, experiments, and circuit implementation
• Neural network architectures for selecting the maximum input

Cites work

• A CDMA multiuser detection algorithm on the basis of belief propagation
• A review of combinatorial problems arising in feedforward neural network design
• Generalization learning in a perceptron with binary synapses
• scientific article; zbMATH DE number 3214054 (Why is no real title available?)
• Information, Physics, and Computation
• Learning representations by back-propagating errors
• Network calculus. A theory of deterministic queueing systems for the Internet
• Optimizing spread dynamics on graphs by message passing
• Statistical mechanics of learning

Cited in

(8)

• GXNOR-Net: training deep neural networks with ternary weights and activations without full-precision memory under a unified discretization framework
• Discriminative training of feed-forward and recurrent sum-product networks by extended Baum-Welch
• Local entropy as a measure for sampling solutions in constraint satisfaction problems
• scientific article; zbMATH DE number 1191259 (Why is no real title available?)
• Clustering of solutions in the symmetric binary perceptron
• On the atypical solutions of the symmetric binary perceptron
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Overlap gap and computational thresholds in the square wave perceptron

This page was built for publication: A Max-Sum algorithm for training discrete neural networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302364)