Coursera ML - Beeinflusst die Wahl des Optimierungsalgorithmus die Genauigkeit der logistischen Regression mehrerer Klassen?

7

Ich habe kürzlich Übung 3 von Andrew Ngs maschinellem Lernen auf Coursera mit Python abgeschlossen .

Als ich die Teile 1.4 bis 1.4.1 der Übung zum ersten Mal absolvierte, hatte ich Schwierigkeiten sicherzustellen, dass mein trainiertes Modell die Genauigkeit aufweist, die den erwarteten 94,9% entspricht. Selbst nachdem ich debuggt und sichergestellt hatte, dass meine Kosten- und Verlaufsfunktionen fehlerfrei waren und mein Prädiktorcode ordnungsgemäß funktionierte, erhielt ich immer noch eine Genauigkeit von nur 90,3%. Ich habe den Conjugate Gradient (CG) -Algorithmus in verwendet scipy.optimize.minimize.

Aus Neugier entschied ich mich für einen anderen Algorithmus und verwendete Broyden-Fletcher-Goldfarb-Shannon (BFGS). Zu meiner Überraschung verbesserte sich die Genauigkeit drastisch auf 96,5% und übertraf damit die Erwartungen. Der Vergleich dieser beiden unterschiedlichen Ergebnisse zwischen CG und BFGS kann in meinem Notizbuch unter der Überschrift Unterschied in der Genauigkeit aufgrund unterschiedlicher Optimierungsalgorithmen angezeigt werden .

Liegt der Grund für diesen Genauigkeitsunterschied in der unterschiedlichen Wahl des Optimierungsalgorithmus? Wenn ja, könnte jemand erklären, warum?

Außerdem würde ich mich über eine Überprüfung meines Codes sehr freuen, um sicherzustellen, dass in keiner meiner Funktionen ein Fehler vorliegt, der dies verursacht.

Vielen Dank.

BEARBEITEN: Hier unten habe ich den Code hinzugefügt, der in der Frage enthalten ist, auf Anfrage in den Kommentaren, die ich auf dieser Seite mache, anstatt die Leser auf die Links zu meinen Jupyter-Notizbüchern zu verweisen.

Modellkostenfunktionen:

def sigmoid(z):
    return 1 / (1 + np.exp(-z))

def compute_cost_regularized(theta, X, y, lda):
    reg =lda/(2*len(y)) * np.sum(theta[1:]**2) 
    return 1/len(y) * np.sum(-y @ np.log(sigmoid(X@theta)) 
                             - (1-y) @ np.log(1-sigmoid(X@theta))) + reg

def compute_gradient_regularized(theta, X, y, lda):
    gradient = np.zeros(len(theta))
    XT = X.T
    beta = sigmoid(X@theta) - y
    regterm = lda/len(y) * theta
    # theta_0 does not get regularized, so a 0 is substituted in its place
    regterm[0] = 0 
    gradient = (1/len(y) * XT@beta).T + regterm
    return gradient

Funktion, die ein Ein-gegen-Alles-Klassifizierungstraining implementiert:

from scipy.optimize import minimize

def train_one_vs_all(X, y, opt_method):
    theta_all = np.zeros((y.max()-y.min()+1, X.shape[1]))
    for k in range(y.min(),y.max()+1):
        grdtruth = np.where(y==k, 1,0)
        results = minimize(compute_cost_regularized, theta_all[k-1,:], 
                           args = (X,grdtruth,0.1),
                           method = opt_method, 
                           jac = compute_gradient_regularized)
        # optimized parameters are accessible through the x attribute
        theta_optimized = results.x
        # Assign thetheta_optimized vector to the appropriate row in the 
        # theta_all matrix
        theta_all[k-1,:] = theta_optimized
    return theta_all

Rief die Funktion auf, um das Modell mit verschiedenen Optimierungsmethoden zu trainieren:

theta_all_optimized_cg = train_one_vs_all(X_bias, y, 'CG')  # Optimization performed using Conjugate Gradient
theta_all_optimized_bfgs = train_one_vs_all(X_bias, y, 'BFGS') # optimization performed using Broyden–Fletcher–Goldfarb–Shanno

Wir sehen, dass sich die Vorhersageergebnisse je nach verwendetem Algorithmus unterscheiden:

def predict_one_vs_all(X, theta):
    return np.mean(np.argmax(sigmoid(X@theta.T), axis=1)+1 == y)*100

In[16]: predict_one_vs_all(X_bias, theta_all_optimized_cg)
Out[16]: 90.319999999999993

In[17]: predict_one_vs_all(X_bias, theta_all_optimized_bfgs)
Out[17]: 96.480000000000004

Jeder, der Daten zum Ausprobieren des Codes erhalten möchte, kann diese in meinem Github finden, wie in diesem Beitrag verlinkt.

AKKA
quelle
1
Logistische Regression sollte ein einziges stabiles Minimum haben (wie lineare Regression), daher ist es wahrscheinlich, dass etwas dies verursacht, das Sie nicht bemerkt haben
Neil Slater
Es muss also eine Konvergenz zu den Mindestkosten garantiert werden? Könnten Sie bitte eine Codeüberprüfung für mich durchführen?
AKKA
1
Wenn Sie viel Code überprüfen müssen, veröffentlichen Sie ihn möglicherweise auf codereview.stackexchange.com. Wenn nur eine geringe Menge erforderlich ist, um das Problem zu replizieren, können Sie ihn hier zu Ihrer Frage hinzufügen (bearbeiten Sie ihn als Codeblock. Bitte geben Sie genug an, um das Problem vollständig zu replizieren.
Neil Slater
Zwar sollte die Sicherstellung eines globalen Minimums unabhängig vom Optimierungsalgorithmus zu demselben Ergebnis führen, doch kann die Implementierung des Algorithmus (dh die Methoden zum Umgang mit numerischer Stabilität usw.) Feinheiten aufweisen, die zu geringfügig unterschiedlichen Lösungen führen können. Dieser kleine Unterschied in den Lösungen kann zu einem größeren Leistungsunterschied führen, wenn er mit einem kleinen Testsatz bewertet wird. Möglicherweise verursacht dies in Ihrem Fall einen so großen Leistungsunterschied. Und ja, im Allgemeinen können Optimierungsalgorithmen das Lernergebnis stark beeinflussen. Übrigens habe ich in MATLAB das gewünschte Ergebnis erzielt.
Sal
1
@NeilSlater: ok, ich habe den Code gerade als Bearbeitung direkt in die Frage eingefügt. Sieht es ok aus
AKKA

Antworten:

3

Grenzen der numerischen Genauigkeit und Stabilität führen zu Schwierigkeiten bei den Optimierungsroutinen.

Sie können dies am einfachsten erkennen, indem Sie den Regularisierungsterm auf 0.0 ändern. Es gibt keinen Grund, warum dies im Prinzip nicht funktionieren sollte, und Sie verwenden kein Feature-Engineering, das dies besonders benötigt. Wenn die Regularisierung auf 0,0 eingestellt ist, werden die Genauigkeitsgrenzen erreicht und es wird versucht, bei der Berechnung der Kostenfunktion ein Protokoll von 0 zu erstellen. Die beiden unterschiedlichen Optimierungsroutinen sind unterschiedlich betroffen, da unterschiedliche Stichprobenpunkte auf der Route auf ein Minimum reduziert werden.

Ich denke, dass Sie mit einem hoch eingestellten Regularisierungsterm die numerische Instabilität beseitigen, aber auf Kosten der Tatsache, dass Sie nicht sehen, was mit den Berechnungen wirklich los ist - tatsächlich werden die Regularisierungsterme für die schwierigen Trainingsbeispiele dominant.

Sie können einige Genauigkeitsprobleme ausgleichen, indem Sie die Kostenfunktion ändern:

def compute_cost_regularized(theta, X, y, lda):
    reg =lda/(2*len(y)) * np.sum(theta[1:]**2) 
    return reg - 1/len(y) * np.sum(
      y @ np.log( np.maximum(sigmoid(X@theta), 1e-10) ) 
      + (1-y) @ np.log( np.maximum(1-sigmoid(X@theta), 1e-10) ) )

Um während des Trainings Feedback zu erhalten, können Sie auch hinzufügen

                       options = {
                           'disp': True
                       }

Zum Anruf an minimize.

Mit dieser Änderung können Sie versuchen, den Regularisierungsterm auf Null zu setzen. Wenn ich das mache, bekomme ich:

predict_one_vs_all(X_bias, theta_all_optimized_cg)
Out[156]:
94.760000000000005
In [157]:

predict_one_vs_all(X_bias, theta_all_optimized_bfgs)
/usr/local/lib/python3.6/site-packages/ipykernel/__main__.py:2: RuntimeWarning: overflow encountered in exp
  from ipykernel import kernelapp as app
Out[157]:
98.839999999999989

Der CG-Wert von 94,76 scheint gut mit dem erwarteten Ergebnis übereinzustimmen - daher frage ich mich, ob dies ohne Regularisierung geschehen ist. Der BFGS-Wert ist immer noch "besser", obwohl ich nicht sicher bin, wie sehr ich ihm angesichts der Warnmeldungen während des Trainings und der Bewertung vertraue. Um festzustellen, ob dieses anscheinend bessere Trainingsergebnis tatsächlich zu einer besseren Ziffernerkennung führt, müssten Sie die Ergebnisse an einem Hold-Out-Test-Set messen.

Neil Slater
quelle
Schätzen Sie wirklich die Analyse, die Sie in Ihrer Antwort angegeben haben. Ich habe noch eine Frage zu der Änderung, die Sie an der Kostenfunktion vorgenommen haben, z. B. mit np.maximum(sigmoid(X@theta), 1e-10), woher wussten Sie, dass Sie sie 1e-10als Schwellenwert verwenden sollen? Außerdem ist mir aufgefallen, dass Sie das negative Vorzeichen von den einzelnen Begriffen der Summe verschoben und herausgebracht haben, sodass es jetzt reg - der Regularisierungsterm minus dem Summenterm ist. Ist das auch wichtig?
AKKA
Wie Sie vorgeschlagen haben, habe ich auch versucht, den Regularisierungsterm auf 0,0 zu setzen, und ich erhalte nicht nur den Fehler zum Teilen durch Null, sondern die Laufzeit wird auch viel länger! Über die Division durch Null Fehler verstehe ich allerdings nicht ganz warum. Wie kam es dazu? Hat dies etwas mit den Implementierungsdetails der Algorithmen zu tun? Verzeihen Sie mir, da ich mit numerischen Methoden nicht vertraut bin ...
AKKA
@AKKA: Ich habe nur willkürlich 1e-10 gewählt, und das Mischen von Begriffen war ein Nebeneffekt davon, dass ich den Code doppelt überprüft und verstanden habe. Ich denke auch nicht, dass es einen großen Unterschied macht. Technisch gesehen ist es keine Division durch Null, sondern eine, np.log( array_containing_a_zero )die aufgrund einer großen negativen oder positiven Summe in einem oder mehreren Beispielen während der Optimierungssuche aufgetreten ist.
Neil Slater
Da der Code potenziert dann Protokolle nimmt, die Zahlen , die Sie sehen können scheinen sich in Grenzen, aber die Zwischenberechnungen können extrem sein. Einige Frameworks können die Ausdrücke so auflösen, dass Exponentiation und Protokolle nicht tatsächlich auftreten - aber die Mathematik dafür ist mir ein Rätsel.
Neil Slater
Aha. Denken Sie dann, dass die besseren Ergebnisse, die Sie erzielt haben, überpassend gewesen sein könnten? Ich denke, deshalb haben Sie gesagt, dass letztendlich ein
AKKA
2

CG konvergiert nicht so gut wie BFGS

Wenn ich hier auch eine Antwort auf meine eigene Frage hinzufügen darf, werden Credits an einen guten Freund vergeben, der sich freiwillig bereit erklärt hat, meinen Code anzusehen. Er ist nicht bei Data Science Stackexchange und hatte nicht das Bedürfnis, ein Konto zu erstellen, nur um die Antwort zu veröffentlichen. Deshalb hat er diese Chance verpasst, an mich zu senden.

Ich würde auch auf @Neil Slater verweisen, da es eine Chance gibt, dass seine Analyse zum Thema der numerischen Stabilität dies erklären könnte.

Die Hauptprämisse hinter meiner Lösung lautet also:

Wir wissen, dass die Kostenfunktion konvex ist, dh sie hat keine Einheimischen und nur ein globales Minimum. Da die Vorhersage unter Verwendung von mit BFGS trainierten Parametern besser ist als die unter Verwendung von CG trainierten, impliziert dies, dass BFGS näher am Minimum konvergierte als CG. Ob BFGS zum globalen Minimum konvergierte oder nicht, können wir nicht sicher sagen, aber wir können definitiv sagen, dass es näher ist als CG.

Wenn wir also die mit CG trainierten Parameter nehmen und sie mit BFGS durch die Optimierungsroutine führen, sollten wir sehen, dass diese Parameter weiter optimiert werden, da BFGS alles näher an das Minimum bringt. Dies sollte die Vorhersagegenauigkeit verbessern und sie näher an die bringen, die mit einfachem BFGS-Training erhalten wurde.

Hier unten ist Code, der dies überprüft. Variablennamen folgen dem gleichen wie in der Frage:

# Copy the old array over, else only a reference is copied, and the 
# original vector gets modified
theta_all_optimized_bfgs_from_cg = np.copy(theta_all_optimized_cg)

for k in range(y.min(),y.max()+1):
    grdtruth = np.where(y==k, 1,0)
    results = minimize(compute_cost_regularized,theta_all_optimized_bfgs_from_cg[k-1,:], 
                       args = (X_bias,grdtruth,0.1),
                       method = "BFGS", 
                       jac = compute_gradient_regularized, options={"disp":True})
    # optimized parameters are accessible through the x attribute
    theta_optimized = results.x
    # Assign thetheta_optimized vector to the appropriate row in the 
    # theta_all matrix
    theta_all_optimized_bfgs_from_cg[k-1,:] = theta_optimized

Während der Ausführung der Schleife erzeugte nur eine der Iterationen eine Nachricht, die eine Anzahl von Optimierungsroutineniterationen ungleich Null zeigte, was bedeutet, dass eine weitere Optimierung durchgeführt wurde:

Optimization terminated successfully.
         Current function value: 0.078457
         Iterations: 453
         Function evaluations: 455
         Gradient evaluations: 455

Und die Ergebnisse wurden verbessert:

In[19]:  predict_one_vs_all(X_bias, theta_all_optimized_bfgs_from_cg)
Out[19]:  96.439999999999998

Durch weiteres Training der Parameter, die ursprünglich von CG erhalten wurden, durch einen zusätzlichen BFGS-Lauf haben wir sie weiter optimiert, um eine Vorhersagegenauigkeit zu erhalten, 96.44%die sehr nahe an der liegt 96.48%, die durch direkte Verwendung von nur BFGS erhalten wurde!

Ich habe mein Notizbuch mit dieser Erklärung aktualisiert.

Dies wirft natürlich weitere Fragen auf, z. B. warum CG bei dieser Kostenfunktion nicht so gut funktioniert hat wie BFGS, aber ich denke, das sind Fragen, die für einen anderen Beitrag bestimmt sind.

AKKA
quelle
Ich denke, Sie sollten dies immer noch an einem Hold-Out-Test-Set testen, um auszuschließen, dass BFGS stattdessen beschädigt wird. Seit ich geantwortet habe, habe ich mich jedoch gefragt, ob das Hinzufügen von Regularisierung die Verlustfläche weniger einfach macht. . . Dies bedeutet, dass die BFGS-Ergebnisse in dieser Situation strikt besser sind, jedoch ohne Regularisierung dieses Datensatzes instabil werden.
Neil Slater
@NeilSlater: Richtig, ich stimme zu, dass die beste Validierung und Standardpraxis darin besteht, sie auf einem Testdatensatz auszuführen. Die Durchführung eines Test-Sets war jedoch nicht Teil der Coursera-Aufgabe, sodass uns keine derartigen Test-Sets zur Verfügung gestellt wurden. Ich muss einen Teil des ursprünglichen MNIST herausnehmen. Was Sie gesagt haben, erscheint plausibel, da sich der konjugierte Gradient ohne Regularisierung verbessert. Wenn die Verlustfläche jedoch wirklich einfacher wäre, warum sollte CG dann immer noch schlechter als BFGS und nicht gleich sein?
AKKA