Perceptron
A perceptron is an algorithm used in machine-learning. It's the simplest of all neural networks, consisting of only one neuron, and is typically used for pattern recognition.
A perceptron attempts to separate input into a positive and a negative class with the aid of a linear function. The inputs are each multiplied by weights, random weights at first, and then summed. Based on the sign of the sum a decision is made.
In order for the perceptron to make the right decision, it needs to train with input for which the correct outcome is known, so that the weights can slowly be adjusted until they start producing the desired results.
- The task
The website The Nature of Code demonstrates a perceptron by making it perform a very simple task : determine if a randomly chosen point (x, y) is above or below a line y = mx + b. Implement this perceptron and display an image of the result.
- See also
Java
<lang java>import java.awt.*; import java.awt.event.ActionEvent; import java.util.*; import javax.swing.*; import javax.swing.Timer;
public class Perceptron extends JPanel {
class Trainer {
double[] inputs;
int answer;
Trainer(double x, double y, int a) {
inputs = new double[]{x, y, 1};
answer = a;
}
}
Trainer[] training = new Trainer[2000]; double[] weights; double c = 0.00001; int count;
public Perceptron(int n) {
Random r = new Random();
Dimension dim = new Dimension(640, 360);
setPreferredSize(dim);
setBackground(Color.white);
weights = new double[n];
for (int i = 0; i < weights.length; i++) {
weights[i] = r.nextDouble() * 2 - 1;
}
for (int i = 0; i < training.length; i++) {
double x = r.nextDouble() * dim.width;
double y = r.nextDouble() * dim.height;
int answer = y < f(x) ? -1 : 1;
training[i] = new Trainer(x, y, answer);
}
new Timer(30, (ActionEvent e) -> {
repaint();
}).start();
}
private double f(double x) {
return x * 0.7 + 40;
}
int feedForward(double[] inputs) {
assert inputs.length == weights.length : "weights and input length mismatch";
double sum = 0;
for (int i = 0; i < weights.length; i++) {
sum += inputs[i] * weights[i];
}
return activate(sum);
}
int activate(double s) {
return s > 0 ? 1 : -1;
}
void train(double[] inputs, int desired) {
int guess = feedForward(inputs);
double error = desired - guess;
for (int i = 0; i < weights.length; i++) {
weights[i] += c * error * inputs[i];
}
}
@Override
public void paintComponent(Graphics gg) {
super.paintComponent(gg);
Graphics2D g = (Graphics2D) gg;
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
// we're drawing upside down
int x = getWidth();
int y = (int) f(x);
g.setStroke(new BasicStroke(2));
g.setColor(Color.orange);
g.drawLine(0, 0, x, y);
train(training[count].inputs, training[count].answer);
count = (count + 1) % training.length;
g.setStroke(new BasicStroke(1));
g.setColor(Color.black);
for (int i = 0; i < count; i++) {
int guess = feedForward(training[i].inputs);
x = (int) training[i].inputs[0] - 4;
y = (int) training[i].inputs[1] - 4;
if (guess > 0)
g.drawOval(x, y, 8, 8);
else
g.fillOval(x, y, 8, 8);
}
}
public static void main(String[] args) {
SwingUtilities.invokeLater(() -> {
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setTitle("Perceptron");
f.setResizable(false);
f.add(new Perceptron(3), BorderLayout.CENTER);
f.pack();
f.setLocationRelativeTo(null);
f.setVisible(true);
});
}
}</lang>
Pascal
This is a text-based implementation, using a 20x20 grid (just like the original Mark 1 Perceptron had). The rate of improvement drops quite markedly as you increase the number of training runs. <lang pascal>program Perceptron;
(*
* implements a version of the algorithm set out at * http://natureofcode.com/book/chapter-10-neural-networks/ , * but without graphics *)
function targetOutput( a, b : integer ) : integer; (* the function the perceptron will be learning is f(x) = 2x + 1 *) begin
if a * 2 + 1 < b then
targetOutput := 1
else
targetOutput := -1
end;
procedure showTargetOutput; var x, y : integer; begin
for y := 10 downto -9 do
begin
for x := -9 to 10 do
if targetOutput( x, y ) = 1 then
write( '#' )
else
write( 'O' );
writeln( )
end;
writeln( )
end;
procedure randomWeights( var ws : array of real ); (* start with random weights -- NB pass by reference *) var i : integer; begin
randomize; (* seed random-number generator *)
for i := 0 to 2 do
ws[i] := random * 2 - 1
end;
function feedForward( ins : array of integer; ws : array of real ) : integer; (* the perceptron outputs 1 if the sum of its inputs multiplied by its input weights is positive, otherwise -1 *) var sum : real;
i : integer;
begin
sum := 0;
for i := 0 to 2 do
sum := sum + ins[i] * ws[i];
if sum > 0 then
feedForward := 1
else
feedForward := -1
end;
procedure showOutput( ws : array of real ); var inputs : array[0..2] of integer;
x, y : integer;
begin
inputs[2] := 1; (* bias *)
for y := 10 downto -9 do
begin
for x := -9 to 10 do
begin
inputs[0] := x;
inputs[1] := y;
if feedForward( inputs, ws ) = 1 then
write( '#' )
else
write( 'O' )
end;
writeln( )
end;
writeln( )
end;
procedure train( var ws : array of real; runs : integer ); (* pass the array of weights by reference so it can be modified *) var inputs : array[0..2] of integer;
error : real; x, y, i, j : integer;
begin
inputs[2] := 1; (* bias *)
for i := 1 to runs do
begin
for y := 10 downto -9 do
begin
for x := -9 to 10 do
begin
inputs[0] := x;
inputs[1] := y;
error := targetOutput( x, y ) - feedForward( inputs, ws );
for j := 0 to 2 do
ws[j] := ws[j] + error * inputs[j] * 0.01;
(* 0.01 is the learning constant *)
end;
end;
end;
end;
var weights : array[0..2] of real;
begin
writeln( 'Target output for the function f(x) = 2x + 1:' ); showTargetOutput; randomWeights( weights ); writeln( 'Output from untrained perceptron:' ); showOutput( weights ); train( weights, 1 ); writeln( 'Output from perceptron after 1 training run:' ); showOutput( weights ); train( weights, 4 ); writeln( 'Output from perceptron after 5 training runs:' ); showOutput( weights )
end.</lang>
- Output:
Target output for the function f(x) = 2x + 1: ##############OOOOOO #############OOOOOOO #############OOOOOOO ############OOOOOOOO ############OOOOOOOO ###########OOOOOOOOO ###########OOOOOOOOO ##########OOOOOOOOOO ##########OOOOOOOOOO #########OOOOOOOOOOO #########OOOOOOOOOOO ########OOOOOOOOOOOO ########OOOOOOOOOOOO #######OOOOOOOOOOOOO #######OOOOOOOOOOOOO ######OOOOOOOOOOOOOO ######OOOOOOOOOOOOOO #####OOOOOOOOOOOOOOO #####OOOOOOOOOOOOOOO ####OOOOOOOOOOOOOOOO Output from untrained perceptron: OOO################# OOOO################ OOOOO############### OOOOO############### OOOOOO############## OOOOOO############## OOOOOOO############# OOOOOOOO############ OOOOOOOO############ OOOOOOOOO########### OOOOOOOOO########### OOOOOOOOOO########## OOOOOOOOOOO######### OOOOOOOOOOO######### OOOOOOOOOOOO######## OOOOOOOOOOOOO####### OOOOOOOOOOOOO####### OOOOOOOOOOOOOO###### OOOOOOOOOOOOOO###### OOOOOOOOOOOOOOO##### Output from perceptron after 1 training run: ###############OOOOO ###############OOOOO ##############OOOOOO #############OOOOOOO #############OOOOOOO ############OOOOOOOO ############OOOOOOOO ###########OOOOOOOOO ##########OOOOOOOOOO ##########OOOOOOOOOO #########OOOOOOOOOOO #########OOOOOOOOOOO ########OOOOOOOOOOOO #######OOOOOOOOOOOOO #######OOOOOOOOOOOOO ######OOOOOOOOOOOOOO ######OOOOOOOOOOOOOO #####OOOOOOOOOOOOOOO ####OOOOOOOOOOOOOOOO ####OOOOOOOOOOOOOOOO Output from perceptron after 5 training runs: ##############OOOOOO #############OOOOOOO #############OOOOOOO ############OOOOOOOO ############OOOOOOOO ###########OOOOOOOOO ###########OOOOOOOOO ##########OOOOOOOOOO ##########OOOOOOOOOO #########OOOOOOOOOOO #########OOOOOOOOOOO ########OOOOOOOOOOOO ########OOOOOOOOOOOO #######OOOOOOOOOOOOO #######OOOOOOOOOOOOO ######OOOOOOOOOOOOOO ######OOOOOOOOOOOOOO #####OOOOOOOOOOOOOOO #####OOOOOOOOOOOOOOO ####OOOOOOOOOOOOOOOO
zkl
Uses the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl <lang zkl>class Perceptron{
const c=0.00001;
var [const] W=640, H=350;
fcn init(n){
r:=(0.0).random.fp(1); // r()-->[0..1)
var weights=n.pump(List(),'wrap(){ r()*2 - 1 }), // Float[n]
training=(2000).pump(List,'wrap(){ // (x,y,1,answer)[2000]
x,y,answer:=r()*W, r()*H, (if(y<f(x)) -1 or 1);
return(x,y,1,answer) });
}
fcn f(x){ 0.7*x + 40 } // a line
fcn feedForward(xy1a){
sum:=0.0;
foreach i in (weights.len()){ sum+=xy1a[i]*weights[i] }
(sum<0) and -1 or 1 // activate(sum)
}
fcn train(xy1a){
guess,error:=feedForward(xy1a), xy1a[-1] - guess;
foreach i in (weights.len()){ weights[i]+=c*error*xy1a[i] }
}
}</lang> <lang zkl>p:=Perceptron(3); p.training.apply2(p.train);
PPM:=Import("ppm.zkl").PPM; pixmap:=PPM(p.W+20,p.H+20,0xFF|FF|FF);
foreach xy1a in (p.training){
guess,x,y:=p.feedForward(xy1a), 8 + xy1a[0], 8 + xy1a[1]; color:=(if(guess>0) 0 else 0xFF|00|00); // black or red pixmap.circle(x,y,8,color);
} pixmap.writeJPGFile("perceptron.zkl.jpg");</lang>
- Output:
