Artificial Intelligence

Research Directions in Cognitive Science: European Perspectives Vol. 5

D. Sleeman, N. O. Bernsen

• Publisher: Routledge
• Year: 2019
• eBook ISBN: 9781000734775
• Edition: 1
• Topic: Psychology
• Subtopic: Artificial Intelligence (AI) & Semantics
• Index: Psychology

Originally published in 1992, this title reviews seven major subareas in artificial intelligence at that time: knowledge acquisition; logic programming and representation; machine learning; natural language; vision; the design of an AI programming environment; and medicine, a major application area of AI. This volume was an attempt primarily to inform fellow AI workers of recent European work in AI. It was hoped that researchers in 'sister' disciplines, such as computer science and linguistics would gain a deeper understanding of the assumptions, techniques and tools of contemporary AI.

CHAPTER 1
KNOWLEDGE REPRESENTATION AND LOGIC PROGRAMMING

Roberto Barbuti
Dipartimento di Informatica, Università di Pisa, Italia

Maurizio Martelli
Dipartimento di Matematica, Università di Genova, Italia

Maria Simi
Dipartimento di Matematica e Informatica, Università di Udine, Italia

1. INTRODUCTION

The underlying assumption of most of the current research in Artificial Intelligence is that intelligent systems can be constructed using explicit, declaratively represented, factual knowledge together with general reasoning mechanisms. Therefore the study of formal ways of extracting information from symbolically represented knowledge is recognized of central importance in the field of Knowledge Representation (KR); see (Brachman & Levesque, 1985) for a large collection of papers in the field.

In the history of Knowledge Representation, a great deal of effort has gone into the study and development of various notations and formalisms, with rather less attention paid to logical foundations and inferential consequences of the notations. However many authors have argued about the fundamental importance of a formal semantics to give a precise account of the meaning of the notations used (Hayes, 1974; McDermott, 1978) and defended the role of formal logic as an essential tool for modelling and understanding representation formalisms (Hayes, 1977; Moore, 1982). This point of view has now become widely accepted.

When First Order Predicate Logic is used as a representation formalism, the basic problem of deciding whether a fact is a logical consequence of a knowledge base is in general unsolvable and intractable. Most techniques and formal proposals in Artificial Intelligence can be understood as attempts to deal with only limited kinds of reasoning in exchange for reasonable complexity of behaviour. The explicit recognition of this "fundamental trade-off in knowledge representation and reasoning" is, for example, the basis of current research on terminological languages and hybrid systems (Levesque & Brachman, 1984).

The need of a powerful theorem prover for full First Order Logic has influenced many early studies in improving the efficiency of the proof procedures: from the seminal work on resolution of Alan Robinson (Robinson, 1965) to the important results on SLD-resolution (Kowalski & Kuehner, 1971; Hill, 1974). The realization that a subclass of First Order Logic (Horn clauses) has a procedural interpretation (Kowalski, 1974), together with some experiments on theorem provers for natural languages (Colmerauer, 1973), gave rise to the PROLOG language and to a new field called Logic Programming (LP); (see (Lloyd, 1987; Apt, 1987) for an introduction to the theory; (Sterling & Shapiro, 1986) for a nice presentation of the language and its applications. Many important foundational aspects of Logic Programming can be found in (Kowalski, 1979a, 1979b; van Emden & Kowalski, 1976; Apt & van Emden, 1982; Clark & Tarnlund, 1982)).

Logic Programming is characterized by two essential features: non-determinism, i.e. search-based computation, and unification. The central role of search in LP languages is connected with their being halfway between theorem provers and standard programming languages, which makes them suitable for many artificial intelligence applications.

Programs are statements in a logical language and a program execution is a proof from the set of axioms (the program) of a specific formula (the goal). As observed in (Pereira, 1985), peculiar to LP, with respect to automated deduction, are deduction steps which are simple so that their effect will be easier to predict (as for functional application). The boundaries between LP and automated deduction is not a sharp one and there is always a mutual influence; new results in automated deduction can widen what is considered LP and results in LP can improve the field of automated deduction.

