Books

• Artificial Intelligence by Elaine Rich, Knight -

Mc Graw Hill
• AI: A Modern Approach by Stuart J. Russel,
Peter Norvig - Pearson Education
Introduction
 Artificial Intelligence

Artificial Intelligence

• Not Real • Logic

• Simulated • Understanding
• Example ? • Self-awareness
• Learning
• Emotional knowledge
• Planning
• Problem solving
• Example?
 What is Artificial Intelligence ?
• making computers/machines that think?
• the automation of activities we associate with
human thinking, like decision making, learning
... ?
• the art of creating machines that perform
functions that require intelligence when
performed by people ?
 So, AI is defined as:
– AI is the study of ideas that enable computers to
be intelligent.
– AI is the part of computer science concerned with
design of computer systems that exhibit human
intelligence(From the Concise Oxford Dictionary)
From the above two definitions, we can see that
AI has two major roles:
– Study the intelligent part concerned with humans.
– Represent those actions using computers.
 What is Artificial Intelligence ?

THOUGHT Systems that thinkSystems that think

like humans rationally

Systems that act Systems that act

BEHAVIOUR like humans rationally

HUMAN RATIONAL
 Goals of AI
• To make computers more useful by letting
them take over dangerous or tedious tasks
from human

• Understand principles of human intelligence

The Foundations of AI

•Philosophy (423 BC - present):

- Logic, methods of reasoning.
- Mind as a physical system.
- Foundations of learning, language, and rationality.

• Mathematics (c.800 - present):

- Formal representation and proof.
- Algorithms, computation, decidability, tractability.
- Probability.
 The Foundations of AI
• Psychology (1879 - present):
- Adaptation.
- Phenomena of perception and motor control.
- Experimental techniques.

• Linguistics (1957 - present):

- Knowledge representation.
- Grammar.
 A Brief History of AI
• The gestation of AI (1943 - 1956):
- 1943: McCulloch & Pitts: Boolean circuit model of brain.
- 1950: Turing’s “Computing Machinery and Intelligence”.
- 1956: McCarthy’s name “Artificial Intelligence” adopted.

• Early enthusiasm, great expectations (1952 - 1969):

- Early successful AI programs: Samuel’s checkers, Newell
& Simon’s Logic Theorist
- Robinson’s complete algorithm for logical reasoning.
 A Brief History of AI
• A dose of reality (1966 - 1974):
- AI discovered computational complexity.
- Neural network research almost disappeared in
1969.
1970: (first) AI Winter

• Knowledge-based systems (1969 - 1979):

- 1976: MYCIN by Shortliffle.
- 1979: PROSPECTOR by Duda et al..
 A Brief History of AI
• AI becomes an industry (1980 - 1988):
- Expert systems industry booms.
- 1981: Japan’s 10-year Fifth Generation project.

• The return of NNs and novel AI (1986 -present):

- Mid 80’s: Back-propagation learning algorithm reinvented.
- Expert systems industry busts.
- 1988: Novel AI (ALife, GAs, Soft Computing, …).
-1995: Agents everywhere.
-1997: Deep Blue
-2003: Human-level AI back on the agenda
-2013: Atari Games
-2015: AlphaGo
 A Brief History of AI
• 21st Century
- Deep learning
- Big Data
- Artificial General Intelligence?
- Super Intelligence?
AI can be achieved in many ways-
 Areas of AI and Some
Dependencies
Knowledge
Search Logic Representation

Machine
Planning
Learning

Expert
NLP Vision Robotics Systems
 Questions need to discuss
1. What are the underlying assumptions about the
intelligence?
2. What kinds of techniques will be useful for
solving AI problems?
3. At what level of detail, we are trying to model
human intelligence?
4. How will we know we have succeeded in building
an intelligent program?
 The Underlying Assumption
• Physical Symbol System
– It consists of set of entities, called symbols
– Symbols can occur as components of another type of entity
called an Expression
– A Symbol structure is composed of number of instances of
symbols related in some physical way.
– A whole System is collection of
• these symbol structures,
• Collection of processes that operates on expressions
to produce another expression
• Process of creation, modification, reproduction and
deletion
– A Physical Symbol System is a machine that produces
through time an evolving collection of symbol structures
 The Underlying Assumption(contd…)
• Hypothesis
– A physical Symbol system has necessary and sufficient
means of general intelligent actions
• Problems to prove Hypothesis
– Difficult to prove by giving evidences, As there are
equal no of evidences that say it is true or false.
– Difficult to make programs that do all the selected
tasks.
– Evidence in support came from areas like Game
Playing, visual perception
– Evidence in oppose came from areas such as human
psychology such as understanding of Jokes.
AI Applications
 AI Techniques
