Spatial Reasoning and Connectionist Inference

1 Introduction

Intellectics, ie. Artificial Intelligence and Cognitive Sci­ ence, is an interdisciplinary field whose goals are to un­ derstand and explain intelligence on the one hand and to develop computational models which show intelligent behavior on the other hand [Bibel, 1992]. In recent years the field has developed in many subfields and these sub­ fields are often developed as independent areas. Auto­ mated Reasoning and Connectionism are such subfields. Ori~inally, the goal of Automated Reasoning was to for­ malize human thought. Much work in this area is di­ rected toward the developement of automated theorem provers for certain logics. But although these systems show quite impressive computational power they are of­ ten not adequate as it takes them a long time to solve problems which humans solve almost immediately.

Connectionist and PDP models, on the other hand, have recently attracted much attention as they were ap­ plied to m~dels. of behav~or which match psychological data, are b1ologtcal plaus1ble, and computationally effi­ cient. But considerably little experience has been gath­ ered so far in modelling high-level cognitive tasks such ~ knowledge representation and reasoning. Connection1St systems are not yet able to handle inference, the main process of cognition [Fodor and Pylyshyn, 1988], and Paul Smolensky [1987] has argued that connection­ ilt IY6tem6 may well offer an opportunity to e1cape the brittlene88 of 1ymbolic AI 1y8tem8 ... if we can find way1

· A long version of this paper is available from the authors.

fA B ' . . ermger lS supported by DFG, project MPS, grant no. HO 1294/3-1. F. Kurfefi is supported by BMFT, project WINA, contract no. 413-4001-01 IN 103 E/9.

Franz Kurfeflt

N euroinformatik, U niversitii.t Ulm Oberer Eselsberg D-7800 Ulm (Germany) franz@neuro.informatik. uni-ulm.de

of ~atur~ll~ in1tantiating the power of symbolic compu· tataon wtthm fully connectioni1t 8y8tem8.

Unfortunately, the relationship between automated reasoning and connectionist models has often been ne­ glected. There are only few exceptions like the work by.Gadi_ Pinkas [1991b; 1991a], who investigated there­ la~l~ns.hlp. between propositional reasoning and energy m1mm1zat10n, o~ J . A. Barnden [1989], who has given a neural network 1mplementation of syllogistic reasoning. L. Shastri and V. A.jjanagadde [1993] even talk about ~he AI paradoz which means the gap between the abil­ lty of humans to draw a variety of inferences effortlessly spontaneously, and with remarkable efficiency and th~ ~esults _about the ~?mplexity of reasoning. As shown m [Bermger and Holldobler, 1993] Shastri and Ajjana· gadde's connectionist inference system can be simulated by a classical deductive system if appropriate reduction techniques are applied in parallel.

_CHCL is another attempt to investigate the relation· sh1p between automated reasoning and connectionism ~Holldobler, 1990a; Holldobler and Kurfefi, 1992]. CHCL 1s ?' purely connectionist inference system for Horn lo~~c, based on a connectionist unification algorithm [Holldobler, 1990b]. It utilizes the connection method [Bibel, 1987], where a proof for a formula consists of a so-called spanning set of simultaneously unifiable pairs of literals (occurring in this formula) . CHCL generates sequentially all spanning sets for a given formula and unifies the pairs of literals in these sets in parallel. It al~o c~ntains various reduction techniques which are ap­ plied m parallel and essentially reduce the number of spanning sets.

In this paper we show how a slightly modified ver· sion of CHCL can solve spatial reasoning tasks occur· ring in the miniature language acquisition project L0· Lo is a project to investigate how could we learn to de­ scribe what we see [Feldman et al., 1990]. The task is to construct a system that decides after a learning period whether a statement is a true description of a given pic· ture. The pictures show two-dimensional scenes with simple geometric objects. The statements are drawn from a finite corpus capturing (as closely as possible) the meaning of English descriptions. As an example, Figure 1 shows a typical scene with a true description.

