Octave: régression logistique: différence entre fmincg et fminunc

contrairement à d'autres réponses ici suggérant que la différence principale entre fmincg et fminunc est la précision ou la vitesse, peut-être la différence la plus importante pour certaines applications est l'efficacité de la mémoire. Dans l'exercice de programmation 4 (c.-à-d., formation de réseau neuronal) de la classe de Machine D'Andrew Ng à Coursera, le commentaire dans ex4.m à propos de fmincg is

%% =================== Partie 8: la Formation NN ===================

% Vous avez maintenant mis en œuvre tout le code nécessaire pour former un neuronal

% réseau. Pour former votre réseau neuronal, nous allons maintenant utiliser "fmincg", qui

% est une fonction qui fonctionne de la même manière que "fminunc". Rappelons que ces

% optimiseurs avancés sont en mesure de former efficacement nos fonctions de coût comme

% tant que nous leur fournissons les calculs de gradient.

comme l'affiche originale, j'étais aussi curieux de savoir comment les résultats de ex4.m peut différer en utilisant fminunc au lieu de fmincg. J'ai donc essayé de remplacer l'appel fmincg

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

avec l'appel suivant à fminunc

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

mais a reçu le message d'erreur suivant d'une construction de 32 bits D'Octave tournant sur Windows:

erreur: mémoire épuisée ou taille demandée trop grande pour la portée de L'Octave index type -- essayer de revenir à l'invite

une compilation de 32 bits de MATLAB tournant sous Windows fournit un message d'erreur plus détaillé:

erreur en utilisant find

Hors de la mémoire. Tapez mémoire D'aide pour vos options.

Erreur dans les spones (ligne 14)

[i, j] = find (s);

Erreur de couleur (ligne 26)

J = spones (J);

Erreur dans sfminbx (ligne 155)

groupe = couleur (Hstr, p);

Erreur dans fminunc (ligne 408)

[x, FVAL,~, EXITFLAG,OUTPUT,GRAD,HESSIAN] = sfminbx(funfcn,x,l, u,...

Erreur dans ex4 (ligne 205)

[nn_params, cost, exit_flag] = fminunc (costFunction, initial_nn_params, options);

la mémoire MATLAB commande sur mon ordinateur portable rapports:

Maximum de la gamme: 2046 MO (2.146 e+09 octets) *

Mémoire disponible pour tous les tableaux: 3402 MB (3.568 E+09 octets) * *

Mémoire utilisée par MATLAB: 373 MB (3.910 E+08 octets)

Mémoire physique (RAM): 3561 MB (3.734 e+09 octets)

* Limité par un espace d'adresse virtuel contigu disponible.

** Limitée par l'espace d'adresse virtuelle disponible.

je pensais auparavant que le professeur Ng a choisi d'utiliser fmincg pour former le ex4.m réseau neuronal (doté de 400 fonctions d'entrée, 401 y compris l'entrée bias) pour augmenter la vitesse d'entraînement. Cependant, maintenant, je crois que sa raison d'utiliser fmincg était d'augmenter l'efficacité de la mémoire assez pour permettre l'entraînement à effectuer sur des constructions 32 bits D'Octave / MATLAB. Court discussion sur le travail nécessaire pour obtenir une construction 64 bits D'Octave qui fonctionne sur Windows OS est ici.

selon Andrew Ng lui-même, fmincg est utilisé pour ne pas obtenir un résultat plus précis (rappelez-vous, votre fonction de coût sera le même dans les deux cas, et votre hypothèse pas plus simple ou plus complexe), mais parce qu'il est plus efficace à faire descente gradient pour les hypothèses particulièrement complexes. Il semble lui-même utiliser fminunc où l'hypothèse a peu de caractéristiques, mais fmincg où il a des centaines.

pourquoi fmincg fonctionne-t-il?

Voici une copie du code source avec des commentaires expliquant les divers algorithmes utilisés. Il est un doozy, car il fait la même chose que le cerveau d'un enfant fait en apprenant à distinguer le chien et la chaise.

C'est la source D'Octave pour 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');

fmincg est plus précis que fminunc. Le temps pris par les deux est presque le même.Dans le réseau neuronal ou en général qui n'a plus de poids fminunc peut donner de l'erreur de mémoire.Donc fmincg est plus efficace de mémoire.

en utilisant fminunc, la précision est de 93.10 et le temps pris est de 11.3794 secondes.

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

en utilisant fmincg, la précision est de 95,12 et le temps pris est de 11,7978 secondes.

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

fmincg utilise le gradient conjugué la méthode

si vous regardez l'image à ce lien, vous verrez que la méthode CG converge beaucoup plus rapidement que fminunc, mais elle suppose un certain nombre de contraintes qui je pense ne sont pas nécessaires dans la méthode fminunc ( BFGS ) (vecteurs conjugués vs vecteurs non conjugués).

en d'autres termes, la méthode fmincg est plus rapide mais plus grossière que fminunc, donc il fonctionne mieux pour les grandes matrices (beaucoup de fonctionnalités, comme des milliers) vs les plus petites avec jusqu'à des centaines de fonctionnalités. Espérons que cette aide.