Pulse stream VLSI neural networks

EPSILON, a large, working, VLSI device, demonstrates pulse stream methods in the wider context of analog neural networks. EPSILON uses dynamic weight storage techniques, but a nonvolatile alternative is desirable. To that end, we have developed an amorphous silicon memory, which we present in experiments incorporating the device in a modest pulse stream neural chip. We have also developed a target-based training algorithm, which we demonstrate in a prototype learning device using a realistic problem. Finally, we explore system-level problems in experiments with a second version of EPSILON in a small, autonomous robot     

“Chaotic relaxation” in concurrently asynchronous neural networks

In this paper we analyze a fundamental issue which directly impacts the scalability of current theoretical neural network models to applicative embodiments, in both software as well as hardware. This pertains to the inherent and unavoidable concurrent asynchronicity of emerging fine-grained computational ensembles and the consequent chaotic manifestations in the absence of proper conditioning. The latter concern is particularly significant since the computational inertia of neural networks in general and our dynamical learning formalisms manifests itself substantially, only in massively parallel hardward—optical, VLSI or opto-electronic. We introduce a mathematical framework for systematically reconditioning additive-type models and derive a neuro-operator, based on the chaotic relaxation paradigm whose resulting dynamics are neither “concurrently” synchronous nor “sequentially” asynchronous. Necessary and sufficient conditions guaranteeing concurrent asynchronous convergence are established in terms of contracting operators. Lyapunov exponents are also computed to characterize the network dynamics and to ensure that throughput-limiting “emergent computational chaos” behavior in models reconditioned with concurrently asynchronous algorithms was eliminated.     

Spiking neurons and the induction of finite state machines

We discuss in this short survey article some current mathematical models from neurophysiology for the computational units of biological neural systems: neurons and synapses. These models are contrasted with the computational units of common artificial neural network models, which reflect the state of knowledge in neurophysiology 50 years ago. We discuss the problem of carrying out computations in circuits consisting of biologically realistic computational units, focusing on the biologically particularly relevant case of computations on time series. Finite state machines are frequently used in computer science as models for computations on time series. One may argue that these models provide a reasonable common conceptual basis for analyzing computations in computers and biological neural systems, although the emphasis in biological neural systems is shifted more towards asynchronous computation on analog time series. In the second half of this article some new computer experiments and theoretical results are discussed, which address the question whether a biological neural system can, in principle, learn to behave like a given simple finite state machine.     

On the computational power of winner-take-all

This article initiates a rigorous theoretical analysis of the computational power of circuits that employ modules for computing winner-take-all. Computational models that involve competitive stages have so far been neglected in computational complexity theory, although they are widely used in computational brain models, artificial neural networks, and analog VLSI. Our theoretical analysis shows that winner-take-all is a surprisingly powerful computational module in comparison with threshold gates (also referred to as McCulloch-Pitts neurons) and sigmoidal gates. We prove an optimal quadratic lower bound for computing winner-take-all in any feedforward circuit consisting of threshold gates. In addition we show that arbitrary continuous functions can be approximated by circuits employing a single soft winner-take-all gate as their only nonlinear operation. Our theoretical analysis also provides answers to two basic questions raised by neurophysiologists in view of the well-known asymmetry between excitatory and inhibitory connections in cortical circuits: how much computational power of neural networks is lost if only positive weights are employed in weighted sums and how much adaptive capability is lost if only the positive weights are subject to plasticity.     

SpikeNET: an event-driven simulation package for modelling large networks of spiking neurons

Many biological neural network models face the problem of scalability because of the limited computational power of today's computers. Thus, it is difficult to assess the efficiency of these models to solve complex problems such as image processing. Here, we describe how this problem can be tackled using event-driven computation. Only the neurons that emit a discharge are processed and, as long as the average spike discharge rate is low, millions of neurons and billions of connections can be modelled. We describe the underlying computation and implementation of such a mechanism in SpikeNET, our neural network simulation package. The type of model one can build is not only biologically compliant, it is also computationally efficient as 400 000 synaptic weights can be propagated per second on a standard desktop computer. In addition, for large networks, we can set very small time steps (< 0.01 ms) without significantly increasing the computation time. As an example, this method is applied to solve complex cognitive tasks such as face recognition in natural images.     

Square-root algorithms for parallel processing in optimal estimation

We give explicit algorithms in square-root form that allow measurements for the standard state estimation problem to be processed in a highly parallel fashion with little communication between processors. After this preliminary processing, blocks of measurements may be incorporated into state estimates with essentially the same computation as usually accompanies the incorporation of a single measurement. This formulation also leads to square-root doubling formulae for calculating the steady-state error-covariance matrix of constant models, and an extension of the class of problems for which Chandrasekhar-type algorithms offer computational reductions to include piecewise constant systems with arbitrary initial conditions.     

