We present a neural virtual machine that can be trained to perform algorithmic tasks. Rather than combining a neural controller with non-neural memory storage as has been done in the past, this architecture is purely neural and emulates tape-based memory via fast associative weights (one-step learning). Here we formally define the architecture, and then extend the system to learn programs using recurrent policy gradient reinforcement learning based on examples of program inputs labeled with corresponding output targets, which are compared against actual output to generate a sparse reward signal. We describe the policy gradient training procedure used, and report its empirical performance on a number of small-scale list processing tasks, such as finding the maximum list element, filtering out certain elements, and reversing the order of the elements. These results show that program induction via reinforcement learning is possible using sparse rewards and solely neural computations.

In this work, we study the dynamical properties of a machine learning technique called reservoir computing in order to gain insight into how representations of chaotic signals are encoded through learning. We train the reservoir on individual chaotic Lorenz signals. The Lorenz system is characterized by a set of equations and known to have three fixed points, all of which are unstable in the chaotic regime of the strange attractor. Exploration of the fixed points of the reservoir whose outputs are trained allows us to understand whether inherent Lorenz dynamics are transposed onto reservoir dynamics during learning. We do so by using a novel fixed point finding technique called directional fibers. Directional fibers are mathematical objects that systematically locate fixed points in a high dimensional space, and are found to be competitive and complementary with other traditional approaches. We find that the reservoir, after training of output weights, contains a higher dimensional projection of the Lorenz fixed points with matching stability, even though the training data did not include the fixed points. This tells us that the reservoir does indeed learn dynamical properties of the Lorenz attractor. We also find that the directional fiber also identifies additional fixed points in the reservoir space outside the projected Lorenz attractor region; these amplify perturbations during prediction and play a role in failure of long-term time series prediction.

Learning a set of patterns in a content-addressable memory is an important aspect of many neurocomputational systems. Historically, this has often been done using Hebbian learning with attractor neural networks such as the standard discrete-valued Hopfield model. However, such systems are currently severely limited in terms of their memory capacity: as an increasing number of patterns are stored as fixed points, spurious attractors ("false memories") are increasingly created and compromise the network's functionality. Here we adopt a new method for identifying the fixed points (both stored and false memory patterns) learned by attractor networks in general, applying it to the special case of a continuous-valued analogue of the standard Hopfield model. We use computational experiments to show that this continuous-valued model functions as a content-addressable memory, characterizing its ability to learn training examples effectively and to store them at energy minima having substantial basins of attraction. We find that the new fixed point locator method not only identifies learned memories, but also many of the spurious attractors that occur. These results are a step towards systematically characterizing what is learned by attractor networks and may lead to more effective learning by allowing the use of techniques such as selective application of anti-Hebbian unlearning of spurious memories.

We introduce mathematical objects that we call "directional fibers," and show how they enable a new strategy for systematically locating fixed points in recurrent neural networks. We analyze this approach mathematically and use computer experiments to show that it consistently locates many fixed points in many networks with arbitrary sizes and unconstrained connection weights. Comparison with a traditional method shows that our strategy is competitive and complementary, often finding larger and distinct sets of fixed points. We provide theoretical groundwork for further analysis and suggest next steps for developing the method into a more powerful solver.

The idea that there is an edge of chaos, a region in the space of dynamical systems having special meaning for complex living entities, has a long history in artificial life. The significance of this region was first emphasized in cellular automata models when a single simple measure, λCA, identified it as a transitional region between order and chaos. Here we introduce a parameter λNN that is inspired by λCA but is defined for recurrent neural networks. We show through a series of systematic computational experiments that λNN generally orders the dynamical behaviors of randomly connected/weighted recurrent neural networks in the same way that λCA does for cellular automata. By extending this ordering to larger values of λNN than has typically been done with λCA and cellular automata, we find that a second edge-of-chaos region exists on the opposite side of the chaotic region. These basic results are found to hold under different assumptions about network connectivity, but vary substantially in their details. The results show that the basic concept underlying the lambda parameter can usefully be extended to other types of complex dynamical systems than just cellular automata.

Using only simple rules for local interactions, groups of agents can form self-organizing super-organisms or flocks that show global emergent behavior. When agents are also extended with memory and goals the resulting flock not only demonstrates emergent behavior, but also collective intelligence: the ability for the group to solve problems that might be beyond the ability of the individual alone. Until now, research has focused on the improvement of particle design for global behavior; however, techniques for human-designed particles are task-specific. In this paper we will demonstrate that evolutionary computing techniques can be applied to design particles, not only to optimize the parameters for movement but also the structure of controlling finite state machines that enable collective intelligence. The evolved design not only exhibits emergent, self-organizing behavior but also significantly outperforms a human design in a specific problem domain. The strategy of the evolved design may be very different from what is intuitive to humans and perhaps reflects more accurately how nature designs systems for problem solving. Furthermore, evolutionary design of particles for collective intelligence is more flexible and able to target a wider array of problems either individually or as a whole.

While the concept of gating has been explored in past studies of neural networks, and neural network controllers have been successfully designed through evolutionary computation methods, very little past work has focused on empirically determining the value of adding gating to evolved neural network architectures. In this study, we do precisely that, by examining a neural architecture and genetic representation that explicitly permits the use of gating connections in a neurocontroller, and comparing the evolved controller performance to similar evolved controllers where gating connections are not explicitly included. The performance of these different approaches is evaluated in evolving a neurocontroller for an autonomous agent navigating through a simulated predator-prey environment. We find that the neural architecture that explicitly allows gating clearly outperforms three other architectures without gating, suggesting that there is a clear benefit to having gating connections directed by a command module. Further analysis of the best evolved agent reveals that its controller executes by producing command signals that encode high-level goals, which then modify low-level behaviors to achieve those goals, supporting the hypothesis that allowing gated connections in neural networks substantially improves the neurocontrollers that can be evolved.

The long short-term memory (LSTM) neural network utilizes specialized modulation mechanisms to store information for extended periods of time. It is thus potentially well-suited for complex visual processing, where the current video frame must be considered in the context of past frames. Recent studies have indeed shown that LSTM can effectively recognize and classify human actions (e.g., running, hand waving) in video data; however, these results were achieved under somewhat restricted settings. In this effort, we seek to demonstrate that LSTM's performance remains robust even as experimental conditions deteriorate. Specifically, we show that classification accuracy exhibits graceful degradation when the LSTM network is faced with (a) lower quantities of available training data, (b) tighter deadlines for decision making (i.e., shorter available input data sequences) and (c) poorer video quality (resulting from noise, dropped frames or reduced resolution). We also clearly demonstrate the benefits of memory for video processing, particularly, under high noise or frame drop rates. Our study is thus an initial step towards demonstrating LSTM's potential for robust action recognition in real-world scenarios.

