teorema - Algoritmo de aprendizaje de Perceptron que no converge a 0

red neuronal xor

Question

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

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

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 programa 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 programa 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).

Answer 2

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

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

^{(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 |----> output (+1/-1) y ---->| | w1 ----- ^ w2 1(bias) ---|

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

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

... 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:

Answer 3

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

Answer 4

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

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