論文 - 武藤　佳恭

A super-parallel sorting algorithm based on neural networks

Takefuji Yoshiyasu, Lee Kuo Chun

IEEE Transactions on Circuits and Systems 37 （ 11 ） 1425 - 1429 1990年11月

ISSN  0098-4094

　概要を見る

<p>A novel neural network parallel algorithm for sorting problems is presented. The proposed algorithm using O(n²) processors requires only two steps, and does not depend on the size of the problem, while the conventional parallel sorting algorithm using O(n) processors by F. T. Leighton (1984) needs the computation time O(log n²). A set of simulation results substantiates the proposed algorithm. The hardware system based on the proposed parallel algorithm is also presented.</p>

• Access to Document (DOI)

A parallel algorithm for estimating the secondary structure in ribonucleic acids

Takefuji Y., Lin C. W., Lee K. C.

Biological Cybernetics 63 （ 5 ） 337 - 340 1990年09月

ISSN  0340-1200

　概要を見る

<p>A parallel algorithm for estimating the secondary structure of an RNA molecule is presented in this paper. The mathematical problem to compute an optimal folding based on free-energy minimization is mapped onto a graph planarization problem. In the planarization problem we want to maximize the number of edges in a plane with no two edges crossing each other. To solve a sequence of n bases, n(n - 1)/2 processing elements are used in our algorithm.</p>

• Access to Document (DOI)

Parallel algorithms for finding a near-maximum independent set of a circle graph

Takefuji Yoshiyasu, Chen Li Lin, Lee Kuo Chun, Huffman John

IEEE Transactions on Neural Networks 1 （ 3 ） 263 - 267 1990年09月

ISSN  1045-9227

　概要を見る

<p>A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph of the number of possible base pairs), not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. The simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid, than previously proposed structures.</p>

• Access to Document (DOI)

Analog components for the VLSI of neural networks

Foo Simon Y., Anderson Lisa R., Takefuji Yoshiyasu

IEEE Circuits and Devices Magazine 6 （ 4 ） 18 - 26 1990年07月

ISSN  8755-3996

　概要を見る

<p>Principles of operation and basic building blocks of artificial neural networks are described. Deterministic components, comprising variable linear conductance devices and components used for processing elements, are discussed. These devices are analyzed using SPICE. The reasons for using simple analog circuits rather than digital circuits are examined.</p>

• Access to Document (DOI)

Parallel algorithm for tiling problems

Takefuji Yoshiyasu, Lee Kuo Chun

IEEE Transactions on Neural Networks 1 （ 1 ） 143 - 145 1990年03月

ISSN  1045-9227

　概要を見る

<p>A parallel algorithm for tiling with polyominoes is presented. The tiling problem is to pack polyominoes in a finite checkerboard. The algorithm using l × m × n processing elements requires O(1) time, where l is the number of different kinds of polyominoes on an m × n checkerboard. The algorithm can be used for placement of components or cells in a very large-scale integrated circuit (VLSI) chip, designing and compacting printed circuit boards, and solving a variety of two- or three-dimensional packing problems.</p>

• Access to Document (DOI)

Databases and cell-selection algorithms for VLSI cell libraries

Foo Simon Y., Takefuji Yoshiyasu

Computer 23 （ 2 ） 18 - 30 1990年02月

ISSN  0018-9162

　概要を見る

<p>The issues that must be addressed before commercial database management systems can be used to manage VLSI CAD data are defined. A survey is presented of approaches addressing four of the defined issues: design hierarchies and multilevel representations, design alternatives and version control, common interface between cell libraries, and efficient cell selection based on given design constraints. A frame-based model is considered as a case study of the special-purpose design database management system approach. This framework for capturing design data is based on semantic networks. It is well suited for application-specific ICs, yet general enough for other CAD/CAM environments. Benchmark results for the selection algorithms that run on top of the frame-based database system are presented.</p>

• Access to Document (DOI)

Implementing fuzzy rule-based systems on silicon chips

Lim Meng Hiot, Takefuji Yoshiyasu

IEEE Expert 5 （ 1 ） 31 - 45 1990年02月

ISSN  0885-9000

　概要を見る

<p>The authors address the implementation of a fuzzy simulator (FSIM) and discuss architectures for a general-purpose VLSI fuzzy-inference processor. The FSIM tool aids in the rapid prototyping of fuzzy production system (FPS), and represents a convenient transitional step in the implementation of an FPS on silicon. They present a brief theoretical review of fuzzy reasoning, introduce the FSIM, and discuss FPS development using the FSIM. An overall picture of the various stages involved in developing a fuzzy-inference processor is provided. The authors then outline the general architecture of a VLSI inference processor for FPSs. To further illustrate the development of a fuzzy inference processor, they describe an FPS example from conceptualization to implementation on silicon chips.</p>

• Access to Document (DOI)

A two step sorting algorithm