With the recent surge in availability of data sets containing not only individual attributes but also relationships, classification techniques that take advantage of predictive relationship information have gained in popularity. The most popular existing collective classification techniques have a number of limitations-some of them generate arbitrary and potentially lossy summaries of the relationship data, whereas others ignore directionality and strength of relationships. Popular existing techniques make use of only direct neighbor relationships when classifying a given entity, ignoring potentially useful information contained in expanded neighborhoods of radius greater than one. We present a new technique that we call recurrent neural collective classification (RNCC), which avoids arbitrary summarization, uses information about relationship directionality and strength, and through recursive encoding, learns to leverage larger relational neighborhoods around each entity. Experiments with synthetic data sets show that RNCC can make effective use of relationship data for both direct and expanded neighborhoods. Further experiments demonstrate that our technique outperforms previously published results of several collective classification methods on a number of real-world data sets.

Most self-organizing models of moving agent collectives (simulated herds, bird flocks, etc.) employ reflexive agents that lack significant memory of past movements and previously encountered environmental features. Further, these agent collectives often act in fairly open environments where obstacles to movement are relatively sparse. In this work, we explore the hypothesis that a limited working memory of recently encountered environmental features, distributed throughout the collective, can improve task performance for a team of interacting agents that are operating in a highly occluded environment. Investigating a team of agents pursuing a mobile target in an “urban environment”, we found that the team benefited from 1) communication that coordinated team movements, and 2) from a working memory of the environment that was distributed among the agents, despite individual agents knowing only a small part of the relevant information. These results further our understanding of methodologies that can be applied to control robotic teams and swarm optimization, and may also provide insight into herd behavior of biological populations in some densely occluded environments.

Fodor and Pylyshyn [(1988). Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1–2), 3–71] famously argued that neural networks cannot behave systematically short of implementing a combinatorial symbol system. A recent response from Frank et al. [(2009). Connectionist semantic systematicity. Cognition, 110(3), 358–379] claimed to have trained a neural network to behave systematically without implementing a symbol system and without any in-built predisposition towards combinatorial representations. We believe systems like theirs may in fact implement a symbol system on a deeper and more interesting level: one where the symbols are latent – not visible at the level of network structure. In order to illustrate this possibility, we demonstrate our own recurrent neural network that learns to understand sentence-level language in terms of a scene. We demonstrate our model's learned understanding by testing it on novel sentences and scenes. By paring down our model into an architecturally minimal version, we demonstrate how it supports combinatorial computation over distributed representations by using the associative memory operations of Vector Symbolic Architectures. Knowledge of the model's memory scheme gives us tools to explain its errors and construct superior future models. We show how the model designs and manipulates a latent symbol system in which the combinatorial symbols are patterns of activation distributed across the layers of a neural network, instantiating a hybrid of classical symbolic and connectionist representations that combines advantages of both.

Simple recurrent error backpropagation networks have been widely used to learn temporal sequence data, including regular and context-free languages. However, the production of relatively large and opaque weight matrices during learning has inspired substantial research on how to extract symbolic human-readable interpretations from trained networks. Unlike feedforward networks, where research has focused mainly on rule extraction, most past work with recurrent networks has viewed them as dynamical systems that can be approximated symbolically by finite-state machine (FSMs). With this approach, the network's hidden layer activation space is typically divided into a finite number of regions. Past research has mainly focused on better techniques for dividing up this activation space. In contrast, very little work has tried to influence the network training process to produce a better representation in hidden layer activation space, and that which has been done has had only limited success. Here we propose a powerful general technique to bias the error backpropagation training process so that it learns an activation space representation from which it is easier to extract FSMs. Using four publicly available data sets that are based on regular and context-free languages, we show via computational experiments that the modified learning method helps to extract FSMs with substantially fewer states and less variance than unmodified backpropagation learning, without decreasing the neural networks' accuracy. We conclude that modifying error backpropagation so that it more effectively separates learned pattern encodings in the hidden layer is an effective way to improve contemporary FSM extraction methods.

The production of relatively large and opaque weight matrices by error backpropagation learning has inspired substantial research on how to extract symbolic human-readable rules from trained networks. While considerable progress has been made, the results at present are still relatively limited, in part due to the large numbers of symbolic rules that can be generated. Most past work to address this issue has focused on progressively more powerful methods for rule extraction (RE) that try to minimize the number of weights and/or improve rule expressiveness. In contrast, here we take a different approach in which we modify the error backpropagation training process so that it learns a different hidden layer representation of input patterns than would normally occur. Using five publicly available datasets, we show via computational experiments that the modified learning method helps to extract fewer rules without increasing individual rule complexity and without decreasing classification accuracy. We conclude that modifying error backpropagation so that it more effectively separates learned pattern encodings in the hidden layer is an effective way to improve contemporary RE methods.

Particle Swarm Optimization (PSO) is a well-known technique for numerical optimization with real-parameter representation. Like other meta-heuristics, PSO is usually designed for the goal of finding a single optimal solution for a given problem. However, many scientific and engineering optimization problems have convoluted search spaces with a large number of optima. This paper explores the ability of a cooperative combinatorial PSO (CCPSO) used in tandem with explicit diversity strategies to discover sets of high-quality and diverse solutions. This idea has been pursued in numerical optimization in several PSO variants, but no explicit PSO has been developed to handle multimodal combinatorial problems. A protein sequence redesign problem is selected to assess the exploratory ability of multimodal CCPSO by evaluating both the quality and diversity of the solutions obtained.

Cellular automata models have historically been a major approach to studying the information-processing properties of self-replication. Here we explore the feasibility of adopting genetic programming so that, when it is given a fairly arbitrary initial cellular automata configuration, it will automatically generate a set of rules that make the given configuration replicate. We found that this approach works surprisingly effectively for structures as large as 50 components or more. The replication mechanisms discovered by genetic programming work quite differently than those of many past manually designed replicators: There is no identifiable instruction sequence or construction arm, the replicating structures generally translate and rotate as they reproduce, and they divide via a fissionlike process that involves highly parallel operations. This makes replication very fast, and one cannot identify which descendant is the parent and which is the child. The ability to automatically generate self-replicating structures in this fashion allowed us to examine the resulting replicators as their properties were systematically varied. Further, it proved possible to produce replicators that simultaneously deposited secondary structures while replicating, as in some past manually designed models. We conclude that genetic programming is a powerful tool for studying self-replication that might also be profitably used in contexts other than cellular spaces.

