1CMSC 421: Neural Computation• definition• synonyms neural networks artificial neural networks neural modeling connectionist models parallel distributed processing• AI perspectiveApplications of Neural Networks• pattern classification - virus/explosive detection, financial predictions, etc.• image processing - character recognition, manufacturing inspection, etc.• control - autonomous vehicles, industrial processes, etc.• optimization - VLSI layout, scheduling, etc.• bionics - prostheses, brain implants, etc.• brain/cognitive models - memory, learning, disorders, etc.2Nature-Inspired Computation natural system applicationsformalmodels,theories biology,physics, etc. computer science engineeringinterdisciplinary neural networks genetic programming swarm intelligence self-replicating machines ..Inspiration for neural networks?applicationspattern classificationspeech recognitionimage processingtext-to-speechexpert systemsautonomous vehiclesfinancial predictionsassociative memorydata visualization …+ brain modelingNeural Networksmodel/theoryrandom networksHebbian learningperceptronserror backpropagationself-organizing maps …nature3- complex- flow of information- what is known?The Brain(Purkinje cells; Golgi + Nissl stains) - neurons - synapsesNeuron Information Processing4How Does the Brain Compute?A familiar example …How fast is the processing? - cycle time vs. CPU… - signal speeds …How does it do that?! … - massively parallel processing 1011 neurons - different computational principlesSummary: Brain as Inspiration network of neurons 1011 neurons, 1014 synapses Relevance to AI: Can a machine think? Alan Turing and “weak AI” Prospects for “strong AI”? neuron flow ofinformation synapse spikes (pulses)5The Computer vs. The Brain• information access• control• processing method• how programmed• adaptabilitylocaldecentralizedmassively parallelself-organizingprominentlyglobalcentralizedsequentialprogrammedminimallyHistory of Neural Networks1945-1955: pre-computing1955-1970: classical period1970-1985: dark ages1985-1995: renaissance1995-today: modern eraperceptronserror back-propagationOur immediate focus: supervised/inductive learning6Neural Computation• basics• feedforward networks - perceptrons - error backpropagation• recurrent networksNeural Network Basics neural network = network + activation rule + learning rule7Neural Networks node/neuron activation level ai connection/synapse weight wij excitatory: wij > 0 inhibitory: wij < 01. network graph2. activation rule! ini= wijj"aj! ai= g(ini)• “executing” a neural network feedforward vs. recurrent networks...ai ! r w i ! r a wijajaiji+Choices for Activation FunctionLTU (step) logistic (sigmoid)! ai="(ini)local computations → emergent behaviorothers: sign, tanh, linear, radial basis, …! ai= step"(ini)θ83. Learning Rule weight changes as function of local activity! "wij= f (aj,ai,ini,wij,...)ji wijNeural Computation• basics• feedforward networks - perceptrons - error backpropagation• recurrent networks9Single Layer Networks• supervised learning: LMS Rule Perceptron Learning Rule• derived using gradient descent• associative memory, pattern classification inputs outputs o o o | o o o o | o number of layers?...Elementary Perceptronar ! r w rLTU = linear threshold unit ! r a θr! ar= step(inr) input layer outputr = response {0, 1}Example …ar =101 3.0 5.0-1.0inr =2.01θr = 1.010Perceptrons as Logic Gates1111-1Threshold needed to produce … AND ORNOTθr = 1.5θr = 0.5θr = -0.5 a1 a2 a2 a1 a1 a1 a2 a2Linear separability:Perceptron Learning Rule! wri= wri+"(tr# ar)aiEquivalent to the intuitive rules:If output is correct:If output is low (ar=0, tr=1):If output is high (ar=1, tr=0):Must also adjust threshold:(or, equivalently, assume there is a weight wr0 for an extra input unit that has a0=-1: bias node)If the target output for unit r is tr don’t change the weights increment weights for inputs = 1 decrement weights for inputs = 1! "r="r#$(tr# ar)η > 0 δr = tr - ar11Example of Perceptron Learning101 3.0 5.0-1.0θr = 1.0! wri= wri+"(tr# ar)aiSuppose η = 0.1 and tr = 0 …+! "r="r#$(tr# ar)Perceptron Learning Algorithm• repeatedly iterate through examples adjusting weightsusing perceptron learning rule until all outputs correct– initialize the weights randomly or to all zero– until outputs for all training examples are correct• for each training example do– compute the current output ar– compare it to the target tr and update weights• each pass through the training data is an epoch• when will the algorithm terminate?12Perceptron Properties• Perceptrons can only represent linear thresholdfunctions and can therefore only learn functions thatlinearly separate the data, i.e., the positive andnegative examples are separable by a hyperplane inn-dimensional space.• Unfortunately, some functions (like xor) cannot berepresented by a LTU.• Perceptron Convergence Theorem: If there are a setof weights that are consistent with the training data(i.e., the data is linearly separable), the perceptronlearning algorithm will converge on a solution.Error Backpropagation• widely used neural network learning method• seminal version about 1960 (Rosenblatt)• multiple versions since• basic contemporary version popularized ≈ 1985• uses multi-layer feedforward network13Uses Layered Feedforward Networkoutput unitshidden unitsinput unitsOHIRepresentation Power ofMulti-Layer NetworksTheorem: any boolean function of N inputs can be represented by a network with one layer of hidden units.XOR a1 a2 a3 a4 ar111-211θ3 = 1.5θ4 = 0.5θr = 0.5 ar = a4 ∧ ~ a3 = or(a1,a2) ∧ ~and(a1,a2)14Activation Function logistic (sigmoid)! ar="(inr)Error Backpropagation Learning activity errors! "wkj=#$kaj! "k= (tk# ak)ak(1# ak)! "j= wkj"kk#$ % & & ' ( ) ) aj(1 * aj)! "wji=#$jaiaiajak15Recall: Perceptron Learning Rule! wji= wji+"(tj# aj)aiδjRewritten:! "wji=#$jaiEBP Learning Rule! "wji=#$jai! "j= (tj# aj)aj(1# aj)! "j= wkj"kk#$ % & & ' ( ) ) aj(1 * aj)ji wji! "wji=#$jaijik’s wji! "k output hidden output hidden input16Error Backpropagation• repeatedly found to be effective in practice• however, not guaranteed to find solution• why?• most widely used neural network method hill climbing can get stuck in local minimaError