next up previous
Next: Hayes Up: LAI in today's implementations Previous: LAI in today's implementations

Kim

Kim attempts to unite important and related concepts in LAI, logic programming, and software engineering. On the surface, this is an exceedingly tall order - given that each of these fields is apparently based on large islands of its own research and applications and that each is driven by its own (largely) self-contained theoretical and applied communities. This book, however, succeeds; the reason it does is twofold: One, its foundation is the concept of an implemented LAI system (as explicated above) - a system that interweaves AI, logic programming, and software engineering; two, Kim targets an introductory undergraduate course in computer programming, which allows the book to dodge genuine but rarefied distinctions between the fields to be united. In short, Kim succeeds in championing a logic-based approach to building implemented LAI systems (called knowledge systems in Kim).

This is not to say that Kim is flawless. Far from it. One problem is that Kim views logic programming, in the form of standard Prolog, as a programming system based on mathematical models of human thinking. Kim believes that the unique strengths of the LAI approach spring from its affinity to the thinking patterns of people as opposed to those of computers. Indeed, Kim holds that first-order logic was created to address flaws in human reasoning:

Unfortunately, we humans are prone to error when it comes to complex problems in reasoning. For example, careful studies of legal documents - which are intended to be paragons of logical precision - often result in the exposure of internal inconsistencies. ... Mathematical logic tex2html_wrap_inline1275 was developed to address the problems of faulty reasoning and ambiguity in everyday language. The basic premise is that correct procedures for reasoning or deductive thinking can be formalized and used profitably, independently of the specific domain of discourse (Kim, p 10).

That correct procedures for reasoning can be formalized independent of specific domains is true and, we agree, helpful. But as most readers will know, there is a longstanding controversy about whether logic, at least in the form of tex2html_wrap_inline773 tex2html_wrap_inline775 , serves as an accurate model of the way humans in fact think. Even if logic provides an answer to the question ``What is a proof?'' - the tackling of which, as we've noted, Glymour chronicles - it doesn't follow that logic captures human thinking. Logic evolved out of attempts to meet the challenge of constructing an impeccable foundation for classical mathematics.And then once tex2html_wrap_inline773 tex2html_wrap_inline775 had been devised, computability theory was born because of attempts to settle certain mathematical problems arising from this system (which is really, from the standpoint of string theory, a rather straightforward context-sensitive language). For example, Turing machines were designed so as to settle the question of whether determining satisfiability of formulas in tex2html_wrap_inline773 tex2html_wrap_inline775 is algorithmically solvable. It was Montague, as Thayse 1989 nicely explains, who wanted in earnest to formalize natural language - and Montague knew well that first-order logic, of which Prolog is a proper fragment, would be insufficient for that formalization. Nonetheless, though Prolog isn't, as Kim opines, ``based on human logic'', it does, we agree, represent a powerful and appropriate tool for building AI systems, especially in the areas of natural language processing, robotics and expert systems. (It's certainly true that some aspects of human deliberate thinking are nicely formalized in Prolog, and that as a vehicle for smooth and rapid implementation it enjoys perhaps unrivaled power.)

Part I of Kim includes an introduction to and an historical view of AI from the perspective of implementation. Part II of the book, entitled ``Prolog'', presents this language as a vehicle for building implemented AI systems. The advantages of Prolog, as Kim explains, lie in its well-understood roots in tex2html_wrap_inline773 tex2html_wrap_inline775 , and, again, the ease with which the software engineer can map a problem domain into working software.

A particularly notable feature of Prolog (by our lights) is competently discussed in Chapter 11, wherein Kim treats Prolog's support for meta programming, a powerful notion underlying LP that views programs as mathematical objects that can themselves be analyzed, evaluated and modified. The meta-programming facility in Prolog allows a program to reason about other programs. Variables in Prolog can denote other clauses; predicates can be developed which describe other predicates. A simple example is the two-place predicate arg. The fact

displaymath1639

expresses that the predicate p has two arguments.

