On the Efficient Classification of Data Structures by Neural Networks

1 Introduction

It is well-known that connectionist models are not only capable of dealing with static patterns, but also with sequential inputs. Real world, however, often proposes structured domains that can hardly be represented by simple sequences . For instance, there are cases in which the information can be framed naturally in graphs of variable size, and one may be interested in processing these structures as a whole, and not pay attention specifically to their nodes. The ability to classify these structured data is fundamental in a number of different applications such as medical and technical diagnoses, molecular biology and chemistry, automated reasoning, software engineering, geometrical and spatial reasoning, and pattern recognition. Neural networks for processing data structures have been proposed by Pollack [1990] and, recently, by Sperduti, Starita & Goller [1995], and by Sperduti & Starita [1997]. It has been shown that they can actually be used for classifying data structures by using an algorithm, referred to

Alessandro Sperduti

Dipartimento di Informatica U niversita di Pis a. Corso Italia., 40 56125 Pisa, Italy

as BPTS (backpropagation through structure), that extends naturally the time unfolding carried out by BPTT, in the case of sequences. It has also been pointed out that BPTS is significantly better suited for dealing with long-term dependencies than BPTT, because of its inherent unfolding through structures instead of simple lists, the data structure counterpart of sequences. As for any neural network learning algorithm, however, the efficiency of BPTS, may be seriously plagued by the presence of local minima in the associated error function. In the epilogue of the expanded edition of Perceptron, Minsky [1988] pointed out that

" as the field of connectionism becomes more mature, the quest for a general solution to all learning problems will evolve into an understanding of which types of learning processes are likely to work on which classes of learning problems. And this means that, past a certain point, we won't be able to get by with vacuous generalities about hill-climbing. We will really need to know a great deal more about the nature of those surfaces for each specific realm of problems that we want to solve."

In this paper, we analyze the efficiency of learning the membership of DOAGs (Directed Ordered Acyclic Graphs) in terms of local minima of the error surface by relying on the principle that their absence is a guarantee of efficient learning. We give a sufficient condition under which the error surface is local minima free. In particular, we define a topological index associated with a collection of DOAGs that make it possible to design the architecture so as to avoid local minima. The condition we give holds for any training set composed of graphs with symbolic nodes and a neural network capable of learning the assigned data.

2 Recurrent networks for processing of data structures

In this section, we review briefly the basic idea proposed in [Sperduti and Starita, 1997] concerning adaptive processing of data structures. In particular, we focus on the classification of DOAGs (Directed Ordered Acyclic Graphs) [Arbib and Given'on, 1968] and show that their membership can be learned from examples. The recurrent networks considered in this paper process data structures beginning from a fixed initial state. Each experiment £ involving data structures can conveniently be expressed by means of three entities: a learning environment C, (set of data used for learning) , a network N, and a cost index E.

· Learning Environment C,.

Instances in the learning domain are structured pieces of information described by annotated directed ordered acyclic graphs (DOAGs) . Here for a DOAG we mean a DAG S = {V, E} with vertex set V and edge set E, where for each vertex v E V a total order on the edges leaving from v is defined. Specifically, let 0 P ~ { q : ( vp, vq) E E} and Op ~ lOP! the outdegree of node vp , then the out-port function p( Op, q) returns the position of the edge ( vp, vq) in the total order defined on the edges leaving from vp . 1 Similarly, let Ip ~ {q: (vq, vp) E E}, and lp ~ !Ip! the indegree of node vp, then u (Ip , q) is the in-port function which returns the position of the edge ( vq, vp) in the total order defined on the edges leaving from vq.

We shall require the DOAG to possess a supersource, i.e. a vertex v. E V such that every vertex in V can be reached by a directed path starting from v, . The reasons for this requirement are related to the processing scheme that will be defined in the following. Note that if a DOAG does not possess a supersource, it is still possible to define a convention for adding an extra vertex v, (with a minimal number of outgoing edges), such that v . is a supersource for the expanded DOAG. The graphs we are considering are annotated by labels on vertices, where U/j denotes the label attached to vertex Vj of DOAG u,. In the following, depending on the context, we will use Ulj to refer either a vertex or the label attached to the vertex.

The learning environment is a collection of pairs composed of DOAGs with their own targets. Formally, let d- , d+ E R be such that [d-, d+] c [4, d] and define:

where U, E Su is a DOAG with corresponding target value d1 E { d-, d+}, and U1

1 An example of out-port function is simply PASCAL ord function which returns the position of a given element in an ordered set. For instance ({3, 6, 7, 11, 13}, 11)-+ 4.

{ ( U/p) Ulq ) : lllp) Ulq E nm}. The collection of DOAGs 1h ~ {U1 , ... , UL} will be also useful itself for analysis on graph topology. A topological sorting TI : [1, ... , Pl] -+ [1, ... , Pl] : k -+ Pk can be associated with any U, E Su such that V h, k : uPh -< Uq1 ~ Ph < q1c. Let PM = maxP1 and MpM be the space of all matrices in nm,Pr) being I ~ L. Using this sorting we can associate DOAGs with matrices as follows

