Nov 8 / Richard Knop

Perceptron in ANSI C

One of my school assignments was to write a simple ANSI C Perceptron algorithm that would be able to separate points on a two dimensional plane into two sets (-1 and 1). Fortunately, while reading a Wikipedia article about Perceptron, I have found a great external link at the bottom of it: C# implementation of a Perceptron. This helped me a lot to understand how the Perceptron works and how to implement it programatically.

What I have done is rewrite the code snippet from John Wakefield in the C language. Instead of data type double I used two integer arrays (one denotes x and the other one y coordinates of points from a training set). Plus I have added a simple code do draw a nice graph of the training set and its linear separation. I used GD to draw the image. I would also like to thank Amro for helping me finish this algorithm.

Perceptron linear separation

Here’s the entire code:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <gd.h>
  4. #include <math.h>
  5.  
  6. #define NUMEL            208
  7. #define LEARNING_RATE    0.1
  8. #define MAX_ITERATION    100
  9.  
  10. float randomFloat()
  11. {
  12.     float r = (float)rand() / (float)RAND_MAX;
  13.     return r;
  14. }
  15.  
  16. int calculateOutput(float weights[], float x, float y)
  17. {
  18.     float sum = x * weights[0] + y * weights[1] + weights[2];
  19.     return (sum >= 0) ? 1 : -1;
  20. }
  21.  
  22. int main(int argc, char *argv[])
  23. {
  24.     srand(time(NULL));
  25.  
  26.     float x[NUMEL], y[NUMEL], weights[3], localError, globalError, a, b;
  27.     int outputs[NUMEL], patternCount, i, p, iteration, output;
  28.  
  29.     FILE *fp;
  30.     if ((fp = fopen("training-set.txt", "r")) == NULL)
  31.     {
  32.         printf("Cannot open file.\n");
  33.         exit(1);
  34.     }
  35.     i = 0;
  36.     while (fscanf(fp, "%f %f %d", &x[i], &y[i], &outputs[i]) != EOF)
  37.     {
  38.         if (outputs[i] == 0)
  39.         {
  40.             outputs[i] = -1;
  41.         }
  42.         printf("%.4f %.4f %d\n", x[i], y[i], outputs[i]);
  43.         i++;
  44.     }
  45.     patternCount = i;
  46.  
  47.     system("PAUSE");
  48.  
  49.     weights[0] = randomFloat();
  50.     weights[1] = randomFloat();
  51.     weights[2] = randomFloat();
  52.  
  53.     iteration = 0;
  54.     do {
  55.  
  56.         iteration++;
  57.         globalError = 0;
  58.         for (p = 0; p < patternCount; p++)
  59.         {
  60.             output = calculateOutput(weights, x[p], y[p]);
  61.  
  62.             localError = outputs[p] - output;
  63.  
  64.             // Update weights.
  65.             weights[0] += LEARNING_RATE * localError * x[p];
  66.             weights[1] += LEARNING_RATE * localError * y[p];
  67.             weights[2] += LEARNING_RATE * localError;
  68.  
  69.             globalError += (localError * localError);
  70.         }
  71.  
  72.         /* Root Mean Squared Error */
  73.         printf("Iteration %d : RMSE = %.4f\n", iteration,
  74.                sqrt(globalError / patternCount));
  75.  
  76.     } while (globalError != 0 && iteration <= MAX_ITERATION);
  77.  
  78.     // Display network generalisation.
  79.     printf("X       Y     Output\n");
  80.     float j, k;
  81.     for (j = -1; j <= 1; j += .5)
  82.     {
  83.         for (j = -1; j <= 1; j += .5)
  84.         {
  85.             // Calculate output.
  86.             int output = calculateOutput(weights, j, k);
  87.             printf("%.4f %.4f %s\n", j, k, (output == 1) ? "Blue" : "Red");
  88.         }
  89.     }
  90.  
  91.     // Display modified weights.
  92.     printf("Modified weights: %.2f %.2f\n", weights[0], weights[1]);
  93.  
  94.     // Create image representation.
  95.     gdImagePtr im;
  96.     im = gdImageCreateTrueColor(600, 600);
  97.     if (im != 0)
  98.     {
  99.          // Allocate colors.
  100.          int white = gdImageColorAllocate(im, 255, 255, 255);
  101.          int lightGrey = gdImageColorAllocate(im, 220, 220, 220);
  102.          int black = gdImageColorAllocate(im, 0, 0, 0);
  103.          int blue = gdImageColorAllocate(im, 0, 0, 255);
  104.          int red = gdImageColorAllocate(im, 255, 0, 0);
  105.          int green = gdImageColorAllocate(im, 0, 200, 50);
  106.  
  107.          // White flood fill.
  108.          gdImageFill(im, 0, 0, lightGrey);
  109.  
  110.          // Points.
  111.          float cx, cy;
  112.          for (i = 0; i < patternCount; i++)
  113.          {
  114.              // Calculate output.
  115.              int output = calculateOutput(weights, x[i], y[i]);
  116.  
  117.              cx = floor(300 + 30*x[i] + 0.5);
  118.              cy = floor(300 - 30*y[i] + 0.5);
  119.  
  120.              int color = (output == 1) ? blue : red;
  121.  
  122.              gdImageFilledEllipse(im, (int)cx, (int)cy, 5, 5, color);
  123.          }
  124.  
  125.          // Linear separation
  126.          a = -weights[0] / weights[1];
  127.          b = -weights[2] / weights[1];
  128.          printf("Decision boundary (line) equation: y = %.4fx + %.4f\n", a, b);
  129.          // x = -10 => y = -10a+b
  130.          // x = 10 => y = 10*a + b
  131.  
  132.          gdImageLine(im, 0, (int)(300 + 300*a - 30*b), 600, (300 - 300*a - 30*b), green);
  133.  
  134.          // X coordinate.
  135.          gdImageLine(im, 0, 300, 600, 300, black);
  136.  
  137.          // Y coordinate.
  138.          gdImageLine(im, 300, 0, 300, 600, black);
  139.  
  140.          fp = fopen("training.png", "wb");
  141.          if (fp != 0)
  142.          {
  143.              gdImagePng(im, fp);
  144.              fclose(fp);
  145.          }
  146.     }
  147.     gdImageDestroy(im);
  148.  
  149.     system("PAUSE");
  150.     return 0;
  151. }

