Dynamic analyses of information encoding in neural ensembles

Neural spike train decoding algorithms and techniques to compute Shannon mutual information are important methods for analyzing how neural systems represent biological signals. Decoding algorithms are also one of several strategies being used to design controls for brain-machine interfaces. Developing optimal strategies to design decoding algorithms and compute mutual information are therefore important problems in computational neuroscience. We present a general recursive filter decoding algorithm based on a point process model of individual neuron spiking activity and a linear stochastic state-space model of the biological signal. We derive from the algorithm new instantaneous estimates of the entropy, entropy rate, and the mutual information between the signal and the ensemble spiking activity. We assess the accuracy of the algorithm by computing, along with the decoding error, the true coverage probability of the approximate 0.95 confidence regions for the individual signal estimates. We illustrate the new algorithm by reanalyzing the position and ensemble neural spiking activity of CA1 hippocampal neurons from two rats foraging in an open circular environment. We compare the performance of this algorithm with a linear filter constructed by the widely used reverse correlation method. The median decoding error for Animal 1 (2) during 10 minutes of open foraging was 5.9 (5.5) cm, the median entropy was 6.9 (7.0) bits, the median information was 9.4 (9.4) bits, and the true coverage probability for 0.95 confidence regions was 0.67 (0.75) using 34 (32) neurons. These findings improve significantly on our previous results and suggest an integrated approach to dynamically reading neural codes, measuring their properties, and quantifying the accuracy with which encoded information is extracted.     

Efficient Markov chain Monte Carlo methods for decoding neural spike trains

Stimulus reconstruction or decoding methods provide an important tool for understanding how sensory and motor information is represented in neural activity. We discuss Bayesian decoding methods based on an encoding generalized linear model (GLM) that accurately describes how stimuli are transformed into the spike trains of a group of neurons. The form of the GLM likelihood ensures that the posterior distribution over the stimuli that caused an observed set of spike trains is log concave so long as the prior is. This allows the maximum a posteriori (MAP) stimulus estimate to be obtained using efficient optimization algorithms. Unfortunately, the MAP estimate can have a relatively large average error when the posterior is highly nongaussian. Here we compare several Markov chain Monte Carlo (MCMC) algorithms that allow for the calculation of general Bayesian estimators involving posterior expectations (conditional on model parameters). An efficient version of the hybrid Monte Carlo (HMC) algorithm was significantly superior to other MCMC methods for gaussian priors. When the prior distribution has sharp edges and corners, on the other hand, the "hit-and-run" algorithm performed better than other MCMC methods. Using these algorithms, we show that for this latter class of priors, the posterior mean estimate can have a considerably lower average error than MAP, whereas for gaussian priors, the two estimators have roughly equal efficiency. We also address the application of MCMC methods for extracting nonmarginal properties of the posterior distribution. For example, by using MCMC to calculate the mutual information between the stimulus and response, we verify the validity of a computationally efficient Laplace approximation to this quantity for gaussian priors in a wide range of model parameters; this makes direct model-based computation of the mutual information tractable even in the case of large observed neural populations, where methods based on binning the spike train fail. Finally, we consider the effect of uncertainty in the GLM parameters on the posterior estimators.     

In quest of the missing neuron: spike sorting based on dominant-sets clustering

Spike sorting algorithms aim at decomposing complex extracellular signals to independent events from single neurons in the electrode's vicinity. The decision about the actual number of active neurons is still an open issue, with sparsely firing neurons and background activity the most influencing factors. We introduce a graph-theoretical algorithmic procedure that successfully resolves this issue. Dimensionality reduction coupled with a modern, efficient and progressively executable clustering routine proved to achieve higher performance standards than popular spike sorting methods. Our method is validated extensively using simulated data for different levels of SNR.     

Slabpose Columnsort: A New Oblivious Algorithm for Out-of-Core Sorting on Distributed-Memory Clusters

