POLYNOMIAL TIME ALGORITHMS FOR LEARNING NEURAL NETS OF NONOVERLAPPING PERCEPTRONS

We investigate the problem of learning two-layer neural nets of nonoverlapping perceptrons where each input unit is connected to one and only one hidden unit. We first show that this restricted problem with no overlap at all between the receptive fields of the hidden units is as hard as the general problem (with total overlap) if the learner uses examples only. However, if membership queries are allowed, the restricted problem is indeed easier to solve. We give a learning algorithm that uses examples and membership queries to PAC learn the intersection of K -nonoverlapping perceptrons, regardless of whether the instance space in Boolean, discrete, or continuous. An extension of this algorithm is proven to PAC learn two-layer nets with K -nonoverlapping perceptrons. The simulations performed indicate that both algorithms are fast and efficient.     

Supervised Learning of Logical Operations in Layered Spiking Neural Networks with Spike Train Encoding

Few algorithms for supervised training of spiking neural networks exist that can deal with patterns of multiple spikes, and their computational properties are largely unexplored. We demonstrate in a set of simulations that the ReSuMe learning algorithm can successfully be applied to layered neural networks. Input and output patterns are encoded as spike trains of multiple precisely timed spikes, and the network learns to transform the input trains into target output trains. This is done by combining the ReSuMe learning algorithm with multiplicative scaling of the connections of downstream neurons. We show in particular that layered networks with one hidden layer can learn the basic logical operations, including Exclusive-Or, while networks without hidden layer cannot, mirroring an analogous result for layered networks of rate neurons. While supervised learning in spiking neural networks is not yet fit for technical purposes, exploring computational properties of spiking neural networks advances our understanding of how computations can be done with spike trains.     

Connectivity and performance tradeoffs in the cascade correlationlearning architecture

The cascade correlation is a very flexible, efficient and fast algorithm for supervised learning. It incrementally builds the network by adding hidden units one at a time, until the desired input/output mapping is achieved. It connects all the previously installed units to the new unit being added. Consequently, each new unit in effect adds a new layer and the fan-in of the hidden and output units keeps on increasing as more units get added. The resulting structure could be hard to implement in VLSI, because the connections are irregular and the fan-in is unbounded. Moreover, the depth or the propagation delay through the resulting network is directly proportional to the number of units and can be excessive. We have modified the algorithm to generate networks with restricted fan-in and small depth (propagation delay) by controlling the connectivity. Our results reveal that there is a tradeoff between connectivity and other performance attributes like depth, total number of independent parameters, and learning time.     

A fast learning algorithm for deep belief nets

We show how to use "complementary priors" to eliminate the explaining-away effects that make inference difficult in densely connected belief nets that have many hidden layers. Using complementary priors, we derive a fast, greedy algorithm that can learn deep, directed belief networks one layer at a time, provided the top two layers form an undirected associative memory. The fast, greedy algorithm is used to initialize a slower learning procedure that fine-tunes the weights using a contrastive version of the wake-sleep algorithm. After fine-tuning, a network with three hidden layers forms a very good generative model of the joint distribution of handwritten digit images and their labels. This generative model gives better digit classification than the best discriminative learning algorithms. The low-dimensional manifolds on which the digits lie are modeled by long ravines in the free-energy landscape of the top-level associative memory, and it is easy to explore these ravines by using the directed connections to display what the associative memory has in mind.     

Detection of Spikes with Artificial Neural Networks Using Raw EEG