Meta-programming plays a key role in our own research, which is in significant part devoted to engineering a literarily creative artificial agent known as BRUTUS (Bringsjord and Ferrucci, forthcoming). BRUTUS includes a formalization of the concept of betrayal, and reasons about this concept with help from our meta-programming. This programming technique facilitates the amalgamation of an object-level language with a portion of a meta-level language suitable for formalizing the derivability relation of the orginal object lanaguage.For details on the notion of the amalgamation of language and metalanguage in logic programming, see Bowen and Kowalski 1982. Such amalgamation in the same system allows greater expressivity than the object language alone. Consider, for example, BRUTUS' reasoning about different agents' belief systems. Suppose, for example, that there are two individuals, Julius and Brutus, in the BRUTUS world. Each has their own beliefs about this world and about one another. Suppose that some sequence of actions take place in their ``reality'', the result of which is that Brutus stabs Julius. BRUTUS must determine if Brutus acted with malintent to murder Julius, or if he acted in self-defense. To determine this the system must inspect Brutus' belief system and determine if it was consistent for Brutus to believe that his life was threatened by Julius. Fleshing out this example helps communicate the power of meta-programming (and helps bring to life the technique as delineated in Kim and employed - as we shall see below - in Hayes et al. and Thayse 1991); we do so as follows.

First, consider the following formulation, which is a simplification of a sort BRUTUS in fact manages.

malintent(Accused,Victim) tex2html_wrap_inline1641
person(Accused),
person(Victim),
beliefs(Accused,ABeliefs),
not(proof(ABeliefs,`threatened-by(Accused,Victim)'))).

The predicate proof represents the provability relation embodied in Prolog (i.e., resolution logic). It is a meta-logical predicate used to determine if the statement

displaymath1643

can be proven from the accused's beliefs using resolution logic.

This mixed formulation of object and meta-level constructs allows the AI system to treat agents' thought processes independently from each other and from the system's beliefs. This is key for reasoning about the intent of an agent independent of reality. For example, Julius may have been conspiring to destroy Brutus, but unless this fact can be realized from Brutus' beliefs, this truth would not exonerate Brutus in the least.

Consider, along these lines, a pure object-level formulation:

malintent(Accused,Victim) tex2html_wrap_inline1641
person(Accused),
person(Victim),
not(threatened-by(Accused,Victim)).

If it were the case that Julius conspired to kill Brutus, but Brutus was entirely unaware of this evil, then the latter formulation would fail to correctly determine Brutus' intent.

In sum, meta-programming as an enabler for amalgamating object-level and meta-level language is an important representation and implementation tool for LP-based LAI systems, and we refer readers interested in this topic first to Kim, then to (a key paper discussed below in) Hayes et al. and then to the logical system EPL, which is specified and applied in ``Bulding Expert Systems'', Chapter 3 of Thayse 1991.

Chapter 13 of Kim is notable as well. This chapter is a demonstration of how Prolog provides a logic-based facility for parsing and attributing semantics to statements given in natural language. We encourage those interested in natural language processing to consider how the theoretical treatment of natural language in Thayse 1989 and Thayse 1991, touched upon above, can be realized with the sort of techniques discussed in this part of Kim.

Part III, entitled Knowledge Structures and Systems, discusses techniques in representing, structuring and organizing knowledge and developing software systems. It concentrates on modular architectures for knowledge systems in industry. Chapter 14 is worth particular mention. It demonstrates that knowledge structuring techniques like frames, semantic networks, hierarchies and rules have been central in engineering implemented LAI systems. Although there is certainly no in-depth study to be found here, Kim competently discusses how Prolog can enable a formal and mathematical approach to realizing these structures in software.

Part IV presents three implemented AI systems: A robot simulator, a calculus aid and an investment counselor. The treatment is appropriate for an undergraduate course in programming. Though not terribly robust, these examples do make the point that LAI pursued through Prolog offers practical engineering advantages.


next up previous
Next: Hayes Up: LAI in today's implementations Previous: LAI in today's implementations

Selmer Bringsjord
Mon Nov 17 14:57:06 EST 1997