Simulation: D. Mani and L. Shastri, "Massively Parallel Real-time Reasoning with Very Large Knowledge Bases: An interim report", TR-94-031 International Computer Science Institute (ICSI), August, 1994.
Introduction
Shastri and Ajjanagaddes (1993) Connectionist model SHRUTI is an attempt to model the efficiency with which humans reason. From the perspective of artificial intelligence researchers, reasoning is seen as an inherently complex task whereas cognitively, reasoning is achieved efficiently as if it were a reflexive response to some given stimuli. The aim of the model is to encode knowledge in a manner that will allow real-time or rapid reasoning when mapped to a massively parallel computing architecture. Mani and Shastri (1994) define real-time or rapid reasoning to be reasoning that is fast enough to support real-time language understanding.
To achieve an efficient reasoning system Shastri and Ajjanagadde solve the problem of dynamically binding fillers to roles within a semantic network. Long term knowledge, explicitly encoded in the form of rules and facts, is then used to construct a network capable of reasoning in a time that is independent of the size of the knowledge base. Although the system can reason efficiently by either forward or backward chaining, we confine the description of SHRUTI to the backward chaining case.
The Network
Reasoning is accomplished in the SHRUTI model by the interaction between two distinct subnetworks; the rule based reasoner and the IS_A hierarchy. Both networks are composed of nodes with distinct behaviour over a defined time frame. The IS_A hierarchy encodes is a and instance of relations between entities that can be bound to roles in the reasoning network. Every entity in the knowledge base has an associated node in the hierarchy and as a node is selected to be part of a query, its activation is propagated along connections in both subnetworks. The direction of propagation in the IS_A hierarchy being dependent on the quantification of its associated variable in the query. The rule based reasoner contains groups of nodes that represent predicates and their associated facts. Connections between predicates in the system encode rules of inference between the predicates. When a predicate is queried and fillers bound to nodes representing its arguments, activation propagates simultaneously both to test whether the current bindings represent a known true instance of the predicate and also to query antecedent predicates in a further search to confirm the original query.
Task
To test the efficiency of the SHRUTI model when mapped to a massively parallel architecture, Mani and Shastri (1994) constructed an artificial knowledge base containing 150,000 rules, 150,000 facts, 50,000 predicates and 50,000 entities. To examine how the time taken for reasoning scales with the size of the knowledge base, queries were posed to the system with different inferential depth and the response times compared. Of the two massively parallel architectures chosen, the connection machines CM-2 (a SIMD architecture) and CM-5 (a MIMD architecture), the CM-5 showed a 100-fold speed increase due to its superior message passing ability between processors. The results showed that the response time for queries requiring an inference depth of up to eight was under 500 milliseconds.
The method employed to map the SHRUTI network to the CM-2 and CM-5 connection machines is beyond the scope of this case study but is discussed in length in Mani and Shastri (1994). The following paper examines the original SHRUTI model from the perspectives of time, structure, memory and change.
Structure
The network structure is created from symbolic definitions in the form of rules, facts and is a relations. A fact states a correspondence between the arguments of a predicate and nodes representing entities in the IS_A hierarchy. Rules define a correspondence between a predicate, its antecedents and connections from the is_a hierarchy which ensure correct types are occurring in predicate arguments. IS_A relations define relations between instances and concepts only in the IS_A hierarchy.
There are no existing mechanisms to automatically change the structure of the network or the behaviour of individual nodes. Knowledge is hardwired into the network either during the networks construction or added to the network at some later stage. The following sections outline the structure of the IS_A hierarchy and the rule based reasoner in greater detail.
IS_A Hierarchy
The IS_A hierarchy consists of nodes which represent constant values and the links between the nodes represent is a and instance of relations between entities. This is a somewhat simplified description of the hierarchy as concepts, being distinct from instances, require a number of nodes for their representation and a mechanism to control the direction of propagation within the subnetwork. The group of nodes that represent a single concept are referred to as a concept bank.
If an of a query to the knowledge base is universally quantified then the concept node associated with this binding propagates its activation upwards through the hierarchy to its superconcepts. As more than one entity may share a superconcept it is necessary to disambiguate which entity is represented at the superconcept. This is managed by a bank of nodes at a concept, if a concept receives input from a number of subconcepts or instances then a nodes from the concept banks are associated with each of the inputs.
If an entity is chosen to be bound to an existentially quantified variable during a query, then not only must its signature propagate to its ancestors but also its descendents and the ancestors of its descendents. The reason that a concept can be associated with an existential variable is that the interaction between the rule based reasoner and the IS_A hierarchy allows for type constraints on the variables that can participate in a session of reasoning. This enables queries like "Is there a anything furry that can eat Tweety".
The structure required to ensure the direction of propagation in the hierarchy and assignment of a concept node to an input to the concept bank are quite complex and beyond the scope of what is required in this case study.
Rule Based Reasoner
The rule-based reasoner consists of predicates that are composed of several nodes. Each predicate argument has an associated node which receives input from its corresponding node in a consequent predicate. This ensures systematicity between the arguments in rules. To enable reasoning a further two nodes are required within a predicate; an enabler node and a collector node. An enabler node receives input from enabler nodes in consequent predicates and the collector node receives input from collector nodes in antecedent predicates. Activating the enabler node in conjunction with the argument nodes queries the predicate, the query will be confirmed if the collector node becomes active.
Nodes representing facts associated with a predicate are realized by connections from the arguments of a predicate and entities in the IS_A hierarchy. The collector node in a predicate also has receives input from all fact nodes associated with the predicate.
Time
Time and timing play an integral role in a SHRUTI system as every node type within the network can exhibit an oscillatory behaviour. The nodes most crucial to the reasoning process are Tau-or nodes and Rho-btu nodes. Tau-or nodes are employed as enabler, collector and fact nodes while Rho-btu nodes are used to represent the arguments of predicates and concepts/instances in the IS_A hierarchy. Rho-btu nodes may exhibit different oscillatory behaviour depending on the oscillatory activation of other Rho-btu nodes from which they receive input. In this manner Rho-btu nodes can be distinguished from each other based on their activation over time and provide the basis for dynamic binding.
Dynamic Binding
All node types in the network are capable of firing in a discrete, non overlapping time slices. If we consider a time interval consisting of a fixed number of such time slices, then it becomes possible to assign the same meaning to nodes which fire in the same time slice within that period. The Rho-btu nodes representing entities and predicate arguments in the system are restricted to only firing during a single time slice in the given period. The dynamic binding of a filler to a role is then achieved when both the node representing a particular entity and an argument node are firing in phase. As there must be a limited number of time slices within a time interval, the total number of entities that can be bound to arguments in a reasoning process must be limited.
Reflexive Response
Time plays a further part in the system as a query posed to the network must be confirmed within a certain number of time intervals before it is assumed false. As every node in the network requires a full period of oscillation before its activation will be known, then every predicate in the knowledge base also requires a full period of oscillation before activation from its nodes can be propagated to its antecedent predicates. This implies that the time taken for a confirmation of a query will be proportional to the length of the longest inference path needed to confirm the query.
Memory
Memory in the system is realized in the structure of rule based reasoner and the IS_A hierarchy which combine to realize temporal pattern matchers during the propagation of activation. The temporal pattern matchers are employed to provide mechanisms for encoding facts about a predicate and type restrictions on the entities that may participate in a valid rule.
Enabler, fact and collector nodes are Tau-or nodes and must receive input in every time slice for a full period of oscillation to begin firing in every time slice during the ensuing period. If the pulse train is interrupted for a single time slice a Tau-or node will cease firing. To realize a fact, a connection is made from a predicates enabler unit to a fact unit. Thus, the enabler firing for a full period will lead to the firing of the fact unit. To match the bindings being propagated between predicate arguments an inhibitory connection is made from the argument units to the connection between the enabler and fact nodes. When the arguments are active and firing in particular time slices, these connections impede the pulse train between the enabler and fact nodes. For a fact unit to fire, that is, the relationship between the current bindings is true, all that is necessary is to impede any activation propagating along the inhibitory connections from the arguments. This is achieved by providing inhibitory connections from nodes in the IS_A hierarchy firing in phase with the argument units.
Change
Reasoning is a reflexive response to a query by the propagation of a change in the oscillatory behaviour of nodes. When a query is posed to a SHRUTI database, a spike train is applied to the enabler unit of a predicate for a full period during which each argument node is caused to fire in phase with a concept unit appropriate to the query. The activation of nodes within the queried predicate propagates the query to antecedent predicates and simultaneously attempts to activate fact nodes associated with the predicate. When a fact node commences firing it causes the collector node in the associated predicate to become active, indicating the query is true. If none of the local fact nodes become active, the query may still be confirmed by the predicates collector becoming active due to the queries propagated to each of the antecedent predicates.
Conclusion
The SHRUTI model is capable of representing a restricted first order logic where unification is replaced by ensuring systematicity between predicate arguments and matching processes. The penalties incurred by avoiding a unification process become apparent when trying to express equality among the arguments of a rules antecedent. If there is no corresponding argument in the rules consequent, systematicity is insufficient to ensure that variables in the antecedent will become bound to the same, in fact any, entity. Shastri and Ajjanagadde suggest that the model is biologically plausible in several aspects; the number of nodes required to represent a long term knowledge base is linear in the size of the knowledge base; the speed at which the system can respond to a query and the use of temporal synchrony to solve the dynamic binding problem. They also indicate psychological implications of the model, for example, drift in the firing times causing a loss of synchronisation between nodes especially over very long inference paths could produce spurious results even though the knowledge is explicitly represented in the network.
References
L. Shastri and V. Ajjanagadde, "From Simple Associations to Systematic Reasoning: A Connectionist representation of rules, variables and dynamic bindings using temporal synchrony", Behavioural Brain Sciences 16: pp 417-494, 1993.
D. Mani and L. Shastri, "Massively Parallel Real-time Reasoning with Very Large Knowledge Bases: An interim report", TR-94-031 International Computer Science Institute (ICSI), August, 1994.