Laurea in INFORMATICA Laurea in INFORMATICA MAGISTRALE MAGISTRALE

1

Knowledge-based and Expert Systems Knowledge-based and Expert Systems Development: languages and environments Development: languages and environments

Expert Systems in Prolog Expert Systems in Prolog

Laurea in INFORMATICA Laurea in INFORMATICA

MAGISTRALE MAGISTRALE

Corso di

ARTIFICIAL INTELLIGENCE Stefano Ferilli

Questi lucidi sono stati preparati per uso didattico. Essi contengono materiale originale di proprietà dell'Università degli Studi di Bari e/o figure di proprietà di altri autori, società e organizzazioni di cui e' riportato il riferimento. Tutto o parte del materiale può essere fotocopiato per uso personale o didattico ma non può essere distribuito per uso commerciale. Qualunque altro uso richiede una specifica autorizzazione da parte dell'Università degli Studi di Bari e degli altri autori coinvolti.

“You were right, but it is worth nothing if you cannot explain it”

Dr. House

Knowledge-based Agent

●

Starts with general knowledge of the world and of its own actions

●

Uses logic reasoning to

●

Maintain a description of the world which is consistent with the arrival of new perceptions

●

Deduce a sequence of actions that will lead to attaining of its objectives

Knowledge-based Systems (1980)

●

Systems that are able to solve problems in a limited domain but with performance that is similar to that of a human expert of the same domain

●

Usually consider a large number of possibilities and dynamically builds a solution

●

“The power of an intelligent program in solving a problem primarily depends on the quantity and quality of knowledge it has on such a problem”

–

[Feigenbaum]

Knowledge-based Systems

●

Program =

●

NOT a set of immutable statements representing the solution to the problem

●

BUT an environment in which

–

Representing

–

Using

–

Modifying a knowledge base

●

Properties

–

Generality

–

Explicit representation of knowledge

–

Reasoning mechanisms

–

Ability to explain

–

Ability to operate in ill-structured domains

Expert System

●

Program that behaves like a (human) expert for a given problem

●

Knowledge-based system that

●

Carries out a task like a human expert would

●

Can explain the exploited reasoning mechanism

●

Knowledge base made up of a domain knowledge representation produced by an expert

●

Representation of expert knowledge and reasoning mechanisms (rules)

●

Often private, non-formalized knowledge

Expert System

●

“The first caution consists in making more explicit the process of interpreting behavioral clues”

●

[Paul Ekman]

Expert Systems

●

Features

●

Exploiting a knowledge base on a specific domain for solving problems related to that domain

●

Make explicit and explain decisions taken and underlying reasoning

●

Uses

●

Analysis

–

Classification

●

Synthesis

–

Deduction of new knowledge starting from the available one

Expert Systems

●

Example

●

An expert system about animals, trying to identify the species to which an animal belongs

–

User answers are in bold, system’s output is in italics

●Question, please –Peter is a tiger

●Is it true: Peter has hair?

–Yes

●Is it true: Peter eats meat?

–No

●Is it true: Peter has sharp teeth?

–Yes

Expert Systems

●

An example (cont.)

●Is it true: Peter has claws?

–Why?

●To understand through rule 3, if Peter is carnivore To understand, through rule 4, if Peter is a tiger This was your question.

●Is it true: Peter has claws?

–Yes

●Is it true: Peter has frontal eyes?

–Yes

●Is it true: Peter is reddish brown?

–Yes

●Is it true: Peter has black stripes?

–Yes

●(Peter is a tiger) is true

Would you like to see how did I deduce it?

–Yes

Expert Systems

●Peter is a tiger

was deduced, through rule 5, from Peter is a carnivore

was deduced, through rule 3, from Peter is a mammal

was deduced, through rule 1, from Peter has hair

I was told AND

Peter has sharp teeth I was told AND

Peter has claws I was told AND

Peter has frontal eyes I was told AND

Peter is reddish brown I was told AND

Peter has black stripes I was told

Expert Systems

●

Functional schema

Knowledge Base

Inference Engine

User Interface

Working Memory

Linguistic Module Shell

Expert Systems

●

Knowledge Base

●

General knowledge about the domain

–

~ long term memory in humans

●

Typically includes rules in the form

“consequent IF antecedent”

–

Consequent includes one or more actions on the working memory

●2 possible actions –Adding a fact –Removing a fact

●

Working memory

●

Specific knowledge on the case under consideration

–

~ short term memory in humans

