Optimization

The problem of optimizing the neural network costfunction is usually a nonlinear static unconstrained optimization problem.

Nonlinear meaning that it is usually not possible to solve the problem directly, --- instead iterative schemes must be applied.

There is usually no temporal state involved in the feed-forward neural network. The patterns are treated as independent. Therefore is the problem static.

Unconstrained meaning that the variables to be optimized is not bounded, --- for example that they should be positive. This is in regard to the costfunction. Optimization of the errorfunction may be regarded as a constrained optimization where the constraints are imposed by the regularization. Fortunately the constraints are differentiable, so the constraints are easily added to the errorfunction giving the costfunction.

The optimization in connection with neural network usually called training or learning. Each of the iterative steps is called an epoch.

For an optimization methods 3 efficiency measures may be given [62]:

• Robustness. This concerns the methods ability to convergence and converge to the global minimum: global convergence. In neural network optimization the global minimum is not exclusive. A ''good'' local minimum is sufficient.

• Speed of convergence. This describes how much the optimization is improving the weights from epoch to epoch. Often this is by the terms: Linear, superlinear and quadratic [62].

   

  One may say that linear convergence is where the number of determined ciphers increase linearly with the epochs, and that quadratic convergence is where the number increase quadratic.

• Complexity of computation. This is a measure of what the single epoch --- a single step --- of the iterative optimization take of time. The value can be given in the big-O notation. The complexity of computation is first of all dependant upon the number of variables under optimization and the required functions: the ordinary function value, the first order derivative, and the second order derivative. A other complexity measure for the optimization is the store complexity, but neural network optimization the use of storage is usually of no importance.

The speed of convergence and the complexity of computation usually work opposite --- it is just a question of where to put the epoch. If the 2 values are ''multiplied'' together we get the time consume of the algorithm. Often the robustness fight against the time consume. This is because a robust algorithm often works not so locally, uses more points, where the function is evaluated.

Some algorithms are only robust with a convex costfunction, that is where the Hessian is positive definite. The neural network costfunction --- especially a unregularized --- is not convex. To get both robustness and a fair time consume optimization methods can be mixed forming a hybrid optimization methods.

• Exhaustive search. By exhaustive search I mean the systematic search of all possible states. If the variables are unlimited the number of states must be restricted be the help of some prior knowledge. With continuous valued weights a finite number of states can be obtained with a grid search strategy. After the computation of the function values in the grid points, we might interpolate and find a better minimum between the gridlines.

• Random search. The technique of random search is also called monte carlo: Start out with a number of random weights and hope that some of them wins --- having a low function value. If the best is picked and mutated, that is some noise is added to the weights, we end up with a new group of weights in the surroundings of the ancestor. Hopefully one of them is better. This is then used in a new mutation. Critical is the size of the standard deviation of the noise used in the mutation.

• Amoeba. The Nelder-May method [60] uses only the functional value, --- no derivatives. If the weight space under optimization is of dimension it will need function evaluations. These are the vertices in a simplex --- a irregular shaped sort of prism. The vertex having the largest function value is mirror in the hyperplane the other vertices spans. This creates a new simplex, where a new vertex with the highest function value now can be mirror. The simplex --- also called amoeba --- should gradually move downhill.

• Gradient descent.  If the costfunction is decreasing in a direction --- the negative gradient direction --- a step can be taking a that direction (of course!) If the step is kept fixed at a value we arrive at the ordinary backprobagation:

   

  The problem with backpropagation is that if the step is too small, the convergence is to slow, and if it is to large, it is not certain that the costfunction will decrease: We might land on the opposite side of the costfunction valley. By using soft line search, where we start off with a large a gradually decrease it until the costfunction is decreased, we can get both improvement in the robustness and the speed of convergence, but at the cost of more complexity of computation. If the line search is hard, that is the optimal step size is found, we end up with steepest descent:

   

  This is usually not worth the effort, compared to soft line search.

  Some curvature information can be obtained if the old step is used in backpropagation with momentum:

   

  A problem with the gradient descent is that all directions share the same step size. This is a problem with stiff functions, that is functions with a long shallow valley in one direction and a short steep valley in an other. In mathematical terms this means that the ratio between the largest and the smallest Hessian eigenvalue is big. The step size has to be fitted to the short steep valley, not to bump into its valley side.

  Neural network costfunction are often stiff because the inputs have different importance for the outputs. Consider the neural network input of principal components: The first one should be of importance, while the higher should be noise that should be ignored.

  The gradient descent algorithms have linear convergence.

• Conjugate gradient methods and Quasi-newton methods. These 2 methods tries to bend the gradient direction by remembering in smart ways the gradient from epoch to epoch. Some of the algorithms in this domain is Fletcher-Reeves, Polak-Ribiere, BFGS, DFP and scaled conjugate gradient [52] [62] [60]. These types of have superlinear convergence.

• Newton methods.  Newton methods are where the second order derivative - or part of it --- is computed directly, that is not by approximations found through the use of the first order derivative. The pure newton multiply the inverted costfunction Hessian with the costfunction gradient:

   

  The pure newton is not robust, because the Hessian might not be positive definite, that is the cost function is not fully convex. If the costfunction is concave in one dimension it will take a step uphill. Using the gauss-newton approximation4.6.2 the Hessian automatically becomes positive definite (or at least semi-positive definite). If the pseudo approximation is used the matrix inversion of 4.67 is replaced by an element-by-element division:

  

  If the costfunction surface is ''hyperparaboloidic'', one newton step will immediately bring the weights to their optimal sizes. The costfunction surface has to have axis-parallel cross sections of the hyperparaboloide for that to happen with the pseudo-newton approximation.

  Usually the costfunction is certainly not hyperparaboloidic and we have to take several steps. The costfunction can be of such a type, that the newton methods take a too large step, crossing the valley, and getting a worser costfunction value. In parallel with the gradient descent methods, some of the cure for this behavior is soft line search. To make the newton method yet more robust the failed newton step can be followed by a gradient descent step.

  The Levenberg-Marquardt method uses the gauss-newton approximation step and the usual gradient descent step in a combination:

   

  The is here the identity matrix. Thus the Levenberg-Marquardt approximation is a interpolating between the gauss-newton step and a infinitely small gradient step with the parameter . The parameter functions as a sort of line search parameter, and is stored from epoch to epoch.

  It seems to me that this method requires matrix inversions in the line search.

  The pure newton has quadratic convergence for convex costfunctions [62].

• Direct methods. For some of the optimization problems in the neural network there are actually direct methods. For the linear output activation function the output weights is linear parameters, and with the square errorfunction it is the standard problem of least square, where the normal equation  can be employed [45] [48]:

   

  This is actually just the pure newton. Correlation among the outputs (see the equation 4.36) is no further problem:

  

  Neither is the augmentation of the square weight decay. In this case we end up with the ridge regression:

   

• Batch or on-line training
• Initialization