![]() |
|||
![]()
|
![]() |
![]() |
![]() |
2. HISTORICAL BACKGROUNDThe deep history of logic is typically associated with ancient Greek thinkers like Aristotle, and their pursuit of rules of reasoning. These historical roots continue to flow through the development of modern mathematics, for example, with the Leibniz goal of reducing thought to calculation. The modern application of logic to computation could be attributed to the formalization of logical reasoning first proposed by the German mathematician Gottlob Frege, and subsequently, to the formalization of the interpretation or semantics of logic by Alfred Tarski (see van Heijenoort and Tarski). Their combined insight into the relationship among the three essential ingredients of logic- -- syntax, semantics, and proof (or reasoning) rules -- has laid the foundation for the modern application of logic within the field of computation. The general impetus for the use of logic within artificial intelligence (AI) first arose with McCarthy's proposal for an advice taking program (McCarthy). The thesis is that no program or system is intelligent unless it can accept some form of input that is interpreted as advice about how to improve performance in some task. Expert systems can be considered a subclass of intelligent systems that attempt to capture and deploy the advice of an expert or collection of experts. Some of the confusion about the role of logic with respect to expert systems arises within this longstanding framework first proposed by McCarthy, and with the difficult challenges it entails. Developments in the principled implementation of logic systems in the support of building advice takers has taken a lot longer than alternatives based on more expedient approaches. The major development in understanding the application of logic as a practical computational tool lies with the development of programs to automate logical reasoning, including the early work of Prawitz, Davis, and Putnam, and Gilmore (Prawitz, Davisputnam, and Gilmore). These first demonstrations on the programmability of logical reasoning revealed the essential programmability of logic, but didn't provide any clear indication that such an endeavor was practical. Robinson's (Robinson) proposal for a machine-oriented logic modestly revolutionized the use of logic as a method of machine reasoning, by demonstrating that a very simple system of inference focusing on only one inference rule could be deployed in a kind of naive or mechanical way -- instead of perpetuating the idea that reasoning consisted of the rather clever choice from a large repertoire of complex reasoning rules. The development of logic-based artificial intelligence in the 1960s was paralleled by a kind of alternative development of heuristic methods, including a lot of work on knowledge structures for general problem-solving and the development of meaning representation systems largely motivated by natural language processing. The mere existence of an informal logic and nonlogical research style helped develop a myth that the two styles of artificial intelligence development were somehow fundamentally different (cf. McDermott, Levesque, and Goebel). The momentum of this distinction between the so-called "logicists" and non-logicists is at least partly the reason that the logical framework embedded within the first expert systems was overshadowed by the excitement of their performance in complex tasks. One of the earliest systems to establish a recognized framework for the idea of an expert system was the Dendral system of Feigenbaum, Buchanan, and Lederberg (Feigen and Baumbuchanan). The problem was to interpret mass spectrographs using rules about the relationship between segments of spectrograms and their corresponding molecular structure, in order to infer the structure of a complete molecular compound. Unlike previously successful performance systems, for example Gerlenter's geometry reasoning system (Gerlenter), the appeal of Dendral was not just its human-level performance of interpreting spectrograms, but the intuitive appeal of its reasoning framework. Specifically, it was the notion of modular, self-contained rules that had a reasonable clear meaning both as statements about the relationship between spectrogram segments and molecular structure, and as procedurally interpreted "antecedent-consequent" relations of "if-then-else" rules. The early adoption of these rules as a representation of expertise, combined with the important promotion of a rule-level debugging ("explanation" supporting user queries like "why" or "how" a certain result was obtained) sealed the popular appeal of the expert system idea and provides the departure point for many of the other expositions in this volume. However, the point here with respect to logic and its relation to expert systems lies with the conception of the ways in which rules in Dendral were conceived, and what the logic of their use was intended to be. In the example of Figure 1, the rule antecedent expresses properties of a spectrogram that suggest the rule consequent as conclusion. Contrary to its role within a logical reasoning system; such rules have attracted the misnomer "inference rule," assuming they encode some rule of logical inference instead of a fact about the application domain. To see the difference, consider the most common of inference rules, modus ponens: "From a fact A, and a fact A implies B, then one can infer B." Again, there is a logic underlying the rule structure of Dendral (and all of its rule-based descendants), but to uncover the logic first requires an analysis of the intended meaning of the Dendral rules. The required analysis is clear in hindsight (especially based on recent work by Konolige, Poole, and others (Poole, Konolige, and Poole): in all rules of the form "A if B" one can make one of two analyses: one is that situation A being true causes situation B. Such is the case in causal models of diagnosis, where a certain disease is the cause of certain symptoms. Within the details of Figure 1, this kind of causal analysis might misleadingly suggest that the antecedent regarding the two mass peaks at X1 and X2 somehow cause the consequence that the molecule contains a ketone group. However, this is obviously false, as the antecedent lists properties that are causal consequences of the ketone property, not vice versa.
FIGURE 1 An example rule from the Dendral Expert System. Alternatively, and like the intended interpretation of Dendral rules, the antecedent A is taken as evidence suggesting or supporting the tentative conclusion that situation B holds. Thus, the Dendral rule structure encodes the causal relationship in an operational form: to hypothesize a ketone first requires one to establish certain properties about mass peaks of components. This relationship between a reasoning strategy and causal knowledge is implicit in the use of all such rule-based systems, and is a part of the reason for their popularity. The challenge of building knowledge-based systems based on such rules can focus on the articulation of more-or-less independent rules that can be used to articulate such relationships in an incremental fashion. The key to understanding the role of logic in this earliest of expert systems and its rule-based successors is to first understand that the knowledge or axioms encoded as the system's expert knowledge are statements about evidential reasoning. In fact, it has been shown that program transformation methods can take a formal specification of the reasoning strategy of such rules together with the causal form of axioms, and automatically produce the equivalent rule-based form (e.g., [Goebel]). The idea is to view the schema of the Dendral rules as an abductive rule (see below) of the form given A causes B, to determine the cause of B, assume A and combine that generic reasoning strategy with causal knowledge, e.g., "colds cause runny noses." The combination provides an instance of a combined reasoning strategy and causal relation rendered as an evidential rule: "if you have a runny nose, assume it is caused by a cold." It is somewhat ironic that some of the earliest work on expert systems including that of Buchanan et al. (Churchman and Buchanan) was based on this kind of abductive reasoning, but it took several more years to re-extract the ideas (e.g., Poole, Poole, and Konolige). From the viewpoint of logic's impact on expert systems, the newer analysis explicitly acknowledges the important role of a clearly defined method for using logic for knowledge-based systems (e.g., PMG97).
|
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |