Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | Production System

A Knowledge representation formalism consists of collections of condition-action rules(Production Rules or Operators), a database which is modified in accordance with the rules, and a Production System Interpreter which controls the operation of the rules i.e The 'control mechanism' of a Production System, determining the order in which Production Rules are fired.

**Production System**

**Types of Production Systems.**

A
Knowledge representation formalism consists of collections of condition-action
rules(Production Rules or Operators), a database which is modified in
accordance with the rules, and a Production System Interpreter which controls
the operation of the rules i.e The 'control mechanism' of a Production System,
determining the order in which Production Rules are fired.

A system
that uses this form of knowledge representation is called a production system.

A
production system consists of rules and factors. Knowledge is encoded in a
declarative from which comprises of a set of rules of the form

Situation
------------ Action SITUATION that implies ACTION.

Example:-

IF the
initial state is a goal state THEN quit.

The major
components of an AI production system are

A global
database

A set of
production rules and

A control
system

The goal
database is the central data structure used by an AI production system. The
production system. The production rules operate on the global database. Each
rule has a precondition that is either satisfied or not by the database. If the
precondition is satisfied, the rule can be applied. Application of the rule
changes the database. The control system chooses which applicable rule should
be applied and ceases computation when a termination condition on the database
is satisfied. If several rules are to fire at the same time, the control system
resolves the conflicts.

Four
classes of production systems:-

A
monotonic production system

A non
monotonic production system

A
partially commutative production system

A
commutative production system. Advantages of production systems:-

Production
systems provide an excellent tool for structuring AI programs.

Production
Systems are highly modular because the individual rules can be added, removed
or modified independently.

The
production rules are expressed in a natural form, so the statements contained in
the knowledge base should the a recording of an expert thinking out loud.

Disadvantages
of Production Systems:-

One
important disadvantage is the fact that it may be very difficult analyse the
flow of control within a production system because the individual rules don’t
call each other.

Production
systems describe the operations that can be performed in a search for a
solution to the problem. They can be classified as follows.

Monotonic
production system :- A system in which the application of a rule never prevents
the later application of another rule, that could have also been applied at the
time the first rule was selected.

Partially
commutative production system:-

A
production system in which the application of a particular sequence of rules transforms
state X into state Y, then any permutation of those rules that is allowable
also transforms state x into state Y.

Theorem
proving falls under monotonic partially communicative system. Blocks world and
8 puzzle problems like chemical analysis and synthesis come under monotonic,
not partially commutative systems. Playing the game of bridge comes under non
monotonic , not partially commutative system.

For any
problem, several production systems exist. Some will be efficient than others.
Though it may seem that there is no relationship between kinds of problems and
kinds of production systems, in practice there is a definite relationship.

Partially
commutative , monotonic production systems are useful for solving ignorable
problems. These systems are important for man implementation standpoint because
they can be implemented without the ability to backtrack to previous states,
when it is discovered that an incorrect path was followed. Such systems
increase the efficiency since it is not necessary to keep track of the changes
made in the search process.

Monotonic
partially commutative systems are useful for problems in which changes occur
but can be reversed and in which the order of operation is not critical (ex: 8
puzzle problem).

Production
systems that are not partially commutative are useful for many problems in
which irreversible changes occur, such as chemical analysis. When dealing with
such systems, the order in which operations are performed is very important and
hence correct decisions have to be made at the first time itself.

__Control or Search Strategy :__

Selecting
rules; keeping track of those sequences of rules that have already been tried
and the states produced by them.

Goal
state provides a basis for the termination of the problem solving task.

**PATTERN MATCHING STAGE**

Execution
of a rule requires a match.

when
match is found => rule is applicable several rules may be applicable

**CONFLICT RESOLUTION (SELECTION STRATEGY ) STAGE**

Selecting
one rule to execute;

**ACTION STAGE**

Applying
the action part of the rule => changing the content of the workspace
=>new patterns,new matches => new set of rules eligible for execution
Recognize -act control cycle

Search
Strategies

**Uninformed Search Strategies **have no
additional information about states beyond that

provided
in the **problem definition**.

**Strategies ***that
know whether one non goal state is ―more promising‖*** **than another are

called **Informed search or heuristic search**
strategies. There are five uninformed search strategies as given below. o
Breadth-first search

Uniform-cost
search o Depth-first search

Depth-limited
search

Iterative
deepening search

Problem
characteristics

**Analyze
each of them with respect to the seven problem characteristics**

**Chess**

**Water jug**

**8-puzzle**

**Traveling
salesman**

**Missionaries
and cannibals**

**Tower of
Hanoi**

**Chess**

**Water jug**

**8 puzzle**

**Travelling
Salesman (TSP)**

**Missionaries
and cannibals**

**Tower of
Hanoi**

**Measuring Performance of Algorithms**

There are
*two aspects* of algorithmic
performance:

Time

Instructions take time.

How fast does the algorithm perform?

