A Framework for Network Modeling in Prolog

1. Introduction

Graph models are commonly used in AI. Their expressive power makes them suitable in almost a 11 AI fields. How ever, in the framework of Prolog programming graph algo­ rithms have a restricted meaning of graph searching techniques. Searching graphs is a fundamental technique for solving many AI problems as state-space represented problems, game p layi ng, planning etc . However, the re are other opera tions on graphs not less useful in the context of AI. Such are for example graph isomorphism (graph matching) and constraint satisfying (constraint propagation). Graph models can be vi ewe d mor e g en era lly a s n etw or k models, such as neural networks, knowledge representing networks (semantic networks, frames) and many other distributed computational models grouped a round the term connectionism.

The present paper deals with a graph model of a etas s of visual objects polyhedra . The Prolog implementation of the problem inspired a new concept for repre­ senting graphs and networks. The proposed representation scheme requires some exten­ sions of the standard Prolog mechanisms, which are introduced in an experimental version of the language developed by the author.

2. Attributed graph represen­ tation of polyhedra

The polyhedra are a large class of graphical objects frequently used in geometric model­ ing and vision. They can be used for model­ ing curved objects as well by approximation. This class is suitable for object recognition since there exist well developed methods for extracting linear features from real images. This aspect of the problem is discussed in [Engelbrecht and Wahl, 1986]. The Prolog based approach for polyhedron recognition is described in [Markov and Risse, 1988]. In the field of CAD the class of polyhedral ob­ jects is used for the 3-D interpretation of 2-D sketches. This problem is recently con­ sidered in the framework of network models, which we discuss in the next sections. Here we outline only the basic ideas concerning polyhedral modeling in Prolog, which are used later for building an altemative net­ work model of the same problem domain.

A polyhedron can be considered as a structured collection of its parts - vertices and edges. For example a four-side figure can be expressed in Prolog by the list

[edge(1,2),edge(2,3),edge(3,4 ),edge( 4 ,1)], where the structure edg e(M,N) represents an edge connecting the vertices M and N. The above list represents a too large class of geometric figures. To obtain a sub-class (e.g. parallelogram, rhombus etc.) we should introduce more geometrical information. In our model this means some constraints i.e.

attributes attached to each edge . For this purpose the following form of the edges can be used:

edge(Vl, V2,Slope ,Length)

Using this notation a parallelogram can be

represented as:

[ edge(1,2,0,20),edge(2,3,30,50), cdgc(3,4,0,20),edge(4,1,30,50) ]

The edges of the above figure are separated in 2 groups, distinguished by their slopes ­ and lengths. These groups are implicitly defined by edge attributes having equa 1 values, which we call same-valued classes. A very important feature of this representa­ tion scheme is the possibility to define a class of such figures, using variables in­ stead of fixed names or values standing for the vertex names and attributes. The above shown list representing an instance of a parallelogram can be transformed in the fol­ lowing form:

[ edge(A,B,Sl,Ll),edge(B,C,S2,L2), edge(C,D,Sl,Ll),edge(D,E,S2,L2) ]

In this list the equal names or values are replaced by shared variables. Using vari­ ables as arc attributes ensures that the class representation is free of any specific geometric properties as size, orientation, etc . The only fact taken into account is the equality or in equality of the attributes, and this is provided by the built- in Proto g unification mechanism. The real values of the attributes can be of any type and measurement units. Si nee parallelism and same length are properties, preserved by the parallel projection, this class representation can be used for 3-D polyhedra.

Our aim now is using the described repre­ sentation scheme to de fine a procedure , which can check whet her an in stance belongs to a certain class. In the graph ter­ minology this is called graph isomorphism or graph match in g. We propose a graph matching procedure based on the following idea: a graph is a subgraph of another graph, if and only if the set of all arcs of the first graph is a subset of all arcs of the second graph. During the subset opera­ tion the variables, representing the class nodes and attributes are successively in­ stantiated to the corresponding instance nodes and attributes. Then the consistency of these ins.tantiations is checked and pos­ si bly ba ckt ra cki ng oc curs. The wh ol e process is hidden in the recursion used in the definition of the predi cate match , which is a slight modification of the predicate subset, described in [Clocksin and Mellish, 1981].

match([A I X],Y):-member(A,Y),match(X,Y). match(0._):-1.