Our goal is to develop a robust out-of-core sorting program for a distributed-memory cluster. The literature contains two dominant paradigms for out-of-core sorting algorithms: merging-based and partitioning-based. We explore a third paradigm, that of oblivious algorithms. Unlike the two dominant paradigms, oblivious algorithms do not depend on the input keys and therefore lead to predetermined I/O and communication patterns in an out-of-core setting. Predetermined I/O and communication patterns facilitate overlapping I/O, communication, and computation for efficient implementation. We have developed several out-of-core sorting programs using the paradigm of oblivious algorithms. Our baseline implementation, 3-pass columnsort, was based on Leighton's columnsort algorithm. Though efficient in terms of I/O and communication, 3-pass columnsort has a restriction on the maximum problem size. As our first effort toward relaxing this restriction, we developed two implementations: subblock columnsort and M-columnsort. Both of these implementations incur substantial performance costs: subblock columnsort performs additional disk I/O, and M-columnsort needs substantial amounts of extra communication and computation. In this paper we present slabpose columnsort, a new oblivious algorithm that we have designed explicitly for the out-of-core setting. Slabpose columnsort relaxes the problem-size restriction at no extra I/O or communication cost. Experimental evidence on a Beowulf cluster shows that unlike subblock columnsort and M-columnsort, slabpose columnsort runs almost as fast as 3-pass columnsort. To the best of our knowledge, our implementations are the first out-of-core multiprocessor sorting algorithms that make no assumptions about the keys and produce output that is perfectly load balanced and in the striped order assumed by the Parallel Disk Model.     

Dynamic analysis of neural encoding by point process adaptive filtering

Neural receptive fields are dynamic in that with experience, neurons change their spiking responses to relevant stimuli. To understand how neural systems adapt their representations of biological information, analyses of receptive field plasticity from experimental measurements are crucial. Adaptive signal processing, the well-established engineering discipline for characterizing the temporal evolution of system parameters, suggests a framework for studying the plasticity of receptive fields. We use the Bayes' rule Chapman-Kolmogorov paradigm with a linear state equation and point process observation models to derive adaptive filters appropriate for estimation from neural spike trains. We derive point process filter analogues of the Kalman filter, recursive least squares, and steepest-descent algorithms and describe the properties of these new filters. We illustrate our algorithms in two simulated data examples. The first is a study of slow and rapid evolution of spatial receptive fields in hippocampal neurons. The second is an adaptive decoding study in which a signal is decoded from ensemble neural spiking activity as the receptive fields of the neurons in the ensemble evolve. Our results provide a paradigm for adaptive estimation for point process observations and suggest a practical approach for constructing filtering algorithms to track neural receptive field dynamics on a millisecond timescale.     

Mapping of visual receptive fields by tomographic reconstruction

The moving bar experiment is a classic paradigm for characterizing the receptive field (RF) properties of neurons in primary visual cortex (V1). Current approaches for analyzing neural spiking activity recorded from these experiments do not take into account the point-process nature of these data and the circular geometry of the stimulus presentation. We present a novel analysis approach to mapping V1 receptive fields that combines point-process generalized linear models (PPGLM) with tomographic reconstruction computed by filtered-back projection. We use the method to map the RF sizes and orientations of 251 V1 neurons recorded from two macaque monkeys during a moving bar experiment. Our cross-validated goodness-of-fit analyses show that the PPGLM provides a more accurate characterization of spike train data than analyses based on rate functions computed by the methods of spike-triggered averages or first-order Wiener-Volterra kernel. Our analysis leads to a new definition of RF size as the spatial area over which the spiking activity is significantly greater than baseline activity. Our approach yields larger RF sizes and sharper orientation tuning estimates. The tomographic reconstruction paradigm further suggests an efficient approach to choosing the number of directions and the number of trials per direction in designing moving bar experiments. Our results demonstrate that standard tomographic principles for image reconstruction can be adapted to characterize V1 RFs and that two fundamental properties, size and orientation, may be substantially different from what is currently reported.     

Model-based decoding, information estimation, and change-point detection techniques for multineuron spike trains

