Transcript CSCE4310-1 - Computer Science and Engineering

CSCI 4410
Introduction to Artificial Intelligence
What is AI?
Difficult to define
 “The Intelligence of a System is
inversely proportional to our
understanding of it”

What is AI?

making computer programs that appear to 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 ?

the study of mental faculties through the use of
computational models ?

the study of computations that make it possible to perceive,
reason and act ?

a branch of computer science that is concerned with the
automation of intelligent behavior ?

anything in Computing Science that we don't yet know how
to do properly ?
AI

“The art of creating machines that perform
functions that require intelligence when
performed by people.” (Kurzweil)

“The study of how to make computers do
things at which, at the moment, people are
better.” (Rich and Knight)

But what about creativity?

Many would argue machines are already writing
rap music and reality shows
Rational Systems

How do we know how humans think?
Introspection vs. psychological
experiments
 Brain research (scanning, experiments,
testing)


Cognitive Science
Rational Systems
Humans are not always ‘rational’
 Rational - defined in terms of logic?
 Logic can’t express everything (e.g.
uncertainty)
 Logical approach is often not feasible
in terms of computation time - needs
‘guidance’
 We will never get to intelligence with
rules

Satisfiability
Rule systems must be checked
 This is the Satisfiability Problem
 NP-complete
 Checking all the states of a large rule
system is computationally expensive

Turing Test
Described by Alan Turing in 1950
 A human judge engages in a natural
language conversation with a human
and a machine
 If the judge cannot reliably tell which
is which, then the machine passes the
Turing test.
 The conversation is usually limited to
text.

Turing Test

However…
Turing Test

A machine passing the Turing test
may be able to simulate human
conversation





Is this intelligence?
how do we know humans don't just
follow rules?
Blockhead – all paths
Chinese room - rules
Can young children pass the test?
Turing Test



Turing test measures human-like
behavior
Even if the Turing test is a good
definition of intelligence, it may not
indicate consciousness.
Does intelligence imply
consciousness?
Practical AI

Do we care whether a system:
 Replicates human thought
processes
 Makes the same decisions as
humans
 Uses purely logical reasoning
AI in Practice

Medical advice system

Part-picking robots

Credit card fraud detection

Spam filters

Medical diagnosis, teleoperated/micro
surgery
AI in Practice

Information retrieval, Google

Scheduling, logistics, supply chain
management

Aircraft and pipeline inspection

Speech recognition, generation,
translation
AI in Practice

And robots and chatbots
Heuristics

Two fundamental goals:
finding algorithms with good run times
and
 optimal solutions.

But… these goals are often mutually
exclusive
 A heuristic is an algorithm that
relaxes one or both of these goals

Heuristics
Special instances of the problem may
cause the heuristic to produce poor
results or run slowly
 These instances may be rare


Ex: sorting algorithms where the list is
already sorted
Matching the heuristic to the domain
is important
 Heuristics are very common in real
world implementations.

Example – Spam Assassin
Spam Assassin
 uses a wide variety of heuristic rules
to determine whether an email is a
spam or ham

Bayesian filter
 Blacklisting
 Regular expression matching

Modern Focus
Artificial intelligence can be considered under
a number of headings:
 Search
 Representing Knowledge and Reasoning
 Planning
 Uncertainty
 Learning
 Interacting with the Environment
(e.g. Vision, Speech, Robotics)
Search

Search is the fundamental technique of AI.

Possible answers, decisions or courses of action are
structured into an abstract space, which we then search.

Search is either "blind" or "informed":
 blind
 we move through the space without
worrying about what is coming next, but
recognising the answer if we see it
 informed
 we guess what is ahead, and use that
information to decide where to look next.

Desire for optimal solutions leads to heuristics
Knowledge Representation and
Reasoning

If we are going to act rationally in our environment, then we
must have some way of describing that environment.

how do we represent what we know about the world ?

how do we represent it concisely ?

how do we represent it so that we can get hold of the
right piece of knowledge when we need it ?

how do we generate new pieces of knowledge ?

how do we deal with uncertain knowledge ?
Planning
Given a set of goals, construct a sequence
of actions that achieves those goals:





often very large search space
but most parts of the world are independent of
most other parts
often start with goals and connect them to
actions
no necessary connection between order of
planning and order of execution
what happens if the world changes as we
execute the plan and/or our actions don’t
produce the expected results?
Uncertainty
Given the set of “uncertain” information, how
can we achieve the goals (and how certain
are we of that answer).
 How do we deal with uncertainty in our
daily lives?

How can we make this more systematic


How can we build systems that deal with
uncertainty
How can we insure that the systems are
reasonable and correct
Learning

If a system is going to act truly
appropriately, then it must be able to
change its actions in the light of
experience:

Generating new facts from old

How do we generate new concepts ?

How do we learn to distinguish different
situations in new environments ?
Knowledge
Virtually all techniques benefit from
‘common sense’
 CYC – a very large database of
general purpose knowledge

Resolving Ambiguity – Ex.

Consider the following pair of sentences:






Fred saw the plane flying over Zurich.
Fred saw the mountains flying over Zurich.
Humans recognize that in the first sentence,
"flying" refers to the plane
In the second sentence, "flying" almost certainly
refers to Fred.
Traditional Natural Language systems will have
difficulty resolving this syntactic ambiguity
Cyc knows that planes fly and mountains do not,
and can reject nonsensical interpretations.