DNA-based logic

 Complex natural processes may often be expressed in terms of networks of computational components, such as Boolean logic gates or artificial neurons. The interaction of biological molecules and the flow of information controlling the development and behaviour of organisms is particularly amenable to this approach, and these models are well-established in the biological community. However, only relatively recently have papers appeared proposing the use of such systems to perform useful, human-defined tasks. Rather than merely using the network analogy as a convenient technique for clarifying our understanding of complex systems, it may now be possible to harness the power of such systems for the purposes of computation. In this paper we review several such proposals, focusing on the molecular implementation of fundamental computational elements.     

On the computational power of circuits of spiking neurons

Complex real-time computations on multi-modal time-varying input streams are carried out by generic cortical microcircuits. Obstacles for the development of adequate theoretical models that could explain the seemingly universal power of cortical microcircuits for real-time computing are the complexity and diversity of their computational units (neurons and synapses), as well as the traditional emphasis on offline computing in almost all theoretical approaches towards neural computation. In this article, we initiate a rigorous mathematical analysis of the real-time computing capabilities of a new generation of models for neural computation, liquid state machines, that can be implemented with—in fact benefit from—diverse computational units. Hence, realistic models for cortical microcircuits represent special instances of such liquid state machines, without any need to simplify or homogenize their diverse computational units. We present proofs of two theorems about the potential computational power of such models for real-time computing, both on analog input streams and for spike trains as inputs.     

Efficient algorithms for computation of the burstiness curve of video sources

The burstiness of a video source can be characterized by its burstiness curve. The burstiness curve is useful in the optimal allocation of resources to satisfy a desired quality of service for the video stream in a packet network. In this paper, we present deterministic algorithms for exact computation of the burstiness curve of a video source, for both elementary video streams and MPEG-2 Transport Streams. The algorithms exploit the piecewise linearity of the burstiness curve and compute only the points at which the slope of the burstiness curve changes. We also present approximate versions of these algorithms, which save computational effort by considering only a small number of candidate points at which the slope of the burstiness curve may change. The approximate algorithm was able to compute the burstiness curve of a 2-h long elementary video stream in approximately 10 s, as compared to over 6 h for the exact algorithm, with virtually no loss of accuracy in the computation. The efficiency of the proposed algorithms makes them suitable for quality-of-service (QoS) provisioning not only in off-line environments such as in video-on-demand (VoD) servers, but also in real-time applications such as in live TV distribution systems.     

模拟神经网络VLSI脉冲流技术在故障诊断中的应用分析

介绍了模拟神经网络VLSI脉冲流技术实现神经网络模式识别硬件电路的方法，并且直接将故障分类。提出利用包含有故障信息的原始模拟噪声信号，经过前置信号处理和神经网络运算，得出VLSI电路输出端电容的电压值－代表待识别信号与模板故障信号的“欧氏距离”，以实现噪声故障信号的实时硬件在线识别。     

On computing Boolean functions by a spiking neuron

Computations by spiking neurons are performed using the timing of action potentials. We investigate the computational power of a simple model for such a spiking neuron in the Boolean domain by comparing it with traditional neuron models such as threshold gates (or McCulloch–Pitts neurons) and sigma-pi units (or polynomial threshold gates). In particular, we estimate the number of gates required to simulate a spiking neuron by a disjunction of threshold gates and we establish tight bounds for this threshold number. Furthermore, we analyze the degree of the polynomials that a sigma-pi unit must use for the simulation of a spiking neuron. We show that this degree cannot be bounded by any fixed value. Our results give evidence that the use of continuous time as a computational resource endows single-cell models with substantially larger computational capabilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

Converting spatially encoded sensory information to motor signals using analog VLSI circuits

A collective computational architecture and real-time, analog VLSI implementation for localizing and tracking a stimulus in a sensory image are developed. This architecture is presented as a layered two-dimensional computationalframework which generates signals to autonomously control a mechanical system that tracks the stimulus. The framework is a schematic representation of the described computation. The input to the framework is a spatially encoded sensory image and the outputs are a set of pulse trains that are used to control a robotic motor system. The analog VLSI implementation is based upon circuits that provide a real-time, small-size, low-power implementation technology for this and other sensorimotor applications. The circuits perform the desired computation entirely in parallel on a single VLSI chip. The layer-to-layer communications occur via arrays of currents which are modified at each level in the framework and then communicated to the subsequent layer. The outputs generated by the circuit are a set of pulse-encoded signals sufficient to antagonistically control DC actuators. A system implementation and resulting data are also presented. The system combines a visual imaging array, computational circuitry, and a mechanical plant, which, through negative feedback, moves the imager to hold a stimulus (a bright spot on a darker background) stationary in the sensory field.     

