While the human brain efficiently handles various computations with a limited number of neurons, traditional deep learning networks require a significant increase in parameters to improve performance. Yet, these parameters are used inefficiently as the networks employ the same amount of computation for inputs of the same size, regardless of the input's complexity. We address this inefficiency by introducing self-introspection capabilities to the network, enabling it to adjust the number of used parameters based on the internal representation of the task and adapt the computation time based on the task complexity. This enables the network to adaptively reuse parameters across tasks, dynamically adjusting the computational effort to match the complexity of the input. We demonstrate the effectiveness of this method on language modeling and computer vision tasks. Notably, our model achieves 96.62\% accuracy on ImageNet with just a three-layer network, surpassing much larger ResNet-50 and EfficientNet. When applied to a transformer architecture, the approach achieves 95.8\%/88.7\% F1 scores on the SQuAD v1.1/v2.0 datasets at negligible parameter cost. These results showcase the potential for dynamic and reflective computation, contributing to the creation of intelligent systems that efficiently manage resources based on input data complexity.

Extensive research on formal verification of machine learning systems indicates that learning from data alone often fails to capture underlying background knowledge, such as specifications implicitly available in the data. Various neural network verifiers have been developed to ensure that a machine-learnt model satisfies correctness and safety properties; however, they typically assume a trained network with fixed weights. A promising approach for creating machine learning models that inherently satisfy constraints after training is to encode background knowledge as explicit logical constraints that guide the learning process via so-called differentiable logics. In this paper, we experimentally compare and evaluate various logics from the literature, present our findings, and highlight open problems for future work. We evaluate differentiable logics with respect to their suitability in training, and use a neural network verifier to check their ability to establish formal guarantees. The complete source code for our experiments is available as an easy-to-use framework for training with differentiable logics at https://github.com/tflinkow/comparing-differentiable-logics .

Sketching for speeding up regression problems involves using a sketching matrix $S$ to quickly find the approximate solution to a linear least squares regression (LLS) problem: given $A$ of size $n \times d$, with $n \gg d$, along with $b$ of size $n \times 1$, we seek a vector $y$ with minimal regression error $\lVert A y - b\rVert_2$. This approximation technique is now standard in data science, and many software systems use sketched regression internally, as a component. It is often useful to calculate derivatives (gradients for the purpose of optimization, for example) of such large systems, where sketched LLS is merely a component of a larger system whose derivatives are needed. To support Automatic Differentiation (AD) of systems containing sketched LLS, we consider propagating derivatives through $\textrm{LLS}$: both propagating perturbations (forward AD) and gradients (reverse AD). AD performs accurate differentiation and is efficient for problems with a huge number of independent variables. Since we use $\textrm{LLS}_S$ (sketched LLS) instead of $\textrm{LLS}$ for reasons of efficiency, propagation of derivatives also needs to trade accuracy for efficiency, presumably by sketching. There are two approaches for this: (a) use AD to transform the code that defines $\textrm{LLS}_S$, or (b) approximate exact derivative propagation through $\textrm{LLS}$ using sketching methods. We provide strong bounds on the errors produced due to these two natural forms of sketching in the context of AD, giving the first dimensionality reduction analysis for calculating the derivatives of a sketched computation. Our results crucially depend on the analysis of the operator norm of a sketched inverse matrix product. Extensive experiments on both synthetic and real-world experiments demonstrate the efficacy of our sketched gradients.

Abstract Automatic differentiation (AD) is a technique for augmenting computer programs to compute derivatives. The essence of AD in its forward accumulation mode is to attach perturbations to each number, and propagate these through the computation by overloading the arithmetic operators. When derivatives are nested, the distinct derivative calculations, and their associated perturbations, must be distinguished. This is typically accomplished by creating a unique tag for each derivative calculation and tagging the perturbations. We exhibit a subtle bug, present in fielded implementations which support derivatives of higher-order functions, in which perturbations are confused despite the tagging machinery, leading to incorrect results. The essence of the bug is as follows: a unique tag is needed for each derivative calculation, but in existing implementations unique tags are created when taking the derivative of a function at a point. When taking derivatives of higher-order functions, these need not correspond! We exhibit a simple example: a higher-order function f whose derivative at a point x , namely f ′( x ), is itself a function which calculates a derivative. This situation arises naturally when taking derivatives of curried functions. Two potential solutions are presented, and their deficiencies discussed. One uses eta expansion to delay the creation of fresh tags in order to put them into one-to-one correspondence with derivative calculations. The other wraps outputs of derivative operators with tag substitution machinery. Both solutions seem very difficult to implement without violating the desirable complexity guarantees of forward AD.