Artificial neural networks (ANN) using raw electroencephalogram (EEG) data were developed and tested off-line to detect transient epileptiform discharges (spike and spike/wave) and EMG activity in an ongoing EEG. In the present study, a feedforward ANN with a variable number of input and hidden layer units and two output units was used to optimize the detection system. The ANN system was trained and tested with the backpropagation algorithm using a large data set of exemplars. The effects of different EEG time windows and the number of hidden layer neurons were examined using rigorous statistical tests for optimum detection sensitivity and selectivity. The best ANN configuration occurred with an input time window of 150 msec (30 input units) and six hidden layer neurons. This input interval contained information on the wave component of the epileptiform discharge which improved detection. Two-dimensional receiver operating curves were developed to define the optimum threshold parameters for best detection. Comparison with previous networks using raw EEG showed improvement in both sensitivity and selectivity. This study showed that raw EEG can be successfully used to train ANNs to detect epileptogenic discharges with a high success rate without resorting to experimenter-selected parameters which may limit the efficiency of the system.     

Computational capabilities of recurrent NARX neural networks

Recently, fully connected recurrent neural networks have been proven to be computationally rich-at least as powerful as Turing machines. This work focuses on another network which is popular in control applications and has been found to be very effective at learning a variety of problems. These networks are based upon Nonlinear AutoRegressive models with eXogenous Inputs (NARX models), and are therefore called NARX networks. As opposed to other recurrent networks, NARX networks have a limited feedback which comes only from the output neuron rather than from hidden states. They are formalized by y(t)=Psi(u(t-n(u)), ..., u(t-1), u(t), y(t-n(y)), ..., y(t-1)) where u(t) and y(t) represent input and output of the network at time t, n(u) and n(y) are the input and output order, and the function Psi is the mapping performed by a Multilayer Perceptron. We constructively prove that the NARX networks with a finite number of parameters are computationally as strong as fully connected recurrent networks and thus Turing machines. We conclude that in theory one can use the NARX models, rather than conventional recurrent networks without any computational loss even though their feedback is limited. Furthermore, these results raise the issue of what amount of feedback or recurrence is necessary for any network to be Turing equivalent and what restrictions on feedback limit computational power.     

Learning efficiency of redundant neural networks in Bayesianestimation

This paper proves that the Bayesian stochastic complexity of a layered neural network is asymptotically smaller than that of a regular statistical model if it contains the true distribution. We consider a case when a three-layer perceptron with M input units, H hidden units and N output units is trained to estimate the true distribution represented by the model with H(0) hidden units and prove that the stochastic complexity is asymptotically smaller than (1/2) {H(0 ) (M+N)+R} log n where n is the number of training samples and R is a function of H-H(0), M, and N that is far smaller than the number of redundant parameters. Since the generalization error of Bayesian estimation is equal to the increase of stochastic complexity, it is smaller than (1/2 n) {H(0) (M+N)+R} if it has an asymptotic expansion. Based on the results, the difference between layered neural networks and regular statistical models is discussed from the statistical point of view.     

Learning Nonoverlapping Perceptron Networks from Examples and Membership Queries

We investigate, within the PAC learning model, the problem of learning nonoverlapping perceptron networks (also known as read-once formulas over a weighted threshold basis). These are loop-free neural nets in which each node has only one outgoing weight. We give a polynomial time algorithm that PAC learns any nonoverlapping perceptron network using examples and membership queries. The algorithm is able to identify both the architecture and the weight values necessary to represent the function to be learned. Our results shed some light on the effect of the overlap on the complexity of learning in neural networks.     

RBF网学习的进化优选算法

讨论了用正交最小二乘算法训练ＲＢＦ网的不足之处,然后引入了选择路径的概念,在此基础上,提出了ＲＢＦ网隐层节点选取的进化优选算法,仿真结果表明,在不同的精度要求下,用进化优选算法均能设计出比正交最小二乘算法更小的ＲＢＦ网。     

能量限制的连通支配集分布式构造

在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网以进行分层路由。在支配集中的节点的耗能相对其它节点要多,虚拟骨干网的生存周期由剩余能量最小的传感器节点决定。提出了一个有能量门限限制的连通支配集分布式构造算法,算法的主要思路是从任一节点开始,采用邻域深度优先搜索,当一个方向搜索结束时再回朔搜索其它方向来形成连通支配集;若某一支配点的邻域中的节点能量小于门限值,则回朔搜索其它方向来形成支配集。     

