感知机学习算法无法收敛至0

Question

感知机学习算法无法收敛至0

calgorithmmachine-learningneural-networkperceptron

72

这是我在 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;
}

我使用的训练集是：数据集

我已经删除了所有无关代码。现在基本上它会读取test1.txt文件，并将其值加载到三个数组中：x，y和outputs。

然后有一个感知器学习算法，但由于某种原因，它没有收敛到0（globalError应该收敛到0），因此我得到了一个无限循环。

当我使用较小的训练集（如5个点）时，它表现得非常好。有任何想法，可能出了什么问题？

我编写的算法与这个C#感知器算法非常相似:

编辑：

以下是示例，其中包含较小的训练集：

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

- Richard Knop

1

小建议：在“无法打开文件”的情况下退出，或者至少初始化数组为某些值。 - schnaader

5

顺便提一下，数据集似乎是有效的 - 上传了一个快速而简单的POV-Ray可视化图：http://img175.imageshack.us/img175/7135/pointtest.png - schnaader

3

为什么你会认为误差会降至0？目前全局误差被计算为对数损失，应该被最小化但不是0。如果你的数据是通过设计可分离的，则0-1损失可能会降至0（尽管由于梯度下降的随机性，这也并不确定）。 - Jonathan Chang

@Jonathan：我数学不是很好，但如果两个点集是线性可分的话，它应该会收敛到0。我还查了维基百科上有关感知器的文章，我的算法似乎是正确的。我在下面加了一个小的训练集的例子，你可以看一下应该如何操作。 - Richard Knop

C/C++感知器：http://sourceforge.net/projects/ccperceptron/ - SomethingSomething

以下库可以帮助您：https://sourceforge.net/projects/c-c-neural-networks/ - SomethingSomething

4个回答

7

如果你把随机生成器的种子放在主函数的开头而不是在每次调用randomFloat时重新播种，可能会有所帮助。

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

- rsp

这是一个非常好的建议，尽管它并没有帮助（在此运行会导致超过100万次迭代而无法结束）。我认为这里算法仍然存在一些问题，或者假设它应该收敛于0存在问题。 - schnaader

3

我在您的源代码中发现了一些小错误：

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

更好的做法是将此处修改为

。

int patternCount = i;

所以您不必依赖于您的x数组具有正确的大小。

在p循环内增加迭代次数，而原始的C#代码在p循环外执行此操作。最好将printf和iteration++移至PAUSE语句之前的p循环外 - 我还会删除PAUSE语句或将其更改为

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

尽管你做了所有的改变，但你的程序仍然不能使用你的数据集终止，但输出更加一致，给出的错误在 56 到 60 之间波动。

你可以尝试在该数据集上测试原始的 C# 程序，如果它也不能终止，那么算法就有问题（因为你的数据集看起来是正确的，参考我的可视化评论）。

- schnaader

我在帖子末尾添加了一个使用较小训练集的示例。您可以尝试编译它以查看它应该如何工作。我不知道为什么它无法处理更大的训练集。 - Richard Knop

0

globalError 不会变成零，它会像你所说的那样收敛于零，也就是说它会变得非常小。

将您的循环更改为以下内容：

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

请提供适用于您的问题的maxIterations和maxError值。

- jilles de wit

1

感谢您的帮助，问题在于训练集是线性可分的，因此误差应该收敛到0并有可能变为0，do while循环应该结束。我的感知器算法实现中一定有些错误。 - Richard Knop

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Amro · Accepted Answer

在你当前的代码中，感知器成功地学习了决策边界的方向，但无法将其“转换”。

    y                              y
    ^                              ^
    |  - + \\  +                   |  - \\ +   +
    | -    +\\ +   +               | -   \\  + +   +
    | - -    \\ +                  | - -  \\    +
    | -  -  + \\  +                | -  -  \\ +   +
    ---------------------> x       --------------------> x
        像这样卡住            需要像这样

^{(正如有人指出的那样，这是一个更准确的版本)}

问题在于你的感知器没有偏置项，即没有连接到值为1的输入的第三个权重分量。

       w0   -----
    x ---->|     |
           |  f  |----> 输出 (+1/-1)
    y ---->|     |
       w1   -----
               ^ w2
    1(偏置) ---|

以下是我纠正问题的方法：

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

...并输出以下内容：

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

以下是用MATLAB编写的与上面代码相关的短动画，展示了每次迭代中的决策边界：