Transcript Algorithms of Artificial Intelligence

Algorithms of Artificial
Intelligence
E. Tyugu
Spring 2003
Course content
• We start with a brief introduction into knowledge systems, where
simple knowledge-handling and inference algorithms are presented.
• Search algorithms are a classical and well-developed part of the
artificial intelligence. In this part, various heuristic as well as bruteforce search methods are systematically explained and represented
by their algorithms.
• Learning is represented by algorithms of parametric and adaptive
learning, symbolic learning, including various concept learning
methods, inductive inference and massively parallel learning
methods including neural nets and genetic algorithms.
• Problem solving (incl. constraint solving and planning) is a branch of
the artificial intelligence that has given a considerable output into the
computing practice in various application domains.
© Enn Tyugu
2
Course literature (recommended)
• Russell, S. and Norvig, P. (1995) Artificial Intelligence: A Modern
Approach. Prentice Hall.
• Shapiro, S. (1992) Encyclopedia of Artificial Intelligence. John Wiley
& Sons, Inc. Publishers
• Bratko, I. (2001) Prolog Programming for Artificial Intelligence.
Addison Wesley.
• Proc. IJCAI ( published every third year)
• Genesereth, M. and Nilsson N. (1987) Logical Foundations of
Artificial Intelligence. Morgan Kaufmann
© Enn Tyugu
3
Content of the lecture
Language of algorithms
Knowledge
Deductive systems
Knowledge system
Post’s systems
Brute force deduction
Resolution method
© Enn Tyugu
4
Language of algorithms
1. Loop control with while, for and until constructions
2. Set notations used in loop control and other expressions
Example: for x S do .......... od
3. Conditional expressions and statements
4. Recursive definitions
Example: f(x) = if x=0 then 1 else f(x-1)*x fi
5. exit L - exit a statement labelled L
break – end execution of the current block
continue – break execution of the body of the loop.
© Enn Tyugu
5
Language of algorithms continued
Some predicates and functions are being used without introducing
them in
the preface. They have the following predefined meaning:
good(x) - x is a good solution satisfying the conditions given for the
problem
empty(x) - x is an empty object (tree, set, list etc.)
success() - actions taken in the case of successful termination of the
algorithm, it can be supplied with the argument which is then the
output of the algorithm: success(x)
failure() - actions taken in the case of unsuccessful termination of the
algorithm
Common functions for list manipulation (head, tail, append etc.)
are used without introduction.
We consider functions with finite domains as arrays.
For instance, we can use the assignment
l(i):=l(n)+p(n,i) for changing the value of function l at i, if it is
convenient
© Enn Tyugu
6
for representing an algorithm.
Knowledge and knowledge system
•Knowledge is the content of data for a user who understands
the data. Knowledge may be:
– deep or shallow,
– soft or hard
– weak or strong,
but how to measure knowledge?
•Knowledge system is a language for representing knowledge plus
a mechanism (a program, usually) for using the knowledge by making
inferences. A knowledge system can be inplemented in the form of a
knowledge base and an inference engine.
© Enn Tyugu
7
Deductive system
There are a certain number of initial objects and a certain
number of rules for generating new objects from the initial
objects and from those already constructed.
To put it another way: There are an initial position (state) and
"rules of the game" (rules for transition from one state into
another). A system of this kind is called a deductive system or
a calculus.
Interpretation of a deductive system is a set S of objects which
can be considered as possible meanings of objects of the
deductive system, and a function i which gives a meaning to
every object, i.e. computes a set of elements of S for any
object, derivable in the deductive system.
© Enn Tyugu
8
Knowledge system
Now we can define a knowledge system as
a class of interpreted deductive systems with fixed
language of objects and fixed inference rules.
Interpretations of objects of a knowledge system may be objects
of another knowledge system. The latter may have other
inference rules, e.g. more detailed ones. One can build a tower
of knowledge systems.
© Enn Tyugu
9
Example
Objects are built of sets (denoted by A, B, etc.), arrow -> and
symbol  (union of sets), e.g. A  C -> B .
Inference rules are:
A -> B
B  C -> D
A  C -> B  D
A -> B  C
A -> B
(1)
(2)
Meaning of the letters can be data, A -> B can denote computability.
© Enn Tyugu
10
How to build a knowledge system
In order to build a knowledge system, one has to
•
•
•
•
specify a syntax of the knowledge language
give inference rules
define the meaning
formalize the meaning by constructing an interpretation of derivable
objects
We expect that there will be a great variety of meanings reflecting the
variety in the real world. A well-known knowledge system is firstorder predicate calculus.
© Enn Tyugu
11
Post's systems
Let us have an alphabet A, a set of variables P, a set A of initial objects
which are words in the alphabet A. These initial objects are also called
axioms. Inference rules are given in the following form:
S1, ..., Sm
________
S0
where S0, S1, ... , Sm are words in the alphabet A  P, and S0 doesn't
contain
variables which do not occur in S1, ... ,Sm. A word W0 is derivable from
the words
W1, ... ,Wm by an inference rule in the calculus iff there exists an
assignment of
words in A to variables occuring in the rule such that it transforms the
© Enn
Tyugu
words S1, ... , Sm into W1, ...
, Wm
and the word S0 into W0.
12
Post´s systems continued
•
•
•
•
•
Let B be a subset of the alphabet of a Post´s system. We say that the Post´s
system is given over B and we consider the words in the alphabet B generated
by the Post´s system.
Two Post´s systems are equivalent, iff they generate the same set of words in B.
Post´s system is in a normal form, iff there is only one axiom and one variable
in it and all its inference rules are in the form
S1 p
p S0
A Post's system is decidable iff there exists a regular way (an algorithm)
to decide for any word whether the word is generated by it or not.
A set of words is called recursively enumerable iff there exists a Post's
system which generates it.
© Enn Tyugu
13
Post´s systems continued
Theorems:
1. It is possible to build an equivalent normal form for any Post's system.
2. There exist undecidable Post's systems (exist undecidable recursively
enumerable
sets).
3. There exists a universal Post's system which generates exactly the set of all
words NW such that N is a coding of a Post's system and W is a word
generated
by the latter.
© Enn Tyugu
14
Brute force deduction
axioms - set of axioms of the calculus
wanted - word to be generated
active - set of words to to be used to produce a set of new words
new - currently built set of new words
app(r,w) - function which for a given rule r and word w produces the application of r
to w
applicable(r,w) - true iff the rule r is applicable to word w.
A.1
active := axioms;
while wanted  active do
new:={};
for w  active do
for r  rules do
if applicable(r,w)
then new:=new  {app(r,w)}
fi
od
od;
if new = {} then failure()
else active:= new fi;
od;
success()
© Enn Tyugu
15
Calculus of computability
known - set of elements already known to be computable;
found - boolean variable showing whether something was found during the last
search
axioms - set of axioms;
arg(r) - set of given elements in axiom r;
res(r) - set of computable elements in axiom r;
plan - sequence of applied axioms which is a plan for computations.
The following algorithm finds a plan for computing the variables out from in:
A.1.2: known:=in;
plan:=();
while out  known do
found:=false;
for r axioms do
if arg(r)  known & res(r)  known
then found:=true;
known:=known  res(r);
append(plan,r)
fi;
od;
if not found then failure() fi
od;
© Enn Tyugu
16
success(plan)
Clauses
Atomic formula is of the form P(e1,...,en) where P is a predicate symbol,
denoting some n-ary relation (i.e. a relation which binds exactly n
objects) and e1,...,en are terms.
Examples: father(Tom,John), employee(x), less_than(a,b).
Clause is a collection of atomic formulae which can occur in the clause
positively or negatively. It is convenient to speak about a clause as a set
of literals, which are nonnegated or negated atomic formulas. We
denote negation by means of the "minus" sign before an atomic
formula.
Meaning of a clause consisting of literals L1,...,Ln is: "There exist only the
options L1 or ... or Ln." Meaning of a collection of clauses C1, …, Cn is
“It is true that C1 and … and Cn .”
© Enn Tyugu
17
A simple resolution rule
{A,B,...,C}
{-A,D,...,E}
_____________________________
{B,....,E}
where A is an atomic formula, B,...,C,D,...,E are literals. The clause
{B,...,E}
contains all elements from B,...,C and D,...,E, but doesn't contain
multiple
elements or elements of the contradictory pair. The clause {B,...,E} is
called
the resolvent of the premises of the rule.
© Enn Tyugu
18
Unification
• A substitution is a tuple of pairs (variable, term), e.g.(
(x,f(z)),(y,z)) where all variables are different and do not occur in
the terms.
• Application of a substitution s to a term or a formula F is
simultaneous changing of the variables in F into their
corresponding terms in the substitution s.
• We denote the result of this application by F¤ s. A substitution s
which gives F1¤ s=F2¤ s is called a unifier for F1 and F2, and
its application to F1 and F2 is called unification.
© Enn Tyugu
19
General resolution rule
{A,B,...C}
{-A',D,...,E}
___________________________________
{B¤ s,...,E¤ s}
A¤ s=A´ ¤ s
where s is a unifier for A and A' and the resolvent {B¤ s,...,E¤ s}
includes results of applying the substitution s to literals
B,...,C,D,...,E without repetition of identical literals and
without contradictory pairs.
© Enn Tyugu
20
Clausal calculi
Clausal calculi have become very popular, because they are
handy to use and they also have a nice and neat logical
explanation. Originally, the resolution method was developed
in 1965 by J. A. Robinson just for automation of logical
deductions (Robinson 65). Independently from Robinson,
Sergei Maslov developed and implemented very effciently the
same method at the same time in Leningrad.
Clauses with at most one positive literal are called Horn
clauses. They possess several good properties.
© Enn Tyugu
21
Refutation
Given a finite set of clauses, the resolution method allows us to
answer the question, whether this set of clauses is unsatisfiable
(contradictory), i.e. whether there exists a derivation of the empty
clause from the given set of clauses.
Derivation of an empty clause is called refutation. This is the
most common usage of resolution -- theorems are often proved by
refuting their negations.
© Enn Tyugu
22
Some resolution strategies
Unit resolution. Unit resolvent is a resolvent for
which at least one of the premises is a unit clause contains one literal. Unit resolution is the process of
deduction of unit resolvents. It is complete for Horn
clauses, and good algorithms are known for this
case.
Input resolution. Input resolvent is a resolvent for
which at least one of the premises is in the initial
set of clauses. Input resolution is the process of
deduction of input resolvents. It is complete for
Horn clauses, and good algorithms are known for
this case.
© Enn Tyugu
23
Resolution strategies continued
Linear resolution. A linear resolvent is a resolvent for
which at least one of the premises is either in the initial
set of clauses or is an ancestor of another premise of
this resolution step. Linear resolution is complete for
refutation (deriving an empty clause).
Ordered resolution. Literals are considered to be
ordered in clauses from left to right. The ordering of
literals of premises is preserved in resolvents. Only
first, i.e. the leftmost literals in clauses can be resolved
upon. This is a restrictive strategy, but it is still
complete for Horn clauses.
© Enn Tyugu
24
Exercises
• Define a Post´s system that enables one to split any finite set
with at least two elements represented as {a1, …,an} into two
sets {a1,…, ai} and {ai+1,…, an} for any i=1,…, n-1.
• Define a PS that enables one to split a set in an arbitrary way.
© Enn Tyugu
25
Exercises
Find the most general unifier, if a pair of literals is unifiable, and explain
why, if it is not:
• Color(Tweety, Yellow) Color(x,y)
• R(F(x),B)
R(x,y)
• R(F(y),x)
R(R(x),F(B))
• Loves(X,Y)
Loves(y,x)
Prove by refutation the following theorem:
(a&b -> c) & (d -> a) & (d -> b) & d |- c
© Enn Tyugu
26
Bibliography
• Maslov, S. (1987) Theory of Deductive Systems and its
Application. The MIT Press.
• Robinson, J. A. (1965) A Machine-Oriented Logic Based on the
Resolution Principle. Journal of the ACM, v. 12, 23 - 41.
• Tyugu, E. (1991) Modularity of Knowledge. In: Hayes, J., Michie,
D., Tyugu, E. (Eds.) Machine Intelligence 12 (Towards an
automated logic of human thought). Clarendon Press. Oxford, 3
- 16.
• Lorents, P. (2001) Formalization of data and knowledge based on the
fundamental notation-denotation relation. In: H. R. Arabnia (ed.)
Proc. IC-AI’2001.
© Enn Tyugu
27