In this paper we examine the issues involved in adding concurrency to the Robin Hood hash table algorithm. We present a non-blocking obstruction-free K-CAS Robin Hood algorithm which requires only a single word compare-and-swap primitive, thus making it highly portable. The implementation maintains the attractive properties of the original Robin Hood structure, such as a low expected probe length, capability to operate effectively under a high load factor and good cache locality, all of which are essential for high performance on modern computer architectures. We compare our data-structures to various other lock-free and concurrent algorithms, as well as a simple hardware transactional variant, and show that our implementation performs better across a number of contexts.

“Happy New Year!” At the beginning of 2016, I would like to take this opportunity to wish everyone a very happy, healthy, and prosperous new year! It is my great honor and privilege to serve as the Editor-in-Chief (EiC) of the IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS (TNNLS), and I am excited to write this Editorial to start a new journey with you all.

We propose that the critical function of sleep is to prevent uncontrolled neuronal feedback while allowing rapid responses and prolonged retention of short-term memories. Through learning, the brain is tuned to react optimally to environmental challenges. Optimal behavior often requires rapid responses and the prolonged retention of short-term memories. At a neuronal level, these correspond to recurrent activity in local networks. Unfortunately, when a network exhibits recurrent activity, small changes in the parameters or conditions can lead to runaway oscillations. Thus, the very changes that improve the processing performance of the network can put it at risk of runaway oscillation. To prevent this, stimulus-dependent network changes should be permitted only when there is a margin of safety around the current network parameters. We propose that the essential role of sleep is to establish this margin by exposing the network to a variety of inputs, monitoring for erratic behavior, and adjusting the parameters. When sleep is not possible, an emergency mechanism must come into play, preventing runaway behavior at the expense of processing efficiency. This is tiredness.

We show that reverse-mode AD (Automatic Differentiation)—a generalized gradient-calculation operator—can be incorporated as a first-class function in an augmented lambda calculus, and therefore into a functional-programming language. Closure is achieved, in that the new operator can be applied to any expression in the augmented language, yielding an expression in that language. This requires the resolution of two major technical issues: (a) how to transform nested lambda expressions, including those with free-variable references, and (b) how to support self application of the AD machinery. AD transformations preserve certain complexity properties, among them that the reverse phase of the reverse-mode AD transformation of a function have the same temporal complexity as the original untransformed function. First-class unrestricted AD operators increase the expressive power available to the numeric programmer, and may have significant practical implications for the construction of numeric software that is robust, modular, concise, correct, and efficient.

A method is presented for computing all higher-order partial derivatives of a multivariate function R n → R. This method works by evaluating the function under a nonstandard interpretation, lifting reals to multivariate power series. Multivariate power series, with potentially an infinite number of terms with nonzero coefficients, are represented using a lazy data structure constructed out of linear terms. A complete implementation of this method in Scheme is presented, along with a straightforward exposition, based on Taylor expansions, of the method's correctness.

We motivate and discuss a novel functional programming construct that allows convenient modular run-time nonstandard interpretation via reflection on closure environments. This map-closure construct encompasses both the ability to examine the contents of a closure environment and to construct a new closure with a modified environment. From the user's perspective, map-closure is a powerful and useful construct that supports such tasks as tracing, security logging, sandboxing, error checking, profiling, code instrumentation and metering, run-time code patching, and resource monitoring. From the implementor's perspective, map-closure is analogous to call/cc. Just as call/cc is a non-referentially-transparent mechanism that reifies the continuations that are only implicit in programs written in direct style, map-closure is a non-referentially-transparent mechanism that reifies the closure environments that are only implicit in higher-order programs. Just as CPS conversion is a non-local but purely syntactic transformation that can eliminate references to call/cc, closure conversion is a non-local but purely syntactic transformation that can eliminate references to map-closure. We show how the combination of map-closure and call/cc can be used to implement set! as a procedure definition and a local macro transformation.

Neuronal activity in response to a fixed stimulus has been shown to change as a function of attentional state, implying that the neural code also changes with attention. We propose an information-theoretic account of such modulation: that the nervous system adapts to optimally encode sensory stimuli while taking into account the changing relevance of different features. We show using computer simulation that such modulation emerges in a coding system informed about the uneven relevance of the input features. We present a simple feedforward model that learns a covert attention mechanism, given input patterns and coding fidelity requirements. After optimization, the system gains the ability to reorganize its computational resources (and coding strategy) depending on the incoming attentional signal, without the need of multiplicative interaction or explicit gating mechanisms between units. The modulation of activity for different attentional states matches that observed in a variety of selective attention experiments. This model predicts that the shape of the attentional modulation function can be strongly stimulus dependent. The general principle presented here accounts for attentional modulation of neural activity without relying on special-purpose architectural mechanisms dedicated to attention. This principle applies to different attentional goals, and its implications are relevant for all modalities in which attentional phenomena are observed.