Intelligence requires knowledge. All AI techniques agrees the following
properties of knowledge
– Voluminous
– Hard to characterize accurately
– Constantly changing
– Differs from data by being organized in a way that corresponds the ways
it is being used.
• AI technique is a method that exploit knowledge with following property
– Knowledge captures generalizations.
• With this property data become the knowledge. Data are categorized
according to its properties.
– Understood By people who must provide it.
– Can easily be modified to correct errors.
– Can be used in many situations even if it is not complete or accurate.
– Can be used to narrow the range of possibilities.
 AI Techniques
Although AI techniques are not necessary to be
applied on AI problems and further they can be
applied on the non-AI problems. To elaborate this
further, we will look at following two problems and
try to solve these by different techniques.
– Tic-Tac-Toe Problem
– Question Answering Problem
• Different techniques used varies in
– Their complexity
– Their use of generalizations
– Clarity of their knowledge
– Extensibility of their approach
 Tic-Tac-Toe Program 1
• Data Structures
– Board: A nine element vector representing the board
• Value 0 means Square is blank
• Value 1 means Square contains X
• Value 2 means Square contains 0
– Movetable: A large vector of 19683 elements(3^9), each
element of which is nine-element vector
• Algorithm
1. View the vector board as ternary number (base three).
Convert it into decimal number
2. Use the number computed above as an index into the
movetable and access the vector stored there.
3. The vector selected in the step 2 represents the way the
board will look after the move that should be made.
 Tic-Tac-Toe Program 1
• Comments
– Efficient in terms of time.
– Takes a lots of space to store the movetable vector
– Manual work is needed to store the entries into
the table without any error.
– Cannot be extended, say to 3 dimensions because
that will require 3^27 board positions to store.
 Tic-Tac-Toe Program 2
• Data Structures
– Board: A nine element vector representing the board
• Value 2 means Square is blank
• Value 3 means Square contains X
• Value 5 means Square contains O
– Turn: An integer indicating which move of the game is about to be
played; 1 indicates the first move, 9 the last.
• Algorithm
– The main algorithm uses three sub procedures.
– Make2: Returns 5 if the centre square of the board is blank, that is if
board[5]=2. otherwise, this returns any non-blank square(2,4,6 or 8)
– Posswin(p): Returns 0 if player p can not win on his next move;
otherwise it returns the number of the square that constitutes the
winning move.
• This function will enable the program both to win and to block the
opponent’s win.
 Tic-Tac-Toe Program 2
– Posswin operates by checking one row, column &
diagonal at a time.
– It multiplies the values in squares for a particular
row, column or diagonal to check win as follows
• If product is 18(3*3*2) then X can win
• If the product is 50(5*5*2) then O can win
– If we find a winning row then number of blank
square is returned.
• Go (n) : makes a move into square n.
– This procedure sets the board [n] to 3 if turn is
odd, or 5 if turn is even. It also increments the turn
by one.
 Tic-Tac-Toe Program 2
