wake-up-neo.com

Oktave: logistische Regression: Unterschied zwischen fmincg und fminunc

Ich benutze oft fminunc für ein logistisches Regressionsproblem. Ich habe im Web gelesen, dass Andrew Ngfmincg anstelle von fminunc mit den gleichen Argumenten verwendet. Die Ergebnisse sind unterschiedlich und oft fmincg ist genauer, aber nicht zu viel. (Ich vergleiche die Ergebnisse der fmincg-Funktion fminunc mit denselben Daten.)

Meine Frage ist also: Was ist der Unterschied zwischen diesen beiden Funktionen? Welchen Algorithmus hat jede Funktion implementiert? (Jetzt benutze ich diese Funktionen, ohne genau zu wissen, wie sie funktionieren.).

Vielen Dank :)

39
hqt

Sie müssen in den Code von fmincg schauen, da er nicht Teil von Octave ist. Nach einiger Suche fand ich heraus, dass es sich um eine Funktionsdatei handelt, die von der Machine Learning-Klasse von Coursera als Teil der Hausaufgaben bereitgestellt wird. Lesen Sie die Kommentare und Antworten zu dieser Frage für eine Diskussion über die Algorithmen.

41
carandraug

Im Gegensatz zu anderen Antworten, die hier darauf hinweisen, dass der Hauptunterschied zwischen fmincg und fminunc in der Genauigkeit oder Geschwindigkeit liegt, ist vielleicht der wichtigste Unterschied für einige Anwendungen die Speichereffizienz. In der Programmierübung 4 (d. H. Neuronales Netzwerktraining) der Machine Learning-Klasse von Andrew Ng bei Coursera lautet der Kommentar in ex4.m zu fmincg

Teil 8: Training NN =====================================================
% Sie haben jetzt den gesamten Code implementiert, der zum Trainieren eines Neuronalen benötigt wird
% Netzwerk. Um Ihr neuronales Netzwerk zu trainieren, verwenden wir jetzt "fmincg", welches
% ist eine Funktion, die ähnlich arbeitet wie "fminunc". Daran erinnern, dass diese
% fortschrittliche Optimierer können unsere Kostenfunktionen effizient trainieren
%, solange wir sie mit den Gradientenberechnungen versehen. 

Wie das Originalposter war ich auch neugierig, wie sich die Ergebnisse von ex4.m mit fminunc anstelle von fmincg unterscheiden können. Also habe ich versucht, den Fmincg-Aufruf zu ersetzen 

options = optimset('MaxIter', 50);
[nn_params, cost] = fmincg(costFunction, initial_nn_params, options);

mit dem folgenden Aufruf von fminunc

options = optimset('GradObj', 'on', 'MaxIter', 50);
[nn_params, cost, exit_flag] = fminunc(costFunction, initial_nn_params, options);

bekam aber die folgende Fehlermeldung aus einem 32-Bit-Build von Octave, der unter Windows ausgeführt wird:

fehler: Speicher ist erschöpft oder angeforderte Größe zu groß für den Octave-Indexbereich Typ - Versuch, zur Eingabeaufforderung zurückzukehren

Eine 32-Bit-Version von MATLAB, die unter Windows ausgeführt wird, enthält eine ausführlichere Fehlermeldung:

Fehler bei der Suche
Kein Speicher mehr. Geben Sie für Ihre Optionen HELP MEMORY ein.
Fehler in Spones (Zeile 14)
[i, j] = find (S);
Fehler in Farbe (Zeile 26)
J = Spones (J);
Fehler in sfminbx (Zeile 155)
Gruppe = Farbe (Hstr, p);
Fehler in fminunc (Zeile 408)
[x, FVAL, ~, EXITFLAG, OUTPUT, GRAD, HESSIAN] = sfminbx (funfcn, x, l, u, ...
Fehler in Ex4 (Zeile 205)
[nn_params, cost, exit_flag] = fminunc (costFunction, initial_nn_params, Optionen);

Der MATLAB-Speicherbefehl auf meinem Laptopcomputer meldet:

Maximal mögliches Array: 2046 MB (2.146e + 09 Byte) *
Für alle Arrays verfügbarer Speicher: 3402 MB (3.568e + 09 Byte) **
Von MATLAB verwendeter Speicher: 373 MB (3.910e + 08 Byte)
Physischer Speicher (RAM): 3561 MB (3.734e + 09 Byte)
* Begrenzt durch angrenzenden virtuellen Adressraum verfügbar.
** Begrenzt durch den verfügbaren virtuellen Adressraum. 

Ich dachte vorher, dass Professor Ng sich entschied, fmincg zu verwenden, um das neuronale ex4.m-Netzwerk (das 400 Eingangsmerkmale hat, 401 einschließlich des Bias-Eingangs), um die Trainingsgeschwindigkeit zu erhöhen. Ich glaube jedoch, dass sein Grund für die Verwendung von fmincg darin lag, die Speichereffizienz so zu erhöhen, dass das Training mit 32-Bit-Builds von Octave/MATLAB durchgeführt werden kann. Eine kurze Diskussion über die notwendige Arbeit, um einen 64-Bit-Build von Octave zu erhalten, der unter Windows läuft, ist hier.

22
gregS

Laut Andrew Ng selbst wird fmincg nicht verwendet, um ein genaueres Ergebnis zu erhalten (denken Sie daran, dass Ihre Kostenfunktion in beiden Fällen gleich ist und Ihre Hypothese nicht einfacher oder komplexer ist), sondern weil der Gradientenabstieg besonders effizient ist komplexe Hypothesen. Er selbst scheint fminunc zu verwenden, wo die Hypothese wenige Merkmale hat, aber fmincg, wo es Hunderte gibt.

11
Edward Dixon

Warum funktioniert fmincg?

Hier ist eine Kopie des Quellcodes mit Kommentaren, die die verschiedenen verwendeten Algorithmen erläutern. Es ist ein Dummkopf, da es dasselbe macht wie das Gehirn eines Kindes, wenn er lernt, zwischen Hund und Stuhl zu unterscheiden.

Dies ist die Octave-Quelle für fmincg.m.

function [X, fX, i] = fmincg(f, X, options, P1, P2, P3, P4, P5)
% Minimize a continuous differentialble multivariate function. Starting point
% is given by "X" (D by 1), and the function named in the string "f", must
% return a function value and a vector of partial derivatives. The Polack-
% Ribiere flavour of conjugate gradients is used to compute search directions,
% and a line search using quadratic and cubic polynomial approximations and the
% Wolfe-Powell stopping criteria is used together with the slope ratio method
% for guessing initial step sizes. Additionally a bunch of checks are made to
% make sure that exploration is taking place and that extrapolation will not
% be unboundedly large. The "length" gives the length of the run: if it is
% positive, it gives the maximum number of line searches, if negative its
% absolute gives the maximum allowed number of function evaluations. You can
% (optionally) give "length" a second component, which will indicate the
% reduction in function value to be expected in the first line-search (defaults
% to 1.0). The function returns when either its length is up, or if no further
% progress can be made (ie, we are at a minimum, or so close that due to
% numerical problems, we cannot get any closer). If the function terminates
% within a few iterations, it could be an indication that the function value
% and derivatives are not consistent (ie, there may be a bug in the
% implementation of your "f" function). The function returns the found
% solution "X", a vector of function values "fX" indicating the progress made
% and "i" the number of iterations (line searches or function evaluations,
% depending on the sign of "length") used.
%
% Usage: [X, fX, i] = fmincg(f, X, options, P1, P2, P3, P4, P5)
%
% See also: checkgrad
%
% Copyright (C) 2001 and 2002 by Carl Edward Rasmussen. Date 2002-02-13
%
%
% (C) Copyright 1999, 2000 & 2001, Carl Edward Rasmussen
%
% Permission is granted for anyone to copy, use, or modify these
% programs and accompanying documents for purposes of research or
% education, provided this copyright notice is retained, and note is
% made of any changes that have been made.
%
% These programs and documents are distributed without any warranty,
% express or implied.  As the programs were written for research
% purposes only, they have not been tested to the degree that would be
% advisable in any important application.  All use of these programs is
% entirely at the user's own risk.
%
% [ml-class] Changes Made:
% 1) Function name and argument specifications
% 2) Output display
%

% Read options
if exist('options', 'var') && ~isempty(options) && isfield(options, 'MaxIter')
    length = options.MaxIter;
else
    length = 100;
end

RHO = 0.01;                            % a bunch of constants for line searches
SIG = 0.5;       % RHO and SIG are the constants in the Wolfe-Powell conditions
INT = 0.1;    % don't reevaluate within 0.1 of the limit of the current bracket
EXT = 3.0;                    % extrapolate maximum 3 times the current bracket
MAX = 20;                         % max 20 function evaluations per line search
RATIO = 100;                                      % maximum allowed slope ratio

