next up previous
Next: AI's Other Spouse: Connectionism Up: LAI in today's implementations Previous: Hayes

Thayse 1991

Thayse 1991, visited above under the topic of ``Metatheory'', does an excellent job of compiling a number of LAI research thrusts in a variety of classic problem domains (natural language processing, expert systems, machine learning, requirements engineering, etc.), where the thrusts are often shown to naturally lend themselves to Prolog or other LP systems for implementation.

In Chapter 2, Jean-Louis Binot argue that effective natural language processing requires the structure of an intermediate logical form. The intermediate form is used for semantic interpretation of natural language constructs and naturally lends itself to Prolog as an implementation formalism.

Chapter 3, by Albert Bruffaerts and Eric Henin, addresses the development of knowledge bases for expert systems. They wrap together in canonical fashion the concepts of logical system and implemented AI system:

In a logical framework, a knowledge base is specified as a logical theory whose standard model consists of the expert's perception of the application domain. The axioms of the theory are a formal expression of the knowledge of the application domain. The conclusions drawn from the knowledge base correspond to the logical consequence of the theory. Given a well chosen set of inference rules, which is sound and complete, answers to queries can be identified to theorems derived from the axioms through a formal deduction process. The proof of the theorem defines the nature of what could be a justification of a query answer (Thayse 1991, p. 119).

Chapter 3 also outlines the classic case for using LP to represent knowledge and handle (via resolution) derivation. The case, in short, runs as follows. Declarative representations are important because they capture the factual information about the domain, as precise logical statements independent of the control strategy used to execute the computation on a particular computer architecture. Consequently, LP, as a means for declarative programming, allows the AI practitioner to directly and declaratively represent the logic of the system independently of control and performance concerns. LP provides means for separating concerns about ``what'' knowledge the system has without worrying about ``how'' it can be derived. Prolog does, however, allow access to certain procedural control mechanisms for fine-tuning the performance of the underlying inference engine.

This case for LP may be compelling in the abstract, but if LP is wed to Prolog, some problems, as Bruffaerts and Henin point out in Chapter 3, arise. They explain that Prolog, while a strong fundamental technology, does not provide sufficient expressive power for supporting a purely declarative approach that insulates the developer from some of the procedural enticements accessible in pure Prolog. They propose the EPL language as an extension to Prolog that supports:

  1. The use of predicate names as terms so that knowledge and meta-knowledge can be treated equally in the same formalism.
  2. Explicit universal and existential quantifiers in rules and queries.
  3. Lambda terms for representing parameterized formulae.
  4. A functional notation for binary relations that represent mappings to improve the structuring and readability of the rules.

EPL is described in detail. As a credit to Prolog's meta-programming facility, this language is implemented in Prolog. The EPL language is used in the remaining portions of the chapter as a representation and implementation formalism to address plausible reasoning, class hierarchies, inheritance and the automatic generation of explanations.

The application of logical formalisms to real world problems, as we saw above when motivating revisable reasoning, requires some mechanism for efficiently handling change. Idealized domains like those dealt with in classical mathematics are in some sense immutable: the axioms of arithmetic, for example, don't change over time. The ``real world'', of course, isn't so clean: it presents problems requiring a mechanism for efficiently realizing the effect that modifying the starting assumptions has on derived conclusions. Chapter 4, by Jean- Pierre Mueller and Dominique Snyers, provides an excellent discussion of one of the practical sides of revisable reasoning, namely, reason maintenance systems.

Chapter 5, by Axel van Lamsweerde, ``Learning Machine Learning'', presents a logic-based treatment of learning systems. This chapter provides an important introductory perspective on learning for those convinced that learning can only be productively tackled by CAI. Our suggestion is that those interested in learning about learning within LAI start with this chapter, and then move on to the ``Non-monotonic Learning'' piece (in Hayes et al.) we discussed above.

Chapter 6, by Eric Duboies, Jacques Hagelstein and Adre Rifaut, is similar in approach to Chapter 3. The authors address the domain of requirements engineering of computer systems. They offer an excellent justification for their commitment to LAI and develop a logical system to tackle the problem. The system is called ERAE and includes characteristics of several weaker logical systems (e.g., ERAE's temporal logic component provides significantly greater declarative expressivity than ordinary Prolog and tex2html_wrap_inline773 tex2html_wrap_inline775 ). The semantics of its temporal component are smoothly defined and, as the authors informatively show, allow the language to declaratively express challenging sentences like ``A package can only arrive in a bin if it previously passed through the source station.''

ERAE marks progress over the linear time temporal logic we considered above: it extends the predicate rather than the propositional calculus, and the set of temporal operators now grows to a much more expressive quintet (each of which has a ``dual''):We have changed the notation slightly.

  1. tex2html_wrap_inline1169 (read: ``at the next time'')
  2. tex2html_wrap_inline955 (read: ``always'')
  3. tex2html_wrap_inline953 (read: ``eventually'')
  4. tex2html_wrap_inline1171 (read: ``until'')
  5. tex2html_wrap_inline1171 ! (strong until)
  6. tex2html_wrap_inline769 (read: ``at the previous time'')
  7. tex2html_wrap_inline1707 (read: ``since ever'')
  8. tex2html_wrap_inline1709 (read: ``eventually in the past'')
  9. S (read: ``since'')
  10. S (strong since)

The semantic interpretation for these operators, as was the case for the simpler propositional linear time temporal logic visited above, are based on a set of histories, that is, infinite series of states. Using the binary functional ``successor'' relation R on S from above, and ignoring the complexity that including predicates and quantifiers produces, one can quickly get a sense for how the binary relation tex2html_wrap_inline857 works for the temporal component of ERAE. For example, here is how ``eventually in the past'' is cashed out:

ERAE's temporal component makes it very powerful for declaratively expressing and reasoning about temporal relationships that would require convoluted procedural programming in a less expressive system. Incorporating formal temporal reasoning components in logic programming systems promises to encourage and strengthen the application of logic-based approaches to a broader range of applications.

Chapter 7, by Philippe Delsarte and Andre Thayse, is a refinement of Montague's program; we touched upon it above.

Chapter 8, by Frank van der Linden, provides a succint introduction to the fascinating class of higher-order typed systems (typed versions of the system tex2html_wrap_inline773 tex2html_wrap_inline889 ) and shows how they can be implemented for proof-checking tasks. Though certainly an advanced topic, this an exciting area that testifies to the multi-faceted power of LAI.

next up previous
Next: AI's Other Spouse: Connectionism Up: LAI in today's implementations Previous: Hayes

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