Perceptron algorytm uczenia się nie zbiegają do 0

Question

Oto moja realizacja perceptron w 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; 
} 

Zestaw szkoleniowy Używam: Data Set

Usunąłem wszystkie istotne kod. Zasadniczo to, co robi teraz czyta plik test1.txt i ładuje z niego wartości do trzech tablic: x, y, outputs.

Następnie jest perceptron learning algorithm, który z jakiegoś powodu nie jest zbieżny z 0 (globalError powinien zbiegać się do 0) i dlatego otrzymuję nieskończoną pętlę while.

Kiedy używam mniejszego zestawu treningowego (np. 5 punktów), działa całkiem dobrze. Jakieś pomysły, gdzie może być problem?

pisałem tego algorytmu bardzo podobnego do tego C# Perceptron algorithm:

---

EDIT:

Oto przykład z mniejszego zestawu treningowego:

#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

W swoim bieżącym kodzie, perceptron skutecznie uczy się kierunku granicy decyzji, ale nie jest w stanie przetłumaczyć .

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

^{(jak ktoś zauważył, tutaj jest more accurate version)}

Problem polega na tym, że perceptron nie ma Odchylenie termin, czyli trzeciego składnika masy podłączone do wejście od wartości 1.

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

Poniżej jaki sposób skorygować problem:

#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; 
} 

... z następującym wyjścia:

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 

A oto krótka animacja powyższym kodzie MATLAB, pokazując decision boundary w każdej iteracji:

Answer 2

To może pomóc, jeśli umieszczasz wysianie losowego generatora na początku głównej magistrali zamiast reseeding przy każdym połączeniu do randomFloat, tj

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

kilka małych błędów dostrzegłem w kodzie źródłowym:

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

Lepiej zmienić na

int patternCount = i; 

więc nie muszą polegać na swojej tablicy x mieć odpowiedni rozmiar.

Powiększasz iteracje wewnątrz pętli p, podczas gdy oryginalny kod C# robi to poza pętlą p. Lepiej przesunąć printf i iteracji pętli zewnętrznej ++ p przed stwierdzeniem PAUSE - też bym usunąć oświadczenie wstrzymać lub zmienić go na

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

Nawet robi wszystkie te zmiany, program nadal nie rozwiązać za pomocą swojego zestaw danych, ale wynik jest bardziej spójny, dając błąd oscylujący gdzieś pomiędzy 56 a 60.

Ostatnią rzeczą, którą można wypróbować, jest sprawdzenie oryginalnego programu C# na tym zestawie danych, o ile też się nie kończy, coś nie tak z algorytmem (ponieważ twój zestaw danych wygląda poprawnie, zobacz mój komentarz do wizualizacji).

Answer 4

globalError nie wyniesie zero, to zbiegają się zera jak pan powiedział, to znaczy, że stanie się bardzo mały.

Zmień swoją pętlę takich jak:

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)); 

Daj maxIterations i maxError wartości odnoszą się do danego problemu.