Lineare Regression schlechte Gradientenabstiegsleistung

Question

Ich habe eine einfache lineare Regression (single variate für jetzt) ​​Beispiel in C++ implementiert, um mir zu helfen, die Konzepte zu verstehen. Ich bin mir ziemlich sicher, dass der Schlüsselalgorithmus stimmt, aber meine Leistung ist schrecklich.

Dies ist die Methode, die tatsächlich die Gradientenabfallsaktualisierung führt:

void LinearRegression::BatchGradientDescent(std::vector<std::pair<int,int>> & data,float& theta1,float& theta2) 
{ 

    float weight = (1.0f/static_cast<float>(data.size())); 
    float theta1Res = 0.0f; 
    float theta2Res = 0.0f; 

    for(auto p: data) 
    { 

     float cost = Hypothesis(p.first,theta1,theta2) - p.second; 
     theta1Res += cost; 
     theta2Res += cost*p.first; 
    } 

    theta1 = theta1 - (m_LearningRate*weight* theta1Res); 
    theta2 = theta2 - (m_LearningRate*weight* theta2Res); 
} 

Mit den anderen wichtigen Funktionen wie gegeben:

float LinearRegression::Hypothesis(float x,float theta1,float theta2) const 
{ 
    return theta1 + x*theta2; 
} 


float LinearRegression::CostFunction(std::vector<std::pair<int,int>> & data, 
            float theta1, 
            float theta2) const 
{ 
    float error = 0.0f; 
    for(auto p: data) 
    { 

     float prediction = (Hypothesis(p.first,theta1,theta2) - p.second) ; 
     error += prediction*prediction; 
    } 

    error *= 1.0f/(data.size()*2.0f); 
    return error; 
} 

void LinearRegression::Regress(std::vector<std::pair<int,int>> & data) 
{ 
    for(unsigned int itr = 0; itr < MAX_ITERATIONS; ++itr) 
    { 
     BatchGradientDescent(data,m_Theta1,m_Theta2); 
     //Some visualisation code 
    } 
} 

Nun das Problem ist, dass, wenn die Lernrate ist größer als etwa 0.000001 der Wert der Kostenfunktion nach Gradientabstieg ist höher als vor. Das heißt, der Algorithmus arbeitet rückwärts. Die Linie bildet sich ziemlich schnell in einer geraden Linie durch den Ursprung, aber dann braucht man nur Millionen von Iterationen, um tatsächlich eine einigermaßen gut passende Linie zu erreichen.

mit einer Lernrate von 0,01 nach sechs Iterationen der Ausgang ist: (wobei Unterschied ist costAfter-costBefore)

Cost before 102901.945312, cost after 517539430400.000000, difference 517539332096.000000 
Cost before 517539430400.000000, cost after 3131945127824588800.000000, difference 3131944578068774912.000000 
Cost before 3131945127824588800.000000, cost after 18953312418560698826620928.000000, difference 18953308959796185006080000.000000 
Cost before 18953312418560698826620928.000000, cost after 114697949347691988409089177681920.000000, difference 114697930004878874575022382383104.000000 
Cost before 114697949347691988409089177681920.000000, cost after inf, difference inf 
Cost before inf, cost after inf, difference nan 

In diesem Beispiel ist die thgr Null ist, die Lernrate auf 0,000001 gesetzt, und es gibt 8.000.000 Iterationen! Der Visualisierungscode aktualisiert das Diagramm nur nach jeweils 100.000 Iterationen.

Funktion, die die Datenpunkte erstellt:

static void SetupRegressionData(std::vector<std::pair<int,int>> & data) 
{ 
    srand (time(NULL)); 

    for(int x = 50; x < 750; x += 3) 
    { 
     data.push_back(std::pair<int,int>(x+(rand() % 100), 400 + (rand() % 100))); 
    } 
} 

Kurz gesagt, wenn meine Lernrate zu hoch ist der Gradientenabstiegsalgorithmus effektiv rückwärts läuft und gegen Unendlich und wenn es abgesenkt der Punkt, an dem es tatsächlich gegen ein Minimum konvergiert, ist die Anzahl der Iterationen, die erforderlich sind, um dies tatsächlich zu tun, inakzeptabel hoch.

Habe ich etwas verpasst/einen Fehler im Kernalgorithmus gemacht?

Answer 1

Sieht aus, als ob sich alles wie erwartet verhält, aber Sie haben Probleme bei der Auswahl einer angemessenen Lernrate. Das ist kein völlig triviales Problem, und es gibt viele Ansätze, die von vordefinierten Zeitplänen reichen, die die Lernrate progressiv reduzieren (siehe z. B. this paper), zu adaptiven Verfahren wie AdaGrad oder AdaDelta.

Für Ihre Vanilla-Implementierung mit fester Lernrate sollten Sie Ihr Leben erleichtern, indem Sie die Daten auf Null und Standardabweichungen normieren, bevor Sie sie in den Gradienten-Abstiegsalgorithmus einspeisen. Auf diese Weise können Sie leichter über die Lernrate nachdenken. Dann kannst du deine Vorhersage einfach neu skalieren.