First Order Predicate Logic has other problems as a tool for KR; in fact, classical logic is inadequate to deal with common sense reasoning problems, where one has to draw conclusions based on incomplete knowledge or defaults and has to reason about knowledge and belief and other mental attitudes, time, actions and plans. Current research in these fields remains within the logic framework, originating a number of non-standard logics that try to capture the essential aspects of our every-day way of reasoning about the world. Recently in the LP community several extensions have been proposed in order to cope with such representation problems.

Knowledge representation and logic programming are getting together (as it was foreseen by Kowalski in (Kowalski, 1979a)), especially in recent years when, from one side the knowledge representation community has evolved towards formal representations with concerns about efficiency, and on the other side the logic programming community has developed many powerful extensions and integrations with other programming paradigms, which make logic programming languages increasingly able to cope with the representation of complex knowledge.

A possible direction of development for LP is a system which enables the user to write specifications using the full power of logic with the ability to refine them into efficient logic programs (for example see (Bundy, 1988)). This kind of approach will make the difference between LP and KR even smaller.

In this paper we survey some research topics and results in KR and we emphasize the recent proposals in LP which can be considered as contributions to these research topics. The aim is to show that research in LP, with its necessary extensions and improvements, can contribute a formal and efficient representation of knowledge that emerges from the recent research in KR.

In Section 2 we will discuss some classical AI paradigms and proposals to accommodate them into a logical framework. These proposals have been taken into consideration as possible LP applications since the early years of LP. Section 3 is devoted to the new trend of KR towards hybrid systems and specialized reasoners and of LP towards new extensions and integrations. From the KR point of view the emphasis is on using different and specialized reasoning components, while from the LP point of view the aim is to offer a richer language which integrates different paradigms. These approaches can be seen as part of the same trend towards multiple paradigm systems resulting in similar solutions in the two fields. Section 4 covers an important area of KR research, i.e. non-monotonic reasoning, which is producing a number of different non-standard logics to deal with common sense reasoning tasks, and is also playing a more and more important role in LP, especially for the treatment of negation. Section 5 addresses the problem of reasoning about knowledge and belief pointing out how one of the approaches coming from KR, i.e. meta-level reasoning, is also becoming usefully applied in LP. Finally, in Section 6, we outline some research directions towards higher-order logic which will play a significant role in providing a unifying framework for research proposals in KR and LP.

2. STRUCTURED REPRESENTATION OF KNOWLEDGE

This section will briefly review some of the more popular paradigms for representing knowledge which emerged from the AI community, namely production systems or rule based representations, associative representations such as semantic networks and object centred or frame based representations. Each of these paradigms can be understood as a class of proposals able to cope with a number of specific representation and reasoning tasks. We will discuss early attempts to include these proposals in the LP framework.

2.1 Production Systems, Semantic Networks, Frames

Production Systems

Production rules are one of the most popular paradigms for representing knowledge in expert systems. This is due to the fact that in some tasks it appears that the domain knowledge of an expert can be conveniently expressed as a set of "if-then" associations, called rules, of the form "if antecedent then consequent".

A production system can be considered as constituted of three parts: a rule base, a working memory and a rule interpreter. The interpretation cycle proceeds essentially as follows: the antecedents of all rules are matched against every element in the working memory and the set of rules that are applicable is determined (the conflict set). A rule in the conflict set is then activated according to a conflict resolution strategy. The activation changes the working memory by executing the consequent part of the rule and the cycle repeats.

A disadvantage of this representation schema is that it forces the user to think about control of the inference process by selecting the most appropriate conflict resolution strategy. This can be embedded in the interpreter or encoded in meta-rules.

The expressive power is in general very weak but nevertheless adequate for a significant number of applications. Techniques for speeding up the computation of the conflict set have been developed by exploiting a special internal representation of the rules (Forgy, 1982) and parallel processing (Gupta, 1985). This makes possible the development of applications involving thousands of rules.

