MATLAB fminunc() wird für große Datasets nicht abgeschlossen. Funktioniert für kleinere

Question

Ich führe logistische Regression in MATLAB mit L2 Regularisierung auf Textdaten. Mein Programm funktioniert gut für kleine Datensätze. Bei größeren Sets läuft es unendlich weiter.

Ich habe die potenziell doppelte Frage (matlab fminunc not quitting (running indefinitely)) gesehen. In dieser Frage waren die Kosten für das anfängliche Theta NaN und es wurde ein Fehler in der Konsole ausgegeben. Für meine Implementierung bekomme ich einen echten Wert und es gibt keinen Fehler, selbst wenn ausführliche Parameter an fminunc() übergeben werden. Daher glaube ich, dass diese Frage kein Duplikat ist.

Ich brauche Hilfe bei der Skalierung zu größeren Sets. Die Größe der Trainingsdaten, an denen ich gerade arbeite, beträgt ungefähr 10k * 12k (10k Textdateien kumulativ mit 12k Wörtern). Also habe ich m = 10k Trainingsbeispiele und n = 12k Features.

Meine Kostenfunktion wird wie folgt definiert:

function [J gradient] = costFunction(X, y, lambda, theta) 

    [m n] = size(X); 
    g = inline('1.0 ./ (1.0 + exp(-z))'); 
    h = g(X*theta); 
    J =(1/m)*sum(-y.*log(h) - (1-y).*log(1-h))+ (lambda/(2*m))*norm(theta(2:end))^2; 

    gradient(1) = (1/m)*sum((h-y) .* X(:,1)); 

    for i = 2:n 
     gradient(i) = (1/m)*sum((h-y) .* X(:,i)) - (lambda/m)*theta(i); 
    end 
end 

Ich Durchführung Optimierung MATLAB fminunc() Funktion. Die Parameter I fminunc() übergeben sind:

options = optimset('LargeScale', 'on', 'GradObj', 'on', 'MaxIter', MAX_ITR); 
theta0 = zeros(n, 1); 

[optTheta, functionVal, exitFlag] = fminunc(@(t) costFunction(X, y, lambda, t), theta0, options); 

ich auf einer Maschine diesen Code leite mit diesen Spezifikationen:

Macbook Pro i7 2.8GHz/8GB RAM/MATLAB R2011b 

Die Kostenfunktion scheint richtig zu verhalten. Für das Anfangs-Theta bekomme ich akzeptable Werte von J und Gradient.

K>> theta0 = zeros(n, 1); 
K>> [j g] = costFunction(X, y, lambda, theta0); 
K>> j 

j = 

    0.6931 

K>> max(g) 

ans = 

    0.4082 

K>> min(g) 

ans = 

    -2.7021e-05 

Das Programm dauert unglaublich lange zu laufen. Ich begann Profiling zu halten MAX_ITR = 1 für fminunc(). Bei einer einzelnen Iteration wurde die Ausführung des Programms auch nach einigen Stunden nicht abgeschlossen. Meine Fragen sind:

1. Mache ich etwas mathematisch falsch?

2. Sollte ich anstelle von fminunc() einen anderen Optimierer verwenden? Wenn LargeScale = on ist, verwendet fminunc() Vertrauensbereichsalgorithmen.

3. Ist dieses Problem Cluster-Skala und sollte nicht auf einer einzigen Maschine ausgeführt werden?

Alle anderen allgemeinen Tipps werden geschätzt. Vielen Dank!

---

Dies trug dazu bei, das Problem zu lösen: ich in der Lage war (diese Funktion zu erhalten, indem die groß Flagge auf ‚off‘ in fminunc Einstellung). Soweit ich weiß, verwendet LargeScale = 'on' Trust-Region-Algorithmen, während 'Off' Quasi-Newton-Methoden verwendet. Quasi-Newton-Methoden zu verwenden und den Gradienten zu übergeben, hat bei diesem speziellen Problem viel schneller geklappt und sehr gute Ergebnisse gebracht.

---

Answer 1

Hier ist mein Rat:

-Set der Matlab-Flag Debug-Ausgabe während des Laufes zu zeigen. Wenn Sie nicht nur in Ihrer Kostenfunktion die Kosten drucken, können Sie Iterationszählung und -fehler überwachen.

Und zweitens, was sehr wichtig ist:

Ihr Problem ist illposed oder so unterbestimmt zu sagen. Sie haben einen 12k-Feature-Space und stellen nur 10k-Beispiele zur Verfügung, was für eine uneingeschränkte Optimierung bedeutet, dass die Antwort -Inf lautet. Um ein kurzes Beispiel zu geben, warum dies so ist, lautet Ihr Problem: Minimieren Sie x + y + z, vorausgesetzt, dass x + y-z = 2 ist. Merkmalsraum dim 3, überspannter Vektorraum - 1d. Ich schlage vor, PCA oder CCA zu verwenden, um die Dimensionalität der Textdateien zu reduzieren, indem ihre Variation bis zu 99% beibehalten wird. Dies wird Ihnen wahrscheinlich einen Feature-Space ~ 100-200dim geben.

PS: Nur um darauf hinzuweisen, dass das Problem sehr von Clustergröße Anforderung, die in der Regel 1kk + Datenpunkte ist und dass fminunc ist überhaupt kein Overkill, und LIBSVM hat nichts damit zu tun, weil fminunc nur ein ist quadratischer Optimierer, während LIBSVM ein Klassifikator ist. Zum Löschen verwendet LIBSVM etwas ähnliches wie fminunc nur mit unterschiedlicher Zielfunktion.

Answer 2

Hier ist, was ich vermute, das Problem, basierend auf meiner Erfahrung mit dieser Art von Problem. Sie verwenden eine dichte Darstellung für X anstelle von sparse. Sie sehen auch den typischen Effekt in der Textklassifizierung, dass die Anzahl der Begriffe ungefähr linear mit der Anzahl der Stichproben ansteigt. Effektiv steigen die Kosten der Matrixmultiplikation X*theta quadratisch mit der Anzahl der Abtastungen. Im Gegensatz dazu iteriert eine gute dünn besetzte Matrixdarstellung nur über die Nicht-Null-Elemente, um eine Matrixmultiplikation durchzuführen, die tendenziell pro Dokument ungefähr konstant ist, wenn sie von geeigneter konstanter Länge sind, was eine lineare statt quadratische Verlangsamung verursacht die Anzahl der Proben.

Ich bin kein Matlab Guru, aber ich weiß, es hat eine , also versuchen Sie es zu verwenden.

Answer 3

Ich konnte dies erreichen, indem ich das Flag LargeScale in fminunc() auf 'off' setzte. Soweit ich weiß, verwendet LargeScale = 'on' Trust-Region-Algorithmen, während 'Off' Quasi-Newton-Methoden verwendet. Quasi-Newton-Methoden zu verwenden und den Gradienten zu übergeben, hat bei diesem speziellen Problem viel schneller geklappt und sehr gute Ergebnisse gebracht.