We describe a system that localizes a single dipole to reasonable accu- racy from noisy magnetoencephalographic (MEG) measurements in real time. At its core is a multilayer perceptron (MLP) trained to map sen- sor signals and head position to dipole location. Including head position overcomes the previous need to retrain the MLP for each subject and ses- sion. The training dataset was generated by mapping randomly chosen dipoles and head positions through an analytic model and adding noise from real MEG recordings. After training, a localization took 0.7 ms with an average error of 0.90 cm. A few iterations of a Levenberg-Marquardt routine using the MLP’s output as its initial guess took 15 ms and im- proved the accuracy to 0.53 cm, only slightly above the statistical limits on accuracy imposed by the noise. We applied these methods to localize single dipole sources from MEG components isolated by blind source separation and compared the estimated locations to those generated by standard manually-assisted commercial software.

We applied second-order blind identification (SOBI), an independent component analysis method, to MEG data collected during cognitive tasks. We explored SOBI's ability to help isolate underlying neuronal sources with relatively poor signal-to-noise ratios, allowing their identification and localization. We compare localization of the SOBI-separated components to localization from unprocessed sensor signals, using an equivalent current dipole modeling method. For visual and somatosensory modalities, SOBI preprocessing resulted in components that can be localized to physiologically and anatomically meaningful locations. Furthermore, this preprocessing allowed the detection of neuronal source activations that were otherwise undetectable. This increased probability of neuronal source detection and localization can be particularly beneficial for MEG studies of higher-level cognitive functions, which often have greater signal variability and degraded signal-to-noise ratios than sensory activation tasks.

We consider a problem of blind source separation from a set of instan(cid:173) taneous linear mixtures, where the mixing matrix is unknown. It was discovered recently, that exploiting the sparsity of sources in an appro(cid:173) priate representation according to some signal dictionary, dramatically improves the quality of separation. In this work we use the property of multi scale transforms, such as wavelet or wavelet packets, to decompose signals into sets of local features with various degrees of sparsity. We use this intrinsic property for selecting the best (most sparse) subsets of features for further separation. The performance of the algorithm is ver(cid:173) ified on noise-free and noisy data. Experiments with simulated signals, musical sounds and images demonstrate significant improvement of sep(cid:173) aration quality over previously reported results.

The blind source separation problem is to extract the underlying source signals from a set of linear mixtures, where the mixing matrix is unknown. This situation is common in acoustics, radio, medical signal and image processing, hyperspectral imaging, and other areas. We suggest a two-stage separation process: a priori selection of a possibly overcomplete signal dictionary (for instance, a wavelet frame or a learned dictionary) in which the sources are assumed to be sparsely representable, followed by unmixing the sources by exploiting the their sparse representability. We consider the general case of more sources than mixtures, but also derive a more efficient algorithm in the case of a nonovercomplete dictionary and an equal numbers of sources and mixtures. Experiments with artificial signals and musical sounds demonstrate significantly better separation than other known techniques.

A simplified model of the fly's early visual processing system was simulated. The model contains coupled nonlinear differential equations, increasing the complexity of software and its computational burden. An extension of the model to large arrays of retinal cartridges required high performance computing which further increased the complexity. Conventional visualization methods limited software development and model analysis. As a solution, more sophisticated visualization tools, such as IBM's open visualization data explorer and UNM's Flatland, were employed. These tools expedited software debugging and development. The accuracy and added insight afforded by these visualization tools provided a more natural environment for simulation analysis.

Intrusion detection systems rely on a wide variety of observable data to distinguish between legitimate and illegitimate activities. We study one such observable-sequences of system calls into the kernel of an operating system. Using system-call data sets generated by several different programs, we compare the ability of different data modeling methods to represent normal behavior accurately and to recognize intrusions. We compare the following methods: simple enumeration of observed sequences; comparison of relative frequencies of different sequences; a rule induction technique; and hidden Markov models (HMMs). We discuss the factors affecting the performance of each method and conclude that for this particular problem, weaker methods than HMMs are likely sufficient.

We find the VC dimension of a leaky integrate-andfire neuron model.The VC dimension quantifies the ability of a function class to partition an input pattern space, and can be considered a measure of computational capacity.In this case, the function class is the class of integrate-and-fire models generated by varying the integration time constant ~ and the threshold 0, the input space they partition

We compute the VC dimension of a leaky integrate-and-fire neuron model. The VC dimension quantifies the ability of a function class to partition an input pattern space, and can be considered a measure of computational capacity. In this case, the function class is the class of integrate-and-fire models generated by varying the integration time constant T and the threshold θ, the input space they partition is the space of continuous-time signals, and the binary partition is specified by whether or not the model reaches threshold at some specified time. We show that the VC dimension diverges only logarithmically with the input signal bandwidth N. We also extend this approach to arbitrary passive dendritic trees. The main contributions of this work are (1) it offers a novel treatment of computational capacity of this class of dynamic system; and (2) it provides a framework for analyzing the computational capabilities of the dynamic systems defined by networks of spiking neurons.

We show that a k/spl times/n diagonal mesh is isomorphic to a (n+k)/2/spl times/(n+k)/2-(n-k)/2/spl times/(n-k)/2 twisted toroidal mesh, i.e., a network similar to a standard (n+k)/2/spl times/(n+k)/2 toroidal mesh, but with opposite handed twists of (n-k)/2 in the two directions, which results in a loss of ((n-k)/2)/sup 2/ nodes.

In an isopotential neuron with rapid response, it has been shown that the receptive fields formed by Hebbian synaptic modulation depend on the principal eigenspace of Q(0), the input autocorrelation matrix, where Qij(tau) = and xi i(t) is the input to synapse i at time t (Oja 1982). We relax the assumption of isopotentiality, introduce a time-skewed Hebb rule, and find that the dynamics of synaptic evolution are determined by the principal eigenspace of Q. This matrix is defined by Qij = integral of 0 infinity (Qij * psi i) (tau) Kij (tau) d tau, where Kij (tau) is the neuron's voltage response to a unit current injection at synapse j as measured tau seconds later at synapse i, and psi(tau) is the time course of the opportunity for modulation of synapse i following the arrival of a presynaptic action potential.

Surveys learning algorithms for recurrent neural networks with hidden units and puts the various techniques into a common framework. The authors discuss fixed point learning algorithms, namely recurrent backpropagation and deterministic Boltzmann machines, and nonfixed point algorithms, namely backpropagation through time, Elman's history cutoff, and Jordan's output feedback architecture. Forward propagation, an on-line technique that uses adjoint equations, and variations thereof, are also discussed. In many cases, the unified presentation leads to generalizations of various sorts. The author discusses advantages and disadvantages of temporally continuous neural networks in contrast to clocked ones continues with some "tricks of the trade" for training, using, and simulating continuous time and recurrent neural networks. The author presents some simulations, and at the end, addresses issues of computational complexity and learning speed.

The best previous algorithm for the matching shoulders lob-pass game, ARTHUR (Abe and Takeuchi 1993), suffered O(t1/2) regret. We prove that this is the best possible performance for any algorithm that works by accurately estimating the opponent's payoff lines. Then we describe an algorithm which beats that bound and meets the information-theoretic lower bound of O(logt) regret by converging to the best lob rate without accurately estimating the payoff lines. The noise-tolerant binary search procedure that we develop is of independent interest.

The abstract is included in the text.

Just storing the Hessian H (the matrix of second derivatives δ 2 E/δw i δw j of the error E with respect to each pair of weights) of a large neural network is difficult. Since a common use of a large matrix like H is to compute its product with various vectors, we derive a technique that directly calculates Hv, where v is an arbitrary vector. To calculate Hv, we first define a differential operator R v {f(w)} = (δ/δr)f(w + rv)|r=0, note that R v {▽w} = Hv and R v {w} = v, and then apply R v {·} to the equations used to compute ▽ w . The result is an exact and numerically stable procedure for computing Hv, which takes about as much computation, and is about as local, as a gradient evaluation. We then apply the technique to a one pass gradient calculation algorithm (backpropagation), a relaxation gradient calculation algorithm (recurrent backpropagation), and two stochastic gradient calculation algorithms (Boltzmann machines and weight perturbation). Finally, we show that this technique can be used at the heart of many iterative techniques for computing various properties of H, obviating any need to calculate the full Hessian.

The commenter claims that in the above-titled paper (ibid., vol.2, p.465-467, July 1991), which presents an efficient algorithm using dynamic programming to find weights which load a set of examples into a feedforward neural network with minimal error, a contradiction lies buried in the paper's notation. In reply, the author maintains that the comments are due to some misunderstandings about the implementation of dynamic-programming-based algorithms and clarifies the work.

Many neural network learning procedures compute gradients of the errors on the output layer of units after they have settled to their final values. We describe a procedure for finding ∂E/∂wij, where E is an error functional of the temporal trajectory of the states of a continuous recurrent network and wij are the weights of that network. Computing these quantities allows one to perform gradient descent in the weights to minimize E. Simulations in which networks are taught to move through limit cycles are shown. This type of recurrent network seems particularly suited for temporally continuous domains, such as signal processing, control, and speech.

The Scheme papers demonstrated that lisp could be made simpler and more expressive by elevating functions to the level of first class objects. Oaklisp shows that a message based language can derive similar benefits from having first class types.