Perception using a Perceptron
Courtesy: [Link] /
Perceptron Node – Threshold Logic Unit
x1 w1
x2 w2 𝜃q z
xn wn
n
1 if åx w ³q
i =1
i i
z= n
0 if åx w <q
i =1
i i
Perceptron Node – Threshold Logic Unit
x1 w1
x2 w2 𝜃 z
xn wn
• Learn weights such that an objective 1 if åx w ³q
i =1
i i
function is maximized. z= n
• What objective function should we use?
• What learning algorithm should we use?
0 if åx w <q
i =1
i i
Perceptron Learning Algorithm
x1 .4
_+b=θ z
x2 -.2
n
x1 x2 t
1 if åx w ³qi i
.8 .3 1 z=
i =1
n
.4 .1 0 0 if åx w <q
i =1
i i
First Training Instance
.8 .4
b=0 z =1
.3 -.2 net = .8*.4 + .3*-.2 = .26
n
x1 x2 t
1 if åx w ³qi i
.8 .3 1 z=
i =1
n
.4 .1 0 0 if åx w <q
i =1
i i
Second Training Instance
.4 .4
b=0 z =1
.1 -.2 net = .4*.4 + .1*-.2 = .14
n
x1 x2 t
1 if åx w ³qi i
.8 .3 1 z=
i =1 wi = (t - z) c xi
n
.4 .1 0 0 if åx w <q
i =1
i i
Perceptron Rule Learning
wi = c(t – z) xi
⚫ Where wi is the weight from input i to the perceptron node, c is the
learning rate, t is the target for the current instance, z is the current output,
and xi is ith input
⚫ Least perturbation principle
– Only change weights if there is an error
– small c rather than changing weights sufficient to make current pattern correct
– Scale by xi
⚫ Create a perceptron node with n inputs
⚫ Iteratively apply a pattern from the training set and apply the perceptron
rule
⚫ Each iteration through the training set is an epoch
⚫ Continue training until total training set error ceases to improve
⚫ Perceptron Convergence Theorem: Guaranteed to find a solution in finite
time if a solution exists
Training Sets and Noise
⚫ Assume a Probability of Error at each input and output
value each time a pattern is trained on
⚫ 0 0 1 0 1 1 0 0 1 1 0 -> 0 1 1 0
⚫ i.e. P(error) = .05
⚫ Or a probability that the algorithm is applied wrong
(opposite) occasionally
⚫ Averages out over learning
Linear Separability
Linear Separability and Generalization
When is data noise vs. a legitimate exception
Limited Functionality of Hyperplane
How to Handle Multi-Class Output
⚫ This is an issue with learning models which only support binary
classification (perceptron, SVM, etc.)
⚫ Create 1 perceptron for each output class, where the training set
considers all other classes to be negative examples (one vs the
rest)
– Run all perceptrons on novel data and set the output to the class of the
perceptron which outputs high
– If there is a tie, choose the perceptron with the highest net value
⚫ Another approach: Create 1 perceptron for each pair of output
classes, where the training set only contains examples from the
2 classes (one vs one)
– Run all perceptrons on novel data and set the output to be the class
with the most wins (votes) from the perceptrons
– In case of a tie, use the net values to decide
– Number of models grows by the square of the output classes
Perceptron Learning Algorithm
⚫ First neural network learning model in the 1960’s
– Frank Rosenblatt
⚫ Simple and limited (single layer model)
⚫ Basic concepts are similar for multi-layer and deep models
so this is a good learning tool
⚫ Still used in some current applications (large business
problems, where intelligibility is needed, etc.)
UC Irvine Machine Learning Data Base
Iris Data Set
4.8,3.0,1.4,0.3, Iris-setosa
5.1,3.8,1.6,0.2, Iris-setosa
4.6,3.2,1.4,0.2, Iris-setosa
5.3,3.7,1.5,0.2, Iris-setosa
5.0,3.3,1.4,0.2, Iris-setosa
7.0,3.2,4.7,1.4, Iris-versicolor
6.4,3.2,4.5,1.5, Iris-versicolor
6.9,3.1,4.9,1.5, Iris-versicolor
5.5,2.3,4.0,1.3, Iris-versicolor
6.5,2.8,4.6,1.5, Iris-versicolor
6.0,2.2,5.0,1.5, Iris-viginica
6.9,3.2,5.7,2.3, Iris-viginica
5.6,2.8,4.9,2.0, Iris-viginica
7.7,2.8,6.7,2.0, Iris-viginica
6.3,2.7,4.9,1.8, Iris-viginica
Objective Functions: Accuracy/Error
⚫ How do we judge the quality of a particular model (e.g.
Perceptron with a particular setting of weights)
⚫ Consider how accurate the model is on the data set
– Classification accuracy = # Correct/Total instances
– Classification error = # Misclassified/Total instances (= 1 – acc)
⚫ Usually minimize a Loss function (aka cost, error)
⚫ For real valued outputs and/or targets
– Pattern error = Target – output: Errors could cancel each other
⚫ |tj – zj| (L1 loss) where j indexes all outputs in the pattern
⚫ Common approach is Squared Error = (tj – zj)2 (L2 loss)
– Sum squared error (SSE) = pattern squared errors = (tij – zij)2
where i indexes all the patterns in training set
⚫ For nominal data, pattern error is typically 1 for a mismatch and
0 for a match
– For nominal (including binary) output and targets, L1, L2, and
classification error are equivalent
Mean Squared Error
⚫ Mean Squared Error (MSE) – SSE/n where n is the number of
instances in the data set
– This can be nice because it normalizes the error for data sets of
different sizes
– MSE is the average squared error per pattern
⚫ Root Mean Squared Error (RMSE) – is the square root of the
MSE
– This puts the error value back into the same units as the features and
can thus be more intuitive
⚫ Since we squared the error on the SSE
– RMSE is the average distance (error) of targets from the outputs in the
same scale as the features
– Note RMSE is the root of the total data set MSE, and NOT the sum of
the root of each individual pattern MSE
Gradient Descent Learning: Minimize
(Maximize) the Objective Function
Error Landscape
Total SSE:
Sum
Squared
Error
(t – z)2
0
Weight Values
Deriving a Gradient Descent Learning
Algorithm
⚫ Goal is to decrease overall error (or other loss function)
each time a weight is changed
⚫ Total Sum Squared error one possible loss function
E: (t – z)2
¶E
⚫ Seek a weight changing algorithm such that is
¶wij
negative
⚫ If a formula can be found then we have a gradient descent
learning algorithm
⚫ Delta rule is a variant of the perceptron rule which gives a
gradient descent learning algorithm with perceptron nodes
Delta rule algorithm
⚫ Delta rule uses (target - net) before the net value goes through the
threshold in the learning rule to decide weight update
Dwi = c(t - net)xi
⚫ Weights are updated even when the output would be correct
⚫ Because this model is single layer and because of the SSE objective
function, the error surface is guaranteed to be parabolic with only one
minima
⚫ Learning rate
– If learning rate is too large can jump around global minimum
– If too small, will get to minimum, but will take a longer time
– Can decrease learning rate over time to give higher speed and still
attain the global minimum (although exact minimum is still just for
training set and thus…)
Batch vs Stochastic Update
⚫ To get the true gradient with the delta rule, we need to sum
errors over the entire training set and only update weights
at the end of each epoch
⚫ Batch (gradient) vs stochastic (on-line, incremental)
– SGD (Stochastic Gradient Descent)
– With the stochastic delta rule algorithm, you update after every pattern,
just like with the perceptron algorithm (even though that means each
change may not be along the true gradient)
– Stochastic is more efficient and best to use in almost all cases, though not
all have figured it out yet
– We’ll talk about this in more detail when we get to Backpropagation
Quadric Machine
⚫ All quadratic surfaces (2nd order)
– ellipsoid
– parabola
– etc.
⚫ That significantly increases the number of problems that
can be solved
⚫ Can we solve XOR with this model?
Quadric Machine
⚫ All quadratic surfaces (2nd order)
– ellipsoid
– parabola
– etc.
⚫ That significantly increases the number of problems that
can be solved
⚫ But still many problem which are not quadrically separable
⚫ Could go to 3rd and higher order features (cubic), but
number of possible features grows exponentially
⚫ Multi-layer neural networks will allow us to discover high-
order features automatically from the input space
Simple Quadric Example
-3 -2 -1 0 1 2 3
f1
⚫ What is the decision surface for a 1-d (1 input) problem?
⚫ Perceptron with just feature f1 cannot separate the data
⚫ Could we add a transformed feature to our perceptron?
Simple Quadric Example
-3 -2 -1 0 1 2 3
f1
⚫ Perceptron with just feature f1 cannot separate the data
⚫ Could we add a transformed feature to our perceptron?
⚫ f2 = f12
Simple Quadric Example
f2
-3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3
f1 f1
⚫ Perceptron with just feature f1 cannot separate the data
⚫ Could we add another feature to our perceptron f2 = f12
⚫ Note could also think of this as just using feature f1 but now
allowing a quadric surface to divide the data
– Note that f1 not actually needed in this case
⚫ Reference: [Link]