#### Transcript Slide 1

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) T T W= Ai Bi = A1 B1 + A2 B2 T i1 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 i1 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, 2009 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