Conventional modeling of the multilayer perceptron using polynomialbasis functions

A technique for modeling the multilayer perceptron (MLP) neural network, in which input and hidden units are represented by polynomial basis functions (PBFs), is presented. The MLP output is expressed as a linear combination of the PBFs and can therefore be expressed as a polynomial function of its inputs. Thus, the MLP is isomorphic to conventional polynomial discriminant classifiers or Volterra filters. The modeling technique was successfully applied to several trained MLP networks.     

On the computational complexity of binary and analog symmetric hopfield nets

We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this problem in the case of binary nets. Finally, we show that symmetric analog nets with an external clock are computationally Turing universal.     

Feedforward neural network construction using cross validation.

This article presents an algorithm that constructs feedforward neural networks with a single hidden layer for pattern classification. The algorithm starts with a small number of hidden units in the network and adds more hidden units as needed to improve the network's predictive accuracy. To determine when to stop adding new hidden units, the algorithm makes use of a subset of the available training samples for cross validation. New hidden units are added to the network only if they improve the classification accuracy of the network on the training samples and on the cross-validation samples. Extensive experimental results show that the algorithm is effective in obtaining networks with predictive accuracy rates that are better than those obtained by state-of-the-art decision tree methods.     

A fast parallel algorithm for routing unicast assignments in Benesnetworks

This paper presents a new parallel algorithm for routing unicast (one-to-one) assignments in Benes networks. Parallel routing algorithms for such networks were reported earlier, but these algorithms were designed primarily to route permutation assignments. The routing algorithm presented in this paper removes this restriction without an increase in the order of routing cost or routing time. We realize this new routing algorithm on two different topologies. The algorithm routes a unicast assignment involving O(k) pairs of inputs and outputs in O(lg ² k+lg n) time on a completely connected network of n processors and in O(lg⁴ k+lg² k lg n) time on an extended shuffle-exchange network of n processors. Using O(n lg n) professors, the same algorithm can be pipelined to route α unicast assignments each involving O(k) pairs of inputs and outputs, in O(lg² k+lg n+(α-1) lg k) time on a completely connected network and in O(lg⁴ k+lg² k lg n+(α-1)(lg ³ k+lg k lg n)) time on the extended shuffle-exchange network. These yield an average routing time of O(lg k) in the first case, and O(lg³ k+1g k lg n) in the second case, for all α⩾lg n. These complexities indicate that the algorithm given in this paper is as fast as Nassimi and Sahni's algorithm for unicast assignments, and with pipelining, it is faster than the same algorithm at least by a factor of O(lg n) on both topologies. Furthermore, for sparse assignments, i.e., when k=O(1), it is the first algorithm which has an average routing time of O(1g n) on a topology with O(n) links     

Hidden control neural architecture modeling of nonlinear timevarying systems and its applications

The application of neural networks to modeling time-invariant nonlinear systems has been difficult for complicated nonstationary signals, such as speech, because the networks are unable to characterize temporal variability. This problem is addressed by proposing a network architecture, called the hidden control neural network (HCNN), for modeling signals generated by nonlinear dynamical systems with restricted time variability. The mapping implemented by a multilayered neural network is allowed to change with time as a function of an additional control input signal. The network is trained using an algorithm based on ;backpropagation' and segmentation algorithms for estimating the unknown control together with the network's parameters. Application of the network to the segmentation and modeling of a signal produced by a time-varying nonlinear system, speaker-independent recognition of spoken connected digits, and online recognition of handwritten characters demonstrates the ability of the HCNN to learn time-varying nonlinear dynamics and its potential for high-performance recognition of signals produced by time-varying sources.     

A learning algorithm for Recurrent Radial Basis Function Networks