A first attempt to give a connectionist semantics for the sf.atial relations has been made by S. H. Weber [1991 . Since the prohibitive combinatorics makes it im· possible to simply tabulate all geometric relationships, her idea is to employ an iterative search controller pro­ viding a focus on certain candidate objects. An open problem in Weber's approach is the question how such a controller can be modelled in a connectionist setting and this is one of the tasks considered here.

The connectionist system presented in this paper de­ cides whether a statement is a true description of a vi­ sual scene. The objects in the scene are represented analogically as a pattern of activation in a matrix of units called plane. As only a limited number of ob­ jects is present in each scene, the objects are phase­ coded as in [Shastri and Aijanagadde, 1993]. The ex­ ternal activation of the objects leads to the recruitment of a reference unit for each object such that (after the recruitment) the excitation of the reference unit trig­ gers the activation of the object in the plane and vice versa. The features of each object - ie. its shape, size, and shade - are extracted using a trained multi-layer feed-forward network such that this information becomes available for CHCL. The rules defining spatial relations like bel(T, L) {: rbel(L, R) A in(T, R) -expressing that a trajector T is below a landmark L if there is a region R below L and T is in R - are represented as usual in CHCL 1 · The facts for the relations rbel and in are not explicitely represented, rather there is a dummy for the two relations which tells CHCL that there are facts for rbel and in. As described in the next paragraph these facts are inferred abductively as soon as necessary. Fi­ nally, the sentence is posed as a query.

As CHCL generates the spanning sets of a formula se­ quentially, it provides the controller for focussing on cer­ tain objects and spatial relations. If, for example, the controller requires to check whether the object b is be­ low the object cas shown in Figure 1, then the dummy for rbel and in is activated with L bound to c and T bound to b. With the help of the reference unit for c, the activation of the dummy will trigger a downward spreading of activation in the plane originating from the units representing c. If this activation reaches the units representing b, then b is in the region below c.

In Section 2 the kind of spatial reasoning problems considered here is presented. Section 3 briefly describes CHCL and the main Section 4 describes the modifications and extensions of CHCL needed to solve the spatial rea­ soning problems. Finally, Section 5 discusses the results and possible directions for future work.

1 Variable symbols begin with upper case letters, whereas predicate and constant symbols begin with lower case letters. Variables are considered to be universally quantified.

As mentioned, the problem is to decide whether a given statement is a true description of a given visual scene containing simple graphical objects. We are interested in their shape (square sq, triangle tr, or circle ci), shade (dark da or light li), and size (large l, medium m, or small s ). The scene is given as a picture from which we have to extract the features. In the example shown in Figure 1 we should extract the facts obj(a, sq, da, s), obj(b, sq, li, l), and obj(c, ci, li, s), with system gener­ ated internal names a, b, and c. The spatial relations are defined by universally closed rules of the general form

where relation is abv, bel, lo, or ro denoting that the trajector Tis above, below, left or right of the landmark L, respectively. in denotes that T is in region R and spec_region is rabv, 1'bel, rlo, or rro denoting the region R above, below, left or right of L, respectively. 2 To solve the example shown in Figure 1 we need the rules

Such rules are applicable if their conditions are satisfied. This requires to determine regions in the visual scene and to check whether an object is in a certain region. In our example this requires to determine the region r1 right­ of object b ( rro(b, rl)) and the region r 2 below object c (rbel(c, r2)), and to check whether object a is in 7'1 (in(a,rl)) and b is in r2 (in(b,1'2)).

A statement is a conjunction of atomic propositions describing objects and their spatial relations. State­ ments are quite simple English sentences and we may assume that they are in relational form. The sentence in Figure 1 can thus be expressed as the query 3

Logically, to determine whether a statement correctly describes a picture we must decide whether the query representing the statement is a logical consequence of the facts about objects and regions extracted from the picture and the set of rules defining the spatial relations.

3 CHCL

CHCL is a connectionist inference system for Horn logic [Holldobler, 1990a; Holldobler and KurfeB, 1992]. From its expressive power it can easily handle the kind of prob­ lems presented in Section 2 if all the rules and facts are given. CHCL is based on the connection method [Bibel, 1987]. This method tells us that a proof of a formula is found, if there exists a spanning set of pairs

2 0ne should observe that Shastri and Ajjanagadde's [1993] as well as Lange and Dyer's [1989] inference system carmot handle this kind of rules as the variable Z does not occur in the conclusion of the rule but twice in its conditions.

3 The symbols "-" denote different variables, where we do not care about the bindings. The connectionist inference sys­ tems proposed in [Shastri and Ajjanagadde, 1993] and [Lange and Dyer, 1989] again cannot handle this kind of queries as unbound variables like the X occur more than once.

.,.

.,.

Figure 2: The formula representing the problem depicted in Figure 1, where the logical connectives are omitted. The lines show unifiable pairs of literals. The set of pairs of literals shown by regular lines is a spanning set.