●

Typically includes facts

Expert Systems

●

Interface

●

Interaction between users and systems through a language akin to the application domain language

●

Interactive use of the system

●

Linguistic Module

●

Must explain the underlying reasoning

–

Explaining HOW

●Reasoning followed to reach a conclusion –

Explaining WHY

●Relevance of a required information for the reasoning –

Content of Short Term memory

●To let the user study and/or modify it

Inference

●

Process used to obtain new knowledge from the acquired information

●

Inference Engine

●

Matches facts in the working memory with facts in the knowledge base

●

To find a satisfactory/optimal solution to a problem

Comparison to Human Experts

●

Human Expert

●

Short Term memory

●

Long Term memory

●

Reasoning

●

Advised person

●

Expert System

●

Working Memory

●

Knowledge Base

●

Inference Engine

●

User

Comparison to Traditional Systems

●

Program

●

Numeric

●

Algorithms

●

Integrated information and control

●

Difficult to modify

●

Precise information

●

Command-based interface

●

Final result

●

Optimal solution

●

Expert System

●

Symbolic

●

Heuristic

●

Knowledge separated from control

●

Easy to modify

●

Uncertain information

●

Natural dialogue with explanations

●

Recommendation with explanations

●

Acceptable solution

Search Strategy

●

Approaches

●

Backward

–

Start from the goal

–

Apply the rules backward

–

Until obtaining a working memory with the facts that describe the problem

●

Forward

–

Place in the working memory the facts that describe the problem

–

Search rules whose antecedent is satisfied

–

Choose one and apply actions in its consequent, adding or removing facts from the memory itself

–

Terminate search when goal appears in the working

memory

Implementation

●

KBS development tools

●

The development of systems for specific applications usually implies a symbolic (and then numeric) quantification of known relationships among the entities involved in the model of the system

–

Traditional programming

●The task of developing algorithms is usually fundamental and of primary importance

–

Development of KBS

●The effective processing of typically large amounts of data (often tending to increase) is a relevant issue

Programming

–

Conventional

●Bits, bytes, number, functions, formatted outputs

●Procedural algorithms to solve problems

●Definite sequences of steps to get to a solution

●Complete deterministic conclusion

●Data types: numbers, characters

●Pre-declared variables and types (Pascal)

●Fixed-size variables

●Exact representation of information

●Exact/precise outcomes

–

In AI

●Symbols, concepts, rules, relationships

●Descriptive languages (for known facts and relationships)

●Search/heuristics to find a solution

●Unknown if algorithms converge

●Data types: atoms, objects, lists

●Declaring variables and types useless (variables can be created during solution process)

●Size of data structures may expand or shrink

●Imprecise representation of information

●Any satisfactory outcome

Desirable AI Software Capabilities

●

[R.J. Schalkoff “Artificial Intelligence: an engineering approach”,1990]

●

“The ability to develop models and reasoning mechanisms incrementally, by decomposing the problem solution into smaller, interrelated solution units.

●

Flexible control structures to facilitate

–

(a) goal-directed programming.

(b) data-directed programming.

(c) recursion, etc.

–

(d) parallel programming.

●

Interactive system communication capability.

Desirable AI Software Capabilities

●

Debuggers that facilitate program checking, particularly with respect to unification, recursion, etc.

●

Built-in list or other symbolic data representation facilities, and the means to extend these

representations into complex knowlegde structures (frames).

●

Pattern matching facilities.

●

Variable binding strategies such and trial and error solution approaches are facilitated.”

Tools for Knowledge-based Systems Implementation

Certain languages are specifically designated for the purpose of creating intelligent systems. Among other important characteristics, these languages facilitate symbolic manipulation.

Languages

Expert systems and expert system shells

A specialized tool for creating intelligent systems.

The characteristics of specialization include the type of knowledge representation (rules) and the paradigm implemented by the expert system.

Tool Class Description Examples Class Function

LISP Prolog Smalltalk

Implementing intelligent systems

M.4 (an embeddable expert system shell), OPS EXSYS (standalone expert system shell)

Implementing rule-based expert systems

Tools for Knowledge-based Systems Implementation

Prolog (logic- based knowledge representation) KL-ONE (and its successors) – a noncommercial inheritance network

Representing various kinds of knowledge contained in and used by an intelligent system These are tools used to

represent symbolic data- specifically data used to represent knowledge.

Knowledge representation systems typically are part of systems that reason with knowledge.

Knowledge representation tools

Tool Class Description Examples Class Function

Multiparadigm programming environments

Provide a set of software modules that allow the user to mix a number of different styles of programming

KEE, LOOPS, KnowledgeCraft ART KAPPA CLIPS JESS

Mixing four programming paradigms within a message-passing architecture to implement intelligent systems

Implementation of Knowlege-based Systems

●

Languages

●

So-called “logic” programming languages basically

–

Allow to set a series of constraints to which the solving method must comply,

–

but do not determine it a-priori, nor provide for it totally

●

The program will decide during execution how to operate, albeit with the descriptions indicated by the programmer when writing the code

●

2 typical examples

–

Lisp

–

Prolog

●

While of the same type, they are completely different

Implementation of Knowlege-based Systems

●

Languages

●

Pattern Matching

–

Variables are only in the pattern, not in the components of the status

●

Unification

–

Variables may be both in the pattern and in the components of the status

●

The former is a particular case of the latter

Lisp

●

[John McCarthy, late 50s]

●

Basic concepts

–

Ancestor of functional programming languages

●Inspired by recursive functions and lambda calculus –

Interpreted

–

Based on a recursive and incremental approach

–

Dynamic data structures

–

Procedures handled as data

●

Basic notions

–

Combination of primitive expressions in composite expressions

–

Abstraction: composite objects named and handled as units

Lisp

●

Allows recursion and can overwrite its own code

–

Self-updating

●

To answer questions of arbitrary complexity

–

Dynamically reallocates data in the memory

–

Gets back reusable space through garbage collection

●Reduces the problem of shortage of storage that takes place with other languages when dealing with “open-ended” problems –

So is carried out also the automatic management of the

stack

Lisp

●

Main data structure: binary tree

●

Abstract object useful in most typical data in AI

●

Data types

Lists

S - expressions

Floating point Integer Non-empty list Empty list

Atoms

Symbols Numbers

Lisp

●

Based on the evaluation of logistic

–

true/false or parametric

–

Return the result of the operation expressions

●

Handles search in binary trees

–

Particularly powerful in handling lists

●Comparison, appending, extraction, etc.

Lisp

●

Available functionality origin from a set of primitives implemented in machine language

●

Additionally, user-defined functions in terms of such primitives are available

●

Operators provided

–

Selection, construction, modification, recognition

–

Logic comparators, assignment operators, arithmetical, input/output, evaluation, application of parametrized functions

Lisp

●

Example

–

Problem

●Define a procedure that takes 3 numbers as arguments and returns the sum of squares of the two largest numbers –

Solution

●> (defun sos-greatest (x y z) (cond ((and (< x y) (< x z)) (sum-of-squares y z)) ((and (< y x) (< y z)) (sum-of-squares x z)) (else

(sum-of-squares x y)))))

Prolog

●

[Kowalski & Colmerauer, late ’70s]

●

Logic programming

–

Based on absolute (facts) and conditional (rules) assertions

●It can be a non-trivial problem examining a specific rule and a given state of the problem and determining whether the preconditions of the rule are satisfied

–

Automatically generates the search tree starting from a user query (goal), by evaluating the unknown parameters appearing in the assertions

●Much search needed to discover whether a particular situation and the preconditions of a rule match (unify)

–

Execution returns the search result, if it involves a finite number of steps

●

Interpreted

●

Data structure: list

Building Expert Systems

●

2 types of development tools (Shell)

●

Skeleton

–

Inference engine and interface taken from an existing expert system, deprived of the specific knowledge related to the application domain

●“Skeleton” derived by a specific methodology –

More immediate, less flexible

●

Environment

–

General-purpose environments that allow to create both the interface and the reasoning mechanism

●Provides a language for knowledge representation, offers guarantees of adaptability and openness towards the underlying system

–

More flexible, but also more complex

Building Expert Systems

●

Skeleton Shells

●

Expert System – Skeleton = Domain-specific knowledge

–

Derived from existing expert systems

–

Closed and complete system, also as to the user interface

–

Operate in their original environment

–

Unique and non-adaptable formalism

–

Available reasoning and control mechanism suggest their use in applications that are similar to the original one

●

Extremely easy to use: allow

–

Rule elicitation through very simple meta-languages

–

(sometimes) Forms of probabilistic reasoning and Bayesian inference

–

Transparency of reasoning

Building Expert Systems

●

Skeleton Shells

●

“Abstractions” on one or many application programs

●

Not suitable for all tasks

–

Limited by a specialized architecture for the solution of a specific problem

●Diagnosis and classification vs planning, problem decomposition, constraint satisfaction, etc.

●

Advantage associated to simplicity of the

knowledge representation language may generate

disadvantages

Building Expert Systems

●

Skeleton Shells

●

Some examples

–

EMYCIN (1980)

●Derived from MYCIN, oriented to medical diagnosis –

KAS (1979)

●Derived from PROSPECTOR, an expert system for mineralogic prospections

–

EXPERT (1979)

●Derived from CASNET, expert system in medical diagnosis, through models of disease (Causal Associational Network) –

Many many others, usually based on production rules

●MICROEXPERT, EXSYS, 1st-CLASS, ESP ADVISOR, SAGE X_i PLUS, PERSONAL CONSULTANT, EXPERT-EDGE, RAINBOW, AL/X, Expert Systems Environment, &c.

Expert Systems

●

Criticisms to EMYCIN [Aitkins, 1983]

●

Its production rule formalism cannot distinguish different types of knowledge

–

Heuristic, control, etc.

●

The set, unstructured, of rules generated means keeping under control, when adding a new rule, the possibility of applying changes everywhere in the system

●

Exhaustive backward chaining used as reasoning and inference scheme, both at the meta-rule level and at the base rule level, make explanations difficult and heavy

Expert Systems

●

Other criticisms to EMYCIN

–

Run time interface

●Consultation is question-driven, driven by the system with scarce intervention from the user

●The explanation system describes rather than explaining the reasoning models

–

Build time interface

●Access to the knowledge base is limited

●The knowledge engineer may access one rule at a time

●

These criticisms can be generalized to all shells distinguishing building and running modes (efficient but unsuitable)

–

Ideally, it should be possible to run the inference engine while building the system, and access the knowledge base while consulting it, for check or experimental purposes

Expert Systems

●

Further criticisms to shells

●

Uncertainty handling

●

Often they provide formalisms for inexact reasoning, but

–

Do not provide appropriate information about consistency with the theory of probabilities

–

Cannot distinguish between used theories

●Certainty factors, belief factors, possibilities, etc.

–

Do not allow one to check the existence of preconditions for applicability of the theory

Expert Systems

●

Environment systems

–

Provide a support for quick prototyping

–

Run time and Building time interfaces are very close

●The code may run and be tested incrementally

–

User interface not so friendly as for skeleton systems

–

Provide the programmer more freedom than Skeleton systems in

●specifying the control regime

●dealing with uncertainty –

Limitations

●E.g., the dynamic memory of the OPS family is limited to vectors in the working memory

–Recursive data structures excluded

–Control structures such as recursion and iteration are difficult to implement

–The recognize-act cycle is computationally heavy

●

Development Environments for Production Systems

●

OPS family

PAS

PSG

PSS

GRAPES

PSNLST OPS OPS2 OPS4

PRISM PRISM2

ACT* CAPS

ACTE ACTF

OPS3 OPS5 OPS83

SOAR SOAR2

XAPS XAPS2

OPS6 CLIPS

–

PSG [Newell, McDermott 1975]

●Defined a whole class of architectures

–A queue model of the working memory with elements stored in an ordered list

–

PSNLST [Richener, 1976]

●Added a conflict resolution method based on “recency”, a dynamic reordering of productions based on the number of times in which the rules appeared in the “match list”

–

OPS [Forgy, McDermott 1976]

●Based on an important pattern matcher (RETE)

●The working memory is assumed to be limited

●Several conflict resolution strategies have been tried –

OPS 5

–

OPS 83

–

CLIPS

The OPS family uses FORWARD CHAINING reasoning

Expert Systems Development

●

Phases

●

Definition

●

Knowledge Acquisition

●

Design

●

Test

●

Documentation

●

Maintenance

Expert Systems Development

●

Conventional Programming

●

Focuses on the solution

●

Programmer works alone

●

Sequential development

●

Expert System

●

Focuses on the problem

●

Team work

●

Iterative development

Expert Systems Development

●

Players

–

Domain Expert

●Has expert knowledge

●Has competences in efficient problem solving

●Knows how to communicate knowledge

●Can devote time

●Is not hostile –

Knowledge Engineer

●Has competences in knowledge engineering

●Has good communication competences

●Knows how to associate a problem to the software

●Has competences in expert systems programming –

Final user

●Can help in defining the interface specifications

●Can help in knowledge acquisition

●Can help in system development

Knowledge Engineer

●

Main responsibilities

●

Problem definition

●

Interviewing the expert

●

Identifying the concepts

●

Organizing knowledge

●

Identifying problem solving methods

●

Choose software

●

System coding

●

System testing

●

System revision

●

Integration of the system in the place of exploitation

●

System maintenance

Kinds of Knowledge

●

Public

●

Private

●

Procedural

–

How to solve a problem

●

Declarative

–

What is known about a problem

●

Meta-knowledge

–

Knowledge about knowledge

●Other kinds of knowledge and how to use them

●

Heuristic

–

Shallow Knowledge

●

Structural

–

Knowledge structures

Procedural Rules Strategies Agendas Procedures Declarative Concepts

Objects Facts

Meta-knowledge Knowledge About the Other Types of Knowledge Heuristics Rules of Thumb Structural Rule sets

Concept relationships Relationships between concepts and objects

Knowledge Selection

●

Established knowledge

●

Public

●

Declarative and Procedural

●

Norms

●

Private

●

Experimental knowledge

●

Extracted from data (inductive algorithms)

●

Extracted by instrumental tests

–

Must be validated

Knowledge Acquisition

●

“Knowledge Acquisition consists of elicitation and interpretation of data on the functioning of expertise in some domain, in order to design, build, extend, adapt or modify a knowledge based (expert) system.

●

In this view, knowledge acquisition is a permanent and crucial activity throughout all stages of designing, implementing and maintaining an expert system.”

●

[Wielinga et al, 1986]

Knowledge Acquisition

●

Thinking Aloud

●

The expert speaks aloud, explaining in detail his reasoning about a case

●

Interview

●

The knowledge engineer asks questions about a specific case

●

Cross-examination

●

The engineer and the expert talk together about a case

Knowledge Representation

●

Techniques

●

<Object, Attribute, Value> triples

●

Rules

●

Semantic nets

●

Frames

●

Logics

References

●

F. Hayes-Roth, D.A. Waterman, D.B. Lenat (Eds.) “Building Expert Systems”, Addison- Wesley, 1983

●

M. Stefik: “Introduction to Knowledge Systems”, Morgan Kaufmann, 1995

●

Durkin J.: “Expert Systems design and development”, Macmillan, 1994

●

Jackson: “Introduction to Expert Systems”, 3 ed, Addison-Wesley

Prolog for Building Expert Systems

●

Development tool of type “Environment”

●

Partially useful as-is to enter and consult knowledge bases

–

Backward chaining reasoning strategy

●Other strategies may be more appropriate –

Final answer to queries

●Explanation of reasoning may be required –

Strictly true/false nature

●Knowledge may be available only with some degree of certainty

●

Allows to implement other strategies

–

General-purpose programming language

Development Phases

●

Knowledge Representation

●

Choosing and defining formalism

●

Designing an inference engine to exploit it

●

Add tools for interacting with the user

●

Add tools to handle specialized features

–

E.g., uncertainty

●

Design

●

Define intended behavior

●

Outline reasoning process

●

Answer ‘why’ questions

●

Answer ‘how’ questions

Reasoning Process

–

To find an answer R to a question D

●Simplification: only True/False answers allowed –

Use first applicable principle among:

●If D is available as a fact in the KB, then R = “D is true”

●If a rule of type “IF condition then D” is available in the KB, then check condition and use result to build answer R to question D

●If D can be asked to the user, then ask the user about D

●If D = “D1 and D2”, then –explore D1

–If D1 is false, then R = “D is false”

–Else, explore D2 and combine answers to D1 and D2 in R

●If D = “D1 or D2”, then –explore D1

–If D1 is true, then R = “D is true”

–Else, explore D2 and combine answers to D1 and D2 in R

●If D = “ not D’ ”

–Apply the adopted interpretation for negation

●Be careful in order to avoid getting wrong answers

User Interaction

●

Request for information

●

Questions, possibly with simple answers

–

Values

–

Binary

●“Yes” should let the system go ahead in exploring the current hypothesis

●“No” should cause the system to explore alternate paths

●

Questionnaire/menu

–

Including basic questions or questions that are strictly inter-related

●Typically (but not only) at the beginning

●Useful to address towards a set of hypotheses rather than another

User Interaction

●

Explanation of operations

●

Why a given question

–

Usefulness

●Unclear link of the question to the problem

●Answering would require significant effort –

Explanation

●Minimal: generic answer for each possible question

–More practical solution, BUT same question might be asked in different moments and with different objectives

●Explaining reasoning process linking the question to the original goal

–Smarter solution BUT requires to keep track of the reasoning carried out so far

●

How an answer was found

–

Allows to check validity

●Requires to keep track of the reasoning carried out so far (all

“converging” paths that led to that conclusion)

System Procedures

●

expert -> the main

–

Reads the user question

–

Starts reasoning mechanism to find a (positive or negative) answer to such a question

–

Asks the user if he wants to know more possible answers, if any

●

explore(Goal, Trace, Answer)

–

Exploits the knowledge base to search for an answer to the question

●Goal: the question

–Combination of conjunctions and/or disjuctions of simple claims

●Trace: the chain of goals and rules between the current goal Goal and the initial goal

–Allows to answer questions about why the current goal is being investigated

●Answer: the answer to the current goal Goal

–In the form of a proof tree, to answer a “how”-type question

System Procedures

●

useranswer(Goal, Trace, Answer)

–

Alternative to procedure ‘explore’

●In case the knowledge base does not contain sufficient information to obtain answer Answer to the current goal Goal, it asks it, if possible, directly to the user

–

Same objectives <=> same arguments

●Trace: allows to answer at a “why”-type question, in case –

Tries, as far as possible, to abstract away from the

specific expression used by the user

●

present(Answer)

–

Shows the user the answer Answer to his initial question,

and in case also how it did reach it

Uncertainty

●

Prolog has a strict true/false nature

●

Each element in the reasoning is true or false (tertium non datur)

–

In some contexts, need for associating “probabilities” to knowledge items

●

Embedding uncertainty handling into Prolog

●

Assigning a degree of likelihood to each knowledge element

●

Defining the way in which such probabilities combine with each other and evolve when exploited by the reasoning process

Uncertainty

●

A degree of likelihood may be assigned to each known fact or rule

●

2 possibilities

–

Strict concept, as in mathematical theory

●More theoretical foundation

–

“Subjective”, intuitive, informal confidence in a claim being true or in an inference rule being applicable

●Simpler and more efficient to implement

●More similar to those actually used by humans

●

Still under discussion which is the most appropriate

Uncertainty

●

Expressing degrees of likelihood

●

Finite set of discrete descriptors

●

A number within a given range of values

–

E.g., classical [0,1]; MYCIN [-1,+1]

●

Associating the degree of likelihood to knowledge items

●

Facts: additional argument?

●E.g.: p(a,b)  p(a,b,0.7)

●

Rules: reserved predicate, having such a value as its argument?

●E.g.: h(X) :- p(X,Y), q(Y)  h(X) :- p(X,Y), q(Y), prob(0.8).

Uncertainty

–

A simple but effective schema for combining probabilities

●Usually knowledge elements are not independent –

c(X)  [0,1] the probability of a knowledge item X

–

Facts: P1, P2

●c(P1 and P2) = min(c(P1), c(P2))

–Must be both true -> the probability of the result is affected by the weaker one

●c(P1 or P2) = max(c(P1), c(P2))

–It suffices that one is true -> they may be regarded as being interchangeable -> the result takes the value of the stronger one

●c(not P1) = (1 – c(P1))

–Similar to the mathematical theory: the probability of the opposite is the complement of the probability –

Rule: “R = if P1 then P2”

●c(P2) = c(P1) * c(R)

–Probability of condition, weighted with the probability of the rule itself to obtain the probability of the consequent

Uncertainty

●

Another approach

–

Given a hypothesis H to verify, and evidence E collected to confirm it, modeling the possibility that E changes the expectation of H using 2 parameters

●N = necessity factor (“how necessary E is to H”) –If E is false, the lower N, the less probable H

●S = sufficiency factor (“how sufficient E is to H”) –If E is true, the higher S, the more probable H –

If the probability of E is in between certainty and

impossibility, the probability of H will be determined by interpolation between the following extreme cases

●E is known to be false

●E is known to be true

●Nothing is known about E

–

H has an a-priori likelihood, that is changed as long as new knowledge is acquired

Control strategy

●

Changing the standard Prolog strategy

●

Hybrid rule cycle involving backward and forward chaining

–

Simpler to implement

●

Pure forward

●

Note: for the sake of simplicity, we will suppose

that rules do not contain negated literals

Control strategy

●

Hybrid cycle

●

Transform each rule h :– b

, ..., b

of the program

–

Add a literal asserta(h) at the end of the body

–

Add a literal not(h) at the beginning of the body

–

Replace the head with a fresh dummy predicate

●not already used in the program

●

Example

●a :- b.  dummy :- not(a), b, asserta(a).

●b :- d, e, f.  dummy :- not(b), d, e, f, asserta(b).

Control strategy

●

Hybrid cycle

●

Rules never call each other

–

Even if intermediate predicates are present

●

Main = loop : Repeat

–

Evaluate all rules in sequence

until reaching a predefined stop condition

–

Typically, the solution to the problem

Control strategy

●

Pure forward chaining

●

Search and progressively remove from the left- hand-side of rules literals that turn out to be true in the knowledge base

–

Transform head and body of each rule into arguments of a meta-predicate rule/2

●The body translates into a list

–Allows to exploit Prolog procedures member and delete –

Express each fact as the argument of a meta-predicate

fact/1

●

Example

●p(a,b).  fact(p(a,b)).

●a :- b,c.  rule(a, [b, c]).

●g(X) :- p(X, Y), not(f(Y)).  rule(g(X), [p(X, Y), not(f(Y))]).

Control strategy

●

Pure forward chaining

●

Main = loop: while possible

–

Read a fact, delete it from the body of all rules including it and

●If all literals of the body have been deleted –Replace the rule with a new fact equal to its head

●Otherwise

–Replace the new rule so-obtained to the previous one

●

A used fact must not be reconsidered

–

Remove it as soon as it is used but it is still relevant knowledge

–

Reassert it using a meta-predicate usedfact

●

In the end, all conclusions obtained from the knowledge base will be in the form of facts or usedfacts

Efficiency

●

Important issue for the success of a system

●

Several evaluation parameters

●

Several kinds of solutions

●

Predicate indexing

●

Prolog automatically indexes clauses based on their head predicate; sometimes, however, a different approach might be more useful

–

e.g., in forward chaining, indexing predicates in the body

●

Meta-predicate rules/2

–

First argument: index value

–

Second argument: list of rules having such value

–

Disadvantage: redundancy (one rule might be associated to many indexes at the same time)

Meta-rules

●

Prolog uses candidate rules in the order they are specified by the programmer

●

Sometimes a more complex strategy might be more appropriate

–

Might require more time

●

Meta-predicate prefer/4

–

Arguments: head and body of each of the two clauses to be compared

–

Implements the chosen evaluation function

Comments and Further Developments

●

Lack of declarative clarity

●

Negated goals

●

Improvements

●

Cyclic goals

●

Browsing of the proof tree

●

Making explicit the rules used

●

Improve dialogue with the user

●

Optimize search

–

Request-length

Example: designing knowledge

●

AND-OR graphs

●

Nodes = concepts

●

Arcs = preconditions

●

And = rule precondition

I₃ I₄ I5

H₂

H_j

H₁

H_j H_m

H₁

H_m I₁

I₂ H₁

Diagnosis of jaundice-related diseases Jaundice present

Franc jaundice Scleral jaundice

Fever? Fever?

Young patient? (1) Young patient?

History of alcohol abuses? Stress or fasting in the last period?

Increased liver volume?

Increased spleen volume?

Gilbert’s syndrome Alcoholic cirrhosis

yes no

no

no

yes yes yes

yes

Fatigue (Asthenia)?

yes

Dyspeptic disorders?

yes

Increase in liver volume?

Acute viral hepatitis

no

Frequent pains at level of upper- right quadrant before jaundice?

yes

Pain at level of cholecystis?

yes Cholecystitis (Cholangitis)‏

(1)

/* Top-level diagnosis rules */

diagnosis('Gibert’’s Sindrome')‏ :- scleral_jaundice, askifnot(has(fever)‏)‏, stress_fasting.

diagnosis('Acute viral hepatitis')‏ :- franc_jaundice, askif(has(fever)‏)‏, askif(young)‏, askif(fatigue)‏, askif(dyspepsia)‏, askif(growth_liver)‏.

diagnosis('Cholecystitis')‏ :- franc_jaundice, askif(has(fever)‏)‏, askifnot(young)‏, askif(frequent_pain)‏, askif(cholecystis_pain)‏.

