gov.sandia.cognition.learning.algorithm.minimization
Class FunctionMinimizerGradientDescent

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
          extended by gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>
              extended by gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<EvaluatorType,InputOutputPair<InputType,OutputType>>
                  extended by gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer<Vector,Double,DifferentiableEvaluator<? super Vector,Double,Vector>>
                      extended by gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizerGradientDescent
All Implemented Interfaces:
AnytimeAlgorithm<InputOutputPair<Vector,Double>>, IterativeAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<DifferentiableEvaluator<? super Vector,Double,Vector>,InputOutputPair<Vector,Double>>, BatchLearner<DifferentiableEvaluator<? super Vector,Double,Vector>,InputOutputPair<Vector,Double>>, FunctionMinimizer<Vector,Double,DifferentiableEvaluator<? super Vector,Double,Vector>>, CloneableSerializable, Serializable, Cloneable

public class FunctionMinimizerGradientDescent
extends AbstractAnytimeFunctionMinimizer<Vector,Double,DifferentiableEvaluator<? super Vector,Double,Vector>>

This is an implementation of the classic Gradient Descent algorithm, also known as Steepest Descent, Backpropagation (for neural nets), or Hill Climbing. This algorithm takes a small step in the direction indicated by the gradient. This implementation is "efficient" in that it only uses gradient calls during minimization (not function calls). We also use a momentum term to mimic "heavy ball" optimization to speed up learning and avoid local minima.

A few words of advice: Don't use this algorithm. I'm not one of those hard-core "gradient descent sucks" people, but there are uniformly better algorithms out there, such as BFGS and conjugate gradient. It's really here for illustrative purposes and essentially contains absolutely no advantage over BFGS or conjugate gradient minimization, except its simplicity. If you're looking for something quick and dirty, then be my guest. However, please consider using BFGS or CG instead. (CG is like GD, but where the momentum and step size are optimally selected for each step.) In my experience, non-derivative algorithms, like Powell's method, are more efficient and have better convergence than GD.

Oh, yeah. The other minimization algorithms don't require you to guess parameters either.

Since:
2.0
Author:
Kevin R. Dixon
See Also:
Serialized Form

Field Summary
static double DEFAULT_LEARNING_RATE
          Default learning rate
static int DEFAULT_MAX_ITERATIONS
          Default max iterations
static double DEFAULT_MOMENTUM
          Default momentum
static double DEFAULT_TOLERANCE
          Default tolerance
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer
initialGuess, result, tolerance
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner
data, keepGoing
 
Fields inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm
maxIterations
 
Fields inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
DEFAULT_ITERATION, iteration
 
Constructor Summary
FunctionMinimizerGradientDescent()
          Creates a new instance of FunctionMinimizerGradientDescent
FunctionMinimizerGradientDescent(double learningRate, double momentum)
          Creates a new instance of FunctionMinimizerGradientDescent
FunctionMinimizerGradientDescent(double learningRate, double momentum, Vector initialGuess, double tolerance, int maxIterations)
          Creates a new instance of FunctionMinimizerGradientDescent
 
Method Summary
protected  void cleanupAlgorithm()
          Called to clean up the learning algorithm's state after learning has finished.
 double getLearningRate()
          Getter for learningRate
 double getMomentum()
          Setter for momentum
protected  boolean initializeAlgorithm()
          Called to initialize the learning algorithm's state based on the data that is stored in the data field.
 void setLearningRate(double learningRate)
          Setter for learningRate
 void setMomentum(double momentum)
          Getter for momentum
protected  boolean step()
          Called to take a single step of the learning algorithm.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer
getInitialGuess, getResult, getTolerance, setInitialGuess, setResult, setTolerance
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner
clone, getData, getKeepGoing, learn, setData, setKeepGoing, stop
 
Methods inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm
getMaxIterations, isResultValid, setMaxIterations
 
Methods inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
addIterativeAlgorithmListener, fireAlgorithmEnded, fireAlgorithmStarted, fireStepEnded, fireStepStarted, getIteration, getListeners, removeIterativeAlgorithmListener, setIteration, setListeners
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface gov.sandia.cognition.learning.algorithm.minimization.FunctionMinimizer
learn
 
