algorithme d'apprentissage Perceptron ne convergent pas vers 0

Question

Voici mon implémentation perceptron en ANSI C:

#include <stdio.h> 
#include <stdlib.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, Y coordinates of the training set. 
    float x[208], y[208]; 

    // Training set outputs. 
    int outputs[208]; 

    int i = 0; // iterator 

    FILE *fp; 

    if ((fp = fopen("test1.txt", "r")) == NULL) 
    { 
     printf("Cannot open file.\n"); 
    } 
    else 
    { 
     while (fscanf(fp, "%f %f %d", &x[i], &y[i], &outputs[i]) != EOF) 
     { 
      if (outputs[i] == 0) 
      { 
       outputs[i] = -1; 
      } 
      printf("%f %f %d\n", x[i], y[i], outputs[i]); 
      i++; 
     } 
    } 

    system("PAUSE"); 

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

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

    float learningRate = 0.1; 

    int iteration = 0; 
    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 %.2f %.2f\n", iteration, globalError, localError); 

      iteration++; 
     } 

     system("PAUSE"); 

    } while (globalError != 0); 

    system("PAUSE"); 
    return 0; 
} 

L'ensemble de la formation J'utilise: Data Set

J'ai supprimé tout le code hors de propos. Fondamentalement, ce qu'il fait maintenant lit le fichier test1.txt et charge les valeurs à trois tableaux: x, y, outputs.

Ensuite, il y a un perceptron learning algorithm qui, pour une raison quelconque, ne converge pas vers 0 (globalError devrait converger vers 0) et donc j'obtiens une boucle while while infinie. Lorsque j'utilise un ensemble d'entraînement plus petit (comme 5 points), cela fonctionne plutôt bien. Des idées où pourrait être le problème?

j'ai écrit cet algorithme très similaire à ce C# Perceptron algorithm:

---

EDIT:

Voici un exemple avec un ensemble de formation plus petite:

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

float randomFloat() 
{ 
    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[]) 
{ 
    srand(time(NULL)); 

    // 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 i = 0; // iterator 

    FILE *fp; 

    system("PAUSE"); 

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

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

    float learningRate = 0.1; 

    int iteration = 0; 
    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 %.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("%.2f %.2f %s\n", j, k, (output == 1) ? "Blue" : "Red"); 
     } 
    } 

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

    system("PAUSE"); 
    return 0; 
} 

Answer 1

Dans votre code actuel, le perceptron apprend avec succès la direction de la limite de décision MAIS est incapable de traduire il.

 
    y        y 
    ^       ^
    | - + \\ +     | - \\ + + 
    | - +\\ + +    | - \\ + + + 
    | - - \\ +     | - - \\ + 
    | - - + \\ +    | - - \\ + + 
    ---------------------> x  --------------------> x 
     stuck like this   need to get like this 

^{(comme quelqu'un l'a souligné, voici une more accurate version)}

Le problème réside dans le fait que votre perceptron n'a pas de terme de polarisation , à savoir un troisième composant de poids connecté à un entrée de valeur 1.

 
     w0 ----- 
    x ---->|  | 
      | f |----> output (+1/-1) 
    y ---->|  | 
     w1 ----- 
      ^w2 
    1(bias) ---| 

Ci-dessous la façon dont je corrige le problème:

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

#define LEARNING_RATE 0.1 
#define MAX_ITERATION 100 

float randomFloat() 
{ 
    return (float)rand()/(float)RAND_MAX; 
} 

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

int main(int argc, char *argv[]) 
{ 
    srand(time(NULL)); 

    float x[208], y[208], weights[3], localError, globalError; 
    int outputs[208], patternCount, i, p, iteration, output; 

    FILE *fp; 
    if ((fp = fopen("test1.txt", "r")) == NULL) { 
     printf("Cannot open file.\n"); 
     exit(1); 
    } 

    i = 0; 
    while (fscanf(fp, "%f %f %d", &x[i], &y[i], &outputs[i]) != EOF) { 
     if (outputs[i] == 0) { 
      outputs[i] = -1; 
     } 
     i++; 
    } 
    patternCount = i; 

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

    iteration = 0; 
    do { 
     iteration++; 
     globalError = 0; 
     for (p = 0; p < patternCount; p++) { 
      output = calculateOutput(weights, x[p], y[p]); 

      localError = outputs[p] - output; 
      weights[0] += LEARNING_RATE * localError * x[p]; 
      weights[1] += LEARNING_RATE * localError * y[p]; 
      weights[2] += LEARNING_RATE * localError; 

      globalError += (localError*localError); 
     } 

     /* Root Mean Squared Error */ 
     printf("Iteration %d : RMSE = %.4f\n", 
      iteration, sqrt(globalError/patternCount)); 
    } while (globalError > 0 && iteration <= MAX_ITERATION); 

    printf("\nDecision boundary (line) equation: %.2f*x + %.2f*y + %.2f = 0\n", 
     weights[0], weights[1], weights[2]); 

    return 0; 
} 

... avec la sortie suivante:

Iteration 1 : RMSE = 0.7206 
Iteration 2 : RMSE = 0.5189 
Iteration 3 : RMSE = 0.4804 
Iteration 4 : RMSE = 0.4804 
Iteration 5 : RMSE = 0.3101 
Iteration 6 : RMSE = 0.4160 
Iteration 7 : RMSE = 0.4599 
Iteration 8 : RMSE = 0.3922 
Iteration 9 : RMSE = 0.0000 

Decision boundary (line) equation: -2.37*x + -2.51*y + -7.55 = 0 

Et voici une courte animation du code ci-dessus en utilisant Matlab, montrant la decision boundary à chaque itération:

Answer 2

Il pourrait aider si vous mettez l'ensemencement du générateur aléatoire au début de votre main au lieu de réappliquer à chaque appel au randomFloat, à savoir

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

// ... 

int main(int argc, char *argv[]) 
{ 
    srand(time(NULL)); 

    // X, Y coordinates of the training set. 
    float x[208], y[208]; 

Answer 3

Quelques petites erreurs que je repéré dans votre code source:

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

changement Mieux que cela

int patternCount = i; 

de sorte que vous ne faut pas compter sur votre tableau x avoir la bonne taille.

Vous augmentez les itérations à l'intérieur de la boucle p, alors que le code C# original le fait en dehors de la boucle p. Mieux déplacer le printf et l'itération ++ en dehors de la boucle de p avant l'instruction PAUSE - aussi je supprimer l'instruction PAUSE ou changer pour

if ((iteration % 25) == 0) system("PAUSE"); 

Même faire tous ces changements, votre programme ne fonctionne toujours se termine pas en utilisant votre ensemble de données, mais la sortie est plus cohérente, ce qui donne une erreur oscillant quelque part entre 56 et 60.

La dernière chose que vous pourriez essayer est de tester le programme d'origine C# sur cet ensemble de données, s'il ne se termine pas, il y a Quelque chose ne va pas avec l'algorithme (parce que votre jeu de données semble correct, voir mon commentaire de visualisation).

Answer 4

globalError ne deviendra pas zéro, il convergent vers zéro comme vous avez dit, à savoir qu'il deviendra très faible.

Changer votre boucle comme par exemple:

int maxIterations = 1000000; //stop after one million iterations regardless 
float maxError = 0.001; //one in thousand points in wrong class 

do { 
    //loop stuff here 

    //convert to fractional error 
    globalError = globalError/((float)patternCount); 

} while ((globalError > maxError) && (i<maxIterations)); 

Donnez maxIterations et maxError valeurs applicables à votre problème.