Problems with Parts

1. Introduction

Much of our knowledge of enduring relation­ ships (as opposed to events) concerns relation­ ships among parts of physical and abstract objects. Yet part-whole relationships have until recently received scant attention in the AI literature, compared for example to generalization (IS-A) relationships. Interest in parts structure has been confined almost exclusively to its role in reLational models for computer vision (e.g., [1-5]). However, the ability to reason about parts was an important feature of Raphael's pro­ gram SIR[6]. It was able to chain together both particular and generic subpart relationships, and to combine parts inference with subset in­ ference to answer questions about (sets of) parts of (sets of) individuals. The "slots" of Minsky's frames [7] rna~ facilitate the representation of part-whole relationships, among others, but do not presuppose any particular theory of such re­ lationships. To date, the most elaborate propo­ sals for representing and reasoning about parts structure appear to be those of Philip Hayes [8,9].

* The work reported was done while the author was on leave at Universitat Karlsruhe, Institut fur Informatik I, W. Germany

The present paper addresses two problems in the use of parts knowledge which people find tri­ vially easy but which have not been adequately mechanized: the extraction of "part-of" relation­ ships (and disjointness relationships, etc.) from overlapping parts hierarchies, and relation - ship inheritance for parts of objects in a type hierarchy.

Sec. 2 introduces a convenient representation for sets of partitioning assertions, called "parts graphs". Although based on parti tionings, parts graphs can represent non-exhaustive and overlapping decompositions of parts structure.

Sec. 3 notes that label-propagation methods for extracting "part-of" (and other) relation­ ships from simple partitioning hierarchies do not generalize to arbitrary parts graphs; the problem is in general NP-complete. A restricted type of parts graph, called "closed", is de­ fined, which reduces all parts of the top-level object to a common set of pairwise disjoint ul­ timate (lowest-level) parts. For closed parts graphs, efficient complete inference methods can be supplied.

In Sec. 4 a relationship inheritance scheme is proposed in which corresponding parts of con­ cepts in a type hierarchy are identifiable by the names of their Skolem functions. This over­ comes a difficulty with Hayes' [8,9] property inheritance scheme, without sacrificing any of its advantages.

2. Parts graphs

The following takes for granted a notion of "part-of" which is at least a partial orde­ ring with the extension property (if all parts of x are part of y, then x is part of y), and for which there exists a unique empty part e, a dyadic "overlap" function n (the largest entity which is part of both arguments) , an n-adic "merge" function U , n=2, 3,... (the smallest entity which has all of its arguments as parts), and a dyadic "remainder" function ' (the part of the first argument which is not part of the second). These properties are stated formally in .. [ 10} · . Bunt 1 s [ 11 l a:xiomatizati<im of "partof" satisfies these constraints and leads to a logically consistent generalization of Zermelo­ Fraenkel .:,et theory. Thus the theories of "part­ of" and "subset-of" are closely related, and much of what is said here about the representa­ tion and use of parts knowledge also applies to the representation and use of knowledge about set inclusion relationships.

