Transcript Lecture Slides

Conceptual Foundations
(MATH21001)
Lecture Week 12
Review and Applications
Reading:
Textbook, Chapters 1-14
Conceptual Foundations © 2008 Pearson Education Australia
Lecture slides for this course are based on teaching materials provided/referred by: (1) Statistics for Managers using Excel by Levine (2) Computer Algorithms:
Introduction to Design & Analysis by Baase and Gelder (slides by Ben Choi to accompany the Sara Baase’s text). (3) Discrete Mathematics by Richard
Johnsonbaugh
1
Learning Objectives
In this lecture, you will learn:
 To apply some basic concepts from weeks 1-11 in
computational intelligence based learning algorithms
 Matrices in implementing associate memories
 Gaussian distribution and matrices in RBF neural network
 Statistics in various learning algorithms
 Automata in real world applications such as speech
recognition, handwriting recognition, etc.
2
Artificial Intelligence (AI)/
Computational Intelligence (CI)
 The techniques that make computers learn and
behave like humans are called artificial/
computational intelligence based techniques.
 The term AI was first time used in 1956 by John
McCarthy. The term Computational Intelligence
(CI) was first time used in 1994 to mainly cover
areas such as neural networks, evolutionary
algorithms and fuzzy logic.
 In this lecture we will focus only on neural network
based algorithms because of time constrain.
3
Artificial Neuron – Mathematical Model
 Artificial neural network consists of many neurons.
An artificial neuron defined by McCulloch and Pitts in
1943 is as follows.
x1
net
w1
x2
.
.
w2
.
.
wn

f (net)
out
Activation function
xn
We may express this mathematically:
n
OUT = f (  wi xi )
i=1
where,
OUT is neuron’s output
f is the activation function
n is the number of inputs
xi is the i neuron’s input
wi is the weight of the i th neuron
4
Activation Functions
Activation Functions
a. Hard limiter
f(x)
+1
x
-1
+1
f(x) =
-1
x>0
x<=0
b. Sigmoidal
f(x)
+1
x
f(x)= 1/(1+exp(-x))
5
Implementation of Boolean
AND and OR
AND
x1 x2
1 1
1 0
0 1
0 0
y
1
0
0
0
OR
x1 x2
1 1
1 0
0 1
0 0
y
1
1
1
0
6
x1
w1
+1
w0=-1

AND
y
w2
x2
x1*w1 + x2*w2 + w0=y
w1=1;
w2=1;
x1
w1
+1
w0=-1

OR
y
w2
x2
w1=2;
w2=1;
7
Hebb: 1949
Learning/Training Algorithm
Step 1: Initialise weights
Initialise weights to small random values.
Step 2: Present input x1, .. ,xn
Step 3: Calculate actual output
n
y = f (  wi xi )
i=1
Step 4: Adjust weights
wij(t+1)= wij(t) +  * xi * yj
where  is between 0 and 1
Step 5: Repeat by going to Step 2
8
EXAMPLE:
Consider a 4-input single neuron to be trained with the input
vector x and an initial weight vector w as given below:
 1 
 2

x  
0



1.5 
 1 
 1 

w  
 0 .5 


0

  1
