Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


3.5. ABDUCTION

Abduction is used for finding plausible explanations for some observed events, in contrast to deduction, which is normally used for deriving facts from premises. Reasoning by abduction can be described by the following inference rule:

Contrary to this abductive rule, deductive inference is typically based on modus ponens: [alpha] is a premise and [beta] is a derived fact. Another difference concerns the nature of the implication. Modus ponens assumes material implication as defined in classical logic, whereas abuction characterizes the relationship between [alpha] and [beta] with more freedom. Material implication says that [alpha] is a reason for [beta] to be true, establishing in this way, a causal relationship between [alpha] and [beta]. However, not all abduction is concerned with cause and effect. Levesque suggests the extension of the notion of explanation in order to include the case that [alpha] is sufficient and not just necessary to explain why [beta] must be true.

The concept of abduction was first presented by the philosopher Peirce (Peirce) and introduced to AI by Pople (Pople) and by Charniak and McDermott (Charniak). Peirce sees abduction as a reasoning process from effect to cause that yields explanations. Induction and abduction can be utilized together: abduction is used to synthesize an explanation, which is then generalized by induction.

The most important part of an abductive procedure is the formation of a new theory that explains the observed data. Among the methods used to generate hypotheses are a type of linear resolution and an assumption-based truth maintenance system (Merziger; Kakaskowalskitoni). In general, there are several possible abductive hypotheses to choose from. Criteria that a good explanation should meet include: a hypothesis that should account for the facts and should be the simplest hypothesis available.

Abduction is a type of nonmonotonic reasoning because as a system becomes more experienced by knowing more observations, it is possible that previous explanations have to be rejected. Default logic is a nonmonotonic formalism that can be adapted to find explanations (Poole).

4. LOGICAL REASONING SYSTEMS

During the 1960s, research efforts in AI concentrated on finding problem representation formalism for general problem-solving. The General Problem Solver (GPS) of Newell and Simon is the best known example of this work (Newell-Simon). A fundamental contribution of the research around the paradigmatic expert systems DENDRAL an MYCIN was the idea that key to effective problem-solving was the emphasis on knowledge required to solve the problem, thus changing the focus of research efforts from problem representation to knowledge representation. Another important contribution was the distinction between domain knowledge and control knowledge. The former is specific to the domain in which the problem is being solved; the latter is about how to conduct the search for a desired solution in a search space and is independent of the problem domain. This idea led to the concept of shells, which included control, inference, and knowledge acquisition mechanisms that could be used throughout domains and started the establishments of AI companies that commercialized expert system development tools. In this section we describe the main systems that use logic as the underlying mechanism for accomplishing reasoning and intelligent behavior. This include rule-based systems, logic programming systems, theorem provers, semantic networks and frame systems, description logics, and truth-maintenance systems.

4.1. RULE-BASED SYSTEMS

Production rules were first proposed by Emil Post in 1943 (Post), to characterize a general method of computation. They were subsequently used by Chomsky as rewrite rules in the context of language processing in 1957, and used by Newell and Simon for modeling human problem-solving in 1972 (Newell-Simon). This technique was adopted in the DENDRAL and MYCIN projects to represent knowledge and became a popular technique in developing expert systems applications during the 1970s. As introduced above, rules are implications of the form if P then Q. The consequent of a rule can be interpreted as a new knowledge or as an action to be taken. In the former, we have a deduction rule-based system; and in the latter, we have a reactive rule-based system. In a rule-based system, if we move in the direction of the antecedents to the consequents of the rules, we do forward-chaining, and if we move in the direction of the consequents to the antecedents, we do backward-chaining.

Forward-chaining rule-based systems, which reason from input facts to conclusions, are more appropriate for modeling intelligent systems that interact with an environment and respond to stimuli in many possible ways. Backward-chaining rule-based systems, which hypothesize a certain goal and reason backwards to justify the hypothesis with input facts, are more appropriate in designing diagnostic systems or types of goal-directed reasoning systems such as theorem provers and logic programming languages. We notice that the reasoning conducted in backward-chaining rule-based systems is simply a form of abductive reasoning.

A typical rule-based system works as follows:

  • The system keeps a rule base with rules of the form x1 ... xn —> y1 ... ym where the xi represent facts and the yi represent actions to be performed.
  • The system also keeps a working memory to store facts obtained from the environment or inferred by the system.
  • In each cycle, the system computes a subset of rules whose left-hand side matches the facts stored in the working memory. This is called the match phase.
  • A rule from the computed subset of matching rules is selected for execution. This is called the conflict resolution phase.
  • The selected rule is then executed by performing the action specified by the right-hand side of the rule. This is called the act phase.

The XCON expert system, built for the configuration of computer systems for the customers of Digital Equipment Corporation, is the best known forward-chaining rule-based system. Forward-chaining rule-based systems are also used for cognitive modeling where the working memory models the short-term memory and the rule-base models the long-term memory. The SOAR expert system is the best representative of this type of system (Laird-Soar).


Previous Table of Contents Next

footer nav
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.