Transcript ppt - CSE, IIT Bombay

CS 621 Artificial Intelligence
Lecture 1 – 28/07/05
Prof. Pushpak Bhattacharyya
Introduction
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
1
AI Introduction
Language Processing
Expert
System
Planning
Search
Reasoning
Learning
Knowledge Representation
Vision
Robotics
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
2
Thinking Ability in Machines
“Can machines think”
320 BC Aristotle – Syllogism (Disjunctive Reasoning)
ex: All men are mortal.
Shakespeare is a man.
Shakespeare is mortal.
Inductive Reasoning – specific  general (difficult for machine)
ex: Crows in Bhopal are black.
Crows in Mumbai are black.
All crows are black.
Abductive Learning - p  q
if Q is true then P is true in absence of any other info.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
3
Turing Machine
Finite state control
Infinite tape
Church-Turing Hypothesis
Anything that is computable, is computable by a TM & viceversa.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
4
Turing Test
Human
Computer
Interrogator has to find which is a
machine and which is a human by
asking questions to both of them. If the
machine is able to fool the interrogator
to behave like a human, then that
machine passes the Turing Test.
Interrogator
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
5
Machines
Gene/DNA: A string of bits which is a coded instruction.
ANIMATE THEORY: Intelligence is producable only on carbon base.
Silicon intelligence is not possible.
PHYSICAL SYMBOL HYPOTHESIS: (opposed to Animate theory):
Intelligence emerges from manipulating symbols & nothing else is
needed.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
6
Levels in AI
Knowledge level (Disambiguation)
● Symbol level (e.g. Lisp program)
● Signal level (e.g. Neural Net)
●
AI
Science (Cognitive Sc, Psychology, social science, physics
Sci + Engg (theory + code)
Engineering
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
7
Search
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
8
Search is Fundamental and
Ubiquitous
Fundamental in all of AI.
In planning :
A
B
C
B
A
C
Table
At every stage: multiple possibilities, search for the best possible
sequence of options.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
9
In Vision
R
World
28-07-05
L
Two eye system
Left eye retina & right eye retina have
pixels activated. Search for corresponding
points:
points in the left eye should correspond to
points in the right eye – O(n2) algorithm.
Prof. Pushpak Bhattacharyya, IIT
Bombay
10
In Language Processing
The man would like to play.
Noun
Verb
Prep Verb Noun Verb
System has to search amongst the possibilities to get the correct meaning.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
11
Abstractions of Search
State
 state space
● Operators
 transform states
● Cost
 associated operations
● Start node
● Goal node (S)
● Minimal cost path
●
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
12
Classical Example
8-puzzle
4
2
5
1
2
3
3
1
6
4
5
6
7
7
8
8
Goal
Start (S0)
State: Matrix repersentation of the board.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
13
Operators
Here operators are movements of blank space.
MU
4
3
8
28-07-05
2
5
1
6
MR
7
ML
Prof. Pushpak Bhattacharyya, IIT
Bombay
4
3
8
2
1
4
3
8
2
1
4
3
8
2
1
5
6
7
5
6
7
5
6
7
14
Cost
Cost of each operation = 1 for this problem.
Which path leads to the goal –
Uninformed search (Breadth first, Depth first)
●
Heuristic Search (A* algorithm)
●
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
15
Search
All searchs are instantiations of “General Graph Search” (GGS) algo.
Input:
Output:
The state space graph (implicit/explicit).
The path to the goal node.
Data Structures: 1. Open list (OL)
2. Closed list (CL)
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
16
Example
Start
A
1
3
B
4
D
C
6
2
E
9
8
F
State space graph
28-07-05
3
OL
CL
:A
:
OL
CL
:BCD
:A
OL
CL
:CDE
:AB
OL
CL
:DEF
:ABC
OL
CL
:EFG
:ABCD
G
Prof. Pushpak Bhattacharyya, IIT
Bombay
17
KNOWLEDGE REPRESENTATION &
INFERENCING
USING PREDICATE CALCULUS
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
18
Example
Example:
John, Jack & Jill are members of Alpine club. Every member if the club
is either a mountain climber or a skier. All skiers like snow. No
mountain climber likes rain. Jack dislikes whatever John likes, and likes
whatever John dislikes. John likes rain and snow.
Is there a member who is a mountain climber but not a skier.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
19
Knowledge Representation
1. member (John, Alpine)
2. member (Jack, Alpine)
3.member (Jill, Alpine)
 sk(x)]
