Complexity Results on Learning by Neural Nets

We consider the computational complexity of learning by neural nets. We are interested in how hard it is to design appropriate neural net architectures and to train neural nets for general and specialized learning tasks. Our main result shows that the training problem for 2-cascade neural nets (which have only two non-input nodes, one of which is hidden) is N-complete, which implies that finding an optimal net (in terms of the number of non-input units) that is consistent with a set of examples is also N-complete. This result also demonstrates a surprising gap between the computational complexities of one-node (perceptron) and two-node neural net training problems, since the perceptron training problem can be solved in polynomial time by linear programming techniques. We conjecture that training a k-cascade neural net, which is a classical threshold network training problem, is also N-complete, for each fixed k2. We also show that the problem of finding an optimal perceptron (in terms of the number of non-zero weights) consistent with a set of training examples is N-hard.Our neural net learning model encapsulates the idea of modular neural nets, which is a popular approach to overcoming the scaling problem in training neural nets. We investigate how much easier the training problem becomes if the class of concepts to be learned is known a priori and the net architecture is allowed to be sufficiently non-optimal. Finally, we classify several neural net optimization problems within the polynomial-time hierarchy.     

Topological network design: A survey

We consider the problem of topological optimization of communication networks subject to a number of design constraints, such as maximum network diameter, maximum node degree, k-node (link) survivability, and network fault tolerance. The primary design problem can be described as follows: Given a set of network nodes, it is required to find a topology Ψ, selected from all possible topologies, so that the cost of Ψ (measured possibly in terms of the maximum diameter, maximum node degree, etc.) is less than that of any other network topology and such that Ψ satisfies some given design constraints. Fault tolerance is concerned with the ability of the network nodes to communicate in the presence of a set of faulty links and/or nodes. The network design problem considering reliability constraints is NP-hard. We classify the research efforts presented in the literature for solving the topological optimization design problem as hierarchical, enumerative, or iterative techniques. In this paper, we provide a survey of the topological network design techniques under different design constraints. Experimental results obtained by applying a number of algorithms to a set of randomly generated networks are presented and compared.     

An optimized instance based learning algorithm for estimation of compressive strength of concrete

This article proposes an optimized instance-based learning approach for prediction of the compressive strength of high performance concrete based on mix data, such as water to binder ratio, water content, super-plasticizer content, fly ash content, etc. The base algorithm used in this study is the k nearest neighbor algorithm, which is an instance-based machine leaning algorithm. Five different models were developed and analyzed to investigate the effects of the number of neighbors, the distance function and the attribute weights on the performance of the models. For each model a modified version of the differential evolution algorithm was used to find the optimal model parameters. Moreover, two different models based on generalized regression neural network and stepwise regressions were also developed. The performances of the models were evaluated using a set of high strength concrete mix data. The results of this study indicate that the optimized models outperform those derived from the standard k nearest neighbor algorithm, and that the proposed models have a better performance in comparison to generalized regression neural network, stepwise regression and modular neural networks models.     

On the Sample Complexity for Nonoverlapping Neural Networks

A neural network is said to be nonoverlapping if there is at most one edge outgoing from each node. We investigate the number of examples that a learning algorithm needs when using nonoverlapping neural networks as hypotheses. We derive bounds for this sample complexity in terms of the Vapnik-Chervonenkis dimension. In particular, we consider networks consisting of threshold, sigmoidal and linear gates. We show that the class of nonoverlapping threshold networks and the class of nonoverlapping sigmoidal networks on n inputs both have Vapnik-Chervonenkis dimension (nlog n). This bound is asymptotically tight for the class of nonoverlapping threshold networks. We also present an upper bound for this class where the constants involved are considerably smaller than in a previous calculation. Finally, we argue that the Vapnik-Chervonenkis dimension of nonoverlapping threshold or sigmoidal networks cannot become larger by allowing the nodes to compute linear functions. This sheds some light on a recent result that exhibited neural networks with quadratic Vapnik-Chervonenkis dimension.     

Classical and superposed learning for quantum weightless neural networks

A supervised learning algorithm for quantum neural networks (QNN) based on a novel quantum neuron node implemented as a very simple quantum circuit is proposed and investigated. In contrast to the QNN published in the literature, the proposed model can perform both quantum learning and simulate the classical models. This is partly due to the neural model used elsewhere which has weights and non-linear activations functions. Here a quantum weightless neural network model is proposed as a quantisation of the classical weightless neural networks (WNN). The theoretical and practical results on WNN can be inherited by these quantum weightless neural networks (qWNN). In the quantum learning algorithm proposed here patterns of the training set are presented concurrently in superposition. This superposition-based learning algorithm (SLA) has computational cost polynomial on the number of patterns in the training set.     

