Algoritmo de aprendizaje de Perceptron que no converge a 0

Aquí está mi implementación de perceptron en 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; } 

El conjunto de entrenamiento que estoy usando: conjunto de datos

He eliminado todo el código irrelevante. Básicamente lo que hace ahora lee el archivo test1.txt y carga valores de él a tres matrices: x , y , outputs .

Luego hay un algoritmo de aprendizaje de perceptrón que, por alguna razón, no está convergiendo a 0 ( globalError debe converger a 0) y, por lo tanto, obtengo un ciclo infinito do while.

Cuando uso un conjunto de entrenamiento más pequeño (como 5 puntos), funciona bastante bien. ¿Alguna idea de dónde podría ser el problema?

Escribí este algoritmo muy similar a este algoritmo C # Perceptron :


EDITAR:

Aquí hay un ejemplo con un conjunto de entrenamiento más pequeño:

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

    En su código actual, el perceptrón aprende con éxito la dirección del límite de decisión PERO no puede traducirlo .

         yy
         ^ ^
         |  - + \\ + |  - \\ + +
         |  - + \\ + + |  - \\ + + +
         |  - - \\ + |  - - \\ +
         |  - - + \\ + |  - - \\ + +
         ---------------------> x --------------------> x
             atrapado como este tiene que ser así
    

    (como alguien señaló, aquí hay una versión más precisa )

    El problema radica en el hecho de que su perceptrón no tiene un término de sesgo , es decir, un tercer componente de peso conectado a una entrada de valor 1.

            w0 -----
         x ----> |  |
                |  f | ----> salida (+ 1 / -1)
         y ----> |  |
            w1 -----
                    ^ w2
         1 (parcialidad) --- |
    

    La siguiente es la forma en que corregí el problema:

     #include  #include  #include  #include  

    ... con el siguiente resultado:

     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 

    Y aquí hay una breve animación del código anterior usando MATLAB, que muestra el límite de decisión en cada iteración:

    captura de pantalla

    Puede ser útil si coloca la siembra del generador aleatorio al inicio de la conexión principal en lugar de resembrar en cada llamada a randomFloat , es decir,

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

    Algunos pequeños errores que vi en tu código fuente:

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

    Mejor cambiar esto a

     int patternCount = i; 

    por lo que no tiene que confiar en que su matriz x tenga el tamaño correcto.

    Aumenta las iteraciones dentro del bucle p, mientras que el código C # original hace esto fuera del bucle p. Mejor mover el printf y la iteración ++ fuera del bucle p antes de la instrucción PAUSE; también eliminaría la instrucción PAUSE o la cambiaría a

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

    Incluso haciendo todos esos cambios, su progtwig aún no termina utilizando su conjunto de datos, pero la salida es más consistente, dando un error que oscila entre 56 y 60.

    Lo último que podría intentar es probar el progtwig C # original en este conjunto de datos, si tampoco termina, hay algo mal con el algoritmo (porque su conjunto de datos parece correcto, vea mi comentario de visualización).

    globalError no se convertirá en cero, convergerá a cero como dijiste, es decir, se volverá muy pequeño.

    Cambie su ciclo como tal:

     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 

    Proporcione los valores de maxIterations y maxError aplicables a su problema.