One of the central problems in systems neuroscience is to understand how neural spike trains convey sensory information. Decoding methods, which provide an explicit means for reading out the information contained in neural spike responses, offer a powerful set of tools for studying the neural coding problem. Here we develop several decoding methods based on point-process neural encoding models, or forward models that predict spike responses to stimuli. These models have concave log-likelihood functions, which allow efficient maximum-likelihood model fitting and stimulus decoding. We present several applications of the encoding model framework to the problem of decoding stimulus information from population spike responses: (1) a tractable algorithm for computing the maximum a posteriori (MAP) estimate of the stimulus, the most probable stimulus to have generated an observed single- or multiple-neuron spike train response, given some prior distribution over the stimulus; (2) a gaussian approximation to the posterior stimulus distribution that can be used to quantify the fidelity with which various stimulus features are encoded; (3) an efficient method for estimating the mutual information between the stimulus and the spike trains emitted by a neural population; and (4) a framework for the detection of change-point times (the time at which the stimulus undergoes a change in mean or variance) by marginalizing over the posterior stimulus distribution. We provide several examples illustrating the performance of these estimators with simulated and real neural data.     

Quantifying neurotransmission reliability through metrics-based information analysis

We set forth an information-theoretical measure to quantify neurotransmission reliability while taking into full account the metrical properties of the spike train space. This parametric information analysis relies on similarity measures induced by the metrical relations between neural responses as spikes flow in. Thus, in order to assess the entropy, the conditional entropy, and the overall information transfer, this method does not require any a priori decoding algorithm to partition the space into equivalence classes. It therefore allows the optimal parameters of a class of distances to be determined with respect to information transmission. To validate the proposed information-theoretical approach, we study precise temporal decoding of human somatosensory signals recorded using microneurography experiments. For this analysis, we employ a similarity measure based on the Victor-Purpura spike train metrics. We show that with appropriate parameters of this distance, the relative spike times of the mechanoreceptors' responses convey enough information to perform optimal discrimination--defined as maximum metrical information and zero conditional entropy--of 81 distinct stimuli within 40 ms of the first afferent spike. The proposed information-theoretical measure proves to be a suitable generalization of Shannon mutual information in order to consider the metrics of temporal codes explicitly. It allows neurotransmission reliability to be assessed in the presence of large spike train spaces (e.g., neural population codes) with high temporal precision.     

The impact of spike timing variability on the signal-encoding performance of neural spiking models.

It remains unclear whether the variability of neuronal spike trains in vivo arises due to biological noise sources or represents highly precise encoding of temporally varying synaptic input signals. Determining the variability of spike timing can provide fundamental insights into the nature of strategies used in the brain to represent and transmit information in the form of discrete spike trains. In this study, we employ a signal estimation paradigm to determine how variability in spike timing affects encoding of random time-varying signals. We assess this for two types of spiking models: an integrate-and-fire model with random threshold and a more biophysically realistic stochastic ion channel model. Using the coding fraction and mutual information as information-theoretic measures, we quantify the efficacy of optimal linear decoding of random inputs from the model outputs and study the relationship between efficacy and variability in the output spike train. Our findings suggest that variability does not necessarily hinder signal decoding for the biophysically plausible encoders examined and that the functional role of spiking variability depends intimately on the nature of the encoder and the signal processing task; variability can either enhance or impede decoding performance.     

基于梯度下降的脉冲神经元精确序列学习算法

基于梯度下降的脉冲神经元有监督学习算法通过计算梯度最小化目标序列和实际输出序列间的误差使得神经元能激发出目标脉冲序列。然而该算法中的误差函数是基于实际输出脉冲序列和相对应的目标输出脉冲序列动态构建而成,导致算法在收敛时可能出现实际输出序列的个数和期望输出个数不相等的情况。针对这一缺陷提出了一种改进的脉冲神经元梯度下降学习算法,算法在学习过程中检测目标序列脉冲个数和实际激发脉冲个数,并引入虚拟实际激发脉冲和期望激发脉冲构建误差函数以分别解决激发个数不足和激发个数多余的问题。实验结果证明该算法能有效地防止学习算法在输出脉冲个数不等的情况下提前结束,使得神经元能够精确地激发出目标脉冲序列。     

Communication-Efficient Sorting Algorithms on Reconfigurable Array of Processors With Slotted Optical Buses