of literals such that all pairs are simultaneously unifi­ able. A spanning set can informally be defined as fol­ lows: Each literal occurring in the query must be in the spanning set and, if the conclusion of a rule is in the spanning set, then each literal occurring in the con­ ditions of the rule must be in the spanning set. It is easy to check that the regular curves in Figure 2 form a spanning set. Moreover, all pairs of literals in this set are simultaneously unifiable yielding the answer substi­ tutiOil {X 1-+ a, Y 1-+ b, U 1-+ b, V 1-+ c}. For all other spanning sets the pairs of literals are not simultaneously unifiable.

CHCL contains a subnetwork to represent the pairs of literals which are potential elements of spanning sets. For each pair of literals l this subnetwork contains an output unit which becomes active iff l is an element of the current spanning set. The subnetwork resembles a Jordan network [Jordan, 1986] and sequentially gener­ ates the various spanning sets of a formula. As soon as a spanning set has been determined, all pairs of literals occurring in this set have to be simultaneously unified. This is done with the help of the connectionist unifica­ tion algorithm presented in [Holldobler, 1990b].

Terms are represented in a so-called term layer using a role-filler representation as shown in Figure 3. Each ele­ ment of the term layer is a selfexcitatory binary thresh­ old unit. The eight units representing shape, shade, and size are referred to as the feature vector. The large dark squares · represent the terms in the original for­ mula. If the spanning set contains a pair of literals like (-,obj(X, _, da, _), obj(a, sq, da, s )), then the representa­ tions of the terms of these literals in the term layer are feature vector put on top of each other. This is simultaneosly done for all elements of the spanning set. In Figure 3 the medium sized dark squares · show the result of this process for the spanning set defined by the regular curves in Fig­ ure 2. Now, the terms are unified.

The problems considered in this paper are such that terms are constants and variables only. Hence, unifi­ cation is successful if multiple occurrences of the same variable are bound to the same term and two different constants do not appear in the same position. The bind­ ings are represented as the activation pattern of the rows in the term layer. For example, from the activation pat­ tern in the first row of the term layer shown in Figure 3 we learn that the variables X and T are bound to the constant a. The unification algorithm further activates units such that whenever a variable occurs in more than one row, then the activation patterns of these rows are recursively put on top of each other until eventually they become identical. This takes no longer than O(log(n)) time in the worst case, where n is the number of vari­ ables occurring in the formula. The small dark squares 1 show the result of this process for the running example. Two different constants appear in the same position if in one line more than one unit for the shape, shade, size, or references is active. As this is not the case in Figure 3 all elements of the spanning set are simultaneously unifi­ able and, hence, a proof is found. Note that an attempt to unify obj(X, _, da,_) and obj(a, sq, li, l) would result in the simultaneous activation of the units representing darkness ( da) and lightness ( li) for the two literals.

4 Spatial Reasoning with CHCL

A slightly modified version of CHCL can be used to deal with the problems described in Section 2. We consider a fixed query together with a fixed number of copies of each rule. The maximal number of simultaneously con­ siderable objects is restricted tow, where w = 7 seems to be a biologically and psychologically plausible restriction [Miller, 1956; Shastri and Ajjanagadde, 1993].

The picture is represented as a pattern of activation in a matrix of units, called plane, where each unit repre­ sents an atomic part of the picture. To distinguish the objects considered simultaneously, they are coded in dif­ ferent phases. So the matrix units are phase sensitive binary threshold units. Those collectively representing an object are activated in the same unique phase.

The objects and their features must be extracted from the analogue representation. The object descriptions are stored in feature vectors as described in Section 3. To establish the correspondence between the units repre­ senting a certain object in the plane and the associated object description in the term layer we use phase sensi­ tive reference unit6, which are recruited in an extra step. A reference unit will be activated if the units of the cor­ responding object in the plane are active, and vice versa. Thus, by activating the reference unit via the feature vec­ tor, the analogue object representation can be retrieved and by activating the reference units via the analogue object representation, ie. the units in the plane, the ob­ ject's internal name and features can be recovered.

Spatial relations between objects must be inferred ab­ ductively. In particular, we must consider regions in the plane wrt a given landmark and check whether a given trajector is in such a region. The regions are identified by spreading of activation originating from the units rep­ resenting the landmark. Therefore, each of the units in the plane is connected to its neighbours and these con­ nections are controlled by phase sensitive direction gates. H, for example, the region below a landmark is to be con­ sidered, the gates on the connections going downwards from the units in the plane are opened through activation of the corresponding direction unit. If the units repre­ senting the landmark are activated now, this activation spreads downwards in the plane. Since the involved units are phase sensitive, w different regions can be generated simultaneously without cross-talk.

