Goto

Collaborating Authors

 Genre



Hard and Easy SAT Problems

Classics

"We report results from large-scale experiments in satisfiability testing. As has been observed by others, testing the satisfiability of random formulas often appears surprisingly easy. Here we show that by using the right distribution of instances, and appropriate parameter values, it is possible to generate random formulas that are hard, that is, for which satisfiability testing is quite difficult. Our results provide a benchmark for the evaluation of satisfiability-testing procedures." Proc. AAAI-92.


A New Method for Solving Hard Satisfiability Problems

Classics

"We introduce a greedy local search procedure called GSAT for solving propositional satisfiability problems. Our experiments show that this procedure can be used to solve hard, randomly generated problems that are an order of magnitude larger than those that can be handled by more traditional approaches such as the Davis-Putnam procedure or resolution. We also show that GSAT can solve structured satisfiability problems quickly. In particular, we solve encodings of graph coloring problems, N-queens, and Boolean induction. General application strategies and limitations of the approach are also discussed. GSAT is best viewed as a model-finding procedure. Its good performance suggests that it may be advantageous to reformulate reasoning tasks that have traditionally been viewed as theorem-proving problems as model-finding tasks." Proc. AAAI-92.



Speech Recognition Using Demi-Syllable Neural Prediction Model

Neural Information Processing Systems

The Neural Prediction Model is the speech recognition model based on pattern prediction by multilayer perceptrons. Its effectiveness was confirmed by the speaker-independent digit recognition experiments. This paper presents an improvement in the model and its application to large vocabulary speech recognition, based on subword units. The improvement involves an introduction of "backward prediction," which further improves the prediction accuracy of the original model with only "forward prediction". In application of the model to speaker-dependent large vocabulary speech recognition, the demi-syllable unit is used as a subword recognition unit.


Lg Depth Estimation and Ripple Fire Characterization Using Artificial Neural Networks

Neural Information Processing Systems

This srudy has demonstrated how artificial neural networks (ANNs) can be used to characterize seismic sources using high-frequency regional seismic data. We have taken the novel approach of using ANNs as a research tool for obtaining seismic source information, specifically depth of focus for earthquakes and ripple-fire characteristics for economic blasts, rather than as just a feature classifier between earthquake and explosion populations. Overall, we have found that ANNs have potential applications to seismic event characterization and identification, beyond just as a feature classifier. In future studies, these techniques should be applied to actual data of regional seismic events recorded at the new regional seismic arrays. The results of this study indicates that an ANN should be evaluated as part of an operational seismic event identification system. 1 INTRODUCTION ANNs have usually been used as pattern matching algorithms, and recent studies have applied ANNs to standard classification between classes of earthquakes and explosions using wavefonn features (Dowla, et al, 1989), (Dysart and Pulli, 1990).


ART2/BP architecture for adaptive estimation of dynamic processes

Neural Information Processing Systems

The goal has been to construct a supervised artificial neural network that learns incrementally an unknown mapping. As a result a network consisting of a combination of ART2 and backpropagation is proposed and is called an "ART2/BP" network. The ART2 network is used to build and focus a supervised backpropagation network. The ART2/BP network has the advantage of being able to dynamically expand itself in response to input patterns containing new information. Simulation results show that the ART2/BP network outperforms a classical maximum likelihood method for the estimation of a discrete dynamic and nonlinear transfer function.


On the Circuit Complexity of Neural Networks

Neural Information Processing Systems

Viewing n-variable boolean functions as vectors in'R'2", we invoke tools from linear algebra and linear programming to derive new results on the realizability of boolean functions using threshold gat.es. Using this approach, one can obtain: (1) upper-bounds on the number of spurious memories in HopfielJ networks, and on the number of functions implementable by a depth-d threshold circuit; (2) a lower bound on the number of ort.hogonal input.


The Tempo 2 Algorithm: Adjusting Time-Delays By Supervised Learning

Neural Information Processing Systems

In this work we describe a new method that adjusts time-delays and the widths of time-windows in artificial neural networks automatically. The input of the units are weighted by a gaussian input-window over time which allows the learning rules for the delays and widths to be derived in the same way as it is used for the weights. Our results on a phoneme classification task compare well with results obtained with the TDNN by Waibel et al., which was manually optimized for the same task.


Further Studies of a Model for the Development and Regeneration of Eye-Brain Maps

Neural Information Processing Systems

We describe a computational model of the development and regeneration of specific eye-brain circuits. The model comprises a self-organizing map-forming network which uses local Hebb rules, constrained by (genetically determined) molecular markers. Various simulations of the development and regeneration of eye-brain maps in fish and frogs are described, in particular successful simulations of experiments by Schmidt-Cicerone-Easter; Meyer; and Y oon. 1 INTRODUCTION In a previous paper published in last years proceedings (Cowan & Friedman 1990) we outlined a new computational model for the development and regeneration of eye-brain maps. We indicated that such a model can simulate the results of a number of the more complicated surgical manipulations carried out on the visual pathways of goldfish and frogs. In this paper we describe in more detail some of these experiments, and our simulations of them.