What affects its runtime?

Space

- Data
structures take space

What kind
of data structures can be used?

How does
choice of data structure affect the runtime?

Algorithms
can not be compared by running them on computers. Run time is system dependent.
Even on same computer would depend on language Real time units like
microseconds not to be used.

Generally
concerned with how the amount of work varies with the data.

**Measuring Time Complexity**

Counting
number of operations involved in the algorithms to handle n items.

Meaningful
comparison for very large values of n.

**Complexity of Linear Search**

Consider
the task of searching a list to see if it contains a particular value.

A useful
search algorithm should be *general.*

Work done
varies with the size of the list

What can
we say about the work done for list of *any*
length?

i = 0;

while (i < MAX &&
this_array[i] != target) i = i + 1;

if (i <MAX)

printf ( “Yes, target is there \n” );
else

printf( “No, target isn’t there \n”
);

The work
involved : Checking target value with each of the n elements.

no. of
operations: 1 (best case)

n (worst case)

n/2 (average case)

Computer
scientists tend to be concerned about the *Worst
Case complexity*.

The worst
case guarantees that the performance of the algorithm will be at least as good
as the analysis indicates.

*Average Case Complexity:*

It is the
best statistical estimate of actual performance, and tells us how well an
algorithm performs if you average the behavior over all possible sets of input
data. However, it requires considerable mathematical sophistication to do the
average case analysis.

**Algorithm Analysis: Loops**

Consider
an n X n two dimensional array. Write a loop to store the row sums in a
one-dimensional array rows and the overall total in grandTotal.

**LOOP 1:**

grandTotal = 0;

for (k=0; k<n-1; ++k) { rows[k] =
0;

for (j = 0; j <n-1; ++j){

rows[k] = rows[k] + matrix[k][j];
grandTotal = grandTotal + matrix[k][j];

}

}

It takes 2n^{2} addition operations

**LOOP 2:**

grandTotal =0;

for (k=0; k<n-1; ++k) rows[k] = 0;

for (j = 0; j <n-1; ++j)

rows[k] = rows[k] + matrix[k][j];
grandTotal = grandTotal + rows[k];

}

This one takes n^{2}
+ n operations

**Big-O Notation**

We want
to understand how the performance of an algorithm responds to changes in
problem size. Basically the goal is to provide a *qualitative* insight. The Big-O notation is a way of measuring the
order of magnitude of a mathematical expression

O(n)
means on the Order of n

Consider

*n ^{4} + 3_{1}n^{2} +
10 = f (n)*

The idea
is to reduce the formula in the parentheses so that it captures the qualitative
behavior in simplest possible terms. We eliminate any term whose contribution
to the total ceases to be significant as n becomes large.

We also
eliminate any constant factors, as these have no effect on the overall pattern
as n increases. Thus we may approximate f(n) above as

*(n ^{4} + 3_{1}n^{2} + 10) =
O( n^{4)}*

Let g(n)
= *n ^{4}*

Then the
order of f(n) is O[g(n)].

**Definition: **f(n) is O(g(n)) if there exist
positive numbers c** **and N such that
f(n) < = c g(n) for all n >=N.