After stating the sentence as a query and presenting the picture by externally activating appropriate matrix units the network's tasks are as follows.

1. Recruit a reference unit for each object.
2. Extract the features of the objects.
3. Generate a new spanning setS. If there exists none, stop with NO.
4. Simultaneously unify the pairs of literals occurring in S. If this results in a failure go to 3.
5. Try to abductively infer the regions and related facts needed for S being a proof for the query. If this is possible, then stop with YES; otherwise go to 3.

The recruitment of the reference units can be done as described in [Diederich, 1988] or [Feldman, 1982]. The reference units are connected bidirectionally to every matrix unit via links with initially low weights which are adjusted phase dependently by Hebbian learn­ ing. The connections from the matrix to the reference units are in addition normalized [Grossberg, 1988] such that a threshold of . 7, for example, means that the ref­ erence unit should be activated if more than 70% of the units representing the object in the plane are active. In other words, if at least 70 % of an object are in a certain region, the object is said to be in this region.

The feature extraction component mainly consists of a feed forward network built of the matrix units as input units, one hidden layer, and eight phase sensitive units representing a condensed version of the feature vec­ tors {CFV), where the features of all objects are coded in parallel by a phase dependent representation. The correct weights of the connections are learned by back­ propagation. Thereafter, the pattern of activation in the plane causes some units of the CFV to be activated. As each reference unit is activated in a unique phase, they can be used to divide the CFV into at most w separate feature vectors (see Figure 4). The rows of the feature vectors in the term layer additionally contain w marker units representing the internal names of objects.

The computation of the spanning sets is ex­ plained in Section 3. The number of spanning sets is always finite as we allow only a fixed number of copies for each rule. Thus, if none of the spanning sets consti­ tutes a proof, a user may provide additional copies.

