Transcript Intelligent Systems

Intelligent Systems
Introduction Part 2
1
AI Areas
1. Alan Turing defined intelligent behavior as the
ability to achieve human level performance in
cognitive tasks, sufficient to fool an interrogator
2. Minsky defined intelligence in terms of
mechanisms. e.g., a human is a 'meat' machine
3. More recently some scientists have come to view
intelligence as a genetic process - evolving in a
competitive environment. The more competitive
the more intelligent.
4. Insect Intelligence
2
5. Recently Hybrid Systems
In terms of Software
1.
2.
3.
4.
Knowledge based systems, expert systems
Neural Networks
Genetic algorithms, genetic programming
Particle Swarm Optimization
3
Early AI
• 1950 – 1953: Early chess programs
(Shannon and Turing)
• 1956: Logic Theorist (Newell and Simon)
• 1960 – 1972( SAINT (Calculus),
ANALOGY (Geometric analogy),
STUDENT (read and solved high school
algebra word problems) - Winograd
4
ANALOGY
5
STUDENT
If the number of customers Tom gets is three times the
square of 20 percent of the number of advertisements he runs,
and the number of advertisements he runs is 45 what is the
number of customers Tom gets?
6
Early Operational Definition of
Intelligence - Herb Simon
A (mental) act or series of acts is intelligent if it accomplishes
something that, if accomplished by a human being, would be called
intelligent.
“I know my friend is intelligent because he plays pretty good chess
(can keep a car on the road, can diagnose symptoms of a disease,
can solve the problem of the Missionaries and Cannibals, etc.). I
know that computer A is intelligent because it can play excellent
chess (better than all but about 50 humans in the entire world). I
know that Navlab is intelligent because it can stay on the road, etc,
etc. The trouble with those people who think that computer
intelligence is in the future is that they have never done serious
7
research on human intelligence.”
Class Exercise
Solve this problem
8-Puzzle: Arrange the tiles so that all the tiles are in the correct positions.
Goal
1 2 3
8
4
7 6 5
Start
134
862
7 5
http://www.permadi.com/java/puzzle8/
8
Class Exercise
How much money is sent?
Crypt Arithmetic
SEND
+ MORE
MONEY
9
Class Exercise
Solve this game problem
MC Problem: There are three missionaries and three cannibals on the left bank
of a river. They wish to cross over to the right bank using a boat that can only
carry two at a time. The number of cannibals on either bank must never exceed
the number of missionaries on the same bank, otherwise the missionaries will
become the cannibals' dinner! Plan a sequence of crossings that will take
everyone safely across.
http://www.learn4good.com/games/puzzle/boat.htm
10
What do these problems have in common?
11
State Space Problem Solving
States
Initial State
Operators are rules that expand a state into a new states.
(Operators have costs associated with them.)
Goal State
Path cost
Branching Factor: If each state can be expanded into (generates)
b new states at the next level we say that the branching factor is b
1 + b + b2 + …. + bd
12
State of a MC problem
the number of missionaries on the left bank,
the number of cannibals on the left bank,
the side the boat is on.
All other information can be deduced from this
state(M,C,side)
Start state is: state(3,3,left)
End state is: state(0,0,right)
13
Search Algorithm
Specify the problem {state space, initial states, goal state, set of
operators}
Start from an initial state
Set the frontier to the initial state
loop: If the frontier is empty fail;
remove a choice s from the frontier and set path to this choice
if s is a goal succeed (return the path);
expand the choice (for a in actions add [path + a -> Result(s,a)]
to frontier)
The algorithm terminates when we have found the goal state or there
are no new states to be found or time has expired
14
Ways of making the choice
15
Uniform Cost Search
g(n) is the cost of the search to node n
chooses the lowest cost node on the frontier.
Uniform cost search is breadth first search
with g(n) = DEPTH(n)
16
Modifications
Depth-limited search
Iterative deepening - a depth first
search is run repeatedly, increasing
the depth limit with each iteration
17
Bi-directional
18
Find a route from
Arad to Bucharest
Class Exercise
Find a route from Arad to Bucharest
Using Depth first
Using Breadth first
For uniformity assume nodes ordered anti clockwise
starting from west first come first expanded
How would you then find a shortest (least cost) route?
Heuristic Functions
Humans intuitively uses heuristics
h(n) = estimated cost of the cheapest path from node n to a
goal state.
21
Now find a shortest route from
Arad to Bucharest
22
Exercise
The straight line distance may be used as an heuristic to
estimate the cost to the destination
h(n) = d(n, Bucharest)
Question: If this heurisic function is used what path will be
selected [Resolve node selection from vertically up
clockwise and first come first expanded]? Breadth first ?
23
A* Search
The selection function used is f(n) = g(n) + h(n)
where g(n) is the actual cost of the path to n, and,
h(n) is the heuristically estimated cost from n to the goal
state
A* is optimal provided that h(n) does not overestimate
the cost from n to the destination.
Question: If this heuristic function is used what path will
be selected?
Early AI
• Was all about searching using heuristics
• Computer Scientists thought that difficult
AI problems could be solved by heuristic
search
• The 8-puzzle can be solved very
successfully using a particular heuristic.
What do you think such an heuristic can
look like?
25
Difficulties with Early AI
The main difficulties for early AI were:
 Because AI researchers were developing general
methods for broad classes of problems, early
programs contained little or even no knowledge
about a problem domain. To solve problems,
programs applied a search strategy by trying out
different combinations of small steps, until the right
one was found. This approach was quite feasible for
smaller problems, so it seemed reasonable that, if
the programs could be “scaled up” to solve large
problems, they would finally succeed.
26
Domain Knowledge
• The power of AI programs to perform at high
levels of competence is primarily a function of the
program's knowledge of its task domain, and not
of the programs reasoning process.
• 1969 - 1982: DENDRYL, MYCIN, Prospector
• 1975: Frames (Objects) (Minski)
• 1982: R1 (McDermott)
27
Knowledge Based Systems
• To build an intelligent computer system, we
have to capture, organize and use human
expert knowledge in some narrow area of
expertise.
28
Narrow Domain Turing Tests
• A program thought intelligent in some
narrow area of expertise is evaluated by
comparing its performance with the
performance of a human expert.
29
The technology of expert systems,
the key to success

Probably the most important development in the
eighties was the realisation that the domain for
intelligent machines had to be sufficiently
restricted.
30
Knowledge Based Systems
•
•
•
•
•
Tax Cut: rule based tax advisor
Configurators
Medical Diagnosis
Pension regulation helpers
Insurance
31
Modeling Human Intelligence

AI researchers decided to have a new look at
neural networks (mid-1980s – onwards)
32


The real breakthrough came in 1986 when the backpropagation learning algorithm, first introduced by
Bryson and Ho in 1969 (Bryson & Ho, 1969), was
reinvented by Rumelhart and McClelland in Parallel
Distributed Processing (1986).
Artificial neural networks have come a long way
from the early models of McCulloch and Pitts to an
interdisciplinary subject with roots in neuroscience,
psychology, mathematics and engineering, and will
continue to develop in both theory and practical
applications.
33
Use of Prediction
What would you do if you had $10000CA and $50000ZAR?
Evolutionary Meaning of
Intelligence
• Genes, chromosomes
• Evolutionary fitness (survival of the fittest)
• Competing populations
35
Insect Intelligence
• Realization that insects are constantly
optimizing survival parameters
• Particle Swarm Optimization
• Ant Colony Optimization
• Bees Algorithm
36
Hybrid Intelligent Systems
• Combination of powerful techniques
applied to solve a problem
• Different components solved by hybridizing
intelligent systems
• From loosely coupled to tightly coupled
37
Stand Alone Models
• Independent components that do not interact
• Solving problems that have naturally
independent components – eg., decision
support and categorization
Transformational
• Expert systems with neural networks
• Knowledge from the ES is used to set the
initial conditions and training set of the NN
Transformational
• An ANN uses a GA to optimize its topology
Integrated – Fused Architectures
• Combine different techniques in one
computational model
• Share data structures and knowledge
representations
• Extended range of capabilities – e.g.,
classification with explanation, or,
adaptation with classification
Can Computer Intelligence equal
human intelligence?
• AI may have a comparative advantage in
some areas
• Example: electronic book is both more and
less than a real book
• Virtual shopping mall is similarly different
from a real mall
• Robotic Soccer
42
AI Topics
http://www.aaai.org/AITopics
AI Topics
a dynamic library of introductory information about
Artificial Intelligence
43