People tend to conceptualize objects in terms of pairwise disjoint, jointly exhaustive parts, i.e., in terms of partitionings. For example, the top level of a human parts hierarchy might reasonably divide the human body x into a head h, neck n, torso t, arms a&a 1 , and legs 1&1 1 · Thus it is natural to base computer representa­ tions of parts structure on a partioning rela­ tion P,1 where [x P x1 .·· xml iff

Thus (Vx) (3hntaa I 11 I)[ rx human] ... [[x Ph n ··· l 1 ]&[h head1&[n neckl& ··· &[l 1 leq].

It is important to notice that "part-of" is expressible in terms of P. For example, [b part­ of a] can be rewritten as [a P b c], where cis a previously unused constant denoting ('- a b) , i.e., the (possibly empty) remainder of a with respect to b. In general, arbitrary sets of "part-of" assertions and disjointness assertions can be converted to sets of partitioning assertions. However, the conversion may intro­ duce parts wich are possibly empty, even if all of the original parts are known to be nonempty.

1 cf. the partitionings of Grossman [12] and "complete splits" of Fahlman [ 13] for concept taxo­ nomies.

2In the form of predicate calculus used here sen­ tential formulas are in infix form and deli~ited by square brackets (so that the second list ele­ ment is the predicator or operator) and function­ al expressions are in prefix form and delimited by round brackets; e.g., (Vxy)[[x =(mother-of y)l ... [x female]].

Sets of partitioning assertions can be repre­ semted as "parts graphs" as illustrated in Fig.l.

This shows two overlapping parts hierarchies for a particular (as opposed to generic) lamp, with a "structural view" on the left and a "functio­ nal view" on the right.

In the graphical representation, partitioning assertions and particular parts are represented as assertion nodes and constant nodes respecti­ vely. Assertion nodes are marked "P" and have an incoming edge from the first argument of the assertion and outgoing edges to the remaining arguments. Such parts graphs are readily repre­ sented as semantic nets in the network formalism of [ 14].

Hierarchies are distinguishedfrom unrestricted parts graphs by having exactly one downward edge from each nonleaf parts node and a unique path from the root to each parts node. As Fig.1 shows, the available knowledge about an object need not form a single hierarchy. "Tangled" hierarchies result when there are multiple views of the same object, known overlap regions such as shoulders, waist, or knees, or parts with unknown mutual overlap.

3. Extracting information from parts graphs

A partitioning hierarchy has the important advantage of allowing efficient inference of part-of and disjointness relationships. In fact, if a and b are any two nonempty parts appearing in a hierarchy, then b is part of a iff a is an ancestor of b, and a and b are disjoint iff neither is an ancestor of the other. 3

For parts within a common subhierarchy of a non-hierarchic parts graph the same methods can be used. For example, in Fig.1 the plug must be part of the electrical system since the latter is an ancestor of the former in the "functional view" of the la!!i>; the cord is disjoint from the bulb since neither is an ancestor of the other in the "structural view".

3 Incidentally, these conditions can be checked in constant time usin~ a method based on left-to­ right numbering of the leaves, whereas the worat­ case complexity of label-propagation methods is inear in the number of edges.

However, not all implicit part-of and dis­ jointness relationships can be extracted in this way. In Fig.1, the switch must be part of the stand; in fact, the switch and support structure must partition the stand, because the stand on the one hand and the switch plus support struc­ ture on the other are the only nonoverlapping parts of the two lamp hierarchies. Another point worth noting is that even without the assertion [lamp P stand top cord], it follows from the graph that "top" is part of the lamp, be­ cause all of its parts are.

One can devise additional inference methods to handle these particular cases, but such stop­ gap measures are almost surely futile because of the following result.

Theorem 1. The problem of confirming [b part-of al, where a and bare nodes of a parts graph, is NP-complete.

This is proved in [10] by mapping the unsatis­ fiability problem of the propositional calculus into a "part-of" problem for a parts graph, and vice versa.

This suggests that additional constraints should be i!!i>osed on parts graphs so as to per­ mit efficient information extraction, while still allowing for overlap parts and multiple views of the same part. Such constraints are obtained by requiring parts graphs to be closed: G is closed iff any two of its parts nodes are projectible into a common subhierarchy. A node a is projectible into a subhierarchy H if G con­ tains a subhierarchy rooted at a whose leaves lie in H. (Since a single parts node is a sub­ hierarchy, any parts node is trivially projecti­ ble into any subhierarchy to which it belongs. Hence any two nodes of a subhierarchy H are pro­ jectible into a common subhierarchy, viz.,H).

For example, if the left and right views of the lamp in Fig.1 are called HL and HR, then "top" and "bulb" are projectible into ~ (be­ cause they belong to H ) , and "top" and "elec­ trical system" are pro~ectible into HR (be«:ause the leaves {lamp shade, socket, bulb} of a sub­ hierarchy rooted at "top", as well as "electri­ cal system", belong to HR). However, neither "stand" and "switch", nor "stand" and "support structure" are projectible into any common sub­ hierarchy. Thus the graph is open, but could easily be closed by addition of the assertion [stand P switch support-structure].

The notion of a closed graph becomes clearer if parts graphs are required to be "'fully con­ sistent" in the sense that none of the parts they represent are necessarily elli>ty. This rules out graphs, for example, in which two disjoint parts (distinct leaves of a single subhie'rarchy) have a common descendant, or in which one "view" of a part terminates in a proper subset of the leaves of another "view" of that part.

It is proved in [ 10] that all leaf nodes of a fully consistent, closed graph belong to a single (not necessarily unique) main hierarchy whose root represents the whole entity. All nodes of the graph are projectible into this main hierarchy. In such a graph, therefore, all leaves are pairwise disjoint and each parts node corresponds to a subset of the leaves. The graph of Fig.1 is now easily seen to be open, since the leaf nodes "stand" and "switch", for example, do not belong to any common subhierarchy.

Fig.2 shows a closed graph with a main hierar­ chy rooted at a, an overlap part b made up of two parts occurring in the main hierarchy, and two "views" of a part c.

Fig. 2. A closed parts graph with an "overlap part" b and two "views" of a part c. The darkened nodes represent the ultimate parts of a.

Surprisingly, the syntactical restrictions of closed graphs do not lead to any logical re­ strictions:

Theorem 2. For every parts graph there is a lo­ gically equivalent closed graph.

The proof and a procedure for constructing a closed graph from a set of partitioning assertions are given in [10]. The sort of idea involved is illustrated in Fig.~ Admittedly, the size of the equivalent closed graph may be ex­ ponential in the size of a given open graph. However, this exponential growth is associated with unknown and unrestricted overlap between sets of parts, a situation which rarely, if ever, occurs in our conception of real objects.

The following methods are complete for ans­ wering questions of the form ?[b part-of a] and ?[a disjoint-from b) in fully consistent, closed graphs. Projecting a node a into a hierarchy H means determining a set of nodes A= {a 1 , ··· ,~} which lie in H and are the leaves of a subhierar­ chy with root a (if a already lies in H then A = {a}).

Preliminary step: Project a and b into a common subhierarchy H, obtaining respective projections A= {a1, ··· ,am} and B = {b 1 , · ·· bn}.

To answer ?[b part-of a]: If every node with an ancestor in B has an ance~tor or descendant in A, return "yes"; if some nodes with ancestors in B have no ancestors and no descendants in A, and the merge of these nodes is known to be non­ empty, return "no"; else return "unknown" (see Fig.4)

To answer ?[a disjoint-from b): If no aiEA has an ancestor in B and no bjEB has an ancestor in A, return "yes"; if some nodes in A have an an­ cestor in B and/or some nodes in B have an an­ cestor in A, and the merge of these nodes is known to be nonempty, return "no"; else return "unknown" (see Fig.S).

In [10] the completeness claim is made precise and proved. It is assumed that the merge of a set of nodes A= {a1, ·.· ,~} is known to be nonempty iff[(U al···aml F eJ is a logical consequence of the graph, the assumed properties of "part-of", and a set of "nonemptiness assertions" of the form [a = eJ about some of the nodes of the graph. It is shown that the predicate "known to be nonempty" is efficiently decidable when so defined. The given question-answering methods are then shown to be im­ plementable in linear space-time relative to the number of edges of the closed graph. Heuristic methods are discussed which can often give nearly constant question-answering times for closed graphs.

Similar methods can be used to compute the "disjoint merge" of two parts, i.e., a set of dis­ joint parts whose merge equals the merge of the given parts (retain elements of AUB which do not have ancestors in B) , the overlap of two parts (retain elements of A with ancestors in B and vice versa), and other functions over tuples of parts. Thus questions involving such functions could also be answered.

Needless to say, reasoning about parts cannot in general go very far on the basis of "part-of" predications or partitionings alone. In the case of physical objects, for example, knowledge about the mode of connection and relative position of parts is indispensable. But the fact remains that people can answer questions such as "Is a toe part of a leg?" or "Is a spark plug part of an automo­ bile engine?" with consummate ease. The proposed methods may help to equip machines wl th comparable abilities.

One serious limitation of the proposals is that they do not allow for dislunctive parts relation­ ships (even "alternative viewpoints" are logically conjoined) . A second is that only the structure of particular objects has been considered, whereas much human parts knowledge is generic. A third is that no provision has been made for avoiding individual mention of multiple parts of the same type, such as a centipede's legs or a human being's neurons.

In [10] some extensions to generic graphs and graphs containing representations of sets of parts are sketched. The chief problem with generic graphs is that they are dispersed over (possibly over­ lapping) type hierarchies. For example, only ele­ phant-specific partitioning assertions, such~ those subdividing the proboscis, would be associ­ ated directly with the concept of an elephant. Most of the remaining partitioning assertions, such as that dividing the body into head, neck, torso, tail, and limbs would be associated with higher-level concepts, such as that of a legged animal. Assuming that the fragments form a closed graph when brought together at corresponding nodes, the question-answering methods of this section can be adapted to generic graphs. The main requirement is the availability of methods for identifying corresponding nodes. This problem is discussed in a more general context in the next section.

The introduction of nodes representing sets of parts into parts graphs complicates both their syntax and use. Additional partitioning relations are needed(e.g., for partitioning an object into a~ of parts, and for partitioning the sets themselves), and methods must be provided to deal with more complicated questions-, such as "Is every leg part of some body segment?" Nevertheless, the definition of a closed graph can be modified to allow for sets of parts, and linear or subli­ near methods can be provided for answering seve­ ral types of questions for such graphs.

4. Property inheritance

When one describes a type of object, such as a robin, in some representation system, one would like many of its anatomical characteristics to be "inherited" from the description of a super­ ordinate concept; for example, the position of the beak on the head or of the wings on the body should transfer smoothly from "bird" to "robin".

Hayes [8,9] has discussed two alternative net­ work methods for facilitating property and re­ lationships inheritance from parts of more general to parts of less general kinds of objects. The first method involves connecting corresponding parts with "binders" which then serve as inheri­ tance paths. The second method actually uses the same nodes for corresponding parts of the two kinds of objects; however, the "depictions"4

4Essentially, a ··~piction" is a list of assertions which are specific to a particular (kind of) ob­ ject, accessible via the name of that object.

for the two kind of objects provide a·ccess to different sets of propositions about the parts. The latter proposal was adopted and given a logi­ cal interpretation in terms of shared variables in [15]. However, a serious flaw has become appa­ rent in this scheme. The telescoping of nodes, carried all the way down to the level of instan­ ces, assigns all instances of a concept to a sin­ gle node, and similarly for correspondi ng parts of those instances. As a result, relationShips between distinct instances or parts of distinct instances, such as "Polly's beak is larger than Tweety' s" cannot be stated. Even above the level of instances, the sharing of nodes prevents ex­ pression of relational propositions such as "The African elephant has larger ears than the Indian elephant", "Seagulls recognize each other by the colouration of their eyelids", "Dogs hate cats" (assuming "dog" and "cat" have a common superor­ dinate concept) , "No two dollar bills have the same serial number", etc ·.

The key to a logically respectable alternative which avoids these difficulties lies in the use of functions. For example, suppose that h is the Skolem function determined by the statement "Every higher animal has a head". Suppose further that the head of the universally quantified robin y has been identified with the value (h y) and si­ milarly, that the head of the universally quanti­ fied bird x has been identifi ed with the value (h x) . If other corresponding parts have been si­ milarly linked via their functional names, it is clear that parts relationships can be trasferred from parts of the bird to parts of the robin as easily as the corresponding universally quantified variables can be matched and the function values dependent on those variables located.

Locating values of functions can be made effi­ cient by attaching a "function table" to each node, in which known values (nodes) of functions appli­ cable to that node are indexed by function name. This scheme resembles Hayes' "binder" scheme, but the correspondence between a part of a subordi­ nate concept and a part of a superordinate con­ cept several levels above it are established in a single, trivial matching operation, instead of a series of binder traversals. Some complications are described in 00], including those arising from the presence of nodes representing sets of parts, and from the application of a function at different levels of a parts hierarchy (e.g., application of a "heart-of" function at the level of the whole animal and at the l evel of the ani­ mal's chest) .

Any system for representing parts correspon­ dences explicitly, whether it is based on shared nodes, binders, or functional indexing, presuppo­ ses a method of establishing these correspondences in the first place. Hand-coding such correspondences ought to be a temporary expedient, to be re­ placed eventually by a method of inferring and representing them on the basis of arbitrary sets of parts relationships such as might be obtained from natural language input. To see the problem and an approach to a solution, suppose that a na­ tural language system is told for the first time that "A bird has a tai 1". The system cannot assume that "tail" is translatable as a logical function; for this would lead to the unwarranted (and false) conclusion that "a bird with two tails" is a con­ tradiction in terms. A plausible translation is

('v'x) (3y) [ [x bird] ... [ [y tailJ & [y part-of x] J J. At the same time, a conjecture that y is normally the only tail should be stored, since the wording would more likely have been "at least one tail", "one or more tails", or something to that effect, had that been the interpretation intended by the informant. Skolemization of y gives

(Vx) [ [x bird] ... [ [ (t x) tail] & [ (t x) part-of x] J J. If told subsequently that "A magpie has a long tail", how could the system identify "a ·.· tail" with t applied to the universal "magpie" variable instead of creating a new Skolem function? It would at least have to c~eck for a possible re­ ferent of "a ... tail" among the parts of concepts superordinate to "magpie". After finding such a part at "bird", and verifying that this is pro­ bably the only part of a bird satisfying the pre­ dicate "tail", it could transfer the name of the Skolem function into the new context, at least tentatively.

In general, a wider search of prior instantia­ tions of "tail" would be required since the first occurrence need not have been at the superconcept level, but might instead have been at the subcon­ cept level, or in connection with a concept which is neither a superconcept nor a subconcept of "magpie" (e.g., "dog"). If an occurre.Jlceof "tail" is found for a subconcept of "magpie", then the name of the corresponding Skolem function can be transferred to the "magpie" context, provided that the newly mentioned "tail" is likely to be the magpie's only "tail" (in which case it is also the subconcept's only "tail"). If an occuc ... renee of "tail" is found for a concept such as "dog", then again the Skolem function can be trans­ ferred to the "magpie" context provided that bo.th the magpie's tail and the dog's tail are like~ to be unique (this policy prevents later naming conflicts at the level of common superconcepts of "magpie" and "dog") .

This approach is also workable for compound identifying descriptions. For example, the infor­ mation that a perch has a spiny fin on its back might be rendered as

('v'x) (3y) [ [x perch]-+ [ [y fin) & [y part-of xJ

& [y joins (back-of x) J & [y spiny J J J. If a part can be found for the superconcept "fish"

which uniquely satisfies "is a fin, is part of the fish, and joins the back of the fish", then its Skolem function name can be used in the Skolemiza­ tion of the perch's fin y. Much the same as be­ fore can be said about occurrences of parts satis­ fying the description in question but belonging to subconcepts or unrelated concepts.

All this presupposes a method for locating parts satisfying given descriptions, i.e. associative accessing. This topic cannot be covered here; Hayes' associative accessing methods are easily modified for use with semantic nets in which cor­ responding nodes are linked via their Skolem func­ tion names, rather than being telescoped or con­ nected with binders.

5. Concluding discussion

The seemingly trivial problem of extracting parts relationships from sets of partitioning assertions was seen to be quite difficult. The suggested methods for "closed graphs" provide a partial solution.

Effective property inheritance requires effec­ tive ways of establishing node correspondences. A method of establishing correspondences through names of Skolem functions was suggested which overcomes a difficulty with Hayes' node-sharing method.

Many problems in generalizing the proposed methods remain to be solved, such as that of providing detailed inference algorithms for ex­ tracting "part-of" relationships from fragmented generic parts graphs, or for establishing node correspondences or. the basis of composed func­ tions such as ( f (h x)) ) · Moreover, several im­ portant problems with parts have not been touched on here, such as the problem of inferring the mode of connection and relative position of parts of physical objects, the problem of determining the number of parts of a given type of a given object (counting the known instances only provi­ des a lower bound on that number), and the problem of accessing parts associatively on the basis of compound descriptions (Hayes considered unitary descriptions only) .

In view ot the centrality of parts relation­ ships in human thought, these are important areas for future research.

Acknowledgements

Alan Covington and Randy Rawson contributed to this paper through discussions and their work on a semantic net system. Pat Hayes' careful refe­ reeing provided much useful guidance. The re­ search was supported by an Alexander von Humboldt Fellowship and by Operating Grant No. A8818 of the National Research Council of Canada.