A comparative study of the scalability of a sensitivity-based learning algorithm for artificial neural networks

Until recently, the most common criterion in machine learning for evaluating the performance of algorithms was accuracy. However, the unrestrainable growth of the volume of data in recent years in fields such as bioinformatics, intrusion detection or engineering, has raised new challenges in machine learning not simply regarding accuracy but also scalability. In this research, we are concerned with the scalability of one of the most well-known paradigms in machine learning, artificial neural networks (ANNs), particularly with the training algorithm Sensitivity-Based Linear Learning Method (SBLLM). SBLLM is a learning method for two-layer feedforward ANNs based on sensitivity analysis, that calculates the weights by solving a linear system of equations. The results show that the training algorithm SBLLM performs better in terms of scalability than five of the most popular and efficient training algorithms for ANNs.     

Complexity of min-max subsequence problems

We determine the computational complexity of the problem of ordering a set of n numbers, either into a sequence or a cycle, such that the maximum sum of any k successive numbers is minimal. Both problems are easy for k=2 and strongly NP-hard for any k?3. However, the two problems allow a polynomial-time approximation scheme that is linear in n.     

Multi-class pattern classification using neural networks

Multi-class pattern classification has many applications including text document classification, speech recognition, object recognition, etc. Multi-class pattern classification using neural networks is not a trivial extension from two-class neural networks. This paper presents a comprehensive and competitive study in multi-class neural learning with focuses on issues including neural network architecture, encoding schemes, training methodology and training time complexity. Our study includes multi-class pattern classification using either a system of multiple neural networks or a single neural network, and modeling pattern classes using one-against-all, one-against-one, one-against-higher-order, and P-against-Q. We also discuss implementations of these approaches and analyze training time complexity associated with each approach. We evaluate six different neural network system architectures for multi-class pattern classification along the dimensions of imbalanced data, large number of pattern classes, large vs. small training data through experiments conducted on well-known benchmark data.     

Locating centers in a dynamically changing network,and related problems

In a dynamically changing network, the costs or distances between locations are changing in each discrete time period. We consider the location of emergency facilities that must minimize the maximum distance to any customer on the network across all time periods. We call the problem of locating p centers over k underlying networks corresponding to k periods the k-Network p-Center problem. The problem is considered when, in each period, the network satisfies the triangle inequality. In this paper, we provide a polynomial time 3-approximation algorithm for Δ k-Network p-Center for the case k=2. We discuss generalizations inspired by this problem to other optimization problems with multiple underlying networks and the objective of finding a single solution that varies as little as possible from the optimum for each network. The additional combinatorial problems discussed include: sorting; perfect matching; shortest path; minimum spanning tree; and minimum cut. All are shown to be NP-hard for k⩾2.     

On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions

We study networks of spiking neurons that use the timing of pulses to encode information. Nonlinear interactions model the spatial groupings of synapses on the neural dendrites and describe the computations performed at local branches. Within a theoretical framework of learning we analyze the question of how many training examples these networks must receive to be able to generalize well. Bounds for this sample complexity of learning can be obtained in terms of a combinatorial parameter known as the pseudodimension. This dimension characterizes the computational richness of a neural network and is given in terms of the number of network parameters. Two types of feedforward architectures are considered: constant-depth networks and networks of unconstrained depth. We derive asymptotically tight bounds for each of these network types. Constant depth networks are shown to have an almost linear pseudodimension, whereas the pseudodimension of general networks is quadratic. Networks of spiking neurons that use temporal coding are becoming increasingly more important in practical tasks such as computer vision, speech recognition, and motor control. The question of how well these networks generalize from a given set of training examples is a central issue for their successful application as adaptive systems. The results show that, although coding and computation in these networks is quite different and in many cases more powerful, their generalization capabilities are at least as good as those of traditional neural network models.     

An MLP-based representation of neural tensor networks for the RDF data models