Most construction of artificial, multicomponent structures is based upon an external entity that directs the assembly process, usually following a script/blueprint under centralized control. In contrast, recent research has focused increasingly on an alternative paradigm, inspired largely by the nest building behavior of social insects, in which components “self-assemble” into a given target structure. Adapting such a nature-inspired approach to precisely self-assemble artificial structures (bridge, building, etc.) presents a formidable challenge: one must create a set of local control rules to direct the behavior of the individual components/agents during the self-assembly process. In recent work, we developed a fully automated procedure that generates such rules, allowing a given structure to successfully self-assemble in a simulated environment having constrained, continuous motion; however, the resulting rule sets were typically quite large. In this article, we present a more effective methodology for automatic rule generation, which makes an attempt to parsimoniously capture both the repeating patterns that exist within a structure, and the behaviors necessary for appropriate coordination. We then empirically show that the procedure developed here generates sets of rules that are not only correct, but significantly reduced in size, relative to our earlier approach. Such rule sets allow for simpler agents that are nonetheless still capable of performing complex tasks, and therefore demonstrate the problem-solving potential of self-organized systems.

In this paper, we investigate the use of nested evolution in which each step of one evolutionary process involves running a second evolutionary process. We apply this approach to build an evolutionary system for reinforcement learning (RL) problems. Genetic programming based on a descriptive encoding is used to evolve the neural architecture, while an evolution strategy is used to evolve the connection weights. We test this method on a non-Markovian RL problem involving an autonomous foraging agent, finding that the evolved networks significantly outperform a rule-based agent serving as a control. We also demonstrate that nested evolution, partitioning into subpopulations, and crossover operations all act synergistically in improving performance in this context.

This paper describes a new method for extracting symbolic rules from multilayer feedforward neural networks. Our approach is to encourage backpropagation to learn a sparser representation at the hidden layer and to use the improved representation to extract fewer, easier to understand rules. A new error term defined over the hidden layer is added to the standard sum of squared error so that the total squared distance between hidden activation vectors is increased. We show that this method helps extract fewer rules without decreasing classification accuracy in four publicly available data sets.

A recent neurocomputational study showed that it is possible for a model of the language areas of the brain (Wernicke's area, Broca's area, etc.) to learn to process words correctly. This model is unique in that it is a neuroanatomically based model of word learning derived from the Wernicke-Lichtheim-Geschwind theory of language processing. For example, when subjected to simulated focal damage, the model breaks down in ways reminiscent of the classic aphasias. While such results are intriguing, this previous work was limited to processing only single words: nouns corresponding to concrete objects. Here we take the first steps towards generalizing the methods used in this earlier model to work with full sentences instead of isolated words. We gauge the richness of the neural representations that emerge during purely unsupervised learning in several ways. For example, using a separate ldquorecognition networkrdquo, we demonstrate that the model's encoding of sentences is adequate to permit subsequent extraction of a symbolic, hierarchical representation of sentence meaning. Although our results are encouraging, substantial further work will be needed to create a large-scale model of the human cortical network for language.

Particle Swarm Optimization (PSO) is a well-known, competitive technique for numerical optimization with real-parameter representation. This paper introduces CCPSO, a new Cooperative Particle Swarm Optimization algorithm for combinatorial problems. The cooperative strategy is achieved by splitting the candidate solution vector into components, where each component is optimized by a particle. Particles move throughout a continuous space, their movements based on the influences exerted by static particles that then get feedback based on the fitness of the candidate solution. Here, the application of this technique to side-chain packing (a proteomics optimization problem) is investigated. To verify the efficiency of the proposed CCPSO algorithm, we test our algorithm on three side-chain packing problems and compare our results with the provably optimal result. Computational results show that the proposed algorithm is very competitive, obtaining a conformation with an energy value within 1% of the provably optimal solution in many proteins.

In many species, adjacent topographic maps in sensory neocortex are found to be oriented as roughly mirror-image copies of one another. Here we use a computational model to show for the first time that, in principle, adjacent cortical topographic maps that are mirror-image symmetric along two dimensions can arise from activity-dependent changes if the distribution radius of afferents sufficiently exceeds that of horizontal intracortical interactions. We also find that infrequently, other types of intermap symmetry and previously unexpected map relationships (such as interlocking rotation, in which two adjacent maps become intertwined) can occur. These results support the hypothesis that activity-dependent synaptic changes play a more important role in forming the orientations of adjacent cortical maps than is currently recognized.

Recurrent neural architectures having oscillatory dynamics use rhythmic network activity to represent patterns stored in short-term memory. Multiple stored patterns can be retained in memory over the same neural substrate because the network's state persistently switches between them. Here we present a simple oscillatory memory that extends the dynamic threshold approach of Horn and Usher (1991) by including weight decay. The modified model is able to match behavioral data from human subjects performing a running memory span task simply by assuming appropriate weight decay rates. The results suggest that simple oscillatory memories incorporating weight decay capture at least some key properties of human short-term memory. We examine the implications of the results for theories about the relative role of interference and decay in forgetting, and hypothesize that adjustments of activity decay rate may be an important aspect of human attentional mechanisms.

In this paper, we investigate the use of nested evolution in which each step of one evolutionary process involves running a second evolutionary process. We apply this approach to build a neuroevolution system for reinforcement learning (RL) problems. Genetic programming based on a descriptive encoding is used to evolve the neural architecture, while a nested evolution strategy is used to evolve the needed connection weights. We test this hierarchical evolution on a non-Markovian RL problem involving an autonomous foraging agent, finding that the evolved networks significantly outperform a rule-based agent serving as a control.

Evolutionary algorithms are a promising approach to the automated design of artificial neural networks, but they require a compact and efficient genetic encoding scheme to represent repetitive and recurrent modules in networks. We present a problem-independent approach based on a human-readable and writable descriptive encoding using a high-level language. This encoding is based on developmental methods and a modular neural network paradigm. Here, we show that our approach works effectively by demonstrating that it can specify the search space compactly for "n-partition problems" and for sequence generation problems requiring recurrent networks, and that the evolved neural networks are parsimonious, modular, and capable of high-performance. We conclude that this approach based on high-level descriptive encoding can be useful in designing hierarchical, modular networks which may have recurrent connectivity, and is effective in describing the evolutionary search space, as well as the final neural networks resulting from the evolutionary process

