論文

Summary form only given, as follows. A new parallel distributed processing architecture called an entropy machine (EM) is proposed. This machine, which is based on an artificial neural network composed of massive neurons and interconnections, is used for solving a variety of NP-complete optimization problems. The EM performs either the parallel distributed gradient descent method or gradient ascent method to search for minima or maxima.

A near-optimum parallel planarization algorithm is presented. The planarization algorithm, which is designed to embed a graph on a plane, uses a large number of simple processing elements called neurons. The proposed system, composed of an N×N neural network array (where N is the number of vertices), not only generates a near-maximal planar subgraph from a nonplanar graph or a planar graph but also embeds the subgraph on a single plane within 0(1) time. The algorithm can be used in multiple-layer problems such as designing printed circuit boards and routing very-large-scale integration circuits.

In its first 40 years the neural network learning (NNL) movement has produced an impressive array of learning models. We introduce a general family of fast and efficient NNL learning modules for binary events called 'conjunctoids', which employ an appropriate framework from probability theory; adapt a class of recently developed conjunctive models from psychometric theory; tailor sound statistical estimation and evaluation schemes to fit NNL learning needs; and allow VLSI implementations.

A general family of fast and efficient neural network learning modules for binary events is introduced. The family subsumes probabilistic as well as functional event associations; subsumes all levels of input/output association; yields truly parallel learning processes; provides for optimal parameter estimation; points toward a workable description of optimal model performance; and yields procedures that are simple and fast enough to be serious candidates for reflecting both neural functioning and real time machine learning. Examples as well as operational details are provided.

This paper describes analog and digital multinomial conjunctoid modules that are currently under silicon fabrication using a MOSIS program based on CMOS technology. The digital multinomial conjunctoid module is featured, but digital and analog modules are compared as well. The feasibility of large scale multinomial machines are discussed. Designs for parameter estimation modules and indispensable digital components are also given.

In this paper a rule-based Lisp dialect translator using paramodulation is presented as an example of a general purpose program translator application where the knowledge about the translation is embedded in rules. The advantage of using a rule-based system is to allow the user to supply his own rules for translation, thus the translator can be considered as a general purpose converter. Also, the rule-based LDT has the ability to test individual rules for correctness to aid in rule development. The translation being used for development is Franz to Common Lisp.

We explore the applications of binary neurons with analog conductance or communication links in solving large-scale NP-complete optimization problems such as the classical traveling salesperson problems (TSP) and job-shop scheduling. In particular, the energy function of J.J. Hopfield and D.W. Tank neural network model is reformulated so that the network is likely to converge to a proportional number of valid solutions as the size of problem scales up. G.V. Wilson and G.S. Pawley identified the reasons for failure on the Hopfield and Tank computation algorithm in their attempts to solve a 10-city TSP. K. Sheff and H. Szu proposed a necessary and sufficient condition based on binary neurons and traceless energy for a Hopfield and Tank network to converge to stable states. In this paper, we study the effectiveness of this fast neural network convergent scheme through two case studies: an n-job m-machine job-shop problem and an N-city TSP.

An application of neural networks is presented for solving job-shop scheduling, an NP-complete optimization problem with constaint satisfaction. In particular, the authors introduce a neural computation architecture based on a stochastic Hopfield neural-network model. First, the job-shop problem is mapped into a two-dimensional matrix representation of neurons similar to those for solving the traveling salesman problem (TSP). Constant positive and negative current biases are applied to specific neurons as excitations and inhibitions, respectively, to enforce the operation precedence relationships. At the convergence of neural network, the solution to the job-shop problem is represented by a set of cost function trees encoded in the matrix of stable states. Each node in the set of trees represents a job, and each link represents the interdependency between jobs. A computation circuit computes the total completion times (costs) of all jobs, and the cost difference is added to the energy function of the stochastic neural network. Using a simulated annealing algorithm, the temperature of the system is slowly decreased according to an annealing schedule until the energy of the system is at a local or global minimum. By choosing an appropriate annealing schedule, near-optimal and optimal solutions to job-shop problems can be found.