member(edge(X,Y,S,L),[edge(X,Y,S,L) I ]). member(edge(X,Y ,S,L),[edge(Y ,X,S,L) 1_]). member(X,[_ I T]):-member(X, T).

The pure subgraph matching problem is NP-complete. However, in some cases a proper representation may be found to make the graph matching algorithm applicable in practi ce. The aim is to minimize the num­ ber of the backtracking steps occurring in the "bad" ordering combinations obtained enumerating the graph arcs. In our case the use of attributes in the graph improves the efficiency as it is shown in [Markov and Risse, 1988]. However, there is a "second­ order" problem, which appears in practice where more than one class is used. The overall efficiency in such a case depends very much on the order of the selected classes to be recognized, since a possible matching between the instance and each one of the classes is tested sequentially. A solution of this problem can be found in matching the instance against all classes simultaneously. Such a scheme is proposed in the next section.

3. Database representation of attributed graphs

As we mentioned in the previous section the problem of the different ordering combina­ tions of the edges in the class and in the instance is solved by involving set opera­ tions. Besides the lists, the Prolog database is also suitable for storing set elements. An element belongs to such a set if its activa­ tion as a goal succeeds. Thus a subset operation is just an execution of a conjunc­ tion of goals. For example the following program checks whether an instance of a rhombus belongs to the class of all rhom­

buses.

1· An instance of a rhombus ·1 edge(1,2,0,100).

edge(2,3,45,100).

edge(3,4,0,100).

edge(4,1,45,100).

1· The class of all rhombuses ·1 ?- edge(A,B,Sl,L),edge(B,C,S2,L), edge(C,D,Sl,L),edge(D,A,S2,L).

The above scheme is much more efficient than the corresponding subset operation on lists, since two Pro log built-in mechanisms are directly used database access and backtracking. How ever, it is impossible using this representation to check a sub­ graph to graph isomorphism (with missed edges in the instance, e.g. hidden edges in a rea 1 image). That is a su bst ant ia 1 shortage, which makes this approach inap­ propriate for our model. To avoid that we introduce an extension of Prolog, which al­ to ws shared variables among different clauses in the database.

The proposed extension, which we call "net-clause", is syntactically a Prolog struc­ ture with the functor ":" and arguments normal clauses. The clauses contained in a net-clause form a special domain in the Prolog database, which has the same seman­ tic as the normal Prolog clauses, taking into account the special behavior of the vari­ ables contained.

A natural semantic interpretation of the proposed net-clause is a network, where the nodes are represented by clauses and the connections - by shared variables. The nodes can be used as processing units and the connections - as channels for informa­ tion transfer. This interpretation is our basic paradigm, which will be elaborated further in the paper.

The features of the net-clause variables are used to improve the attributed graph model of polyhedra. Besides for representing the topology and geometric constraints shared variables are used to represent the part-of hierarchy between the vertices and the objects they constitute, so that after a successful matching of an instance, the in­ stantiated variables (vertices) indicate the corresponding class, where they belong. The network illustrating this idea is shown in Figure 1.

The following program implements the net­ work from Figure 1. (The use of a special Prolog extension, ensuring all different vari­ ables to be bound to different objects, is essential in this example. Such an extension is also available in Prolog III.)

1· Edges of the figures ·1

edge(A,B,Sl,Ll ):

edge(B,C,S2,Ll):

edge(C,D,Sl,Ll):

edge(D,A,S2,Ll):

edge(B,E,S2,L2):

edge(E,F ,Sl,Ll ):

edge(F ,A,S2,L2):

edge(E,G,S3,L3):

edge(G,A,S4,L4):

1· Classes of figures ·! class{four_side_figure,A,B,E,G): class(parallelogram,A,B,E,F): class(rhombus,A,B,C,D).

1· Network activation ·1

• ?- edge(1,2,0,20),edge(2,3,45,30), edge(3,4,0,20),edge( 4,1,45,30), class(Name,X, Y ,Z,P),nonvar(X), nonvar(Y),nonvar(Z),nonvar(P).

N ame=parallelogram The network from Figure 1 has a shortage inherited from the static behavior of described model. Let us explain this. The facts edge can be considered as inputs and class - as outputs of the network. To obtain an answer we should activate both the in­ puts and the outputs (call them as goals, specifying the input/output values as arguments). This scheme is good as long as we know the outputs previously. But that is not the case in our example. We enter a pattem (the instance) and then scan all possible classes to find which one is matched. In other words if we have many outputs in the network we should check all of them to find which one is active.