The reconfigurable array with slotted optical buses (RASOB) has recently received a lot of attention from the research community. In this paper, we first discuss the reconfiguration methods and communication capabilities of the RASOB architecture. Then, we use this architecture for the implementation of efficient sorting algorithms on the 1D RASOB and the 2D RASOB. Our parallel sorting algorithm on the 1D RASOB is based on an efficient divide-and-conquer scheme. It sortsNdata items usingNprocessors inO(k) communication cycles where k is the size of the data items to be sorted in bits. We further develop a parallel sorting algorithm on the 2D RASOB based on the sorting algorithm on the 1D RASOB in conjunction with the well known Rotatesort algorithm. Similarly, this algorithm sortsNdata items on a 2D RASOB of sizeNinO(k) communication cycles. These sorting algorithms are much more efficient than state-of-the-art sorting algorithms on reconfigurable arrays of processors withelectronicbuses using the same number of processors.     

A gradient descent rule for spiking neurons emitting multiple spikes

A supervised learning rule for Spiking Neural Networks (SNNs) is presented that can cope with neurons that spike multiple times. The rule is developed by extending the existing SpikeProp algorithm which could only be used for one spike per neuron. The problem caused by the discontinuity in the spike process is counteracted with a simple but effective rule, which makes the learning process more efficient. Our learning rule is successfully tested on a classification task of Poisson spike trains. We also applied the algorithm on a temporal version of the XOR problem and show that it is possible to learn this classical problem using only one spiking neuron making use of a hair-trigger situation.     

Compression of Binary Images on a Hypercube Machine

The S-tree linear representation is an efficient structure for representing binary images which requires three bits for each disjoint binary region. We present parallel algorithms for encoding and decoding the S-tree representation from/onto a binary pixel array in a hypercube connected machine. Both the encoding and the decoding algorithms make use of a condensation procedure in order to produce the final result cooperatively. The encoding algorithm conceptually uses a pyramid configuration, where in each iteration half of the processors in the grid below it remain active. The decoding algorithm is based on the observation that each processor can independently decode a given binary region if it contains in its memory an S-tree segment augmented with a linear prefix. We analyze the algorithms in terms of processing and communication time and present results of experiments performed with real and randomly generated images that verify our theoretical results.     

Reliable distributed sorting through the application-oriented faulttolerance paradigm

A fault-tolerant parallel sorting algorithm developed using the application-oriented fault tolerance paradigm is presented. The algorithm is tolerant of one processor/link failure in an n-cube. The addition of reliability to the sorting algorithm results in a performance penalty. Asymptotically, the fault-tolerant algorithm is less costly than host sorting. Experimentally it is shown that fault-tolerant sorting quickly becomes more efficient that host sorting when the bitonic sort/merge is considered. The main contribution is the demonstration that the application-oriented fault tolerance paradigm is applicable to problems of a noniterative-convergent nature     

Continuous speech recognition with sparse coding

Sparse coding is an efficient way of coding information. In a sparse code most of the code elements are zero; very few are active. Sparse codes are intended to correspond to the spike trains with which biological neurons communicate. In this article, we show how sparse codes can be used to do continuous speech recognition. We use the TIDIGITS dataset to illustrate the process. First a waveform is transformed into a spectrogram, and a sparse code for the spectrogram is found by means of a linear generative model. The spike train is classified by making use of a spike train model and dynamic programming. It is computationally expensive to find a sparse code. We use an iterative subset selection algorithm with quadratic programming for this process. This algorithm finds a sparse code in reasonable time if the input is limited to a fairly coarse spectral resolution. At this resolution, our system achieves a word error rate of 19%, whereas a system based on Hidden Markov Models achieves a word error rate of 15% at the same resolution.     

Decoding algorithms for shortened-extended turbo product codes in WiMAX systems

