Rule-based system

Last updated

In computer science, a rule-based system is a computer system in which domain-specific knowledge is represented in the form of rules and general-purpose reasoning is used to solve problems in the domain.

Contents

Two different kinds of rule-based systems emerged within the field of artificial intelligence in the 1970s:

The differences and relationships between these two kinds of rule-based system has been a major source of misunderstanding and confusion.

Both kinds of rule-based systems use either forward or backward chaining, in contrast with imperative programs, which execute commands listed sequentially. However, logic programming systems have a logical interpretation, whereas production systems do not.

Production system rules

A classic example of a production rule-based system is the domain-specific expert system that uses rules to make deductions or choices. [1] For example, an expert system might help a doctor choose the correct diagnosis based on a cluster of symptoms, or select tactical moves to play a game.

Rule-based systems can be used to perform lexical analysis to compile or interpret computer programs, or in natural language processing. [2]

Rule-based programming attempts to derive execution instructions from a starting set of data and rules. This is a more indirect method than that employed by an imperative programming language, which lists execution steps sequentially.

Construction

A typical rule-based system has four basic components: [3]

  • Match: In this first phase, the condition sides of all productions are matched against the contents of working memory. As a result a set (the conflict set) is obtained, which consists of instantiations of all satisfied productions. An instantiation of a production is an ordered list of working memory elements that satisfies the condition side of the production.
  • Conflict-resolution: In this second phase, one of the production instantiations in the conflict set is chosen for execution. If no productions are satisfied, the interpreter halts.
  • Act: In this third phase, the actions of the production selected in the conflict-resolution phase are executed. These actions may change the contents of working memory. At the end of this phase, execution returns to the first phase.

Whereas the matching phase of the inference engine has a logical interpretation, the conflict resolution and action phases do not. Instead, "their semantics is usually described as a series of applications of various state-changing operators, which often gets quite involved (depending on the choices made in deciding which ECA rules fire, when, and so forth), and they can hardly be regarded as declarative". [5]

Logic programming rules

The logic programming family of computer systems includes the programming language Prolog, the database language Datalog and the knowledge representation and problem-solving language Answer Set Programming (ASP). In all of these languages, rules are written in the form of clauses :

A :- B1, ..., Bn.

and are read as declarative sentences in logical form:

A if B1 and ... and Bn.

In the simplest case of Horn clauses (or "definite" clauses), which are a subset of first-order logic, all of the A, B1, ..., Bn are atomic formulae.

Although Horn clause logic programs are Turing complete, [6] [7] for many practical applications, it is useful to extend Horn clause programs by allowing negative conditions, implemented by negation as failure. Such extended logic programs have the knowledge representation capabilities of a non-monotonic logic.

Differences and relationships between production rules and logic programming rules

The most obvious difference between the two kinds of systems is that production rules are typically written in the forward direction, if A then B, and logic programming rules are typically written in the backward direction, B if A. In the case of logic programming rules, this difference is superficial and purely syntactic. It does not affect the semantics of the rules. Nor does it affect whether the rules are used to reason backwards, Prolog style, to reduce the goal B to the subgoals A, or whether they are used, Datalog style, to derive B from A.

In the case of production rules, the forward direction of the syntax reflects the stimulus-response character of most production rules, with the stimulus A coming before the response B. Moreover, even in cases when the response is simply to draw a conclusion B from an assumption A, as in modus ponens, the match-resolve-act cycle is restricted to reasoning forwards from A to B. Reasoning backwards in a production system would require the use of an entirely different kind of inference engine.

In his Introduction to Cognitive Science, [8] Paul Thagard includes logic and rules as alternative approaches to modelling human thinking. He does not consider logic programs in general, but he considers Prolog to be, not a rule-based system, but "a programming language that uses logic representations and deductive techniques" (page 40).

He argues that rules, which have the form IF condition THEN action, are "very similar" to logical conditionals, but they are simpler and have greater psychological plausability (page 51). Among other differences between logic and rules, he argues that logic uses deduction, but rules use search (page 45) and can be used to reason either forward or backward (page 47). Sentences in logic "have to be interpreted as universally true", but rules can be defaults, which admit exceptions (page 44). He does not observe that all of these features of rules apply to logic programming systems.

See also

Related Research Articles

Knowledge representation and reasoning is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medical condition or having a dialog in a natural language. Knowledge representation incorporates findings from psychology about how humans solve problems, and represent knowledge in order to design formalisms that will make complex systems easier to design and build. Knowledge representation and reasoning also incorporates findings from logic to automate various kinds of reasoning, such as the application of rules or the relations of sets and subsets.

Logic programming is a programming, database and knowledge-representation and reasoning paradigm which is based on formal logic. A program, database or knowledge base in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

Prolog is a logic programming language that has its origins in artificial intelligence and computational linguistics.

Planner is a programming language designed by Carl Hewitt at MIT, and first published in 1969. First, subsets such as Micro-Planner and Pico-Planner were implemented, and then essentially the whole language was implemented as Popler by Julian Davies at the University of Edinburgh in the POP-2 programming language. Derivations such as QA4, Conniver, QLISP and Ether were important tools in artificial intelligence research in the 1970s, which influenced commercial developments such as Knowledge Engineering Environment (KEE) and Automated Reasoning Tool (ART).

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical rather than mathematical induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.

In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form that gives it useful properties for use in logic programming, formal specification, universal algebra and model theory. Horn clauses are named for the logician Alfred Horn, who first pointed out their significance in 1951.