To make the net-clause network more dynamic we extend the semantics of the clauses to local processing units, which are activated on certain conditions. In terms of Prolog this means the possibility to activate the goals in the body of the clauses. At the normal Prolog computation a clause is ac­ tivated when the current goal unifies its head. In our case there is no current goal, instead there are instantiated variables and we can use them as an indication that some processing unit has enough information to do its work. So, we define the following a c­ tivati on rule: a clause body is activated when the clause head is "enough" instan­ tiated. The quantitative measure of the clause head instantiation is the number of its uninstantiated variables - arguments.

An implementation of the above idea is the built-in predicate ac tivate(N ), supported by our experimental Prolog version. It ac­ tivates all clause bodies, whose heads have less than N uninstantiated variables - argu­ ments. In this way the variables in the head of a clause can be viewed as activating links. We introduce also inhibitory links, represented syntactically as unary minus fol­ lowed by the variable name, e.g. -x. Such links are interpreted by the activation pro­ cedure as a negation of the instantiation condition, i.e. if X is instantiated, -x is treated as an uninstantiated variable and vice versa.

The best suited computational scheme for the outlined network model is the parallel one. Since we could not avoid the sequen­ tial activation of the clauses we simulate the functional behavior of a parallel execu­ tion based on the following features:

• (a) Multiple scanni ng the net-clause database and executing each time a 11 ac­ tive clauses, so that each clause is ex­ ecuted successfully just once. This scheme ensures a special activation order guided only by the activation rule
• (b) Delaying the execution of the active clauses which have failed. This rule is based on the assumption that an active clause may fail due to some conditions in the network, not present at the current pass through the net-clause database. That is a way to synchronize the work of the hidden network units or to organize switching be­ tween branches of the network. Functionally the same effect could be reached using in­ hibitory links. In fact the two mechanisms reflect the two paradigms - logic program­ ming and network modeling, integrated in the proposed formalism.
• (c) According to (a) and (b) the clauses are checked which satisfy repeatedly and those of them the activation condition are process terminates when no instantiations have been pass through the net-clause executed. This more variable done during a database.
• (d) Executi ng all active clauses in a common environment. This feature of the activation procedure is very important, since it ensures that all newly established con­ nections between the clauses (variable in­ stantiations) are kept until all active local procedures in all units of the network are executed.

Using the newly defined predicate ac­ tivate, the program representing the network for recognition of planar figures, shown in Figure 1 can be modified by replacing the facts class with the following clauses:

four_ side_ figure( A ,B ,E, G):- parallelogram(A ,B ,E,F):­ write('parallelogram matched'): rhombus(A,B,C,D):-

write( 'four_ side_ figure matched'): write('rhombus matched'). Now initiating the network by the question

?- edge(1,2,0,20),edge(2,3,45,30), edge(3,4 ,0,20),edge( 4 ,1,45,30), activate(O).

parallelogram matched we obtain as an answer the name of the class, which the entered pattern belongs to.

In the 3-D polyhedral model the instance may contain less edges than the class (e.g. hidden edges). In this case the activate predicate should be used with an argument greater than 0, allowing in such a way "fuzzy" matching.

The above examples are in fact one-layer network models where the local processing capabilities of the network are not used. This is because the patterns to be recog­ nized are quite simple. The basic properties of the characteristics specifying them are only two - equality and inequality. However there are some geometric properties, which can not be expressed in terms of equality and inequality. For example such a property is the perpendicularity of edges. To check it some calculations are required, which can be performed by intermediate nodes (hidden units) in the network. Using the edge facts from Figure 1 and adding the following clause s we obtain an capable to recognize squares too. extended network , r ect ang ul ars an d

1· General case of four-side figures ·1 four_side_figure(A,B,E,G):-

write( 'four_ side_ figure matched'):

1· Calculating perpendicularity ·1 perpendicular(Sl,S2):-Done=ok,

(0 is (Sl-52) mod 90, P=ok;true):

