Perzeptron-Lernalgorithmus konvergiert nicht gegen 0

Lesezeit: 8 Minuten

Benutzeravatar von Richard Knop
Richard Knopf

Hier ist meine Perceptron-Implementierung in 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;
}

Das Trainingsset, das ich verwende: Datensatz

Ich habe alle irrelevanten Codes entfernt. Im Grunde, was es jetzt tut, liest es test1.txt Datei und lädt Werte daraus in drei Arrays: x, y, outputs.

Dann gibt es eine Perzeptron-Lernalgorithmus was aus irgendeinem Grund nicht gegen 0 konvergiert (globalError sollte gegen 0 konvergieren) und daher bekomme ich eine unendliche Do-While-Schleife.

Wenn ich ein kleineres Trainingsset verwende (wie 5 Punkte), funktioniert es ziemlich gut. Irgendwelche Ideen wo das Problem liegen könnte?

Ich habe diesen Algorithmus sehr ähnlich geschrieben C# Perceptron-Algorithmus:


BEARBEITEN:

Hier ist ein Beispiel mit einem kleineren Trainingsset:

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

  • Kleiner Vorschlag: Beenden Sie nach “Datei kann nicht geöffnet werden” oder initialisieren Sie in diesem Fall zumindest Arrays mit etwas.

    – schnaader

    8. November 2009 um 17:41 Uhr

  • Übrigens, der Datensatz scheint gültig zu sein – hat eine schnelle POV-Ray-Visualisierung hochgeladen: img175.imageshack.us/img175/7135/pointtest.png

    – schnaader

    8. November 2009 um 18:10 Uhr

  • Warum würden Sie davon ausgehen, dass der Fehler auf 0 geht? Im Moment wird der globalError als Protokollverlust berechnet, der minimiert, aber nicht null sein sollte. Wenn Ihre Daten vom Design her trennbar sind, könnte der 0-1-Verlust 0 erreichen (obwohl dies aufgrund der Stochastik des Gradientenabfalls wiederum nicht sicher ist).

    – Jonathan Chang

    8. November 2009 um 19:12 Uhr

  • @Jonathan: Ich bin nicht wirklich gut in Mathe, aber es sollte gegen 0 konvergieren, wenn die beiden Punktsätze linear trennbar sind. Ich habe auch einen Wikipedia-Artikel über Perceptron überprüft und mein Algorithmus scheint korrekt zu sein. Ich habe unten ein Beispiel mit einem kleinen Trainingsset hinzugefügt, Sie können überprüfen, wie es funktionieren sollte.

    – Richard Knopp

    8. November 2009 um 19:42 Uhr

  • C/C++ Perzeptron: sourceforge.net/projects/ccperceptron

    – Etwas etwas

    16. Oktober 2014 um 3:00 Uhr

Benutzeravatar von Amro
Amro

In Ihrem aktuellen Code ist die Perzeptron lernt erfolgreich die Richtung der Entscheidungsgrenze, kann es ABER nicht Übersetzen es.

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

(wie jemand darauf hingewiesen hat, hier ist eine genauere Version)

Das Problem liegt darin, dass Ihr Perzeptron keine hat Bias-Begriffdh eine dritte Gewichtskomponente, die mit einem Eingang mit dem Wert 1 verbunden ist.

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

So habe ich das Problem behoben:

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

… mit folgender Ausgabe:

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

Und hier ist eine kurze Animation des obigen Codes mit MATLAB, die die zeigt Entscheidungsgrenze bei jeder Iteration:

Bildschirmfoto

  • Wie soll ich die Trennlinie ziehen? Wenn y = ax + c ist die Gleichung für die Trennlinie. Wie bekomme ich a und c Konstanten aus Gewichten des gelernten Perzeptrons?

    – Buksi

    22. Dezember 2012 um 21:12 Uhr

  • @Buksy: Die Gleichung der Linie lautet: w0*x + w1*y + w2 = 0 wo w_i sind die gelernten Gewichte (Gewichtskomponenten, die mit den x/y-Eingängen verbunden sind + die Vorspannung; siehe Diagramm am Anfang des Beitrags). Natürlich können Sie die Terme so umordnen, dass sie wie y=ax+b aussehen

    – Amro

    22. Dezember 2012 um 22:53 Uhr

  • Warum konvergiert es nicht, wenn die Aussage if (outputs[i] == 0) outputs[i] = -1; ist entfernt?

    – MathuSum Mut

    2. Juni 2017 um 17:45 Uhr


  • @MathuSumMut Die verwendete Aktivierungsfunktion calculateOutput gibt -1 oder +1 zurück, was ich vom ursprünglichen Code beibehalten habe. Das Klassenziel im Original Datensatz-Datei ist als 0/1 codiert, daher muss 0 durch -1 ersetzt werden.

    – Amro

    2. Juni 2017 um 17:55 Uhr

Es könnte hilfreich sein, wenn Sie das Seeding des Zufallsgenerators an den Anfang Ihres Mains stellen, anstatt bei jedem Aufruf neu zu Seeding randomFloatdh

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

  • Dies ist ein sehr guter Ratschlag, obwohl er nicht hilft (das Ausführen hier führt zu >= 1 Million Iterationen, ohne dass ein Ende in Sicht ist). Ich denke, es gibt hier immer noch ein Problem mit dem Algorithmus oder mit der Annahme, dass er gegen 0 konvergieren sollte.

    – schnaader

    8. November 2009 um 17:37 Uhr

Einige kleine Fehler, die ich in Ihrem Quellcode entdeckt habe:

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

Ändern Sie dies besser in

int patternCount = i;

Sie müssen sich also nicht darauf verlassen, dass Ihr x-Array die richtige Größe hat.

Sie erhöhen die Iterationen innerhalb der p-Schleife, während der ursprüngliche C#-Code dies außerhalb der p-Schleife tut. Verschieben Sie das printf und die Iteration ++ besser außerhalb der p-Schleife vor der PAUSE-Anweisung – außerdem würde ich die PAUSE-Anweisung entfernen oder ändern

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

Selbst wenn Sie all diese Änderungen vornehmen, wird Ihr Programm immer noch nicht mit Ihrem Datensatz beendet, aber die Ausgabe ist konsistenter und gibt einen Fehler aus, der irgendwo zwischen 56 und 60 oszilliert.

Das Letzte, was Sie versuchen könnten, ist, das ursprüngliche C#-Programm auf diesem Dataset zu testen. Wenn es auch nicht beendet wird, stimmt etwas mit dem Algorithmus nicht (weil Ihr Dataset korrekt aussieht, siehe meinen Visualisierungskommentar).

  • Ich habe ein Beispiel mit kleinerem Trainingssatz am Ende meines Beitrags hinzugefügt. Sie können versuchen, das zu kompilieren, um zu sehen, wie es funktionieren sollte. Ich habe keine Ahnung, warum es bei größeren Trainingssätzen fehlschlägt.

    – Richard Knopp

    8. November 2009 um 19:44 Uhr

globalError wird nicht Null, es wird konvergieren zu Null, wie Sie sagten, dh es wird sehr klein.

Ändern Sie Ihre Schleife wie folgt:

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

Geben maxIterations und maxError Werte, die für Ihr Problem gelten.

1416400cookie-checkPerzeptron-Lernalgorithmus konvergiert nicht gegen 0

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy