Artificial Intelligence - unit 4

 

Unit IV

 

 

Representing Knowledge Using Rules:

Types of rules are mostly used in the Rule-based production systems.

1)                   Knowledge Declarative Rules :

These rules state all the facts and relationships about a problem.

Example :

IF inflation rate declines

THEN the price of gold goes down. These rules are a part of the knowledge base.

2)                   Inference Procedural Rules

These rules advise on how to solve a problem, while certain facts areknown.

Example :

IF the data needed is not in the system THEN request it from the user.

These rules are part of the inference engine.

3)                     Meta rules

These are rules for making rules. Meta-rules reason about which rules should be considered for firing.

Example :

IF the rules which do not mention the current goal in their premise, AND there are rules which do mention the current goal in their premise, THEN the former rule should be used in preference to the latter.

− Meta-rules direct reasoning rather than actually performing reasoning.

− Meta-rules specify which rules should be considered and in which order they should be invoked.

KR – procedural & declarative versus Declarative Knowledge

ð     Procedural Knowledge : knowing 'how to do'

Includes : rules, strategies, agendas, procedures, models.

These explains what to do in order to reach a certain conclusion.

Example

Rule: To determine if Peter or Robert is older, first find their ages.

 

 

 

It is knowledge about 'how to do' something. It manifests itself in the doing of something, e.g., manual or mental skills cannot reduce to words. It is held by individuals in a way which does not allow it to be communicated directly to other individuals.

Accepts a description of the steps of a task or procedure. It Looks similar to declarative knowledge, except that tasks or methods are being described instead of facts or things.

ð Declarative Knowledge : knowing 'what', knowing 'that'

Includes : concepts, objects, facts, propositions, assertions, models.

It is knowledge about facts and relationships, that It can be expressed in simple and clear statements,

and It can be added and modified without difficulty. Examples : A car has four tyres; Peter is older than Robert.

Declarative knowledge and explicit knowledge are articulated knowledge and may be treated as synonyms for most practical purposes. Declarative knowledge is represented in a format that can be manipulated, decomposed and analyzed independent of its content.

ð Comparison :

Comparison between Procedural and Declarative Knowledge:

Procedural Knowledge Declarative Knowledge

Ø    Hard to debug

Ø    Easy to validate

Ø    Black box

Ø    White box

Ø    Obscure

Ø    Explicit

Ø    Process oriented

Ø    Data - oriented

Ø    Extension may effect stability

Ø    Extension is easy

Ø    Fast , direct execution

Ø    Slow (requires interpretation)

Ø    Simple data type can be used

Ø    May require high level data type

Ø    Representations in the form of sets of rules, organized into routines and subroutines.

Ø    Representations in the form of production system, the entire set of rules for executing the task.

 

Comparison between Procedural and Declarative Language :

Procedural Language Declarative Language

Ø    Basic, C++, Cobol, etc

Ø    SQL

Ø    Most work is done by interpreter of the languages

Ø    Most work done by Data Engine within the DBMS

Ø    For one task many lines of code

Ø    For one task one SQL statement

Ø    Programmer must be skilled in translating the objective into lines of procedural code

Ø    Programmer must be skilled in clearly stating the objective as a SQL statement

Ø    Requires minimum of management around the actual data

Ø    Relies on SQL-enabled DBMS to hold the data and execute the SQL statement .

Ø    Programmer understands and has access to each step of the code

Ø    Programmer has no interaction with the execution of the SQL statement

Ø    Data exposed to programmer during execution of the code

Ø    Programmer receives data at end as an entire set

Ø    More susceptible to failure due to changes in the data structure

Ø    More resistant to changes in the data structure

Ø    Traditionally faster, but that is changing

Ø    Originally slower, but now setting speed records

Ø    Code of procedure tightly linked to front end

Ø    Same SQL statements will work with most front ends Code loosely linked to front end.

Ø    Code tightly integrated with structure of the data store

Ø    Code loosely linked to structure of data; DBMS handles structural issues

Ø    Programmer works with a pointer or cursor

Ø    Programmer not concerned with positioning

Ø    Knowledge of coding tricks applies only to one language

Ø    Knowledge of SQL tricks applies to any language using SQLprogramming offers a formalism for specifying a computation in termsof logical relations between entities.

 

 

•                     logic program is a collection of logic statements.

•                     programmer describes all relevant logical relationships between the various entities.

•                     computation determines whether or not, a particular conclusion follows from those logical statements.

 

 

 

 

 

 

•   Characteristics of Logic program

Logic program is characterized by set of relations and inferences.

− program consists of a set of axioms and a goal statement.

− rules of inference determine whether the axioms are sufficient to ensure the truth of the goal statement.

− execution of a logic program corresponds to the construction of a proof of the goal statement from the axioms.

− programmer specify basic logical relationships, does not specify the manner in which inference rules are applied.

Thus Logic + Control = Algorithms

•   Examples of Logic Statements

− Statement

A grand-parent is a parent of a parent.

− Statement expressed in more closely related logic terms as,

A person is a grand-parent if she/he has a child and that child is a parent.

− Statement expressed in first order logic as(for all) x: grandparent (x, y) :- parent (x, z), parent (z, y) read as x is the grandparent of y if x is a parent of z and z is a parent of y

Programming Language

language includes :

− the syntax

− the semantics of programs and

− the computational model.

There are many ways of organizing computations. The most familiar paradigm is procedural. The program specifies a computation by saying "how" it is to be performed. FORTRAN, C, and Object- oriented languages fall under this general approach.

Another paradigm is declarative. The program specifies a computation by giving the properties of a correct answer. Prolog and logic data language (LDL) are examples of declarative languages, emphasize the logical properties of a computation. Prolog and LDL are called logic programming languages.

PROLOG (PROgramming LOGic) is the most popular Logic programming language rose within the realm of Artificial Intelligence (AI). It became popular with AI researchers, who know more about "what" and "how" intelligent behavior is achieved.

KR – Logic Programming and Terminology (relevant to Prolog programs) language, the formation of components (expressions, statements,etc.), is guided by syntactic rules. The components are divided into two parts: (A) data components and (B) program components.

(A) Data components :

Data components are collection of data objects that follow hierarchy. Data object of any kind is also called

a term. A term is a constant, a variable or a compound term.

Simple data object is not decomposable; e.g. atoms, numbers, constants, variables. Syntax distinguishes the data objects, hence no need for declaring them. Structured data object are made of several components.

 

Forward and Backward Chaining:

Given a set of rules, there are essentially two ways to generate new knowledge: one, forward chaining and the other, backward chaining.

ð    Forward chaining : also called data driven. It starts with the facts, and sees what rules apply.

ð     Backward chaining : also called goal driven. It starts with something to find out, and looks for rules that will help in

answering it.

Forward Chaining

It is a strategy of an expert system to answer the question, “What can happen next?”

Here, the Inference Engine follows the chain of conditions and derivations and finally deduces the outcome. It considers all the facts and rules, and sorts them before concluding to a solution.

This strategy is followed for working on conclusion, result, or effect. For example, prediction of share market status as an

effect of changes in interest rates.

Backward Chaining

With this strategy, an expert system finds out the answer to the question,“Why this happened?”

On the basis of what has already happened, the Inference Engine tries to find out which conditions could have happened in the past for this result. This strategy is followed for finding out cause or reason. For example, diagnosis of blood cancer in humans.

 

Example Rule 1

R1 : KR – forward-backward reasoning ,

IF hot AND smoky THEN fire

Rule R2 : IF alarm_beeps THEN smoky

Rule R3 : IF fire THEN switch_on_sprinklers Fact F1 : alarm_beeps [Given]

Fact F2 : hot [Given]

 

 

■  Example 2

Rule R1 : IF hot AND smoky THEN ADD fire Rule R2 : IF alarm_beeps THEN ADD smoky

Rule R3 : IF fire THEN ADD switch_on_sprinklers Fact F1 : alarm_beeps [Given]

Fact F2 : hot [Given]

 

 

Example Rule KR – forward-backward reasoning

3 : A typical Forward Chaining,

R1 : IF hot AND smoky THEN ADD fire Rule R2 : IF alarm_beeps THEN ADD smoky

Rule R3 : If fire THEN ADD switch_on_sprinklers Fact F1 : alarm_beeps [Given]

Fact F2 : hot [Given]

Fact F4 : smoky [from F1 by R2] Fact F2 : fire [from F2, F4 by R1]

Fact F6 : switch_on_sprinklers [from F2 by R3]

 

 

■  Example 4 : A typical Backward Chaining

Rule R1 : IF hot AND smoky THEN fire Rule R2 : IF alarm_beeps THEN smoky

Rule R3 : If _fire THEN switch_on_sprinklers Fact F1 : hot [Given]

Fact F2 : alarm_beeps [Given]

 

Goal : Should I switch sprinklers on?

Chaining Forward chaining system, KR – forward chaining ,properties , algorithms, and conflict

resolution strategy are illustrated.

■  Forward chaining system

ð    facts are held in a working memory

ð    condition-action rules represent actions to be taken when specified facts occur in working memory.

ð    typically, actions involve adding or deleting facts from the working memory.

■  Properties of Forward Chaining

ð    all rules which can fire do fire.

ð    can be inefficient - lead to spurious rules firing, unfocused problem solving

ð    set of rules that can fire known as conflict set.

ð    decision about which rule to fire is conflict resolution.

 

 

Engine facts

KR – forward chaining

■  Forward chaining algorithm - I

Repeat

ð    Collect the rule whose condition matches a fact in WM.

ð    Do actions indicated by the rule.(add facts to WM or delete facts from WM) Until problem is solved or no condition match

Apply on the Example 2 extended (adding 2 more rules and 1 fact) Rule R1 : IF hot AND smoky THEN ADD fire

Rule R2 : IF alarm_beeps THEN ADD smoky Rule R3 : If fire THEN ADD switch_on_sprinklers

Rule R4 : IF dry THEN ADD switch_on_humidifier Rule R5 : IF sprinklers_on THEN DELETE dry Fact F1 : alarm_beeps [Given]

Fact F2 : hot [Given] Fact F2 : Dry [Given]

Now, two rules can fire (R2 and R4)

Rule R4 ADD humidifier is on [from F2]

 

ADD smoky [from F1] ADD fire [from F2 by R1]

ADD switch_on_sprinklers [by R3]

Rule R2[followed by sequence of actions]

DELEATE dry, ie humidifier is off a conflict ![by R5 ]

■  Forward chaining algorithm - II (applied to example 2 above )

Repeat

ð    Collect the rules whose conditions match facts in WM.

ð    If more than one rule matches as stated above then

Use conflict resolution strategy to eliminate all but one

Do actions indicated by the rules (add facts to WM or delete facts from WM) Until problem is solved or no condition match

Conflict Conflict Resolution set is Strategy

the set of rules that have KR – forward chaining ,their conditions satisfied by working memory elements. Conflict resolution normally selects a single rule to fire.

The popular conflict resolution mechanisms are :Refractory, Recency, Specificity.

Ø    Refractory: It is a rule should not be allowed to fire more than once on the samedata.

It discard executed rules from the conflict set. It prevents undesired loops.

Ø    Recency: It rank instantiations in terms of the recency of the elements in the premise of the rule. The rules which use more recent data are preferred. It is working memory elements are time-tagged indicating at what cycle each fact was added to working memory.

Ø    Specificity: The rules which have a greater number of conditions and are therefore more difficult to satisfy, are preferred to more general rules with fewer conditions. There are more specific rules are ‘better’ because they take more of the data into account.

Alternative Instead KR – forward chaining to Conflict Resolution – Use Meta Knowledge,of conflict resolution strategies, sometimes we want to useknowledge in deciding which rules to fire. Meta-rules reason aboutwhich rules should be considered for firing. They direct reasoning ratherthan actually performing reasoning.

Meta-knowledge : knowledge about knowledge to guide search.

Example of meta-knowledgeIF conflict set contains any rule (c , a) such that a = "animal is mammal'' THEN fire (c , a)

This example says meta-knowledge encodes knowledge about how to guide search for

solution.

Meta-knowledge, explicitly coded in the form of rules with "object level" knowledge.

 

KR – backward chaining Chaining:

Chaining system and the algorithm are illustrated.

■  Backward chaining system

ð    Backward chaining means reasoning from goals back to facts.The idea is to focus on the search.

ð    Rules and facts are processed using backward chaining interpreter.

ð    Checks hypothesis, e.g. "should I switch the sprinklers on?"

■  Backward chaining algorithm

ð    Prove goal G If G is in the initial facts , it is proven. Otherwise, find a rule which can be used to conclude G, and try to prove each of that rule's conditions.

 

Encoding of rules

Rule R1 : IF hot AND smoky THEN fire Rule R2 : IF alarm_beeps THEN smoky Rule R3 : If fire THEN switch_on_sprinklers Fact F1 : hot [Given]

Fact F2 : alarm_beeps [Given]

Goal : Should I switch sprinklers on?

 

 

Depends vs Backward on Chaining problem, and KR – backward chaining ,on properties of rule set.

ð    Backward chaining is likely to be better if there is clear hypotheses.Examples : Diagnostic problems or classification problems, Medical expert systems

ð    Forward chaining may be better if there is less clear hypothesis and want to see what can be concluded from current situation;

 

Examples : Synthesis systems - design / configuration.

Knowledge algorithm consists KR – control knowledge, of: logic component, that specifies the knowledge to be used in solving problems, and control component, that determines the problem-solving strategies by means of which that knowledge is used.

Thus Algorithm = Logic + Control .

The logic component determines the meaning of the algorithm whereas the control component only affects its efficiency. An algorithm may be formulated in different ways,

 

 

producing same behavior. One formulation, may have a clear statement in logic component but employ a sophisticated problem solving strategy in the control component.

The other formulation, may have a complicated logic component but employ a simple problem-solving strategy. The efficiency of an algorithm can often be improved by improving the control component without changing the logic of the algorithm and therefore without changing the meaning of the algorithm. The trend in databases is towards the separation of logic and control.

The programming languages today do not distinguish between them. The programmer specifies both logic and control in a single language. The execution mechanism exercises only the most rudimentary problem-solving capabilities.

Computer programs will be more often correct, more easily improved, and more readily adapted to new problems when programming languages separate logic and control, and when execution mechanisms provide more powerful problem-solving facilities of the kind provided by intelligent theorem-proving systems.

 

 

------Unit IV Completed-----

unit 4

one mark questions

1.      The rules which state all the facts and relationships about the problem are …………

2.      Logic + Control = ?

3.      ……………..is the knowledge about knowledge.

4.      ……………is a strategy of an Expert System to answer the question “what can happened next?”

5.      Backward chaining : also called as ……………..

2 Mark questions

1.      Define Logic.

2.      Define knowledge.

3.      Write any two properties of forward chaining

4.      What is meant by declarative knowledge?

15 mark questions

1.      Explain Logic programming with example

2.      Describe Control Knowledge with example.

3.      Compare Procedural Knowledge with Declarative Knowledge.

4.      Explain Forward and Backward Chaining.