Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

-

Artificial Intelligence

Course Notes
Dr
...


Lecture-3

Percept (Smell, Hear, See)

Agent

Environment

Act

Faculties of Agent
Faculty means the component/parts of the agent
...


Agent Performance
The execution of an action by an agent is known as agent performance

Intelligent Agent
There are different definitions about this
...
(OR)
...


Rationality/Bounded Rationality
Rationality is that do action with the best available knowledge
...
It was proposed by Herbert Simon
in 1957
...
Like playing Bank game with
cards
...
Like Chess playing
...
Like Luddo playing
...
It means that you know what would be the result after a certain input/action
...
f(x) = y
...


v) Schematic/Game Theoretic
There are two things in this environment
...

b) Your action must consider response of your component
...


vii) Static
While the agent is thinking, if the environment does not change, then it is called static
environment
...


ix) Discrete
Where actions and perceptions are finite, it is called Discrete Environment
...
It means, the agent doesn’t make any action by
itself
...
The action depends on what the
agent perceive from different things
...
Distributed system, not centralized
...
It does not have self awareness
...


Strong Artificial Intelligence
It is a machine which has human characteristics and self awareness
...


Performance
The execution of an action is known as performance
...

i)
ii)
iii)
iv)

Speed
Cost
Reliability
Power

Ideal Mapping
A mapping, from perception to action, to achieve maximum performance, is known as Ideal
Mapping
...
Weak Artificial Intelligence
A machine is simulating a human
...
It weak AI, machines just can
act intelligently
...
Strong Artificial Intelligence
It is a machine which has human characteristics and self awareness
...


3
...
After 1960, the practical application/machines like robots had been developed, which
worked to find different solutions
...
Cognitive Artificial Intelligence
Use the cognition of human in AI
...
cognitive science works
on mental process
...
Its purpose is to
gain a better understanding of the neuron-cognitive basis of human cognition, and to further the
realization of human-like and user-friendly cognition in artificial systems
...
Uninformed search
Uninformed Search is basically any search pattern where the domain (or area) of the search is
unknown
...


2
...
Examples are Optimal path
finding on a map (usually
...
)

States
States are possible situations an agent can adopt
...
States are traversed with the help to state functions/operations/actions
...
(Like in finding path
game, operators/functions are move left, move right, and move forward)
...
If two states are connected, then there must be an operator
...


Problem solving
In problem solving, we have problem statement, operators and conditions
...

Slide [Xλ]
[λX]
ii
...

All A’s move right
iv
...
The sequence of actions is called paths
...

Is deterministic
...

Have Boolean function, Goal(S) =True, to declare a state a goal
...


Lecture-5
Four Characteristics of State Space Search
i) Time Complexity
How much time is consumed to perform the search? It should take less time to perform an
operation

ii) Space Complexity
How much memory is needed to perform the search? It should perform operation in less
space/memory

iii) Termination
Is the algorithm guaranteed to find a solution when there is one? Algorithm should be terminated

iv) Optimality
Does the strategy find the optimal solution?

Problem Solving with Uninformed search / Blind search
Uninformed Search is basically any search pattern where the domain (or area) of the search is
unknown
...
There are two methods for
doing Blind search
...
Let we take the following Graph and
we assume that our destination is node ‘H’:
(Root)
S
A
C
G

B
D

H

E
I

F
J

Algorithm
1)
2)
3)
4)
5)
6)

Select Q = (S)
...

IF Q is empty, Exit
...

Check if X is Goal, Return
...

Explore children of X and put them in visited
...


Depth First Search (DFS)
Q

Visited

S
SAB
AB
CDB
GHDB
HDB
Return H

S
SAB
SAB
SABCD
SABCDGH
SABCDGH
SABCDGH

Breath First Search (BFS)
Q

Visited

S
SAB
ABCD
BCD
CDEF
DEFGH
EFGH
FGHIJ
GHIJ
HIJ
Return H

S
SAB
SABCD
SABCD
SABCDEF
SABCDEFGH
SABCDEFGH
SABCDEFGHIJ
SABCDEFGHIJ
SABCDEFGHIJ

Lecture-6
Let we take the following Graph and we assume that our destination is node ‘J’:
(Root)
A
B
D
H

C
E

I

F

G

J

K

Depth First Search (DFS)
Q

Visited

A
ABC
BC
DEC
HIEC
IEC
EC
C
FG
JKG
Return J

A
ABC
ABC
ABCDE
ABCDEHI
ABCDEHI
ABCDEHI
ABCDEHI
ABCDEFGHI
ABCDEFGHIJK

DFS is like a stack (LIFO)
...

P(H) = 1/height

Breath First Search (BFS)
Q

Visited

A
ABC
BC
CDE
DEFG
EFGHI
FGHI
GHIJK
HIJK
IJK
JK
Return J

A
ABC
ABC
ABCDE
ABCDEFG
ABCDEFGHI
ABCDEFGHI
ABCDEFGHIJK
ABCDEFGHIJK
ABCDEFGHIJK
ABCDEFGHIJK

BFS is like a Queue (FIFO)
...
P(H) = height

Comparison of DFS and BFS
DFS
More
Equal
Less
Less (Can stuck in infinite Loop)

Memory Complexity
Time Complexity
Optimality
Termination

BFS
Less
Equal
More
More

Iterative/Progressive Deepening
To get advantage of both algorithms, we merge them in progressive deepening
...
They give optimal solution, take less time, but don’t ensure the result
...

The 8-problem, 8 Queen Problem etc are examples of Uninformed search
...
Examples are Optimal path finding
on a map (usually
...
)
The followings are examples of Informed Search:




Best First Search
Beam Search
Branch and Bound

1
...
Best-first search is a search algorithm which explores a graph by expanding the
best node chosen according to a specified rule
...
Beam Search
Beam search is a heuristic search algorithm that explores a graph by expanding the most
promising node in a limited set
...
Best-first search is a graph search which orders all partial solutions (states)

according to some heuristic which attempts to predict how close a partial solution is to a complete
solution (goal state)
...


3
...

Until the first path is the queue terminates at the goal node or the queue is empty,
o Remove the first path from the queue; create new paths by extending the first path to
all the neighbors of the terminal node
...

o Add the remaining new paths, if any, to the queue
...

If the goal node is found, announce success; otherwise announce failure
...

A
A

4

Start with
root node
A
...


0
A

C
4

15

13

D

4

E

12

10

I

18

F

16

6

J G1

B

H
3

K L

1

M

4

N

Since B has the least cost,
we expand it
...


E 17

H
15

Node H has the least cost thus far, so we expand it
...


H

19

13

4

E 17

F
6

7

G2
21

3

L
21

3

1

M N
18 15

Note: Both
nodes F and N
have a cost of
15, we chose to
expand the
leftmost node
first
...



Step 1:

The path to node N cannot be extended
...




Step 3:

The path to node M, much like to node N, cannot be extended
...
Its cost, 29, now exceeds the

start -> goal path
...


Lecture-8
Uniform Cost Search (Partially Informed Search)
Uniform Cost Search is the best algorithm for a search problem, which does not involve the use
of heuristics
...
Uniform Cost Search as it sounds searches
in branches which are more or less the same in cost
...
At any given point in the execution, the algorithm never
expands a node which has a cost greater than the cost of the shortest path in the graph because
Uniform Cost Search gives the minimum cumulative cost the maximum priority
...

As you can see from the above example, in each iteration, the algorithm picks out the least costly among
all the paths that it hasn’t already visited
...


Comparison of Uninformed Searches

Heuristic/ Informed search
Heuristics are special
...
It means that Heuristic refers to a general problem-solving rule or set of
rules that do not guarantee the best solution or even any solution, but serves as a useful guide for
problem-solving
...


4
...
This
algorithm is a mathematical process that recursively constructs a set of objects from the smallest
possible remaining distance using the heuristic function h(n) as f(n) (where h(n) is the estimated cost of
the cheapest path from node n to a goal node)
...

Let we take an example of the below graph and apply A* Search on it
...


[States-path, f(n)= h(n) ]
Initialization: { [ S , 4 ] }
Iteration1: { [ S->G , 0 ] , [ S->A , 2 ] }
Iteration2 gives the final output as S-> G, which is not optimal because we have the optimal solution as
S->A->C->G, if we apply Uniform Cost here
...


5
...
It evaluates nodes by combining
g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal: f(n) = g(n) +h(n)
...
A* is
better than Greedy as its evaluation function is the combination of both g(n)+h(n), so it always finds an
optimal path to the goal
...

We will use h1 as the heuristic, given in the diagram below
...


Admissible Heuristic
The function h(n) is said to be admissible heuristic if it never overestimates the actual cost of
getting to the goal state
...
An admissible
heuristic is also known as an optimistic heuristic
...

The straight Line distance heuristic is consistence because for every node n and every successor n’ of n,
the estimated cost of reaching the goal from n is less than the step cost of getting n’ plus the estimated
cost of reaching the goal from n’
...
The estimated
distance for reaching to Bucharest from Arad is 366, and the distance from Arad to Sibiu is 144 and
estimating distance from Sibiu to Bucharest is 253
...