where Uf = lllp denotes the p-th U1 's column. The learning environment c. can be partitioned into the following sets

which collect the positive and the negative structures of the learning environment, respectively.

· Network .N.

The network can be thought of as a triple .N "' {W , V r M } of weight matrices. W E nn,m+l is the input-neuron matrix which also incorporates biases. Note that, m is the number of input units, while n is the number of hidden units. V = {V 1 , ... , V o} are the pointer matrices that make it possible to extend the typical recurrent processing of sequences to data structures as put forward in the following. 0 is the maximum outdegree of all the nodes of the graphs belonging to C. and it represents a bound on the maximum number of pointer matrices, that is Vr = 1, ... 0, VT E nn,n.

For any graph U, we define the associated encoding network .N(U1) as a feedforward network created as follows (see Fig. 1):

1. The architecture of .N(Ul) is the DOAG inherited by U1 by simple inversion in the graph arrows.

1. Each vertex vp (p = 1, ... , P,) of the graph U, is associated with a corresponding layer p of n sigmoidal neurons.
2. The output of the neuron i in layer pis related to its activation a;1p as follows

where f(·) : R --+ [4, d] is a C 2 bijection such that V a;lp, f'(ailp) > 0.

1. The generic layer p of network .N(U,) receives connections from both the input Ulp and layers with index in OP . Specifically, the outputs from units in layers with index in Op are properly weighed by matrices V, according to the out­ port function r = p(Op, q), q E Op.
2. The computation carried out at layer p depends on matrices W and V according to:

being alp='= [allp····,anlp]', and u~P ='= [u;P,1]' the input, taking into account also an eventual bias term.

1. When feeding the network with graph u,, the output for each vertex vp is

where x~P ='= [x;P, 1]', takes into account also an eventual bias term.

Given a structure U, and the associated encoding network .N(U, ), the corresponding processing is carried out by the typical forward step of feedforward networks. Note that, apart from the architecture, which is inherited by the given DOAG, weight matrices W, V, and M are independent of the given graph. Hence, the computation defined by equations (5) can be carried out by means of a generalized recurrent network whose computation takes place in the pseuo-time space [1, ... , max1 P,]. LetT! be the topological sorting of graph U1 defining which node must be processed at pseudotime p E [1, ... , max, Pl]. The computation described by equation (5) can be considered as a recurrent computation at pseudo-time p, once the computation had already taken place Vq < p. The computation ends for p = s = P,; at that pseudo-time the supersource layer activations are computed and, finally, the DOAG's membership is given by (6) .

• Cost index.

Given the pair (.N, c.), the output-target data fitting is measured by means of the cost function

where

and " 1 " stands for differentiation with respect to a. This threshold-LMS error has been introduced by Sontag & Sussman [1989]. This cost does not penalize outputs "beyond" the target values 2 .

Let us introduce some more notation for gaining a compact vectorial of the gradient of the cost.

2 It can be proven that the choice of this type of functions makes it possible to avoid the spurious local minima arising when choosing non-a9'mptotical values for the targets, th~t when [r,d+J c [.4,d), that is r :j: 4 and (or) d+ :j: d. This kind of spurious local minima were shown in [Brady et a/., 1989], while Sontag & Sussman [1989] proved that they disappear when choosing threshold-LMS functions. Gori & Tesi [1992] proved that no such spurious local minima arise when [r, d+] C [4, d] .