4. x [member(x, Alpine) → mc(x)
5. x [sk(x) → like(x, snow)]
6. x [mc(x) → ~like(x, rain)]
7.  x [like(John, x) → ~like(John, x)]
8.  x [~like(John, x) → like(Jack, x)]
9. like(John, rain)
10. like(John, snow)


Ques: x [member(x, Alpine)
28-07-05

mc(x)
Prof. Pushpak Bhattacharyya, IIT
Bombay
~sk(x)]
20
Inference Strategy - RESOLUTION
Basic Idea: REFUTATION of the goal
Proof by contradiction
Suppose the goal is false. Then show contradiction in the knowledge base.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
21
Steps in Inferencing
Convert all expressions, including the falsified goal, into clauses.
1. member (John, Alpine)
2. member (Jack, Alpine)
3. member (Jill, Alpine)
4. ~ member(x1, Alpine) ν mc(x1) ν sk(x1)
5. ~ sk(x2) ν like(x2,snow)
6. ~ mc(x3) ν ~ like(x3,rain)
7. ~ like(John, x4) ν ~ like(Jack, x4)
8. like(John, x5) ν like(Jack, x5)
9. like(John, rain)
10. like(John, snow)
11. ~ member(x6, Alpine) ν ~ mc(x6) ν sk(x6)
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
22
Run Resolution
By unification find value for x6
Theory of resolution: given P & ~P ν Q
Resolvents
we can obtain Q (Resolute)
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
23
Inverted Tree Diagram
~P ν Q
P
Q
Aim
C1
C2
Indicates contradiction
null clause
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
24
Goal with Negation

~[ x{(member (x, Alpine) Λ mc(x) Λ ~ sk(x))}]

x[~ member (x, Alpine) ν ~ mc(x) ν sk(x)]
11. ~ member(x6, Alpine) ν ~ mc(x6) ν
sk(x6)
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
25
Monotonic Logic
Every step of resolution increases the knowledge base monotonically.
Non-monotonic logic which used default reasoning.
NEGATION BY FAILURE
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
26
Modus Ponens & Modus Tolens
Modus Ponen:
P & P →Q
gives Q
Modus Tolens:
~Q and P →Q
gives ~P
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
27
Prolog
Predicate calculus (HORN Clause)
+
Resolution
HORN Clauses: All the implications have a single literal as consequent.
A(antecedent) → B(consequent)
B is a single literal, never contain any operator.
Moreover B has to be a positive literal.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
28
Summary
• AI is a fascinating discipline, needing input from many
branches of knowledge.
• Scaling up and robustness are the needs of today’s world.
• Web has introduced new challenges to the field.
• Language processing and machine learning have assumed
great importance.
• In this lecture we took a look at two core areas: search and
reasoning, which will be developed further.
• Will delve into other areas as the course progresses.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
29
Reading Material
• Basic Text Books
– Russell S, Norvig P (1995) Artificial Intelligence: A
Modern Approach, Prentice Hall Series in Artificial
Intelligence. Englewood Cliffs, New Jersey
– Nilsson N. J. (1980) Principles of Artificial Intelligence,
Morgan Kaufmann Publishers Inc.
• Journals
– AI, IEEE SMC, Machine Learning, Computational
Linguistics
• Proceedings of
– AAAI, ECAI, IJCAI, ICML, ACL, COLING etc. etc.
28-07-05
Prof. Pushpak Bhattacharyya, IIT
Bombay
30