In this paper, a new representation of neural tensor networks is presented. Recently, state-of-the-art neural tensor networks have been introduced to complete RDF knowledge bases. However, mathematical model representation of these networks is still a challenging problem, due to tensor parameters. To solve this problem, it is proposed that these networks can be represented as two-layer perceptron network. To complete the network topology, the traditional gradient based learning rule is then developed. It should be mentioned that for tensor networks there have been developed some learning rules which are complex in nature due to the complexity of the objective function used. Indeed, this paper is aimed to show that the tensor network can be viewed and represented by the two-layer feedforward neural network in its traditional form. The simulation results presented in the paper easily verify this claim.

     

Algorithms for maximum weight induced paths

A family of graphs is a k-bounded-hole family if every graph in the family has no holes with more than k vertices. The problem of finding in a graph a maximum weight induced path has applications in large communication and neural networks when worst case communication time needs to be evaluated; unfortunately this problem is NP-hard even when restricted to bipartite graphs. We show that this problem has polynomial time algorithms for k-bounded-hole families of graphs, for interval-filament graphs and for graphs decomposable by clique cut-sets or by splits into prime subgraphs for which such algorithms exist.     

Blind equalization of a noisy channel by linear neural network

In this paper, a new neural approach is introduced for the problem of blind equalization in digital communications. Necessary and sufficient conditions for blind equalization are proposed, which can be implemented by a two-layer linear neural network, in the hidden layer, the received signals are whitened, while the network outputs provide directly an estimation of the source symbols. We consider a stochastic approximate learning algorithm for each layer according to the property of the correlation matrices of the transmitted symbols. The proposed class of networks yield good results in simulation examples for the blind equalization of a three-ray multipath channel.     

Dynamic optimal learning rates of a certain class of fuzzy neuralnetworks and its applications with genetic algorithm

The stability analysis of the learning rate for a two-layer neural network (NN) is discussed first by minimizing the total squared error between the actual and desired outputs for a set of training vectors. The stable and optimal learning rate, in the sense of maximum error reduction, for each iteration in the training (back propagation) process can therefore be found for this two-layer NN. It has also been proven in this paper that the dynamic stable learning rate for this two-layer NN must be greater than zero. Thus it Is guaranteed that the maximum error reduction can be achieved by choosing the optimal learning rate for the next training iteration. A dynamic fuzzy neural network (FNN) that consists of the fuzzy linguistic process as the premise part and the two-layer NN as the consequence part is then illustrated as an immediate application of our approach. Each part of this dynamic FNN has its own learning rate for training purpose. A genetic algorithm is designed to allow a more efficient tuning process of the two learning rates of the FNN. The objective of the genetic algorithm is to reduce the searching time by searching for only one learning rate, which is the learning rate of the premise part, in the FNN. The dynamic optimal learning rates of the two-layer NN can be found directly using our innovative approach. Several examples are fully illustrated and excellent results are obtained for the model car backing up problem and the identification of nonlinear first order and second order systems.     

Participant selection for <Emphasis Type="Italic">t</Emphasis>-sweep <Emphasis Type="Italic">k</Emphasis>-coverage crowd sensing tasks

With the popularization of wireless networks and mobile intelligent terminals, mobile crowd sensing is becoming a promising sensing paradigm. Tasks are assigned to users with mobile devices, which then collect and submit ambient information to the server. The composition of participants greatly determines the quality and cost of the collected information. This paper aims to select fewest participants to achieve the quality required by a sensing task. The requirement namely “t-sweep k-coverage” means for a target location, every t time interval should at least k participants sense. The participant selection problem for “t-sweep k-coverage” crowd sensing tasks is NP-hard. Through delicate matrix stacking, linear programming can be adopted to solve the problem when it is in small size. We further propose a participant selection method based on greedy strategy. The two methods are evaluated through simulated experiments using users’ call detail records. The results show that for small problems, both the two methods can find a participant set meeting the requirement. The number of participants picked by the greedy based method is roughly twice of the linear programming based method. However, when problems become larger, the linear programming based method performs unstably, while the greedy based method can still output a reasonable solution.     

Delay dependent stability results for fuzzy BAM neural networks with Markovian jumping parameters