argstr = ['feval(f, X'];                      % compose string used to call function
for i = 1:(nargin - 3)
  argstr = [argstr, ',P', int2str(i)];
end
argstr = [argstr, ')'];

if max(size(length)) == 2, red=length(2); length=length(1); else red=1; end
S=['Iteration '];

i = 0;                                            % zero the run length counter
ls_failed = 0;                             % no previous line search has failed
fX = [];
[f1 df1] = eval(argstr);                      % get function value and gradient
i = i + (length<0);                                            % count epochs?!
s = -df1;                                        % search direction is steepest
d1 = -s'*s;                                                 % this is the slope
z1 = red/(1-d1);                                  % initial step is red/(|s|+1)

while i < abs(length)                                      % while not finished
  i = i + (length>0);                                      % count iterations?!

  X0 = X; f0 = f1; df0 = df1;                   % make a copy of current values
  X = X + z1*s;                                             % begin line search
  [f2 df2] = eval(argstr);
  i = i + (length<0);                                          % count epochs?!
  d2 = df2'*s;
  f3 = f1; d3 = d1; z3 = -z1;             % initialize point 3 equal to point 1
  if length>0, M = MAX; else M = min(MAX, -length-i); end
  success = 0; limit = -1;                     % initialize quanteties
  while 1
    while ((f2 > f1+z1*RHO*d1) | (d2 > -SIG*d1)) & (M > 0)
      limit = z1;                                         % tighten the bracket
      if f2 > f1
        z2 = z3 - (0.5*d3*z3*z3)/(d3*z3+f2-f3);                 % quadratic fit
      else
        A = 6*(f2-f3)/z3+3*(d2+d3);                                 % cubic fit
        B = 3*(f3-f2)-z3*(d3+2*d2);
        z2 = (sqrt(B*B-A*d2*z3*z3)-B)/A;       % numerical error possible - ok!
      end
      if isnan(z2) | isinf(z2)
        z2 = z3/2;                  % if we had a numerical problem then bisect
      end
      z2 = max(min(z2, INT*z3),(1-INT)*z3);  % don't accept too close to limits
      z1 = z1 + z2;                                           % update the step
      X = X + z2*s;
      [f2 df2] = eval(argstr);
      M = M - 1; i = i + (length<0);                           % count epochs?!
      d2 = df2'*s;
      z3 = z3-z2;                    % z3 is now relative to the location of z2
    end
    if f2 > f1+z1*RHO*d1 | d2 > -SIG*d1
      break;                                                % this is a failure
    elseif d2 > SIG*d1
      success = 1; break;                                             % success
    elseif M == 0
      break;                                                          % failure
    end
    A = 6*(f2-f3)/z3+3*(d2+d3);                      % make cubic extrapolation
    B = 3*(f3-f2)-z3*(d3+2*d2);
    z2 = -d2*z3*z3/(B+sqrt(B*B-A*d2*z3*z3));        % num. error possible - ok!
    if ~isreal(z2) | isnan(z2) | isinf(z2) | z2 < 0   % num prob or wrong sign?
      if limit < -0.5                               % if we have no upper limit
        z2 = z1 * (EXT-1);                 % the extrapolate the maximum amount
      else
        z2 = (limit-z1)/2;                                   % otherwise bisect
      end
    elseif (limit > -0.5) & (z2+z1 > limit)          % extraplation beyond max?
      z2 = (limit-z1)/2;                                               % bisect
    elseif (limit < -0.5) & (z2+z1 > z1*EXT)       % extrapolation beyond limit
      z2 = z1*(EXT-1.0);                           % set to extrapolation limit
    elseif z2 < -z3*INT
      z2 = -z3*INT;
    elseif (limit > -0.5) & (z2 < (limit-z1)*(1.0-INT))   % too close to limit?
      z2 = (limit-z1)*(1.0-INT);
    end
    f3 = f2; d3 = d2; z3 = -z2;                  % set point 3 equal to point 2
    z1 = z1 + z2; X = X + z2*s;                      % update current estimates
    [f2 df2] = eval(argstr);
    M = M - 1; i = i + (length<0);                             % count epochs?!
    d2 = df2'*s;
  end                                                      % end of line search

  if success                                         % if line search succeeded
    f1 = f2; fX = [fX' f1]';
    fprintf('%s %4i | Cost: %4.6e\r', S, i, f1);
    s = (df2'*df2-df1'*df2)/(df1'*df1)*s - df2;      % Polack-Ribiere direction
    tmp = df1; df1 = df2; df2 = tmp;                         % swap derivatives
    d2 = df1'*s;
    if d2 > 0                                      % new slope must be negative
      s = -df1;                              % otherwise use steepest direction
      d2 = -s'*s;
    end
    z1 = z1 * min(RATIO, d1/(d2-realmin));          % slope ratio but max RATIO
    d1 = d2;
    ls_failed = 0;                              % this line search did not fail
  else
    X = X0; f1 = f0; df1 = df0;  % restore point from before failed line search
    if ls_failed | i > abs(length)          % line search failed twice in a row
      break;                             % or we ran out of time, so we give up
    end
    tmp = df1; df1 = df2; df2 = tmp;                         % swap derivatives
    s = -df1;                                                    % try steepest
    d1 = -s'*s;
    z1 = 1/(1-d1);
    ls_failed = 1;                                    % this line search failed
  end
  if exist('OCTAVE_VERSION')
    fflush(stdout);
  end
end
fprintf('\n');
8
Eric Leschinski

fmincg verwendet die konjugierte Gradientenmethode

Wenn Sie das Bild unter diesem Link betrachten, werden Sie feststellen, dass die CG-Methode viel schneller konvergiert als fminunc, jedoch eine Reihe von Einschränkungen, die meiner Meinung nach in der fminunc-Methode nicht erforderlich sind ( BFGS ) ( konjugierte Vektoren vs. nicht-konjugierte Vektoren).

Mit anderen Worten, die fmincg-Methode ist schneller, aber gröber als fminunc, sodass sie für große Matrizen (viele Funktionen, z. B. Tausende) besser geeignet ist als für kleinere mit bis zu Hunderten von Funktionen .. __Hoffentlich hilft das.

1
Sv Vr

fmincg ist genauer als fminunc. Die Zeit, die von beiden benötigt wird, ist fast gleich. Neural Network oder im Allgemeinen, das keine Gewichte mehr hat, kann fminunc aus dem Speicherfehler ergeben. So ist fmincg speichereffizienter.  

Bei Verwendung von fminunc beträgt die Genauigkeit 93,10 und die benötigte Zeit beträgt 11,3794 Sekunden.

Testing lrCostFunction() with regularization
Cost: 2.534819
Expected cost: 2.534819
Gradients:
 0.146561
 -0.548558
 0.724722
 1.398003
Expected gradients:
 0.146561
 -0.548558
 0.724722
 1.398003
Program paused. Press enter to continue.

Training One-vs-All Logistic Regression...
id = 1512324857357
Elapsed time is 11.3794 seconds.
Program paused. Press enter to continue.

Training Set Accuracy: 93.100000

Bei Verwendung von fmincg beträgt die Genauigkeit 95,12 und die benötigte Zeit beträgt 11,7978 Sekunden.

Testing lrCostFunction() with regularization
Cost: 2.534819
Expected cost: 2.534819
Gradients:
 0.146561
 -0.548558
 0.724722
 1.398003
Expected gradients:
 0.146561
 -0.548558
 0.724722
 1.398003
Program paused. Press enter to continue.

Training One-vs-All Logistic Regression...
id = 1512325280047
Elapsed time is 11.7978 seconds.

Training Set Accuracy: 95.120000
1
Goyal Vicky

Die Verwendung von fmincg zur Optimierung der Kostenfunktion fmincg funktioniert ähnlich wie fminunc, ist jedoch effizienter, wenn es sich um eine große Anzahl von Parametern handelt. Ihre Kostenfunktion ist in beiden Fällen gleich und Ihre Hypothese ist weder einfacher noch komplexer. Sie ist jedoch effizienter, wenn Sie für besonders komplexe Hypothesen einen Gradientenabstieg durchführen. 

Es wird für eine effiziente Speichernutzung verwendet.

0
tonystark117

fmincg ist eine interne Funktion, die von Coursera entwickelt wurde, im Gegensatz zu fminunc, der eine eingebaute Oktavfunktion besitzt. Da beide für die logistische Regression verwendet werden, unterscheiden sie sich nur in einem Aspekt. Wenn die Anzahl der zu berücksichtigenden Parameter beträchtlich groß ist (im Vergleich zur Größe des Trainingssatzes oder nicht), arbeitet fmincg schneller und verarbeitet genauer als fminunc. Und fminunc wird bevorzugt, wenn die Parameter, die an fminunc übergeben werden, nicht eingeschränkt sind.

0
a_ran