1. U ::::: [U 1, · · · , U L] E Rm,P" collects the topological sorting of all the given data structures, where P* ::::: 2:,~= 1 P1. Similarly, for each graph U1, the outputs of the hidden units can be collected in matrix XI = [xl ,l' . .. , Xi ,P,] E nn,P, and, for all the graphs, matrix X = [X1' ... 'XL] E nn,P" is used for keeping the hidden output trace.
2. Let us define Yilp ::::: aEjaa;lp · For node p of a given DOAG U1, the corresponding delta error Yilp can be collected in vector Yip = [Yllp, .. . , Ynlp ]' and the contributions from all the graph's nodes can be collected in matrix Y1 = [YI ,1, .. . , Yi ,P 1 ] E R"·P'. Finally, Y ::::: (Y 1 , ... , YL] E nn,P" contains the delta errors for all the graphs of the learning environment, while the delta error corresponding with the output unit is denoted by 3 Yh ::::: 8 8 E . a,,

The gradient. of the cost. can be calculated by using Backpropagation in each encoding network (see e.g. Fig. 1) , that is by propagating the error through the given structure, instead of through time, as typically happens for recurrent networks processing sequences. The gradient of the cost can be written in a compact form by using the vectorial notation Gw ::::: [ 8~~ 1 ] E 'R."'·" and V;· E [1, ... , 0] : Gv ::::: [a 8 E_ ] E . r v,Jr 'R."·". Based on these definitions, Gw and Gvr can be computed a.s follows

where ~(p, 1·) is the r-t.h vertex pointed by Vp, Gw,l, Gvr,l are the gradient contributions corresponding to E1, that is to DOAG I. The gradient coordinates are denoted by Gw,i ,j ,l and G vr,i,j,/, respectively. The delta-error Yilp can be computed recursively according to BPTS:

These equations represent a vectorial form of Back-Propagation Through Structure (BPTS) gradient computational scheme [Sperduti and Starita, 1997].

3 Note .the difference between Yls and Yl s· While Yls E R is the delta error associated with the output unit, Yl · E R n is the delta error corresponding to the supersource layer.

The analysis proposed in this paper is based on the implicit assumption there exists at least one set of weights for which E = 0, that is we assume that all the DOAGs of the learning environment can be classified correctly.

3 A bound on the hidden units for efficient learning

In this section we study the role of graph topology regardless of the information attached to the nodes. This is harder than studying the case which there are also significant labels attached to the nodes, which are likely to simplify the learning process .

Definition 1 Given DOA Gs collection DL, let U L ::::: {ulp : p = 1, .. . , P1; I= 1, ... , L} be the corresponding set of nodes obtained when using a topological sorting T,. We define relation txt C VL x VL as follows:

where DOAG(u) denotes the DOAG having node u as a supersource.

Definition 2 Given DOA Gs collection D L , consider quotient set U £/...,. The number D L 11' ::::: I U L/..., I is referred to as the power pointer of DL .

Theorem 1 Given E "' { .Ce, N, E(-)}, assume that there exists at least a solution with E = 0. Then, function E(-) has no local minima different from E = 0, provided that DL 1f ~ n.

Proof: see the Appendix A. D Note that DL 11' ~ n forces to use neural metworks with at least as many hidden units as DOAGs to learn, since DL 11' ~ L. A special interesting case is that in which DL 11' ~ L. This holds for all those DOAGs with structure indicated in the following definition.

Definition 3 A set of DOAGs 1h is a Chinese box provided that 'V Ut E Su, 3ut, Ut 1 , ··· , Ut k : Ut = { ( Ut , Ut l ) , .·· , ( Ut, Ut k ) , Utp ... , Ut k } ·

Corollary 1 Let VL be a Chinese box, with associated learning environment £., and N a generalized recurrent network such that there exists at least a solution with E = 0. If n 2:1 £. I= L then error function E(·) has no local minima different from E = 0.

Proof: Trivial , since for Chinese boxes VL it= L . Example 1 Consider the problem of classifying DOAGs depending the their outdegree. Positive DOAGs are those with outdegree less than three (see Fig 3). It can can easily be checked that

Hence, V L it = 8. Because of Theorem 1, we conclude that when using a neural network with n = 8 hidden units, the given training set gives rise to an error function with no local minima.

