Weight smoothing to improve network generalization

A weight smoothing algorithm is proposed in this paper to improve a neural network's generalization capability. The algorithm can be used when the data patterns to be classified are presented on an n-dimensional grid (n>/=1) and there exists some correlations among neighboring data points within a pattern. For a fully-interconnected feedforward net, no such correlation information is embedded into the architecture. Consequently, the correlations can only be extracted through sufficient amount of network training. With the proposed algorithm, a smoothing constraint is incorporated into the objective function of backpropagation to reflect the neighborhood correlations and to seek those solutions that have smooth connection weights. Experiments were performed on problems of waveform classification, multifont alphanumeric character recognition, and handwritten numeral recognition. The results indicate that (1) networks trained with the algorithm do have smooth connection weights, and (2) they generalize better.     

Comments on “Can backpropagation error surface not have localminima?”

in the above paper Yu (IEEE Trans. Neural Networks, vol.3, no.6, p.1019-21 (1992)) claims to prove that local minima do not exist in the error surface of backpropagation networks being trained on data with t distinct input patterns when the network is capable of exactly representing arbitrary mappings on t input patterns. The commenter points out that the proof presented is flawed, so that the resulting claims remain unproved. In reply, Yu points out that the undesired phenomenon that was sited can be avoided by simply imposing the arbitrary mapping capacity of the network on lemma 1 in the article.     

Hierarchical models for analysis and recognition of handwritten characters

Different hierarchical models in pattern analysis and recognition are proposed, based on occurrence probability of patterns. As an important application of recognizing handprinted characters, three typical kinds of hierarchical models such asM _89-89,M _89-36 andM _36-36 have been presented, accompanied by the computer algorithms for computing recognition rates of pattern parts. Moreover, a comparative study of their recognition rates has been conducted theoretically; and numerical experiments have been carried out to verify the analytical conclusions made. Various hierarchical models deliberated in this paper can provide users more or better choices of pattern models in practical application, and lead to a uniform computational scheme (or code). The recognition rates of parts can be improved remarkably by a suitable hierarchical model. For the modelM _89-36 in which case some of the Canadian standard handprinted characters have multiple occurrence probabilities, the total mean recognition rates of the given sample may reach 120% of that by the model proposed by Li et al., and 156% of that obtained from the subjective experiments reported by Suen.     

Machine independent AND and OR parallel execution of logicprograms. I. The binding environment

We describe a binding environment for the AND and OR parallel execution of logic programs that is suitable for both shared and nonshared memory multiprocessors. The binding environment was designed with a view of rendering a compiler using this binding environment machine independent. The binding environment is similar to closed environments proposed by J. Conery. However, unlike Conery's scheme, it supports OR and independent AND parallelism on both types of machines. The term representation, the algorithms for unification and the join algorithms for parallel AND branches are presented in this paper. We also detail the differences between our scheme and Conery's scheme. A compiler based on this binding environment has been implemented on a platform for machine independent parallel programming called the Chare Kernel     

On loop transformations for generalized cycle shrinking

This paper describes several loop transformation techniques for extracting parallelism from nested loop structures. Nested loops can then be scheduled to run in parallel so that execution time is minimized. One technique is called selective cycle shrinking, and the other is called true dependence cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how true dependence shrinking is related to conflict-free mappings of higher dimensional algorithms into lower dimensional processor arrays. Methods are proposed in this paper to find the selective and true dependence shrinkings with minimum total execution time by applying the techniques of finding optimal linear schedules and optimal and conflict-free mappings proposed by W. Shang and A.B. Fortes     

The fault-tolerant extension problem for complete multipartitenetworks

We develop a characterization for m-fault-tolerant extensions, and for optimal m-fault-tolerant extensions, of a complete multipartite graph. Our formulation shows that this problem is equivalent to an interesting combinatorial problem on the partitioning of integers. This characterization leads to a new procedure for constructing an optimal m-fault-tolerant extension of any complete multipartite graph, for any m⩾0. The proposed procedure is mainly useful when the size of the graph is relatively small, because the search time required is exponential. This exponential search, however, is not always necessary. We prove several necessary conditions that help us, in several cases, to identify some optimal m-fault-tolerant extensions without performing any search     

Structuring fault-tolerant object systems for modularity in adistributed environment

The object-oriented approach to system structuring has found widespread acceptance among designers and developers of robust computing systems. The authors propose a system structure for distributed programming systems that support persistent objects and describe how properties such as persistence and recoverability can be implemented. The proposed structure is modular, permitting easy exploitation of any distributed computing facilities provided by the underlying system. An existing system constructed according to the principles espoused here is examined to illustrate the practical utility of the proposed approach to system structuring     

Scheduling DAG's for asynchronous multiprocessor execution

A new approach is given for scheduling a sequential instruction stream for execution “in parallel” on asynchronous multiprocessors. The key idea in our approach is to exploit the fine grained parallelism present in the instruction stream. In this context, schedules are constructed by a careful balancing of execution and communication costs at the level of individual instructions, and their data dependencies. Three methods are used to evaluate our approach. First, several existing methods are extended to the fine grained situation. Our approach is then compared to these methods using both static schedule length analyses, and simulated executions of the scheduled code. In each instance, our method is found to provide significantly shorter schedules. Second, by varying parameters such as the speed of the instruction set, and the speed/parallelism in the interconnection structure, simulation techniques are used to examine the effects of various architectural considerations on the executions of the schedules. These results show that our approach provides significant speedups in a wide-range of situations. Third, schedules produced by our approach are executed on a two-processor Data General shared memory multiprocessor system. These experiments show that there is a strong correlation between our simulation results, and these actual executions, and thereby serve to validate the simulation studies. Together, our results establish that fine grained parallelism can be exploited in a substantial manner when scheduling a sequential instruction stream for execution “in parallel” on asynchronous multiprocessors     

Neural network control of communications systems

Neural networks appear well suited to applications in the control of communications systems for two reasons: adaptivity and high speed. This paper describes application of neural networks to two problems, admission control and switch control, which exploit the adaptivity and speed property, respectively. The admission control problem is the selective admission of a set of calls from a number of inhomogeneous call classes, which may have widely differing characteristics as to their rate and variability of traffic, onto a network. It is usually unknown in advance which combinations of calls can be simultaneously accepted so as to ensure satisfactory performance. The approach adopted is that key network performance parameters are observed while carrying various combinations of calls, and their relationship is learned by a neural network structure. The network model chosen has the ability to interpolate or extrapolate from the past results and the ability to adapt to new and changing conditions. The switch control problem is the service policy used by a switch controller in transmitting packets. In a crossbar switch with input queueing, significant loss of throughput can occur when head-of-line service order is employed. A solution can be based on an algorithm which maximizes throughput. However since this solution is typically required in less than one microsecond, software implementation policy is infeasible. We will carry out an analysis of the benefits of such a policy, describe some existing proposed schemes for its implementation, and propose a further scheme that provides this submicrosecond optimization.