不收斂於0

Question

感知學習算法，這是我在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; 
} 

訓練集我使用的是：Data Set

我已刪除了所有無關的代碼。基本上它現在所做的是它讀取test1.txt文件並將其值從三個數組加載到三個數組：x,y,outputs。

然後有一個perceptron learning algorithm，由於某種原因，它不收斂到0（globalError應該收斂到0），因此我得到一個無限的while while循環。

當我使用較小的訓練集（如5分）時，它運行得非常好。任何想法可能是問題？

我寫這個算法非常相似，這C# Perceptron algorithm：

---

編輯：

這裏是一個較小的訓練集的例子：

#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

在您當前的代碼中，perceptron成功瞭解了決策邊界的方向但是無法通過翻譯它。

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

^{（有人指出的那樣，這裏是一個more accurate version）}

的問題在於，你的感知沒有偏項的，即連接到第三組份的事實輸入值爲1.

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

以下是我如何糾正問題：

#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代碼的動畫短片，展示了decision boundary在每次迭代：

Answer 2

可能有幫助，如果你把隨機發生器的播種放在你的main的開頭，而不是每次調用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]; 

Answer 3

一些小錯誤，我在源代碼中發現：

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

更好地改變了這

int patternCount = i; 

，所以你不必依靠你的X陣列擁有合適的尺寸。

您可以增加p循環內的迭代次數，而原始C＃代碼會在p循環外執行此操作。更好的移動printf和迭代++暫停語句之前在p循環外 - 還我刪除PAUSE語句或將其更改爲

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

即使做所有這些變化，你的程序仍不會終止使用數據集，但輸出更一致，給出的錯誤在56到60之間。

您可以嘗試的最後一件事是測試此數據集上的原始C＃程序，如果它也未終止，那麼算法出錯了（因爲你的數據集看起來正確，請參閱我的可視化評論）。

Answer 4

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