Cranfield University, 16th November 2005

Useful Techniques in
Artificial Intelligence
-
Introduction

PRESENTED BY: Dr WILL BROWNE

Cybernetics,
University of Reading
Whiteknights
Reading
UK
Picture of Lt Commander Data
This 1100 spin Bosch machine is incredibly
quiet and positively high-end. It has
everything you would expect to find on a
Bosch including exclusive features like
the 3D AquaSpa wash system with Fuzzy
Control.
 Stanley
http://en.wikipedia.org/wiki/Darpa_grand_challenge

$2 million Prize awarded to Stanford Racing Team

Five teams completed the Grand Challenge; four of them
under the 10 hour limit. The Stanford Racing Team took the
prize with a winning time of 6 hours, 53 minutes.

The SRT software system employs a number of advanced

techniques from the field of artificial intelligence,
such as probabilistic graphical models and machine learning.

http://www.darpa.mil/grandchallenge/index.asp
http://www.darpa.mil/grandchallenge/gallery.asp
 Aim
To introduce the field of artificial
intelligence,

so that it is possible to

Determine if an artificial intelligence

technique is useful for a problem

and be able to

Select an appropriate technique for further

investigation.
 Objective

• Introduction to Artificial Intelligence

• Generic function of Artificial

Intelligence tools

• Review of major techniques

• Benefit and pitfalls of applying these

tools.
 Contents

• Applications of Techniques

• Description of Artificial Intelligence

Field

• Function of Important Techniques

• Benefit and Pitfalls of Applying

Techniques

• Summary
 Finance & Business

• Predict stock market trends

• Insurance/credit risk assessment

• Fraud detection
 Industry

• Communication: mobile phone

ground station & satellite networks

• Scheduling of work, transport, crane

operations and so on

• Routing of computer networks.

INTELSAT operates a fleet of 19 satellites

 Engineering

• Optimisation of route planning

• Design of complex structures

• Process optimisation
 Control

• Domestic appliances, such as

Microwave ovens

• Traffic flows

• Aircraft flight manoeuvres

 Academia

• Game playing, e.g., chess

• Robotic football

• Test problems, e.g., iterated

prisoner’s dilemma.
 “Definition” of AI

Artificial :-
easily understood

Artificial Intelligence :-
whole concept can be discussed

Intelligence :-
easy to recognise
hard to define
 Artificial

• Not Human, plant or animal

• Computer-based
(workstation, PC, parallel-computer
or Mac)

• Computer programs
 Artificial Intelligence

• Enable computers to perceive,

reason and act.

• Do jobs that currently humans do

better.

• Artificial Intelligence is what

Artificial Intelligence researchers
study.
 Intelligence

• Intelligence is the ability to store,

retrieve and act on data - efficiently
and effectively.

• Intelligence has insight and can go

beyond problem definition - but not
experience?

• True intelligence does not exist!

“How do you speak ‘Alien’?”
 Programme Languages

• Assembler

• C, C++, Java and FORTRAN

• Lisp, Small Talk and PROLOG

• Shells, e.g., G2 Expert System

• Toolboxes, e.g., Neural Networks in

Matlab.
 Function

NOT RELIANT UPON

MATHEMATICAL DESCRIPTION
OF DOMAIN.

(stochastic)

• May include mathematics within

technique

• May be similar to mathematical

techniques
 Functionality

Search Optimisation
Modelling
Knowledge-handling
Routing Scheduling
Visualisation Design Querying
Learning
Game-playing Adaptive-Control
Rule-Induction
Data-Access Data-Manipulation
PredictionDiagnosis
 Function Summary

EXPLORE v EXPLOIT

EFFICIENTLY AND EFFECTIVELY

 Functional Division of AI

Modelling -- Explore

Knowledge-Based -- Exploit

Optimisation -- Explore then

Exploit

Advanced -- Explore &

Exploit
 Theoretical Division of AI
ARTIFICIAL INTELLIGENCE TECHNIQUES

KNOWLEDGE BASED ENUMERATIVES

NON-GUIDED GUIDED
Expert Decision Case Based Backtracking Dynamic Branch &
Systems Support Reasoning Programming Bound

INTELLIGENT AGENTS
FUZZY LOGIC (inc. Artificial Life)

LEARNING
ANT CELLULAR IMMUNE
GUIDED COLONY AUTOMATA SYSTEMS

HILL CLIMBING
Tabu
REINFORCEMENT LEARNING
Search Simulated NON-GUIDED
Annealing

STATE-BASED Las Vegas

GENETIC EVOLUTIONARY COMPUTATION NEURAL NETWORKS

Hopfiled Kohonen Multilayer

Maps Perceptrons

GENETIC ALGORITHMS EVOLUTION STRATEGIES GENETIC

& PROGRAMMING PROGRAMMING

LEARNING CLASSIFIER SYSTEMS

 Knowledge-Based:
Expert Systems
What: Capture and reason about knowledge
(especially human) in a transparent form.

How: Store of rules and information (the

knowledge base)
Reason about information (inference
engine).

Where: Rolling Mill Expert System project.

Satellite control/maintenance.

IF Temp < 400 oC THEN Rolling is Poor

 Knowledge-Based:
Case Based Reasoning (CBR)
What: Past examples (cases) used to reason
about novel examples.

How: Store of cases and information

Reason and interpolate information
Update, maintain and repair cases.

Where: Decision support type systems.

Initial bridge design selection.

Temp Temp Temp

400 oC 450 oC 430 oC
Rolling Rolling Rolling
Poor Good ?
 Enumerative:
Branch & Bound
What: Knowledge stored in decision trees.
E.g., ID3 and C4.5

How: Domain is classified into sections

Tree of decisions is formed.

Where: Insurance fraud detection

Credit assessment.

Age > 25
T F
Sex = F
T F T F
250 300 300 425
 Fuzzy Logic

What: Grey or fuzzy (i.e. human) thinking in

computers.

How: Member sets formed to classify inputs

Overlap of sets allows imprecise logic.

Where: Domestic appliance ‘intelligence’,

e.g., washing machines & microwaves.

Distribution
in
department F M

5.2 5.6 5.10 6.2

Height
 Fuzzy Logic

What: Grey or fuzzy (i.e. human) thinking in

computers.

How: Member sets formed to classify inputs

Overlap of sets allows imprecise logic.

Where: Domestic appliance ‘intelligence’,

e.g., washing machines & microwaves.

Detergent :
Water ratio
Silk Wool

2 4 6 8
Weight
 Learning:
Guided Search
What: Optimisation techniques that avoid
being trapped in local optima.

How: Simulated Annealing

Probability of accepting new search point
Probability reduced near to optimum.
How: Tabu Search
Can not search previously visited point
Therefor will not become stuck.

Where: Optimisation problems, where

domain is described by a function.
http://www.exatech.com/Optimization/optimization.htm
 Learning:
Genetic Evolutionary Computation

What: Uses evolution to optimise fitness

(function) of solution.

How:
1. Population of solutions created
2. Fitness of each solution evaluated
3. Best solutions mated for new
population
4. Repeated until optimum solution.

Where: Design optimisation

Stock market investment
Autonomous programme development
 Learning:
Genetic Evolutionary Computation

Genetic Algorithms:
Optimise numeric solution of fitness
function.
Learning Classifier Systems:
Optimise the co-operation of rules for
solving and input/output thickness
function.
Genetic Programming:
Optimise the interaction of code to
solve a programming function.
Evolutionary Systems:
Optimise the solution based on a
behavioural (phenotypic) instead of
genetic (genotypic) level.
 F(x) = cos(x) + sin(x2) : 1 < x< 3
2

1.5

0.5

0
1 1.5 2 2.5 3
-0.5

-1

-1.5

-2

GA: j1 = 00010001
j2 = 01110001
j3 = 10010101

GP: j1 = sin(x) + 2sin(x2)

j2 = sin(x) + 2sin(x)cos(x)
j3 = sin(x) - 2sin(x)cos(x)
 Intelligent-Agents:
Cellular Automata
What: Autonomous individuals (cells)
reacting to state of neighbouring
individuals - governed by rules.

How: Grid of individuals initiated

Behaviour rules introduced
(e.g., if > 3 neighbours on, then on)
Iteration until stable pattern emerges.

Where: Cast and mould design

Screensavers!
 Neural Networks:
Back-Propagation
What: Mimic the function of the human
brain within a computer.
How: Nodes (representing neurons) are
linked to other nodes via connections
(representing synapses)
Nodes send messages to their output
(firing) when a threshold from their inputs
has been reached.
Where: Modelling of industrial systems
Speech recognition programs.
NODE

CONNECTION

INPUTS OUTPUTS

INPUT HIDDEN OUTPUT

LAYER LAYER LAYER
 Neural Networks:
Self-Organising-Maps
What: Mimic the function of the human
brain within a computer. To determine
input relations (instead of input-output
relationships).

How: Nodes are linked to other nodes via

connections
Network of nodes autonomously adjusts to
represent input patterns.

Where: Fault diagnosis of industrial systems

Growing patterns in crops
 Technique Selection

Overall Strategy - Explore (search) or

Exploit (optimise)

Representation - Required
transparency

Learning - Domain / fitness

function known?

Supervision - Feedback from

domain available?
 No Free Lunch Theorem

“...all algorithms that search

for an extreme of a cost
function perform exactly the
same, according to any
performance measures,
when averaged over all
possible cost functions.”

[Wolpert and Macready 96]

 No Free Lunch Theorem

Reasons why theorem does not hold in

practical situations:

• Inclusion of domain knowledge

• Co-adaptation algorithms
• Domain specific algorithms
• Non-infinite populations
• Resampling is important
• Representation style is important in
specific domains

[Wilson 97]
 Interpolate & Extrapolate

• Aliasing
1.2

0.8
x x Learnt
0.6 Actual

0.4

0.2

0 x x
0 1 2 3
-0.2

• Incomplete picture
0
-0.2 0.7 1.2 1.7 2.2 2.7

-0.4
xx
-0.6 xx
-0.8
xx
-1 x
-1.2
-1.4
-1.6
-1.8
-2
 Garbage In = Garbage Out

• Often blind acceptance of inputs

• Often blind generation of outputs

• Practical need to:

Verify
Validate
Test
 Lack of Transparency

• “Black Box” techniques, such as

Neural Networks

• Semi-transparent techniques, such as

Branch & Bound, become difficult
for human interpretation with large
problems

• Transparent techniques, such as

Expert Systems, become difficult for
human interpretation with very large
problems - above 1000 rules, the
logic chain becomes huge.
 Benefits
• Not reliant upon the mathematical
description of the domain

• Speed, efficient solution production

• New/novel answers, effective solutions

produced

• Direct areas of further research (human or

conventional techniques)

• Hybridisation of techniques is possible

• Cost, wide range of options available

 Conclusion

• Useful tools to complement existing

techniques

• Multiple uses from exploring to

exploiting the domains of problems

• Beneficial in efficiently and

effectively obtaining solutions to
problems