Neural networks have been studied for many years with the hope of achieving human-like performance in such fields as speech and image recognition. A recent resurgence has resulted from VLSI advances, neural network models, and learning algorithms. Neural networks are also very suitable in certain areas such as NP-complete constraint and satisfaction problems, due to the nature of parallel and distributed processing. Neural network models are composed of a mass of fairly simple computational elements and rich interconnections between the elements. Neural networks operate in a parallel and distributed fashion which may resemble biological neural networks. Behaviors of neurons and the strengths of synaptic interconnections are simulated by operational amplifiers and resistors respectively. Several examples are presented, including how to build neural network components based on analog circuits for simulating neural networks and conventional logic circuits.

The authors introduce a neural computation architecture based on a stochastic Hopfield neural network model for solving job-shop scheduling. A computation circuit computes the total completion times (costs) of all jobs, and the cost difference is added to the energy function of the stochastic neural network. Using a simulated annealing algorithm, the temperature of the system is slowly decreased according to an annealing schedule until the energy of the system is at a local or global minimum. By choosing an appropriate annealing schedule, near-optimal and optimal solutions to job-shop problems can be found. The architecture of the system is diagrammed at both the functional and circuit levels. Simulation results are presented.

A statistical learning model called the multinomial conjunctoid is reviewed. Multinomial conjunctoids are based on a well-developed, statistical-decision-theory framework, which guarantees that conjunctoid learning will converge to optimal states over learning trials and the learning will be fast during these trials. In addition, a prototype multinomial conjunctoid module based on CMOS VLSI technology is introduced.

An error-correcting system based on neural circuit techniques is presented. This system is expected to perform significantly faster than conventional error-correcting systems based on logic gate designs. Two example circuits demonstrate how the neural error-correcting system works.

A simple example of (7,4) codes for one-bit error correction is shown. However the proposed neural model can be expanded to multiple-bit error correction. Generally an (N,K) neural decoder of this type will require 2**k op amps, an N multiplied by 2**k resistor network, 2**k comparators, and an N multiplied by 2**k diode network. This error-correction model is effective in a severe environment such as control or military equipment's.

A neural-based scheme for pattern recognition and construction of three-dimensional images from partial cues is presented. Clusters of neural nets operating concurrently are used to learn and recall patterns at X, Y, Z planes. Simulations are performed based on a Hopfield-like network to investigate the effect of learning trials and firing percentage of nodes per cycle. A method for computing the common features of input patterns is given. Results showed that maximum parallel processing can be achieved.

A general-purpose cross assembler named gpca using Franz Lisp on a VAX11/750 with Berkeley Unix BSD4. 2 was developed. All the user has to do is to provide rule lists to a rule-database for code generation. The rule-based technique used in the gpca can enhance the productivity for developing cross assemblers for 4-, 8-, 16-, and 32-bit microprocessors in a short period of time through the rule independency. The implemented cross-assembler is composed of database management routines, lexical pattern matching routines, and a few other routines. The cross assembler, which is small enough to be understood completely by the user, has a flexibility and an expandability in terms of user extensible pseudo-operations and macro functions.

Authors propose parallel/pipelined and parallel/iterative spanning tree generators for directed and undirected graphs based on graph theory algorithms using adjacency matrices. A generator employing iterative logic circuits with high regularity suitable for VLSI implementation can be realized with O(n**2) gates where n is the number of nodes in a given graph. This generator can compute a spanning tree of an nXn adjacency matrix within O(n**2) gate delays. The organizations of spanning tree generators are discussed.

The yield of chips tends to decrease with the degree of integration of memory chips, which is presently a serious problem. A method is proposed to utilize the fault chips being discarded to produce a normal chip, increasing the apparent yield. The relation between the yield and the reliability of the fault memory chip system is discussed. Using the proposed method, the yield of 10% can be improved up to 40% without substantially decreasing the reliability of the fault chip memory system from that of a normal memory chip. The method was implemented using fault 16 K RAM, and the effectiveness of the method was verified.