Takefuji Yoshiyasu, Lee Kuo Chun, Tanaka Toshimitsu

  793 - 798 1990年

　概要を見る

<p>A parallel algorithm based on neural networks for solving sorting problems is presented. The proposed algorithm uses O(n²) processing elements called binary neurons, where n is the number of unsorted elements. It requires two and only two iteration steps, while the conventional parallel sorting algorithm using (On) processors proposed by F. T. Leighton (1984) requires the computation time O(log n). A set of simulation results substantiates the proposed algorithm. The hardware system based on the proposed parallel algorithm is also presented.</p>

Computation scheme for the general purpose VLSI fuzzy inference engine as expert system

Takefuji Yoshiyasu, Lim Meng Hiot

Knowledge-Based Systems 2 （ 2 ） 109 - 116 1989年

ISSN  0950-7051

　概要を見る

<p>Fuzzy inference engines based on the existing fuzzy theory are inadequate to perform reliable decision making. Besides requiring the fuzzy sets and data to be normalized, the inference engine is also sensitive to noise in observational data. Inaccurate conclusions are produced if noise is present and also when the fuzzy sets are not normalized. In this paper, a new term 'similarity' (σ) and the method to compute σ to enhance the capability of fuzzy set theory for application in expert systems is introduced. Even though the complexity of the hardware engine is slightly increased, it actually reduces the overhead of computation by eliminating the need for normalization of fuzzy data. With reliable fuzzy data manipulation, it is easy to extend to a multi-dimensional membership function which has a wider scope of applications. To To implement the Very Large Scale Integration fuzzy inference engine, two general schemes of the hardware architecture that van be easily reconfigured to satisfy given performance requirements are discussed.</p>

• Access to Document (DOI)

A near-optimum parallel planarization algorithm

Takefuji Yoshiyasu, Lee Kuo Chun

Science 245 （ 4923 ） 1221 - 1223 1989年

ISSN  0036-8075

　概要を見る

<p>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.</p>

Parallel distributed gradient descent and ascent methods

Takefuji Yoshiyasu

  584 1989年

　概要を見る

<p>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.</p>

Design of parallel distributed Cauchy machines

Takefuji Yoshiyasu, Szu Harold

  529 - 532 1989年

　概要を見る

<p>A parallel and stochastic version of Hopfield-like neural networks is presented. Cauchy color noise is assumed. The specific noise is desirable for fast convergence to a fixed point representing a neighborhood minimum. It can be quickly quenched at each iteration according to a proven cooling schedule in generating random states on the energy landscape. An exact Cauchy acceptance criterion is analytically derived for hill-climbing capability. The improvement is twofold: a faster cooling schedule (the inversely linear cooling schedule characterized by the Cauchy simulated annealing) and parallel executions of all neurons. Such a Cauchy machine can be electronically implemented, and the design is given.</p>

Conjunctoid learning and performance algorithms

Jannarone R. J., Yu K. F., Takefuji Y.

Neural Networks 1 （ 1 SUPPL ） 186 1988年

ISSN  0893-6080

　概要を見る

<p>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.</p>

• Access to Document (DOI)

MULTINOMIAL CONJUNCTOID STATISTICAL LEARNING MACHINES.

Takefuji Yoshiyasu, Jannarone Robert, Cho Yong B., Chen Tatung

  12 - 17 1988年

　概要を見る

<p>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.</p>

Stochastic neural networks for solving job-shop scheduling. II - Architecture and simulations

Foo Yoon Pin Simon, Takefuji Yoshiyasu

  283 - 290 1988年

　概要を見る

<p>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.</p>

ANALOG CIRCUIT DESIGN BASED ON NEURAL NETWORKS.

Cho Yong B., Takefuji Yoshiyasu

  100 - 105 1988年

　概要を見る

<p>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.</p>

Stochastic neural networks for solving job-shop scheduling. I - Problem representation

Foo Yoon Pin Simon, Takefuji Yoshiyasu

  275 - 282 1988年

　概要を見る

<p>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.</p>

Binary neurons with analog communication links for solving large-scale optimization problems

Foo Yoon Pin Simon, Takefuji Yoshiyasu, Szu Harold

Neural Networks 1 （ 1 SUPPL ） 437 1988年

ISSN  0893-6080

　概要を見る

<p>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.</p>

• Access to Document (DOI)

Novel approach to a rule-based general purpose program translator using paramodulation

Takefuji Yoshiyasu, Dowell Michael

Knowledge-Based Systems 1 （ 2 ） 90 - 93 1988年

ISSN  0950-7051

　概要を見る

<p>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.</p>

• Access to Document (DOI)

Silicon multinomial conjunctoid statistical learning modules

Takefuji Yoshiyasu, Jannarone Robert J., Chen Tatung, Cho Yong B.

Neural Networks 1 （ 1 SUPPL ） 413 1988年

ISSN  0893-6080

　概要を見る

<p>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.</p>

• Access to Document (DOI)