- 2 
)
output  f[w x]  f([ 1 - 1 0.5 0] 
0 


1.5
output=f(3)=+1
First iteration (update weight)
w(2)= w(1) + *output*x
For simplicity,  is set to 1.
 1 
 1 
  2
 1 
  2
 3 
  
  

w( 2)  
0.5
0

0.5 






0

1.5 
1.5 
Repeat the steps iteratively until the weights reach a
steady state (they do not change)
or #of iterations < maximum #of iterations
9
Application - matrices
Bi-directional Associative Memory (BAM)
 The BAM is a nearest neighbour, pattern matching
neural network that encodes binary or bipolar
pattern pairs. It thus associates patterns from a set
A to patterns from a set B, and vice versa.
A
B
10
BAM
Training
The weight matrix W is calculated as
m
W=
 A Bi
i 1
T
i
Recall
Bi=AiW where i is ith training pair
sum = where j is number of inputs
sum>0 values
>= +1 become +1
< +1 become -1
sum<0 values
> -1 become +1
<= -1 become -1
sum=0 values
>0
become +1
<=0 become -1
11
Example
Calculate the weights of 2x2 BAM
Pair 1:
Pair 2:
2
A1=(+1, +1, -1)
A2=(+1, -1, +1)
and B1=(-1, +1, -1, +1)
and B2=(+1, -1, +1, -1)
W=  AiT Bi = A1 B1 + A2 B2
T
T
i1
 1
1  1  1  1
A B1 =  1 1,1,1,1 = 1  1  1  1
1
 1  1  1  1
 1
 1  1  1  1
T
A2 B2 = 1 1,1,1,1 = 1  1  1  1
 1
 1  1  1  1
 0  0  0  0 
2
T
W=  Ai Bi =  2  2  2  2 
i1
2  2  2  2 
T
1
12
Example
Recall pattern:
A1=(+1,+1,-1)
 0  0  0  0 
B1=A1W=(+1,+1,-1)  2  2  2  2  =(-4,+4,-4,+4)
2  2  2  2 
4
sum=  Bi [ j ]=(-4+4-4+4)=0
j 1
sum=0
values
>0 become +1
<=0 become -1
Recall pattern: B1=(-1,+1,-1,+1)
13
Application of Gaussian
function
 The structure of radial basis function based
neural network (classifier) with n inputs and one
output is shown in the figure below:
x1
sum
x
s(x)
n
w
The network implements the mapping function:
m
s(x)   w j ( x  c j )
j 1
x, cj   n
14
Gaussian/radial basis function
 The general form of a Gaussian/radial basis function
is
(r )  e
(
r2

)
 where  is a parameter specifying the width of the
basis function, often called the smooth factor or the
receptive field. The shape of the function with three
different sizes of  is shown below:
15
Finite State Automata (FSA) and
different variants of Hidden Markov
Models (HMMs)
 Finite State Automata (FSA) and different
variants of Hidden Markov Models (HMMs),
have been used quite successfully to address
several complex pattern recognition
problems, such as speech recognition,
cursive handwritten text recognition, time
series prediction, biological sequence
analysis, etc.
16
Websites
 For "Introduction to Neural Networks" you may
refer to the following websites.
 http://www.doc.ic.ac.uk/~nd/surprise_96/jou
rnal/vol4/cs11/report.html
 http://www.neurosolutions.com/products/ns/
whatisNN.html
 http://www.cs.stir.ac.uk/~lss/NNIntro/InvSli
des.html
17
Exam Review
 Date And Time
 As advised by the university.
 Open Book (3 hours)
Conceptual Foundations, TERM 1, 2008 is an
open book examination.
18
You will see the following instructions on
your exam paper
 Instructions to the student
Answer all questions in the examination booklet
provided.
19
Things to do before the exam …
 A specimen exam paper is available on the course website.
You should do it before the exam and if you have a
problem, please see your local tutor.
 You should review the course material (week 1 to week 12),
including your assignments.
20
Some typical questions & topics…
 Some typical questions & topics are given below to help you in
exam preparation & you should study accordingly.
 You may be asked to state whether a statement is true or false.
 For example,
“Gaussian distribution is square shaped”
“A problem Q is NP-complete, if it has no solution”
 You may be given some distribution and asked to calculate
various thing such as standard deviation, variance, mean, etc.
 You may be asked to calculate regression coefficients based
on provided samples.
21
Some typical questions & topics…
 You may be asked to calculate sample size based on given parameters





such as Z, etc.
You may be asked to draw a transition diagram for the finite state
automaton.
Do you know various sorting algorithms? If not, try to learn how to
compare sorting algorithms. You may be asked to give an example.
Do you know various searching algorithms? You might be asked to
apply searching algorithm (e.g. binary search).
You may be asked to compare two algorithms. Do you know how to
calculate “number of comparisons”?
You may be asked to combine AND, OR, NAND, etc.
22
Some typical questions & topics…
 You may be asked to write a boolean expression to describe the
combinatorial circuit.
 You may be asked to write the logic table.
 Do you understand weighted graphs and various strategies such
as nearest neighbor?
 You may be given a weighted graph and asked to do the
following.
 What is the tour (a cycle through all the vertices) found by
the nearest neighbor algorithm?
 What is the total weight for the tour found by the nearest
neighbor algorithm?
 Did the algorithm find the optimum solution (minimum
tour)?
Good Luck
Course Coordinator of MATH21001
23
Summary
In this lecture, we have
 Introduced simple AI/CI algorithms
 Discussed applications
 Reviewed sample exam questions
24