This paper deals with the delay-dependent asymptotic stability analysis problem for a class of fuzzy bidirectional associative memory (BAM) neural networks with time-varying interval delays and Markovian jumping parameters by Takagi–Sugeno (T–S) fuzzy model. The nonlinear delayed BAM neural networks are first established as a modified T–S fuzzy model in which the consequent parts are composed of a set of Markovian jumping BAM neural networks with time-varying interval delays. The jumping parameters considered here are generated from a continuous-time discrete-state homogeneous Markov process, which are governed by a Markov process with discrete and finite-state space. The new type of Markovian jumping matrices P_k and Q_k are introduced in this paper. The parameter uncertainties are assumed to be norm bounded and the delay is assumed to be time-varying and belong to a given interval, which means that the lower and upper bounds of interval time-varying delays are available. A new delay-dependent stability condition is derived in terms of linear matrix inequality by constructing a new Lyapunov–Krasovskii functional and introducing some free-weighting matrices. Numerical examples are given to demonstrate the effectiveness of the proposed methods.     

Learning Bayesian Networks: The Combination of Knowledge and Statistical Data

We describe a Bayesian approach for learning Bayesian networks from a combination of prior knowledge and statistical data. First and foremost, we develop a methodology for assessing informative priors needed for learning. Our approach is derived from a set of assumptions made previously as well as the assumption of likelihood equivalence, which says that data should not help to discriminate network structures that represent the same assertions of conditional independence. We show that likelihood equivalence when combined with previously made assumptions implies that the user's priors for network parameters can be encoded in a single Bayesian network for the next case to be seen—a prior network—and a single measure of confidence for that network. Second, using these priors, we show how to compute the relative posterior probabilities of network structures given data. Third, we describe search methods for identifying network structures with high posterior probabilities. We describe polynomial algorithms for finding the highest-scoring network structures in the special case where every node has at most k = 1 parent. For the general case (k > 1), which is NP-hard, we review heuristic search algorithms including local search, iterative local search, and simulated annealing. Finally, we describe a methodology for evaluating Bayesian-network learning algorithms, and apply this approach to a comparison of various approaches.     

Neural Network Modeling of the Level of Observation Decision in an Acute Psychiatric Ward

Patients in an acute psychiatric ward need to be observed with varying levels of closeness. We report a series of experiments in which neural networks were trained to model this “level of observation” decision. One hundred eighty-seven such clinical decisions were used to train and test the networks which were evaluated by a multitrialv-fold cross-validation procedure. One neural network modeling approach was to break down the decision process into four subproblems, each of which was solved by a perceptron unit. This resulted in a hierarchical perceptron network having a structure that was equivalent to a sparsely connected two-layer perceptron. Neural network approaches were compared with nearest neighbor, linear regression, and naive Bayes classifiers. The hierarchical and sparse neural networks were the most accurate classifiers. This shows that the decision process is nonlinear, that neural nets can be more accurate than other statistical approaches, and that hierarchical decomposition is a useful methodology for neural network design.     

Bayesian neural networks at scale: a performance analysis and pruning study

Bayesian neural networks (BNNs) are a promising method of obtaining statistical uncertainties for neural network predictions but with a higher computational overhead which can limit their practical usage. This work explores the use of high-performance computing with distributed training to address the challenges of training BNNs at scale. We present a performance and scalability comparison of training the VGG-16 and Resnet-18 models on a Cray-XC40 cluster. We demonstrate that network pruning can speed up inference without accuracy loss and provide an open-source software package, BPrune, to automate this pruning. For certain models we find that pruning up to 80% of the network results in only a 7.0% loss in accuracy. With the development of new hardware accelerators for deep learning, BNNs are of considerable interest for benchmarking performance. This analysis of training a BNN at scale outlines the limitations and benefits compared to a conventional neural network.

     

Generalization and PAC learning: some new results for the class ofgeneralized single-layer networks

The ability of connectionist networks to generalize is often cited as one of their most important properties. We analyze the generalization ability of the class of generalized single-layer networks (GSLNs), which includes Volterra networks, radial basis function networks, regularization networks, and the modified Kanerva model, using techniques based on the theory of probably approximately correct (PAC) learning which have previously been used to analyze the generalization ability of feedforward networks of linear threshold elements (LTEs). An introduction to the relevant computational learning theory is included. We derive necessary and sufficient conditions on the number of training examples required by a GSLN to guarantee a particular generalization performance. We compare our results to those given previously for feedforward networks of LTEs and show that, on the basis of the currently available bounds, the sufficient number of training examples for GSLNs is typically considerably less than for feedforward networks of LTEs with the same number of weights. We show that the use of self-structuring techniques for GSLNs may reduce the number of training examples sufficient to guarantee good generalization performance, and we provide an explanation for the fact that GSLNs can require a relatively large number of weights.