Methods inherited from interface gov.sandia.cognition.util.CloneableSerializable
clone
 
Methods inherited from interface gov.sandia.cognition.algorithm.AnytimeAlgorithm
getMaxIterations, setMaxIterations
 
Methods inherited from interface gov.sandia.cognition.algorithm.IterativeAlgorithm
addIterativeAlgorithmListener, getIteration, removeIterativeAlgorithmListener
 
Methods inherited from interface gov.sandia.cognition.algorithm.StoppableAlgorithm
isResultValid, stop
 

Field Detail

DEFAULT_LEARNING_RATE

public static final double DEFAULT_LEARNING_RATE
Default learning rate

See Also:
Constant Field Values

DEFAULT_MOMENTUM

public static final double DEFAULT_MOMENTUM
Default momentum

See Also:
Constant Field Values

DEFAULT_TOLERANCE

public static final double DEFAULT_TOLERANCE
Default tolerance

See Also:
Constant Field Values

DEFAULT_MAX_ITERATIONS

public static final int DEFAULT_MAX_ITERATIONS
Default max iterations

See Also:
Constant Field Values
Constructor Detail

FunctionMinimizerGradientDescent

public FunctionMinimizerGradientDescent()
Creates a new instance of FunctionMinimizerGradientDescent


FunctionMinimizerGradientDescent

public FunctionMinimizerGradientDescent(double learningRate,
                                        double momentum)
Creates a new instance of FunctionMinimizerGradientDescent

Parameters:
learningRate - The learning rate (or step size), must be (0,1], typically ~0.1
momentum - The momentum rate, must be [0,1), typically ~0.8

FunctionMinimizerGradientDescent

public FunctionMinimizerGradientDescent(double learningRate,
                                        double momentum,
                                        Vector initialGuess,
                                        double tolerance,
                                        int maxIterations)
Creates a new instance of FunctionMinimizerGradientDescent

Parameters:
learningRate - The learning rate (or step size), must be (0,1], typically ~0.1
momentum - The momentum rate, must be [0,1), typically ~0.8
initialGuess - Initial guess of the minimum
tolerance - Tolerance of the algorithm, must be >=0.0, typically 1e-5
maxIterations - Maximum number of iterations before stopping, must be >0, typically ~1000
Method Detail

initializeAlgorithm

protected boolean initializeAlgorithm()
Called to initialize the learning algorithm's state based on the data that is stored in the data field. The return value indicates if the algorithm can be run or not based on the initialization.

Specified by:
initializeAlgorithm in class AbstractAnytimeBatchLearner<DifferentiableEvaluator<? super Vector,Double,Vector>,InputOutputPair<Vector,Double>>
Returns:
True if the learning algorithm can be run and false if it cannot.

step

protected boolean step()
Called to take a single step of the learning algorithm.

Specified by:
step in class AbstractAnytimeBatchLearner<DifferentiableEvaluator<? super Vector,Double,Vector>,InputOutputPair<Vector,Double>>
Returns:
True if another step can be taken and false it the algorithm should halt.

cleanupAlgorithm

protected void cleanupAlgorithm()
Called to clean up the learning algorithm's state after learning has finished.

Specified by:
cleanupAlgorithm in class AbstractAnytimeBatchLearner<DifferentiableEvaluator<? super Vector,Double,Vector>,InputOutputPair<Vector,Double>>

getLearningRate

public double getLearningRate()
Getter for learningRate

Returns:
The learning rate (or step size), must be (0,1], typically ~0.1

setLearningRate

public void setLearningRate(double learningRate)
Setter for learningRate

Parameters:
learningRate - The learning rate (or step size), must be (0,1], typically ~0.1

getMomentum

public double getMomentum()
Setter for momentum

Returns:
The momentum rate, must be [0,1), typically ~0.8

setMomentum

public void setMomentum(double momentum)
Getter for momentum

Parameters:
momentum - The momentum rate, must be [0,1), typically ~0.8