IRIS Pol. Torinohttps://iris.polito.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Thu, 17 Oct 2019 10:54:35 GMT2019-10-17T10:54:35Z1071Local entropy as a measure for sampling solutions in constraint satisfaction problemshttp://hdl.handle.net/11583/2635495Titolo: Local entropy as a measure for sampling solutions in constraint satisfaction problems
Abstract: We introduce a novel entropy-driven Monte Carlo (EdMC) strategy to efficiently sample solutions of random constraint satisfaction problems (CSPs). First, we extend a recent result that, using a large-deviation analysis, shows that the geometry of the space of solutions of the binary perceptron learning problem (a prototypical CSP), contains regions of very high-density of solutions. Despite being sub-dominant, these regions can be found by optimizing a local entropy measure. Building on these results, we construct a fast solver that relies exclusively on a local entropy estimate, and can be applied to general CSPs. We describe its performance not only for the perceptron learning problem but also for the random K-satisfiabilty problem (another prototypical CSP with a radically different structure), and show numerically that a simple zero-temperature Metropolis search in the smooth local entropy landscape can reach sub-dominant clusters of optimal solutions in a small number of steps, while standard Simulated Annealing either requires extremely long cooling procedures or just fails. We also discuss how the EdMC can heuristically be made even more efficient for the cases we studied.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11583/26354952016-01-01T00:00:00ZUnreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemeshttp://hdl.handle.net/11583/2660985Titolo: Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes
Abstract: In artificial neural networks, learning from data is a computationally demanding task in which a large number of connection weights are iteratively tuned through stochastic-gradient-based heuristic processes over a cost function. It is not well understood how learning occurs in these systems, in particular how they avoid getting trapped in configurations with poor computational performance. Here, we study the difficult case of networks with discrete weights, where the optimization landscape is very rough even for simple architectures, and provide theoretical and numerical evidence of the existence of rare-but extremely dense and accessible-regions of configurations in the network weight space. We define a measure, the robust ensemble (RE), which suppresses trapping by isolated configurations and amplifies the role of these dense regions. We analytically compute the RE in some exactly solvable models and also provide a general algorithmic scheme that is straightforward to implement: define a cost function given by a sum of a finite number of replicas of the original cost function, with a constraint centering the replicas around a driving assignment. To illustrate this, we derive several powerful algorithms, ranging from Markov Chains to message passing to gradient descent processes, where the algorithms target the robust dense states, resulting in substantial improvements in performance. The weak dependence on the number of precision bits of the weights leads us to conjecture that very similar reasoning applies to more conventional neural networks. Analogous algorithmic schemes can also be applied to other optimization problems.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11583/26609852016-01-01T00:00:00ZThe patient-zero problem with noisy observationshttp://hdl.handle.net/11583/2587161Titolo: The patient-zero problem with noisy observations
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11583/25871612014-01-01T00:00:00ZInference of causality in epidemics on temporal contact networkshttp://hdl.handle.net/11583/2656874Titolo: Inference of causality in epidemics on temporal contact networks
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11583/26568742016-01-01T00:00:00ZSubdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapseshttp://hdl.handle.net/11583/2634623Titolo: Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11583/26346232015-01-01T00:00:00ZStatistical Mechanics Approach to Inverse Problems on Networkshttp://hdl.handle.net/11583/2641787Titolo: Statistical Mechanics Approach to Inverse Problems on Networks
Abstract: Statistical Mechanics has gained a central role in modern Inference and Computer Science. Many optimization and inference problems can be cast in a Statistical Mechanics framework, and various concepts and methods developed in this area of Physics can be very helpful not only in the theoretical analysis, but also constitute valuable tools for solving single instance cases of hard inference and computational tasks. In this work, I address various inverse problems on networks, from models of epidemic spreading to learning in neural networks, and apply a variety of methods which have been developed in the context of Disordered Systems, namely Replica and Cavity methods from the theoretical side, and their algorithmic incarnation, Belief Propagation, to solve hard inverse problems which can be formulated in a Bayesian framework.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11583/26417872016-01-01T00:00:00ZNetwork reconstruction from infection cascadeshttp://hdl.handle.net/11583/2741836Titolo: Network reconstruction from infection cascades
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11583/27418362019-01-01T00:00:00Z