Turing Machines, Transition Systems, and Interaction

We present Persistent Turing Machines (PTMs), a new way of interpreting Turing-machine computation, one that is both interactive and persistent. We show that the class of PTMs is isomorphic to a very general class of effective transition systems. One may therefore conclude that the extensions to the Turing-machine model embodied in PTMs are sufficient to make Turing machines expressively equivalent to transition systems. We also define the persistent stream language (PSL) of a PTM and a corresponding notion of PSL-equivalence, and consider the infinite hierarchy of successively finer equivalences for PTMs over finite interaction-stream prefixes. We show that the limit of this hierarchy is strictly coarser than PSL-equivalence, a “gap” whose presence can be attributed to the fact that the transition systems corresponding to PTM computations naturally exhibit unbounded nondeterminism.We also consider amnesic PTMs and a corresponding notion of equivalence based on amnesic stream languages (ASLs). It can be argued that amnesic stream languages are representative of the classical view of Turing-machine computation. We show that the class of ASLs is strictly contained in the class of PSLs. Furthermore, the hierarchy of PTM equivalence relations collapses for the subclass of amnesic PTMs. These results indicate that, in a stream-based setting, the extension of the Turing-machine model with persistence is a nontrivial one, and provide a formal foundation for reasoning about programming concepts such as objects with static attributes.     

The design, fabrication, and test of a new VLSI hybridanalog-digital neural processing element

A hybrid analog-digital neural processing element with the time-dependent behavior of biological neurons has been developed. The hybrid processing element is designed for VLSI implementation and offers the best attributes of both analog and digital computation. Custom VLSI layout reduces the layout area of the processing element, which in turn increases the expected network density. The hybrid processing element operates at the nanosecond time scale, which enables it to produce real-time solutions to complex spatiotemporal problems found in high-speed signal processing applications. VLSI prototype chips have been designed, fabricated, and tested with encouraging results. Systems utilizing the time-dependent behavior of the hybrid processing element have been simulated and are currently in the fabrication process. Future applications are also discussed.     

Template-guided DNA recombination

The family of stichotrichous ciliates have received a great deal of study due to the presence of scrambled genes in their genomes. The mechanism by which these genes are descrambled is of interest both as a biological process and as a model of natural computation. Several formal models of this process have been proposed, the most recent of which involves the recombination of DNA strands based on template guides. We generalize this template-guided DNA recombination model proposed by Prescott, Ehrenfeucht and Rozenberg to an operation on strings and languages. We then proceed to investigate the properties of this operation with the intention of viewing ciliate gene descrambling as a computational process.     

Set Cover和Hitting Set问题的研究进展

Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。     

Cintia: a neuro-fuzzy real-time controller for low-power embeddedsystems

Cintia, a neuro-fuzzy real-time controller based on pulse stream computation techniques, is designed for applications in low-power embedded systems. The system mixes two approaches: neuro-fuzzy controllers and finite-state automata. We implement the former by means of a custom neural chip, the latter as sequential code on a traditional microcontroller. Cintia demonstrates the advantages of mixing the two approaches and the feasibility of embedded neuro-fuzzy control systems. A low-power, single-chip version is also under design     

On transformations of formal power series

Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve recognizability, generalizing the recent results of Zhang [16] to the formal power series setting. We show, for example, that the “square-root” operation, while preserving regularity for formal languages, preserves recognizability for formal power series when the underlying semiring is commutative or locally finite, but not in general.     

Computing Green's function of the initial-boundary value problem for the wave equation in a layered cylinder

A new analytical method for the approximate computation of the time-dependent Green's function for the initial-boundary value problem of the three-dimensional wave equation on multi-layered bounded cylinder is suggested in this paper. The method is based on the derivation of eigenvalues and eigenfunctions for an ordinary differential equation with piecewise constant coefficients, and an approximate computation of Green's function in the form of the Fourier series with a finite number of terms relative to the orthogonal set of the derived eigenfunctions. The computational experiment confirms the robustness of the method.     

Synaptic dynamics in analog VLSI

Synapses are crucial elements for computation and information transfer in both real and artificial neural systems. Recent experimental findings and theoretical models of pulse-based neural networks suggest that synaptic dynamics can play a crucial role for learning neural codes and encoding spatiotemporal spike patterns. Within the context of hardware implementations of pulse-based neural networks, several analog VLSI circuits modeling synaptic functionality have been proposed. We present an overview of previously proposed circuits and describe a novel analog VLSI synaptic circuit suitable for integration in large VLSI spike-based neural systems. The circuit proposed is based on a computational model that fits the real postsynaptic currents with exponentials. We present experimental data showing how the circuit exhibits realistic dynamics and show how it can be connected to additional modules for implementing a wide range of synaptic properties.