diagnosis('Alcoholic cirrhosis’)‏ :- franc_jaundice, askifnot(has(fever)‏)‏, askifnot(young)‏, askif(alcohol)‏, askif(growth_liver)‏, askif(growth_spleen)‏.

diagnosis('The patient does not show any of the diseases recognized by the system')‏.

scleral_jaundice :- askif(yellow_eyes)‏, askifnot(yellow_skin)‏.

franc_jaundice :- askif(yellow_eyes)‏, askif(yellow_skin)‏.

stress_fasting :- askif(stress)‏ . stress_fasting :- askif(fasting)‏.

middle_old_age :- askifnot(young)‏.

/* Question decoding */

questioncode(yellow_eyes,'Has the patient yellow eyes')‏.

explain(yellow_eyes)‏ :- write(‘I need this to check for presence of jaundice')‏, nl.

questioncode(yellow_skin,'Has the patient also yellow skin’)‏.

explain(yellow_skin)‏ :- write('I need this to distinguish scleral from franc jaundice’)‏, nl.

questioncode(stress,'Does the patient feel stressed in this period')‏.

explain(stress)‏ :- write('Presence of stress suggests Gibert’’s syndrome')‏, nl.

questioncode(fasting,'Did the patient fast in this period')‏.

explain(fasting)‏ :- write('Presence of fasting suggests Gibert’’s syndrome')‏, nl.

questioncode(young,'Is the patient young')‏.

explain(young)‏ :- write('The patient being young or middle- or old-aged leads to examining different diagnoses')‏, nl.

questioncode(fatigue,'Does patient feel asthenia')‏.

explain(fatigue)‏ :- write('Presence of fatigue in the patient might be a clue of acute viral hepatitis')‏, nl.

questioncode(dyspepsia,'Did the patient have dyspeptic ailment')‏.

explain(dyspepsia)‏ :- write('Presence of dyspeptic ailment might be a clue of acute viral hepatitis')‏, nl.

questioncode(growth_liver,'Was an increase in patient’s liver volume observed')‏.

explain(growth_liver)‏ :- write('Based on previous answers, this information might help in distinguishing hepatitis and cirrhosis from other diseases')‏, nl.

questioncode(frequent_pain,'Did the patient feel frequent pain to upper-right quadrant before jaundice')‏.

explain(frequent_pain)‏ :- write('Franc jaundice, fever and middle- or old-age suggest a cholecystitis, which in this way might be confirmed')‏, nl.

questioncode(cholecystis_pain,'Does the patient feel pain at cholecystis')‏.

explain(cholecystis_pain)‏ :- write('Based on previous symptoms, this would confirm the presence of cholecystitis')‏, nl.

questioncode(alcohol,'Is it known that the patient made abuse of alcohol')‏.

explain(alcohol)‏ :- write('It would a hint toward cirrhosis')‏, nl.

questioncode(growth_spleen, ‘ Was an increase in patient’s spleen volume observed')‏.

explain(growth_spleen)‏ :- write('It is a typical symptom of cirrhosis, together with increase in liver volume, in alcohol abuse histories')‏, nl.

questioncode(has(X)‏,X)‏ :- write('H as the patient ')‏.

explain(has(fever)‏)‏ :- write('Given the presence of franc jaundice, this allows to consider some diagnoses rather than others')‏, nl.

askif(Q)‏ :- ask(Q,A)‏, positive_answer(Q,A)‏.

positive_answer(Q,A)‏ :- affirmative(A)‏.

positive_answer(Qcode,A)‏ :- not(negative(A)‏)‏, not(affirmative(A)‏)‏, write('Please answer yes or no.’)‏, read(A2)‏, retract(asked(Qcode,A)‏)‏, asserta(asked(Qcode,A2)‏)‏, affirmative(A2)‏.

askifnot(Q)‏ :- not(askif(Q)‏)‏.

ask(Qcode,A)‏ :- asked(Qcode,A)‏.

ask(Qcode,A)‏ :- not(asked(Qcode,A)‏)‏, questioncode(Qcode,Q)‏, write(Q)‏, write(‘? ')‏, read(A2)‏, ask2(Q,Qcode,A2,A)‏ .

ask2(Q,Qcode,'why’,A)‏ :- explain(Qcode)‏, ask(Qcode,A)‏.

ask2(Q,Qcode,A,A)‏ :- not(A = ' why')‏, asserta(asked(Qcode,A)‏)‏.

affirmative(yes)‏.

affirmative(y)‏.

affirmative(right)‏.

affirmative(ok)‏.

affirmative(sure)‏.

negative(no)‏.

negative(n)‏.

negative(not)‏.

negative(never)‏.

negative(impossible)‏.