I used the Dev C++ to write the program. Here is how to use GD in Dev C++.

#include <stdio.h>
#include <stdlib.h>
#include <gd.h>
#include <math.h>

float randomFloat()
{
srand(time(NULL));
float r = (float)rand() / (float)RAND_MAX;
return r;
}

int calculateOutput(float weights[], float x, float y)
{
float sum = x * weights[0] + y * weights[1];
return (sum >= 0) ? 1 : -1;
}

int main(int argc, char *argv[])
{
// X coordinates of the training set.
float x[] = {
-3.2, 1.1, 2.7, -1
};

// Y coordinates of the training set.
float y[] = {
1.5, 3.3, 5.12, 2.1
};

// The training set outputs.
int outputs[] = {
1, -1, -1, 1
};

int patternCount = sizeof(x) / sizeof(int);

float weights[2];
weights[0] = randomFloat();
weights[1] = randomFloat();

float learningRate = 0.01;

int iteration = 0;
int i, p;
float globalError;

do {

globalError = 0;
int p = 0; // iterator
for (p = 0; p < patternCount; p++)
{
// Calculate output.
int output = calculateOutput(weights, x[p], y[p]);

// Calculate error.
float localError = outputs[p] – output;

if (localError != 0)
{
// Update weights.
for (i = 0; i < 2; i++)
{
float add = learningRate * localError;
if (i == 0)
{
add *= x[p];
}
else if (i == 1)
{
add *= y[p];
}
weights[i] += add;
}
}

// Convert error to absolute value.
globalError += fabs(localError);

printf(“Iteration %d Error %5.2f\n”, iteration, globalError);

iteration++;
}

} while (globalError != 0);

// Display network generalisation.
printf(“X Y Output\n”);
float j, k;
for (j = -1; j <= 1; j += .5)
{
for (j = -1; j <= 1; j += .5)
{
// Calculate output.
int output = calculateOutput(weights, j, k);
printf(“%5.2f %5.2f %s\n”, j, k, (output == 1) ? “Blue” : “Red”);
}
}

// Display modified weights.
printf(“Modified weights: %5.2f %5.2f\n”, weights[0], weights[1]);

// Create image representation.
gdImagePtr im;
FILE *fp;
im = gdImageCreateTrueColor(600, 600);
if (im != 0)
{
// So the points are further from each other
// and the graph is more readable.
int multiplier = 50;

// Allocate colors.
int white = gdImageColorAllocate(im, 255, 255, 255);
int lightGrey = gdImageColorAllocate(im, 220, 220, 220);
int black = gdImageColorAllocate(im, 0, 0, 0);
int blue = gdImageColorAllocate(im, 0, 0, 255);
int red = gdImageColorAllocate(im, 255, 0, 0);
int green = gdImageColorAllocate(im, 0, 200, 50);

// White flood fill.
gdImageFill(im, 0, 0, lightGrey);

// Points.
float cx, cy;
for (i = 0; i < patternCount; i++)
{
// Calculate output.
int output = calculateOutput(weights, x[i], y[i]);

cx = floor(300 + multiplier*x[i] + 0.5);
cy = floor(300 – multiplier*y[i] + 0.5);

int color = (output == 1) ? blue : red;

gdImageFilledEllipse(im, (int)cx, (int)cy, 10, 10, color);
}

// Linear separation.
float a = 0, b = 0;
for (i = 0; i < patternCount; i++)
{
int fx = (a > 0 && b > 0) ? 1 : 0;
a += learningRate * (y[i] – fx) * x[i];
b += learningRate * (y[i] – fx);
}
printf(“y = %5.2fx + %5.2f\n”, a, b);
// x = -300 => y = -300*a + b
// x = 300 => y = 300*a + b
gdImageLine(im, -2, (int)(300 + multiplier*300*a + b), 598, (int)(300 – multiplier*300*a + b), green);
gdImageLine(im, -1, (int)(300 + multiplier*300*a + b), 599, 300 – (int)(multiplier*300*a + b), green);
gdImageLine(im, 0, (int)(300 + multiplier*300*a + b), 600, 300 – (int)(multiplier*300*a + b), green);
gdImageLine(im, 1, (int)(300 + multiplier*300*a + b), 601, 300 – (int)(multiplier*300*a + b), green);
gdImageLine(im, 2, (int)(300 + multiplier*300*a + b), 602, 300 – (int)(multiplier*300*a + b), green);

// X coordinate.
gdImageLine(im, 0, 300, 600, 300, black);

// Y coordinate.
gdImageLine(im, 300, 0, 300, 600, black);

fp = fopen(“training.png”, “wb”);
if (fp != 0)
{
gdImagePng(im, fp);
fclose(fp);
}
}
gdImageDestroy(im);

system(“PAUSE”);
return 0;
}

Filed under Uncategorized
Leave a Comment