Copyright | (c) Justin Le 2017 |
---|---|

License | BSD3 |

Maintainer | justin@jle.im |

Stability | experimental |

Portability | non-portable |

Safe Haskell | None |

Language | Haskell2010 |

Offers full functionality for implicit-graph back-propagation with
monomorphic inputs. The intended usage is to write a `BPOp`

, which is
a normal Haskell function from `BVar`

s to a result `BVar`

. These `BVar`

s
can be manipulated using their `Num`

* Fractional *

`Floating`

instances.The library can then perform back-propagation on the function (using
`backprop`

or `grad`

) by using an implicitly built graph.

This is an "implicit-only" version of Numeric.Backprop.Mono, and a monomorphic version of Numeric.Backprop.Implicit, monomorphic in the sense that all of the inputs are of the same type.

Like for Numeric.Backprop.Implicit, this should actually be powerful
enough for most use cases, but falls short because without explicit
graph capabilities, recomputation can sometimes be inevitable. If the
result of a function on `BVar`

s is used twice (like `z`

in ```
let
z = x * y in z + z
```

), this will allocate a new redundant graph node for
every usage site of `z`

. You can explicitly *force* `z`

, but only using
an explicit graph description using Numeric.Backprop.Mono.

Like Numeric.Backprop.Implicit, this can't handle sum types, but neither can Numeric.Backprop.Mono, so no loss here :)

This module implements pretty much the same functionality as
Numeric.AD and Numeric.AD.Mode.Reverse from the *ad* package,
because it uses the same implicit-graph back-propagation method. It
can't compute jacobians/generalized gradients, however. This isn't
a fundamental limitation of the implementaiton, though, but rather just
a conscious design decision for this module's API.