Semantic Networks

Semantic networks, originated by Quillian (Quillian, 1967), are a model accounting for the organization of "semantic" knowledge (as opposed to syntactic) in the human mind. Quillian emphasizes the connectivity of knowledge; like in a dictionary, each concept is defined in terms of others, creating a linked structure connecting all the concepts of interest. As a data structure, a semantic network is constituted of nodes, corresponding to concepts (individual entities or classes of entities), and directed arcs corresponding to binary relationships between concepts.

Among these relations, the sub-class relation between concepts (often called is-a) was soon recognized as an important one, for which specialized built-in inference rules have been proposed: more specific nodes can be considered to "inherit" properties specified for the more general ones.

Semantic network systems differ from one another on a number of aspects. Some allow the "cancellation" of inherited properties accounting for exceptions to general rules; some have a single top node; some a single bottom node; some are complete lattices; some networks allow all link names to be specified by the user; others provide a set of predefined relations; some provide extended notations for the representation of the full first-order logic expressions (i.e. partitioned semantic networks (Fikes & Hendrix, 1977)).

In general, a semantic network system includes a set of structure manipulation primitives for adding and deleting nodes and links, and for traversing the graph. A few built-in inheritance mechanisms are provided; for different reasoning tasks, the users have to write their own search and inference procedures. The completeness and correctness of such implemented mechanisms is in general extremely hard to predict.

Semantic net notations are popular in language understanding programs and in contexts where the fundamental operation is the recognition of complex objects, for example in vision systems.

Frames

Another influential idea in Knowledge Representation has been that of frames introduced by Minsky (Minsky, 1981). While semantic networks emphasize small and primitive units of knowledge and their relations to one another, frames emphasize larger and complex chunks of knowledge. A frame is a cluster of information related to a concept including relations to other frames, attributes with their "typical" values and procedures.

The original conception of frames focused on their use as prototypical schémas against which to compare new situations with the goal of recognizing them, filling in the details, generating predictions or expectations.

The more concrete version of frames which has survived in representation languages is best described as a collection of slot/value pairs where the values may be among other things, defaults, demons (procedures which are activated on occurrence of specified events), and relations to other frames. Among frame-based representation languages are KRL (Bobrow & Winograd, 1977), FRL (Roberts & Goldstein, 1977), KEE (Fikes & Kehler, 1985), KRS (Steels, 1985).

Formal Accounts of AI Paradigms

The excessive freedom in the use of semantic network and frame formalisms, due to a lack of precise semantics, drew criticisms from a number of researchers. In particular Woods (Woods, 1975) and Brachman (Brachman, 1983) advocated the importance of a more formal account of the meaning of nodes and links in semantic networks. Hayes (Hayes, 1979) argues that the essential aspects of reasoning with frames can be captured by a first order formalization. Therefore frame based representations, at the representational level, are equivalent to a set of expressions in first order logic. Nevertheless some of the basic ideas such as inheritance and attributes have survived as useful structuring mechanisms, and are being given a more formal account in more recent knowledge representation systems. KRYPTON (Brachman, Gilbert Pigman & Levesque, 1985), KL-TWO (Vilain, 1985) and OMEGA (Attardi & Simi, 1981, 1986) are examples of systems in which logic is used to give formal semantics to the representation language and reasoning apparatus.

As a consequence of this formalization effort, propertie...

Table of contents

• Cover
• Half Title
• Title
• Copyright
• Original Title
• Original Copyright
• Contents
• Acknowledgements
• Artificial Intelligence: Achievements and Promises
• 1. Knowledge Representation and Logic Programming
• 2. Language Understanding by Computer: Developments on the Theoretical Side
• 3. Characterising Machine Learning Programs: A European Compilation
• 4. A Perspective on Machine Vision
• 5. ProtoKEW: A Knowledge Based System for Knowledge Acquisition
• 6. POPLOG's Two-level Virtual Machine Support for Interactive Languages
• 7. Applications of Expert Systems Technology to Medicine
• Author Index
• Subject Index