Swarm intelligence can be viewed as the emergent collective intelligence of a group of agents, emphasizing direct or indirect local interactions among relatively simple agents. Swarm methods have been widely used for low-dimensional problems such as modeling collective movements in physical space (computer-generated animation, multi-robot teams, etc.), but they have been less studied in higher dimensional problems, mostly in the form of numerical optimization. In this work, we take a step toward applying these kind of systems to diagnostic problem-solving using causal networks. In our model, simple agents move in an abstract high-dimensional space, and based only on local interactions, generate a solution as a result of their collective behavior. Computational experiments show that this model can approximate the best diagnostic solutions (i.e., Bayesian optimal) in reasonably sized problems.

The aggregate movement of animals has inspired computational models that have proven useful for controlling navigation in teams of mobile agents. Additionally, strategies adopted from social insects have been employed in a multitude of problems to perform distributed problem solving. In this work, we combine collective movements with general problem solving capabilities to build multi-agent teams that perform search and collection tasks that require not only navigational skills but also a coordinate team strategy. The results show that agents undertaking collective movements are better able to self-coordinate and propagate information than those moving independently.

Multiple adjacent, roughly mirror-image topographic maps are commonly observed in the sensory neocortex of many species. The cortical regions occupied by these maps are generally believed to be determined initially by genetically controlled chemical markers during development, with thalamocortical afferent activity subsequently exerting a progressively increasing influence over time. Here we use a computational model to show that adjacent topographic maps with mirror-image symmetry can arise from activity-dependent synaptic changes whenever the distribution radius of afferents sufficiently exceeds that of horizontal intracortical interactions. Which map edges become adjacent is strongly influenced by the probability distribution of input stimuli during map formation. Our results suggest that activity-dependent synaptic changes may play a role in influencing how adjacent maps become oriented following the initial establishment of cortical areas via genetically determined chemical markers. Further, the model unexpectedly predicts the occasional occurrence of adjacent maps with a different rotational symmetry. We speculate that such atypically oriented maps, in the context of otherwise normally interconnected cortical regions, might contribute to abnormal cortical information processing in some neurodevelopmental disorders.

Self-organizing particle systems consist of numerous autonomous, purely reflexive agents ("particles") whose collective movements through space are determined primarily by local influences they exert upon one another. Inspired by biological phenomena (bird flocking, fish schooling, etc.), particle systems have been used not only for biological modeling, but also increasingly for applications requiring the simulation of collective movements such as computer-generated animation. In this research, we take some first steps in extending particle systems so that they not only move collectively, but also solve simple problems. This is done by giving the individual particles (agents) a rudimentary intelligence in the form of a very limited memory and a top-down, goal-directed control mechanism that, triggered by appropriate conditions, switches them between different behavioral states and thus different movement dynamics. Such enhanced particle systems are shown to be able to function effectively in performing simulated search-and-collect tasks. Further, computational experiments show that collectively moving agent teams are more effective than similar but independently moving ones in carrying out such tasks, and that agent teams of either type that split off members of the collective to protect previously acquired resources are most effective. This work shows that the reflexive agents of contemporary particle systems can readily be extended to support goal-directed problem solving while retaining their collective movement behaviors. These results may prove useful not only for future modeling of animal behavior, but also in computer animation, coordinated movement control in robotic teams, particle swarm optimization, and computer games.

We examine the extent to which modified Kohonen self-organizing maps (SOMs) can learn unique representations of temporal sequences while still supporting map formation. Two biologically inspired extensions are made to traditional SOMs: selection of multiple simultaneous rather than single "winners" and the use of local intramap connections that are trained according to a temporally asymmetric Hebbian learning rule. The extended SOM is then trained with variable-length temporal sequences that are composed of phoneme feature vectors, with each sequence corresponding to the phonetic transcription of a noun. The model transforms each input sequence into a spatial representation (final activation pattern on the map). Training improves this transformation by, for example, increasing the uniqueness of the spatial representations of distinct sequences, while still retaining map formation based on input patterns. The closeness of the spatial representations of two sequences is found to correlate significantly with the sequences' similarity. The extended model presented here raises the possibility that SOMs may ultimately prove useful as visualization tools for temporal sequences and as preprocessors for sequence pattern recognition systems.

Past self-organizing models of collectively moving "particles" (simulated bird flocks, fish schools, etc.) have typically been based on purely reflexive agents that have no significant memory of past movements. We hypothesized that giving such individual particles a limited distributed memory of past obstacles they encountered could lead to significantly faster travel between goal destinations. Systematic computational experiments using six terrains that had different arrangements of obstacles demonstrated that, at least in some domains, this conjecture is true. Furthermore, these experiments demonstrated that improved performance over time came not only from the avoidance of previously seen obstacles, but also (surprisingly) immediately after first encountering obstacles due to decreased delays in circumventing those obstacles. Simulations also showed that, of the four strategies we tested for removal of remembered obstacles when memory was full and a new obstacle was to be saved, none was better than random selection. These results may be useful in interpreting future experimental research on group movements in biological populations, and in improving existing methodologies for control of collective movements in computer graphics, robotic teams, particle swarm optimization, and computer games.

In a number of multi-agent artificial life studies where agents interact over limited distances, the emergence and/or evolution of a specific behavior may depend critically upon interagent distances. Little theoretical analysis has been done previously concerning how to predict such distances. In this paper, we derive a probabilistic method that, for an agent at an arbitrary location in a two-dimensional cellular world, predicts the expected distance to a nearest other agent. Our method works for many world topologies, and we apply it to determine the expected distance for six commonly used ones. Further, the method is readily adapted to handle special restrictions. Over a wide variety of agent densities we show that the theoretically predicted distances are largely in agreement with the distances measured in computational experiments with randomly placed agents. We then utilize our prediction method to interpret recent observations that an imprecise threshold in the density of agents exists for the evolution of communication. We thus illustrate that, despite its conceptual simplicity, our method can aid the analysis and even the design of complex artificial environments populated by agents that have the potential to interact with one another.