1· Non-perpendicular figures ·1 parallelogram(A,B,E,F,Done,""'P):­

write('parallelogram matched'): rhombus(A,B,C,D,Done,""'P):­

write('rhombus matched'):

1· Figures with perpendicular edges ·/ rectangular(A,B,E,F ,P):­

write('rectangular matched'): square(A,B,C,D,P):- write('square matched').

The clauses re presenting the classes of parallelogram and rhombus are modified ac­ cording to the use of the hidden unit per­ pendic ular. They become candidates for ac­ tivation only after the check for perpen­ dicularity has been done (the variable Done is instantiated). This check actually distin­ guishes the two groups of classes - with and without perpendicular edges, indicated by the variable P, which is used respec­ tively as an activating or an inhibitory link.

4. Connectionism in Prolog

The described results in network modeling in Prolog may be naturally discussed tn the more general framework of connectionism. That is a field focusing a growing interest, characterized mainly by the quite old idea that hard problems could be solved intercon­ necting simpl e processing units . Connec­ tionism may be characterized by several fea­ tures [Arbib, 1987], which we discuss in connection with the features of our network, described in the previous section.

• (a) The use of networks of active com­ puting elements, with programs residing in the structure of interconnections. The active computing units in our model are the clauses, activated cin certain conditions or unconditionally. The procedure specifying the way the patterns are processed (matched) actually resides in the structure of shared variables (i.e. the structure of interconnec­ tions) representing the topology and the geometry of the polyhedra.
• (b) Massive parallelism, with no central­ ized control. The proposed here network for­ malism is implemented in a sequential com­ putational e nv ironment. However it is designed in such a way that the sequential implementation affects minimally the network properties. Although the processing of the entered in the network pattern is based on backtracking, this process is hidden and the result does not depend on the order of the subgoals specifying the pattern. Thus the process of setting up the inputs/outputs of the network can be viewed actually as a parallel one and the one-layer models without hidden units can be considered parallel too.

The features of the activation rule, described in the previous section are in a sense steps toward simulating parallelism in multi-layer networks. The functional be­ havior of a parallel computation is fully reached when the network satisfies two quite natural requirements:

1. The execution of the active clauses has no "side effects" (in Prolog terminology);

1. The network is consistent. Clauses, which "undo" what have been done by other clauses, and never-fulfilled conditions may be considered as network inconsistencies.

The d esc ri bed network co mp uta tiona 1 scheme can be viewed in the framework of the parallel computation as one without centralized control and synchronization. Ac­ t u a 11 y t h i s i s a " s ha r e d m e m o r y architecture", where the role of the common memory is played by the shared variables in the net-clause.

• (c) The encoding network semantics either by single network units (localized representation) or by patterns of activity in a population of such units (distributed representation). The use of the two repre­ sentations is essential in the described ex­ ample of a polyhedron recognition network. The semantics of the classes is locally rep­ resented by some of the network nodes and the patterns representing the class charac­ teristics are distributed in the interconnec­ tions of the network. As it is mentioned in [Arbib, 1987] the distributed representation is based on the principle "letting the fea­ tures fall where they may", which actually is the main principle of the polyhedron recognition network too.

5. Conclusion

The aim of the present paper is to outline the basic concepts of using Prolog as a framework for building . network models. For lack of space we have skipped the im­ plementation details, though they are critical for the applicability of the proposed for­ malism in practice. In fact the only source of inefficiency could be the activate predi ­ cate, which involves some notion of a second-order 1 ogic ignoring the c taus e functors as an access rule. However the ac­ tivation rule ensures that only the clauses, which could do some "useful" work are ac­ tivated, and all others are simply skipped. Thus, formally speaking the effectiveness of the net-clause network and a normal Prolog program must be the same, as in both cases only the "useful" clauses are executed (of course, if both models are "enough" adequate to the problem domain).

The network programming in Prolog could be a feasible tool for some applications as vision (e.g. polyhedron recognition, 3D in­ terpretation of 2D sketches etc.), semantic networks, production systems and other schemes for knowledge representation, and natural language processing.

Further research in the above-listed fields of application needs at first deepening of the proposed form a lis m, which we see focused toward the following topics:

• (a) Extending the functionality of the con­ nections allowing not only equality and ine­ quality to be propagated through the shared variables, but some calculations to be per­ formed during the unification (solving equa­ tions, constraint satisfying etc.). This means transferring some of the hidden unit seman­ tics to the network links.
• (b) Using other activation schemes, e.g. activation by need (when a variable instan­ tiation is required by a processing unit, the eta use , capable to ins tan ti ate it, is activated).
• (c) Developing learning procedures suited to the proposed network representation.

Acknowledgments

I owe special thanks to L. Sinapova for her support in preparing the paper. I am also grateful to D.Dochev and G.Agre for the help­ ful discussions about network modeling in Pro log.