Algoritmo di apprendimento Perceptron non convergente a 0

Ecco la mia implementazione perceptron in ANSI C:

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

Il set di allenamento che sto utilizzando: Data Set

Ho rimosso tutto il codice irrilevante. Fondamentalmente quello che fa ora legge il file test1.txt e carica i valori da esso a tre matrici: x , y , outputs .

Poi c’è un algoritmo di apprendimento perceptron che, per qualche ragione, non converge a 0 ( globalError dovrebbe convergere a 0) e quindi ottengo un ciclo infinito do while.

Quando uso un set di allenamento più piccolo (come 5 punti), funziona piuttosto bene. Qualche idea dove potrebbe essere il problema?

Ho scritto questo algoritmo molto simile a questo algoritmo C # Perceptron :


MODIFICARE:

Ecco un esempio con un set di allenamento più piccolo:

 #include  #include  #include  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("XY 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; } 

Nel tuo codice corrente, il perceptron apprende con successo la direzione del confine della decisione, ma non è in grado di tradurlo .

     aa
     ^ ^
     |  - + \\ + |  - \\ + +
     |  - + \\ + + |  - \\ + + +
     |  - - \\ + |  - - \\ +
     |  - - + \\ + |  - - \\ + +
     ---------------------> x --------------------> x
         bloccato come questo bisogno di ottenere come questo

(come qualcuno ha sottolineato, ecco una versione più accurata )

Il problema sta nel fatto che il tuo perceptron non ha alcun termine di bias , cioè una terza componente di peso collegata ad un input di valore 1.

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

Il seguente è come ho corretto il problema:

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

... con il seguente risultato:

 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 

Ed ecco una breve animazione del codice sopra usando MATLAB, mostrando il confine della decisione ad ogni iterazione:

immagine dello schermo

Potrebbe essere d’aiuto se metti il ​​seeding del generatore casuale all’inizio di yout main invece di eseguire randomFloat il seeding su ogni chiamata a randomFloat , cioè

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

Alcuni piccoli errori che ho individuato nel codice sorgente:

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

Meglio cambiarlo

 int patternCount = i; 

quindi non devi fare affidamento sul tuo array x per avere le giuste dimensioni.

Si aumentano le iterazioni all’interno del ciclo p, mentre il codice C # originale lo fa al di fuori del ciclo p. Meglio spostare il printf e l’iterazione ++ fuori dal ciclo p prima dell’istruzione PAUSE – inoltre rimuoverò l’istruzione PAUSE o lo cambierò in

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

Anche facendo tutte queste modifiche, il tuo programma non termina ancora usando il tuo set di dati, ma l’output è più consistente, dando un errore oscillante tra 56 e 60.

L’ultima cosa che potresti provare è testare il programma C # originale su questo set di dati, se anche non termina, c’è qualcosa di sbagliato nell’algoritmo (perché il set di dati sembra corretto, vedi il mio commento di visualizzazione).

globalError non diventerà zero, convergerà a zero come hai detto, cioè diventerà molto piccolo.

Cambia il tuo loop come tale:

 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 

maxError valori maxIterations e maxError applicabili al tuo problema.