The component codes of turbo product codes inWiMAX systems are extended Hamming codes and single parity check codes as well as their shortened forms. In this paper, three novel iterative decoding algorithms based on Chase, MAP algorithms and their combination are proposed for shortened-extended turbo product codes. The iterative decoding algorithm based on Chase algorithm is proposed to reduce the decoding complexity without any performance loss. An efficient MAP algorithm is then proposed to decode the component codes of shortened single parity check codes and shortened-extended Hamming codes. A comprehensive performance comparison of the proposed decoding schemes is conducted for three typical classes of turbo product codes in WiMAX OFDMA systems. The suitable decoding algorithms are recommended for different classes based on the simulation results.     

社交网络中一种快速精确的节点影响力排序算法

在大规模在线社交网络中,通过对用户影响力进行排序找出其中最具影响力的节点（集合）是一个很重要的研究方向,对于有效控制信息扩散、舆情分析和控制、精准营销等均有重要的作用。已有的节点影响力排序算法或者需要网络的全局拓扑信息来计算单个节点影响力（如基于介数中心性的算法）而时间开销过大,不适用于大规模网络;或者基于传统的网页排序算法（如PageRank）而不能很好地处理社交网络中存在着大量“末梢”节点的问题以及不同用户之间的联系强度不同的问题。在传统的PageRank算法的基础上做出了两点改进。首先,通过在PageRank算法的权值回收步骤中考虑对不同的连接赋予不同的权值,有效避免了末梢节点带来的影响。其次,在PageRank算法的投票过程中考虑邻居个体的差异性,提出了一种基于半邻域信息的节点权值分配方法,有效提高了节点排序的准确度。在一个包含大约15 000个用户的样本网络中,我们所提出的改进算法能够找出前1 000个最有影响力的节点中的40%以上的节点,而传统的PageRank算法仅能找出其中11%的节点。同时,相比于基于介数中心性的算法,所提出的改进算法以小得多的时间开销达到了相近甚至更好的排序准确度。     

高效LDPC译码器的优化与FPGA实现

针对高效LDPC译码器设计过程中的参数选择问题,提出了针对Turbo译码消息传播（Turbo decoding message passing,TDMP）译码算法的离散密度进化算法。利用这种离散密度进化算法对译码算法中的校正因子及量化精度进行了优化。与传统的通过数值仿真进行优化的方法相比,本文算法效率大大提高,且效果显著。测试结果表明,优化的定点化译码器与纯浮点仿真相比性能只相差0.1 dB左右。在译码器实现结构设计中提出了一种基于分布式RAM的P消息循环存储结构,与传统的基于寄存器和Benes网络的存储器结构相比,资源消耗明显下降。在Xilinx公司的FPGA平台上进行了硬件实现与测试,结果表明与同类译码器相比在资源消耗和吞吐率上均有一定优势,是一种高效的LDPC硬件译码器。     

A review of methods for spike sorting: the detection and classification of neural action potentials

The detection of neural spike activity is a technical challenge that is a prerequisite for studying many types of brain function. Measuring the activity of individual neurons accurately can be difficult due to large amounts of background noise and the difficulty in distinguishing the action potentials of one neuron from those of others in the local area. This article reviews algorithms and methods for detecting and classifying action potentials, a problem commonly referred to as spike sorting. The article first discusses the challenges of measuring neural activity and the basic issues of signal detection and classification. It reviews and illustrates algorithms and techniques that have been applied to many of the problems in spike sorting and discusses the advantages and limitations of each and the applicability of these methods for different types of experimental demands. The article is written both for the physiologist wanting to use simple methods that will improve experimental yield and minimize the selection biases of traditional techniques and for those who want to apply or extend more sophisticated algorithms to meet new experimental challenges.     

Prufer编解码的最优算法

讨论标号树的Prufer编码的编解码算法.文献中常见的Prufer编解码算法需要O(n log n)时间.文献[1,2,4,9]提出了Prufer编解码的线性时间算法.这些算法都用到了整数排序算法,利用待排序整数的取值特殊性,得到线性时间整数排序算法.由此将Prufer编解码问题的计算归结为整数排序问题.本文从更直接的角度考察Prufer编解码问题,从简单算法出发,挖掘问题的本质特征,逐步简化,得到Prufer编码的一个非常简单实用的线性时间最优编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.