Warum ist mein Farbverlauf falsch (Coursera, Logistische Regression, Julia)?

Question

Ich versuche Logistic Regression von Coursera in Julia zu tun, aber es funktioniert nicht.

Der Julia-Code die Steigung zu berechnen:

sigmoid(z) = 1/(1 + e^-z) 

hypotesis(theta, x) = sigmoid(scalar(theta' * x)) 

function gradient(theta, x, y) 
    (m, n) = size(x) 
    h = [hypotesis(theta, x[i,:]') for i in 1:m] 
    g = Array(Float64, n, 1) 
    for j in 1:n 
     g[j] = sum([(h[i] - y[i]) * x[i, j] for i in 1:m]) 
    end 
    g 
end 

Wenn dieser Gradient verwendet es die falschen Ergebnissen führt. Kann nicht herausfinden, warum, der Code scheint wie der richtige.

Die full Julia script. In diesem Skript wird der optimale Theta mithilfe meiner Gradient Descent-Implementierung und mithilfe des integrierten Optim-Pakets berechnet, und die Ergebnisse sind unterschiedlich.

Answer 1

habe ich versuchte gradient() in der OP-Kodex mit numerischer Ableitung von cost_j() Vergleich (welche die Zielfunktion der Minimierung ist) unter Verwendung der Routine folgenden

function grad_num(theta, x, y) 
    g = zeros(3) 

    eps = 1.0e-6 
    disp = zeros(3) 

    for k = 1:3 
     disp[:] = theta[:] 

     disp[ k ]= theta[ k ] + eps 
     plus = cost_j(disp, x, y) 
     disp[ k ]= theta[ k ] - eps 
     minus = cost_j(disp, x, y) 

     g[ k ] = (plus - minus)/(2.0 * eps) 
    end 
    return g 
end 

Aber die Gradientenwerte von den zwei Routinen erhielten keine scheinen zu stimmen sehr gut (zumindest für die Anfangsphase der Minimierung) ... Also habe ich abgeleitet manuell den Gradienten cost_j(theta, x, y), von dem es scheint, dass die Division durch m fehlt:

#/ OP's code 
# g[j] = sum([ (h[i] - y[i]) * x[i, j] for i in 1:m ]) 

#/ modified code 
    g[j] = sum([ (h[i] - y[i]) * x[i, j] for i in 1:m ])/m 

Da ich mir nicht sicher bin, ob der obige Code und der Ausdruck wirklich korrekt sind, können Sie sie selbst überprüfen ...?

Aber tatsächlich, unabhängig davon, ob ich die ursprünglichen oder korrigierten Gradienten verwende, konvergiert das Programm zum selben minimalen Wert (0,2034977016, fast der gleiche wie von Optim), weil sich die beiden Gradienten nur durch einen multiplikativen Faktor unterscheiden!Da die Konvergenz sehr langsam war, habe ich verändern auch die Schrittgrßenregister alpha adaptiv nach dem Vorschlag von Vincent (hier habe ich moderate Werte für die Beschleunigung/Abbremsung):

function gradient_descent(x, y, theta, alpha, n_iterations) 
    ... 
    c = cost_j(theta, x, y) 

    for i = 1:n_iterations 
     c_prev = c 
     c = cost_j(theta, x, y) 

     if c - c_prev < 0.0 
      alpha *= 1.01 
     else 
      alpha /= 1.05 
     end 
     theta[:] = theta - alpha * gradient(theta, x, y) 
    end 
    ... 
end 

und diese Routine als

optimal_theta = gradient_descent(x, y, [0 0 0]', 1.5e-3, 10^7)[ 1 ] 

genannt

Die Variation von cost_j gegen Iterationsschritte ist unten aufgetragen.

Answer 2

Der Farbverlauf ist korrekt (bis zu einem skalaren Vielfachen, wie @roygvib angibt). Das Problem ist mit dem Gradientenabstieg.

Wenn man sich die Werte der Kostenfunktion während Ihrer Gradientenabfallsaktualisierung betrachtet, werden Sie eine Menge NaN, sehen, die aus den exponentiellen wahrscheinlich kommen: die Schrittgröße senken (zB zu 1e-5) den Überlauf vermeiden , , aber Sie müssen die Anzahl der Iterationen sehr erhöhen (vielleicht auf 10_000_000).

Eine bessere (schnellere) Lösung wäre es, die Schrittweite variieren zu lassen. Zum Beispiel könnte man die Schrittgröße von 1.1 wenn die Kostenfunktion verbessert nach einem Schritt multiplizieren (das Optimum noch weit entfernt sieht in dieser Richtung: wir schneller gehen können), und teilen sie durch 2 wenn es nicht der Fall ist (wir sind zu schnell gefahren und sind über das Minimum hinaus).

Man könnte auch eine Liniensuche in Richtung des Gradienten durchführen, um die beste Schrittgröße zu finden (aber dies ist zeitaufwendig und kann durch Näherungen ersetzt werden, z. B. Armijos Regel).

Rescaling die prädiktiven Variablen hilft auch.