i.e. f is
big –O of g if there is larger than cg for sufficiently large than N) such that
f is not value of n ( greater c g(n) is
an upper bound on the value of f(n)

That is,
the number of operations is at worst proportional to g*(n)* for all large values of *n*.

How does
one determine c and N?

Let f(n)
= 2 *n ^{2}*

Now 2 *n ^{2}*

Or 2 +
(3/n) + ( 1 / *n ^{2}* ) < = c

You want
to find c such that a term in f becomes the largest and stays the largest.
Compare first and second term. First will overtake the second at N = 2,

so for N=
2, c >= 3.75,

for N =
5, c >= slightly more than 2, for very large value of n, c is almost 2.

g is
almost always > = f if it is multiplied by a constant c

Look at
it another way : suppose you want to find weight of elephants, cats and ants in
a jungle. Now irrespective of how many of each item were there, the net weight
would be proportional to the weight of an elephant.

Incidentally
we can also say f is big -O not only of *n ^{2}*

but also
of *n ^{3}* ,

** **Loop 1
and Loop 2 are both in the same big-O category:

Properties
of Big-O notation:

O(n) +
O(m) = O(n) if n > = m

The
function log n to base a is order of O( log n to base b) For any values of a
and b ( you can show that any log values are multiples of each other)

**Linear search Algorithm:**

**Best Case **- It’s the first value** **“order 1,” O(1)

**Worst Case **- It’s the last value, n** **“order n,” O(n)

**Average **- N/2 (if value is present)** **“order n,” O(n)

**Example 1:**

Use big-O
notation to analyze the time efficiency of the following fragment of C code:

**for(k = 1; k <= n/2; k++)**

**{**

**.**

**.**

**for (j = 1; j <= n*n; j++)**

**{**

**}**

**}**

Since
these loops are nested, the efficiency is *n ^{3}/2*,
or O(

Thus, for
two loops with O[*f _{1}(n)*]
and O[

O[*f _{1}(n) * f_{2}(n)*].

**Example 2:**

Use big-O
notation to analyze the time efficiency of the following fragment of C code:

**for (k=1; k<=n/2; k++)**

**{**

**.**

**.**

**}**

**for (j = 1; j <= n*n; j++)**

**{**

**.**

**.**

**}**

The
number of operations executed by these loops is the sum of the individual loop
efficiencies. Hence, the efficiency is *n/2+n ^{2}*,
or O(

Thus, for
two loops with O[*f _{1}(n)*]
and O[

**Complexity of Linear Search**

In
measuring performance, we are generally concerned with how the amount of work
varies with the data. Consider, for example, the task of searching a list to
see if it contains a particular value.

A useful
search algorithm should be *general.*

Work done
varies with the size of the list

What can
we say about the work done for list of *any*
length?

i = 0;

while (i < MAX &&
this_array[i] != target) i = i + 1;

if (i <MAX)

printf ( “Yes, target is there \n” );
else

printf( “No, target isn’t there \n”
);

**Order Notation**

How much
work to find the target in a list containing N elements?

*Note*: we care here only about the* growth rate *of work.* *Thus, we *toss out all constant values*.

Best Case
work is *constant*; it does not grow
with the size of the list.

Worst and
Average Cases work is *proportional* to
the size of the list, N.

**Order Notation**

*O(1) or
“Order One”: Constant time*

does *not* mean that it takes only one
operation

*does *mean that the work* doesn’t change *as N changes* *is a notation for *“constant work”*

*O(n) or
“Order n”: Linear time*

does *not* mean that it takes N operations

*does *mean that the work changes in a
way that is* proportional *to N

is a
notation for *“work grows at a linear rate*”

**O( n^{2})
or “Order n^{2} ”: Quadratic time**

**O( n^{3})
or “Order n^{3} ”: Cubic time**

Algorithms
whose efficiency can be expressed in terms of a polynomial of the form

*a _{m}n^{m} + a_{m-1}n^{m-1}
+ ... + a_{2}n^{2} + a_{1}n + a_{0}*

are
called ** polynomial algorithms**.

Some
algorithms even take less time than the number of elements in the problem.
There is a notion of logarithmic time algorithms.

We know *10 ^{3}*

*So we can write it as log _{10}1000 = 3*

Similarly
suppose we have

*2 ^{6}
=64*

then we
can write

*log _{2}64 = 6*

If the
work of an algorithm can be reduced by half in one step, and in k steps we are
able to solve the problem then

*2 ^{k}
= n*

or in
other words

*log _{2}n = k*

This
algorithm will be having **a logarithmic
time** complexity ,usually written as **O(ln
n).**

Because *log _{a}n* will increase much more
slowly than

**Example 3:**

Use big-O
notation to analyze the time efficiency of the following fragment of C code:

**k = n;**

**while (k > 1)**

**{**

**.**

**.**

**k = k/2;**

**}**

Since the
loop variable is cut in half each time through the loop, the number of times
the statements inside the loop will be executed is log_{2}n.

Thus, an
algorithm that halves the data remaining to be processed on each iteration of a
loop will be an O(*log _{2}n*)
algorithm.

There are
a large number of algorithms whose complexity is **O( n** *log _{2}n*) .

Finally
there are algorithms whose efficiency is dominated by a term of the form *a ^{n}*

These are
called ** exponential algorithms**. They are of more theoretical rather
than practical interest because they cannot reasonably run on typical computers
for moderate values of

**Comparison of N,
logN and N^{2}**

**Constraint Satisfaction**

**Constraint satisfaction **is the
process of finding a solution to a** **set
of constraints that impose conditions that the variables must satisfy. A
solution is therefore a set of values for the variables that satisfies all
constraints—that is, a point in the feasible region.

The
techniques used in constraint satisfaction depend on the kind of constraints
being considered. Often used are constraints on a finite domain, to the point
that constraint satisfaction problems are typically identified with problems
based on constraints on a finite domain. Such problems are usually solved via
search, in particular a form of backtracking or local search. Constraint
propagation are other methods used on such problems; most of them are
incomplete in general, that is, they may solve the problem or prove it
unsatisfiable, but not always. Constraint propagation methods are also used in
conjunction with search to make a given problem simpler to solve. Other
considered kinds of constraints are on real or rational numbers; solving
problems on these constraints is done via variable elimination or the simplex
algorithm.

**Complexity**

Solving a
constraint satisfaction problem on a finite domain is an NP complete problem
with respect to the domain size. Research has shown a number of tractable
subcases, some limiting the allowed constraint relations, some requiring the
scopes of constraints to form a tree, possibly in a reformulated version of the
problem. Research has also established relationship of the constraint
satisfaction problem with problems in other areas such as __finite model theory__.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.