Path-Based and Node-Based Inference in Semantic Networks

PATH-BASED AND NODE-BASED INFERENCE IN SEMANTIC NETWORKS Stuart C. Shapiro Department of Computer Science State University of New York at Buffalo Amherst, New York 14226 Abstract Two styles of performing inference in semantic networks are presented and com- pared. Path-based inference allows an arc or a path of arcs between two given nodes to be inferred from the existence of an- other specified path between the same two nodes. Path-based inference rules may be written using a binary relational calculus notation. Node-based inference allows a structure of nodes to be inferred from the existence of an instance of a pattern of node structures. Node-based inference rules can be constructed in a semantic network using a variant of a predicate calculus notation. Path-based inference is more efficient, while node-based infer- ence is more general. A method is de- scribed of combining the two styles in a single system in order to take advantage of the strengths of each. Applications of path-based inference rules to the repre- sentation of the extensional equivalence of intensional concepts, and to the expli- cation of inheritance in hierarchies are sketched. I. Introduction Semantic networks have developed since the mid sixties [10;11] as a formal- ism for the representation of knowledge. Methods have also been developing for per- forming deductive inference on the knowl- edge represented in the network. In this paper, we will compare two styles of in- ference that are used in semantic networks, path-based inference and node-based infer- ence. In sections 2 and 3, these terms will be explained and references to sys- tems that use them will be provided. In sections 4 and 5, the advantages and dis- advantages of each will be discussed. Sections 6, 7 and 8 will show how they can be used to complement each other in a sin- gle semantic network system, how path- based inference can help represent the ex- tensional equivalence of intensional con- cepts, and :low a formalism for writing path-based inference rules can be used to explicate the notion of "inheritance = in a semantic network. 2. Path-Based Inference Let us refer to a relation (perforce binary) that is represented by an arc in a network as an arc-relation. If R is an arc-relation, an arc la~elled R from node a to node b represents that the relation- ship aRb holds. It may be that this arc is not present in the network, but aRb may be inferred from other information present in the network and one or more inference rules. If the other information in the network is a specified path of arcs from a to b, we will refer to the inference as path-based. The ways in which such paths may be specified will be developed as this paper proceeds. The two clearest examples of the gen- eral use of path-based inference are in SAMENLAQ II [18] and Protosynthex III [13]. Both these systems use what might be call- ed "relational" networks rather than =semantic = networks since arc-relations include conceptual relations …

Content truncated to 500 words