In the research described here we extend past computational investigations of animal signaling by studying an artificial world in which a population of initially noncommunicating agents evolves to communicate about food sources and predators. Signaling in this world can be either beneficial (e.g., warning of nearby predators) or costly (e.g., attracting predators or competing agents). Our goals were twofold: to examine systematically environmental conditions under which grounded signaling does or does not evolve, and to determine how variations in assumptions made about the evolutionary process influence the outcome. Among other things, we found that agents warning of nearby predators were a common occurrence whenever predators had a significant impact on survival and signaling could interfere with predator success. The setting most likely to lead to food signaling was found to be difficult-to-locate food sources that each have relatively large amounts of food. Deviations from the selection methods typically used in traditional genetic algorithms were also found to have a substantial impact on whether communication evolved. For example, constraining parent selection and child placement to physically neighboring areas facilitated evolution of signaling in general, whereas basing parent selection upon survival alone rather than survival plus fitness measured as success in food acquisition was more conducive to the emergence of predator alarm signals. We examine the mechanisms underlying these and other results, relate them to existing experimental data about animal signaling, and discuss their implications for artificial life research involving evolution of communication.

While recent experimental work has defined asymmetries and lateralization in left and right cortical maps, the mechanisms underlying these phenomena are currently not established. In order to explore some possible mechanisms in theory, we studied a neural model consisting of paired cerebral hemispheric regions interacting via a simulated corpus callosum. Starting with random synaptic strengths, unsupervised (Hebbian) synaptic modifications led to the emergence of a topographic map in one or both hemispheric regions. Because of uncertainties concerning the nature of hemispheric interactions, both excitatory and inhibitory callosal influences were examined independently. A sharp transition in model behavior was observed depending on callosal strength. For excitatory or weakly inhibitory callosal interactions, complete and symmetric mirror-image maps generally appeared in both hemispheric regions. In contrast, with stronger inhibitory callosal interactions, partial to complete map lateralization tended to occur, and the maps in each hemispheric region often became complementary. Lateralization occurred readily toward the side having a larger cortical region or higher excitability. Asymmetric synaptic plasticity, however, had only a transitory effect on lateralization. These results support the hypotheses that interhemispheric competition occurs, that multiple underlying asymmetries may lead to function lateralization, and that the effects of asymmetric synaptic plasticity may vary depending on whether supervised or unsupervised learning is involved. To our knowledge, this is the first computational model to demonstrate the emergence of topographic map lateralization and asymmetries.

Currently, how the brain recovers from acute damage is poorly understood. Our goal in this study was to use a neural model of the left and right hemispheric regions connected via a corpus callosum for exploration of the effects of callosal lesions. We wanted to determine how pre-lesion lateralization of function and the assumed nature of callosal influences affected post-lesion performance, individual hemispheric contribution to recovery, and regional activation levels. The overall results with lesions to our model support the hypothesis that callosal effects are predominantly excitatory.

Cortical sensory maps in mammalian brain exhibit various kinds of asymmetry and lateralization, the causes and mechanisms of which are not well understood and are a subject of controversy. This study uses a neural network model of left and right cortical regions connected via a corpus callosum to examine possible factors involved an the development of map lateralization and asymmetries. Competitive distribution of activation and competitive learning rules are used. The effects of varying callosal connection strength (both excitatory and inhibitory) in the symmetric case and in the presence of some model asymmetries are studied along with the effects of varying training input overlap. The results may provide some insight into how underlying cortical asymmetries and callosal influences can interact to cause hemispheric map asymmetries.

The effects of simulated lesions on a bihemispheric letter-identification model are examined in the acute and chronic phases under various assumptions about hemispheric asymmetries, callosal influence, and lesion size and side. In the acute phase, generally a "mass effect" is seen: post- lesion performance of the full model worsens as lesion size increases. Up to a lesion size of 80%, both hemispheres usually participate in recovery with more active participation of the damaged hemisphere, and in most cases, full recovery is achieved. For lesions of more than 80%, recovery is partial and due to improvement in the non-damaged hemisphere. Most importantly, the model demonstrates participation of the intact hemisphere in the recovery process as a function of pre-existing lateralization and lesion size, indicating that interpretation of experimental work should take these factors into account.

There have been various attempts to simulate the self-assembly process of lipid aggregates by computers. However, due to the computationally complex nature of the problem, previous simulations were often conducted with unrealistic simplifications of the molecules' morphology, intermolecular interactions, and the environment in which the lipid molecules interact. In this article, we present a new computational model in which each lipid is simulated by a more realistic amphiphilic particle consisting of a hydrophilic head and a long hydrophobic tail. The intermolecular interactions are approximated by a set of simple forces reflecting physical and chemical properties of lipids, for example, hydrophobicity and electrostatic forces, which are believed to be crucial for the formation of various aggregates. With a set of carefully selected parameters, this model is able to simulate successfully the formation of micelles in an aqueous environment and reversed micelle structures in an oil solvent from an initially randomly distributed set of lipidlike particles. This model can be used to study, at the microscopic level, the self-assembly of different protocell structures in the evolutionary process and the impact of environmental conditions on the formation of these structures. It may be further generalized to simulate the formation of other, more complex structures of amphiphilic molecules such as monolayer and bilayer aggregates.

Since von Neumann's seminal work around 1950, computer scientists and others have studied the algorithms needed to support self-replicating systems. Much of this work has focused on abstract logical machines (automata) embedded in two-dimensional cellular spaces. This research was motivated by a desire to understand the basic information-processing principles underlying self-replication, the potential long-term applications of programmable self-replicating machines, and the possibility of gaining insight into biological replication and the origins of life. We view past research as taking three main directions: early complex universal computer-constructors modeled after Turing machines, qualitatively simpler self-replicating loops, and efforts to view self-replication as an emergent phenomenon. We discuss our recent studies in the latter category showing that self-replicating structures can emerge from nonreplicating components, and that genetic algorithms can be applied to program automatically simple but arbitrary structures to replicate. We also describe recent work in which self-replicating structures are successfully programmed to do useful problem solving as they replicate. We conclude by identifying some implications and important research directions for the future.

The mechanisms underlying cerebral lateralization of language are poorly understood. Asymmetries in the size of hemispheric regions and other factors have been suggested as possible underlying causal factors, and the corpus callosum (interhemispheric connections) has also been postulated to play a role. To examine these issues, we created a neural model consisting of paired cerebral hemispheric regions interacting via the corpus callosum. The model was trained to generate the correct sequence of phonemes for 50 monosyllabic words (simulated reading aloud) under a variety of assumptions about hemispheric asymmetries and callosal effects. After training, the ability of the full model and each hemisphere acting alone to perform this task was measured. Lateralization occurred readily toward the side having larger size, higher excitability, or higher-learning-rate parameter. Lateralization appeared most readily and intensely with strongly inhibitory callosal connections, supporting past arguments that the effective functionality of the corpus callosum is inhibitory. Many of the results are interpretable as the outcome of a "race to learn" between the model's two hemispheric regions, leading to the concept that asymmetric hemispheric plasticity is a critical common causative factor in lateralization. To our knowledge, this is the first computational model to demonstrate spontaneous lateralization of function, and it suggests that such models can be useful for understanding the mechanisms of cerebral lateralization.

