gov.sandia.cognition.learning.algorithm.minimization

Class FunctionMinimizerGradientDescent

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>

gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<EvaluatorType,InputOutputPair<InputType,OutputType>>

gov.sandia.cognition.learning.algorithm.minimization.AbstractAnytimeFunctionMinimizer<Vector,java.lang.Double,DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>>

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

All Implemented Interfaces:

AnytimeAlgorithm<InputOutputPair<Vector,java.lang.Double>>, IterativeAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.Double>>, BatchLearner<DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.Double>>, FunctionMinimizer<Vector,java.lang.Double,DifferentiableEvaluator<? super Vector,java.lang.Double,Vector>>, CloneableSerializable, java.io.Serializable, java.lang.Cloneable

public class FunctionMinimizerGradientDescent
extends AbstractAnytimeFunctionMinimizer<Vector,java.lang.Double,DifferentiableEvaluator<? super Vector,java.lang.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

Fields

Modifier and Type	Field and Description
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

Constructors

Constructor and Description
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

Modifier and Type	Method and Description
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,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.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,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.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,java.lang.Double,Vector>,InputOutputPair<Vector,java.lang.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