• The algorithm has in built strategy for each move as
follows:
– Turn-1 : Go(1) (upper left corner)
– Turn-2: if Board[5] is blank then Go(5) else Go(1)
– Turn-3: if Board[9] is blank then Go(9) else Go(3)
– Turn-4: if posswin(X) is not 0, then Go(posswin(X)) else
Go(Make2)
– Turn-5: if posswin(X) is not 0, then Go(posswin(X)) else if
posswin(O) is not 0 then Go(Posswin(O)){i.e. block
opponent’s Win; else if Board*7+ is blank then Go(7) else
Go(3).
– Turn-6: if posswin(O) is not 0 then Go(Posswin(O)) else if
posswin(X) is not 0, then Go(posswin(X)) else Go(make2).
 Tic-Tac-Toe Program 2
– Turn-7: if posswin(X) is not 0, then Go(posswin(X))
else if posswin(O) is not 0 then Go(Posswin(O)) else
goanywhere that is blank.
– Turn-8: if posswin(O) is not 0 then Go(Posswin(O))
else if posswin(X) is not 0, then Go(posswin(X)) else
go anywhere that is blank.
– Turn-9: Same as Turn=7.
• Comments
– Not efficient in terms of time since it has to check
the several conditions before making each move.
– Efficient in terms of space.
– Not easy to extend to 3-dimensional program.
 Tic-Tac-Toe Program 3
• Data Structures
– A nine element vector representing the board
– A List of Board positions that could result from the next move
– A Number representing the estimate of how likely the board
position is lead to an ultimate win for the player to move.
• Algorithm
– To decide on next move; look ahead at the board position that
result from each possible move. Make the best move and assign
the rating of best move to the current position.
– To decide which of the board position is best, do the following for
each of them
• See if it is a win, call it best by giving highest rating
• Consider all the moves the opponent could make next, See which
of them is worst for us. Assume the opponent will make that move.
Whatever rating that move has , assign it to node we are
considering
• Best node is the one with highest rating
 Tic-Tac-Toe Program 3
• Comments
– Require much more time than others since it must
search a tree representing all possible moves before
taking each move.
– It could be extended for 3-D Tic-Tac-Toe and for
other games as well.
– This program is an example of an AI technique.
– For very small problems it is less efficient but it can
be used where other methods fails.
 Question Answering Problem
• In question answering problem, we want that our
program reads some English text and then answer some
questions based on that.
• These types of problems are tough and different from
Tic-Tac-Toe because we can not precisely state that what
our problem is and what constitute correct solution to it.
• For lack of better technique, we will illustrate 3
different methods to define the question answering
problem.
• Whether these methods are successful to find the
solution, depends upon the fact that how much the
solutions generated by these method appeal to the other
people.
 Question Answering Problem
• In order to compare these methods we illustrate
all of them by using the following text
– Mary went shopping for a new coat. She found a
red one she really liked. When she got it home, she
discovered that it went perfectly with her favourite
dress.
• The question that we will attempt to answer are
– Q1: What did Mary go shopping for?
– Q2: What did Mary find that she liked?
– Q3: Did Mary Buy anything?
 QA Problem Program 1
• This program attempts to answer questions by matching the
text fragments in the questions against the input text .

• Data Structures:
– Question Patterns: A set of templates that matches common
question forms. From these question pattern we produce
patterns that are to be used to match against input text.
• e.g If the template “who did x y” matches an input question, then
the text pattern x y z is matched against the input text and the
value of z is given as an answer to the question.

– Input Text
– Questions
 QA Problem Program 1
• Algorithm
– Compare each element of question pattern against
the questions and use all those that match
successfully to generate a set of text patterns.
– Pass each of these patterns through a substitution
process that generates alternative forms of verbs
such as “go” in the question might match “went” in
the text pattern.
– Apply these text patterns to the text and collect
the resulting answers.
– Reply with the set of answer just collected.
 QA Problem Program 1
• First Question :The template “What did x y” matches this
question and generates the text pattern “Mary go shopping
for Z”. After Pattern substitution this expands to set of pattern
including
– “Mary goes shopping for Z”
– “Mary went shopping for Z”
The latter pattern matches the input text and is produced as a
solution.
• Second Q:Unless the template set is very large and allow
insertion or modification of certain phrases in Q pattern, text
pattern and input text, This question can not be answered.
• Third Q: Since no answer to this question is contained in the
text, no answer will be found.
 QA Problem Program 1
• Comments
– The approach is clearly inadequate to answer the
questions that people could answer after reading
the simple text.
– Further answering depends upon the pattern we
have stored already and the substitutions we have
allowed in the text.
 Introductory Problem: Question
Answering
Program 2:
Structured representation of sentences:
Event2 Thing1 Event 2

Instance: Finding Instance: Coat Instance: Liking

Tense: Past Colour: Red Tense: Past

agent: Mary Modifier: much

object: Thing1 object: Thing1
 Introductory Problem: Question
Answering
Program 3:
Background world knowledge:
C enters L

C begins looking around

C looks for a specific M

C looks for any interesting M
C asks S for Help

C finds M’ C fails to find M

C Leaves L C buys M’ C leaves L Goto step 2

C Leaves L
 Criteria of Success
• Goal - to simulate human performance

• Measure of success- the extent to which the

program’s behaviour corresponds to that
performance.

• How to measure success- Experiments and

protocol analysis.
 AI Applications
• Autonomous Planning & Scheduling:
– Autonomous rovers.
– Telescope scheduling
 AI Applications
• Autonomous Planning & Scheduling:
– Analysis of data:
 AI Applications
• Medicine:
– Image guided surgery
– Image analysis and enhancement
 AI Applications
• Transportation:
– Image Enhancement
– Autonomous vehicle control
 AI Applications
• Transportation:
– Pedestrian detection:
 AI Applications
Games:
 AI Applications
• Robots:
 AI Applications
Other application areas:
• Bioinformatics:
– Gene expression data analysis
– Prediction of protein structure
• Text classification, document sorting:
– Web pages, e-mails
– Articles in the news
• Video, image classification
• Music composition, picture drawing
• Natural Language Processing .
• Perception.
Sci-Fi AI
 Advantages of AI
– more powerful and more useful computers
– new and improved interfaces
– solving new problems
– better handling of information
– relieves information overload
– conversion of information into knowledge
 Disadvantages of AI
– increased costs
– difficulty with software development - slow
and expensive
– few experienced programmers
– few practical products have reached the
market as yet.
 Quiz: Which of the following can be done
at present?
• Play a decent game of table tennis?
• Play a decent game of Jeopardy?
• Drive safely along a curving mountain road?
• Buy a week's worth of groceries on the web?
• Buy a week's worth of groceries from some store?
• Discover and prove a new mathematical theorem?
• Converse successfully with another person for an hour?
• Perform a surgical operation?
• Put away the dishes and fold the laundry?
• Translate spoken Chinese into spoken English in real
time?
• Write an intentionally funny story?