- type BVar s n a = BVar s (Replicate n a)
- type BPOp n a b = forall s. VecT n (BVar s n a) a -> BVar s n a b
- type Op n a b = Op (Replicate n a) b
- type OpB s n a b = OpB s (Replicate n a) b
- data VecT k n f a :: forall k. N -> (k -> *) -> k -> * where
- type Vec n = VecT * n I
- newtype I a :: * -> * = I {
- getI :: a

- backprop :: forall n a b. (Num a, Known Nat n) => BPOp n a b -> Vec n a -> (b, Vec n a)
- grad :: forall n a b. (Num a, Known Nat n) => BPOp n a b -> Vec n a -> Vec n a
- eval :: forall n a b. (Num a, Known Nat n) => BPOp n a b -> Vec n a -> b
- constVar :: a -> BVar s n r a
- liftB :: forall s m n a b r. OpB s m a b -> VecT m (BVar s n r) a -> BVar s n r b
- (.$) :: forall s m n a b r. OpB s m a b -> VecT m (BVar s n r) a -> BVar s n r b
- liftB1 :: OpB s N1 a a -> BVar s n r a -> BVar s n r a
- liftB2 :: OpB s N2 a a -> BVar s n r a -> BVar s n r a -> BVar s n r a
- liftB3 :: OpB s N3 a a -> BVar s n r a -> BVar s n r a -> BVar s n r a -> BVar s n r a
- op1 :: Num a => (forall s. AD s (Forward a) -> AD s (Forward a)) -> Op N1 a a
- op2 :: Num a => (forall s. Reifies s Tape => Reverse s a -> Reverse s a -> Reverse s a) -> Op N2 a a
- op3 :: Num a => (forall s. Reifies s Tape => Reverse s a -> Reverse s a -> Reverse s a -> Reverse s a) -> Op N3 a a
- opN :: (Num a, Known Nat n) => (forall s. Reifies s Tape => Vec n (Reverse s a) -> Reverse s a) -> Op n a a
- pattern (:+) :: forall a n. a -> Vec n a -> Vec (S n) a
- (*:) :: f a -> f a -> VecT k (S (S Z)) f a
- (+:) :: a -> a -> Vec (S (S Z)) a
- head' :: VecT k (S n) f a -> f a
- type N0 = Z
- type N1 = S N0
- type N2 = S N1
- type N3 = S N2
- type N4 = S N3
- type N5 = S N4
- type N6 = S N5
- type N7 = S N6
- type N8 = S N7
- type N9 = S N8
- type N10 = S N9

# Types

## Backprop types

type BVar s n a = BVar s (Replicate n a) Source #

The basic unit of manipulation inside `BP`

(or inside an
implicit-graph backprop function). Instead of directly working with
values, you work with `BVar`

s contating those values. When you work
with a `BVar`

, the *backprop* library can keep track of what values
refer to which other values, and so can perform back-propagation to
compute gradients.

A

refers to a value of type `BVar`

s n r a`a`

, with an environment
of `n`

values of type `r`

. The phantom parameter `s`

is used to
ensure that stray `BVar`

s don't leak outside of the backprop process.

(That is, if you're using implicit backprop, it ensures that you interact
with `BVar`

s in a polymorphic way. And, if you're using explicit
backprop, it ensures that a

never leaves the `BVar`

s n r a

that it was created in.)`BP`

s n r

`BVar`

s have `Num`

, `Fractional`

, `Floating`

, etc. instances, so they
can be manipulated using polymorphic functions and numeric functions in
Haskell. You can add them, subtract them, etc., in "implicit" backprop
style.

(However, note that if you directly manipulate `BVar`

s using those
instances or using `liftB`

, it delays evaluation, so every usage site
has to re-compute the result/create a new node. If you want to re-use
a `BVar`

you created using `+`

or `-`

or `liftB`

, use
`bindVar`

to force it first. See documentation for
`bindVar`

for more details.)

type BPOp n a b = forall s. VecT n (BVar s n a) a -> BVar s n a b Source #

An operation on `BVar`

s that can be backpropagated. A value of type:

`BPOp`

n r a

takes a vector (`VecT`

) of `BVar`

s containg `n`

`r`

s and uses them to
(purely) produce a `BVar`

containing an `a`

.

foo ::`BPOp`

`N2`

Double Double foo (x`:*`

y`:*`

'ØV') = x + sqrt y

`BPOp`

here is related to `BPOpI`

from the normal
explicit-graph backprop module Numeric.Backprop.Mono.

type Op n a b = Op (Replicate n a) b Source #

An

describes a differentiable function from `Op`

n a b`n`

values of
type `a`

to a value of type `b`

.

For example, a value of type

`Op`

`N2`

Int Double

is a function that takes two `Int`

s and returns a `Double`

.
It can be differentiated to give a *gradient* of two `Int`

s, if given
a total derivative for the `Double`

. Mathematically, it is akin to a:

\[ f : \mathbb{Z}^2 \rightarrow \mathbb{R} \]

See `runOp`

, `gradOp`

, and `gradOpWith`

for examples on how to run it,
and `Op`

for instructions on creating it.

This type is abstracted over using the pattern synonym with constructor
`Op`

, so you can create one from scratch with it. However, it's
simplest to create it using `op2'`

, `op1'`

, `op2'`

, and `op3'`

helper
smart constructors And, if your function is a numeric function, they
can even be created automatically using `op1`

, `op2`

, `op3`

, and `opN`

with a little help from Numeric.AD from the *ad* library.

Note that this type is a *subset* or *subtype* of `OpM`

(and also of
`OpB`

). So, if a function ever expects an

(or a `OpM`

m as a`OpB`

), you can always provide an

instead.`Op`

as a

Many functions in this library will expect an

(or
an `OpM`

m as a

), and in all of these cases, you can
provide an `OpB`

s as a

.`Op`

as a

type OpB s n a b = OpB s (Replicate n a) b Source #

A subclass of `OpM`

(and superclass of `Op`

),
representing `Op`

s that the *backprop* library uses to perform
backpropation.

An

`OpB`

s n a b

represents a differentiable function that takes a `n`

values of type `a`

produces an a `b`

, which can be run on

s and also inside
`BVar`

s

s. For example, an `BP`

s

takes two `OpB`

s `N2`

Double Bool`Double`

s
and produces a `Bool`

, and does it in a differentiable way.

`OpB`

is a *superset* of `Op`

, so, if you see any function that expects
an `OpB`

(like `opVar'`

and `~$`

, for
example), you can give them an `Op`

, as well.

You can think of `OpB`

as a superclass/parent class of `Op`

in this
sense, and of `Op`

as a subclass of `OpB`

.

## Vectors

See Numeric.Backprop.Mono for a mini-tutorial on `VecT`

and
`Vec`

data VecT k n f a :: forall k. N -> (k -> *) -> k -> * where #

Functor1 l l (VecT l n) | |

Foldable1 l l (VecT l n) | |

Traversable1 l l (VecT l n) | |

Witness ØC (Known N Nat n) (VecT k n f a) | |

(Monad f, Known N Nat n) => Monad (VecT * n f) | |

Functor f => Functor (VecT * n f) | |

(Applicative f, Known N Nat n) => Applicative (VecT * n f) | |

Foldable f => Foldable (VecT * n f) | |

Traversable f => Traversable (VecT * n f) | |

Eq (f a) => Eq (VecT k n f a) | |

(Num (f a), Known N Nat n) => Num (VecT k n f a) | |

Ord (f a) => Ord (VecT k n f a) | |

Show (f a) => Show (VecT k n f a) | |

type WitnessC ØC (Known N Nat n) (VecT k n f a) | |

# back-propagation

# Var manipulation

liftB :: forall s m n a b r. OpB s m a b -> VecT m (BVar s n r) a -> BVar s n r b Source #

Apply `OpB`

over a `VecT`

of `BVar`

s, as inputs. Provides "implicit"
back-propagation, with deferred evaluation.

If you had an

, this function will expect a vector of of
three `OpB`

s N3 a b

s, and the result will be a `BVar`

s n r a

:`BVar`

s n r b

myOp ::`OpB`

s N3 a b x ::`BVar`

s n r a y ::`BVar`

s n r a z ::`BVar`

s n r a x`:*`

y :* z :* 'ØV' ::`VecT`

N3 (`BVar`

s n r) a`liftB`

myOp (x :* y :* z :* ØV) ::`BVar`

s n r b

Note that `OpB`

is a superclass of `Op`

, so you can provide any `Op`

here, as well (like those created by `op1`

, `op2`

, `constOp`

, `op0`

etc.)

`liftB`

has an infix alias, `.$`

, so the above example can also be
written as:

myOp`.$`

(x :* y :* z :* ØV) ::`BVar`

s n r b

to let you pretend that you're applying the `myOp`

function to three
inputs.

The result is a new *deferred* `BVar`

. This should be fine in most
cases, unless you use the result in more than one location. This will
cause evaluation to be duplicated and multiple redundant graph nodes to
be created. If you need to use it in two locations, you should use
`opVar`

instead of `liftB`

, or use `bindVar`

:

`opVar`

o xs =`bindVar`

(`liftB`

o xs)

`liftB`

can be thought of as a "deferred evaluation" version of `opVar`

.

(.$) :: forall s m n a b r. OpB s m a b -> VecT m (BVar s n r) a -> BVar s n r b Source #

Infix synonym for `liftB`

, which lets you pretend that you're applying
`OpB`

s as if they were functions:

myOp ::`OpB`

s N3 a b x ::`BVar`

s n r a y ::`BVar`

s n r a z ::`BVar`

s n r a x`:*`

y :* z :* 'ØV' ::`VecT`

N3 (`BVar`

s n r) a myOp`.$`

(x :* y :* z :* ØV) ::`BVar`

s n r b

Note that `OpB`

is a superclass of `Op`

, so you can pass in any `Op`

here, as well (like those created by `op1`

, `op2`

, `constOp`

, `op0`

etc.)

See the documentation for `liftB`

for all the caveats of this usage.

`.$`

can also be thought of as a "deferred evaluation" version of `~$`

:

o`~$`

xs =`bindVar`

(o`.$`

xs)

liftB1 :: OpB s N1 a a -> BVar s n r a -> BVar s n r a Source #

Convenient wrapper over `liftB`

that takes an `OpB`

with one argument
and a single `BVar`

argument. Lets you not have to type out the entire
`VecT`

.

`liftB1`

o x =`liftB`

o (x`:*`

'ØV') myOp ::`Op`

N2 a b x ::`BVar`

s n r a`liftB1`

myOp x ::`BVar`

s n r b

Note that `OpB`

is a superclass of `Op`

, so you can pass in an `Op`

here
(like one made with `op1`

) as well.

See the documentation for `liftB`

for caveats and potential problematic
situations with this.

liftB2 :: OpB s N2 a a -> BVar s n r a -> BVar s n r a -> BVar s n r a Source #

Convenient wrapper over `liftB`

that takes an `OpB`

with two arguments
and two `BVar`

arguments. Lets you not have to type out the entire
`VecT`

.

`liftB2`

o x y =`liftB`

o (x`:*`

y`:*`

'ØV') myOp ::`Op`

N2 a b x ::`BVar`

s n r a y ::`BVar`

s n r b`liftB2`

myOp x y ::`BVar`

s n r b

Note that `OpB`

is a superclass of `Op`

, so you can pass in an `Op`

here
(like one made with `op2`

) as well.

See the documentation for `liftB`

for caveats and potential problematic
situations with this.

liftB3 :: OpB s N3 a a -> BVar s n r a -> BVar s n r a -> BVar s n r a -> BVar s n r a Source #

Convenient wrapper over `liftB`

that takes an `OpB`

with three arguments
and three `BVar`

arguments. Lets you not have to type out the entire
`Prod`

.

`liftB3`

o x y z =`liftB`

o (x`:*`

y`:*`

z`:*`

'ØV') myOp ::`Op`

N3 a b x ::`BVar`

s n r a y ::`BVar`

s n r b z ::`BVar`

s n r b`liftB3`

myOp x y z ::`BVar`

s n r b

Note that `OpB`

is a superclass of `Op`

, so you can pass in an `Op`

here
(like one made with `op3`

) as well.

See the documentation for `liftB`

for caveats and potential problematic
situations with this.

# Op

op2 :: Num a => (forall s. Reifies s Tape => Reverse s a -> Reverse s a -> Reverse s a) -> Op N2 a a Source #

op3 :: Num a => (forall s. Reifies s Tape => Reverse s a -> Reverse s a -> Reverse s a -> Reverse s a) -> Op N3 a a Source #

opN :: (Num a, Known Nat n) => (forall s. Reifies s Tape => Vec n (Reverse s a) -> Reverse s a) -> Op n a a Source #