Transcript chp10

Chapter 10: Artificial Intelligence

Outline





Introduction
Main tasks
Knowledge
representation
Recognition tasks
Reasoning tasks
Social Issues
Applications
Software
Virtual Machine
Hardware
Algorithmic Foundations
1
Introduction

Artificial Intelligence (AI)



The part of computer science that exploits human
intelligence in deriving computer algorithms
The more we know how human intelligence works, the more
“intelligent” computer-based solutions can be achieved.
Is the machine “intelligence” not enough?




No …
Because we still have a multitude of problems that cannot be
solved by a computer at all.
Because we still have a multitude of (unfortunately practiceclose) problems that are solvable but need years or hundreds
of years to come to a result.
Because humans are “more intelligent” than computers in a
variety of situations.
2
Introduction

Turing Test


A. Turing proposed in 1950s a method to test the
intelligence of machines
Human interrogates two entities




Entity 1: Human
Entity 2: Computer
Interrogator is not allowed to see where an answer comes
from (e.g. answers are printed prior to inspection)
Test:

If as a result of the questioning, the interrogator is not able to
determine which answer originates from the computer and
which answer originates from the human, then the computer
has passed the Turing intelligence test.
3
Introduction

Examples:



Is your partner in a chess game a computer or a human?
Are you communicating (e.g. by email) with a computer or
humans?
Problems with Turing Test:



Measures intelligence of computers based on human
intelligence.
This kind of comparisons are no more of interest, since
computer should support humans and NOT replace them.
Also:



What about interrogator’s intelligence?
What types of questions are representative ones?
…
4
Introduction

Roughly speaking there were two phases in the
history of AI



Initial euphoric phase with great expectations, which were
not realized. (science fiction remained science fiction!)
Current phase with more realistic expectations and with
valuable results.
Observe:


Artificial: may mean apparent, non-genuine, mimed, …
Intelligence: may mean thought-based information, the right
information in the right place/time, …
5
Main Tasks

Let us focus on three human tasks:

Computational tasks






Recognition tasks




Adding columns of numbers
Sorting a list of numbers
Search a given name in telephone book
Manage the payroll of a company
…
Recognizing your best friend
Understanding the spoken word
Finding the tennis ball in the grass in your backyard
Reasoning tasks



Planning what to wear today
Deciding on the strategic directions of a company in the next five years
Running an alarm after an earthquake
6
Main Tasks

Humans and computational tasks:


Humans can follow algorithmic steps in order to come to a result
But results should be found very quickly:




Computers and computational tasks





Humans make mistakes
Get bored
And become sloppy
Computers are the specialists in this domain (and only this
domain?)
They don’t get bored and don’t become sloppy
They are very fast in following stepwise instructions
This is why we emphasized the step-by-step instruction processing
so much in the early chapters
 computers are better than humans in performing
computation tasks provided that an efficient step-by-step
solution (algorithm) is used
7
Main Tasks

Humans and recognition tasks






We, humans, are good in recognition tasks
We exploit our sensory-recognition-motor skills very
effectively
We receive information through our senses (hearing, seeing)
We can recognize the information we “sensed”
And we usually response to the received information by
“doing” something (e.g. movement)
Compare: an infant (a few weeks old) is able to recognize
his/her mom’s face!!, BUT the same person will need in
general at least six/seven years in order to perform basic
arithmetic operations
8
Main Tasks

How do we recognize things?


This topic is shared by different science disciplines
Consider recognizing your best friend:





You have a “database” of pictures in your brain
When you see your best friend, you match his/her picture against
your “file”
If the match was successful you will probably laugh and select a
specific manner of communication (e.g. language)
Moreover:
 You can recognize your best friend’s sister even if you have
never seen her before
 Thus you don’t need exact or complete information for
recognition!
Computers are not that good in recognition tasks
9
Main Tasks

Humans and reasoning tasks



We use also here a large storehouse of information (e.g.
experience)
This information consists not only of immediate facts like images
but also of cause-and-effect rules
Example: wearing a coat in a winter day




You decide to wear a coat because you know by experience that you
would be uncomfortable without a coat
Reasoning steps
 I don’t want to be cold
 If it is winter and I don’t wear a coat, then I will be cold
 It is winter now
 Conclusion: I will wear a coat
To mimic reasoning steps using a computer is a challenging task
We, humans, can often come to a conclusion even if we do not
have enough information, we may be ambiguous, and exploit
intuition
10
Knowledge Representation




From the previous assessment it follows that AI tries
to improve computer ability for solving recognition
and reasoning problems
Likewise, it was mentioned that for these tasks to be
achieved, information bases (e.g. picture databases)
are needed
Thus: we need to tackle the problem of representing
information (knowledge) in a computer system
Knowledge:


Facts or truths about some topic
Rules for gaining new facts
11
Knowledge Representation

How to represent knowledge?

Natural language:

For example:
“Spot is a brown dog, and, like any dog, has four legs and a tail. Also, like
any dog, Spot is a mammal, which means Spot is warm-blooded.”


Notice that these “strings” have a meaning and have to be treated as
such
Formal language:



x: entity e.g. a dog
A(x): x has attribute A
Above example:






Dog(Spot)
Brown(Spot)
For all x: Dog(x)  FourLegs(x)
For all x: Dog(x)  hasTail(x)
For all x: Dog(x)  isMammal(x)
For all x: isMammal(x)  isWarmBlooeded(x)
12
Knowledge Representation

Pictorial representation:




Give the picture of Spot showing that it is brown and has four
legs and a tail
+: additional information can be contained
-: attributes warm-blooded and mammal cannot be
represented, additional text is necessary
Graphical representation

Semantic net
Mammal
has
is a
Warm blood
4 legs
has
Dog
has
instance
Spot
is color
brown
tail
13
Knowledge Representation

What type of representation to use:





It depends on the application domain
E.g. for computer vision, rather pictorial
Semantic nets are extensible and therefore are appropriate
for capturing non-complete knowledge
Natural languages are not as exact as formal languages.
General criteria for representation methods:




Adequateness
Efficiency
Extensibility
Appropriateness
14
Recognition Tasks


AI sometimes tries to mimic the way of human
thinking ( brain functions)
But how does our brain function?






1011-1012 neurons
Stimuli “enter” a neuron though dendrites
Stimuli “exit” a neuron through axons
Axons connect to other dendrites by synapses
A neuron gathers stimuli from dendrites
If the sum of signals is higher than a threshold, the neuron
fires; it sends a new signal down its axon and affects other
neurons in its neighborhood
15
Recognition Tasks

Neural Network







Computer scientists have developed (artificial) neural networks to
simulate the work of our brain in order to solve problems related to
recognition
Hardware or software implementation
Each node represents the nucleus of a neuron
Each node has a specific threshold value
Each node has a number of weighted input lines; the dendrites
Each node has a number of output lines; the axons/synapses
 If sum of weighted inputs >= threshold, then output is activated
Weight 1
Weight 2
Weight 3
Node
(Nucleus)
Weight
16
Recognition Tasks

Example: recognizing two character patterns:

Node: Class A



Node: Class B



Input: all shapes of a “B”
Output: to “Different” and “Equivalent” nodes
Examples:




Input: all shapes of an “A”
Output: to “Different” and “Equivalent” nodes
Inputs: A and A  Equivalent is activated
Inputs: B and B  Equivalent is activated
Inputs: A and B  Different is activated
How to come to the correct weights:  training

Training phase (done automatically by a “trainer” module):



Network is fed by an initial set of input with known output
Weights are iteratively adjusted until actual output is close enough to
desired output
Compare: training a dog until it “hardwires” things in its brain
17
Recognition Tasks

Example network
A
2
2
A
2
2
Class A
1
A
Different
3
-2
2
B
B
2
2
2
Class B
1
-2
Equivalent
-3
B
18
Recognition Tasks

Neural networks have been applied in a wide range
of areas:








Handwriting recognition
Speech recognition
Recognizing bad credit risks in loans
Predicting the odds of cancer susceptibility
Limited visual recognition
Segmenting magnetic resonance images in medicine
Adapting mirror shapes for astronomical observations
Discovering a good routing algorithm in a computer network
19
Reasoning Tasks


How do humans reason in a logical way?
Example: Triage center in a hospital

Understanding the situation





Conclusion:




Capability of staff
Availability of resources
Older experiences
…
Patient A: first priority
Patient B: second priority
…
In AI, rule-based systems (or expert systems) are
used to emulate this kind of reasoning
20
Reasoning Tasks

A rule-based system consists of:



A knowledge base and
An inference engine
Knowledge base:


Set of facts and rules about a special domain
Examples (compare Prolog facts and rules):
F1: Lincoln was president during Civil War
F2: Kennedy was president before Nixon
F3: FDR was president before Kennedy
R1: if X was president before Y, then X precedes Y
R2: if X was president before Z and Z precedes Y, then X precedes Y
21
Reasoning Tasks

Inference Engine:



How to generate new facts from the knowledge base
Example 1:
F2: Kennedy was president before Nixon
R1: if X was president before Y, then X precedes Y
F2 and R1 lead to a new fact F4:
F4: Kennedy precedes Nixon
Example 2:
F3: FDR was president before Kennedy
R2: if X was president before Z and Z precedes Y, then X precedes Y
F3, F4, and R2 lead to a new fact F5:
F5: FDR precedes Nixon
22
Reasoning Tasks

Inference Engine:





Basic meta-rule we are using to infer new knowledge is:
Given the fact A and the rule if A then B,
then infer a new fact B.
Using this meta-rule, called modus ponens, new facts can be “learned”
from older ones.
These new facts may let other rules in the knowledge to be used in
order to generate further new facts, and so on.
The process of inference is repeated until no new rules can be inferred.
Two policies for inference:
Forward chaining: Match facts to the if-branches of rules (like our
examples)
Backward chaining: Match facts to the then-branches of rules
23