Example 2 Consider problem of classifying DOAGs depending the presence of a common sub-graph and assume, in particu.l.e,r, that positive DOAGs are those containing subgraph {(A, B) , (B, C), (A, C)} (see Fig. 4) . It can can easily be checked that

Hence, VL it= 9, which means that can surely get rid of local minima when using neural networks with 9 hidden units .

Example 3 Consider the problem of learning the concept of perfect binary tree from the examples shown in Fig. 5. It can easily be proven that the given learning environment is a Chinese box and, therefore, according to Corollary 1, a network with 8 hidden units ensures that there are no local minima.

4 Conclusions

In this paper we have proven that if we use as many hidden units as the pointer power of the given collection of DOAGs, any problem of learning their classification can be solved with a unimodal error function. Moreover , in the special case of Chinese boxes, the pointer power reduces to the cardinality of the given training set . The given bound on the number of hidden units that are needed to avoid local minima, however, is not necessarily useful for the network design, since our condition is not related to generalization issues. The given bound, however , seems to be very interesting from a theoretical point of vie.w, especially when compared with related results given for multilayer networks [Poston et al. , 1991; Yu, 1992].

Appendix

Proof: Sketch 4 - Theorem 1 According to the hypothesis, when using 1><1 , we can reduce VL to VL/t>d and, because of the defined computation scheme, all DOAG(utp) : Utp E ut>d(P) E

~The basic idea of the proof is somewhat related to Poston et . a/'s [Poston eta/., 1991] and Yu's [Yu, 1992], for the case of multilayer perceptrons . L. Harney [Harney, 1994] pointed out that Poston et a/. proof was not complete and that Yu's proof contained a flaw. Yu and Chen [Yu and Chen, 1995], however, have recently proven that the flaw pointed out by Harney can be fixed up and that the claimed result holds.

1h/r>d give rise to the same pointers on the network hidden layer. Let X= [xl, ... 'XDdtl E nn,Ddt be the matrix of different pointers and Dp ='= {l: urp E tir><j(p)}. Equation (9) for the gradient w.r.t a generic matrix V, can be re-organized to a sum with 'DL 1't different terms only, that is

where

and y _:_ [Yl· ... , YDdtl E nn.,Ddt. Since n ~ 'DL 1'1', matrix X is full rank with P = 1. Now, the proof can be given separately in the cases in which rank X = 'DL 1't and rank X < 'DL 1't.

1. rank X = 'DL 1't.

Under this condition, because of (1~, the condition for critical points Gv, = 0 yields Y = 0. Now we have two different cases for graphs in 'DL

• (a) Ur : ur. E tir><j(p) and ltir><j(p) I= 1. In this case Yls = 0 ==::} Yls = 0, which, because of BPTS equations (10) yields Er = 0, in the case of m; i=- 0 (if m; i=- 0, see the singular case (2)).
• (b) Ur : ur. E tir><j(p) and ltir><j(p) I> 1.
• Also in this case, we can prove that Yr. = 0.

Consider the generic condition that can be derived from (13), that is Ypp = L:rED, Yip = 0. We can remove all terms Yr. in (14), for which Yrs = 0 were already proven in (1a) and, for the correspondent graphs we have Yr. = 0, which, in turn, yields Er = 0. Let 'DF be the set of graphs whose terms in (14) were removed. All other graphs in 'DL \ 'DF are necessarily subgraphs of elements in 'DF. For any Ur E 'D L \ 'D F consider the corresponding encoding network of a graph U>., such that Ur is a su bgraph of U >. E 'D F. According to the analysis carried in (1a) we derive that Y>.· = 0. Since Ur is a subgraph of U>., we can always find a node uPm : DOAG(u>. ,pm) = Ur. According to the BPTS equations (11), when following a path connecting s to Pm we derive that Y>.,pm = 0. If matrices V, are full rank, then Yrs = 0 and, finally, Er = 0.

2. rank X < 'DL 1't

Under this assumption, there is the possibility that Vr Gv, = 0 <¢=::: Y i=- 0. Now we prove that the corresponding configuration cannot be a local minimum for E(· ). Assume, by contradiction, that configuration {W0 , V0 , Mo} is a local minimum. Since X = n ·holds with P = 1, there would be infinite global minima (E = 0) in the neighborhood of {W0 , V0 ,M0 }, which is not consistent with the assumption that E(·) is a continuous function 5 .