It has been claimed that rotation of neuronal population vectors in the primary motor cortex during tasks involving transformation of movement directions provides direct evidence that a mental rotation algorithm is being used. An alternative explanation offered here, the 'asynchronous superposition hypothesis', asserts that the apparent rotation can result from the summation of two stationary vectors, one in the stimulus direction and one in the target movement direction, which vary in length over time. Computer simulations demonstrate the surprising result that the asynchronous superposition hypothesis can produce activation of motor corex cells with intermediate preferred directions, something previously assumed to confirm a mental rotation algorithm. Simulations also demonstrate that the asynchronous superposition hypothesis accounts for some aspects of the data more naturally than does an explanation based on a mental rotation algorithm, and suggest experimental tests that can distinguish between these two hypotheses.

Previous computational models of self-replication using cellular automata (CA) have been manually designed, a difficult and time-consuming process. We show here how genetic algorithms can be applied to automatically discover rules governing self-replicating structures. The main difficulty in this problem lies in the choice of the fitness evaluation technique. The solution we present is based on a multiobjective fitness function consisting of three independent measures: growth in number of components, relative positioning of components, and the multiplicity of replicants. We introduce a new paradigm for CA models with weak rotational symmetry, called orientation-insensitive input, and hypothesize that it facilitates discovery of self-replicating structures by reducing search-space sizes. Experimental yields of self-replicating structures discovered using our technique are shown to be statistically significant. The discovered self-replicating structures compare favorably in terms of simplicity with those generated manually in the past, but differ in unexpected ways. These results suggest that further exploration in the space of possible self-replicating structures will yield additional new structures. Furthermore, this research sheds light on the process of creating self-replicating structures, opening the door to future studies on the discovery of novel self-replicating molecules and self-replicating assemblers in nanotechnology.

In the construction of neural networks involving associative recall, information is sometimes best encoded with a local representation. Moreover, a priori knowledge can lead to a natural selection of connection weights for these networks. With predetermined and fixed weights, standard learning algorithms that work by altering connection strengths are unable to train such networks. To address this problem, this paper derives a supervised learning rule based on gradient descent, where connection weights are fixed and a network is trained by changing the activation rule. It incorporates both traditional and competitive activation mechanisms, the latter being an efficient method for instilling competition in a network. The learning rule has been implemented, and the results from several test networks demonstrate that it works effectively.

How do multiple feature maps that coexist in the same region of cerebral cortex align with each other? We hypothesize that such alignment is governed by temporal correlations: features in one map that are temporally correlated with those in another come to occupy the same spatial locations in cortex over time. To examine the feasibility of this hypothesis and to establish some of its detailed implications, we studied a multilayered, closed-loop computational model of primary sensorimotor cortex. A simulated arm moving in three dimensions formed the external environment for the model cortical regions. Coexisting proprioceptive and motor maps formed and generally aligned in a fashion consistent with the temporal correlation hypothesis. For example, in simulated proprioceptive sensory cortex the map of elements responding strongly to stretch of a particular muscle matched the map of tension sensitivity in antagonist muscles. In simulated primary motor cortex the map of elements responding strongly to increased tension in specific muscles matched the map of output elements for the same muscles. These computational results suggest specific experimental measurements that can support or refute the temporal correlation hypothesis for map alignments.

Current understanding of the effects of damage on neural networks is rudimentary, even though such understanding could lead to important insights concerning neurological and psychiatric disorders. Motivated by this consideration, we present a simple analytical framework for estimating the functional damage resulting from focal structural lesions to a neural network model. The effects of focal lesions of varying area, shape, and number on the retrieval capacities of a spatially organized associative memory are quantified, leading to specific scaling laws that may be further examined experimentally. It is predicted that multiple focal lesions will impair performance more than a single lesion of the same size, that slit like lesions are more damaging than rounder lesions, and that the same fraction of damage (relative to the total network size) will result in significantly less performance decrease in larger networks. Our study is clinically motivated by the observation that in multi-infarct dementia, the size of metabolically impaired tissue correlates with the level of cognitive impairment more than the size of structural damage. Our results account for the detrimental effect of the number of infarcts rather than their overall size or structural damage, and for the "multiplicative" interaction between Alzheimer's disease and multi-infarct dementia.

Current understanding of the effects of damage on neural networks is rudimentary, even though such understanding could lead to im(cid:173) portant insights concerning neurological and psychiatric disorders. Motivated by this consideration, we present a simple analytical framework for estimating the functional damage resulting from fo(cid:173) cal structural lesions to a neural network. The effects of focal le(cid:173) sions of varying area, shape and number on the retrieval capacities of a spatially-organized associative memory. Although our analyti(cid:173) cal results are based on some approximations, they correspond well with simulation results. This study sheds light on some important features characterizing the clinical manifestations of multi-infarct dementia, including the strong association between the number of infarcts and the prevalence of dementia after stroke, and the 'mul(cid:173) tiplicative' interaction that has been postulated to occur between Alzheimer's disease and multi-infarct dementia. *Dr. Reggia is also with the Department of Neurology and the Institute of Advanced Computer Studies at the University of Maryland. 36 Eytan Ruppin, James A. Reggia

We implement and study a computational model of Stevens' [19921 theory of the pathogenesis of schizophrenia. This theory hypoth(cid:173) esizes that the onset of schizophrenia is associated with reactive synaptic regeneration occurring in brain regions receiving degener(cid:173) ating temporal lobe projections. Concentrating on one such area, the frontal cortex, we model a frontal module as an associative memory neural network whose input synapses represent incoming temporal projections. We analyze how, in the face of weakened external input projections, compensatory strengthening of internal synaptic connections and increased noise levels can maintain mem(cid:173) ory capacities (which are generally preserved in schizophrenia) . However, These compensatory changes adversely lead to sponta(cid:173) neous, biased retrieval of stored memories, which corresponds to the occurrence of schizophrenic delusions and hallucinations with(cid:173) out any apparent external trigger, and for their tendency to con(cid:173) centrate on just few central themes. Our results explain why these symptoms tend to wane as schizophrenia progresses, and why de(cid:173) layed therapeutical intervention leads to a much slower response. 150 Eytan Ruppin, James A. Reggia, David Hom