This paper proposes a Recurrent Radial Basis Function network (RRBFN) that can be applied to temporal pattern classifications and predictions. Based on the architecture of the conventional Radial Basis Function networks, the RRBFNs use Gaussian nonlinearity and have feedback paths between every hidden node. These feedback paths enable the networks to learn temporal patterns without an input buffer to hold the recent elements of an input sequence. A gradient descent learning algorithm for the RRBFNs is derived. Two RRBFNs with different number of hidden nodes were tested using a temporal sequence generated by an infinite impulse response filter. The results show that the RRBFNs can approximate the filter more accurate than the Continually Running Fully Recurrent networks trained by the Real-Time Recurrent Learning algorithm.     

Refinements of universal approximation results for deep belief networks and restricted Boltzmann machines

We improve recently published results about resources of restricted Boltzmann machines (RBM) and deep belief networks (DBN)required to make them universal approximators. We show that any distribution pon the set {0,1}(n) of binary vectors of length n can be arbitrarily well approximated by an RBM with k-1 hidden units, where k is the minimal number of pairs of binary vectors differing in only one entry such that their union contains the support set of p. In important cases this number is half the cardinality of the support set of p (given in Le Roux & Bengio, 2008). We construct a DBN with 2n/ 2(n-b) , b ～ log n, hidden layers of width n that is capable of approximating any distribution on {0,1}(n) arbitrarily well. This confirms a conjecture presented in Le Roux and Bengio (2010).     

A new pruning heuristic based on variance analysis of sensitivityinformation

Architecture selection is a very important aspect in the design of neural networks (NNs) to optimally tune performance and computational complexity. Sensitivity analysis has been used successfully to prune irrelevant parameters from feedforward NNs. This paper presents a new pruning algorithm that uses the sensitivity analysis to quantify the relevance of input and hidden units. A new statistical pruning heuristic is proposed, based on the variance analysis, to decide which units to prune. The basic idea is that a parameter with a variance in sensitivity not significantly different from zero, is irrelevant and can be removed. Experimental results show that the new pruning algorithm correctly prunes irrelevant input and hidden units. The new pruning algorithm is also compared with standard pruning algorithms.     

一种主动秘密共享算法

在电子商务和开放网络中，有一类高度机密且长期有效的密钥需要保护．直接使用传统密码学甚至门限密码学提供的方法都不能很好地保证其安全性．而主动秘密共享方案则能较好地解决这类问题．它是在(t 1，n)-门限密码学密钥共享的基础上，通过周期性地刷新影子的值(但不改变共享的密钥)并清除原来的影子值，使得攻击者在一个周期中获得的信息在刷新之后变得毫无用处．所以，攻击者要想窃取一个系统的密钥，必须在同一个周期内攻破t个以上的服务器才可能成功．因此，合理设置门限参数和时间周期的长短就可以保证密钥的长期安全性．迄今为止，只有一个有缺陷的主动秘密共享算法．在此给出一个针对离散对数密钥的主动共享算法，并完整地证明了其安全性和鲁棒性．     

Learning a circuit by injecting values

We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of the circuit's single output wire may be observed. We give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) Boolean circuits of constant depth and unbounded fan-in over AND, OR, and NOT gates. Thus, both AC0 and NC1 circuits are learnable in polynomial time in this model. Negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn AND/OR circuits of unbounded depth and fan-in; it is NP-hard to learn AND/OR circuits of unbounded depth and fan-in 2; and it is NP-hard to learn circuits of constant depth and unbounded fan-in over AND, OR, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. We also consider the effect of adding an oracle for behavioral equivalence. In this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn Boolean circuits with arbitrary fan-in and unbounded depth over AND, OR, and NOT gates. A corollary is that these two classes are PAC-learnable if experiments are available. Finally, we consider an extension of the model called the synchronous model. We show that an even more general class of circuits are learnable in this model. In particular, we are able to learn circuits with cycles.