IRIS Pol. Torinohttps://iris.polito.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Mon, 16 Sep 2019 03:57:57 GMT2019-09-16T03:57:57Z10221Local 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:00ZA method to reduce the rejection rate in Monte Carlo Markov chainshttp://hdl.handle.net/11583/2671514Titolo: A method to reduce the rejection rate in Monte Carlo Markov chains
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11583/26715142017-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:00ZEfficient supervised learning in networks with binary synapseshttp://hdl.handle.net/11583/1818195Titolo: Efficient supervised learning in networks with binary synapses
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11583/18181952007-01-01T00:00:00ZTheory and learning protocols for the material tempotron modelhttp://hdl.handle.net/11583/2535489Titolo: Theory and learning protocols for the material tempotron model
Abstract: Neural networks are able to extract information from the timing of spikes. Here we provide new results on the behavior of the simplest neuronal model which is able to decode information embedded in temporal spike patterns, the so-called tempotron. Using statistical physics techniques we compute the capacity for the case of sparse, time-discretized input, and 'material' discrete synapses, showing that the device saturates the information theoretic bounds with a statistics of output spikes that is consistent with the statistics of the inputs. We also derive two simple and highly efficient learning algorithms which are able to learn a number of associations which are close to the theoretical limit. The simplest versions of these algorithms correspond to distributed online protocols of interest for neuromorphic devices, and can be adapted to address the more biologically relevant continuous-time version of the classification problem, hopefully allowing the understanding of some aspects of synaptic plasticity.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/11583/25354892013-01-01T00:00:00ZSharing information to reconstruct patient-specific pathways in heterogeneous diseaseshttp://hdl.handle.net/11583/2535491Titolo: Sharing information to reconstruct patient-specific pathways in heterogeneous diseases
Abstract: Advances in experimental techniques resulted in abundant genomic, transcriptomic, epigenomic, and proteomic data that have the potential to reveal critical drivers of human diseases. Complementary algorithmic developments enable researchers to map these data onto protein-protein interaction networks and infer which signaling pathways are perturbed by a disease. Despite this progress, integrating data across different biological samples or patients remains a substantial challenge because samples from the same disease can be extremely heterogeneous. Somatic mutations in cancer are an infamous example of this heterogeneity. Although the same signaling pathways may be disrupted in
a cancer patient cohort, the distribution of mutations is long-tailed, and many driver mutations may only be detected in a small fraction of patients. We developed a computational approach to account for heterogeneous data when inferring signaling pathways by sharing information across the samples. Our technique builds upon the prize-collecting Steiner forest problem, a network optimization algorithm that extracts pathways from a protein-protein interaction network. We recover signaling pathways that are similar across all samples yet still re ect the unique characteristics of each biological sample. Leveraging data from related tumors improves our ability to recover the disrupted pathways and reveals patient-specic pathway perturbations in breast cancer.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11583/25354912014-01-01T00:00:00ZShape similarity, better than semantic membership, accounts for the structure of visual object representations in a population of monkey inferotemporal neuronshttp://hdl.handle.net/11583/2514880Titolo: Shape similarity, better than semantic membership, accounts for the structure of visual object representations in a population of monkey inferotemporal neurons
Abstract: The anterior inferotemporal cortex (IT) is the highest stage along the hierarchy of visual areas that, in primates, processes visual objects. Although several lines of evidence suggest that IT primarily represents visual shape information, some recent studies have argued that neuronal ensembles in IT code the semantic membership of visual objects (i.e., represent conceptual classes such as animate and inanimate objects). In this study, we investigated to what extent semantic, rather than purely visual information, is represented in IT by performing a multivariate analysis of IT responses to a set of visual objects. By relying on a variety of machine-learning approaches (including a cutting-edge clustering algorithm that has been recently developed in the domain of statistical physics), we found that, in most instances, IT representation of visual objects is accounted for by their similarity at the level of shape or, more surprisingly, low-level visual properties. Only in a few cases we observed IT representations of semantic classes that were not explainable by the visual similarity of their members. Overall, these findings reassert the primary function of IT as a conveyor of explicit visual shape information, and reveal that low-level visual properties are represented in IT to a greater extent than previously appreciated. In addition, our work demonstrates how combining a variety of state-of-the-art multivariate approaches, and carefully estimating the contribution of shape similarity to the representation of object categories, can substantially advance our understanding of neuronal coding of visual objects in cortex.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/11583/25148802013-01-01T00:00:00ZA Max-Sum algorithm for training discrete neural networkshttp://hdl.handle.net/11583/2617481Titolo: A Max-Sum algorithm for training discrete neural networks
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11583/26174812015-01-01T00:00:00ZLearning may need only a few bits of synaptic precisionhttp://hdl.handle.net/11583/2643407Titolo: Learning may need only a few bits of synaptic precision
Abstract: Learning in neural networks poses peculiar challenges when using discretized rather then continuous synaptic
states. The choice of discrete synapses is motivated by biological reasoning and experiments, and possibly by
hardware implementation considerations as well. In this paper we extend a previous large deviations analysis
which unveiled the existence of peculiar dense regions in the space of synaptic states which accounts for the
possibility of learning efficiently in networks with binary synapses. We extend the analysis to synapses with
multiple states and generally more plausible biological features. The results clearly indicate that the overall
qualitative picture is unchanged with respect to the binary case, and very robust to variation of the details of
the model. We also provide quantitative results which suggest that the advantages of increasing the synaptic
precision (i.e., the number of internal synaptic states) rapidly vanish after the first few bits, and therefore that,
for practical applications, only few bits may be needed for near-optimal performance, consistent with recent
biological findings. Finally, we demonstrate how the theoretical analysis can be exploited to design efficient
algorithmic search strategies.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11583/26434072016-01-01T00:00:00ZEfficient supervised learning in networks with binary synapseshttp://hdl.handle.net/11583/1913197Titolo: Efficient supervised learning in networks with binary synapses
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11583/19131972007-01-01T00:00:00Z