Model of computation | EPFL Graph Search

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology. Models Models of computation can be classified into three categories: sequential models, functional models, and concurrent models. Sequential models Sequential models include:

Finite state machines
Post machines (Post–Turing machines and tag machines).
Pushdown automata
Register machines ** Random-access machines
Turing machines
Decision tree model

Functional models Functional models in

Thermodynamics of organic electrochemical transistors

Hsin Tseng

Though models describing the operating mechanism of organic electrochemical transistors (OECTs) have been developed, these models are unable to accurately reproduce OECT electrical characteristics. Here, the authors report a thermodynamic-based framework that accurately models OECT operation. Despite their increasing usefulness in a wide variety of applications, organic electrochemical transistors still lack a comprehensive and unifying physical framework able to describe the current-voltage characteristics and the polymer/electrolyte interactions simultaneously. Building upon thermodynamic axioms, we present a quantitative analysis of the operation of organic electrochemical transistors. We reveal that the entropy of mixing is the main driving force behind the redox mechanism that rules the transfer properties of such devices in electrolytic environments. In the light of these findings, we show that traditional models used for organic electrochemical transistors, based on the theory of field-effect transistors, fall short as they treat the active material as a simple capacitor while ignoring the material properties and energetic interactions. Finally, by analyzing a large spectrum of solvents and device regimes, we quantify the entropic and enthalpic contributions and put forward an approach for targeted material design and device applications.

NATURE PORTFOLIO2022

Theory of representation learning in cortical neural networks

Carlos Stein Naves de Brito

Our brain continuously self-organizes to construct and maintain an internal representation of the world based on the information arriving through sensory stimuli. Remarkably, cortical areas related to different sensory modalities appear to share the same functional unit, the neuron, and develop through the same learning mechanism, synaptic plasticity. It motivates the conjecture of a unifying theory to explain cortical representational learning across sensory modalities. In this thesis we present theories and computational models of learning and optimization in neural networks, postulating functional properties of synaptic plasticity that support the apparent universal learning capacity of cortical networks. In the past decades, a variety of theories and models have been proposed to describe receptive field formation in sensory areas. They include normative models such as sparse coding, and bottom-up models such as spike-timing dependent plasticity. We bring together candidate explanations by demonstrating that in fact a single principle is sufficient to explain receptive field development. First, we show that many representative models of sensory development are in fact implementing variations of a common principle: nonlinear Hebbian learning. Second, we reveal that nonlinear Hebbian learning is sufficient for receptive field formation through sensory inputs. A surprising result is that our findings are independent of specific details, and allow for robust predictions of the learned receptive fields. Thus nonlinear Hebbian learning and natural statistics can account for many aspects of receptive field formation across models and sensory modalities. The Hebbian learning theory substantiates that synaptic plasticity can be interpreted as an optimization procedure, implementing stochastic gradient descent. In stochastic gradient descent inputs arrive sequentially, as in sensory streams. However, individual data samples have very little information about the correct learning signal, and it becomes a fundamental problem to know how many samples are required for reliable synaptic changes. Through estimation theory, we develop a novel adaptive learning rate model, that adapts the magnitude of synaptic changes based on the statistics of the learning signal, enabling an optimal use of data samples. Our model has a simple implementation and demonstrates improved learning speed, making this a promising candidate for large artificial neural network applications. The model also makes predictions on how cortical plasticity may modulate synaptic plasticity for optimal learning. The optimal sampling size for reliable learning allows us to estimate optimal learning times for a given model. We apply this theory to derive analytical bounds on times for the optimization of synaptic connections. First, we show this optimization problem to have exponentially many saddle-nodes, which lead to small gradients and slow learning. Second, we show that the number of input synapses to a neuron modulates the magnitude of the initial gradient, determining the duration of learning. Our final result reveals that the learning duration increases supra-linearly with the number of synapses, suggesting an effective limit on synaptic connections and receptive field sizes in developing neural networks.

EPFL2016

Function computation via subspace coding

Christina Fragouli, Nikhil Karamchandani

This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.

2010

Theory of representation learning in cortical neural networks

Carlos Stein Naves de Brito

EPFL2016