The abductive reasoning component is explained with respect to the example shown in Figure 1. From the feature extraction component we obtain the facts shown in Figure 4. Thereafter, CHCL eventually generates the spanning set (2) except that the facts rro(b, rt), in( a, rt), rbel(c, r 2), and in(b, r2) represent­ ing the spatial relations are not present yet. After a successful unification of the pairs of literals in the spanning set, it must be checked whether ro(a,b) and bel(b,c) hold. The rows in the term layer representing the conditions of these rules are partially instantiated to rro(b, R), in( a, R) and 1'bel(c, R'), in(b, R'). Figure 5 shows the rows for rbel(c, R') and in(b, R').

The literals in the body of a rule share a rule unit be­ ing activated by the spanning set unit for the head of the rule (see Figure 5) . The rule unit is the dummy e~tab­ lishing that the two literals in the body share a var1able not occuring in the head of the rule. Moreover, it represents the assumption that facts satisfying the conditions of the rule can be inferred. Figure 5 shows the part of the spatial inference component to infer bel(b,c). The tasks of its units are the following.

The spanning set unit belonging to the conclusion of the rule activates two other units, viz. the binary fail­ ure unit and the rule unit.

The failure unit signals that the rule has been used. It is connected to the answer component of CHCL. This connection is inhibited if spatial relations satisfying the conditions of the rule can be inferred. Otherwise, the activation of the failure unit forces a negative answer.

The rule unit must trigger the abductive inference process and, therefore, has three tasks, viz. to open the correct gates in the plane, to activate the units represent­ ing the landmark - and, thus, to activate the missing region -, and to check whether the trajector is in the region. The rule unit is phase sensitive and, hence, w different spatial relations can be tested simultaneously.

If a rule unit is excited in phase p, it causes the opening of the appropriate direction gates in the plane for p by exciting the corresponding direction unit in phase p. In Figure 5 the down unit is activated. As the marker c in the term layer row for rbel is activated, the rule unit excites the reference unit for c in phase p by opening the corresponding gates. The reference unit excites the units representing c in the plane in phase p. (The connections between the reference units and the plane are not shown in Figure 5.)

To infer whether the trajector b is in the region below c, the rule unit opens the gates on the connections from marker units of the in row to the gate on the connection from the reference units to the failure unit in phase p. Thus the activation of the marker unit b is propagated in phase p and causes the opening of the gate behind refer­ ence unit b in phase p. As b is below c in the plane, the activation of the corresponding units for c in the plane spreads downwards and reaches the units for b. Thus these units and, consequently, the reference unit for b become active in phase p, too. Reference unit b now in­ hibits the connection from the failure unit facilitating a positive answer . The marker units for rbel inhibit the connections from the same marker in in, avoiding infer­ ences like bel(a,a).

Finally, as different phases are used for the rule units, the relations bel(b,c) and ro(a,b) can be tested simulta­ neously. The activation of the units representing object b does not spread to the right, because the gates to the right are opened only in a different phase corresponding to the query ro(a,b).

5 Discussion

We would like to build a system which decides whether a statement in natural language is a true description or a given picture. Such a system must be capable of rea­ soning, learning, and autonomous operation; it should be massively parallel and physiologically plausible. The main emphasis in this paper is on the reasoning compo­ nent. Therefore, we assume that the description is avail­ able in a logic notation and that the picture is given as a pattern of activation in a .matrix of units. In this setting a number of technical problems have to be solved: an adequate internal representation has to be found; the reasoning mechanism has to be powerful enough; the correlation between the objects and their features has to be preserved; the description of features cannot be in absolute terms and linguistic variables [Zadeh, 1989] might be necessary to characterize their relative values; the variable binding problem; the treatment of alterna­ tive solutions; abductive reasoning via the generation of required facts on demand; the concordance between the expression of spatial relations in language and the rela­ tive positions of objects in the visual scene.

The system presented in this paper achieves most of the goals and solves the technical problems in a proto­ typical way. The reasoning mechanism is essentially the same as in CHCL. In contrast to other connectionist in­ ference mechanisms ( eg. [Shastri and Ajjanagadde, 1993; Lange and Dyer, 1989]) CHCL is powerful enough to deal with the class of problems required here. Our sys­ tem is capable of learning to associate objects and fea­ tures. A backpropagation network is trained to extract features from the pixel representation; no information about the relative or absolute position is preserved. Ref· erence units are recruited to relate the objects in the geometric scence to the internal reprentation of their fea­ tures. The quest for autonomous operation obviously is relative: after extensive training we expect the system to be capable to handle previously unseen pictures and new sentences. CHCL is a massively parallel inference system in the sense of [Feldman and Ballard, 1982]. Computa­ tion is performed by spreading activation.

As for the more technical problems, we have shown that the internal representation as used in CHCL can be applied without major problems to the specific task of spatial reasoning. Physiological and cognitive plau­ sibility can be considered on various levels. On a high level, the treatment of alternative solutions in CHCL is sequential, which seems to be the same for reasoning tasks which require deliberate thinking in humans. On a lower level, there is no strong evidence that reasoning problems are represented in the brain as matrices mirror­ ing the structure of predicates and terms. As a model, however, neural networks can be represented in a similar way as associative memories [Palm, 1980], which again have a strong similarity to the structure of the matrix used in CHCL. For the bindings between objects and their features [Rock and Palmer, 1990] and for testing spatial relations we use phase-sensitive units similar to the ones used in [Shastri and .Aijanagadde, 1993]. This concept seems to be quite plausible and allows to treat a moderate number of objects and relations simultane. ously. The use of linguistic variables is implicit in the learning process for the features and their values. How­ ever, it is not yet supported from the language end.

A solution for the variable binding problem as well as for the treatment of alternative solutions is already given through CHCL: the correspondence between vari­ ables and their values are represented in the term layer as shown in Figure 3, and alternative solutions corre­ spond to different spanning sets. In contrast to conven­ tional inference mechanisms this representation even al­ lows for a straightforward realization of abductive reaso­ ning: whereas in conventional systems all possible com­ binations of features and objects would have to be gen­ erated and stored as facts, our systems initiates the gen­ eration of a fact only when it is really needed in the reasoning process. In our present system, the four ele­ mentary spatial notions below, above, left-of, a.nd right­ of are built into the system via direction units, which control the direction gates for a specific flow of activa­ tion (see Figure 5). These notions are used to compose the spatial relations used in the language part.

In total, the system as presented here solves the prob­ lem of checking the correspondence between a. simple visual scene and a simple natural language characteriza­ tion of the spatial relations between objects in that scene. With a. moderate enhancement of the basic CHCL mech­ anism, it is possible to extract the necessary information from the analogue representation of the scene, without a necessity to generate an excessive amount of facts de­ scribing all its spatial aspects. The system is currently being implemented using IcsiM [Schmidt, 1990].

As for future work many open questions remain: How can the rules be learned? Can we train the system such that spanning sets leading to a proof are generated with a certain priority? What is the meaning of above, below, etc. and when do we call an object small rather than medium, ... ?