Hence it is proved that Straight Line Distance heuristic is consistent
...
This heuristic is routinely used to generate useful
solutions to optimization and search problems
...


Fitness Function
A fitness function is a particular type of objective function that is used to summaries, as a
single figure of merit, how close a given design solution is to achieving the goal
...


Types of Knowledge
i
...
Everyone
has different Heuristic
...


Meta
Information about the type of the knowledge is called Meta Knowledge
...


Structural
It means, Dependency of facts from top to bottom in a structural way
...

v
...

Declarative
It is simple type of knowledge
...


Expert System
Expert

User

GUI

Knowledge Engineer

Inference engine

Components of Expert System/Flow Diagram of Expert System
Expert

Knowledge Base
Knowledge Engineering

Knowledge Base

Inference Engine

GUI

User

In knowledge base, Engineer represents the knowledge
...

Knowledge Engineering
To create, maintain and update Expert system
...

Inference Engine
A computer program, designed to produce reasoning on rules
...

GUI
GUI is hardware and software that provide the dialogue between the user and the computer
...
Batch
All input at start (Once)
2
...
Input required step by step

Advantages and Disadvantages of Expert System
Advantages
1
...

2
...
Rules may not exist
...
Contradictory rules
...
It cannot work in dynamic environment
...


1
...


Fuzzy
Ambiguity

ii
...


Uncertain
Not sure
...


2
...

Example
If it is humidity and hot, then it is raining
...


i
...


ii
...


iii
...


iv
...


v
...


Metarules

3
...
This is
often used as a form of knowledge representation
...
Example is shown in above diagram
...
Frames
A frame is an artificial intelligence data structure used to divide knowledge into substructures
...

The frame contains information on how to use the frame, what to expect next, and what to do when
these expectations are not met
...
Different frames may share the same terminals
...
The information can contain:
i
...


Values (called facets)
...

Triggers (also called procedural attachments)



IF-NEEDED : deferred evaluation



IF-ADDED : updates linked information

iii
...


5
...
Two forms of logic are following:i
...
It is also called the statement of facts
...


ii
...
It allows the use of quantifiers on predicate and can express
facts about objects, their properties, and their relations with each other
...


Fuzzy Logic
If we are not sure about things, then it is fuzzy statement
...


Reasoning
1
...


2
...

Example
 Man is mortal
...

 Amir is mortal
...
Abductive
If you don’t get a choice of deduction, then apply Abduction (Risk)
...
Common Sense
Heuristic is a common sense
...
Compound Rules
Multiple if conditions
Example
If it is humidity and hot, then it is raining
...
Logical Connective
Logical connective/operator is a symbol or word used to connect two or more statements
...
Non-Monotonic Rules
Logic is non-monotonic if some conclusions can be invalidated by adding more knowledge
...
Non-monotonic reasoning is useful for
representing defaults
...


4
...


Long Term Memory

The long-term memory, also known as knowledge base where it keeps the knowledge that is
needed to act in the future
...


ii
...
When the rules are applied on the case facts, the new results coming out from them is
stored in the STM
...
Inference
Inference is the act or process of deriving logical conclusions from premises known or assumed to
be true
...


Logic

Logic is used for knowledge representation and problem solving, but it can be applied to other
problems as well
...



Syntax
Syntax is the rules to write a statement
...
Deduction Mechanism
1
2
3

AΛB
AC
(B Λ C) D

4
5
6
7
8

(True)
(True)

To Prove
D = True

A
B
C
BΛC
D

(True)
AND-Elimination 1
AND-Elimination 2
Modus Ponen 2, 4
AND-Intro 5, 6
Modus-Ponen 3, 7

7
...
A literal is a propositional variable or the
negation of a propositional variable
...
Let we take the following example and make the truth table for it:
αVβ

¬β

V γ

α V γ
α

β

γ

¬β

αVβ

0
0
0
0
1

0
0
1
1
0

0
1
0
1
0

1
1
0
0
1

0
0
1
1
1

¬β

V γ
1
1
0
1
1

α V γ
0
1
0
1
1

1
1
1

0
1
1

1
0
1

1
0
0

1
1
1

1
0
1

1
1
1

8
...
It is
also called AND of ORs
...

1
...

3
...
A V (B Λ C) = (A V B) Λ (A V C)
Example:
(A V B)  (C  D)
(A V B)  (C  D)

¬(A

1

V B) V (C  D)

1, 2

(¬A Λ ¬B) V (¬C V D)
(¬A V ¬C V D) Λ (¬B V

¬C

V D)

4



---