Current understanding of feature maps in proprioceptive cortex is quite limited. To complement experimental studies, we developed a computational model of map formation in proprioceptive cortex. Muscle length and tension from six muscle groups controlling the position of a model arm in three-dimensional space served as input to the simulated cortex. The resultant feature map consisted of regularly spaced clusters of cortical columns representing individual muscle lengths and tensions. Cortical units became tuned to plausible combinations of tension and length, and multiple representations of each muscle group were present. The map was organized such that compact regions within which all muscle group lengths and tensions are represented could be identified. Most striking was the observation that, although not explicitly present in the input, the cortical map developed a representation of the three-dimensional space in which the arm moved. These findings represent testable predictions about proprioceptive cortex, and may also help clarify some organizational issues concerning primary motor cortex.

Past models of somatosensory cortex have successfully demonstrated map formation and subsequent map reorganization following localized repetitive stimuli or deafferentation. They provide an impressive demonstration that fairly simple assumptions about cortical connectivity and synaptic plasticity can account for several observations concerning cortical maps. However, past models have not successfully demonstrated spontaneous map reorganization following cortical lesions. Recently, an assumption universally used in these and other cortex models, that peristimulus inhibition is due solely to horizontal intracortical inhibitory connections, has been questioned and an additional mechanism, the competitive distribution of activity, has been proposed. We implemented a computational model of somatosensory cortex based on competitive distribution of activity. This model exhibits spontaneous map reorganization in response to a cortical lesion, going through a two-phase reorganization process. These results make a testable prediction that can be used to experimentally support or refute part of the competitive distribution hypothesis, and may lead to practically useful computational models of recovery following stroke.

Implementations of competitive learning often use input and weight vectors "normalized" based on the sum of weight vector components. While it is realized that some distortion of results can occur with this procedure, it is generally not appreciated how dramatic the distortion can be, and that it compromises the dot product as a similarity measure. We show here that in some cases an input vector identical to an existing output node weight vector can be classified as belonging to a different output node. This contradicts the generally-accepted concept of weight vectors developing as prototypes during competitive learning. Ways to minimize this problem are also given.

Competitive activation mechanisms introduce competitive or inhibitory interactions between units through functional mechanisms instead of inhibitory connections. A unit receives input from another unit proportional to its own activation as well as to that of the sending unit and the connection strength between the two. This, plus the finite output from any unit, induces competition among units that receive activation from the same unit. Here we present a backpropagation learning rule for use with competitive activation mechanisms and show empirically how this learning rule successfully trains networks to perform an exclusive-OR task and a diagnosis task. In particular, networks trained by this learning rule are found to outperform standard backpropagation networks with novel patterns in the diagnosis problem. The ability of competitive networks to bring about context-sensitive competition and cooperation among a set of units proved to be crucial in diagnosing multiple disorders.

This paper describes a connectionist approach to solving computationally difficult minimum vertex covering problems. This approach uses the graph representing the vertex covering problem as the connectionist network without any modifications (nodes of the connectionist network represent vertices and links represent edges of the given graph). The activation rule governing node behavior is derived by breaking down the global constraints on a solution into local constraints on individual nodes. The resulting model uses a competitive activation mechanism to carry out the computation where vertices compete not by explicit inhibitory links but through common resources (edges). Convergence and other properties of this model are formally established by introducing a monotonically non-increasing global energy function. Simulation results show that this model yields very high accuracy, significantly outperforming a well-known sequential approximation algorithm.

Peristimulus inhibition in sensory pathways is generally attributed to lateral inhibitory connections. However, in the neocortex circuitry is incompletely understood at present, and in some cases there is an apparent mismatch between observed inhibitory effects and intracortical inhibitory connections. This paper studies the hypothesis that an additional mechanism, competitive distribution of activation, underlies some inhibitory effects in cortex. Analysis of a mathematical model based on this hypothesis predicts that per stimulus inhibitory effects can be caused by competitive distribution of activation, and computer simulations confirm these predictions by demonstrating Mexican Hat patterns of lateral interactions, transformation of initially diffuse activity patterns into tightly focused "islands" of activation, and edge enhancement. The amount of inhibition can be adjusted by varying the intensity of the underlying competitive process. The concept of competitive distribution of activation provides an important perspective for interpreting neocortical and thalamocortical circuitry and can serve as a guide for further morphological and physiological studies. For example, it provides an explanation for the existence of recurrent cortex-to-thalamus connections that perform a logical AND-operation, and predicts the existence of analogous neocortical circuitry.

A significant body of causal knowledge for diagnostic problem-solving is organized at multiple levels of abstraction. By this we mean that causal relations are specified in terms of disorder and manifestation classes that can be further refined as well as in terms of specific, unrefinable disorders and manifestations. Such knowledge enables diagnostic problem-solvers (human or automated) to efficiently form initial, high-level diagnostic hypotheses while avoiding the explicit consideration of unnecessary details. This article develops a knowledge representation framework to precisely yet naturally capture causal relations at multiple levels of abstraction. Different interpretations of high-level causal associations are precisely defined and systematically tabulated. Rules to infer implicit causal relations from explicitly declared causal relations are also identified. These ideas have been implemented in a working system for medical diagnosis. the results presented in this article also offers a new perspective on studying the semantics of knowledge representation in general.

Diagnostic reasoning at multiple levels of abstraction is an efficient problem-solving strategy. It enables diagnostic problem-solvers (human or automated) to efficiently form plausible high-level diagnostic hypotheses while avoiding the explicit consideration of unnecessary details. This article describes a domain-independent inference mechanism for diagnostic reasoning at multiple levels of abstraction. the inference mechanism uses the causal knowledge representation framework described in an earlier companion article.1 This inference strategy has been tested through the implementation of a prototype diagnostic system with encouraging results.

Abductive diagnostic problem-solving systems use causal relations to infer plausible diagnostic hypotheses. An important but controversial issue for such models is what characteristics should define the most plausible hypotheses. While there are theoretical predictions relevant to this issue, there are almost no empirical data on which to base rational decisions. Accordingly, this study examines four different criteria of hypothesis plausibility in diagnosing the site of brain damage in 100 medical patients. The criteria examined are (1) naive minimal cardinality, (2) irredundancy, (3) most probable (Bayesian), and (4) minimal cardinality when adjacency relations are taken into account. Model performance when these different hypothesis plausibility criteria are used confirms the previously predicted inadequacy of minimal cardinality. It also indicates that irredundancy (‘minimality’), the criterion most widely used in current AI models, is not useful in this setting because of the large number of alternative, implausible hypotheses it produces. The most interesting result is that a modified minimal cardinality criterion produces the best hypotheses when measured as the ratio of agreements with human experts per hypothesis generated. In addition, comparing the results of this study to two previous rule-based systems for a similar application indicates that abductive diagnostic systems can be very powerful as application programs. These results, useful in themselves, underscore the need for more systematic empirical studies of abductive problem-solving models.

