golang-spsa: github.com/yanatan16/golang-spsa Index | Files

package spsa

import "github.com/yanatan16/golang-spsa"

Package spsa provides the Simultaneous Perturbation Stochastic Approximation method.

Much of the notation is taken from Introduction To Stochastic Search and Optimization (ISSO), James Spall's book on Stochastic Optimization. (published by Wiley 2003)

Example Usage:

This example uses the core optimization api with access to all the tunable knobs.

spsa := &SPSA{
	L: AbsoluteSum, // Loss Function
	C: NoConstraints,
	Theta: Vector{1,1,1,1,1},
	Ak: StandardAk(1, 100, .602),
	Ck: StandardCk(.1, .101),
	Delta: Bernoulli{1},
}
theta := spsa.Run(1000)

This example uses the helper function Optimize which shortens the boilerplate with default options.

theta := Optimize(AbsoluteSum/*Loss function*/, Vector{1,1,1,1,1}/*Theta0*/, 100/*n*/, 1/*a*/, .1/*c*/)

Index

Package Files

example_loss.go spsa.go vector.go

func AbsoluteSum Uses

func AbsoluteSum(v Vector) (a float64)

Basic absolute sum loss function which is used for testing

func Rosenbrock Uses

func Rosenbrock(v Vector) (a float64)

type Bernoulli Uses

type Bernoulli struct {
    // contains filtered or unexported fields
}

The bernoulli +/- r distribution.

func (Bernoulli) Sample Uses

func (b Bernoulli) Sample() float64

type BoundedConstraints Uses

type BoundedConstraints []Bounds

An array of bounds on an array of variables. This object's Constrain function can be used as a ConstraintFunction for SPSA.

func (BoundedConstraints) Constrain Uses

func (bc BoundedConstraints) Constrain(theta Vector) Vector

Constrain theta by mapping each value into its bounded domain. (in place)

type Bounds Uses

type Bounds struct {
    Lower, Upper float64
}

A pair of bounds on a variable. The first is the lower bound and the second is the upper bound

type ConstraintFunction Uses

type ConstraintFunction func(Vector) Vector

Map the parameter vector to a constrained version of itself.

type GainSequence Uses

type GainSequence <-chan float64

Gain sequences are infinite iterators of floats. The must follow the conditions specified in ISSO.

func StandardAk Uses

func StandardAk(a, A, alpha float64) GainSequence

Create an infinite iterator of a_k gain values in standard form. Standard form is a_k = a / (k + 1 + A) ^ alpha Semiauomatic tuning says that A should be roughly 10% of the iterations, and alpha should be .602. However, if running for a very long time, alpha = 1.0 might be more advantageous.

func StandardCk Uses

func StandardCk(c, gamma float64) GainSequence

Create an infinite iterator of c_k gain values in standard form. Standard form is c_k = c / (k + 1) ^ gamma Semiautomatic tuning says that c = sqrt(Var(L(x))) where L is the loss function being optimized. Gamma has restrictions based on alpha (see ISSO), but for best results in finite samples, use gamma = .101.

type LossFunction Uses

type LossFunction func(Vector) float64

A loss function is a vector-valued to real function. It will be minimized in SPSA. (Negate maximization functions to act as Loss functions.)

type PerturbationDistribution Uses

type PerturbationDistribution interface {
    Sample() float64
}

A perturbation distribution is used to simultaneously perturb the otimization criteria to approximate the loss function's gradient. It must have special properties, the most restrictive is E[1/X] is bounded. This rules out uniform and normal. The asymptotically optimal distribution is Bernoulli +/- 1.

type SPSA Uses

type SPSA struct {
    // The parameter vector in question. Initialize with Theta0 starting point.
    Theta Vector

    L      LossFunction
    Ak, Ck GainSequence
    Delta  PerturbationDistribution
    C      ConstraintFunction
}

An instance of the SPSA optimization algorithm. Initialize with all the parameters as object instantiation.

func (*SPSA) Run Uses

func (spsa *SPSA) Run(rounds int) Vector

Helper function to run many rounds of SPSA and return the current Theta value.

type SegmentedUniform Uses

type SegmentedUniform struct {
    // contains filtered or unexported fields
}

The segmented/mirrored uniform distribution. Samples with equal probability all real numbers in [a,b] U [-b,-a] where 0 < a < b.

func (SegmentedUniform) Sample Uses

func (su SegmentedUniform) Sample() float64

type Vector Uses

type Vector []float64

A simple real vector type for better readability. All operations are out-of-place.

func NoConstraints Uses

func NoConstraints(a Vector) Vector

A ConstraintFunction that is just the identity mapper

func Optimize Uses

func Optimize(L LossFunction, theta0 Vector, n int, a, c float64, C ...ConstraintFunction) Vector

A helper function to optimize a loss function using SPSA using mostly default options. It uses standard ak and ck gain sequences, bernoulli +/- 1 perturbation distribution and n rounds. The constraint function is optional.

func SampleN Uses

func SampleN(n int, d PerturbationDistribution) Vector

func (Vector) Add Uses

func (a Vector) Add(b Vector) Vector

Add a and b. (out of place)

func (Vector) Copy Uses

func (a Vector) Copy() Vector

Copy a to a new vector.

func (Vector) Mean Uses

func (a Vector) Mean() (m float64)

Mean of a

func (Vector) MeanSquare Uses

func (a Vector) MeanSquare() (x float64)

Mean squared of a

func (Vector) Scale Uses

func (a Vector) Scale(s float64) Vector

Scale a by s. Returns the new vector. (out of place)

func (Vector) String Uses

func (a Vector) String() (s string)

String form

func (Vector) Subtract Uses

func (a Vector) Subtract(b Vector) Vector

Add b from a. (out of place)

func (Vector) Sum Uses

func (a Vector) Sum() (s float64)

Sum a

func (Vector) Var Uses

func (a Vector) Var() (x float64)

Variance of a

Package spsa imports 3 packages (graph). Updated 2016-07-20. Refresh now. Tools for package owners.