<span class="mw-page-title-main">Symbolic artificial intelligence</span> Methods in artificial intelligence research

In artificial intelligence, symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence research that are based on high-level symbolic (human-readable) representations of problems, logic and search. Symbolic AI used tools such as logic programming, production rules, semantic nets and frames, and it developed applications such as knowledge-based systems, symbolic mathematics, automated theorem provers, ontologies, the semantic web, and automated planning and scheduling systems. The Symbolic AI paradigm led to seminal ideas in search, symbolic programming languages, agents, multi-agent systems, the semantic web, and the strengths and limitations of formal knowledge and reasoning systems.

The Fifth Generation Computer Systems was a 10-year initiative begun in 1982 by Japan's Ministry of International Trade and Industry (MITI) to create computers using massively parallel computing and logic programming. It aimed to create an "epoch-making computer" with supercomputer-like performance and to provide a platform for future developments in artificial intelligence. FGCS was ahead of its time, and its excessive ambitions led to commercial failure. However, on a theoretical level, the project was a strong stimulus for the development of concurrent logic programming.

In the field of artificial intelligence, an inference engine is a component of an intelligent system that applies logical rules to the knowledge base to deduce new information. The first inference engines were components of expert systems. The typical expert system consisted of a knowledge base and an inference engine. The knowledge base stored facts about the world. The inference engine applied logical rules to the knowledge base and deduced new knowledge. This process would iterate as each new fact in the knowledge base could trigger additional rules in the inference engine. Inference engines work primarily in one of two modes either special rule or facts: forward chaining and backward chaining. Forward chaining starts with the known facts and asserts new facts. Backward chaining starts with goals, and works backward to determine what facts must be asserted so that the goals can be achieved.

Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more.

<span class="mw-page-title-main">Logic in computer science</span> Academic discipline

Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas:

<span class="mw-page-title-main">Robert Kowalski</span> British computer scientist (born 1941)

Robert Anthony Kowalski is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent most of his career in the United Kingdom.

A deductive database is a database system that can make deductions based on rules and facts stored in its database. Datalog is the language typically used to specify facts, rules and queries in deductive databases. Deductive databases have grown out of the desire to combine logic programming with relational databases to construct systems that support a powerful formalism and are still fast and able to deal with very large datasets. Deductive databases are more expressive than relational databases but less expressive than logic programming systems such as Prolog. In recent years, deductive databases have found new application in data integration, information extraction, networking, program analysis, security, and cloud computing.

Negation as failure is a non-monotonic inference rule in logic programming, used to derive from failure to derive . Note that can be different from the statement of the logical negation of , depending on the completeness of the inference algorithm and thus also on the formal logic system.

A "production system" is a computer program typically used to provide some form of artificial intelligence, which consists primarily of a set of rules about behavior, but it also includes the mechanism necessary to follow those rules as the system responds to states of the world. Those rules, termed productions, are a basic representation found useful in automated planning, expert systems and action selection.

A deductive language is a computer programming language in which the program is a collection of predicates ('facts') and rules that connect them. Such a language is used to create knowledge based systems or expert systems which can deduce answers to problem sets by applying the rules to the facts they have been given. An example of a deductive language is Prolog, or its database-query cousin, Datalog.

In information technology a reasoning system is a software system that generates conclusions from available knowledge using logical techniques such as deduction and induction. Reasoning systems play an important role in the implementation of artificial intelligence and knowledge-based systems.

Concurrent logic programming is a variant of logic programming in which programs are sets of guarded Horn clauses of the form:

Logic programming is a programming paradigm that includes languages based on formal logic, including Datalog and Prolog. This article describes the syntax and semantics of the purely declarative subset of these languages. Confusingly, the name "logic programming" also refers to a specific programming language that roughly corresponds to the declarative subset of Prolog. Unfortunately, the term must be used in both senses in this article.

References

  1. ↑ Crina Grosan; Ajith Abraham (29 July 2011). Intelligent Systems: A Modern Approach. Springer Science & Business Media. pp. 149–. ISBN   978-3-642-21004-4.
  2. ↑ Sin-Wai Chan (13 November 2014). Routledge Encyclopedia of Translation Technology. Routledge. pp. 454–. ISBN   978-1-317-60815-8.
  3. ↑ "What is a rule-based system?". j-paine.org.
  4. ↑ Cabitza, F., & Dal Seno, B. (2005). "DJess-A Knowledge-Sharing Middleware to Deploy Distributed Inference Systems". International Journal of Computer and Information Engineering. 2: 66–69. doi:10.1109/PERSER.2005.1506416. S2CID   27323155.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  5. ↑ Maier, D., Tekle, K.T., Kifer, M. and Warren, D.S., 2018. Datalog: concepts, history, and outlook. In Declarative Logic Programming: Theory, Systems, and Applications (pp. 3-100).
  6. ↑ Tärnlund, S.Å. (1977). "Horn clause computability". BIT Numerical Mathematics . 17 (2): 215–226. doi:10.1007/BF01932293. S2CID   32577496.
  7. ↑ Andréka, H.; Németi, I. (1978). "The generalised completeness of Horn predicate-logic as a programming language". Acta Cybernetica. 4 (1): 3–10.
  8. ↑ Thagard, Paul (2005). Mind: Introduction to Cognitive Science. The MIT Press. p. 11. ISBN   9780262701099. https://www.google.co.uk/books/edition/Mind_second_edition/gjcR1U2HT7kC?hl=en&gbpv=1&pg=PP11&printsec=frontcover
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.