Reinforced and supervised variations of competitive learning are developed and contrasted with D. Rumelhart and D. Zipser (Cognitive Science, vol.9, p.75-112, 1985), the one previous similar effort known to the authors. Their implementation assures that an output node's weight vector only learns for nodes in one desired grouping by spatially separating the desired groupings. The authors' implementation directly ensures that an output node's weight vector only learns for nodes in one desired grouping by specifying which output node should win for each input vector and only having that output node's weight vector learn for the input vector. The present version of supervised competitive learning provides the advantages of needing no additional input or weight vector components (which, for large input vectors, can significantly increase the size of the network) and guaranteeing that if the network converges to the desired classification during learning, it will still produce the desired classification when learning is subsequently turned off

A description is presented of the first learning rule devised to work with competitive activation mechanisms. Terminology is defined and the idea of a competitive activation mechanism is summarized. A basic unsupervised competitive learning rule for use with competitive activation mechanisms is presented, and the results of a small series of experiments that demonstrate the viability of this approach are described. The basic unsupervised competitive learning rule is then analyzed, identifying fixed points and contrasting its use with competitive and noncompetitive activation rules. Analysis shows that using competitive activation mechanisms corrects for weight vector distortions that have occurred in previous competitive learning systems. Simulations provide evidence that this learning rule can be used effectively

A phase transition in a connectionist model refers to a qualitative change in the model's behavior as parameters determining the spread of activation (gain, decay rate, etc.) pass through certain critical values. As connectionist methods have been increasingly adopted to model various problems in neuroscience, artificial intelligence, and cognitive science, there has been an increased need to understand and predict these phase transitions to assure meaningful model behavior. This paper extends previous results on phase transitions to encompass a class of connectionist models having rapidly varying connection strengths (“fast weights”). Phase transitions are predicted theoretically and then verified through a series of computer simulations. These results broaden the range of connectionist models for which phase transitions are identified and lay the foundation for future studies comparing models with rapidly varying and slowly varying connection strengths.

A recently proposed connectionist methodology for diagnostic problem-solving is critically examined for its ability to construct problem solutions. A sizeable causal network (56 manifestation nodes, 26 disorder nodes, 384 causal links) served as the basis of experimental simulations. Initial results were discouraging, with less than two-thirds of simulations leading to stable solution states (equilibria). Examination of these simulation results identified a critical period during simulations, and analysis of the connectionist model's activation rule during this period led to an understanding of the model's non-stable oscillatory behavior. Slower decrease in the model's control parameter during the critical period resulted in all simulations reaching a stable equilibrium with plausible problem solutions. As a consequence of this work, it is possible to determine more rationally a schedule for control parameter variation during problem solving, and the way is now open for real-world experimental assessment of this problem-solving method.

A competition-based connectionist model for solving diagnostic problems is described. The problems under consideration are computationally difficult in that multiple disorders may occur simultaneously and a global optimum in the space exponential to the total number of possible disorders is sought as a solution. To solve this problem, global optimization criteria are decomposed into local optimization criteria that are used to govern node activation updating in the connectionist model. Nodes representing disorders compete with each other to account for each 'individual' present manifestation, yet complement each other to account for all present manifestation, yet complement each other to account for all present manifestations through parallel node interactions. When equilibrium is reached, the network settles into a locally optimal state in which some disorder nodes (winners) are fully activated and compose the diagnosis for the given case, while all other disorder nodes are fully deactivated. A resettling process is proposed to improve accuracy. Three randomly generated examples of diagnostic problems, each of which has 1024 cases, were tested.>

Self-processing networks (connectionist models, neural networks, marker-passing systems, etc.) represent information as a network of interconnected nodes and process that information through the controlled spread of activation throughout the network. Properties characterized as manifestations of intelligence, such as associative recall of stored memories, pattern classification, and learning, are emergent properties; they are global system properties that arise from the concurrent local interactions between the numerous network components. The authors characterize the nature of self-processing networks developed as models of intelligent systems in neuroscience, cognitive science, and artificial intelligence, and contrast them with more traditional information processing models.>

Parsimonious covering theory is a formal model of abductive diagnostic problem-solving, Diagnostic knowledge is represented as a network of causal associations, and inferences are made using a sequential hypothesize-and-test procedure. In this article, we extend the methods available in parsimonious covering theory and related models to handle causal chaining (situations where multistep causal associations exist between disorders and manifestations). These extensions make parsimonious covering theory capable of representing a much broader range of real-world diagnostic problems.

The issue of how to effectively integrate and use symbolic causal knowledge with numeric estimates of probabilities in abductive diagnostic expert systems is examined. In particular, a formal probabilistic causal model that integrates Bayesian classification with a domain-independent artificial intelligence model of diagnostic problem solving (parsimonious covering theory) is developed. Through a careful analysis, it is shown that the causal relationships in a general diagnostic domain can be used to remove the barriers to applying Bayesian classification effectively (large number of probabilities required as part of the knowledge base, certain unrealistic independence assumptions, the explosion of diagnostic hypotheses that occurs when multiple disorders can occur simultaneously, etc.). Further, this analysis provides insight into which notions of "parsimony" may be relevant in a given application area. In a companion paper, Part Two, a computationally efficient diagnostic strategy based on the probabilistic causal model discussed in this paper is developed.

An important issue in diagnostic problem solving is how to generate and rank plausible hypotheses for a given set of manifestations. Since the space of possible hypotheses can be astronomically large if multiple disorders can be present simultaneously, some means is required to focus an expert system's attention on those hypotheses most likely to be valid. A domain-independent algorithm is presented that uses symbolic causal knowledge and numeric probabilistic knowledge to generate and evaluate plausible hypotheses during diagnostic problem solving. Given a set of manifestations known to be present, the algorithm uses a merit function for partially completed competing hypotheses to guide itself to the provably most probable hypothesis or hypotheses.

Use of a heuristically guided state-space search to classify complex errors in discrete sequential processes is described, and a general method for deriving heuristic function to guide such a search is introduced. A specific heuristic function and alternate sets of elementary errors are studied through the use of an implemented program.